Skip to main content

A survey of congestion+dilation results for packet scheduling

Publication ,  Journal Article
Maggs, BM
Published in: 2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings
January 1, 2006

This paper surveys a collection of theoretical results that relate the congestion and dilation of the paths taken by a set of packets in a network to the time required for their delivery, or to the rate at which they can be delivered, where the congestion is the maximum number of paths that pass through a link, over all links, and the dilation is the length of the longest path. Results are stated first for batch routing algorithms and then for continuous routing. Most of the given results are for store-and-forward algorithms (e.g., as implemented in Internet routers), while some are for wormhole or connection-based routing. None of the algorithms described in this survey ever drop packets. The first result in this area was proved by Leighton, Maggs, and Rao in 1988. They showed that any set of packets whose paths have congestion c and dilation d (and are loop free) can be delivered to their destinations in a synchronous store-and-forward network in O(c + d) steps. © 2006 IEEE.

Duke Scholars

Published In

2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings

DOI

Publication Date

January 1, 2006

Start / End Page

1505 / 1510
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Maggs, B. M. (2006). A survey of congestion+dilation results for packet scheduling. 2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings, 1505–1510. https://doi.org/10.1109/CISS.2006.286378
Maggs, B. M. “A survey of congestion+dilation results for packet scheduling.” 2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings, January 1, 2006, 1505–10. https://doi.org/10.1109/CISS.2006.286378.
Maggs BM. A survey of congestion+dilation results for packet scheduling. 2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings. 2006 Jan 1;1505–10.
Maggs, B. M. “A survey of congestion+dilation results for packet scheduling.” 2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings, Jan. 2006, pp. 1505–10. Scopus, doi:10.1109/CISS.2006.286378.
Maggs BM. A survey of congestion+dilation results for packet scheduling. 2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings. 2006 Jan 1;1505–1510.

Published In

2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings

DOI

Publication Date

January 1, 2006

Start / End Page

1505 / 1510