Article

Sequence-preserving adaptive load balancers

Authors:

Lukas KenclAuthors Info & Claims

ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems

Pages 143 - 152

https://doi.org/10.1145/1185347.1185367

Published: 03 December 2006 Publication History

Abstract

Load balancing in packet-switched networks is a task of ever-growing importance. Network traffic properties, such as the Zipf-like flow length distribution and bursty transmission patterns, and requirements on packet ordering or stable flow mapping, make it a particularly difficult and complex task, needing adaptive heuristic solutions. In this paper, we present two main contributions:Firstly, we evaluate and compare two recently proposed algorithmic heuristics that attempt to adaptively balance load among the destination units. The evaluation on real life traces confirms the previously conjectured impact of the Zipf-like flow length distribution and traffic burstiness. Furthermore, we identify the distinction between the goals of preserving either the sequence order of packets, or the flow-to-destination mapping, showing different strengths of each algorithm. Secondly, we demonstrate a novel hybrid scheme that combines best of the flow-based and burst-based load balancing techniques and excels in both of the key metrics of flow remapping and packet reordering.

References

[1]

H. Adiseshu, G. Parulkar, and G. Varghese. A reliable and scalable striping protocol. In Proceedings of ACM SIGCOMM, Stanford University, CA, USA, September 1996.

Digital Library

[2]

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

Digital Library

[3]

Z. Cao, Z. Wang, and E. Zegura. Performance of hashing-based schemes for Internet load balancing. In IEEE INFOCOM 2000, pages 332--341, Tel-Aviv, Israel, March 2000.

[4]

T. L. Casavant and J. G. Kuhl. A taxonomy of scheduling in general-purpose distributed computing systems. IEEE Transactions on Software Engineering, 14(2):141--154, February 1988.

Digital Library

[5]

D. E. Comer. Network Systems Design using Network Processors. Prentice Hall, 2004.

Digital Library

[6]

G. Dittmann and A. Herkersdorf. Network processor load balancing for high-speed links. In 2002 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS 2002), pages 727--735, San Diego, CA, USA, July 2002.

[7]

D. L. Eager, E. D. Lazowska, and J. Zahorjan. Adaptive load sharing in homogenous distributed systems. IEEE Transactions on Software Engineering, 12(5):662--675, May 1986.

Digital Library

[8]

R. Haas, P. Droz, L. Kencl, A. Kind, B. Metzler, C. Jeffries, R. Pletka, and M. Waldvogel. Creating advanced functions on network processors: Experience and perspectives. IEEE Network, 2003.

Digital Library

[9]

J. Jo, Y. Kim, H. 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.

[10]

L. Kencl and J.-Y. L. Boudec. Adaptive load sharing for network processors. In Proceedings of IEEE Infocom, New York, 2002.

[11]

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

[12]

A. Moore, J. Hall, E. Harris, C. Kreibich, and I. Pratt. Architecture of a network monitor. In Proceedings of the Fourth Passive and Active Measurement (PAM)Workshop, April 2003.

[13]

NLANR (National Laboratory for Applied Network Research) Measurement and Operations Analysis Team (MOAT). Packet header traces. http://moat.nlanr.net.

[14]

K. W. Ross. Hash routing for collections of shared Web caches. IEEE Network,11(7):37--44, Nov-Dec 1997.

Digital Library

[15]

S. Sarvotham, R. Riedi, and R. Baraniuk. Connection-level analysis and modeling of network traffic. In ACM SIGCOMM Internet Measurement Workshop, pages 99--103, San Francisco, CA, USA, November 2001.

Digital Library

[16]

A. Shaikh, J. Rexford, and K. Shin. Load-sensitive routing of long-lived IP flows. In Proceedings of ACM SIGCOMM, pages 215--226, 1999.

Digital Library

[17]

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.

[18]

W. Shi, M. H. MacGregor, and P. Gburzynski. Load balancing for parallel forwarding. IEEE/ACM Transactions on Networking, 2004. to appear.

Digital Library

[19]

W. Shi, M. H. MacGregor, and P. Gburzynski. A scalable load balancer for forwarding Internet traffic: Exploiting flow-level burstiness. In Symposium on Architectures for Networking and Communications Systems (ANCS), Princeton, NJ, USA, October 2005.

Digital Library

[20]

S. Sinha, S. Kandula, and D. Katabi. Harnessing TCP 's burstiness with flowlet switching. In HotNets 2004, San Diego, CA, USA, November 2004.

[21]

J. Spirn. Program Behavior: Models and Measurements. Elsevier-North Holland, N.Y., 1977.

Digital Library

[22]

