等價多徑算法的分析

本備忘錄狀態
本文檔講述了一種Inte.net通信的標準Internet跟蹤協議,并對其改進提出了討論和建
議。請參考最新版本的"InternetOfficialProtocolStandards"(STD1)來獲得本協議的
標準化進程和狀態，此備忘錄的發布不受任何限制。
版權注意
版權歸因特網協會（2000）所有，保留一切權利。
摘要
等價多徑（ECMP）是在有多個等價路徑的時候發送分組的一項路由技術。轉發引擎用下
一跳來區分這多個路徑。在轉發一個分組的時候路由器必須作出決策使用哪一條路徑。本文
檔分析了一種決策的方法，其中包括對算法復雜度的分析和對改變下一跳路徑時引起的流量
分裂的分析。

目錄
1.哈希門限（HASH-THRESHOLD） 2
2.分析 2
2.1.復雜度 2
2.2.分裂（Disruption） 3
3.與其它算法的比較 5
4.安全性問題 6
5.參考文獻 6
6.作者地址 6
7.版權聲明 6
致謝 7

1.哈希門限（Hash-Threshold）
哈希門限是等價多徑問題中決定路由的下一跳的一種方法。路由器首先對包頭中決定流
向的各個域進行哈希運算（例如CRC16），得到一個決策碼（key）。將決策碼的可能取值空
間劃分成N個區域，給每個不同的下一跳分配其中的一個區域。這樣，路由器就可以用根據
決策碼處在哪個區域中來決定下一跳的路由。
作為哈希門限的一個例子，對包頭中決定流向的域（包的源地址和目的地址）進行一個
CRC16運算，然后得到一個16比特的決策碼。假定要到達目的地址有4個不同的下一跳地址
可供選擇，對每個下一跳都在16比特空間中分配一塊區域。如果要使機會均等，路由器應當
使每塊區域都具有相同大小，即65536/4或者16k。哪個區域包含了這個決策碼，就選擇相
應的下一跳地址。
2.分析
當選擇一個算法來進行下一跳的決策時，我們關心這樣幾個問題。第一個是復雜度，也
就是算法的運算量。第二個是分裂（disruption，也就是同一個數據包流改變其路由）。第
三個是均衡。由于算法的均衡特性是與哈希函數直接有關的，在我們的分析中將不對這個問
題做深入探討。
在我們的分析中我們假定各個區域都具有相同的大小。如果哈希函數的輸出是平均分布
的，那么各條路徑上的流量分布也是平均分布的，這樣這個算法就可以比較好地實現等價多
徑（ECMP）。非定價多徑（non-equal-costmulti-path）可以通過給各個區域分配不同的大
小來實現，但是這不在本文的范圍之內。
2.1.復雜度
哈希門限算法的復雜度可以分成以下三個部分：不同下一跳的區域劃分，決策碼的計算
和判斷決策碼在哪一個區域中。
算法中并沒有強制規定用哪個哈希函數來計算決策碼。這一步的算法復雜度完全取決于
哈希函數的復雜度。我們假定這一步的計算可以在硬件上與其他需要在做出決策之前完成的
操作并行完成。
由于各個區域都具有相同的大小，對于區域邊界的計算是很容易的。每一條邊界都可以
用第一個區域的邊界推出來。后面我們將證明，對于同樣大小的區域，并不需要存儲它們的
邊界值。
為了選擇下一跳，我們必須確定決策碼包含在哪個區域里。因為各個區域都是同樣大小，
我們用一個簡單的除法就可以確定出它屬于哪個區域。
區域大?。酱a空間大小/下一跳的個數
區域號＝決策碼/區域大小
因此找到下一跳所需要的時間取決于下一跳在內存中的組織方式。最直接的辦法是用一
個從0（1）開始計數的數組來存放各個下一跳。
2.2.分裂（Disruption）
類似TCP的協議在建立連接之后如果路由一直不發生變化，其性能會比較好。分裂
（disruption）就是用來衡量有多少流量因為路由器的某些變化，它們的路由產生了變化。
我們將分裂定義為由于路由器原因而發生路由變化的流量占總流量的比例。Thiscanbecome
importantifoneormoreofthepathsisflapping.更詳細的關于分裂以及它如何對類
似TCP的協議產生影響的信息可參考[1]。
類似round-robin的算法（接收到一個包以后，選擇最近最少使用的下一跳）出現分裂
的情況是非常頻繁的，而且與路由器的變化無關。顯然這跟哈希門限算法的情況不一樣。對
于一個給定的流來說，只要各個區域的邊界不變，就會始終選擇相同的下一跳。
由于我們規定了各個區域的大小是相同的，那么區域邊界發生變化的唯一原因就是增加
或者去掉了一個下一跳。這時各個區域就必須同時增大或者縮小，仍然保持將整個決策碼空
間填滿。我們從下面的這個例子開始進行分析。

