建立路由索引树的方法、装置和查找路由索引树的方法、装置

摘要

本发明实施例提供了一种建立路由索引树的方法、装置及查找路由索引树的方法、装置，涉及网络通信领域；所述一种建立路由索引树的方法，包括：路由索引树根节点保存网络标识，其中所述网络标识包括虚拟专用网标识；在所述根节点下挂的子树节点，保存所述网络标识对应网络中路由前缀的区间端点值。一种查找路由索引树的方法，包括：获取待发报文的目的地址及所述目的地址所属的网络；在路由索引树中，根据所述网络对应的网络标识以及所述目的地址，获取所述待发报文的下一跳地址。所述方法、装置提高了路由查找的速度，可应用于路由查找。

说明书

技术领域

本发明涉及网络通信领域，尤其涉及一种建立路由索引树的方法、装置及查找路由索引树的方法、装置。

背景技术

随着全球化的倾向，很多企业在不同的地点有了更多的分支结构，人们需要安全、方便的数据通讯手段，因此带来了VPN(Virtual Private Network，虚拟专用网)的广泛应用。以往只有接入端路由转发设备才需要支持VPN路由，现在很多中高端路由转发设备直接连接到最终用户。由于传输媒介的速率在迅速增长，路由转发设备需要有更高的最长路由前缀查找能力。如支持100G光缆端口的路由转发设备需要每秒钟查找150M次路由前缀、支持150G端口的路由转发设备需要每秒钟查找250M次路由前缀等。

发明内容

本发明实施例提供了建立路由索引树的方法、装置及查找路由索引树的方法、装置，能够提高路由查找的速度。

一方面，本发明实施例提供了一种建立路由索引树的方法、装置。

一种建立路由索引树的方法，包括：

路由索引树根节点保存网络标识，其中所述网络标识包括虚拟专用网标识；

在所述根节点下挂的子树节点保存所述网络标识对应网络中路由前缀的区间端点值。

一种建立路由索引树的装置，包括：

标识保存模块，用于路由索引树根节点保存网络标识，其中所述网络标识包括虚拟专用网标识；

区间端点值保存模块，用于在所述根节点下挂的子树节点保存所述网络标识对应网络中路由前缀的区间端点值。

另一方面，本发明实施例提供了一种查找路由索引树的方法、装置。

一种查找路由索引树的方法，包括：

获取待发报文的目的地址及所述目的地址所属的网络；

在路由索引树中，根据所述网络对应的网络标识以及所述目的地址，获取所述待发报文的下一跳地址。

一种查找路由索引树的装置，包括：

信息获取模块，用于获取待发报文的目的地址及所述目的地址所属的网络；

地址获取模块，用于在路由索引树中，根据所述网络对应的网络标识以及所述目的地址，获取所述待发报文的下一跳地址。

本发明实施例提供的查找路由索引树的方法、装置，在路由查找过程中添加网络标识为查找值，缩小在路由查找过程中路由前缀的查找范围，达到缩短路由前缀匹配的时间的目的，提高了路由索引树的收敛速度。

附图说明

图1为本发明实施例一提供的建立路由索引树的方法流程图；

图2为本发明实施例二提供的建立路由索引树的方法流程图；

图3为本发明实施例三提供的建立路由索引树的方法流程图；

图4为本发明实施例四提供的建立路由索引树的方法流程图；

图5为本发明实施例四中路由区间的示意图1；

图6为本发明实施例四中路由区间的示意图2；

图7为本发明实施例五提供的建立路由索引树的装置的结构示意图；

图8为图7中区间端点值保存模块的结构示意图；

图9为中本发明实施例五提供的另一种建立路由索引树的装置的结构示意图；

图10为本发明实施例六提供的查找路由索引树的装置的结构示意图；

图11为中本发明实施例六提供的另一种建立路由索引树的装置的结构示意图。

具体实施方式

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

下面结合附图对本发明实施例的方法进行详细描述。

实施例一

如图1所示，一种建立路由索引树的方法，包括：

S101、路由索引树根节点保存网络标识，其中所述网络标识包括虚拟专用网标识；

