research-article

Load balancing with JET: just enough tracking for connection consistency

Authors:

Shay Vargaftik,

Dean H. Lorenz,

Kathy Barabash,

Isaac Keslassy,

Ariel OrdaAuthors Info & Claims

CoNEXT '21: Proceedings of the 17th International Conference on emerging Networking EXperiments and Technologies

Pages 191 - 204

https://doi.org/10.1145/3485983.3494851

Published: 03 December 2021 Publication History

Abstract

Hash-based stateful load-balancers employ connection tracking to avoid per-connection-consistency (PCC) violations that lead to broken connections. In this paper, we propose Just Enough Tracking (JET), a new algorithmic framework that significantly reduces the size of the connection tracking tables for hash-based stateful load-balancers without increasing PCC violations.

Under mild assumptions on how backend servers are added, JET adapts consistent hash techniques to identify which connections do not need to be tracked. We provide a model to identify these safe connections and a pluggable framework with appealing theoretical guarantees that supports a variety of consistent hash and connection-tracking modules.

We implement JET in two different environments and with four different consistent hash techniques. Using a series of evaluations, we demonstrate that JET requires connection-tracking tables that are an order of magnitude smaller than those required with full connection tracking while preserving PCC and balance properties. In addition, JET often increases the lookup rate due to improved caching.

Supplementary Material

MP4 File (3494851-presentation.mp4)

Load Balancing with JET: Just Enough Tracking for Connection Consistency Presentation video

Download
30.35 MB

References

[1]

Cheetah authors. Github - cheetah source code, 2020. https://github.com/cheetahlb/simulations.

[2]

Data Set for IMC 2010 Data Center Measurement. http://pages.cs.wisc.edu/~tbenson/IMC10_Data.html, 2010.

[3]

The CAIDA equinix-newyork packet trace, 20181220--130000, 2018.

[4]

J. Alakuijala, B. Cox, and J. Wassenberg. Fast Keyed Hash/Pseudo-Random Function Using Simd Multiply and Permute. arXiv preprint arXiv:1612.06257, 2016.

[5]

M. Ankerl (martinus) et al. Fast & Memory Efficient Hashtable Based on Robin Hood Hashing for C++11/14/17/20. https://github.com/martinus/robin-hood-hashing, 2021.

[6]

J. T. Araujo, L. Saino, L. Buytenhek, and R. Landa. Balancing on the Edge: Transport Affinity without Network State. In Usenix NSDI, 2018.

[7]

T. Barbette, C. Tang, H. Yao, D. Kostić, G. Q. Maguire Jr, P. Papadimitratos, and M. Chiesa. A High-Speed Load-Balancer Design With Guaranteed per-Connection-Consistency. In Usenix NSDI, pages 667--683, 2020.

[8]

T. Benson, A. Akella, and D. A. Maltz. Network Traffic Characteristics of Data Centers in the Wild. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement, pages 267--280, 2010.

Digital Library

[9]

L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. On the Implications of Zipf's Law for Web Caching. Technical report, University of Wisconsin-Madison Department of Computer Sciences, 1998.

[10]

L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and Zipf-like distributions: Evidence and implications. In IEEE Infocom, volume 1, pages 126--134, 1999.

[11]

R. Cohen, M. Kadosh, A. Lo, and Q. Sayah. LB Scalability: Achieving the Right Balance Between Being Stateful and Stateless. IEEE/ACM Transactions on Networking, 2021.

[12]

M. Duke and N. Banks. QUIC-LB: Generating Routable QUIC Connection IDs. Internet-Draft draft-ietf-quic-load-balancers-06, Internet Engineering Task Force, Feb. 2021. Work in Progress.

[13]

L. Eggert and F. Gont. Tcp User Timeout Option. Technical report, RFC 5482, March, 2009.

[14]

D. E. Eisenbud, C. Yi, C. Contavalli, et al. Maglev: A Fast and Reliable Software Network Load Balancer. In Usenix NSDI, 2016.

