一種逐跳方式的域內(nèi)單節(jié)點故障保護算法

耿海軍，施新剛，王之梁，尹 霞

1(山西大學 軟件學院， 太原 03000 2清華大學 網(wǎng)絡(luò)科學與網(wǎng)絡(luò)空間研究院，北京100084 3清華大學 計算機科學與技術(shù)系，北京100084)

1 引 言

近些年來，互聯(lián)網(wǎng)的發(fā)展速度已經(jīng)遠遠超出了人們的預(yù)期[1,2]，并且互聯(lián)網(wǎng)支撐的應(yīng)用范圍[3]也在不斷擴大.互聯(lián)網(wǎng)在迅速發(fā)展的同時，面臨了新的挑戰(zhàn)，其中域內(nèi)路由可用性(Availability)[4]便是其中一個亟待需要解決的問題.相關(guān)研究[5]表明，網(wǎng)絡(luò)中的故障頻繁發(fā)生，并且不可避免.在故障修復(fù)期間，路由協(xié)議需要經(jīng)歷一段時間的收斂過程，在路由協(xié)議收斂過程中將有大量報文丟失，大大降低了路由可用性[6].然而，隨著一些新型應(yīng)用的出現(xiàn)，例如VoIP、在線游戲、視頻[7-9]，這些應(yīng)用對網(wǎng)絡(luò)時延提出了更加嚴格的要求[10,11].因此，如何提高網(wǎng)絡(luò)可用性[12]，降低路由協(xié)議收斂過程中報文丟失率，是互聯(lián)網(wǎng)面臨的一個重要挑戰(zhàn)[13,14].為了解決該問題，學術(shù)界和工業(yè)界提出了路由保護方案[15]，該方案預(yù)先計算備份路由，當網(wǎng)絡(luò)出現(xiàn)故障時，利用事先計算好的備份路徑轉(zhuǎn)發(fā)受故障影響的報文，從而有效減少報文丟失率.

等價多路徑( ECMP：Equal Cost Multiple Paths)[16]是最早使用的路由保護方案.當源地址和目的地址之間存在多條代價相等的最優(yōu)路徑時，利用等價路徑作為其備份路徑，該方案實現(xiàn)簡單，支持增量部署.然而，該方案要求備份路徑和最優(yōu)路徑具有相同的代價，雖然網(wǎng)絡(luò)管理員可以通過調(diào)整鏈路代價達到該目的，但是該問題被證明是NP問題[17].因此，ECMP對網(wǎng)絡(luò)可用性的貢獻有一定的局限性.

IP快速重路由[18]方案以其獨特的優(yōu)勢受到學術(shù)界和工業(yè)界的青睞，該方案利用無環(huán)路規(guī)則(Loop Free Alternates：LFA)，計算備份下一跳，從而實現(xiàn)路由保護.該方案計算復(fù)雜度小，容易部署，因此大部分廠商的路由器支持該方案.然而，研究表明[19,20]，利用該方案僅僅能保護50%左右的單故障情形.基于IP快速重路由框架，我們在文章[21-23]提出了一種高效的路由保護方案.該方案算法復(fù)雜度低，并且支持動態(tài)更新，支持增量部署，然而該方案的故障保護率和IP快速重路由的故障保護率接近.

為了進一步提高網(wǎng)絡(luò)可用性，文章[24]提出了利用U-turn方案提高故障保護率，該方案可以在其鄰居節(jié)點中計算LFA下一跳.U-turn雖然明顯提高了故障保護率，但是仍然達不到預(yù)期目標.基于快速重路由和U-turn存在的缺陷，文章[25]提出了基于Not-Via地址的快速重路由方案.該方案利用輔助機制Not-Via地址，顯式的表明網(wǎng)絡(luò)中的故障，從而可用有效保護網(wǎng)絡(luò)中所有單故障情形.雖然該機制可以大大提高網(wǎng)絡(luò)的可用性，但是該機制的實現(xiàn)比較復(fù)雜，開銷較大，不容易實際部署.

