On-line load balancing with applications to machine scheduling and virtual circuit routing

Abstract

In this paper we study an idealized problem of on-line allocation of routes to virtual circuits where the goal is to minimize the required bandwidth. For the case where virtual circuits continue to exist forever, we describe an algorithm that achieves an 0(log n) competitive ratio, where n is the number of nodes in the network. Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an O(logn) factor. We also show that this result is tight, i.e. for any on-line algorithm there exists a scenario in which O(logn) increase in bandwidth is necessary. We view virtual circuit routing as a generalization of an on-line scheduling problem, and hence a major part of the paper focuses on development of algorithms for non-preemptive on-line scheduling for related and unrelated machines. Specialization of routing to scheduling leads us to concentrate on scheduling in the case where jobs must be assigned immediately upon arrival; assigning a job to a machine increases this machine's load by an amount that depends both on the job and on the machine. The goal is to minimize the maximum load. For the related machines case, we describe the first algorithm that achieves constant competitive ratio. For the unrelated case (with n machines), we describe a new method that yields 0(log n)-competirive algorithm. This stands in contrast to the natural greedy approach, which we show has only a ⊖(n) competitive ratio. The virtual circuit routing result follows as a generalization of the unrelated machines.