A general theory for deadlock-free adaptive routing using a mixed set of resources
Authors:
- T.M. PinkstonTPT.M. Pinkston
- 1 December 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 12 (12) , 1219-1235
Abstract
This paper presents a theoretical framework for the design of deadlock-free fully adaptive routing algorithms for a general class of network topologies and switching techniques in a single, unified theory. A general theory is proposed that allows the design of deadlock avoidance-based as well as deadlock recovery-based wormhole and virtual cut-through adaptive routing algorithms that use a homogeneous or a heterogeneous (mixed) set of resources. The theory also allows channel queues to be allocated nonatomically, utilizing resources efficiently. A general methodology for the design of fully adaptive routing algorithms applicable to arbitrary network topologies is also proposed. The proposed theory and methodology allow the design of efficient network routers that require minimal resources for handling infrequent deadlocks.Keywords
This publication has 52 references indexed in Scilit:
- On the use of virtual channels in networks of workstations with irregular topologyIEEE Transactions on Parallel and Distributed Systems, 2000
- A formal model of message blocking and deadlock resolution in interconnection networksIEEE Transactions on Parallel and Distributed Systems, 2000
- Flexible and efficient routing based on progressive deadlock recoveryIEEE Transactions on Computers, 1999
- Design issues for core-based optoelectronic chips: a case study of the WARRP network routerIEEE Journal of Selected Topics in Quantum Electronics, 1999
- The message flow model for routing in wormhole-routed networksIEEE Transactions on Parallel and Distributed Systems, 1995
- Myrinet: a gigabit-per-second local area networkIEEE Micro, 1995
- Virtual-channel flow controlIEEE Transactions on Parallel and Distributed Systems, 1992
- An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubesIEEE Transactions on Computers, 1991
- Deadlock Avoidance in Store-and-Forward Networks--I: Store-and-Forward DeadlockIEEE Transactions on Communications, 1980
- Virtual cut-through: A new computer communication switching techniqueComputer Networks (1976), 1979