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

Next: 1 Introduction

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 ...

Bruce Maggs Mon Jul 22 20:27:47 EDT 1996