[15]

R. Gandhi, H. H. Liu, Y. C. Hu, G. Lu, J. Padhye, L. Yuan, and M. Zhang. Duet: Cloud Scale Load Balancing With Hardware and Software. ACM SIGCOMM Computer Communication Review, 44(4):27--38, 2014.

Digital Library

[16]

K. He, E. Rozner, K. Agarwal, W. Felter, J. Carter, and A. Akella. Presto: Edge-based load balancing for fast datacenter networks. ACM SIGCOMM Computer Communication Review, 45(4):465--478, 2015.

Digital Library

[17]

W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. In The Collected Works of Wassily Hoeffding, pages 409--426. Springer, 1994.

[18]

C. Hopps. Katran: A high performance layer 4 load balancer. https://github.com/facebookincubator/katran, 2021.

[19]

D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, and D. Lewin. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 654--663, 1997.

Digital Library

[20]

D. Karger, A. Sherman, A. Berkheimer, et al. Web Caching With Consistent Hashing. Comp. Netw., 1999.

Digital Library

[21]

A. Kesselman and Y. Mansour. Optimizing Tcp Retransmission Timeout. In International Conference on Networking, pages 133--140. Springer, 2005.

[22]

J. Lamping and E. Veach. A Fast, Minimal Memory, Consistent Hash Algorithm. arXiv preprint arXiv:1406.2294, 2014.

[23]

G. Mendelson, S. Vargaftik, K. Barabash, D. H. Lorenz, I. Keslassy, and A. Orda. AnchorHash: A Scalable Consistent Hash. IEEE/ACM Transactions on Networking, 29(2):517--528, 2021.

Digital Library

[24]

R. Miao, H. Zeng, C. Kim, J. Lee, and M. Yu. Silkroad: Making Stateful Layer-4 Load Balancing Fast and Cheap Using Switching Asics. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication, pages 15--28, 2017.

Digital Library

[25]

V. Mirrokni, M. Thorup, and M. Zadimoghaddam. Consistent hashing with bounded loads. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 587--604. SIAM, 2018.

Digital Library

[26]

M. Mitzenmacher. The Power of Two Choices in Randomized Load Balancing. IEEE Transactions on Parallel and Distributed Systems, 12(10):1094--1104, 2001.

Digital Library

[27]

V. Olteanu, A. Agache, A. Voinescu, and C. Raiciu. Stateless Datacenter Load-balancing with Beamer. In Usenix NSDI, 2018.

[28]

P. Patel, D. Bansal, L. Yuan, A. Murthy, A. Greenberg, D. A. Maltz, R. Kern, H. Kumar, M. Zikos, H. Wu, et al. Ananta: Cloud Scale Load Balancing. ACM SIGCOMM Computer Communication Review, 43(4):207--218, 2013.

Digital Library

[29]

B. Pit-Claudel, Y. Desmouceaux, P. Pfister, M. Townsley, and T. Clausen. Stateless Load-Aware Load Balancing in P4. In IEEE ICNP, pages 418--423, 2018.

[30]

M. Raab and A. Steger. "Balls into bins"---A simple and tight analysis. In International Workshop on Randomization and Approximation Techniques in Computer Science, pages 159--170. Springer, 1998.

Digital Library

[31]

D. G. Thaler and C. V. Ravishankar. Using Name-Based Mappings to Increase Hit Rates. IEEE/ACM Trans. Netw., 1998.

Digital Library

[32]

M. Uruena, D. Larrabeiti, and P. Serrano. Fast Robust Hashing. In IEEE Globecom, 2006.

[33]

S. Vargaftik and D. H. Lorenz. Implementation of AnchorHash - A Scalable Consistent Hash. https://github.com/anchorhash/cpp-anchorhash, 2021.

[34]

