Online Bicriteria Load Balancing Using Object Reallocation

摘要

We study the bicriteria load balancing problem on two independent parameters under the allowance of object reallocation. The scenario is a system of $M$ distributed file servers located in a cluster, and we propose three online approximate algorithms for balancing their loads and required storage spaces during document placement. The first algorithm is for heterogeneous servers. Each server has its individual tradeoff of load and storage space under the same rule of selection. The other two algorithms are for homogeneous servers. The second algorithm combines the idea of the first one and the best existing solution for homogeneous servers. Using document reallocation, we obtain a smooth tradeoff curve of the upper bounds of load and storage space. The last one bounds the load and storage space of each server by less than three times of their trivial lower bounds, respectively; and more importantly, for each server, the value of at least one parameter is far from its worst case. The time complexities of these three algorithms are $O(log M)$ plus the cost of document reallocation.