路由表项的处理方法和装置

摘要

本发明公开了一种路由表项的处理方法和装置。该方法包括：将路由表项的原边界值增加边界信息位，生成边界信息值，所述原边界值是根据所述路由表项的IP地址得出的；将所述路由表项的掩码设置到所述边界信息值的边界信息位中，生成扩展边界值；将所述扩展边界值存储到二叉树中。本实施例中可根据二叉树中存储的扩展边界值得出扩展边界值对应的路由表项的IP地址和掩码，并根据扩展边界值对应的路由表项的IP地址和掩码得出路由表项之间的包含关系，无需采用三叉树记录路由表项之间的包含关系从而节省了内存资源，并且无需进行针对三叉树的查找和平衡操作仅需进行针对二叉树的查找，从而提高了对路由表项的刷新性能。

权利要求

1.一种路由表项的处理方法，其特征在于，包括：

将路由表项的原边界值增加边界信息位，生成边界信息值，所述原边界值是根据所述路由表项的IP地址得出的；

将所述路由表项的掩码设置到所述边界信息值的边界信息位中，生成扩展边界值；

将所述扩展边界值存储到二叉树中；

所述原边界值包括原上边界值和原下边界值，所述边界信息值包括上边界信息值和下边界信息值；所述将路由表项的原边界值增加边界信息位，生成边界信息值包括：对所述原上边界值进行左移设定位运算处理将所述原上边界值增加边界信息位，生成上边界信息值；以及对所述原下边界值进行左移设定位运算处理将所述原下边界值增加边界信息位，生成下边界信息值；

所述扩展边界值包括扩展上边界值和扩展下边界值；

所述将所述路由表项的掩码设置到所述边界信息值的边界信息位中，生成扩展边界值包括：将所述上边界信息值与所述掩码进行相加处理，生成所述扩展上边界值；以及将所述下边界信息值与所述掩码进行相减处理，生成所述扩展下边界值。

2.根据权利要求1所述的方法，其特征在于，所述将所述扩展边界值存储到二叉树中包括：按照所述生成的扩展下边界值的大小，将所述生成的扩展下边界值存储到所述二叉树中；

按照所述生成的扩展上边界值的大小，将所述生成的扩展上边界值存储到所述二叉树中。

3.根据权利要求2所述的方法，其特征在于，所述按照所述生成的扩展下边界值的大小，将所述生成的扩展下边界值存储到所述二叉树中之后包括：从所述二叉树中查找出第一边界值，所述第一边界值为比所述生成的扩展下边界值大的第一个扩展下边界值；

将所述生成的扩展下边界值对应的关联数据设置为所述第一边界值对应的路由表项的关联数据，并将所述生成的扩展下边界值对应的关联数据存储到所述二叉树中；

从所述二叉树中查找出第二边界值，所述第二边界值为比所述生成的扩展下边界值小的第一个扩展下边界值；

将所述第二边界值对应的关联数据更新为所述生成的扩展下边界值对应的路由表项的关联数据。

4.根据权利要求3所述的方法，其特征在于，所述将所述扩展边界值存储到二叉树中之后还包括：将所述生成的扩展上边界值从所述二叉树中删除，并将所述生成的扩展上边界值对应的关联数据从所述二叉树中删除；

从所述二叉树中查找出第三边界值和第四边界值，所述第三边界值为比所述生成的扩展下边界值小的第一个扩展下边界值，所述第四边界值为比所述生成的扩展下边界值大的第一个扩展下边界值；

将所述第三边界值对应的关联数据更新为所述第四边界值对应的路由表项的关联数据。

将所述生成的扩展下边界值从所述二叉树中删除，并将所述生成的扩展下边界值对应的关联数据从所述二叉树中删除。

5.一种路由表项的处理装置，其特征在于，包括：

第一处理模块，用于将路由表项的原边界值增加边界信息位，生成边界信息值，所述原边界值是根据所述路由表项的IP地址得出的；

第二处理模块，用于将所述路由表项的掩码设置到所述边界信息值的边界信息位中，生成扩展边界值；

存储模块，用于将所述扩展边界值存储到二叉树中；

所述原边界值包括原上边界值和原下边界值，所述边界信息值包括上边界信息值和下边界信息值；

所述第一处理模块用于对所述原上边界值进行左移设定位运算处理将所述原上边界值增加边界信息位，生成上边界信息值；以及对所述原下边界值进行左移设定位运算处理将所述原下边界值增加边界信息位，生成下边界信息值；

所述扩展边界值包括扩展上边界值和扩展下边界值；

所述第二处理模块用于将所述上边界信息值与所述掩码进行相加处理，生成所述扩展上边界值；以及将所述下边界信息值与所述掩码进行相减处理，生成所述扩展下边界值。

6.根据权利要求5所述的装置，其特征在于，所述存储模块用于按照所述生成的扩展下边界值的大小，将所述生成的扩展下边界值存储到所述二叉树中；以及按照所述生成的扩展上边界值的大小，将所述生成的扩展上边界值存储到所述二叉树中。

