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: ea ch 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 hi erarchy. 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 ma ximum total load on a server is minimized. We consider the linear hierarchy in which the servers are totally ordered i n terms of their capabilities. We investigate several variants of the probl em. 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 assi gned to several servers, each receiving some fraction of its weight. Finall y, temporary ( as opposed to permanent) jobs may depart after being active for some finite duration of time. We show an optimal e-competitive algorith m for the unweighted integral permanent model. The same algorithm is (e+1)- competitive in the weighted case. Its fractional version is e-competitive e ven if temporary jobs are allowed. or the integral model with temporary job s 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 unweig hted case ( both integral and fractional). This bound is valid even with re spect to randomized algorithms. We also show a lower bound of 3 for the unw eighted integral model when temporary jobs are allowed. We generalize the problem and consider hierarchies in which the servers for m a tree. In the tree hierarchy, any job assignable to a node is also assig nable 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.