Prevention of Deadlocks and Livelocks in Lossless: Backpressured Packet Networks

When congestion builds up in a packet network, two general approaches are possible to cope with the shortage of buffer space. One approach is to drop incoming packets for which buffer is not available and to rely on the end- to-end protocols for the recovery of lost packets. The alternative approach is to insist that no packets should be dropped inside a packet network, even when congestion builds up. This goal may be accomplished by, for example, having the congested nodes send backpressure feedback to neighboring nodes, informing them of unavailability of buffering capacity and in effect stopping them from forwarding more packets until enough buffer becomes available. While there are potential advantages in back- pressured networks that do not allow packet dropping, such networks are susceptible to a condition known as deadlock in which throughput of the network goes to zero (i.e., no packets are transmitted). In this paper, we describe a simple, lossless method of preventing deadlocks and livelocks in back pressured packet networks.