基于链路状态路由协议的路由计算方法和网络节点

摘要

本发明公开了一种基于链路状态路由协议的路由计算方法，该方法包括：创建并维护节点表和可达前缀表；其中，所述节点表中保存有最短路径树上的每个节点的标识和路径信息，所述可达前缀表中保存有所述最短路径树上的每个节点所对应的可达前缀信息；当所述网络中有链路状态发生变化时，通过重新构建最短路径树获得所述每个节点的最新路径信息；将每个节点的最新路径信息与所述节点表中的相应路径信息进行比较，确定路径发生变化的节点；计算所述可达前缀表中的与所述路径发生变化的节点对应的各可达前缀的路径。本发明还公开了一种运行链路状态路由协议的网络节点。本发明的技术方案较易实现且效率高。

说明书

技术领域

本发明涉及网络通信技术，尤指一种基于链路状态路由协议的路由计算方法和一种运行链路状态路由协议的网络节点。

背景技术

链路状态路由协议(link-state routing protocol)是指通过在网络中收集所有路由器相关的链路状态并通过计算得到相应路由信息的协议。一般将一台路由器上运行路由协议的接口信息以及邻居信息称为链路状态。目前主要的链路状态路由协议有：开放最短路径优先路由(OSPF，Open Shortest PathFirst)协议、开放最短路径优先路由版本3(OSPFv3，Open Shortest Path FirstVersion 3)协议和中间系统到中间系统的域内路由信息交换(IS-IS，Intermediate System-to-Intermediate System intra-domain routing informationexchange protocol)协议。

链路状态路由协议的基本工作原理如下：在自治系统(AS，AutonomousSystem)中每一台运行路由协议的路由器收集各自的接口/邻居信息并生成相应的链路状态信息报文在整个自治系统中进行扩散，使得在整个自治系统内部的每台路由器都可以接收到系统内所有路由器的链路状态信息并维护一个相同的链路状态数据库(LSDB，link-state Date Base)；在获得完整的LSDB之后，每台路由器根据LSDB里描述的路由信息利用Dijkstra算法计算出以自己为根的一棵最短路径树(SPT，Shortest Path Tree)，同时将LSDB里描述的对应于各个节点的可达前缀作为树上的相应节点的叶子；图1为一棵最短路径树以及依附于树上各节点的叶子的示意图，在图1中，圆形框表示最短路径树上的节点，可理解为一台设备，方形框表示依附于节点的叶子，对应于设备上的可达前缀；在利用Dijkstra算法计算最短路径树的过程中，每计算出SPT树上的一个节点的路径，就相应的计算依附于该节点的所有可达前缀的路由信息，最终保存所有可达前缀的路由信息，即生成本机的路由表。通常将上述路由计算过程称为最短路径优先(SPF)算法。

在传统的SPF算法实现中，网络中的任何链路状态信息的变化都需要每个节点全部重新计算自身的路由表，即重新构建最短路径树，并在构建最短路径树的过程中，同时计算出依附于树上节点的所有可达前缀的路由信息。随着IP网络的日益壮大，同一自治系统内的节点数和依附于节点的IP前缀数不断增多，频繁地全部重新计算所有路由严重制约了系统性能和路由收敛速度。

为了解决系统的CPU资源，加快收敛速度，目前业界提出了一些新技术用于对SPF算法做出改进，主要目标是尽量避免重新全部计算路由，而是根据链路信息变化的不同情况做出不同的处理，使得重新进行路由计算的波及面控制在较小范围内，以提高系统性能。这是因为在实际网络应用中，某些链路状态信息的变化并不需要让所有路由都全部重新计算，例如，图1中的节点C和节点D之间的链路断开时，并不影响节点B、C、E、F和G之间的拓扑结构和路由信息，所以不需要重新计算节点B、C、E、F和G的相关拓扑，而只计算节点C和D的相关拓扑和路由信息即可。

