劉艷萍，楊喜敏*，馮偉，唐菀

(1 中南民族大學(xué) 計算機(jī)科學(xué)學(xué)院，武漢 430074；2 海能達(dá)通信股份有限公司，深圳 518000)

隨著Internet的飛速發(fā)展，特別是5G時代的到來，視頻直播、IPTV、實時監(jiān)控等網(wǎng)絡(luò)業(yè)務(wù)與應(yīng)用與日俱增[1-2].一發(fā)多收的組播顯然比一對一的單播更符合這些網(wǎng)絡(luò)業(yè)務(wù)的性能需求[3-4]，但由于資源容量的有限性和組播協(xié)議復(fù)雜[5]等諸多原因，傳統(tǒng)的組播技術(shù)已難以適應(yīng)這些業(yè)務(wù)的大規(guī)模應(yīng)用[6].軟件定義網(wǎng)絡(luò)(Software-Defined Networking, SDN)與生俱來的全局視角和可編程等特性[7-8]，可以賦予組播管理更高的效率和靈活性[9-10]，但實時維護(hù)數(shù)據(jù)平面轉(zhuǎn)發(fā)設(shè)備中的組播報文轉(zhuǎn)發(fā)規(guī)則，既會增加控制器的負(fù)擔(dān)，也會影響組播報文的傳輸性能[11].

位索引顯式復(fù)制(Bit Index Explicit Replication, BIER)[12]是一種新的協(xié)議無關(guān)組播技術(shù).中間節(jié)點完全基于組播報文攜帶的二進(jìn)制位串跨域轉(zhuǎn)發(fā)組播報文[13]，既不需要維護(hù)每條組播數(shù)據(jù)流的狀態(tài)，也不受接收者動態(tài)變化的影響，極大簡化了組播信息管理和維護(hù)的時空復(fù)雜度，能提升組播報文的轉(zhuǎn)發(fā)效率，且易于實現(xiàn)大規(guī)模組播結(jié)合 SDN的全局視角等固有優(yōu)勢，BIER還可有效應(yīng)對組播網(wǎng)絡(luò)動態(tài)變化的問題[14].

BIER的組播報文轉(zhuǎn)發(fā)規(guī)則用一個二進(jìn)制位串來表示,其中的每一位對應(yīng)一個交換機(jī)/轉(zhuǎn)發(fā)設(shè)備.要支持BIER，交換機(jī)就需要配備位索引轉(zhuǎn)發(fā)表(Bit Index Forwarding Table, BIFT)，并依據(jù)其存儲的轉(zhuǎn)發(fā)規(guī)則來轉(zhuǎn)發(fā)組播報文.因此，為網(wǎng)絡(luò)中的所有交換機(jī)構(gòu)建BIFT是BIER應(yīng)用時的關(guān)鍵之處.尤其是當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化或動態(tài)規(guī)劃網(wǎng)絡(luò)資源而需調(diào)整組播報文的傳輸路徑時，BIFT重構(gòu)效率不僅會直接影響組播報文的傳輸性能，甚至?xí)?dǎo)致網(wǎng)絡(luò)傳輸?shù)闹袛?

文中將對組播路由樹依據(jù)接收者的構(gòu)成模式進(jìn)行分類，并設(shè)計基于子樹分類和歸并的BIFT構(gòu)造器(BIFT Constructor based on Classifying and Combining, C3-BIFT)，通過一次組播路由樹的回溯遍歷，快速構(gòu)建所有交換機(jī)的BIFT，以盡量減小對接收者加入延遲和組播報文傳輸性能的影響.

1 相關(guān)工作及問題描述

