BIER 技術(shù)與雙P 圈保護(hù)方案研究

劉結(jié)源，王 斌，王文鼐

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

0 引言

近年來(lái)，隨著IPTV、VR、網(wǎng)絡(luò)直播等新型業(yè)務(wù)的出現(xiàn)，網(wǎng)絡(luò)流量的需求越來(lái)越大，對(duì)組播技術(shù)的要求也不斷提升。常規(guī)組播路由協(xié)議［1-4］依賴于組播轉(zhuǎn)發(fā)樹(shù)（Spanning Tree Protocol，STP）。為實(shí)現(xiàn)常規(guī)組播路由協(xié)議，網(wǎng)絡(luò)中的設(shè)備需要組建組播樹(shù)、減枝組播樹(shù)、維護(hù)組播樹(shù)，還需要為每個(gè)組播組保存狀態(tài)，極大地消耗了網(wǎng)絡(luò)流量。不僅如此，頻繁的收斂和更新組播樹(shù)還會(huì)降低處理效率。為解決上述問(wèn)題，國(guó)際互聯(lián)網(wǎng)工程任務(wù)組（The Internet Engineering Task Force，IETF）提出了位索引顯示復(fù)制協(xié)議（Bit Index Explicit Replication，BIER）［5］。BIER 依據(jù)單播轉(zhuǎn)發(fā)表生成BIER 組播轉(zhuǎn)發(fā)表，然后通過(guò)BIER 報(bào)頭（BIER Header）中位串（BitString）對(duì)應(yīng)位（Bit）的設(shè)置完成數(shù)據(jù)轉(zhuǎn)發(fā)。相較于傳統(tǒng)組播路由協(xié)議，BIER 協(xié)議的優(yōu)點(diǎn)為無(wú)需構(gòu)建組播轉(zhuǎn)發(fā)樹(shù)，且組播路由器的路由表中無(wú)需存儲(chǔ)狀態(tài)信息。然而，BIER 缺乏配置簡(jiǎn)單且高性能的保護(hù)方案，因此該領(lǐng)域還需要更多研究［6］。

1 相關(guān)研究

關(guān)于BIER 的保護(hù)方案，Wijnands 等［7］提出BIER 封裝方法，適用于MPLS 網(wǎng)絡(luò)和非MPLS 網(wǎng)絡(luò)；Merling 等［8］提出一種針對(duì)BIER 的快速重路由方法，并創(chuàng)建了一種包含主路由條目和備用路由條目的位索引轉(zhuǎn)發(fā)表（Bit Index Forwarding Table，BIFT），用于轉(zhuǎn)發(fā)工作和保護(hù)分組，但該方法復(fù)雜度較高，不利于實(shí)際應(yīng)用；Braun 等［9］在SDN 環(huán)境下分別對(duì)傳統(tǒng)組播方案和BIER 方案進(jìn)行了仿真，證實(shí)了BIER 方案的可行性和優(yōu)越性；Papan 等［10］提出修護(hù)鏈路故障的IP快速重路由（FRR）方案，使用BitString 表示保護(hù)路徑，但未考慮與BIER方案的兼容性；Enyedi 等［11］對(duì)最大冗余樹(shù)（Maximally Redundant Tree，MRT）的保護(hù)機(jī)制進(jìn)行了研究，建議在BIER 協(xié)議中使用MRT 提供“1+1”保護(hù)，并提出最大冗余樹(shù)快速重路由（Maximally Redundant Tree Fast Reroute，MRT FRR）方案，但該方案未考慮具體的BIER 封裝方法［12］；韓玉芳［13］提出一種修護(hù)鏈路故障的BIER 方案，該方案為拓?fù)渲械乃墟溌贩峙淞吮Ｗo(hù)環(huán)并為環(huán)分配了比特位，然后定義了BIER 環(huán)轉(zhuǎn)發(fā)表（BIER Ring Forwarding Table，BRFT），指示保護(hù)分組轉(zhuǎn)發(fā)至相應(yīng)的保護(hù)環(huán)，但該方法計(jì)算的環(huán)過(guò)多，時(shí)間復(fù)雜度較高；喻敬海等［14］設(shè)計(jì)了一種BIER 原型系統(tǒng)，該系統(tǒng)由BIER APP、BIER 控制器和BIER 轉(zhuǎn)發(fā)設(shè)備組成，相關(guān)實(shí)驗(yàn)驗(yàn)證了該系統(tǒng)的可擴(kuò)展性和優(yōu)越性；武欣婷［15］設(shè)計(jì)了HF-BIER 協(xié)議的架構(gòu)并進(jìn)行了仿真，拓寬了BIER 協(xié)議的應(yīng)用范圍。

