CF-RIP：一種無收斂的RIP協(xié)議

王濱，張建輝，郭云飛，蘭巨龍

（1. 解放軍信息工程大學(xué) 電子技術(shù)學(xué)院，河南 鄭州 450004；2. 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002）

1 引言

傳統(tǒng)的路由算法（包括基于鏈路狀態(tài)和距離向量的算法）中某些特定事件的信息，比如鏈路失效信息等，需要向全網(wǎng)傳播，以達(dá)到全網(wǎng)信息一致，保證協(xié)議正常工作。這個信息的傳播過程稱為收斂過程。在收斂過程中，由于全網(wǎng)各個節(jié)點的信息不一致，可能導(dǎo)致產(chǎn)生路由環(huán)路、錯誤路由等問題，而受到網(wǎng)絡(luò)規(guī)模、節(jié)點處理速度等因素的影響，收斂過程通常要持續(xù)一段時間。在一個規(guī)模較大的網(wǎng)絡(luò)中（幾千節(jié)點），收斂過程的持續(xù)時間可達(dá)幾十秒。因此，如何加速收斂過程，減少收斂時間，是路由研究中的一個熱點問題。

為了解決協(xié)議的收斂問題通常采用以下3類方法。1) 重新設(shè)計獨立于現(xiàn)有路由協(xié)議的快速收斂路由協(xié)議[1,2]，這種途徑涉及到路由協(xié)議的重新設(shè)計，在目前的情況下很難被部署和使用。2) 修改現(xiàn)有路由協(xié)議的參數(shù)，減少收斂時間[3,4]，文獻(xiàn)[3]中提出的OSPF通過減小Hello間隔，以及文獻(xiàn)[4]中提出的BGP通過減小最小路由通告間隔MRAI可以加快網(wǎng)絡(luò)的收斂。但是由于 Internet中大多數(shù)的故障都是短時存在的[5]，太過頻繁地觸發(fā)重收斂可能引發(fā)路由抖動，增加網(wǎng)絡(luò)的不穩(wěn)定性[6]。3) 為了保證收斂過程中網(wǎng)絡(luò)的可用性使用預(yù)計算備份路由策略[1,7～14]，這種途徑供的備用路由只能在一定的程度上保證其正確性，保護(hù)覆蓋的范圍有限，只能夠抵抗網(wǎng)絡(luò)中部分節(jié)點和鏈路的單故障；在各種拓?fù)錀l件下采用的不同方法，復(fù)雜度相對比較高；另外這種方法是基于保護(hù)路徑，靈活性較差。

為了實現(xiàn)路由協(xié)議的無收斂K.Lakshminarayanan等人提出了一種新型的無收斂路由協(xié)議[15]，該協(xié)議使用錯誤信息傳送包(FCP, failure-carrying packet)的方法。檢測到故障鏈路的節(jié)點將生成故障信息，對于鏈路故障發(fā)生后的第一個數(shù)據(jù)分組，將該鏈路故障信息放入其中，該數(shù)據(jù)分組即為FCP。收到FCP的每一個下游節(jié)點，重新計算路由表，并繼續(xù)轉(zhuǎn)發(fā)該FCP直至目的節(jié)點。該方法具有多鏈路故障的應(yīng)對能力，并且從另一個角度實現(xiàn)了協(xié)議無收斂，避免了收斂過程中伴隨的路由不可達(dá)和路由環(huán)路等問題。

本文研究了無收斂路由機制FCP存在的問題，并為了解決RIP協(xié)議的收斂速度慢的問題，設(shè)計了一種基于 RIP協(xié)議的無收斂路由機制——CF-RIP(convergence-free RIP )，并從理論和仿真實驗2方面分析了該機制對網(wǎng)絡(luò)可用性和穩(wěn)定性的影響，以及對網(wǎng)絡(luò)故障的應(yīng)對能力。

2 FCP及其存在的問題

文獻(xiàn)[15]中提出無收斂路由協(xié)議(以下簡稱 FCP協(xié)議)，其基本思路是各個節(jié)點擁有一張全網(wǎng)的拓?fù)鋱D，各節(jié)點的拓?fù)鋱D保持一致。其通過使用攜帶途徑鏈路的失效路由信息的方法，使得途徑的節(jié)點獲知路由失效信息，從而避免將路由失效信息廣播到整個網(wǎng)絡(luò)，浪費網(wǎng)絡(luò)的帶寬。該協(xié)議存在以下的問題。

1) FCP協(xié)議是完全獨立于現(xiàn)有的域內(nèi)路由協(xié)議，其設(shè)計思路屬于解決收斂過程帶來的問題的第一種途徑，顯然其在目前的網(wǎng)絡(luò)情況下這種途徑只存在理論上的研究價值。

