技术领域

本发明涉及计算机技术领域，特别涉及一种路 由表项的存储方法和装置。 背景技术

范围匹配算法是路由器的一项关键技术， 主要基于二叉树的树形结构对 数据进行存储、 查找和更新。 在基于范围匹配算法建立二叉树过程中， 现有 技术将一条路由表项拆成 2个节点，即低节点（ Lowpoint )和高节点（ Toppoint ), 再分别将低节点和高节点以特定规则插入到二 叉树中， 其中二叉树中的每个 节点的大小为表项的大小， 如表项长度为 32bit, 则每个节点的大小为 32bit。

下面以带掩码的 IPv4表项生成 4层二叉树为例进行说明。 表 1中将每条拆 分为 2个节点， 即低节点和高节点， 2个节点形成的范围区间用于表示相应的 带掩码的路由表项， 如 192.0.0.0-193.0.0.0形成的范围区间， 用于表示表项 192.0.0.0/8。 这样， 3条带掩码的 IPv4表项拆分后可得到 6个节点， 按照自右向 左递增的顺序， 将 6个节点插入到二叉树中， 可生成如图 1所示的 4层 2叉树。

发明人在实现本发明实施例过程中发现， 现有技术中二叉树中每个节点 的大小必须等于表项的大小， 当二叉树的节点大小变大时， 二叉树占用的内 存大小就按正比增多。 例如： IPv4表项长度为 32bit, IPv6表项长度为 128bit, 现有技术将一条表项拆分为二个节点， 这样， 如果生成相同层的二叉树， 如 形成如图 1所示的 4层包括 15个节点的二叉树， 则 IPv4表项需要占用的存储空 间大小为 32bit*15=480bit , IPv6表项需要占用 的存储空间大小为 128bit*15=1290bit, 可见， 随着表项长度的增加， 所需占用的内存总量也正比 增力口。 发明内容

本发明实施例提供一种路由表项的存储方法和 装置， 用以减小路由表项 存储所需占用的存储空间。

本发明实施例提供了一种路由表项的存储方法 ， 包括：

将路由表项依据范围匹配策略拆分为二个节点 ， 每个节点的长度等于 所述路由表项的长度； 将每个节点划分为多个段， 所述多个段至少包括： 第一段和第二段， 所述第一段为所述二个节点的共同部分， 所述第二段为 所述二个节点的不同部分；

获取所述路由表项在分层二叉树中的存储位置 ， 所述分层二叉树包括 各段的二叉树， 所述各段的二叉树至少包括第一段的二叉树和 第二段的二 叉树；

根据所述存储位置， 将与所述路由表项相关的各段添加到各段的二 叉 树中， 所述第一段的二叉树通过指针指向所述第二段 的二叉树。

本发明实施例还提供了一种路由表项的存储装 置， 包括：

表项拆分模块， 用于将路由表项依据范围匹配策略拆分为二个 节点， 每个节点的长度等于所述路由表项的长度； 将每个节点划分为多个段， 所 述多个段至少包括： 第一段和第二段， 所述第一段为所述二个节点的共同 部分， 所述第二段为所述二个节点的不同部分；

存储位置获取模块， 用于获取所述路由表项在分层二叉树中的存储 位 置， 所述分层二叉树包括各段的二叉树， 所述各段的二叉树至少包括第一 段的二叉树和第二段的二叉树；

表项存储模块， 用于根据所述存储位置， 将与所述路由表项相关的各 段添加到各段的二叉树中， 所述第一段的二叉树通过指针指向所述第二段 的二叉树。

本发明实施例提取路由表项根据范围匹配策略 拆分的各节点的相同 段作为共同部分、 各节点的不同段作为不同部分， 将路由表项分段存储到 分层二叉树中， 由于本发明实施例无需为提取出的共同部分重 复分配存储空 间， 且不同部分所需占用的存储空间大小小于路由 表项长度， 因此显著减少 了路由表项存储所需占用的内存总量。 附图说明

为了更清楚地说明本发明实施例的技术方案， 下面将对实施例描述中所 需要使用的附图作简单地介绍， 显而易见地， 下面描述中的附图仅仅是本发 明的一些实施例， 对于本领域普通技术人员来讲， 在不付出创造性劳动的前 提下， 还可以根据这些附图获得其他的附图。

