RFC 2992

Analysis of an Equal-Cost Multi-Path Algorithm

📅 published November 2000, from ietf

RFC 2992: Analysis of an Equal-Cost Multi-Path Algorithm 🎀

Okay bestie, this one is a whole vibe 💅. It's RFC 2992, written by C. Hopps of NextHop Technologies for the Network Working Group, and it's classified as Informational. It was published in November 2000. The header doesn't list any RFCs it obsoletes or updates, so it's standing on its own ✨.

  • RFC number: 2992
  • Title: Analysis of an Equal-Cost Multi-Path Algorithm
  • Author: C. Hopps (NextHop Technologies)
  • Working group: Network Working Group
  • Category: Informational
  • Date: November 2000
  • Obsoletes / Updates: none listed in the header

Status of this Memo 📝

So this memo is here to inform the Internet community 🌸. It is not specifying any kind of Internet standard, and distribution is unlimited, so share away 🫶.

Copyright (C) The Internet Society (2000). All Rights Reserved. 💜

Abstract 🦋

Equal-cost multi-path (ECMP) is a routing technique for sending packets along multiple paths that all cost the same, so it's basically the router spreading the love across all the good routes 🌈. The forwarding engine tells paths apart by their next-hop. Every time a packet shows up, the router has to decide which next-hop (path) to use 🤔.

This document analyses one method for making that call. It looks at how well the algorithm performs and how much disruption happens when the set of next-hops changes 🔥.

1. Hash-Threshold ✨

Okay, so one way a router can pick a next-hop with ECMP is called hash-threshold 🧚. The router first makes a key by running a hash (for example, CRC16) over the packet header fields that identify a flow. Then the N next-hops each get their own unique region in the key space, and the router uses the key to figure out which region it lands in, and therefore which next-hop to use 💖.

Here's a concrete example, because I love one 🍓. When a packet comes in, the router runs CRC16 on the header fields that define the flow, like the source and destination fields. That result is the key. Say this destination has 4 next-hops to pick from. Each next-hop gets a region in 16 bit space (the key space). If the router wants equal usage, it can split the space evenly, so each region is 65536/4, or 16k, big. The next-hop gets chosen by checking which region the key (aka the CRC result) falls inside 💅.

2. Analysis 🧮

There are a few things to think about when you're picking an algorithm for choosing a next-hop 👑. The first is performance, which is how much computing it takes to run the algorithm. The second is disruption, which is how often a flow gets moved to a different path. The third is balancing, but since the balancing behaviour is tied directly to the hash function you pick, this analysis doesn't go deep on it 🙈.

For this analysis, we'll assume regions are all the same size. If the hash function's output is uniformly distributed, then flows will spread out evenly across the paths too, which means the algorithm properly implements ECMP ✨. You can do non-equal-cost multi-path routing by using regions of different sizes, but that's outside the scope of this document, so we're not going there today 🙅‍♀️.

2.1. Performance 🏎️

Performance for hash-threshold breaks down into three parts: picking the regions for the next-hops, getting the key, and comparing the key against the regions to decide the next-hop 💜.

The algorithm doesn't say which hash function to use to get the key. Its performance in that step is exactly the performance of whatever hash function you choose. The assumption is that if this step turns out to be a bottleneck, it can be done in hardware, running in parallel with the other operations that have to finish before the next-hop gets picked ⚡.

Because the regions have to be the same size, working out the region boundaries is super easy 🥰. Each boundary is exactly regionsize away from the one before it, starting at 0 for the first region. And as we'll show, for equal-sized regions, we don't actually need to store the boundary values 🤯.

To pick the next-hop, we need to figure out which region contains the key. Since the regions are equal in size, that's just a simple division:

regionsize = keyspace.size / #{nexthops}
region = key / regionsize;

So the time to find the next-hop depends on how the next-hops are laid out in memory 🧠. The obvious approach, an array indexed by region, gives you O(1) 🏆.

Part 1 ends here. Part 2 picks up at Section 2.2 (Disruption), where the figures and the big disruption math live 🦋🧮. Stay tuned, bestie 💖

