多路徑分發在單點傳送和多點傳送下一路程段選擇

本備忘錄的狀態

此備忘錄為網絡成員提供信息。它不詳細說明任何形式的一個網絡標準，因此這個備忘
錄所作的貢獻是有限的。

版權申明
Copyright(C)TheInte.netSociety(2000).AllRightsReserved.


摘要

各種各樣的路由協議，包括開放式的最短路徑優先（OSPF）和中間系統對中間系統
（ISIS），都明確的遵循ECMP路由。一些路由器的執行也按照RIP的平等選擇多路徑分發和
其它的路由協議。在一個轉換器上多路徑路由的作用是使用某種方法選擇哪種傳送下一路段
將給定的數據包送到任意給定的目的地。

目錄
1.介紹 1
2.關心的問題 2
3.要求 2
4.解決辦法 3
4.1.單點傳送轉換 4
4.2.多點傳送轉換 4
5.適用性 4
6.冗余的并行連接 4
7.安全方面的考慮 5
8.參考書 5
9.作者地址 5
10.所有版權申明 6
10.鳴謝 7

1.介紹

各種各樣的路由協議，包括OSPF和ISIS，明確的按照“平等選擇多路徑”路由。一些
路由器的執行也按照RIP的平等選擇多路分發和其它的路由協議。使用平等選擇多路意味著
如果多路的平等選擇路由到同一目的地，它們能夠發現并且在多余的路徑中加載平衡。

多路由在一個轉換機上的作用是使用某種方法選擇哪種傳送下一路段將給定的數據包
送到任意給定的目的地。此備忘錄的概述了目前的慣例，問題和解決辦法。

2.關心的問題

多路由器轉換機運許多路徑傳輸。有時通過round-robin來路由，每個數據包按照
round-robin的形式路由到給定的目的地。這就提供了一種加載平衡的形式，但是有些問題伴
隨著像round-robin或隨機而產生：

各種各樣的路徑MTU
由于每個冗長的路徑可以有不同的MTU，這就意味著所有的路徑MTU能通過一個個
包的成分而改變，否定了路徑MTU發現的有用路徑。

各種各樣的潛伏因素：
由于各種冗長的路徑可以有不同的潛伏，會引起數據包在各自路徑傳輸時常常導致不按
照命令發送，增加了發送的潛伏和緩沖設備。


數據包的重新整理導致TCP認為當一個很長的隊列數據包到時替換了以前的那個數據
包而導致丟失。但有三個或更多數據包時再后來到的包前被接收時，TCP進入了一個被叫
做“快速轉發”的模式，這種模式消耗了額外的帶寬（它能夠潛伏的促使更多的丟失，減少
了吞吐量）當它試圖轉發不必要的被耽擱的數據包時。因此，數據包的重新整理對網絡的性
能是不利的。

調試
普通的調試方法像ping和tranceroute在目前的多路徑中缺乏可靠性而且甚至是完全錯
誤的結果。

在多點傳送路由中，多路徑的問題是多點傳送路由協議通過對同一組地址的所有接收者構造
一棵單一的樹阻止了循環和復制。多點傳送路由協議配置現在（DVMRP,PIM-DM,PIM-SM）
構造最短路徑的樹來確立任一資源，或是另一個路由器被命名為核心或集合點。
因此，他們確保復制的方式不會出現因為一個給定的樹必須僅能使用對單一樹根的下一路
段。

3.要求
在文件的最后，我們將用術語“流程”來代表那個路由器保持路由狀態的間隔尺寸。流
程的精確定義可以依據是實際的執行。例如，一個流程可能由目的地址單獨確定，或是由（資
源地址，目的地址，協議id）三部分確定。因此“流程”不是術語“微流程”的同義詞。當
然，包括實際上由問題的下一路程段選擇程序的傳輸層信息。例如，如果數據包被分段，傳
輸層信息不可能在每個數據包中被看到。此外，選擇路徑依靠傳輸層域像用在兩個相同終端
的并發線路中的MTU可能否定了隱藏信息的好處。
所有在以前的部分中被概括出來的問題會發生當在相同的單點傳送或多點傳送的數據
包在多選路徑中被分開。正常的解決辦法是確保相同的流程總是被用在相同的路徑中。

值得注意的兩點附加特點：