图 1为现有技术路由表项存储的二叉树结构示意� �；

图 2为本发明实施例提供的路由表项的存储方法� �程图；

图 3为本发明实施例提供的路由表项存储的二叉� �结构示例一； 图 4为本发明实施例提供的路由表项存储的二叉� �结构示例二； 图 5为本发明实施例提供的路由表项存储的二叉� �结构示例三； 图 6为本发明实施例提供的路由表项的存储装置� �结构示意图。 具体实施方式

下面将结合本发明实施例中的附图， 对本发明实施例中的技术方案进行 清楚、 完整地描述， 显然， 所描述的实施例仅仅是本发明的一部分实施例 ， 而不是全部的实施例。 基于本发明中的实施例， 本领域普通技术人员在没有 做出创造性劳动前提下所获得的所有其他实施 例，都属于本发明保护的范围。 图 2为本发明实施例提供的路由表项的存储方法� �程图。本发明实施例的 执行主体可为路由器。 如图 2所示， 本实施例路由表项的存储方法包括：

步骤 21 : 将一条路由表项依据范围匹配策略拆分为二个 节点， 每个节点 的长度等于所述路由表项的长度； 将每个节点划分为多个段， 所述多个段至 少包括： 第一段和第二段， 所述第一段为所述二个节点的共同部分， 所述第 二段为所述二个节点的不同部分。

通过 Key值信息和掩码长度信息，可以依据范围匹配 策略将一个路由表项 表示为一个范围， 如： 1.1.1.1/24的路由表项中， 1.1.1.1为 Key值信息， 24为掩 码长度信息， 该路由表项所表示的范围为 1.1.1.0 - 1.1.1.255这段区间， 即在此 区间的目的地址都将匹配到 1.1.1.1/24。 这样一个带掩码的路由表项就拆分为 由不带掩码的二个节点表示的范围区间， 每个节点的长度等于路由表项的长 度 24bit。

在将路由表项拆分为二个节点表示的范围区间 之后， 再进行各个节点的 分段拆分。 在分段拆分过程中， 可提取各节点的相同段， 该相同段为各节点 的共同部分， 即为本发明实施例所述的第一段， 如： 提取 1.1.1.0和 1.1.1.255 的高位共同部分 "1.1" 作为第一段； 各节点的不同段， 该不同段为各节点的 不同部分， 即为本发明实施例所述的第二段， 如： 提取 1.1.1.0和 1.1.1.255的低 位不同部分 "1.0" 和 "1.255" 作为第二段。 需要说明的是， 根据各段长度的 大小， 一条路由表项拆分过程中可能出现一个或多个 第一段， 一个或多个第 二段， 即将共同部分划分为一个或多个段， 将不同部分划分为一个或多个段， 其具体实现方式不受限制。

步骤 22: 获取所述路由表项在分层二叉树中的存储位置 ， 所述分层二叉 树包括各段的二叉树， 所述各段的二叉树至少包括第一段的二叉树和 第二段 的二叉树。

分层二叉树中， 高层空洞和与该空洞相邻的低层的空洞即组成 一个二叉 树， 可参图 1所示。 各节点划分为各段之后， 可根据预设策略确定各段的二叉 树。 预设策略如： 分层二叉树各空洞中填入的各段的数值按照 "上大下小且 左大右小" 的策略， 或者， 分层二叉树各空洞中填入的各段的数值按照 "上 大下小且右大左小" 的策略等， 这样在确定某一路由表项相关的各段在分层 二叉树中的存储位置时， 则可根据预设存储策略将需要添加到分层二叉 树的 各段的数值， 与分层二叉树中已添加的段的数值进行比较， 从而确定需要添 加到分层二叉树的各段对应的二叉树的位置， 确定的各段对应的二叉树的位 置整体即为这些段相关的路由表项的存储位置 。

步骤 23 : 根据所述存储位置， 将与所述路由表项相关的各段添加到各段 的二叉树中， 所述第一段的二叉树通过指针指向所述第二段 的二叉树。

