最短路径树与生成树结合的节能路由方法

摘要

最短路径树和生成树结合的路由方法属于网络拓扑中的技术领域，其特征在于,在标准链路状态路由协议的基础上，网络中路由器节点所连接的每条链路增加休眠状态，在给定的网络拓扑上选定一棵共享的生成树，其上的链路始终处于工作状态以确保网络连通，其他不在生成树上的链路若没有流量经过则进入休眠状态，每个路由器保存全网路径的最短路径路由表和对应生成树的路由表，对于一个数据包，入口路由器根据当前链路负载决定数据包采用其中一种路径，并增加标签标识，非入口路由器根据标签选择相应路由表进行转发。

说明书

技术领域

绿色网络

背景技术

绿色网络是当今网络研究的一个重要方向，互联网的巨大能耗问题以 及低效能量使用问题日益凸显。为了更加有效的利用能源，减少能量 浪费，利用链路休眠机制实现网络节能的研究正在得到学术界和工业 界越来越多的关注。在一般Internet Service Provider(ISP)网络 中，为了应对流量巅峰和潜在链路故障，在网络搭建和升级时期，网 络运营商通常会部署冗余链路和增大冗余链路带宽，而实际日常网络 中大部分的时候网络负载不高，导致链路平均利用率偏低，而路由器 功耗相比全负荷运行状态并无减小。这些因素都会造成网络中的能量 浪费问题。

链路状态路由协议是现在常用的域内路由协议，该协议的路由器计算 的路径为最短路径，由于该协议设计之初并没有考虑到能耗等因素， 导致了ISP网络上链路的利用率低，大量的能量浪费的问题。本发明的 目的在于改进传统的标准链路状态路由，采用生成树（ST：spanning  tree）和最短路径树（SPT：shortest path tree）结合的节能机 制，把流量聚集到尽可能少的链路上，其余链路进入空闲休眠状态来 达到节能。

发明内容

本发明的目的在于用两种不同的路径最短路径和生成树路径构造一个 新型的节能路状态路由方法，把流量聚集到生成树上，使得更多链路 进入休眠状态，实现节能目的的同时，提高平均链路利用率，减少能 量浪费。

本发明的特征在于：

1.网络拓扑上依次按以下步骤实现：

步骤(1)，网络拓扑初始化：在标准链路状态路由协议的基础上，对其 中各个路由器节点连接的每条链路上增加休眠状态；

步骤(2)，每个路由器节点周期性地检测所有直连链路的负载情况，使 用开放式最短路径优先协议OSPF本身的链路状态通告机制LSA把链路负 载信息连同链路状态信息一起洪泛到网络拓扑上，使得所述网络拓扑 上的每个路由器节点均拥有完全相同的网络拓扑信息和链路负载信息 ；

步骤(3)，每个路由器节点根据从步骤(2)得到的结果计算自己到网络 拓扑上其他任一路由 器节点的最短路径和生成树路径，生成路由表，而且所有路由器节点 的计算结果是一致的；

步骤(4)，所述网络拓扑上的每个路由器节点依据数据流经过的路径上 链路负载的情况，按目的地址为每一条数据流选择一条合适的路径， 选择相应路由表，并把选择结果作为标签添加到数据报文的头部，再 按“目的地址+标签”进行转发，根据标签在路由表中决定路由下一跳 ；

步骤(5)，当下游路由器节点收到由上游路由器转发的带有标签的报文 后，根据标签选择下一跳，按“目的地址+标签”的格式进行转发；

步骤(6)，核心路由器节点接收到一个报文后，检查转发端的链路，若 转发段端路正常，则按标签正常转发，若发现转发端的链路正处于休 眠状态时，需要把该休眠链路唤醒，再将该数据报的标签修改为生成 树的标签进行转发，直到到达目的路由器。

2．根据权利要求1所述的最短路径树与生成树结合的节能路由方法， 其特征在于，在所述生成树上再构造一个供实际采用的在线子图，其 上的每一个路由器节点都在所述生成树的某一个链路上，还要包含最 少的数目的边，以防止单链路失效。

