Optimization of load-balanced file allocation
Lin-Wen Chen Lee · 1995
This work is concerned with optimum file allocation in a distributed file system that consists of M identical file servers on a local area network serving file retrieval traffic to and from user stations. The files are characterized by their access rates and service times while the servers are represented by an open queuing network model. The files are to be assigned to the servers such that the server loads are balanced and the mean server response time is minimized. We propose and analyze a load-balanced file allocation algorithm, called that assigns files in order of their service times in such a manner that the service time of any file in Server k is no less than the service time of any file in Server k + 1. We proved by induction that this algorithm is optimum under the assumption that file access rate is a non-increasing function of file service time. Without any constraints on file access rates and service times, we then exploit the performance characteristics of SORT-PARTITION. Specifically, based on a performance bound, we derive a worst-case performance for any given load-balanced file allocation. We then show that SORT-PARTITION has the best performance ratio of all. We also present an on-line version of Algorithm SORT-PARTITION which assigns files to the servers on a first-come-first-serve basis. This algorithm seeks to minimize file movements between servers and maintains load-balancing within a maximum deviation of one file. Finally, we study some file allocation problems that involve caching. For a server with a given cache space, it is shown that caching the files with the largest service times minimizes the mean response time while caching the files with the smallest service times maximizes the cache hit probability and minimizes server load under the assumption that file access rates are non-increasing with file service times. In allocating a given quantity of cache to multiple servers, we show that focusing the cache on a minimum number of servers yields the best mean response time results.