技术领域

本发明涉及数据的存储和查找， 更具体地说， 涉及一种用于异构地址 路由的转发方法及装置。

背景技术

传统的基于 IP的路由架构是针对远程主机接入设计的， 随着互联网规 模的不断扩大以及新型网络业务的不断涌现， IP网络提供的面向主机的路 由和尽力服务显然无法满足所有这些需求， 因此人们提出了新型的面向身 份、 内容、 服务的路由寻址机制来解决这些问题。 这些新的路由寻址机制 不再使用 IP来标识其路由对象， 而是使用其他特性， 例如新的名字空间， 来标识目标地址； 比如一段视频的地址可以由名称、 时间、 作者、 类型等 组成， 用户无需知道这段视频存储在网络中的哪个服 务器上， 只需要向网 络要求这个新型的视频标识地址就可以直接找 到它； 又如， 一个电子文档 的地址可以包含作者的数字签名和水印来保证 其完整性和真实性， 用户通 过这个新型的地址就可以在网络中访问它。 一般来讲， 将这种不是由 IP地 址构成的地址称为异构地址。

这些新型路由寻址机制的引入再加上 IPv6的部署使得未来的路由器 需要能够处理海量的异构地址的路由， 而网络的不断扩容增速使得以线速 进行转发变得更加具有挑战性。 转发功能的核心是查表操作， 即对转发表 进行查表， 由于网络规模的增长和新型地址的加入， 这些查找工作还要面 对于越来越大的转发表。 比如当前典型的 IPv4核心路由器中已经需要维护 多达 340k+的记录而且还在不断增长。 随着 32比特的 I P v4地址到 128比特的 IPv6地址的迁移， 以及像 NDN这种为每一个文件、 音乐、 视频都取一个名 字的路由体系， 还有以扁平命名空间形式呈现的其他新型的地 址体系的出 现， 速度与规模的需求将会随着时间增长。

现有的线速转发在硬件上通常使用三态内容寻 址存储器（TCAM, Ternary Content Addres sable Memory) 。 TCAM由于其查找具有严格的线 性速度， 因此在商业路由器中应用的最为广泛。 但 TCAM由于成本高、 功耗 大、 记录更新复杂的问题， 显然无法满足上述的对海量异构地址的查找需 求。 而现有线速转发的软件一般是基于查找树 Tr ie。 查找树的树形的数据 结构在设计上比较适用于 IP这样的结构化的地址， 而其对于异构地址则不 太适合。 另外查找树还有空间消耗大、 速度比较慢等缺点。

发明内容

本发明要解决的技术问题在于， 针对现有技术的上述不适于异构地址、 空间消耗较大、速度较慢的缺陷，提供一种适 合异构地址、 空间消耗较小、 速度较快的用于异构地址路由的转发方法及装 置。

本发明解决其技术问题所采用的技术方案是： 构造一种用于异构地址 路由的转发方法， 包括如下步骤：

A )对转发的地址通过布隆过滤器进行初选， 所述布隆过滤器分 为多个哈希函数段； 初选后得到该地址分别在所述每个哈希函数段 中对应 的初选项；

B )分别依据得到的所述每个哈希函数段中对应� �初选项， 查找 与其对应的摘要向量表中的摘要项；

C )分别相加每个出选项中的值和其对应的摘要� �中的值， 得到 多个表示不同查找路径的权值； 比较得到的多个权值， 选择其值最小的一 个作为转发路径的查找项；

D )依据选择的查找项中摘要项所对应的转发表� �相应位置， 访 问所述转发表， 得到其转发路径。

更进一步地， 所述摘要向量表包括多个摘要项， 每个摘要项分别对应 于所述每个哈希函数段中与其编号相同的初选 项； 所述摘要项还分别对应 于所述转发表中的一项。

更进一步地， 所述转发表使用哈希函数构建； 所述每个哈希函数段的 哈希函数长度、 所述摘要向量表的长度和所述转发表的哈希函 数长度相等。

更进一步地， 所述步骤 B ) 中进一步包括： Bl )逐个将得到初选项中的值和与其对应的摘要� �中的值相加， 得到多个权值；