基于上述方案存在的缺陷，文章[26]提出了將基于IP快速重路由和基于Not-Via地址快速重路由結(jié)合的路由保護方案.該方案的基本思想是，當某節(jié)點存在IP快速重路由下一跳時，利用IP快速重路由方案，然而當該節(jié)點不在上述保護下一跳時，則利用基于Not-Via地址快速重路由計算保護下一跳.相比基于Not-Via地址快速重路由方案，融合方案大大降低了算法的復(fù)雜度，然而該方案仍然需要使用Not-Via地址，因此不容易實際部署.為了進一步降低上述融合算法的復(fù)雜度，我們在文章[27]中提出了一種高效的融合保護方案，該方案大大降低了算法的復(fù)雜度，并且故障保護率高，然而該方案部署復(fù)雜.文章[28]提出了利用O2方案來提高網(wǎng)絡(luò)可用性.該方案基本思路如下，算法為每個節(jié)點計算兩個到達目的地址的下一跳，當故障發(fā)生時，利用備份下一跳轉(zhuǎn)發(fā)報文.然而，該方案對網(wǎng)絡(luò)拓撲有一定的要求，并且計算復(fù)雜度較高.

2 單節(jié)點故障保護算法

2.1 基本模型

網(wǎng)絡(luò)拓撲結(jié)構(gòu)可以用圖G=(V,E)來表示，其中V表示網(wǎng)絡(luò)中路由器的集合，E表示網(wǎng)絡(luò)中鏈路的集合.對于網(wǎng)絡(luò)中的某條鏈路e=(x,y)∈E，用w(e)代表該鏈路的權(quán)值，該值可以是跳數(shù)、時延、帶寬、能耗等，也可以是其中這幾個度量的組合.假設(shè)源地址為s，目的地址為d，P(s,d)表示源到目的的最優(yōu)下一跳；B(s,d)表示源到目的的備份下一跳；SP(s,d)表示源到目的的最優(yōu)路徑；C(s,d)表示源到目的的最優(yōu)路徑的代價.

定義1.在網(wǎng)絡(luò)拓撲G=(V,E)中，對于該網(wǎng)絡(luò)中的任意一個目的地址d，稱Td(V,Ed)是以節(jié)點d為根的最優(yōu)路由樹，當且僅當滿足下面兩個條件：

1)Ed?E，|Ed|=|V|-1;

2)對于樹中的任意一個節(jié)點v∈E，該節(jié)點到目的地址d的路徑具有最小的代價;

定義2.在最優(yōu)路由樹Td(V,Ed)中，對于樹中的任意一個節(jié)點v∈V，child(v)表示該節(jié)點的所有孩子節(jié)點，parent(v)表示該節(jié)點的父親節(jié)點，subtree(v)表示以該節(jié)點為根的子樹中的所有節(jié)點.

定義3.在以目的地址d為根的最優(yōu)路由樹中，對于該樹中的任意一個節(jié)點v∈V-d，假設(shè)該節(jié)點出現(xiàn)故障.當節(jié)點u∈child(v)時，如果存在一條鏈路(x,y)，使得x∈subtree(d,u)和y∈V-subtree(v)-d同時成立，則稱鏈路(x,y)是子樹subtree(u)的第一類橋，用Candidate(u)={(x,y)}表示；當節(jié)點w∈child(v)時，如果存在一條鏈路(p,q)，使得p∈subtree(u)和q∈subtree(w)同時成立，則稱鏈路(p,q)為子樹subtree(u)和子樹subtree(w)的第二類橋，用Candidate2(u)=Candidate2(w)={(p,q)}表示.第一橋和和第二類橋統(tǒng)稱為橋，用Candidate來表示.

定義4.對于任意事件(u,d,f)，其中u表示源地址，d表示目的地址，f表示u到d的最優(yōu)路徑SP(u,d)上的單節(jié)點故障.當該事件出現(xiàn)時，如果u到d依然存在別的路徑，二者仍然保持連通.即該網(wǎng)絡(luò)圖中不存在割點，當該網(wǎng)絡(luò)拓撲結(jié)構(gòu)中的任何一個節(jié)點出現(xiàn)故障時，都不會影響該網(wǎng)絡(luò)的連通性，則稱該網(wǎng)絡(luò)具有健壯拓撲結(jié)構(gòu).

定理1. 對于一個健壯的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，假設(shè)節(jié)點f出現(xiàn)故障，節(jié)點f有k個孩子節(jié)點，分別用(f1,f2,…,fk)表示，則必定存在一個孩子節(jié)點fx∈child(f)，該孩子節(jié)點對應(yīng)的子樹subtree(fx)至少有一個第一類橋；當某個孩子節(jié)點fy∈child(f)對應(yīng)的子樹沒有第一類橋時，則該孩子節(jié)點對應(yīng)的子樹subtree(fy)至少有一個二類橋.

