CN111988229B - 用于ip与mac地址映射表的压缩存储及快速查找系统及方法 - Google Patents

Abstract

本发明公开了一种用于IP与MAC地址映射表的压缩存储及快速查找系统及方法，该系统中：寄存器组，用于存放大概率IP字段和对应的生命周期倒计时器；设置多个寄存器组，并对寄存器组进行依次编号，用寄存器组的对应编号来表示其对应的大概率IP字段；存储单元阵列，用于存放数据块组成的阵列，阵列的行数为2的“寻址位宽”次幂，寻址位宽即寻址字段的位宽度；列数为允许冲突点的个数，允许冲突点为具有相同寻址字段，但大概率IP字段或其它字段相异的IP地址；数据块的数据结构为：其它字段、MAC地址、寄存器组对应的编号、该数据块对应的生命周期倒计时器。本发明基于硬件实现，减少CPU的负荷，提高存储查找的效率，能减少存储单元的大小，实现快速查询。

Description

用于IP与MAC地址映射表的压缩存储及快速查找系统及方法

技术领域

本发明涉及网络通信技术领域，尤其涉及一种用于IP与MAC地址映射表的压缩存储及快速查找系统及方法。

背景技术

在网络内可以规划使用的IP地址，当有主机要加入该网络时，分配某个IP地址给其使用，当该主机脱离本网络，先前分配给他的IP地址可以给另一台新的主机再使用，因此在网络通信中就需要实时的知晓某个IP地址到底是哪台设备在使用，而标志设备的唯一ID就是他的MAC地址。因此需要存储最新的网络内的IP地址与MAC地址的映射关系。

在传统设备中这部分工作由CPU来完成。而CPU的工作方式是串行的，即他在执行某项任务时就不能执行其他任务了，一次只能有一项任务在做，如果想提高CPU处理其他任务的效率，就必须释放他的部分工作。FPGA因其并行工作及可编程属性，且具备一定的存储的单元(无需再外挂DDR，省成本)，被选中来替代CPU处理该部分工作就具有明显的优势。

发明内容

本发明要解决的技术问题在于针对现有技术中的缺陷，提供一种用于IP与MAC地址映射表的压缩存储及快速查找系统及方法。

本发明解决其技术问题所采用的技术方案是：

本发明提供一种用于IP与MAC地址映射表的压缩存储及快速查找系统，该系统包括：

IP地址拆分单元，用于将IP地址划分为：大概率IP字段、寻址字段、其它字段；其划分规则为：将IP地址以二进制数表示，以8位为单位被分割，32位的IP地址被分割成4个字段，转换为十进制，即采用点分十进制描述方法，预先设定一个大概率阈值；哪个字段的十进制数相同的次数最少，则被划分为寻址字段；哪些字段相同的次数超过大概率阈值，则被划分为大概率字段；未被选中的即为其他字段；

寄存器组，用于存放大概率IP字段和对应的生命周期倒计时器；设置多个寄存器组，并对寄存器组进行依次编号，用寄存器组的对应编号来表示其对应的大概率IP字段；

存储单元阵列，用于存放数据块组成的阵列，阵列的行数为2的“寻址位宽”次幂，寻址位宽即寻址字段的二进制位宽度；列数为允许冲突点的个数，允许冲突点为具有相同寻址字段，但大概率IP字段或其它字段相异的IP地址；数据块的数据结构为：其它字段、MAC地址、寄存器组对应的编号、该数据块对应的生命周期倒计时器；

地址写入单元，用于获取需要写入的IP地址和对应的MAC地址，并将IP地址和MAC地址按照寄存器组和存储单元阵列的数据结构写入其中；

地址读取单元，用于获取需要读取的IP地址，根据其寻址字段读取存储单元阵列，并根据读取到的编号进而读取寄存器组，读取成功后返回数据块中存储的MAC地址。

进一步地，本发明的寄存器组中的数据结构具体为：

大概率IP字段：记作IP[m:n]，表示IP地址区间中，动态指定的大概率字段的上限位标n及下限位标m；

