CN102404198B - 用于控制对路由数据的通告的方法和设备 - Google Patents

Abstract

提供了用于控制向邻居路由器通告路由数据的方法。维护(301)前缀的列表，以及使每一个前缀与包含用于邻居路由器中的每一个的数据项的自身指示符向量相关联(302)，使得数据项指示(304)是否要向所涉及的邻居路由器通告所涉及的前缀。对于每一个邻居路由器，存在(303)处理指针，其指向与和该邻居路由器有关的通告过程的状态相关的前缀，以及随着向该邻居路由器通告前缀，处理指针在前缀的列表上向前移动。由于不需要对于每一个邻居路由器分别维护自身的前缀的列表，而仅维护指示符向量中的邻居路由器特定的条目，所以可以实现所需存储器空间的节省。

Description

用于控制对路由数据的通告的方法和设备

技术领域

本发明涉及用于在数据传输网络中控制从路由器向其它路由器通告路由数据的方法和设备。此外，本发明涉及用于在数据传输网络中控制从路由器向其它路由器通告路由数据的计算机程序。此外，本发明涉及能够向其它路由器通告路由数据的路由器。

背景技术

路由协议是指定路由器如何相互通信来分发使其能够在数据传输网络中选择路由的信息的协议。每一个路由器仅具有直接附接至其的数据传输网络的区域的先验知识。路由协议首先在最接近的邻居路由器当中通告该信息，并且然后遍及数据传输网络。通过这种方式，路由器获得数据传输网络的拓扑的知识。例如，在边界网关协议(“BGP”)下，在路由器处从其邻居路由器接收到的前缀和其相关属性被首先组织成传入信息的邻接路由信息库“Adj_Rib_In”。该信息库然后被删余(bepruned)，使得例如不必要的重复被移除。该结果构成本地信息库“Loc_Rib”。根据适当策略，向邻居路由器通告在Loc_Rib中包含的前缀和其相关属性，以便使邻居路由器意识到经由考虑的路由器可访问的网络区域，即，与前缀相对应的子网络。传统上，执行对邻居路由器的通告，使得对于每一个邻居路由器创建传出信息的邻接路由信息库“Adj_Rib_Out”。每一个Adj_Rib_Out逻辑上是要向与该特定Adj_Rib_Out有关的邻居路由器通告的前缀和其相关属性表。例如，Adj_Rib_Out可以是链接列表，其中在构成Adj_Rib_Out的列表上，每一个前缀与指向下一前缀的正向指针和指向前一前缀的反向指针相关联。对于每一个邻居路由器构造Adj_Rib_Out，使得适于该邻居路由器的策略被应用于在Loc_Rib中包含的前缀和其相关属性。对于每一个邻居路由器，通告过程沿着与该邻居路由器有关的Adj_Rib_Out前进，使得仍然要被通告的那些前缀和其相关联的属性被发送给考虑中的邻居路由器。与在此简短描述的通告过程相关联的问题是：当数据传输网络的大小增长时，Adj_Rib_Out所需的总存储器空间增长非常强劲。这是由于以下事实：当数据传输网络的大小增长时，Adj_Rib_Out的数量和每一个Adj_Rib_Out中的条目的数量两者均增加，并且因此存储器消耗与这些两个数量的乘积成比例。因此，可缩放性是有限的。

发明内容

下面呈现了简化的发明内容，以便提供对各种发明实施例的一些方面的基本理解。本发明内容并不是本发明的穷尽概述。其并不意在识别本发明的关键性或决定性元素，也不意在详述本发明的范围。作为本发明的示例性实施例的更加详细的描述的前序，下面的发明内容仅仅以简化的形式呈现本发明的一些概念。

根据本发明的第一方面，提供了用于控制从第一路由器向第二路由器通告路由数据的新的方法，路由数据包括与经由第一路由器可访问的数据传输网络的区域有关的前缀。该方法包括：

-维护前缀的主要列表，使得在主要列表上，每一个前缀具有前任(predecessor)和/或继任(successor)，

-维护指示符向量，使得前缀中的每一个与指示符向量中的一个相关联，每一个指示符向量包含用于第二路由器中的每一个的数据项，以及该指示符向量的每一个数据项指示是否要向与该数据项相关联的第二路由器通告与该指示符向量相关联的前缀，

-对于第二路由器中的每一个，维护指向所述前缀中的特定一个前缀的主要处理指针，所述特定一个前缀与和该第二路由器有关的通告过程的主导状态相关，当向与主要处理指针相关联的第二路由器通告前缀时，所述主要处理指针在前缀主要列表上向前移动，以及

-关于每一个第二路由器，基于与对应于和该第二路由器有关的主要处理指针的位置的前缀相关联的指示符向量，确定是否需要向该第二路由器通告该前缀。

例如，与前缀有关的指示符向量可以是比特(bit)映射，其例如具有用于第二路由器中的每一个的下面两比特数据项：第一比特，用于指示是否要向所涉及的第二路由器通告前缀以及还可能其属性；以及第二比特，用于指示是否已经向所述第二路由器通告了所述前缀以及还可能其属性。因此，对于所有第二路由器的通告过程可以使用同一前缀主要列表。由于不需要对于第二路由器中的每一个分别维护自身的前缀列表，而仅仅维护指示符向量中的第二路由器特定的条目，所以所需要的存储器空间比与在本文档中的背景技术部分中描述的传统方法结合所需的存储器空间显著更小。

结合IPv4(网际协议版本4)和IPv6(网际协议版本6)，典型地，前缀被定义为地址和网络掩码的长度。在VPN(虚拟专用网)的情况下，前缀可以进一步包括路由标识符(“RD”)。结合BGP(边界网关协议)，前缀可以被看作唯一识别与经由考虑的路由器可访问的设备或网络区域有关的路由信息的密钥。

根据本发明的第二方面，提供了用于控制从第一路由器向第二路由器通告路由数据的新的设备，路由数据包括与经由第一路由器可访问的数据传输网络的区域有关的前缀。该设备包括处理器，其被布置成：

-维护前缀的主要列表，使得在主要列表上，每一个前缀具有前任和/或继任，

-维护指示符向量，使得前缀中的每一个与指示符向量中的一个相关联，每一个指示符向量包含用于第二路由器中的每一个的数据项，以及该指示符向量的每一个数据项指示是否要向与该数据项相关联的第二路由器通告与该指示符向量相关联的前缀，

