RFC 2992 (rfc2992) - Page 1 of 8

Analysis of an Equal-Cost Multi-Path Algorithm

Alternative Format: Original Text Document
Next >
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
Next >