寄存器组的生命周期倒计时器：记作reg_alive_s_time，采用16位宽的计时器，以满足TCP_IP协议要求。

进一步地，本发明的寄存器组的设置个数为：

寄存器组的编号记作reg_id，若编号reg_id的位宽为k，则它最多描述2的k次幂个寄存器组，为了节省资源，选择满足条件的最小整数值作为寄存器组的数量。

进一步地，本发明的存储单元阵列的数据块中的数据结构具体为：

其它字段：记作others_ip，即IP地址中除了大概率IP字段和寻址字段外的值，长度为N个byte；

MAC地址：记作mac_addr，长度为6byte；

寄存器组对应的编号，记作reg_id；

该数据块对应的生命周期倒计时器，记作block_alive_s_time，reg_id和block_alive_s_time的长度共2byte。

进一步地，本发明的该系统还设置有全局清零的功能，当需要清零时CPU控制系统各单元重新回归到原始状态。

本发明提供一种用于IP与MAC地址映射表的压缩存储及快速查找方法，包括以下步骤：

地址映射表的写入流程：获取需要写入的IP地址和对应的MAC地址，并将IP地址和MAC地址按照寄存器组和存储单元阵列的数据结构写入其中；

地址映射表的读取流程：获取需要读取的IP地址，根据其寻址字段读取存储单元阵列，并根据读取到的编号进而读取寄存器组，读取成功后返回数据块中存储的MAC地址。

进一步地，本发明的地址映射表的写入流程的具体步骤为：

W1：产生需要写入的IP地址wr_req_ip，对应的MAC地址wr_req_mac；

W2：根据wr_req_ip中的寻址位，访问存储单元阵列中同一行的多个数据块；

W3：根据步骤W2中各数据块中的编号reg_id查询对应寄存器组，恢复出原始的IP地址；

W4：将wr_req_ip与步骤W3中恢复的各IP比较，若匹配表示已经记录过；记录过进入步骤W5，没有记录过则依次进入步骤W6、W7；

W5：将wr_req_mac写入到mac_addr单元，将对应的数据块中的block_alive_s_time复归到最大生命时长；同时将编号reg_id对应寄存器中的reg_alive_s_time复归到最大生命时长；至此写入操作完成；

W6：查看寄存器组中的内容，分三种情况：

A：当有匹配寄存器值，reg_alive_s_time复归到最大生命时长，进入步骤W7；

B：无匹配值，但有空闲寄存器时，将大概率IP字段写入空闲寄存器，reg_alive_s_time复归到最大生命时长，进入步骤W7；

C：无匹配寄存器且无空闲寄存器时，复位整个寄存器组及存储单元阵列，该情况属于异常回归，向CPU报告异常清空；此时操作异常完成；

W7：查看存储单元阵列中被寻址的数据块，找出block_alive_s_time最小的数据块，将wr_req_mac写入到mac_addr单元，将wr_req_ip中其它字段写入到others_ip单元，且将block_alive_s_time复归到最大生命时长；至此写入操作完成。

进一步地，本发明的地址映射表的读取流程的具体步骤为：

R1：产生需要读取的IP地址rd_req_ip；

R2：根据步骤R1中的IP地址rd_req_ip的寻址字段，访问存储单元阵列中同一行的多个数据块；

R3：根据步骤R2中各个数据块中的reg_id查询对应寄存器组，恢复出原始的IP值；

R4：将rd_req_ip与步骤R3中恢复的各IP比较，匹配表示已经记录过；记录过进入步骤R5，没有记录过进入步骤R6；

R5：回复操作完成，读取成功，返回数据块中的mac_addr；

R6：回复操作完成，读取失败。