-对于第二路由器中的每一个，维护指向前缀中的特定一个前缀的主要处理指针，所述特定一个前缀与和该第二路由器有关的通告过程的主导状态相关，当向与主要处理指针相关联的第二路由器通告前缀时，所述主要处理指针在前缀的主要列表上向前移动，以及

-关于每一个第二路由器，基于与对应于和该第二路由器有关的主要处理指针的位置的前缀相关联的指示符向量，确定是否需要向该第二路由器通告该前缀。

根据本发明的第三方面，提供了新的路由器，其包括：

-用于连接到数据传输链路的数据传输端口，

-用于支持路由协议的处理系统，以及

-根据本发明的、用于控制从路由器向其它路由器通告路由数据的设备，路由数据与路由协议有关，并且包括与经由路由器可访问的数据传输网络的区域有关的前缀，

其中，处理系统被布置成：作为对设备已经确定需要向这些其它路由器通告这些前缀的情况的响应，向其它路由器中的一个或多个通告前缀中的一个或多个。

根据本发明的第四方面，提供了用于控制从第一路由器向第二路由器通告路由数据的新的计算机程序，路由数据包括与经由第一路由器可访问的数据传输网络的区域有关的前缀。该计算机程序包括计算机可执行的指令，所述计算机可执行的指令用于控制可编程处理器用于：

-维护前缀的主要列表，使得在主要列表上，每一个前缀具有前任和/或继任，

-维护指示符向量，使得前缀中的每一个与指示符向量中的一个相关联，每一个指示符向量包含用于第二路由器中的每一个的数据项，以及该指示符向量的每一个数据项指示是否要向与该数据项相关联的第二路由器通告与该指示符向量相关联的前缀，

-对于第二路由器中的每一个，维护指向前缀中的特定一个前缀的主要处理指针，所述特定一个前缀与和该第二路由器有关的通告过程的主导状态相关，当向与主要处理指针相关联的第二路由器通告前缀时，所述主要处理指针在前缀的主要列表上向前移动，以及

-关于每一个第二路由器，基于与对应于和该第二路由器有关的主要处理指针的位置的前缀相关联的指示符向量，确定是否需要向该第二路由器通告该前缀。

根据本发明的第五方面，提供了一种新的计算机程序产品。该计算机程序产品包括编码有根据本发明的计算机程序的非易失性计算机可读介质，例如光盘(“CD”)。

在所附从属权利要求中描述了本发明的多个示例性实施例。

就构造和操作方法两者而言，当结合附图阅读时，从下面的具体示例性实施例的描述将最佳地理解本发明的各种示例性实施例，以及其附加目的和优点。

动词“包括”在本文档中用作开放式限制，其既不排除也不要求另外未记载的特征的存在。除非另外明确说明，在从属权利要求中记载的特征可相互自由组合。

附图说明

在下面参考附图更加详细地解释了本发明的示例性实施例和其优点，在附图中：

图1示出了根据本发明的实施例的包括路由器的示例性数据传输网络的示意图示，

图2示出了在根据本发明的实施例的用于在数据传输网络中控制从路由器向其它路由器通告路由数据的方法中使用的示例性数据结构的示意图示，以及

图3示出了根据本发明的实施例的用于在数据传输网络中控制从路由器向其它路由器通告路由数据的方法的流程图。

具体实施方式

图1示出了根据本发明的实施例的包括路由器101的示例性数据传输网络的示意图示。数据传输网络可以例如但不一定是因特网，以及部分121可以表示因特网的自治系统(“AS”)，以及部分122可以表示因特网的其余部分。数据传输网络也可以是不与公共因特网连接的孤立网络。数据传输网络的部分121包括路由器101，以及还包括路由器102、103、104、105和106。这些路由器与物理数据传输链路110、111、112、113、114和115互连，其每一个是电缆或光缆或无线电链路，以及路由器优选地被布置成支持网际协议。此外，例如，路由器可以被布置成支持多协议标签交换(“MPLS”)。如图1中所示，终端设备107和108可以连接到数据传输网络。除路由器101-106之外，数据传输网络的部分121可以包括在图1中未示出的其它路由器和网络设备，和/或部分121可以连接到在图1中未示出的终端设备。这在图1中用绘制为虚线继续的数据传输链路图示，诸如数据传输链路116。

路由器101-106中的每一个包括用于连接到数据传输链路的数据传输端口，以及用于支持一个或多个路由协议的处理系统，所述一个或多个路由协议首先在最接近的邻居路由器之间通告路由数据，并且然后遍及数据传输网络。路由数据包括与经由考虑的路由器可访问的数据传输网络的区域(即子网络)有关的前缀。因此，路由器获得数据传输网络的拓扑的知识。在不失一般性的情况下，我们可以聚焦于考虑路由器101。路由器101包括设备117，其用于控制从路由器101向其邻居路由器102和103，以及同样向其在数据传输网络的部分122中的邻居路由器通告路由数据。应当注意到，结合某些路由协议，术语“邻居路由器”并不限于仅仅是指在其之间只有一个跃距(hop)的“最接近的邻居路由器”，而在邻居之间可以有更多跃距。因此，结合某些路由协议，路由器101还可以向路由器104-106通告路由数据，即，路由器101可以向其它路由器102-106通告路由数据。路由器101的处理系统被布置成：作为对设备117已经确定需要向这些邻居路由器通告这些前缀的情况的响应，向邻居路由器中的一个或多个通告前缀中的一个或多个。路由器101可以被布置成例如：支持用于与数据传输网络的部分122协作的外部边界网关协议(eBGP)，在这种情况下，路由数据包括外部边界网关协议的路由数据；以及支持用于在数据传输网络的部分121内部操作的内部边界网关协议(iBGP)，在这种情况下，路由数据包括内部边界网关协议的路由数据。在iBGP的情况下，路由器101可以不仅向其最接近的邻居路由器102和103，而且向是在两个跃距后的邻居的路由器104-106通告路由数据。

