Article

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

Authors:

Mike H. MacGregor,

Pawel GburzynskiAuthors Info & Claims

ANCS '05: Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems

Pages 145 - 152

https://doi.org/10.1145/1095890.1095911

Published: 26 October 2005 Publication History

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]

J. Aikat, J. Kaur, F. D. Smith, and K. Jeffay. Variability in tcp round-trip times. In IMC '03, pages 279--284, Miami Beach, FL, USA, 2003. ACM Press.

Digital Library

[3]

J. C. R. Bennett, C. Partridge, and N. Shectman. Packet reordering is not pathological network behavior. IEEE/ACM Trans. Netw., 7(6):789--798, 1999.

Digital Library

[4]

E. Blanton and M. Allman. On the impact of bursting on tcp performance. In PAM '05, Boston, MA, USA, March 2005.

Digital Library

[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]

R. Fonseca, V. Almeida, and M. Crovella. Locality in a web of streams. Commun. ACM, 48(1):82--88, 2005.

Digital Library

[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.

Digital Library

[8]

H. Jiang and C. Dovrolis. Source-level ip packet bursts: causes and effects. In IMC '03, Miami, FL, USA, October 2003.

Digital Library

[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]

S. Jin and A. Bestavros. Sources and characteristics of web temporal locality. In MASCOTS '00, pages 28--35, San Fransisco, CA, USA, August 2000.

Digital Library

[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.

Digital Library

[13]

K. Papagiannaki, R. Cruz, and C. Diot. Network performance monitoring at small time scales. In IMC '03, pages 295--300, Miami Beach, FL, USA, 2003. ACM Press.

Digital Library

[14]

C. Partridge, et al. A 50-gb/s ip router. IEEE/ACM Trans. Netw., 6(3):237--248, 1998.

Digital Library

[15]

S. Shakkottai, N. Brownlee, and K. Klaffy. A study of burstiness in tcp flows. In PAM '05, Boston, MA, USA, March 2005.

Digital Library

[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.

Digital Library

[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.

Digital Library

[19]

W. Shi, M. H. MacGregor, and P. Gburzynski. Load balancing for parallel forwarding. IEEE/ACM Transactions on Networking, 13(4), 2005.

Digital Library

[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.

Cited By

Xia YHamdi MChao H(2016)A Practical Large-Capacity Three-Stage Buffered Clos-Network Switch ArchitectureIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.240861427:2(317-328)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2408614
Liu BLu JKai YWang YTian Pan (2014)Power-proportional router: Architectural design and experimental evaluation2014 IEEE 22nd International Symposium of Quality of Service (IWQoS)10.1109/IWQoS.2014.6914339(344-349)Online publication date: May-2014
https://doi.org/10.1109/IWQoS.2014.6914339
Shi LLiu BSun CYin ZBhuyan LChao H(2012)Load-Balancing Multipath Switching System with Flow SliceIEEE Transactions on Computers10.1109/TC.2010.27961:3(350-365)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1109/TC.2010.279
Show More Cited By

Index Terms

A scalable load balancer for forwarding internet traffic: exploiting flow-level burstiness
1. Networks
  1. Network architectures

Recommendations

An Adaptive Load Balancer for Multiprocessor Routers

By investigating flow-level characteristics of Internet traffic, the authors are able to trace the root of load imbalance in hash-based load-splitting schemes. They model flow popularity distributions as Zipf-like and prove that for typical Internet ...
The impact of bursty traffic on FPCF packet switch performance

This paper analyses and compares the performance of forward planning conflict-free (FPCF), virtual output queuing-partitioned (VOQ-P) and virtual output queuing-shared (VOQ-S) packet switches. The influence of packet burst size, offered switch load and ...
Load balancing for parallel forwarding

Workload distribution is critical to the performance of network processor based parallel forwarding systems. Scheduling schemes that operate at the packet level, e.g., round-robin, cannot preserve packet-ordering within individual TCP connections. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ANCS '05: Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems

October 2005

230 pages

ISBN:1595930825

DOI:10.1145/1095890

General Chair:
Alan Berenbaum
SMSC
,
Program Chairs:
Kai Li
Princeton University, Princeton, NJ
,
Jonathan Turner
Washington University in St. Louis

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 October 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ANCS05

Sponsor:

ANCS05: Symposium on Architecture for Networking and Communications Systems 2005

October 26 - 28, 2005

NJ, Princeton, USA

Acceptance Rates

Overall Acceptance Rate 88 of 314 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
528
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xia YHamdi MChao H(2016)A Practical Large-Capacity Three-Stage Buffered Clos-Network Switch ArchitectureIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.240861427:2(317-328)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2408614
Liu BLu JKai YWang YTian Pan (2014)Power-proportional router: Architectural design and experimental evaluation2014 IEEE 22nd International Symposium of Quality of Service (IWQoS)10.1109/IWQoS.2014.6914339(344-349)Online publication date: May-2014
https://doi.org/10.1109/IWQoS.2014.6914339
Shi LLiu BSun CYin ZBhuyan LChao H(2012)Load-Balancing Multipath Switching System with Flow SliceIEEE Transactions on Computers10.1109/TC.2010.27961:3(350-365)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1109/TC.2010.279
Khazali IAgarwal A(2012)Load balancing with minimal flow remapping for network processors2012 IEEE Symposium on Computers and Communications (ISCC)10.1109/ISCC.2012.6249373(000662-000666)Online publication date: Jul-2012
https://doi.org/10.1109/ISCC.2012.6249373
Kuang JBhuyan LXie HGuo D(2011)E-AHRWProceedings of the 2011 ACM/IEEE Seventh Symposium on Architectures for Networking and Communications Systems10.1109/ANCS.2011.15(45-56)Online publication date: 3-Oct-2011
https://dl.acm.org/doi/10.1109/ANCS.2011.15
Nelms TAhamad MLin BMogul JIyer R(2010)Packet scheduling for deep packet inspection on multi-core architecturesProceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems10.1145/1872007.1872033(1-11)Online publication date: 25-Oct-2010
https://dl.acm.org/doi/10.1145/1872007.1872033
Musoll E(2010)A cost-effective load-balancing policy for tile-based, massive multi-core packet processorsACM Transactions on Embedded Computing Systems10.1145/1698772.16987829:3(1-25)Online publication date: 5-Mar-2010
https://dl.acm.org/doi/10.1145/1698772.1698782
Liu TSun YZhang ZGuo L(2009)Load balancing for flow-based parallel processing systems in CMP architectureProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811982.1812161(4694-4700)Online publication date: 30-Nov-2009
https://dl.acm.org/doi/10.5555/1811982.1812161
Liu JTao MXu YWang X(2009)Superimposed XOR: A New Physical Layer Network Coding Scheme for Two-Way Relay ChannelsGLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference10.1109/GLOCOM.2009.5426240(1-6)Online publication date: Nov-2009
https://doi.org/10.1109/GLOCOM.2009.5426240
Liu WFeng K(2009)Realization of Greedy Anti-Void Routing Protocol for Wireless Sensor NetworksGLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference10.1109/GLOCOM.2009.5425945(1-6)Online publication date: Nov-2009
https://doi.org/10.1109/GLOCOM.2009.5425945
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten