Network Working Group S. Dikshit Internet-Draft Aruba Networks, HPE Intended status: Informational 30 August 2026 Expires: 1 March 2027 Applicability of Consistent Hashing to Designated Forwarder Election Scope Transitions in EVPN draft-dikshit-bess-evpn-df-hashing-analysis-00 Abstract [RFC8584] defines Highest Random Weight (HRW) as the algorithm for Designated Forwarder election in EVPN, and, in Section 3.1, names the Consistent Hashing family of algorithms as addressing the same object-to-server mapping problem before explicitly declining to evaluate them: "these will not be considered here." [I-D.ietf-bess-evpn-per-mcast-flow-df-election] subsequently introduces a scope transition, from per-(ES,VLAN) to per- (ES,VLAN,S,G) election, that is precisely a key-space-resizing event of the kind Consistent Hashing was designed to bound churn for. This document proposes the applicability analysis RFC 8584 declined to make: it defines a DF-churn metric, states HRW's and Consistent Hashing's known theoretical guarantees against it, and sets out an evaluation methodology, using bounded-load Consistent Hashing as the specific comparison point, given multicast group popularity is known to be highly non-uniform in deployed networks. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on 1 March 2027. Copyright Notice Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Table of Contents 1. Introduction 2. The Comparison RFC 8584 Declined 3. The Scope Transition Introduced by Per-Flow DF Election 4. A DF-Churn Metric 5. Known Theoretical Guarantees 5.1. HRW 5.2. Plain Consistent Hashing 5.3. Bounded-Load Consistent Hashing 6. Where HRW Is Expected to Underperform 7. Proposed Evaluation Methodology 8. Relationship to RFC 9722 and RFC 9785 9. Security Considerations 10. IANA Considerations 11. References 11.1. Normative References 11.2. Informative References Author's Address 1. Introduction Designated Forwarder election in EVPN determines which PE, among those attached to a given Ethernet Segment, forwards broadcast, unknown-unicast, and multicast traffic for a given scope. [RFC8584] generalized the original modulus-based election of [RFC7432] to Highest Random Weight (HRW) specifically because HRW gives a documented property: adding or removing a PE only changes the winning PE for the (ES, VLAN) keys that mapped to the changed PE, not for every key. This is the same property that motivates the use of Consistent Hashing in distributed caching and load balancing, and RFC 8584 says so directly, in Section 3.1, before stating that a comparison between the two families "will not be considered here." This document takes up that comparison, specifically for the new scope-transition scenario introduced by [I-D.ietf-bess-evpn-per-mcast-flow-df-election], because that scenario is exactly the kind of key-space change (not just PE membership change, but a change in the shape of the key itself) for which the two families' guarantees can plausibly differ. 2. The Comparison RFC 8584 Declined [RFC8584] Section 3.1, quoted in full for precision: "HRW is not the only algorithm that addresses the object-to-server mapping problem with goals of fair load distribution, redundancy, and fast access. There is another family of algorithms that also addresses this problem; these fall under the umbrella of the Consistent Hashing Algorithms [CHASH]. These will not be considered here." [CHASH] is [Karger1997], the founding Consistent Hashing paper, already present in RFC 8584's own reference list. Nine years after RFC 8584's publication, no subsequent BESS document has taken up this comparison; RFC 9722 addresses fast-recovery timers and RFC 9785 addresses preference-based tie-breaking, neither of which bears on the choice of mapping algorithm itself (see Section 8). 3. The Scope Transition Introduced by Per-Flow DF Election [I-D.ietf-bess-evpn-per-mcast-flow-df-election] Section 5.3 changes the DF election key from (ES, VLAN) to (ES, VLAN, S, G) once per-multicast-flow election is active for a given (S,G). This is not merely a change in which PEs participate (the scenario RFC 8584's HRW analysis already covers); it is a change in the cardinality and structure of the key space itself, since a single (ES, VLAN) key becomes as many (ES, VLAN, S, G) keys as there are active multicast groups on that VLAN, each independently subject to election. The document making this change already asserts, without analysis, that the comparison this document proposes is unnecessary: Section 5.1 of [I-D.ietf-bess-evpn-per-mcast-flow-df-election] states verbatim that "All the benefits described in Section 3.2 of [RFC8584] with respect to HRW-based Designated Forwarder (DF) election -- such as deterministic selection, consistency across nodes, and minimal churn -- are fully applicable to the mechanism defined in this document." That sentence is the specific claim this document tests. RFC 8584 Section 3.2's minimal-churn property was established for PE membership changes at a fixed key granularity; it was never evaluated, by RFC 8584 or by this later draft, for the key-space-structure change described above, and no citation or derivation is offered for extending it to that case. Section 6 explains why the extension is not obviously free of cost once realistic (S,G) popularity skew is taken into account. 4. A DF-Churn Metric Define DF-churn, for a transition event (a PE joining or leaving an ES, or the per-flow feature activating for a VLAN), as the fraction of keys (either (ES,VLAN) keys before the transition, or (ES,VLAN,S,G) keys after it, as applicable) whose elected DF changes as a direct result of that event, among all keys that existed both before and after it. A mapping algorithm that minimizes DF-churn for a given class of transition event is preferable for that class, all else equal, because every DF change carries a brief forwarding-state re-convergence cost. 5. Known Theoretical Guarantees 5.1. HRW HRW [HRW1999] guarantees that, for a fixed key, adding or removing a single PE from the candidate set changes the winning PE only for keys that previously mapped to the removed PE (on removal) or that newly map to the added PE with higher weight than the previous winner (on addition); no other key's winner changes. This bounds DF-churn optimally for PE membership change. HRW does not, however, account for per-key load or popularity: it selects a winner by weight alone, with no mechanism to avoid concentrating many high-traffic (S,G) keys onto the same PE. 5.2. Plain Consistent Hashing Consistent Hashing [Karger1997] gives the analogous guarantee for its own setting (cache-to-server assignment under server set changes): on average, only a 1/n fraction of keys remap when a server is added to or removed from a set of n. For the EVPN DF election setting specifically, this guarantee is not stronger than HRW's for PE membership changes; the two are, for that class of event, comparable in the churn they bound. 5.3. Bounded-Load Consistent Hashing [Mirrokni2018] extends Consistent Hashing with an explicit per-server capacity bound, so that no server receives more than a configurable multiple of its fair share of keys, at the cost of redirecting a bounded number of keys away from their otherwise-assigned server. This guarantee has no HRW analogue: HRW has no capacity-awareness mechanism at all, so a HRW-elected DF set can be arbitrarily imbalanced if a small number of (S,G) keys carry most of the traffic, a distribution known empirically to be highly non-uniform (multicast group popularity is routinely modeled as Zipfian in IPTV and financial-market-data deployments, the two dominant use cases for high-scale EVPN multicast). 6. Where HRW Is Expected to Underperform The applicability question this document poses is precisely: does the key-space-structure change in Section 3 (not a PE membership change, a key cardinality change) combined with realistic, skewed (S,G) popularity, produce a PE load imbalance under unmodified HRW large enough to matter operationally, and would a bounded-load Consistent Hashing scheme correct that imbalance at an acceptable DF-churn cost relative to HRW's membership-change optimality. Nothing in [RFC8584] answers this, because RFC 8584 explicitly scoped the underlying algorithm comparison out (Section 2), and [I-D.ietf-bess-evpn-per-mcast-flow-df-election] answers it only by assertion (Section 3), not analysis: its Section 5.1 claim that HRW's minimal-churn property carries over is the conclusion this document's evaluation methodology (Section 7) is designed to check, not an established result it needs to reproduce. 7. Proposed Evaluation Methodology This document proposes, as future work building on this draft: (a) simulate a population of (S,G) keys under a Zipfian popularity distribution across a candidate PE set of realistic size (4-16 PEs, per typical EVPN ES redundancy group sizes); (b) compute per-PE assigned load and DF-churn under PE add/remove and under per-flow-election activation, for unmodified HRW and for bounded-load Consistent Hashing with a capacity bound parameter swept across a representative range; (c) report the load-imbalance / DF-churn trade-off curve for both algorithms, identifying whether there exists a capacity-bound setting under which bounded-load Consistent Hashing dominates HRW on both axes simultaneously for this specific transition class. A negative result (no such dominating setting exists) is as valuable a WG input as a positive one, since RFC 8584's silence on this question currently leaves even that negative conclusion unestablished. 8. Relationship to RFC 9722 and RFC 9785 [RFC9722] ("Fast Recovery for EVPN Designated Forwarder Election") and [RFC9785] ("Preference-Based EVPN Designated Forwarder (DF) Election") both update RFC 8584, addressing, respectively, the time to reconverge after a PE failure and the ability to prefer a specific PE deterministically. Neither revisits the underlying HRW-versus-Consistent-Hashing mapping question this document raises; a candidate mapping-algorithm change of the kind proposed here would need to be shown compatible with both, since fast recovery and preference-based tie-breaking are both properties layered on top of whichever base mapping algorithm the WG selects. 9. Security Considerations An attacker able to influence multicast group membership or (S,G) activation, for instance by joining many distinct groups from a compromised or malicious host, could deliberately trigger DF-churn or PE load imbalance under an algorithm without capacity-awareness, as a resource-exhaustion vector against whichever PE HRW happens to assign the resulting keys to. A capacity-bounded mapping algorithm, if adopted following the evaluation proposed in Section 7, would additionally bound this specific denial-of-service surface, which unmodified HRW does not. 10. IANA Considerations This document requests no IANA actions. 11. References 11.1. Normative References [RFC8584] Rabadan, J., Ed., et al., "Framework for Ethernet VPN Designated Forwarder Election Extensibility", RFC 8584, April 2019. 11.2. Informative References [I-D.ietf-bess-evpn-per-mcast-flow-df-election] "Per multicast flow Designated Forwarder Election for EVPN", Work in Progress. [RFC7432] Sajassi, A., Ed., et al., "BGP MPLS-Based Ethernet VPN", RFC 7432, February 2015. [RFC9722] "Fast Recovery for EVPN Designated Forwarder Election", RFC 9722. [RFC9785] "Preference-Based EVPN Designated Forwarder (DF) Election", RFC 9785. [Karger1997] Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., and D. Lewin, "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web", ACM STOC, 1997. [HRW1999] Thaler, D. and C. Ravishankar, "Using Name-Based Mappings to Increase Hit Rates", IEEE/ACM Transactions on Networking, Vol. 6, No. 1, February 1998. [Mirrokni2018] Mirrokni, V., Thorup, M., and M. Zadimoghaddam, "Consistent Hashing with Bounded Loads", ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018. Author's Address Saumya Dikshit Aruba Networks, HPE Email: saumya.dikshit@hpe.com