COMPETITIVE ANALYSIS OF NETWORK LOAD BALANCING

This paper presents a theoretical analysis of the Load Balancing Probl em (LBP) in a network of processing units. The performance objective i s to minimize the makespan, i.e., the time spent to finish all jobs in a network of processing units. Because of the communication delay tha t results from the network topology, it is impossible to have a strate gy which obtains the exact optimum under all load distributions. Inste ad, we measure the information efficiency of a load balancing policy b y the worst case ratio of the solution (for each load distribution) of a load balancing policy to the optimal solution (for the same load di stribution) assuming that processors have complete information about t he load distribution over the network. This ratio is called the compet itive ratio of this strategy [17, 24, 34]. In particular, a policy is called competitive if this ratio is bounded by a constant. As a first step, we discuss the centralized LBP, where all the processors have co mplete information of the load distribution over a network. Its soluti on serves as a benchmark to compare with realistic strategies, both in theoretical analysis, and experimental and simulational studies of di stributed algorithms. We show that when jobs have different sizes, eve n with preemptive scheduling, LBP is NP-complete. When the jobs are of the same size, we give a polynomial algorithm, using network-flow tec hniques, which extends to approximate solutions for jobs of different sizes. We apply this benchmark solution in order to analyze the compet itiveness for three network topologies: completely connected graphs, r ings, and hierarchical complete k-ary trees. The constant competitive ratio results for complete network and hierarchical complete k-ary tre es are applied to a study on the issues of network designs suitable fo r the LBP. We further discuss the problem for general networks with jo bs of different sizes for slightly weaker results than those for the c onstant competitive ratio requirement. Finally, we comment on the rela ted issues of job partitioning over parallel/distributed distributed s ystems. (C) 1997 Academic Press.