一種基于P圈的BIER快速重路由算法

趙 光，陳 睿，王文鼐，莊金成，王 斌

（南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003）

預(yù)測(cè)表明，至2021年多媒體業(yè)務(wù)將占所有網(wǎng)絡(luò)流量78%［1］，其中多播類業(yè)務(wù)的承載優(yōu)化成為網(wǎng)絡(luò)技術(shù)發(fā)展的關(guān)鍵之一［2］。IP多播用于向多播組成員復(fù)制和分發(fā)內(nèi)容，具有高效與并發(fā)的特點(diǎn)。傳統(tǒng)IP多播的轉(zhuǎn)發(fā)設(shè)備需要維持IP多播組的中間狀態(tài)，降低了其擴(kuò)展性［3］。BIER（Bit Index Explicit Replication）是一個(gè)基于分段路由（Segment Routing，SR）的新多播協(xié)議［4］，它由源端或入口路由器定義轉(zhuǎn)發(fā)路徑并將控制信息隨分組一同發(fā)送，網(wǎng)絡(luò)中間路由器不再需要維護(hù)多播組狀態(tài)，而是基于單播方式傳送分組，業(yè)務(wù)得到顯著增強(qiáng)。

IP單播本身并不支持快速故障保護(hù)［5］，一旦通信鏈路或設(shè)備出現(xiàn)故障，在路由的重收斂過程中，業(yè)務(wù)會(huì)出現(xiàn)長(zhǎng)時(shí)延和分組丟失等多種問題。這對(duì)時(shí)延和丟失敏感的業(yè)務(wù)，如流媒體、網(wǎng)絡(luò)游戲以及線上視頻會(huì)議等，極易造成性能降低甚至業(yè)務(wù)中斷，需要采用相應(yīng)的保護(hù)機(jī)制來(lái)快速恢復(fù)。

快速重路由（Fast Re-Route，F(xiàn)RR）為潛在網(wǎng)絡(luò)故障提前計(jì)算備份路徑，得到廣泛關(guān)注。P圈（Preconfiguration Cycle，P-Cycle）是一種基于環(huán)結(jié)構(gòu)的FRR方案［6］，它利用空閑資源預(yù)先設(shè)置環(huán)形通道以實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的快速保護(hù)。

關(guān)于P圈構(gòu)造算法研究有很多，經(jīng)典的P圈構(gòu)造算法有Straddling Link Algorithm（SLA）［7］。SLA的做法是遍歷拓?fù)渲忻恳粭l邊e，以e的兩個(gè)端點(diǎn)作為起點(diǎn)和終點(diǎn)，利用Dijkstra算法在這兩點(diǎn)之間找到兩條分離且不包含e的路徑，如果找到，則將兩條路徑首尾相連組成一個(gè)P圈?；诮?jīng)典算法的改良算法有文獻(xiàn)［8－10］。P圈的先驗(yàn)效率［8］指的是為一個(gè)P圈能保護(hù)的所有工作容量和配置這個(gè)圈所要消耗網(wǎng)絡(luò)容量的比值。改良算法大多數(shù)追求的是構(gòu)造出的P圈能夠具有的更高先驗(yàn)效率，然而它們并沒有考慮網(wǎng)絡(luò)資源是否具有方向區(qū)分這個(gè)前提，構(gòu)造出的P圈并不具有方向性。

文獻(xiàn)［11］提出了一種保護(hù)光網(wǎng)絡(luò)多播傳輸?shù)腜圈方式，優(yōu)化了受保護(hù)的光網(wǎng)絡(luò)的工作和備用容量。文獻(xiàn)［12］提出了一種改進(jìn)的P圈構(gòu)造算法，該算法在選擇擴(kuò)展圈時(shí)考慮了擴(kuò)展圈中未受保護(hù)的工作容量的冗余和方差，從而提高了保護(hù)效率并減少了資源消耗。目前基于P圈的多播業(yè)務(wù)保護(hù)算法都是針對(duì)傳統(tǒng)IP多播，而BIER能實(shí)現(xiàn)極簡(jiǎn)的多播網(wǎng)絡(luò)，基于此設(shè)計(jì)P圈業(yè)務(wù)保護(hù)相對(duì)而言更為簡(jiǎn)單經(jīng)濟(jì)。