针对上述情况，产生了增量最短路径优先(ISPF，Incremental ShortestPath First)技术。ISPF技术的核心在于确定网络拓扑改变后需要重新进行路由计算的最小范围，为了确定该最小范围，必须完整记录网络中的初始拓扑情况，其中包含代表一台设备的NODE以及代表设备与设备间一条连接链路的LINK，图2为NODE与LINK之间的关系示意图，参见图2，路由协议从LSDB中学到的自治系统中的每个节点都会以NODE的形式记录下来，而节点所拥有的所有链路都以LINK形式存储在对应的NODE下面。同时，还要区分记录所有NODE和LINK的不同状态，例如该NODE与LINK是否是最短路径树上的有效节点和有效路径等，以及记录链路状态的变化类型，例如增加或减少的开销(cost)、新建链路和链路断开等情况，然后结合以上信息判断是否需要进行最短路径树的局部修正以及最短路径树上的哪些节点和可达前缀需要重新计算等，并且还发明了一种确定最短路径树上需要重新计算节点和叶子的新算法，但该算法需要多次递归计算，实现过于复杂。

综上所述现有的链路状态路由协议中的路由计算方法，实现复杂且效率低。

发明内容

本发明提供了一种基于链路状态路由协议的路由计算方法，该方法较易实现且效率高。

本发明还提供了一种运行链路状态路由协议的网络节点，该网络节点较易实现路由计算且效率高。

为达到上述目的，本发明的技术方案具体是这样实现的：

本发明公开了一种基于链路状态路由协议的路由计算方法，该方法包括：

创建并维护节点表和可达前缀表；其中，所述节点表中保存有最短路径树上的每个节点的标识和路径信息，所述可达前缀表中保存有所述最短路径树上的每个节点所对应的可达前缀信息；

当所述网络中有链路状态发生变化时，通过重新构建最短路径树获得所述每个节点的最新路径信息；将每个节点的最新路径信息与所述节点表中的相应路径信息进行比较，确定路径发生变化的节点；计算所述可达前缀表中的与所述路径发生变化的节点对应的各可达前缀的路径。

本发明还公开了一种运行链路状态路由协议的网络节点，该网络节点包括：创建维护模块、存储模块和路由计算模块，其中，

所述创建维护模块，用于在存储模块中创建节点表和可达前缀表，并进行维护；其中，所述节点表中保存有以所述网络节点为根的最短路径树上的每个节点的标识和路径信息，所述可达前缀表中保存有所述最短路径树上的每个节点所对应的可达前缀信息；

存储模块，用于存储节点表和可达前缀表；

路由计算模块，用于在网络中有链路状态发生变化时，通过重新构建以所述网络节点为根的最短路径树获得网络中的每个节点的最新路径信息，将每个节点的最新路径信息与所述存储模块节点表中的相应路径信息进行比较，确定路径发生变化的节点，然后计算所述存储模块可达前缀表中的与所述路径发生变化的节点对应的各可达前缀的路径。

由上述技术方案可见，本发明这种创建并维护节点表和可达前缀表，在网络链路状态发生变化时，通过重新构建最短路径树获得每个节点的最新路径信息，将最新路径信息与节点表中的旧路径信息进行比较，确定路径发生变化的节点，然后计算所述可达前缀表中的与所述路径发生变化的节点对应的各可达前缀的路径的技术方案，由于分离了节点的路径计算和可达前缀的路径计算，使得在网络链路状态发生变化时无需重新计算全部可达前缀的路径，而只需计算依附于路径发生变化的节点的可达前缀的路径，因此提高了路由计算的效率，并且不需要像ISPF技术那样记录网络中所有节点和链路的信息，也不需要根据链路状态变化的不同类型确定最短路径树上需要重新计算路径的节点和可达前缀，因此较易实现。

附图说明

图1为一棵最短路径树以及依附于树上各节点的叶子的示意图；

图2为NODE与LINK之间的关系示意图；

图3是本发明实施例一种基于链路状态路由协议的路由计算方法的流程图；

图4是本发明实施例节点表和可达前缀表的一种组织形式示意图；

图5是本发明实施例一个组网简单的自治系统的示意图；

