基于Bloom過濾的多協(xié)議無狀態(tài)交換架構(gòu)研究*

彭 耘

（武漢鐵路職業(yè)技術(shù)學(xué)院，湖北 武漢 430205）

傳統(tǒng)的IP網(wǎng)絡(luò)在傳送分組時(shí)，每個(gè)路由器單獨(dú)執(zhí)行路由算法，以決定每一個(gè)分組由此路由器到下一個(gè)路由器的過程．為了避免每個(gè)分組在每個(gè)路由器轉(zhuǎn)發(fā)的過程中，皆需執(zhí)行一次IP路由查找的動(dòng)作，互聯(lián)網(wǎng)工程工作組（Internet Engineering Task Force，IETF）制定了MPLS標(biāo)準(zhǔn)，形成了MPLS分組轉(zhuǎn)發(fā)框架．

如圖1所示，在MPLS網(wǎng)絡(luò)中，每個(gè)分組只須在邊緣路由器（Provider Edge，PE）被分類加上適當(dāng)?shù)臉?biāo)簽（Label），并以標(biāo)簽交換的方式沿著標(biāo)簽交換路徑（Label Switching Path，LSP）快速傳送到目的地[1]．標(biāo)簽交換路徑的建立可以使用LDP或RSVP-TE信令協(xié)議控制建立[2]．由于MPLS具有多協(xié)議和靈活的特性，在不同的網(wǎng)絡(luò)應(yīng)用中得到廣泛應(yīng)用，包括不同VPN業(yè)務(wù)解決方案．

MPLS標(biāo)簽的應(yīng)用加快了分組的轉(zhuǎn)發(fā)速度，只是給每個(gè)轉(zhuǎn)發(fā)路由分配標(biāo)簽的話將導(dǎo)致標(biāo)簽空間爆炸的問題[3]．另外，在組播應(yīng)用中，組播樹的數(shù)量要遠(yuǎn)遠(yuǎn)高于網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量，這進(jìn)一步突出了MPLS標(biāo)簽空間問題．

Bloom過濾算法由巴頓布魯姆于 1970年提出，它是一種有效的節(jié)省空間的查找算法[4,5]．本文將MPLS分組轉(zhuǎn)發(fā)和Bloom過濾技術(shù)相結(jié)合，提出了一種多協(xié)議無狀態(tài)交換分組轉(zhuǎn)發(fā)架構(gòu)．

圖1 MPLS轉(zhuǎn)發(fā)框架示意圖

1 多協(xié)議無狀態(tài)交換架構(gòu)

在多協(xié)議無狀態(tài)分組轉(zhuǎn)發(fā)架構(gòu)下的信令處理過程中，需要處理3個(gè)問題：1）計(jì)算網(wǎng)絡(luò)拓?fù)渲修D(zhuǎn)發(fā)路徑/轉(zhuǎn)發(fā)樹；2）計(jì)算轉(zhuǎn)發(fā)路徑/轉(zhuǎn)發(fā)樹的BF值；3）有必要的話還需要進(jìn)行相關(guān)資源的分配．

1.1 基于Bloom過濾的轉(zhuǎn)發(fā)路徑計(jì)算

在組播分組轉(zhuǎn)發(fā)中，源路由和組播樹可以采用Bloom過濾算法編碼到分組頭部，并使用鏈路標(biāo)識(shí)代替節(jié)點(diǎn)標(biāo)識(shí)[6]．一旦轉(zhuǎn)發(fā)樹和路徑確定，轉(zhuǎn)發(fā)表也就確定了．其中Bloom過濾算法可以簡(jiǎn)化鏈路集合的表達(dá)．單向轉(zhuǎn)發(fā)鏈路用一個(gè)固定長度的稀疏位串表示．在m位長的字串中有k位置為 1．如圖2所示，A→B的單向鏈路用位串“010001001”表示，B→C鏈路用“100001100”表示．經(jīng)過Bloom過濾算法可獲得A→B→C整個(gè)路徑的位串標(biāo)識(shí)為“110001101”．

