CN100566281C - 虚拟私用网路由查找的方法和装置 - Google Patents

Abstract

本发明公开了一种虚拟私用网路由查找的方法和装置，属于网络通信领域。所述方法包括：在预先建立的索引树中查找关键字对应的最下层的叶子节点；在预先存储的虚拟私用网的IP地址区间和对应的索引信息中，获取叶子节点对应的块，该块包括一个或多个连续的IP地址区间和相应的索引信息；在该块内获取关键字所属的IP地址区间；根据该IP地址区间对应的索引信息，找到该索引信息对应的路由表项。所述装置包括：查找模块和获取模块。本发明实现了VPN路由的查找，且提高了查找的效率。采用索引树与路由相关信息的分层次查找结构，可以很方便地采用FPGA或者ASIC实现，设计和实现的复杂度较低，且可以灵活地支持很多个VPN。

Description

虚拟私用网路由查找的方法和装置

技术领域

本发明涉及网络通信领域，特别涉及一种虚拟私用网路由查找的方法和装置。

背景技术

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

现有技术中通常为每个VPN建立一个独立的路由查找表。如采用多个Muti-bit Trie(或者加bitmap)的算法实现VPN路由查找。另外，还有一种方法是使用B-Tree的路由查找算法进行路由查找，其中路由查找表是一棵B-Tree，在B-Tree的不同层的节点保存了位向量来指引搜索进程。

在实现本发明的过程中，发明人发现上述现有技术至少具有以下缺点：

为每个VPN建立一个独立的路由查找表，空间浪费严重，尤其是路由条目较少的VPN，却要维持大量的辅助信息，导致空间利用率很低下，因此可以支持的VPN数目不多，而且路由更新的速度慢。使用B-Tree进行路由查找时，只能返回最长匹配的路由表项的长度，无法直接返回最长匹配的路由表项。

发明内容

为了提高VPN路由查找的效率，本发明实施例提供了一种虚拟私用网路由查找的方法和装置。所述技术方案如下：

一种虚拟私用网路由查找的方法，所述方法包括：在预先建立的索引树中，根据虚拟私用网的标识信息查找关键字对应的最下层的叶子节点；在预先存储的虚拟私用网的IP地址区间和对应的索引信息中，获取所述叶子节点对应的块，所述块包括一个或多个连续的IP地址区间和相应的索引信息；在所述块内获取所述关键字所属的IP地址区间；根据所述IP地址区间对应的索引信息，找到所述索引信息对应的路由表项。

一种虚拟私用网路由查找的装置，所述装置包括：

查找模块，用于在预先建立的索引树中，根据虚拟私用网的标识信息查找关键字对应的最下层的叶子节点；

获取模块，用于在预先存储的虚拟私用网的IP地址区间和对应的索引信息中，获取所述查找模块找到的叶子节点对应的块，所述块包括一个或多个连续的IP地址区间和相应的索引信息，在所述块内获取所述关键字所属的IP地址区间，根据所述IP地址区间对应的索引信息找到该索引信息对应的路由表项。

本发明实施例提供的技术方案的有益效果是：

通过建立索引树和预存VPN的IP地址区间和索引信息，来查找关键字对应的IP地址区间及其对应的索引，从而获取相应的路由表项，实现了VPN路由的查找，且提高了查找的效率。最下层叶子节点对应保存IP地址区间和索引信息的块，降低了索引树的高度，提高了路由查找的速度，保存IP地址区间和索引信息而不是VPN路由表项，可以进一步提高路由查找的速度。采用索引树与路由相关信息的分层次查找结构，可以很方便地采用FPGA或者ASIC实现，设计和实现的复杂度较低，且可以灵活地支持很多个VPN。

附图说明

图1是本发明实施例1提供的虚拟私用网路由查找的方法流程图；

图2是本发明实施例1提供的VPN索引表、多棵索引树和记录表的关系示意图；

图3是本发明实施例1提供的VPN索引表、索引树内存和路由信息内存的关系示意图；

图4是本发明实施例1提供的采用多棵索引树进行路由查找的示意图；

图5是本发明实施例1提供的添加新的VPN时索引树内存的变化示意图；

图6是本发明实施例2提供的虚拟私用网路由查找的方法流程图；

图7是本发明实施例2提供的一棵索引树和记录表的关系示意图；

图8是本发明实施例2提供的采用一棵索引树进行路由查找的示意图；

