As per Relevance of the word analysis, we have this rfc below:
Network Working Group C.
Request for Comments: 2992 NextHop
Category: Informational November 2000
Analysis of an Equal-Cost Multi-Path
Status of this
This memo provides information for the Internet community. It
not specify an Internet standard of any kind. Distribution of
memo is unlimited
Copyright
Copyright (C) The Internet Society (2000). All Rights Reserved
Equal-cost multi-path (ECMP) is a routing technique for
packets along multiple paths of equal cost. The forwarding
identifies paths by next-hop. When forwarding a packet the
must decide which next-hop (path) to use. This document gives
analysis of one method for making that decision. The
includes the performance of the algorithm and the disruption
by changes to the set of next-hops
1. Hash-
One method for determining which next-hop to use when routing
ECMP can be called hash-threshold. The router first selects a key
performing a hash (e.g., CRC16) over the packet header fields
identify a flow. The N next-hops have been assigned unique
in the key space. The router uses the key to determine which
and thus which next-hop to use
As an example of hash-threshold, upon receiving a packet the
performs a CRC16 on the packet's header fields that define the
(e.g., the source and destination fields of the packet), this is
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
each region is 65536/4 or 16k large. The next-hop is chosen
determining which region contains the key (i.e., the CRC result).
Hopps Informational [Page 1]
RFC 2992 Analysis of ECMP Algorithm November 2000
2.
There are a few concerns when choosing an algorithm for
which next-hop to use. One is performance, the
requirements to run the algorithm. Another is disruption (i.e.,
changing of which path a flow uses). Balancing is a third concern
however, since the algorithm's balancing characteristics are
related to the chosen hash function this analysis does not treat
concern in depth
For this analysis we will assume regions of equal size. If
output of the hash function is uniformly distributed the
of flows amongst paths will also be uniform, and so the
will properly implement ECMP. One can implement non-equal-
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.
The performance of the hash-threshold algorithm can be broken
into three parts: selection of regions for the next-hops,
the key and comparing the key to the regions to decide which next-
to use
The algorithm doesn't specify the hash function used to obtain
key. Its performance in this area will be exactly the performance
the hash function. It is presumed that if this calculation proves
be a concern it can be done in hardware parallel to other
that need to complete before deciding which next-hop to use
Since regions are restricted to be of equal size the calculation
region boundaries is trivial. Each boundary is exactly
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
boundary values
To choose the next-hop we must determine which region contains
key. Because the regions are of equal size determining which
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
the next-hops are organized in memory. The obvious use of an
indexed by region yields O(1).
Hopps Informational [Page 2]
RFC 2992 Analysis of ECMP Algorithm November 2000
2.2.
Protocols such as TCP perform better if the path they flow along
not change while the stream is connected. Disruption is
measurement of how many flows have their paths changed due to
change in the router. We measure disruption as the fraction of
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
TCP see [1].
Some algorithms such as round-robin (i.e., upon receiving a
the least recently used next-hop is chosen) are disruptive
of any change in the router. Clearly this is not the case
hash-threshold. As long as the region boundaries remain
the same next-hop will be chosen for a given flow
Because we have required regions to be equal in size the only
for a change in region boundaries is the addition or removal of
next-hop. In this case the regions must all grow or shrink to
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
equally and shift to compensate. In this case 1/4 of region 2 is
in region 1, 1/2 (2/4) of region 3 is in region 2, 1/2 of region 3
in region 4 and 1/4 of region 4 is in region 5. Since each of
original regions represent 1/5 of the flows, the total disruption
1/5*(1/4 + 1/2 + 1/2 + 1/4) or 3/10.
Note that the disruption to flows when adding a region is
to that of removing a region. That is, we are considering
fraction of total flows that changes regions when moving from N
N-1 regions, and that same fraction of flows will change when
from N-1 to N regions
Hopps Informational [Page 3]
RFC 2992 Analysis of ECMP Algorithm November 2000
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
grow equally and shift to compensate. 1/4 of region 2 is now
region 1, 1/2 of region 3 is in region 2, 3/4 of region 4 is
region 3 and 1/4 of region 4 is in region 5. Since each of
original regions represent 1/5 of the flows the, total disruption
7/20.
To generalize, upon removing a region K the remaining N-1
grow to fill the 1/N space. This growth is evenly divided
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
move. The first region grows and so the second region is
towards K by the change in size of the first region. 1/(N(N-1))
the flows from region 2 are subsumed by the change in region 1'
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
1/(N(N-1)). This continues from both ends until you reach
regions that bordered K. The calculation for the number of
subsumed from the Kth region into the bordering regions accounts
the removal of the Kth region. Thus we have the following equation
K-1
--- 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]
RFC 2992 Analysis of ECMP Algorithm November 2000
We now use the the concrete formulas for the sum of integers.
first summation is (K)(K-1)/2. For the second summation notice
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
when K is as close to half way between 1 and N as possible. This
be proven by finding the minimum of the concrete formula for
holding N constant. First break apart the quantities and collect
2K*K - 2K - 2NK + 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
as is the denominator (N)(N-1) so we can drop them. To minimize
take the derivative
-- (K*K - (N+1)K
= 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
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
the least disruption when K is N/2 or N/2 + 1.
Now since the formula is quadratic with a global minimum half
between 1 and N the maximum possible disruption must occur when
regions (1 and N) are removed. If K is 1 or N the formula reduces
1/2.
The minimum possible disruption is obtained by letting K=(N+1)/2.
this case the formula reduces to 1/4 + 1/(4*N). So the range
possible disruption is (1/4, 1/2].
To minimize disruption we recommend adding new regions to the
rather than the ends
Hopps Informational [Page 5]
RFC 2992 Analysis of ECMP Algorithm November 2000
3. Comparison to other
Other algorithms exist to decide which next-hop to use.
algorithms all have different performance and
characteristics. Of these algorithms we will only consider ones
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
exclude round-robin and random choice. We will look at modulo-N
highest random weight
Modulo-N is a "simpler" form of hash-threshold. Given N next-
the packet header fields which describe the flow are run through
hash function. A final modulo-N is applied to the output of
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
added or removed the disruption is (N-1)/N. The performance
Modulo-N is equivalent to hash-threshold
Highest random weight (HRW) is a comparative method similar in
ways to hash-threshold with non-fixed sized regions. For each next
hop, the router seeds a pseudo-random number generator with
packet header fields which describe the flow and the next-hop
obtain a weight. The next-hop which receives the highest weight
selected. The advantage with using HRW is that it has
disruption (i.e., disruption due to adding or removing a next-hop
always 1/N.) The disadvantage with HRW is that the next-
selection is more expensive than hash-threshold. A description
HRW along with comparisons to other methods can be found in [2].
Although not used for next-hop calculation an example usage of
can be found in [3].
Since each of modulo-N, hash-threshold and HRW require a hash on
packet header fields which define a flow, we can factor
performance of the hash out of the comparison. If the hash can
be done inexpensively (e.g., in hardware) it too must be
when using any of the above methods
The lookup performance for hash-threshold, like modulo-N is
optimal O(1). HRW's lookup performance is O(N).
Disruptive behavior is the opposite of performance. HRW is best
1/N. Hash-threshold is between 1/4 and 1/2. Finally Modulo-N
(N-1)/N
If the complexity of HRW's next-hop selection process is
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
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
obvious choice is hash-threshold as it performs as well as modulo-
and is less disruptive
4. Security
This document is an analysis of an algorithm used to implement
ECMP routing decision. This analysis does not directly affect
security of the Internet Infrastructure
5.
[1] Thaler, D. and C. Hopps, "Multipath Issues in Unicast
Multicast", RFC 2991, November 2000.
[2] Thaler, D. and C.V. Ravishankar, "Using Name-Based Mappings
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):
Specification", RFC 2362, June 1998.
6. Author's
Christian E.
NextHop Technologies, Inc
517 W. William
Ann Arbor, MI 48103-4943
U.S.
Phone: +1 734 936 0291
EMail: chopps@nexthop.
Hopps Informational [Page 7]
RFC 2992 Analysis of ECMP Algorithm November 2000
7. Full Copyright
Copyright (C) The Internet Society (2000). All Rights Reserved
This document and translations of it may be copied and furnished
others, and derivative works that comment on or otherwise explain
or assist in its implementation may be prepared, copied,
and distributed, in whole or in part, without restriction of
kind, provided that the above copyright notice and this paragraph
included on all such copies and derivative works. However,
document itself may not be modified in any way, such as by
the copyright notice or references to the Internet Society or
Internet organizations, except as needed for the purpose
developing Internet standards in which case the procedures
copyrights defined in the Internet Standards process must
followed, or as required to translate it into languages other
English
The limited permissions granted above are perpetual and will not
revoked by the Internet Society or its successors or assigns
This document and the information contained herein is provided on
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED,
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE
Funding for the RFC Editor function is currently provided by
Internet Society
Hopps Informational [Page 8]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
