Network Working Group                                            C. HoppsRequest for Comments: 2992                           NextHop TechnologiesCategory: Informational                                     November 2000             Analysis of an Equal-Cost Multi-Path AlgorithmStatus of this Memo   This memo provides information for the Internet community.  It does   not specify an Internet standard of any kind.  Distribution of this   memo is unlimited.Copyright Notice   Copyright (C) The Internet Society (2000).  All Rights Reserved.Abstract   Equal-cost multi-path (ECMP) is a routing technique for routing   packets along multiple paths of equal cost.  The forwarding engine   identifies paths by next-hop.  When forwarding a packet the router   must decide which next-hop (path) to use.  This document gives an   analysis of one method for making that decision.  The analysis   includes the performance of the algorithm and the disruption caused   by changes to the set of next-hops.1.  Hash-Threshold   One method for determining which next-hop to use when routing with   ECMP can be called hash-threshold.  The router first selects a key by   performing a hash (e.g., CRC16) over the packet header fields that   identify a flow.  The N next-hops have been assigned unique regions   in the key space.  The router uses the key to determine which region   and thus which next-hop to use.   As an example of hash-threshold, upon receiving a packet the router   performs a CRC16 on the packet's header fields that define the flow   (e.g., the source and destination fields of the packet), this is the   key.  Say for this destination there are 4 next-hops to choose from.   Each next-hop is assigned a region in 16 bit space (the key space).   For equal usage the router may have chosen to divide it up evenly so   each region is 65536/4 or 16k large.  The next-hop is chosen by   determining which region contains the key (i.e., the CRC result).Hopps                        Informational                      [Page 1]RFC 2992               Analysis of ECMP Algorithm          November 20002.  Analysis   There are a few concerns when choosing an algorithm for deciding   which next-hop to use.  One is performance, the computational   requirements to run the algorithm.  Another is disruption (i.e., the   changing of which path a flow uses).  Balancing is a third concern;   however, since the algorithm's balancing characteristics are directly   related to the chosen hash function this analysis does not treat this   concern in depth.   For this analysis we will assume regions of equal size.  If the   output of the hash function is uniformly distributed the distribution   of flows amongst paths will also be uniform, and so the algorithm   will properly implement ECMP.  One can implement non-equal-cost   multi-path routing by using regions of unequal size; however, non-   equal-cost multi-path routing is outside the scope of this document.2.1.  Performance   The performance of the hash-threshold algorithm can be broken down   into three parts: selection of regions for the next-hops, obtaining   the key and comparing the key to the regions to decide which next-hop   to use.   The algorithm doesn't specify the hash function used to obtain the   key.  Its performance in this area will be exactly the performance of   the hash function.  It is presumed that if this calculation proves to   be a concern it can be done in hardware parallel to other operations   that need to complete before deciding which next-hop to use.   Since regions are restricted to be of equal size the calculation of   region boundaries is trivial.  Each boundary is exactly regionsize   away from the previous boundary starting from 0 for the first region.   As we will show, for equal sized regions, we don't need to store the   boundary values.   To choose the next-hop we must determine which region contains the   key.  Because the regions are of equal size determining which region   contains the key is a simple division operation.                regionsize = keyspace.size / #{nexthops}                region = key / regionsize;   Thus the time required to find the next-hop is dependent on the way   the next-hops are organized in memory.  The obvious use of an array   indexed by region yields O(1).Hopps                        Informational                      [Page 2]RFC 2992               Analysis of ECMP Algorithm          November 20002.2.  Disruption   Protocols such as TCP perform better if the path they flow along does   not change while the stream is connected.  Disruption is the   measurement of how many flows have their paths changed due to some   change in the router.  We measure disruption as the fraction of total   flows whose path changes in response to some change in the router.   This can become important if one or more of the paths is flapping.   For a description of disruption and how it affects protocols such as   TCP see [1].   Some algorithms such as round-robin (i.e., upon receiving a packet   the least recently used next-hop is chosen) are disruptive regardless   of any change in the router.  Clearly this is not the case with   hash-threshold.  As long as the region boundaries remain unchanged   the same next-hop will be chosen for a given flow.   Because we have required regions to be equal in size the only reason   for a change in region boundaries is the addition or removal of a   next-hop.  In this case the regions must all grow or shrink to fill   the key space.  The analysis begins with some examples of this.              0123456701234567012345670123456701234567             +-------+-------+-------+-------+-------+             |   1   |   2   |   3   |   4   |   5   |             +-------+-+-----+---+---+-----+-+-------+             |    1    |    2    |    4    |    5    |             +---------+---------+---------+---------+              0123456789012345678901234567890123456789              Figure 1. Before and after deletion of region 3   In figure 1. region 3 has been deleted.  The remaining regions grow   equally and shift to compensate.  In this case 1/4 of region 2 is now   in region 1, 1/2 (2/4) of region 3 is in region 2, 1/2 of region 3 is   in region 4 and 1/4 of region 4 is in region 5.  Since each of the   original regions represent 1/5 of the flows, the total disruption is   1/5*(1/4 + 1/2 + 1/2 + 1/4) or 3/10.   Note that the disruption to flows when adding a region is equivalent   to that of removing a region.  That is, we are considering the   fraction of total flows that changes regions when moving from N to   N-1 regions, and that same fraction of flows will change when moving   from N-1 to N regions.Hopps                        Informational                      [Page 3]RFC 2992               Analysis of ECMP Algorithm          November 2000              0123456701234567012345670123456701234567             +-------+-------+-------+-------+-------+             |   1   |   2   |   3   |   4   |   5   |             +-------+-+-----+---+---+-----+-+-------+             |    1    |    2    |    3    |    5    |             +---------+---------+---------+---------+              0123456789012345678901234567890123456789              Figure 2. Before and after deletion of region 4   In figure 2. region 4 has been deleted.  Again the remaining regions   grow equally and shift to compensate.  1/4 of region 2 is now in   region 1, 1/2 of region 3 is in region 2, 3/4 of region 4 is in   region 3 and 1/4 of region 4 is in region 5.  Since each of the   original regions represent 1/5 of the flows the, total disruption is   7/20.   To generalize, upon removing a region K the remaining N-1 regions   grow to fill the 1/N space.  This growth is evenly divided between   the N-1 regions and so the change in size for each region is 1/N/(N-   1) or 1/(N(N-1)).  This change in size causes non-end regions to   move.  The first region grows and so the second region is shifted   towards K by the change in size of the first region.  1/(N(N-1)) of   the flows from region 2 are subsumed by the change in region 1's   size.  2/(N(N-1)) of the flows in region 3 are subsumed by region 2.   This is because region 2 has shifted by 1/(N(N-1)) and grown by   1/(N(N-1)).  This continues from both ends until you reach the   regions that bordered K.  The calculation for the number of flows   subsumed from the Kth region into the bordering regions accounts for   the removal of the Kth region.  Thus we have the following equation.                           K-1              N                           ---    i        ---  (i-K)             disruption =  \     ---    +  \     ---                           /   (N)(N-1)    /   (N)(N-1)                           ---             ---                           i=1            i=K+1   We can factor 1/((N)(N-1)) out as it is constant.                                /  K-1         N        \                          1     |  ---        ---       |                     =   ---    |  \    i  +  \   (i-K) |                       (N)(N-1) |  /          /         |                                \  ---        ---       /                                     1        i=K+1Hopps                        Informational                      [Page 4]