每個(gè)節(jié)點(diǎn)都使用函數(shù)Z（L，I），利用節(jié)點(diǎn)本地信息L和部分包頭信息I來計(jì)算鏈路標(biāo)識(shí)．轉(zhuǎn)發(fā)路徑樹的組成由組成該樹的鏈路標(biāo)識(shí)進(jìn)行二進(jìn)制OR操作獲得．分組源節(jié)點(diǎn)在發(fā)送的分組的頭部攜帶該轉(zhuǎn)發(fā)路徑樹標(biāo)識(shí)．轉(zhuǎn)發(fā)節(jié)點(diǎn)在收到帶轉(zhuǎn)發(fā)路徑樹標(biāo)識(shí)的分組后匹配各輸出鏈接標(biāo)識(shí)，如果匹配，則將該分組沿本鏈路轉(zhuǎn)發(fā)．如果轉(zhuǎn)發(fā)路徑樹標(biāo)識(shí)中攜帶有多個(gè)輸出口鏈路標(biāo)識(shí)，則實(shí)現(xiàn)了分組的多播轉(zhuǎn)發(fā)．文獻(xiàn)[2]通過實(shí)驗(yàn)分析得到，35～40條鏈路可以編碼到256位路徑標(biāo)識(shí)，可以達(dá)到90%的轉(zhuǎn)發(fā)效率（有效負(fù)荷的轉(zhuǎn)發(fā)）．

1.2 基于Bloom過濾的多協(xié)議無狀態(tài)轉(zhuǎn)發(fā)框架

轉(zhuǎn)發(fā)路徑/轉(zhuǎn)發(fā)樹的處理可以使用現(xiàn)有的MPLS技術(shù)．MPLS分組轉(zhuǎn)發(fā)需要網(wǎng)絡(luò)狀態(tài)信息．單播路徑的建立比較簡(jiǎn)單，但是要實(shí)現(xiàn)組播樹就比較困難．多協(xié)議無狀態(tài)交換的基本思想是在 MPLS架構(gòu)的基礎(chǔ)上，將 MPLS標(biāo)簽用包內(nèi)Bloom過濾標(biāo)識(shí)替代．這樣數(shù)據(jù)轉(zhuǎn)發(fā)平面就是無狀態(tài)的，而且天然支持多播，可以避免MPLS中組播轉(zhuǎn)發(fā)的復(fù)雜性．

在MPLS中，連接的建立使用RSVP信令消息可以建立顯示的標(biāo)簽轉(zhuǎn)發(fā)路徑．同時(shí)這些信令消息還用來建立轉(zhuǎn)發(fā)表和預(yù)留資源．當(dāng)使用Bloom過濾標(biāo)識(shí)時(shí)，轉(zhuǎn)發(fā)表可以保持不變．資源預(yù)留需要做些細(xì)小的調(diào)整，主要是如何將轉(zhuǎn)發(fā)層傳遞到控制層面處理．框架示意圖如圖3所示．

1.3 資源預(yù)留問題處理

圖2 Bloom過濾算法示意圖

圖3 基于Bloom過濾算法的多協(xié)議無狀態(tài)轉(zhuǎn)發(fā)框架示意圖

資源預(yù)留是流量工程的一個(gè)基本功能塊．可以通過擴(kuò)展RSVP-TE實(shí)現(xiàn)基于Bloom過濾的無狀態(tài)轉(zhuǎn)發(fā)下的資源預(yù)留．

其中有2種處理方法：1）資源預(yù)留信令消息通過IP路由；2）資源預(yù)留信令消息通過Bloom過濾路由．如圖4所示的一個(gè)P節(jié)點(diǎn)上的RSVP操作過程中，當(dāng)RSVP Path消息進(jìn)入P節(jié)點(diǎn)后，它上傳到控制層面處理．其請(qǐng)求的資源是臨時(shí)分配的，分組會(huì)繼續(xù)轉(zhuǎn)發(fā)．在出口PE，會(huì)發(fā)送RSVP Resv分組以響應(yīng)臨時(shí)的資源分配．如果請(qǐng)求的資源在某些路由器是無法獲得滿足，Path消息不會(huì)繼續(xù)轉(zhuǎn)發(fā)，而是回應(yīng)一個(gè) PathErr失敗通告消息．在基于 IP的信令路由方案中，分組是按照ERO對(duì)象描述路徑逐跳轉(zhuǎn)發(fā)的．而在基于Bloom過濾的方案中，使用兩種類型的鏈路節(jié)點(diǎn)標(biāo)識(shí)（也稱為控制LID）：阻塞和非阻塞LID．當(dāng)分組中包含阻塞LID，分組不再轉(zhuǎn)發(fā)，直到得到控制層面的允許．而當(dāng)分組中包含的是非阻塞LID時(shí)，分組同時(shí)向路徑標(biāo)識(shí)匹配的出接口發(fā)送．在 RSVP資源預(yù)留消息中，Path消息阻塞LID由LID與Bloom過濾標(biāo)識(shí)進(jìn)行OR操作獲得，而反方向的Resv和PathErr則在分組頭加入非阻塞的LID．無狀態(tài)多協(xié)議分組轉(zhuǎn)發(fā)資源預(yù)留實(shí)現(xiàn)示意圖如圖4所示．

1.4 多協(xié)議無狀態(tài)轉(zhuǎn)發(fā)路徑建立