图9是本发明实施例3提供的虚拟私用网路由查找的装置结构图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明实施方式作进一步地详细描述。

本发明实施例通过在预先建立的索引树中查找关键字对应的最下层的叶子节点，并在预先存储的虚拟私用网的IP地址区间和对应的索引信息中，获取该叶子节点对应的块，在该块内获取关键字所属的IP地址区间，根据该IP地址区间对应的索引信息找到对应的路由表项，实现了VPN路由表项的查找。

实施例1

本实施例以给每个VPN建立一棵索引树为例进行说明，在本实施例中关键字即目的IP地址。参见图1，本发明实施例提供了一种虚拟私用网路由查找的方法，具体包括以下步骤：

步骤101：预先存储VPN的IP地址区间和索引信息，可以采用记录表的形式，将VPN的IP地址区间和索引信息保存在一个记录表中，或者将VPN的IP地址区间和索引信息分别保存在两个记录表中，并建立IP地址区间和索引信息的一一对应关系，根据该对应关系可以从IP地址区间找到索引信息。记录表可以是一个有序的数组，数组中的元素可以按照IP地址的大小来排序，如从小到大的顺序。数组可以采用低速的存储器来实现，从而降低成本。

步骤102：预先为每个VPN建立一棵索引树，多个VPN时，则建立多棵索引树，每个索引树中的叶子节点保存有该索引树对应的VPN的IP地址，且最下层的叶子节点对应了记录表的一个块(section)，块中有一个或多个连续的元素，每个元素包括一个IP地址区间和一个索引信息。采用包含多个连续的元素的块与采用包含一个元素的块相比，可以提高查找速度。

其中，索引树可以为二叉树，也可以为多叉树，通常为满树，如Cache Oblivious B-Tree。索引树可以采用高速存储器来保存。索引树中叶子节点的排列顺序可以根据二叉查找树规则进行排列，如下一层左边的节点保存的IP地址小于本层节点保存的IP地址，下一层右边的节点保存的IP地址大于或等于本层节点保存的IP地址。

为了区分不同的索引树，进一步地，还可以建立VPN索引表，保存VPN的标识信息，如VPN ID，以及该VPN对应的索引树的根节点的地址，通过VPN索引表中的VPN标识来找到目标VPN的索引树，进行路由查找。例如，参见图2，为每个VPN建立一棵索引树，VPN索引表中有多个VPN的标识和索引树根节点的地址信息，包括VPNi，VPNk和VPNm，其中，根据VPNi的标识及对应的索引树的根节点的地址可以找到索引树i，根据VPNk的标识及对应的索引树的根节点的地址可以找到索引树k，根据VPNm的标识及对应的索引树的根节点的地址可以找到索引树m，每个索引树的最下层的叶子节点对应该VPN的路由表项的相关信息，包括IP地址区间和索引信息。另外，VPN索引表中保存的信息还可以包括索引树的高度，代表索引树在内存中占用的空间长度。例如，参见图3，VPN索引表中每个VPN ID对应的信息都包括指针和索引树的高度，该指针是指索引树的根节点的地址，对应了索引树内存中该索引树的起始地址，索引树的高度决定了该索引树在内存中占用的空间长度。索引树的最下层的叶子节点对应路由信息内存中保存的路由表项的索引信息和IP地址区间。路由信息内存中可以保留有适当的空洞，即未使用的内存空间，以方便路由信息的添加和删除等操作，可以实现快速的路由更新。

步骤103：根据关键字中的目的IP地址(即待查找的IP地址)所属的VPN的标识信息，找到对应的索引树，即在VPN索引表中找到该标识对应的索引树的根节点的地址，按照该地址找到索引树。例如，关键字中的目的IP地址为1.1.1.1，其所属的VPN为VPN2，对应了索引树2，则在VPN索引表中找到索引树2的根节点的地址，根据该地址在内存中找到索引树2。

步骤104：在找到的索引树中比对目的IP地址与该索引树的叶子节点保存的IP地址，直到找到关键字即目的IP地址对应的最下层的叶子节点，即从索引树的根节点开始，游历索引树，如果目的IP地址小于当前节点保存的IP地址，则在该节点的左子树中继续查找，如果目的IP地址大于或等于当前节点保存的IP地址，则在该节点的右子树中继续查找，直到找到关键字对应的最下层的叶子节点。