用于控制从路由器110向其邻居路由器通告路由数据的设备117包括处理器，其被布置成：维护前缀的主要列表，使得在主要列表上，每一个前缀具有前任和/或继任。例如，主要列表可以是链接列表，其中每一个前缀与指向在主要列表中为下一个的继任前缀的正向指针和指向在主要列表中为前一个的前任前缀的反向指针相关联。设备117的处理器被布置成：维护指示符向量，使得前缀中的每一个与指示符向量中的一个相关联。每一个指示符向量包含数据项，使得对于邻居路由器中的每一个存在数据项，以及每一个数据项指示是否要向与考虑的数据项相关联的邻居路由器通告与考虑的指示符向量相关联的前缀。可以基于例如与前缀有关的属性来构造指示符向量。设备117的处理器被布置成：对于邻居路由器中的每一个维护指向前缀中的特定一个前缀的主要处理指针，所述特定一个前缀与和该邻居路由器有关的通告过程的主导状态相关。随着向与该主要处理指针相关联的邻居路由器通告前缀，每一个主要处理指针在前缀的主要列表上向前移动。关于每一个主要处理指针，设备117的处理器被布置成：基于与对应于该主要处理指针的位置的前缀相关联的指示符向量，确定是否需要向与该主要处理指针有关的邻居路由器通告该前缀。例如，指示符向量中的每一个数据项可以包括：第一变量，其用于指示与该指示符向量有关的前缀是否是要向与该数据项有关的邻居路由器通告的前缀；以及第二变量，其用于指示是否已经向与该数据项有关的邻居路由器通告了与该指示符向量有关的前缀。第一变量可以是单个比特，以及因此，第二变量也可以是单个比特。例如，设备117的处理器可以被布置成：作为对第一变量指示与主要处理指针的位置相对应的前缀是要向该邻居路由器通告的前缀以及第二变量指示尚未向该邻居路由器通告该前缀的情况的响应，确定需要向对应的邻居路由器通告该前缀。优选地，该处理器进一步被布置成：将该确定的结果递送给被布置成运行路由协议的处理系统。在递送该结果之后，第二变量可以被设置成指示已经向考虑的邻居路由器通告了考虑的前缀，或已排序(order)要向考虑的邻居路由器通告考虑的前缀。设备117的处理器可以用一个或多个处理器单元来实现，其每一个可以是提供有适当软件的可编程处理器单元。此外，一个或多个相同处理器单元可以用于实现设备117和被布置成运行路由协议的处理系统两者。

图2示出了可以用于在图1中所示的数据传输网络中控制从路由器101向其邻居路由器通告路由数据的示例性数据结构的示意图示。每一个前缀与包含前缀特定的指示符向量V和指针数据Ptd的数据字段相关联。借助于指针数据，将前缀的主要列表作为链接列表维护。在图2中，V(1)是前缀1的指示符向量以及Ptd(1)是前缀1的指针数据，V(2)和Ptd(2)是前缀2的指示符向量和指针数据，…，以及V(n)和Ptd(n)是前缀n的指示符向量和指针数据。每一个指针数据Ptd(i)，其中i＝1,2，…，n，可以包含例如下述数据：

Ptd_Pr(i)＝指向包含前缀i和其属性的存储器区域的指针，

Ptd_F(i)＝指向包含主要列表上的下一前缀的指针数据Ptd(i+1)的存储器区域的正向指针，如果前缀i是主要列表上的最后一个，则该指针是空指针，以及

Ptd_B(i)＝指向包含主要列表上的前一前缀的指针数据Ptd(i–1)的存储器区域的反向指针，如果前缀i是主要列表上的第一个，则该指针是空指针。

每一个指示符向量V(i)，其中i＝1,2,…n，包含用于每一个邻居路由器NR(j)，其中j＝1,2,…,m的数据项V(i,j)。例如，邻居路由器NR(1)可以是图1中所示的路由器102，以及邻居路由器NR(2)可以是图1中所示的路由器103，以及邻居路由器NR(3),…,以及NR(m)可以是图1中所示的数据传输网络的部分122中的路由器。数据项V(i,j)例如可以包含：第一比特，其指示是否要向邻居路由器j通告前缀i；以及第二比特，其指示是否已经向邻居路由器NR(j)通告了前缀i、或排序要向邻居路由器NR(j)通告前缀i。

对于邻居路由器NR(j)，其中j＝1,2,…,m，中的每一个，存在主要处理指针HP(j)，主要处理指针HP(j)指向与和邻居路由器NR(j)有关的通告过程的主导状态相关的前缀。例如，在图2中所示的示例性情况下，邻居路由器NR(1)的主要处理指针HP(1)通过指向前缀2的指针数据Ptd(2)来指向前缀2。当与邻居路由器NR(1)有关的通告过程进行时，主要处理指针HP(1)被移位到指向前缀3的指针数据Ptd(3)。因此，随着向邻居路由器NR(1)通告前缀，主要处理指针HP(1)在前缀的主要列表上向前移动，即在图2中向下移动。主要处理指针HP(j)，其中j＝1,2,…,m，可以被布置成例如指向最后向适当邻居路由器通告的前缀，或又例如，其可以被布置成指向当前处于确定中的前缀，所述确定涉及需要向其通告该前缀的邻居路由器，如果存在的话。例如，关于主要处理指针HP(1)，可能的是，前缀2是最后向适当邻居路由器，如果存在的话，通告的前缀，以及前缀3当前处于确定中，所述确定涉及应当向其通告前缀3的邻居路由器，如果存在的话。同样可能的是，前缀2当前处于确定中，所述确定涉及应当向其通告前缀2的邻居路由器，如果存在的话。原则上，在主要处理指针和处于上述确定中的前缀之间，任何预定的偏移是可能的。在不失一般性的情况下，我们可以聚焦于下述情况：主要处理指针指向每次处于上述确定中的前缀。例如，在图2中所示的情况下，基于数据项V(3,2)，处于确定中的是：是否需要向邻居路由器NR(2)通告前缀3。