證明：下面使用反證法來證明該定理.

首先證明該定理的前半部分.當節(jié)點f出現(xiàn)故障時，假設(shè)節(jié)點f的所有孩子節(jié)點都沒有第一類橋.即對于任意節(jié)點fx∈child(f)不存在任何鏈路(p,q)，使得p∈subtree(fx)和q∈V-subtree(f)-d同時成立.那么對于任意節(jié)點p∈subtree(fx)，與節(jié)點p相連的鏈路的另一端q僅僅和集合subtree(fx)中的結(jié)點相連，q到d的最優(yōu)路徑必定經(jīng)過節(jié)點f.根據(jù)上述描述可知，當節(jié)點f出現(xiàn)故障時，節(jié)點fy∈child(f)對應(yīng)的子樹中的節(jié)點將無法到達目的.這與健壯的網(wǎng)絡(luò)拓撲結(jié)構(gòu)的前提假設(shè)相矛盾.因此該定理的前半部分成立.

下面證明該定理的后半部分.當節(jié)點f出現(xiàn)故障時，對于節(jié)點fy∈child(f)，當該節(jié)點對應(yīng)的子樹沒有第一類橋時，假設(shè)該節(jié)點對應(yīng)的子樹也不存在第二類橋.即對于節(jié)點fy∈child(f)，不存在任何鏈路(m,n)，使得m∈subtree(fy)和n∈subtree(fk)同時成立，其中fk∈child(f).那么對于任意節(jié)點m∈subtree(fy)，與節(jié)點m相連的鏈路的另一端n僅僅和集合subtree(fy)中的結(jié)點相連，n到d的最優(yōu)路徑必定經(jīng)過節(jié)點f.根據(jù)上述描述可知，當節(jié)點f出現(xiàn)故障時，節(jié)點fy∈child(f)對應(yīng)的子樹中的節(jié)點將無法到達目的.這與健壯的網(wǎng)絡(luò)拓撲結(jié)構(gòu)的前提假設(shè)相矛盾.因此該定理的后半部分成立.

根據(jù)上述證明可知，該定理成立.

定義5.在網(wǎng)路拓撲中，假設(shè)節(jié)點f出現(xiàn)故障.對于任意的源-目的(s,d)，當源到目的的最優(yōu)路徑經(jīng)過節(jié)點f時，即：f∈SP(s,d)，則s到d的最優(yōu)路徑將無法連通.如果fx∈child(f)，(x,y)∈Candidate(fx)和(x,y)∈RP(s,d)成立，其中RP(s,d)表示節(jié)點s到節(jié)點d重路由路徑，則稱該橋為RP(s,d)的有效橋.

引理1.在網(wǎng)路拓撲中，假設(shè)節(jié)點f出現(xiàn)故障，對于其孩子節(jié)點fx∈child(f)，如果橋(x,y)∈Candidate(fx)是第一類橋，則該橋一定是有效橋；如果該橋是第二類橋，則該橋不一定是有效橋.

證明：當節(jié)點f出現(xiàn)故障時，對于其孩子節(jié)點fx∈child(f)，如果橋(x,y)∈Candidate(fx)是第一類橋，其孩子節(jié)點fx的重路由路徑可以表示為RP(fx,d)=(fx,…,x,y,…,d)，因此(x,y)∈RP(fx,d)，即第一類橋一定是有效橋.當橋(x,y)∈Candidate(fx)是第二類橋時，假設(shè)fk∈child(f),y∈child(fk)，則(x,y)∈Candidate(fy).當子樹fk只有該二類橋，不存在別的橋時，節(jié)點fx的重路由路徑將不包含該橋.這是因為如果節(jié)點fx的重路由路徑將包含該橋，則當報文轉(zhuǎn)發(fā)到節(jié)點y時，節(jié)點y到目的的最優(yōu)路徑必然經(jīng)過節(jié)點f，而子樹fk沒有別的橋，因此報文將無法被正確轉(zhuǎn)發(fā)到目的地址.相反，當子樹fk存在別的橋時，節(jié)點fx的重路由路徑可能包含該橋.因此，第二類橋不一定是有效橋.

2.2 路由保護算法

本節(jié)將重點解決3個問題：

1)如何找出子樹對應(yīng)的有效橋；

2)如何選擇最佳的橋，從而使得重路由路徑具有最小的代價；

3)如何為節(jié)點計算保護下一跳.