最小中斷：
當多路選擇被用時，意味著對下一路段是多路線有效的，從考慮的事項來添加刪除路程
比僅僅通過使用“最好"路線時的機會要更多。當多種路徑在使用中，因此一系列更優先的
路線實際上可能被用來傳輸，由于沒使用多路程路線的變動可能會更大，因此潛在的數據包
重新整理和數據包丟失。所以，由于下一路段的附加或刪除而引起的影響就需要最小化活動
的流程。
快速執行：
附加計算的數量需要前一個數據包應該小。例如，當進行round-robin時，這一計算可
能由一下一段路程的索引組成。

4.解決辦法
我們目前提供了三種可能的方法來改進多路徑的性能然后討論他們對單點傳送和多點
傳送傳輸的適用性。


N模式的復述
從下一路段的N列表中選擇一個下一路段，路由器在確定以流程的數據包頭域中執行一
種N模式的復述。它有快速的優點，所有流程改變路徑花費(N-1)/N無論何時當一個下一路
段被增加或刪除。

開端復述：
在執行確定流程的數據包頭域的復述前路由器先選擇一個鍵。N下一路段已經被分配了
特殊的區域在復述運行輸出的空間。通過比較區域邊界的價值路由器能夠決定復述價值屬于
哪個區和決定使用哪個下一路段。當下一路段被增加或刪除時這種方法有僅僅作用與區域邊
界的流程的優點。對ECMP的開端復述查找能通過一種簡單的分配來實現。當下一路段被增
加或刪除時，在1/4和1/2之間所有流程的被改變路徑。一種這種方法的分析就能被建立。

最高的隨機負荷（HRW）
路由器就像在下一路段的地址上那樣通過執行對確定流程的數據包頭域的復述來為
EACH的下一路段估計一個鍵。然后路由器根據結果最高的鍵值來選擇下一路段。這樣有利
于使通過下一路段增加或減少而起作用的流程的數目達到最小，但是這樣的花費大約是一個
N復述模型的N倍。
這三種選擇性的辦法的適用性至少依據兩個因素：不管轉換機是否維持每一流程的狀態
和CPU對多路轉換機是怎樣的珍貴。
一些路由器因為某些理由可以維持每一流程而不去支持多路徑。例如，路由器典型的為
多點傳送流程維持每一流程以至于他們能保持在流程中應該被復制的數據包的接口目錄。
如果每一流程的狀態在一個多路徑轉換集中被保持，那下一路段的估計能夠在狀態創建
的時間里被路由器執行。由于下一路段已被提前估計，因此這就不用像一般的單一下一路段
那樣在數據包轉換的時候需要花費額外的時間。在這樣的情況下，包括round-robin,隨機，
N模型，開端復述或HRW中的任意一種都可以被用了。在一個流程的生命期中由于通過路由
器的并發的下一路段估計往往總是被選擇同一路徑，所以如果轉換機的狀態能夠通過任意理
由被去掉的話那像N模型，開端復述和HRW這些復述的運行將會更好。這對改進路由的調試
也是有用的。最后，最佳化路徑的穩定性在上面提到的方法中HRW的使用是最好的。
如果在轉換機中每一流程的狀態不能被維持，那使用多點傳送下一路段時需要的因為下
一路段在數據包到達時已經被計算出來。當CPU比流程路徑穩定性更珍貴時，在上面提到的
方法中開端復述將被建議使用。

4.1.單點傳送轉換
依據執行單點傳送的運行可能保持每一流程的狀態也可能不被保持。我們建議轉換機執
行保持流程的狀態，路由器應該使用HRW在選擇下一路段的狀態創建時間時，沒有每一流程
狀態的轉換機使用開端復述。
4.2.多點傳送轉換
目前的多點傳送轉換引擎使用根據組和源分址的一個高速緩沖存儲器。這就意味著目前的多
點傳送轉換機總是保持每個流程的狀態，雖然流程因為一些多點傳送路由協議可能相當的不
精確（e.g.從所有的原傳送到同一目的地）。由于每一流程的狀態都被轉換機保持，因此建
議路由器總是使用HRW來選擇下一路段。
路由器使用像PIM-SM這樣的簡明連接協議因此應該用多路徑通知當決定連接哪一相鄰
的地方并且發送一條連接信息。例如，當因為一個給定的RP(RendezvousPoint)存在多重
的下一路段連接信息將被發送到下一個連接，建議為每個組使用HRW來選擇下一路段。