日前很多BIER 保護(hù)方案無(wú)法兼顧配置簡(jiǎn)單、保護(hù)成本低、兼容工作模式等方方面面［16-17］，因此需要一種能夠盡量滿足以上需求的保護(hù)方案，整體環(huán)結(jié)構(gòu)保護(hù)方案便是可行方案之一。P 圈（Preconfiguration Cycle，p-cycle）是一種基于環(huán)結(jié)構(gòu)的FRR 方案［18］，可利用空閑資源預(yù)先設(shè)置環(huán)形通道以實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的快速保護(hù)，其在BIER 中應(yīng)用的難點(diǎn)是保護(hù)效率問(wèn)題［19］。本文提出基于雙P 圈的BIER 保護(hù)方案，通過(guò)聯(lián)合P 圈實(shí)現(xiàn)組播保護(hù)，彌補(bǔ)了其他方案配置復(fù)雜、保護(hù)成本高、工作模式不兼容的缺點(diǎn)。

2 BIER 技術(shù)

支持BIER 協(xié)議的路由器稱為位轉(zhuǎn)發(fā)路由器（Bit-Forwarding Router，BFR）。BIER控制平面協(xié)議在BIER域（BIER domain）內(nèi)運(yùn)行，域內(nèi)的BFR 可以互相交換、轉(zhuǎn)發(fā)所需信息。組播數(shù)據(jù)包從一個(gè)位轉(zhuǎn)發(fā)入口路由器（Bit-Forwarding Ingress Route，BFIR）進(jìn)入BIER 域，并從一個(gè)或多個(gè)位轉(zhuǎn)發(fā)出口路由器（Bit-Forwarding Egress Router，BFER）轉(zhuǎn)發(fā)出BIER 域，轉(zhuǎn)發(fā)過(guò)程中的中間BFR 稱為轉(zhuǎn)接BFR（Transit BFR）。在BIER 域內(nèi)進(jìn)行組播轉(zhuǎn)發(fā)時(shí)，BFIR 先將組播數(shù)據(jù)包封裝成BIER 包，然后將其轉(zhuǎn)發(fā)至BIER 域內(nèi)部，通過(guò)若干transit BFR 轉(zhuǎn)發(fā)，直至到達(dá)BFER，最終轉(zhuǎn)發(fā)出BIER 域。

當(dāng)BFIR 確定組播數(shù)據(jù)包的目的地BFER（s）后會(huì)對(duì)數(shù)據(jù)包進(jìn)行封裝，即添加BIER 報(bào)頭（BIER Header）。BIER 報(bào)頭中最重要的信息為BitString，其是由一組比特序列組成的比特串，其中的每一個(gè)比特只能置位為0 或1，若某個(gè)比特?cái)?shù)值為1，則表示該位對(duì)應(yīng)的BFR 是當(dāng)前數(shù)據(jù)包的BFER，因此BFIR 可以通過(guò)將BFER 的比特位全部置為1，其余置為0 的方式完成BIER 報(bào)頭中BitString 的封裝。例如一個(gè)BSL=4（BSL，BitStringLength，位串長(zhǎng)度）的BIER 域內(nèi)的4 個(gè)路由器編號(hào)分別為1（0001），2（0010），3（0100）和4（1000），當(dāng)目的路由器為路由器3 和路由器4 時(shí)，位串就可以置位為1100。如果BSL 的長(zhǎng)度小于路由器的數(shù)量，則可以通過(guò)SI（序列號(hào)）來(lái)擴(kuò)展，例如BSL=4，SI=1，BitString=0001 表示編號(hào)為5 的路由器。當(dāng)一個(gè)組播組的成員收到數(shù)據(jù)包時(shí)，該路由器對(duì)應(yīng)BitString 的位就會(huì)置0，因此上述BitString 在路由器3 接收到數(shù)據(jù)包后就從1100 置位為1000。在BIER 轉(zhuǎn)發(fā)機(jī)制中，路由器不需要確認(rèn)組播源地址和目的地址，這些信息已經(jīng)包含在BitString 及其變化中。