BIER自2014年被提出后就備受關(guān)注. IETF于2017年發(fā)布的RFC 8279和2019年4月發(fā)布的BIER體系架構(gòu)RFC 8556中，詳細(xì)描述了服務(wù)供應(yīng)商的骨干網(wǎng)絡(luò)如何承載組播流量的方法、協(xié)議和過程.既有研究結(jié)果表明，BIER不僅能夠使SDN網(wǎng)絡(luò)組播的管理和配置更加簡單和高效[12]，組播報文的快速重路由也相當(dāng)簡捷[13].HF-BIER(Hierarchical Forwarding Bit Index Explicit Replication)模型[15]是通過分層BIER網(wǎng)絡(luò)的方法來解決鏈路中的數(shù)據(jù)冗余問題.PAPN 等提出的IPFRR(IP Fast Reroute)則是以位串替代反向路徑信號的機(jī)制，來解決由于鏈路或者交換機(jī)故障導(dǎo)致的網(wǎng)絡(luò)流量中斷問題[16].不過，這些研究較少涉及BIER位串和交換機(jī)BIFT的更新和重構(gòu)方法，是否能在網(wǎng)絡(luò)拓?fù)渥兏⒔M播組成員變化以及動態(tài)規(guī)劃網(wǎng)絡(luò)資源時依然保證組播性能尚未可知.

在一個由8個交換機(jī)(s1 ～ s8)組成的網(wǎng)絡(luò)，如圖1所示，當(dāng)有源連接于s1、接收者連接于s5的組播組W時，一是要基于組播路由樹為網(wǎng)絡(luò)中的交換機(jī)構(gòu)建BIFT；二是交換機(jī)s1要以位串“00010000”將組播報文封裝成BIER報文后才能依據(jù)其BIFT中的規(guī)則轉(zhuǎn)發(fā)到相應(yīng)的端口；三是后續(xù)交換機(jī)在轉(zhuǎn)發(fā)報文時，需要修改BIER頭中的位串以保證報文傳輸?shù)姆较?因此，當(dāng)組播組固定且傳輸路徑不變時，BIFT的構(gòu)建重點在于是否正確，而不是構(gòu)建效率.

當(dāng)有名為h的主機(jī)(假設(shè)連接于s3)要加入組播組W時，s3將h的加入請求以packet_in消息發(fā)送給控制器；組播管理器通常是一個SDN北向應(yīng)用或控制器中的模塊，既需要重構(gòu)交換機(jī)BIFT，也需要通知s1使用新的位串“00010100”來標(biāo)記組播報文.這些工作在SDN網(wǎng)絡(luò)中，都是通過控制器下發(fā)的流表/組表項來完成.也就是說，相對于傳統(tǒng)組播主機(jī)加入延遲，BIER用于SDN網(wǎng)絡(luò)組播時，加入延遲不僅包括各種報文的封裝與傳輸時延，還包括請求處理、組播路由樹構(gòu)造、BIFT重建和入口位串生成等的處理時間.除BIFT重建和入口位串生成的時間開銷外，其它時延也是SDN網(wǎng)絡(luò)組播加入延遲固有的構(gòu)成部分.因此，要保證組播報文的傳輸性能和請求者的加入延遲沒有明顯變化，就必須快速重建相關(guān)交換機(jī)的BIFT和入口交換機(jī)的BIER頭.

圖1 BIER通信過程Fig.1 BIER communication process

2 解決方案

2.1組播子樹分類及其BIFT

交換機(jī)的BIFT存儲組播報文的分發(fā)規(guī)則，初始BIER頭實際標(biāo)注的是接收者直連的交換機(jī)，再加上組播樹的生成算法已相當(dāng)成熟，通過組播樹構(gòu)建交換機(jī)的BIFT顯然是一種優(yōu)選的解決方案.組播樹通常有源樹和共享樹兩種.源樹是以組播源為樹根、以接收者為葉子的轉(zhuǎn)發(fā)樹；共享樹則是以匯集交換機(jī)為根、以接收者為葉子的轉(zhuǎn)發(fā)樹.鑒于共享樹中組播源與匯集交換機(jī)的報文傳輸并不影響B(tài)IFT的構(gòu)建過程，下面基于源樹來描述交換機(jī)BIFT的構(gòu)建方案.

定義1：基于網(wǎng)絡(luò)拓?fù)鋱DG(V,E)生成的組播源為h的源樹,是以h的直接后繼為根的子樹的集合Th={Tv|v∈V-{h},(h,v)∈E}. 其中，V是非空的節(jié)點集，E是非空的節(jié)點間的邊集.

推論1：源樹Th中的接收者集合為：R={v|v∈V-{h},不存在x∈V,(v,x)∈E}；交換機(jī)集合為：S=V-{h}-R.

(1)

