Paper Info
Title
A necessary and sufficient condition for deadlock-free wormhole routing
Abstract
Abstract An important open problem,in wormhole,routing has been to find a necessary and sufficie nt condition for deadlock-free adaptive routing. Recently, Duato has solved this problem f or a restricted class of adaptive routing algorithms. In this paper, a necessary and sufficient condition is proposed that can be used for any adaptive or nonadaptive routing algorithm for wormhole routing, as long as only local information is required for routing. The underlying proof technique intr oduces a new type of dependency graph, the channel waiting graph, which omits most channel dependencies that cannot be used to create a deadlock configuration. The necessary and suffic ient condition can be applied in a straightforward manner to most routing algorithms. This is i llustrated by proving deadlock freedom for a partially adaptive nonminimal,mesh routing algorithm that does not require virtual channels and a fully adaptive minimal hypercube routing algorithm with two virtual channels per physical channel. Both routing algorithms are more adaptive than any previously proposed routing algorithm with similar virtual channel requirements. Keywords: wormhole routing, routing algorithms, deadlock freedom, channel waiting graph, nec-
Year
DOI
Venue
1996
10.1006/jpdc.1996.0008
J. Parallel Distrib. Comput.
Keywords
Field
DocType
sufficient condition,deadlock-free wormhole routing,adaptive routing,routing algorithms
Equal-cost multi-path routing,Multipath routing,Link-state routing protocol,Dynamic Source Routing,Enhanced Interior Gateway Routing Protocol,Static routing,Computer science,Destination-Sequenced Distance Vector routing,Wireless Routing Protocol,Distributed computing
Journal
Volume
Issue
ISSN
32
1
Journal of Parallel and Distributed Computing
Citations 
PageRank 
References 
46
1.75
21
Authors
2
Name
Order
Citations
PageRank
Loren Schwiebert187190.17
D. N. Jayasimha215816.02