一種改進(jìn)的IP網(wǎng)絡(luò)多故障快速恢復(fù)算法

陳榮慶，黃艷紅

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

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

1 兩種主要的多故障快速恢復(fù)算法

目前，在IP網(wǎng)絡(luò)中處理多故障快速恢復(fù)問(wèn)題的方法主要是先應(yīng)式的多拓?fù)洌∕T）技術(shù)，基本思想是由網(wǎng)絡(luò)原始拓?fù)鋱D生成多個(gè)備份拓?fù)鋪?lái)保護(hù)所有鏈路和節(jié)點(diǎn)。如果某些鏈路和節(jié)點(diǎn)同時(shí)發(fā)生故障，則快速切換到能保護(hù)這些組件的備份拓?fù)?，被保護(hù)的網(wǎng)絡(luò)組件在對(duì)應(yīng)的備份拓?fù)渲胁粫?huì)轉(zhuǎn)發(fā)任何數(shù)據(jù)流，從而實(shí)現(xiàn)故障時(shí)數(shù)據(jù)流的正常傳輸。該技術(shù)的重點(diǎn)是如何根據(jù)網(wǎng)絡(luò)原始拓?fù)鋱D構(gòu)建備份拓?fù)浼?，使得其中包含的備份拓?fù)鋽?shù)量盡可能少，并且每個(gè)節(jié)點(diǎn)對(duì)之間的最佳傳輸路徑長(zhǎng)度盡可能短。

1.1 彈性路由層算法

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

1.2 多路由配置算法

MRC算法基于“配置圖”描述備份拓?fù)?，每個(gè)圖包含有正常鏈路、孤立鏈路、受限鏈路和正常節(jié)點(diǎn)、孤立節(jié)點(diǎn)。算法中孤立鏈路被賦予一個(gè)無(wú)窮大的度量值，故其在對(duì)應(yīng)的備份拓?fù)渲胁粫?huì)被用來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)流。受限鏈路被賦予一個(gè)有限但很大的度量值，其在對(duì)應(yīng)的備份拓?fù)渲袃H能作為第一跳或最后一跳鏈路接收和發(fā)送數(shù)據(jù)[4]。只有孤立鏈路和受限鏈路才可以連接到孤立節(jié)點(diǎn)。算法的實(shí)現(xiàn)過(guò)程是通過(guò)將前一個(gè)備份拓?fù)渲泄铝⒐?jié)點(diǎn)連接的受限鏈路和其對(duì)端節(jié)點(diǎn)，在下一個(gè)備份拓?fù)渲泄铝⒊鰜?lái)，如此循環(huán)直到每個(gè)網(wǎng)絡(luò)組件都被孤立出來(lái)為止。

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

2 算法改進(jìn)

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

算法先初始化所有參數(shù)，隨機(jī)產(chǎn)生一組用于生成最小生成樹(shù)的鏈路權(quán)值集。該鏈路權(quán)值與鏈路度量值不同，因?yàn)楦倪M(jìn)算法中第一個(gè)最小生成樹(shù)將影響以后創(chuàng)建備份拓?fù)?，如果由鏈路度量值決定權(quán)值，那么只能生成一個(gè)確定的最小生成樹(shù)，而它可能并不適合用來(lái)創(chuàng)建其他備份拓?fù)洌赃@里使用一組隨機(jī)產(chǎn)生的鏈路權(quán)值來(lái)生成最小生成樹(shù)，如果它不適合用來(lái)進(jìn)一步創(chuàng)建其他備份拓?fù)?，就循環(huán)執(zhí)行整個(gè)算法，隨機(jī)產(chǎn)生另外一組合適的鏈路初始權(quán)值集來(lái)生成最小生成樹(shù)。

圖1 改進(jìn)算法實(shí)現(xiàn)流程圖

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

3 算法仿真與性能分析

對(duì)改進(jìn)算法和傳統(tǒng)MRC算法在不同網(wǎng)絡(luò)拓?fù)淠Ｐ椭械谋憩F(xiàn)進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證其在減少備份拓?fù)鋫€(gè)數(shù)和節(jié)省網(wǎng)絡(luò)存儲(chǔ)資源方面具有比較好的性能。實(shí)驗(yàn)中采用的網(wǎng)絡(luò)拓?fù)淠Ｐ褪请S機(jī)型的Waxman模型和冪律型的BA模型。

圖2和圖3是分別對(duì)Waxman模型和BA模型的拓?fù)鋵?shí)例進(jìn)行仿真的結(jié)果。表明相同情況下，改進(jìn)算法產(chǎn)生的備份拓?fù)淇倲?shù)一直都少于傳統(tǒng)MRC算法。網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)數(shù)越多，這種差別越明顯。備份拓?fù)淇倲?shù)減少將對(duì)應(yīng)減少節(jié)點(diǎn)中存儲(chǔ)的轉(zhuǎn)發(fā)表項(xiàng)和網(wǎng)絡(luò)中的鏈路狀態(tài)信息報(bào)文，從而節(jié)省有限的存儲(chǔ)資源。

結(jié)果還表明，無(wú)論是Waxman模型還是BA模型，隨著網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)的增加，傳統(tǒng)算法生成的備份拓?fù)淇倲?shù)會(huì)同時(shí)增加很多，而改進(jìn)算法中這種變化比較平緩。這是因?yàn)橛蓚鹘y(tǒng)MRC算法相繼生成的備份拓?fù)渲?，孤立鏈路和孤立?jié)點(diǎn)總是處在相鄰的位置上，其他不在此范圍內(nèi)的鏈路和節(jié)點(diǎn)要一直等到循環(huán)到達(dá)，才能被孤立出來(lái)。所以當(dāng)網(wǎng)絡(luò)規(guī)模擴(kuò)大時(shí)，就需要生成更多的備份拓?fù)洌欢倪M(jìn)算法由最小生成樹(shù)盡最大可能孤立出所有鏈路和節(jié)點(diǎn)，其受網(wǎng)絡(luò)規(guī)模的影響較小，因此當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)增加時(shí)，算法生成的備份拓?fù)鋫€(gè)數(shù)變化并不大。此外，雖然改進(jìn)算法在兩個(gè)拓?fù)淠Ｐ椭卸加辛己玫谋憩F(xiàn)，但在BA模型中表現(xiàn)更好，這是由于兩種模型中節(jié)點(diǎn)度分布不同造成的。BA模型中節(jié)點(diǎn)度分布服從冪律分布特性，小部分節(jié)點(diǎn)需承擔(dān)大量的鏈路負(fù)載；Waxman模型中節(jié)點(diǎn)度的分布則比較均衡，而改進(jìn)算法總是將度量值大的鏈路優(yōu)先孤立出來(lái)，故其在BA模型中表現(xiàn)更好。目前網(wǎng)絡(luò)服務(wù)提供商(ISP)的網(wǎng)絡(luò)拓?fù)浯蠖喾膬缏煞植继匦訹5]，因此改進(jìn)算法更適合應(yīng)用于實(shí)際網(wǎng)絡(luò)中。

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

[1]張民貴，劉斌.IP網(wǎng)絡(luò)的快速故障恢復(fù)[J].電子學(xué)報(bào)，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.