0123456701234567012345670123456701234567
+-------+-------+-------+-------+-------+
|1|2|3|4|5|
+-------+-+-----+---+---+-----+-+-------+
|1|2|4|5|
+---------+---------+---------+---------+
0123456789012345678901234567890123456789
圖1.刪除區域3的前后
在圖1中，區域3被刪除了。剩下的區域同時增大并且平移，將整個碼空間仍然填滿。
這時區域2中的1/4現在屬于區域1，區域3的1/2現在屬于區域2，區域3的另1/2屬于區
域4，還有區域4的1/4屬于區域5。原來每個區域都代表流量的1/5，那么整個的分裂比例
可以計算為
1/5*(1/4+1/2+1/2+1/4)即3/10
需要注意的是當加入一個新的區域的時候所產生的分裂和去掉一個區域是完全相同的。
也就是說，我們只需要考慮區域數從N變化到N-1時所產生的分裂流量的比例，而區域數從
N-1變到N時的分裂流量的比例是完全相同的。

0123456701234567012345670123456701234567
+-------+-------+-------+-------+-------+
|1|2|3|4|5|
+-------+-+-----+---+---+-----+-+-------+
|1|2|3|5|
+---------+---------+---------+---------+
0123456789012345678901234567890123456789
圖2.刪除區域4的前后

在圖2中，區域4被刪除了。與前面一樣，剩下的區域同時增大并且相應平移。區域2
的1/4現在屬于區域1，區域3的1/2現在屬于區域2，區域4的3/4現在屬于區域3，并且
區域4的1/4現在屬于區域5。由于原來每個區域代表整個流量的1/5，總體的分裂比例是
7/20。
考慮一般的情況，去掉了區域K，剩下的N-1個區域平均增長。增長的流量是平均分配在N-1
個區域中的，因此每個區域的大小的變化為1/N/(N-1)或1/(N(N-1))。大小上的變化會引起
除了兩端以外的其它區域發生平移。第一個區域增大了，那么第二個區域就朝向K移動了相
應的增長量。區域2中的1/(N(N-1))的流量包含在區域1的大小變化之中。區域3中的
2/(N(N-1))的流量包含在區域2之中，這是因為區域2向區域3的方向平移了1/(N(N-1))又
增大了1/(N(N-1))。這樣的過程從兩端開始，一直到到達區域K。這樣我們就有了下面的計
算公式：

K-1N
---i---(i-K)
分裂比例=\---+\---
/(N)(N-1)/(N)(N-1)
------
i=1i=K+1

將常數因子1/((N)(N-1))提出來，

/K-1N\
1|------|
分裂比例=---|\i+\(i-K)|
(N)(N-1)|//|
\------/
1i=K+1

我們現在用連續整數和的計算公式，第一項為(K)(K-1)/2，第二項為(N-K)(N-K+1)/2，
那么

(K-1)(K)+(N-K)(N-K+1)
分裂比例=-----------------------
2(N)(N-1)

從公式中可以看出當K接近1和N的中間的時候分裂比例最小。這一點可以很容易得到
證明。假定N為常數，先將各個因子分解在合并：

2K*K-2K-2NK+N*N+N
=-------------------------
2(N)(N-1)

K*K-K-NKN+1
=--------------+-------
(N)(N-1)2(N-1)

上式的第二項是常量，可以將其忽略。第一項的分母也是常量，也可以忽略。對第一項
取導數，得到：
d
--(K*K-(N+1)K)
dk

=2K-(N+1)