S102、在所述根节点下挂的子树节点保存所述网络标识对应网络中路由前缀的区间端点值。

本发明实施例提供的建立路由索引树的方法，通过在路由索引树中设置网络标识，实现子树共用所述路由索引树根节点的存储空间，克服现有技术中分配子树固定存储空间，出现子树存储空间不足的问题，实现子树存储空间的自动平衡。

实施例二

如图2所示，下面对本发明实施例一的方法进行详细介绍。

本发明实施例通过软件的二叉树算法实现一个分级的路由索引树，所述路由索引树分为根树和子树，其中每个根树上的根节点下挂一棵子树。

S201、路由索引树的根节点保存网络标识

其中所述网络标识包括虚拟专用网标识和非虚拟专用网的标识。

获取至少一个虚拟专用网的标识，并将所述标识分配给所述虚拟专用网的根节点；设置至少一个非虚拟专用网的网络标识，其中所述标识为保留使用，适用于非虚拟专用网，如公网；将所述网络标识分配给所述路由索引树根节点。

S202、在所述根节点下挂的子树节点保存所述网络标识对应网络中路由前缀的区间端点值

在每个子树根节点，设置子树节点保存路由前缀的区间端点值的阈值，其中所述阈值为子树节点保存路由前缀的区间端点值的最大值或最小值；确定每个路由前缀的区间端点值在所述路由索引树中所属的根节点；在确定后的所述根节点下挂的子树节点保存对应路由前缀的区间端点值。

当所述子树上节点已满时，或子树上节点达到一预定的阈值时，例如子树大小为256个节点，达到或超过3/4，则需要在所述路由索引树上分配新的子树。具体过程如下：当所述子树上节点已满时，有至少一个路由前缀未添加到子树节点，获取未添加的所述路由前缀所属的网络及所述网络对应的网络标识；在所述路由索引树根树上添加一个保存网络标识的根节点，其中所述网络标识为未添加的所述路由前缀对应的网络标识；在添加的所述根节点下，添加一棵子树；在添加的所述根节点，设置添加的所述子树节点保存路由前缀的区间端点值的阈值；在添加的所述子树节点保存所述未添加的路由前缀的区间端点值。

本发明实施例提供的方法，通过在路由索引树中设置网络标识，实现子树共用所述路由索引树根节点的存储空间，克服现有技术中分配子树固定存储空间，出现子树存储空间不足的问题，实现子树存储空间的自动平衡，避免在出现存储空间不足时，消耗系统资源搬移子树的问题，减少系统资源消耗。

实施例三

如图3所示，一种查找路由索引树的方法，包括：

S301、获取待发报文的目的地址及所述目的地址所属的网络；

S302、在路由索引树中，根据所述网络对应的网络标识以及所述目的地址，获取所述待发报文的下一跳地址。

实施例四

如图4所示，本发明实施例提供的另一种查找路由索引树的方法。

S401、获取待发报文的目的地址及所述目的地址所属的网络

具体的，现有技术中获取上述信息的方法均适用于此步骤，不再赘述。

S402、在路由索引树中，根据所述网络对应的网络标识以及所述目的地址，获取所述待发报文的下一跳地址

具体的，在所述路由索引树的根树，以网络标识和目的地址为查找值，确定路由索引树的根节点；在所述根节点下挂的子树节点，以目的地址为查找值，获取所述待发报文的下一跳地址。

可选的，根据所述网络标识，从预先保存的根节点的地址表中确定路由索引树的根节点，其中所述根节点的地址表可通过以网络标识为索引建立；在所述根节点下挂的子树节点，以目的地址为查找值，获取所述待发报文的下一跳地址。

其中在所述路由索引树中不存在记录所述下一跳地址的节点时，则在所述索引树中添加记录所述下一跳地址的节点；

添加所述节点的过程包括：根据网络标识和阈值，确定所述节点在路由索引树中所属的根节点；在所述根节点下的子树上，添加所述节点；根据节点的左右相邻节点的路由前缀的区间端点值，更新所述节点的相邻节点和所述节点的路由前缀区间所包含的子区间对应的节点的路由前缀的区间端点值。

