一种基于动态聚合树模型的路由方法

技术领域

本发明属于网络通信技术领域，涉及一种点对点的动态网络通信技术，特别涉及基于网 络动态拓扑结构及链路权值随时间变化的分布式路由方法。

背景技术

随着Internet规模的不断扩大，多样化的组网设备层出不穷。这些设备构成了通信网络 中的一个个自治系统，为了使这些自治系统内部和自治系统之间形成高效低成本的通信，就 需要进行数据路由。系统中所有设备，共同遵守同一套的路由规则，使用相同的路由信息表 述和存储方法。

在现有的技术中，路由协议是解决数据路由的主要技术手段。路由协议基于抽象的网络 模型来计算网络中节点对之间的最优路径。按照最优路径的计算方式，路由协议可以分为两 大类：链路状态路由和距离矢量路由。在链路状态协议的运行过程中，网络中的每台负责交 换路由信息的设备(路由器、交换机等)都维护着整个网络的路由结构信息，并根据这些信 息使用相应的路由算法计算最优路径并生成路由表。距离矢量路由协议在使用过程中则不需 要维护整个网络路由信息，分布式路由的信息仅在邻居节点之间传递，并在每个节点的使用 分布式路由算法获得路由表。目前在Internet上使用最普遍的两种路由协议是：RIP( Routing Information Protocol，路由信息协议)和OSPF(Open Shortest Path First， 开放式最短路径优先协议)。其中，RIP协议是距离矢量路由协议，使用分布式 Ford-Bellman算法。它具有简单、可扩展性高的特点，但收敛速度较慢。OSPF协议是典型地 链路状态路由协议，使用Dijkstra算法。它有效的提高了路由信息汇聚的速度和准确性，因 而减小了网络阻塞的几率，提高了网络的整体效率。但OSPF协议过于庞大，对路由设备有相 当高的要求。

目前，随着电信业务的引入，IP网的服务质量(IP QoS)成为下一代Internet的重要研 究课题。QoS路由的目标也是一个通过当前路由器路由表寻从源节点到目的节点的最优路 径的问题。为了解决QoS路由算法随网络规模的增大所需的执行时间和存储需求提高的问题 ，拓扑结构分层聚合的思想被广泛的应用在大规模的网络中。拓扑聚合的过程是将网络中每 个域会聚成具有该域信息的一个简单的拓扑。这一思想虽然大大地简化了路由表的大小，但 是网络的在动态改变后产生了路由信息的不精确性。而在这一思想上延伸的各种动态最短路 径树问题得到了很高的成效。但是现存的最短路径树路由模型研究在网络动态改变后，仍然 需要冗余的计算和具有不准确的信息，因而基于这些协议的网络路由过程必然不能获得符合 实际的精确优化结果和很高的路由效率。因此建立符合实际的高精确性高路由效率并切合实 际流量情况的路由方案、研究适合于大规模网络动态改变的路由协议成为一个迫切需要解决 的问题。

发明内容

本发明的目的是提供一种能够有效为目前的互联网骨干网自治域提供准确切合实际流量 情况的高精确性高路由效率，并且可以动态自制更新的路由方法。

本发明的技术解决方案是，在至少存在两个具有路由承载功能的通信设备组成的数据通 信网络中，分别使用如下所述的本发明运行方案。数据通信网的拓扑可以是分布式网络或环 形网络。网络传输媒介可以使用包括光纤、数字微波、普通同轴电缆、双绞线等多种。通信 网络的物理层和数据链路层可以使用多种接口，以支持用户的不同接入方式。本发明的技术 方案工作在网络层。由于本发明所使用的模型及路由算法对网内设备的处理器、内存资源的 占用比较小，低档路由器甚至软路由设备均可以使用。

本发明是一种适合于互联网骨干网自治域使用的路由方法。该方法使用现有的硬件路由 设备为基础，适用于路由器和具有软路由功能的设备。

本发明的技术方案包括以下步骤：

1.路由设备根据预留磁盘空间记录历史流量数据和操作记录，以文件形式存储在外部 存储器上，如硬盘等。

2.路由设备通过外部接口接受用户设定，确定需要路由的起始时间以及路由量度变化 的单位时段并由路由协议程序统一管理。

3.由路由设备运行路由协议程序，根据本发明设计的动态聚合树网络模型，在路由设 备的内部高速存储器内存中构建新型的路由表。该路由表由两个子表组成，分别存储有本路 由节点到其它路由节点的路径量度(Metric)和下一条信息。

对于每台路由设备，其具体需要维护的信息如下：

数组D，每个元素Dj是从当前节点到目的地址j最短路径的权值。

数组P，每个元素Pj是从当前节点到目的地址j最短路径的下一跳。

