CN110460529A - 内容路由器fib存储结构及其数据处理方法 - Google Patents

Abstract

本发明公开了一种内容路由器FIB存储结构，包含一个片内存储单元和一个片外存储单元。片内存储单元使用高速存储器，部署多个与不同名称前缀组件数对应的索引结构，以实现基于最长名称前缀匹配机制的名称数据快速索引；片外存储单元使用大容量低速存储器，部署多个与索引结构对应的FIB存储池，以存储实际转发信息。其中，片内索引结构基于神经网络实现，通过学习索引内容在存储器中的分布情况，提高存储效率。对于片内索引结构可能产生的误判，在片外FIB存储池中使用链地址法来处理冲突，即映射到相同地址的数据以链表的形式连接。本发明的结构适合于当前存储器硬件水平，可以有效支持最长名称前缀匹配机制，并提高名称数据的检索速度。

Description

内容路由器FIB存储结构及其数据处理方法

技术领域

本发明属于高性能路由器存储结构设计领域，特别针对命名数据网内容路由器FIB的结构设计和数据处理问题。

背景技术

随着互联网与移动通信技术的不断发展，用户不再满足于传统的点到点通信方式，而是希望可以广泛分发、共享数据信息。然而基于传统TCP/IP技术的互联网通信模型逐渐暴露出IP地址空间耗尽、移动性差、安全性低等弊端，使得无法满足用户对于低延时数据传输、高质量通信的要求。基于这些原因，命名数据网作为一种新型未来网络架构，一经提出便得到广泛关注。

相比于传统的TCP/IP互联网，命名数据网使用完全面向数据内容的通信模式，不再关心内容存储在哪里，而仅关心内容本身。通过在路由节点部署缓冲存储器，命名数据网极大地降低了网络负载，提高了网络资源的共享率，提升了数据传输的性能。

在命名数据网中，所有通信均由消费者驱动，通过交换包含名称标识的兴趣包和数据包实现。为了请求所需数据，消费者首先向网络发送一个兴趣包，路由器记录兴趣包的传入接口，并利用兴趣包的名称根据转发信息库(Forwarding Information Base，FIB)转发，直至到达含有相应数据包的网络节点，将该数据包发回给消费者。因此，FIB的设计直接关系到命名数据网内容路由器的工作性能。然而，由于内容名称不同于IP地址的诸多特征，内容路由器的FIB研究面临着一系列亟待解决的问题和挑战。其一，FIB以名称字符串为索引主键，具有变长、无边界的基本特点，且内容名称在不同应用场景下极具个性化，如何支持差异化名称快速检索成为公认的难题。其二，FIB条目数可达百万级别，且需要更多的存储空间来记录远比IP地址复杂的内容名称及转发信息，如何高效地将转发信息存储在有限的内存中是一个极具挑战的问题。其三，内容路由器FIB具有不同于IP网络路由器的最长名称前缀匹配(Longest Name Prefix Matching，LNPM)机制，如何支持这种机制仍是有待解决的问题。

自2010年命名数据网被提出以来，内容路由器FIB的研究和设计引起了国内外学术界的广泛关注。但是，目前提出的FIB设计方案难以很好地兼顾存储消耗和名称检索速度，且未充分考虑如何有效支持差异化名称检索和LNPM机制。因此，急需提出新的解决思路，设计新颖的FIB整体解决方案，以充分应对上述问题和挑战。

发明内容

针对现有技术，本发明提供了一种新型内容路由器FIB存储结构及其数据处理方法。该结构适合于当前存储器硬件水平，可以有效支持LNPM机制，并提高名称数据的检索速度。

为了解决上述技术问题，本发明提出的一种内容路由器FIB存储结构，包括一个片内存储单元和一个片外存储单元；所述片内存储单元使用高速存储器，其中部署多个与不同名称前缀组件数相对应的索引结构，以实现基于LNPM机制的名称数据快速索引；

所述片内存储单元中的索引结构基于神经网络实现，该索引结构包括输入单元、模型单元和输出单元；所述输入单元用于将路由表索引数据转变为输入向量，将每一条索引数据拆分为若干子向量，然后对所有子向量中相同位置的元素执行按位异或运算，最终得到该索引数据对应的输入向量；所述模型单元用于训练、预测累积分布函数值，所述模型单元是包括第一级的一个神经网络和第二级的若干神经网络；所述输出单元将模型单元已预测的累积分布函数值乘以映射表中槽的总个数，得到映射表中的映射位置，随后根据该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量，求得最终索引地址；

