RFC 2992               Analysis of ECMP Algorithm          November 2000


   We now use the the concrete formulas for the sum of integers.  The
   first summation is (K)(K-1)/2.  For the second summation notice that
   we are summing the integers from 1 to N-K, thus it is (N-K)(N-K+1)/2.

                             (K-1)(K) + (N-K)(N-K+1)
                           = -----------------------
                                   2(N)(N-1)

   Considering the summations, one can see that the least disruption is
   when K is as close to half way between 1 and N as possible.  This can
   be proven by finding the minimum of the concrete formula for K
   holding N constant.  First break apart the quantities and collect.

                            2K*K - 2K - 2NK + N*N + N
                          = -------------------------
                                    2(N)(N-1)

                             K*K - K - NK      N + 1
                          = --------------  + -------
                               (N)(N-1)        2(N-1)

   Since we are minimizing for K the right side (N+1)/2(N-1) is constant
   as is the denominator (N)(N-1) so we can drop them.  To minimize we
   take the derivative.
                             d
                             -- (K*K - (N+1)K)
                             dk

                             = 2K - (N+1)

   Which is zero when K is (N+1)/2.

   The last thing to consider is that K must be an integer.  When N is
   odd (N+1)/2 will yield an integer, however when N is even (N+1)/2
   yields an integer + 1/2.  In the case, because of symmetry, we get
   the least disruption when K is N/2 or N/2 + 1.

   Now since the formula is quadratic with a global minimum half way
   between 1 and N the maximum possible disruption must occur when edge
   regions (1 and N) are removed.  If K is 1 or N the formula reduces to
   1/2.

   The minimum possible disruption is obtained by letting K=(N+1)/2.  In
   this case the formula reduces to 1/4 + 1/(4*N).  So the range of
   possible disruption is (1/4, 1/2].

   To minimize disruption we recommend adding new regions to the center
   rather than the ends.



Hopps                        Informational                      [Page 5]

RFC 2992               Analysis of ECMP Algorithm          November 2000


3.  Comparison to other algorithms

   Other algorithms exist to decide which next-hop to use.  These
   algorithms all have different performance and disruptive
   characteristics.  Of these algorithms we will only consider ones that
   are not disruptive by design (i.e., if no change to the set of next-
   hops occurs the path a flow takes remains the same).  This will
   exclude round-robin and random choice.  We will look at modulo-N and
   highest random weight.

   Modulo-N is a "simpler" form of hash-threshold.  Given N next-hops
   the packet header fields which describe the flow are run through a
   hash function.  A final modulo-N is applied to the output of the
   hash.  This result then directly maps to one of the next-hops.
   Modulo-N is the most disruptive of the algorithms; if a next-hop is
   added or removed the disruption is (N-1)/N.  The performance of
   Modulo-N is equivalent to hash-threshold.

   Highest random weight (HRW) is a comparative method similar in some
   ways to hash-threshold with non-fixed sized regions.  For each next-
   hop, the router seeds a pseudo-random number generator with the
   packet header fields which describe the flow and the next-hop to
   obtain a weight.  The next-hop which receives the highest weight is
   selected.  The advantage with using HRW is that it has minimal
   disruption (i.e., disruption due to adding or removing a next-hop is
   always 1/N.)  The disadvantage with HRW is that the next-hop
   selection is more expensive than hash-threshold.  A description of
   HRW along with comparisons to other methods can be found in [2].
   Although not used for next-hop calculation an example usage of HRW
   can be found in [3].

   Since each of modulo-N, hash-threshold and HRW require a hash on the
   packet header fields which define a flow, we can factor the
   performance of the hash out of the comparison.  If the hash can not
   be done inexpensively (e.g., in hardware) it too must be considered
   when using any of the above methods.

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

   Disruptive behavior is the opposite of performance.  HRW is best with
   1/N.  Hash-threshold is between 1/4 and 1/2.  Finally Modulo-N is
   (N-1)/N.

   If the complexity of HRW's next-hop selection process is acceptable
   we think it should be considered as an alternative to hash-threshold.
   This could be the case when, for example, per-flow state is kept and
   thus the next-hop choice is made infrequently.



Hopps                        Informational                      [Page 6]

RFC 2992               Analysis of ECMP Algorithm          November 2000


   However, when HRW's next-hop selection is seen as too expensive the
   obvious choice is hash-threshold as it performs as well as modulo-N
   and is less disruptive.

4.  Security Considerations

   This document is an analysis of an algorithm used to implement an
   ECMP routing decision.  This analysis does not directly affect the
   security of the Internet Infrastructure.

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

   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

















Hopps                        Informational                      [Page 7]

RFC 2992               Analysis of ECMP Algorithm          November 2000


7.  Full Copyright Statement

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

   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, provided that the above copyright notice and this paragraph are
   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, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as 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 contained herein is 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.

Acknowledgement

   Funding for the RFC Editor function is currently provided by the
   Internet Society.



















Hopps                        Informational                      [Page 8]