本发明产生的有益效果是：本发明提出一种硬件实现的、动态的IP与MAC地址映射表存储方案，根据TCP_IP协议要求，对输入的ARP报文中携带的源IP与源MAC地址进行压缩存储，记录本系统中当前活跃装置的地址映射表，响应上游模块的地址访问操作。提供一种动态更新方案，实时记录网络中的任意地址变换，整个记录查询过程由FPGA自主完成，无需CPU参与，无需外挂DDR，节省成本，提高记录及查询效率，减少CPU开销，提高存储查找的效率；针对IP与MAC地址的映射特点，减少存储单元的大小，实现快速查询；本发明根据应用系统中IP集的特征，动态指定大概率字段，实现了动态存储。

附图说明

下面将结合附图及实施例对本发明作进一步说明，附图中：

图1是本发明实施例的地址映射表的写入流程图；

图2是本发明实施例的地址映射表的读取流程。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

本发明实施例的用于IP与MAC地址映射表的压缩存储及快速查找系统，该系统包括：

IP地址拆分单元，用于将IP地址划分为：大概率IP字段、寻址字段、其它字段；通信中的IP地址为二进制数，通常以8位为单位被分割，如32位的IP地址就被分割成4个字节，转换为十进制，即为常见的点分十进制描述方法：a.b.c.d(其中a,b,c,d都是0～255之间的十进制数)，地址划分基于系统内IP的各十进制位的数量统计，另外需根据经验及存储能力预先设定一个大概率阈值(大概率字段的判断依据)，在统计完成时，哪个字段的十进制数相同的次数最少，则被划分为寻址字段。哪些字段相同的次数超过大概率阈值，则被划分为大概率字段，未被选中的即为其他字段。寄存器组，用于存放大概率IP字段和对应的生命周期倒计时器；设置多个寄存器组，并对寄存器组进行依次编号，用寄存器组的对应编号来表示其对应的大概率IP字段；

存储单元阵列，用于存放数据块组成的阵列，阵列的行数为2的“寻址位宽”次幂，寻址位宽即寻址字段的二进制位宽度；列数为允许冲突点的个数，允许冲突点为具有相同寻址字段，但大概率IP字段或其它字段相异的IP地址；数据块的数据结构为：其它字段、MAC地址、寄存器组对应的编号、该数据块对应的生命周期倒计时器；

地址写入单元，用于获取需要写入的IP地址和对应的MAC地址，并将IP地址和MAC地址按照寄存器组和存储单元阵列的数据结构写入其中；

地址读取单元，用于获取需要读取的IP地址，根据其寻址字段读取存储单元阵列，并根据读取到的编号进而读取寄存器组，读取成功后返回数据块中存储的MAC地址。

寄存器组中的数据结构具体为：

大概率IP字段：记作IP[m:n]，表示IP地址区间中，动态指定的大概率字段的上限位标n及下限位标m；

寄存器组的生命周期倒计时器：记作reg_alive_s_time，采用16位宽的计时器，以满足TCP_IP协议要求。

寄存器组的设置个数为：

寄存器组的编号记作reg_id，若编号reg_id的位宽为k，则它最多描述2的k次幂个寄存器组，为了节省资源，选择满足条件的最小整数值作为寄存器组的数量。

存储单元阵列的数据块中的数据结构具体为：

其它字段：记作others_ip，即IP地址中除了大概率IP字段和寻址字段外的值，长度为N个byte；

MAC地址：记作mac_addr，长度为6byte；

寄存器组对应的编号，记作reg_id；

该数据块对应的生命周期倒计时器，记作block_alive_s_time，reg_id和block_alive_s_time的长度共2byte。

该系统还设置有全局清零的功能，当需要清零时CPU控制系统各单元重新回归到原始状态。

在本发明的另一个具体实施例中，描述了一种基于FPGA实现的，可配置的，压缩存储的，动态记录的IP与MAC地址映射表，提供一种无需外挂DDR的，纯逻辑实现的地址映射存储，查询，老化控制的方法，本方案可以使用在所有硬件实现TCP_IP协议栈的网络通信技术领域。

本发明实施例提出一种针对IP地址特点的存储结构模型，可实现无损压缩存储、快速匹配查找。

IP地址中“网络号”相同的概率一般较大，变化率极低，因此没必要在映射表中存储原始内容，可用少数寄存器进行存储，然后对寄存器组进行编码，再用编码代替原始数据，CPU可以根据实际组网情况，对大概率字段进行动态指定，设计更加灵活。

