Pith. sign in

REVIEW 5 major objections 5 minor 71 references

Concury: A Fast and Light-weighted Software Load Balancer

T0 review · 5 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Concury shows a software load balancer can preserve per-connection consistency without storing connection keys, updating only on backend-pool changes.

desk verdict A genuine algorithmic alternative to digest-based stateful LBs, but the headline correctness claim depends on an unstated reliability assumption about host-agent reporting, and the abstract overstates the throughput win. read the letter →

arxiv 1908.01889 v1 pith:3QFZ4D7V submitted 2019-08-05 cs.NI

Shouqian Shi , Chen Qian , Ye Yu , Xin Li , Ying Zhang , Xiaozhou Li This is my paper · ORCID
classification cs.NI
keywords softwareloadbalancerstatefulbalancingminimalperfecthashingOthelloper-connectionconsistencyweighteddataplaneupdatesfalse-hitfreedom
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Concury is a software load balancer built to remove two weaknesses of earlier stateful designs: digest-based connection tables can collide and send a packet to the wrong backend, and inserting every new connection into the data plane slows forwarding and risks inconsistency. The paper's central claim is that a load balancer can keep per-connection consistency while storing no connection keys in the data plane at all, encoding the state-to-backend mapping in two compact arrays produced by minimal perfect hashing. Because the arrays are rebuilt only when the set of backend servers changes, connection arrivals and terminations do not interrupt the data plane, and because no digest is stored, false hits cannot occur by construction. The paper argues this gives higher throughput and lower memory than digest-table designs, with weighted load balancing and support for multi-connection states, which matters for cloud and edge deployments where load-balancer servers consume scarce resources.

What carries the argument

The central object is Othello hashing, a minimal-perfect-hashing scheme in the Bloomier-filter family. For a set of key-value pairs it builds two arrays A and B with two hash functions ha and hb such that looking up key k returns A[ha(k)] xor B[hb(k)]; the keys are not stored, and the construction works by requiring the bipartite graph formed by the hash edges to be acyclic, which makes the value assignment straightforward. Concury uses connection identifiers as keys and DIP codes as values, then maps each code to a real backend through a DIP array, giving the weighted randomizer for first packets. The supporting OthelloMap keeps the dynamic state set in an array C while an Othello returns each state's index, so adding or deleting a state is O(1) and regenerating one VIP's data-plane structure is fast and localized.

What would settle it

Run Concury with a backend pool change and deliberately suppress or delay one host-agent's report of a new connection, then send another packet of that connection after the data-plane rebuild; the paper's claim predicts the packet is always forwarded to the same DIP, so a single packet sent to a different DIP would falsify the false-hit-free and consistency claim.

Watch

Extended reading notes

Core claim

The central claim is that 'look up the backend of an existing connection' and 'choose a backend for a new connection' are the same operation. Concury gives each virtual IP an Othello lookup structure of two arrays; for any packet, the lookup returns a backend code, with active connections resolving to the backend that holds their state and unseen connections receiving a code that the DIP-code-to-DIP table maps to a weighted-random backend. Since the keys themselves are not stored, digest collisions are impossible, and the data plane needs no updates on connection arrivals or terminations, only on DIP-pool changes, when the control plane's OthelloMap regenerates the affected structures. The evaluation reports more than double the throughput of digest-table algorithms and memory around one-fifth to one-third of a digest-table design at large state counts, with the abstract claiming up to 4x throughput; the prototype sustains 62.5% of two 10GbE NICs' capacity on one thread and full capacity on two threads, while tests show 100% packet consistency and no false hits.

Load-bearing premise

The guarantee stands or falls on the host agents' reports: every backend server must promptly and correctly report every new and terminated connection to the control plane, so the rebuilt data-plane structure contains all active states; if a state is missing from the control plane's view, its packets will be assigned a fresh random backend after the rebuild and the connection breaks.

Editorial extensions

