ABSTRACT
Because network resources are finite and, ultimately, are contended for, structural hazards on those resources are inevitable which delay or prevent packet
transmission in the network. This occurs even in networks that feature advanced router architectures. Such hazards cause packets to block which, eventually, can lead to network congestion and, possibly, deadlock. One of the more critical problems to be addressed in order to achieve high network performance and robustness is that of efficiently handling deadlock anomalies. Deadlock occurs when there is a circular hold-and-wait dependency relation on network resources by in-flight packets such that progress in routing those packets is indefinitely inhibited. That is, packets would block in the network forever unless some action to resolve the deadlock situation were taken. This phenomenon can result in the entire network (and system) coming to a complete stand-still, consequently degrading system reliability, availability, and dependability considerably. Thus, it is vitally important to guard against deadlock in such a way as not to impose overly restrictive measures that under-utilize network resources.
