Deadlock-free dynamic reconfiguration schemes for increased network dependability
Authors:
- Ruoming PangRPRuoming Pang
- J. DuatoJDJ. Duato
- 26 August 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 14 (8) , 780-794
Abstract
Network-based parallel computing systems often require the ability to reconfigure the routing algorithm to reflect changes in network topology if and when voluntary or involuntary changes occur. The process of reconfiguring a network's routing capabilities may be very inefficient and/or deadlock-prone if not handled properly. We propose efficient and deadlock-free dynamic reconfiguration schemes that are applicable to routing algorithms and networks which use wormhole, virtual cut-through, or store-and-forward switching, combined with hard link-level flow control. One requirement is that the network architecture use virtual channels or duplicate physical channels for deadlock-handling as well as performance purposes. The proposed schemes do not impede the injection, transmission, or delivery of user packets during the reconfiguration process. Instead, they provide uninterrupted service, increased availability/reliability, and improved overall quality-of-service support as compared to traditional techniques based on static reconfiguration.Keywords
This publication has 20 references indexed in Scilit:
- A general theory for deadlock-free adaptive routing using a mixed set of resourcesIEEE Transactions on Parallel and Distributed Systems, 2001
- A protocol for deadlock-free dynamic reconfiguration in high-speed local area networksIEEE Transactions on Parallel and Distributed Systems, 2001
- 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
- Characterization of deadlocks in k-ary n-cube networksIEEE Transactions on Parallel and Distributed Systems, 1999
- A theory of fault-tolerant routing in wormhole networksIEEE Transactions on Parallel and Distributed Systems, 1997
- Myrinet: a gigabit-per-second local area networkIEEE Micro, 1995
- A new theory of deadlock-free adaptive routing in wormhole networksIEEE Transactions on Parallel and Distributed Systems, 1993
- Autonet: a high-speed, self-configuring local area network using point-to-point linksIEEE Journal on Selected Areas in Communications, 1991
- Virtual cut-through: A new computer communication switching techniqueComputer Networks (1976), 1979