BIER 技術與雙P 圈保護方案研究

劉結源，王 斌，王文鼐

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

0 引言

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

1 相關研究

關于BIER 的保護方案，Wijnands 等［7］提出BIER 封裝方法，適用于MPLS 網絡和非MPLS 網絡；Merling 等［8］提出一種針對BIER 的快速重路由方法，并創建了一種包含主路由條目和備用路由條目的位索引轉發表（Bit Index Forwarding Table，BIFT），用于轉發工作和保護分組，但該方法復雜度較高，不利于實際應用；Braun 等［9］在SDN 環境下分別對傳統組播方案和BIER 方案進行了仿真，證實了BIER 方案的可行性和優越性；Papan 等［10］提出修護鏈路故障的IP快速重路由（FRR）方案，使用BitString 表示保護路徑，但未考慮與BIER方案的兼容性；Enyedi 等［11］對最大冗余樹（Maximally Redundant Tree，MRT）的保護機制進行了研究，建議在BIER 協議中使用MRT 提供“1+1”保護，并提出最大冗余樹快速重路由（Maximally Redundant Tree Fast Reroute，MRT FRR）方案，但該方案未考慮具體的BIER 封裝方法［12］；韓玉芳［13］提出一種修護鏈路故障的BIER 方案，該方案為拓撲中的所有鏈路分配了保護環并為環分配了比特位，然后定義了BIER 環轉發表（BIER Ring Forwarding Table，BRFT），指示保護分組轉發至相應的保護環，但該方法計算的環過多，時間復雜度較高；喻敬海等［14］設計了一種BIER 原型系統，該系統由BIER APP、BIER 控制器和BIER 轉發設備組成，相關實驗驗證了該系統的可擴展性和優越性；武欣婷［15］設計了HF-BIER 協議的架構并進行了仿真，拓寬了BIER 協議的應用范圍。

日前很多BIER 保護方案無法兼顧配置簡單、保護成本低、兼容工作模式等方方面面［16-17］，因此需要一種能夠盡量滿足以上需求的保護方案，整體環結構保護方案便是可行方案之一。P 圈（Preconfiguration Cycle，p-cycle）是一種基于環結構的FRR 方案［18］，可利用空閑資源預先設置環形通道以實現對網絡的快速保護，其在BIER 中應用的難點是保護效率問題［19］。本文提出基于雙P 圈的BIER 保護方案，通過聯合P 圈實現組播保護，彌補了其他方案配置復雜、保護成本高、工作模式不兼容的缺點。

2 BIER 技術

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

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

位索引路由表（Bit Index Routing Table，BIRT）是從BIER 域中的網絡拓撲分析而來，通過BIRT 可以生成位索引轉發表（Bit Index Forwarding Table，BIFT）。如果在BIRT中有若干行擁有相同的SI 和BFR-NBR，則可以采取這些行位串的邏輯OR 運算得到一個對應SI 和BFR-NBR 的組合位掩碼。RFC8279 協議將該組合位掩碼命名為轉發位掩碼（Forwarding Bit Mask，F-BM）。BIER 的轉發邏輯見圖1。

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

Table 2 First expansion case表2 邊擴張情況一

Table 3 Second expansion case表3 邊擴張情況二

Table 4 Third expansion case表4 邊擴張情況三

Fig.1 Schematic diagram of BIER forwarding logic圖1 BIER 轉發邏輯示意圖

如圖1 所示，控制面通過鏈路狀態廣播（Link-State Advertisement，LSA）感知拓撲變化并更新BIRT 和BIFT，BFR在數據面進行組播轉發時通過查詢BIRT 和BIFT 完成下一跳轉的選擇。

3 雙P 圈保護方案

3.1 P 圈簡介

P 圈（p-cycle）算法又稱為預置圈算法，該算法會預先設置一個P 圈，當檢測到網絡故障時會啟用該P 圈進行保護。與傳統環保護不同的是，P 圈含有一些跨接鏈路，類似于環上的弦，可保護P 圈上的鏈路，因此比傳統環保護具有更大的保護范圍和保護概率。

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

本文使用grow 算法生成和擴展動態雙P 圈。grow 算法的實質就是在生成一個基本圈的基礎上通過不斷擴張使得所有組播目的節點都在P 圈上。雙P 圈中的P1 圈鏈路可能包含最短路徑樹的鏈路，這里的最短路徑樹即BIER 組播工作路徑，是基于迪杰斯特拉算法生成的。

3.2 grow 算法描述

grow 算法是基于基本圈展開的，因此首先需要生成基本圈。一個圈最少需要3 個節點，因此一個基本圈最簡單的結構為3 個度數為2 的節點兩兩相連。基本圈的構成算法偽代碼如表1 所示。