在确定了路由表项各段的存储位置后，则可将 各段添加到相应二叉树中， 即将各段填入与各段存储位置对应的二叉树的 空洞， 这样完成了各段数值在 分层二叉树的存储。 之后， 需要建立各段之间的关联， 以便通过分层二叉树 进行信息查询。 具体的， 可采用指针关联的方式建立分层二叉树中各段 内容 之间的关联， 即在使用分层二叉树过程进行信息查询时， 如果当前查询指针 指向分层二叉树中添加的第一段的内容， 则可根据预先建立的指针关联弓 ]导 当前查询指针沿分层二叉树从上到下， 即从高层到低层的自动跳转， 从而可 将当前查询指针由该第一段所在的二叉树指向 的第二段所在的二叉树。

所述将与所述路由表项相关的各段添加到各段 的二叉树中， 可包括： ( 1 )在向所述分层二叉树中添加第一条路由表项� �， 依据步骤 21所示 的方法将该路由表项划分为多个段， 该多个段至少包括第一段和第二段， 为所述第一条路由表项分配各段的二叉树，各 段的二叉树之间通过指针关联。 例如： 为所述第一条路由表项分配第一段的二叉树和 第二段的二叉树， 将第 二段的二个子节点添加到第二段的二叉树，将 第一段添加到第一段的二叉树， 并将第一段的二叉树通过指针指向第二段的二 叉树， 从而建立起该路由表项 的第一段和第二段之间的关联。 由于第二段是二个节点的不同部分组成， 因此， 第二段包括有第一节 点的低位部分和第二节点的低位部分， 第一节点的低位部分和第二节点的 低位相应部分即为组成第二段的二个子节点， 如： 1.1.1.0和 1.1.1.255的低 位部分 " 1.0" 和 " 1.255" 组成第二段， 则 " 1.0" 和 " 1.255" 即为第二段 的二个子节点。 第二段包括的二个子节点添加到第二段的二叉 树中， 如将

" 1.0" 和 " 1.255" 填入第二段的二叉树的空洞中。 这二个字节点在第二 段的二叉树中的具体填入位置， 可根据预设策略， 如前述的 "上大下小、 左大右小" 的策略， 或者， "上大下小、 右大左小" 的策略将二个子节点 填入第二段的二叉树的空洞中。 第一段的二叉树通过指针指向第二段的二 叉树， 即指向第二段的二叉树的顶层节点。

( 2 )在继续向所述分层二叉树中添加路由表项时� � 依据步骤 21所示的方 法将该路由表项划分为多个段， 该多个段至少包括第一段和第二段， 根据精 确匹配策略查找分层二叉树中是否存在需要添 加的路由表项的第一段的二叉 树。 如果分层二叉树中存在需要添加的路由表项的 第一段的二叉树， 则根据 范围匹配策略查找分层二叉树中是否存在需要 添加的路由表项的第二段的二 叉树。 如果分层二叉树中存在需要添加的路由表项的 第一段的二叉树， 但没 有需要添加的路由表项的第二段的二叉树， 则在分层二叉树中分配需要添加 的路由表项的第二段的二叉树， 将需要添加的路由表项的第二段的二个子节 点添加到新分配的第二段的二叉树 , 并将第一段的二叉树通过指针指向新分 配的第二段的二叉树， 从而建立起需要添加的路由表项的第一段和第 二段之 间的关联。

进一步的， 本发明实施例还可包括在分层二叉树中存储与 路由表项对应 的索引信息。 每条路由表项对应的索引信息可根据实际需要 确定， 该索引信 息用于指示该路由表项对应的转发地址信息等 。 为便于在分层二叉树中添加 新的路由表项， 本发明实施例确定在分层二叉树的最底层存储 索引信息， 通 过指针建立路由表项与该路由表项对应的索引 信息之间的关联， 如将路由表 项的第二段， 通过指针指向该路由表项对应的索引信息。

下面以将一条路由表项拆分为二个节点， 且每个节点划分为两段， 即第 一段和第二段为例进行详细说明：

1、 假设将第一条路由表项 192.168.0.1/32插入分层二叉树中：

( 1 )将 32bit掩码的路由表项 192.168.0.1/32拆分为二个节点， 即低节点

192.168.0.1和高节点 192.168.0.2。 低节点和高节点的大小均为 32bit。