步骤105：在上述预先存储的VPN的IP地址区间和索引信息中，获取找到的最下层叶子节点对应的块，即读取该最下层叶子节点在记录表中对应的块。

步骤106：在得到的块内获取关键字中的目的IP地址所属的IP地址区间，并根据该IP地址区间对应的索引信息，找到该索引信息对应的路由表项，即得到了关键字对应的VPN的路由表项，完成路由查找。

其中，可以使用逻辑选择器在得到的块中进行选择，选择的IP地址区间即该块内的一个IP地址区间，该IP地址区间对应的索引即待查找的索引，根据该索引可以找到目的IP地址对应的路由表项。例如，参见图4，目的IP地址为VPNk的路由表项的IP地址，根据VPNk的ID找到索引树k，游历该索引树，直到找到最下层的叶子节点，该叶子节点对应了记录表中的一个块，在该块内获取目的IP地址所属的IP地址区间，并读取该IP地址区间对应的索引信息，根据该索引信息找到相应的路由表项，完成路由查找。

本实施例可以使用低主频的芯片来实现高速的路由查找、以及实现快速的路由信息更新。

进一步地，当VPN信息发生变化时，上述方法还可以包括更新的步骤：

1)当在已有的VPN中删除路由表项时，在预先存储的IP地址区间和对应的索引信息中删除该路由表项对应的IP地址区间和索引信息，若删除后该路由表项所属的块中无内容，则在索引树中删除该块对应的最下层叶子节点。

2)当在已有的VPN中增加路由表项时，在预先存储的IP地址区间和对应的索引信息中已有的块中增加该路由表项对应的IP地址区间和索引信息；或者在预先存储的IP地址区间和对应的索引信息中增加新块，在新块中存储该路由表项对应的IP地址区间和索引信息，并在索引树中增加该新块对应的最下层叶子节点。

3)当增加新VPN时，在预先存储的IP地址区间和对应的索引信息中增加至少一个新块，将新VPN的所有路由表项对应的IP地址区间和索引信息存储在新块中，并为新VPN建立一棵新的索引树，新的索引树的最下层叶子节点对应上述新块，并将新索引树的信息写入相应的索引树内存中，进一步地，还可以在VPN索引表中保存新增的VPN的标识信息(如ID)以及对应的新索引树的根节点的地址。

例如，参见图5，已有VPNi和VPNj等等，在VPN索引表中保存有相应的ID、索引树高度、指针等信息，当新增VPNk时，建立新的索引树k，写入索引树内存中，并在VPN索引表中增加新的记录，VPNk的ID、索引树k的高度和指针k，指针k指向内存中索引树k的起始地址。新增的索引树k与相邻的索引树j之间可以保留有空闲区，该空闲区的起始地址是上一个索引树j的起始地址加上索引树j的内存耗用，该空闲区的容量是下一个索引树k的起始地址减去该空闲区的起始地址。

本实施例通过建立索引树和预存VPN的IP地址区间和索引信息，来查找关键字对应的IP地址区间及其对应的索引，从而获取相应的路由表项，实现了VPN路由的查找，且提高了查找的效率。采用记录表存储IP地址区间和索引信息，与现有技术为每个VPN建立一个路由查找表相比，极大地节省了空间资源，提高了空间利用率。为每个VPN建立一棵索引树，提高了路由查找的速度。最下层叶子节点对应保存IP地址区间和索引信息的块，降低了索引树的高度，提高了路由查找的速度。保存IP地址区间和索引信息而不是VPN路由表项，可以进一步提高路由查找的速度。采用索引树与记录表的分层的查找结构，可以很方便地采用FPGA或者ASIC实现，设计和实现的复杂度较低，且可以灵活地支持很多个VPN。使用低主频的芯片可以实现高速的路由查找、以及实现快速的路由表更新。通过更新IP地址区间和索引信息，以及相应的索引树信息，使路由查找在更新后的信息中进行，可以进一步提高查找的准确性。

实施例2

本实施例以给所有VPN共同建立一棵索引树为例进行说明，在本实施例中关键字包括目的IP地址和VPN的标识信息。参见图6，本发明实施例提供了一种虚拟私用网路由查找的方法，具体包括以下步骤：

步骤201：预先存储VPN的IP地址区间和索引信息，可以采用记录表的形式，将VPN的IP地址区间和索引信息保存在一个记录表中。也可以保存在两个记录表中，并建立IP地址区间和索引信息的一一对应关系。

