基于逐跳轉(zhuǎn)發(fā)方式的單故障路由保護(hù)方法

摘 要：業(yè)界提出利用LFA（loop free alternates）方案來(lái)應(yīng)對(duì)網(wǎng)絡(luò)中頻繁出現(xiàn)的故障，然而LFA并不能保護(hù)網(wǎng)絡(luò)中所有可能出現(xiàn)的單故障情形。針對(duì)上述問(wèn)題，提出了一種基于逐跳轉(zhuǎn)發(fā)方式的單故障路由保護(hù)算法SFRPA（single failure routing protection algorithm based on hop by hop forwarding）。SFRPA首先提出了三個(gè)無(wú)環(huán)路備份下一跳選取規(guī)則，然后制定了優(yōu)先級(jí)隊(duì)列的操作規(guī)則，最后利用優(yōu)先級(jí)隊(duì)列和無(wú)環(huán)路備份下一跳選取規(guī)則為所有源目的節(jié)點(diǎn)對(duì)計(jì)算出一個(gè)最優(yōu)的備份下一跳。該算法具有支持逐跳轉(zhuǎn)發(fā)、支持增量部署、保護(hù)網(wǎng)絡(luò)中所有可能的單故障情形三個(gè)特征。實(shí)驗(yàn)結(jié)果表明，與經(jīng)典的路由保護(hù)方案LFA、DMPA、TBFH和IAC相比較，SFRPA不僅可以應(yīng)對(duì)網(wǎng)絡(luò)中所有可能的單故障情形，并且具有較小的路徑拉伸度。

關(guān)鍵詞：路由可用性；單故障；路由保護(hù)算法；實(shí)時(shí)應(yīng)用；路徑拉伸度

中圖分類(lèi)號(hào)：TP309.7 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）11-039-3444-06

doi：10.19734/j.issn.1001-3695.2022.04.0153

Single failure routing protection algorithm based on hop by hop forwarding

Guo Xumin¹，Geng Haijun²，Zong Chunmei³

（1.Dept. of Computer amp; Information Engineering，Shanxi Youth Vocational College，Taiyuan 030032，China；2.School of Automation amp; Software Engineering，Shanxi University，Taiyuan 030006，China；3.Dept. of Computer Science，Xinzhou Teachers University，Xinzhou Shanxi 034000，China）

Abstract：The industry proposes to use the LFA scheme to cope with the frequent failures in the network.However，LFA cannot protect all possible single failure scenarios in the network.In response to the above problem，this paper proposed SFRPA.SFRPA firstly proposed three loop-free backup next-hop selection rules，and then formulated the operation rules for priority queues.Finally，it used the priority queue and loop-free backup next-hop selection rules to calculate an optimal backup next hop for all source-destination pairs.The algorithm had the following characteristics：supports hop by hop forwarding，supports incremental deployment，and protects all possible single failure scenarios in the network.The experimental results show that compared with the classical routing protection schemes LFA，DMPA，TBFH and IAC，SFRPA can not only deal with all possible single failure situations in the network，but also has less path stretch.

Key words：routing availability；single failure；routing protection algorithm；real-time applications；path stretch

基金項(xiàng)目：山西省應(yīng)用基礎(chǔ)研究計(jì)劃資助項(xiàng)目（20210302123444）；中國(guó)高校產(chǎn)學(xué)研創(chuàng)新基金資助項(xiàng)目（2021FNA02009）；國(guó)家自然科學(xué)基金資助項(xiàng)目（61702315）；山西省重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目（201903D421003）；國(guó)家“863”計(jì)劃資助項(xiàng)目（2018YFB1800401）

作者簡(jiǎn)介：郭旭敏（1987-），男，山西運(yùn)城人，講師，碩士，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、大數(shù)據(jù)和網(wǎng)絡(luò)安全；耿海軍（1983-），男（通信作者），山西太原人，副教授，博士，主要研究方向?yàn)榫W(wǎng)絡(luò)體系結(jié)構(gòu)和路由算法（ghj123025449@163.com）；宗春梅（1977-），女，山西忻州人，講師，碩士，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)和機(jī)器學(xué)習(xí).

0 引言

互聯(lián)網(wǎng)最初僅僅由四個(gè)節(jié)點(diǎn)組成，在短短三十幾年的時(shí)間內(nèi)迅速發(fā)展成為了一個(gè)全球性的基礎(chǔ)平臺(tái)^［1］。互聯(lián)網(wǎng)中的路由技術(shù)和互聯(lián)網(wǎng)產(chǎn)業(yè)得到了飛速的發(fā)展，部署在互聯(lián)網(wǎng)中的應(yīng)用^［2］發(fā)生了翻天覆地的變化。

隨著互聯(lián)網(wǎng)的快速發(fā)展和規(guī)模的逐步擴(kuò)大，互聯(lián)網(wǎng)中自治系統(tǒng)的規(guī)模和數(shù)量急劇增長(zhǎng)，域內(nèi)路由出現(xiàn)了很多需要解決的問(wèn)題，其中路由可用性問(wèn)題顯得尤為突出^［3～5］。研究者對(duì)網(wǎng)絡(luò)中的故障規(guī)律進(jìn)行了大量的研究，研究結(jié)果表明^［6］網(wǎng)絡(luò)中的故障頻繁出現(xiàn)，并且不可避免。當(dāng)網(wǎng)絡(luò)故障發(fā)生時(shí)，互聯(lián)網(wǎng)部署的傳統(tǒng)路由協(xié)議需要經(jīng)歷一個(gè)漫長(zhǎng)的收斂過(guò)程，無(wú)法在50 ms的時(shí)間內(nèi)完成收斂，很難滿足實(shí)時(shí)應(yīng)用對(duì)網(wǎng)絡(luò)收斂時(shí)間的要求^［7］。因此，當(dāng)網(wǎng)絡(luò)故障出現(xiàn)時(shí)，可能導(dǎo)致ISP無(wú)法提供承諾的服務(wù)質(zhì)量，進(jìn)而影響其聲譽(yù)和收益。