在根据本发明的一个实施例的用于控制通告路由数据的设备中，该设备的处理器被布置成：维护一个或多个相似性列表，使得每一个相似性列表包含前缀，所述前缀的属性基于预定的准则是相似的。属性可以例如但不一定指示路由的AS路径(自治系统)、下一跃距、源、路由目标、识别VPN资格(虚拟专用网)的扩展社区、和/或与由考虑的前缀表示的子网有关或与经由考虑的路由器到该子网的路由有关的其它问题。通过相互比较前缀的对应属性或通过将适当的哈希函数用于分类，前缀可以被分类为相似性列表。设备的处理器被布置成：作为对需要向对应的邻居路由器通告与主要处理指针的位置相对应的前缀的情况的响应，以及基于指示符向量，确定是否需要向对应的邻居路由器通告在包含与主要处理指针的位置相对应的前缀的相似性列表上的其它前缀中的一个或多个。

参考图2，例如，可以如下所述来实现上述相似性列表和与其有关的操作。

每一个指针数据Ptd(i)，其中i＝1,2,…,n，例如可以进一步包含下列数据：

Ptd_S(i)＝指向包含前缀k的指针数据Ptd(k)的存储器区域的相似性指针，所述前缀K具有与前缀i相似的属性，并且在主要列表上前缀i之后是最接近的，即k＝min{l,l>i以及具有与前缀i相似的属性的前缀l}，如果前缀l是相似性列表上的最后一个，则该指针是空指针。

因此，每一个相似性列表是链接列表，使得该相似性列表上的每一个前缀与指向该相似性列表上的下一前缀的指针相关联。为了说明起见，我们考虑邻居路由器NR(3)。主要处理指针HP(3)指向前缀2的指针数据Ptd(2)。数据项V(2,3)指示是否需要向邻居路由器NR(3)通告前缀2以及可能其属性。如果需要向邻居路由器NR(3)通告前缀2，则我们检查相似性指针Ptd_S(2)是否指向任何其他前缀的指针数据或Ptd_S(2)是否是空指针。现在我们假设Ptd_S(2)指向前缀k1的指针数据，即，前缀k1属于与前缀2相同的相似性列表。我们从数据项V(k1,3)检查是否需要向邻居路由器NR(3)通告前缀k1。此后，我们从前缀k1的指针数据Ptd(k1)检查Ptd_S(k1)是否指向任何其他前缀的指针数据或Ptd_S(k1)是否是空指针。现在我们假设Ptd_S(k1)指向前缀k2的指针数据，即，前缀k2属于与前缀2和前缀k1相同的相似性列表。我们从数据项V(k2,3)检查是否需要向邻居路由器NR(3)通告前缀k2。此后，我们从前缀k2的指针数据Ptd(k2)检查Ptd_S(k2)是否指向任何其他前缀的指针数据或Ptd_S(k2)是否是空指针。如此继续，直到到达具有作为相似性指针的空指针的指针数据，或直到已经找到需要向邻居路由器NR(3)通告的预定数量的前缀。有利地，需要向邻居路由器NR(3)通告的前缀被收集成传送给邻居路由器NR(3)的单个通告消息，即IP分组。对于向邻居路由器NR(3)通告的每一个前缀，数据项V(前缀号,3)被设置成指示已经向邻居路由器NR(3)通告了该前缀。此后，主要处理指针HP(3)被更新成指向前缀3的指针数据Ptd(3)。上述数据项被设置成指示已经向邻居路由器NR(3)通告了上述前缀，以便例如当主要处理指针HP(3)在通告过程的某个阶段到达Ptd(k1)时，避免不必要的重复通告。优选地，通告消息包含仅仅一次对在通告消息中包含的前缀而言相同的属性，以便避免通告消息中的不必要的重复数据。

当借助于相似性指针Ptd_S，以上述方式实现相似性列表时，每一个相似性列表的前缀按照与主要列表上的前缀的相互顺序相对应的相互顺序，并且按照该相互顺序来检查包含与主要处理指针的位置相对应的前缀的相似性列表的前缀。

在根据本发明的实施例的用于控制通告路由数据的设备中，该设备的处理器被布置成：作为对前缀已被认为是需要向邻居路由器通告的前缀的情况的响应，运行特定于该邻居路由器的策略函数，使得该前缀和其属性是该策略函数的输入量。处理器进一步被布置成：基于用策略函数获得的策略结果，允许或不允许向该邻居路由器通告该前缀。策略函数例如可以确定不必向与讨论中的策略函数有关的邻居路由器通告与数据传输网络的某些区域有关的前缀。由于策略函数，不必以相同方式对待在同一相似性列表上出现的所有前缀。当审查相似性列表并且策略函数指示不以与早前从相似性列表中找到前缀的相同的方式来处理考虑的前缀时，该前缀可以被忽视，并且过程可以针对相似性列表上的下一前缀继续或针对该相似性列表的过程可以停止，即，不再从该相似性列表检查前缀。甚至可能的是，策略函数改变前缀的属性。

在根据本发明的实施例的用于控制通告路由数据的设备中，该设备的处理器被布置成：维护策略组，使得每一个策略组包含与同一策略函数有关的这样的邻居路由器。该设备被布置成：关于每一个前缀和每一个策略组，存储与该前缀、其属性以及与该策略组有关的策略函数相对应的策略结果。处理器被布置成：作为对需要向属于该策略组的任何邻居路由器通告该前缀的情况的响应，使用已存储的策略结果，而不是运行策略函数。对于所有策略组或仅仅对于其中邻居路由器的数量超过预定限额的这样的策略组，可以实现对策略结果的上述存储和重用。

参考图2，例如，可以如下所述实现上述策略组和与其有关的操作。

除前缀特定的指示符向量V和前缀特定的指针数据Ptd外，每一个前缀特定的数据字段包含前缀特定的策略结果PR。在图2中所示的示例性情况下，假设存在三个不同的策略函数。第一策略函数与邻居路由器的第一子组有关，第二策略函数与邻居路由器的第二子组有关，以及第三策略函数与邻居路由器的第三子组有关。例如，图2中所示的数据元素PR(2,1)可以表示与前缀2、其属性以及第一策略函数相对应的策略结果，以及因此，例如数据元素PR(n,3)可以表示与前缀n、其属性以及第三策略函数相对应的策略结果。对于每一个邻居路由器NR(1),…,NR(m)，可以有基址指针，借助于该基址指针，可以对于每一个前缀和每一个邻居路由器构造指向相关策略结果的指针P。在图2中，数据元素Bp可以表示基址指针。关于前缀i和邻居路由器j的指针P(i,j)，其中i＝1,2,…,n以及j＝1,2,…,m原则上可以被构造为P(i,j)＝Bp(j)+Ptd(i)的起始地址+预定偏移。还可能的是，每一个前缀特定的数据字段包含指向关于考虑的前缀和其属性的所有或仅仅最大策略组的策略结果的指针。每一个邻居路由器与指示所述指针中的哪一个与该邻居路由器有关的数据相关联。在这种情况下，图2中所示的数据元素PR(i,k)，其中i＝1,…,n以及k＝1,2或3，可以是指向关于每一个前缀1,…,n和其属性的三个最大策略组的策略结果的指针，以及在图2中所示的数据元素Bp(j)，其中j＝1,…,m，可以是指示指针PR(i,1),PR(i,2)和PR(i,3)中的哪一个与邻居路由器j有关的数据。

