可扩展路由器中OSPF链路状态信息的分布式存储方法

摘要

本发明公开了一种可扩展路由器中OSPF链路状态信息的分布式存储方法，包括以下步骤：S1：对待处理的OSPF区域中的各项参数进行初始化；S2：将所述待处理的OSPF区域的网络拓扑结构图形转换成树形结构；S3：根据所述树形结构对所述待处理的OSPF区域进行区域划分及进行节点处理器的分配；S4：在按照预设顺序划分后的每个区域内选择一个代理路由器用以交换各个区域间的OSPF链路状态信息。本发明的方法既可以减少OSPF内部总体的交换链路状态信息的带宽，又可以很好地实现板卡间的负载均衡。

说明书

技术领域

本发明涉及互联网IP路由器体系结构设计研究技术领域，特别涉及一种可扩展路由器中OSPF链路状态信息的分布式存储方法。

背景技术

Internet技术的发展特别是云计算和物联网技术的快速发展给路由器的处理能力带来了很大的挑战，大量的数据充斥着网络带宽，这种现状带来的问题促使了可扩展路由器的兴起与发展。可扩展路由器是一种建立在路由器的功能、性能以及其接口上的可扩展性路由器。

OSPF(Open Shortest Path First，开放式最短路径优先)协议是现在应用最广泛的IGP(Interior Gateway Protocol，内部网关协议)协议，其配置和实施决定整个网络的性能。通常来说，OSPF协议适用于大型的路由系统，尽管OSPF协议本身是以使用区域划分的方法来减少路由器之间的信息通信量，但是一个配置恰当的OSPF区域内部可能仍然会有几百台甚至上千台的路由器信息需要维护。另外，OSPF协议本身所包含的链路状态信息也会占用很大的网络带宽，这就使得整个网络的LSDB(Link State DataBase，链路状态数据库)数据库非常庞大，这就给OSPF区域内部的路由信息维护带来了很大的挑战。目前，解决这种问题的方法往往是使用可扩展路由器中的多个节点处理器去同时维护整个区域的信息，这样，单个OSPF区域内需要维护数量较大的链路状态信息，可扩展路由器中的多个处理器同时管理着区域中的链路状态信息，这就在一定程度上造成了冗余存储。因此，这种方法可能会导致板卡的负载不均衡，而这种负载不均衡的情况可能会进一步阻碍整个区域的路由信息处理速度。

发明内容

本发明旨在至少在一定程度上解决上述相关技术中的技术问题之一。

为此，本发明的目的在于提出一种可扩展路由器中OSPF链路状态信息的分布式存储方法，该方法既可以减少OSPF内部总体的交换链路状态信息的带宽，又可以很好地实现板卡间的负载均衡。

为达到上述目的，本发明的实施例提出了一种可扩展路由器中OSPF链路状态信息的分布式存储方法，包括以下步骤：S1：对待处理的OSPF区域中的各项参数进行初始化；S2： 将所述待处理的OSPF区域的网络拓扑结构图形转换成树形结构；S3：根据所述树形结构对所述待处理的OSPF区域进行区域划分及进行节点处理器的分配；S4：在按照预设顺序划分后的每个区域内选择一个代理路由器用以交换各个区域间的OSPF链路状态信息。

根据本发明实施例的通过将与指定的路由器相连的所有路由器作为其孩子节点的思想将OSPF区域的网络拓扑图转换为特定的抽象树型结构，然后按照一定的遍历顺序遍历这种树型结构，每当得到一定数量的路由器时，将这些一定数量的路由器的链路状态信息交给一个节点处理器去维护，直到区域中所有的路由器平均分配给不同的节点处理器去维护链路状态信息，并通过划分后的区域内的代理器和管理该区域的处理器进行路由器链路状态信息的管理和维护，而其它路由器不做任何改动。这样，每个处理器就只会管理和维护自己所需要管理的区域，而区域之间选择各自的代理节点相互发布信息，从而可以减少OSPF内部总体的交换链路状态信息的带宽，又可以很好地实现板卡间的负载均衡，并有效地提高了可扩展路由器中各处理器的处理效率。