位索引路由表（Bit Index Routing Table，BIRT）是從BIER 域中的網(wǎng)絡(luò)拓?fù)浞治龆鴣?lái)，通過(guò)BIRT 可以生成位索引轉(zhuǎn)發(fā)表（Bit Index Forwarding Table，BIFT）。如果在BIRT中有若干行擁有相同的SI 和BFR-NBR，則可以采取這些行位串的邏輯OR 運(yùn)算得到一個(gè)對(duì)應(yīng)SI 和BFR-NBR 的組合位掩碼。RFC8279 協(xié)議將該組合位掩碼命名為轉(zhuǎn)發(fā)位掩碼（Forwarding Bit Mask，F(xiàn)-BM）。BIER 的轉(zhuǎn)發(fā)邏輯見(jiàn)圖1。

Table 1 Fundamental cycle generation表1 基本圈生成

Table 2 First expansion case表2 邊擴(kuò)張情況一

Table 3 Second expansion case表3 邊擴(kuò)張情況二

Table 4 Third expansion case表4 邊擴(kuò)張情況三

Fig.1 Schematic diagram of BIER forwarding logic圖1 BIER 轉(zhuǎn)發(fā)邏輯示意圖

如圖1 所示，控制面通過(guò)鏈路狀態(tài)廣播（Link-State Advertisement，LSA）感知拓?fù)渥兓⒏翨IRT 和BIFT，BFR在數(shù)據(jù)面進(jìn)行組播轉(zhuǎn)發(fā)時(shí)通過(guò)查詢BIRT 和BIFT 完成下一跳轉(zhuǎn)的選擇。

3 雙P 圈保護(hù)方案

3.1 P 圈簡(jiǎn)介

P 圈（p-cycle）算法又稱為預(yù)置圈算法，該算法會(huì)預(yù)先設(shè)置一個(gè)P 圈，當(dāng)檢測(cè)到網(wǎng)絡(luò)故障時(shí)會(huì)啟用該P(yáng) 圈進(jìn)行保護(hù)。與傳統(tǒng)環(huán)保護(hù)不同的是，P 圈含有一些跨接鏈路，類似于環(huán)上的弦，可保護(hù)P 圈上的鏈路，因此比傳統(tǒng)環(huán)保護(hù)具有更大的保護(hù)范圍和保護(hù)概率。

P 圈算法主要包括SLA 算法、SP-Add 算法和SP-Expand 算法等［20-23］。針對(duì)不同業(yè)務(wù)，P 圈的配置方式也不相同，主要分為靜態(tài)P 圈和動(dòng)態(tài)P 圈兩種。靜態(tài)P 圈主要針對(duì)靜態(tài)業(yè)務(wù)，即已知網(wǎng)絡(luò)資源使用情況，預(yù)先配置一組P 圈，一旦P 圈配置成功則不再改變。靜態(tài)P 圈的配置方法主要為整數(shù)線性規(guī)劃（Integral Linear Programming，ILP），通過(guò)構(gòu)造網(wǎng)絡(luò)模型確定優(yōu)化目標(biāo)，給定一系列約束條件求得P 圈候選集合，通過(guò)ILP 的計(jì)算可以得出最優(yōu)P 圈組合，但當(dāng)網(wǎng)絡(luò)很大時(shí)該種方法效率不高。動(dòng)態(tài)P 圈主要針對(duì)動(dòng)態(tài)業(yè)務(wù)，即業(yè)務(wù)在傳送過(guò)程中可根據(jù)網(wǎng)絡(luò)狀況實(shí)時(shí)修改P 圈配置，一旦當(dāng)前P 圈不能有效保護(hù)網(wǎng)絡(luò)，將釋放資源重新配置。動(dòng)態(tài)P 圈的配置方法主要為啟發(fā)式算法。

本文使用grow 算法生成和擴(kuò)展動(dòng)態(tài)雙P 圈。grow 算法的實(shí)質(zhì)就是在生成一個(gè)基本圈的基礎(chǔ)上通過(guò)不斷擴(kuò)張使得所有組播目的節(jié)點(diǎn)都在P 圈上。雙P 圈中的P1 圈鏈路可能包含最短路徑樹(shù)的鏈路，這里的最短路徑樹(shù)即BIER 組播工作路徑，是基于迪杰斯特拉算法生成的。

