Dynamic load balancing without packet reordering

ABSTRACT

Dynamic load balancing is a popular recent technique that protects ISP networks from sudden congestion caused by load spikes or link failures. Dynamic load balancing protocols, however, require schemes for splitting traffic across multiple paths at a fine granularity. Current splitting schemes present a tussle between slicing granularity and packet reordering. Splitting traffic at the granularity of packets quickly and accurately assigns the desired traffic share to each path, but can reorder packets within a TCP flow, confusing TCP congestion control. Splitting traffic at the granularity of a flow avoids packet reordering but may overshoot the desired shares by up to 60% in dynamic environments, resulting in low end-to-end network goodput

Contrary to popular belief, we show that one can systematically split a single flow across multiple paths without causing packet reordering. We propose FLARE, a new traffic splitting algorithm that operates on bursts of packets, carefully chosen to avoid reordering. Using a combination of analysis and trace-driven simulations, we show that FLARE attains accuracy and responsiveness comparable to packet switching without reordering packets. FLARE is simple and can be implemented with a few KB of router state

REFERENCES

• 1: A. Aggarwal, S. Savage, and T. Anderson. Understanding the performance of TCP pacing. In INFOCOM, 2000.
• 2: Aditya Akella , Srinivasan Seshan , Anees Shaikh, Multihoming performance benefits: an experiment evaluation of practical enterprise strategies, Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference, p.9-9, June 27-July 02, 2004, Boston, MA
• 3: Mark Allman , Wesley M. Eddy , Shawn Ostermann, Estimating loss rates with TCP, ACM SIGMETRICS Performance Evaluation Review, v.31 n.3, p.12-24, December 2003 [doi>10.1145/974036.974038]
• 4: S. Amstutz. Burst switching|an update. In IEEE Commun. Mag., 1986.
• 5: David G. Andersen , Alex C. Snoeren , Hari Balakrishnan, Best-path vs. multi-path overlay routing, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948218]
• 6: Jon C. R. Bennett , Craig Partridge , Nicholas Shectman, Packet reordering is not pathological network behavior, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.789-798, Dec. 1999 [doi>10.1109/90.811445]
• 7: Ethan Blanton , Mark Allman, On making TCP more robust to packet reordering, ACM SIGCOMM Computer Communication Review, v.32 n.1, p.20-30, January 2002 [doi>10.1145/510726.510728]
• 8: James E. Burns , Teunis J. Ott , Anthony E. Krzesinski , Karen E. Müller, Path selection and bandwidth allocation in MPLS networks, Performance Evaluation, v.52 n.2-3, p.133-152, April 2003 [doi>10.1016/S0166-5316(02)00177-3]
• 9: Z. Cao, Z. Wang, and E. W. Zegura. Performance of hashing-based schemes for internet load balancing. In IEEE INFOCOM, 2000.
• 10: C. N. Chuah and C. Diot. A tier-1 isp prespective: Design principles & observations of routing behavior. In PAM, 2002.
• 11: Cisco express forwarding (cef). Cisco white paper, Cisco Systems., July 2002.
• 12: A. Elwalid, C. Jin, S. H. Low, and I. Widjaja. MATE: MPLS Adaptive Traffic Engineering. In INFOCOM, 2001.
• 13: B. Fortz and M. Thorup. Internet Traffic Engineering by Optimizing OSPF Weights in a Changing World. In INFOCOM, 2000.
• 14: B. Fortz and M. Thorup. Optimizing OSPF Weights in a Changing World. In IEEE JSAC, 2002.
• 15: R. G. Gallager. In Discrete Stochatic Processes, 1996.
• 16: H. Jiang and C. Dovrolis. The origin of tcp traffic burstiness in short time scales. Technical report, Georgia Tech., 2004.
• 17: Junos 6.3 internet software routing protocols configuration guide. www.juniper.net/techpubs/software/junos/junos63/swconfig63-routing/html/.
• 18: Srikanth Kandula , Dina Katabi , Bruce Davie , Anna Charny, Walking the tightrope: responsive yet stable traffic engineering, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 19: S. Katti, C. Blake, D. Katabi, E. Kohler, and J. Strauss. M&M: Passive measurement tools for internet modeling. In ACM IMC, 2004.
• 20: M. Laor and L. Gendel. The effect of packet reordering in a backbone link on application throughput. IEEE Network, 2002.
• 21: Reiner Ludwig , Randy H. Katz, The Eifel algorithm: making TCP robust against spurious retransmissions, ACM SIGCOMM Computer Communication Review, v.30 n.1, January 2000 [doi>10.1145/505688.505692]
• 22: K. Papagiannaki, N. Taft, and C. Diot. Impact of flow dynamics on traffic engineering design principles. In INFOCOM, Hong Kong, March 2004.
• 23: Vern Paxson, End-to-end internet packet dynamics, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.277-292, June 1999 [doi>10.1109/90.779192]
• 24: V. Paxson and M. Allman. Computing tcp's retransmission timer, 2000. IETF RFC 2988.
• 25: S. Rost and H. Balakrishnan. Rate-aware splitting of aggregate traffic. Technical report, MIT, 2003.
• 26: Matthew Roughan , Albert Greenberg , Charles Kalmanek , Michael Rumsewicz , Jennifer Yates , Yin Zhang, Experience in measuring backbone traffic variability: models, metrics, measurements and meaning, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637213]
• 27: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round robin, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.231-242, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 28: C. Villamizar. MPLS Optimized Multipath (MPLS-OMP), 1999. Internet Draft.
• 29: C. Villamizar. Ospf Optimized Multipath (OSPF-OMP), 1999. Internet Draft.
• 30: Hao Wang , Haiyong Xie , Lili Qiu , Yang Richard Yang , Yin Zhang , Albert Greenberg, COPE: traffic engineering in dynamic networks, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 31: Y. Wang and Z. Wang. Explicit routing algorithms for internet traffic engineering. In IEEE ICCCN, 1999.
• 32: Lixia Zhang , Scott Shenker , Daivd D. Clark, Observations on the dynamics of a congestion control algorithm: the effects of two-way traffic, Proceedings of the conference on Communications architecture & protocols, p.133-147, September 03-06, 1991, Zurich, Switzerland
• 33: 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
• 34: Yin Zhang , Lee Breslau , Vern Paxson , Scott Shenker, On the characteristics and origins of internet flow rates, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 35: Z.-L. Zhang, V. Ribeiro, S. Moon, and C. Diot. Small-time scaling behaviors of internet backbone traffic. In INFOCOM, 2003.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
FLARE, packet reordering, traffic splitting