D. G. Thaler and C. V. Ravishankar. Using name-based mappings to increase hit rates. IEEE/ACM Transactions on Networking, 6(1): 1--14, February 1998.

Digital Library

[23]

G. K. Zipf. Human Behavior and the Principle of Least-Effort. Addison-Wesley, Cambridge, MA, 1949.

Cited By

Li CSong LZeng X(2021)An Adaptive Throughput-First Packet Scheduling Algorithm for DPDK-Based Packet Processing SystemsFuture Internet10.3390/fi1303007813:3(78)Online publication date: 19-Mar-2021
https://doi.org/10.3390/fi13030078
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
Iqbal MHolt JRyoo Jde Veciana GJohn L(2016)Dynamic Core Allocation and Packet Scheduling in Multicore Network ProcessorsIEEE Transactions on Computers10.1109/TC.2016.256083865:12(3646-3660)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1109/TC.2016.2560838
Show More Cited By

Index Terms

Sequence-preserving adaptive load balancers
1. Networks
  1. Network architectures

Recommendations

A distributed backoff-channel deflection algorithm with load balancing for optical burst switching networks

Optical burst contention is one of the major factors that cause the burst loss in the optical burst switching (OBS) networks. So far, various contention resolution schemes have been proposed. Among them, the deflection path is more attractive due to its ...
Load balanced Birkhoff-von Neumann switches, part I: one-stage buffering

Motivated by the need for a simple and high performance switch architecture that scales up with the speed of fiber optics, we propose a switch architecture with two-stage switching fabrics and one-stage buffering. The first stage performs load balancing,...
Elastic Load Balancing Classic Load Balancers

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems

December 2006

202 pages

ISBN:1595935800

DOI:10.1145/1185347

General Chair:
Laxmi N. Bhuyan
University of California, Riverside, USA
,
Program Chairs:
Michel Dubois
University of Southern California, USA
,
Will Eatherton
Cisco, USA

Copyright © 2006 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: 03 December 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ANCS06

Sponsor:

ANCS06: Symposium on Architecture for Networking and Communications Systems

December 3 - 5, 2006

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 88 of 314 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
397
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li CSong LZeng X(2021)An Adaptive Throughput-First Packet Scheduling Algorithm for DPDK-Based Packet Processing SystemsFuture Internet10.3390/fi1303007813:3(78)Online publication date: 19-Mar-2021
https://doi.org/10.3390/fi13030078
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
Iqbal MHolt JRyoo Jde Veciana GJohn L(2016)Dynamic Core Allocation and Packet Scheduling in Multicore Network ProcessorsIEEE Transactions on Computers10.1109/TC.2016.256083865:12(3646-3660)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1109/TC.2016.2560838
Chun-Hua Z(2014)MC-SPSProceedings of the 2014 Sixth International Conference on Measuring Technology and Mechatronics Automation10.1109/ICMTMA.2014.98(398-400)Online publication date: 10-Jan-2014
https://dl.acm.org/doi/10.1109/ICMTMA.2014.98
Cho JJin HLee MSchwan K(2014)Dynamic core affinity for high-performance file upload on Hadoop Distributed File SystemParallel Computing10.1016/j.parco.2014.07.00540:10(722-737)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.parco.2014.07.005
Xiong BYang KLi FChen XZhang JTang QLuo Y(2014)The impact of bitwise operators on hash uniformity in network packet processingInternational Journal of Communication Systems10.1002/dac.253227:11(3158-3184)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1002/dac.2532
Jiang HZhang GXie GSalamatian KMathy LNajjar WYavatkar RRixner S(2013)Scalable high-performance parallel design for network intrusion detection systems on many-core processorsProceedings of the ninth ACM/IEEE symposium on Architectures for networking and communications systems10.5555/2537857.2537883(137-146)Online publication date: 21-Oct-2013
https://dl.acm.org/doi/10.5555/2537857.2537883
Cho JJin HLee MSchwan KSun XChen YRoth P(2013)On the core affinity and file upload performance of HadoopProceedings of the 2013 International Workshop on Data-Intensive Scalable Computing Systems10.1145/2534645.2534651(25-30)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.1145/2534645.2534651
Iqbal MHolt JRyoo JJohn LVeciance G(2013)Flow Migration on Multicore Network ProcessorsProceedings of the 2013 42nd International Conference on Parallel Processing10.1109/ICPP.2013.24(150-159)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1109/ICPP.2013.24
Jiang HZhang GXie GSalamatian KMathy L(2013)Scalable high-performance parallel design for Network Intrusion Detection Systems on many-core processorsArchitectures for Networking and Communications Systems10.1109/ANCS.2013.6665196(137-146)Online publication date: Oct-2013
https://doi.org/10.1109/ANCS.2013.6665196
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