學(xué)術(shù)界和工業(yè)界普遍采用路由保護(hù)方案^［8，9］來(lái)應(yīng)對(duì)網(wǎng)絡(luò)中頻繁發(fā)生的故障。等價(jià)多路徑路由（equal-cost multipath routing，ECMP）是業(yè)界最早采用的一種最簡(jiǎn)單的路由保護(hù)方案，但是研究證實(shí)該方案無(wú)法提供較高的故障保護(hù)率^［10］。針對(duì)ECMP存在的問(wèn)題，國(guó)際互聯(lián)網(wǎng)工程任務(wù)組（Internet Enginee-ring Task Force，IETF）發(fā)布了快速重路由的框架，在該框架的基礎(chǔ)上提出了LFA^［11］、基于Not-Via的路由保護(hù)方案^［12］和基于隧道的路由保護(hù)方案^［13］等。在已經(jīng)提出的路由保護(hù)方案中，LFA得到了業(yè)界的高度關(guān)注和認(rèn)可，并且已經(jīng)部署在商業(yè)路由器中。LFA雖然得到了路由器廠商的部署，但是故障保護(hù)率較低，無(wú)法滿足實(shí)時(shí)應(yīng)用的需求。TBFH（two best first hop disjoint paths）^［14］和DMPA（dynamic distributed multipath algorithm）^［15］雖然降低了部署LFA開(kāi)銷(xiāo)，但是依然無(wú)法提高LFA的故障保護(hù)率。為了提高LFA的故障保護(hù)率，文獻(xiàn)［16］首先將該問(wèn)題描述為一個(gè)線性規(guī)劃模型，然后利用啟發(fā)式算法調(diào)整網(wǎng)絡(luò)中鏈路的代價(jià)，從而大大提高了LFA的故障保護(hù)率，但是依然無(wú)法達(dá)到100%的單故障保護(hù)率。為了解決文獻(xiàn)［16］存在的問(wèn)題，本文首先研究了LFA的故障保護(hù)率和網(wǎng)絡(luò)拓?fù)渲g的關(guān)系模型，然后通過(guò)增加鏈路來(lái)提高LFA的故障保護(hù)率。實(shí)驗(yàn)結(jié)果表明，僅僅需要在網(wǎng)絡(luò)中增加少量的鏈路就可以達(dá)到100%的單故障保護(hù)率。但是該方法需要增加鏈路，對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的改動(dòng)較大，不易于實(shí)際部署。基于Not-Via地址的快速重路由算法可以保護(hù)網(wǎng)絡(luò)中所有可能的單故障情形，但是該方法需要借助Not-Via地址，計(jì)算和存儲(chǔ)開(kāi)銷(xiāo)較大，因此很難得到ISP的支持。

以上介紹的路由保護(hù)方案要么無(wú)法保護(hù)網(wǎng)絡(luò)中所有的單故障情形，要么實(shí)現(xiàn)復(fù)雜，不支持增量部署，因此無(wú)法得到ISP的大規(guī)模部署。LFA雖然得到了業(yè)界的支持，但是只能提供50%左右的故障保護(hù)率。Not-Via雖然能夠提供100%的單故障保護(hù)率，但是需要輔助機(jī)制的協(xié)助，不支持增量部署。FCP^［17］（failure carrying packet）記錄報(bào)文轉(zhuǎn)發(fā)過(guò)程中遇到的故障，當(dāng)路由器接收到報(bào)文時(shí)，利用報(bào)文頭部的故障信息生成新的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，利用該新拓?fù)浣Y(jié)構(gòu)計(jì)算新的最短路徑，從而保證報(bào)文的正確轉(zhuǎn)發(fā)。但是FCP對(duì)目前互聯(lián)網(wǎng)部署的路由協(xié)議的改動(dòng)過(guò)大，無(wú)法實(shí)際部署。

因此，本文主要關(guān)注如何設(shè)計(jì)一種路由保護(hù)方法，該方法不僅支持增量部署，并且可以保護(hù)網(wǎng)絡(luò)中所有可能的單故障情形。本文的主要貢獻(xiàn)可以總結(jié)為：a）提出了三個(gè)備份下一跳選取規(guī)則；b）基于備份下一跳選取規(guī)則，提出了一種基于逐跳轉(zhuǎn)發(fā)的單故障路由保護(hù)算法SFRPA；c）在大量的真實(shí)拓?fù)洹⒛M拓?fù)浜蜕赏負(fù)渖向?yàn)證了算法SFRPA的故障保護(hù)率和路徑拉伸度性能。

SFRPA充分考慮了已有路由保護(hù)方案存在的故障保護(hù)率較低的問(wèn)題，在不改變已有路由協(xié)議的基礎(chǔ)上提出了三種無(wú)環(huán)路備份下一跳選擇規(guī)則，利用這些規(guī)則可以為所有源目的對(duì)計(jì)算出相應(yīng)的備份一跳。當(dāng)網(wǎng)絡(luò)中出現(xiàn)單故障情形時(shí)，受該故障影響的源目的節(jié)點(diǎn)利用報(bào)文轉(zhuǎn)發(fā)規(guī)則依然可以將報(bào)文順利地轉(zhuǎn)發(fā)到目的地址，大大提高了網(wǎng)絡(luò)的可用性。

1 網(wǎng)絡(luò)模型和問(wèn)題描述

1.1 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)可以用無(wú)向圖G=（V，E）來(lái)表示，其中V代表該圖中節(jié)點(diǎn)（路由器）的集合，E代表該圖中邊（鏈路）的集合。w（u，v）表示鏈路（u，v）∈E的代價(jià)，該代價(jià)可以是時(shí)延、跳數(shù)或者鏈路可靠性等。互聯(lián)網(wǎng)服務(wù)提供商將根據(jù)用戶的需求選擇相應(yīng)的代價(jià)。對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)u∈V，ID（u）表示節(jié)點(diǎn)u的標(biāo)識(shí)，或者稱為路由器ID；N（u）表示節(jié)點(diǎn)u的所有鄰居節(jié)點(diǎn)的集合。對(duì)于網(wǎng)絡(luò)中的任意兩個(gè)節(jié)點(diǎn)x和y，sp（x，y）表示節(jié)點(diǎn)x到y(tǒng)的最短路徑包含的鏈路的集合，cost（x，y）表示節(jié)點(diǎn)x到y(tǒng)的最短路徑對(duì)應(yīng)的代價(jià)。下面給出一些定義，包括最優(yōu)路由樹(shù)、跳數(shù)、祖先節(jié)點(diǎn)、父親節(jié)點(diǎn)和故障保護(hù)率等。

