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

Document Type RFC - Informational (November 2000; No errata)
Last updated 2013-03-02
Stream Legacy
Formats plain text html pdf htmlized bibtex
Stream Legacy state (None)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state RFC 2992 (Informational)
Telechat date
Responsible AD (None)
Send notices to (None)
Network Working Group                                            C. Hopps
Request for Comments: 2992                           NextHop Technologies
Category: Informational                                     November 2000

             Analysis of an Equal-Cost Multi-Path Algorithm

Status 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 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                      [Page 2]
RFC 2992               Analysis of ECMP Algorithm          November 2000

2.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.
Show full document text