所述片外存储单元使用存储空间可达十亿字节的低速存储器，部署多个与索引结构对应的FIB存储池，以存储实际转发信息；同时，所述片外存储单元对于所述片内索引结构可能产生的误判进行处理。

进一步讲，本发明所述的内容路由器FIB存储结构，其中，所述片外存储单元对于所述片内索引结构可能产生的误判进行处理，是在片外FIB存储池中使用链地址法来处理冲突，即映射到相同地址的数据以链表的形式连接。

同时，本发明还提出了针对上述内容路由器FIB存储结构的数据处理方法，主要包括对兴趣包的转发信息检索和转发信息的更新。

其中，对兴趣包的转发信息检索包括以下步骤：

步骤一、名称数据输入：将兴趣包的内容名称输入到FIB存储结构中；

步骤二、所述片内存储单元的输入处理：所述输入单元将兴趣包的内容名称向量拆分为若干子向量，然后对所有子向量中相同位置的元素执行按位异或运算，得到定长输入向量；

步骤三、所述片内存储单元的模型运算：将步骤二得到的定长输入向量输入模型单元，计算预测的累积分布函数值；

步骤四、所述片内存储单元的位置映射：所述输出单元将步骤三已预测的累积分布函数值乘以映射表中槽的总个数，得到映射表中的映射位置；

步骤五、所述片内存储单元的数据存在性判断：如果映射表中该位置的值不为0，则此兴趣包对应的名称前缀在该FIB存储结构中，执行步骤六；如果映射表中该位置的值为0，则此兴趣包对应的名称前缀不在该FIB存储结构中，转到步骤八；

步骤六、所述片内存储单元的索引地址计算：计算映射表中该位置所在的部分，根据该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量，求得索引地址；

步骤七、所述片外存储单元的转发信息输出：根据索引地址访问片外FIB存储池中的对应地址，输出下一跳路由转发信息，转到步骤九；

步骤八、输出检索结果为：无法匹配；

步骤九、对兴趣包的转发信息检索操作结束。

转发信息的更新包括以下步骤：

步骤一、名称数据和更新类型输入：将待更新的内容名称和对应的更新类型输入到FIB存储结构中；

步骤二、所述片内存储单元的输入处理：将内容名称向量拆分为若干子向量，然后对所有子向量中相同位置的元素执行按位异或运算，得到定长输入向量；

步骤三、所述片内存储单元的模型运算：将定长输入向量输入模型单元，计算预测的累积分布函数值；

步骤四、所述片内存储单元的位置映射：所述输出单元将步骤三已预测的累积分布函数值乘以映射表中槽的总个数，得到映射表中的映射位置，并计算映射表中该位置所在的部分；

步骤五、所述片内存储单元的更新类型判断：如果更新类型为添加，则执行步骤六；如果更新类型为修改，则转到步骤八；如果更新类型为删除，则转到步骤九；

步骤六、所述片内存储单元的添加操作：将该更新的内容名称插入片内与其前缀长度对应的索引结构中，并根据映射表中该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量求得索引地址；

步骤七、所述片外存储单元的添加操作：根据索引地址访问片外FIB存储池中的对应地址，插入相应的路由转发信息，转到步骤十一；

步骤八、所述片外存储单元的修改操作：根据映射表中该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量求得索引地址，根据索引地址访问片外FIB存储池中的对应地址，修改相应的路由转发信息，转到步骤十一；

步骤九、所述片外存储单元的删除操作：根据映射表中该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量求得索引地址，根据索引地址访问片外FIB存储池中的对应地址，删除相应的路由转发信息；

步骤十、所述片内存储单元的删除操作：映射表中对应位置清零；

步骤十一、转发信息的更新操作结束。

与现有技术相比，本发明的有益效果是：