BIER本身只定義了中間節(jié)點的報文轉(zhuǎn)發(fā)規(guī)則，因此，為保證報文傳輸過程的完整性，即為交換機(jī)構(gòu)造BIFT的同時也構(gòu)造交換機(jī)向接收者的報文轉(zhuǎn)發(fā)規(guī)則，所提出的解決方案基于樹根的直接后繼節(jié)點集的構(gòu)成模式，依據(jù)式(1)將樹中的節(jié)點劃分為A、B和C三類，如圖2所示.

圖2 子樹類型Fig.2 Types of subtrees

事實上，A類子樹的根都是組播報文的接收者；B類子樹僅需將組播報文轉(zhuǎn)發(fā)給它連接于它的A類子樹；C類子樹稍復(fù)雜，既需本地轉(zhuǎn)發(fā)組播報文，還需維護(hù)BIER頭中的位串，以保證報文的傳輸方向.

定義2：BIER的組播報文轉(zhuǎn)發(fā)規(guī)則是一個由位串、鄰節(jié)點和報文出端口構(gòu)成的三元組.

定義3：一個BIFT是由BIER組播報文轉(zhuǎn)發(fā)規(guī)則構(gòu)成的集合.

Bbift(v)={(2N(v),-,locale)}∪{(0,i,vi)|Ti∈Tv,f(i)=A} ，

(2)

(3)

2.2 組播子樹歸并

組播子樹歸并是將組播子樹歸并為以其根節(jié)點表示的一個單一節(jié)點，且根節(jié)點的類型不變.A類子樹無需歸并，或可認(rèn)為歸并結(jié)果與原節(jié)點相同；B類和C類子樹歸并后為一個類型不變的單一節(jié)點，子樹歸并及BIFT生成過程如圖3所示.

m:Tv=∑Ti∈Tv,f(i)=BN(i)+∑Tj∈Tv,f(j)=Cm(j)+N(j).

(4)

定義4：組播子樹歸并后的位串為其所有子樹的位串的和.計算過程見式(4).

圖3 子樹歸并及BIFT生成Fig.3 Subtree merging and BIFT generation

子樹歸并后，B類子樹僅需向其父節(jié)點注冊其自身的信息，而C類歸并后，則需向其父節(jié)點歸集其自身及其子樹的位串.

子樹歸并的過程是各節(jié)點的BIFT逐步向上歸并直至組播樹的樹根的過程.

2.3 算法描述

基于前面對解決方案的描述，C3-BIFT采用深度優(yōu)先遞歸遍歷名為T的路由樹，生成每個節(jié)點的BIER串及每個交換機(jī)的BIFT，并對子樹進(jìn)行合并，再以向上回溯的方法處理下一個子樹，直到到達(dá)樹T的根節(jié)點.下面給出C3-BIFT的偽代碼描述.

算法:BIFT生成算法 C3-BIFT輸入:組播樹T, 根節(jié)點s1輸出:BIFT表bift_table1.Ts ← SubTree(s1)2.while Depth(Ts) != 2 do3. ? si ∈ s.Child4. C3-BIFT (T,si, bift_table)5.end while6.tree_type← SubTreeType(Ts)7.if tree_type == 'A' then8. bift_table←treeInfo(s,'00000000',port) 9.else if tree_type == 'B' then 10. bift_table ← subTreeInfo(s, Ts) 11. bift_table← treeInfo(s, cString, 'local') 12. CombineSubtree(Ts, bift_table)13.else if tree_type == 'C' then 14. bift_table← subTreeInfo(s, Ts)15. bift_table← treeInfo(s, cString, 'local')16. CombineSubtree(Ts, bift_table)17.end if18.return bift_table

C3-BIFT算法從樹T的根節(jié)點s1開始，進(jìn)行深度優(yōu)先遞歸遍歷每一個節(jié)點的孩子節(jié)點，直到到達(dá)只有一個節(jié)點的子樹Ts，這個子樹為A類子樹或者B類子樹.隨后對子樹Ts進(jìn)行相關(guān)處理，如果子樹是A類子樹，則s的位串為“00000000”；如果是B類子樹或C類子樹，首先生成s的BIFT，存入map_tree中，再合并子樹Ts為子樹根節(jié)點s，s的位串為s的BIFT中所有位串邏輯或后的值；然后返回本次的bift_table，結(jié)束本次遞歸，進(jìn)入上層遞歸，繼續(xù)以上操作，直到子樹Ts的根節(jié)點為樹T的根節(jié)點，返回最終的bift_table，算法結(jié)束.

