一种在OSPF协议中改进路由算法的网络级节能方法

摘要

本发明公开了一种在OSPF协议中改进路由算法的网络级节能方法。本发明通过将能耗因素值加入到路由协议中，通过对OSPF协议中SPF算法的修改，具体如下：步骤1.在路由器中设置能耗因素值；能耗因素值用于记路由器的能耗，该能耗因素值P

说明书

技术领域

本发明涉及到路由器能耗差的计算，利用Dijkstra算法的改进来节能。

背景技术

当今世界，由于能源紧张和许多资源的不可再生，国际社会逐渐注重节能 减排的理念。据统计数据显示，2010年全球以太网的接入节点数已超过30亿， 而与之相连的交换机、路由器等设备的数量也同样庞大。在由服务器、路由器、 存储和交换机等IT设备构成的整个网络系统中，服务器的耗能量是不可忽视 的。而路由器作为互联网络的枢纽，根据美能源部备忘录公布的估算数据，1999 年美国Internet相关的电量消耗约在36TW-h，路由器的功耗就达5.2TW-h。

随着人们对如何提高能量有效利用率，控制网络系统电量的大力关注，研 究人员已提出一系列节能机制和措施。我们可以从网络粒度的角度对现有的节 能策略进行分类：节点级节能策略，网络级节能策略。目前，在网络全局的角 度提出的对网络协议修改的节能策略已有许多，但各有缺陷。

本文发明提出一种针对网络级节能策略，并在有线网络中将能耗作为节点 间第二权重的绿色路由算法，首先对网络中不同设备能耗的分析，可观察到不 同内部配置的路由器对于能耗的影响也是不同的，获得不同路由器的科学的功 耗值。其次，在OSPF中设置一个新的参数，改进路由算法使传输路径的能耗最 小化，从而实现节能。

发明内容

本发明提出了一种在OSPF(OpenShortestPathFirst开放式最短路径优 先)协议中改进路由算法的网络级节能方法。通过将能耗因素加入到路由协议 中，通过对OSPF协议中SPF算法的修改，使得路由器在执行Dijkstra算法时 在产生的所有等价路径中选择能耗差最小的路由路径，在网络轻负载期间应用 到大规模的网络时具有较为显著的节能效果。包括路由器在有无数据包经过时 的能耗差，产生多条最短路径的改进Dijkstra算法。

本发明解决其技术问题所采用的技术方案包括如下步骤：

步骤1、在路由器中设置能耗因素值；能耗因素值用于记路由器的能耗， 该能耗因素值P_m计算如下：

P_m(X)＝P_t(X)-P_i(X)

其中X代表路由器的型号，Pt有数据包经过时路由器的耗能，Pi为空闲 状态的耗能。

步骤2、通过对OSPF协议中SPF算法的修改，使得路由器在执行Dijkstra 算法时产生的所有等价路径中选择能耗因素值总和最小的路由路径，具体修改 如下：

2-1.在优先队列类中定义一个代表能耗变量的能耗因素值P_m；

2-2.在lsa头文件的Link类中添加变量l_fwdcst2，l_fwdcst2用于存储 一条链路的forwardcost2。

2-3.初始化数据结构，清除候选列表，初始化最短路径树使其只包含树根；

2-4.设V为新加入最短路径树的节点，扫描该初始节点V的所有邻居节点， 并依次将扫描到的邻居节点W加入候选列表；

2-5.判断邻居节点W是否在最短路径树上，如果邻居节点W的标记状态显 示在最短路径树上，则检查该邻居节点W的下一个链接并计算 链路代价总和值new_cost＝V→cost0+tlp→l_fwdcst；节点能耗总 值new_cost2＝V→cost2+tlp→l_fwdcst2；

2-6.若邻居节点W在最短路径树上，则继续判断该邻居节点W是否在候选 列表中；

2-6-1.若邻居节点W的标记状态显示在候选列表中，则判断所得的 new_cost是否大于候选列表中该邻居节点W的链路代价值cost0，如果 new_cost大于cost0，则继续检查该邻居节点W的下一个链接；如果 new_cost小于cost0，则在候选列表中删除该邻居节点W；如果new_cost 等于cost0，则判断到邻居节点W为止的节点能耗总值new_cost2是否 小于该邻居节点W本身已有的节点能耗值cost2。如果new_cost2大于 cost2，则直接使用所宣告的链接计算下一跳。如果new_cost2小于 cost2，则对new_cost和new_cost2重新赋值，具体如下：new_cost＝W →cost0，new_cost2＝W→cost2。

其中，V→cost0表示初始节点V的链路代价值，tlp→l_fwdcst表示邻 居节点W的下一个链接的代价；V→cost2表示初始节点V的能耗值， l_fwdcst2表示邻居节点W的能耗值；W→cost0表示邻居节点W的链路 代价值，W→cost2表示邻居节点W的能耗值；