将本发明的内容路由器FIB存储结构及其数据处理方法在一台配置为Intel XeonE5-1650 v2 3.50GHz、DDR3 24GB SDRAM的计算机上进行软件部署测试。实验结果表明，在误判概率为1％的条件下，该FIB存储结构的片内存储消耗为58.258MB，能够部署于高速存储器SRAM上。在支持LNPM机制的条件下，该FIB存储结构的实际吞吐量为1,164万数据包/秒，可满足当前互联网对数据包快速处理的要求。由此表明，本发明中设计的内容路由器FIB存储结构及其数据处理方法，适合于当前存储器硬件水平，可以有效支持LNPM机制，并提高名称数据的检索速度。

附图说明

图1为本发明内容路由器FIB存储结构的结构设计图；

图2为本发明内容路由器FIB存储结构的片内索引结构图；

图3为本发明数据处理方法中关于兴趣包转发信息检索方法的流程框图；

图4为本发明数据处理方法中关于转发信息更新方法的流程框图。

具体实施方式

下面结合附图及具体实施例对本发明做进一步的说明，但下述实施例绝非对本发明有任何限制。

本发明提出内容路由器FIB存储结构，包含一个片内存储单元和一个片外存储单元。所述片内存储单元使用高速存储器，部署多个与不同名称前缀组件数相对应的索引结构，以实现基于LNPM机制的名称数据快速索引；所述片外存储单元使用存储空间较大的低速存储器，部署多个与索引结构对应的FIB存储池，以存储实际转发信息。其中，片内索引结构基于神经网络实现，通过学习索引内容在存储器中的分布情况，提高存储效率。对于片内索引结构可能产生的误判，在片外FIB存储池中使用链地址法来处理冲突，即映射到相同地址的数据以链表的形式连接。

本发明同时提出上述内容路由器FIB存储结构的数据处理方法，包括对兴趣包的转发信息检索方法，以及转发信息更新方法。对兴趣包的转发信息检索过程中，首先按照LNPM机制在片内索引结构组中执行并行检索操作，判断此兴趣包对应的名称前缀是否在该FIB存储结构中；如果存在最长匹配前缀，则根据索引结构输出结果获得最长匹配前缀在片外FIB存储池中的地址，进而读取下一跳路由转发信息；如果不存在匹配前缀，则输出检索结果“无法匹配”。对转发信息更新过程中，如果执行添加操作，首先将该名称插入到片内与其前缀长度对应的索引结构中，然后根据索引结构输出结果访问片外FIB存储池，插入相应的路由转发信息；如果执行修改操作，直接根据片内索引结构输出结果访问片外FIB存储池，修改相应的路由转发信息；若执行删除操作，则同步删除片内索引结构和片外FIB存储池中的相应记录。

如图1所示，本发明提出的内容路由器FIB存储结构，包括一个片内存储单元和一个片外存储单元。具体说明如下：

所述片内存储单元使用高速存储器，部署多个与不同名称前缀组件数相对应的索引结构，以实现基于LNPM机制的名称数据快速索引；所述片外存储单元使用存储空间较大的低速存储器，部署多个与索引结构对应的FIB存储池，以存储实际转发信息。

其中，片内存储单元中的索引结构基于神经网络实现，通过学习索引内容在存储器中的分布情况，提高存储效率。该索引结构如图2所示，输入单元用于将路由表索引数据转变为输入向量，对于每一条索引数据，将其拆分为若干子向量，然后对所有子向量中相同位置的元素执行按位异或运算，最终得到该索引数据对应的输入向量；模型单元用于训练、预测累积分布函数值，包括第一级一个神经网络和第二级若干神经网络；输出单元则将已预测的累积分布函数值乘以映射表中槽的总个数，得到映射表中的映射位置，随后根据该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量，求得最终索引地址。对于片内索引结构可能产生的误判，在片外FIB存储池中使用链地址法来处理冲突，即映射到相同地址的数据以链表的形式连接。

针对本发明的内容路由器FIB存储结构的数据处理方法，包括对兴趣包的转发信息检索方法，以及转发信息更新方法：

(1)对兴趣包的转发信息检索方法，如图3所示，包括以下步骤：

步骤一、名称数据输入：将兴趣包的内容名称输入到上述FIB存储结构中；

步骤二、片内存储单元的输入处理：将内容名称向量拆分为若干子向量，然后对所有子向量中相同位置的元素执行按位异或运算，得到定长输入向量；

