Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

One of the triumphs of wireline network research of the last decade has been the casting of the Internet congestion control problem within an optimization framework based on utility functions. Such an approach provides a sound understanding of the underlying stability and fairness issues, as well as a post-facto justification of TCP-like additive-increase multiplicative-decrease (AIMD) algorithms. This paper provides a counter-example showing that the same result cannot be extended to wireless networks, at least not in a straightforward manner.The fundamental difference is that wireless networks are of a broadcast nature. There is no strict notion of a "link," since transmissions from nearby nodes interfere with each other. Using a simple model of interference in wireless networks, a counter-example of a wireless network is presented in which the congestion control mechanism has an unstable equilibrium point at the desired fair solution. Further, ns-2 simulations of this counter-example manifest an oscillatory behavior. Surprisingly, this oscillatory behavior appears to be fairly typical in wireless networks, with most randomly chosen network examples manifesting it. This loss of stability suggests a possible need for the re-design of wireless TCP and wireless queue management to explicitly account for the wireless nature of the effects of interference. wireless interference can make this mechanism unstable. We present counter-example wireless graphs and flow patterns in which the congestion control mechanism fails to remain stable. ns-2 simulations indicate that this loss of stability manifests in practice as oscillatory behavior. Moreover, this oscillatory behavior is fairly typical in wireless networks. This loss of stability suggests a need for the re-design of wireless TCP and wireless queue management to explicitly account for the effects of interference.

REFERENCES

• 1: F. Kelly, A. Maulloo, and D. Tan, "Rate control in communication networks: shadow prices, proportional fairness and stability," in Journal of the Operational Research Society, vol. 49, 1998.
• 2: Steven H. Low, A duality model of TCP and queue management algorithms, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.525-536, August 2003 [doi>10.1109/TNET.2003.815297]
• 3: K. Ramakrishnan, S. Floyd, and D. Black, "RFC 3168 - the addition of Explicit Congestion Notification (ECN) to IP," 2001.
• 4: F. Xue, L. L. Xie, and P. R. Kumar, "The transport capacity of wireless networks over fading channels," IEEE Trans. on Information Theory, vol. 51, no. 3, pp. 834--847, Mar 2005.
• 5: R. M. Gray, "Toeplitz and circulant matrices: A review," 2002. {Online}. Available: http://www-ee.stanford.edu/~gray/toeplitz.pdf
• 6: A. Veres and M. Boda, "The chaotic nature of TCP congestion control." in Proceedings of IEEE INFOCOM, 2000, pp. 1715--1723.
• 7: A. Gilbert, Y. Joo, and N. McKeown, "Congestion control and periodic behaviour," in LANMAN Workshop, 2001.
• 8: F. Kelly, "Charging and rate control for elastic traffic," European Transactions on Telecommunications, vol. 8, pp. 33--37, January 1997.
• 9: S. Kunniyur and R. Srikant, "A time scale decomposition approach to adaptive ECN marking," in Proceedings of IEEE INFOCOM, 2001, pp. 1330--1339.
• 10: Steven H. Low , David E. Lapsley, Optimization flow control—I: basic algorithm and convergence, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.861-874, Dec. 1999 [doi>10.1109/90.811451]
• 11: Hari Balakrishnan , Srinivasan Seshan , Randy H. Katz, Improving reliable transport and handoff performance in cellular wireless networks, Wireless Networks, v.1 n.4, p.469-481, 1995 [doi>10.1007/BF01985757]
• 12: A. Bakre , B. R. Badrinath, I-TCP: indirect TCP for mobile hosts, Proceedings of the 15th International Conference on Distributed Computing Systems, p.136, May 30-June 02, 1995
• 13: Kartik Chandran , Sudarshan Raghunathan , S. Venkatesan , Ravi Prakash, A Feedback Based Scheme for Improving TCP Performance in Ad-Hoc Wireless Networks, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.472, May 26-29, 1998
• 14: Gavin Holland , Nitin Vaidya, Analysis of TCP performance over mobile ad hoc networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.219-230, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313540]
• 15: Z. Fu, P. Zerfos, H. Luo, S. Lu, L. Zhang, and M. Gerla, "The impact of multihop wireless channel on TCP throughput and loss," in Proceedings of IEEE INFOCOM, 2003.
• 16: Vikas Kawadia , P. R. Kumar, Experimental investigations into TCP performance over wireless multihop networks, Proceeding of the 2005 ACM SIGCOMM workshop on Experimental approaches to wireless network design and analysis, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080148.1080155]
• 17: M. Gerla, K. Tang, and R. Bagrodia, "TCP performance in wireless multi-hop networks," 1999.
• 18: Kaixin Xu , Mario Gerla , Lantao Qi , Yantai Shu, Enhancing TCP fairness in ad hoc wireless networks using neighborhood RED, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938988]
• 19: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 20: Thyagarajan Nandagopal , Tae-Eun Kim , Xia Gao , Vaduvur Bharghavan, Achieving MAC layer fairness in wireless packet networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.87-98, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345925]
• 21: X. Lin and N. Shroff, "Joint rate control and scheduling in multihop wireless networks," in Proceedings of IEEE CDC, 2004.
• 22: L. Chen, S. Low, and J. Doyle, "Joint congestion control and media access control design for ad hoc wireless networks," in Proceedings of IEEE INFOCOM, 2005.
• 23: Daniel R. Figueiredo , Benyuan Liu , Vishal Misra , Don Towsley, On the autocorrelation structure of TCP traffic, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.40 n.3, p.339-361, 22 October 2002 [doi>10.1016/S1389-1286(02)00299-2]
• 24: Liang Guo , Mark Crovella , Ibrahim Matta, How Does TCP Generate Pseudo-Self-Similarity?, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.215, August 15-18, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms, Performance

Keywords:
TCP, congestion control, fairness, stability, wireless ad hoc networks