陳榮慶，黃艷紅

（1.泰州市海陵區(qū)經濟和信息化委員會，江蘇 泰州225300；2.華碩科技有限公司，浙江 杭州310012）

互聯(lián)網(wǎng)在設計之初主要用于傳輸非實時業(yè)務，如收發(fā)電子郵件、瀏覽網(wǎng)頁等。當網(wǎng)絡發(fā)生故障時，應用傳統(tǒng)路由協(xié)議（OSPF、IS-IS等）進行全網(wǎng)路由收斂，耗費時間長達數(shù)秒[1]，對于非實時業(yè)務，這個時間是可以接受的。然而，近年來網(wǎng)絡實時業(yè)務（如在線游戲、VoIP、視頻播放等）不斷發(fā)展，要求網(wǎng)絡故障的恢復時間達到毫秒級，傳統(tǒng)路由協(xié)議已不能滿足此要求，因此IP網(wǎng)絡的故障快速恢復技術成為當前的研究熱點。網(wǎng)絡中大部分故障為單鏈路或節(jié)點故障[2]，這種情況下的快速恢復技術比較多，主要有快速重路由算法（IP FRR）、故障不敏感路由算法（FIR）、偏轉路由算法（DR）等[1]。但是隨著網(wǎng)絡的迅速發(fā)展和其規(guī)模的不斷擴大，承載的數(shù)據(jù)流越來越多，多個鏈路和節(jié)點同時發(fā)生故障的概率也逐漸增加，帶來的影響比較大，可是由于這種情況以前發(fā)生概率很小，國內外學者關注的并不多，其研究成果主要是將彈性路由層算法（RRL）和多路由配置算法（MRC）應用于多個故障的快速恢復中，但都存在一些不足之處。本文將在比較總結RRL算法和MRC算法的基礎上，提出一種改進的IP網(wǎng)絡多故障快速恢復算法，并進行仿真實驗驗證其優(yōu)化效果。

1 兩種主要的多故障快速恢復算法

目前，在IP網(wǎng)絡中處理多故障快速恢復問題的方法主要是先應式的多拓撲（MT）技術，基本思想是由網(wǎng)絡原始拓撲圖生成多個備份拓撲來保護所有鏈路和節(jié)點。如果某些鏈路和節(jié)點同時發(fā)生故障，則快速切換到能保護這些組件的備份拓撲，被保護的網(wǎng)絡組件在對應的備份拓撲中不會轉發(fā)任何數(shù)據(jù)流，從而實現(xiàn)故障時數(shù)據(jù)流的正常傳輸。該技術的重點是如何根據(jù)網(wǎng)絡原始拓撲圖構建備份拓撲集，使得其中包含的備份拓撲數(shù)量盡可能少，并且每個節(jié)點對之間的最佳傳輸路徑長度盡可能短。

1.1 彈性路由層算法

RRL算法基于“路由層”描述備份拓撲，每個層包含網(wǎng)絡中的部分鏈路和所有節(jié)點，如果某一層中不包含原始拓撲的某條鏈路，則該鏈路在此層中被保護；如果在該層中某個節(jié)點只有一條鏈路與之相連，則該節(jié)點在此層中同樣被保護[3]。

1.2 多路由配置算法

MRC算法基于“配置圖”描述備份拓撲，每個圖包含有正常鏈路、孤立鏈路、受限鏈路和正常節(jié)點、孤立節(jié)點。算法中孤立鏈路被賦予一個無窮大的度量值，故其在對應的備份拓撲中不會被用來轉發(fā)數(shù)據(jù)流。受限鏈路被賦予一個有限但很大的度量值，其在對應的備份拓撲中僅能作為第一跳或最后一跳鏈路接收和發(fā)送數(shù)據(jù)[4]。只有孤立鏈路和受限鏈路才可以連接到孤立節(jié)點。算法的實現(xiàn)過程是通過將前一個備份拓撲中孤立節(jié)點連接的受限鏈路和其對端節(jié)點，在下一個備份拓撲中孤立出來，如此循環(huán)直到每個網(wǎng)絡組件都被孤立出來為止。