在根据本发明的实施例的用于控制通告路由数据的设备中，该设备的处理器被布置成：将其主要处理指针指向前缀的主要列表上的同一前缀的邻居路由器相互关联以形成链接列表，并且使用单个指针来表示在链接列表上的所有邻居路由器的主要处理指针。在图2中所示的示例性情况下，邻居路由器NR(1)、NR(3)和NR(m)的主要处理指针HP(1)、HP(3)和HP(m)分别经由指向指针数据Ptd(2)来指向前缀2。因此，这些邻居路由器可以用共同主要处理指针来处理，并且通过将这些邻居路由器组织成与共同主要处理指针有关的链接列表，可以将这些邻居路由器与共同主要处理指针相关联。优选地，邻居路由器的这些链接列表是动态的，因为与不同邻居路由器有关的通告过程可能沿着前缀主要列表以不同的速度进行。

在根据本发明的实施例的用于控制通告路由数据的设备中，该设备的处理器被布置成：将其主要处理指针指向前缀的主要列表上的同一前缀的邻居路由器相互关联以形成链接列表，并且将该前缀与指向该链接列表的列表指针相关联。在图2中所示的示例性情况下，邻居路由器NR(1)、NR(3)和NR(m)的主要处理指针HP(1)、HP(3)和HP(m)分别经由指向指针数据Ptd(2)来指向前缀2。因此，将这些邻居路由器组织成链接列表，并且将前缀2与指向该链接列表的列表指针相关联。仅仅一个共同主要处理指针需要用于控制与NR(1)、NR(3)和NR(m)有关的通告过程，因为在链接列表中给出了与共同主要处理指针有关的邻居路由器。因此，在通告过程中，将邻居路由器NR(1)、NR(3)和NR(m)作为组来处理。

在根据本发明的实施例的用于控制通告路由数据的设备中，该设备的处理器被布置成：作为对已经从邻居路由器中的一个接收到新的前缀和其属性并且该新的前缀不同于前缀的主要列表上的现有前缀中的任何一个的情况的响应，将新的前缀插入前缀的主要列表的末尾，以及基于新的前缀的属性来为新的前缀形成新的指示符向量。在图2中所示的示例性情况下，指针数据Ptd(n+1)包含指向包含新的前缀n+1和其属性的存储器区域的指针Ptd_Pr(n+1)。指针数据Ptd(n)的正向指针Ptd_F(n)是空指针，因为前缀n是主要列表上的最后一个。通过将正向指针Ptd_F(n)设置成指向包含新的前缀的指针数据Ptd(n+1)的存储器区域，通过将指针数据Ptd(n+1)的反向指针设置成指向包含前缀n的指针数据Ptd(n)的存储器区域，并且通过为新的前缀n+1构造指示符向量V(n+1)和还可能策略结果PR(n+1,1),…,PR(n+1,3)，将新的前缀n+1添加到数据结构。指针数据Ptd(n)的正向指针Ptd_F(n)被设置为空指针。

在根据本发明的实施例的用于控制通告路由数据的设备中，该设备的处理器被布置成：作为对已经改变了前缀的属性中的一个或多个的情况的响应，从前缀的主要列表移除该前缀，以及将该前缀插入前缀的主要列表的末尾，以及基于该前缀的属性为该前缀形成新的指示符向量。关于图2中所示的示例性情况，为了说明起见，我们假设已经改变了前缀2的属性，并且因此必须向适当邻居路由器重新通告前缀2和其属性。因此，包含指针数据Ptd(2)、指示符向量V(2)和策略结果PR(2,1),…,PR(2,3)的数据字段从主要列表的其当前位置移除，更新了指示符向量V(2)和与PR(2,1),…,PR(2,3)相对应的策略结果，并且将更新后的数据字段添加到主要列表的末尾。所述移除和添加操作包括下列动作：将正向指针Ptd_F(1)设置成指向Ptd(3)，将反向指针Ptd_B(3)设置成指向Ptd(1)，将反向指针Ptd_B(2)设置成指向Ptd(n)，将正向指针Ptd_F(n)设置成指向Ptd(2)，以及将正向指针Ptd_F(2)设置为空指针。将主要处理指针HP(1)、HP(3)和HP(m)或表示其全部的共同指针更新成指向Ptd(3)。还可能的是，将策略结果设置成非现有状态，以及在通告过程期间构造并且存储更新后的策略结果，而不是在上述前缀更新期间对策略结果进行更新。优选地，每一个前缀特定的数据字段包括指向其主要处理指针指向讨论中的前缀的那些邻居路由器的列表的列表指针。优选地，上述邻居路由器的列表是链接列表。指针数据Ptd(2)可以包含指向列表的列表指针，该列表指示其主要处理指针指向Ptd(2)的邻居路由器是NR(1)、NR(3)、和NR(m)。因此，简单明了的是，找出必须被更新成指向Ptd(3)的主要处理指针，以及不需要检查所有主要处理指针来找到必须被更新成指向Ptd(3)的那些。

应当注意到，图2中所示的数据结构不是唯一可能的替代。例如，如果没有使用相似性列表，则可以使数据结构简化，使得每一个数据项V(i,j)，其中i＝1,2,…,n以及j＝1,2,…,m，是仅仅一个比特，因为在这种情况下，主要处理指针的位置能够表达是否已通告了要被通告的某一前缀和还可能的其属性。

