## DIMACS TR: 2002-20

## Source Routing and Scheduling in Packet Networks

### Authors: Matthew Andrews, Antonio Fern\'andez, Ashish Goel and Lisa Zhang

**
ABSTRACT
**

We study {\em routing} and {\em scheduling} in packet-switched
networks. We assume an adversary that controls the injection time,
source, and destination for each packet injected. A set of paths for
these packets is {\em admissible} if no link in the network is
overloaded. We present the first on-line routing algorithm that finds
a set of admissible paths whenever this is feasible. Our algorithm
calculates a path for each packet as soon as it is injected at its
source using a simple shortest path computation. The length of a link
reflects its current congestion. We also show how our algorithm can
be implemented under today's Internet routing paradigms.

When the paths are known (either given by the adversary or computed as
above) our goal is to schedule the packets along the given paths so
that the packets experience small end-to-end delays. The best
previous delay bounds for deterministic and distributed scheduling
protocols were exponential in the path length. In this paper we
present the first deterministic and distributed scheduling protocol
that guarantees a polynomial end-to-end delay for every packet.

Finally, we discuss the effects of combining routing with scheduling.
We first show that some unstable scheduling protocols remain unstable
no matter how the paths are chosen. However, the freedom to choose paths
can make a difference. For example, we show that a ring with parallel
links is stable for all greedy scheduling protocols if paths are
chosen intelligently, whereas this is not the case if the adversary
specifies the paths.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-20.ps.gz

DIMACS Home Page