2) FCP協(xié)議之所以能夠?qū)崿F(xiàn)無收斂，其中一個關(guān)鍵的技術(shù)是各個節(jié)點擁有一張全網(wǎng)的拓?fù)鋱D，各節(jié)點的全網(wǎng)拓?fù)鋱D保持一致，但是在目前的網(wǎng)絡(luò)環(huán)境下要實現(xiàn)這個功能存在如下的問題：① 網(wǎng)絡(luò)拓?fù)浞?wù)器如何保證其所分發(fā)網(wǎng)絡(luò)拓?fù)鋱D的正確性和實時性；② 如何保證各個節(jié)點能夠及時收到最新的網(wǎng)絡(luò)拓?fù)洌⑶冶ＷC全網(wǎng)各節(jié)點在更新過程中的粗同步性。如果這些問題不能很好的解決，那么協(xié)議的可用性將會大大降低，甚至?xí)?dǎo)致整個網(wǎng)絡(luò)的不可用。

由于 FCP協(xié)議給出了一種很好的解決路由協(xié)議收斂問題的思路，所以如何克服其存在的弊端，并將這種思想應(yīng)用于目前已有的距離矢量類路由協(xié)議是本文研究的主要內(nèi)容。

3 CF-RIP的設(shè)計

CF-RIP協(xié)議是通過使用FCP的方法和為每個節(jié)點備份多個到達(dá)目的節(jié)點的下一跳的方法，實現(xiàn)對故障鏈路的顯式標(biāo)識與定向通告，從而實現(xiàn)無收斂路由。CF-RIP協(xié)議具有以下的特點：

1) 實現(xiàn) RIP協(xié)議的無收斂路由，有效地解決RIP協(xié)議的慢收斂問題；

2) 增強路由的穩(wěn)定性，提高服務(wù)的可用性， 實現(xiàn)與RIP協(xié)議的無縫結(jié)合；

3) 計算得到的路由正確，且不會產(chǎn)生路由環(huán)；

4) 有效處理多鏈路或節(jié)點的相繼或同時故障。

3.1 RIP協(xié)議介紹

路由信息協(xié)議(RIP, routing information protocol)是因特網(wǎng)工程任務(wù)組（IETF）的內(nèi)部網(wǎng)關(guān)協(xié)議工作組為IP網(wǎng)絡(luò)專門設(shè)計的路由協(xié)議，是一種基于距離矢量算法的內(nèi)部網(wǎng)關(guān)動態(tài)路由協(xié)議，該協(xié)議易于配置和管理，所以應(yīng)用較為廣泛。每個運行RIP的路由器都維護(hù)著一張RIP路由表，該路由表的內(nèi)容為＜目的，下一跳，度量，標(biāo)志，年齡＞。下一跳（nexthop）表示下一站數(shù)據(jù)分組要到達(dá)的地址；度量（metric）代表把數(shù)據(jù)分組從本路由器送達(dá)目的站所需的花費（cost），也就是跳數(shù)。RIP路由器周期性地以多播形式向鄰居發(fā)送自己的路由表拷貝，即＜目的，度量＞組，每個接收到該消息的路由器修改消息中路由的度量，在每條路由的度量上加上接收該路由消息接口的花費。然后，依據(jù)度量的大小來判斷路由的好壞，把度量值最小的一條路由放入路由表。

如今的RIP已經(jīng)從RIPv1、RIPv2，發(fā)展到今天有變革意義的基于IPv6的RIPng。本文提到的RIP協(xié)議如無特殊說明，都是指RIPv2協(xié)議。

3.2 相關(guān)概念定義

CF-RIP協(xié)議需要引入以下幾個概念。

定義 1 路由信息庫(RIB, routing information base)，每一個節(jié)點有一個RIB，保存最近一次從各個鄰居節(jié)點收到的路由信息。路由選擇程序?qū)腞IB中選擇最佳路由，然后保存進(jìn)路由表。RIB中的保存格式為＜dest_id, neighbor, next hop, cost＞，這里的dest_id就是目的節(jié)點的地址；neighbor表示發(fā)送update創(chuàng)建了這個條目的鄰居（也就是這個路由的下一跳）；next hop表示鄰居節(jié)點到達(dá)目的節(jié)點的下一跳；cost是鄰居節(jié)點到達(dá)目的節(jié)點的距離。

定義2 主要的下一跳，CF-RIP協(xié)議將為每個節(jié)點備份多個下一跳，而按照Bellman-Ford算法計算得到下一跳定義為主要下一跳。

定義 3 備用下一跳集，就是除了可以到達(dá)某個目的節(jié)點的主要下一跳之外的其他也可以達(dá)到該目的節(jié)點的可用下一跳組成的集合。

3.3 備份節(jié)點集的生成算法