步骤三、片内存储单元的模型运算：将定长输入向量输入神经网络模型，计算预测的累积分布函数值；

步骤四、片内存储单元的位置映射：将已预测的累积分布函数值乘以映射表中槽的总个数，得到映射表中的映射位置；

步骤五、片内存储单元的数据存在性判断：如果映射表中该位置的值不为0，则此兴趣包对应的名称前缀在该FIB存储结构中，继续执行；如果映射表中该位置的值为0，则此兴趣包对应的名称前缀不在该FIB存储结构中，转到步骤八；

步骤六、片内存储单元的索引地址计算：计算映射表中该位置所在的部分，根据该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量，求得索引地址；

步骤七、片外存储单元的转发信息输出：根据索引地址访问片外FIB存储池中的对应地址，输出下一跳路由转发信息，转到步骤九；

步骤八、输出检索结果“无法匹配”；

步骤九、对兴趣包的转发信息检索操作结束。

(2)转发信息更新方法，如图4所示，包括以下步骤：

步骤一、名称数据输入：将待更新的内容名称输入到上述FIB存储结构中；

步骤二、片内存储单元的输入处理：将内容名称向量拆分为若干子向量，然后对所有子向量中相同位置的元素执行按位异或运算，得到定长输入向量；

步骤三、片内存储单元的模型运算：将定长输入向量输入神经网络模型，计算预测的累积分布函数值；

步骤四、片内存储单元的位置映射：将已预测的累积分布函数值乘以映射表中槽的总个数，得到映射表中的映射位置，并计算映射表中该位置所在的部分；

步骤五、片内存储单元的更新类型判断：如果更新类型为“添加”，则继续执行；如果更新类型为“修改”，则转到步骤八；如果更新类型为“删除”，则转到步骤九；

步骤六、片内存储单元的添加操作：将该名称插入片内与其前缀长度对应的索引结构中，并根据映射表中该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量求得索引地址；

步骤七、片外存储单元的添加操作：根据索引地址访问片外FIB存储池中的对应地址，插入相应的路由转发信息，转到步骤十一；

步骤八、片外存储单元的修改操作：根据映射表中该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量求得索引地址，根据索引地址访问片外FIB存储池中的对应地址，修改相应的路由转发信息，转到步骤十一；

步骤九、片外存储单元的删除操作：根据映射表中该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量求得索引地址，根据索引地址访问片外FIB存储池中的对应地址，删除相应的路由转发信息；

步骤十、片内存储单元的删除操作：映射表中对应位置清零；

步骤十一、转发信息更新操作结束。

实施例：

将本发明的内容路由器FIB存储结构及其数据处理方法在一台配置为Intel XeonE5-1650 v2 3.50GHz、DDR3 24GB SDRAM的计算机上进行软件部署测试。实验结果表明，在误判概率为1％的条件下，该FIB存储结构的片内存储消耗为58.258MB，能够部署于高速存储器SRAM上。在支持LNPM机制的条件下，该FIB存储结构的实际吞吐量为1,164万数据包/秒，可满足当前互联网对数据包快速处理的要求。由此表明，本发明中设计的内容路由器FIB存储结构及其数据处理方法，适合于当前存储器硬件水平，可以有效支持LNPM机制，并提高名称数据的检索速度。

尽管上面结合附图对本发明进行了描述，但是本发明并不局限于上述的具体实施方式，上述的具体实施方式仅仅是示意性的，而不是限制性的，本领域的普通技术人员在本发明的启示下，在不脱离本发明宗旨的情况下，还可以做出很多变形，这些均属于本发明的保护之内。

Claims (5)

1.一种内容路由器FIB存储结构，包括一个片内存储单元和一个片外存储单元；其特征在于：

所述片内存储单元使用高速存储器，其中部署多个与不同名称前缀组件数相对应的索引结构，以实现基于最长名称前缀匹配机制的名称数据快速索引；

所述片内存储单元中的索引结构基于神经网络实现，该索引结构包括输入单元、模型单元和输出单元；

所述输入单元用于将路由表索引数据转变为输入向量，将每一条索引数据拆分为若干子向量，然后对所有子向量中相同位置的元素执行按位异或运算，最终得到该索引数据对应的输入向量；

所述模型单元用于训练、预测累积分布函数值，所述模型单元是包括第一级的一个神经网络和第二级的若干神经网络；

