# On-line routing of virtual circuits with applications to load balancing and machine scheduling

James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, and Orli Waarts.
On-line routing of virtual circuits with applications to load balancing and machine scheduling.
*Journal of the Association for Computing Machinery*
44(3):486–504, May 1997.
An earlier version appeared
in
*Twenty-Fifth Annual ACM Symposium on Theory of
Computing*, May 1993, pp. 623–631,
under the title
“On-line
load balancing with applications to machine scheduling
and virtual circuit routing.”

## Abstract

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
an *O(log n)* competitive ratio with respect to maximum congestion,
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(log n)* factor. We also show that this result is tight, *i.e.*
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 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 *O(log
n)*-competitive algorithm. This stands in contrast to the natural greedy
approach, whose competitive ratio is exactly *n*.

## BibTeX

Download@article(AspnesAFPW1993,
title="On-line routing of virtual circuits with applications to load balancing and machine scheduling",
author="James Aspnes and Yossi Azar and Amos Fiat and Serge Plotkin and Orli Waarts",
journal=jacm,
volume=44,
number=3,
pages={486--504},
month=may,
year=1997
)

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page