高性能路由器FIB压缩方法*

张立平，廖梦虎

高性能路由器FIB压缩方法*

张立平，廖梦虎

（武汉铁路职业技术学院，湖北 武汉 430205）

高性能IP路由器使用复杂的转发表查找算法优化查找时间、存储空间和更新时间．在对ORTC压缩算法及信息熵理论研究的基础上，提出了一种基于多位特里算法，通过消除信息冗余的方式实现对FIB的压缩方法．该方法具有不改变路由语义和外部路由器行为特征，在典型的路由器应用环境下，可以节省约50%的存储空间，路由查找效率可提高25%．

IP转发表; 数据压缩; 前缀树

FIB（Forwarding Information Base）表的快速增长成为存储空间和管理的负担．如果采用已在Linux内核中实现的fib_trie数据结构存储这些路由前缀，需要占用大量的存储空间，并且严重影响高速率的分组转发性能[1]．文献[2]研究以FIB聚合的方式压缩FIB的大小，进而延长已部署网络设备的生命周期，缓解互联网路由规模扩张的问题．FIB聚合是一种将原始FIB表述转换为一个占用空间小但又能提供快速查找的替代表述的技术．从最初的24字节/每前缀，可以采用哈希、路径或层压缩多位Tries、位图等压缩方法将FIB的存储空间占用降到2～4.5字节/每前缀．同时查找性能也会提升[3]．理论上，上述这些方法还未达到FIB表的压缩极限．基于FIB信息熵压缩度量，本文以FIB聚合为前提，提出一个熵压缩的FIB数据结构，以期实现FIB压缩的理论极限．

1 FIB压缩实现原理

1.1FIB聚合原理

FIB聚合就是在转发等价的条件下将多个相同下一跳的路由条目减少为一个．一个明显的例子是2个地址空间相邻的路由前缀条目，如下一跳相同的2.0.0.0/8和3.0.0.0/8可以聚合为一个路由前缀条目2.0.0.0/7．图1说明FIB表的聚合过程，其中2个下一跳为A的路由前缀条目可以聚合为一个/14条目．

这种FIB压缩算法是Draves等[4]在1998年设计的，称为优化路由表构造器算法（ORTC：Optimal Routing Table Constructor）．不过该算法中针对源表的每次改变都需要重新计算一次聚合，算法的时间耗费与前缀树种的节点线性相关，通常达到秒级．因此在高性能的路由器中无法实用．

本文在ORTC的基础上，结合信息理论，通过验证一个聚合调整后的FIB前缀树的存储空间是否达到了它的信息理论边界作为FIB压缩抉择的依据，选择最优的解集的方式实现理论最优化的FIB压缩算法，简称为XB算法．

图1 FIB聚合原理示意图

1.2FIB压缩实现框架

图2 FIB压缩实现框架示意图

在Internet环境下，一个实用的FIB压缩算法应该是对现有的协议、关联的数据结构和FIB查找算法的影响尽量的小，这样才能在现网中部署实施．本文提出的FIB压缩算法可以在不改变FIB查找算法、路由协议及其关联的数据结构的基础上，在现有的路由解析过程中作为一个模块构件插入．如图2所示，在常规的路由器操作中，路由解析函数从BGP、IGP获得路由条目，形成前前缀和下一跳的条目列表（FIB表）．同时，路由器在收到分组数据后，需要进行FIB查找操作，在FIB表中寻找前缀最佳匹配的条目，指导分组数据的转发．FIB压缩算法插入到这两块功能之间，将FIB源表压缩为便于转发语义等价的新的FIB表．这个新表不影响原有的FIB查询，指导分组转发等操作．

2 FIB压缩算法描述

2.1 压缩FIB构造

本文提出的FIB压缩结构，是基于Jacobson[5]提出的简洁的分级索引的二叉树，通过巴罗斯—惠勒转换，得到可以进一步简洁描述的叶压入树．压缩算法的前提是一个常规的叶标识特里树．即在本压缩算法执行前，已经进过叶压入处理．

本算法思想是将T结构编码归并到2个位串中Slast和SI，将叶标识编码为Sa串．通过无损的串压缩来达到压缩空间的边界．该转换算法可以用一个三元组表示：XB（T）=（Slast，SI，Sa）．其中：

Slast：一个长度为t的位串，T中第i个节点是层级中最后一个孩子该位置1，否则置0；

SI：如果第i个节点是内节点则该位为0，否则置1；

Sa：长度为n的串，用来编码叶标识．

为了实现该转换，需要使用树的宽度优先遍历来实现．算法过程描述如下：

i←0; j←0

BFS-TRAVERSE(节点v,i,j)

If v 是父节点的最后一个孩子 then

END BFS-TRAVERSE

假定根是last：Slast[0] = 1，对于一个有t个节点的叶标识特里树T，XB（T）转换可以在O(t)时间内完成，如图3所示．

图3 叶节点压入特里树的压缩转换示意图

2.2Memory尺寸边界

首先，XB算法是一个简洁FIB表达方式，因此它支持FIB查找的算法时间复杂度为O(W)，且编码为信息理论低界限．