IP地址中“设备号”相同的概率一般较小，变化率极高，因此可以选取变化率最高的几位做存储空间的索引，这样既可以快速查找，又无需再存储该内容。

若多个IP索引位相同，其他不同，视为冲突节点，可根据板卡能力设计多个冲突节点，为了解决存储空间容量限制，无法全部记录各个装置的地址情况，设计如下解决方案：每个存储节点从写入开始进行生命周期倒计时，倒计时归0，该节点内容被自动清除，当相同索引的多个冲突节点都被使用，新的写操作值被存入生命周期计数最小(倒计时)的节点。这样当前活跃的地址可以被记录，不活跃的地址也会被动态清除，保证整个系统的动态可持续运行。该系统中：

一、存储区间分两部分：寄存器组、存储单元阵列。

二、寄存器组用来存放大概率IP字段，它的结构如表1所示，其中reg_alive_s_time为生命周期倒计时器(在实现中，设计16位宽的计时器，足够满足TCP_IP协议要求)，IP区间的m及n：动态指定的大概率字段的上限位标及下限位标，可以观察平时使用的IP地址，同网络内的IP地址，大部分字段变化比较小，但不同的网络，可能变化小的字段又不太一样，因此可以根据现场IP的特点，找到变化小的字段的区间，即此处提到到大概率字段的上限位标及下限位标，并把该部分内容存储在表1中的寄存器中，每个不同内容的大概率字段都对应一个寄存器组。

表1：寄存器组结构

三、因为表1中存储变化小的字段，因此寄存器组个数并不多，可以给这些寄存器编号，以少数量的编号来替代原来较长的内容，该编号以reg_id表示，根据表1中寄存器组的个数来定reg_id的位宽，若位宽为k，它最多描述2的k次幂个寄存器组，为了节省资源，选择满足条件的最小整数值。

四、存储单元阵列的结构如表2所示，行数为2的“寻址位宽”次幂，比如寻址位宽为8位，则行数为256，列数为允许冲突点的个数，存放有相同寻址值，但其他内容相异的IP。寻址地址我们一般选用变化比较快的字段，一般使用最低字节来作为寻址地址，比如192.168.2.56，192.168.3.56，如果我们以最低字节为寻址地址(他的寻址位宽为8)，地址行为56，因两个IP的次低字节不同，因此需要使用同一行的两个数据块来分别存储。

该阵列的每个元素称为数据块，数据块的结构如表3所示，数据块的结构中block_alive_s_time为生命周期倒计时器，reg_id为对应的寄存器编码，mac_addr为mac地址，前N个字节存放IP中除了大概率字节和寻址字节外的值。因前面提到表1中已存储大概率字节，寻址地址作为行编号，不用额外存储，因此表2中的只需存储未归类的剩余IP字段，该内容将填入others_ip。

表2：存储阵列结构

表3：数据块结构图

五、地址映射表的写入流程：(假设：寻址位为IP的低8位，256*16个存储单元阵列，16个寄存器组)

W1：ARP解析模块(也由FPGA实现，但不属于本文描述范围)产生需要写入的IP地址(wr_req_ip)，对应的MAC地址(wr_req_mac)。

W2：根据步骤W1中的IP的低8位，访问表2中同行的16个数据块。表2在上电初始化时会被全部写零，确保各个节点的在未有效写入之前是无效的，只有有数据被写入后才会在该数据有效期内有效，有效的标志为该节点对应的block_alive_s_time大于0，等于0即代表已失效。当然在运行过程中，也设计有CPU全局清零的功能，确保CPU在需要时将各节点重新回归到原始状态。

W3：根据步骤W2中各数据块中的reg_id查表1寄存器组，恢复出原始的IP地址。

W4：将wr_req_ip与步骤3中恢复的各IP比较，匹配表示已经记录过。记录过进入步骤W5，没有记录过进入步骤W6、W7。

