資源描述：
《等價多徑算法的分析》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、www.woxia.netNetworkWorkingGroupC.HoppsRequestforComments:2992NextHopTechnologiesCategory:InformationalNovember2000等價多徑算法的分析（RFC2992——AnalysisofanEqual-CostMulti-PathAlgorithm）本備忘錄狀態(tài)本文檔講述了一種Internet通信的標(biāo)準(zhǔn)Internet跟蹤協(xié)議,并對其改進提出了討論和建議。請參考最新版本的"InternetOfficialProtocolStandards"(STD1)
2、來獲得本協(xié)議的標(biāo)準(zhǔn)化進程和狀態(tài)，此備忘錄的發(fā)布不受任何限制。版權(quán)注意版權(quán)歸因特網(wǎng)協(xié)會（2000）所有，保留一切權(quán)利。摘要等價多徑（ECMP）是在有多個等價路徑的時候發(fā)送分組的一項路由技術(shù)。轉(zhuǎn)發(fā)引擎用下一跳來區(qū)分這多個路徑。在轉(zhuǎn)發(fā)一個分組的時候路由器必須作出決策使用哪一條路徑。本文檔分析了一種決策的方法，其中包括對算法復(fù)雜度的分析和對改變下一跳路徑時引起的流量分裂的分析。目錄1.哈希門限（HASH-THRESHOLD）22.分析22.1.復(fù)雜度22.2.分裂（Disruption）33.與其它算法的比較54.安全性問題65.參考文獻66.作者地址67.版
3、權(quán)聲明6致謝71.哈希門限（Hash-Threshold）哈希門限是等價多徑問題中決定路由的下一跳的一種方法。路由器首先對包頭中決定流向的各個域進行哈希運算（例如CRC16），得到一個決策碼（key）。將決策碼的可能取值空間劃分成N個區(qū)域，給每個不同的下一跳分配其中的一個區(qū)域。這樣，路由器就可以用根據(jù)決策碼處在哪個區(qū)域中來決定下一跳的路由。作為哈希門限的一個例子，對包頭中決定流向的域（包的源地址和目的地址）進行一個CRC16運算，然后得到一個16比特的決策碼。假定要到達(dá)目的地址有4個不同的下一跳地址可供選擇，對每個下一跳都在16比特空間中分配一塊區(qū)域。
4、如果要使機會均等，路由器應(yīng)當(dāng)使每塊區(qū)域都具有相同大小，即65536/4或者16k。哪個區(qū)域包含了這個決策碼，就選擇相應(yīng)的下一跳地址。2.分析當(dāng)選擇一個算法來進行下一跳的決策時，我們關(guān)心這樣幾個問題。第一個是復(fù)雜度，也就是算法的運算量。第二個是分裂（disruption，也就是同一個數(shù)據(jù)包流改變其路由）。第三個是均衡。由于算法的均衡特性是與哈希函數(shù)直接有關(guān)的，在我們的分析中將不對這個問題做深入探討。在我們的分析中我們假定各個區(qū)域都具有相同的大小。如果哈希函數(shù)的輸出是平均分布的，那么各條路徑上的流量分布也是平均分布的，這樣這個算法就可以比較好地實現(xiàn)等價多路
5、過··走過···需要的時候記得回來看看····因為容易得到所以得不到大家的珍惜·即使這樣我們也要做下去！·············我下資源網(wǎng)www.woxia.net徑（ECMP）。非定價多徑（non-equal-costmulti-path）可以通過給各個區(qū)域分配不同的大小來實現(xiàn)，但是這不在本文的范圍之內(nèi)。2.1.復(fù)雜度哈希門限算法的復(fù)雜度可以分成以下三個部分：不同下一跳的區(qū)域劃分，決策碼的計算和判斷決策碼在哪一個區(qū)域中。算法中并沒有強制規(guī)定用哪個哈希函數(shù)來計算決策碼。這一步的算法復(fù)雜度完全取決于哈希函數(shù)的復(fù)雜度。我們假定這一步的計算可以在硬件上與其
6、他需要在做出決策之前完成的操作并行完成。由于各個區(qū)域都具有相同的大小，對于區(qū)域邊界的計算是很容易的。每一條邊界都可以用第一個區(qū)域的邊界推出來。后面我們將證明，對于同樣大小的區(qū)域，并不需要存儲它們的邊界值。為了選擇下一跳，我們必須確定決策碼包含在哪個區(qū)域里。因為各個區(qū)域都是同樣大小，我們用一個簡單的除法就可以確定出它屬于哪個區(qū)域。區(qū)域大?。酱a空間大小/下一跳的個數(shù)區(qū)域號＝?jīng)Q策碼/區(qū)域大小因此找到下一跳所需要的時間取決于下一跳在內(nèi)存中的組織方式。最直接的辦法是用一個從0（1）開始計數(shù)的數(shù)組來存放各個下一跳。2.2.分裂（Disruption）類似TCP的協(xié)
7、議在建立連接之后如果路由一直不發(fā)生變化，其性能會比較好。分裂（disruption）就是用來衡量有多少流量因為路由器的某些變化，它們的路由產(chǎn)生了變化。我們將分裂定義為由于路由器原因而發(fā)生路由變化的流量占總流量的比例。Thiscanbecomeimportantifoneormoreofthepathsisflapping.更詳細(xì)的關(guān)于分裂以及它如何對類似TCP的協(xié)議產(chǎn)生影響的信息可參考[1]。類似round-robin的算法（接收到一個包以后，選擇最近最少使用的下一跳）出現(xiàn)分裂的情況是非常頻繁的，而且與路由器的變化無關(guān)。顯然這跟哈希門限算法的情況不一樣
8、。對于一個給定的流來說，只要各個區(qū)域的邊界不變，就會始終選擇相同的下一跳。由于我們規(guī)定了各個區(qū)