7.根据权利要求6所述的装置，其特征在于，还包括：与所述存储模块连接的第三处理模块；

所述第三处理模块，用于从所述二叉树中查找出第一边界值，所述第一边界值为比所述生成的扩展下边界值大的第一个扩展下边界值；将所述生成的扩展下边界值对应的关联数据设置为所述第一边界值对应的路由表项的关联数据；从所述二叉树中查找出第二边界值，所述第二边界值为比所述生成的扩展下边界值小的第一个扩展下边界值；将所述第二边界值对应的关联数据更新为所述生成的扩展下边界值对应的路由表项的关联数据；

所述存储模块还用于将所述生成的扩展下边界值对应的关联数据存储到所述二叉树中。

8.根据权利要求7所述的装置，其特征在于，还包括：与所述第三处理模块连接的删除模块；

所述第三处理模块还用于从所述二叉树中查找出第三边界值和第四边界值，所述第三边界值为比所述生成的扩展下边界值小的第一个扩展下边界值，所述第四边界值为比所述生成的扩展下边界值大的第一个扩展下边界值；将所述第三边界值对应的关联数据更新为所述第四边界值对应的路由表项的关联数据；

所述删除模块，用于将所述生成的扩展上边界值从所述二叉树中删除，并将所述生成的扩展上边界值对应的关联数据从所述二叉树中删除，将所述生成的扩展下边界值从所述二叉树中删除，以及将所述生成的扩展下边界值对应的关联数据从所述二叉树中删除。

说明书

路由表项的处理方法和装置

技术领域

[0001] 本发明实施例涉及通信技术领域，特别涉及一种路由表项的处理方法和装置。

背景技术

[0002] 目前，路由器对大容量路由的需要越来越大，针对大容量路由通常采用范围匹配算法进行路由表项的存储和查找。

[0003] 范围匹配算法的基本思想是：将路由表中的路由表项转换为上边界值和下边界值，采用二叉树将所有路由表项的上边界值和下边界值进行排序和存储，并采用三叉树记录路由表项之间的包含关系。当需要从路由表中查找出路由表项时，需要查找二叉树和三叉树以得出路由表项。当路由表项的数量很大时采用三叉树记录表项之间的包含关系会占用大量内存，造成内存资源的浪费；并且当路由表项的数量很大时三叉树的层次会很多，此时针对三叉树进行查找和平衡操作均会耗费相当长的时间，从而降低了对路由表项的刷新性能。

发明内容

[0004] 本发明提供一种路由表项的处理方法和装置，用以节省内存资源和提高对路由表项的刷新性能。

[0005] 本发明实施例提供一种路由表项的处理方法，包括：

[0006] 将路由表项的原边界值增加边界信息位，生成边界信息值，所述原边界值是根据所述路由表项的IP地址得出的；

[0007] 将所述路由表项的掩码设置到所述边界信息值的边界信息位中，生成扩展边界值；

[0008] 将所述扩展边界值存储到二叉树中。

[0009] 本实施例还提供一种路由表项的处理装置，包括：

[0010] 第一处理模块，用于将路由表项的原边界值增加边界信息位，生成边界信息值，所述原边界值是根据所述路由表项的IP地址得出的；

[0011] 第二处理模块，用于将所述路由表项的掩码设置到所述边界信息值的边界信息位中，生成扩展边界值；

[0012] 存储模块，用于将所述扩展边界值存储到二叉树中。

[0013] 本实施例提供的路由表项的处理方法和装置，将路由表项的原边界值增加边界信息位，该原边界值是根据路由表项的IP地址得出的，将路由表项的掩码设置到边界信息值的边界信息位中生成扩展边界值，并将扩展边界值存储到二叉树中，本实施例中可根据二叉树中存储的扩展边界值得出扩展边界值对应的路由表项的IP地址和掩码，并根据扩展边界值对应的路由表项的IP地址和掩码得出路由表项之间的包含关系，无需采用三叉树记录路由表项之间的包含关系从而节省了内存资源，并且无需进行针对三叉树的查找和平衡操作仅需进行针对二叉树的查找，从而提高了对路由表项的刷新性能。

附图说明

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

[0015] 图1a为本发明实施例一提供的一种路由表项的处理方法的流程图；

[0016] 图1b为本发明实施例中路由表项的原边界值的示意图；

[0017] 图1c为本发明实施例中路由表项的扩展边界值的示意图；

[0018] 图2a为本发明实施例二提供的一种路由表项的处理方法的流程图；

[0019] 图2b为本发明实施例中存储或删除路由表项的示意图；

[0020] 图3为本发明实施例三提供的一种路由表项的处理方法的流程图；

[0021] 图4为本发明实施例四提供的一种路由表项的处理装置的结构示意图；

[0022] 图5为本发明实施例五提供的一种路由表项的处理装置的结构示意图；