3.2 grow 算法描述

grow 算法是基于基本圈展開(kāi)的，因此首先需要生成基本圈。一個(gè)圈最少需要3 個(gè)節(jié)點(diǎn)，因此一個(gè)基本圈最簡(jiǎn)單的結(jié)構(gòu)為3 個(gè)度數(shù)為2 的節(jié)點(diǎn)兩兩相連?；救Φ臉?gòu)成算法偽代碼如表1 所示。

在表1 中，參數(shù)G為網(wǎng)絡(luò)拓?fù)洌枪?jié)點(diǎn)集合V和鏈路集合E的序偶；參數(shù)e是從節(jié)點(diǎn)u指向節(jié)點(diǎn)v的有向鏈路的鏈路成本，即COST；參數(shù)vs為P 圈構(gòu)建時(shí)的源節(jié)點(diǎn)。算法的1～6 行找出了與源節(jié)點(diǎn)直連的鏈路成本最低的兩個(gè)節(jié)點(diǎn)va、vb，7～8 行在去除了邊ea、eb的網(wǎng)絡(luò)拓?fù)渲惺褂玫辖芩固乩惴ㄕ页鰒a→vb的最短路徑P。如果P不為空，則將源節(jié)點(diǎn)加入P形成基本圈。

對(duì)于源節(jié)點(diǎn)來(lái)說(shuō)，與其直接相連的節(jié)點(diǎn)是固定的，因此鏈路成本最低的兩個(gè)節(jié)點(diǎn)也是確定的，在這兩個(gè)節(jié)點(diǎn)之間使用迪杰斯特拉算法計(jì)算出來(lái)的最短路徑也是確定的。如果存在兩條及以上相同鏈路成本的路徑，則可以通過(guò)節(jié)點(diǎn)ID、路徑節(jié)點(diǎn)跳數(shù)等信息確定唯一路徑，從而保證基本圈的唯一性，其中節(jié)點(diǎn)ID 可以根據(jù)BIER 域中設(shè)備的BFRid 確定。

構(gòu)建完基本圈后需要使用grow 算法進(jìn)行擴(kuò)張，對(duì)基本圈的每條邊進(jìn)行判定，如果該邊兩個(gè)末端節(jié)點(diǎn)的度數(shù)均≥3才可以進(jìn)行擴(kuò)張。當(dāng)邊的兩個(gè)末端節(jié)點(diǎn)有一個(gè)度數(shù)等于2且該節(jié)點(diǎn)不是目的節(jié)點(diǎn)時(shí)，會(huì)進(jìn)行擴(kuò)邊，即沿著該點(diǎn)度數(shù)為2 的邊進(jìn)行延伸，直到末端節(jié)點(diǎn)度數(shù)≥3，從而進(jìn)行下一步擴(kuò)張。

在基本圈的邊擴(kuò)張中會(huì)遇到3 種情況，分別為有多個(gè)目的節(jié)點(diǎn)與邊末端節(jié)點(diǎn)直連，有一個(gè)目的節(jié)點(diǎn)與邊末端節(jié)點(diǎn)直連以及沒(méi)有目的節(jié)點(diǎn)與邊末端節(jié)點(diǎn)直連，具體如圖2所示，其中粗線為基本圈，灰色節(jié)點(diǎn)為組播組目的節(jié)點(diǎn)。

Fig.2 First expansion case（a），second expansion case（b）and third expansion case（c）圖2 擴(kuò)張情況一（a）、擴(kuò)張情況二（b）與擴(kuò)張情況三（c）

