Network Working Group C. Hopps
Request for Comments: 2992 NextHop Technologies
Category: Informational November 2000
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.
版权所有（C）互联网协会（2000年）。版权所有。
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.
等成本多径（ECMP）是一种沿多条等成本路径路由数据包的路由技术。转发引擎通过下一跳识别路径。转发数据包时，路由器必须决定使用哪个下一跳（路径）。本文件分析了作出该决定的一种方法。分析包括算法的性能和下一跳集的变化所造成的中断。
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.
当使用ECMP路由时，一种确定下一跳使用的方法称为哈希阈值。路由器首先通过在识别流的分组报头字段上执行散列（例如，CRC16）来选择密钥。N个下一跳已在密钥空间中分配唯一区域。路由器使用密钥来确定要使用的区域和下一跳。
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).
作为散列阈值的一个示例，在接收到分组时，路由器对定义流的分组的报头字段（例如，分组的源字段和目的字段）执行CRC16，这是密钥。假设这个目的地有4个下一跳可供选择。每个下一跳被分配一个16位空间（密钥空间）中的区域。为了获得相同的使用率，路由器可能会选择将其平均分割，使每个区域的大小为65536/4或16k。通过确定哪个区域包含密钥（即CRC结果）来选择下一跳。
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.
在本分析中，我们将假设区域大小相等。如果散列函数的输出是均匀分布的，那么流在路径之间的分布也是均匀的，因此该算法将正确地实现ECMP。通过使用大小不等的区域，可以实现非等代价多径路由；但是，非等成本多路径路由不在本文档范围内。
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.
由于区域被限制为大小相等，因此区域边界的计算非常简单。对于第一个区域，从0开始，每个边界与前一个边界的区域大小完全相同。正如我们将要展示的，对于大小相同的区域，我们不需要存储边界值。
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;
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).
因此，找到下一跳所需的时间取决于下一跳在内存中的组织方式。显然，使用按区域索引的数组会产生O（1）。
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）沿的路径不变，则它们的性能会更好。中断是指测量由于路由器的某些变化而导致其路径发生变化的流的数量。我们将中断测量为路径随路由器的某些变化而变化的总流量的分数。如果一条或多条路径正在拍动，这可能会变得很重要。有关中断及其如何影响协议的描述，如
TCP see [1].
TCP见[1]。
Some 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
0123456701234567012345670123456701234567
+-------+-------+-------+-------+-------+
| 1 | 2 | 3 | 4 | 5 |
+-------+-+-----+---+---+-----+-+-------+
| 1 | 2 | 4 | 5 |
+---------+---------+---------+---------+
0123456789012345678901234567890123456789
Figure 1. Before and after deletion of region 3
图1。删除区域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.
在图1中。区域3已被删除。其余地区的增长是平等的，并且会转移以进行补偿。在这种情况下，区域2的1/4现在位于区域1，区域3的1/2（2/4）位于区域2，区域3的1/2位于区域4，区域4的1/4位于区域5。由于每个原始区域代表1/5的流量，因此总中断为1/5*（1/4+1/2+1/2+1/4）或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.
请注意，添加区域时对流的中断等同于删除区域。也就是说，我们正在考虑当从N个区域移动到N-1个区域时，改变区域的总流量的比例，以及当从N-1个区域移动到N个区域时，相同比例的流量将改变。
0123456701234567012345670123456701234567
+-------+-------+-------+-------+-------+
| 1 | 2 | 3 | 4 | 5 |
+-------+-+-----+---+---+-----+-+-------+
| 1 | 2 | 3 | 5 |
+---------+---------+---------+---------+
0123456789012345678901234567890123456789
0123456701234567012345670123456701234567
+-------+-------+-------+-------+-------+
| 1 | 2 | 3 | 4 | 5 |
+-------+-+-----+---+---+-----+-+-------+
| 1 | 2 | 3 | 5 |
+---------+---------+---------+---------+
0123456789012345678901234567890123456789
Figure 2. Before and after deletion of region 4
图2。删除区域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.
如图2所示。区域4已被删除。另外，其余地区也同样增长，并转移以进行补偿。区域2的1/4现在位于区域1，区域3的1/2位于区域2，区域4的3/4位于区域3，区域4的1/4位于区域5。由于每个原始区域代表流量的1/5，因此总中断为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后，剩余的N-1区域增长以填充1/N空间。这种增长在N-1个区域之间平均分配，因此每个区域的大小变化为1/N/（N-1）或1/（N（N-1））。此大小更改会导致非端点区域移动。第一区域增长，因此第二区域因第一区域大小的变化而向K移动。1/（N（N-1））区域2的流量包含在区域1大小的变化中。区域3中的2/（N（N-1））流量包含在区域2中。这是因为区域2移动了1/（N（N-1））并增长了1/（N（N-1））。这将从两端继续进行，直到到达边界为K的区域。计算从第K个区域包含到边界区域的流量数量时，将考虑删除第K个区域。因此，我们有以下等式。
K-1 N
--- i --- (i-K)
disruption = \ --- + \ ---
/ (N)(N-1) / (N)(N-1)
--- ---
i=1 i=K+1
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.
我们可以把因子1/（（N）（N-1））取出来，因为它是常数。
/ K-1 N \
1 | --- --- |
= --- | \ i + \ (i-K) |
(N)(N-1) | / / |
\ --- --- /
1 i=K+1
/ K-1 N \
1 | --- --- |
= --- | \ i + \ (i-K) |
(N)(N-1) | / / |
\ --- --- /
1 i=K+1
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）（K-1）/2。对于第二次求和，请注意，我们是从1到N-K对整数求和，因此它是（N-K）（N-K+1）/2。
(K-1)(K) + (N-K)(N-K+1)
= -----------------------
2(N)(N-1)
(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.
考虑到总和，我们可以看到，当K尽可能接近1和N之间的一半时，干扰最小。这可以通过找到保持N常数的K的混凝土公式的最小值来证明。首先将数量分开并收集。
2K*K - 2K - 2NK + N*N + N
= -------------------------
2(N)(N-1)
2K*K - 2K - 2NK + N*N + N
= -------------------------
2(N)(N-1)
K*K - K - NK N + 1
= -------------- + -------
(N)(N-1) 2(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
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)
= 2K - (N+1)
Which is zero when K is (N+1)/2.
当K为（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.
最后要考虑的是K必须是整数。当N为奇数时（N+1）/2将产生一个整数，而当N为偶数时（N+1）/2将产生一个整数+1/2。在这种情况下，由于对称性，当K为N/2或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.
现在，由于公式是二次的，全局最小值在1和N之间，因此当删除边缘区域（1和N）时，必须出现最大可能的中断。如果K为1或N，则公式减少到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].
通过让K=（N+1）/2获得可能的最小干扰。在这种情况下，公式减少到1/4+1/（4*N）。因此，可能的破坏范围为（1/4，1/2）。
To minimize disruption we recommend adding new regions to the center rather than the ends.
为了最大限度地减少中断，我们建议向中心而不是末端添加新区域。
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.
还有其他算法可以决定使用哪个下一跳。这些算法都具有不同的性能和破坏性特征。在这些算法中，我们只考虑不具有破坏性的设计（即，如果对下一跳的集合不发生变化，则流所采用的路径保持不变）。这将排除循环和随机选择。我们将研究模N和最高随机权重。
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.
模N是散列阈值的“更简单”形式。给定N个下一跳，描述流的包头字段通过哈希函数运行。最后的模N应用于散列的输出。然后，该结果直接映射到下一个跃点之一。模N是最具破坏性的算法；如果添加或删除下一跳，中断为（N-1）/N。模N的性能相当于散列阈值。
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].
最高随机权重（HRW）是一种比较方法，在某些方面类似于非固定大小区域的散列阈值。对于每个下一跳，路由器使用描述流和下一跳的包头字段来种子一个伪随机数生成器，以获得权重。选择接收到最高权重的下一跳。使用HRW的优点是其中断最小（即，由于添加或删除下一跳而导致的中断始终为1/N）。HRW的缺点是下一跳选择比哈希阈值更昂贵。关于HRW的描述以及与其他方法的比较，见[2]。尽管未用于下一跳计算，但可在[3]中找到HRW的示例用法。
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.
由于模N、hash threshold和HRW中的每一个都需要对定义流的包头字段进行hash，因此我们可以从比较中考虑hash的性能。如果哈希不能以低成本完成（例如，在硬件中），则在使用上述任何方法时也必须考虑。
The lookup performance for hash-threshold, like modulo-N is an optimal O(1). HRW's lookup performance is O(N).
哈希阈值的查找性能，如模N是最佳的O（1）。HRW的查找性能为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.
破坏性行为与性能相反。HRW最好使用1/N。哈希阈值在1/4和1/2之间。最后，模N是（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.
如果HRW的下一跳选择过程的复杂性是可以接受的，我们认为它应该被视为哈希阈值的替代方案。这可能是这样的情况，例如，保持每流状态，因此很少选择下一跳。
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.
然而，当HRW的下一跳选择被视为过于昂贵时，显而易见的选择是哈希阈值，因为它的性能与模N一样好，并且破坏性更小。
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.
本文分析了用于实现ECMP路由决策的算法。此分析不会直接影响互联网基础设施的安全性。
[1] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and Multicast", RFC 2991, November 2000.
[1] Thaler，D.和C.Hopps，“单播和多播中的多路径问题”，RFC 29912000年11月。
[2] Thaler, D. and C.V. Ravishankar, "Using Name-Based Mappings to Increase Hit Rates", IEEE/ACM Transactions on Networking, February 1998.
[2] Thaler，D.和C.V.Ravishankar，“使用基于名称的映射来提高命中率”，IEEE/ACM网络交易，1998年2月。
[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.
[3] Estrin，D.，Farinaci，D.，Helmy，A.，Thaler，D.，Deering，S.，Handley，M.，Jacobson，V.，Liu，C.，Sharma，P.和L.Wei，“协议独立多播稀疏模式（PIM-SM）：协议规范”，RFC 2362，1998年6月。
Christian E. Hopps NextHop Technologies, Inc. 517 W. William Street Ann Arbor, MI 48103-4943 U.S.A
Christian E.Hopps NextHop Technologies，Inc.美国密歇根州安娜堡威廉街西517号，邮编：48103-4943
Phone: +1 734 936 0291
EMail: chopps@nexthop.com
Phone: +1 734 936 0291
EMail: chopps@nexthop.com
Copyright (C) The Internet Society (2000). All Rights Reserved.
版权所有（C）互联网协会（2000年）。版权所有。
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.
RFC编辑功能的资金目前由互联网协会提供。