( 2 )将低节点 192.168.0.1划分为二段， 即低节点第一段为 192.168, 低节 点第二段为 0.1 , 低节点第一段和低节点第二段的大小均为 16bit。

( 3 )将高节点 192.168.0.2拆分为二段， 即高节点第一段为 192.168, 高节 点第二段为 0.2, 高节点第一段和高节点第二段的大小均为 16bit。

( 4 )确定需要插入的分层二叉树的段并确定相应� �在分层二叉树中的存 储位置， 将确定的段插入相应段的二叉树。

低节点第二段和高节点第二段即组成本发明实 施例所述的第二段的二个 子节点。 将低节点第二段和高节点第二段进行范围匹配 比较， 且将低节点第 二段 0.1和高节点第二段 0.2插入同一二叉树， 插入有低节点第二段 0.1和高节 点第二段 0.2的二叉树称为第二段的二叉树。 低节点第二段和高节点第二段在 同一二叉树中的位置， 可根据预设插入顺序， 如左大由小或者左小右大的顺 序进行插入。 生成的二叉树示例如图 3所示。

将低节点第一段 192.168和高节点第一段 192.168进行精确比较，且在二者 一致时， 说明 192.168为低节点第一段和高节点第一段的共同� �分， 将 192.168 插入与第二段的二叉树相邻的二叉树中， 插入 192.168的二叉树称为第一段的 二叉树。

( 5 )建立插入有 192.168的第一段的二叉树， 与插入有 0.2和 0.1的第二段 的二叉树之间的关联。

将第一段的二叉树的指针指向第二段的二叉树 ， 这样就在二叉树中添加 了路由表项 192.168.0.1/32。 2、 将上述分层二叉树中继续添加路由表项 192.168.11.11/32:

( 1 )将 32bit掩码的路由表项 192.168.11.11/32拆分为二个节点， 即低节点 192.168.11.11和高节点 192.168.11.12。 低节点和高节点的大小均为 32bit。

( 2 )将低节点 192.168.11.11划分为二段， 即低节点第一段为 192.168, 低 节点第二段为 11.11 , 低节点第一段和低节点第二段的大小均为 16bit。

( 3 )将高节点 192.168.11.12拆分为二段， 即高节点第一段为 192.168, 高 节点第二段为 11.12, 高节点第一段和高节点第二段的大小均为 16bit。

( 4 )确定需要插入的分层二叉树的段并确定相应� �在分层二叉树中的存 储位置， 将确定的段插入相应段的二叉树。

将低节点第一段 192.168和高节点第一段 192.168进行精确比较，在二者一 致时， 查找分层二叉树中是否存在 192.168的二叉树； 且在分层二叉树中存在 192.168的二叉树时，获取 192.168的二叉树的指针指向的第二段的二叉树� �空 节点数， 即获取插入有 0.1和 0.2的二叉树的空节点数。 如果空节点数不足， 即 空节点数小于第二段的数量， 如空节点数为 1 , 但第二段的数量为 2, 则分配 新的第二段的二叉树， 即将插入有 0.1和 0.2的二叉树向上提一层， 将 11.11、 11.12插入 0.2所在的二叉树中。 生成的二叉树示例如图 4所示。

( 5 )建立插入有 192.168的第一段的二叉树， 与插入有 11.11、 11.12和 0.2 的第二段的二叉树之间的关联。

将插入有 192.168的第一段的二叉树的指针， 指向插入有 11.11、 11.12和 0.2的第二段的二叉树， 这样就在分层二叉树中添加了路由表项 192.168.0.1/32 和路由表项 192.168.11.11/32。

3、 将路由表项对应的索引信息存储到分层二叉树 的最底层：

可预先确定将分层二叉树的最底层用于存储路 由表项对应的索引信息， 生成的二叉树示例如图 5所示。在实际应用中，可在建立分层二叉树� �过程中， 将分层二叉树的最底层空出来，在将路由表项 的各段添加到分层二叉树之后， 将路由表项对应的索引信息添加到分层二叉树 的最底层， 并通过指针建立路 由表项与其对应的索引信息之间的关联， 例如： 如果在建立分层二叉树过程 中，各段插入顺序为左大右小插入，则从某路 由表项第一段开始顺指针自左再 一直向右直至到达分层二叉树最底层， 指针最终指向的索引即为该路由表项 对应的索引。