2-6-2.若该邻居节点W不在候选列表中，或new_cost小于W→cost0 时，将W加入候选列表，使用所宣告的链接计算下一跳，并以此设定邻 居节点W的下一跳值。

2-7.如果候选列表为空，表明最短路径树就被构建完成，结束本次最短路 径树构建。否则，在候选列表中选择最靠近树根的节点，将其加入最短 路径树，同时在候选列表中删除该节点；

2-8.递归调用步骤2-4～步骤2-6。

本发明有益效果如下：

1.本发明的技术方案相对于其他的节能方案复杂度更低，不影响网络的性 能。2.本发明适用于网络的全时间段，不涉及不同时间段路由协议的切换。3. 在保证QOS的前提下与原本的OSPF路由协议相比本发明的节能效果较为显著。

附图说明

图1为OSPF绿色路由器模型；

图2(a)为最短路径选择示意图；

图2(b)为最短路径选择示意图；

图2(c)为最短路径选择示意图；

具体实施方式

下面根据附图详细说明本发明，本发明的目的和效果将变得更加明显。

如图1、2所示，一种在OSPF(OpenShortestPathFirst开放式最短路 径优先)协议中改进路由算法的网络级节能方法。通过将能耗因素加入到路由 协议中，通过对OSPF协议中SPF算法的修改，使得路由器在执行Dijkstra算 法时在产生的所有等价路径中选择能耗差最小的路由路径，在网络轻负载期间 应用到大规模的网络时具有较为显著的节能效果。包括路由器在有无数据包经 过时的能耗差，产生多条最短路径的改进Dijkstra算法。

本发明解决其技术问题所采用的技术方案包括如下步骤：

步骤1、在路由器中设置能耗因素值；能耗因素值用于记路由器的能耗， 该能耗因素值P_m计算如下：

P_m(X)＝P_t(X)-P_i(X)

其中X代表路由器的型号，Pt有数据包经过时路由器的耗能，Pi为空闲 状态的耗能。

步骤2、通过对OSPF协议中SPF算法的修改，使得路由器在执行Dijkstra 算法时产生的所有等价路径中选择能耗因素值总和最小的路由路径，具体修改 如下：

2-1.在优先队列类中定义一个代表能耗变量的能耗因素值P_m；

2-2.在lsa头文件的Link类中添加变量l_fwdcst2，l_fwdcst2用于存储 一条链路的forwardcost2。

2-3.初始化数据结构，清除候选列表，初始化最短路径树使其只包含树根；

2-4.设V为新加入最短路径树的节点，扫描该初始节点V的所有邻居节点， 并依次将扫描到的邻居节点W加入候选列表；

2-5.判断邻居节点W是否在最短路径树上，如果邻居节点W的标记状态显 示在最短路径树上，则检查该邻居节点W的下一个链接并计算 链路代价总和值new_cost＝V→cost0+tlp→l_fwdcst；节点能耗总 值new_cost2＝V→cost2+tlp→l_fwdcst2；

2-6.若邻居节点W在最短路径树上，则继续判断该邻居节点W是否在候选 列表中；

2-6-1.若邻居节点W的标记状态显示在候选列表中，则判断所得的 new_cost是否大于候选列表中该邻居节点W的链路代价值cost0，如果 new_cost大于cost0，则继续检查该邻居节点W的下一个链接；如果 new_cost小于cost0，则在候选列表中删除该邻居节点W；如果new_cost 等于cost0，则判断到邻居节点W为止的节点能耗总值new_cost2是否 小于该邻居节点W本身已有的节点能耗值cost2。如果new_cost2大于 cost2，则直接使用所宣告的链接计算下一跳。如果new_cost2小于 cost2，则对new_cost和new_cost2重新赋值，具体如下：new_cost＝W →cost0，new_cost2＝W→cost2。

其中，V→cost0表示初始节点V的链路代价值，tlp→l_fwdcst表示邻 居节点W的下一个链接的代价；V→cost2表示初始节点V的能耗值， l_fwdcst2表示邻居节点W的能耗值；W→cost0表示邻居节点W的链路 代价值，W→cost2表示邻居节点W的能耗值；

2-6-2.若该邻居节点W不在候选列表中，或new_cost小于W→cost0 时，将W加入候选列表，使用所宣告的链接计算下一跳，并以此设定邻 居节点W的下一跳值。

2-7.如果候选列表为空，表明最短路径树就被构建完成，结束本次最短路 径树构建。否则，在候选列表中选择最靠近树根的节点，将其加入最短 路径树，同时在候选列表中删除该节点；

2-8.递归调用步骤2-4～步骤2-6。

如图1所示，本发明使用OSPF绿色路由器，且将路由器接口信息进行修改， 接口将设置一个路由器能耗的参数(powermarginofrouter)，控制层面将使用改 进的节能Dijkstra算法进行路由选择。

如图2(a)-2(c)所示，选择路由器总能耗差最小的最短路径：在多条最 短路径中选取最小总路由器能耗差的路径。如图2(c)所示，其中虚线路径为 总能耗差最小的。