綜上所述，RRL算法生成的每個“路由層”只包含網(wǎng)絡中的所有節(jié)點和部分鏈路，去除了其保護的那部分鏈路，故生成的備份拓撲實際上改變了原始拓撲圖結構。MRC算法與之不同，其生成的“配置圖”不改變拓撲圖結構，只是設置鏈路度量值使數(shù)據(jù)流傳輸時不經過故障部件，相比RRL算法簡單可行。但是MRC算法生成的備份拓撲數(shù)量過多，造成相應的轉發(fā)表項和鏈路狀態(tài)信息報文過多，消耗大量的存儲資源，在網(wǎng)絡規(guī)模較大時，節(jié)點不能存儲所有的備份拓撲信息，從而影響網(wǎng)絡的擴展性。

2 算法改進

針對MRC算法存在的問題提出一種改進算法，能夠有效生成數(shù)量盡可能少的備份拓撲，但同樣可以保護網(wǎng)絡所有鏈路和節(jié)點，旨在用最少的存儲資源實現(xiàn)多故障下的快速恢復。該算法中孤立鏈路、受限鏈路和孤立節(jié)點的定義與前文所述一致。改進算法將自動生成網(wǎng)絡無向圖G=(N，E)的備份拓撲集，圖1是其實現(xiàn)流程圖。

算法先初始化所有參數(shù)，隨機產生一組用于生成最小生成樹的鏈路權值集。該鏈路權值與鏈路度量值不同，因為改進算法中第一個最小生成樹將影響以后創(chuàng)建備份拓撲，如果由鏈路度量值決定權值，那么只能生成一個確定的最小生成樹，而它可能并不適合用來創(chuàng)建其他備份拓撲，所以這里使用一組隨機產生的鏈路權值來生成最小生成樹，如果它不適合用來進一步創(chuàng)建其他備份拓撲，就循環(huán)執(zhí)行整個算法，隨機產生另外一組合適的鏈路初始權值集來生成最小生成樹。

圖1 改進算法實現(xiàn)流程圖

初始化完成后，會得到一個最小生成樹，一部分權值較大的鏈路被分離出來，將其設為孤立鏈路（鏈路的度量值設為無窮大值），最小生成樹的葉子節(jié)點設為孤立節(jié)點，與孤立節(jié)點相連的鏈路設為受限鏈路（鏈路的度量值設為一個有限但很大的值）。由此，依據(jù)原始拓撲圖的最小生成樹就可以得到第一個備份拓撲，其中孤立和受限鏈路的度量值被重新設置，其他鏈路保持不變。然后，檢查是否滿足結束條件。算法中維護一個包含尚未被孤立出來的所有鏈路和節(jié)點的集合G′，如果G′為空，表明備份拓撲集已經能保護所有網(wǎng)絡組件，則結束整個算法；如果G′不為空，結束條件不滿足，則算法將對最小生成樹的相關鏈路權值進行多次（M次）調整，嘗試產生最佳的下一個備份拓撲，可以盡可能多地保護尚未被孤立的鏈路和節(jié)點。權值調整具體方法為：對尚未被保護的鏈路權值增加一個任意值，那么調整后生成的最小生成樹就可以使該鏈路孤立出來；將之前備份拓撲連接到非孤立節(jié)點的某一條鏈路的權值設為一個更小的值，而與該節(jié)點相連的其他鏈路的權值設為一個更大的值，則在調整后生成的最小生成樹中該節(jié)點就會成為葉子節(jié)點。經過M次調整后選取一組最佳權值，用于產生下一個備份拓撲，它能最大數(shù)目地保護尚未被孤立的鏈路和節(jié)點，最終減少備份拓撲的個數(shù)。最后，循環(huán)執(zhí)行直到獲得的備份拓撲集滿足要求為止，即所有的鏈路和節(jié)點都至少被一個備份拓撲保護。

3 算法仿真與性能分析