[0023] 图6为本发明实施例六提供的一种路由表项的处理装置的结构示意图。

具体实施方式

[0024] 为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0025] 图1a为本发明实施例一提供的一种路由表项的处理方法的流程图，如图1a所示，该方法包括：

[0026] 步骤101、将路由表项的原边界值增加边界信息位，生成边界信息值，该原边界值是根据该路由表项的IP地址得出的。

[0027] 本实施例中的各步骤可以由路由表项的处理装置执行。

[0028] 按照范围匹配算法的基本思想，需要首先把路由表项转换为边界值。本实施例中，路由表项的原边界值可以由路由表项的处理装置根据路由表项的IP地址得出，得出的原边界值包括原上边界值和原下边界值。具体地，可以对IP地址对应的数值进行右移指定位运算处理和左移指定位运算处理，得出原上边界值；以及对IP地址对应的数值进行右移指定位运算处理、加1运算处理以及左移指定位运算处理，得出原下边界值。其中指定位为最大掩码减去该路由表项的掩码。图1b为本发明实施例中路由表项的原边界值的示意图，如图1b所示，图1b中示出了三个路由表项：路由表项A、路由表项B和路由表项C。本发明各实施例中，将IP地址、掩码、指定位、设定位数值和设定位最大数值以十进制数值表示，将其余数值均以十六进制数值表示。为便于与十进制数值进行区分，本发明各实施例中的十六进制数值均添加后缀H。本实施例中，以IPv4路由表项为例进行说明。例如：路由表项A的IP地址为0.0.0.0，掩码为20，IPv4路由表项的最大掩码为32，则指定位为12，该IP地址0.0.0.0对应的数值为0H，则对0H进行右移12位运算处理和左移12位运算处理得出原上边界值为0H，对0H进行右移12位运算处理、加1运算处理和左移12位运算处理得出原下边界值为1000H。例如：路由表项B的IP地址为0.0.0.0，掩码为24，IPv4路由表项的最大掩码为32，则指定位为8，该I P地址0.0.0.0对应的数值为0H，则对0H进行右移8位运算处理和左移8位运算处理得出原上边界值为0H，对0H进行右移8位运算处理、加1运算处理和左移8位运算处理得出原下边界值为F0H。例如：路由表项C的IP地址为0.0.15.0，掩码为24，IPv4路由表项的最大掩码为32，则指定位为8，该IP地址0.0.15.0对应的数值为F0H，则对F0H进行右移8位运算处理和左移8位运算处理得出原上边界值为F00H，对F0H进行右移8位运算处理、加1运算处理和左移8位运算处理得出原下边界值为
1000H。若可通过每个原上边界值得出该原上边界值对应的路由表项的IP地址和掩码，以及通过每个原下边界值得出该原下边界值对应的路由表项的IP地址和掩码，则可获知每个原上边界值对应的路由表项和每个下边界值对应的路由表项，也就是说可以获知每个路由表项对应的原上边界值和原下边界值，从而得出路由表项之间的包含关系。但是由于上述各路由表项的原上边界值和原下边界值是根据路由表项的IP地址计算得出的，并且在计算过程中采用的指定位需要通过该路由表项的掩码获得，因此在无法获知路由表项的掩码的情况下仅通过原上边界值或者原下边界值是无法反向计算得出该路由表项的IP地址的。由于只有在获知原上边界值对应的路由表项和原下边界值对应的路由表项才能得出路由表项之间的包含关系，因此仅通过二叉树中的原边界值是无法得出各路由表项之间的包含关系的。

[0029] 本实施例中，边界信息值可包括上边界信息值和下边界信息值。则路由表项的处理装置将路由表项的原上边界值增加边界信息位生成上边界信息值，以及将路由表项的原下边界值增加边界信息位生成下边界信息值。其中，增加的边界信息位可用于设置路由表项的掩码。具体地，路由表项的处理装置可以对原上边界值进行左移设定位运算处理将原上边界值增加边界信息位，生成上边界信息值；以及对原下边界值进行左移设定位运算处理将原下边界值增加边界信息位，生成下边界信息值。其中，设定位可以为大于路由表项的最大掩码所占用位数的位数。例如：本实施例中，以IPv4路由表项为例，由于IPv4路由表项的最大掩码为32，需要占用6bit即该最大掩码32所占用位数为6位，则可以该设定位可以为大于6bit的位数，例如：设定位可以为7位。例如：路由表项A的原上边界值为0H，原下边界值为1000H，则对0H进行左移7位运算处理得出上边界信息值为0H，对1000H进行左移7位运算处理得出下边界信息值为80000H。例如：路由表项B的原上边界值为0H、原下边界值为F0H，则对0H进行左移7位运算处理得出上边界信息值为0H，对F0H进行左移7位运算处理得出下边界信息值为7800H。例如：路由表项C的原上边界值为F00H、扩展下边界值为1000H，则对F00H进行左移7位运算处理得出上边界信息值为78000H，对1000H进行左移7位运算处理得出下边界信息值为80000H。其中，将上边界信息值和下边界信息值以二进制数值表示后，则上述各上边界信息值和各下边界信息值中包括的边界信息位为最后7位，即7个0。