在根据本发明的一个实施例的用于控制通告路由数据的设备中，该设备的处理器被布置成：维护VPN(虚拟专用网)特定的前缀主要列表，以及相互有关并且根据上述原则并行运行不同VPN的通告过程。在这种情况下，每一个前缀可以包括地址、网络掩码的长度以及路由标识符(“RD”)。可以对于不同VPN分别维护根据图2的数据结构。

在根据本发明的实施例的用于控制通告路由数据的设备中，该设备的处理器被布置成：对于邻居路由器的预定义组维护组特定的前缀主要列表，以及相互有关并且根据上述原则并行运行不同组的通告过程。可以对于邻居路由器的不同组分别维护根据图2的数据结构。通过对邻居路由器分组并且对这些组进行并行处理，使通告对于多处理器环境可缩放是可能的。

在根据本发明的实施例的用于控制通告路由数据的设备中，该设备的处理器被布置成：对于每一个本地配置的VRF实例(虚拟路由和转发)的邻居路由器维护地址族特定的前缀主要列表，以及相互有关并且根据上述原则并行运行每一个VRF实例中的不同地址族的通告过程。可以对于不同VRF实例中的不同地址族分别维护根据图2的数据结构。通过并行处理每一个VRF实例的地址族，使通告对于多处理器环境可缩放是可能的。地址族可以包含例如IPv4单播路由、IPv4VPN路由、IPv6单播路由或PWE3自动发现路由(边缘到边缘伪线仿真)。

图3示出了根据本发明的实施例的用于在数据传输网络中控制从第一路由器向其邻居路由器通告路由数据的方法的流程图，其中路由数据包括与经由第一路由器可访问的数据传输网络的区域有关的前缀。该方法包括：

-在阶段301中，维护前缀的主要列表，使得在主要列表上，每一个前缀具有前任和/或继任，

-在阶段302中，维护指示符向量，使得每一个前缀与指示符向量中的一个相关联，每一个指示符向量包含用于邻居路由器中的每一个的数据项，以及该指示符向量的每一个数据项指示是否要向与该数据项相关联的邻居路由器通告与该指示符向量相关联的前缀，

-在阶段303中，对于邻居路由器中的每一个，维护指向前缀中的特定一个前缀的主要处理指针，所述特定一个前缀与和该邻居路由器有关的通告过程的主导状态相关，当向与主要处理指针相关联的邻居路由器通告前缀时，所述主要处理指针在前缀的主要列表上向前移动，以及

-在阶段304中，关于每一个邻居路由器，基于与对应于和该邻居路由器有关的主要处理指针的位置的前缀相关联的指示符向量，确定是否需要向该邻居路由器通告该前缀。

在根据本发明的实施例的方法中，每一个指示符向量的每一个数据项包括：

-第一变量，其用于指示是否要向与该数据项有关的邻居路由器通告前缀与该指示符向量有关的前缀，以及

-第二变量，其用于指示是否已经向与该数据项有关的邻居路由器通告了与该指示符向量有关的前缀。

其中如果第一变量指示与主要处理指针的位置相对应的前缀是要向该邻居路由器通告的前缀，并且第二变量指示尚未向该邻居路由器通告该前缀，则该前缀被认为是需要向对应的邻居路由器通告的前缀，以及该方法包括作为对向该邻居路由器通告该前缀的响应，将第二变量设置成指示已经向该邻居路由器通告了该前缀。

在根据本发明的实施例的方法中，对一个或多个相似性列表进行维护，使得每一个相似性列表包含其属性基于预定的准则是相似的这样的前缀，以及作为对需要向对应的邻居路由器通告与主要处理指针的位置相对应的前缀的情况的响应，基于指示符向量来确定是否需要向对应的邻居路由器通告包含与主要处理指针的位置相对应的前缀的相似性列表上的一个或多个其它前缀。

根据本发明的实施例的方法进一步包括：

-使每一个相似性列表上的前缀保持与主要列表上的前缀的相互顺序相对应的相互顺序，以及

-将其它前缀中的一个或多个选择为是在相似性列表上、按照前缀的相互顺序，在与主要处理指针的位置相对应的前缀之后的前缀。

根据本发明的实施例的方法，包括：作为对前缀中的一个已经被认为是需要向邻居路由器中的一个通告的前缀的情况的响应，运行特定于该邻居路由器的策略函数，使得该前缀和其属性是该策略函数的输入量，以及基于用策略函数获得的策略结果，允许或不允许向该邻居路由器通告该前缀。

根据本发明的实施例的方法包括：

-维护策略组，使得每一个策略组包含与同一策略函数有关的这样的邻居路由器，

-对于每一个前缀和每一个策略组，存储与该前缀、其属性以及与该策略组有关的策略函数相对应的策略结果，以及

-作为对需要向属于该策略组的任何邻居路由器通告该前缀的情况的响应，使用已存储的策略结果，而不是运行策略函数。

对于所有策略组或仅仅对于其中邻居路由器的数量超过预定限额的这样的策略组，可以实现对策略结果的上述存储和重用。

根据本发明的实施例的方法，包括：将其主要处理指针指向前缀的主要列表上的同一前缀的邻居路由器相互关联以形成链接列表，以及使用单个指针来表示在链接列表上的所有邻居路由器的主要处理指针。

根据本发明的实施例的方法，包括：作为对已经从邻居路由器中的一个接收到新的前缀和其属性，并且新的前缀不同于前缀的主要列表上的现有前缀中的任何一个的情况的响应，将新的前缀插入前缀的主要列表的末尾，以及基于该新的前缀的属性为新的前缀形成新的指示符向量。

根据本发明的实施例的方法，包括：作为对已经改变了前缀的属性中的一个或多个的情况的响应，从前缀的主要列表移除该前缀，以及将该前缀插入前缀的主要列表的末尾，以及基于该前缀的属性为该前缀形成新的指示符向量。

在根据本发明的实施例的方法中，前缀的主要列表是链接列表。

根据本发明的实施例的计算机程序，包括：软件模块，其用于控制从第一路由器向其邻居路由器通告路由数据，其中路由数据包括与经由第一路由器可访问的数据传输网络的区域有关的前缀。该软件模块包括计算机可执行的指令，所述计算机可执行的指令用于控制可编程处理器用于：

-维护前缀的主要列表，使得在主要列表上，每一个前缀具有前任和/或继任，

