  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.
