一種改進的IP網(wǎng)絡快速恢復重路由算法

張莉敏 周錫玲 鄧怡辰 陳曉純

摘要： 針對IP網(wǎng)絡發(fā)生單個網(wǎng)絡組件（鏈路或節(jié)點）故障時，重路由花費（重路由數(shù)據(jù)包增加的跳數(shù)）增加的情況，提出了一種新的備份配置創(chuàng)建方法。主要思想是根據(jù)備份配置中節(jié)點的介數(shù)值（Betweenness）和親密度（Closeness）來定義關(guān)鍵節(jié)點，然后最大化關(guān)鍵節(jié)點的可用鏈路，從而減少最短路徑跳數(shù)。從仿真數(shù)據(jù)可得出，采用的改進算法對于較大型的網(wǎng)絡，考慮關(guān)鍵節(jié)點的位置并且使用Closeness算法選取關(guān)鍵節(jié)點能最大的減少重路由跳數(shù)。

關(guān)鍵詞： IP快速恢復；路由花費；重路由；備份配置；關(guān)鍵節(jié)點

中圖分類號：TP393 文獻標識碼：A

文章編號：1009-3044（2019）08-0126-03

An Improved Reroute Method for Fast IP Network Recovery

ZHANG Li-min， ZHOU Xi-ling， DENG Yi -chen，CHEN Xiao-chun

（Information Engineering，Guang Dong Polytechnic College ，Zhao qing 526100， China）

Abstract： IP fast reroute is based on two principles： local rerouting and precomputed reroute paths， when single network component （link or node） fails， routers are able to switch to an alternate path instantly. So this paper proposes a new backup topology design method. The main idea is to define the Key nodes according to the value of Betweenness Centrality and Closeness of nodes in backup topology， and then maximizes available links of Key nodes to reduce the number of hops in the shortest path. Two methods are adopted to select the key nodes： the first is Top K method， it is select K nodes with higher value of Betweenness and Closeness； the second method is Non-adjacent K method， when selecting the key nodes， considering the location of the key nodes， the adjacent nodes cannot be the used as the key nodes. The experimental results show that the proposed algorithm can achieve better results in large networks. For larger networks， considering the location of the key nodes and using the Closeness algorithm selected the key nodes can maximum reduce the number of hops.

Key words： IP fast reroute； routing cost； reroute； backup topology； key node

IP快速重路由是一種新的提高網(wǎng)絡可靠性和穩(wěn)定性的方法[1-2]。在網(wǎng)絡發(fā)生單個故障（鏈路或節(jié)點）后，它重路由數(shù)據(jù)流量到備份路由，而不必等待路由重收斂過程的完成。

為了能從單個組件（鏈路或節(jié)點）網(wǎng)絡故障快速恢復，多路由備份配置（MRC）方法也已經(jīng)被提出[3]。MRC的核心思想是為網(wǎng)絡的物理拓撲（或稱為原始拓撲）提前配置多個備份的拓撲，并計算相對應的備份路由。當數(shù)據(jù)包遇到故障時，故障ID標記到數(shù)據(jù)包頭部，并且采用與故障ID相對應的轉(zhuǎn)發(fā)表將數(shù)據(jù)包轉(zhuǎn)發(fā)到備份的下一跳[4-5]。

IP快速恢復主要是通過使用提前計算的備份配置減少重收斂時間。針對MRC算法的改進，文獻[6]提出IMRC算法，該算法增加了重路由時可使用的路徑數(shù)，從而降低恢復路徑的總跳數(shù)；文獻[7]提出在備份配置中生成最小生成數(shù)，減少路由跳數(shù)；文獻[8]給出了一種新的備份配置設計方案，將高負荷路徑的流量分離到其他可用路徑，同時兼顧網(wǎng)絡狀況，如流量矩陣或網(wǎng)絡拓撲。因為備份配置的減少會成功的減少轉(zhuǎn)發(fā)表的數(shù)量，但是備份配置數(shù)的減少也會造成網(wǎng)絡中某些鏈路負載過重，備份配置中的可用于備份路由的可用鏈路數(shù)量也會減少，這將造成重路由跳數(shù)的增加，重路由跳數(shù)的增加也會造成數(shù)據(jù)包延遲的增加。

