F. T. Leighton
Bruce M. Maggs
Satish B. Rao
Mathematics Department and
Laboratory for Computer Science
Massachusetts Institute of Technology
Cambridge, Massachusetts 02139
NEC Research Institute
4 Independence Way
Princeton, NJ 08540
In this paper, we prove that there exists a schedule for routing any set of packets with edge-simple paths, on any network, in steps, where c is the congestion of the paths in the network, and d is the length of the longest path. The result has applications to packet routing in parallel machines, network emulations, and job-shop scheduling.