本发明实施例将路由表项分段存储， 即将路由表项依据范围匹配策略拆 分为二个节点， 每个节点划分为多个段， 提取各节点的相同段作为共同部分、 各节点的不同段作为不同部分分别添加到各段 的分层二叉树中， 并通过指针 建立相同段的二叉树与不同段的二叉树之间的 关联。 由于本发明实施例无需 为提取出的共同部分重复分配存储空间， 且不同部分所需占用的存储空间大 小小于路由表项长度， 因此减少了范围匹配节点的存储空间。 如 IPv6路由表项长度为 128bit, 则由于采用路由表项分段存储的策略， 路由表 项存储所需占用的内存总量相对于现有技术明 显减少。 不妨以存储 IPV6路由 表项所需占用的内存总量为例进行对比说明。 IPV6路由表项长度为 128bit。采 用现有技术进行路由表项存储， 则则存储 1条 IPV6路由表项需要 2*128bit的内 存， 而本发明实施例进行路由表项存储， 则存储 1条路由表项只需要 3*64bit 的内存。 如果存储的多条路由表项之间都没有重复部分 ， 则采用现有技术存 储 n条路由表项， 需要占用 n*128bit的内存， 而采用本发明实施例存储则 n条路 由表项， 则需要占用 3*n*64bit的内存， 该情形下， 本发明实施例存储路由表 项所需占用的内存总量仅为现有技术的 3/4。 如果存储的多条路由表项之间都 没有重复部分， 例如 n条路由表项的高 64bit都相同， 则采用本发明实施例的存 储方法存储 n条路由表项， 仅需要占用 （2n+l ) *64bit的存储空间， 其所需占 用的内存总量约为现有技术的 1/2。 可见， 采用本发明实施例进行路由表项存 储， 明显减少了路由表项存储所需占用的内存总量 。

在采用本发明上述实施例建立分层二叉树后,� �基于生成的分层二叉树 查找某一路由表项的索引信息。 下面结合图 5对查找过程说明如下： ( 1 )将预先确定的查询路由表项拆分为多个段， 查询路由表项拆段的方 法与在建立分层二叉树过程中插入路由表项时 的拆段方法相同。 以下不妨以 将查询路由表项拆分为二段为例进行说明。 如： 将 IPv4查询路由表项 192.168.0.2拆分为第一段和第二段， 第一段为 IPv4查询路由表项 192.168.0.2的 高 16bit "192.168", 第二段为 IPv4查询路由表项 192.168.0.2的低 16bit "0.2"。

( 2 ) 以精确匹配的查找策略确定填入有与第一段相 同节点的子树。

具体的， 对于子树节点左大右小的分层二叉树,以精确� �配的查找策略, 将第一段" 192.168"与分层二叉树中的节点进行比较,确定填 入有与第一段 "192.168"相同节点的子树。如果第一段" 192.168"大于当前节点，则沿当前节点 相邻的左子树继续查找;如果第一段" 192.168"小于当前节点，则沿当前节点相 邻右子树继续查找； 如果第一段" 192.168"等于当前节点，则沿当前节点的下一 层子树查找第二段。

( 3 )从填入有与第一段相同节点的子树的下一层� �树开始， 以范围匹配 的查找策略确定指针路径。

在填入有第一段" 192.168"节点的下一层子树查找第二段 "0.2"。 如果第二 段 "0.2"大于当前节点，则沿当前节点下一层相邻� ��左子树继续查找;如果第二 段 "0.2"小于当前节点，则沿当前节点下一层相邻� ��右子树继续查找； 如果第二 段 "0.2"等于当前节点,则从当前节点向右直至到达 分层二叉树最底层， 指针最 终指向的索引即为该查询路由表项 192.168.0.2对应的索引。

上述查询路由表项 192.168.0.2索引信息查找过程中的指针路径如图 5中 虚线所示。 在基于分层二叉树确定查询路由表项的索引信 息之后， 可根据索 引信息进行数据转发等处理。

