RFC 2992 (rfc2992) - Page 2 of 8

Analysis of an Equal-Cost Multi-Path Algorithm

RFC 2992               Analysis of ECMP Algorithm          November 2000


2.  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