當(dāng)某個直連鏈路發(fā)生擁塞或故障，將該鏈路從有效鏈路列表中刪除，并重新計算路由，這個過程稱為重計算路由。預(yù)計算路由是指假設(shè)一個主要下一跳節(jié)點出現(xiàn)故障或擁塞時為了將數(shù)據(jù)送達(dá)對應(yīng)的目的地，提前為該節(jié)點計算備用的下一跳，并將結(jié)果保存在節(jié)點的路由表中，當(dāng)某直連鏈路擁塞或發(fā)生錯誤時，立即啟用相應(yīng)的備用鏈路，使計算時延減少為零。CF-RIP協(xié)議預(yù)計算備份點集的生成是該協(xié)議中一個重要的環(huán)節(jié)，算法使用的符號如下：V表示所有的節(jié)點集合；Ni表示節(jié)點i的所有的鄰居節(jié)點集合；表示節(jié)點i到節(jié)點D的主要下一跳集合；表示節(jié)點i到節(jié)點D的備份下一跳集合；表示節(jié)點i到節(jié)點D的代價；表示節(jié)點i的RIB數(shù)據(jù)庫中可到達(dá)節(jié)點D的路由信息；Bellman-Ford(·)表 示 Bellman-Ford 算 法 ；Sort↑(·)表示一個按升序排列的算法。

備份節(jié)點集的生成算法：

1) For all D∈V do

2) For all d∈V do

假設(shè)在一個有n+1節(jié)點的網(wǎng)絡(luò)中，節(jié)點d的備份節(jié)點集的生成算法其生成步驟如下。

1) 當(dāng)節(jié)點d收到其鄰居節(jié)點發(fā)送過來的路由更新信息時，首先將鄰居發(fā)送過來的路由信息＜dest_id, next hop, cost1＞修改為＜dest_id, neighbor,next hop, cost2＞存入RIB，其中的neighbor為節(jié)點發(fā)送該條路由信息的鄰居，cos t2=cos t1+1，從而得到，其中 Di∈V/ d(i = 1 ,… ,n)；

2) 按照RIB中的信息，使用Bellman-Ford算法生成節(jié)點的主要下一跳集合，也就是RIP協(xié)議生成的實際轉(zhuǎn)發(fā)表Di∈ V / d( i =1,…,n )。

3) 將所有鄰居節(jié)點(不包括主要下一跳)Nd/，使用升序排序算法 S ort↑(·)，按度量值進(jìn)行排序后將其記入，這就組成了到達(dá)目的節(jié)點D的備份節(jié)點集。

3.4 CF-RIP轉(zhuǎn)發(fā)處理流程

CF-RIP協(xié)議節(jié)點收到一個數(shù)據(jù)分組后，其轉(zhuǎn)發(fā)數(shù)據(jù)分組流程圖如圖1所示。

圖1 CF-RIP轉(zhuǎn)發(fā)數(shù)據(jù)分組流程

CF-RIP協(xié)議轉(zhuǎn)發(fā)數(shù)據(jù)分組的詳細(xì)步驟如下。

step1 查看數(shù)據(jù)分組后附的錯誤信息，如果錯誤信息非空，那么節(jié)點將對應(yīng)的錯誤節(jié)點采取避讓策略，在進(jìn)行路由選擇時，不選擇這些錯誤節(jié)點作為下一跳，也不選擇以這些錯誤節(jié)點作為下一跳的節(jié)點。

step2 判斷主要下一跳是否可達(dá)，如果主要下一跳是可達(dá)的，那么將數(shù)據(jù)分組轉(zhuǎn)發(fā)出去；如果主要下一跳不可達(dá)，那么進(jìn)入本地重路由進(jìn)程。

step3 進(jìn)入本地重路由進(jìn)程后首先檢查備用下一跳集合是否為空，如果為空，那么說明該節(jié)點沒有可以到達(dá)目的網(wǎng)路的下一跳，此時丟棄該數(shù)據(jù)分組；如果集合非空，那么從對應(yīng)目的節(jié)點的備用下一跳集合中取出第一個備用節(jié)點。

step4 選出備用節(jié)點后，檢查其是否可達(dá)，如果不可達(dá)，那么從備份下一跳集合中刪除該節(jié)點，并返回step3。

step5 如果備用節(jié)點可達(dá)，那么將發(fā)生錯誤的節(jié)點信息加入到錯誤信息中，并將數(shù)據(jù)分組轉(zhuǎn)發(fā)出去到可達(dá)備用節(jié)點。

3.5 錯誤處理策略

