Mark Karol
Abstract
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.
- {1} W. Noureddine and F. Tobagi, "Selective back-pressure in switched ethernet LAN's," in Proc. IEEE GLOBECOM, Dec. 1999, pp. 1256-1263.Google Scholar
- {2} P. M. Merlin and P. J. Schweitzer, "Deadlock avoidance in store-and-forward networks-I: Store-and-forward deadlock," IEEE Trans. Commun., vol. COM-28, pp. 345-354, Mar. 1980.Google Scholar
- {3} K. D. Gunther, "Prevention of deadlocks in packet-switched data transport systems," IEEE Trans. Commun., vol. COM-29, pp. 512-524, Apr. 1981.Google Scholar
- {4} I. S. Gopal, "Prevention of store-and-forward deadlock in computer networks," IEEE Trans. Commun., vol. COM-33, pp. 1258-1264, Dec. 1985.Google Scholar
- {5} I. Cidon, J. M. Jaffe, and M. Sidi, "Distributed store-and-forward deadlock detection and resolution algorithms," IEEE Trans. Commun., vol. COM-35, pp. 1139-1145, Nov. 1987.Google Scholar
- {6} M. D. Schroeder et al., "Autonet: A high-speed, self-configuring local area network using point-to-point links," IEEE J. Select. Areas Commun., vol. 9, pp. 1318-1335, Oct. 1991.Google Scholar
- {7} W. J. Dally and C. L. Seitz, "Deadlock-free message routing in multiprocessor interconnection networks," IEEE Trans. Comput., vol. C-36, pp. 547-553, May 1987. Google Scholar
- {8} E. Leonardi et al., "Congestion control in asynchronous, high-speed wormhole routing networks," IEEE Commun. Mag., pp. 58-69, Nov. 1996. Google Scholar
- {9} D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice-Hall, 1992. Google Scholar
- {10} M. Karol, S. J. Golestani, and D. Lee, "Prevention of deadlocks and live-locks in lossless, backpressured packet networks," in Proc. INFOCOM, Mar. 2000, pp. 1333-1342.Google Scholar
- {11} I. Iliadis, "A new feedback congestion control policy for long propagation delays," IEEE J. Select. Areas Commun., vol. 13, pp. 1284-1295, Sept. 1995. Google Scholar
- {12} I. Iliadis and R. Marie, "Evaluation of a start-stop protocol for best-effort traffic in ATM networks," Comput. Commun. Rev., vol. 21, pp. 1544-1588, 1998. Google Scholar
- {13} R. G. Gallager and S. J. Golestani, "Flow control and routing algorithms for data networks," in Proc. 5th Int. Conf. Computer Communications, 1980, pp. 779-784.Google Scholar
- {14} S. J. Golestani and S. Bhattacharyya, "A class of end-to-end congestion control algorithms for the Internet," in Proc. 6th Int. Conf. Network Protocols , Oct. 1998, pp. 137-150. Google Scholar
Index Terms
- Prevention of deadlocks and livelocks in lossless backpressured packet networks
Recommendations
A packet forwarding controller for mobile IP-based networks with packet buffering
Performance of TCP can be severely degraded in Mobile IP-based wireless networks where packet losses not related to network congestion occur frequently during inter-subnetwork handoffs by user mobility. To solve such a problem in the networks using ...
Improving performance of backpressured packet networks by integrating with an end-to-end congestion control algorithm
Most of the existing congestion control schemes are classified according to where the control decision is made and what the feedback is. In backpressure mechanism, control decision is made hop-by-hop inside the network. These schemes dynamically react ...
A DAG-Based Algorithm for Prevention of Store-and-Forward Deadlock in Packet Networks
Store-and-forward deadlock (SFD) occurs in packet- switched computer networks when, among some cycle of packets buffered by the communication system, each packet in the cycle waits for the use of the buffer currently occupied by the next packet in the ...
Comments