[0030] 步骤102、将路由表项的掩码设置到边界信息值的边界信息位中，生成扩展边界值。

[0031] 具体地，扩展边界值可以包括扩展上边界值和扩展下边界值。则步骤102可以包括：路由表项的处理装置将上边界信息值与路由表项的掩码进行相加处理，生成扩展上边界值；路由表项的处理装置将下边界信息值与路由表项的掩码进行相减处理，生成扩展下边界值。其中，将上边界信息值与掩码进行相加处理的过程即实现了将掩码设置到上边界信息值的边界信息位中；将下边界信息值与掩码进行相减处理的过程即实现了将掩码设置到下边界信息值的边界信息位中。图1c为本发明实施例中路由表项的扩展边界值的示意图，如图1c所示，例如：路由表项A的上边界信息值为0H、掩码为20，则生成的扩展上边界值为14H；路由表项A的下边界信息值为80000H、掩码为20，则生成的扩展下边界值为7FFECH。例如：路由表项B的上边界信息值为0H、掩码为24，则生成的扩展上边界值为18H；
路由表项B的下边界信息值为7800H、掩码为24，则生成的扩展下边界值为77E8H。例如：
路由表项C的上边界信息值为78000H、掩码为24，则生成的扩展上边界值为78018H；路由表项C的下边界信息值为80000H、掩码为24，则生成的扩展下边界值为7FFE8H。

[0032] 步骤103、将扩展边界值存储到二叉树中。

[0033] 本实施例中，路由表项的处理装置是将扩展边界值按照大小顺序存储到二叉树中的。本步骤具体包括：路由表项的处理装置按照路由表项的扩展下边界值的大小，将扩展下边界值存储到二叉树中；并且路由表项的处理装置按照路由表项的扩展上边界值的大小，将扩展上边界值存储到二叉树中。

[0034] 如图1c所示，路由表项的处理装置将路由表项A、路由表项B和路由表项C的扩展边界值按照大小顺序存储到二叉树中，则二叉树中存储的各个扩展边界值的顺序为：路由表项A的扩展上边界值14H、路由表项B的扩展上边界值18H、路由表项B的扩展下边界值77E8H、路由表项C的扩展上边界值78018H、路由表项C的扩展下边界值7FFE8H、路由表项A的扩展下边界值7FFECH。

[0035] 本实施例中，由于二叉树中存储的扩展边界值是将路由表项的掩码设置到边界信息值的边界信息位中得出的，边界信息值是将路由表项的原边界值增加边界信息位得出的，而原边界值是根据路由表项的IP地址得出的，因此二叉树中存储的扩展边界值包含了路由表项的IP地址和掩码。其中，根据扩展边界值得出路由表项的IP地址和掩码的过程具体可以为：取扩展边界值的最后设定位得出设定位数值，其中，扩展边界值的最后设定位为以二进制数值表示的扩展边界值的最后设定位。将该设定位数值与最大掩码进行比较，若该设定位数值小于或等于该最大掩码，则将设定位数值确定为该扩展边界值对应的路由表项的掩码，并判定出该扩展边界值为扩展上边界值；若该设定位数值大于最大掩码，则将设定位最大数值减去设定位数值得出该扩展边界值对应的路由表项的掩码，并判定出该扩展边界值为扩展下边界值，其中设定位最大数值为将设定位取全1时形成的二进制数值对应的十进制数值。在获知了该扩展边界值为扩展上边界值或者扩展下边界值之后，可根据该扩展边界值和该路由表项的掩码计算得出该路由表项的原边界值，其中得出原边界值的过程为根据路由表项的掩码和该路由表项的原边界值得出该扩展边界值的逆运算过程，此处不再详细描述。根据路由表项的原边界值得出该扩展边界值对应的路由表项的IP地址的过程可以为根据路由表项的IP地址得出原边界值的逆运算过程，此处不再详细描述。由于对应于相同IP地址和掩码的扩展边界值对应于同一个路由表项，也就是说，同一个路由表项的扩展边界值对应于相同的IP地址和掩码，因此，本实施例中可根据每个扩展边界值的IP地址和掩码获知每个扩展边界值对应的路由表项，并且通过比较路由表项的扩展边界值的大小得出路由表项之间的包含关系。例如：分别比较两个路由表项的上边界值和下边界值的大小，若一个路由表项的上边界值大于另一个路由表项的上边界值，并且该路由表项的下边界值大于另一个路由表项的下边界值，则该路由表项包含另一个路由表项。