定理1：假设一个有n个叶子的叶标识特里树T，通过XB(T)压缩，可以用4n+nlgS位来储存，且XB(T)的查找可以在O(W)时间内完成．

证明：使用RRR简洁位串索引[6]，一个T树可以最多用2t≈4n位来编码形成Slast和SI位串，且可以在O(1)时间内完成其中的选择和排序操作．另外，最复杂的Sa也可以用δnlg位编码，且编码操作可以在O(1)时间内完成．因此，每次迭代查找都可以在一个常量时间内完成．

定理2：假定T为一个有n个叶子的适度的叶标识特里树，其大小为O(polylogn)．H0为叶标识分布的香农熵．那么XB(T)可以用4n+nH0+o(n)位编码存储，其查找时间花费在O(W)时间内．

证明：Slast和SI可以如前所述的方法进行编码，而Sa在字符空间为O(polylogn)的条件下，可以使用广义小波分析树编码，存储在4n+nH0+o(n)位的位串中，且访问时间是O(1)[7]．

上述的零阶熵边界可以很容易地推进到高阶熵．这是因为数据集中的成员之间相互依赖，他们之间的关联关系越密切，就越容易从他们的邻居推测出来，压缩的效率就越高．高阶串压缩可以使用巴罗斯-惠勒转换来计算数据集成员间的关联关系，

3 算法评估

为了评估本文提出的算法的有效性，在Linux环境下，将FIB压缩算法作为一个独立的模块插入到RIB和FIB之间，其运行在用户空间，而FIB查找等嵌入到Linux内核．代码在一个单核2.5GHz的Intel Core i5处理器上，64K字节L1数据缓存、256K字节的L2缓存和3M字节的L3缓存．

FIB数据集的产生来源于实际IP路由器和随机生成器．实际的IP路由器选择了学校的接入路由器AR，采集的前缀数据有400K．随机生成了两组FIB数据，一组为600K的数据量，一组为1百万数据量．随机FIB数据集依照泊松分布（H0 = 1.06，δ= 5）进行前缀分离和下一跳设置的方式生成的．用这三组数据验证本文压缩算法的有效性．表1描述了采用XB算法和fib-tries算法可以实现的FIB数据集的存储空间的需求对比列表，其中N为前缀数量；s下一跳数量；H0为下一跳分布的香农熵；I为信息理论限制；E为熵．后两列为针对三组数据集经过XB压缩算法和Fib-tries算法处理后所需存储空间．从表1可以看出，XB算法可以实现2-4bit/每前缀的压缩效果，是当前FIB软件压缩最常用的fib-tries算法的2倍左右的压缩效率，并接近信息理论边界值．

表1 压缩效率对比列表

另外，还将本算法的查找执行效率与linux内核实现的fib_tries算法进行了对比．本文实现算法的FIB查找次数约为3万次/s左右，远小于fib_tries的300万次/s．利用本文FIB算法的路由器转发吞吐量是fib_tries算法的2～3倍．

[1] Bolla R and Bruschi R. RFC2544 performance evaluation and internal measurements for a Linux based open router[J/OL]. http://ieeexplore.ieee.org/xpl/mostRecent Issuejsp?punumber=11206[2006-06-07/09].

[2] Zhao Xiaoliang, Dante J Pacella, and Jason Schiller. Routing scalability: an operator’s view[J]. IEEE J Sel A Commun, 2010，28（8）：1262-1270．

[3] Nilsson S and Karlsson G. IP-address lookup using LC-tries[J]. IEEE JSAC, 1999，17（6）：1083-1092．

[4] Draves R P, King C, Venkatachary S, et al. Constructing Optimal IP Routing Tables[C]// Proceedings of IEEE Infocom, 1999：88-97．

[5] Jacobson G. Space-efficient static trees and graphs[J]. IEEE FOCS, 1989，12（5）：549-554．

[6] Raman R, Raman V, Rao S S. Succinct indexabledictionaries with applications to encoding k-ary trees andmultisets[A]//ACM-SIAM SODA, 2002：233-242．

[7] Ferragina P, Manzini G, M¨akinen V, et al. Compressed representations of sequences and full-text Indexes[J]. ACM Trans Algorithms, 2007，3（2）：243-249．

FIB Compression Techniques of High Performance Router

ZHANG Liping, LIAO Menghu

（Wuhan Railway Vocational College of Technology, Wuhan, Hubei 430205,China）

IP routers use sophisticated forwarding table (FIB) lookup algorithms that reduce lookup time, storage, and update time. This paper presents a practical, optimal FIB aggregation scheme that reduces forwarding table size without modifying routing semantics or the external behavior of routers, and FIB lookup algorithms and related hardware and software. On typical IP routers, this method will reduce FIB storage by at least 50%, and reduce average lookup time by 25% for a uniform traffic matrix.

IP forwarding table; data compression; prefix tree

T319

A

1672-0318（2014）03-0017-04

2013-12-18

*项目来源：湖北省“十二五”规划项目（2010ZX03004-003-03）

张立平（1977-），女，湖北随州人，讲师，主要研究方向：计算机软件及应用．