定義1 給定一個(gè)網(wǎng)絡(luò)拓?fù)銰=（V，E），對(duì)于該圖中的任意節(jié)點(diǎn)d∈V，稱T_d（V，E_d）是以節(jié)點(diǎn)d為根的最優(yōu)路由樹(shù)，當(dāng)且僅當(dāng)滿足下面兩個(gè)條件：a）E_dE，|E_d|=|V|-1；b）對(duì)于樹(shù)中的任意一個(gè)節(jié)點(diǎn)v∈V，節(jié)點(diǎn)v到d的路徑的代價(jià)等于cost（v，d），即在T_d（V，E_d）中，任意節(jié)點(diǎn)到d的路徑都是兩個(gè)節(jié)點(diǎn)之間的最短路徑。

定義2 在最優(yōu)路由樹(shù)T_d（V，E_d）中，對(duì)于樹(shù)中的任意一個(gè)節(jié)點(diǎn)v∈V，hop（v）表示該節(jié)點(diǎn)的跳數(shù)，本文規(guī)定hop（d）=1。parent（v）表示該節(jié)點(diǎn)的父親節(jié)點(diǎn)，ancestors（v）表示該節(jié)點(diǎn)的所有祖先節(jié)點(diǎn)，祖先節(jié)點(diǎn)為節(jié)點(diǎn)v到d的路徑上的節(jié)點(diǎn)，ancestor（v）表示跳數(shù)為2的祖先節(jié)點(diǎn)，當(dāng)parent（v）=d時(shí)，ancestor（v）=v。

定義3 在最優(yōu)路由樹(shù)T_d（V，E_d）中，對(duì)于樹(shù)中的任意兩個(gè)鄰居節(jié)點(diǎn)u，v∈V，ancestormax（u，v）表示這兩個(gè)節(jié)點(diǎn)對(duì)應(yīng)的跳數(shù)最大的共同祖先節(jié)點(diǎn)。

定義4 在T_d（V，E_d）中，每個(gè)節(jié)點(diǎn)v∈V，都有一個(gè)優(yōu)先級(jí)priority（v），優(yōu)先級(jí)的取值為{0，1，2，3}，節(jié)點(diǎn)的優(yōu)先級(jí)的初始值均為0，優(yōu)先級(jí)的數(shù)值越大，優(yōu)先級(jí)別越高。

定義5 在T_d（V，E_d）中，對(duì)于節(jié)點(diǎn)u的任意鄰居節(jié)點(diǎn)v∈N（u），min（ancestormax（u，v））表示跳數(shù)最小時(shí)對(duì)應(yīng)的鄰居節(jié)點(diǎn)，min（w（u，v）+cost（v，d））表示w（u，v）+cost（v，d）的代價(jià)最小時(shí)對(duì)應(yīng)的鄰居節(jié)點(diǎn)，max（priority（v））表示priority（v）最大時(shí)對(duì)應(yīng)的鄰居節(jié)點(diǎn)。

定義6 給定一個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，當(dāng)網(wǎng)絡(luò)中任意一個(gè)節(jié)點(diǎn)或者一條鏈路出現(xiàn)故障時(shí)，除去該故障節(jié)點(diǎn)或者故障鏈路外，其余所有的節(jié)點(diǎn)之間依然保持連通，稱這樣的網(wǎng)絡(luò)為健壯網(wǎng)絡(luò)。

定義7 假設(shè)目的地址為d，每個(gè)節(jié)點(diǎn)存儲(chǔ)到達(dá)目的d的兩個(gè)下一跳，分別是最優(yōu)下一跳和備份下一跳，bestn（v，d）表示節(jié)點(diǎn)v到d的最優(yōu)下一跳bestn（v，d）=parent（v）。backn（v，d）表示節(jié)點(diǎn)v到d的備份下一跳，備份下一跳需要滿足bestn（v，d）sp（backn（v，d），d）。

定義8 當(dāng)網(wǎng)絡(luò)中出現(xiàn)故障時(shí)，如果受該故障影響的源—目的節(jié)點(diǎn)對(duì)依然可以將報(bào)文正確轉(zhuǎn)發(fā)到目的地址，則稱該源—目的節(jié)點(diǎn)對(duì)被保護(hù)。故障保護(hù)率定義為R（G）=被保護(hù)源-目的節(jié)點(diǎn)對(duì)的數(shù)量/網(wǎng)絡(luò)中所有源-目的節(jié)點(diǎn)對(duì)的數(shù)量。

圖1表示一個(gè)以節(jié)點(diǎn)d為根的最優(yōu)路由樹(shù)T_d（V，E_d），實(shí)線表示最優(yōu)路由樹(shù)中的鏈路，虛線表示網(wǎng)絡(luò)中的鏈路，但是這些鏈路不在最優(yōu)路由樹(shù)上，鏈路上的數(shù)字表示該鏈路對(duì)應(yīng)的代價(jià)。圖1中，節(jié)點(diǎn)的集合可以表示為V={a，b，c，d，e，f，g，h，i，j，k，m，n，o}，邊的集合可以表示為E={（a，d），（b，d），（c，d），…}。鏈路（m，b）的代價(jià)可以表示為w（m，b）=7。對(duì)于節(jié)點(diǎn)d，N（d）={a，b，c}，網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)k和d，sp（k，d）={k，j，i，e，a，d}，cost（k，d）=5。對(duì)于節(jié)點(diǎn)k，該節(jié)點(diǎn)的跳數(shù)為hop（k）=6，該節(jié)點(diǎn)的父親節(jié)點(diǎn)可以表示為parent（k）=j，ancestors（k）={j，i，e，a，d}，ancestor（k）=a，ancestor（a）=a，ancestormax（h，j）=e，節(jié)點(diǎn)k到d的最優(yōu)下一跳可以表示為bestn（k，d）=j。因?yàn)閎estn（m，d）sp（g，d），所以節(jié)點(diǎn)g可以作為節(jié)點(diǎn)m到d的備份下一跳backn（m，d）={g}。

1.2 問(wèn)題描述

本文需要解決的科學(xué)問(wèn)題可以表示為：給定一個(gè)健壯的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G=（V，E），是否可以設(shè)計(jì)一個(gè)高效的路由保護(hù)算法。該算法滿足以下三個(gè)條件：a）可以為網(wǎng)絡(luò)中所有的源—目的節(jié)點(diǎn)對(duì)（s，d）計(jì)算一個(gè)備份下一跳，backn（s，d）不等于空，即故障保護(hù)率為1，R（G）=1；b） 支持逐跳轉(zhuǎn)發(fā)；c）支持增量部署。