-维护指示符向量，使得前缀中的每一个与指示符向量中的一个相关联，每一个指示符向量包含用于邻居路由器中的每一个的数据项，以及该指示符向量的每一个数据项指示是否要向与该数据项相关联的邻居路由器通告与该指示符向量相关联的前缀，

-对于邻居路由器中的每一个，维护指向前缀中的特定一个前缀的主要处理指针，该特定一个前缀与和该邻居路由器有关的通告过程的主导状态相关，当向与主要处理指针相关联的邻居路由器通告前缀时，所述主要处理指针在前缀的主要列表上向前移动，以及

-关于每一个邻居路由器，基于与对应于和该邻居路由器有关的主要处理指针的位置的前缀相关联的指示符向量，确定是否需要向该邻居路由器通告该前缀。

根据本发明的实施例的计算机程序产品包括编码有根据本发明的实施例的计算机程序的计算机可读介质，例如光盘(“CD”)。

根据本发明的实施例的信号被编码成携带定义根据本发明的实施例的计算机程序的信息。

在上面给出的描述中提供的具体示例不应当被解释为限制性的。因此，本发明不仅限于上述实施例，许多变体是可能的。

Claims (25)

1.一种用于控制从第一路由器向第二路由器通告路由数据的设备(117)，所述路由数据包括与经由所述第一路由器可访问的数据传输网络的区域有关的前缀，以及所述设备包括用于维护所述前缀的主要列表，使得在所述主要列表上，每一个前缀具有前任和/或继任的装置，其特征在于，所述设备进一步包括：

-用于维护指示符向量，使得所述前缀中的每一个与所述指示符向量中的一个相关联，每一个指示符向量包含用于所述第二路由器中的每一个的数据项，以及所述指示符向量的每一个数据项指示是否要向与所述数据项相关联的所述第二路由器通告与所述指示符向量相关联的所述前缀的装置，

-用于对于所述第二路由器中的每一个，维护指向所述前缀中的特定一个前缀的主要处理指针，所述特定一个前缀与和所述第二路由器有关的通告过程的主导状态相关，当向与所述主要处理指针相关联的所述第二路由器通告所述前缀时，所述主要处理指针在所述前缀的所述主要列表上向前移动的装置，以及

-用于关于每一个第二路由器，基于与对应于和所述第二路由器有关的所述主要处理指针的位置的所述前缀相关联的所述指示符向量，确定是否需要向所述第二路由器通告所述前缀的装置。

2.根据权利要求1所述的设备，其中，每一个指示符向量的每一个数据项包括：

-第一变量，所述第一变量用于指示与所述指示符向量有关的所述前缀是否是要向与所述数据项有关的所述第二路由器通告的前缀，以及

-第二变量，所述第二变量用于指示是否已经向与所述数据项有关的所述第二路由器通告了与所述指示符向量有关的所述前缀，

其中，所述设备进一步包括用于作为对所述第一变量指示与所述主要处理指针的所述位置相对应的所述前缀是要向所述第二路由器通告的前缀并且所述第二变量指示尚未向所述第二路由器通告所述前缀的情况的响应，确定需要向对应的第二路由器通告所述前缀的装置，以及用于作为对向所述第二路由器通告所述前缀的响应，将所述第二变量设置成指示已经向所述第二路由器通告了所述前缀的装置。

3.根据权利要求1所述的设备，进一步包括用于维护一个或多个相似性列表，使得每一个相似性列表包含其属性基于预定的准则是相似的这样的前缀的装置；以及用于作为对需要向所述对应的第二路由器通告与所述主要处理指针的所述位置相对应的所述前缀的情况的响应，基于所述指示符向量来确定是否需要向所述对应的第二路由器通告包含与所述主要处理指针的所述位置相对应的所述前缀的所述相似性列表上的其它前缀中的一个或多个的装置。

4.根据权利要求3所述的设备，进一步包括：

--用于使每一个相似性列表上的所述前缀保持与所述主要列表上的所述前缀的相互顺序相对应的相互顺序的装置，以及

-用于将所述其它前缀中的所述一个或多个选择为是在所述相似性列表上、按照所述前缀的所述相互顺序，在与所述主要处理指针的所述位置相对应的所述前缀之后的前缀的装置。

5.根据权利要求1-4中的任何一个所述的设备，进一步包括用于作为对所述前缀中的一个被认为是需要向所述第二路由器中的一个通告的前缀的情况的响应，运行特定于所述第二路由器的策略函数，使得所述前缀和其属性是所述策略函数的输入量；以及用于基于所述策略函数的策略结果，允许或不允许向所述第二路由器通告所述前缀的装置。

6.根据权利要求5所述的设备，其中，进一步包括用于维护策略组，使得每一个策略组包含与同一策略函数有关的这样的第二路由器的装置，用于关于每一个前缀和所述策略组中的至少一个，存储与所述前缀、其属性以及与所述策略组有关的所述策略函数相对应的策略结果的装置，以及用于作为对需要向属于所述策略组的任何第二路由器通告所述前缀的情况的响应，使用已存储的策略结果，而不是运行所述策略函数的装置。

7.根据权利要求1-4中的任何一个所述的设备，进一步包括用于将其主要处理指针指向所述前缀的所述主要列表上的同一前缀的所述第二路由器相互关联以形成链接列表；以及使用单个指针来表示在所述链接列表上的所有所述第二路由器的所述主要处理指针的装置。

8.根据权利要求1-4中的任何一个所述的设备，进一步包括用于作为对已经从所述第二路由器中的一个接收到新的前缀和其属性，并且所述新的前缀不同于所述前缀的所述主要列表上的现有前缀中的任何一个的情况的响应，将所述新的前缀插入所述前缀的所述主要列表的末尾，以及基于所述新的前缀的属性为所述新的前缀形成新的指示符向量的装置。

9.根据权利要求1-4中的任何一个所述的设备，进一步包括用于作为对已经改变了前缀的属性中的一个或多个的情况的响应，从所述前缀的所述主要列表移除所述前缀的装置，以及将所述前缀插入所述前缀的所述主要列表的末尾的装置，以及基于所述前缀的属性为所述前缀形成新的指示符向量的装置。

10.根据权利要求1-4中的任何一个所述的设备，进一步包括用于以链接列表的形式来维护所述前缀的所述主要列表的装置。