針對上述問題，提出在備份配置創(chuàng)建過程中定義關(guān)鍵節(jié)點（Key node）[9]的方法來減少重路由跳數(shù)。主要思想是根據(jù)備份配置中節(jié)點的介數(shù)值（Betweenness）和親密度（Closeness）來定義關(guān)鍵節(jié)點，通過增加關(guān)鍵節(jié)點的可用鏈路，縮短最短路徑的跳數(shù)。選擇關(guān)鍵節(jié)點時考慮節(jié)點的位置，相鄰的節(jié)點不能同為關(guān)鍵節(jié)點。

1 多路由備份配置

本小節(jié)描述了使用MRC算法創(chuàng)建備份配置的特征，說明了如何使用備份配置進行IP網(wǎng)絡快速恢復，并且討論了使用該算法所存在的問題。

1.1 備份配置的創(chuàng)建

如圖1所示，表示的最初網(wǎng)絡拓撲和由原始備份配置算法產(chǎn)生的三個備份配置。每一個備份配置包括兩種節(jié)點（如圖中的圓形所示）和兩種鏈路（如圖中的連接線所示）。其中孤立節(jié)點和受保護的鏈路不用來轉(zhuǎn)發(fā)數(shù)據(jù)包。為保證所產(chǎn)生的備份配置能從單一網(wǎng)絡組件故障中快速恢復，該配置應該符合以下條件：

（1）必須包含每一個節(jié)點，并且任意兩個節(jié)點間需有一條可用鏈路。

（2）原始拓撲中的所有鏈路和節(jié)點至少在一個備份配置（backup configuration， BC）中孤立一次。

如果備份配置滿足以上的特征，將會確保每一條鏈路至少在一個備份配置中受保護。

1.2 數(shù)據(jù)包重路由過程

在MRC算法中，通常存儲兩種路由表來傳輸數(shù)據(jù)：正常路由表和備份路由表。具體路由過程已在之前工作文獻[7]中詳細寫出。此處，以圖1為例說明。假如數(shù)據(jù)包從節(jié)點1發(fā)送到節(jié)點6，路徑1-4不可用。正常情況下從節(jié)點1到節(jié)點6的最短路徑是1→4→6，當節(jié)點1收到來自上層的數(shù)據(jù)包，它會在數(shù)據(jù)包的頭部標記0，根據(jù)最短路徑，將數(shù)據(jù)包發(fā)送給節(jié)點4。當數(shù)據(jù)包到達節(jié)點4，因為路徑1-4不可用，并且節(jié)點6是目的節(jié)點，所以節(jié)點4將會選擇節(jié)點6和鏈路4-6受保護的備份配置進行重路由，即BC3。然后，它會在數(shù)據(jù)包的頭部標記3，數(shù)據(jù)包會轉(zhuǎn)發(fā)到節(jié)點2，因為在BC3中，從節(jié)點4到節(jié)點6的最短路徑為4→2→5→6。如此反復，數(shù)據(jù)包轉(zhuǎn)發(fā)到節(jié)點6。因此新的轉(zhuǎn)發(fā)路徑為1→4→2→5→6。

1.3 MRC算法出現(xiàn)的問題

在MRC方法中，如前面所描述，在正常情況下如果數(shù)據(jù)包不經(jīng)過故障鏈路，則在故障狀態(tài)下這些數(shù)據(jù)包的重路由跳數(shù)保持不變。相反地，如果在正常情況下數(shù)據(jù)包經(jīng)過故障鏈路，則在故障狀態(tài)下這些數(shù)據(jù)包重路由跳數(shù)會增加。路由跳數(shù)的增加將導致數(shù)據(jù)流量增多和包傳輸延遲的增大。故而，研究的目標是要盡量縮短重路由增加的總跳數(shù)。

2新的備份配置創(chuàng)建算法

2.1 關(guān)鍵節(jié)點選取

文章所提算法的主要思想就是在備份配置創(chuàng)建的過程中使用關(guān)鍵節(jié)點，通過增加關(guān)鍵節(jié)點的可用鏈路來縮短最短路徑的跳數(shù)?；诰W(wǎng)絡環(huán)境，我們有兩種定義關(guān)鍵節(jié)點[10]的方法：介數(shù)中心性排序法和親密度排序法。