另外，根据本发明上述实施例的可扩展路由器中OSPF链路状态信息的分布式存储方法还可以具有如下附加的技术特征：

在本发明的一个实施例中，所述步骤S1进一步包括：S11：获取所述待处理的OSPF区域中的可扩展路由器中的节点处理器的个数NUM_P以及所述待处理的OSPF区域中路由器的个数NUM_R，设NUM_P＝n，NUM_R＝m；S12：将所述可扩展路由器中各节点处理器按照当前任务的个数从小到大进行排序；S13：设置一个大小为预设大小的数组存放所有路由器的标识信息，并将所述数组中的所有元素置零以完成初始化；S14：设置数据结构RTNode，用以存储各个路由器之间的连接关系，其中，所述数据结构RTNode中的信息包括：Router ID，指向左孩子路由器的L_router指针和指向右孩子路由器的R_router指针。

在本发明的一个实施例中，所述步骤S2进一步包括：S21：查找所有路由器的路由表以获取Router_root；S22：以Router_root作为根节点开始构建树型结构；S23：将所述根节点Router_root的Router ID放入所述数组，将CPointer指向数组中的第一个元素，并根据当前路由器生成树形结构。

在本发明的一个实施例中，所述步骤S3进一步包括：S31：根据节点处理器的个数n和所有路由器的个数m，得到每个要划分成的区域的路由器的个数A，其中，A＝[m/n]+1，并对所述树型结构进行遍历；S32：查找所述树形结构最左边的叶子节点；S33：从所述最左边的叶子节点开始按照所述预设顺序依次进行遍历；S34：将遍历后得到的A个路由器分配给该划分区域内的n个节点处理器中指定的一个进行处理；S35：判断所述A个路由器是否都分配给了指定的节点处理器，如果未分配完毕，则继续执行该步骤S35，如果分配完毕，则进入开始遍历，并执行n--；S36：判断n是否小于或等于0，如果n小于或等于0，则判 定所述待处理OSPF区域分区完成，否则继续执行步骤S32至步骤S36。

在本发明的一个实施例中，所述步骤S4进一步包括：在每个划分后的区域中选择连接数最多的路由器作为本区域内的代理路由器，如果连接数最多的路由器有多个，则选择第一个找到的路由器作为本区域内的代理路由器，并通过所述代理路由器代理该区域内的所有路由器与其它划分后的区域进行OSPF链路状态信息的交换，并通过划分后的区域内的代理路由器和管理该区域的节点处理器进行路由器链路状态信息的管理和维护，并且其它路由器不做任何改动。

在本发明的一个实施例中，所述步骤S21进一步包括：S211：记录每个路由器的路由表中与其自身直连的路由器的个数；S212：获取所述路由表中与其自身直连的路由器的个数最多的路由器的Router ID，并将该路由器标记为Router_root；S213：如果所述路由表中与其自身直连的路由器的个数最多的路由器为多个，则将到所述待处理的OSPF区域中的指定路由器(DR，Designated Router)的跳数最小的路由器作为Router_root。

在本发明的一个实施例中，所述步骤S23进一步包括：S231：查询当前路由器的路由表，获取与所述当前路由器直接相连的所有路由器的个数K，其中，将到当前路由器之间的跳数为1的路由器称为与当前路由器直接相连的路由器；S232：根据从上到下的顺序查找所述当前路由器的路由表，并将所述当前路由器的L_router指针指向第一个在路由表中查询到的路由器，并将当前查找到的路由器的Router ID放入数组，然后执行K--；S233：判断K是否大于0；S234：如果K大于0，则继续在当前路由器的路由表中查找与CPointer指针指向的路由器直连的路由器，并将上一个查询到的路由器的R_router指针指向本次查找到的路由器，并将本次查询到的路由器的Router ID放入数组，并执行K--；S235：判断K是否小于或等于0，如果K小于或等于0，则执行步骤S236，否则返回执行所述步骤S234；S236：将CPointer指针指向所述数组中的下一个路由器以作为当前路由器，并执行上述步骤S234至步骤S235；步骤S237：重复执行步骤S234至步骤S236，直至所述数组中所有的Router ID都被遍历完。