If this is right

  • Because the data plane stores no keys, it cannot suffer digest collisions; packets of an active connection always resolve to the backend that holds the state, so the false-hit problem of digest tables is eliminated by construction.
  • Data-plane updates occur once per DIP-pool change rather than once per connection, so heavy new-connection arrival rates no longer interrupt packet processing; throughput during updates stays far higher than digest-table designs.
  • The same DIP-code mechanism acts as a weighted randomizer for first packets: with enough DIP codes per backend, the near-uniform output of Othello on unknown keys yields weighted load balancing across heterogeneous servers.
  • The structure is portable: the same two-array lookup fits a commodity-server data plane and a programmable switch data plane, so both software and ASIC deployments can use the same algorithm.
  • Multi-connection and device-level states are supported naturally because the state identifier is not required to be a single TCP flow; any key the host agents track can be encoded in the Othello structure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extension: if host-agent reports can be lost or delayed, the zero-false-hit guarantee degrades to a probabilistic one; a fault-injection test that drops a fraction of reports before a DIP-pool change would show the mis-forwarded-connection fraction matching the dropped-report fraction.
  • Extension: the same lookup-plus-randomizer pattern applies to NAT gateways and edge-compute session affinity, where the state set is large and per-connection data-plane updates are the bottleneck; the paper itself names NAT and EPC as candidate applications.
  • Extension: treating the state identifier as an arbitrary key rather than a TCP 5-tuple means Concury can handle device-level or process-level affinity; a direct experiment would use long-lived UDP flows from one device and check that all its packet types stay on one backend across a DIP change.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. This paper presents Concury, a stateful software load balancer built on Othello/Bloomier minimal perfect hashing. The data plane maps each packet's state identifier to a short DIP code by XORing two small arrays, so connection keys are not stored and digest collisions are avoided by construction. The control plane maintains a per-VIP OthelloMap, and the data-plane Othello is rebuilt only on DIP-pool or weight changes rather than on every connection event. The paper claims false-hit freedom, weighted load balancing, lower memory than Maglev- and SilkRoad-style digest tables, and a throughput advantage (4x in the abstract, >2x in the body), supported by algorithm microbenchmarks, a DPDK prototype on CloudLab, and a P4 prototype on Mininet.

Significance. The idea of using MWHC perfect hashing to combine stateful lookup with a weighted randomizer is appealing, and the separation of data-plane updates from per-connection events is a worthwhile design goal. The paper correctly credits the Othello structure to prior work [39,40], so the claimed novelty lies in the LB-specific workflow, the OthelloMap control-plane structure, and the evaluation. The paper provides concrete implementation details, a complexity comparison in Appendix C, and two prototypes; the CloudLab numbers (17.63 Mpps on one thread and line rate on two threads) are concrete and useful. However, the central consistency guarantee is conditional on an unstated reliability assumption about the host-agent report channel, and several quantitative claims in the abstract are stronger than the body's results. If the report-reliability dependency is resolved or explicitly bounded, and the missing figures and baseline concerns are addressed, this would be a solid contribution.

major comments (5)
  1. [§5.1, §5.5, §5.6] The unconditional consistency guarantee in §5.6 ('Therefore Concury achieves packet consistency without requiring updating for every new state') presupposes that the Concury-CP's OthelloMap contains every active state at the moment a DIP-pool change triggers a rebuild. The data plane does not store state keys (§5.2), so the only source of state membership is the host-agent report channel described in §5.1. If a 'new state' report is delayed or lost, a rebuild under §5.5 constructs the Othello without that state, and subsequent packets of that state fall into case 2 of §5.6, receiving a fresh arbitrary Dcode that may map to a different DIP; the connection is silently broken. The 'additional mechanism' at the end of §5.6 covers packets arriving during the update itself, not reports that arrive late or never. Please add a reliability mechanism for the report channel, quantify the assumed report delay or loss bound, or explicitly qualify the consistency guarantee.
  2. [Abstract and §6.2/§6.5] The abstract claims '4x throughput', but §6.2 reports '> 2x advantage' for Concury over both baselines and §6.5 summarizes the result as '>2x'. The numbers should be reconciled, and the abstract should state the measured speedup actually supported by the evaluation.
  3. [§6.1, §6.2] The throughput and memory comparisons are against best-effort re-implementations of Maglev's and SilkRoad's algorithms, as admitted in §6.1 ('we implement the LB algorithms of Maglev and SilkRoad in our best effort... we are not able to rebuild identical system prototypes'). The abstract's comparison to 'other LB algorithms' is therefore not a comparison to the published Maglev and SilkRoad systems. Please state this limitation in the abstract and conclusion and, ideally, validate the baselines against published numbers or release the baseline code alongside Concury's.
  4. [§5.3] The uniformity argument for the weighted randomizer is not correct as written. After constructing Othello for n states with array size m, a vertex of A or B is 'determined' if it is incident to any constructed edge, so the number of pairs (ha(c), hb(c)) that yield a determined Dcode can be as large as the product of the numbers of determined A and B vertices (up to O(n^2) when m = O(n)), not 'only n pairs' as stated in §5.3. The empirical chi-squared and KS tests suggest acceptable uniformity, but the theoretical claim in §5.3 should be corrected or replaced by an empirical statement.
  5. [§6.2 and §6.4] Several claims in the evaluation are supported only by missing figures: 'We further show the time cost of inserting new states... in Fig. ??' (§6.2) and the dynamic weight-change results in §6.4 ('The results are shown in Fig. ??', 'We further change the weights once every 30 second and show the results in Fig. ??', 'We use Fig. ?? to show the cumulative distribution...'). Without these figures, the claims about control-plane insertion scalability and resilience to weight changes are unverifiable. Please insert the figures or remove the corresponding claims.