2 備份下一跳選取規(guī)則和轉(zhuǎn)發(fā)規(guī)則

本文主要解決的問(wèn)題是設(shè)計(jì)一種路由保護(hù)算法，該算法可以為每一個(gè)源—目的節(jié)點(diǎn)對(duì)計(jì)算一個(gè)備份下一跳。為了完成該目標(biāo)，本文首先提出了選取備份下一跳的規(guī)則和計(jì)算備份下一跳的方法，然后設(shè)計(jì)了轉(zhuǎn)發(fā)規(guī)則。

2.1 備份下一跳選取規(guī)則

為了給每一個(gè)節(jié)點(diǎn)計(jì)算備份下一跳，本文提出了備份下一跳選擇規(guī)則，下面將詳細(xì)介紹該規(guī)則。在T_d（V，E_d）中，對(duì)于節(jié)點(diǎn)u的任意鄰居節(jié)點(diǎn)v∈N（u）并且v≠bestn（u，d）。

規(guī)則1 當(dāng)ancestor（u）≠ancestor（v）成立時(shí)，節(jié)點(diǎn)u可以選擇其鄰居節(jié)點(diǎn)min（w（u，v）+cost（v，d））作為備份下一跳，當(dāng)有多個(gè)鄰居節(jié)點(diǎn)符合該條件時(shí)，選擇鄰居節(jié)點(diǎn)ID最小的作為備份下一跳。

規(guī)則2 當(dāng)ancestor（u）=ancestor（v）和parent（u）ancestors（v）成立時(shí)，節(jié)點(diǎn)u可以選擇其鄰居節(jié)點(diǎn)min（ancestormax（u，v））作為備份下一跳，當(dāng)有多個(gè)鄰居節(jié)點(diǎn)符合該條件時(shí)，選擇鄰居節(jié)點(diǎn)ID最小的作為備份下一跳。

規(guī)則3 當(dāng)ancestor（u）=ancestor（v）和parent（u）∈ancestors（v）成立時(shí)，節(jié)點(diǎn)u可以選擇其鄰居節(jié)點(diǎn)max（priority（v））作為備份下一跳，當(dāng)有多個(gè)鄰居節(jié)點(diǎn)符合該條件時(shí)，選擇鄰居節(jié)點(diǎn)ID最小的作為備份下一跳。

2.2 計(jì)算備份下一跳的步驟

在備份下一跳選取規(guī)則的基礎(chǔ)上，為了給每個(gè)節(jié)點(diǎn)計(jì)算唯一的備份下一跳，本文將進(jìn)一步介紹計(jì)算備份下一跳的方法。在T_d（V，E_d）中，v∈N（u）并且v≠bestn（u，d），節(jié)點(diǎn)u計(jì)算備份下一跳的步驟如下：

a）計(jì)算出符合規(guī)則1的備份下一跳，當(dāng)計(jì)算結(jié)束后，如果backn（u，d）≠，則將節(jié)點(diǎn)u的優(yōu)先級(jí)設(shè)置為3，否則執(zhí)行步驟b）；

b）計(jì)算出符合規(guī)則2的備份下一跳，當(dāng)計(jì)算結(jié)束后，如果backn（u，d）≠，則將節(jié)點(diǎn)u的優(yōu)先級(jí)設(shè)置為2，否則執(zhí)行步驟c）；

c）計(jì)算出符合規(guī)則3的備份下一跳，將節(jié)點(diǎn)u的優(yōu)先級(jí)設(shè)置為1。

從計(jì)算備份下一跳的步驟可知，每個(gè)節(jié)點(diǎn)按照規(guī)則1～3的順序依次計(jì)算備份下一跳。當(dāng)節(jié)點(diǎn)有符合規(guī)則1的備份下一跳時(shí)，不再計(jì)算滿足規(guī)則2和3的備份下一跳，如果該節(jié)點(diǎn)沒(méi)有符合規(guī)則1的備份下一跳，然后依次計(jì)算符合規(guī)則2和3的備份下一跳，如果有符合規(guī)則2的備份下一跳，則不再計(jì)算滿足規(guī)則3的備份下一跳，如果該節(jié)點(diǎn)沒(méi)有符合規(guī)則2的備份下一跳，然后計(jì)算符合規(guī)則3的備份下一跳。因此，每個(gè)節(jié)點(diǎn)最終僅保留唯一的一個(gè)備份下一跳，并且該節(jié)點(diǎn)具有最高的優(yōu)先級(jí)。

2.3 計(jì)算備份下一跳的例子

下面通過(guò)圖1來(lái)解釋節(jié)點(diǎn)m，節(jié)點(diǎn)j和k計(jì)算備份下一跳的過(guò)程。

節(jié)點(diǎn)m的鄰居集合為N（m）={g，b}，因?yàn)閍ncestor（m）≠ancestor（g）w（m，g）+cost（g，d）=10，ancestor（m）≠ancestor（b）w（m，b）+cost（b，d）=8，w（m，b）+cost（b，d）gt;w（m，g）+cost（g，d），所以根據(jù)規(guī)則1可知，節(jié)點(diǎn)m可以選擇其鄰居節(jié)點(diǎn)b作為備份下一跳，m的優(yōu)先級(jí)為3。

節(jié)點(diǎn)j計(jì)算備份下一跳的過(guò)程，節(jié)點(diǎn)j的鄰居集合為N（j）={h，f}，因?yàn)閍ncestor（j）=ancestor（h），parent（j）ancestors（h），ancestormax（j，h）=e；ancestor（j）=ancestor（f），parent（j）ancestors（f），ancestormax（j，f）=a；hop（ancestormax（j，h））=3，hop（ancestormax（j，f））=2，hop（ancestormax（j，h））gt;hop（ancestormax（j，f）），所以根據(jù)規(guī)則2可知，節(jié)點(diǎn)j可以選擇其鄰居節(jié)點(diǎn)f作為備份下一跳，j的優(yōu)先級(jí)為2。同理，節(jié)點(diǎn)n可以選擇其鄰居節(jié)點(diǎn)o作為備份下一跳，n的優(yōu)先級(jí)為2。

