摘  要： 隨著網(wǎng)絡(luò)承載數(shù)據(jù)量的不斷增加和實時業(yè)務(wù)的迅速發(fā)展，要求網(wǎng)絡(luò)故障的恢復(fù)時間越來越短，而傳統(tǒng)路由協(xié)議收斂時間過長，已不能滿足其要求，并且多故障同時發(fā)生的情況也在增多，這些都影響了IP網(wǎng)絡(luò)的穩(wěn)定運行，嚴重時甚至?xí)斐梢欢ǖ慕?jīng)濟損失。提出一種改進的IP網(wǎng)絡(luò)多故障情況下的快速恢復(fù)算法，可以用少量的備份拓撲應(yīng)對同時發(fā)生的多個鏈路和節(jié)點故障。與傳統(tǒng)算法相比，有效節(jié)省了網(wǎng)絡(luò)存儲資源，增強了網(wǎng)絡(luò)的可擴展性，具有良好的實用價值。
關(guān)鍵詞： IP網(wǎng)絡(luò)；故障恢復(fù)；MRC；備份拓撲

    互聯(lián)網(wǎng)在設(shè)計之初主要用于傳輸非實時業(yè)務(wù)，如收發(fā)電子郵件、瀏覽網(wǎng)頁等。當(dāng)網(wǎng)絡(luò)發(fā)生故障時，應(yīng)用傳統(tǒng)路由協(xié)議（OSPF、IS-IS等）進行全網(wǎng)路由收斂，耗費時間長達數(shù)秒[1]，對于非實時業(yè)務(wù)，這個時間是可以接受的。然而，近年來網(wǎng)絡(luò)實時業(yè)務(wù)（如在線游戲、VoIP、視頻播放等）不斷發(fā)展，要求網(wǎng)絡(luò)故障的恢復(fù)時間達到毫秒級，傳統(tǒng)路由協(xié)議已不能滿足此要求，因此IP網(wǎng)絡(luò)的故障快速恢復(fù)技術(shù)成為當(dāng)前的研究熱點。網(wǎng)絡(luò)中大部分故障為單鏈路或節(jié)點故障[2]，這種情況下的快速恢復(fù)技術(shù)比較多，主要有快速重路由算法（IP FRR）、故障不敏感路由算法（FIR）、偏轉(zhuǎn)路由算法（DR）等[1]。但是隨著網(wǎng)絡(luò)的迅速發(fā)展和其規(guī)模的不斷擴大，承載的數(shù)據(jù)流越來越多，多個鏈路和節(jié)點同時發(fā)生故障的概率也逐漸增加，帶來的影響比較大，可是由于這種情況以前發(fā)生概率很小，國內(nèi)外學(xué)者關(guān)注的并不多，其研究成果主要是將彈性路由層算法（RRL）和多路由配置算法（MRC）應(yīng)用于多個故障的快速恢復(fù)中，但都存在一些不足之處。本文將在比較總結(jié)RRL算法和MRC算法的基礎(chǔ)上，提出一種改進的IP網(wǎng)絡(luò)多故障快速恢復(fù)算法，并進行仿真實驗驗證其優(yōu)化效果。
1 兩種主要的多故障快速恢復(fù)算法
    目前，在IP網(wǎng)絡(luò)中處理多故障快速恢復(fù)問題的方法主要是先應(yīng)式的多拓撲（MT）技術(shù)，基本思想是由網(wǎng)絡(luò)原始拓撲圖生成多個備份拓撲來保護所有鏈路和節(jié)點。如果某些鏈路和節(jié)點同時發(fā)生故障，則快速切換到能保護這些組件的備份拓撲，被保護的網(wǎng)絡(luò)組件在對應(yīng)的備份拓撲中不會轉(zhuǎn)發(fā)任何數(shù)據(jù)流，從而實現(xiàn)故障時數(shù)據(jù)流的正常傳輸。該技術(shù)的重點是如何根據(jù)網(wǎng)絡(luò)原始拓撲圖構(gòu)建備份拓撲集，使得其中包含的備份拓撲數(shù)量盡可能少，并且每個節(jié)點對之間的最佳傳輸路徑長度盡可能短。
1.1 彈性路由層算法
    RRL算法基于“路由層”描述備份拓撲，每個層包含網(wǎng)絡(luò)中的部分鏈路和所有節(jié)點，如果某一層中不包含原始拓撲的某條鏈路，則該鏈路在此層中被保護；如果在該層中某個節(jié)點只有一條鏈路與之相連，則該節(jié)點在此層中同樣被保護[3]。