因在所述子树添加了新的节点，为保证所述路由索引树中节点的路由前缀区间不交叉，要更新所述节点的相邻节点和子节点的路由前缀的区间端点值。

为便于修改路由前缀的区间端点值，为每个子树节点保存左右相邻节点和左右最远节点的路由前缀的区间端点值，所述端点值的记录方法可通过在所述子树节点添加指针实现，但方法不限于此，在此不再举例。

更新节点的表项索引值的具体方法如下：

第一类，节点的路由前缀区间左右端点值在索引树中不存在，例如在区间[a1，a2]内添加了节点的路由前缀区间[b1，b2]，则所述区间变成3个子区间，分别为[a1，b1]，[b1，b2]，[b2，a2]，区间[a1，b1]的表项索引值为a1，区间[b1，b2]的表项索引值为b1，[b2，a2]的表项索引值更新为a1。

第二类，节点的路由前缀区间左端点值已存在，右端点值不存在，例如路由索引树中已有区间[a1，a2]后添加了路由前缀区间[b1，b2]，其中a1＝b1。若区间的右端点值b2>a2时，区间[a1，a2]的表项索引值为a1，区间[a2，b2]的表项索引值为a1，并保存所述节点的右端点值。若区间的右端点值b2<a2时，则区间为a1，b2]的表项索引值为a1，区间[b2，a2]的表项索引值为a1，不保存所述节点的右端点值。

第三类，节点的路由前缀区间左端点值不存在，右端点值已存在，例如路由索引树中已有区间[a1，a2]后添加了路由前缀区间[b1，b2]，其中a2＝b2。若区间的左端点值b1<a1时，区间[b1，b2]的表项索引值为a1，不保存所述节点的左端点值；若区间的左端点值b1>a1时，区间[b1，b2]的表项索引值为b1，保存所述节点的左端点值。

第四类，节点的路由前缀区间为其他区间的父区间时，参见图5，添加区间[b1，b2]，所述[b1，b2]区间为[a1，a2]，[a2，a3]，[a3，a4]，[a4，a5]的父区间，则所述[a2，a3]，[a4，a5]，[a5，a6]的表项索引值更新为b1，并保存a2，a4，a5的原表项索引值。

上面对添加节点作了介绍，下面对删除节点作以说明。

在所述路由索引树中删除所述节点时，根据节点的左右最远节点的区间端点值和左右邻节点信息，确定所述节点是否保留；若节点未删除，则所述节点保存的索引值更新为所述节点的路由区间的父区间保存的索引值；更新所述节点的相邻节点和所述节点的路由前缀区间所包含的子区间对应节点的左右相邻节点的区间端点值、索引值；更新节点所在子树根节点的最大值或最小值。

例如，参见图6，若删除区间[b1，b2]时，通过[b2，b3]存的原路由索引值c1，更新[a2，a3][a4，a5]，[a5，a6]的表项索引；若删除区间[b2，b3]，通过区间[b2，b3]原路由索引值c1，更新b2，a7的表项索引值为c1。

本发明实施例提供的方法本发明实施例提供的查找路由索引树的方法、装置，在路由查找过程中添加网络标识为查找值，缩小在路由查找过程中路由前缀的查找范围，达到缩短路由前缀匹配的时间的目的，提高了路由索引树的收敛速度。通过在每个节点设置相邻节点的信息，方便对路由前缀的修改，加快了路由索引树的处理速度，从而提高了网络的收敛速度。

实施例五

如图7所示，本发明实施例五提供的一种建立路由索引树的装置包括：

标识保存模块701，用于路由索引树根节点保存网络标识，其中所述网络标识包括虚拟专用网标识；

其中所述网络标识还包括非虚拟专用网络标识。

进一步的，所述标识保存模块701具体用于：获取至少一个虚拟专用网的网络标识；将所述网络标识分配给所述路由索引树根节点。

所述标识保存模块701具体用于：设置至少一个非虚拟专用网的网络标识；将所述网络标识分配给所述路由索引树根节点。