在多協(xié)議無狀態(tài)交換架構(gòu)下，控制轉(zhuǎn)發(fā)樹的建立在入口PE實(shí)現(xiàn)．與基于分支節(jié)點(diǎn)的解決方案比較，這種方式對(duì)于點(diǎn)到多點(diǎn)樹上增加或刪除接收PE的操作更為靈活．這種方式的實(shí)現(xiàn)需要源PE能夠存儲(chǔ)每個(gè)到出口PE的每個(gè)分支的單播Bloom過濾標(biāo)識(shí)．組播Bloom過濾標(biāo)識(shí)由這些單播過濾標(biāo)識(shí)進(jìn)行簡(jiǎn)單的OR操作獲得．由于鏈路中斷或其他的原因，可能分組需要重路由．為了處理這種情況，本文使用了文獻(xiàn)[8]描述的方法．

1.4.1 Bloom過濾標(biāo)識(shí)發(fā)布協(xié)議

為了將Bloom過濾標(biāo)識(shí)在全網(wǎng)傳播，可以象LDP的有序工作模式那樣，如果PE接收到的發(fā)布信息是從其最短路徑路由器上來的，PE接收并轉(zhuǎn)發(fā)Bloom過濾標(biāo)識(shí)，否則丟棄．每個(gè)Bloom過濾標(biāo)識(shí)發(fā)布消息中包含一個(gè)過濾標(biāo)識(shí)字段，其他的PE收到發(fā)布消息后，收集并儲(chǔ)存該字段值．利用這些單播過濾標(biāo)識(shí)值可以計(jì)算出任意點(diǎn)到多點(diǎn)的最短路徑樹．

1.4.2 Path請(qǐng)求

入口PE在RSVP的Path分組中初始化Path請(qǐng)求．消息中包含ERO對(duì)象攜帶的顯示路徑信息和一個(gè)Bloom過濾標(biāo)識(shí)．Path請(qǐng)求消息到達(dá)出口PE后，PE會(huì)利用收集到的過濾標(biāo)識(shí)，回應(yīng)一個(gè)Resv消息．對(duì)于點(diǎn)到多點(diǎn)樹，每個(gè)分支都會(huì)發(fā)送一個(gè)請(qǐng)求．因此在出口 PE上，需要將這些分支過濾標(biāo)識(shí)進(jìn)行 OR操作，再插入 Resv消息中返回．在沒有資源預(yù)留應(yīng)用中，控制層面也不需要處理Resv消息．

圖4 無狀態(tài)多協(xié)議分組轉(zhuǎn)發(fā)資源預(yù)留實(shí)現(xiàn)示意圖

2 多協(xié)議無狀態(tài)交換在組播VPN中應(yīng)用

圖5 L3VPN業(yè)務(wù)場(chǎng)景示意圖

如圖5所示，用戶站點(diǎn)的符合是IP分組，Bloom過濾標(biāo)識(shí)在業(yè)務(wù)提供商的網(wǎng)絡(luò)的分組轉(zhuǎn)發(fā)中應(yīng)用．

與當(dāng)前的MPLS VPN設(shè)計(jì)類似[4,5]，多協(xié)議無狀態(tài)交換架構(gòu)中，L3VPN業(yè)務(wù)的實(shí)現(xiàn)也使用層次標(biāo)簽．其中外層標(biāo)簽使用的是Bloom過濾標(biāo)識(shí)，內(nèi)層標(biāo)簽依然使用MPLS標(biāo)簽．

2.1 控制層面

在組播VPN業(yè)務(wù)應(yīng)用中，控制層面主要實(shí)現(xiàn)兩個(gè)功能：

1）在業(yè)務(wù)提供商網(wǎng)絡(luò)內(nèi)創(chuàng)建轉(zhuǎn)發(fā)路徑/轉(zhuǎn)發(fā)樹．這個(gè)功能在本文的第二部分已經(jīng)介紹．

2）通過業(yè)務(wù)提供商網(wǎng)絡(luò)傳播用戶站點(diǎn)網(wǎng)絡(luò)的路由信息．由于在出口PE上復(fù)用了MPLS標(biāo)簽，當(dāng)前部署的VPN的控制平面可以繼續(xù)使用．只傳播單播路由的話，BGP不需要做任何擴(kuò)展．

在多播環(huán)境下，需要使用一個(gè)成員分發(fā)協(xié)議用來顯示追蹤組播分組接收者．對(duì)于一個(gè)組播域，源PE需要知道接收PE有哪些，進(jìn)而使用匹配的Bloom過濾標(biāo)識(shí)以進(jìn)行網(wǎng)絡(luò)內(nèi)的分組轉(zhuǎn)發(fā)．