S. Vargaftik and D. H. Lorenz. Implementation of Load Balancing with JET: Just Enough Tracking for Connection Consistency. https://github.com/anchorhash/jetlb, 2022.

[35]

W. Wang and G. Casale. Evaluating Weighted Round Robin Load Balancing for Cloud Web Services. In 2014 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pages 393--400. IEEE, 2014.

[36]

W. Wang and C. V. Ravishankar. Hash-Based Virtual Hierarchies for Scalable Location Service in Mobile Ad-Hoc Networks. Mobile Networks and Applications, 2009.

Digital Library

Cited By

Tajbakhsh HParizotto RSchaeffer-Filho AHaque I(2024)P4Hauler: An Accelerator-Aware In-Network Load Balancer for Applications Performance BoostingIEEE Transactions on Cloud Computing10.1109/TCC.2024.338965812:2(697-711)Online publication date: Apr-2024
https://doi.org/10.1109/TCC.2024.3389658
Levi YKeslassy I(2023)Beyond the Ring: Quantized Heterogeneous Consistent Hashing2023 IEEE 31st International Conference on Network Protocols (ICNP)10.1109/ICNP59255.2023.10355577(1-12)Online publication date: 10-Oct-2023
https://doi.org/10.1109/ICNP59255.2023.10355577

Index Terms

Load balancing with JET: just enough tracking for connection consistency
1. Networks
  1. Network algorithms
    1. Control path algorithms
      1. Network resources allocation
    2. Data path algorithms
      1. Packet scheduling
  2. Network components
    1. Middle boxes / network appliances

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 ...
Stateless datacenter load-balancing with beamer
NSDI'18: Proceedings of the 15th USENIX Conference on Networked Systems Design and Implementation

Datacenter load balancers (or muxes) steer traffic destined to a given service across a dynamic set of backend machines. To ensure consistent load balancing decisions when backends come or leave, existing solutions make a load balancing decision per ...
Flow-based packet-mode load-balancing for parallel packet switches

Parallel Packet Switch (PPS) is broadly used in designing large-capacity switching fabrics, since it resolves the bottlenecks of scheduling algorithm, memory bandwidth, and serial transmission technology simultaneously. Current packet-based load-...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '21: Proceedings of the 17th International Conference on emerging Networking EXperiments and Technologies

December 2021

507 pages

ISBN:9781450390989

DOI:10.1145/3485983

General Chairs:
Georg Carle
Technical University of Munich, Germany
,
Jörg Ott
Technical University of Munich, Germany

Copyright © 2021 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 the author(s) 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

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 December 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Qualifiers

Research-article

Funding Sources

Israel Science Foundation
Technion Hiroshi Fujiwara Cyber Security Research Center
Hasso Plattner Institute Research School
Israel Cyber Bureau
Fulbright Postdoctoral Scholar Program
Israeli Consortium for Network Programming (Neptune)

Conference

CoNEXT '21

Sponsor:

SIGCOMM

CoNEXT '21: The 17th International Conference on emerging Networking EXperiments and Technologies

December 7 - 10, 2021

Virtual Event, Germany

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
241
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)4

Reflects downloads up to 19 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tajbakhsh HParizotto RSchaeffer-Filho AHaque I(2024)P4Hauler: An Accelerator-Aware In-Network Load Balancer for Applications Performance BoostingIEEE Transactions on Cloud Computing10.1109/TCC.2024.338965812:2(697-711)Online publication date: Apr-2024
https://doi.org/10.1109/TCC.2024.3389658
Levi YKeslassy I(2023)Beyond the Ring: Quantized Heterogeneous Consistent Hashing2023 IEEE 31st International Conference on Network Protocols (ICNP)10.1109/ICNP59255.2023.10355577(1-12)Online publication date: 10-Oct-2023
https://doi.org/10.1109/ICNP59255.2023.10355577

View Options

Get Access

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.

Media

Figures

Other

Tables

View Table of Contents