A scalable load balancer for forwarding internet traffic: exploiting flow-level burstiness

ABSTRACT

Packet scheduling in parallel forwarding systems is a hard problem. Two major goals of a scheduler that distributes incoming packets to multiple forwarding engines are to achieve high system utilization (by balancing the load evenly among the multiple engines) and to maintain packet ordering within individual flows. Additionally, from the viewpoint of the overall performance, the system should exhibit a good cache behavior by preserving temporal locality in the workload of each forwarding engine. In this paper, we show how the burstiness in Internet flows can be exploited to improve the performance of the scheduler. Specifically, TCP flows, which contribute to over 90 percent of the Internet traffic, transmit in bursts with relatively large delays in between. We propose a load balancing scheme based on this insight to achieve the scheduling goals. Our design is verified by simulations driven by real-world traces.

REFERENCES

• 1: L. Adamic and B. Huberman. Zipf's law and the internet. Glottometrics 3, pages 143--150, 2002.
• 2: Jay Aikat , Jasleen Kaur , F. Donelson Smith , Kevin Jeffay, Variability in TCP round-trip times, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948241]
• 3: 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]
• 4: E. Blanton and M. Allman. On the impact of bursting on tcp performance. In PAM '05, Boston, MA, USA, March 2005.
• 5: J. Duffy. Someone's having core router problems, but who is it?, November 2000. http://www.nwfusion.com/edge/news/2000/-1109routerprob.html.
• 6: Rodrigo Fonseca , Virgílio Almeida , Mark Crovella, Locality in a web of streams, Communications of the ACM, v.48 n.1, p.82-88, January 2005 [doi>10.1145/1039539.1039543]
• 7: R. Jain and S. Routhier. Packet trains: Measurements and a new model for computer network traffic. IEEE Journal of Selected Areas in Communications, SAC-4(6):986--995, September 1986.
• 8: Hao Jiang , Constantinos Dovrolis, Source-level IP packet bursts: causes and effects, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948245]
• 9: H. Jiang and C. Dovrolis. The effect of flow capacities on the burstiness of aggregated traffic. In PAM '04, Antibes Juan-les-Pins, France, April 2004.
• 10: Shudong Jin , Azer Bestavros, Sources and Characteristics of Web Temporal Locality, Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.28, August 29-September 01, 2000
• 11: J.-Y. Jo, Y. Kim, H. J. Chao, and F. Merat. Internet traffic load balancing using dynamic hashing with flow volumes. In Internet Performance and Control of Network Systems III at SPIE ITCOM 2002, pages 154--165, Boston, MA, USA, July 2002.
• 12: M. Laor and L. Gendel. The effect of packet reordering in a backbone link on application throughput. IEEE Network, 16(5):28--36, 2002.
• 13: Konstantina Papagiannaki , Rene Cruz , Christophe Diot, Network performance monitoring at small time scales, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948244]
• 14: Craig Partridge , Philip P. Carvey , Ed Burgess , Isidro Castineyra , Tom Clarke , Lise Graham , Michael Hathaway , Phil Herman , Allen King , Steve Kohalmi , Tracy Ma , John Mcallen , Trevor Mendez , Walter C. Milliken , Ronald Pettyjohn , John Rokosz , Joshua Seeger , Michael Sollins , Steve Storch , Benjamin Tober , Gregory D. Troxel, A 50-Gb/s IP router, IEEE/ACM Transactions on Networking (TON), v.6 n.3, p.237-248, June 1998 [doi>10.1109/90.700888]
• 15: S. Shakkottai, N. Brownlee, and K. Klaffy. A study of burstiness in tcp flows. In PAM '05, Boston, MA, USA, March 2005.
• 16: W. Shi, M. H. MacGregor, and P. Gburzynski. Traffic locality charateristics in a parallel forwarding system. International Journal of Communication Systems, 16(9):823--839, November 2003.
• 17: W. Shi, M. H. MacGregor, and P. Gburzynski. A novel load balancer for multiprocessor routers. In SPECTS '04, pages 671--679, San Jose, CA, USA, July 2004.
• 18: W. Shi, M. H. MacGregor, and P. Gburzynski. Synthetic trace generation for the internet: An integrated model. In SPECTS '04, pages 471--477, San Jose, CA, USA, July 2004.
• 19: Weiguang Shi , M. H. MacGregor , Pawel Gburzynski, Load balancing for parallel forwarding, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.790-801, August 2005 [doi>10.1109/TNET.2005.852881]
• 20: W. Shi, M. H. MacGregor, and P. Gburzynski. A Load-balancing Scheme for Parallel Internet Forwarding Systems. Unpublished manuscript, 2004.
• 21: S. Sinha, S. Kandula, and D. Katabi. Harnessing tcps burstiness using flowlet switching. In 3rd ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets), San Diego, CA, November 2004.
• 22: G. K. Zipf. Human Behavior and the Principle of Least-Effort. Addison-Wesley, Cambridge, MA, 1949.

INDEX TERMS

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

General Terms:
Measurement, Performance

Keywords:
TCP, bursty traffic, hashing, load balancing, parallel forwarding