RIP協(xié)議中只要一個路由器發(fā)現(xiàn)其鄰居節(jié)點的鏈路狀態(tài)發(fā)生改變，該路由器就要向其鄰居節(jié)點發(fā)送更新的路由信息。但是根據(jù)文獻(xiàn)[19,20]對網(wǎng)路故障的研究數(shù)據(jù)可以得到：在固定網(wǎng)絡(luò)中，絕大部分故障持續(xù)時間短、影響范圍小。所以為了節(jié)約網(wǎng)絡(luò)帶寬和減少網(wǎng)絡(luò)的負(fù)載，CF-RIP協(xié)議為了實現(xiàn)無收斂路由將采用如下的辦法來處理這些錯誤消息：當(dāng)條鏈路發(fā)現(xiàn)故障時，其并不立即向其鄰接的節(jié)點發(fā)送Update消息，而是啟動一個定時器抑制錯誤信息一段時間δ，在此期間節(jié)點將不修改任何關(guān)于故障鏈路的路由信息，如果定時器在重啟之前沒有收到發(fā)生錯誤鏈路的Update消息，此時修改自己的路由表，等待下一個路由更新周期到來將路由表發(fā)送給其鄰居；相反如果在定時器重啟之前收到了鄰居的Update消息，那么就不修改路由表中對應(yīng)的路由表項將路由表發(fā)送給其鄰居。下面討論定時器的時間δ應(yīng)該如何設(shè)置。

按照文獻(xiàn)[18,19]的一組來自Sprint IP骨干網(wǎng)的統(tǒng)計數(shù)據(jù)結(jié)果，在所有類型的故障中，只有10%的故障持續(xù)時間超過 20min，40%的故障持續(xù)時間介于1～20min之間，50%的故障持續(xù)時間不到1min。也就是說如果將抑制時間設(shè)置為大于 60s，那么就可能使得將近50%的網(wǎng)絡(luò)錯誤不會被通告出去。如圖2所示其中T1為節(jié)點發(fā)現(xiàn)鏈路故障的時間，T2為定時器重啟的時間，且 T2-T1=δ，下面討論δ如何取值才能保證不論T1出現(xiàn)在軸上的何處都能保證從錯誤被檢測出來到錯誤消息被通告出去的時間大于 60s。為了討論的方便假設(shè) T1∈ [ 0,30)，T2∈ [ 30n, 30(n + 1 ))，而 3 0(n + 1 )- T1≥60，所以只要1≤n就能滿足不等式，這就意味著T2∈ [ 60,+ ∞)，而要保證T2一定出現(xiàn)在[60,+∞)之間那么δ≥60，所以取δ＝60s。

圖2 錯誤抑制時間的取值

4 CF-RIP的分析

4.1 CF-RIP的性能分析

CF-RIP協(xié)議具有以下的性質(zhì)。

1) CF-RIP協(xié)議可以有效處理多鏈路或節(jié)點的相繼或同時故障。

傳統(tǒng)的多徑路由為節(jié)點備份幾條路徑，當(dāng)這些備份路徑上均出現(xiàn)故障的時候，對應(yīng)的多徑路由機制就沒有辦法實現(xiàn)快速的重路由。相反，由于CF-RIP協(xié)議是為每個節(jié)點備份到達(dá)目的地的多個下一跳，所以只要是網(wǎng)絡(luò)中有到達(dá)目的節(jié)點的路徑，那么不論網(wǎng)絡(luò)中有多少的鏈路或節(jié)點相繼或同時出現(xiàn)故障，該數(shù)據(jù)分組均可送達(dá)。所以說采用CF-RIP協(xié)議可以有效處理多鏈路/節(jié)點的相繼或同時故障。

下面將以圖3所示的網(wǎng)絡(luò)拓?fù)渲袨槔?，對比彈性路由層IP快速重路由方法[16]來說明CF-RIP協(xié)議可以有效處理多鏈路或節(jié)點的相繼或同時故障。首先按照彈性路由層技術(shù)將為源節(jié)點S和目的節(jié)點D 之間備份 3條路徑(S , 1,2,3,D ), (S , 4,5,6,D),(S , 7,8,9,D)，假設(shè)常用路徑為(S , 1,2,3,D )，但是源節(jié)點S向目的節(jié)點D發(fā)送數(shù)據(jù)分組時，當(dāng)數(shù)據(jù)分組到達(dá)節(jié)點1時發(fā)現(xiàn)鏈路故障，通告給源節(jié)點；源節(jié)點將改用路徑(S , 4,5,6,D)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，但是此時當(dāng)數(shù)據(jù)到達(dá)節(jié)點5時，發(fā)現(xiàn)鏈路故障，通告給源節(jié)點；源節(jié)點將改用路徑(S , 7,8,9,D)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，但是此時當(dāng)數(shù)據(jù)到達(dá)節(jié)點7時，發(fā)現(xiàn)鏈路故障，通告源節(jié)點，源節(jié)點認(rèn)為節(jié)點D不可達(dá)。但是如果使用CF-RIP協(xié)議當(dāng)數(shù)據(jù)到達(dá)節(jié)點1后發(fā)現(xiàn)節(jié)點2錯誤，將會把數(shù)據(jù)發(fā)送到備用下一跳節(jié)點5，節(jié)點5發(fā)現(xiàn)其主要下一跳不可達(dá)時，會自動將數(shù)據(jù)發(fā)送給其備用下一跳節(jié)點3，節(jié)點3將數(shù)據(jù)轉(zhuǎn)發(fā)給目的節(jié)點D，從而CF-RIP實現(xiàn)了應(yīng)對網(wǎng)絡(luò)中多鏈路或節(jié)點的相繼或同時故障。