1.2 多路由配置算法
    MRC算法基于“配置圖”描述備份拓撲，每個圖包含有正常鏈路、孤立鏈路、受限鏈路和正常節(jié)點、孤立節(jié)點。算法中孤立鏈路被賦予一個無窮大的度量值，故其在對應(yīng)的備份拓撲中不會被用來轉(zhuǎn)發(fā)數(shù)據(jù)流。受限鏈路被賦予一個有限但很大的度量值，其在對應(yīng)的備份拓撲中僅能作為第一跳或最后一跳鏈路接收和發(fā)送數(shù)據(jù)[4]。只有孤立鏈路和受限鏈路才可以連接到孤立節(jié)點。算法的實現(xiàn)過程是通過將前一個備份拓撲中孤立節(jié)點連接的受限鏈路和其對端節(jié)點，在下一個備份拓撲中孤立出來，如此循環(huán)直到每個網(wǎng)絡(luò)組件都被孤立出來為止。
    綜上所述，RRL算法生成的每個“路由層”只包含網(wǎng)絡(luò)中的所有節(jié)點和部分鏈路，去除了其保護的那部分鏈路，故生成的備份拓撲實際上改變了原始拓撲圖結(jié)構(gòu)。MRC算法與之不同，其生成的“配置圖”不改變拓撲圖結(jié)構(gòu)，只是設(shè)置鏈路度量值使數(shù)據(jù)流傳輸時不經(jīng)過故障部件，相比RRL算法簡單可行。但是MRC算法生成的備份拓撲數(shù)量過多，造成相應(yīng)的轉(zhuǎn)發(fā)表項和鏈路狀態(tài)信息報文過多，消耗大量的存儲資源，在網(wǎng)絡(luò)規(guī)模較大時，節(jié)點不能存儲所有的備份拓撲信息，從而影響網(wǎng)絡(luò)的擴展性。
2 算法改進
    針對MRC算法存在的問題提出一種改進算法，能夠有效生成數(shù)量盡可能少的備份拓撲，但同樣可以保護網(wǎng)絡(luò)所有鏈路和節(jié)點，旨在用最少的存儲資源實現(xiàn)多故障下的快速恢復(fù)。該算法中孤立鏈路、受限鏈路和孤立節(jié)點的定義與前文所述一致。改進算法將自動生成網(wǎng)絡(luò)無向圖G=(N，E)的備份拓撲集，圖1是其實現(xiàn)流程圖。

    算法先初始化所有參數(shù)，隨機產(chǎn)生一組用于生成最小生成樹的鏈路權(quán)值集。該鏈路權(quán)值與鏈路度量值不同，因為改進算法中第一個最小生成樹將影響以后創(chuàng)建備份拓撲，如果由鏈路度量值決定權(quán)值，那么只能生成一個確定的最小生成樹，而它可能并不適合用來創(chuàng)建其他備份拓撲，所以這里使用一組隨機產(chǎn)生的鏈路權(quán)值來生成最小生成樹，如果它不適合用來進一步創(chuàng)建其他備份拓撲，就循環(huán)執(zhí)行整個算法，隨機產(chǎn)生另外一組合適的鏈路初始權(quán)值集來生成最小生成樹。
    初始化完成后，會得到一個最小生成樹，一部分權(quán)值較大的鏈路被分離出來，將其設(shè)為孤立鏈路（鏈路的度量值設(shè)為無窮大值），最小生成樹的葉子節(jié)點設(shè)為孤立節(jié)點，與孤立節(jié)點相連的鏈路設(shè)為受限鏈路（鏈路的度量值設(shè)為一個有限但很大的值）。由此，依據(jù)原始拓撲圖的最小生成樹就可以得到第一個備份拓撲，其中孤立和受限鏈路的度量值被重新設(shè)置，其他鏈路保持不變。然后，檢查是否滿足結(jié)束條件。算法中維護一個包含尚未被孤立出來的所有鏈路和節(jié)點的集合G′，如果G′為空，表明備份拓撲集已經(jīng)能保護所有網(wǎng)絡(luò)組件，則結(jié)束整個算法；如果G′不為空，結(jié)束條件不滿足，則算法將對最小生成樹的相關(guān)鏈路權(quán)值進行多次（M次）調(diào)整，嘗試產(chǎn)生最佳的下一個備份拓撲，可以盡可能多地保護尚未被孤立的鏈路和節(jié)點。權(quán)值調(diào)整具體方法為：對尚未被保護的鏈路權(quán)值增加一個任意值，那么調(diào)整后生成的最小生成樹就可以使該鏈路孤立出來；將之前備份拓撲連接到非孤立節(jié)點的某一條鏈路的權(quán)值設(shè)為一個更小的值，而與該節(jié)點相連的其他鏈路的權(quán)值設(shè)為一個更大的值，則在調(diào)整后生成的最小生成樹中該節(jié)點就會成為葉子節(jié)點。經(jīng)過M次調(diào)整后選取一組最佳權(quán)值，用于產(chǎn)生下一個備份拓撲，它能最大數(shù)目地保護尚未被孤立的鏈路和節(jié)點，最終減少備份拓撲的個數(shù)。最后，循環(huán)執(zhí)行直到獲得的備份拓撲集滿足要求為止，即所有的鏈路和節(jié)點都至少被一個備份拓撲保護。