節(jié)點(diǎn)k計(jì)算備份下一跳的過(guò)程，節(jié)點(diǎn)k的鄰居集合為N（k）={m，n}，因?yàn)閍ncestor（k）=ancestor（m）；parent（k）∈ancestors（m）；ancestor（k）=ancestor（n）；parent（k）∈ancestors（m）；priority（m）gt;priority（n），所以根據(jù)規(guī)則3可知，節(jié)點(diǎn)k可以選擇其鄰居節(jié)點(diǎn)m作為備份下一跳，k的優(yōu)先級(jí)為1。

2.4 轉(zhuǎn)發(fā)方法

對(duì)于任意目的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)在轉(zhuǎn)發(fā)表中維護(hù)兩個(gè)下一跳，分別是最優(yōu)下一跳和備份下一跳。當(dāng)目的地址為d，節(jié)點(diǎn)u將報(bào)文轉(zhuǎn)發(fā)到目的地址的轉(zhuǎn)發(fā)規(guī)則為

a）如果bestn（u，d）沒(méi)有出現(xiàn)故障，則u將報(bào)文轉(zhuǎn)發(fā)給bestn（u，d）；

b）如果bestn（u，d）出現(xiàn)故障，則u將報(bào)文轉(zhuǎn)發(fā)給備份下一跳backn（u，d）；

c）如果節(jié)點(diǎn)u從其最優(yōu)下一跳收到報(bào)文，則u將報(bào)文轉(zhuǎn)發(fā)給備份下一跳backn（u，d）。

3 算法SFRPA

因?yàn)閷?duì)于每個(gè)目的地址，算法SFRPA的計(jì)算過(guò)程是相同的，所以下面以目的地址d為例說(shuō)明算法SFRPA的執(zhí)行過(guò)程。圖2為算法SFRPA的流程。

在描述算法SFRPA前，本文首先介紹該算法中使用的一些函數(shù)。

函數(shù)EnQueue（Q）表示將網(wǎng)絡(luò)中所有的節(jié)點(diǎn)加入到優(yōu)先級(jí)隊(duì)列中；函數(shù)IsnotEmpty（Q）表示判斷優(yōu)先級(jí)隊(duì)列是否為空，當(dāng)隊(duì)列為空時(shí)，該函數(shù)的值為0，否則為1；GetTop（Q）表示讀取優(yōu)先級(jí)隊(duì)列的隊(duì)首元素，該隊(duì)列的隊(duì)首元素具有下面兩個(gè)性質(zhì)：a）元素具有最大的跳數(shù)；b）當(dāng)有多個(gè)元素的跳數(shù)相同時(shí)，選取具有最小ID的元素。DeQueue（Q，v）表示出隊(duì)列操作，將節(jié)點(diǎn)v從優(yōu)先級(jí)隊(duì)列中刪除。PF（v）是懲罰函數(shù)，該函數(shù)表示將節(jié)點(diǎn)v的跳數(shù)修改為hop（v）-1。如果某個(gè)節(jié)點(diǎn)僅僅有符合規(guī)則3的備份下一跳，根據(jù)備份下一跳計(jì)算規(guī)則可知，當(dāng)該節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)的優(yōu)先級(jí)確定后，該節(jié)點(diǎn)才能準(zhǔn)確計(jì)算出自己的備份下一跳。因此，懲罰函數(shù)的目的就是推遲節(jié)點(diǎn)出隊(duì)列的順序，保證僅僅有符合規(guī)則3的節(jié)點(diǎn)計(jì)算出正確的備份下一跳。

以下將介紹算法SFRPA的詳細(xì)執(zhí)行步驟。SFRPA的輸入為網(wǎng)絡(luò)拓?fù)銰=（V，E）和目的節(jié)點(diǎn)d∈V，SFRPA的輸出為除去目的節(jié)點(diǎn)以外的其余所有節(jié)點(diǎn)到目的節(jié)點(diǎn)的備份下一跳集合。對(duì)于網(wǎng)絡(luò)中所有節(jié)點(diǎn)u∈V＼g0gggggg，將該節(jié)點(diǎn)到目的節(jié)點(diǎn)d的備份下一跳初始化為（算法1～3行）。利用迪杰斯特拉算法，構(gòu)造以目的節(jié)點(diǎn)d為根的最優(yōu)路由樹(shù)，在構(gòu)造樹(shù)的過(guò)程中，記錄每個(gè)節(jié)點(diǎn)到目的節(jié)點(diǎn)的最短路徑的代價(jià)、節(jié)點(diǎn)的跳數(shù)、節(jié)點(diǎn)的父親節(jié)點(diǎn)、節(jié)點(diǎn)的祖先節(jié)點(diǎn)等（算法第4行）。創(chuàng)建一個(gè)優(yōu)先級(jí)隊(duì)列Q，隊(duì)列中元素的結(jié)構(gòu)為（v，hop（v），ID（v）），利用Enqueue（Q）函數(shù)將網(wǎng)絡(luò)中所有的節(jié)點(diǎn)加入到優(yōu)先級(jí)隊(duì)列Q中（算法第5行）。初始化三個(gè)變量mincost、min、max的數(shù)值（算法第6行）。判斷隊(duì)列是否為空，當(dāng)隊(duì)列不為空時(shí)，算法執(zhí)行下面的迭代過(guò)程。利用GetTop（Q）函數(shù)讀取優(yōu)先級(jí)隊(duì)列的隊(duì)首節(jié)點(diǎn)u（算法第8行），遍歷該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)v，根據(jù)兩者之間的關(guān)系選擇執(zhí)行算法2～4（算法第10～12行）。如果變量state的值為0，并且節(jié)點(diǎn)u的優(yōu)先級(jí)為1，表示節(jié)點(diǎn)u并沒(méi)有最終計(jì)算出符合規(guī)則3的備份下一跳。算法需要執(zhí)行懲罰函數(shù)，并且刪除節(jié)點(diǎn)u的備份下一跳（算法第14～18行）。當(dāng)遍歷完節(jié)點(diǎn)u的所有鄰居時(shí)，如果節(jié)點(diǎn)u的備份下一跳不為空，則將該節(jié)點(diǎn)從優(yōu)先級(jí)隊(duì)列中刪除（算法第19～21行）。將變量state的值設(shè)置為1（算法第22行）。程序執(zhí)行完畢后，返回所有節(jié)點(diǎn)到目的節(jié)點(diǎn)的備份下一跳（算法第24行）。