B2 ) 比较这些权值的大小， 选择其中最小值所表示的查找路径作 为转发路径的查找项。

更进一步地， 所述步骤 B ) 中还包括如下步骤：

B3 )如果得到的所述权值中最小值多于一个， 则选择其中靠进哈希 表头的最小值所表示的查找路径作为转发路径 的查找项。

更进一步地， 还包括如下步骤：

E )在选择存储数据路径时， 如果在步骤 C )中得到的查找项对应的 转发路径中已经存储有数据， 则通过改变所述摘要向量表项中的数值使得 所述权值最小项变化， 从而使得其转发路径的查找项变化， 将数据存储在 不同位置。

更进一步地， 还包括如下步骤：

F )在选择存储数据路径时， 如果所有的经过初选项所对应的查找 项对应的转发路径中已经存储有数据， 则通过改变所述摘要项中的数值移 动一个已存储的数据。

更进一步地， 用于初选的所述布隆过滤器和所述摘要向量表 设置在路 由芯片上， 所述转发表设置在所述路由芯片外的存储器上 。

本发明还涉及一种实现上述方法的装置， 包括：

布隆过滤单元： 用于对转发的地址通过布隆过滤器进行初选， 所 述布隆过滤器分为多个哈希函数段； 初选后得到该地址分别在所述每个哈 希函数段中对应的初选项；

摘要项取得单元： 用于分别依据得到的所述每个哈希函数段中对 应的初选项， 查找与其对应的摘要向量表中的摘要项；

查找项选择单元： 用于分别相加每个出选项中的值和其对应的摘 要项中的值， 得到多个表示不同查找路径的权值； 比较得到的多个权值， 选择其值最小的一个作为转发路径的查找项； 转发表读取单元： 用于依据选择的查找项中摘要项所对应的转发 表中相应位置， 访问所述转发表， 得到其转发路径。

更进一步地， 所述查找项选择单元进一步包括：

权值取得模块： 用于逐个将得到初选项中的值和与其对应的摘 要 项中的值相加， 得到多个权值；

查找项取得模块： 用于比较这些权值的大小， 选择其中最小值所 表示的查找路径作为转发路径的查找项； 如果得到的所述权值中最小值多 于一个， 则选择其中靠进哈希表头的最小值所表示的查 找路径作为转发路 径的查找项。 果： 由于在转发表和进行初步筛选的布隆滤波器之 间设置了摘要向量表， 并通过摘要向量表的值进行运算来选择或指向 转发表中的项， 因此， 其路 由转发工作不依赖于任何类型的地址结构信息 ， 可以工作在无结构的地址 空间中，也可以为有结构的地址提供转发功能 ，而且性能上没有任何区别； 通过初筛机制和引入摘要向量表进行计算， 降低了不必要的对片外存储的 访问要求， 提高了系统效率。

附图说明

图 1 是本发明用于异构地址路由的转发方法及装置 实施例中转发路径 取得的流程图；

图 2是所述实施例中摘要向量表的结构示意图；

图 3是所述实施例中查找项取得流程图；

图 4是所述实施例中的装置结构示意图。

具体实施方式

下面将结合附图对本发明实施例作进一步说明 。

如图 1 所示， 在本发明的异构地址路由的转发方法及装置实 施例中， 其转发方法包括如下步骤：

步骤 S11 通过布隆过滤器进行初选， 得到初选项： 在本步骤中， 将需 要进行转发的地址进行初筛。 由于在本实施例中， 采用布隆过滤器（Bloom f i l ter )对地址进行初步的筛选， 而在本实施例中布隆过滤器是由多段组 成的 （也可以认为是并行的多段过滤器组成一个布 隆过滤器） ， 每段均采 用一个哈希 （Hash )表对地址进行筛选； 经过每段的哈希表对地址进行筛 选后， 可以得到该地址对于每个哈希表所对应的、 该哈希表中的项， 该项 就是一个初选项。 由于布隆过滤器有多段， 而每段均可以得到一个这样的 初选项， 所以， 在本实施例中， 可以得到多个初选项， 该初选项的个数与 布隆过滤器的段数是相同的。