区间端点值保存模块702，用于在所述根节点下挂的子树节点保存所述网络标识对应网络中路由前缀的区间端点值。

进一步的，如图8所示，所述区间端点值保存模块702可以进一步包括：

阈值设置单元7021，用于在每个子树根节点设置所述子树节点的路由前缀的区间端点值的阈值，其中所述阈值为子树节点保存路由前缀的区间端点值的最大值或最小值；

根节点确定单元7022，用于根据网络标识和阈值，确定每个路由前缀的区间端点值在所述路由索引树中所属的根节点；

区间端点值保存单元7023，用于在确定后的所述根节点下挂的子树节点保存对应路由前缀的区间端点值。

可选的，如图9所示，所述建立路由索引树的装置还可以包括：

子树添加模块703，用于当所述子树上节点已满时，有至少一个路由前缀未添加到子树节点，则获取未添加的所述路由前缀所属的网络及所述网络对应的网络标识；在所述路由索引树根树上添加一个保存网络标识的根节点，其中所述网络标识为未添加的所述路由前缀对应的网络标识；在添加的所述根节点下，添加一棵子树；在添加的所述根节点，设置添加的所述子树节点保存路由前缀的区间端点值的阈值；在添加的所述子树节点保存所述未添加的路由前缀的区间端点值。

本发明实施例提供的建立路由索引树的装置，可以与本发明实施例提供的方法结合使用，通过在路由索引树中设置网络标识，实现子树共用所述路由索引树根节点的存储空间，克服现有技术中固定分配子树固定空间，出现子树存储空间不足的问题，实现子树存储空间的自动平衡。

实施例六

如图10所示，一种查找路由索引树的装置，包括：

信息获取模块1001，用于获取待发报文的目的地址及所述目的地址所属的网络；

地址获取模块1002，用于在路由索引树中，根据所述网络对应的网络标识以及所述目的地址，获取所述待发报文的下一跳地址。

进一步的，所述地址获取模块1002，具体用于在所述路由索引树的根树。以网络标识和目的地址为查找值，确定路由索引树的根节点；在所述根节点下挂的子树，以目的地址为查找值，获取所述待发报文的下一跳地址。

所述地址获取模块1002，具体用于根据所述网络标识，从预先保存的根节点的地址表中确定路由索引树的根节点，其中所述根节点的地址表可通过以网络标识为索引建立；在所述根节点下挂的子树节点，以目的地址为查找值，获取所述待发报文的下一跳地址。

可选的，如图11所示，所述查找路由索引树的装置还可以包括：

添加更新模块1003，具体用于在路由索引树中不存在记录所述下一跳地址的节点时，根据网络标识和阈值确定所述路由索引树中根节点；在所述根节点下的子树上，添加所述节点；根据节点的左右相邻节点的路由前缀的区间端点值，更新所述节点的相邻节点和所述节点的路由前缀区间所包含的子区间对应的节点的路由前缀的区间端点值。

删除更新模块1004，具体用于在删除记录所述下一跳地址的节点时，根据节点的左右最远节点的区间端点值和左右邻节点信息，确定所述节点是否保留；则所述节点保存的索引值更新为所述节点的路由区间的父区间保存的索引值；更新所述节点的相邻节点和所述节点的路由前缀区间所包含的子区间对应节点的左右相邻节点的区间端点值、索引值；更新节点所在子树根节点的最大值或最小值。

本发明实施例提供的查找路由索引树的装置，可以与本发明实施例提供的装置结合使用，在路由查找过程中添加网络标识为查找值，缩小在路由查找过程中路由前缀的查找范围，达到缩短路由前缀匹配的时间的目的，提高了路由索引树的收敛速度。

另外，在本发明各个实施例中的各功能单元可以集成在一个处理模块中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。所述集成的模块如果以软件功能模块的形式实现并作为独立的产品销售或使用时，也可以存储在一个计算机可读取存储介质中。

上述提到的存储介质可以是只读存储器，磁盘或光盘等。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应所述以权利要求的保护范围为准。