所述输出单元将模型单元已预测的累积分布函数值乘以映射表中槽的总个数，得到映射表中的映射位置，随后根据该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量，求得最终索引地址；

所述片外存储单元使用存储空间可达十亿字节的低速存储器，部署多个与索引结构对应的FIB存储池，以存储实际转发信息；同时，所述片外存储单元对于所述片内索引结构可能产生的误判进行处理。

2.根据权利要求1所述内容路由器FIB存储结构，其特征在于：所述片外存储单元对于所述片内索引结构可能产生的误判进行处理，是在片外FIB存储池中使用链地址法来处理冲突，即映射到相同地址的数据以链表的形式连接。

3.一种内容路由器FIB存储结构的数据处理方法，其特征在于，针对如权利要求1或2所述的内容路由器FIB存储结构，包括对兴趣包的转发信息检索和转发信息的更新。

4.根据权利要求3所述的内容路由器FIB存储结构的数据处理方法，其特征在于，对兴趣包的转发信息检索，包括以下步骤：

步骤一、名称数据输入：将兴趣包的内容名称输入到FIB存储结构中；

步骤二、所述片内存储单元的输入处理：所述输入单元将兴趣包的内容名称向量拆分为若干子向量，然后对所有子向量中相同位置的元素执行按位异或运算，得到定长输入向量；

步骤三、所述片内存储单元的模型运算：将步骤二得到的定长输入向量输入模型单元，计算预测的累积分布函数值；

步骤四、所述片内存储单元的位置映射：所述输出单元将步骤三已预测的累积分布函数值乘以映射表中槽的总个数，得到映射表中的映射位置；

步骤五、所述片内存储单元的数据存在性判断：如果映射表中该位置的值不为0，则此兴趣包对应的名称前缀在该FIBFIB存储结构中，执行步骤六；如果映射表中该位置的值为0，则此兴趣包对应的名称前缀不在该FIB存储结构中，转到步骤八；

步骤六、所述片内存储单元的索引地址计算：计算映射表中该位置所在的部分，根据该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量，求得索引地址；

步骤七、所述片外存储单元的转发信息输出：根据索引地址访问片外FIB存储池中的对应地址，输出下一跳路由转发信息，转到步骤九；

步骤八、输出检索结果为：无法匹配；

步骤九、对兴趣包的转发信息检索操作结束。

5.根据权利要求3所述的内容路由器FIB存储结构的数据处理方法，其特征在于，转发信息的更新，包括以下步骤：

步骤一、名称数据和更新类型输入：将待更新的内容名称和对应的更新类型输入到FIB存储结构中；

步骤二、所述片内存储单元的输入处理：将内容名称向量拆分为若干子向量，然后对所有子向量中相同位置的元素执行按位异或运算，得到定长输入向量；

步骤三、所述片内存储单元的模型运算：将定长输入向量输入模型单元，计算预测的累积分布函数值；

步骤四、所述片内存储单元的位置映射：所述输出单元将步骤三已预测的累积分布函数值乘以映射表中槽的总个数，得到映射表中的映射位置，并计算映射表中该位置所在的部分；

步骤五、所述片内存储单元的更新类型判断：如果更新类型为添加，则执行步骤六；如果更新类型为修改，则转到步骤八；如果更新类型为删除，则转到步骤九；

步骤六、所述片内存储单元的添加操作：将该更新的内容名称插入片内与其前缀长度对应的索引结构中，并根据映射表中该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量求得索引地址；

步骤七、所述片外存储单元的添加操作：根据索引地址访问片外FIB存储池中的对应地址，插入相应的路由转发信息，转到步骤十一；

步骤八、所述片外存储单元的修改操作：根据映射表中该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量求得索引地址，根据索引地址访问片外FIB存储池中的对应地址，修改相应的路由转发信息，转到步骤十一；

步骤九、所述片外存储单元的删除操作：根据映射表中该位置所在部分对应的基地址和该位置中记录的实际存储器地址偏移量求得索引地址，根据索引地址访问片外FIB存储池中的对应地址，删除相应的路由转发信息；

步骤十、所述片内存储单元的删除操作：映射表中对应位置清零；

步骤十一、转发信息的更新操作结束。