由于C3-BIFT采用深度優(yōu)先遞歸遍歷組播樹的所有節(jié)點，其時間復(fù)雜度為O(n=|T|)；空間復(fù)雜度則相關(guān)于樹的最大深度d，為O(d)，當(dāng)樹趨于平衡時，d逼近Log(n).

3 實驗與性能評估

3.1 仿真環(huán)境及性能指標(biāo)

實驗在Ubuntu 16.04系統(tǒng)上使用Mininet 2.2.1網(wǎng)絡(luò)模擬器進(jìn)行，選用OpenDayLight 0.6.4 Carbon作為SDN控制器，使用VLC 2.2.1和Wireshark 2.6.1分別完成數(shù)據(jù)包發(fā)送和分析.

仿真實驗的網(wǎng)絡(luò)拓?fù)淙鐖D4所示，網(wǎng)絡(luò)中有8個交換機(jī)、8個接收者、1個組播源，組播源h0用來發(fā)送數(shù)據(jù)，交換機(jī)s1為BIER組播入口交換機(jī).

圖4 實驗網(wǎng)絡(luò)拓?fù)銯ig.4 Experimental network topology

主要采用組播加入延遲、流表項數(shù)和BIFT構(gòu)建時間三項指標(biāo)，通過與傳統(tǒng)的SDN組播進(jìn)行對比來評估C3-BIFT算法對網(wǎng)絡(luò)性能的影響.這里的流表項數(shù)指的是每次組播網(wǎng)絡(luò)組成員發(fā)生變化，需要更新的交換機(jī)流表項數(shù)，此指標(biāo)能夠有效地反映組播延遲與流表項更新數(shù)的關(guān)系.

3.2 結(jié)果與分析

仿真實驗在下面4個場景進(jìn)行，測量采用C3-BIFT算法后網(wǎng)絡(luò)中組播接收者的加入延遲，并與基于SDN的傳統(tǒng)組播進(jìn)行對比，取10次測試平均值作為接收者初始加入延遲.

(1)初始加入：單個接收者加入初始組播組，即組播組第1個接收者加入.

(2)空組加入：每次從所有主機(jī)中隨機(jī)選擇一個接收者加入空組播組，即僅當(dāng)組播組中沒有任何其他接收者時，才允許該接收者加入組播組，但不要求組播組為初始狀態(tài).每輪測試8個接收者.

(3)連續(xù)加入：每次從所有主機(jī)中隨機(jī)選擇一個接收者加入組播組，直至所有接收者都加入組播組.與空組加入不同的是，接收者加入組播時并不要求組播組為空，且加入后不會離開組播組.

(4) 隨機(jī)加入：接收者隨機(jī)加入或離開組播組.與其它實驗不同，接收者既可以加入，也可以離開組播組，且任何接收者加入組播組時也不要求組播組必須是空的.每次測試采集50次接收者的加入延遲，最后計算每個接收者的多次加入延遲的平均值為其加入延遲.