minor comments (5)
  1. [§5.2] The text says 'the last 8 bits of a VIP can be used as the VIP index, supporting 1K VIPs'; 8 bits support at most 256 indices, so the arithmetic should be corrected.
  2. [§5.2 and Appendix C] The memory-cost formula uses m for the Othello array size without reconciling with ma and mb defined in §3; the formula in §5.4 uses different variable names (lin, lk) and should be aligned with Appendix C.
  3. [§5.2] Step 2 says the lookup key is the 5-tuple, while the earlier text and Algorithm 1 describe the state identifier as a 4-tuple; please make the state-identifier definition consistent.
  4. [References] Reference [14] is an anonymous Dropbox link, which is not a stable archival reference; please provide a permanent repository or DOI for the source code.
  5. [Abstract and text] There are numerous grammar and copyediting issues (e.g., 'provides flexibility' with a plural subject in the abstract, 'once very 30 second' in §6.4); a thorough copyedit pass is recommended.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Concury's lookup, consistency, and false-hit-free claims are constructive uses of the published Othello/MWHC structure, with only an operational report-completeness assumption, not a circular reduction.

full rationale

Concury's derivation is not circular. The core data plane structure is Othello/MWHC minimal perfect hashing, cited to prior published work [18,21,22,27,39,40]; the paper explicitly says 'Othello itself is not a merit of this work' and uses Othello's acyclicity and assignment properties as external, parameter-free mathematical facts that do not include the LB claims. Thus the self-citations are not load-bearing in a circular way. The false-hit-free and consistency arguments in Section 5.6 are constructive: the data plane stores no connection keys, every l-bit Dcode maps through the DIP array DA to a valid DIP, and deterministic Othello lookups return the same Dcode until a rebuild. No fitted parameter is renamed as a prediction; ld, hash seeds, and memory formulas are design/evaluation parameters, not tuned to reproduce the claimed results. The evaluation compares against best-effort reimplementations of Maglev and SilkRoad, which is a benchmarking caveat rather than circularity. The one genuine gap is operational, not circular: Section 5.1's host-agent reporting must deliver every active state to Concury-CP before the Section 5.5 DIP-pool rebuild for the Section 5.6 case-1 guarantee to hold; delayed or lost reports would orphan a connection after the rebuild. This is a robustness limitation and an unstated assumption about report completeness, not a reduction of the paper's output to its input. Missing 'Fig. ??' references in Section 6 are presentation defects, not circular steps.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The design rests on the Othello minimal perfect hashing structure, which is prior published work, and on a set of system-level assumptions about host-agent reliability and update timing. No new physical entities are introduced. The free parameters are design choices (Dcode length, array size, hash seeds) that affect performance but are not fitted to match the claimed results.

free parameters (3)
  • ld (DIP code length) = 12 bits
    Chosen in Section 5.3 to balance memory cost (2.33ld n) against granularity for weighted load balancing; uniformity tests improve when ld > 11.
  • m (Othello array size per VIP) = Not explicitly stated; implied around 1.33n from Othello construction
    Affects construction success probability (acyclic graph) and memory; inherited from Othello design and referenced by the memory formula in Section 5.2.
  • Hash seeds seeda, seedb = Not specified in the paper
    Determine the specific CRC32-based hash functions ha and hb; different seeds give different load-balancing uniformity, with chi-squared/KS failure rates around 10% for the tested seeds.
assumptions (4)
  • standard math Othello construction produces an acyclic bipartite graph with high probability when n <= 0.75m; if not, re-hashing with fresh hash functions succeeds in expected <1.51 attempts.
    Result from [39,40]; used in Section 5.2 and Section 5.4 for the data-plane structure and OthelloMap updates.
  • domain assumption Hash functions ha and hb behave as uniform random hash functions for unknown keys.
    Stated in Section 5.3 'which is true if ha and hb are uniform hashes'; needed for the weighted-randomizer uniformity analysis.
  • ad hoc to paper Host agents correctly and promptly report every new and terminated state to Concury-CP, so the CP's state set matches reality at every DIP-pool change.
    Invoked in Section 5.1 and Section 5.4; if a state is missing, the rebuilt Othello can map ongoing packets to a new DIP, causing false hits (the paper's central claim of 0 false hits depends on this).
  • domain assumption DIP-pool changes are infrequent enough that the OthelloMap update (2-12ms) can be completed without losing packets in the concurrent-update window.
    Section 5.5 and Section 6.2; the update race acknowledged in Section 5.6.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Concury: A Fast and Light-weighted Software Load Balancer." pith.science (2026). https://pith.science/paper/3QFZ4D7V

@misc{pith2026190801889,
  author       = {Pith},
  title        = {Pith review of: Concury: A Fast and Light-weighted Software Load Balancer},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3QFZ4D7V}},
  note         = {Machine review of arXiv:1908.01889}
}
read the original abstract