對(duì)于圖2（a）中的情況，應(yīng)該在多個(gè)目的節(jié)點(diǎn)中找到距離該邊最近的一個(gè)目的節(jié)點(diǎn)，確定該目的節(jié)點(diǎn)到該邊的最短路徑，再尋找一條與該最短路徑不相交的另一條路徑，該路徑的目的節(jié)點(diǎn)為邊的另一個(gè)末端節(jié)點(diǎn)，從而完成邊的擴(kuò)張。該種情況的偽代碼如表2 所示。在表2 中，es（us，vs）為節(jié)點(diǎn)us到vs的初始邊，D為目的節(jié)點(diǎn)集合，S為已在圈中的節(jié)點(diǎn)集合。第1～8 行是計(jì)算邊兩個(gè)末端節(jié)點(diǎn)相連的最短目的節(jié)點(diǎn)，第9～14 行是在最短目的節(jié)點(diǎn)找到之后，運(yùn)用迪杰斯特拉算法在去除已在圈中路徑的拓?fù)渲杏?jì)算該目的節(jié)點(diǎn)到另一末端節(jié)點(diǎn)的最短路徑。如果找到的最短路徑不為空，則將其壓入圈中，返回已完成擴(kuò)張的P 圈。

對(duì)于圖2（b）中的情況，由于直連的目的節(jié)點(diǎn)是唯一的，只需在表2 算法的基礎(chǔ)上進(jìn)行改良即可。該種情況的偽代碼如表3 所示。在表3 中，us為連接該唯一直連目的節(jié)點(diǎn)的末端節(jié)點(diǎn)。如果有兩個(gè)末端節(jié)點(diǎn)同時(shí)直連至該目的節(jié)點(diǎn)，則us為路徑成本較小的末端節(jié)點(diǎn)。

對(duì)于圖2（c）中的情況，應(yīng)計(jì)算目的節(jié)點(diǎn)集合中各個(gè)節(jié)點(diǎn)到兩個(gè)末端節(jié)點(diǎn)的最短路徑之和，將最小的和代表的兩條路徑確定為擴(kuò)張的邊。該部分偽代碼如表4 所示。在表4 中，el為目的節(jié)點(diǎn)至兩個(gè)末端節(jié)點(diǎn)的最短路徑成本之和，vl為目的節(jié)點(diǎn)至兩個(gè)末端節(jié)點(diǎn)的最短路徑。算法的第3～7 行為向el和vl兩個(gè)空列表中填充信息，其中第7 行的reverse（）函數(shù)功能為倒置，使得P1+P2為一條相連的路徑。第8～10行為選出成本列表el中最小值的索引號(hào)，將擴(kuò)邊P設(shè)為路徑列表中vl相應(yīng)的值。算法的最后為將擴(kuò)邊P加入原P 圈S并返回。

對(duì)于圖2（a）的情況，兩個(gè)末端節(jié)點(diǎn)不在圈中且與之直連的目的節(jié)點(diǎn)數(shù)量固定，鏈路成本最低的節(jié)點(diǎn)唯一，從該成本最低點(diǎn)到另一末端節(jié)點(diǎn)的最短路徑也唯一。對(duì)于圖2（b）的情況，唯一的直連目的節(jié)點(diǎn)構(gòu)成的擴(kuò)張是唯一的。對(duì)于圖2（c）的情況，目的節(jié)點(diǎn)集合中到兩個(gè)末端節(jié)點(diǎn)的最短路徑之和的最小值是唯一的。

以上即為使用grow 算法擴(kuò)張生成P 圈的過(guò)程。對(duì)于雙P 圈算法來(lái)說(shuō)，運(yùn)行一次grow 算法生成的P 圈即為P1 圈。在網(wǎng)絡(luò)拓?fù)渲袑⒐ぷ髀窂降淖疃搪窂綐?shù)去掉，再次運(yùn)行g(shù)row 算法即生成P2 圈。圖3 所示的網(wǎng)絡(luò)拓?fù)渖傻碾pP 圈如圖4 所示，其中源節(jié)點(diǎn)為1，目的節(jié)點(diǎn)為3、4、5，箭頭為最短路徑樹(shù)，粗線為P1 圈，虛線為P2 圈，粗虛線為P1 圈與P2圈重合的邊。

Fig.3 The shortest path tree of network topology圖3 網(wǎng)絡(luò)拓?fù)涞淖疃搪窂綐?shù)

Fig.4 Double P-cycle of network topology圖4 網(wǎng)絡(luò)拓?fù)涞碾pp 圈