步骤202：预先为所有VPN共同建立一棵索引树，该索引树中的叶子节点保存有VPN的IP地址和VPN的标识信息，如叶子节点保存有VPN ID和VPN路由表项的IP地址，且索引树的最下层的叶子节点对应了记录表的一个块。本实施例中的索引树的类型以及叶子节点的排列顺序与实施例1中的相同，此处不再赘述。

例如，参见图7，为所有VPN建立一棵索引树，索引树的最下层的每个叶子节点对应记录表中的一个块，该块内有多个连续的元素，每个元素保存有IP地址区间和索引信息。

步骤203：在索引树中比对关键字中的VPN标识信息和目的IP地址与索引树上的叶子节点保存的标识信息和IP地址，直到找到关键字对应的最下层的叶子节点，即从索引树的根节点开始，游历索引树，一直找到关键字对应的最下层叶子节点。

步骤204：在上述预先存储的VPN的IP地址区间和索引信息中，获取该最下层叶子节点对应的块，即读取最下层叶子节点在记录表中对应的块。

例如，参见图8，关键字包括VPNk的ID和目的IP地址，该目的IP地址为VPNk的路由表项的IP地址，根据关键字游历索引树，直到找到关键字对应的最下层的叶子节点，读取该叶子节点对应的记录表中的一个块，通过逻辑选择器在该块内获取关键字中的目的IP地址所属的IP地址区间，并读取该IP地址区间对应的索引信息。

步骤205：在上述块内获取关键字中的目的IP地址所属的IP地址区间，并根据该IP地址区间对应的索引信息，找到该索引信息对应的路由表项，即得到了关键字对应的VPN的路由表项，完成路由查找。

本实施例可以使用低主频的芯片来实现高速的路由查找、以及实现快速的路由信息更新。

进一步地，当VPN信息发生变化时，上述方法还可以包括更新的步骤，包括在已有的VPN中添加新的路由表项或删除已有的路由表项时的更新，以及增加新的VPN时的更新。其中，在已有的VPN中添加或删除的更新具体过程同实施例1中的描述，此处不再赘述。增加新的VPN时，更新过程具体包括：在预先存储的IP地址区间和对应的索引信息中增加至少一个新块，将新VPN的所有路由表项对应的IP地址区间和索引信息存储在新块中，并在已有的索引树中增加与新VPN相应的叶子节点，并将新增的叶子节点的信息写入相应的索引树内存中。

本实施例通过建立索引树和预存VPN的IP地址区间和索引信息，来查找关键字对应的IP地址区间及其对应的索引，从而获取相应的路由表项，实现了VPN路由的查找，且提高了查找的效率。采用记录表存储IP地址和索引信息，与现有技术为每个VPN建立一个路由查找表相比，极大地节省了空间资源，提高了空间利用率。最下层叶子节点对应保存IP地址区间和索引信息的块，降低了索引树的高度，提高了路由查找的速度。保存IP地址区间和索引信息而不是VPN路由表项，可以进一步提高路由查找的速度。采用索引树与记录表的分层的查找结构，可以很方便地采用FPGA或者ASIC实现，设计和实现的复杂度较低，且可以灵活地支持很多个VPN。使用低主频的芯片可以实现高速的路由查找、以及实现快速的路由表更新。通过更新IP地址区间和索引信息，以及相应的索引树信息，使路由查找在更新后的信息中进行，可以进一步提高查找的准确性。

实施例3

参见图9，本发明实施例还提供了一种虚拟私用网路由查找的装置，具体包括：

查找模块，用于在预先建立的索引树中查找关键字对应的最下层的叶子节点；

获取模块，用于在预先存储的虚拟私用网的IP地址区间和对应的索引信息中，获取查找模块找到的叶子节点对应的块，该块包括一个或多个连续的IP地址区间和相应的索引信息，在该块内获取关键字所属的IP地址区间，根据该IP地址区间对应的索引信息找到该索引信息对应的路由表项。

其中，查找模块可以具体包括：

建立单元，用于预先建立一棵索引树，索引树的叶子节点保存有虚拟私用网的标识信息和IP地址；

查找单元，用于在建立单元建立的索引树中比对关键字中的虚拟私用网的标识信息和目的IP地址与索引树的叶子节点保存的标识信息和IP地址，直到找到关键字对应的最下层的叶子节点。

另外，查找模块还可以具体包括：