A load balancer (LB) is a vital network function for cloud services to balance the load amongst resources. Stateful software LBs that run on commodity servers provides flexibility, cost-efficiency, and packet consistency. However current designs have two main limitations: 1) states are stored as digests which may cause packet inconsistency due to digest collisions; 2) the data plane needs to update for every new connection, and frequent updates hurt throughput and packet consistency. In this work, we present a new software stateful LB called Concury, which is the first solution to solve these problems. The key innovation of Concury is an algorithmic approach to store and look up large network states with frequent connection arrivals, which is succinct in memory cost, consistent under network changes, and incurs infrequent data plane updates. The evaluation results show that the Concury algorithm provides 4x throughput and consumes less memory compared to other LB algorithms, while providing weighted load balancing and false-hit freedom, for both real and synthetic data center traffic. We implement Concury as a prototype system deployed in CloudLab and show that the throughput of Concury on a single thread can reach 62.5% of the maximum capacity of two 10GbE NICs and that on two threads can reach the maximum capacity.

Figures

Figures reproduced from arXiv: 1908.01889 by the authors.

Figure 1
Figure 1. Construction of Othello and stateless LBs to network operators. 3. BACKGROUND: BLOOMIER AND OTH￾ELLO We propose to use the data structure and algorithms of MWHC minimal perfect hashing [18, 21, 22, 27, 39] for the Concury LB. One well-known perfect hashing based data structure is the Bloomier filters [21, 22]. The recently pro￾posed Othello Hashing [39, 40] makes use of Bloomier fil￾ters for the forwarding tables in… view at source ↗
Figure 2
Figure 2. Lookups of Othello ues of all keys are satisfied [39]. If a cycle is found, Othello needs to find another pair of hash functions to re-build G. It is proved that during the construction of n keys, the expected total number of re-hashing is < 1.51 when n ≤ 0.75m [39]. Hence the expected time cost to construct G of n keys is O(n), and the expected time to add, delete, or change a key is O(1). Othello lookups in the da… view at source ↗
Figure 4
Figure 4. Workflow of Concury data plane ing for every new state in the data plane. 5.2 Concury data plane Concury uses Othello as both a lookup structure to rep￾resent the state-to-DIP mapping and a weighted randomizer. As introduced in § 3, an Othello lookup structure is built based on a set S of keys. To apply Othello for Concury, each key is the identifier of a state, i.e., 4-tuple. The value cor￾responding to a key is a … view at source ↗
Figures from the paper (8 more)
Figure 5
Figure 5. Figure 5: Stateless packet distribution by Dcode 1024 2048 4096 8192 Number of Dcode 0 10 20 30 40 50 Failure Rate (%) Concury SHA-256 MD5 [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 9
Figure 9. Figure 9: Memory cost for DIP-E and Small network 1K 4K 16K 64K 256K 1M Number of states 1 10 Memory (MB) Maglev Concury SilkRoad [PITH_FULL_IMAGE:figures/full_fig_p009_9.png]
Figure 15
Figure 15. Figure 15: Throughput for DIP-E and Large network 1K 4K 16K 64K 256K 1M 4M 16M Number of states 0 50 100 Throughput (Mpps) Concury Multi HT - digest Hash table - digest [PITH_FULL_IMAGE:figures/full_fig_p010_15.png]
Figure 17
Figure 17. Figure 17: Throughput for multi-thread 1024 4096 16384 65536 262144 Number of new states per second 0 10 20 30 40 50 60 Throughput (Mpps) Concury Multi HT - digest Hash table - digest [PITH_FULL_IMAGE:figures/full_fig_p010_17.png]
Figure 19
Figure 19. Figure 19: Throughput for DIP-V traffic by DPDK 0 20 40 60 80 100 120 DIP Index 0 1 2 3 4 Normalized DIP load 104 [PITH_FULL_IMAGE:figures/full_fig_p011_19.png]
Figure 22
Figure 22. Figure 22: P4 prototype on Mininet ity problems to DPDK. The results show that Concury can achieve very high performance with little resource. 6.4 Evaluation on P4 prototype P4 prototype of Concury. We have also built a P4 pro￾totype of Concury, in which the data plane includes …
Figure 23
Figure 23. Figure 23: PCC violation of static hashing A.2 B. Pseudocode We also show the pseudocode of the Concury-DP lookup algorithm in Algorithm 1 and the Concury-DP updating algorithm in Algorithm 2. A.3 C. Data plane complexity analysis and com￾parison. Time cost. 1) Concury. Concury-…
Figure 24
Figure 24. Figure 24: OthelloMap of 5 state-DIP mappings (64+lv)n = 83.6n. The experimental results show that the Cuckoo+digest method (Maglev) needs around 3x memory compared to Concury, which agrees with the analysis here. Note one assumption here is that all VIPs use a same length of Dc…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

