Universal packet routing algorithms
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 256-269
- https://doi.org/10.1109/sfcs.1988.21942
Abstract
The packet-routing problem is examined 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 routing problem is partitioned into two stages: a path-selection stage and a scheduling stage. In the first stage, paths for the packets are found with small maximum distance and small maximum congestion. Once the paths are fixed, both are lower bounds on the time required to deliver the packets. In the second stage, a schedule is found for the movement of each packet along its path so that no two packets traverse the same edge at the same time and the total time and maximum queue size required to route all of the packets to their destinations are minimized. The second stage is more challenging and is the focus of this study.<>Keywords
This publication has 15 references indexed in Scilit:
- Communication-efficient parallel algorithms for distributed random-access machinesAlgorithmica, 1988
- Routing and sorting on mesh-connected arraysPublished by Springer Nature ,1988
- Optimal routing algorithms for mesh-connected processor arraysPublished by Springer Nature ,1988
- A logarithmic time sort for linear size networksJournal of the ACM, 1987
- Parallel hashing---an efficient implementation of shared memoryPublished by Association for Computing Machinery (ACM) ,1986
- Fat-trees: Universal networks for hardware-efficient supercomputingIEEE Transactions on Computers, 1985
- An 0(n log n) sorting networkPublished by Association for Computing Machinery (ACM) ,1983
- Randomized parallel communication (Preliminary Version)Published by Association for Computing Machinery (ACM) ,1982
- Universal schemes for parallel communicationPublished by Association for Computing Machinery (ACM) ,1981
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979