在BIER協(xié)議實(shí)現(xiàn)多播業(yè)務(wù)的基礎(chǔ)上，本文聚焦于P圈解決BIER多播的鏈路故障及快速重路由。技術(shù)出發(fā)點(diǎn)是，根據(jù)多播業(yè)務(wù)的特點(diǎn)構(gòu)造有方向的P圈序列，并通過廣度優(yōu)先搜索（Breadth First Search，BFS）為中間路由器計(jì)算出BFR轉(zhuǎn)發(fā)表（Bit Index Forwarding Table，BIFT）。通過對(duì)NSF拓?fù)洌?4個(gè)節(jié)點(diǎn)，21條鏈路）的仿真實(shí)驗(yàn)驗(yàn)證了算法的可行性。

1 技術(shù)背景與故障保護(hù)需求

IP多播沿多播樹傳送多播分組，為此要求轉(zhuǎn)發(fā)路由器維護(hù)多播樹狀態(tài)。當(dāng)多播組成員數(shù)量較大，路由器需要維護(hù)大量的轉(zhuǎn)發(fā)狀態(tài)；當(dāng)有成員加入、退出多播組，路由器需要更新轉(zhuǎn)發(fā)狀態(tài)，這限制了IP多播的可擴(kuò)展性。因此，在IP多播中實(shí)現(xiàn)路由保護(hù)是困難的。

BIER技術(shù)是一種新型多播技術(shù)，它將多播承載網(wǎng)絡(luò)中的核心網(wǎng)部分替換為BIER域。BIER域包括位轉(zhuǎn)發(fā)入口路由器（BFIR），位轉(zhuǎn)發(fā)路由器（BFR）和位轉(zhuǎn)發(fā)出口路由器（BFER）。

BFIR在發(fā)送多播分組到BFER時(shí)，將BFER的標(biāo)識(shí)（BFR-id）信息編碼到多播分組BIER頭部中的比特位串（BitString）中。BFR通過BIFT轉(zhuǎn)發(fā)多播分組。BIFT中有一列字段為轉(zhuǎn)發(fā)比特掩碼（FBM），它是由有相同下一跳的BFR-id進(jìn)行邏輯或得到的。BFR將分組頭部的BitString和F-BM進(jìn)行邏輯與，復(fù)制有相同下一跳的多播分組并進(jìn)行轉(zhuǎn)發(fā)。

BIER本質(zhì)上等同于IP單播，中間路由器不需要維護(hù)多播樹狀態(tài)，處理多播分組可以像單播一樣通過BIFT復(fù)制轉(zhuǎn)發(fā)分組。因此基于BIER的保護(hù)本質(zhì)上是對(duì)IP單播的保護(hù)。

文獻(xiàn)［13］介紹了幾種IP單播的FRR機(jī)制，包括Not-Via Adresses、Loop-Free Alternates（LFA）、Remote LFA、Directed LFA等，文獻(xiàn)［3］提出了2種針對(duì)BIER的FRR機(jī)制，包括LFA和基于隧道的FRR。LFA需要增加標(biāo)識(shí)開銷，僅能保護(hù)70%的目的地免受單鏈路故障的影響?；谒淼赖腇RR，要在路由表中引入大量的備份條目，存在較重的空間開銷。

P圈也是一種常見的FRR機(jī)制，基于P圈的BIER多播路由保護(hù)目前尚無(wú)人研究。由于目前的P圈構(gòu)造算法不能構(gòu)造出具有方向的P圈，因此需要設(shè)計(jì)一個(gè)有向的P圈序列構(gòu)造算法，并在生成的有向P圈序列上實(shí)現(xiàn)BIER的快速重路由。