圖3 CF-RIP處理多鏈路錯誤

2) CF-RIP協(xié)議不會產(chǎn)生回環(huán)路由。

為了說明CF-RIP協(xié)議不會產(chǎn)生回環(huán)路由，使用反證法來證明。假設(shè)一個數(shù)據(jù)分組p在網(wǎng)絡(luò)中沿著一個閉合的環(huán)進(jìn)行路由，其起始節(jié)點為v，路由的閉合環(huán)路徑為v=v0→v1→v2→…→vn→v0=v，其中節(jié)點{v0, v1, v2,…,vn}各不相同。如果網(wǎng)絡(luò)中沒有鏈路故障，RIP協(xié)議保證了不會出現(xiàn)這種上述的情況，所以此時節(jié)點v0到達(dá)目的節(jié)點的主要下一跳vx不可達(dá)，而選用了備用下一跳v1，而對于節(jié)點vn來說v0一定是其主要或備用到達(dá)目的節(jié)點的下一跳，但是由于vx是v0到達(dá)目的節(jié)點的主要下一跳，所以v0在進(jìn)行初始路由通告時一定通告的是〈D, vx,cost〉，而vn的RIB中記錄為〈D, v0, vx,cost +1〉，但是由于當(dāng)v0選用了備用下一跳v1進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)時一定會生成節(jié)點vx的錯誤消息附加在數(shù)據(jù)分組后，而節(jié)點vn收到數(shù)據(jù)分組后會首先檢查不可達(dá)節(jié)點，并在接下來的選路過程中回避節(jié)點vx，所以節(jié)點vn一定不會選擇v0作為其下一跳，故假設(shè)不成立。下面以2個節(jié)點之間的來回轉(zhuǎn)發(fā)為例說明。

假設(shè)數(shù)據(jù)在節(jié)點v0、v2、v1之間形成路由環(huán)。這種情況發(fā)生可能如圖4所示，按照常規(guī)路由RIP協(xié)議保證了不會出現(xiàn)這種2個節(jié)點之間的來回轉(zhuǎn)發(fā)，所以網(wǎng)絡(luò)中一定出現(xiàn)了故障，導(dǎo)致了v0到達(dá)目的節(jié)點的主要下一跳vx不可達(dá)，所以節(jié)點v0在備份路集中選出備用下一跳節(jié)點v2進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)之前v0需要將不可達(dá)節(jié)點的信息附在轉(zhuǎn)發(fā)數(shù)據(jù)分組后，v2收到數(shù)據(jù)報后將數(shù)據(jù)分組轉(zhuǎn)發(fā)給其下一跳v1；當(dāng)節(jié)點v1收到數(shù)據(jù)分組后，會首先檢查數(shù)據(jù)分組附帶的錯誤信息，此時發(fā)現(xiàn)節(jié)點vx不可達(dá)，那么就會回避所有經(jīng)過節(jié)點vx的下一跳節(jié)點，此時其將不使用RIB中的記錄〈D, v1, v2,cost 3〉這個條目，所以此時節(jié)點v1不會在將數(shù)據(jù)轉(zhuǎn)發(fā)給v0，所以這時會發(fā)生路由環(huán)的問題。

圖4 3個節(jié)點路由環(huán)

3) CF-RIP協(xié)議可以增強路由的穩(wěn)定性，提高服務(wù)的可用性。

CF-RIP協(xié)議在處理錯誤節(jié)點消息時，并不是馬上對發(fā)現(xiàn)的錯誤進(jìn)行通告，而是對錯誤消息進(jìn)行一定時間的抑制，這里抑制時間記為δ，按照文獻(xiàn)[9]中給出的關(guān)于網(wǎng)絡(luò)穩(wěn)定性的評估公式為：，m表示網(wǎng)絡(luò)的鏈路條數(shù)，=P{ Sl( t )=0}，Sl( t)=0表示網(wǎng)絡(luò)在時間t處在不穩(wěn)定的狀態(tài)。由此可見網(wǎng)絡(luò)中的不穩(wěn)定狀態(tài)時間越少，網(wǎng)絡(luò)的穩(wěn)定性越高。