图6为图5所示自治系统中的以节点A为根的最短路径树的示意图；

图7是根据本发明中的方案为图5所示组网结构的自治系统生成的节点表和可达前缀表的示意图；

图8为图5所示自治系统中的节点C和D之间的链路发生故障时的以节点A为根的最短路径树的示意图；

图9为本发明实施例一个可达前缀具有多发布源时的示意图；

图10是本发明实施例一种运行链路状态路由协议的网络节点的结构框图。

具体实施方式

本发明的核心在于分离路由计算过程中的节点路径计算过程和可达前缀路径计算过程。由于现有技术中，节点路径计算过程和可达前缀路径计算过程耦合在一起，即重建最短路径树的过程和可达前缀的路由计算过程耦合在一起，每当计算出最短路径树上的一个节点的路径后，就随即确定依附于该节点的可达前缀并计算这些可达前缀的路径，因此，在重建整棵最短路径树的同时就会重新计算所有可达前缀的路径，给系统性能带来了较大的影响。然而在实际应用中，即使重建整棵最短路径树，很多节点的路径都是不变的，而一旦节点的路径不变，依附于该节点的可达前缀的路径也不会发生变化，因此也不需要重新计算这些可达前缀的路径。正因为如此，在本发明中通过分离节点的路径计算过程和可达前缀的路径计算过程来避免一些无谓的计算量，来提高路由计算效率。

为使本发明的目的、技术方案及优点更加清楚明白，以下参照附图并举较佳实施例，对本发明进一步详细说明。

图3是本发明实施例一种基于链路状态路由协议的路由计算方法的流程图。如图3所述，该方法包括以下步骤：

步骤301，创建并维护节点表和可达前缀表；其中，所述节点表中保存有最短路径树上的每个节点的标识和路径信息，所述可达前缀表中保存有所述最短路径树上的每个节点所对应的可达前缀信息。

步骤302，当所述网络中有链路状态发生变化时，通过重新构建最短路径树获得所述每个节点的最新路径信息；将每个节点的最新路径信息与所述节点表中的相应路径信息进行比较，确定路径发生变化的节点；计算所述可达前缀表中的与所述路径发生变化的节点对应的各可达前缀的路径。

当运行链路状态路由协议的网络节点，如路由器等，在网络链路状态变化而需要更新路由表时，根据图3所示的方案计算需要更新的路由，可以大大提高路由计算效率，并且该方法也较易实现。

在图3所示实施例的步骤301中，各网络节点(如路由器等)所创建的节点表和可达前缀表可按图4所示的结构进行组织。图4是本发明实施例节点表和可达前缀表的一种组织形式示意图，如图4所示，节点表中记录了SPT中的每个节点和该节点的路径信息，而节点表中的每一个节点都对应一个可达前缀表，该可达前缀表中记录了依附于该节点的所有可达前缀信息。当然也可以将所有节点的可达前缀表视为一个大的可达前缀表，其中的可达前缀按照其所对应的节点分类保存，这并不影响实现本发明的目的。

在具体实现过程中，节点表可以采用哈希(Hash)表或Radix树的形式来组织，与节点表中的各节点对应的每一个可达前缀表可以采用链表的形式来组织，该链表挂接在对应节点的结构上。当然也可以用其它的方式进行组织，只要能够表示出图3所述的关系结构即可。

在图3所示实施例的步骤301中，所述节点表和可达前缀表可以在LSDB中收到LSA/LSP报文时通过实时解析报文进行创建和维护。其中，根据所接收到的LSA/LSP报文实时创建节点表，初始时由于还不能获知节点的路径信息，因此节点表中只包含节点的标识信息，之后当LSDB中的LSA/LSP报文数量达到预设值或者在预设时间段后，通过现有的Dijkstra算法根据LSDB里描述的拓扑信息构建最短路径树SPT，然后根据该最短路径树获得到达每个节点的路径信息，并将每个节点的路径信息与节点表中的相应节点标识对应保存；并且在接收的新的LSA/LSP报文时，可以对节点表实时地进行维护。而可达前缀表可以在相应的节点表建立之后，根据相关的LSA/LSP报文中携带的可达前缀信息实时创建和维护。