2 算法描述

2.1 P圈序列構(gòu)造

P圈序列構(gòu)造算法利用初始鏈路并通過有向P圈構(gòu)造算法構(gòu)建出初始P圈，利用已構(gòu)建P圈上的擴(kuò)展鏈路擴(kuò)展出新的P圈。由于拓?fù)涞碾S機(jī)性，某一個(gè)初始P圈擴(kuò)展出的P圈序列可能無(wú)法覆蓋拓?fù)渲兴墟溌?，所以需要選擇未遍歷過的鏈路作為初始鏈路再次構(gòu)建初始P圈，并擴(kuò)展出其他的P圈序列。

拓?fù)渲锌赡艽嬖谝恍┨厥獾逆溌?，這些鏈路不能通過有向P圈構(gòu)造算法構(gòu)造出P圈，所以無(wú)法通過P圈對(duì)這些鏈路進(jìn)行保護(hù)，本文將此種鏈路稱之為孤立鏈路。

如圖1所示的拓?fù)?，其中空心圓點(diǎn)中的數(shù)字代表節(jié)點(diǎn)的序號(hào)，實(shí)際可由BFR的BFR-id確定。鏈路（3，4）為一條孤立鏈路。P圈用節(jié)點(diǎn)序列表示，如｛1，2，3，1｝代表拓?fù)渲械囊粋€(gè)P圈。

圖1 孤立鏈路示例拓?fù)洌招膱A點(diǎn)表示節(jié)點(diǎn)，連線表示鏈路）

根據(jù)有向鏈路e構(gòu)造出有向P圈的算法偽代碼如算法1所示。

算法1有向P圈構(gòu)造算法

算法1是采用python格式語(yǔ)法描述。其中，輸入?yún)?shù)G為網(wǎng)絡(luò)拓?fù)?，是?jié)點(diǎn)集合V和鏈路集合E的序偶；參數(shù)e是從節(jié)點(diǎn)u指向節(jié)點(diǎn)v的有向鏈路；參數(shù)M是P圈構(gòu)建時(shí)的標(biāo)記鏈路集合。

算法1的第2行，調(diào)用Dijkstra［8］函數(shù)計(jì)算節(jié)點(diǎn)v到u的最短路徑，計(jì)算時(shí)忽略M中的鏈路。因此，算法1計(jì)算出的最短路徑和被標(biāo)記的鏈路是分離的。由于Dijkstra函數(shù)返回的最短路徑是v到u節(jié)點(diǎn)序列，所以算法1的第4行調(diào)用head函數(shù)在節(jié)點(diǎn)序列頭部加入節(jié)點(diǎn)s，使其變成方向是u到v的P圈。

例如，針對(duì)圖1所示的拓?fù)?，傳入的e（u，v）是有向鏈路（1，2），M包含e，則調(diào)用Dijkstra函數(shù)后返回節(jié)點(diǎn)序列｛2，3，1｝，最后返回的P圈是｛1，2，3，1｝。如果是無(wú)法計(jì)算出最短路徑的情況，如傳入的e（u，v）是有向鏈路（3，4），則直接返回空序列。

P圈序列構(gòu)造算法如算法2所示。

算法2的思想是遍歷拓?fù)渲兴墟溌?，確定初始鏈路并構(gòu)造出初始P圈，其他P圈通過已構(gòu)造P圈上的擴(kuò)展鏈路擴(kuò)展得到。如果是無(wú)法構(gòu)造P圈的鏈路，則加入到孤立鏈路集合中。當(dāng)無(wú)法擴(kuò)展出新P圈且拓?fù)渲腥源嬖谖幢闅v的鏈路時(shí)，則會(huì)在未遍歷過的鏈路重新確定初始鏈路并繼續(xù)擴(kuò)展新P圈，直到所有鏈路都被遍歷過。

