Deadlock Resolution in Networks Employing Connection-Based Adaptive Routing
Yoshio Turner, Yuval Tamir · 1996
Adaptive routing is used in networks in order to achieve fault tolerance and optimize performance for all traffic patterns. Most adaptive routing schemes route each packet independently, requiring addressing and sequencing information to be transmitted and processed for each packet. Connection-based message transport, such as virtual circuits, reduces the overhead for routing packets through the network and maintain FIFO packets delivery. Dynamic Virtual Circuits (DVCs) combine the advantages of adaptive routing and connection-based message transport. When used with arbitrary topologies and without restricting the routes of packets, networks employing DVCs are susceptible to deadlocks. In this paper we investigate a scheme for resolving such deadlocks. The scheme takes into account dependencies introduced by the DVC mechanism as well as the inherent dependencies among packet buffers at the input ports of each switch. Detailed simulations of the scheme have been performed using a multi-threaded event-driven simulator. Preliminary performance results are presented.