由于在自治系统中每个网络节点(如路由器等)都收集各自的接口/邻居信息并生成相应的包含自身标识的链路状态信息报文(LSA或LSP)在整个自治系统中扩散，使得自治系统中的每个节点都接收到系统内所有节点的链路状态信息并维护一个相同的LSDB。因此，LSDB中有创建节点表所需的拓扑信息和创建可达前缀表所需的可达前缀信息。在不同版本的链路状态协议下，根据不同的链路状态信息报文获得拓扑信息和可达前缀信息，举例如下：

1)网络拓扑信息的获取途径：

当前运行的链路状态协议为IS-IS协议时，根据链路状态报文(LSP)中编码类型为2的中间系统邻居信息字段(Intermediate System Neighbours)和编码类型为22的扩展中间系统邻居信息字段(Extended IS reachability)获取网络拓扑信息；

当前运行的链路状态协议为OSPF协议时，从路由器链路状态通告(Router-LSA)报文和网络链路状态通告(Network-LSA)报文以及自治系统边界路由器链路状态通告(ASBR-Summary-LSA)报文获取网络拓扑信息。具体为：Router-LSA报文中携带的非stub link信息，如p2p link信息以及transit link信息等；Network-LSA报文中的Attached Router以及ASBRSummary LSA等。

当前运行的链路状态协议为OSPFv3协议时，从路由器链路状态通告(Router-LSA)报文、网络链路状态通告(Network-LSA)报文以及区域间路由器链路状态通告(Inter-Area-Router-LSA)报文等获取网络拓扑信息。

2)可达前缀信息的获取途径：

当前运行的链路状态协议为IS-IS协议时，通过解析每个节点生成的LSP报文中的如下字段获取该节点发布的可达前缀信息；

编码类型128，IP内部可达地址前缀信息(IP Internal ReachabilityInformation)；

编码类型130，IP外部可达地址前缀信息(IP External ReachabilityInformation)；

编码类型135，扩展IP可达地址前缀信息(Extended IP Reachability)；

编码类型132，接口IP地址信息(IP Interface Addresses)；

编码类型236，IPv6可达地址前缀信息(IPv6 Reachability Information)；

编码类型232，接口IPv6地址信息(IPv6 Interface Addresses)。

当前运行的链路状态协议为OSPF协议时，通过解析每个节点生成的路由器链路状态通告(Router-LSA)报文、网络链路状态通告(Network-LSA)报文获得该节点发布的本区域内直接可达IP前缀；通过解析每个节点生成的网络摘要链路状态通告(Network-Summary-LSA)报文获得该节点发布的区域间可达IP前缀；通过解析每个节点生成的自治系统外部链路状态通告(AS-external-LSA)报文获得该节点发布的从其他协议引入到OSPF中的可达IP前缀；

当前运行的链路状态协议为OSPFv3协议，通过解析每个节点生成的区域内前缀链路状态通告(Intra-Area-Prefix-LSA)报文获得该节点发布的区域内直接可达的IP前缀；通过解析该节点生成的区域间前缀链路状态通告(Inter-Area-Prefix-LSA)报文获得该节点发布的区域间可达IP前缀；通过解析自治系统外部链路状态通告(AS-external-LSA)报文获得该节点发布的从其他协议引入到OSPFv3中的可达IP前缀。

在本实施例中，可达前缀表可以在收到上述LSA/LSP报文时通过实时解析报文进行维护。

在图3所示的步骤302中，网络节点(如路由器等)在发现网络链路状态发生变化时，通过现有的Dijkstra算法根据自身LSDB里描述的拓扑信息重新构建以自身为根的最短路径树，获得网络中的每个节点的最新路径信息，并将各节点的最新路径信息与节点表中所保存各节点的旧路径信息一一进行比较，找出路径发生变化的节点；然后根据可达前缀表获得依附于这些路径发生变化的各节点的可达前缀，并重新计算这些可达前缀的路径。