在本发明的一个实施例中，在所述步骤S32中，查找所述树形结构最左边的叶子节点的过程通过如下代码实现：

本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中：

图1为根据本发明一个实施例的可扩展路由器中OSPF链路状态信息的分布式存储方法的流程图；以及

图2为根据本发明另一个实施例的可扩展路由器中OSPF链路状态信息的分布式存储方法的流程图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不能理解为对本发明的限制。

此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。在本发明的描述中，“多个”的含义是两个或两个以上，除非另有明确具体的限定。

在本发明中，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”、“固定”等术语应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。

在本发明中，除非另有明确的规定和限定，第一特征在第二特征之“上”或之“下”可以包括第一和第二特征直接接触，也可以包括第一和第二特征不是直接接触而是通过它们之间的另外的特征接触。而且，第一特征在第二特征“之上”、“上方”和“上面”包括第一特征在第二特征正上方和斜上方，或仅仅表示第一特征水平高度高于第二特征。第一特征在第二特征“之下”、“下方”和“下面”包括第一特征在第二特征正上方和斜上方，或仅仅表示第一特征水平高度小于第二特征。

下面参照附图描述根据本发明实施例的可扩展路由器中OSPF链路状态信息的分布式存储方法。

图1为根据本发明一个实施例的可扩展路由器中OSPF链路状态信息的分布式存储方法的流程图。图2为根据本发明另一个实施例的可扩展路由器中OSPF链路状态信息的分布式存储方法的流程图。结合图1和图2所示，该方法包括以下步骤：

步骤S1：对待处理的OSPF区域中的各项参数进行初始化。

具体地，步骤S1包括以下步骤：

步骤S11：获取待处理的OSPF区域中的可扩展路由器中的节点处理器的个数NUM_P以及待处理的OSPF区域中的路由器的个数NUM_R，设NUM_P＝n，NUM_R＝m。

步骤S12：按照可扩展路由器中各节点处理器中所有板卡的当前任务的个数对其从小到大进行排序，当前任务的个数越少就表示其处理能力越强。节点处理器按照处理能力从大到小分别标记为P₁～P_n。

步骤S13：设置一个大小为预设大小的数组存放网络中所有路由器的标识信息，并将数组中的所有元素置零以完成初始化。其中，预设大小例如为m*4B，具体地说，每个待处理的OSPF区域用4B的大小去存储一个路由器的标识，称为Router ID，并用该4B大小的Router ID信息来唯一的标识一台路由器。

步骤S14：设置数据结构RTNode，用以存储网络中各个路由器之间的连接关系，其中，数据结构RTNode中的信息包括：Router ID，指向左孩子路由器的L_router指针和指向右孩子路由器的R_router指针。

步骤S2：将待处理的OSPF区域的网络拓扑结构图形转换成树形结构。

具体地，步骤S2包括以下步骤：

S21：从待处理的OSPF区域中的可扩展路由器开始，查找所有路由器的路由表以获取Router_root。

更为具体地，步骤S21包括以下步骤：

S211：记录每个路由器的路由表中与其自身直连的路由器的个数。

S212：获取步骤S211中的路由表中与其自身直连的路由器的个数最多的路由器的Router ID，并将该路由器标记为Router_root。

S213：如果步骤S211中的路由表中与其自身直连的路由器的个数最多的路由器有多个，则将到待处理的OSPF区域中的DR(Designated Router，指定路由器)的跳数最小的路由器作为Router_root。

S22：以Router_root作为根节点开始构建树型结构(将路由器的每个接口作为遍历的单位)。

S23：将根节点Router_root的Router ID放入数组，将CPointer指向数组中的第一个元素，并根据当前路由器生成树形结构。其中，指针CPointer指向数组中的Router_root节点，称指针CPointer所指的路由器节点为当前路由器节点。

具体地，步骤S23进一步包括以下步骤：