算法2P圈序列構(gòu)造算法

算法2中1至2行是初始化相關(guān)變量，3至10行是遍歷拓?fù)渲形幢槐闅v的鏈路并生成初始P圈，11至31行的邏輯是根據(jù)初始P圈擴(kuò)展出新P圈。

1至2行中，隊(duì)列R代表最終得到的P圈序列；隊(duì)列O代表孤立鏈路的序列；隊(duì)列T是用來(lái)存儲(chǔ)構(gòu)造出且未被遍歷過的P圈序列，是輔助算法執(zhí)行的隊(duì)列；序列F最開始等于拓?fù)滏溌芳?，存?chǔ)的是未被遍歷過的鏈路。

3至10行中，pcycle函數(shù)即算法1表示的有向P圈構(gòu)造函數(shù)。如果生成的初始P圈是空，則將當(dāng)前鏈路加入到孤立鏈路集合O中，結(jié)束此次循環(huán)。否則，通過enque函數(shù)把生成的P圈加入到R和T中，進(jìn)入擴(kuò)展P圈邏輯。

11至21行中，edge函數(shù)是將以節(jié)點(diǎn)序表示的P圈轉(zhuǎn)換成以有向鏈路表示的P圈，如｛1，2，3，1｝將轉(zhuǎn)換成｛（1，2），（2，3），（3，1）｝。deg函數(shù)是求節(jié)點(diǎn)的節(jié)點(diǎn)度，當(dāng)一條有向鏈路上的兩端節(jié)點(diǎn)的節(jié)點(diǎn)度都大于等于2，該鏈路即為擴(kuò)展鏈路。

22至24行中，為了確保擴(kuò)展出的P圈不同于該鏈路所在的P圈，會(huì)去斷開原P圈中的每一條邊，再嘗試構(gòu)造新P圈。

25至31行中，通過循環(huán)擴(kuò)展出所有包含擴(kuò)展鏈路的P圈，下次循環(huán)會(huì)將上次循環(huán)生成的P圈中鏈路加到標(biāo)記鏈路集合M中。通過hasNewEdge函數(shù)判斷擴(kuò)展出的新P圈是否擁有已生成P圈不包含的鏈路。如果函數(shù)返回是，則將其加入到隊(duì)列R和T中；否則將忽略該P(yáng)圈，并結(jié)束循環(huán)。

按照添加到隊(duì)列R的先后順序定義P圈的優(yōu)先級(jí)大小，先添加到序列R的P圈優(yōu)先級(jí)更高，P圈的優(yōu)先級(jí)將作用于確定鏈路方向上。

由于每條鏈路只會(huì)遍歷一次且拓?fù)渲墟溌窋?shù)目是有限的，所以本算法中的遍歷有終止條件。

為了更形象地說(shuō)明P圈序列構(gòu)造算法，舉例如下。圖2（a）代表示例拓?fù)洹?/p>

圖2 P圈序列構(gòu)造算法示例

初始化序列R、O、T和F。從F中彈出一條鏈路得到初始鏈路（1，2），構(gòu)造出P圈｛1，2，3，1｝加入R、T中。從T中取出并把鏈路（2，3）、（3，1）從F中剔除。

此時(shí)F不為空且無(wú)法擴(kuò)展出新P圈。鏈路（3，4）是鏈路（1，2）的后續(xù)鏈路，從F中彈出初始鏈路（3，4），因?yàn)闊o(wú)法通過（3，4）構(gòu)造P圈，把鏈路（3，4）加入O中。

鏈路（4，5）是鏈路（3，4）的后續(xù)鏈路，彈出初始鏈路（4，5），構(gòu)造P圈｛4，5，7，6，4｝。通過擴(kuò)展鏈路（5，7）擴(kuò)展出P圈｛5，7，10，5｝，刪除F中對(duì)應(yīng)鏈路。