組播加入延遲如圖5所示， BIER組播接收者的加入延遲基本小于傳統(tǒng)SDN組播中的加入延遲，傳統(tǒng)的SDN組播接收者加入延遲的波動也更加明顯.這是由于在每次接收者加入或退出組播時，支持BIER的控制器只需向發(fā)送者直連的交換機(jī)下發(fā)1條組表項，向接收者直連的交換機(jī)下發(fā)1條流表項，即可完成組播報文的傳遞.而在傳統(tǒng)的SDN組播中，控制器需要向組播路徑上的所有交換機(jī)下發(fā)流表項，下發(fā)流表項的數(shù)目完全取決于組播路徑中的交換機(jī)數(shù)量.在本實驗的4個場景中，當(dāng)交換機(jī)直連的主機(jī)已經(jīng)有了接收者的情況下，傳統(tǒng)SDN組播只需要下發(fā)/更新一條流表項就可以完成新接收者的組播處理.例如，在圖4的拓?fù)渲?，如果h3已經(jīng)在組播內(nèi)，這時h8再加入組播組的話，傳統(tǒng)的SDN組播只需要更新一條流表項就可以完成新的組播報文的傳遞.仿真實驗的網(wǎng)絡(luò)中，交換機(jī)數(shù)量有限且層數(shù)較少，在連續(xù)加入的場景中，傳統(tǒng)的SDN組播網(wǎng)絡(luò)平均只需要更新1.875條流表，但是傳統(tǒng)組播每次主機(jī)加入都要進(jìn)行尋路，而BIER組播只需要進(jìn)行簡單的位串計算就可以，尋路的過程遠(yuǎn)比BIER的位串計算時間要高，從而傳統(tǒng)組播接收者的加入延遲基本比BIER組播網(wǎng)絡(luò)接收者的加入延遲高.還可以看到，由于接收者加入BIER組播時，控制器僅需控制入口和出口交換機(jī)，所以，無論接收者是密集還是稀疏，接收者的加入延遲都不會像傳統(tǒng)的SDN組播網(wǎng)絡(luò)那樣存在較大的波動，而是會處于一個相對穩(wěn)定的態(tài)勢.

圖5 組播加入延遲Fig.5 Multicast join delays in different scenarios

C3-BIER算法為所有交換機(jī)構(gòu)建BIFT時間與樹的深度、寬度與節(jié)點數(shù)的關(guān)系如圖6所示，從其中可以看出BIFT構(gòu)建時間與樹的深度與節(jié)點數(shù)基本成正相關(guān)；當(dāng)樹的寬度小于30時，BIFT的構(gòu)建時間隨著寬度的增加緩慢上升，而當(dāng)樹的寬度大于30時，BIFT構(gòu)建時間隨著寬度的增加上升比較明顯.

圖6 交換機(jī)BIFT構(gòu)建時間與樹的深度、寬度、節(jié)點數(shù)的關(guān)系Fig.6 The relationship between the BIFT construction time and thetree depth and width, and the number of nodes on the tree

總體而言，多播加入延遲的高低主要與下發(fā)流表項或組表項的數(shù)量有關(guān).傳統(tǒng)的SDN組播網(wǎng)絡(luò)接收者加入延遲與交換機(jī)的數(shù)量有著密切的關(guān)系，而在采用BIER的組播中，接收者加入組播時涉及的交換機(jī)最多只有2個，使得加入延遲更加穩(wěn)定.此外，實驗也驗證了所設(shè)計的BIFT構(gòu)建算法的有效性，且接收者加入組播組時的請求處理時間沒有明顯增加.

4 總結(jié)與展望

BIER采用位串匹配的方式進(jìn)行組播報文的轉(zhuǎn)發(fā)，能夠有效的適應(yīng)動態(tài)的組播網(wǎng)絡(luò).所提出的解決方案能夠在組播網(wǎng)絡(luò)發(fā)生變化時，通過快速重構(gòu)各個SDN交換機(jī)的BIFT，強(qiáng)化BIER組播對網(wǎng)絡(luò)動態(tài)變化的適應(yīng)能力.設(shè)計的基于子樹合并和分類的BIFT構(gòu)建算法C3-BIFT中，采用所提出的依據(jù)組播報文接收者的組播路由子樹分類模式，通過一次組播路由樹的回溯遍歷，為全網(wǎng)交換機(jī)構(gòu)建BIFT.仿真實驗表明，接收者加入BIER組播時涉及的交換機(jī)將不超過2個，使接收者的加入延遲比較穩(wěn)定，不會呈現(xiàn)出類似于傳統(tǒng)的SDN網(wǎng)絡(luò)的波動.所提出的C3-BIFT算法的時間開銷幾乎不增加流表的更新時間，也不會導(dǎo)致接收者的加入延遲發(fā)生明顯的變化.下一步工作將繼續(xù)優(yōu)化C3-BIER算法，以能夠在組播網(wǎng)絡(luò)拓?fù)浒l(fā)生變化的情況下，實現(xiàn)全網(wǎng)交換機(jī)的BIFT快速重構(gòu).