步骤 S12 依据上述各初选项得到其对应的摘要项： 在本步骤中， 依据 上述得到的初选项， 分别得到其对应的、 位于摘要向量表中的项， 即摘要 项。 值得一提的是， 在本实施例中， 摘要向量表的设置使得其中的每一个 向量表中有 4项， 而一个布隆过滤器包括两段， 且每段分别包括 4项， 则 摘要向量表中的第 1 项对应于布隆过滤器中第一段的 1项和第二段的第 1 项， 摘要向量表中的第 2项对应于布隆过滤器中第一段的 2项和第二段的 第 2项， 以此类推（请参见图 2的说明部分） 。 在本步骤中， 就是根据上 述布隆过滤器中得到的初选项， 找到每个初选项对应的摘要项。

步骤 S13 分别使初选项和摘要项相加， 得到其权值； 比较各权值， 选 择其中权值最小的作为转发路径的查找项： 在本步骤中， 逐个将上述得到 的初选项中的值与其对应的摘要项中的值相加 ， 得到多个权值。 在本实施 例中， 初选项实际上是查找转发地址的入口， 通过这些初选项， 可以得到 查找表中的一个具体的位置， 该具体位置存储的内容就是转发地址。 而初 选项和摘要项的值相加得到的权值， 表示在本次选择中初选项的权重， 按 照一定的规律选择不同权重的入口， 即可以得到不同的转发地址。 值得一 提的是，在本实施例中，转发的含义包括了数 据的存储和查找，也就是说， 不同的入口将导致将数据写入到不同位置或读 出不同位置的数据。 只要存 储数据按照一定的规定选择存储地址， 在读出数据时只要按照同样的规定， 即可以得到正确的数据。 此外， 在本步骤中还需要将本步骤中得到的表示 不同入口 （查找项或查找表中的项） 的权值进行比较， 找到并选择其权值 最小的一个作为查找项。

步骤 S 14 访问选择路径中摘要项对应的转发表中的项， 得到转发路径： 在本步骤中， 访问选择的查找项对应的查找表中的项， 得到转发路径。 在 本实施例中， 上述摘要向量表中的项与上述转发表中的项是 ——对应的。 在得到转发路径后， 剩下的操作就是按照该转发路径将数据存储或 读出， 实现转发即可。

请参见图 2 , 在图 2中， 示出了实现上述步骤的摘要向量表结构及其与 初选的布隆滤波器及转发表的关系示意图。 由于在本实施例中要解决面向 海量异构地址的快速路由转发问题， 其面临的问题是转发地址的搜索空间 巨大、 结构特征异构 （不一定是类 IP的最长前缀匹配型， 可以是 平的或 者是其他结构） ， 而且转发表需要容纳海量记录等等。 为了实现该目的， 在当前硬件片上高速存储空间有限的条件下， 采用片上和片外存储的两层 结构， 巨型转发表存储于片外的大容量但访问速度慢 的存储空间中。 该转 发表采用 Hash表结构， 查找速度快而且不需要利用任何地址的结构特 征。 片上使用布隆过滤器（Bloom f i l ter )预筛所有的转发请求， 使得只有转 发表中记录的地址才会访问转发表， 从而节省对慢速片外存储的访问， 同 时提高处理速度。 一般来讲， 普通的 Hash表为了降低沖突的概率， 存储的 空间效率一般都不高。 提高 Hash表的存储效率需要付出其他代价， 比如采 用多个 Hash函数的 Cuckoo Hash通过在每次查找时查看多个表项位置来提 高存储效率。 不过这种方法提高了查找时对 Hash表的读访问次数， 显然会 影响本方案两层结构下的转发查表效率。 为此， 在本实施例中， 在片上增 加一个数据结构， 称为摘要向量表， 通过将片外转发表的摘要信息存储在 这个结构中来帮助定位， 从而不再需要对多个表项位置进行访问。 另外， 在 Bloom f i l ter的运行中总是需要进行一组 Hash计算， 我们也将这些 Hash 计算结果直接应用于片外的转发表查找， 从而节省更多的空间和计算代价。 这样， 通过对初选的结果赋予不同的权重， 从而由初筛结果中找到或选择 正确的项， 减少对转发表的访问次数。