在表1 中，參數G為網絡拓撲，是節點集合V和鏈路集合E的序偶；參數e是從節點u指向節點v的有向鏈路的鏈路成本，即COST；參數vs為P 圈構建時的源節點。算法的1～6 行找出了與源節點直連的鏈路成本最低的兩個節點va、vb，7～8 行在去除了邊ea、eb的網絡拓撲中使用迪杰斯特拉算法找出va→vb的最短路徑P。如果P不為空，則將源節點加入P形成基本圈。

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

構建完基本圈后需要使用grow 算法進行擴張，對基本圈的每條邊進行判定，如果該邊兩個末端節點的度數均≥3才可以進行擴張。當邊的兩個末端節點有一個度數等于2且該節點不是目的節點時，會進行擴邊，即沿著該點度數為2 的邊進行延伸，直到末端節點度數≥3，從而進行下一步擴張。

在基本圈的邊擴張中會遇到3 種情況，分別為有多個目的節點與邊末端節點直連，有一個目的節點與邊末端節點直連以及沒有目的節點與邊末端節點直連，具體如圖2所示，其中粗線為基本圈，灰色節點為組播組目的節點。

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

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

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

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

對于圖2（a）的情況，兩個末端節點不在圈中且與之直連的目的節點數量固定，鏈路成本最低的節點唯一，從該成本最低點到另一末端節點的最短路徑也唯一。對于圖2（b）的情況，唯一的直連目的節點構成的擴張是唯一的。對于圖2（c）的情況，目的節點集合中到兩個末端節點的最短路徑之和的最小值是唯一的。

以上即為使用grow 算法擴張生成P 圈的過程。對于雙P 圈算法來說，運行一次grow 算法生成的P 圈即為P1 圈。在網絡拓撲中將工作路徑的最短路徑樹去掉，再次運行grow 算法即生成P2 圈。圖3 所示的網絡拓撲生成的雙P 圈如圖4 所示，其中源節點為1，目的節點為3、4、5，箭頭為最短路徑樹，粗線為P1 圈，虛線為P2 圈，粗虛線為P1 圈與P2圈重合的邊。

Fig.3 The shortest path tree of network topology圖3 網絡拓撲的最短路徑樹

Fig.4 Double P-cycle of network topology圖4 網絡拓撲的雙p 圈

對于圖3 中的拓撲，當不在P1 圈上的2-3 鏈路出現故障時，可直接通過P1 圈進行保護，即1-3 或1-2-4-5-3；當在P1 圈上的2-4 鏈路出現故障時，此時不可通過P1 圈保護而是通過P2 圈保護，保護鏈路為1-7-8-4 和1-3-5-4。雙P 圈方案相對于傳統P 圈方案的優勢為保護成本低、適用性強、保護效率高，這里的保護成本包括鏈路成本、鏈路節點數等。例如，圖3 中2-5 鏈路故障的傳統P 圈保護為1-7-8-4-5 或1-3-5，鏈路成本比雙P 圈的1-2-4-5 高。如果是傳統雙P 圈，即路徑完全分離的兩個P 圈，則對節點度數有較高要求，即節點度數都要≥4，而雙P 圈方案對節點度數的要求降低，適用性更強。

3.3 組播分組的BIER 封裝

工作BIFT 即正常的BIER 轉發表。本文采用VLAN 封裝的形式實現BIFT 的保護，因此保護表可以省去。雙P 圈保護封裝方案采用VLAN 實現，即在生成P1 圈時，將P1 圈上節點端口的VLAN 設置為P1 圈專有VLAN，例如VLANID 設為101；在生成P2 圈時，將P2 圈上節點端口的VLAN設置為P2 圈專有VLAN，例如VLAN-ID 設為102。端口VLAN 為trunk 模式，可以接收和發送多個VLAN 報文。對于圖3 網絡拓撲中的節點1 來說，1-2 端口設置為port trunk allow-pass vlan 101；1-3 端口設置為port trunk allow-pass vlan 101 102；1-7端口設置為port trunk allow-pass vlan 102。

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

接下來是組播分組的BIER 封裝形式，圖4 中工作數據的包封裝格式如圖5 所示。其中，VLAN 表示該組播分組如何轉發，如果VLAN-ID=1 即默認VLAN，按照工作BIFT 進行轉發；如果VLAN-ID 為P1 圈專有VLAN，如101，則在VLAN-ID=101上轉發；如 果VLAN-ID 為P2 圈專有VLAN則同法處理。SD 表示BIER 域，一般標為0。SI 表示序列號，用于擴展BitString 長度。BitString 為目的節點位串，在位串上為1 的標志位表示對應BFR-ID 的路由器為目的節點。Data 表示負載數據。