4.由路由设备运行路由协议程序，根据本发明设计的动态聚合树网络模型，针对通信 网内路由设备的不同类型，按照路由器间的链路参数将各链路分属聚合树的不同层次域中。 在路由设备的内部存储器(如内存)中构建路由子表。从聚合树网络模型的角度，目前的网 络通信设备可以根据其是否是关联节点(联系不同层次域的节点)分为两类，对于非关联节 点，它的路由表仅包括从该节点到该节点所在域的每个节点的信息；对于关联节点，它的路 由表不但包括从该节点到该节点所在域的每个节点的信息，还包括从该节点到其它关联节点 的信息。具体需要维护的信息如下：

集合V，路由信息，每个元素V是从当前节点到目的地址j最短路径的最近一次计 算的权值。

5.由路由设备运行路由协议程序，根据本发明设计的动态聚合树网络模型，在路由设 备的高速存储器，如高速缓存等，构建高速路由缓存表。对于每台路由设备，必须在高速存 储器，如内存，flashmemory等，上存储该表，高速存储器为内存、flash memory等。其具 体需要维护的信息如下：

表T，二维缓存表，每个元素Tkj是从当前节点路经邻居节点k到达目的地址j最短路径 的权值。

6.路由设备从外部接口接受用户输入，确定每条物理网络接口的物理标识和接口标识 ，用以唯一确定数据发送单元，即邻居，并在路由设备的内部存储器上，运行路由协议程序 构建邻居信息列表。

7.每个数据发送单元有路由协议程序控制，根据确定的时间间隔向邻居发送探测数据 包，用以确定链路的的状态。

8.当路由设备在收到由邻居发送的新的路由表信息时，从网络设备(如网卡)的缓冲 区中取得新的路由信息，送路由设备的内部存储器，并由处理器运行路由协议程序，根据本 发明设计路由表信息更新算法来更新相应的高速缓存表项。并判断是否需要触发路由表计算 。

9.如需要进行路由表的计算，则由路由协议程序根据本发明设计的路由表更新算法进 行路由表的更新。在更新的过程中，将更新的表项记录在路由设备的内部存储器中，并根据 本发明设计的路由状态信息格式，组织被更新的路由表项，形成路由数据包，由路由设备的 网络接口发送给邻居。

10.路由设备根据当前时间段的变化运行路由协议程序自动更新当前路由表。

11.路由设备每隔一段时间通过物理网络接口向邻居发送下N个时段的路由信息，N因 具体的网络环境而异，本发明设计缺省值为4。

由上述技术路线可知，本发明是一种基于动态聚合树网络模型的路由方案。在保持原有 路由设备硬件架构的基础上，设计了全新的网络路由模型及增量算法，并根据此模型形成了 一套完整新颖的路由技术。

本发明所达到的有益效果和益处是，设计的动态聚合树网络模型能够准确的描述网络的 实际运行状态，有效的描述了网络中链路状态随时间的变化。在这一模型的基础上，本发明 设计了适合该模型的分布式距离矢量类的路由协议。该协议的优势在于高精确性高路由效率 、收敛性能好、运行效率高、对路由设备的资源占用小、可以有效的降低路由设备的成本， 减少研发和维护费用，符合QoS路由的目标。本发明的路由方案适用于大规模网络链路的拓 扑结构随时间变化及链路权值随时间变化的情况，其中基于动态聚合树模型所设计的路由信 息更新算法，有效的解决了传统路由方法不能解决的大规模网络中链路状态及拓扑结构随时 间变化的问题，更加合理的分配了网络流量，提高了网络的实际吞吐量。

附图说明

下面结合附图和具体实施方式对本发明作进一步的说明。

图1为本发明使用的网络类型示意图。

图2为本发明路由方案基本流程图。

图3为本发明路由信息数据包格式图。

图4为本发明路由数据探测包格式图。

图5为本发明动态聚合树生成流程图。

图6为本发明路由信息更新算法流程图。

具体实施方式

本发明所述的路由方案，以现有的路由设备为应用对象，适合于目前的互联网骨干 网自治域使用。该方案主要由动态聚合树的网络模型和基于该模型的增量算法以及一整套路 由技术组成。这套路由技术主要由一种路由状态预测方法和一个使用动态聚合树模型的路由 协议组成。

本发明所述的动态聚合树网络模型具体描述如下：

任何一个网络均可划分成若干个称之为域的不规则区域，这个域是原网络的子网络并构 成聚合树的一个节点。聚合树是n(n＞0)个域的有限集合，在非空的聚合树中：(1)有且 仅有一个特定的域为聚合树的根；(2)当n＞1时，其余域可分为m(m＞0)个有限集合 T1，T2，…，Tm，并且i≠k，1≤i，k≤m，Ti∩Tk∈V，其中每一个集合本身又是一棵聚合树 ，并且称为根的子树。原网络中的链路根据其参数的取值赋予不同级别，而聚合树的层次正 是通过这一级别来划分的。各域通过关联节点联系。当网络的链路状态发生改变时，相关的 路由器调用增量算法更新网络的状态及受到影响的路由器的路由表。当网络中某个路由器收 到的数据包表明它所连接的链路参数发生改变时，触发该算法识别受到影响的所有路由器及 链路，然后对这些受到影响的路由器的路有表中各信息进行更新。