图 2包括一个片上分段计数的布隆过滤器 B ( Bloom f i l ter ) , 一个 片下基于 Hash的转发表 Τ, 在二者之间有一个存储在片上的摘要向量表 S ( summary vector )。摘要向量表中的每一个槽（摘要项）都与 Bloom f i l ter 中每个 Hash函数段中的计数器对应。 如果 Bloom f i 1 ter使用了 k个 Hash函 数， 则摘要向量表中的每个槽就和 Bloom f i l ter中的 k个槽对应 （这些槽 在每段中具有相同的位置或编号）。 例如 S中的第一个槽就和 Hash函数 1的 第一个槽、 Hash函数 2的第一个槽、 直到 Hash函数 k的第一个槽对应。 这 k 个槽再加上摘要向量中对应的那个槽中的数值 将确定查找对象在片外转 发表中的具体位置， 从而使得任何一次查找在摘要向量表的帮助下 最多只 需要访问片外转发表一次， 而不用去查看所有可能的位置。

对于每一个没有通过 Bloom f i l ter的查询， 显然没有必要去访问片外 的转发表， 因为转发表中不会找到该查询的结果。 路由器可以直接进入缺 省的路由生成和添加机制， 比如广播查找机制， 从而避免对片外存储的没 有必要的访问。

如果查询请求通过了 Bloom f i l ter的初筛， 就需要访问片外转发表来 确定具体的转发路径了。首先在 Bloom f i l ter的测试中已经进行了 k个 Hash 计算， 如果在之前插入该记录到转发表的时候如果把 这 k个位置作为储存 记录的潜在选项的话， 查找的时候就只需要考虑这 k个位置就行。 在没有 摘要向量表的情况下， 需要读取这 k个位置的信息才能确定该记录实际上 到底是存放在那个位置； 而在摘要向量表的帮助下， 可以给这 k个位置计 算一个权值， 通过对这些权值排序来确定唯一一个位置来储 存该记录。 这 个权值的计算基于每个候选位置在 k个 Hash函数中对应的槽中的计数再加 上摘要向量中对应的槽中的计数， 总共 k+1个计数。 例如可以将这 k+1个计 数之和作为该位置的权值， 然后比较 k个位置的权值， 取其中最小的一个 存放该记录。 如果最小的权值不止一个， 就选取最靠近 Hash表头的那个位 置来存放。 例如在图 2中， x3定位在哈希表中的第二个位置。

由于 Bloom f i l ter中的 k个哈希函数提供 k个候选位置来存储一项， 可 以利用这 k个哈希函数的来建立一个无沖突的转发表。 比如说， 如果前面 计算出来的位置已经被其他记录占用， 那么还可以考虑其他 k-1个位置是 否空闲； 如果所有候选位置均被占用， 那么可以考虑将某个占用的记录移 走， 因为那个记录自己也有 k个候选位置可以存放， 其中可能还有部分候 选未被占用。 通过在插入记录的时候反复移动 Hash表中的记录可以找到一 个所有记录都能无沖突存放的情况， 而由于能够移动记录这个优势， 最后 形成的无沖突 Hash表的空间效率就比传统 Hash表要高得多。

当然， 由于记录存放的位置是通过前述权值的计算得 到的， 如果选择 移动记录， 就必须改变权值的计算结果， 使得最后选择的那个位置对应的 权值最小。由于 Bloom f i l ter中的 k个 Hash函数的计数本来是 Bloom f i l ter 的内部变量， 直接用于其对输入请求的判断， 如果改变这些计数将影响到 Bloom f i l ter预筛的正确性， 所以改变权值的排序需要通过调整引入的摘 要向量的值来完成。 比如我们可以通过把当前权值小于调整位置权 值的所 有位置对应的摘要向量的槽的计数增加， 来使得调整位置的权值变成最小。 由于摘要向量中计数可能会用于多个记录的位 置的计算， 所以需要在这些 计数的调整过程中保证不会影响到其他无需调 整的记录的位置的计算。

在本实施例中， 如图 3所示， 查找项取得的方法如下：