5.適用性
運算法則在所有依靠某些復述功能形式（除了round-robin）上討論。當復述運行被均
一的分配時平等的流程分配也被完成。由于一般使用的復述功能僅僅當輸入數量相當大時才
變成均一分配，這些運算法則更加適用路由器路由許多流程，例如，一個小的商業設置。



6.冗余的并行連接
當在同一對路由器中使用多重的并行連接時一個相關聯的問題就發生了。一個普遍的解
決辦法是當被用于路由時把兩個連接捆到一個超連接上。對多點傳送轉換來說這樣兩個連接
減少到一個下一路段的結果是可以防止復制。當一個單點傳送或多點傳送的包被隊列在復合
連接上時，仍然需要某種前面討論過的方法來決定傳輸數據包到那里的物理連接。如果并行
連接一樣，那本文中所討論的大多數要關心的問題用復合連接可以避免。信息包記錄除外，
因為記錄可能在round-robin中仍然發生，反作用于TCP。

7.安全方面的考慮
本文中討論的分發各種各樣的方法從多重有效的下一路段種選擇一個下一路段。同樣的
它不直接影響因特網的基礎下部構造或是它的應用軟件的安全。
一個問題值得提一下，然而當下一路段的選擇時可預期的，一個攻擊者能合成所有同樣
復述的通信量，使得可能開始一個不接受服務的攻擊而使某一特殊路徑超載。由于當同一下
一路段總是被選擇這一特殊情況，像一個當多路徑不被使用時的攻擊是最容易的。引進多路
徑路由時得像那樣的攻擊變得更加困難，復述越是不可預知，操作對任意單一連接的不接受
服務的攻擊就越難。

8.參考書
1]Moy,J.,"OSPFVersion2",STD54,RFC2328,April1998.

[2]Maufer,T.,"DeployingIPMulticastintheEnterprise",
Prentice-Hall,1998.

[3]Hopps,C.,"AnalysisofanEqual-CostMulti-PathAlgorithm",RFC
2992,November2000.

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

[5]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]Allman,M.,Paxson,V.andW.Stevens,"TCPCongestionControl",
RFC2581,April1999.

[7]Nichols,K.,Blake,S.,Baker,F.andD.Black.,"Definitionof
theDifferentiatedServicesField(DSField)intheIPv4and
IPv6Headers",RFC2474,December1998.
9.作者地址
DaveThaler
Microsoft
OneMicrosoftWay
Redmond,WA98052
電話：+14257038835
E-Mail:dthaler@dthaler.microsoft.com

ChristianE.Hopps
NextHopTechnologies,Inc.
517W.WilliamStreet
AnnArbor,MI48103-4943
U.S.A
電話：+17349360291
E-Mail:chopps@nexthop.com
10.所有版權申明
Copyright(C)TheInternetSociety(2000).AllRightsReserved.

Thisdocumentandtranslationsofitmaybecopiedandfurnishedto
others,andderivativeworksthatcommentonorotherwiseexplainit
orassistinitsimplementationmaybeprepared,copied,published
anddistributed,inwholeorinpart,withoutrestrictionofany
kind,providedthattheabovecopyrightnoticeandthisparagraphare
includedonallsuchcopiesandderivativeworks.However,this
documentitselfmaynotbemodifiedinanyway,suchasbyremoving
thecopyrightnoticeorreferencestotheInternetSocietyorother
Internetorganizations,exceptasneededforthepurposeof
developingInternetstandardsinwhichcasetheproceduresfor
copyrightsdefinedintheInternetStandardsprocessmustbe
followed,orasrequiredtotranslateitintolanguagesotherthan
English.

Thelimitedpermissionsgrantedaboveareperpetualandwillnotbe
revokedbytheInternetSocietyoritssuccessorsorassigns.

Thisdocumentandtheinformationcontainedhereinisprovidedonan
"ASIS"basisandTHEINTERNETSOCIETYANDTHEINTERNETENGINEERING
TASKFORCEDISCLAIMSALLWARRANTIES,EXPRESSORIMPLIED,INCLUDING
BUTNOTLIMITEDTOANYWARRANTYTHATTHEUSEOFTHEINFORMATION
HEREINWILLNOTINFRINGEANYRIGHTSORANYIMPLIEDWARRANTIESOF
MERCHANTABILITYORFITNESSFORAPARTICULARPURPOSE.

10.鳴謝

FundingfortheRFCEditorfunctioniscurrentlyprovidedbythe
InternetSociety.