S231：查询当前路由器的路由表，获取与当前路由器直接相连的所有路由器的个数K，其中，将到当前路由器之间的跳数为1的路由器称为与当前路由器直接相连的路由器。

S232：根据从上到下的顺序查找当前路由的路由表，并将当前路由器的L_router指针(左孩子)指向第一个在路由表中查询到的路由器，并将当前查找到的路由器的Router ID放入数组，然后执行k--。其中，需要说明的是，如果Router ID已经存在，数组中就不再重复放入Router ID。如果未重复压入Router ID，则k--必须执行。

S233：判断K是否大于0。

S234，如果K大于0，则继续在当前路由器的路由表中查找与CPointer指针指向的路由器(当前路由器节点)直连的路由器，并将上一个查询到的路由器的R_router指针(右孩子)指向本次查找到的路由器，并将本次查询到的路由器的Router ID放入数组，然后执行k--。其中，需要说明的是，如果Router ID已经存在，数组中就不再重复放入Router ID。如果未重复压入Router ID，则k--必须执行。

S235：判断K是否小于或等于0，如果K小于或等于0，则执行步骤S236，否则返回执行步骤S234。

S236：将CPointer指针指向数组中下一个路由器的Router ID，也即数组中的下一个路由器作为当前路由器，并执行上述步骤S234至步骤S235，也即执行m--。

步骤S237：重复执行步骤S234至步骤S236，直至数组中所有的Router ID都被遍历完为止，即m＝0时，退出循环。此时，待处理的OSPF区域中的所有路由器被搜索完毕，并形成了待分区的树型结构。

需要说明的是，在上述示例中，不存在与当前路由器相连的路由节点数为零的情况。具体地说，首先，在初始条件下，选取的是拥有最大连接数的路由节点，如果所有的路由器都不相连，这不符合OSPF协议；其次，即使不是在初始条件下，也不可能存在一个点是孤立的，这不符合OSPF协议。

步骤S3：根据树形结构对待处理的OSPF区域进行区域划分及进行节点处理器的分配。

具体地，步骤S3进一步包括以下步骤：

S31：根据步骤S11中节点处理器的个数n和路由器的个数m，得到每个要划分成的区域的路由器的个数A，其中，A＝[m/n]+1，并开始对步骤S2中形成的树型结构进行遍历。

S32：初始化开始进行遍历的路由器节点，即查找树形结构最左边的叶子节点。在本发 明的一个实施例中，该过程可通过如下代码实现：

S33：从树形结构的最左边的叶子节点开始按照预设顺序依次进行遍历。其中，在本发明的一个实施例中，预设顺序例如为由左孩子路由器—父亲路由器—右孩子路由器。

S34：按照步骤S32和步骤S33中描述的规则进行遍历得到A个路由器，将遍历后得到的A个路由器分配给该划分区域内的n个节点处理器中指定的一个进行处理。换言之，即将所有遍历到的路由器交给特定的一个节点处理器P_n处理(n的初始值是节点处理器的个数)，并进一步执行n--。

其中，需要说明的是，因为P_n的处理能力最弱，因此，将其用于处理那些离Router_root最远的路由器的转发信息，因为Router_root必定是最后一个被遍历，所以处理能力最强的P_n去处理Router_root所在的区域。

S35：判断A个路由器是否都分配给了指定的节点处理器，如果未分配完毕，则继续执行该步骤S35，如果分配完毕，则进入开始遍历，并执行n--。

S36：判断n是否小于或等于0，如果n小于或等于0，则判定待处理OSPF区域分区完成，否则继续执行该步骤S36。换言之，即当n>0时，表示n个节点处理器并没有都管理各自的A个路由器节点，也即OSPF区域中的路由器并未都分配到各自所属的节点处理器上，则继续执行该步骤。如果n<＝0，则表示n个节点处理器全部都管理了各自的A个路由器节点，也即OSPF区域中的路由器都已经分配到各自所属的节点处理器上，则判定节点处理器分配完毕，也即待处理OSPF区域分区完成。