步骤 S31 分别使初选项和摘要项相加， 得到多个查找项权值： 在本步 骤中， 分别相加得到的初选项中的值及该初选项对应 的摘要项之值， 得到 多个查找项权值。 例如， 在图 2中， x3经过初筛后， 分别对应布隆过滤器 中第 1段的第 4项 （其值为 1 ) 、 第 2段的第 3项 （其值为 2 )和第 3段的 第 2项（其值为 1 )； 于是， 第 1段的第 4项的值加上摘要向量表第 4项的 值（其值为 2 ) , 得到其权值为 3; 第 2段的第 3项的值加上摘要向量表第 3项的值（其值为 4 ) , 得到其权值为 6; 第 3段的第 2项的值加上摘要向 量表第 2项的值（其值为 2 ) , 得到其权值为 3; 因此在本步骤中， 得到 3 个权值， 分别是 3、 6和 3;

步骤 S32 比较多个路径权值， 选择最小值所在作为转发路径查找项： 在本步骤中， 比较上述步骤中得到的权值， 选择其值最小的一个作为转发 路径查找项。 一般来讲， 如果只有一个最小的， 则选择之， 不再执行下一 步骤。 但是， 在上述例子中显然不是这种情况， 上述例子中， 有两个 3 , 因 此需要执行下一步骤。

步骤 S33如果最小值多于一个， 选择最靠近表头位置的一个作为转发 路径查找项： 在上述例子中， 两个权值为 3 的摘要向量表中的摘要项分别 是第 2项和第 4项， 显然， 第 2项比第 4项更靠进表头， 所以， 选择转发 表中第 2项作为 x3的转发路径， 请参见图 3。

总体上来讲， 本实施例采用片上和片外两个部分来实施。 片上部分可 以是高速网络处理器（或路由芯片 ) 内部集成的 SRAM内存， 片外部分可以 是分离的 DRAM存储器或者高速的 SSD固态存储设备。

在本实施例中， Bloom f i l ter和摘要向量表存储在片上， 实际的转发 表以 Hash表的形式存储在片外， 通过使用多个 Hash函数来实现无沖突前提 下空间效率的提高， 通过前述的权值计算方法来确定每一个记录的 具体存 放位置。

片上 Bloom f i l ter的设计采用分段结构， 每一段对应一个 Hash函数， 其长度与片外 Hash表相同， 这样每个 Hash函数的计算结果都会映射到完整 的片外 Hash表上， 或者说一个片外转发表的位置同这 k个 Hash函数中每个 函数的一个槽（或项）相对应。 摘要向量的长度也与之相同。

对于每一个通过 Bloom f i l ter集合成员测试的查询， 对应于 k个计数 器测试的 k个摘要向量的槽（或项）会被进行检测。 查找算法如下：

在所有的槽（或项） 中， 拥有最小值（t ies broken toward the head of the vec tor)的胜出， 其索引将被直接用于在片外 Hash表中进行定位。 例如在图 2中， x3定位在 Hash表中的第二个位置。

