基于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．