根據(jù)引理1可知，某節(jié)點對應(yīng)的子樹可能存在兩類橋，第一類橋一定是有效橋，而第二類橋不一定是有效橋，因此為了計算有效橋，算法需要計算出該子樹對應(yīng)的所有橋，然后從中選擇有效橋.因為子樹對應(yīng)的橋的數(shù)量可能會很多，如果在算法中計算出所有橋，然后再從中選擇有效橋，該方案將會增加算法的時間復(fù)雜度.因此，為了降低算法復(fù)雜度，本文對橋的優(yōu)先級做了如下規(guī)定，第一類橋的優(yōu)先級大于二類橋的優(yōu)先級，當某個節(jié)點的子樹擁有第一類橋時，不再為其計算第二類橋.如果某個節(jié)點的子樹只有第二類橋時，只為其計算有效第二類橋.

下面描述如何為子樹選擇最佳橋，如何為節(jié)點計算備份下一跳.由于對于任意的目的節(jié)點計算方法都是類似的，因此，不失一般性，算法僅僅考慮目的地址為d的計算方法.在下面的描述中，對節(jié)點的顏色做了區(qū)分，所有節(jié)點的初始顏色都是白色；當節(jié)點f出現(xiàn)故障時，當fx∈child(f)時，將子樹subtree(fx)中的所有節(jié)點標記為黑色，表示將要為該子樹計算最佳橋；當為該子樹計算出有效橋時，將該子樹中所有節(jié)點標記為灰色.

2.2.1 子樹有第一類橋

當節(jié)f點出現(xiàn)故障時，節(jié)點fx∈child(f)對應(yīng)的子樹有第一類橋.將子樹subtree(fx)中的所有節(jié)點標記為黑色，根據(jù)深度優(yōu)先算法遍歷子樹subtree(fx)中的所有節(jié)點，對于該子樹中的節(jié)點p，檢查它的每一個鄰居節(jié)點q，如果該節(jié)點不是黑色，則鏈路(p,q)為子樹subtree(fx)的橋，由公式(1)

C(fx,p)+C(p,q)+C(q,d)

(1)

計算重路由路徑的代價.該公式中涉及到的變量都可以很容易的從鏈路狀態(tài)路由協(xié)議中得到.其中cost(p,q)可以從鏈路狀態(tài)數(shù)據(jù)庫中得到，其余變量可以通過Td得到，因此很容易計算相應(yīng)的橋?qū)?yīng)的重路由路徑的代價.對于找到的所有橋，選擇具有最短重路由路徑的一個作為最終的橋.最后為相應(yīng)的節(jié)點計算保護下一跳.根據(jù)選定的橋，計算節(jié)點fx的重路由路徑，假設(shè)該路徑為(fx,m1,m2,…,mk,p,q)， 則相應(yīng)節(jié)點的保護下一跳為：B(fx,d)=m1，B(m1,d)=m2,…,B(p,d)=q.最后，將子樹subtree(d,fx)中的所有節(jié)點標記為灰色.

2.2.2 子樹只有第二類橋

當節(jié)點f出現(xiàn)故障時，節(jié)點fy∈child(f)對應(yīng)的子樹只有第二類橋.根據(jù)廣度優(yōu)先算法遍歷子樹subtree(d,fy)中的所有節(jié)點，尋找首次出現(xiàn)的一條邊(m,n)，其中m是黑色，n是灰色，則鏈路(m,n)即為該子樹的最佳橋，最后將子樹subtree(fy)中的所有節(jié)點標記為灰色.根據(jù)同樣的方法計算重路由路徑的代價和保護下一跳.

算法1描述了如何為節(jié)點的子樹計算有效橋，如何選擇最終橋，如何為節(jié)點計算保護下一跳.算法將為每個節(jié)點計算一個最優(yōu)下一跳和一個備份下一跳.當網(wǎng)絡(luò)出現(xiàn)故障時，不受該故障影響的節(jié)點依舊按照最優(yōu)下一跳轉(zhuǎn)發(fā)報文，受該故障影響的節(jié)點將報文轉(zhuǎn)發(fā)給備份下一跳.將所有節(jié)點的備份下一跳設(shè)置為空，所有節(jié)點的顏色標記為白色(算法1中的第1-4行).對于目的節(jié)點d，根據(jù)深度優(yōu)先算法遍歷以d為根的最優(yōu)路由樹中的所有節(jié)點，當訪問某個節(jié)點v時，假設(shè)該節(jié)點出現(xiàn)故障.假設(shè)節(jié)點v有k個孩子節(jié)點，分別用(v1,v2,…,vk)表示.首先，將子樹subtree(v)中的所有節(jié)點標記為黑色，其余節(jié)點標記為白色(算法1中的第7行).如果節(jié)點v的孩子節(jié)點已經(jīng)有了備份下一跳，則將該孩子節(jié)點對應(yīng)的子樹全部標記為灰色，(算法1中的第8-12行).