算法2的執(zhí)行過(guò)程如下：如果兩者之間的關(guān)系符合規(guī)則1，并且mincostgt;w（u，v）+cost（v，d），則將mincost的數(shù)值設(shè)置為w（u，v）+cost（v，d），將u到d的備份下一跳修改為v，將u的優(yōu)先級(jí)設(shè)置為3（算法第1～7行）。

算法3的執(zhí)行過(guò)程如下：如果兩者之間的關(guān)系符合規(guī)則2，并且節(jié)點(diǎn)u的優(yōu)先級(jí)大于2，則不再為該節(jié)點(diǎn)計(jì)算符合規(guī)則2和3的備份下一跳。如果兩者之間的關(guān)系符合規(guī)則2，并且節(jié)點(diǎn)u的優(yōu)先級(jí)小于等于2和mingt;ancestormax（u，v）同時(shí)成立，則將min設(shè)置為ancestormax（u，v），將u到d的備份下一跳修改為v，將u的優(yōu)先級(jí)設(shè)置為2（算法第1～10行）。

算法4的執(zhí)行過(guò)程如下：如果兩者之間的關(guān)系符合規(guī)則3，并且節(jié)點(diǎn)u的優(yōu)先級(jí)大于1，則不再為該節(jié)點(diǎn)計(jì)算符合規(guī)則3的備份下一跳。如果兩者之間的關(guān)系符合規(guī)則3，并且節(jié)點(diǎn)u的優(yōu)先級(jí)小于等于1和priority（v）=0同時(shí)成立，則將變量state設(shè)置為0，表示節(jié)點(diǎn)u計(jì)算的符合規(guī)則3的備份下一跳并不準(zhǔn)確（算法第28～33行）。如果兩者之間的關(guān)系符合規(guī)則3，并且節(jié)點(diǎn)u的優(yōu)先級(jí)小于等于1和maxlt;priority（v）同時(shí)成立，則將max設(shè)置為priority（v），將u到d的備份下一跳修改為v，將u的優(yōu)先級(jí)設(shè)置為1（算法第1～13行）。

從上述對(duì)算法SFRPA的描述可知，SFRPA以目前互聯(lián)網(wǎng)部署的鏈路狀態(tài)路由協(xié)議為基礎(chǔ)，在此基礎(chǔ)上增加了計(jì)算備份下一跳的規(guī)則，這些對(duì)原先部署的路由協(xié)議的正常運(yùn)行沒(méi)有任何影響。當(dāng)某個(gè)節(jié)點(diǎn)部署SFRPA時(shí)，該節(jié)點(diǎn)將會(huì)計(jì)算出到目的地址的備份下一跳，也不會(huì)影響到其他沒(méi)有部署SFRPA的節(jié)點(diǎn)的正常工作方式。因此，從上述討論可知，SFRPA支持增量部署。SFRPA雖然支持增量部署，但是在實(shí)際部署前，需要首先向互聯(lián)網(wǎng)工程任務(wù)組提交RFC草案，然后通過(guò)專家委員的討論成為標(biāo)準(zhǔn)RFC文檔，這個(gè)過(guò)程需要比較長(zhǎng)的時(shí)間。因此，在實(shí)際網(wǎng)絡(luò)中部署SFRPA需要經(jīng)歷一些必要的審核流程。

算法1 SFRPA

輸入：G=（V，E）；destination d。

輸出：u∈V；backn（u，d）。

1 for u∈V＼g0gggggg do

2 backn（u，d）←

3 end for

4 constructing T_d（V，E_d）

5 enqueue（Q）

6 mincost←+∞，min←+∞，max←-∞

7 while IsnotEmpty（Q）

8 u←GetTop（Q）

9 for v∈N（u）

10 算法2

11 算法3

12 算法4

13 end for

14 if priority（u）=1 and state=0 then

15 PF（u）

16 backn（u，d）←

17 continue

18 end if

19 if backn（u，d）≠ then

20 DeQueue（Q，u）

21 end if

22 state←1

23 end while

24 return u∈V，backn（u，d）

算法2 rule 1

1 if ancestor（u）≠ancestor（v） then

2 if mincostgt;w（u，v）+cost（v，d） then

3 mincost=w（u，v）+cost（v，d）

4 backn（u，d）←v

5 priority（u）←3

6 end if

7 end if

算法3 rule 2

1 if ancestor（u）=ancestor（v） and parent（u）ancestor（v） then

2 if priority（u）gt;2 then

3 continue

4 end if

5 if mingt;ancestormax（u，v） then

6 min←ancestormax（u，v）

7 backn（u，d）←v

8 priority（u）←2

9 end if

10end if

算法4 rule 3

1 if ancestor（u）=ancestor（v） and parent（u）∈ancestor（v） then

2 if priority（u）gt;1 then

3 continue

4 end if

5 if priority（v）=0 then

6 state=0

7 end if

8 if maxlt;priority（v） then

9 max←priority（v）

10 backn（u，d）←v

11 priority（u）=1

12 end if

13 end if

4 實(shí)驗(yàn)及結(jié)果分析

本章將通過(guò)模擬實(shí)驗(yàn)來(lái)衡量算法SFRPA、LFA、DMPA、TBFH和IAC^［7］的性能，算法的評(píng)價(jià)指標(biāo)主要是故障保護(hù)率和路徑拉伸度。從故障保護(hù)率的定義可知，如果某個(gè)算法的故障保護(hù)率越高，則表明該算法應(yīng)對(duì)故障的能力越強(qiáng)。路徑拉伸度可以表示為，當(dāng)網(wǎng)絡(luò)中出現(xiàn)故障時(shí)，某個(gè)算法計(jì)算出來(lái)的重路由路徑的代價(jià)與利用OSPF計(jì)算出來(lái)的最短路徑的代價(jià)的比值。如果某個(gè)算法計(jì)算出來(lái)的路徑拉伸度越大，則表明該算法對(duì)應(yīng)的重路由路徑的代價(jià)越大，產(chǎn)生的網(wǎng)絡(luò)時(shí)延和開(kāi)銷(xiāo)越大。從上面的描述可知，本文希望路由保護(hù)算法不僅具有較高的故障保護(hù)率，而且具有較低的路徑拉伸度。

