CF-RIP：一種無收斂的RIP協議

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

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

1 引言

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

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

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

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

2 FCP及其存在的問題

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

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

2) FCP協議之所以能夠實現無收斂，其中一個關鍵的技術是各個節點擁有一張全網的拓撲圖，各節點的全網拓撲圖保持一致，但是在目前的網絡環境下要實現這個功能存在如下的問題：① 網絡拓撲服務器如何保證其所分發網絡拓撲圖的正確性和實時性；② 如何保證各個節點能夠及時收到最新的網絡拓撲，并且保證全網各節點在更新過程中的粗同步性。如果這些問題不能很好的解決，那么協議的可用性將會大大降低，甚至會導致整個網絡的不可用。

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

3 CF-RIP的設計

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

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

2) 增強路由的穩定性，提高服務的可用性， 實現與RIP協議的無縫結合；

3) 計算得到的路由正確，且不會產生路由環；

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

3.1 RIP協議介紹

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

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

3.2 相關概念定義

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

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

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

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

3.3 備份節點集的生成算法

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

備份節點集的生成算法：

1) For all D∈V do

2) For all d∈V do

假設在一個有n+1節點的網絡中，節點d的備份節點集的生成算法其生成步驟如下。

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

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

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

3.4 CF-RIP轉發處理流程

CF-RIP協議節點收到一個數據分組后，其轉發數據分組流程圖如圖1所示。

圖1 CF-RIP轉發數據分組流程

CF-RIP協議轉發數據分組的詳細步驟如下。

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

step2 判斷主要下一跳是否可達，如果主要下一跳是可達的，那么將數據分組轉發出去；如果主要下一跳不可達，那么進入本地重路由進程。

step3 進入本地重路由進程后首先檢查備用下一跳集合是否為空，如果為空，那么說明該節點沒有可以到達目的網路的下一跳，此時丟棄該數據分組；如果集合非空，那么從對應目的節點的備用下一跳集合中取出第一個備用節點。

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

step5 如果備用節點可達，那么將發生錯誤的節點信息加入到錯誤信息中，并將數據分組轉發出去到可達備用節點。

3.5 錯誤處理策略

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

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

圖2 錯誤抑制時間的取值

4 CF-RIP的分析

4.1 CF-RIP的性能分析

CF-RIP協議具有以下的性質。

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

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

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

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

2) CF-RIP協議不會產生回環路由。

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

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

圖4 3個節點路由環

3) CF-RIP協議可以增強路由的穩定性，提高服務的可用性。

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

在RIP協議中當節點按照更新的網絡拓撲信息重新計算轉發表，在這個期間內將導致某些節點不可達，從而導致大量的數據分組被丟棄，定義這個時期網絡是不可用的。所以減少網絡中節點的路由表的重計算次數可以有效的提高網絡的可用性。但是在RIP協議中如果對錯誤鏈路消息進行抑制，將會導致某些節點不可達，會導致更多的數據分組被丟棄，這個時間網絡仍然定義為是不可用的。由3.5節可知，由設置的δ保證了錯誤信息被抑制時間時大于60s才被通告出去的，其可以使得將近50%的網絡錯誤不會被通告出去。所以如果能夠既能對錯誤消息進行抑制又能保證網絡是可用的就可以大大提高網絡的可用性。由CF-RIP協議的重路由策略可以看到，CF-RIP協議可以對錯誤消息進行一定時間的抑制，而且還能保證網絡是可用的。

綜上所述，CF-RIP協議可以增強路由的穩定性，提高服務的可用性。

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

按照文獻[15]中定義的無收斂路由的定義，所謂的無收斂就是在協議的運行過程中即使網絡中存在觸發更新事件，節點也不去進行觸發更新，通俗的說無收斂路由就是沒有觸發更新的路由，通過3.5節可知，CF-RIP的節點當檢測到網絡中存在觸發更新事件時并不進行觸發更新，所以 CF-RIP協議也是一個無收斂的協議。

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

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

4.2 擴展性

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

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

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

5 CF-RIP的仿真實驗

本節將使用SSFNet[16]仿真工具對CF-RIP協議的各項性能進行仿真實驗驗證。使用的拓撲是BRITE[17]生成的隨機拓撲。使用的接口是10Mbit/s的以太網口，設定鏈路延遲為0.001s，接口輸出延遲，路由器檢測鏈路失效的時間設定為0.02s。圖5是由BRITE生成的20個節點的BA-2拓撲。

圖5 20個節點的BA-2拓撲

5.1 故障恢復時間

表1中給出了在BA-2拓撲中選取的一組源點到目的節點，RIP收斂時間TRIP就是故障的恢復時間，而CF-RIP的路由表切換時間 TCF-RIP為故障的恢復時間，在本實驗中將故障的檢測時間從故障的恢復時間中省略。通過表1可以看到CF-RIP切換路由表的時間遠遠低于 RIP協議的收斂時間，由于RIP協議在收斂期間會導致大量的數據分組被丟棄，造成網絡的可用性降低，所以使用 CF-RIP將會大大提高網絡的可用性。

表1 RIP和CF-RIP的故障恢復時間

5.2 網絡的丟包率

表 2得到是在網絡選擇不同路徑發送數據分組，當路徑上出現鏈路錯誤時使用 RIP協議和CF-RIP協議網絡的丟包率，由表 2可以看出使用RIP協議網絡的丟包率大致為21.334%，而CF-RIP協議的丟包率卻只有大致0.098%，2種協議的丟包率相差217倍。

表2 單鏈路錯誤網絡的丟包率

表3得到是在表2相同的路徑上發送數據分組，設置路徑上出現2條鏈路故障時使用RIP協議和CF-RIP協議網絡的丟包率，由表3可以看出使用RIP協議網絡的丟包率大致為47.172%，而CF-RIP協議的丟包率卻只有大致0.124 4%。可見當一條路徑上出現兩條鏈路故障時，使用RIP協議的網絡有一半的數據分組被丟棄，此時網絡基本上是不可用的；但是使用CF-RIP協議的網絡仍然有平均 99.8756%的包能成功到達目的節點。

表3 雙鏈路并發錯誤網絡的丟包率

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

5.3 節點轉發表

由于 CF-RIP協議為每個節點都備份多個下一跳，所以會導致網絡節點轉發表增大，轉發表的大小為本地的接口數目乘以所有節點接口數目，由于仿真實驗所用的網絡拓撲節點的平均連接度為4.2，所以使用 CF-RIP協議的網絡中節點的轉發表比使用RIP協議的網絡中節點的轉發表平均增大4.2倍。RIB平均需要的存儲空間為1.696kB。

6 結束語

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

[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] 于濤, 陳山枝, 李昕等. 基于偏轉路由的網絡故障處理技術[J]. 北京郵電大學學報, 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.