[0036] 如图1c所示，二叉树中存储了六个扩展边界值：14H、18H、77E8H、78018H、7FFE8H和7FFECH。依次根据上述扩展边界值得出该扩展边界值对应的路由表项的IP地址和掩码。例如：对于扩展边界值14H，取该扩展边界值的最后7位得出设定位数值20，该设定位数值
20小于最大掩码32，则将设定位数值20确定为该扩展边界值14H对应的路由表项的掩码，并判定出该扩展边界值14H为扩展上边界值。在获知了该扩展边界值14H为扩展上边界值以及掩码为20之后，可根据该扩展边界值14H和掩码20计算得出该扩展边界值对应的路由表项的原边界值为0H，并根据该原边界值0H得出该扩展边界值14H对应的路由表项的IP地址为0.0.0.0。例如：对于扩展边界值7FFECH，取该扩展边界值的最后7位得出设定位数值108，该设定位数值108大于最大掩码32，则将设定位最大数值128减去设定位数值
108得出该扩展边界值7FFECH对应的路由表项的掩码为20，并判定出该扩展边界值7FFECH为扩展下边界值。在获知了该扩展边界值7FFECH为扩展下边界值以及掩码为20之后，可根据该扩展边界值7FFECH和掩码20计算得出该扩展边界值对应的路由表项的原边界值为
1000H，并根据该原边界值1000H得出该扩展边界值7FFECH对应的路由表项的IP地址为
0.0.15.0。按照上述方法依次得出：扩展边界值18H对应的路由表项的IP地址为0.0.0.0，掩码为24；扩展边界值77E8H对应的路由表项的IP地址为0.0.0.0，掩码为24；扩展边界值78018H对应的路由表项的IP地址为0.0.15.0，掩码为24；扩展边界值7FFE8H对应的路由表项的IP地址为0.0.15.0，掩码为24。

[0037] 本实施例中，由于扩展边界值14H和7FFECH对应于相同的IP地址和掩码，因此扩展边界值14和扩展边界值7FFECH对应于同一路由表项，即图1c中的路由表项A，并且扩展边界值14H为路由表项A的扩展上边界值，扩展边界值7FFECH为路由表项A的扩展下边界值。由于扩展边界值18H和77E8H对应于相同的IP地址和掩码，因此扩展边界值18H和扩展边界值77E8H对应于同一路由表项，即图1c中的路由表项B，并且扩展边界值18H为路由表项B的扩展上边界值，扩展边界值77E8H为路由表项B的扩展下边界值。由于扩展边界值78018H和7FFE8H对应于相同的IP地址和掩码，因此扩展边界值78018H和扩展边界值7FFE8H对应于同一路由表项，即图1c中的路由表项C，并且扩展边界值78018H为路由表项C的扩展上边界值，扩展边界值7FFE8H为路由表项C的扩展下边界值。通过比较路由表项A、路由表项B和路由表项C的各扩展边界值的大小得出：路由表项A包含路由表项B和路由表项C。

[0038] 本实施例提供的路由表项的处理方法，将路由表项的原边界值增加边界信息位，该原边界值是根据路由表项的IP地址得出的，将路由表项的掩码设置到边界信息值的边界信息位中生成扩展边界值，并将扩展边界值存储到二叉树中，本实施例中可根据二叉树中存储的扩展边界值得出扩展边界值对应的路由表项的IP地址和掩码，并根据扩展边界值对应的路由表项的IP地址和掩码得出路由表项之间的包含关系，无需采用三叉树记录路由表项之间的包含关系从而节省了内存资源，并且无需进行针对三叉树的查找和平衡操作仅需进行针对二叉树的查找，从而提高了对路由表项的刷新性能。

[0039] 图2a为本发明实施例二提供的一种路由表项的处理方法的流程图，如图2a所示，该方法包括：

[0040] 步骤201、路由表项的处理装置根据路由表项的IP地址得出该路由表项的原上边界值和原下边界值。

[0041] 步骤202、路由表项的处理装置将该路由表项的原上边界值增加边界信息位生成上边界信息值，将该路由表项的原下边界值增加边界信息位生成下边界信息值。

[0042] 具体地，本步骤可以包括：路由表项的处理装置对原上边界值进行左移运算处理将原上边界值增加边界信息位，生成上边界信息值；以及对原下边界值进行左移运算处理将原下边界值增加边界信息位，生成下边界信息值。

[0043] 步骤203、路由表项的处理装置将路由表项的掩码设置到原上边界值的边界信息位中生成扩展上边界值，并将路由表项的掩码设置到原下边界值的边界信息位中生成扩展下边界值。

[0044] 具体地，本步骤可以包括：路由表项的处理装置将上边界信息值与掩码进行相加处理生成扩展上边界值，以及将下边界信息值与掩码进行相减处理生成扩展下边界值。

[0045] 对上述步骤201至步骤203的具体描述可参见上述实施例一中的步骤101至步骤102。

[0046] 步骤204、路由表项的处理装置将生成的扩展下边界值存储到二叉树中。

