Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules,

Abstract

In 1988, Leighton, Maggs, and Rao showed that for any network and any set of packets whose paths through the network are fixed and edge-simple, there exists a schedule for routing the packets to their destinations in O(c + d) steps using constant-size queues, where C is the congestion of the paths in the network, and d is the length of the longest path. The proof, however, used the Lova'sz Local Lemma and was not constructive. In this paper, we show how to find such a schedule in O(P (log log P) log P) time, with probability 1 - 1/pP, for any positive constant p, where P is the sum of the lengths of the paths taken by the packets in the network. We also show how to parallelize the algorithm so that it runs in NC. The method that we use to construct the schedules is based on the algorithmic form of the Lova'sz Local Lemma discovered by Beck.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1996
Accession Number
ADA311323

Entities

People

  • AndrĂ©a W. Richa
  • Bruce M. Maggs
  • F. T. Leighton

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Binomials
  • Boundaries
  • Computations
  • Computer Science
  • Computers
  • Congestion
  • Embedding
  • Inequalities
  • Job Shop Scheduling
  • Mathematics
  • Network Emulation
  • Probability
  • Random Variables
  • Scheduling (Production)
  • Sequences

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.
  • Operations Research