Universal Packet Routing Algorithms
Abstract
This paper examines the packet routing problem in a network independent context. The goal is to devise a strategy for routing that works well for a wide variety of networks. To achieve this goal, the authors partition the routing problem into two stages: A path selection stage and a scheduling stage. In the first stage we find paths for the packets with small maximum distance, d, and small maximum congestion, c. Once the paths are fixed, both are lower bounds on the time required to deliver the packets. In the second stage we find a schedule for the movement of each packet along its path so that no two packets traverse the same edge at the same time, and so that the total time and maximum queue size required to route all of the packets to their destinations are minimized. For many graphs, the first stage is easy - we simply use randomized intermediate destinations suggested by Valiant. The second stage is more challenging, however, and is the focus of this paper.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1988
- Accession Number
- ADA204273
Entities
People
- Bruce Maggs
- S.I. Rao
- Tom Leighton
Organizations
- Massachusetts Institute of Technology