鏈路（4，8）是鏈路（4，5）的后續(xù)鏈路，彈出初始鏈路（4，8），構(gòu)造P圈｛4，8，9，5，4｝，刪除F中對(duì)應(yīng)鏈路。此時(shí)F為空，結(jié)束循環(huán)。最后生成的P圈序列如圖2（b）所示。

2.2 生成路徑

針對(duì)通過上述P圈序列構(gòu)造算法生成的P圈序列，提出一種算法，先通過P圈優(yōu)先級(jí)確定拓?fù)渲墟溌返姆较?，再通過BFS思想，從源節(jié)點(diǎn)src出發(fā)，按鏈路的方向搜索，最終生成從src到其他節(jié)點(diǎn)的工作路徑和保護(hù)路徑集合。

生成工作路徑算法如算法3所示。算法3生成工作路徑算法

算法3中，1至5行是初始化過程；6至13行是通過P圈序列和孤立鏈路集合確定鏈路方向；14至22行是確定pre數(shù)組；23至30行是通過pre數(shù)組確定工作路徑集合。

1至5行中，m表示拓?fù)涞泥徑泳仃嚒re［i］代表第i個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)是第pre［i］個(gè)節(jié)點(diǎn)。U為BFS的輔助隊(duì)列，T為已遍歷節(jié)點(diǎn)的集合，W是工作路徑集合。

6至13行中，按照優(yōu)先級(jí)遍歷P圈序列，當(dāng)某條鏈路在多個(gè)P圈中，該鏈路的方向由優(yōu)先級(jí)最高的P圈方向決定。11至13行表示對(duì)于孤立鏈路集合中的鏈路，規(guī)定其方向是雙向的。最后m保存的是拓?fù)渲兴墟溌返淖罱K方向。

當(dāng)確定拓?fù)渲墟溌贩较蚝?，通過BFS確定src到其他節(jié)點(diǎn)的最短路徑。

保護(hù)路徑集合是從src到其他節(jié)點(diǎn)且逆著鏈路方向的最短路徑集合，因此在生成工作路徑算法上第9、10行將u和v互換，即可得到生成保護(hù)路徑算法。

舉例說(shuō)明，圖2（a）示例拓?fù)渥罱K生成的P圈序列如圖2（b）所示。在生成工作路徑算法中，先通過P圈序列和孤立鏈路集合確定拓?fù)渲墟溌贩较?，如圖3（a）所示。因?yàn)殒溌罚?，5）所在的P圈｛4，5，7，6，4｝比P圈｛4，8，9，5，4｝優(yōu)先級(jí)高，所以該鏈路的方向最終是4指向5。生成保護(hù)路徑算法中，鏈路方向如圖3（b）所示。

圖3 鏈路方向圖

假設(shè)源節(jié)點(diǎn)src為序號(hào)4的節(jié)點(diǎn)，目的節(jié)點(diǎn)集D為其他剩余的節(jié)點(diǎn)。對(duì)應(yīng)的工作路徑集合如圖4（a）所示，保護(hù)路徑集合如圖4（b）所示。

圖4 節(jié)點(diǎn)4的工作路徑和保護(hù)路徑

在生成路徑算法中，通過P圈序列和孤立鏈路集合確定拓?fù)渲墟溌贩较蚝?，從拓?fù)涞娜魏我稽c(diǎn)出發(fā)并沿著鏈路方向能到達(dá)拓?fù)渲械钠渌魏吸c(diǎn)，證明如下。

為便于敘述，現(xiàn)假設(shè)如下：某條初始鏈路e1生成的初始P圈p1；通過p1上的擴(kuò)展鏈路擴(kuò)展出P圈序列R1；另一條初始鏈路生成并擴(kuò)展出P圈序列R2。

