A Survey of Congestion+Dilation Results for Packet Scheduling

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.