下面例举一个具体的例子对上述实施例中的方案进行说明。

图5是本发明实施例一个组网简单的自治系统的示意图。如图5所示，该自治系统包括节点A、B、C和D，此处以节点A的路由计算过程为例进行说明。节点A的端口1与节点B连接，其开销为10，端口2与节点C连接，开销为10；节点B和节点C都与路由D连接，其开销分别为20和10。节点B发布的可达前缀为：10.1.1.0/24，11.1.1.0/24；节点C发布的可达前缀为：20.1.10/24，21.1.10/24；节点D发布的可达前缀为：30.1.10/24，31.1.10/24。则节点A上进行路由计算时，构建以节点A为根的最短路径树，可以得到如图6所示的最短路径树，即图6为图5所示自治系统中的以节点A为根的最短路径树的示意图。根据图6得到从节点A到达节点B、C、和D的路径如表1所示：

  目的节点  出接口  下一跳  开销  节点B  端口1  节点B  10  节点C  端口2  节点C  10  节点D  端口2  节点C  20

表1

则根据图6和表1可得到如图7所示的可达前缀表。图7是根据本发明中的方案为图5所示组网结构的自治系统生成的节点表和可达前缀表的示意图。

如果图5所示的自治系统在某个时刻其节点B和节点D之间的链路发生了故障，则节点A重新构建以自身为根的最短路径树，仍得到如图6所示的最短络路径树，进而仍得到如表1所示的到达各节点的路径信息，将新得到的同表1所示的路径信息与图7所示节点表中记录的各路径信息依次进行比较，会发现所有节点的路径都没有发生变化，因此依附于这些节点的所有可达前缀都不需要重新计算。

或者，如果图5所示的自治系统在某个时刻其节点C和节点D之间的链路发生了故障，则节点A重新构建以自身为根的最短路径树，可得到如图8所示的最短路径树，即图8为图5所示自治系统中的节点C和D之间的链路发生故障时以节点A为根的最短路径树的示意图。根据图8得到从节点A到达节点B、C、和D的路径如表2所示：

  目的节点  出接口  下一跳  开销  节点B  端口1  节点B  10  节点C  端口2  节点C  10  节点D  端口1  节点B  30

表2

将新得到的如表2所示的路径信息与图7所示节点表中记录的各路径信息依次进行比较，会发现节点D的路径发生了变化，因此只需要重新计算依附于节点D的所有可达前缀的路径即可。

还需要说明的是在多个节点发布同样的可达前缀的情况下，通过图3所示的步骤针对同一个可达前缀会计算得到多条经过不同发布源的路径，因此需要根据路径信息中已经记录的协议内部路由选优所需要的所有关键信息对这些路径信息进行重新选优，得到最终的最优路由。

图9为本发明实施例一个可达前缀具有多发布源时的示意图。如图9所示，由于节点B和C同时发布了11.3.1.1/24网段，所以11.3.1.1/24网段同时依附于节点B和C，通过节点B和C可以分别算出到达11.3.1.1/24网段的两条不同路径，此时就需要根据现有的协议内部路由选优算法对这两条不同路径进行选优。其中OSPF/OSPFv3/ISIS协议内部路由选优所需要的关键信息以及选优的具体方法都是现有技术，这里不再详细描述。

基于上述实施例接下来给出本发明一种运行链路状态路由协议的网络节点的组成结构。

图10是本发明实施例一种运行链路状态路由协议的网络节点的结构框图。如图10所示，该网络节点包括：创建维护模块1001、存储模块1002和路由计算模块1003，其中：

创建维护模块1001，用于在存储模块1002中创建节点表和可达前缀表，并进行维护；其中，所述节点表中保存有以所述网络节点为根的最短路径树上的每个节点的标识和路径信息，所述可达前缀表中保存有所述最短路径树上的每个节点所对应的可达前缀信息；

存储模块1002，用于存储节点表和可达前缀表；