11.一种路由器(101)，包括：

-数据传输端口，所述数据传输端口用于连接到数据传输链路，

-处理系统，所述处理系统用于支持路由协议，以及

-根据权利要求1-10中的任何一个所述的设备(117)，所述设备用于控制从所述路由器向其它路由器通告路由数据，所述路由数据与所述路由协议有关，并且包括与经由所述路由器可访问的数据传输网络的区域有关的前缀，

其中所述处理系统被布置成：向所述其它路由器中的一个或多个通告所述前缀中的一个或多个，作为对所述设备已经确定需要向这些其它路由器通告这些前缀的情况的响应。

12.根据权利要求11所述的路由器，其中，所述处理系统被布置成支持外部边界网关协议(eBGP)，并且所述路由数据包括所述外部边界网关协议的路由数据。

13.根据权利要求11所述的路由器，其中，所述处理系统被布置成支持内部边界网关协议(iBGP)，并且所述路由数据包括所述内部边界网关协议的路由数据。

14.根据权利要求11所述的路由器，其中，所述处理系统包括一个或多个处理器单元，以及所述设备用所述处理器单元中的一个或多个来实现。

15.根据权利要求11-14中的任何一个所述的路由器，其中，所述处理系统被布置成支持多协议标签交换(MPLS)。

16.一种用于控制从第一路由器向第二路由器通告路由数据的方法，所述路由数据包括与经由所述第一路由器可访问的数据传输网络的区域有关的前缀，以及所述方法包括维护(301)所述前缀的主要列表，使得在所述主要列表上，每一个前缀具有前任和/或继任，其特征在于，所述方法进一步包括：

-维护(302)指示符向量，使得所述前缀中的每一个与所述指示符向量中的一个相关联，每一个指示符向量包含用于所述第二路由器中的每一个的数据项，以及所述指示符向量的每一个数据项指示是否要向与所述数据项相关联的所述第二路由器通告与所述指示符向量相关联的所述前缀，

-对于所述第二路由器中的每一个，维护(303)指向所述前缀中的特定一个前缀的主要处理指针，所述特定一个前缀与和所述第二路由器有关的通告过程的主导状态相关，当向与所述主要处理指针相关联的所述第二路由器通告所述前缀时，所述主要处理指针在所述前缀的所述主要列表上向前移动，以及

-关于每一个第二路由器，基于与对应于和所述第二路由器有关的所述主要处理指针的位置的所述前缀相关联的所述指示符向量，确定(304)是否需要向所述第二路由器通告所述前缀。

17.根据权利要求16所述的方法，其中，每一个指示符向量的每一个数据项包括：

-第一变量，所述第一变量用于指示与所述指示符向量有关的所述前缀是否是要向与所述数据项有关的所述第二路由器通告的前缀，以及

-第二变量，所述第二变量用于指示是否已经向与所述数据项有关的所述第二路由器通告了与所述指示符向量有关的所述前缀，

其中，如果所述第一变量指示与所述主要处理指针的所述位置相对应的所述前缀是要向所述第二路由器通告的前缀，并且所述第二变量指示尚未向所述第二路由器通告所述前缀，则所述前缀被认为是需要向对应的第二路由器通告的前缀，以及所述方法包括：作为对向所述第二路由器通告所述前缀的响应，将所述第二变量设置成指示已经向所述第二路由器通告了所述前缀。

18.根据权利要求16所述的方法，其中，维护一个或多个相似性列表，使得每一个相似性列表包含其属性基于预定的准则是相似的这样的前缀，以及作为对需要向所述对应的第二路由器通告与所述主要处理指针的所述位置相对应的所述前缀的情况的响应，基于所述指示符向量来确定是否需要向所述对应的第二路由器通告包含与所述主要处理指针的所述位置相对应的所述前缀的所述相似性列表上的其它前缀中的一个或多个。

19.根据权利要求18所述的方法，其中，所述方法包括：

--使每一个相似性列表上的所述前缀保持与所述主要列表上的所述前缀的相互顺序相对应的相互顺序，以及

-将所述其它前缀中的所述一个或多个选择为是在所述相似性列表上、按照所述前缀的所述相互顺序，在与所述主要处理指针的所述位置相对应的所述前缀之后的前缀。

20.根据权利要求16-19中的任何一个所述的方法，其中，所述方法包括：作为对所述前缀中的一个已经被认为是需要向所述第二路由器中的一个通告的前缀的情况的响应，运行特定于所述第二路由器的策略函数，使得所述前缀和其属性是所述策略函数的输入量，以及基于用所述策略函数获得的策略结果，允许或不允许向所述第二路由器通告所述前缀。

21.根据权利要求20所述的方法，其中，所述方法包括：

-维护策略组，使得每一个策略组包含与同一策略函数有关的这样的第二路由器，

-对于每一个前缀以及对于所述策略组中的至少一个，存储与所述前缀、其属性以及与所述策略组有关的所述策略函数相对应的策略结果，以及

-作为对需要向属于所述策略组的任何第二路由器通告所述前缀的情况的响应，使用已存储的策略结果，而不是运行所述策略函数。

22.根据权利要求16-19中的任何一个所述的方法，其中，所述方法包括：将其主要处理指针指向所述前缀的所述主要列表上的同一前缀的所述第二路由器相互关联以形成链接列表，以及使用单个指针来表示在所述链接列表上的所有所述第二路由器的所述主要处理指针。

23.根据权利要求16-19中的任何一个所述的方法，其中，所述方法包括：作为对已经从所述第二路由器中的一个接收到新的前缀和其属性，并且所述新的前缀不同于所述前缀的所述主要列表上的现有前缀中的任何一个的情况的响应，将所述新的前缀插入所述前缀的所述主要列表的末尾，以及基于所述新的前缀的属性来为所述新的前缀形成新的指示符向量。

24.根据权利要求16-19中的任何一个所述的方法，其中，所述方法包括：作为对已经改变了前缀的属性中的一个或多个的情况的响应，从所述前缀的所述主要列表移除所述前缀，以及将所述前缀插入所述前缀的所述主要列表的末尾，以及基于所述前缀的属性来为所述前缀形成新的指示符向量。

25.根据权利要求16-19中的任何一个所述的方法，其中，所述前缀的所述主要列表是链接列表。