（1）介數(shù)中心性排序法。在這個方法中，基于網(wǎng)絡結(jié)構(gòu)定義關(guān)鍵節(jié)點。節(jié)點v的介數(shù)中心性[Bv]表示所有通過節(jié)點v的最短傳輸跳數(shù)與總的最短傳輸跳數(shù)的比值。另外，[σst]定義為從s到t的最短傳輸跳數(shù)，[σst（v）] 定義為從源端s到目的端t并且經(jīng)過節(jié)點v的最短傳輸跳數(shù)。[Bv]定義如公式1，其中n 代表拓拓撲中節(jié)點的數(shù)量。

[Bv=snt，t≠snσstvσst] （1）

（2）親密度排序法。在此方法中，節(jié)點p的親密度（[Cp]）代表的是從點p到拓撲中其他點的最短傳輸跳數(shù)總和的倒數(shù)。[Cp]定義如公式2，其中n 為拓撲中節(jié)點的數(shù)量。[dpi，pk]是從某一點[pi]到某點[pk]的最小路線跳數(shù)。親密度表示了某點相比拓撲中剩余節(jié)點居于中心的水平。

[Cp=1/i=1，i≠kndpi，pk] （2）

2.2算法流程

算法輸入變量是關(guān)鍵節(jié)點的數(shù)量K，輸出變量是備份配置數(shù)量N。初始時，N定義為1，然后算法從步驟1到步驟5連續(xù)執(zhí)行。

步驟1：根據(jù)2.1所提的兩種方法來定義關(guān)鍵節(jié)點。

步驟2：選取K個關(guān)鍵節(jié)點， Non-adjacent K方法：使用此方法選取關(guān)鍵節(jié)點，既要具有較高的介數(shù)值（或親密度值），同時還要兼顧到關(guān)鍵節(jié)點在拓撲中位置信息。如果當前選擇的關(guān)鍵節(jié)點與之前選取的關(guān)鍵節(jié)點相鄰，則跳過當前這個節(jié)點，順序地選取下一個節(jié)點作為關(guān)鍵節(jié)點。

步驟3：與關(guān)鍵節(jié)點連接的路徑的保護過程。與關(guān)鍵節(jié)點相連的受保護鏈路在每個備份配置中的數(shù)量定義為M，關(guān)鍵節(jié)點的最大出入度定義為D，則M的最大整數(shù)值小于等于ceil（D/N）+1（ceil表示向上取整）。

步驟4：執(zhí)行其他普通節(jié)點的鏈路保護過程。按原始的MRC方法，執(zhí)行鏈路保護過程。

步驟5：判斷改進的備份配置是否滿足2.1節(jié)所提出的備份配置創(chuàng)建規(guī)則。如果滿足，則算法結(jié)束。否則，N的值加1，然后繼續(xù)從步驟1執(zhí)行。

3仿真分析

3.1 實驗環(huán)境

為了測試所提方法在單鏈路故障后對重路由總跳數(shù)的影響，仿真是在網(wǎng)絡拓撲結(jié)構(gòu)COST 239和COST 266進行，拓撲圖連接了歐洲主要的城市。實驗評估的參數(shù)是在所有單鏈路故障情況下，數(shù)據(jù)包重路由跳數(shù)隨K值變化的情況。通常情況下鏈路cost值設成1，除了備份配置中孤立的鏈路。

3.2 路由結(jié)果

圖2和圖3分別顯示了在Non-adjacent K方法下，COST 239模型和COST 266模型中路由總跳數(shù)隨K值變化的情況。其中，COST 239備份配置數(shù)N是3，COST 266備份配置數(shù)是4。

如圖2所示，對于COST 239模型，在Non-adjacent K算法中，減少的最大總跳數(shù)是：Betweennes=20， Closeness=33。從結(jié)果可知，在備份配置中確定關(guān)鍵節(jié)點并且最大化關(guān)鍵節(jié)點的可用鏈路數(shù)是可行的。當使用Non- adjacent K方法時， Closeness 算法相比Betweenness算法能更高的減少重路由跳數(shù)。