在RIP協(xié)議中當(dāng)節(jié)點按照更新的網(wǎng)絡(luò)拓?fù)湫畔⒅匦掠嬎戕D(zhuǎn)發(fā)表，在這個期間內(nèi)將導(dǎo)致某些節(jié)點不可達(dá)，從而導(dǎo)致大量的數(shù)據(jù)分組被丟棄，定義這個時期網(wǎng)絡(luò)是不可用的。所以減少網(wǎng)絡(luò)中節(jié)點的路由表的重計算次數(shù)可以有效的提高網(wǎng)絡(luò)的可用性。但是在RIP協(xié)議中如果對錯誤鏈路消息進(jìn)行抑制，將會導(dǎo)致某些節(jié)點不可達(dá)，會導(dǎo)致更多的數(shù)據(jù)分組被丟棄，這個時間網(wǎng)絡(luò)仍然定義為是不可用的。由3.5節(jié)可知，由設(shè)置的δ保證了錯誤信息被抑制時間時大于60s才被通告出去的，其可以使得將近50%的網(wǎng)絡(luò)錯誤不會被通告出去。所以如果能夠既能對錯誤消息進(jìn)行抑制又能保證網(wǎng)絡(luò)是可用的就可以大大提高網(wǎng)絡(luò)的可用性。由CF-RIP協(xié)議的重路由策略可以看到，CF-RIP協(xié)議可以對錯誤消息進(jìn)行一定時間的抑制，而且還能保證網(wǎng)絡(luò)是可用的。

綜上所述，CF-RIP協(xié)議可以增強路由的穩(wěn)定性，提高服務(wù)的可用性。

4) 實現(xiàn)無收斂路由，解決了RIP協(xié)議的慢收斂問題。

按照文獻(xiàn)[15]中定義的無收斂路由的定義，所謂的無收斂就是在協(xié)議的運行過程中即使網(wǎng)絡(luò)中存在觸發(fā)更新事件，節(jié)點也不去進(jìn)行觸發(fā)更新，通俗的說無收斂路由就是沒有觸發(fā)更新的路由，通過3.5節(jié)可知，CF-RIP的節(jié)點當(dāng)檢測到網(wǎng)絡(luò)中存在觸發(fā)更新事件時并不進(jìn)行觸發(fā)更新，所以 CF-RIP協(xié)議也是一個無收斂的協(xié)議。

CF-RIP協(xié)議可以較好的解決 RIP協(xié)議的一個嚴(yán)重的缺陷，即“慢收斂”（slow convergence）問題，又叫“計數(shù)到無窮”（count to infinity）問題。而所謂的慢收斂問題就是如果網(wǎng)絡(luò)中出現(xiàn)環(huán)路，直到路徑長度達(dá)到16，路徑環(huán)路才會被解除。例如當(dāng)前節(jié)點到達(dá)某個目的地的距離為 3，那么要經(jīng)過7個來回（至少30×7=210s），路徑回路才能被解除。

CF-RIP協(xié)議采用的錯誤處理策略是當(dāng)節(jié)點R1發(fā)現(xiàn)節(jié)點R2不可達(dá)時，此時啟動一個定時器，在定時器規(guī)定時間內(nèi)（如 60s），R1采取只接受鄰居節(jié)點的路由信息但是忽略這些路由信息中所有關(guān)于R2的路由信息，如果定時器在重啟之前沒有收到R2的消息，此時修改自己的路由表，并將路由表發(fā)送給其鄰居；相反如果在定時器重啟之前收到了R2消息，那么就不修改路由表中對應(yīng)的路由表項將路由表發(fā)送給其鄰居。從而可以有效地解決慢收斂問題。

4.2 擴展性

CF-RIP協(xié)議是基于RIP協(xié)議設(shè)計的，RIP協(xié)議所能實現(xiàn)的功能 CF-RIP協(xié)議全部可以實現(xiàn)，并且除了刪除了 RIP協(xié)議的觸發(fā)更新機制外，沒有對RIP協(xié)議做任何改變。而CF-RIP協(xié)議通過增加RIB，使用備份節(jié)點生成算法來實現(xiàn)有效處理多鏈路或節(jié)點的相繼或同時故障、無環(huán)路由；并且在通過為RIP協(xié)議增加錯誤處理策略，解決了RIP協(xié)議固有的慢收斂問題。