對(duì)于圖3 中的拓?fù)洌?dāng)不在P1 圈上的2-3 鏈路出現(xiàn)故障時(shí)，可直接通過(guò)P1 圈進(jìn)行保護(hù)，即1-3 或1-2-4-5-3；當(dāng)在P1 圈上的2-4 鏈路出現(xiàn)故障時(shí)，此時(shí)不可通過(guò)P1 圈保護(hù)而是通過(guò)P2 圈保護(hù)，保護(hù)鏈路為1-7-8-4 和1-3-5-4。雙P 圈方案相對(duì)于傳統(tǒng)P 圈方案的優(yōu)勢(shì)為保護(hù)成本低、適用性強(qiáng)、保護(hù)效率高，這里的保護(hù)成本包括鏈路成本、鏈路節(jié)點(diǎn)數(shù)等。例如，圖3 中2-5 鏈路故障的傳統(tǒng)P 圈保護(hù)為1-7-8-4-5 或1-3-5，鏈路成本比雙P 圈的1-2-4-5 高。如果是傳統(tǒng)雙P 圈，即路徑完全分離的兩個(gè)P 圈，則對(duì)節(jié)點(diǎn)度數(shù)有較高要求，即節(jié)點(diǎn)度數(shù)都要≥4，而雙P 圈方案對(duì)節(jié)點(diǎn)度數(shù)的要求降低，適用性更強(qiáng)。

3.3 組播分組的BIER 封裝

工作BIFT 即正常的BIER 轉(zhuǎn)發(fā)表。本文采用VLAN 封裝的形式實(shí)現(xiàn)BIFT 的保護(hù)，因此保護(hù)表可以省去。雙P 圈保護(hù)封裝方案采用VLAN 實(shí)現(xiàn)，即在生成P1 圈時(shí)，將P1 圈上節(jié)點(diǎn)端口的VLAN 設(shè)置為P1 圈專有VLAN，例如VLANID 設(shè)為101；在生成P2 圈時(shí)，將P2 圈上節(jié)點(diǎn)端口的VLAN設(shè)置為P2 圈專有VLAN，例如VLAN-ID 設(shè)為102。端口VLAN 為trunk 模式，可以接收和發(fā)送多個(gè)VLAN 報(bào)文。對(duì)于圖3 網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)1 來(lái)說(shuō)，1-2 端口設(shè)置為port trunk allow-pass vlan 101；1-3 端口設(shè)置為port trunk allow-pass vlan 101 102；1-7端口設(shè)置為port trunk allow-pass vlan 102。

正常情況下，BIER 工作分組帶有默認(rèn)VLAN 頭，即VLAN-ID=1。當(dāng)BIER 分組遇到故障時(shí)，檢查最短路徑P1圈是否完好，如果完好，則加上P1 圈專有VLAN 頭，即VLAN-ID=101；如果P1 圈不完好，則檢查非最短路徑P2 圈是否完好，如果完好，則加上P2 圈專有VLAN 頭，即VLANID=102；如果P2 圈亦不完好，則丟棄分組。當(dāng)P 圈上的鏈路發(fā)生故障時(shí)，故障相鄰的兩個(gè)節(jié)點(diǎn)會(huì)在P 圈的VLAN 上進(jìn)行廣播，使得P 圈上的節(jié)點(diǎn)禁用該VLAN。至此，檢查P圈是否完好的操作通過(guò)端口VLAN 是否禁用即可完成。

接下來(lái)是組播分組的BIER 封裝形式，圖4 中工作數(shù)據(jù)的包封裝格式如圖5 所示。其中，VLAN 表示該組播分組如何轉(zhuǎn)發(fā)，如果VLAN-ID=1 即默認(rèn)VLAN，按照工作BIFT 進(jìn)行轉(zhuǎn)發(fā)；如果VLAN-ID 為P1 圈專有VLAN，如101，則在VLAN-ID=101上轉(zhuǎn)發(fā)；如 果VLAN-ID 為P2 圈專有VLAN則同法處理。SD 表示BIER 域，一般標(biāo)為0。SI 表示序列號(hào)，用于擴(kuò)展BitString 長(zhǎng)度。BitString 為目的節(jié)點(diǎn)位串，在位串上為1 的標(biāo)志位表示對(duì)應(yīng)BFR-ID 的路由器為目的節(jié)點(diǎn)。Data 表示負(fù)載數(shù)據(jù)。

Fig.5 Message encapsulation format of BIER圖5 BIER 報(bào)文封裝格式

3.3.1 工作轉(zhuǎn)發(fā)

BFIR 封裝BIER 組播數(shù)據(jù)包并依據(jù)工作BIFT 進(jìn)行工作轉(zhuǎn)發(fā)的步驟為：