下面將首先介紹上述的四種路由保護(hù)算法運(yùn)行的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，然后評(píng)價(jià)四種算法對(duì)應(yīng)的故障保護(hù)率和路徑拉伸度，并且對(duì)實(shí)驗(yàn)的結(jié)果進(jìn)行討論。

4.1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

為了全面、準(zhǔn)確和客觀地評(píng)價(jià)算法SFRPA、LFA、DMPA、IAC和TBFH的性能，將在以下三種網(wǎng)絡(luò)拓?fù)渖线\(yùn)行上述五種算法。網(wǎng)絡(luò)拓?fù)渲饕ㄕ鎸?shí)網(wǎng)絡(luò)拓?fù)洹y(cè)量網(wǎng)絡(luò)拓?fù)浜屠媚M軟件Brite生成的網(wǎng)絡(luò)拓?fù)洹?/p>

a）真實(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)^［18］。在該類(lèi)型的網(wǎng)絡(luò)拓?fù)渲校疚倪x擇了六個(gè)作為實(shí)驗(yàn)使用的拓?fù)浣Y(jié)構(gòu)，真實(shí)拓?fù)浣Y(jié)構(gòu)的參數(shù)（路由器數(shù)量和鏈路數(shù)量）如表1所示。

b）Rocketfuel^［19］項(xiàng)目測(cè)量的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。在測(cè)量的拓?fù)浣Y(jié)構(gòu)中，本文選擇了六個(gè)作為實(shí)驗(yàn)使用的拓?fù)浣Y(jié)構(gòu)，測(cè)量拓?fù)涞膮?shù)（路由器數(shù)量和鏈路數(shù)量）如表2所示。

c）利用模擬軟件Brite生成的拓?fù)浣Y(jié)構(gòu)。在生成拓?fù)浣Y(jié)構(gòu)的時(shí)候僅僅改變節(jié)點(diǎn)的大小和節(jié)點(diǎn)的平均度，其余參數(shù)均采用軟件默認(rèn)參數(shù)。

4.2 故障保護(hù)率

算法SFRPA、LFA、DMPA、IAC和TBFH可以為網(wǎng)絡(luò)中的源—目的節(jié)點(diǎn)對(duì)計(jì)算出相應(yīng)的備份下一跳，當(dāng)網(wǎng)絡(luò)中出現(xiàn)故障時(shí)，受故障影響的報(bào)文將會(huì)被轉(zhuǎn)發(fā)到對(duì)應(yīng)的重路由路徑。本節(jié)使用故障保護(hù)率來(lái)衡量算法SFRPA、LFA、DMPA、IAC和TBFH應(yīng)對(duì)網(wǎng)絡(luò)故障的性能。表3展示了算法SFRPA、LFA、DMPA、IAC和TBFH在真實(shí)拓?fù)浜蜏y(cè)量拓?fù)渲械墓收媳Ｗo(hù)率。從表3可以看出，SFRPA的故障保護(hù)率始終為100%，其他算法的故障保護(hù)率都遠(yuǎn)遠(yuǎn)低于100%。例如在Abilene拓?fù)渲校琇FA、DMPA和IAC、TBFH的故障保護(hù)率僅僅為62.23%、60.36%、60.36%和56.71%。

圖3展示了在網(wǎng)絡(luò)節(jié)點(diǎn)平均度固定的前提下，算法SFRPA、LFA、DMPA、IAC和TBFH的故障保護(hù)率和網(wǎng)絡(luò)拓?fù)浯笮≈g的關(guān)系。圖4描述了在網(wǎng)絡(luò)拓?fù)浯笮」潭〞r(shí)，四種算法的故障保護(hù)率和網(wǎng)絡(luò)節(jié)點(diǎn)平均度之間的關(guān)系。從圖3和4中，可以得到如下結(jié)論，無(wú)論在何種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，算法SFRPA的故障保護(hù)率始終為100%，其余三種算法的故障保護(hù)率遠(yuǎn)遠(yuǎn)低于100%。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)平均度增加的時(shí)候，LFA、DMPA、IAC和TBFH的故障保護(hù)率也相應(yīng)增加，但是始終無(wú)法到100%。這是因?yàn)槠溆嗳N算法受到計(jì)算方法和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的約束，無(wú)法在網(wǎng)絡(luò)保持連通的情形下計(jì)算出符合條件的備份下一跳，而SFRPA不受網(wǎng)絡(luò)拓?fù)涞南拗疲灰W(wǎng)絡(luò)保持連通，該算法就可以為所有節(jié)點(diǎn)計(jì)算出相應(yīng)的備份下一跳，從而大大提高故障保護(hù)率。

4.3 路徑拉伸度

本節(jié)使用路徑拉伸度來(lái)衡量當(dāng)網(wǎng)絡(luò)中出現(xiàn)故障時(shí)，不同算法對(duì)應(yīng)的重路由路徑與最短路徑之間的差距。當(dāng)路徑拉伸度較小時(shí)，重路由路徑和最短路徑比較接近，不會(huì)引入較大的延遲和開(kāi)銷(xiāo)。相反，當(dāng)路徑拉伸度較大時(shí)，重路由路徑的延遲遠(yuǎn)遠(yuǎn)大于最短路徑的延遲，大大地增加了互聯(lián)網(wǎng)的開(kāi)銷(xiāo)。

下面將描述本文的實(shí)驗(yàn)方法。對(duì)于給定的網(wǎng)絡(luò)，隨機(jī)選擇網(wǎng)絡(luò)中的鏈路或者節(jié)點(diǎn)出現(xiàn)故障，在此故障情形下運(yùn)行不同的算法，根據(jù)算法計(jì)算出重路由路徑的代價(jià)，然后計(jì)算出路徑拉伸度。為了使得實(shí)驗(yàn)結(jié)果更加可信準(zhǔn)確，對(duì)于每個(gè)拓?fù)鋱D，重復(fù)執(zhí)行上述的算法50次，然后計(jì)算路徑拉伸度的平均值。