由于 CF-RIP協(xié)議為每個節(jié)點都備份多個下一跳，所以會導(dǎo)致網(wǎng)絡(luò)節(jié)點轉(zhuǎn)發(fā)表增大，轉(zhuǎn)發(fā)表的大小為本地的接口數(shù)目乘以所有網(wǎng)絡(luò)節(jié)點接口數(shù)目；除此之外RIB的增加也會導(dǎo)致路由器存儲空間的增加，由于RIB存儲路由信息為其鄰居節(jié)點每次路由更新所發(fā)送過來的路由表，通過計算可以得到RIB存儲路由信息平均所需要的存儲空間為(20βN + 4β)byte，其中N為網(wǎng)絡(luò)中的節(jié)點數(shù)，β為節(jié)點的鄰居個數(shù)。當(dāng)網(wǎng)絡(luò)中某個節(jié)點有5個鄰居，網(wǎng)絡(luò)規(guī)模達(dá)到2 000時，RIB所需的存儲空間僅為20kB。

CF-RIP協(xié)議對原始的 RIP協(xié)議幾乎沒有作任何修改，增加的額外代價很小，由此可見 CF-RIP協(xié)議可以與RIP協(xié)議進(jìn)行無縫的結(jié)合，因此CF-RIP協(xié)議具有良好的擴展性。

5 CF-RIP的仿真實驗

本節(jié)將使用SSFNet[16]仿真工具對CF-RIP協(xié)議的各項性能進(jìn)行仿真實驗驗證。使用的拓?fù)涫荁RITE[17]生成的隨機拓?fù)洹Ｊ褂玫慕涌谑?0Mbit/s的以太網(wǎng)口，設(shè)定鏈路延遲為0.001s，接口輸出延遲，路由器檢測鏈路失效的時間設(shè)定為0.02s。圖5是由BRITE生成的20個節(jié)點的BA-2拓?fù)洹?/p>

圖5 20個節(jié)點的BA-2拓?fù)?/p>

5.1 故障恢復(fù)時間

表1中給出了在BA-2拓?fù)渲羞x取的一組源點到目的節(jié)點，RIP收斂時間TRIP就是故障的恢復(fù)時間，而CF-RIP的路由表切換時間 TCF-RIP為故障的恢復(fù)時間，在本實驗中將故障的檢測時間從故障的恢復(fù)時間中省略。通過表1可以看到CF-RIP切換路由表的時間遠(yuǎn)遠(yuǎn)低于 RIP協(xié)議的收斂時間，由于RIP協(xié)議在收斂期間會導(dǎo)致大量的數(shù)據(jù)分組被丟棄，造成網(wǎng)絡(luò)的可用性降低，所以使用 CF-RIP將會大大提高網(wǎng)絡(luò)的可用性。

表1 RIP和CF-RIP的故障恢復(fù)時間

5.2 網(wǎng)絡(luò)的丟包率

表 2得到是在網(wǎng)絡(luò)選擇不同路徑發(fā)送數(shù)據(jù)分組，當(dāng)路徑上出現(xiàn)鏈路錯誤時使用 RIP協(xié)議和CF-RIP協(xié)議網(wǎng)絡(luò)的丟包率，由表 2可以看出使用RIP協(xié)議網(wǎng)絡(luò)的丟包率大致為21.334%，而CF-RIP協(xié)議的丟包率卻只有大致0.098%，2種協(xié)議的丟包率相差217倍。

表2 單鏈路錯誤網(wǎng)絡(luò)的丟包率

表3得到是在表2相同的路徑上發(fā)送數(shù)據(jù)分組，設(shè)置路徑上出現(xiàn)2條鏈路故障時使用RIP協(xié)議和CF-RIP協(xié)議網(wǎng)絡(luò)的丟包率，由表3可以看出使用RIP協(xié)議網(wǎng)絡(luò)的丟包率大致為47.172%，而CF-RIP協(xié)議的丟包率卻只有大致0.124 4%?？梢姰?dāng)一條路徑上出現(xiàn)兩條鏈路故障時，使用RIP協(xié)議的網(wǎng)絡(luò)有一半的數(shù)據(jù)分組被丟棄，此時網(wǎng)絡(luò)基本上是不可用的；但是使用CF-RIP協(xié)議的網(wǎng)絡(luò)仍然有平均 99.8756%的包能成功到達(dá)目的節(jié)點。

表3 雙鏈路并發(fā)錯誤網(wǎng)絡(luò)的丟包率

通過表2、表3可以清楚地看到CF-RIP協(xié)議可以有效地處理鏈路或節(jié)點的相繼或同時故障。

5.3 節(jié)點轉(zhuǎn)發(fā)表

由于 CF-RIP協(xié)議為每個節(jié)點都備份多個下一跳，所以會導(dǎo)致網(wǎng)絡(luò)節(jié)點轉(zhuǎn)發(fā)表增大，轉(zhuǎn)發(fā)表的大小為本地的接口數(shù)目乘以所有節(jié)點接口數(shù)目，由于仿真實驗所用的網(wǎng)絡(luò)拓?fù)涔?jié)點的平均連接度為4.2，所以使用 CF-RIP協(xié)議的網(wǎng)絡(luò)中節(jié)點的轉(zhuǎn)發(fā)表比使用RIP協(xié)議的網(wǎng)絡(luò)中節(jié)點的轉(zhuǎn)發(fā)表平均增大4.2倍。RIB平均需要的存儲空間為1.696kB。