（1）確定數(shù)據(jù)包的SI、BitString 和SD。

（2）如果BitString 完全由0 組成則丟棄該數(shù)據(jù)包，轉(zhuǎn)發(fā)過(guò)程已經(jīng)完成，否則執(zhí)行步驟（3）。

（3）找到當(dāng)前BFR 的BFR-id 對(duì)應(yīng)的位串位k。

（4）如果位k 置位為1 則復(fù)制數(shù)據(jù)包，并發(fā)送拷貝到組播流頂層，然后將位k 置位為0，若此時(shí)位串全為0 則轉(zhuǎn)至步驟（2），否則進(jìn)行步驟（5）。

（5）使用SI 和BitString作為索引查詢當(dāng)前BFR 的BIFT。

（6）將BIFT 的F-BM 掩碼與BitString 進(jìn)行與運(yùn)算，得到新的BitString 及其對(duì)應(yīng)BFR-NBR。

（7）復(fù)制數(shù)據(jù)包，然后將新的BitString 和拷貝轉(zhuǎn)發(fā)到步驟（6）中得到BFR-NBR，該BFR-NBR 轉(zhuǎn)步驟（3），原始BFR 轉(zhuǎn)步驟（8）。

（8）通過(guò)BitString 與F-BM 掩碼的逆反運(yùn)算更新原始數(shù)據(jù)包的位串，若全0 則丟棄，否則轉(zhuǎn)至步驟（5）。

在工作BIFT 中查找時(shí)，可能會(huì)有一個(gè)BFR-NBR 對(duì)應(yīng)多個(gè)目的地的情況，此時(shí)F-BM 就解決了查找次數(shù)的問(wèn)題，沒(méi)有必要為每個(gè)BFER 做單獨(dú)查詢。

3.3.2 保護(hù)轉(zhuǎn)發(fā)

BFIR 封裝BIER 組播數(shù)據(jù)包進(jìn)行保護(hù)轉(zhuǎn)發(fā)的步驟為：

（1）檢查P1 圈是否完好，檢查所有端口是否包含P1 圈的專有VLAN，如果包含則執(zhí)行步驟（2），否則執(zhí)行步驟（3）。

（2）將數(shù)據(jù)包VLAN 頭中的VLAN-ID（默認(rèn)VLAN-ID=1）更換為P1 圈的專有VLAN-ID，隨后在該VLAN 上轉(zhuǎn)發(fā)保護(hù)數(shù)據(jù)包，收到數(shù)據(jù)包的節(jié)點(diǎn)檢查自身BFR-ID 對(duì)應(yīng)于數(shù)據(jù)包中BitString 字段的標(biāo)志位是否為1。是1 則復(fù)制數(shù)據(jù)包，并發(fā)送拷貝到組播流頂層，然后將該位置位為0。若此時(shí)BitString 字段為全0 則丟棄該數(shù)據(jù)包，轉(zhuǎn)發(fā)過(guò)程完成，否則繼續(xù)執(zhí)行步驟（2）；若標(biāo)志位為0 則繼續(xù)執(zhí)行步驟（2）。

（3）檢查P2 圈是否完好，檢查所有端口是否包含P2 圈的專有VLAN，如果包含則執(zhí)行步驟（4），否則執(zhí)行步驟（5）。

（4）將數(shù)據(jù)包VLAN 頭中的VLAN-ID（默認(rèn)VLAN-ID=1）更換為P2 圈的專有VLAN-ID，隨后在該VLAN 上轉(zhuǎn)發(fā)保護(hù)數(shù)據(jù)包，收到數(shù)據(jù)包的節(jié)點(diǎn)檢查自身BFR-ID 對(duì)應(yīng)于數(shù)據(jù)包中BitString 字段的標(biāo)志位是否為1。是1 則復(fù)制數(shù)據(jù)包，并發(fā)送拷貝至組播流頂層，然后將該位置位為0。若此時(shí)BitString 字段為全0 則丟棄該數(shù)據(jù)包，轉(zhuǎn)發(fā)過(guò)程完成，否則繼續(xù)執(zhí)行步驟（4）；若標(biāo)志位為0 則繼續(xù)執(zhí)行步驟（4）。