建立单元，用于预先为每个虚拟私用网建立一棵索引树，索引树的叶子节点保存有虚拟私用网的IP地址；

查找单元，用于在所示建立单元建立的索引树中，根据关键字中的目的IP地址所属的虚拟私用网的标识信息找到对应的索引树，在找到的索引树中比对目的IP地址与索引树的叶子节点保存的IP地址，直到找到关键字对应的最下层的叶子节点。

进一步地，上述装置还可以包括：

删除更新模块，用于当在虚拟私用网中删除路由表项时，在预先存储的IP地址区间和对应的索引信息中删除该路由表项对应的IP地址区间和索引信息，若删除后路由表项所属的块中无内容，则在索引树中删除该块对应的最下层叶子节点。

进一步地，上述装置还可以包括：

增加表项更新模块，用于当在虚拟私用网中增加路由表项时，在预先存储的IP地址区间和对应的索引信息中已有的块中增加该路由表项对应的IP地址区间和索引信息；或者在预先存储的IP地址区间和对应的索引信息中增加新块，在新块中存储该路由表项对应的IP地址区间和索引信息，并在索引树中增加该新块对应的最下层叶子节点。

进一步地，上述装置还可以包括：

增加虚拟私用网更新模块，用于当增加新虚拟私用网时，在预先存储的IP地址区间和对应的索引信息中增加至少一个新块，将新虚拟私用网的所有路由表项对应的IP地址区间和索引信息存储在新块中，并在索引树中增加与新虚拟私用网相应的叶子节点或为新虚拟私用网建立一棵新的索引树。

本实施例通过建立索引树和预存VPN的IP地址区间和索引信息，来查找关键字对应的IP地址区间及其对应的索引，从而获取相应的路由表项，实现了VPN路由的查找，且提高了查找的效率。采用记录表存储IP地址和索引信息，与现有技术为每个VPN建立一个路由查找表相比，极大地节省了空间资源，提高了空间利用率。采用为每个VPN建立一棵索引树的方式，提高了路由查找的速度。最下层叶子节点对应保存IP地址区间和索引信息的块，降低了索引树的高度，提高了路由查找的速度。保存IP地址区间和索引信息而不是VPN路由表项，可以进一步提高路由查找的速度。采用索引树与记录表的分层的查找结构，可以很方便地采用FPGA或者ASIC实现，设计和实现的复杂度较低，且可以灵活地支持很多个VPN。使用低主频的芯片可以实现高速的路由查找、以及实现快速的路由表更新。通过更新IP地址区间和索引信息，以及相应的索引树信息，使路由查找在更新后的信息中进行，可以进一步提高查找的准确性。

本发明实施例可以利用软件实现，相应的软件可以存储在可读取的存储介质中，如计算机的硬盘、内存或光盘中。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (12)

1.一种虚拟私用网路由查找的方法，其特征在于，所述方法包括：

在预先建立的索引树中，根据虚拟私用网的标识信息查找关键字对应的最下层的叶子节点；

在预先存储的虚拟私用网的IP地址区间和对应的索引信息中，获取所述叶子节点对应的块，所述块包括一个或多个连续的IP地址区间和相应的索引信息；

在所述块内获取所述关键字所属的IP地址区间；

根据所述IP地址区间对应的索引信息，找到所述索引信息对应的路由表项。

2.根据权利要求1所述的虚拟私用网路由查找的方法，其特征在于，所述在预先建立的索引树中，根据虚拟私用网的标识信息查找关键字对应的最下层的叶子节点，具体包括：

预先建立一棵索引树，所述索引树的叶子节点保存有虚拟私用网的标识信息和IP地址；

在所述索引树中比对关键字中的虚拟私用网的标识信息和目的IP地址与所述索引树的叶子节点保存的标识信息和IP地址，直到找到所述关键字对应的最下层的叶子节点。

3.根据权利要求1所述的虚拟私用网路由查找的方法，其特征在于，所述在预先建立的索引树中，根据虚拟私用网的标识信息查找关键字对应的最下层的叶子节点，具体包括：

预先为每个虚拟私用网建立一棵索引树，所述索引树的叶子节点保存有虚拟私用网的IP地址；

根据关键字中的目的IP地址所属的虚拟私用网的标识信息找到对应的索引树；

在所述索引树中比对所述目的IP地址与所述索引树的叶子节点保存的IP地址，直到找到所述关键字对应的最下层的叶子节点。

