Randomized Routing on Fat-Trees,
Abstract
Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda = omega (lg n lg lg n) on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is o (lambda) with probability 1-0(1/n). The best previous bound was 0(lambda lg n) for the off-line problem where switch settings can be determined in advance. In a VLSI-like model where hardware cost is equated with physical volume, we use the routing algorithm to demonstrate that fat-trees are universal routing networks in the sense that any routing network can be efficiently simulated by a fat-tree of comparable hardware cost. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1985
- Accession Number
- ADA166965
Entities
People
- Charles E. Leiserson
- Ronald I. Greenberg
Organizations
- Massachusetts Institute of Technology