71 extracted references · 70 canonical work pages

  1. [1]

    INTRODUCTION A load balancer (LB) is a fundamental network function of a data center that provides Internet services. In traditional cloud environments, to accommodate high demand for pop- ular service at scale, such as a search engine, email, photo sharing/storage, or message posting and interactions, a data center maintains multiple backend servers, eac...

    work page Pith review arXiv 1908

  2. [2]

    2) Traditional cloud LBs con- sider a state for every TCP connection

    It fits the condition of an Edge that typically has con- strained resource – the LB in an Edge may only be hosted by few servers and could be co-located with other services on the servers [34, 38, 41]. 2) Traditional cloud LBs con- sider a state for every TCP connection. However, in modern cloud or Edge, states may be for multi-connection and at the device...

    work page

  3. [3]

    The workflow of Concury is designed to achieve memory- efficiency, high throughput, load balancing, consistency, and false hit freedom

    work page

  4. [4]

    We invent a new data structure to maintain the dynamic set of states in the control plane and can instantly produce new lookup structures to update the data plane, under DIP pool changes

    work page

  5. [5]

    We add the functions of weighted randomizer and main- taining multi-connection state to LBs

    work page

  6. [6]

    We also build a P4 prototype to show its com- patibility to programmable switches

    We implement Concury using DPDK [2] to demonstrate its high performance in a publicly-available network plat- form [1]. We also build a P4 prototype to show its com- patibility to programmable switches. We release the an- onymous source code and our results can be verified and re-produced [14]. In a nutshell, this work is indeed about improving L4LB, which...

    work page

  7. [7]

    Tradi- tional hardware load balancers are expensive and not flex- ible

    RELATED WORK An LB is an important component of a data center net- work, which distributes incoming traffic to different backend servers or other network functions [7, 23, 25, 32, 36]. Tradi- tional hardware load balancers are expensive and not flex- ible. Hence, many large cloud services choose to use soft- ware load balancers [7, 12, 23, 25, 32]. In addit...

    work page

  8. [8]

    https://www.a10networks.com/, 2017

    A10. https://www.a10networks.com/, 2017

    work page 2017