W5：将wr_req_mac写入到mac_addr单元，将记录单元数据块中的block_alive_s_time复归到最大生命时长。同时将reg_id对应寄存器中的reg_alive_s_time复归到最大生命时长。至此操作完成。因进入该步骤的前提是该IP值已经被记录过，所以表2中的others_ip部分不用更新。

W6：查看表1中寄存器的内容，分三种情况：

A、当有匹配寄存器值，reg_alive_s_time复归到最大生命时长，进入步骤W7；

B、无匹配值，但有空闲寄存器时，可将大概率字段写入空闲寄存器，reg_alive_s_time复归到最大生命时长，进入步骤W7。

C、无匹配寄存器且无空闲寄存器时，复位整个寄存器及存储阵列，该情况属于异常回归，需向CPU报告异常清空。此时操作异常完成。

W7：查看存储阵列中被寻址的16个节点，找出block_alive_s_time最小的数据块，将wr_req_mac写入到mac_addr单元，将wr_req_ip中除去存入表1寄存器的大概率字段以及作为寻址地址的小概率字段外的其他值写入到others_ip单元，且将block_alive_s_time复归到最大生命时长。回复操作完成。

六、地址映射表的读取流程

R1：上游模块产生需要读取的IP地址(rd_req_ip)。

R2：根据步骤R1中的IP的低8位，访问表2中同行的16个数据块。

R3：根据步骤R2中各个数据块中的reg_id查表1寄存器组，恢复出原始的IP值。

R4：将rd_req_ip与步骤R3中恢复的各IP比较，匹配表示已经记录过。记录过进入步骤R5，没有记录过进入步骤R6。

R5：回复操作完成，读取成功，返回数据块中的mac_addr。

R6：回复操作完成，读取失败。

应当理解的是，对本领域普通技术人员来说，可以根据上述说明加以改进或变换，而所有这些改进和变换都应属于本发明所附权利要求的保护范围。

Claims (8)

1.一种用于IP与MAC地址映射表的压缩存储及快速查找系统，其特征在于，该系统包括：

IP地址拆分单元，用于将IP地址划分为：大概率IP字段、寻址字段、其它字段；其划分规则为：将IP地址以二进制数表示，以8位为单位被分割，32位的IP地址被分割成4个字段，转换为十进制，即采用点分十进制描述方法，预先设定一个大概率阈值；哪个字段的十进制数相同的次数最少，则被划分为寻址字段；哪些字段相同的次数超过大概率阈值，则被划分为大概率字段；未被选中的即为其他字段；

寄存器组，用于存放大概率IP字段和对应的生命周期倒计时器；设置多个寄存器组，并对寄存器组进行依次编号，用寄存器组的对应编号来表示其对应的大概率IP字段；

存储单元阵列，用于存放数据块组成的阵列，阵列的行数为2的“寻址位宽”次幂，寻址位宽即寻址字段的二进制位宽度，寻址地址作为存储单元阵列的行编号；列数为允许冲突点的个数，允许冲突点为具有相同寻址字段，但大概率IP字段或其它字段相异的IP地址；数据块的数据结构为：其它字段、MAC地址、寄存器组对应的编号、该数据块对应的生命周期倒计时器；

地址写入单元，用于获取需要写入的IP地址和对应的MAC地址，并将IP地址和MAC地址按照寄存器组和存储单元阵列的数据结构写入其中；

地址读取单元，用于获取需要读取的IP地址，根据其寻址字段读取存储单元阵列，并根据读取到的编号进而读取寄存器组，读取成功后返回数据块中存储的MAC地址。

2.根据权利要求1所述的用于IP与MAC地址映射表的压缩存储及快速查找系统，其特征在于，寄存器组中的数据结构具体为：

大概率IP字段：记作IP[m:n]，表示IP地址区间中，动态指定的大概率字段的上限位标n及下限位标m；

寄存器组的生命周期倒计时器：记作reg_alive_s_time，采用16位宽的计时器，以满足TCP_IP协议要求。