3. Comparison to other algorithms ✨

okay so there are other algorithms that decide which next-hop to use, and bestie, they all have different performance and disruption vibes 🫶 we're only going to look at the ones that are not disruptive by design. that means if the set of next-hops doesn't change, the path a flow takes stays the same. this kicks out round-robin and random choice 💅 so we're looking at modulo-N and highest random weight (HRW).

modulo-N is kind of a "simpler" version of hash-threshold 🧚 given N next-hops, the packet header fields that describe the flow go through a hash function. then a final modulo-N gets applied to the hash output, and that result maps directly to one of the next-hops. ngl it's the most disruptive of the bunch 💀 if a next-hop gets added or removed, the disruption is (N-1)/N. its performance is equivalent to hash-threshold, so no real glow-up there.

highest random weight (HRW) is a comparative method that's kinda similar to hash-threshold, except its regions aren't fixed in size 🦋 for each next-hop, the router seeds a pseudo-random number generator with the packet header fields that describe the flow and the next-hop, and that gives a weight. the next-hop with the highest weight wins. the big advantage is that it has minimal disruption: the disruption from adding or removing a next-hop is always 1/N. the disadvantage is that picking the next-hop is more expensive than hash-threshold 😭 HRW and how it compares to other methods is described in [2]. HRW isn't used for next-hop calculation there, but an example of how it's used can be found in [3].

since modulo-N, hash-threshold and HRW all need a hash on the packet header fields that define a flow, we can factor the hash's performance out of the comparison 🌸 if the hash can't be done cheaply (for example, in hardware), though, it has to be considered too when using any of the methods above.

the lookup performance of hash-threshold is, like modulo-N, an optimal O(1). HRW's lookup performance is O(N).

disruption is basically the flip side of performance 🍓 HRW is best with 1/N. hash-threshold lands between 1/4 and 1/2. and modulo-N is (N-1)/N.

if HRW's next-hop selection process is acceptable complexity-wise, we think it should be considered as an alternative to hash-threshold 👑 that could be the case when, for example, per-flow state is kept, so the next-hop choice happens infrequently.

but if HRW's next-hop selection is seen as too expensive, the obvious choice is hash-threshold 💖 it performs as well as modulo-N and is less disruptive. literally no brainer.

4. Security Considerations 🔥

okay this part is serious 🙈 this document is an analysis of an algorithm used to implement an ECMP routing decision. the analysis itself does not directly affect the security of the Internet Infrastructure. so no panic, bestie 💜

5. References ✨

  • [1] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and Multicast", RFC 2991, November 2000.
  • [2] Thaler, D. and C.V. Ravishankar, "Using Name-Based Mappings to Increase Hit Rates", IEEE/ACM Transactions on Networking, February 1998.
  • [3] Estrin, D., Farinacci, D., Helmy, A., Thaler, D., Deering, S., Handley, M., Jacobson, V., Liu, C., Sharma, P. and L. Wei, "Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification", RFC 2362, June 1998.

6. Author's Address 🎀

The author is Christian E. Hopps, who you can reach at:

Christian E. Hopps
NextHop Technologies, Inc.
517 W. William Street
Ann Arbor, MI 48103-4943
U.S.A

Phone: +1 734 936 0291
EMail: chopps@nexthop.com

the legal bit, but make it cute: here's the copyright situation, verbatim where it counts 💅

Copyright (C) The Internet Society (2000). All Rights Reserved.

so this document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind. the one catch is that the above copyright notice and this paragraph have to be included on all such copies and derivative works. however, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations. the exceptions are when it's needed for developing Internet standards, in which case the procedures for copyrights defined in the Internet Standards process must be followed, or when it's required to translate it into languages other than English.

the limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns 🦋

this document and the information in it are provided on an "AS IS" basis, and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. no cap, that's the fine print 😭

Acknowledgement 🧚

funding for the RFC Editor function is currently provided by the Internet Society. thank u, Internet Society 🫶✨

📦 where this page comes from