本发明的路由协议执行过程具体步骤描述如下：

1.路由设备初始化路由表。路由表分为三个子表，分别是：

量度路由子表D，一个一维数组，由目标地址索引，每个元素Dj是从当前节点到目的地 址j最短路径的权值。

下一跳路由子表P，一个一维数组，由目标地址索引，每个元素Pj是从当前节点到目的 地址j最短路径的下一跳。

发送路由子表V，一个路由信息的集合，每个元素V是从当前节点到目的地址j最 短路径的最近一次计算的权值。

2.设置本路由设备各个物理网络接口的物理标识和接口标识，并以此唯一确定邻居路 由设备，同时插入邻居信息队列。

3.根据初始化的路由表，生成高速路由二维缓存表T。该表由邻居节点、目标地址索引 表项，每个元素Tkj是从当前节点路经邻居节点k到达目的地址j最短路径的权值。

4.将路由表表项内容打包为路由信息数据包，包中包含的字段有：协议标号、包大小 (byte)、路由表更新项数、路由表项更新内容。其中，路由表项更新内容为目的地、路径 量度组成的一个二元组(j，Dj)。具体数据包格式见附图3。

5.启动时间路由信息时段定时器timer1，有效时间根据具体网络环境确定，本发明建 议缺省值为40秒。

6.向各个邻居发送路由探测数据包。路由探测数据包分为主动探测和答复探测两类， 由包中的类型字段标识，具体格式见附图4。

7.启动邻居探测发送定时器timer2，有效时间根据具体网络环境确定，本发明建议缺 省值为10秒。

8.路由设备接到路由数据包后，首先执行网络分割算法，形成聚合树模型。运行完这 一算法，每个节点都掌握了其子域节点的信息。节点地址由关联节点从根域开始递归分配。 具体的流程见附图5

9.然后执行聚合树路由算法，分三个过程：

9. 1初始化。每个路由器n在接到邻居节点i的路由数据包后，进行分类处理：

如果i为节点地址信息，那么初始化n的节点类路由表信息；如果i为域地址信息，那么 初始化n的域类路由表信息。然后形成发送路由信息发送给邻居节点。

9. 2缓存表和路由表更新算法，当缓存表中的路由或是权值有改变，形成发送路由信 息发送给邻居节点更新路由表信息。路由设备将接到的路由数据包进行分类处理：

如果是路由探测数据包转步骤9.2.1。

如果是路由信息数据包转步骤9.2.2。

9. 2.1如果是路由探测数据包，判断该包的类型并执行相应动作：

如果是主动探测包，则向包的发送接口回复答复探测包，内容中包括本路由单元的物理 和接口标识。

如果是答复探测包，取出其中的邻居信息，检测邻居信息队列相应内容，判断是否需要 更新。

9. 2.2如果是路由信息包，进行高速路由缓存表的更新，具体分以下几步：

(1)按顺序取下一个路由信息包中的更新路由表项。对于更新路由表项中V的每一个元 素，如果高速路由缓存表中不存在Tij，那么将Vij赋值为加入集合V中 。

(2)如果Tij＞cost+Di，那么将Tij更新为cost+Di，并设置标号flag为true

(3)如果flag为true，那么对每一个目标地址j作如下操作：

如果Dj≠≠minTij并且Pj≠≠i，那么Dj←Tij，Pj←i，V←；

(4)结束

9. 3路由信息的会聚，各路由器将收到的路由信息收集，进行路由表的重新计算。

(1)当收到的路由信息为域类地址信息：如果邻居节点是当前节点的子域，那么除了 这一子域的信息外，其余信息都发送。其它情况下，发送所有信息。

(2)当收到的路由信息为节点类地址信息：发送所有信息给同域、父域的邻居节点。 对于邻居节点在子域的情况，除了子域信息外的其它信息都发送。

具体流程见附图6

10.当某个路由器收到的数据包表明与它相连的链路状态发生改变时，则触发增量算法 更新网络的状态及受到影响的路由器的路由表。识别受到影响的所有路由器及链路，然后对 这些受到影响的路由器的路有表中各信息进行更新。

11.如果timer1到时，则向邻居广播下N时段的本地路由表。N的值根据具体网络环境确 定，本发明建议缺省值为4。

12.如果timer2到时，向每个物理接口发送路由探测数据包。同时启动探测包计时 timer3，如果在timer3到时后，还没有收到回复类型的路由探测数据包，确定该路径为断路 ，更新该邻居的路由缓存表项为无穷大，转步骤6。