6 結(jié)束語

本文應(yīng)用 FCP協(xié)議給出的一種設(shè)計無收斂路由協(xié)議的思想，設(shè)計了一種無收斂的RIP協(xié)議——CF-RIP，該協(xié)議基于錯誤信息傳送包的思想，通過為每個節(jié)點生成每目的備份節(jié)點集和使用錯誤處理策略，實現(xiàn)了RIP協(xié)議的無收斂。CF-RIP協(xié)議不僅可以有效的處理鏈路或節(jié)點的相繼或同時故障，并且克服了RIP協(xié)議的慢收斂問題，從而增強了路由的穩(wěn)定性，提高服務(wù)的可用性。

[1] FRANCOIS P, FILSFILS C, EVANS J, et al. Achieving sub-second IGP convergence in large IP networks[J]. ACM SIGCOMM Compute Commune Rev, 2005, 35(2): 35-44.

[2] ATLAS A, et al. Basic specification for IP fast-reroute: loop-free alternate[EB/OL]. http://tools.ietf.org/id/draft-ietf-rtgwg-ipfrr-spec- base-12.txt, 2006.

[3] GOYAL M, RAMAKRISHNAN K K, FENGWUCHI W C. Achieving faster failure detection in OSPF networks[EB/OL]. http://web.cecs.pdx.edu/～wuchi/ Papers/Goya.icc03.pdf, 2008.

[4] GRIFFIN T G, PREMORE B J. An experimental analysis of BGP convergence time[A]. Proceeding of ICNP 2001[C]. California, 2001.

[5] LABOVITZ C, AHUJA A, BOSE A, et al. Delayed internet routing convergence[J]. IEEE/ACM Transactions on Networking, 2001, 9(3):293-306.

[6] BASU A, RIECKE J G. Stability issues in OSPF routing[A]. Proceedings of SIGCOMM 2001[C]. San Diego, 2001.

[7] NELAKUDITI S, LEE S, YU Y, et al. Fast local rerouting for handling transient link failures[J]. IEEE/ACM Transaction on Networking,2007, 15(2): 359-372.

[8] SHAND M, BRYANT S. IP fast reroute framework[EB/OL]. http://tools.ietf.org/id/draft-ietf-rtgwg-ipfrr-framework-11.txt, 2008.

[9] LEE S, YU Y Z, NELAKUDITI S, et al. Proactive vs reactive approaches to failure resilient routing[A]. Proc INFOCOM 2004[C].Hong Kong, China, 2004.

[10] NELAKUDITI S, LEE S, YU Y, et al. Fast local rerouting for handling transient link failures, IEEE/ACM Trans[J]. Networking, 2007,15(2):359-372.

[11] 于濤, 陳山枝, 李昕等. 基于偏轉(zhuǎn)路由的網(wǎng)絡(luò)故障處理技術(shù)[J]. 北京郵電大學(xué)學(xué)報, 2007,29(6):1-4.YU T, CHEN S Z, LI X, et al. Research on network failure handling technology based on deflection routing[J]. Journal of Beijing University of Posts and Telecommunications, 2007,29(6):1-4.

[12] MENTH M, MARTIN R. Network Resilience Through Multi- Topology Routing[R]. University of Wuerzburg, Institute of Computer Science, 2004.

[13] KVALBEIN A, et al. Fast IP network recovery using multiple routing configurations[A]. Proceedings of INFOCOM 2006[C]. Spain, 2006.

[14] HANSEN A, et al. Resilient routing layers for recovery in packet networks[A]. The International Conference on Dependable Systems and Networks (DSN)[C]. 2005.

[15] LAKSHMINARAYANAN K. Achieving convergence-free routing using failure carrying packets[J]. SIGCOMM Computer Communication Review, 2007, 37(4): 241-252.

[16] SSFnet (The Network Simulator)[EB/OL]. http://www.ssfnet.org.2010

[17] BRITE[EB/OL]. http://www.cs.bu.edu/brite/.2010

[18] MARKOPOULOU A, IANNACCONE G, BHATTACHARYYA S, et al. Characterization of failures in an IP backbone[A]. IEEE Infocom 2004[C]. Hong Kong,China, 2004.

[19] IANNACCONE G, CHUAH C, MORTIER R, et al. Analysis of link failures in an IP backbone[A]. Proc of ACM Sigcomm Internet Measurement Workshop[C]. 2002.