3 算法仿真與性能分析
    對改進算法和傳統(tǒng)MRC算法在不同網(wǎng)絡(luò)拓撲模型中的表現(xiàn)進行仿真實驗，驗證其在減少備份拓撲個數(shù)和節(jié)省網(wǎng)絡(luò)存儲資源方面具有比較好的性能。實驗中采用的網(wǎng)絡(luò)拓撲模型是隨機型的Waxman模型和冪律型的BA模型。
    圖2和圖3是分別對Waxman模型和BA模型的拓撲實例進行仿真的結(jié)果。表明相同情況下，改進算法產(chǎn)生的備份拓撲總數(shù)一直都少于傳統(tǒng)MRC算法。網(wǎng)絡(luò)拓撲中節(jié)點數(shù)越多，這種差別越明顯。備份拓撲總數(shù)減少將對應(yīng)減少節(jié)點中存儲的轉(zhuǎn)發(fā)表項和網(wǎng)絡(luò)中的鏈路狀態(tài)信息報文，從而節(jié)省有限的存儲資源。

    結(jié)果還表明，無論是Waxman模型還是BA模型，隨著網(wǎng)絡(luò)中節(jié)點個數(shù)的增加，傳統(tǒng)算法生成的備份拓撲總數(shù)會同時增加很多，而改進算法中這種變化比較平緩。這是因為由傳統(tǒng)MRC算法相繼生成的備份拓撲中，孤立鏈路和孤立節(jié)點總是處在相鄰的位置上，其他不在此范圍內(nèi)的鏈路和節(jié)點要一直等到循環(huán)到達，才能被孤立出來。所以當(dāng)網(wǎng)絡(luò)規(guī)模擴大時，就需要生成更多的備份拓撲；而改進算法由最小生成樹盡最大可能孤立出所有鏈路和節(jié)點，其受網(wǎng)絡(luò)規(guī)模的影響較小，因此當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)增加時，算法生成的備份拓撲個數(shù)變化并不大。此外，雖然改進算法在兩個拓撲模型中都有良好的表現(xiàn)，但在BA模型中表現(xiàn)更好，這是由于兩種模型中節(jié)點度分布不同造成的。BA模型中節(jié)點度分布服從冪律分布特性，小部分節(jié)點需承擔(dān)大量的鏈路負載；Waxman模型中節(jié)點度的分布則比較均衡，而改進算法總是將度量值大的鏈路優(yōu)先孤立出來，故其在BA模型中表現(xiàn)更好。目前網(wǎng)絡(luò)服務(wù)提供商(ISP)的網(wǎng)絡(luò)拓撲大多服從冪律分布特性[5]，因此改進算法更適合應(yīng)用于實際網(wǎng)絡(luò)中。
    本文提出了一種改進的IP網(wǎng)絡(luò)多故障情況下的快速恢復(fù)算法，相比傳統(tǒng)MRC算法，它可以用較少的備份拓撲應(yīng)對同時發(fā)生的多個鏈路和節(jié)點故障，能有效節(jié)省網(wǎng)絡(luò)存儲資源，并且受網(wǎng)絡(luò)中節(jié)點個數(shù)變化的影響較小，在其生成的備份拓撲中應(yīng)用最短路徑算法就可以獲得每個節(jié)點對之間長度最短的傳輸路徑。該算法在服從冪律分布特性的實際大規(guī)模網(wǎng)絡(luò)中表現(xiàn)更優(yōu)，具有良好的實用價值。
參考文獻
[1] 張民貴，劉斌.IP網(wǎng)絡(luò)的快速故障恢復(fù)[J].電子學(xué)報，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.