Packet routing plays a central role in the design of large-scale parallel computers. Simply stated, packet routing consists of moving packets of data from one location to another in a network. The goal is to move all of the packets to their desired locations as quickly as possible, and with as little queuing as possible. The packet routing problem has been extensively studied, and we refer the reader to [5] for a broader coverage of the topic.
The method of packet routing considered in this paper is known as store-and-forward routing. In a store-and-forward routing algorithm, packets are viewed as atomic objects. At each step, a packet can either wait in a queue or jump from one queue to another.
Figure 1 shows a graph model for store-and-forward routing. The shaded nodes labeled 1 through 5 in the figure represent processors or switches, and the edges between the nodes represent wires. A packet is depicted by a square box containing the label of its destination. The goal is to route the packets from their origins to their destinations via a series of synchronized time steps, where at each step at most one packet can traverse each edge.
Packets wait in three different kinds of queues. Before the routing begins, packets are stored at their origins in special initial queues. For example, packets 4 and 5 are stored in the initial queue at node 1. When a packet traverses an edge, it enters the edge queue at the end of that edge. A packet can traverse an edge only if at the beginning of the step the edge queue at the end of that edge is not full. In the example of Figure 1 the edge queues can hold two packets. Upon traversing the last edge on its path, a packet is removed from the edge queue and placed in a special final queue at its destination. For simplicity, the final queues are not shown in Figure 1. Independent of the routing algorithm used, the size of the initial and final queues are determined by the particular packet routing problem to be solved. Thus, any bound on the maximum queue size required by a routing algorithm refers only to the edge queues.
Figure 1: A graph model for packet
routing.
This paper focuses on the problem of timing the movements of the packets along their paths. A schedule for a set of packets specifies which move and which wait at each time step. Given any underlying network, and any selection of paths for the packets, our goal is to produce a schedule for the packets that minimizes the total time and the maximum queue size needed to route all the packets to their destinations.
Of course, there is a strong correlation between the time required to route the packets and the selection of the paths. In particular, the maximum distance, d, traveled by any packet is always a lower bound on the time. We call this distance the dilation of the paths. Similarly, the largest number of packets that must traverse a single edge during the entire course of the routing is a lower bound. We call this number the congestion, c, of the paths. For example, see Figure 2.
Figure 2: A set of paths for the
packets with dilation d=3 and congestion c=3.
Given any set of paths with congestion c and dilation d in any network, it is straightforward to route all of the packets to their destinations in cd steps using queues of size c at each edge. Each packet can be delayed at most c-1 steps at each of at most d edges on the way to its destination (since the queues are big enough so that packets can never be delayed by a full queue in front.)
In this paper, we show that there are much better schedules. We begin
in Section 2 with a randomized on-line algorithm that
produces a schedule of length 
using queues of size
, where N is the total number of packets. This
algorithm is close to optimal when c is large. Our main
result appears in Section 3. It establishes the
existence of a schedule using 
steps and constant-size queues at
every edge, thereby achieving the naive lower bounds for any routing
problem.
The proof of the main result is nonconstructive. However, the result
still has several applications, as described below. In addition, the
result is highly robust in the sense that it works for any set of
edge-simple paths and any underlying network. (A priori, it would
be easy to imagine that there might be some set of paths on some
network that required more than 
steps or nonconstant
queues to route all the packets.) Furthermore, the main result can be
made constructive using the recently discovered algorithmic version of
the Lovász Local Lemma [1, 2]. A
manuscript describing the algorithm is in preparation [7].
If a particular routing problem is to be performed many times over,
then the time required to compute the optimal schedule once becomes
less important. This situation arises in network emulation problems.
Typically, a guest network G is emulated by a host network H by
embedding G into H. (For a more complete discussion of emulations
and embeddings, see [3].) An embedding maps
nodes of G to nodes of H, and edges of G to paths in H. There
are three important measures of an embedding: the load, congestion,
and dilation. The load of an embedding is the maximum number
of nodes of G that are mapped to any one node of H. The
congestion is the maximum number of paths corresponding to edges of
G that use any one edge of H. The dilation is the length
of the longest path. Let l, c, and d denote the load,
congestion, and dilation of the embedding. Once G has been embedded
in H, H can emulate G in a step-by-step fashion. Each node of
H first emulates the local computations performed by the l (or
fewer) nodes mapped to it. This takes 
time. Then for each
packet sent along an edge of G, H sends a packet along the
corresponding path in the embedding. Using the main result of this
paper, routing the packets to their destinations takes 
steps.
Thus, H can emulate each step of G in 
steps.
In a related paper, Leighton, Maggs, Ranade, and Rao
[6] show how to route packets in 
steps using a simple randomized algorithm provided that the underlying
network is leveled and has depth L. As a consequence, optimal
routing algorithms can be derived for most of the networks that are
commonly used for parallel computation. Unfortunately, it seems to be
difficult to extend this result to hold for all networks. In fact, we
have considered many simple on-line algorithms (including the
algorithm presented in [6]), and found routing
problems for each algorithm that result in schedules that use
asymptotically more than 
steps. Several of these
examples are included in Section 4.
The results of this paper also have applications to job-shop
scheduling. In particular, consider a scheduling problem with jobs
, and machines 
, for which each
job must be performed on a specified sequence of machines. In our
application, we assume that each job occupies each machine that works
on it for a unit of time, and that no machine has to work on any job
more than once. Of course, the jobs correspond to packets, and the
machines correspond to edges in the packet routing problem. Hence, we
can define the dilation of the scheduling problem to be the
maximum number of machines that must work on any job, and the
congestion to be the maximum number of jobs that have to be run on
any machine. As a consequence of our packet routing result, we show
that any scheduling problem can be solved in 
steps. In
addition, we will prove that there is a schedule for which each job
waits at most 
steps before it starts running, and that each
job waits at most a constant number of steps in between consecutive
machines. The queue of jobs waiting for any machine will also always
be at most a constant. These results are optimal, and are substantially
better than previously known bounds for this problem
[4, 10].
Recently some results were proved in [11] for the more
general problem of job-shop scheduling where jobs are not assumed to
be unit length and a machine may have to work on the same job more
than once. They give randomized and deterministic algorithms that
produce schedules that are within a polylogarithmic factor of the
optimal length for the more general job-shop problem. However, it is
not known whether there exist schedules of length 
for this
problem.
This paper also leaves open the question of whether or not there is an
on-line algorithm that can schedule any set of paths in 
steps
using constant-size queues. We suspect that finding such an algorithm
(if one exists) will be a challenging task. Our negative suspicions
are derived from the fact that we can construct counterexamples to
most of the simplest on-line algorithms. In other words, for several
natural on-line algorithms we can find paths for N packets for which
the algorithm will construct a schedule using asymptotically more than
steps. Several of the counterexamples are
included in Section 4.