[0047] 具体地，本步骤中路由表项的处理装置按照步骤203中生成的扩展下边界值的大小，将该生成的扩展下边界值存储到二叉树中。

[0048] 图2b为本发明实施例中存储或删除路由表项的示意图，如图2b所示，二叉树中已经存储了路由表项A、路由表项B和路由表项C的扩展边界值，本实施例中将路由表项D的扩展边界值存储到二叉树中。执行步骤201至步骤203得出路由表项D的扩展上边界值60016H以及路由表项D的扩展下边界值7FFEAH。本步骤中，路由表项的处理装置按照路由表项D的扩展下边界值7FFEAH的大小，将扩展下边界值7FFEAH存储到二叉树中7FFE8H和
7FFECH之间的位置。

[0049] 步骤205、路由表项的处理装置从二叉树中查找出第一边界值，该第一边界值为比生成的扩展下边界值大的第一个扩展下边界值。

[0050] 本实施例中，第一边界值为包含该生成的扩展下边界值对应的路由表项的路由表项的扩展下边界值。

[0051] 如图2b所示，比路由表项D的扩展下边界值7FFEAH大的第一个扩展下边界值为扩展下边界值7FFECH，即第一边界值为7FFECH。

[0052] 步骤206、路由表项的处理装置将生成的扩展下边界值对应的关联数据(Associate Data，简称：AD)设置为第一边界值对应的路由表项的关联数据，并将该生成的扩展下边界值对应的关联数据存储到二叉树中。

[0053] 本实施例中，关联数据为数据的索引。其中数据可以为出接口信息、下一跳的IP地址信息等。

[0054] 由于二叉树中路由表项的扩展下边界值对应的关联数据为包含该路由表项的路由表项的关联数据，因此本实施例中，路由表项的处理装置将扩展下边界值对应的关联数据设置为第一边界值对应的路由表项的关联数据，其中第一边界值对应的路由表项为包含该路由表项的路由表项。其中，每个路由表项的关联数据为该路由表项的扩展上边界值对应的关联数据。

[0055] 如图2b所示，由于第一边界值对应的路由表项为路由表项A，则路由表项的处理装置将路由表项D的扩展下边界值7FFEAH对应的关联数据设置为路由表项A的关联数据，并将扩展下边界值7FFEAH对应的关联数据存储到二叉树中。其中，路由表项A的关联数据为路由表项A的扩展上边界值14H对应的关联数据。

[0056] 步骤207、路由表项的处理装置从二叉树中查找出第二边界值，该第二边界值为比该生成的扩展下边界值小的第一个扩展下边界值。

[0057] 本实施例中，第二边界值为该路由表项包含的路由表项的扩展下边界值。

[0058] 如图2b所示，比路由表项D的扩展下边界值7FFEAH小的第一个扩展下边界值为扩展下边界值7FFE8H，即第二边界值为7FFE8H。

[0059] 步骤208、路由表项的处理装置将第二边界值对应的路由表项的关联数据更新为该生成的扩展下边界值对应的路由表项的关联数据。

[0060] 由于二叉树中生成的扩展下边界值对应的路由表项的扩展下边界值对应的关联数据为包含该路由表项的路由表项的关联数据，因此本实施例中，路由表项的处理装置将第二边界值对应的路由表项的关联数据更新为该生成的扩展下边界值对应的路由表项的关联数据，其中第二边界值对应的路由表项为该生成的扩展下边界值对应的路由表项包含的路由表项。

[0061] 如图2b所示，由于第二边界值对应的路由表项为路由表项C，则路由表项的处理装置将路由表项C的扩展下边界值7FFE8H对应的关联数据更新为路由表项D的关联数据，并将扩展下边界值7FFE8H对应的关联数据存储到二叉树中。

[0062] 步骤209、路由表项的处理装置将生成的扩展上边界值存储到二叉树中。

[0063] 具体地，本步骤中路由表项的处理装置按照扩展上边界值的大小，将步骤203中生成的扩展上边界值存储到二叉树中。

[0064] 如图2b所示，步骤中，路由表项的处理装置按照路由表项D的扩展上边界值60016H的大小，将扩展上边界值60016H存储到二叉树中77F8H和78018H之间的位置。

[0065] 步骤210、路由表项的处理装置将生成的扩展上边界值对应的关联数据设置为该生成的扩展上边界值对应的路由表项的关联数据，并将该生成的扩展上边界值对应的关联数据存储到二叉树中。

[0066] 由于二叉树中路由表项的扩展上边界值对应的关联数据为该路由表项的关联数据，因此本实施例中，路由表项的处理装置直接将生成的扩展上边界值对应的关联数据设置为该生成的扩展上边界值对应的路由表项的关联数据。

[0067] 本实施例中，可以将生成的扩展上边界值对应的关联数据存储到二叉树中的最后一层，具体的存储方式可按照现有技术中的存储方式进行存储。