算法重復(fù)執(zhí)行下面的步驟1-步驟3，直到除去節(jié)點 外，沒有黑色節(jié)點.

1)根據(jù)深度優(yōu)先算法遍歷子樹subtree(v)中的所有黑色節(jié)點.

1.1)如果存在第一類橋，計算具有最短保護路徑的一個橋作為最終的橋，記為(m,n)，(算法1中的第15-26行).

1.2)如果不存在第一類橋，根據(jù)廣度優(yōu)先算法遍歷子樹subtree(d,v)中的所有黑色節(jié)點，計算出第二類橋，記為(m,n)，(算法1中的第27-31行).

2)尋找節(jié)點m對應(yīng)的子樹的根節(jié)點，并且將子樹中所有節(jié)點標記為灰色，(算法1中的第32-33行).

3)根據(jù)選擇的最終橋為相應(yīng)節(jié)點計算保護下一跳(算法1中的第34行).

Algorithm1. Node-protection(d)

//每個節(jié)點計算到目的地址d的備份下一跳

Input: v∈V,G(V,E)，目的地址d

Output: B(,d)

1.Forv∈Vdo

2.B(v,d)← φ;

3.v.color← white;

4.EndFor

5.計算Td(V,Ed)，并且存儲節(jié)點到d的最優(yōu)下一跳;

//按照深度優(yōu)先順序訪問Td(V,Ed)中的節(jié)點；當訪問某個節(jié)點時，假設(shè)該節(jié)點出現(xiàn)故障.

6.Forv∈V且v≠ddo

7.將subtree(d,v)中的所有節(jié)點標記為黑色;

8.Foru∈child(v)do

9.IfB(u,d)≠φthen

10.將subtree(u)中的所有節(jié)點標記為灰色;

11.EndIf

12.EndFor

13.mincost← ∞;

14.Flag=0;

15.Form∈subtree(v)并且m是黑色節(jié)點do

16.For每個與節(jié)點m直接相連的節(jié)點ndo

17.Ifn是白色的then

18.Flag = 1;

19.value=C(m,d)-C(v,d)+C(m,n)+C(y,d)

20.Ifmincost≥valuethen

21.m← x

22.n← y

23.EndIf

24.EndIf

25.EndFor

26.EndFor

//如果不存在第一類橋

27.IfFlag=0then

//利用廣度優(yōu)先遍歷subtree(v)中節(jié)點

28.Form∈subtree(v)并且m是黑色do

29.尋找首次出現(xiàn)的一條邊(m; n)，其中m是黑色， n是灰色;

30.EndFor

31.EndIf

32.尋找節(jié)點m所在的子樹，使m∈subtree(f )，其中f∈child(v)

33.將subtree(f)中的所有節(jié)點標記為灰色;

//表示已經(jīng)為該子樹計算出有效橋

34.AssignBackup(m,n,f,d);

//如果不存在第一類橋，則計算有效第二類橋.

35.EndFor

36.return Backup(,d)

Algorithm2. AssignBackup(x,y,v,d)

//為路徑SP(x,v)上的所有節(jié)點計算備份下一跳，其中(x,y)為子樹v的橋

1.u←x;

2.v← y;

3.Whileu≠vdo

4.IfB(u,d)=φthen

5.B(u,d)←v;

6.v←u;

7.u←Primary(u);

8.EndIf

9.EndWhile

圖1描述了當節(jié)點a出現(xiàn)故障時，算法為其孩子節(jié)點計算備份下一跳的過程.

1)找出所有以a為根的子樹(節(jié)點a除外)的橋{(g,k),(i,l),(i,m)}.因為該子樹有第一類橋，所以不再為其計算第二類橋.當選擇(g,k)作為該子樹的橋時，節(jié)點e的重路由路徑的代價最小，因此選擇鏈路(g,k)作為以e為根的子樹的最終橋，并且將以e為根的子樹標記為灰色.根據(jù)選擇的最終橋可知，節(jié)點e的重路由路徑為RP(e)=(e,g,k,j,d)，因此B(g,d)=k,B(e,d)=g.

