摘  要： 隨著網絡承載數據量的不斷增加和實時業務的迅速發展，要求網絡故障的恢復時間越來越短，而傳統路由協議收斂時間過長，已不能滿足其要求，并且多故障同時發生的情況也在增多，這些都影響了IP網絡的穩定運行，嚴重時甚至會造成一定的經濟損失。提出一種改進的IP網絡多故障情況下的快速恢復算法，可以用少量的備份拓撲應對同時發生的多個鏈路和節點故障。與傳統算法相比，有效節省了網絡存儲資源，增強了網絡的可擴展性，具有良好的實用價值。
關鍵詞： IP網絡；故障恢復；MRC；備份拓撲

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

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

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