2.2 轉(zhuǎn)發(fā)平面

當(dāng)PE收到一個(gè)單播IP分組需要發(fā)送到遠(yuǎn)端站點(diǎn)時(shí)，首先查找到關(guān)聯(lián)的VPN路由轉(zhuǎn)發(fā)表，決定出口 PE和內(nèi)層標(biāo)簽．將分組綁定內(nèi)層標(biāo)簽以及到達(dá)指定出口PE的Bloom過濾標(biāo)識(shí)．隨后P路由器基于Bloom過濾標(biāo)識(shí)進(jìn)行轉(zhuǎn)發(fā)．當(dāng)分組到達(dá)目的出口PE時(shí)，剝離掉Bloom過濾標(biāo)識(shí)，并檢查內(nèi)層MPLS標(biāo)簽．基于內(nèi)層標(biāo)簽，將原始IP分組發(fā)送到正確的目的網(wǎng)絡(luò)．

多播分組的轉(zhuǎn)發(fā)比較類似．當(dāng)接收到一個(gè)IP多播分組需要發(fā)送到遠(yuǎn)端網(wǎng)絡(luò)時(shí)，PE在控制平面的控制下打上內(nèi)層標(biāo)簽，以及到達(dá)所有具有接收站點(diǎn)的PE的Bloom過濾標(biāo)識(shí)．

3 結(jié) 論

本文介紹了多協(xié)議無狀態(tài)交換的分組轉(zhuǎn)發(fā)架構(gòu)．在該架構(gòu)下，基于Bloom過濾的分組轉(zhuǎn)發(fā)控制可以通過少量擴(kuò)展 MPLS控制平面協(xié)議實(shí)現(xiàn)．在多協(xié)議無狀態(tài)轉(zhuǎn)發(fā)架構(gòu)下，路由的決策推向了CE，從而減輕了PE的處理負(fù)擔(dān)．PE路由器的更新間隔也就不需要那么迅速．從而保護(hù)運(yùn)營商網(wǎng)絡(luò)設(shè)備的投資．

當(dāng)把這種轉(zhuǎn)發(fā)架構(gòu)應(yīng)用在組播 VPN業(yè)務(wù)應(yīng)用中時(shí)，在轉(zhuǎn)發(fā)平面使用Bloom過濾的優(yōu)勢(shì)是P路由器可以是無狀態(tài)的．P路由器的分組轉(zhuǎn)發(fā)不依賴PE路由器數(shù)量，也不依賴組播VPN的數(shù)量，以及它加入的組播樹數(shù)．這種無狀態(tài)的獲取并沒有影響現(xiàn)在單播分組的轉(zhuǎn)發(fā)，對(duì)組播分組而言，效率的提升所附帶的帶寬低效也是可接受的．這表明，在組播VPN應(yīng)用中，可以在不犧牲帶寬的條件下有效提高組播業(yè)務(wù)流的轉(zhuǎn)發(fā)效率，從而使部署的運(yùn)營網(wǎng)絡(luò)得到較好的投資回報(bào)．基于 Bloom過濾的多協(xié)議無狀態(tài)轉(zhuǎn)發(fā)是 MPLS的一個(gè)有競(jìng)爭(zhēng)力的替代解決方案．

[1] Karpilovsky E, Breslau L, Gerber A. Multicastredux: a first look at enterprise multicast traffic[C]// Proceedings of the 1st ACM workshop on Research on enterprise networking. ACM, 2009：55-64．

[2] Cormen T H, Leiserson C E. Introduction to Algorithms[M]．2nded. Cambridge. M IT Press, 2001：221-252．

[3] Martinez-Yelmo I, Larrabeiti D, Soto I, et al. Multicast traffic aggregation in MPLS-based VPN networks[J]．IEEE Communications Magazine, 2007，45（10）：78-82．

[4] 肖明忠，代亞非．Bloom Filter及其應(yīng)用綜述[J]．計(jì)算機(jī)科學(xué), 2004，30（4）：180-183．

[5] 池靜，倪健，王華，等．Bloom Filter和Weighted Bloom Filter的比較與研究[J]．河北師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，30（4）：398-402．

[6] Bloom B H. Space/time trade-offs in hash coding with allowable errors[C]．ACM, 1970：422-426．

[7] Esteve C, Jokela P, Nikander P,et al. Selfrouting Denial-of-Service Resistant Capabilities using In-packet Bloom Filters [C]// Proceedings of European Conference on Computer Network Defence, 2009：657-660．

[8] Zahemszky A and Arianfar S. Fast Reroute For Stateless Multicast[C]//The Workshop on Reliable Networks Design and Modeling RNDM 2009, 2009：382-387．