本发明所提出的方法的思路在于：在标准链路状态路由协议的基础上 ，对路由器节点所连接的每条链路增加休眠状态。在给定的网络拓扑 上制定一个连通子图，连通子图上的链路始终处于工作状态，连通子 图外的其他节点如果持续一段时间没有流量经过则进入休眠状态。路 由器通过在连通子图上构建一棵生成树，将流量汇集生成树上，使得 进入休眠的链路更多以达到节能的效果。

本发明所提出的方法的优点在于：

1.采用分布式算法，每个入口路由器根据搜集到的链路负载信息独立 进行决策；

2.能够快速对网络负载变化作出实时响应，流量在最短路径树和生成 树之间快速切换；

3.在网络节能效率和网络负载弹性之间取得良好的平衡。

附图说明

图1. 全局拓扑和生成树/连通子图，

图1.1全局拓扑，

图1.2生成树/连通子图（粗线部分）。

图2．“目的地址+标签”转发示意图。

图3．标签重置示意图。

图4. 路由协议流程图，

图4.1 路径选择流程图，

图4.2 数据包转发流程图。

具体实施方式

如图1.1所示，节能效率与网络弹性矛盾的一个极端情况就是当所有链 路均处于工作状态，这时候网络能耗最大，但同时也最可靠和富有弹 性，能够应对突发流量尖峰和链路故障。另一个极端情况见图1.2是在 一个包含所有节点的连通子图上的所有链路处于工作状态，其他链路 均处于休眠状态。如果在线子图取为一棵生成树，则此时候网络节能 效率最高，但同时也是最脆弱的。一个考虑周全的节能路由协议应该 不仅考虑节能效率，同时应该全面考虑网络弹性和全局网络性能。此 外，因为链路状态切换是基于实时流量需求，我们的节能路由协议需 要能够快速做出决策，并在全拓扑范围内保持一致性。我们研究的节 能路由协议主要思路是根据网络实际流量负荷情况，在两种极端情况 之间实现尽可能平滑的切换。流量需求低的时候，尽量利用生成树上 的链路传递流量，使节能率最大化；流量需求增长的时候，逐渐地把 流量从生成树上搬移到全局拓扑上，唤醒必要的链路以保持网络弹性 和性能，直到所有流量都选取最短路，这时候协议自动收敛到OSPF的 情形。我们研究的节能路由协议的关注点在于使得这样的切换尽可能 的平滑，使丢包率和乱序最小化，以至于对上层协议应用来说由于节 能带来的影响最小化。

工作流程：

i）首先每个路由器周期性地检测直连链路的负载情况，并将该链路负 载信息连同链路状态信息一起洪泛到全网络，可以使用OSPF本身的LS A洪泛机制实现。

ii）至此，拓扑上每一路由器均拥有完全相同的网络拓扑信息和链路 负载信息，通过拓扑信息，路由器可以计算出自己到网络其他任一节 点的最短路径和生成树路径，而且由于使用的相同的拓扑，统一的算 法，所以所有路由器计算路径结果是保持一致性的，满足最优子结构 特性。

iii）然后，每个入口路由器依据数据流经过的路径上链路负载状况， 为以其为入口的每一条流选择合适的路径，并将选择结果作为标签添 加到数据报文头部，然后根据“目的地址+标签”进行转发，见图2。

iv）当下游节点接收到上游转发的带标签报文，直接根据“目的地址 +标签”进行转发。

v）当遇到转发端口链路正处于休眠状态时，为了保证流的连续性，在 链路被唤醒期间，转发节点会把数据包的标签重置为沿生成树的标签 再路径转发，链路唤醒后不再进行标签重置，见图3。

为提高网络拓扑的可靠性，实际采用的在线子图应该是在生成树的基 础上一定程度地增大冗余度，一种可行的方案是寻找这样一个子图使 得每个节点都在某一个环上，同时包含最少数目的边，这样的在线子 图可以有效应对单链路失效的情况。

我们在3个真实的拓扑上进行了实验，发现生成树和最短路径树结合的 节能机制在链路利用率较低时可以节省20%~50%的线卡消耗能量，说明 本发明达到了预期的目的。