Fig.5 Message encapsulation format of BIER圖5 BIER 報文封裝格式

3.3.1 工作轉發

BFIR 封裝BIER 組播數據包并依據工作BIFT 進行工作轉發的步驟為：

（1）確定數據包的SI、BitString 和SD。

（2）如果BitString 完全由0 組成則丟棄該數據包，轉發過程已經完成，否則執行步驟（3）。

（3）找到當前BFR 的BFR-id 對應的位串位k。

（4）如果位k 置位為1 則復制數據包，并發送拷貝到組播流頂層，然后將位k 置位為0，若此時位串全為0 則轉至步驟（2），否則進行步驟（5）。

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

（6）將BIFT 的F-BM 掩碼與BitString 進行與運算，得到新的BitString 及其對應BFR-NBR。

（7）復制數據包，然后將新的BitString 和拷貝轉發到步驟（6）中得到BFR-NBR，該BFR-NBR 轉步驟（3），原始BFR 轉步驟（8）。

（8）通過BitString 與F-BM 掩碼的逆反運算更新原始數據包的位串，若全0 則丟棄，否則轉至步驟（5）。

在工作BIFT 中查找時，可能會有一個BFR-NBR 對應多個目的地的情況，此時F-BM 就解決了查找次數的問題，沒有必要為每個BFER 做單獨查詢。

3.3.2 保護轉發

BFIR 封裝BIER 組播數據包進行保護轉發的步驟為：

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

（2）將數據包VLAN 頭中的VLAN-ID（默認VLAN-ID=1）更換為P1 圈的專有VLAN-ID，隨后在該VLAN 上轉發保護數據包，收到數據包的節點檢查自身BFR-ID 對應于數據包中BitString 字段的標志位是否為1。是1 則復制數據包，并發送拷貝到組播流頂層，然后將該位置位為0。若此時BitString 字段為全0 則丟棄該數據包，轉發過程完成，否則繼續執行步驟（2）；若標志位為0 則繼續執行步驟（2）。

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

（4）將數據包VLAN 頭中的VLAN-ID（默認VLAN-ID=1）更換為P2 圈的專有VLAN-ID，隨后在該VLAN 上轉發保護數據包，收到數據包的節點檢查自身BFR-ID 對應于數據包中BitString 字段的標志位是否為1。是1 則復制數據包，并發送拷貝至組播流頂層，然后將該位置位為0。若此時BitString 字段為全0 則丟棄該數據包，轉發過程完成，否則繼續執行步驟（4）；若標志位為0 則繼續執行步驟（4）。

（5）P1圈和P2圈均非完好，無法進行保護，丟棄數據包。圖3所示的網絡拓撲完整的轉發報文過程如圖6所示。

Fig.6 Forward message processing of BIER圖6 BIER 轉發報文處理

3.4 仿真結果分析

P4lang（P4-language）是一門主要用于數據平面且與協議無關的編程語言，其運行效率高、結構清晰，且協議獨立、目標獨立［24］。P4-BIER 仿真模塊包括BIER-P4 架構模型、BIER-P4 程序、p4c 編譯器、目標設置文件以及在RUNTIME 中通過端口交互信息更新的BIRT 和BIFT。網絡拓撲信息采用COST-239 歐洲測量拓撲［25］，如圖7 所示，含有11 個網絡設備，26 條網絡鏈路。

Fig.7 Test topology of BIER圖7 BIER 測試拓撲

在如圖7 所示的網絡拓撲中，每次選取更多數量的組播目的節點，將其作為組播組成員進行組播轉發。每次組播轉發會計算節點的保護性能，以此檢驗雙P 圈方案的優勢。以傳統P 圈方案作為對照，仿真結果如圖8、圖9 所示。

Fig.8 Comparison of average node protection cost圖8 平均節點保護成本比較

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

Fig.9 Comparison of probability of network packet loss圖9 網絡報文丟失概率比較

網絡報文丟失概率為網絡中每條鏈路的失效概率相同時，受故障影響的節點對數量與網絡中所有節點對之間的比值。由圖9 可知，雙P 圈方案比傳統P 圈方案的故障保護率更高，網絡報文丟失概率下降了16.6%，這是由于雙P圈的聯合保護范圍更廣。

4 結語

BIER 協議是對傳統組播協議的一次創新，本文通過對BIER 協議架構和數據平面進行分析與研究，對BIER 保護方案有了更深刻的認識，并基于此提出了配置簡單且性能改進的雙P 圈BIER 保護方案。該方案可對單鏈路故障實現有效保護，但對于多鏈路故障則不能穩定地實現保護，后續工作可對此進行改進，研發多鏈路故障的解決方案。