圖3 表示COST 266模型使用Non-adjacent K方法的結(jié)果。在Non-adjacent K算法下選取關(guān)鍵節(jié)點，使用Betweennes方法減少的最大總跳數(shù)是1198，使用Closeness方法減少的最大總跳數(shù)是6439。從結(jié)果可知，在COST 266模型中，使用改進后的備份配置，能更好地減少路徑跳數(shù)。因為COST 266模型擁有較多的節(jié)點，選取相鄰節(jié)點作為關(guān)鍵節(jié)點的可能性較高并且不能最大化可用鏈路。且Closeness算法比Betweennes算法有更好的效果。由此可以得出，對于較大的網(wǎng)絡，考慮關(guān)鍵節(jié)點的位置，使用Closeness算法選取關(guān)鍵節(jié)點是較好的策略。

3.3 對比分析

基于以上的實驗環(huán)境，將改進算法與文獻[6]中所提IMRC算法進行對比。在單故障情況下，IMRC算法提出使用孤立的非故障鏈路，增加重路由過程中的可用鏈路數(shù)，從而減少替換路徑的總跳數(shù)。實驗評估是在單鏈路故障狀態(tài)下，使用Non-adjacent K算法， IMRC算法后，COST 266模型中所有節(jié)點對之間的總跳數(shù)。

如圖4 所示，在COST 266模型中，路由總跳數(shù)都有明顯的降低，并且在Non-adjacent K算法中，鏈路9故障時，路由總跳數(shù)可以減少42%。由以上結(jié)果可以得知，所提算法在大型網(wǎng)絡中有很好的應用，能減少單組件故障時所增加的路由跳數(shù)。并且，Non-adjacent K算法是較好的選擇策略。

4 總結(jié)

文中提出了一種新的備份配置設計算法來減少IP快速重路由過程中增加的路由跳數(shù)，我們的算法可以在不增加備份配置的前提下減少總路由跳數(shù)。所提方法的主要思想是在備份配置創(chuàng)建的過程中引入關(guān)鍵節(jié)點的概念，比較在不同關(guān)鍵節(jié)點數(shù)量情況下，網(wǎng)絡發(fā)生單故障后重路由路徑總跳數(shù)。仿真實驗可得出，改進的備份配置設計方法在大型網(wǎng)絡中能取得較好的效果。對于較大的網(wǎng)絡，考慮關(guān)鍵節(jié)點的位置并且使用Closeness算法選取關(guān)鍵節(jié)點能最大的減少重路由跳數(shù)。

未來的工作，我們希望使用新的備份配置創(chuàng)建算法進行多故障快速恢復并且實現(xiàn)最小的路由花費。

參考文獻：

[1] Shand M，Bryant S. IP Fast Reroute Framework[J]. IETF RFC 5714，2010，4（4）：206-207.

[2] 余學杰.對TCP/IP計算機網(wǎng)絡擁塞控制的研究[J].現(xiàn)代電子技術(shù)，2014，37（15）：38-40.

[3] Kvalbein A F. Hansen， T. Cicic， et al， Multiple routing configurations for fast IP network recovery[J]. IEEE/ACM Transactions on Networking （TON）， 2009，17（2）：473-486.

[4] 張莉敏，王輝，李沛諭， 等.基于多路由配置的數(shù)據(jù)中心網(wǎng)絡故障恢復研究[J].計算機應用與軟件， 2017，34（3）： 289-293，328.

[5] 郭帥，李沛諭，王輝， 等.基于LFA的IP網(wǎng)絡快速恢復算法[J].計算機工程與設計，2017，38（4）：878-882.

[6] Daiki Imahama， Yukinobu Fukushima， Tokumi Yokohira. A Reroute Method Using Multiple Routing Configurations for Fast IP Network Recovery，APCC 2013：439-444.

[7] Kamamura S， Miyamura T， Pelsser C I. Inoue， and K.Shiomoto. Minimum Backup Configurations Creation Method for IP Fast Reroute[C]. Proceedings of GLOBE COM-2009 IEEE Global Telecommunications Conference. IEEE， Honolulu， 2009：1-6.

[8] 陳榮慶，黃艷紅.一種改進的IP網(wǎng)絡多故障快速恢復算法[J].微型機與應用，2013，32（14）：53-55.

[9] 荊云. 復雜網(wǎng)絡重要節(jié)點識別方法研究[D].河南師范大學，2017.

[10] 南棟卿. 復雜網(wǎng)絡中關(guān)鍵節(jié)點的識別研究[D].吉林大學，2016.

【通聯(lián)編輯：唐一東】