步骤S4：在按照步骤S3中的预设遍历顺序(左孩子路由器—父亲路由器—右孩子路由器)划分后的每个区域内选择一个代理路由器用以交换各个区域间的OSPF链路状态信息。具体地说，由于每个节点处理器按照处理能力的大小分到了一块区域，每块区域所分配到的路由器的个数相同，且都是相邻区域的路由器，所以重新划分区域后，不需要对现有的OSPF 路由体系进行改动。

在一些示例中，步骤S4进一步包括：在每个划分后的区域中选择连接数最多的路由器作为该区域内的代理路由器，如果连接数最多的路由器有多个，则选择第一个找到的路由器作为该区域内的代理路由器，并通过该代理路由器代理该区域内的所有路由器与其它划分后的区域进行OSPF路由状态信息的交换。

综上所述，本发明上述实施例的方法的主要原理可概述如下：首先通过将与指定的路由器相连的所有路由器作为其孩子节点的思想将OSPF区域的网络拓扑图转换为特定的抽象树型结构，然后按照一定的遍历顺序遍历这种树型结构，每当得到一定数量的路由器时，将这些一定数量的路由器的链路状态信息交给一个处理器去维护，直到区域中所有的路由器平均分配(最后一个处理器可能与前面所分到路由器个数不同)给不同的处理器去维护链路状态信息。

换言之，该方法可以通过将OSPF区域内的一些相邻的路由器的划分为一个区域，并拿出一个单独的处理器去管理和维护这些信息，最后，一个OSPF区域就被划分成多个拥有相同数量的路由器的区域，那么，每个处理器就只会管理和维护自己所需要管理的区域，而区域之间选择各自的代理节点相互发布信息，并通过划分后的区域内的代理路由器和管理该区域的节点处理器进行路由器链路状态信息的管理和维护，而其它路由器不做任何改动。

根据本发明实施例的通过将与指定的路由器相连的所有路由器作为其孩子节点的思想将OSPF区域的网络拓扑图转换为特定的抽象树型结构，然后按照一定的遍历顺序遍历这种树型结构，每当得到一定数量的路由器时，将这些一定数量的路由器的链路状态信息交给一个节点处理器去维护，直到区域中所有的路由器平均分配给不同的节点处理器去维护链路状态信息，并通过划分后的区域内的代理器和管理该区域的处理器进行路由器链路状态信息的管理和维护，而其它路由器不做任何改动。这样，每个处理器就只会管理和维护自己所需要管理的区域，而区域之间选择各自的代理节点相互发布信息，从而可以减少OSPF内部总体的交换链路状态信息的带宽，又可以很好地实现板卡间的负载均衡，并有效地提高了可扩展路由器中各处理器的处理效率。

流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个或更多个用于实现特定逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分，并且本发明的优选实施方式的范围包括另外的实现，其中可以不按所示出或讨论的顺序，包括根据所涉及的功能按基本同时的方式或按相反的顺序，来执行功能，这应被本发明的实施例所属技术领域的技术人员所理解。

在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令执 行系统、装置或设备(如基于计算机的系统、包括处理器的系统或其他可以从指令执行系统、装置或设备取指令并执行指令的系统)使用，或结合这些指令执行系统、装置或设备而使用。就本说明书而言，"计算机可读介质"可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装置。计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布线的电连接部(电子装置)，便携式计算机盘盒(磁装置)，随机存取存储器(RAM)，只读存储器(ROM)，可擦除可编辑只读存储器(EPROM或闪速存储器)，光纤装置，以及便携式光盘只读存储器(CDROM)。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理来以电子方式获得所述程序，然后将其存储在计算机存储器中。

应当理解，本发明的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门电路的离散逻辑电路，具有合适的组合逻辑门电路的专用集成电路，可编程门阵列(PGA)，现场可编程门阵列(FPGA)等。

本技术领域的普通技术人员可以理解实现上述实施例方法携带的全部或部分步骤是可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读存储介质中，该程序在执行时，包括方法实施例的步骤之一或其组合。

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

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

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在不脱离本发明的原理和宗旨的情况下在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。