4.根据权利要求1所述的虚拟私用网路由查找的方法，其特征在于，所述方法还包括：

当在所述虚拟私用网中删除路由表项时，在所述预先存储的IP地址区间和对应的索引信息中删除该路由表项对应的IP地址区间和索引信息，若删除后所述路由表项所属的块中无内容，则在所述索引树中删除该块对应的最下层叶子节点。

5.根据权利要求1所述的虚拟私用网路由查找的方法，其特征在于，所述方法还包括：

当在所述虚拟私用网中增加路由表项时，在所述预先存储的IP地址区间和对应的索引信息中已有的块中增加该路由表项对应的IP地址区间和索引信息；或者在所述预先存储的IP地址区间和对应的索引信息中增加新块，在所述新块中存储该路由表项对应的IP地址区间和索引信息，并在所述索引树中增加所述新块对应的最下层叶子节点。

6.根据权利要求1所述的虚拟私用网路由查找的方法，其特征在于，所述方法还包括：

当增加新虚拟私用网时，在所述预先存储的IP地址区间和对应的索引信息中增加至少一个新块，将所述新虚拟私用网的所有路由表项对应的IP地址区间和索引信息存储在所述新块中，并在所述索引树中增加与所述新虚拟私用网相应的叶子节点或为所述新虚拟私用网建立一棵新的索引树。

7.一种虚拟私用网路由查找的装置，其特征在于，所述装置包括：

查找模块，用于在预先建立的索引树中，根据虚拟私用网的标识信息查找关键字对应的最下层的叶子节点；

获取模块，用于在预先存储的虚拟私用网的IP地址区间和对应的索引信息中，获取所述查找模块找到的叶子节点对应的块，所述块包括一个或多个连续的IP地址区间和相应的索引信息，在所述块内获取所述关键字所属的IP地址区间，根据所述IP地址区间对应的索引信息找到该索引信息对应的路由表项。

8.根据权利要求7所述的虚拟私用网路由查找的装置，其特征在于，所述查找模块具体包括：

建立单元，用于预先建立一棵索引树，所述索引树的叶子节点保存有虚拟私用网的标识信息和IP地址；

查找单元，用于在所述建立单元建立的索引树中比对关键字中的虚拟私用网的标识信息和目的IP地址与所述索引树的叶子节点保存的标识信息和IP地址，直到找到所述关键字对应的最下层的叶子节点。

9.根据权利要求7所述的虚拟私用网路由查找的装置，其特征在于，所述查找模块具体包括：

建立单元，用于预先为每个虚拟私用网建立一棵索引树，所述索引树的叶子节点保存有虚拟私用网的IP地址；

查找单元，用于在所述建立单元建立的索引树中，根据关键字中的目的IP地址所属的虚拟私用网的标识信息找到对应的索引树，在所述索引树中比对所述目的IP地址与所述索引树的叶子节点保存的IP地址，直到找到所述关键字对应的最下层的叶子节点。

10.根据权利要求7所述的虚拟私用网路由查找的装置，其特征在于，所述装置还包括：

删除更新模块，用于当在所述虚拟私用网中删除路由表项时，在所述预先存储的IP地址区间和对应的索引信息中删除该路由表项对应的IP地址区间和索引信息，若删除后所述路由表项所属的块中无内容，则在所述索引树中删除该块对应的最下层叶子节点。

11.根据权利要求7所述的虚拟私用网路由查找的装置，其特征在于，所述装置还包括：

增加表项更新模块，用于当在所述虚拟私用网中增加路由表项时，在所述预先存储的IP地址区间和对应的索引信息中已有的块中增加该路由表项对应的IP地址区间和索引信息；或者在所述预先存储的IP地址区间和对应的索引信息中增加新块，在所述新块中存储该路由表项对应的IP地址区间和索引信息，并在所述索引树中增加所述新块对应的最下层叶子节点。

12.根据权利要求7所述的虚拟私用网路由查找的装置，其特征在于，所述装置还包括：

增加虚拟私用网更新模块，用于当增加新虚拟私用网时，在所述预先存储的IP地址区间和对应的索引信息中增加至少一个新块，将所述新虚拟私用网的所有路由表项对应的IP地址区间和索引信息存储在所述新块中，并在所述索引树中增加与所述新虚拟私用网相应的叶子节点或为所述新虚拟私用网建立一棵新的索引树。

Images