On-line load balancing in a hierarchical server topology
In a hierarchical server environment jobs are to be assigned in an on-line fashion to a collection of servers which form a hierarchy of capability: each job requests a specific server meeting its needs, but the system is free to assign it either to that server or to any other server higher in the hierarchy. Each job carries a certain load, which it imparts to the server it is assigned to. The goal is to nd a competitive assignment in which the maximum total load on a server is minimized. We consider the linear hierarchy in which the servers are totally ordered in terms of their capabilities. We investigate several variants of the problem. In the unweighted ( as opposed to weighted) problem all jobs have unit weight. In the fractional ( as opposed to integral) model a job may be assigned to several servers, each receiving some fraction of its weight. Finally, temporary ( as opposed to permanent) jobs may depart after being active for some finite duration of time. We show an optimal e-competitive algorithm for the unweighted integral permanent model. The same algorithm is (e+1)-competitive in the weighted case. Its fractional version is e-competitive even if temporary jobs are allowed. or the integral model with temporary jobs we show an algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case. We show a lower bound of e for the unweighted case ( both integral and fractional). This bound is valid even with respect to randomized algorithms. We also show a lower bound of 3 for the unweighted integral model when temporary jobs are allowed. We generalize the problem and consider hierarchies in which the servers form a tree. In the tree hierarchy, any job assignable to a node is also assignable to the node's ancestors. We show a deterministic algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case, where only permanent jobs are allowed. Randomizing this algorithm improves its competitiveness to e and e+1, respectively. We also show an (n) lower bound when temporary jobs are allowed.
load balancing hierarchical servers temporary jobs on-line algorithms resource procurement