情況1：從p1的某一點(diǎn)出發(fā)，當(dāng)?shù)竭_(dá)p1上的某條擴(kuò)展鏈路e2時(shí)，因?yàn)橥ㄟ^e2擴(kuò)展出的P圈p2擁有和e2一致的方向，所以可以通過e2的尾節(jié)點(diǎn)進(jìn)入p2。如圖3（a）中初始P圈｛4，5，7，6，4｝，可通過節(jié)點(diǎn)7進(jìn)入擴(kuò)展P圈｛5，7，10，5｝。同理通過p2上的擴(kuò)展鏈路可以進(jìn)入基于p2擴(kuò)展出的P圈，因此有結(jié)論：從p1上的任意一點(diǎn)能到達(dá)R1中的任意一點(diǎn)。

情況2：從R1中某一個(gè)P圈p3擴(kuò)展出的P圈p4的某一點(diǎn)出發(fā)，當(dāng)?shù)竭_(dá)p3擴(kuò)展出p4的擴(kuò)展鏈路e3，可以通過e3的尾節(jié)點(diǎn)進(jìn)入p3。同理可通過某條擴(kuò)展鏈路進(jìn)入某個(gè)擴(kuò)展出p3的P圈，直到進(jìn)入到初始P圈p1。又因?yàn)榍闆r1結(jié)論，因此有結(jié)論：從R1中的任意一點(diǎn)能達(dá)到R1中的任意一點(diǎn)。

情況3：若R1和R2相鄰，相鄰關(guān)系有兩種情況。如果R1和R2是通過某個(gè)共享節(jié)點(diǎn)連接，如圖5（a）所示，則可以通過共享節(jié)點(diǎn)進(jìn)入相鄰的P圈序列。如果R1和R2是通過一條或多條孤立鏈路連接，如圖5（b）所示，因?yàn)楣铝㈡溌肥请p向的，則可以通過孤立鏈路進(jìn)入相鄰的P圈序列。又因?yàn)榍闆r2結(jié)論，因此得出結(jié)論：從某個(gè)P圈序列的任意一點(diǎn)能達(dá)到相鄰的P圈序列的任意一點(diǎn)。

圖5 P圈序列相鄰情況

情況4：從拓?fù)渲腥我庖稽c(diǎn)出發(fā)。如果該點(diǎn)不屬于任何P圈序列，可通過孤立鏈路進(jìn)入某一個(gè)P圈序列。從某個(gè)P圈序列中某點(diǎn)出發(fā)，可以根據(jù)情況3結(jié)論進(jìn)入相鄰P圈序列，從而進(jìn)入任意P圈序列，最終可以到達(dá)拓?fù)渲腥我庖稽c(diǎn)。

2.3 路由表

BFR通過查詢BIFT轉(zhuǎn)發(fā)多播分組。BIFT由三列組成。第一列表示目的節(jié)點(diǎn)的BFR-id，由SI（Set Identifier）和BitString組合而成，其中SI表示集合識(shí)別碼，用來(lái)標(biāo)識(shí)不同集合中BFR，BitString表示該SI下目的節(jié)點(diǎn)的BFR-id。圖2（a）示例拓?fù)渲?，只有一個(gè)集合，所以SI為0。第二列代表F-BM。第三列代表轉(zhuǎn)發(fā)分組到目的節(jié)點(diǎn)的下一跳BFR。

為了將工作路徑和保護(hù)路徑配置到路由表中，本算法在傳統(tǒng)的BIFT上進(jìn)行了改造。路由表?xiàng)l目分為兩部分，第一部分代表正常情況下路由器執(zhí)行的工作條目；第二部分代表當(dāng)檢測(cè)到工作路徑上鏈路發(fā)生故障時(shí)，路由器執(zhí)行的保護(hù)條目。

針對(duì)圖4（a）對(duì)應(yīng)的工作路徑集合和圖4（b）對(duì)應(yīng)的保護(hù)路徑集合，可得BFR-id為4的BFR的BIFT表，如表1所列。

表1 節(jié)點(diǎn)4的BIFT表

