Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps

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

Abstract:

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.

• 1 Introduction
• 2 An on-line algorithm
• 3 An O(c+d)-step schedule
  • 3.1 A preliminary result
  • 3.2 The main result
• 4 Counterexamples to on-line algorithms
  • 4.1 Counterexample for routing on leveled networks
  • 4.2 Counterexample for various deterministic strategies
  • 4.3 Counterexample to a randomized strategy
• 5 Acknowledgements
• References
• About this document ...