一种实用高效的FIB压缩算法

廖梦虎，张立平

（武汉铁路职业技术学院 电子信息工程系，湖北 武汉 430205）

一种实用高效的FIB压缩算法

廖梦虎，张立平

（武汉铁路职业技术学院 电子信息工程系，湖北 武汉 430205）

研究了高性能路由器FIB空间压缩的问题。基于多位特里算法和结构化分割的方式构造FIB表，实现FIB表的结构冗余和信息冗余的消除。以学校接入路由器FIB数据和FIB自动生成工具生成的FIB数据进行压缩效率对比分析实验，表明该算法具有接近信息熵边界的压缩效率和较高的转发性能。

FIB表压缩；多位特里树；结构分割；FIB信息熵

现今，由于网络规模的不断增长，影响IP查询效率的FIB（Forward Information Base）表越来越庞大，需要占用更大的存储空间，对路由器线卡上的网络处理器（NP：Network Processor）的要求也就越高。文献[1]指出当前预设自由区（DFZ：Defaul Free Zone）中活动IPv4路由前缀超过440，000，IPv6前缀也会很快达到这个程度。基于此，许多专家认为不断增加的存储需求迟早成为高性能路由器转发平面的瓶颈[2]。FIB聚合是一种有效的降低FIB表大小、延长已部署网络设备生命周期、缓解互联网路由扩张带来的扩展性的解决方案[3，4]。其中以ORTC[3]为代表的降低FIB表转发语义冗余和以多位特里树[4]为代表的降低FIB表结构冗余的方案最为典型。FIB压缩除了要考量压缩空间效率，还需要考虑压缩后FIB查找和更新的算法复杂度必须在可控制范围内。只有满足了这两个条件，才有可能得到实际应用。本文以多位特里树算法为基础，采用多位巴罗斯—惠勒编码，通过降低FIB表的信息冗余的方式，将FIB表压缩到进一步接近FIB信息熵边界的程度。同时，通过采取结构化分割处理的方式，按照设定的子树深度门限，将FIB多位特里树分割成主干树和特里子树，降低FIB查找算法的时间复杂度。

一、系统概述

1.FIB冗余消除。为了实现FIB压缩，首先需弄清楚FIB有哪些信息冗余。路由器中一个FIB表是由地址前缀及其关联的下一跳索引标识构成的。下一跳索引标识取值可以用[1，K]的整型表示。我们将FIB的条目数记为N。一个路由器不需要维护与互联网中的其他所有路由器之间的邻接关系，即K<

2.FIB层次消减。即使按照多位特里树结构来组织FIB，FIB查找的时间复杂度是O（W）。由于前缀地址长度W可以到128位（IPv6地址），要实现分组的线性转发还需要通过层次消减，减少FIB查询次数才有可能。可以通过将FIB结构分割的方式减少FIB树的层次。将源多位特里树分割为设定层次阈值内的多个特里子树。子树根节点作为中继节点实现各子树的关联。

二、算法实现

1.多位特里子树节点生成。本文在实现算法中，每个特里子树节点采用多位特里算法生成。首先通过叶压入算法生成多位特里树，然后利用巴斯特—惠勒编码，将多位特里树进行编码转换。这个基于巴斯特—惠勒编码的多位特里树节点生成算法可用一个三元组表示：XB（T）=（Slast，SI，Sa）来表示。其中：Slast和SI是描述特里子树结构的编码，Sa是描述特里子树下一跳索引标识的编码。其中各子串的生成方法如下：Slast是一个长度为N的位串，如果在T中第i个节点是层级中最后一个“孩子”，则该位置1，否则置0；SI是一个长度为N的位串，如果T中第i个节点是内节点，则该位置0，否则置1；Sa长度为N的串，用来编码叶标识。为了实现巴斯特—惠勒转换，需要使用树的宽度优先来实现。假定根是last：Slast[0]=1，对于一个有t个节点的叶标识特里树T，XB（T）转换可以在O（t）时间内完成。

2.层次化多位特里子树构建。形成巴斯特—惠勒编码的多位特里树后，需要根据设定的子树层级阈值进行结构化分割。当子树层次超过设定层次阈值时，将子树结构化分割为多个特里子树。结构化分割为两个过程：节点增加和节点删除过程。当进行特里子树节点删除操作时，如果子树层次深度小于设定阈值h，且该子树拥有一个父特里子树，则需要将特里子树的根合并到父特里子树中，同时更新根在中继中删除的特里子树中的树节点。

三、算法评估

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

表1 压缩效率对比列表

其中N为前缀数量，为下一跳的个数，H0为下一跳分布的香农熵，I为信息理论限制，E为熵，XB为压缩算法所需空间。可以实现2-4bit/每前缀的压缩效果，接近信息理论边界值。

随着Web的快速发展，网络信息需要有效的描述和存储。FIB是一个典型的应用需求。本文利用数据集节点间的关联关系，通过巴罗斯—惠勒转换，将叶压入树进一步优化，在不影响FIB查询性能的前提下，使得位串压缩率接近信息理论限制。同时，将巴罗斯—惠勒转换后的多位特里树进行层次化分割处理，提升了FIB查询算法的效率。

[1]G.Huston.BGP routing table analysis reports[DB/OL].

http：//bgp.potaroo.net/.

[2]D.Meyer，L.Zhang，and K.Fall.Report from the IABW orkshop on Routing and Addressing[D].RFC 4984，2007.

[3]V.Khare，D.Jen，X.Zhao，el.Evolution towardsglobal routingscalability[J].IEEE JSAC，2010，28（8）：1363-1375.

[4]R.P.D raves，C.King，S.Venkatachary，and B.D.Zill.Constructing Optimal IP Routing Tables[C].In Proceedings of IEEE Infocom，1999，3（1）：88-97.

G642.0

A

1674-9324（2014）25-0245-02

湖北省“十二五”规划项目（2010ZX03004-003-03）。

廖梦虎（1972-），男，湖北通城人，硕士研究生，武汉铁路职业技术学院电子电气工程系讲师，主要研究方向：计算机应用，计算机软件，计算机网络；张立平（1977-），女，湖北随州人，硕士研究生，武汉铁路职业技术学院电子电气工程系讲师，主要研究方向：计算机应用，计算机软件，计算机网络。