Fast algorithms for finding O(congestion+dilation) packet routing schedules


Conference Paper

© 1995 IEEE. In 1988, Leighton, Maggs and Rao (1988) 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 dilation). The proof, however, used the Lovaacute/sz (1975) local lemma and was not constructive. In this paper, we show how to find such a schedule in O(NE+ElogϵE) time, for any fixed ϵ>0, where N is the total number of packets, and E is the number of edges in the network. We also show how to parallelize the algorithm so that it runs in NC. The method that we use to construct efficient packet routing schedules is based on the algorithmic form of the Lovaacute/sz local lemma discovered by Beck (1991).

Full Text

Duke Authors

Cited Authors

  • Leighton, T; Maggs, B

Published In

Start / End Page

  • 555 - 563

International Standard Serial Number (ISSN)

  • 1530-1605

International Standard Book Number 10 (ISBN-10)

  • 0818669306

Digital Object Identifier (DOI)

  • 10.1109/HICSS.1995.375501

Citation Source

  • Scopus