[0068] 如图2b所示，路由表项D的扩展上边界值60016H对应的关联数据为路由表项D的关联数据，并将该扩展上边界值60016H对应的关联数据存储到二叉树中。

[0069] 本实施例以及图2中所示的各步骤的执行顺序仅为一种示例，在实际应用中可根据需要进行变更。例如：还可以先执行将生成的扩展上边界值的存储到二叉树中以及将生成的扩展上边界值对应的关联数据存储到二叉树中的操作，再执行将生成的扩展下边界值的存储到二叉树中以及将生成的扩展下边界值对应的关联数据存储到二叉树中的操作。

[0070] 本实施例提供的路由表项的处理方法，路由表项的处理装置可实现将路由表项的扩展边界值和关联数据存储到二叉树中，无需采用三叉树记录路由表项的关联数据从而进一步节省了内存资源，并且无需进行针对三叉树中关联数据的查找和平衡操作仅需进行针对二叉树的查找，从而进一步提高了对路由表项的刷新性能。

[0071] 图3为本发明实施例三提供的一种路由表项的处理方法的流程图，如图3所示，该方法包括：

[0072] 步骤301至步骤310可参见实施例二中的步骤201至步骤210，此处不再赘述。

[0073] 步骤311、路由表项的处理装置将该生成的扩展上边界值从二叉树中删除，并将该生成的扩展上边界值对应的关联数据从二叉树中删除。

[0074] 本实施例中，可以将生成的扩展上边界值对应的关联数据从二叉树中的最后一层中删除，具体的删除方式可按照现有技术中的删除方式进行存储。

[0075] 如图2b所示，二叉树中存储了路由表项A、路由表项B、路由表项C和路由表项D。本实施例中，路由表项的处理装置要将路由表项D从二叉树中删除。本步骤中，路由表项的处理装置将路由表项D的扩展上边界值60016H从二叉树中删除，并将扩展上边界值60016H对应的关联数据从二叉树中删除。

[0076] 步骤312、路由表项的处理装置从二叉树中查找出第三边界值和第四边界值，该第三边界值为比该生成的扩展下边界值小的第一个扩展下边界值，该第四边界值为比该生成的扩展下边界值大的第一个扩展下边界值。

[0077] 本实施例中，第三边界值为该生成的扩展下边界值对应的路由表项包含的路由表项的扩展下边界值，第四边界值为包含该生成的扩展下边界值对应的路由表项的路由表项的扩展下边界值。

[0078] 如图2b所示，路由表项D的扩展下边界值为7FFEAH，则比路由表项D的扩展下边界值7FFEAH小的第一个扩展下边界值为扩展下边界值7FFE8H，即第三边界值为7FFE8H；比路由表项D的扩展下边界值7FFEAH大的第一个扩展下边界值为扩展下边界值7FFECH，即第四边界值为7FFECH。

[0079] 步骤313、路由表项的处理装置将第三边界值对应的关联数据更新为第四边界值对应的路由表项的关联数据。

[0080] 如图2b所示，第三边界值为路由表项C的扩展下边界值7FFE8H，第四边界值对应的路由表项为路由表项A，则将路由表项C的扩展下边界值7FFE8H对应的关联数据更新为路由表项A的关联数据。

[0081] 步骤314、路由表项的处理装置将该生成的扩展下边界值从二叉树中删除，并将该生成的扩展下边界值对应的关联数据从二叉树中删除。

[0082] 如图2b所示，路由表项的处理装置将路由表项D的扩展下边界值7FFEAH从二叉树中删除，并将扩展下边界值7FFEAH对应的关联数据从二叉树中删除。

[0083] 本实施例以及图3中所示的各步骤的执行顺序仅为一种示例，在实际应用中可根据需要进行变更。例如：还可以先执行将生成的扩展下边界值从二叉树中删除以及将生成的扩展下边界值对应的关联数据从二叉树中删除的操作，再执行将生成的扩展上边界值从二叉树中删除以及将生成的扩展上边界值对应的关联数据从二叉树中删除的操作。

[0084] 本实施例提供的路由表项的处理方法，路由表项的处理装置可实现将路由表项的扩展边界值和关联数据从二叉树中删除，无需采用三叉树记录路由表项的关联数据从而进一步节省了内存资源，并且无需进行针对三叉树中关联数据的查找和平衡操作仅需进行针对二叉树的查找，从而进一步提高了对路由表项的刷新性能。

[0085] 图4为本发明实施例四提供的一种路由表项的处理装置的结构示意图，如图4所示，该装置包括：第一处理模块11、第二处理模块12和存储模块13

[0086] 第一处理模块11用于将路由表项的原边界值增加边界信息位，生成边界信息值，所述原边界值是根据所述路由表项的IP地址得出的。

[0087] 第二处理模块12用于将所述路由表项的掩码设置到所述边界信息值的边界信息位中，生成扩展边界值。

[0088] 存储模块13用于将所述扩展边界值存储到二叉树中。

