On-line routing of virtual circuits with applications to load balancing and machine scheduling.
In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to route all requests while minimizing the required bandwidth.  We concentrate on the case of Permanent virtual circuits (i.e., once a circuit is established it exists forever), and describe an algorithm that achieves on O (log n) competitive ratio with respect to maximum congestin, where nis 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 (log n) factor.  We also show that this result is tight, that is, for any on-line algorithm there exists a scenario in which ***(log n) increase in  bandwidth is necessary in directed networks. We view virtual circuit routing as a generalization of an on-line load balancing problem, defined as follows: jobs arrive on line and each job must be assigned to one of the machines immediately upon arrival.  Assigning a job to a machine increases the 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 nmachines), we describe a new method that yields O(logn)-competitive algorithm.  This stands in contrast to the natural greed approach, whose competitive ratio is exactly n. show that this result is tight, that is, for any on-line algorithm there exists a scenario in which ***(log n) increase in bandwidth is necessary in directed networks.
Introduction
Virtual Circuit Routing High-speed integrated communication networks are going to become a reality in
the near future. Implementation of these networks raises numerous new issues that either did not exist or
could be easily addressed in the context of the existing slow-speed networks. In particular, the increase in
the network speed by several orders of magnitude leads to a situation where the bandwidth-delay product far
exceeds the available buffer space, making it necessary to use bandwidth-reservation techniques.
The main abstraction through which the customer can use the network is by a virtual circuit. In order to
use the network, the customer requests it to reserve the required bandwidth between the two communicating
points. The network guarantees that the reserved bandwidth will indeed be available as long as needed,
creating an illusion of a real circuit dedicated to the customer. One of the basic services that appears in the
proposals for future high-speed networks (e.g. ATM [1]) is the permanent virtual circuit (PVC) service. As
far as the user is concerned, such virtual circuit is supposed to behave like a physical line connecting the
corresponding points, and hence it is desirable that once such a circuit is created, it will not be "rerouted" by
the network except as a result of failures. (Hence the name "permanent").
In this paper we develop a framework and techniques that allow us to address the problem of online
virtual circuit routing. We consider the following idealized setting: We are given a network where each
edge has an associated capacity (bandwidth). Requests for virtual circuits arrive on line, where each request
specifies the source and destination points, and the required bandwidth. The routing algorithm has to choose
a path from the source to the destination and reserve the required bandwidth along this path. The goal is to
minimize the maximum (over all edges) of the relative load, defined as the reserved (used) edge bandwidth,
measured as a percentage of the total edge capacity. In this paper, we assume that no rerouting is allowed
and that the virtual circuits never disappear.
For some applications it is more efficent to use multicast circuits, where instead of a single destination
there are multiple destinations. Examples include teleconferencing, video on demand, database updates, etc.
In this case the routing algorithm has to choose a tree that spans the nodes participating in the multicast.
Our framework and techniques can be applied to several alternative models; discussion of these models
is deferred to the end of the introduction. Several recent papers show how to apply the techniques developed
in this paper to more general cases, including the routing of switched virtual circuits (SVC), i.e. circuits
that have limited duration in time [6, 3, 4, 2]. Simulation and implementation results described in [11]
indicate that online routing algorithms based on our techniques outperform traditional algorithms for routing
permanent virtual circuits circuits in ATM networks.
As customary, we evaluate the performance of the on-line algorithms in terms of competitive ratio [22],
which is the supremum, over all possible input sequences, of the ratio of the maximum load achieved by the
on-line algorithm to the maximum load achieved by the optimal off-line algorithm.
Using our framework, we derive online virtual circuit routing algorithms (point-to-point and multicast)
that are O(log n) competitive with respect to load, where n is the number of nodes in the network. We also
show an
\Omega\Gamma107 n) lower bound on the competitive ratio of any virtual circuit routing algorithm in the case
where the underlying network is directed. (The upper bound works for both directed and undirected cases).
Load Balancing We view virtual circuit routing as a generalization of on-line machine scheduling/load
balancing. To this end, we concentrate on non-preemptive load-balancing, defined as follows: There are
parallel machines and a number of independent jobs; the jobs arrive one by one, where each job has an
associated load vector and has to be assigned to exactly one of the machines, thereby increasing the load
on this machine by the amount specified by the corresponding coordinate of the load vector. Once a job is
assigned, it cannot be re-assigned. The objective is to minimize the maximum load.
The load balancing problems can be categorized into three classes according to the properties of the load
vectors, as it is done for the non-preemptive scheduling problems [13]. In the identical machines case, all
the coordinates of a load vector are the same. This case was first considered by Graham [12], who showed
a
)-competitive algorithm, where n is the number of machines. The bound was improved in [8] to
(the value of ffl was further improved in [14]). In the related machines case, the
ith coordinate of each load vector is equal to w(j)=v(i), where the "weight" w(j) depends only on the job
j and the "speed" v(i) depends only on the machine i. All other cases are referred to as unrelated machines.
The special case where all coordinates of the load vector are either 1 or equal to a given value that depends
only on the job, was considered in [7], who described an O(log n)-competitive algorithm. This case can
be viewed as a hybrid between the identical and the unrelated machines case, and it is incomparable to the
related machines case. A similar special case was studied in [15].
In this paper we show an O(log n)-competitive algorithm for the unrelated machines case, and an
8-competitive algorithm for the related machines case. Although competitive analysis notions apply to
algorithms without any restrictions on their running times, all on-line algorithms presented in this paper run
in deterministic polynomial time, whereas the matching lower bounds are based on information-theoretic
arguments and apply even if we allow the online algorithm to use randomization.
The related machines case is a generalization of the identical machines problem, for which Graham [12]
has shown that a greedy algorithm achieves a constant competitive ratio. Thus, it is natural to ask whether an
adaptation of such an algorithm can give a constant competitive ratio for the related machines case as well.
We prove that, surprisingly, the natural greedy approach (that is, assigning every new job to the machine that
will complete it with the lowest resulting load) is \Theta(log n) competitive. Our (non-greedy) 8-competitive
algorithm for this problem can be viewed as an adaptation of the scheduling algorithm of Shmoys, Wein,
and Williamson [21] to the context of load balancing.
We show that for the unrelated machines case, the natural greedy algorithm is n-competitive. This
bound should be contrasted with the O(log n)-competitive greedy strategy of [7] for the special case where
all coordinates of the load vector are either 1 or equal to a given value that depends only on the job. The
large gap between these bounds indicates that the unrelated machines case is strictly harder, and requires
development of new techniques. We introduce a new approach that leads to an O(log n)-competitive
algorithm for the general unrelated machines case. As shown in [7], this is the best bound on the competitive
ratio one can hope for in this case.
Other related work Some of the techniques which are used for our on-line framework are based on ideas
developed in the context of approximation algorithms for the multicommodity flow and related problems
(see eg. [20, 16, 17, 19]). In particular, we assign each link a weight that is exponential in the link's load,
and choose the routes by computing shortest paths with respect to this weight. A main difference between
the algorithms presented here and the previously known offline approximation algorithms is in a novel way
of proving the approximation factor which allows us to execute the algorithm in an online fashion.
All the results in this paper concentrate on the case where jobs and virtual circuits are permanent, i.e.
jobs never leave and virtual circuits never terminate. Azar, Broder, and Karlin [5] introduced a natural
generalization of this model, in which requests have duration in time. They show
n) lower bound
on the competitive ratio of any load balancing algorithm that deals with the unknown duration case, i.e. the
case where the duration of a request becomes known only upon its termination.
This lower bound suggests considering the case where the duration of a request becomes known upon its
arrival (the known duration case). The methods developed in this paper were generalized in [6], giving an
O(log nT )-competitive algorithm for the problems of scheduling unrelated machines in the known duration
case, where T is the ratio of maximum to minimum duration. Similar results can be achieved for the virtual
circuit routing problem.
Another way to overcome the lower bound in the unknown-duration case is to allow re-assignments of
existing jobs. For the case where the coordinates of the load vector are restricted to be 1 or 1, Phillips
and Westbrook [18] proposed an algorithm that achieves O(log n) competitive ratio while making O(1)
amortized rassignments per job. The general case was considered in [4], who show how to extended the
techniques presented here to design an O(log n)-competitive algorithm with respect to load that reroutes
each circuit at most O(log n) times.
An alternative measure of network performance is the amortized throughput defined as the average over
time of the number of bits transmitted by the accepted connections. In this setting, the network's bandwidth
is assumed to be insufficient to satisfy all the requests so some of the requests may need to be rejected upon
their arrival. An on-line algorithm in this setting is a combination of a decision mechanism that determines
which requests to satisfy together with a strategy that specifies how to route these requests. The goal is to
maximize the amortized throughput. Competitive algorithm that maximizes the throughput in a single-link
case was provided by Garay and Gopal [10]; the case where the network consists of single line of nodes
was considered by Garay, Gopal, Kutten, Mansour and Yung in [9]. The techniques presented here were
extended by Awerbuch, Azar, and Plotkin [3] to provide competitive solution for networks with unrestricted
topology.
Our routing and scheduling algorithms assume a central scheduler that makes all the decisions. In [2],
Awerbuch and Azar extended the techniques of this paper to the case where there are concurrent requests
that have to be satisfied in a decentralized fashion.
Virtual Circuit Routing
In this section we consider the problem of on-line routing of virtual circuits in a capacitated network.
Formally, we are given a graph E) with jV m, and a capacity function
. The requests arrive as tuples (s Request i is
satisfied by choosing a route P i from s i to t i and reserving capacity p(i) along this route.
Since we will always normalize the requested bandwidth to the total available bandwidth, it will be
procedure ASSIGN-ROUTE(p; s; t; G; ~ ';  );
e := p=u(e);
~
Let P be the shortest path from s to t in G w.r.t. costs c e ;
performance guarantee of the algorithm;
then b :=fail
else begin
:=success
end.

Figure

1: Algorithm ASSIGN-ROUTE.
convenient to define:
be the routes assigned to requests 1 through k by the on-line algorithm, and let
k g be the routes assigned by the off-line algorithm. Given a set of routes P , define
the relative load after the first j requests are satisfied by
(1)
and let (j). Similarly, define '
e (j) and -   (j) to be the corresponding quantities for the
routes produced by the off-line algorithm. For simplicity we will abbreviate -(k) as - and -   (k) as -   . The
goal of the on-line algorithm is to produce a set of routes P that minimizes -   .
This problem can be viewed as an instance of 2-terminal net routing or path-packing. Minimizing -
corresponds to asking how much larger we should make the capacities of the edges in order for the on-line
algorithm to be able to satisfy all the requests that the off-line algorithm could have satisfied in the network
with the original capacities.
It is easy to see that the algorithms presented in this section can be extended to the case where the
increase in the load is not uniform along the route, i.e. when p e (i) is arbitrary and not necessarily equal to
p(i)=u(e).
2.1 Routing Algorithm
The ASSIGN-ROUTE algorithm that assumes knowledge of   -   is shown in Figure 1. Given a request to
allocate a route of capacity p from s to t, ASSIGN-ROUTE assigns a weight to each edge as a function of the
change in its relative load if it is used by the new route, and then computes a shortest path from s to t with
respect to these weights; a is an appropriately chosen constant.
For convenience, we define the notion of a performance guarantee fi as follows: the algorithm accepts a
parameter   and never creates load that exceeds fi  . The algorithm is allowed to return "fail" and to refuse
to route a circuit if   ! L   , otherwise it has to route all of the requests.
Lemma 2.1 If -   -  , then there exists n) such that algorithm ASSIGN-ROUTE never fails. Thus, the
performance guarantee is O(log n).
To simplify the formulas, we will use tilde to denote normalization by  , for example ~
e (j)= . Define the potential function:
a ~
'e
e (j));
(2)
where are constants. If the on-line algorithm satisfies the (j 1)st request with route P j+1 and
the off-line algorithm satisfies it with route P
j+1 , we get the following change in the potential function:
e (j))(a ~
a ~ 'e (j+1) ~
fl(a ~
'e (j)+~pe (j+1) \Gamma a ~ 'e (j)
a ~ 'e (j) ~
fl(a ~ 'e (j)+~pe (j+1) \Gamma a ~
'e (j) ~
a ~
'e (j)
fl(a ~
pe
The last inequality follows from the fact that P j+1 is the shortest path between the endpoints of the
1st request with respect to the costs a ~
'e (j)+~pe (j+1) \Gamma a ~ 'e
Since the (j 1)st request is satisfied by the optimal algorithm by assigning it the route P
j+1 , it means
that 8e 2 P
Therefore, in order to show that the potential function does
not increase, it is sufficient to show that 8x 2 [0; which is true for
Initially, is the number of edges in the graph. Since \Phi does not increase, after
satisfying k requests, we have, for all e in E:
which implies that
log a
O(  log n):
We use a simple doubling technique to guess  . We start with   At the beginning of the first
phase, we set   is the requested bandwidth of the first request. At the beginning of
a new phase h ? 1, we set   During a single phase, jobs are assigned independently of the
jobs assigned in the previous phases, i.e. the load created by the jobs that were assigned in the previous
phases is ignored. Phase h ends when ASSIGN-ROUTE returns "fail". It is easy to see that this approach can
increase the competitive factor by at most a factor of 4 (a factor of 2 due to the load in all the rest of the
phases except the last, and another factor of 2 due to imprecise approximation of  ). Since the performance
guarantee of ASSIGN-ROUTE is O(log n), we get the following theorem (observe that it holds both for directed
and undirected graphs):
Theorem 2.2 Algorithm ASSIGN-ROUTE can be used to achieve O(log n) competitive ratio with respect to load.
2.2 Routing Multicast Circuits
Many applications (tele-conferencing, video on demand, etc.) are based on multicast instead of point-to-
point circuits. A request for a multicast circuit consists of a tuple (t 1
are the communicating points and p(i) is the required bandwidth. Any one of the communicating points can
serve as a "source". To satisfy such request, the algorithm need to assign the required bandwidth p(i) along
the edges of some tree T i that spans nodes t 1
. As in the point-to-point case considered in the
previous section, the goal is to minimize load.
Observe that by assigning 2p(i) instead of p(i) bandwidth, we can embed into the network a cycle of
capacity p(i) that passes through all the communicating points. Also note that the case k directly
corresponds to the point-to-point case.
The algorithm to route multicast circuits is a direct extension of the point-to-point routing strategy
presented above. Instead of routing over min-weight paths, multicast circuits are routed over min-weight
steiner trees. Since finding such trees is NP-hard, it is important to note that an approximation is sufficient.
In fact, as we will show below, it is sufficient to route over trees whose weight is within a constant factor
of minimum. Such trees can be easily found by applying a minimum-cost spanning tree algorithm to an
appropriately constructed graph [23].
The proof of the competitive ratio is nearly identical to the proof of Lemma 2.1. The only difference is in
the summation range in equation 3. Instead of summing over the edges on the path chosen by the algorithm
and the edges on the optimum path, the sum will be over the edges of the tree chosen by the algorithm and
the edges of the tree chosen by the optimum offline algorithm.
Equation (3) is based on the fact that the cost of the edges chosen by the algorithm for routing of the
current circuit is not larger than the cost of edges chosen by the optimum algorithm for routing of this
circuit. The fact that these edges form a path is not used. In other words, equation (3) remains correct if
the summation range is changed and if the algorithm routes over min-weight steiner trees. Thus, a multicast
algorithm that routes over min-weight steiner trees is O(log n)-competitive. By using a
instead of 1 1=fl, it can be seen that a 2-approximation to the min-weight steiner tree is sufficient and
increases the competitive ratio by at most a factor of 2.
The above discussion implies the following claim:
Theorem 2.3 There exists an O(log n)-competitive algorithm for multicast virtual circuit routing, where each
decision can be implemented in polynomial time.
2.3 Lower Bound for Routing
In this section we show a lower bound
of\Omega\Gamma/24 n) for the competitive ratio of any on-line routing algorithm
in a directed network, i.e. a network where the capacity between v and w is not necessarily equal to the
capacity between w and v. This implies that our O(log n)-competitive algorithm presented in the previous
section is optimal in this case. Our lower bound also holds for randomized algorithms working against an
oblivious adversary, i.e. an adversary that has to generate new requests independently of the outcome of the
coin flips of the online algorithm.
The basic idea is to modify the lower bound of Azar, Naor and Rom [7] for on-line load balancing. In
their lower bound the adversary introduces a new job at each iteration; the set of machines that can execute
this job is chosen by the adversary and depends on the on-line algorithm. In general, there is an exponential
number of such possible sets whereas in the routing context the graph is fixed and hence the adversary's
choice of the next request is limited: it has to both start and end at existing nodes of the graph. Thus,
literal translation of the lower bounds for the load-balancing problem and, in particular, the lower bound
in [7], leads to an exponential blowup in the size of the resulting graph, indicating that there is a need for a
somewhat more sophisticated construction.
Without loss of generality, assume that n is a power of 2. Consider a directed graph that has a single
source s, connected to each one of n vertices . There is one sink, denoted by S 1;1 , connected
to two sinks, denoted by S 2;1 ; S 2;2 , connected to respectively,
etc. In general, for each 1 - i - log n, we divide vertices sets, the jth of which, for
contains vertices v (j \Gamma1)n=2 . Each of the vertices in a set is connected
to a sink associated with this set, where the sinks are denoted by S i;j for . Observe that the
vertices associated with S i;j are the union of two disjoint sets associated with
We construct a sequence of requests for paths from the source to the sinks, for which the off-line load is
at most 1 but the online algorithm assigns at least load log nto some edge (s; v j ). This, combined with the
fact that the size of the graph is O(n), will yield
the\Omega\Gammae/2 n) lower bound.
We will refer to the load on an edge (s; v j ) as the load of v j . Requests are generated in log n phases;
the bandwidth of every request is equal to 1. We will maintain that the following conditions hold for each
phase
1. In phase i, there are n
requests of paths from the source to a sink S i;j for some j, where 1
2. At the end of phase i, the set average expected load on vertices associated with sink S i;j is i=2.
Clearly, before the first phase begins, the load of each vertex is 0. Assume that the above conditions
hold for phase i. The vertices associated with S i;j are the union of two disjoint sets: vertices associated with
sink those associated with S i+1;2j . Hence, one of these sets must have average expected load
of i=2 at the end of the ith phase. Denote this subset by S. Generate n
requests for unit capacity from
source s to the sink associated with S. Since S is of size n
, the average expected load of S must increase
by 1/2, to at least (i implying that the conditions are satisfied for phase i + 1.
Thus, after the last phase, the average expected load of the two vertices in the last set is at least log nHence the expected load of one of them is at least log nTo complete the proof, we have to show that the off-line algorithm can maintain unit maximum load.
It is enough to show that at each phase the off-line can satisfy the requests by using edge-disjoint paths
and without using vertices associated with sinks requested in latter phases. Indeed, at phase i there are n
requests for paths from the source to some sink S i;j . The set of vertices associated with this sink contains
two disjoint sets each of size n
. By construction, one of these sets is not associated with sinks of latter
requests. Thus, the off-line algorithm can route all the requests of phase i through edge-disjoint paths that
use only vertices of that set.
3 Online Machine Load-Balancing
In this section we present several algorithms for online machine load-balancing. Jobs arrive online, and each
has to be immediately assigned to one of the machines. The goal is to minimize maximum load.
Formally, each job j is represented by its "load vector"
Assigning job j to machine i increases the load on this machine by p i (j). Let ' i (j) denote the
load on machine i after we have already assigned jobs 1 through j:
Consider a sequence of jobs defined by oe
i (j) the load on
machine i achieved by the off-line algorithm A   after assigning jobs 1 through j in oe. The goal of both
the off-line and the on-line algorithms is to minimize L
respectively. More precisely, we measure the performance of the on-line algorithm by the supremum over
all possible sequences of L(k)=L   (k) (of arbitrary length k).
As we have mentioned in the Introduction, the load-balancing problems are usually categorized into
three classes, based on the properties of the load vectors. For identical machines,
For related machines, denotes the speed of
machine i. All other cases are referred to as unrelated machines.
Note that instead of "load" one can talk about "execution time". Restating the problem in these terms,
our goal is to decrease maximum execution time under the requirement that the arriving jobs are scheduled
immediately.
procedure ASSIGN-U(~p; ~ ';  );
Let s be the index minimizing
performance guarantee of the algorithm;
then b :=fail
else begin
:=success
return( ~ '; b).
end.

Figure

2: Algorithm ASSIGN-U.
3.1 Unrelated Machines
In this section we consider on-line load-balancing on unrelated machines. As we will show in Section 4, the
natural greedy approach is far from optimal for this case, achieving a competitive ratio of \Theta(n).
An O(log n)-competitive algorithm for the unrelated machines load-balancing can be constructed as a
reduction to the routing problem considered in the previous section. Unfortunately, such reduction results in
a confusing and non-intuitive algorithm. Instead, we present a simpler algorithm, specifically designed for
the machine load-balancing problem.
For simplicity, we first consider the case where we are given a parameter  , such that   - L   . As before,
an appropriate value of   can be "guessed" using a simple doubling approach, increasing the competitive
ratio by at most a factor of 4. We use tilde to denote normalization by  , i.e. ~
Algorithm ASSIGN-U, which assumes knowledge of  , is shown in Figure 2. The basic step is to assign
job j to make
a ~ ' i (j) as small as possible. In the description of the algorithm, we have omitted the job
index j, since a single invocation of the algorithm deals only with a single job. We will use the notion of
performance guarantee similarly to its use in the online routing case: the algorithm accepts a parameter
and never creates load that exceeds fi  . The algorithm is allowed to return "fail" and to refuse to schedule
a job if   ! L   , otherwise it has to schedule all of the arriving jobs.
Lemma 3.1 If L   -  , then there exists n) such that algorithm ASSIGN-U never fails. Thus, the
performance guarantee is O(log n).
Consider the state of the system after scheduling constants. (Later
we show that a good choice is a - 2; fl - 1.) Recall the assumption that L   (j) - L   -  , and define the
potential function:
a ~
Assume that job j was assigned to machine i 0 by the on-line algorithm and to machine i by the off-line
algorithm. We then have:
a ~
Note that since the off-line algorithm has assigned job j to machine i, we have 0 - ~
Therefore, in order to show that the potential function does not increase, it is sufficient to show that
x. This is true for
Since initially fln, at any point in the assignment process
a ~
and hence
log a
O(  log n)
Notice that the constants in the big O of (6) are small; for example for
1:07 log n+ 3:7. By changing the value of fl, one can trade off the multiplicative factor against the additive
one. Note that log n is a lower bound even for the restricted case considered in [7].
It is interesting to note that for the case where the coordinates of the load vector p(j) are either 1 or
equal to some constant p j that depends only on the job j, our algorithm behaves exactly like the greedy
algorithm considered in [7].
3.2 Related Machines
The related machines case is a generalization of the identical machines case. In Section 4 we show that
a natural generalization for the related machines case of the Graham's greedy algorithm for the identical
machines case, leads to an \Theta(log n) competitive ratio. Here we present a non-greedy algorithm that achieves
a constant competitive ratio.
As before, we first consider the case where we are given a parameter  , such that   - L   (k), where k
is the index of the last job. A simple doubling technique can be used to eliminate this assumption. Roughly
speaking, the algorithm will assign jobs to the slowest machine possible while making sure that the maximum
procedure ASSIGN-R(~p; ~ ';  );
then b :=fail
else begin
:=success
return( ~ '; b).
end.

Figure

3: Algorithm ASSIGN-R.
load will not exceed an appropriately chosen bound. The idea of assigning each job to the "least capable
machine" first appeared in the paper by Shmoys, Wein, and Williamson [21], where they considered an
online scheduling problem.
Algorithm ASSIGN-R, which assumes knowledge of  , is shown in Figure 3. The basic step is to assign
job j to the slowest machine such that the load on this machine will be below 2  after the assignment. In
the description of the algorithm, we have omitted the job index j, since a single invocation of the algorithm
deals only with a single job. We assume that the machines are indexed according to increasing speed.
In the following discussion we will omit the index k when it can be understood from the context. In
particular, we use L and L   instead of L(k) and L   (k), respectively. We use the notion of "performance
guarantee" in the same sense as in the previous section.
Lemma 3.2 If L   -  , then ASSIGN-R never fails. Therefore, the performance guarantee is equal to 2.
Proof: Assume ASSIGN-R fails on task j. Let r be the fastest machine whose load does not exceed L   , i.e.
g: If there is no such machine, we set
Obviously, r 6= n, could have been assigned to the fastest machine n, since
rg, the set of overloaded machines. Since r
Denote by S i and by S
i the set of jobs assigned to machine i by the on-line and the off-line algorithms,
respectively. Since we are dealing with related machines, we have:
This implies that there exists a job s 2
, i.e. there exists a job assigned
by the on-line algorithm to a machine i 2 \Gamma, and assigned by the off-line algorithm to a slower machine
By our assumptions, r is at least as fast as machine i 0 , and
thus p r assigned before job j, ' r . But this
means that the on-line algorithm should have placed job s on r or a slower machine instead of i, which is a
contradiction.
As we have mentioned above, the definition of the ASSIGN-R algorithm facilitates a doubling approach
to approximate  . More precisely, we start with  At the beginning of the first phase,   1 is set to be
equal to the load generated by the first job on the fastest machine for the job. At the beginning of a new phase
During a single phase, jobs are assigned independently of the jobs assigned
in the previous phases. Phase h ends when ASSIGN-R returns "fail". It is easy to see that this approach can
increase the competitive factor by at most a factor of 4 (a factor of 2 due to the load in all the rest of the
phases except the last, and another factor of 2 due to imprecise approximation of  ). Since the performance
guarantee of ASSIGN-R is 2, we get:
Theorem 3.3 Algorithm ASSIGN-R can be modified to achieve a competitive ratio of 8.
4 The Greedy Algorithm
The simple greedy machine load balancing algorithm due to Graham [12] gives a competitive ratio of 2 for the
identical machines case and competitive ratio of O(log n) for the special case considered in [7]. It is natural
to consider whether extensions of this algorithm can lead to small competitive ratios in the respectively
more general cases of related and unrelated machines. In this section we show that, unfortunately, this
is not the case. More precisely, we show that the greedy algorithm has \Theta(n) competitive ratio for the
unrelated machines case, and \Theta(log n) competitive ratio for the related machines case. This is in contrast
to the O(log n) and 8 competitive ratios, respectively, produced by the algorithms presented in the previous
sections.
We consider the following greedy algorithm: each job j is assigned upon arrival to the machine k that
minimizes the resulting load, i.e., the machine k that minimizes ' k (j are broken by
some arbitrary rule.
Lemma 4.1 The greedy algorithm has a competitive ratio no better than n for unrelated machines.
Proof: Consider a sequence of jobs such that job j has cost j on machine j, cost 1
and cost 1 on all other machines (i.e.,
(To avoid distinguishing between the first job and all the other jobs, we refer to machine n also as machine
0.) Here ffl is an arbitrarily small positive constant that is used to avoid ties. Clearly the optimal off-line
algorithm can schedule all of these jobs with a maximum load of 1 assigning job j to machine j \Gamma 1.
On the other hand, the greedy algorithm assigns job 1 to machine 1 for a resulting load of 1 (as opposed
machine n or 1 anywhere else). Similarly, when job 2 arrives, the greedy algorithm assigns it to
1 Note that assigning a job to the machine with the minimum load results in an algorithm with competitive ratio that is at least
equal to the ratio of the fastest to slowest machine speeds.
machine 2 for a resulting load of 2, instead of assigning this job to machine 1, where it would have produced
a load of (2 ffl). Likewise, job 3 is assigned to machine 3 and so forth. A simple induction argument shows
that job j is always assigned to machine j for a resulting load of j, giving a maximum load of n on machine
n. The resulting performance ratio is n=(1 + ffl), which can be made arbitrarily close to n.
Lemma 4.2 The competitive ratio of the greedy algorithm is at most n for unrelated machines.
Proof: Every job j has a minimum load min i p i (j) that can not be avoided by the optimal off-line algorithm.
If S
i is the set of jobs assigned to machine i by the off-line algorithm,
On the other hand, we claim that the the maximum load resulting from the greedy algorithm will
never exceed the sum of the minimum loads. Indeed, suppose that after assigning job
arrives there is some machine m that minimizes p m (j).
The load on this machine is at most L(j \Gamma 1), and so if j is assigned to m the resulting load is at most
is assigned to some other machine, the resulting load on
that machine is not larger. In either case we have
thus, by induction,
Lemma 4.3 The greedy algorithm has a competitive ratio \Omega\Gammatio n) for related machines.
Proof: For simplicity, first we assume that whenever adding a job to two different machines will result in
the same maximum load, the job is assigned to the faster machine. At the end of the proof we show how this
assumption can be avoided.
Consider a collection of machines with speeds ranging from 1 to 2 \Gammak (the relation between k and n will
become clear below). Let n i be the number of machines with speed 2 \Gammai and suppose n
in general
These values are chosen so that the sum of the speeds of all machines with speed 2 \Gammai is equal to the sum of
the speeds of all the faster machines. Thus, a collection of jobs that would add 1 to the load of each machine
with speed 2 \Gammai could instead be assigned to add 1 to the loads of all the faster machines. The total number
of machines
Now consider the following sequence of jobs. First we generate n k jobs of size 2 \Gammak , followed by n
jobs of size 2 \Gamma(k\Gamma1) , and so forth, until at last we generate a single job of size 1. For every machine with
speed 2 \Gammaj there is a corresponding job of size 2 \Gammaj . By simply assigning each job to the corresponding
machine, the off-line algorithm can schedule all the jobs with a resulting maximum load of 1.
However, we claim that the greedy algorithm assigns each group of jobs to machines that are "too fast".
Assume, by induction, that before the jobs of size 2 \Gammai are assigned, the load on machines with speed 2 \Gammaj
is equal to min(k \Gamma j). (In the base case, when condition simply corresponds to each
machine having zero load.) By Equation 8, the greedy algorithm can assign the jobs of size 2 \Gammai to all
machines with speed resulting in load of on each one of these machines.
If instead it assigns one of these jobs to a machine with speed 2 \Gammaj , where j - i, the resulting load will be
which is at least non-negative
x. The greedy algorithm will therefore not assign any job of size 2 \Gammai to a machine with speed 2 \Gammai or slower,
and the induction step follows.
Consequently, after all the jobs have been assigned, each machine with speed 2 \Gammaj has load k \Gamma j; the
single machine with speed 1 has load k
n). Thus, under the simplifying assumption that the greedy
algorithm always breaks ties in favor of the faster machine, the greedy algorithm
n)-competitive.
Next we show how to avoid the above simplifying assumption. Before sending in the "large" jobs, we
will send an "ffl-job" of size ffl i 2 \Gammai for each machine with speed 2 \Gammai , giving it a load of ffl i . To avoid changing
the greedy algorithm's choice of where to assign the large jobs, each ffl i must be less than 2 \Gammak , the smallest
possible difference between loads resulting from large jobs. To force ties to be broken in favor of faster
machines we require that Finally, to ensure that the ffl-job intended for a machine
is not placed on some faster machine, we generate the jobs for the faster machines first and require that
of these conditions can be satisfied by choosing ffl
Lemma 4.4 The greedy algorithm has a competitive ratio of O(log n) for related machines.
Proof: Let L be the maximum load generated by the greedy algorithm and L   be the maximum load
generated by the optimal off-line algorithm. The structure of the proof is as follows. First, we note that
load on the fastest machines is at least L \Gamma L   . Second, we show that if the load on all the machines with
speed - v is at least ', then the load on all the machines with speed - v=2 is at least ' \Gamma 4L   . Repeated
applications of this claim imply that the load on any machine that is no more than n times slower than the
fastest machine, is at least L Finally, we use an argument similar to the one used in
the proof of Lemma 4.2 to show this condition can only hold if
First, consider the last job j assigned by the greedy algorithm to a machine i, causing the load of this
machine to reach '. Since no job can add more than L   to the load of any fastest machine, the fact that the
new load on i is ' implies that the load on all the fastest machines is at least ' \Gamma L   .
Now suppose the load on all the machines with speed v or more is at least ' - 2L   . Consider the set of
jobs that are responsible for the last 2L   load increment on each one of these machines. Observe that at least
one of these jobs (call this job j) has to be assigned by the offline algorithm to some machine i with speed
less than v, and hence it can increase the load on i by most L   . Since the speed of i is at most v, job j can
increase the load on the machines with speeds above v=2 by at most 2L   . The fact that job j was assigned
when the loads on all the machines with speed v and above was at least ' \Gamma 2L   implies that the loads on all
the machines with speed above v=2 is at least ' \Gamma 4L   .
Let v be the speed of the fastest machines. We have shown that all machines with speed v have load
at least L \Gamma L   . Iteratively applying the claim in the above paragraph shows that all machines with speed
v2 \Gammai have load at least L \Gamma L   \Gamma 4iL   . Thus, every machine with speed at least v=n has load at least
Assume, for contradiction, that . Recall that since we are in the related
machines case, for each job j and any two machines i and i 0 , we have W
W (j) can be regarded as the weight of the job. Let I be the set of machines with speed less than v max =n.
The total weight of jobs that can be assigned by the offline algorithm is bounded from above by
i62I
i62I
The assumption that the online algorithm causes load of more than 2L   on all the machines not in I implies
that the total weight of the jobs assigned by the online algorithm is greater than 2L
which is a
contradiction. Thus,

Acknowledgments

We are indebted to David Shmoys for many helpful discussions.



--R

Special issue on Asynchronous Transfer Mode.
Competitive distributed algorithms for concurrent establishment of virtual circuits.
Throughput competitive on-line routing
Competitive routing of virtual circuits with unknown duration.


The competitiveness of on-line assignment
New algorithms for an ancient scheduling problem.
Efficient on-line call control algorithms
Call preemption in communication networks.

Bounds for certain multiprocessing anomalies.
Rinnooy Kan.
A better algorithm for an ancient scheduling problem.
An optimal algorithm for on-line bipartite matching


Online load balancing and network flow.

The maximum concurrent flow problem.
Scheduling parallel machines on-line
Amortized efficiency of list update and paging rules.
An approximate solution for the steiner problem in graphs.
--TR
Amortized efficiency of list update and paging rules
Competitive algorithms for on-line problems
The maximum concurrent flow problem
An optimal algorithm for on-line bipartite matching
Scheduling parallel machines on-line
New algorithms for an ancient scheduling problem
Call preemption in communication networks
The competitiveness of on-line assignments
An optimal on-line algorithm for metrical task system
Online load balancing and network flow
Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
Fast approximation algorithms for multicommodity flow problems
Competitive multicast routing
Fast approximation algorithms for fractional packing and covering problems
Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows
Routing and admission control in general topology networks with Poisson arrivals
Competitive routing of virtual circuits with unknown duration
Competitive non-preemptive call control
Online Load Balancing of Temporary Tasks
Load balancing in the L/sub p/ norm
Disjoint paths in densely embedded graphs
On-line routing for permanent virtual circuits
An Improved Lower Bound for Load Balancing of Tasks with Unknown Duration
Routing and Admission Control in General Topology Networks

--CTR
Nikhil Bansal , Avrim Blum , Shuchi Chawla , Adam Meyerson, Online oblivious routing, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
Csand Imreh, Scheduling problems on two sets of identical machines, Computing, v.70 n.4, p.277-294, August
Baruch Awerbuch , Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton, Online client-server load balancing without global information, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Jan Cosyn , Karl Sigman, Stochastic Networks: Admission and Routing Using Penalty Functions, Queueing Systems: Theory and Applications, v.48 n.3-4, p.237-262, November-December 2004
Ashish Goel , Monika R. Henzinger , Serge Plotkin , Eva Tardos, Scheduling data transfers in a network and the set scheduling problem, Journal of Algorithms, v.48 n.2, p.314-332, September
Kontogiannis, Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Weifa Liang , Yuzhen Liu, On-line disjoint path routing for network capacity maximization in energy-constrained ad hoc networks, Ad Hoc Networks, v.5 n.2, p.272-285, March, 2007
Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Rcke, Optimal oblivious routing in polynomial time, Journal of Computer and System Sciences, v.69 n.3, p.383-394, November 2004
Ran Adler , Yossi Azar, Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms, Journal of Scheduling, v.6 n.2, p.113-129, March/April
Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Racke, Optimal oblivious routing in polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
Ran Adler , Yossi Azar, Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 17-19, 1999, Baltimore, Maryland, United States
Susanne Albers , Stefano Leonardi, On-line algorithms, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999
Allan Borodin , Morten N. Nielsen , Charles Rackoff, (Incremental) priority algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.752-761, January 06-08, 2002, San Francisco, California
Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, The all-or-nothing multicommodity flow problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton , Harald Rcke, Oblivious routing on node-capacitated and directed graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Amitai Armon , Yossi Azar , Leah Epstein , Oded Regev, On-line restricted assignment of temporary tasks with unknown durations, Information Processing Letters, v.85 n.2, p.67-72, 31 January
Tak-Wah Lam , Hing-Fung Ting , Kar-Keung To , Wai-Ha Wong, On-line load balancing of temporary tasks revisited, Theoretical Computer Science, v.270 n.1-2, p.325-340, January
Marek Chrobak , Claire Kenyon-Mathieu, SIGACT news online algorithms column 10: competitiveness via doubling, ACM SIGACT News, v.37 n.4, December 2006
Ashish Goel , Adam Meyerson , Serge Plotkin, Approximate majorization and fair online load balancing, ACM Transactions on Algorithms (TALG), v.1 n.2, p.338-349, October 2005
Sandy Irani , Vitus Leung, Scheduling with conflicts on bipartite and interval graphs, Journal of Scheduling, v.6 n.3, p.287-307, May/June
Niv Buchbinder , Joseph Naor, Fair online load balancing, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
Yair Amir , Baruch Awerbuch , Amnon Barak , R. Sean Borgstrom , Arie Keren, An Opportunity Cost Approach for Job Assignment in a Scalable Computing Cluster, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.760-768, July 2000
Arie Keren , Amnon Barak, Opportunity Cost Algorithms for Reduction of I/O and Interprocess Communication Overhead in a Computing Cluster, IEEE Transactions on Parallel and Distributed Systems, v.14 n.1, p.39-50, January
Marek Chrobak, 2005: an offline persepctive, ACM SIGACT News, v.37 n.1, March 2006
Yi Cui , Klara Nahrstedt, High-bandwidth routing in dynamic peer-to-peer streaming, Proceedings of the ACM workshop on Advances in peer-to-peer multimedia streaming, November 11-11, 2005, Hilton, Singapore
Yi Cui , Baochun Li , Klara Nahrstedt, On achieving optimized capacity utilization in application overlay networks with multiple competing sessions, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
routing;high-speed networks;optimization;on-line algorithms