Show all 71 references
  1. [9]

    not care

    BACKGROUND: BLOOMIER AND OTH- ELLO We propose to use the data structure and algorithms of MWHC minimal perfect hashing [18, 21, 22, 27, 39] for the Concury LB. One well-known perfect hashing based data structure is the Bloomier filters [21, 22]. The recently pro- posed Othello ...

  2. [10]

    The clients send their service requests to the VIP

    SYSTEM MODELS AND OBJECTIVES A service provided by a cloud/edge data center is identi- fied by a publicly visible IP address, called virtual IP (VIP). The clients send their service requests to the VIP. An LB balances the load across the cloud/edge servers, so that no server ge...

  3. [11]

    LB data plane Determines a DIP as the destination for each packet

  4. [12]

    Each VIP is associated with its DIP pool , which includes the DIPs of the servers that provide the service identified by the VIP

    updates Packet with DIP servers with different DIPs Report new state or state deletionMaintains the state and computes the data plane Figure 3: General model of a stateful LB tion of an LB is to map the VIP on a packet header to a DIP, based on the header information of the pa...

  5. [13]

    The LB-DP processes pack- ets and find a DIP for each packet carrying a VIP

    LB data plane (LB-DP). The LB-DP processes pack- ets and find a DIP for each packet carrying a VIP. The DIP should be selected from the DIP pool behind the VIP, rep- resenting the set of servers providing the service of this VIP. The core algorithm should provide two functions:...

  6. [14]

    The LB-CP receives the state changes from the servers, including new state establish- 4 ments and state removals

    LB control plane (LB-CP). The LB-CP receives the state changes from the servers, including new state establish- 4 ments and state removals. Many existing designs uses a TCP SYN packet as the indicator of a new state and allow LB-DP to notify the LB-CP directly [23, 28]. Howeve...

  7. [15]

    The LB-CP will notify LB-DP to make neces- sary changes under certain network dynamics, such as DIP pool and weight changes

    Update. The LB-CP will notify LB-DP to make neces- sary changes under certain network dynamics, such as DIP pool and weight changes. The design objective of the update process is to reduce the frequency of updating because it will interrupt packet processing on the LB-DP. Our ...

  8. [16]

    lookup-then- distribute

    DESIGN OF Concury 5.1 System overview Notations. Let M be the number of VIPs in the network. Each VIP vi is assigned an index i and its DIP pool contains ti DIPs. The number of states of VIP vi is ni. Concury follows the DP model introduced in § 4, includ- ing both data plane ...

  9. [17]

    5.2 Concury data plane Concury uses Othello as both a lookup structure to rep- resent the state-to-DIP mapping and a weighted randomizer

    how to adjust Othello for both active state lookups and weighted randomizer; 2) how to design the data plane to minimize memory cost and maximize throughput; 3) how to resolve the false hits problem without modifying the server network stack; and 4) how to relax the requiremen...

  10. [18]

    The others are kept still

    Under a change of a VIP’s DIP pool, it is only necessary to update the Othello ofthis VIP. The others are kept still

  11. [19]

    Separate the lookups of different VIPs can ensure that packets are not forwarded to DIP in other VIP’s pool

  12. [20]

    Note maintaining per-VIP structures can be also used by other stateful LBs such as Maglev [23] to avoid the cross- VIP problem

    Experimental results show that separate lookup structures provide faster lookup speed than a unified one. Note maintaining per-VIP structures can be also used by other stateful LBs such as Maglev [23] to avoid the cross- VIP problem. However it still cannot resolve the digest- ...

  13. [21]

    Concury-DP is very simple and fast

    Time cost. Concury-DP is very simple and fast. Each lookup is in O(1), including at most 6 read operations from static arrays, 2 hash computations (32 bits for each), and an XOR computation. This cost is smaller than Cuckoo+digest, a commonly used LB table design [23, 28], whi...

  14. [22]

    Let n be the number of total states, ld be the length of Dcode, and lv be the length of the DIP index in the DIP table

    Space cost. Let n be the number of total states, ld be the length of Dcode, and lv be the length of the DIP index in the DIP table. The total memory cost of Concury-DP is 2.33ldn +64m +2ld lvm +48∗2lv bits, which is much smaller than that of Cuckoo+digest in practical setups. ...

  15. [23]

    The core algorithm of Maglev is to use a hash table to store connections as digests for load balancing and a new consistent hashing algorithm for resili- ence to DIP pool changes

    is Google’s distributed software load balancer running on commodity servers. The core algorithm of Maglev is to use a hash table to store connections as digests for load balancing and a new consistent hashing algorithm for resili- ence to DIP pool changes. SilkRoad [28] implem...

  16. [24]

    Then the lookup result τ(k) = Dcode and the packet will be forwarded to the correct DIP

    The state ID of the packet, k, is known by Concury-CP during the construction of Othello-i, and the value of look- ing up k is Dcode which can be mapped to the DIP hold- ing this state. Then the lookup result τ(k) = Dcode and the packet will be forwarded to the correct DIP

  17. [25]

    Then according to the property of Othello, τ(k) is an ar- bitrary l-bit Dcode

    The state ID k is unknown by Concury-CP during the con- struction, and the packet is the first one of a new state. Then according to the property of Othello, τ(k) is an ar- bitrary l-bit Dcode. According to the property of the table DA, DA[i][Dcode] always stores a valid DIP fo...

  18. [26]

    Hence the first packet was processed after the latest construction and update, which was forwarded to a DIP D

    The state ID k is unknown by Concury-CP during the construction, and the packet is not the first one of a new state. Hence the first packet was processed after the latest construction and update, which was forwarded to a DIP D. Since the data plane has not been updated since the...

  19. [27]

    IMPLEMENTATION AND EV ALUATION In this section we evaluate the performance of the Con- cury algorithm and prototype systems. We implement two prototypes: 1) a software LB on commodity servers by Intel DPDK [2] deployed in CloudLab [1], a research infrastruc- ture for cloud com...

  20. [28]

    Hash table with digest, used in Maglev [23]; and 2) Multi hash tables with digest, used in SilkRoad [28]. Note Silk- Road was designed for special hardware, i.e., > 50MB pro- 8 1K 4K 16K 64K 256K 1M Number of states 1 10Memory (MB) Maglev Concury SilkRoad Figure 9: Memory cost...

  21. [29]

    DPDK is a series of libraries for fast user-space packet processing [2]

    running in CloudLab [1]. DPDK is a series of libraries for fast user-space packet processing [2]. DPDK is useful for bypassing the complex networking stack in Linux ker- nel and it has utility functions for huge-page memory al- location and lockless FIFO, etc. We modified the c...

  22. [30]

    Each of the two nodes is equipped with one Dual-port In- tel X520 10Gbps NIC, with 8 lanes of PCIe V3.0 connec- tions between the CPU and the NIC

    and c220g2-011311 (Node 2) in CloudLab to construct the evaluation platform of Concury software LB prototype. Each of the two nodes is equipped with one Dual-port In- tel X520 10Gbps NIC, with 8 lanes of PCIe V3.0 connec- tions between the CPU and the NIC. Each node has two In...

  23. [31]

    It satisfies the require- ments of the load balancer for cloud and edge data cen- ters

    CONCLUSION We design and implement a new software stateful LB called Concury, which achieves weighted balancing of incoming traffic, maintaining consistency, high throughput, memory efficiency, and false hit freedom. It satisfies the require- ments of the load balancer for cloud ...

  24. [32]

    https://www.cloudlab.us/

    CloudLab. https://www.cloudlab.us/

  25. [33]

    https://www.dpdk.org

    Intel DPDK: Data Plane Development Kit. https://www.dpdk.org. 12

  26. [34]

    https://goo.gl/vzBLE4

    P4 Behavioral Model. https://goo.gl/vzBLE4

  27. [35]

    https://goo.gl/wp6no2

    P4 16 language. https://goo.gl/wp6no2

  28. [36]

    https://github.com/pktgen/Pktgen-DPDK

    Pktgen-DPDK. https://github.com/pktgen/Pktgen-DPDK

  29. [37]

    https://goo.gl/J4HkVo, 2007

    Intel SSE4 Programming Reference. https://goo.gl/J4HkVo, 2007

    2007

  30. [38]

    https://goo.gl/692u64, 2014

    Making facebook’s software infrastructure more energy efficient with autoscale. https://goo.gl/692u64, 2014

    2014

  31. [39]

    https://research.fb.com/ data-sharing-on-traffic-pattern-inside-facebooks-datacenter-network/ , 2017

    Data Sharing on traffic pattern inside Facebook’s datacenter network. https://research.fb.com/ data-sharing-on-traffic-pattern-inside-facebooks-datacenter-network/ , 2017

    2017

  32. [40]

    https://www.loadbalancer.org/, 2017

    Loadbalancer.org inc. https://www.loadbalancer.org/, 2017

    2017

  33. [41]

    https://goo.gl/STMuUY, 2017

    Netscaler, citrix systems inc. https://goo.gl/STMuUY, 2017

    2017

  34. [42]

    https://www.nginx.com/, 2017

    Nginx. https://www.nginx.com/, 2017

    2017

  35. [43]

    https://goo.gl/8Np9HQ, 2017

    PI Library. https://goo.gl/8Np9HQ, 2017

    2017

  36. [44]

    https://www

    Anonymous Source Code of the Concury Prototype. https://www. dropbox.com/s/ruou2l340uu1f4u/concury%20code.zip, 2019

    2019

  37. [45]

    https://goo.gl/36qokt, 2019

    Libtins network packet sniffing and crafting library. https://goo.gl/36qokt, 2019

    2019

  38. [46]

    http://www.mininet.org/, 2019

    Mininet. http://www.mininet.org/, 2019

    2019

  39. [47]

    T., S AINO , L., B UYTENHEK , L., AND LANDA , R

    A RA ´UJO , J. T., S AINO , L., B UYTENHEK , L., AND LANDA , R. Balancing on the Edge: Transport Affinity without Network State. In Proc. of USENIX NSDI (2018)

    2018

  40. [48]

    Monotone minimal perfect hashing: searching a sorted table with O(1) accesses

    B ELAZZOUGUI , D., B OLDI , P., PAGH, R., AND VIGNA , S. Monotone minimal perfect hashing: searching a sorted table with O(1) accesses. In Proc. of ACM SODA (2009)

    2009

  41. [49]

    Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines

    B ONOMI , F., M ITZENMACHER , M., P ANIGRAHY , R., S INGH , S., AND VARGHESE , G. Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines. In Proc. of ACM SIGCOMM (2006)

    2006

  42. [50]

    P4: programming protocol-independent packet processors

    B OSSHART , P., DALY, D., G IBB , G., I ZZARD , M., M CKEOWN , N., REXFORD , J., S CHLESINGER , C., T ALAYCO , D., V AHDAT, A., VARGHESE , G., AND WALKER , D. P4: programming protocol-independent packet processors. ACM SIGCOMM Computer Communication Review (2014)

    2014

  43. [51]

    Bloomier Filters: A Second Look

    C HARLES , D., AND CHELLAPILLA , K. Bloomier Filters: A Second Look. In Proc. of ESA (2008)

    2008

  44. [52]

    The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables

    C HAZELLE , B., K ILIAN , J., R UBINFELD , R., AND TAL, A. The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables. In Proc. of ACM SODA (2004), pp. 30–39

    2004

  45. [53]

    E., Y I, C., C ONTAVALLI , C., S MITH , C., KONONOV , R., M ANN -H IELSCHER , E., C ILINGIROGLU , A., CHEYNEY , B., S HANG , W., AND HOSEIN , J

    E ISENBUD , D. E., Y I, C., C ONTAVALLI , C., S MITH , C., KONONOV , R., M ANN -H IELSCHER , E., C ILINGIROGLU , A., CHEYNEY , B., S HANG , W., AND HOSEIN , J. D. Maglev: A Fast and Reliable Software Network Load Balancer. In Proc. of USENIX NSDI (2016)

    2016

  46. [54]

    MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing

    F AN, B., A NDERSEN , D., AND KAMINSKY , M. MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. In Proc. of USENIX NSDI (2013)

    2013

  47. [55]

    H., H U, Y

    G ANDHI , R., L IU, H. H., H U, Y. C., L U, G., P ADHYE , J., Y UAN, L., AND ZHANG , M. Duet: Cloud scale load balancing with hardware and software

  48. [56]

    L I, X., A NDERSEN , D., K AMINSKY , M., AND FREEDMAN , M. J. Algorithmic improvements for fast concurrent cuckoo hashing. In Proc. of ACM EuroSys (2014)

    2014

  49. [57]

    S., W ORMALD , N

    M AJEWSKI , B. S., W ORMALD , N. C., H AVAS, G., AND CZECH , Z. J. A Family of Perfect Hashing Methods. The Computer Journal (1996)

    1996

  50. [58]

    SilkRoad: Making Stateful Layer-4 Load Balancing Fast and Cheap Using Switching ASICs

    M AO, R., Z ENG , H., K IM, C., L EE, J., AND YU, M. SilkRoad: Making Stateful Layer-4 Load Balancing Fast and Cheap Using Switching ASICs. In Proc. of ACM SIGCOMM (2017)

    2017

  51. [59]

    Openflow: Enabling innovation in campus networks

    M CKEOWN , N., A NDERSON , T., B ALAKRISHNAN , H., PARULKAR , G., P ETERSON , L., R EXFORD , J., S HENKER , S., AND TURNER , J. Openflow: Enabling innovation in campus networks. SIGCOMM Comput. Commun. Rev. (2008)

    2008

  52. [60]

    Stateless Datacenter Load-balancing with Beamer

    O LTEANU , V., AGACHE , A., V OINESCU , A., AND RAICIU , C. Stateless Datacenter Load-balancing with Beamer. In Proc. of USENIX NSDI (2018)

    2018

  53. [61]

    P AGH, R., AND RODLER , F. F. Cuckoo hashing. Journal of Algorithms (2004)

    2004

  54. [62]

    A., K ERN , R., K UMAR , H., Z IKOS , M., W U, H., KIM, C., AND KARRI , N

    P ATEL, P., B ANSAL , D., Y UAN, L., M URTHY, A., G REENBERG , A., M ALTZ, D. A., K ERN , R., K UMAR , H., Z IKOS , M., W U, H., KIM, C., AND KARRI , N. Ananta: Cloud scale load balancing

  55. [63]

    Engineering Egress with Edge Fabric: Steering Oceans of Content to the World

    S CHLINKER , B., ET AL . Engineering Egress with Edge Fabric: Steering Oceans of Content to the World. In Proc. of ACM SIGCOMM (2017)

    2017

  56. [64]

    Edge computing: Vision and challenges

    S HI, W., C AO, J., Z HANG , Q., L I, Y., AND XU, L. Edge computing: Vision and challenges. IEEE Internet of Things Journal 3, 5 (2016)

    2016

  57. [65]

    M., AND RODERO -MERINO , L

    V AQUERO , L. M., AND RODERO -MERINO , L. Finding your Way in the Fog: Towards a Comprehensive Definition of Fog Computing. ACM SIGCOMM CCR (2014)

    2014

  58. [66]

    Openflow-based server load balancing gone wild

    W ANG , R., B UTNARIU , D., AND REXFORD , J. Openflow-based server load balancing gone wild

  59. [67]

    Taking the Edge off with Espresso: Scale, Reliability and Programmability for Global Internet Peering

    Y AP, K.-K., ET AL . Taking the Edge off with Espresso: Scale, Reliability and Programmability for Global Internet Peering. In Proc. of ACM SIGCOMM (2017)

    2017

  60. [68]

    Fog Computing: Platform and Applications

    Y I, S., H AO, Z., Q IN, Z., AND LI, Q. Fog Computing: Platform and Applications. In Proc. of IEEE HotWeb(2015)

    2015

  61. [69]

    Othello Hashing for Scalable and Fast Name Switching

    Y U, Y., B ELAZZOUGUI , D., Q IAN , C., AND ZHANG , Q. Othello Hashing for Scalable and Fast Name Switching. In Proc. of IEEE ICNP (2017)

    2017

  62. [70]

    Memory-efficient and Ultra-fast Network Lookup and Forwarding using Othello Hashing

    Y U, Y., B ELAZZOUGUI , D., Q IAN , C., AND ZHANG , Q. Memory-efficient and Ultra-fast Network Lookup and Forwarding using Othello Hashing. IEEE/ACM Transactions on Networking (2018)

    2018

  63. [71]

    SDLB: A Scalable and Dynamic Software Load Balancer for Fog and Mobile Edge Computing

    Y U, Y., L I, X., AND QIAN , C. SDLB: A Scalable and Dynamic Software Load Balancer for Fog and Mobile Edge Computing. In Proc. of ACM SIGCOMM Workshop on Mobile Edge Computing (MECCOM) (2017). APPENDIX A. APPENDIX A.1 A. Example of consistency violation by static hashing. Con...

    2017

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.