2)找出所有以a為根的子樹(灰色節(jié)點和節(jié)點a除外)的橋{(c,g),(f,i)}，并且將以c為根的子樹標記為灰色.因為該子樹只有二類橋，根據(jù)算法只選擇一個橋即可，因此選擇鏈路(c,g)作為以c為根的子樹的最終橋.在選擇橋時，只考慮和灰色節(jié)點相連的鏈路，因此選擇的橋都是有效橋，從而保證算法的正確性.根據(jù)選擇的最終橋可知，節(jié)點c的重路由路徑為RP(c)=(c,g,k,j,d)，因此B(c,d)=g

圖1 計算備份下一跳實例

3)找出所有以a為根的子樹(灰色節(jié)點和節(jié)點a除外)的橋{(b,c)}，并且將以b為根的子樹標記為灰色.根據(jù)選擇的最終橋可知，節(jié)點b的重路由路徑為RP(b)=(b,c,g,k,j,d)，因此B(b,d)=c.

定理2.當網(wǎng)絡(luò)中的所有節(jié)點都部署上述的路由保護算法時，可以保護網(wǎng)絡(luò)中任意單節(jié)點故障.

證明：在網(wǎng)路拓撲中，假設(shè)節(jié)點f出現(xiàn)故障.對于任意的源-目的(s,d)，當源到目的的最優(yōu)路徑經(jīng)過節(jié)點f時，根據(jù)定理1可知，子樹subtree(f)至少存在一個有效橋，則算法可以保護節(jié)點f. 由于節(jié)點s是節(jié)點f的子孫節(jié)點，則當節(jié)點f斷開時，從源節(jié)點s發(fā)送到目的節(jié)點d的報文可以正常到達.

2.3 轉(zhuǎn)發(fā)算法

對于任意目的節(jié)點，每個節(jié)點在轉(zhuǎn)發(fā)表中維護兩個下一跳，分別是最優(yōu)下一跳和備份下一跳.節(jié)點通過運行路由協(xié)議，計算出最優(yōu)下一跳，運行路由保護算法，計算出備份下一跳.根據(jù)上述算法可知，當網(wǎng)絡(luò)中出現(xiàn)單節(jié)點故障時，某些節(jié)點對應(yīng)的重路由路徑可能需要經(jīng)過多個橋.因此可以利用MPLS來配置備份路由，然而該方案需要額外的控制信息，開銷比較大，不容易實際部署.因此，本文的方案采用純IP協(xié)議實現(xiàn)，利用了IP包中的TOS( Type of Service)字段，該字段的數(shù)值記錄節(jié)點重路由路徑經(jīng)過的第二類橋的數(shù)量.在實際網(wǎng)絡(luò)中可以通過雙向轉(zhuǎn)發(fā)檢測機制(BFD，Bidirectional Forwarding Detection)快速檢測網(wǎng)絡(luò)中的節(jié)點故障.下面是具體的報文轉(zhuǎn)發(fā)過程，當某個節(jié)點收到報文時：

1)該節(jié)點不是從最優(yōu)下一跳接收到報文.

1.1)若該報文頭部的TOS字段值為0，將分兩種情況：

1.1.1)該節(jié)點到目的節(jié)點的最優(yōu)下一跳沒有故障，則將報文轉(zhuǎn)發(fā)給最優(yōu)下一跳.

1.1.2)該節(jié)點到目的節(jié)點的最優(yōu)下一跳出現(xiàn)故障，該節(jié)點將修改報文頭部的TOS字段，將報文轉(zhuǎn)發(fā)給備份下一跳.

1.2)如果該報文頭部的TOS字段值不為0時，則將報文轉(zhuǎn)發(fā)給備份下一跳，并且將TOS字段的值減1.

2)該節(jié)點從最優(yōu)下一跳接收到報文，該節(jié)點到目的的最優(yōu)路徑必定出現(xiàn)了故障，因此該節(jié)點需要將報文轉(zhuǎn)發(fā)給備份下一跳.

從上述的轉(zhuǎn)發(fā)方式可以看出，本文提出的算法和目前互聯(lián)網(wǎng)采用的路由算法都是采用的逐跳轉(zhuǎn)發(fā)方式.

3 實驗及結(jié)果分析

