基于Bloom過濾的多協議無狀態交換架構研究*

彭 耘

（武漢鐵路職業技術學院，湖北 武漢 430205）

傳統的IP網絡在傳送分組時，每個路由器單獨執行路由算法，以決定每一個分組由此路由器到下一個路由器的過程．為了避免每個分組在每個路由器轉發的過程中，皆需執行一次IP路由查找的動作，互聯網工程工作組（Internet Engineering Task Force，IETF）制定了MPLS標準，形成了MPLS分組轉發框架．

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

MPLS標簽的應用加快了分組的轉發速度，只是給每個轉發路由分配標簽的話將導致標簽空間爆炸的問題[3]．另外，在組播應用中，組播樹的數量要遠遠高于網絡節點的數量，這進一步突出了MPLS標簽空間問題．

Bloom過濾算法由巴頓布魯姆于 1970年提出，它是一種有效的節省空間的查找算法[4,5]．本文將MPLS分組轉發和Bloom過濾技術相結合，提出了一種多協議無狀態交換分組轉發架構．

圖1 MPLS轉發框架示意圖

1 多協議無狀態交換架構

在多協議無狀態分組轉發架構下的信令處理過程中，需要處理3個問題：1）計算網絡拓撲中轉發路徑/轉發樹；2）計算轉發路徑/轉發樹的BF值；3）有必要的話還需要進行相關資源的分配．

1.1 基于Bloom過濾的轉發路徑計算

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

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

1.2 基于Bloom過濾的多協議無狀態轉發框架

轉發路徑/轉發樹的處理可以使用現有的MPLS技術．MPLS分組轉發需要網絡狀態信息．單播路徑的建立比較簡單，但是要實現組播樹就比較困難．多協議無狀態交換的基本思想是在 MPLS架構的基礎上，將 MPLS標簽用包內Bloom過濾標識替代．這樣數據轉發平面就是無狀態的，而且天然支持多播，可以避免MPLS中組播轉發的復雜性．

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

1.3 資源預留問題處理

圖2 Bloom過濾算法示意圖

圖3 基于Bloom過濾算法的多協議無狀態轉發框架示意圖

資源預留是流量工程的一個基本功能塊．可以通過擴展RSVP-TE實現基于Bloom過濾的無狀態轉發下的資源預留．

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

1.4 多協議無狀態轉發路徑建立

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

1.4.1 Bloom過濾標識發布協議

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

1.4.2 Path請求

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

圖4 無狀態多協議分組轉發資源預留實現示意圖

2 多協議無狀態交換在組播VPN中應用

圖5 L3VPN業務場景示意圖

如圖5所示，用戶站點的符合是IP分組，Bloom過濾標識在業務提供商的網絡的分組轉發中應用．

與當前的MPLS VPN設計類似[4,5]，多協議無狀態交換架構中，L3VPN業務的實現也使用層次標簽．其中外層標簽使用的是Bloom過濾標識，內層標簽依然使用MPLS標簽．

2.1 控制層面

在組播VPN業務應用中，控制層面主要實現兩個功能：

1）在業務提供商網絡內創建轉發路徑/轉發樹．這個功能在本文的第二部分已經介紹．

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

在多播環境下，需要使用一個成員分發協議用來顯示追蹤組播分組接收者．對于一個組播域，源PE需要知道接收PE有哪些，進而使用匹配的Bloom過濾標識以進行網絡內的分組轉發．

2.2 轉發平面

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

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

3 結 論

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

當把這種轉發架構應用在組播 VPN業務應用中時，在轉發平面使用Bloom過濾的優勢是P路由器可以是無狀態的．P路由器的分組轉發不依賴PE路由器數量，也不依賴組播VPN的數量，以及它加入的組播樹數．這種無狀態的獲取并沒有影響現在單播分組的轉發，對組播分組而言，效率的提升所附帶的帶寬低效也是可接受的．這表明，在組播VPN應用中，可以在不犧牲帶寬的條件下有效提高組播業務流的轉發效率，從而使部署的運營網絡得到較好的投資回報．基于 Bloom過濾的多協議無狀態轉發是 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及其應用綜述[J]．計算機科學, 2004，30（4）：180-183．

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