因?yàn)闆]有P圈對(duì)孤立鏈路進(jìn)行保護(hù)，當(dāng)孤立鏈路發(fā)生故障時(shí)，此算法無(wú)法進(jìn)行保護(hù)。

本算法不能保證在同一時(shí)刻對(duì)工作路徑上所有的鏈路進(jìn)行保護(hù)。如果工作路徑上多條鏈路同時(shí)出現(xiàn)故障，只要任意一條鏈路對(duì)應(yīng)的保護(hù)路徑和任一鏈路沒有共享邊，即能同時(shí)對(duì)多條鏈路進(jìn)行保護(hù)；否則，同一時(shí)刻只能保護(hù)其中一個(gè)鏈路。

舉例如下，如圖3所示工作路徑集合和保護(hù)路徑集合。本算法可同時(shí)對(duì)鏈路（1，2）和鏈路（4，5）進(jìn)行保護(hù)，因?yàn)椋?，2）所對(duì)應(yīng)的保護(hù)路徑｛1，3，2｝和（4，5）沒有共享邊，且（4，5）對(duì)應(yīng)的保護(hù)路徑｛4，6，7，5｝和（1，2）沒有共享邊。對(duì)于鏈路（4，5）和鏈路（5，7），因?yàn)椋?，5）對(duì)應(yīng)的保護(hù)路徑｛4，6，7，5｝和鏈路（5，7）有共享邊，則同一時(shí)刻只能保護(hù)其中一條。

3 仿真和結(jié)果分析

3.1 算法結(jié)果

仿真采用NSF網(wǎng)絡(luò)拓?fù)淠Ｐ停?4］（14個(gè)節(jié)點(diǎn)，21條邊），如圖6（a）所示。

圖6 NSF拓?fù)洌ㄌ摼€箭頭表示3個(gè)P圈（P1、P2和P7））

SLA［7］算法會(huì)保存每一個(gè)生成的P圈，因此得到的P圈數(shù)目是巨大的。在算法2中，因?yàn)橛衕asNewEdge函數(shù)的限制條件，只有擴(kuò)展出的P圈擁有已生成的P圈沒有的鏈路時(shí)，才會(huì)保存該P(yáng)圈，因此最終生成的P圈數(shù)目一定不會(huì)超過拓?fù)渲墟溌返膫€(gè)數(shù)，這可以很好地限制P圈數(shù)目。

表2給出了本文所提算法與SLA［7］針對(duì)NSF拓?fù)涞膶?duì)比計(jì)算結(jié)果。

表2 P圈算法的對(duì)比結(jié)果

由表2可見，所提算法生成的P圈個(gè)數(shù)遠(yuǎn)小于SLA。這對(duì)于多播型業(yè)務(wù)樹的構(gòu)造，其計(jì)算復(fù)雜度可以得到有效控制。而先驗(yàn)效率降低的原因，是因?yàn)樗崴惴]有充分利用跨接邊的潛力。此外，所提算法所具備的方向性參數(shù)，可用于多播保護(hù)路徑的進(jìn)一步優(yōu)化。

通過P圈序列構(gòu)造算法對(duì)NSF網(wǎng)絡(luò)構(gòu)造的P圈共有7個(gè)，沒有孤立鏈路。按照優(yōu)先級(jí)排序，生成的P圈序列如表3所示。

表3 NSF的P圈序列

在生成工作路徑算法中，通過P圈序列和孤立鏈路集合確定拓?fù)渲墟溌贩较?，NSF鏈路方向如圖6（b）所示。其中圖6（b）中虛線箭頭表示的P圈有P1、P2和P7，對(duì)應(yīng)表3優(yōu)先級(jí)為1、2和7的P圈，表中其他P圈暫未在圖中標(biāo)出。需要注意的是，P圈方向和鏈路方向沒有必然聯(lián)系，如圖6（b）中P7方向和最終鏈路方向（12，9）相反。鏈路方向需通過算法3和P圈序列確認(rèn)。