[0089] 本实施例中，原边界值包括原上边界值和原下边界值，边界信息值包括上边界信息值和下边界信息值。则第一处理模块11用于对所述原上边界值进行左移设定位运算处理将所述原上边界值增加边界信息位，生成上边界信息值；以及对所述原下边界值进行左移设定位运算处理将所述原下边界值增加边界信息位，生成下边界信息值。

[0090] 本实施例中，扩展边界值包括扩展上边界值和扩展下边界值。则第二处理模块12用于将所述上边界信息值与所述掩码进行相加处理，生成所述扩展上边界值；以及将所述下边界信息值与所述掩码进行相减处理，生成所述扩展下边界值。

[0091] 本实施例中，所述扩展边界值包括生成的扩展上边界值和生成的扩展下边界值；存储模块13用于按照生成的扩展下边界值的大小，将生成的扩展下边界值存储到所述二叉树中；以及按照生成的扩展上边界值的大小，将生成的扩展上边界值存储到二叉树中。

[0092] 本实施例提供的路由表项的处理装置可用于实现上述实施例一提供的路由表项的处理方法，具体描述可参见实施例一。

[0093] 本实施例提供的路由表项的处理装置，将路由表项的原边界值增加边界信息位，该原边界值是根据路由表项的IP地址得出的，将路由表项的掩码设置到边界信息值的边界信息位中生成扩展边界值，并将扩展边界值存储到二叉树中，本实施例中可根据二叉树中存储的扩展边界值得出扩展边界值对应的路由表项的IP地址和掩码，并根据扩展边界值对应的路由表项的IP地址和掩码得出路由表项之间的包含关系，无需采用三叉树记录路由表项之间的包含关系从而节省了内存资源，并且无需进行针对三叉树的查找和平衡操作仅需进行针对二叉树的查找，从而提高了对路由表项的刷新性能。

[0094] 图5为本发明实施例五提供的一种路由表项的处理装置的结构示意图，如图5所示，该装置在上述实施例四的基础上还包括：与存储模块13连接的第三处理模块14。

[0095] 本实施例中，在存储模块13按照生成的扩展下边界值的大小，将生成的扩展下边界值存储到二叉树中之后，第三处理模块14用于从二叉树中查找出第一边界值，第一边界值为比生成的扩展下边界值大的第一个扩展下边界值；将生成的扩展下边界值对应的关联数据设置为第一边界值对应的路由表项的关联数据；从二叉树中查找出第二边界值，第二边界值为比生成的扩展下边界值小的第一个扩展下边界值；将第二边界值对应的关联数据更新为生成的扩展下边界值对应的路由表项的关联数据。

[0096] 本实施例中，存储模块13按照生成的扩展上边界值的大小，将生成的扩展上边界值存储到二叉树中之后，存储模块13还用于将生成的扩展下边界值对应的关联数据存储到二叉树中。

[0097] 本实施例提供的路由表项的处理装置可实现将路由表项添加到二叉树中。

[0098] 本实施例提供的路由表项的处理装置可用于实现上述实施例二提供的路由表项的处理方法，具体描述可参见实施例二。

[0099] 本实施例提供的路由表项的处理装置可实现将路由表项的扩展边界值和关联数据存储到二叉树中，无需采用三叉树记录路由表项的关联数据从而进一步节省了内存资源，并且无需进行针对三叉树中关联数据的查找和平衡操作仅需进行针对二叉树的查找，从而进一步提高了对路由表项的刷新性能。

[0100] 图6为本发明实施例六提供的一种路由表项的处理装置的结构示意图，如图6所示，该装置在上述实施例五的基础上还包括：与第三处理模块14连接的删除模块15。

[0101] 删除模块15用于将生成的扩展上边界值从二叉树中删除，并将生成的扩展上边界值对应的关联数据从二叉树中删除。第三处理模块14还用于从二叉树中查找出第三边界值和第四边界值，第三边界值为比生成的扩展下边界值小的第一个扩展下边界值，第四边界值为比生成的扩展下边界值大的第一个扩展下边界值；将第三边界值对应的关联数据更新为第四边界值对应的路由表项的关联数据。删除模块15用于将生成的扩展下边界值从所述二叉树中删除，以及将生成的扩展下边界值对应的关联数据从所述二叉树中删除。

[0102] 本实施例提供的路由表项的处理装置可实现将路由表项从二叉树中删除。

[0103] 本实施例提供的路由表项的处理装置可用于实现上述实施例三提供的路由表项的处理方法，具体描述可参见实施例三。

[0104] 本实施例提供的路由表项的处理装置，路由表项的处理装置可实现将路由表项的扩展边界值和关联数据从二叉树中删除，无需采用三叉树记录路由表项的关联数据从而进一步节省了内存资源，并且无需进行针对三叉树中关联数据的查找和平衡操作仅需进行针对二叉树的查找，从而进一步提高了对路由表项的刷新性能。

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

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