對改進算法和傳統(tǒng)MRC算法在不同網(wǎng)絡拓撲模型中的表現(xiàn)進行仿真實驗，驗證其在減少備份拓撲個數(shù)和節(jié)省網(wǎng)絡存儲資源方面具有比較好的性能。實驗中采用的網(wǎng)絡拓撲模型是隨機型的Waxman模型和冪律型的BA模型。

圖2和圖3是分別對Waxman模型和BA模型的拓撲實例進行仿真的結果。表明相同情況下，改進算法產生的備份拓撲總數(shù)一直都少于傳統(tǒng)MRC算法。網(wǎng)絡拓撲中節(jié)點數(shù)越多，這種差別越明顯。備份拓撲總數(shù)減少將對應減少節(jié)點中存儲的轉發(fā)表項和網(wǎng)絡中的鏈路狀態(tài)信息報文，從而節(jié)省有限的存儲資源。

結果還表明，無論是Waxman模型還是BA模型，隨著網(wǎng)絡中節(jié)點個數(shù)的增加，傳統(tǒng)算法生成的備份拓撲總數(shù)會同時增加很多，而改進算法中這種變化比較平緩。這是因為由傳統(tǒng)MRC算法相繼生成的備份拓撲中，孤立鏈路和孤立節(jié)點總是處在相鄰的位置上，其他不在此范圍內的鏈路和節(jié)點要一直等到循環(huán)到達，才能被孤立出來。所以當網(wǎng)絡規(guī)模擴大時，就需要生成更多的備份拓撲；而改進算法由最小生成樹盡最大可能孤立出所有鏈路和節(jié)點，其受網(wǎng)絡規(guī)模的影響較小，因此當網(wǎng)絡中節(jié)點數(shù)增加時，算法生成的備份拓撲個數(shù)變化并不大。此外，雖然改進算法在兩個拓撲模型中都有良好的表現(xiàn)，但在BA模型中表現(xiàn)更好，這是由于兩種模型中節(jié)點度分布不同造成的。BA模型中節(jié)點度分布服從冪律分布特性，小部分節(jié)點需承擔大量的鏈路負載；Waxman模型中節(jié)點度的分布則比較均衡，而改進算法總是將度量值大的鏈路優(yōu)先孤立出來，故其在BA模型中表現(xiàn)更好。目前網(wǎng)絡服務提供商(ISP)的網(wǎng)絡拓撲大多服從冪律分布特性[5]，因此改進算法更適合應用于實際網(wǎng)絡中。

本文提出了一種改進的IP網(wǎng)絡多故障情況下的快速恢復算法，相比傳統(tǒng)MRC算法，它可以用較少的備份拓撲應對同時發(fā)生的多個鏈路和節(jié)點故障，能有效節(jié)省網(wǎng)絡存儲資源，并且受網(wǎng)絡中節(jié)點個數(shù)變化的影響較小，在其生成的備份拓撲中應用最短路徑算法就可以獲得每個節(jié)點對之間長度最短的傳輸路徑。該算法在服從冪律分布特性的實際大規(guī)模網(wǎng)絡中表現(xiàn)更優(yōu)，具有良好的實用價值。

[1]張民貴，劉斌.IP網(wǎng)絡的快速故障恢復[J].電子學報，2008，36(8)：26－28.

[2]MARKOPOULOU A，IANNACCONE G，BHATTACHARYYA S，et al.Characterization of failures in an IP backbone[C].Proceedings of IEEE INFOCOMM’04.HK，2004.

[3]HANSEN A F，CICIC T，GJESSING S，et al.Resilient routing layers for recovery in packet networks[C].The International Conference on Dependable Systems and Networks(DSN)，2005.

[4]KVALBEIN A，HANSEN A F，CICIC T，et al.Fast IP network recovery using multiple routing configurations[C].Proceedings of IEEE Infocom，2006.

[5]MEDINA A，LAKHINA A，MATTA I，et al.BRITE：an approach to universal topology generation[C].IEEE MASCOTS，2001.