图 6为本发明实施例提供的路由表项的存储装置� �结构示意图。 如图 6所 示， 本实施例路由表项的存储装置包括： 表项拆分模块 61、 存储位置获取模 块 62和表项存储模块 63。

表项拆分模块 61用于将路由表项依据范围匹配策略拆分为二� ��节点， 每个节点的长度等于所述路由表项的长度； 将每个节点划分为多个段， 所 述多个段至少包括： 第一段和第二段， 所述第一段为所述二个节点的共同 部分， 所述第二段为所述二个节点的不同部分。

存储位置获取模块 62用于获取所述路由表项在分层二叉树中的存� �� 位置， 所述分层二叉树包括各段的二叉树， 所述各段的二叉树至少包括第 一段的二叉树和第二段的二叉树。

表项存储模块 63 用于根据所述存储位置， 将与所述路由表项相关的 各段添加到各段的二叉树中， 所述第一段的二叉树通过指针指向所述第二 段的二叉树。

在上述技术方案的基 上， 可选的， 存储位置获取模块可具体用于在所 述路由表项为插入所述分层二叉树的第一条路 由表项时， 为所述路由表项分 配第一段的二叉树和第二段的二叉树 , 将第二段的二个子节点添加到第二段 的二叉树， 将第一段添加到第一段的二叉树。

存储位置获取模块还可具体用于在所述路由表 项不是插入所述分层二叉 树的第一条路由表项时， 在根据精确匹配策略查找到分层二叉树中存在 所述 路由表项的第一段的二叉树、 且根据范围匹配策略没有查找到所述路由表项 的第二段的二叉树， 则分配所述路由表项的第二段的二叉树。 相应的， 表项 存储模块可具体用于将所述路由表项的第二段 插入分配的所述第二段的二叉 树， 所述第一段的二叉树通过指针指向所述第二段 的二叉树。

在上述技术方案的基础上， 路由表项的存储装置还可包括： 索引信息 存储模块 64。 索引信息存储模块 64用于将与所述路由表项对应的索引信 息存储于所述分层二叉树的最底层， 并将所述路由表项的第二段的二叉树 通过指针指向与所述路由表项对应的索引信息 。

本实施例路由表项存储装置将路由表项分段存 储， 即将路由表项依据范 围匹配策略拆分为二个节点， 每个节点划分为多个段， 提取各节点的相同段 作为共同部分、 各节点的不同段作为不同部分分别添加到各段 的分层二叉树 中， 并通过指针建立相同段的二叉树与不同段的二 叉树之间的关联。 由于本 发明实施例无需为提取出的共同部分重复分配 存储空间， 且不同部分所需占 用的存储空间大小小于路由表项长度， 因此减少了范围匹配节点的存储空间。 本实施例路由表项存储装置的表现实体不受限 制， 如可为路由器， 其实现机 理可参见图 2-图 4对应实施例的记载， 在此不再贅述。

本领域普通技术人员可以理解： 附图只是一个优选实施例的示意图， 附 图中的模块或流程并不一定是实施本发明所必 须的。

本领域普通技术人员可以理解： 实施例中的装置中的模块可以按照实施 例描述分布于实施例的装置中， 也可以进行相应变化位于不同于本实施例的 一个或多个装置中。 上述实施例的模块可以合并为一个模块， 也可以进一步 拆分成多个子模块。

上述本发明实施例序号仅仅为了描述， 不代表实施例的优劣。

本领域普通技术人员可以理解： 实现上述方法实施例的全部或部分步骤 可以通过程序指令相关的硬件来完成， 前述的程序可以存储于一计算机可读 取存储介质中， 该程序在执行时， 执行包括上述方法实施例的步骤； 而前述 的存储介质包括： R0M、 RAM , 磁碟或者光盘等各种可以存储程序代码的介质 。

最后应说明的是： 以上实施例仅用以说明本发明的技术方案， 而非对其 限制； 尽管参照前述实施例对本发明进行了详细的说 明， 本领域的普通技术 人员应当理解： 其依然可以对前述实施例所记载的技术方案进 行修改， 或者 对其中部分技术特征进行等同替换； 而这些修改或者替换， 并不使相应技术 方案的本质脱离本发明实施例技术方案的精神 和范围。