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]
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]
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.
For a description of disruption and how it affects protocols such as    TCP see [1].
unequalSome 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]
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+1
Hopps                        Informational                      [Page 4]
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]

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。