Horizon: balancing tcp over multiple paths in wireless mesh network

ABSTRACT

There has been extensive work on network architectures that support multi-path routing to improve performance in wireless mesh networks. However, previous work uses ad-hoc design principles that cannot guarantee any network-wide performance objectives such as conjointly maximizing resource utilization and improving fairness. In parallel, numerous theoretical results have addressed the issue of optimizing a combined metric of network utilization and fairness using techniques based on back-pressure scheduling, routing and flow control. However, the proposed theoretical algorithms are extremely difficult to implement in practice, especially in the presence of the 802.11 MAC and TCP. We propose Horizon, a novel system design for multi-path forwarding in wireless meshes, based on the theoretical results on back-pressure. Our design works with an unmodified TCP stack and on top of the existing 802.11 MAC. We modified the back-pressure approach to obtain a simple 802.11-compatible packet-forwarding heuristic and a novel, light-weight path estimator, while maintaining global optimality properties. We propose a delayed reordering algorithm that eliminates TCP timeouts while keeping TCP packet reordering to a minimum. We have evaluated our implementation on a 22-node testbed. We have shown that Horizon effectively utilizes available resources (disjoint paths). In contrast to previous work, our design not only avoids bottlenecks but also optimally load-balances traffic across them when needed, improving fairness among competing flows. To our knowledge, Horizon is the first practical wireless system based on back-pressure.

REFERENCES

• 1: http://research.microsoft.com/pchute.
• 2: U. Akyol, M. Andrews, P. Gupta, J. Hobby, I. Saniee, and A. Stolyar. Joint scheduling and congestion control in mobile ad-hoc networks. In INFOCOM, 2008.
• 3: Hari Balakrishnan , Venkata N. Padmanabhan , Srinivasan Seshan , Randy H. Katz, A comparison of mechanisms for improving TCP performance over wireless links, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.756-769, Dec. 1997 [doi>10.1109/90.650137]
• 4: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 5: Matthew Caesar , Miguel Castro , Edmund B. Nightingale , Greg O'Shea , Antony Rowstron, Virtual ring routing: network routing inspired by DHTs, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 6: C. Cetinkaya and E. Knightly. Opportunistic traffic scheduling over multiple network paths. In Proceedings of INFOCOM, 2004.
• 7: M. Chen, S. Low, M. Chiang, and J. Doyle. Cross-layer congestion control, routing and scheduling design in ad hoc wireless networks. In INFOCOM, 2006.
• 8: A. Eryilmaz and R. Srikant. Joint congestion control, routing and mac for stability and fairness in wireless networks. IEEE Journal on Selected Areas in Communications, 24(8):1514--1524, August 2006.
• 9: 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 INFOCOM, 2003.
• 10: Leonidas Georgiadis , Michael J. Neely , Leandros Tassiulas, Resource allocation and cross-layer control in wireless networks, Foundations and Trends® in Networking, v.1 n.1, p.1-144, April 2006 [doi>10.1561/1300000001]
• 11: Srikanth Kandula , Dina Katabi , Shantanu Sinha , Arthur Berger, Dynamic load balancing without packet reordering, ACM SIGCOMM Computer Communication Review, v.37 n.2, April 2007 [doi>10.1145/1232919.1232925]
• 12: Vikas Kawadia , P. R. Kumar, Experimental investigations into TCP performance over wireless multihop networks, Proceedings 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]
• 13: P. Key and L. Massoulié. Control of communication networks: welfare maximization and multipath transfers. Philosophical Transactions of the Royal Society A, 366(1872), 2008.
• 14: Chaegwon Lim , Haiyun Luo , Chong-ho Choi, RAIN: A Reliable Wireless Network Architecture, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.228-237, November 12-15, 2006 [doi>10.1109/ICNP.2006.320216]
• 15: X. Lin and N. Shroff. Joint rate control and scheduling in multihop wireless networks. In 43rd IEEE CDC, 2004.
• 16: Saverio Mascolo , Claudio Casetti , Mario Gerla , M. Y. Sanadidi , Ren Wang, TCP westwood: Bandwidth estimation for enhanced transport over wireless links, Proceedings of the 7th annual international conference on Mobile computing and networking, p.287-297, July 2001, Rome, Italy [doi>10.1145/381677.381704]
• 17: M. Neely, E. Modiano, and C. Li. Fairness and optimal stochastic control for heterogeneous networks. In INFOCOM, 2005.
• 18: C. Pazos, J. Sanchez-Agrelo, and M. Gerla. Using back-pressure to improve TCP performance with many flows. In Proceedings of INFOCOM, pages 431--438, 1999.
• 19: Larry L. Peterson , Bruce S. Davie, Computer networks: a systems approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 20: Lucian Popa , Costin Raiciu , Ion Stoica , David Rosenblum, Reducing Congestion Effects in Wireless Networks by Multipath Routing, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.96-105, November 12-15, 2006 [doi>10.1109/ICNP.2006.320202]
• 21: Rayadurgam Srikant, The Mathematics of Internet Congestion Control (Systems and Control: Foundations and Applications), SpringerVerlag, 2004
• 22: W. Richard Stevens, TCP/IP illustrated (vol. 1): the protocols, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 23: L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. on Automatic Control, 37(12), 1992.
• 24: Z. Ye, S. V. Krishnamurthy, and T. S. K. Effects of multipath routing on TCP performance in ad hoc networks. In Proc. of IEEE GLOBECOM, 2004.
• 25: Ming Zhang , Brad Karp , Sally Floyd , Larry Peterson, RR-TCP: A Reordering-Robust TCP with DSACK, Proceedings of the 11th IEEE International Conference on Network Protocols, p.95, November 04-07, 2003

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Performance

Keywords:
backpressure, congestion control, multi-path tcp, wireless meshes