通過算法3計(jì)算，可得BFR-id為1和4的BFR的BIFT表，分別如表4和表5所示。

表4 節(jié)點(diǎn)1的BIFT表

表5 節(jié)點(diǎn)4的BIFT表

3.2 快速重路由

每個(gè)BFR通過算法3確定工作路徑和保護(hù)路徑，配置BIFT。當(dāng)檢測(cè)到工作路徑上鏈路出現(xiàn)故障，BFR可以將受影響業(yè)務(wù)迅速切換到保護(hù)路徑上，從而實(shí)現(xiàn)快速重路由，達(dá)到快速恢復(fù)多播業(yè)務(wù)的目的。

在本方案中，采用為BIER分組添加外層的BIER頭部實(shí)現(xiàn)路徑的切換。

為了區(qū)分多播分組進(jìn)入BIER域增加的BIER頭和啟用保護(hù)條目而新增的外層BIER頭，需要在BIER頭中設(shè)置一個(gè)比特大小的標(biāo)記位Dbit作為區(qū)分依據(jù)。本算法利用BIER頭中Rsv［15］字段作為Dbit字段。當(dāng)BFR收到分組BIER頭中Dbit字段為0的分組，將會(huì)查找BIFT中工作條目，并根據(jù)工作條目進(jìn)行轉(zhuǎn)發(fā)分組。相對(duì)地，當(dāng)收到Dbit字段為1的分組，BFR將會(huì)查找BIFT中保護(hù)條目，并根據(jù)保護(hù)條目進(jìn)行轉(zhuǎn)發(fā)分組。

下面舉例說(shuō)明快速重路由過程。

如圖6（a）所示NSF拓?fù)?，?dāng)鏈路（1，2）發(fā)生故障時(shí)，BFR-id為1的BFR檢測(cè)到BFR-id為2的BFR不可達(dá)，此BFR將會(huì)給下一跳是2的BIER分組新加一個(gè)BIER頭，其中BitString設(shè)為2，Dbit字段設(shè)為1，并根據(jù)表4中的保護(hù)條目，轉(zhuǎn)發(fā)給BFR-id為4的BFR。

當(dāng)BFR-id為4的BFR收到該分組后，因?yàn)镈bit字段為1，所以會(huì)查詢自己BIFT中保護(hù)條目，如表5所列，將分組轉(zhuǎn)發(fā)給BFR-id為2的BFR。

當(dāng)BFR-id為2的BFR收到該分組后，發(fā)現(xiàn)BitString代表的BFR是其本身，則會(huì)去掉最外層的BIER頭，接下來(lái)根據(jù)內(nèi)層的BIER頭的BitString查找工作條目繼續(xù)轉(zhuǎn)發(fā)分組。

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

針對(duì)時(shí)延和丟包敏感的多播業(yè)務(wù)，需要采取保護(hù)機(jī)制來(lái)快速恢復(fù)業(yè)務(wù)。BIER是一個(gè)基于分段路由的多播技術(shù)。因?yàn)橹虚g路由器不需要維護(hù)多播樹狀態(tài)，BIER本質(zhì)上等同于IP單播。

本文在利用BIER協(xié)議實(shí)現(xiàn)多播的基礎(chǔ)上，提出了一種全新的基于P圈的快速重路由算法，用以解決鏈路故障導(dǎo)致多播業(yè)務(wù)中斷的問題。通過構(gòu)造出有向的P圈序列確定鏈路方向，分布式計(jì)算每一個(gè)BFR的BIFT。當(dāng)檢測(cè)到鏈路出現(xiàn)故障時(shí)，啟用BIFT的保護(hù)條目來(lái)快速恢復(fù)業(yè)務(wù)。通過本文討論，可以發(fā)現(xiàn)本算法在實(shí)現(xiàn)時(shí)對(duì)BIER協(xié)議改動(dòng)不大，因此適宜快速部署到BIER網(wǎng)絡(luò)中。