為了全面準確的說明上述算法的性能，將在試驗中采用多種拓撲結(jié)構(gòu).其中包括Abilene[29]，利用測量工具Rocketfuel[30]測量拓撲結(jié)構(gòu)，利用模擬軟件Brite[31]產(chǎn)生的拓撲結(jié)構(gòu).

1)Abilene是一個實際運行的網(wǎng)絡(luò)拓撲，由11個路由器和14條鏈路構(gòu)成.

2)本文在Rocketfuel測量出的拓撲中選擇6個拓撲，其參數(shù)在表1中列出.

表1 Rocketfuel拓撲參數(shù)

3)利用模擬軟件Brite產(chǎn)生拓撲的具體參數(shù)見表2.

表2 Brite生成拓撲結(jié)構(gòu)的參數(shù)設(shè)置

3.1 故障保護率

本節(jié)將利用故障保護率來評價不同算法應(yīng)對網(wǎng)絡(luò)中單節(jié)點故障的能力.故障保護率定義為：受保護節(jié)點的數(shù)量/網(wǎng)絡(luò)中所有節(jié)點的數(shù)量.從該定義可以看出，對于同一拓撲結(jié)構(gòu)，故障保護率越高，該算法的性能越高.

表3描述了不同算法對應(yīng)的故障保護率，該表中采用真實拓撲和測量拓撲模擬實驗.從該表中可以得出結(jié)論，本文算法可以100%保護網(wǎng)絡(luò)中所有出現(xiàn)的單節(jié)點故障情形，LFA和U-turn只能保護部分單節(jié)點故障.本文算法的故障保護率明顯高于LFA和U-turn.

表3 不同算法對應(yīng)的單節(jié)點故障保護率

圖2表示故障保護率和網(wǎng)絡(luò)中節(jié)點平均度的關(guān)系，采用Brite軟件生成拓撲模擬實驗，可以看出，本文提出的算法始終保持100%故障保護率.LFA和U-turn的故障保護率隨著節(jié)點度的增加而增加，但是仍然無法提供100%故障保護率.當網(wǎng)絡(luò)平均節(jié)點度為30時，LFA和U-turn的故障保護率分別為63%和81%.

圖2 故障保護率隨著節(jié)點平均度變化情況

3.2 路徑拉伸度

當網(wǎng)絡(luò)發(fā)生故障時，受該故障影響的路徑的代價必定會發(fā)生變化.因此，下面將討論網(wǎng)絡(luò)發(fā)生單節(jié)點故障后，算法對應(yīng)的路徑拉伸度.路徑拉伸度表示為：當網(wǎng)絡(luò)中發(fā)生故障時，重路由路徑的代價/最短路徑代價.路徑拉伸度越大，重路由路徑代價越大，對資源的消耗越大，相反，路徑拉伸度越小，重路由路徑越接近最優(yōu)路徑.

圖3 路徑拉伸度

下面詳細描述實驗過程，對于某個網(wǎng)絡(luò)，隨機的選擇某個節(jié)點發(fā)生故障，然后利用不同的算法計算重路由路徑，最后計算出相應(yīng)的路徑拉伸度.圖中的數(shù)值表示重復(fù)上述實驗100次后計算平均值.

圖3描述了不同算法在相應(yīng)的拓撲結(jié)構(gòu)中對應(yīng)的路徑拉伸度.從該圖中，可以看出，本文路徑拉伸度明顯低于LFA和U-turn.這是因為LFA和U-turn采用隨機方法選擇備份下一跳，而本文算法從所有備份路徑中選擇代價最小的下一跳作為備份下一跳.因此，本文提出的算法對應(yīng)的重路由路徑更加接近最優(yōu)路徑.

4 結(jié)束語

針對目前互聯(lián)網(wǎng)部署的域內(nèi)路由協(xié)議存在的可用性問題，本文提出了一種有效的單節(jié)點故障路由保護方案.該方案與目前互聯(lián)網(wǎng)部署的域內(nèi)路由協(xié)議是兼容的，因此支持增量部署，容易在實際環(huán)境中部署.理論和實驗結(jié)果表明，該方案可以100%保護網(wǎng)絡(luò)中所有出現(xiàn)的單節(jié)點故障情形，達到了預(yù)期目標經(jīng).本文提出的方案主要針對網(wǎng)絡(luò)中單故障情形，因此下一步將重點研究如何將該算法應(yīng)用在并發(fā)故障情形.