當K為(N+1)/2上式為零。
當然，K必須是一個整數。當N為奇數時，(N+1)/2是一個整數，然而當N為偶數時，(N+1)/2
不是整數。在這種情況下，當K為N/2或N/2＋1時分裂比例最小。
因為分裂比例的表達式是一個在1和N的中點處取全局最小點的二次多項式，那么它的
最大值一定在兩端處取到。當K為1或N時，分裂比例為1/2。
令K=(N+1)/2，表達式的值為1/4+1/(4*N)，為全局最小值。因此，可能的分裂比例的
取值范圍為(1/4,1/2]。
為了減小可能造成的分裂流量，我們建議將新區域加在中間而不是兩端。
3.與其它算法的比較
目前還有其它的一些算法用來做下一跳決策。這些算法的復雜度和分裂比例都不大一樣。
我們這里只考慮其中的幾種算法，它們在設計上是非頻繁分裂的（notdisruptivebydesign，
也就是說如果下一跳的可能集合不發生變化，路由就會始終保持一致）。這就排除了
round-robin算法和隨機選擇算法。我們這里將考慮模N算法和最高隨機權重算法。
模N算法是哈希門限算法的一種簡單特例。給定N個下一跳，對數據包頭中決定流向（源、
目的地址）的域進行一個哈希運算，然后對哈希運算的結果再對N取模，然后根據這個結果
直接就決定了選取哪一個下一跳。模N算法的分裂比例是所有這類算法中最大的，如果增加
或刪除一個下一跳，所帶來的分裂比例是(N-1)/N。模N算法的復雜度與哈希門限算法是相當
的。
最高隨機權重算法（Highestrandomweight,HRW）在某些方面與哈希門限算法有類似
之處，比如區域大小都是不固定的。對于每個下一跳，路由器用數據包頭中決定流向的域和
下一跳一起作為一個偽隨機數發生器的種子，并用它來生成一個權重。然后選擇權重最大的
那個下一跳。使用HRW的好處在于它所帶來的流量分裂很?。尤牖蛉サ粢粋€下一跳所帶來
的分裂比例一般為1/N）。同時，它的缺點在于它比哈希門限算法更復雜，實現代價更高。
[2]中給出了HRW算法與其它一些算法的比較的結果。[3]中給出了使用HRW的一個例子。
因為模N算法、哈希門限算法、HRW算法都要對決定流向的包頭域進行一次哈希運算，
我們在進行復雜度比較時可以將哈希運算提出來不進行比較。如果哈希運算不能夠用硬件簡
單高效地實現，那么上面的幾種方法都必須重新進行考慮。
哈希門限的查表操作跟模N操作一樣，最優情況下復雜度為O(1)。HRW的查表操作的復
雜度為O(N)。
流量分裂的表現與復雜度相反。HRW最好，分裂因子為1/N。哈希門限的分裂因子在1/4
和1/2之間。模N算法的分裂因子為(N-1)N。
如果HRW下一跳選擇過程的復雜度可以接收的話，我們認為可以在它和哈希門限算法進
行選擇。它可以應用于類似這樣的情況，路由器中保存了每個流的狀態，這樣就不需要頻繁
進行下一跳決策。
當然，如果發現HRW算法實現起來代價太大的時候，顯然還是應該選擇哈希門限算法，
因為它的復雜度與模N算法一樣但是流量分裂要小一些。
4.安全性問題
本文檔時對ECMP路由決策的一個算法的分析，與Internet體系結構的安全性沒有直接的
關系。
5.參考文獻
[1]Thaler,D.andC.Hopps,"MultipathIssuesinUnicastand
Multicast",RFC2991,November2000.

[2]Thaler,D.andC.V.Ravishankar,"UsingName-BasedMappingsto
IncreaseHitRates",IEEE/ACMTransactionsonNetworking,
February1998.

[3]Estrin,D.,Farinaclearcase/" target="_blank" >cci,D.,Helmy,A.,Thaler,D.,Deering,S.,
Handley,M.,Jacobson,V.,Liu,C.,Sharma,P.andL.Wei,
"ProtocolIndependentMulticast-SparseMode(PIM-SM):Protocol
Specification",RFC2362,June1998.
6.作者地址
ChristianE.Hopps
NextHopTechnologies,Inc.
517W.WilliamStreet
AnnArbor,MI48103-4943
U.S.A

Phone:+17349360291
EMail:chopps@nexthop.com
7.版權聲明
版權歸Internet協會所有（1999）。保留所有權利。
本文及其譯本可以提供給其他任何人，可以準備繼續進行注釋，可以繼續拷貝、出版、發
布，無論是全部還是部分，沒有任何形式的限制，不過要在所有這樣的拷貝和后續工作中提
供上述聲明和本段文字。無論如何，本文檔本身不可以做任何的修改，比如刪除版權聲明或
是關于Internet協會、其他的Internet組織的參考資料等。除了是為了開發Internet標準
的需要，或是需要把它翻譯成除英語外的其他語言的時候，在這種情況下，在Internet標準
程序中的版權定義必須被附加其中。
上面提到的有限授權允許永遠不會被Internet協會或它的繼承者或它的下屬機構廢除。
本文檔和包含在其中的信息以"Asis"提供給讀者，Internet社區和Internet工程任務
組不做任何擔保、解釋和暗示，包括該信息使用不破壞任何權利或者任何可商用性擔?；蛱?BR>定目的。
致謝
Internet協會當前為RFC編輯提供了資助，對此表示感謝。