具体伪代码如下： 9： eofl if 在本实施例中涉及的伪代码中， y表示要查找的地址， 而 hi ( )表示布 隆过滤器中使用的第 i个哈希函数； indexy则表示 y的查找项； S[ ]表示摘 要向量表； T[ ]表示转发路径表， 而81^1168 1(16 (^( )表示选取（权值 相同者中的） 索引最小者（也就是本实施例中的最靠近表头 者） 。 基本上， 沖突只有在插入新记录时才会发生， 当在插入阶段解决了沖 突后， 在查找、 删除或者之后的任何操作都不会再出现沖突。 当插入是一 条一条进行时， 沖突只会发生在要插入的记录与之前已占用此 计算出来位 置的记录之间。 为了解决这样的沖突， 至少其中一个需要被移走。 从上面 的伪代码中可以看出， 把一个记录从当前位置移走只需要增加摘要向 量中 最小的值， 直到它不再是最小的。 移走的记录有可能在新的位置造成新的 沖突， 只需继续应用这个算法直到最后所有的记录都 不再有沖突。 具体的 消除沖突的函数 ResolveCollision(x， y)的伪代码如下：

!1： end it

12： Store i to the new localion 插入与删除也十分筒单。 由于片上 Bloom filter计数与片外 Hash表已 分开， 因此可以执行独立地执行插入与删除而不影响 彼此。 插入的算法伪码如下：

!2： t| to I l«? te ; _¾ ]

13： end if 、 、 可以看到， Bloom Filter首先更新记录 y, 然后摘要向量会记录这一插 入， 将该记录对应的 k个槽的数字加一。 当更多的记录被添加时， 摘要向量 的各个槽值将会不同， 那么插入新的记录时， 只要比较对应的备选槽值最 找到最小值的槽进行存储即可。 如果插入产生碰撞， 那么消除沖突的方法 或函数将被调用以解决沖突。 由于插入会导致各个槽值发生变化， 那么一个已经存储在某个槽的 数据在进行检索时 SmallestlndexOf (min(S [hi (y)]) (该表达式表示四个操 作的嵌套， 定义见前）可能会发生改变。 那么， 我们就将这一记录 y转存到 当前 SmallestlndexOf (min(S [hi (y) ])对应的槽中以确保查询的顺利进行。 删除的伪码如下：

3； Re ove i m the Bloom. B

删除的算法 4艮筒单， 只需要查询到对应的记录， 并在 Bloom Filter和查 询表中将该记录删除即可。 摘要向量无需改动。

不难发现， 随着插入过程的持续， 摘要向量中的槽值会逐渐增加。 这 对于负载均衡是有好处的， 因为这样的话由 ResolveCollision(x， y) (即 前面解决冲突的伪代码表示的方法）带来的数 字增加会逐渐变得微不足道， 而由插入带来的槽值增加在统计意义上更趋向 于均勾分布。 但是维护大槽 值则要求每个槽值更大的存储空间以存贮日益 增加的数值。 而这样的结果 对于本就紧张的片上存储空间无疑是不利的。 为了解决这一问题， 在本实 施例中采取了两个措施。 首先， 采用了分布式摘要向量技术， 计数器的值 不再累加到摘要向量中， 而是在计算中直接读取 Bloom Filter。 只有那些 无法直接读取的数据， 例如 ResolveCollision(x， y)，产生的数值， 才会被 直接累加到摘要向量中。 另一方面， 采取标准化的方式， 只要摘要向量表 中的最小值大于 0, 我们就会把摘要向量的每一个槽值都减去一个 最小值， 使得槽值全面减小并保留了原槽值之间的区别 。

如图 4所示， 在本实施例中， 还涉及一种实现上述方法的装置， 包括 布隆过滤单元 41、 摘要项取得单元 42、 查找项选择单元 43以及转发表读 取单元 44。 其中， 布隆过滤单元 41用于对转发的地址通过布隆过滤器进行 初选， 所述布隆过滤器分为多个哈希函数段； 初选后得到该地址分别在所 述每个哈希函数段中对应的初选项； 摘要项取得单元 42用于分别依据得到 的所述每个哈希函数段中对应的初选项， 查找与其对应的摘要向量表中的 摘要项； 查找项选择单元 43用于分别相加每个出选项中的值和其对应的� �� 要项中的值， 得到多个表示不同查找路径的权值； 比较得到的多个权值， 选择其值最小的一个作为转发路径的查找项； 转发表读取单元 44用于依据 选择的查找项中摘要项所对应的转发表中相应 位置， 访问所述转发表， 得 到其转发路径。

而查找项选择单元 43进一步包括： 权值取得模块 431用于逐个将得到 初选项中的值和与其对应的摘要项中的值相加 ， 得到多个权值； 查找项取 得模块 432 用于比较这些权值的大小， 选择其中最小值所表示的查找路径 作为转发路径的查找项； 如果得到的所述权值中最小值多于一个， 则选择 其中靠进哈希表头的最小值所表示的查找路径 作为转发路径的查找项。 但并不能因此而理解为对本发明专利范围的限 制。 应当指出的是， 对于本 领域的普通技术人员来说， 在不脱离本发明构思的前提下， 还可以做出若 干变形和改进， 这些都属于本发明的保护范围。 因此， 本发明专利的保护 范围应以所附权利要求为准。