TY - JOUR
T1 - Prevention of Deadlocks and Livelocks in Lossless Backpressured Packet Networks
AU - Karol, Mark
AU - Golestani, S. Jamaloddin
AU - Lee, David
PY - 2003/12
Y1 - 2003/12
N2 - No packets will be dropped inside a packet network, even when congestion builds up, if congested nodes send backpressure feedback to neighboring nodes, informing them of unavailability of buffering capacity - stopping them from forwarding more packets until enough buffer becomes available. While there are potential advantages in backpressured networks that do not allow packet dropping, such networks are susceptible to a condition known as deadlock in which throughput of the network or part 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 backpressured packet networks. In contrast with prior approaches, our proposed technique does not introduce any packet losses, does not corrupt packet sequence, and does not require any changes to packet headers. It represents a new networking paradigm in which internal network losses are avoided (thereby simplifying the design of other network protocols) and internal network delays are bounded.
AB - No packets will be dropped inside a packet network, even when congestion builds up, if congested nodes send backpressure feedback to neighboring nodes, informing them of unavailability of buffering capacity - stopping them from forwarding more packets until enough buffer becomes available. While there are potential advantages in backpressured networks that do not allow packet dropping, such networks are susceptible to a condition known as deadlock in which throughput of the network or part 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 backpressured packet networks. In contrast with prior approaches, our proposed technique does not introduce any packet losses, does not corrupt packet sequence, and does not require any changes to packet headers. It represents a new networking paradigm in which internal network losses are avoided (thereby simplifying the design of other network protocols) and internal network delays are bounded.
KW - Backpressure
KW - Bounded delay
KW - Congestion control
KW - Deadlock prevention
KW - Livelock prevention
KW - Lossless networks
UR - http://www.scopus.com/inward/record.url?scp=0346686075&partnerID=8YFLogxK
U2 - 10.1109/TNET.2003.820434
DO - 10.1109/TNET.2003.820434
M3 - Review article
AN - SCOPUS:0346686075
SN - 1063-6692
VL - 11
SP - 923
EP - 934
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 6
ER -