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

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

1 引言

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

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

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

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

2 FCP及其存在的問題

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

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

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

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

3 CF-RIP的設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) For all D∈V do

2) For all d∈V do

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

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

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

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

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

CF-RIP協(xié)議節(jié)點(diǎn)收到一個(gè)數(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ù)分組后附的錯(cuò)誤信息，如果錯(cuò)誤信息非空，那么節(jié)點(diǎn)將對(duì)應(yīng)的錯(cuò)誤節(jié)點(diǎn)采取避讓策略，在進(jìn)行路由選擇時(shí)，不選擇這些錯(cuò)誤節(jié)點(diǎn)作為下一跳，也不選擇以這些錯(cuò)誤節(jié)點(diǎn)作為下一跳的節(jié)點(diǎn)。

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

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

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

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

3.5 錯(cuò)誤處理策略

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

按照文獻(xiàn)[18,19]的一組來自Sprint IP骨干網(wǎng)的統(tǒng)計(jì)數(shù)據(jù)結(jié)果，在所有類型的故障中，只有10%的故障持續(xù)時(shí)間超過 20min，40%的故障持續(xù)時(shí)間介于1～20min之間，50%的故障持續(xù)時(shí)間不到1min。也就是說如果將抑制時(shí)間設(shè)置為大于 60s，那么就可能使得將近50%的網(wǎng)絡(luò)錯(cuò)誤不會(huì)被通告出去。如圖2所示其中T1為節(jié)點(diǎn)發(fā)現(xiàn)鏈路故障的時(shí)間，T2為定時(shí)器重啟的時(shí)間，且 T2-T1=δ，下面討論δ如何取值才能保證不論T1出現(xiàn)在軸上的何處都能保證從錯(cuò)誤被檢測(cè)出來到錯(cuò)誤消息被通告出去的時(shí)間大于 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 錯(cuò)誤抑制時(shí)間的取值

4 CF-RIP的分析

4.1 CF-RIP的性能分析

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

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

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

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

圖3 CF-RIP處理多鏈路錯(cuò)誤

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

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

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

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

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

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

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

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

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

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

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

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

4.2 擴(kuò)展性

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

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

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

5 CF-RIP的仿真實(shí)驗(yàn)

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

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

5.1 故障恢復(fù)時(shí)間

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

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

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

表 2得到是在網(wǎng)絡(luò)選擇不同路徑發(fā)送數(shù)據(jù)分組，當(dāng)路徑上出現(xiàn)鏈路錯(cuò)誤時(shí)使用 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 單鏈路錯(cuò)誤網(wǎng)絡(luò)的丟包率

表3得到是在表2相同的路徑上發(fā)送數(shù)據(jù)分組，設(shè)置路徑上出現(xiàn)2條鏈路故障時(shí)使用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)兩條鏈路故障時(shí)，使用RIP協(xié)議的網(wǎng)絡(luò)有一半的數(shù)據(jù)分組被丟棄，此時(shí)網(wǎng)絡(luò)基本上是不可用的；但是使用CF-RIP協(xié)議的網(wǎng)絡(luò)仍然有平均 99.8756%的包能成功到達(dá)目的節(jié)點(diǎn)。

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

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

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

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

6 結(jié)束語

本文應(yīng)用 FCP協(xié)議給出的一種設(shè)計(jì)無收斂路由協(xié)議的思想，設(shè)計(jì)了一種無收斂的RIP協(xié)議——CF-RIP，該協(xié)議基于錯(cuò)誤信息傳送包的思想，通過為每個(gè)節(jié)點(diǎn)生成每目的備份節(jié)點(diǎn)集和使用錯(cuò)誤處理策略，實(shí)現(xiàn)了RIP協(xié)議的無收斂。CF-RIP協(xié)議不僅可以有效的處理鏈路或節(jié)點(diǎn)的相繼或同時(shí)故障，并且克服了RIP協(xié)議的慢收斂問題，從而增強(qiáng)了路由的穩(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é)報(bào), 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.