（5）P1圈和P2圈均非完好，無(wú)法進(jìn)行保護(hù)，丟棄數(shù)據(jù)包。圖3所示的網(wǎng)絡(luò)拓?fù)渫暾霓D(zhuǎn)發(fā)報(bào)文過(guò)程如圖6所示。

Fig.6 Forward message processing of BIER圖6 BIER 轉(zhuǎn)發(fā)報(bào)文處理

3.4 仿真結(jié)果分析

P4lang（P4-language）是一門主要用于數(shù)據(jù)平面且與協(xié)議無(wú)關(guān)的編程語(yǔ)言，其運(yùn)行效率高、結(jié)構(gòu)清晰，且協(xié)議獨(dú)立、目標(biāo)獨(dú)立［24］。P4-BIER 仿真模塊包括BIER-P4 架構(gòu)模型、BIER-P4 程序、p4c 編譯器、目標(biāo)設(shè)置文件以及在RUNTIME 中通過(guò)端口交互信息更新的BIRT 和BIFT。網(wǎng)絡(luò)拓?fù)湫畔⒉捎肅OST-239 歐洲測(cè)量拓?fù)洌?5］，如圖7 所示，含有11 個(gè)網(wǎng)絡(luò)設(shè)備，26 條網(wǎng)絡(luò)鏈路。

Fig.7 Test topology of BIER圖7 BIER 測(cè)試拓?fù)?/p>

在如圖7 所示的網(wǎng)絡(luò)拓?fù)渲?，每次選取更多數(shù)量的組播目的節(jié)點(diǎn)，將其作為組播組成員進(jìn)行組播轉(zhuǎn)發(fā)。每次組播轉(zhuǎn)發(fā)會(huì)計(jì)算節(jié)點(diǎn)的保護(hù)性能，以此檢驗(yàn)雙P 圈方案的優(yōu)勢(shì)。以傳統(tǒng)P 圈方案作為對(duì)照，仿真結(jié)果如圖8、圖9 所示。

Fig.8 Comparison of average node protection cost圖8 平均節(jié)點(diǎn)保護(hù)成本比較

由圖8 可知，隨著節(jié)點(diǎn)數(shù)的增加，兩種方法在平均節(jié)點(diǎn)保護(hù)成本上均表現(xiàn)為增長(zhǎng)趨勢(shì)，但雙P 圈方案在增幅上小于傳統(tǒng)P 圈方案，平均節(jié)點(diǎn)保護(hù)成本下降了30.8%。這是由于傳統(tǒng)P 圈方案不能有效利用正常工作的最短路徑鏈接，而雙P 圈方案中的P1 圈可有效利用可以工作的最短路徑，在無(wú)法使用P1 圈進(jìn)行保護(hù)的情況下再使用路徑分離的P2 圈進(jìn)行保護(hù)，有效降低了平均保護(hù)成本。

Fig.9 Comparison of probability of network packet loss圖9 網(wǎng)絡(luò)報(bào)文丟失概率比較

網(wǎng)絡(luò)報(bào)文丟失概率為網(wǎng)絡(luò)中每條鏈路的失效概率相同時(shí)，受故障影響的節(jié)點(diǎn)對(duì)數(shù)量與網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間的比值。由圖9 可知，雙P 圈方案比傳統(tǒng)P 圈方案的故障保護(hù)率更高，網(wǎng)絡(luò)報(bào)文丟失概率下降了16.6%，這是由于雙P圈的聯(lián)合保護(hù)范圍更廣。

4 結(jié)語(yǔ)

BIER 協(xié)議是對(duì)傳統(tǒng)組播協(xié)議的一次創(chuàng)新，本文通過(guò)對(duì)BIER 協(xié)議架構(gòu)和數(shù)據(jù)平面進(jìn)行分析與研究，對(duì)BIER 保護(hù)方案有了更深刻的認(rèn)識(shí)，并基于此提出了配置簡(jiǎn)單且性能改進(jìn)的雙P 圈BIER 保護(hù)方案。該方案可對(duì)單鏈路故障實(shí)現(xiàn)有效保護(hù)，但對(duì)于多鏈路故障則不能穩(wěn)定地實(shí)現(xiàn)保護(hù)，后續(xù)工作可對(duì)此進(jìn)行改進(jìn)，研發(fā)多鏈路故障的解決方案。