圖5描述了算法SFRPA、LFA、DMPA、IAC和TBFH在真實(shí)拓?fù)浜蜏y(cè)量拓?fù)渲袑?duì)應(yīng)的路徑拉伸度。從圖5可以看出，SFRPA的路徑拉伸度明顯低于LFA、DMPA、IAC和TBFH的路徑拉伸度。這是因?yàn)長(zhǎng)FA、DMPA、IAC和TBFH計(jì)算所有符合規(guī)則的備份下一跳，而SFRPA是從所有符合備份下一跳規(guī)則的備份下一跳中選擇代價(jià)具有的節(jié)點(diǎn)作為備份下一跳。所以，當(dāng)網(wǎng)絡(luò)中出現(xiàn)故障時(shí)，算法SFRPA計(jì)算的重路由路徑更加接近利用OSPF協(xié)議計(jì)算出的最短路徑。

5 結(jié)束語(yǔ)

本文研究了路由協(xié)議存在的一個(gè)根本問(wèn)題，即如何設(shè)計(jì)一個(gè)能夠應(yīng)對(duì)網(wǎng)絡(luò)里面所有單故障情形的路由保護(hù)方法。為此，本文首先詳細(xì)描述了需要解決的關(guān)鍵問(wèn)題，然后提出了備份下一跳選擇規(guī)則，基于備份下一跳選擇規(guī)則，提出了一種基于逐跳轉(zhuǎn)發(fā)方式的路由保護(hù)算法SFRPA。實(shí)驗(yàn)結(jié)果表明SFRPA算法可以應(yīng)對(duì)網(wǎng)絡(luò)中的所有單故障情形。 仿真結(jié)果表明，與已有的路由保護(hù)方案相比較，SFRPA不僅可以實(shí)現(xiàn)更高的故障保護(hù)率，而且具有較小的路徑拉升度。SFRPA主要是針對(duì)網(wǎng)絡(luò)中的單故障情形，無(wú)法解決并發(fā)故障。 因此在未來(lái)將改進(jìn)SFRPA，使得該算法可以適應(yīng)并發(fā)故障情形。

參考文獻(xiàn)：

［1］Clark D D.Design philosophy of the DARPA Internet protocols［J］.Computer Communication Review，1995，25（1）：102-111.

［2］Tian Hui，Sun Jun，Chang C C，et al.Detecting bitrate modulation-based covert voice-over-IP communication［J］.IEEE Communications Letters，2018，22（6）：1196-1199.

［3］Anbiah A，Sivalingam K M.Efficient failure recovery techniques for segment-routed networks［J］.Computer Communications，2022，182：1-12.

［4］Foerster K T，Kamisiski A，Pignolet Y A，et al. Improved fast rerouting using postprocessing［J］.IEEE Trans on Dependable and Secure Computing，2022，19（1）：537-550.

［5］Chiesa M，Kamisinski A，Rak J，et al. A survey of fast-recovery mecha-nisms in packet-switched networks［J］.IEEE Communications Surveys and Tutorials，2021：23（2）：1253-1301.

［6］耿海軍，施新剛，王之梁，等.基于最小路徑交叉度的域內(nèi)路由保護(hù)方案［J］.軟件學(xué)報(bào)，2020，31（5）：1536-1548.（Geng Haijun，Shi Xingang，Wang Zhiliang，et al.Intra-domain routing protection scheme based on minimum path crossing degree［J］.Journal of Software，2020，31（5）：1536-1548.）

［7］黃建洋，蘭巨龍，孫鵬浩，等.一種基于免疫環(huán)進(jìn)行鏈路備份的多鏈路路由保護(hù)機(jī)制［J］.信息工程大學(xué)學(xué)報(bào)，2018，19（2）：146-152.（Huang Jianyang，Lan Julong，Sun Penghao，et al.Immune-ring-based link backup mechanism for multi-link routing protection［J］.Journal of Information Engineering University，2018，19（2）：146-152.）

［8］Yang Yuan，Xu Mingwei，Li Qi.Fast rerouting against multi-link failures without topology constraint［J］.IEEE/ACM Trans on Networking，2018，26（1）：384-397.

［9］Jia Xuya，Li Dan，Zhu Jin，et al. Metro：an efficient traffic fast rerouting scheme with low overhead［J］.IEEE/ACM Trans on Networking，2019，99：2015-2027.

［10］Kwong K W，Gao Lixin，Zhang Zhili.On the feasibility and efficacy of protection routing in IP networks［J］.IEEE/ACM Trans on Networking，2011，19（5）：1543-1556.

［11］Atlas A，Zinin A D.RRC 5286，Basic specification for IP fast reroute：loop-free alternates ［S］.［S.l.］：RFC Editor，2008.

［12］Enyedi G，Szilagyi P，Retvari G，et al.IP fast reroute：lightweight not-via without additional addresses ［C］//Proc of IEEE INFOCOM.Piscataway，NJ：IEEE Press，2009：2771-2775.

［13］Zheng Jiaqi，Xu Hong，Zhu Xiaojun，et al.We’ve got you covered：fai-lure recovery with backup tunnels in traffic engineering［C］//Proc of the 24th International Conference on Network Protocols.Piscataway，NJ：IEEE Press，2016：1-10.

［14］Mérindol P，F(xiàn)rancois P，Bonaventure O，et al.An efficient algorithm to enable path diversity in link state routing networks［J］.Computer Networks，2011，55（5）：1132-1149.

［15］Geng Haijun，Shi Xingang，Wang Zhiliang，et al.A hop-by-hop dynamic distributed multipath routing mechanism for link state network［J］.Computer Communications，2018，116：225-239.

［16］Rétvári G，Csikor L，Tapolcai J，et al.Optimizing IGP link costs for improving IP-level resilience［C］//Proc of the 8th International Workshop on the Design of Reliable Communication Networks.Pisca-taway，NJ：IEEE Press，2011：62-69.

［17］Lakshminarayanan K，Caesar M，Rangan M，et al. Achieving convergence-free routing using failure-carrying packets［J］.ACM SIGCOMM Computer Communication Review，2007，37（4）：241-252.

［18］Antonakopoulos S，Bejerano Y，Koppol P.Full protection made easy：the dispath IP fast reroute scheme［J］.IEEE/ACM Trans on Networking，2015，23（4）：1229-1242.

［19］Spring N，Mahajan R，Wetherall D，et al.Measuring ISP topologies with rocketfuel［J］.IEEE/ACM Trans on Networking，2004，12（1）：2-16.

［20］Rétvári G，Tapolcai J，Enyedi G，et al.IP fast reroute：loop free alternates revisited［C］//Proc of International Conference on Computer Communications.Washington DC：IEEE Computer Society，2011：2948-2956.