《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 一種改進(jìn)的IP網(wǎng)絡(luò)多故障快速恢復(fù)算法
一種改進(jìn)的IP網(wǎng)絡(luò)多故障快速恢復(fù)算法
來(lái)源:微型機(jī)與應(yīng)用2013年第14期
陳榮慶1,黃艷紅2
(1.泰州市海陵區(qū)經(jīng)濟(jì)和信息化委員會(huì),江蘇 泰州225300;2.華碩科技有限公司,浙江 杭州310
摘要: 隨著網(wǎng)絡(luò)承載數(shù)據(jù)量的不斷增加和實(shí)時(shí)業(yè)務(wù)的迅速發(fā)展,要求網(wǎng)絡(luò)故障的恢復(fù)時(shí)間越來(lái)越短,而傳統(tǒng)路由協(xié)議收斂時(shí)間過長(zhǎng),已不能滿足其要求,并且多故障同時(shí)發(fā)生的情況也在增多,這些都影響了IP網(wǎng)絡(luò)的穩(wěn)定運(yùn)行,嚴(yán)重時(shí)甚至?xí)斐梢欢ǖ慕?jīng)濟(jì)損失。提出一種改進(jìn)的IP網(wǎng)絡(luò)多故障情況下的快速恢復(fù)算法,可以用少量的備份拓?fù)鋺?yīng)對(duì)同時(shí)發(fā)生的多個(gè)鏈路和節(jié)點(diǎn)故障。與傳統(tǒng)算法相比,有效節(jié)省了網(wǎng)絡(luò)存儲(chǔ)資源,增強(qiáng)了網(wǎng)絡(luò)的可擴(kuò)展性,具有良好的實(shí)用價(jià)值。
Abstract:
Key words :

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

    互聯(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ù)問題的方法主要是先應(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)過程是通過將前一個(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)過故障部件,相比RRL算法簡(jiǎn)單可行。但是MRC算法生成的備份拓?fù)鋽?shù)量過多,造成相應(yīng)的轉(zhuǎn)發(fā)表項(xiàng)和鏈路狀態(tài)信息報(bào)文過多,消耗大量的存儲(chǔ)資源,在網(wǎng)絡(luò)規(guī)模較大時(shí),節(jié)點(diǎn)不能存儲(chǔ)所有的備份拓?fù)湫畔?,從而影響網(wǎng)絡(luò)的擴(kuò)展性。
2 算法改進(jìn)
    針對(duì)MRC算法存在的問題提出一種改進(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)生一組用于生成最小生成樹的鏈路權(quán)值集。該鏈路權(quán)值與鏈路度量值不同,因?yàn)楦倪M(jìn)算法中第一個(gè)最小生成樹將影響以后創(chuàng)建備份拓?fù)?,如果由鏈路度量值決定權(quán)值,那么只能生成一個(gè)確定的最小生成樹,而它可能并不適合用來(lái)創(chuàng)建其他備份拓?fù)?,所以這里使用一組隨機(jī)產(chǎn)生的鏈路權(quán)值來(lái)生成最小生成樹,如果它不適合用來(lái)進(jìn)一步創(chuàng)建其他備份拓?fù)?,就循環(huán)執(zhí)行整個(gè)算法,隨機(jī)產(chǎn)生另外一組合適的鏈路初始權(quán)值集來(lái)生成最小生成樹。
    初始化完成后,會(huì)得到一個(gè)最小生成樹,一部分權(quán)值較大的鏈路被分離出來(lái),將其設(shè)為孤立鏈路(鏈路的度量值設(shè)為無(wú)窮大值),最小生成樹的葉子節(jié)點(diǎn)設(shè)為孤立節(jié)點(diǎn),與孤立節(jié)點(diǎn)相連的鏈路設(shè)為受限鏈路(鏈路的度量值設(shè)為一個(gè)有限但很大的值)。由此,依據(jù)原始拓?fù)鋱D的最小生成樹就可以得到第一個(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ì)最小生成樹的相關(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)整后生成的最小生成樹就可以使該鏈路孤立出來(lái);將之前備份拓?fù)溥B接到非孤立節(jié)點(diǎn)的某一條鏈路的權(quán)值設(shè)為一個(gè)更小的值,而與該節(jié)點(diǎn)相連的其他鏈路的權(quán)值設(shè)為一個(gè)更大的值,則在調(diào)整后生成的最小生成樹中該節(jié)點(diǎn)就會(huì)成為葉子節(jié)點(diǎn)。經(jīng)過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ù)浔Wo(hù)。
3 算法仿真與性能分析
    對(duì)改進(jìn)算法和傳統(tǒng)MRC算法在不同網(wǎng)絡(luò)拓?fù)淠P椭械谋憩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ù)淠P褪请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ù)?;而改進(jìn)算法由最小生成樹盡最大可能孤立出所有鏈路和節(jié)點(diǎn),其受網(wǎng)絡(luò)規(guī)模的影響較小,因此當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)增加時(shí),算法生成的備份拓?fù)鋫€(gè)數(shù)變化并不大。此外,雖然改進(jìn)算法在兩個(gè)拓?fù)淠P椭卸加辛己玫谋憩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à)值。
參考文獻(xiàn)
[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.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。