等價(jià)多徑算法的分析

《等價(jià)多徑算法的分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、www.woxia.netNetworkWorkingGroupC.HoppsRequestforComments:2992NextHopTechnologiesCategory:InformationalNovember2000等價(jià)多徑算法的分析（RFC2992——AnalysisofanEqual-CostMulti-PathAlgorithm）本備忘錄狀態(tài)本文檔講述了一種Internet通信的標(biāo)準(zhǔn)Internet跟蹤協(xié)議,并對(duì)其改進(jìn)提出了討論和建議。請(qǐng)參考最新版本的"InternetOfficialProtocolStandards"(STD1)

2、來獲得本協(xié)議的標(biāo)準(zhǔn)化進(jìn)程和狀態(tài)，此備忘錄的發(fā)布不受任何限制。版權(quán)注意版權(quán)歸因特網(wǎng)協(xié)會(huì)（2000）所有，保留一切權(quán)利。摘要等價(jià)多徑（ECMP）是在有多個(gè)等價(jià)路徑的時(shí)候發(fā)送分組的一項(xiàng)路由技術(shù)。轉(zhuǎn)發(fā)引擎用下一跳來區(qū)分這多個(gè)路徑。在轉(zhuǎn)發(fā)一個(gè)分組的時(shí)候路由器必須作出決策使用哪一條路徑。本文檔分析了一種決策的方法，其中包括對(duì)算法復(fù)雜度的分析和對(duì)改變下一跳路徑時(shí)引起的流量分裂的分析。目錄1.哈希門限（HASH-THRESHOLD）22.分析22.1.復(fù)雜度22.2.分裂（Disruption）33.與其它算法的比較54.安全性問題65.參考文獻(xiàn)66.作者地址67.版

3、權(quán)聲明6致謝71.哈希門限（Hash-Threshold）哈希門限是等價(jià)多徑問題中決定路由的下一跳的一種方法。路由器首先對(duì)包頭中決定流向的各個(gè)域進(jìn)行哈希運(yùn)算（例如CRC16），得到一個(gè)決策碼（key）。將決策碼的可能取值空間劃分成N個(gè)區(qū)域，給每個(gè)不同的下一跳分配其中的一個(gè)區(qū)域。這樣，路由器就可以用根據(jù)決策碼處在哪個(gè)區(qū)域中來決定下一跳的路由。作為哈希門限的一個(gè)例子，對(duì)包頭中決定流向的域（包的源地址和目的地址）進(jìn)行一個(gè)CRC16運(yùn)算，然后得到一個(gè)16比特的決策碼。假定要到達(dá)目的地址有4個(gè)不同的下一跳地址可供選擇，對(duì)每個(gè)下一跳都在16比特空間中分配一塊區(qū)域。

4、如果要使機(jī)會(huì)均等，路由器應(yīng)當(dāng)使每塊區(qū)域都具有相同大小，即65536/4或者16k。哪個(gè)區(qū)域包含了這個(gè)決策碼，就選擇相應(yīng)的下一跳地址。2.分析當(dāng)選擇一個(gè)算法來進(jìn)行下一跳的決策時(shí)，我們關(guān)心這樣幾個(gè)問題。第一個(gè)是復(fù)雜度，也就是算法的運(yùn)算量。第二個(gè)是分裂（disruption，也就是同一個(gè)數(shù)據(jù)包流改變其路由）。第三個(gè)是均衡。由于算法的均衡特性是與哈希函數(shù)直接有關(guān)的，在我們的分析中將不對(duì)這個(gè)問題做深入探討。在我們的分析中我們假定各個(gè)區(qū)域都具有相同的大小。如果哈希函數(shù)的輸出是平均分布的，那么各條路徑上的流量分布也是平均分布的，這樣這個(gè)算法就可以比較好地實(shí)現(xiàn)等價(jià)多路

5、過··走過···需要的時(shí)候記得回來看看····因?yàn)槿菀椎玫剿缘貌坏酱蠹业恼湎Аぜ词惯@樣我們也要做下去！·············我下資源網(wǎng)www.woxia.net徑（ECMP）。非定價(jià)多徑（non-equal-costmulti-path）可以通過給各個(gè)區(qū)域分配不同的大小來實(shí)現(xiàn)，但是這不在本文的范圍之內(nèi)。2.1.復(fù)雜度哈希門限算法的復(fù)雜度可以分成以下三個(gè)部分：不同下一跳的區(qū)域劃分，決策碼的計(jì)算和判斷決策碼在哪一個(gè)區(qū)域中。算法中并沒有強(qiáng)制規(guī)定用哪個(gè)哈希函數(shù)來計(jì)算決策碼。這一步的算法復(fù)雜度完全取決于哈希函數(shù)的復(fù)雜度。我們假定這一步的計(jì)算可以在硬件上與其

6、他需要在做出決策之前完成的操作并行完成。由于各個(gè)區(qū)域都具有相同的大小，對(duì)于區(qū)域邊界的計(jì)算是很容易的。每一條邊界都可以用第一個(gè)區(qū)域的邊界推出來。后面我們將證明，對(duì)于同樣大小的區(qū)域，并不需要存儲(chǔ)它們的邊界值。為了選擇下一跳，我們必須確定決策碼包含在哪個(gè)區(qū)域里。因?yàn)楦鱾€(gè)區(qū)域都是同樣大小，我們用一個(gè)簡單的除法就可以確定出它屬于哪個(gè)區(qū)域。區(qū)域大小＝碼空間大小/下一跳的個(gè)數(shù)區(qū)域號(hào)＝?jīng)Q策碼/區(qū)域大小因此找到下一跳所需要的時(shí)間取決于下一跳在內(nèi)存中的組織方式。最直接的辦法是用一個(gè)從0（1）開始計(jì)數(shù)的數(shù)組來存放各個(gè)下一跳。2.2.分裂（Disruption）類似TCP的協(xié)

7、議在建立連接之后如果路由一直不發(fā)生變化，其性能會(huì)比較好。分裂（disruption）就是用來衡量有多少流量因?yàn)槁酚善鞯哪承┳兓?，它們的路由產(chǎn)生了變化。我們將分裂定義為由于路由器原因而發(fā)生路由變化的流量占總流量的比例。Thiscanbecomeimportantifoneormoreofthepathsisflapping.更詳細(xì)的關(guān)于分裂以及它如何對(duì)類似TCP的協(xié)議產(chǎn)生影響的信息可參考[1]。類似round-robin的算法（接收到一個(gè)包以后，選擇最近最少使用的下一跳）出現(xiàn)分裂的情況是非常頻繁的，而且與路由器的變化無關(guān)。顯然這跟哈希門限算法的情況不一樣

8、。對(duì)于一個(gè)給定的流來說，只要各個(gè)區(qū)域的邊界不變，就會(huì)始終選擇相同的下一跳。由于我們規(guī)定了各個(gè)區(qū)