路由计算模块1003，用于在网络中有链路状态发生变化时，通过重新构建以所述网络节点为根的最短路径树获得网络中的每个节点的最新路径信息，将每个节点的最新路径信息与存储模块1002中的节点表中的相应路径信息进行比较，确定路径发生变化的节点；然后计算存储模块1002中的可达前缀表中的与所述路径发生变化的节点对应的各可达前缀的路径。

如图10所示的网络节点还包括：链路状态数据库LSDB 1004，在图10中用虚线框表示，用于保存拓扑信息和可达前缀信息；创建维护模块1001，用于根据链路状态数据库LSDB中的拓扑信息创建包含各节点标识的节点表，并利用Dijkstra算法根据LSDB 1004中的拓扑信息构建最短路径树，根据该最短路径树获得每个节点的路径信息后与节点表中的相应节点标识对应保存；用于在LSDB 1004中的拓扑信息有变化时，相应更新所述节点表中的内容；用于利用LSDB 1004中的各节点的可达前缀信息创建可达前缀表，并在LSDB 1004中的可达前缀信息有变化时，相应更新所述可达前缀表中的内容。

如图10所示的网络节点，其创建维护模块1001，在网络节点所运行链路状态路由协议为IS-IS协议时，用于根据LSDB中的链路状态报文LSP中的编码类型为2的中间系统邻居信息字段和编码类型为22的扩展中间系统邻居信息字段的信息构建最短路径树；在网络节点所运行的链路状态路由协议为OSPF协议时，用于根据LSDB中的路由器链路状态通告Router-LSA报文和网络链路状态通告Network-LSA报文以及自治系统边界路由器链路状态通告ASBR-Summary-LSA报文中的信息构建最短路径树；在网络节点所运行的链路状态路由协议为OSPFv3协议时，用于根据LSDB中的路由器链路状态通告Router-LSA报文、网络链路状态通告Network-LSA报文以及区域间路由器链路状态通告Inter-Area-Router-LSA报文中的信息构建最短路径树。

如图10所示的网络节点，其创建维护模块1001，在网络节点所运行的链路状态路由协议为IS-IS协议时，用于根据LSDB中的编码类型为128、130、135、132、1310和232的字段信息创建可达前缀表；在网络节点所运行的链路状态路由协议为OSPF协议时，用于根据LSDB中的由每个节点生成的路由器链路状态通告Router-LSA报文、网络链路状态通告Network-LSA报文、网络摘要链路状态通告Network-Summary-LSA报文以及自治系统外部链路状态通告AS-external-LSA报文中的信息创建所述可达前缀表；在网络节点所运行的链路状态路由协议为OSPFv3协议时，用于根据LSDB中的由每个节点生成的区域内前缀链路状态通告Intra-Area-Prefix-LSA报文、区域间前缀链路状态通告Inter-Area-Prefix-LSA报文和自治系统外部链路状态通告AS-external-LSA报文中的信息创建所述可达前缀表。

如图10所示的网络节点，其创建维护模块1001，用于采用哈希表Hash或者Radix树的形式来组织所述节点表，采用链表的形式组织所述可达前缀表。

图10所示的网络节点具体可以为路由器设备。

由上实施例可见，本发明这种创建并维护节点表和可达前缀表，在网络链路状态发生变化时，通过重新构建最短路径树获得每个节点的最新路径信息，将最新路径信息与节点表中的旧路径信息进行比较，确定路径发生变化的节点，然后计算所述可达前缀表中的与所述路径发生变化的节点对应的各可达前缀的路径的技术方案，由于分离了节点的路径计算和可达前缀的路径计算，使得在网络链路状态发生变化时无需重新计算全部可达前缀的路径，而只需计算依附于路径发生变化的节点的可达前缀的路径，因此提高了路由计算的效率。并且不需要像ISPF技术那样记录网络中所有节点和链路的信息，也不需要根据链路状态变化的不同类型确定最短路径树上需要重新计算路径的节点和可达前缀，大大降低了实现复杂度。

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