3.根据权利要求1所述的用于IP与MAC地址映射表的压缩存储及快速查找系统，其特征在于，寄存器组的设置个数为：

寄存器组的编号记作reg_id，若编号reg_id的位宽为k，则它最多描述2的k次幂个寄存器组，为了节省资源，选择满足条件的最小整数值作为寄存器组的数量。

4.根据权利要求1所述的用于IP与MAC地址映射表的压缩存储及快速查找系统，其特征在于，存储单元阵列的数据块中的数据结构具体为：

其它字段：记作others_ip，即IP地址中除了大概率IP字段和寻址字段外的值，长度为N个byte；

MAC地址：记作mac_addr，长度为6byte；

寄存器组对应的编号，记作reg_id；

该数据块对应的生命周期倒计时器，记作block_alive_s_time，reg_id和block_alive_s_time的长度共2byte。

5.根据权利要求1所述的用于IP与MAC地址映射表的压缩存储及快速查找系统，其特征在于，该系统还设置有全局清零的功能，当需要清零时CPU控制系统各单元重新回归到原始状态。

6.一种用于IP与MAC地址映射表的压缩存储及快速查找方法，采用权利要求1所述的用于IP与MAC地址映射表的压缩存储及快速查找系统，其特征在于，包括以下步骤：

地址映射表的写入流程：获取需要写入的IP地址和对应的MAC地址，并将IP地址和MAC地址按照寄存器组和存储单元阵列的数据结构写入其中；

地址映射表的读取流程：获取需要读取的IP地址，根据其寻址字段读取存储单元阵列，并根据读取到的编号进而读取寄存器组，读取成功后返回数据块中存储的MAC地址。

7.根据权利要求6所述的用于IP与MAC地址映射表的压缩存储及快速查找方法，其特征在于，地址映射表的写入流程的具体步骤为：

W1：产生需要写入的IP地址wr_req_ip，对应的MAC地址wr_req_mac；

W2：根据wr_req_ip中的寻址位，访问存储单元阵列中同一行的多个数据块；

W3：根据步骤W2中各数据块中的编号reg_id查询对应寄存器组，恢复出原始的IP地址；

W4：将wr_req_ip与步骤W3中恢复的各IP比较，若匹配表示已经记录过；记录过进入步骤W5，没有记录过则依次进入步骤W6、W7；

W5：将wr_req_mac写入到mac_addr单元，将对应的数据块中的block_alive_s_time复归到最大生命时长；同时将编号reg_id对应寄存器中的reg_alive_s_time复归到最大生命时长；至此写入操作完成；

W6：查看寄存器组中的内容，分三种情况：

A：当有匹配寄存器值，reg_alive_s_time复归到最大生命时长，进入步骤W7；

B：无匹配值，但有空闲寄存器时，将大概率IP字段写入空闲寄存器，reg_alive_s_time复归到最大生命时长，进入步骤W7；

C：无匹配寄存器且无空闲寄存器时，复位整个寄存器组及存储单元阵列，该情况属于异常回归，向CPU报告异常清空；此时操作异常完成；

W7：查看存储单元阵列中被寻址的数据块，找出block_alive_s_time最小的数据块，将wr_req_mac写入到mac_addr单元，将wr_req_ip中其它字段写入到others_ip单元，且将block_alive_s_time复归到最大生命时长；至此写入操作完成。

8.根据权利要求6所述的用于IP与MAC地址映射表的压缩存储及快速查找方法，其特征在于，地址映射表的读取流程的具体步骤为：

R1：产生需要读取的IP地址rd_req_ip；

R2：根据步骤R1中的IP地址rd_req_ip的寻址字段，访问存储单元阵列中同一行的多个数据块；

R3：根据步骤R2中各个数据块中的reg_id查询对应寄存器组，恢复出原始的IP值；

R4：将rd_req_ip与步骤R3中恢复的各IP比较，匹配表示已经记录过；

记录过进入步骤R5，没有记录过进入步骤R6；

R5：回复操作完成，读取成功，返回数据块中的mac_addr；

R6：回复操作完成，读取失败。

Images