彭 耘

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

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

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

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

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個問題：1）計算網(wǎng)絡(luò)拓撲中轉(zhuǎn)發(fā)路徑/轉(zhuǎn)發(fā)樹；2）計算轉(zhuǎn)發(fā)路徑/轉(zhuǎn)發(fā)樹的BF值；3）有必要的話還需要進行相關(guān)資源的分配．

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

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

每個節(jié)點都使用函數(shù)Z（L，I），利用節(jié)點本地信息L和部分包頭信息I來計算鏈路標識．轉(zhuǎn)發(fā)路徑樹的組成由組成該樹的鏈路標識進行二進制OR操作獲得．分組源節(jié)點在發(fā)送的分組的頭部攜帶該轉(zhuǎn)發(fā)路徑樹標識．轉(zhuǎn)發(fā)節(jié)點在收到帶轉(zhuǎn)發(fā)路徑樹標識的分組后匹配各輸出鏈接標識，如果匹配，則將該分組沿本鏈路轉(zhuǎn)發(fā)．如果轉(zhuǎn)發(fā)路徑樹標識中攜帶有多個輸出口鏈路標識，則實現(xiàn)了分組的多播轉(zhuǎn)發(fā)．文獻[2]通過實驗分析得到，35～40條鏈路可以編碼到256位路徑標識，可以達到90%的轉(zhuǎn)發(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)信息．單播路徑的建立比較簡單，但是要實現(xiàn)組播樹就比較困難．多協(xié)議無狀態(tài)交換的基本思想是在 MPLS架構(gòu)的基礎(chǔ)上，將 MPLS標簽用包內(nèi)Bloom過濾標識替代．這樣數(shù)據(jù)轉(zhuǎn)發(fā)平面就是無狀態(tài)的，而且天然支持多播，可以避免MPLS中組播轉(zhuǎn)發(fā)的復(fù)雜性．

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

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

圖2 Bloom過濾算法示意圖

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

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

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

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

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

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

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

1.4.2 Path請求

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

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

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

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

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

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

2.1 控制層面

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

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

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

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

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

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

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

3 結(jié) 論

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

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

[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]．計算機科學(xué), 2004，30（4）：180-183．

[5] 池靜，倪健，王華，等．Bloom Filter和Weighted Bloom Filter的比較與研究[J]．河北師范大學(xué)學(xué)報：自然科學(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．