面向主干网的网络级绿色节能机制∗

张金宏 , 王兴伟 , 易 波 , 黄 敏

1(东北大学 计算机科学与工程学院,辽宁 沈阳 110169)

2(东北大学 信息科学与工程学院,辽宁 沈阳 110819)

近些年,随着互联网用户数持续增长和云存储、物联网等新技术和新模式的不断涌现和发展,急剧增长的互联网流量呈现出全球化趋势,预计全球网络年流量将从2017 年的1.5ZB 上升到2022 年的4.8ZB(Cisco Systems.Cisco visual networking index:Forecast and trends,2017～2022.2019.https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/white-paper-c11-741490.html).为此,网络运营商不得不频繁增加网络设备数量和升级网络设备性能来容纳新增的网络流量;同时,不得不相应地增强支撑设备(例如冷却设备和不间断电源);而且传统互联网遵循过供给原则(为应对峰值流量而配备网络资源)和冗余设计原则(为应对网络突发故障而设置冗余网络资源),这将进一步增加互联网中的网络设备数量[1].如此激增的网络设备,导致互联网能耗的爆炸式增长[2].全球互联网耗电量约占全球总耗电量的5.3%[3].按目前的增长趋势,到2025 年,互联网耗电量将会达到2006 年的13 倍[4].互联网的电费支出预计在未来的7～8 年将翻一番[5].如此高的能耗增长率必将导致网络运营商的运营成本不断上涨,这将引发一系列的经济问题.

互联网能耗的快速增长往往也伴随着严峻的环境问题,因为目前在整个能源体系中,可再生的清洁能源所占的比重很小,主要还是依赖于传统的化石能源(大约占全球一次能源消耗的81%[6]),这些都加剧了碳排放,引起了全球气候变暖.“全球电子可持续发展倡议组织(global e-sustainability initiative,简称GeSI)”发表的《节能化2020 年:在信息时代推动低碳经济》报告认为:2020 年,全球二氧化碳排放当量将达到519 亿吨(其中,信息通信技术(information and communication technology,简称ICT)领域产生14 亿吨)[7].无论从经济角度、能源角度还是环境角度看,都亟需建设低能耗高能效的绿色互联网[8].

接入网的流量汇聚,使得主干网承受着比接入网更快的流量增长和能耗增长.随着网络流量的激增,主干网路由器将成为互联网中最耗能的网络设备[9].因此,面向主干网的节能问题在绿色互联网的建设与发展过程中必须加以解决.

此外,随着互联网的飞速发展,网络应用类型日益丰富,对文件传输等传统应用的尽力而为(best effort)服务不适用网络电话(voice over Internet protocol,简称VoIP)、视频会议(video teleconference,简称VTC)、网络电视(Internet protocol television,简称IPTV)以及视频点播(video on demand,简称VOD)等网络应用类型[10].鉴于此,互联网工程任务组(Internet engineering task force,简称IETF)于1994 年发布了标准RFC1633,第1 次将服务质量(quality of service,简称QoS)引入网络,提出了综合服务(integrated services,简称IntServ)模型;此后,为了克服IntServ 可扩展性差的不足,IETF 又于1998 年发布了标准RFC2474 和RFC2475,提出了差分服务(differentiated services,简称DiffServ)模型,规定了网络对不同类型应用的QoS 保证.

本文面向主干网节能问题,提出了一种网络级绿色节能机制,它包括对功率感知路由器模型和捆绑链路模型的刻画,在全局视图上,使用基于最小剩余容量优先(smallest remaining capacity first,简称SRCF)的绿色路由算法对网络流量负载进行疏导汇聚,在局部视图上使用绿色降序最佳适应(green-best fit deceasing,简称G-BFD)算法求解捆绑链路内部的流量分配问题(即绿色装箱问题).该机制在考虑网络节能收益最大化的同时,还基于DiffServ 模型考虑网络对不同应用的QoS 支持,在实现最大化网络节能的同时,兼顾应用QoS 需求.

本文第1 节综述目前主干网网络级节能机制的研究工作现状.第2 节介绍本文涉及的网络模型、节点模型、链路模型和功耗模型.第3 节给出我们提出的绿色节能机制所采用的SRCF 算法.第4 节在3 个实际网络拓扑和高、中和低流量负载下将本文提出的路由机制和选定的基准机制在功耗和性能上进行对比分析.第5 节对全文工作进行总结.

1 相关工作

目前,针对主干网网络级节能机制的研究工作[1,11]可以按不同的分类标准划分如下.

1) 按网络链路类型可以分为基于捆绑链路(由多个物理链路构成的逻辑聚合链路)的节能和基于非捆绑链路(由单一物理链路构成的链路)的节能,现阶段,主干网节点间通常由捆绑链路互连[12],这样既可以更好地维持整个网络的连通性,有效避免休眠唤醒链路时网络拓扑的频繁切换以及由此引发的路由振荡,又可以在必要时快速更新链路容量而省去重新布署和更换新链路所需花费的时间[13];

2) 按实现目标可以分为约束节能(在网络性能可接受(性能指标通常作为一种约束出现)的前提下,仅以最大化网络节能为目标)和权衡节能(在能耗和网络性能之间寻求一个最佳平衡点);

3) 按演进范畴可以分为革新式节能(完全打破且不依赖于原有的网络架构、路由算法、路由协议等而进行的全新设计)和增补式节能(在原有的网络架构、路由算法、路由协议等的基础上进行的扩充和改进),前者通常可以获取更为显著的节能效果,但是实现成本巨大;后者通常实现的节能效果较前者有限,但代价也较前者小很多.

按照上述分类,目前研究工作的特点主要体现在以下几方面.

1) 当前研究工作中,网络模型中的链路大多为非捆绑链路,如文献[14-22],少数基于捆绑链路,如文献[23-27].

2) 大多数工作探索约束节能,但主要缺陷在于没有全面考虑对各种 QoS 参数造成的影响,如文献[14-17,19-21,23,25-27],只有少数工作探索权衡节能,如文献[17,21,23].

3) 考虑到部署成本和实现代价,绝大多数工作采用增补式解决方案,如文献[14-22,24-27],只有极少数工作采用革新式解决方案,如文献[23].

文献[14]提出一种绿色分布式拓扑管理机制(distributed topology management scheme for energy saving,简称DTME),利用VCG(vickrey-clarke-groves)机制对网元进行配置管理,通过信息感知、流量预测、分布式拓扑决策和休眠控制之间的协同,对网络进行分布式拓扑管理以实现节能.文献[15]提出一种高能效路由方法——SPEED(safe and practical energy efficient detour routing).SPEED 不需要修改传统IP 分组转发框架和路由协议,在保证网络连通性的前提下,使网络中空闲链路数最大化,同时在将流量负载聚集到活动链路之后休眠空闲链路,以此实现网络节能最大化.文献[16]提出在关闭网元实现网络总功耗显著减少的同时,保证网络具有全连通性和最大链路利用率MLU(maximum link utilization).它将该问题归结为带容量限制的多商品流问题,对节点采用R(random),LL(least-link),LF(least-flow)和OE(opt-edge)共4 种启发式算法进行关闭,对链路采用R(random)和LF(least-flow)两种启发式算法进行关闭,这样对网络而言,排列组合共有8 种贪婪的启发式算法.在网络流量依正弦函数变化的假设下,对这些算法进行了性能对比分析,但是它未分析关闭部分网元对丢包率和延迟等网络性能的影响.文献[17]提出了一个依据流量变化开关链路实现网络节能的分布式能量感知流量工程解决方案DAISIES(distributed and adaptive interface switch-off for Internet energy saving),当流量需求发生变化时,为了尽可能多地关闭链路,同时降低丢包率和避免网络拥塞,DAISIES 通过一个特定的代价函数重新计算其采用的最短路径路由算法中所需的链路权重.文献[18]提出了一种选择性转发(alternative forwarding,简称AF)机制.当路由流量需求时,该机制对每跳转发都尽可能地选择使用当前活动的链路而尽量避免唤醒当前已休眠的链路,从而使已休眠的链路获得更长的休眠时间以实现节能.但是该机制通常使路由具有更长的路径长度,增加了端到端延迟,甚至可能导致路由环路的产生.文献[19]在运行最短路径路由协议的网络中提出基于混合整数线性规划的能量感知权重优化算法求解能量感知的域内流量工程问题,利用内部网关协议权重优化算法优化链路权重,通过贪婪处理阶段以及使用CPLEX 求解带容量限制的最小化成本多商品流模型,尽可能多地关闭网元,实现能耗最小化.文献[20]提出了一种通过调节OSPF(open shortest path first)协议链路权重实现网络级节能的方法.当网络经历混合全天多个时段的流量矩阵时,这种方法始终使用稳定不变的链路权重限制网络配置变化,以此减少网络振荡,提升路由配置的稳定性.然而这种方法牺牲了较多的节能收益,存在较大不必要的能耗开销.文献[21]面向主干网在多对多组播场景下提出一种支持弹性QoS 的两阶段绿色智能路由算法,用以求解最大化用户 QoS 区间需求满意度且最小化全网络功耗的组合优化问题.文献[22]在混合 SDN(software defined network)和IP(Internet protocol)的主干网上研究节能流量工程问题,基于这种革新式的架构,提出了一种快速启发式算法——混合能量感知流量工程算法HEATE(hybrid energy-aware traffic engineering),所有IP 节点使用分布式OSPF 链路权重优化的最短路径路由,所有SDN 节点使用全局SDN 控制器分流管理的多路径路由,HEATE通过联合优化链路权重和分流比将流量汇聚到部分链路上,通过关闭剩余未被使用的链路而实现节能.文献[23]设计了一个定量刻画流量和功耗之间关系的功耗模型,并提出了3 个算法,其中:Dijkstra-Green-B 算法用于实现路由无环,Dijkstra-Green-Adv 算法用于实现大幅节能,Dijkstra-Green 算法联合考虑节能和路径伸展.与本文相比,文献[23]的链路模型也考虑了捆绑链路,也联合考虑了网络能耗和QoS,但其在QoS 方面仅仅考虑了路径伸展,未考虑带宽、延迟、抖动和出错率等重要QoS 参数.基于捆绑链路模型和休眠唤醒策略,文献[24]提出一种在路由过程中,通过整合后续流量进行最短路径路由的高效节能路由算法——最短占用路径优先(shortest occupied path first,简称SOPF)算法,其在QoS 方面仅仅考虑了带宽而未考虑其他QoS 参数.文献[25]研究了如何基于当前的网络拓扑和流量矩阵,通过选择性关闭捆绑链路中的部分物理链路实现主干网的节能.它将该问题归纳为整数线性规划问题,提出了3 个启发式算法,分别是FGH(fast greedy heuristic),EGH(exhaustive greedy heuristic)和BGH(bi-level greedy heuristic),通过最大限度关闭物理链路来最大化网络节能.文献[26]把功率感知的逻辑拓扑设计归结为最优化问题,通过在低流量时期选择性关闭线卡来减少主干网功耗.使用3 种不同的启发式算法——LFA(least flow algorithm),GA(genetic algorithm)和EWA(energy watermark algorithm)分别求解此最优化问题,在网络拓扑变动时,既可以降低流量重配置率,还可以有效地降低网络功率.文献[27]提出了一种可靠绿色路由算法 R-GR(reliable green-routing)用于求解其所提出的可靠流量感知路由问题 R-EAR(reliable energy-aware-routing).虽然在关闭闲置网元获取节能的同时兼顾了网络终端可靠性(terminal reliability,简称TR)和路线可靠性(route reliability,简称RR),但是其主要缺陷在于路由时没有考虑任何QoS 参数,这样导致实际应用中由R-GR 计算出的路由不能提供一些应用所需的必要QoS 支持.

上述文献中,各节能机制间的比较见表1.为了表述简洁,我们将捆绑链路(bundled link)简记为BL,将非捆绑链路(non-bundled link)简记为NBL,将约束节能(constrained energy saving)简记为CE,将权衡节能(trade-off energy saving)简记为TE.

Table 1 Comparison among different network-level energy-saving mechanisms表1 不同网络级节能机制间的比较

相比以上研究工作,本文提出的网络级节能机制是增补式的,它属于约束节能,节能优先,兼顾性能,全面考虑对4 个最重要QoS 参数(带宽、延迟、抖动和出错率)造成的影响.而且由于目前典型主干网核心路由器间采用捆绑链路进行互连[28],因此本文中节点间互连链路均假设为捆绑链路,下文中如非特殊指明,则链路均指捆绑链路.

2 模型建立

2.1 网络模型

本文将主干网建模为连通图G(V,E),如图1 所示.其中,连通图的顶点表示主干网的节点,连通图的边表示主干网的链路.V={v1,…,vn}表示所有节点的集合,E={e1,…,em}表示所有链路的集合.

2.2 节点模型

参考我们之前的研究工作[14],本文提出的节点结构如图2 所示,包括主控引擎、背板、底架、交换结构、调度引擎、线卡、转发引擎、复制引擎和端口等构件.

主控引擎是路由器的控制中心,用于完成分组头部分析和路由表查找等功能.背板由数据总线和交换结构组成,是路由器内部数据交换通道.底架用于承载线卡和交换结构,为线卡提供连接槽位.交换结构用于在路由器内部连接线卡的输入端口和输出端口.线卡用于实现分组处理、队列调度和流量管理等功能.转发引擎用于完成分组输入、存储与转发等功能.复制引擎用于组播所需的分组复制.端口用于连接路由器和外部线路,并在两者之间进行数据传输.

2.3 链路模型

本文采用文献[29]的做法,假设节点vi和节点vj之间的捆绑链路BLij由nij条物理链路组成,表示如下:.本文抽象每条物理链路的结构如图3 所示,包括功率放大器、在线放大器、光再生器和前置放大器等中间设备.其中:功率放大器用来提高信号发送功率,在线放大器用来延长信号传输距离,光再生器用来对信号进行整形,前置放大器用来改善接收端灵敏度.

2.4 功耗模型

根据节点内部各构件的工作原理和功耗特征,抽象出节点功耗模型,如公式(1)所示:

基于先前给出的链路模型,抽象捆绑链路功耗模型如公式(2):

基于上述的节点功耗模型和链路功耗模型,全网的功耗模型如式(3)所示:和出端口

3 网络级绿色节能机制

3.1 QoS保证

对于不同的网络应用,用户有着不同的QoS 需求.本文基于差分服务模型[30],并参考国际电信联盟相关标准ITU-T Y.1540[31]和ITU-T Y.1541[32],将网络应用划分为K种类型:type1,type2,…,typeK.对于每种类型的应用,关注4 个QoS 参数:带宽、延迟、延迟抖动和出错率.对于第k类应用,需要网络提供的带宽、延迟、延迟抖动和出错率分别为,其中,1≤k≤K.

参考我们之前的研究工作[21],本文将路由途经的每个节点处的QoS 合并到与其相连的后向链路中,将链路l的带宽、延迟、延迟抖动和出错率分别表示为bwl,dll,jtl和erl,则路径P的QoS 可以通过公式(4)得到:

本文提出的路由算法针对每个流量需求计算路径,判断路径QoS 是否落入对应应用类型所必须满足的QoS 区间,以此确定求得的路由是否有效.

3.2 SRCF路由算法

本文设计了一种单路径节能路由算法——基于最小剩余容量优先(smallest remaining capacity first,简称SRCF)的功率感知路由算法,该算法将初始全网络图和流量需求矩阵作为算法的输入,以边的剩余容量配置网络图的边权重,每次路由新的流量需求时,都选取和先前所使用路由路线的边重叠最多的路径,这样,随着路由流量需求的不断进行,流量被不断汇聚到一个尽可能小的网络子集,通过关闭剩余的那些未被使用的网元来实现全网节能,伪代码如算法1 所示.流量需求矩阵由网络中所有节点对间的流量需求值组成,描述如公式(5)所示,其中,demandii=0(i∈{1,2,…,|V|}):

算法1.SRCF 算法.

输入:DEMAND,初始网络图G0;

输出:ROUTEorNULL.

3.3 G-BFD算法

在第3.2 节中,我们使用SRCF 算法得到所有流量需求的路由路线.由于我们的链路模型考虑的是捆绑链路,为了保证网络绿色节能,将面临对于流经每条捆绑链路的流量,如何使捆绑链路中开启的物理链路数目最少这样一个装箱问题,其形式化表述如下:

设当前网络中有n个流量需求流经捆绑链路BLij(由nij条物理链路组成),它们的大小分别为.使用当前可用容量分别为的N条物理链路来容纳这n个流量需求,每条物理链路容纳的流量需求总和不能超过该物理链路的可用容量.目标是寻求满足以上条件,使得所使用物理链路的数目N最小的分配解决方案.

我们可以将上述问题规划如下:

由于装箱问题是一个经典的NP 难问题,该问题不存在在多项式时间内求得精确解的算法.因此,我们设计了一种启发式算法——绿色降序最佳适应(green-best fit deceasing,简称G-BFD)算法对其进行求解.

对流经每个捆绑链路BLij(i,j∈{1,2,…,|V|},i≠j)的n个流量需求(v∈{1,2,…,n}),使用G-BFD 算法获取流量分配解决方案,其伪代码如算法2 所示.

算法2.G-BFD 算法.

4 仿真实现与机制评估

为了更好地评价本文提出的SRCF-G 机制(在全局视图下,采用SRCF 算法,沿着具有最小剩余容量的路径路由所有流量需求;而在局部视图下的边内部使用G-BFD 算法进行流量分配),我们采用如下5 种机制在功耗和性能方面进行对比.

· SPT 机制:在全局视图下,以功耗作为边权重,采用SPT(shortest path tree)算法[33]路由所有流量需求;而流量在局部视图下边内部的分配是随机的(只要流量能够被物理链路容纳即可);

· SPT-G 机制:在全局视图下,以功耗作为边权重,采用SPT 算法路由所有流量需求;而在局部视图下的边内部使用G-BFD 算法进行流量分配;

· SOPF 机制:采用SOPF 算法[24]路由所有流量需求,由于此算法是基于捆绑链路模型提出的,故无需进一步改造,可将其直接进行比较;

· MSPF 机制:采用MSPF-NF2(multiple paths by shortest path first-node first version 2)算法[34]路由所有流量需求.同样,由于该算法也是基于捆绑链路模型提出的,可以将其直接进行比较;

· SRCF 机制:在全局视图下,采用SRCF 算法,沿着具有最小剩余容量的路径路由所有流量需求;而流量在局部视图下边内部的分配是随机的(只要流量能够被物理链路容纳即可).

4.1 仿真环境

以上所有方案均在如下仿真环境下进行仿真实现.

· 硬件配置:CPU:Intel Quad-Core i5-4590@3.30GHz,RAM:4GB (DDR3,1600MHz);

· 操作系统:Windows 7 professional 64bits;

· 开发平台:Microsoft Visual Studio 2010;

· 开发语言:C++.

4.2 仿真数据集

· 仿真用例

采用3 个典型的主干网CERNET2(http://www.edu.cn/xxh/ji_shu_ju_le_bu/cernet2_lpv6/cernet2/) (20 个节点和22 条链路),GéANT(http://www.geant.org/Networks/Pan-European_network/Pages/GEANT_topology_map.aspx)(41 个节点和65 条链路)和INTERNET2(https://www.internet2.edu/media/medialibrary/2015/08/04/NetworkMap_all.pdf)(64 个节点和78 条链路)进行测试,如图4 所示,特征属性参见表2.

Table 2 Topology properties表2 拓扑属性

· 流量数据集

对于CERNET2 拓扑,采用教育网Aladdin 网管中心信息平台提供的开放数据集(阿拉丁网络信息管理系统,http://219.243.208.6/snmp/index.php);对于GéANT 拓扑和INTERNET2 拓扑,采用文献[35]中提供的开放数据集.在每天3 个典型时间段,3 个拓扑的节点进出流量负载平均值变化情况如图5 所示.

4.3 参数设置

参考思科12000 系列路由器(Cisco XR 12000 Series and Cisco 12000 Series Routers.http://www.cisco.com/c/en/us/products/routers/12000-series-routers/datasheet-listing.html)设置仿真中使用的参数,见表3.

Table 3 Simulation parameters setting表3 仿真参数设置

4.4 网络功耗对比

从图6 可以观察到:

(1) 在所有情形下,6 种机制按网络功耗从高到低依次排列为:SOPF/MSPF>SPT>SPT-G>SRCF>SRCF-G,在CERNET2,GéANT 和INTERNET2 低负载情形下,SRCF-G 节省功耗分别为86.5%,70.7%和65.79%;

(2) 在INTERNET2 中、高负载和GéANT 高负载情形下,SOPF 的功耗是最高的,仅分别节省功耗7.16%,0.286%和2.13%;而在其他情形下,MSPF 的功耗是最高的;

(3) 在所有情形下,SRCF-G 和SPT-G 的功耗分别比SRCF 和SPT 有较大幅度的降低,尤其是在低流量负载下降幅最大,在CERNET2,GéANT 和INTERNET2 拓扑下分别为30.8%,19.3%,24%和42.4%,18.2%,17.2%;而在高负载情形下差距不明显,在CERNET2,GéANT 和INTERNET2 拓扑下分别为1.29%,1.9%,1.4%和3.25%,1.82%,2.96%.

对于情况(1):首先,SRCF-G 使得网络在全局视图下,能够以最小剩余容量路径和尽量复用已开启网元的原则路由每个流量需求,且在局部视图下每条边的内部采用G-BFD 算法使得开启的物理链路数最小,这样得到一个在所有机制中最小的网络子图路由全部流量需求;其次,SRCF 和SPT 因缺少在局部视图下的流量分配阶段而开启较多的物理链路,使得它们功耗分别高于SRCF-G 和SPT-G;再次,SPT-G 的功耗始终大于SRCF,这表明全局路由算法对节省功耗的贡献大于在局部视图下的流量分配策略;最后,SOPF 和MSPF 的功耗最高,这是因为它们都是基于最少跳数的路由机制,相比于复用已开启网元的SRCF-G 和SRCF 以及直接以功耗为边权重的SPT-G 和SPT,它们开启了更多的网元.

对于情况(2):在拓扑复杂度和流量负载较低时,采用多路径路由的MSPF 与采用单路径路由的SOPF 相比开启了较多的网元;随着拓扑复杂度和流量负载的不断升高,更多的网元不断被开启,SOPF 的单路径优势逐渐被削弱,而MSPF 多路径路由的优势逐渐显现出来,较SOPF 更加均匀地在网元间路由流量需求,这使得其功耗最终低于SOPF.

对于情况(3):这主要是由于低负载情形下,G-BFD 算法将零散的流量分配到极少数物理链路上进行传输,使得大量的剩余空闲物理链路得以休眠,从而获得尽可能多的节能收益,而随机流量分配策略在传输相同的流量时使用较多物理链路,相比之下,剩余空闲物理链路数目较少,导致网络功耗较大.而在高负载情形下,各边中的物理链路利用率近乎饱和,局部视图下的流量分配策略在此时的作用十分有限,这导致各机制网络功耗之间差距不明显.

4.5 网络性能对比

4.5.1 平均路由跳数

从图7 可以观察到:

(1) 在所有情形下,SOPF 的平均路由跳数均最小,MSPF 次之;

(2) 在所有情形下,SPT 和SRCF 的平均路由跳数都分别与SPT-G 和SRCF-G 相同;

(3) SRCF 的平均路由跳数往往会大于SPT(除了在CERNET2 的低负载情形下),且在低负载情形下,两者差距不大(在GéANT 和INTERNET2 下分别相差0.5 跳和1.3 跳);但是随着负载的增加,这种差距会被拉大(在GéANT 和INTERNET2 下分别相差2.35 跳和2.8 跳).

对于情况(1):SOPF 的单路径最短路径路由使其平均路由跳数最小,MSPF 的多路径前k条最短路路由使其仅次于SOPF.

对于情况(2):这是因为局部视图下的流量分配策略并不影响路由选择,所以不会影响路由跳数.

对于情况(3):这是由于SRCF 不同于SPT 那样对于每个流量需求都独立选择功耗权重最小的路径进行路由,而是当路由一个新的流量需求时,都在边剩余容量权重最小的路径中选择与之前路由其他流量需求所使用的边重叠最多的路径进行路由.在低负载情形下,网络中已开启的网元较少,这样在路由流量需求时,SRCF 复用已开启网元的机会大大减少,而此时,SPT 选择的功耗权重最小的路径长度和SRCF 选择的路径长度差别很小.

4.5.2 物理链路关闭数目

从图8 可以观察到:

(1) 在所有情形下,6 种机制按关闭物理链路数目从多到少依次排列为:SRCF-G>SPT-G>SRCF>SOPF>MSPF>SPT,在CERNET2,GéANT 和INTERNET2 的低负载情形下SRCF-G 关闭物理链路数目分别为64 条、135 条和152 条,分别占物理链路总数的58.2%,41.5%和38.97%;

(2) 随着流量负载的增长,各机制关闭物理链路数目不断减少且差异缩小.

对于情况(1):因为SRCF-G 不仅在全局视图下依据最小剩余流量优先进行路由,而且局部视图下的流量分配策略能够尽可能地减少物理链路的使用,两者的共同作用使得其胜过其他方案.SPT-G>SRCF 说明在关闭物理链路方面,流量分配方案是占主导地位的,SPT 关闭物理链路数是最少的.因为其没有采用任何机制保障流量尽量“填满”每个物理链路,MSPF 多路径路由的固有属性使其关闭物理链路数目仅比SPT 多;而SOPF 基于最短路径的单路径路由固有属性使其关闭的物理链路数目介于基于最少剩余容量的单路径路由机制SRCF 和MSPF 之间.

对于情况(2):这是因为高流量负载开启了较多的网元,导致机制之间路由固有属性差异和局部视图下的流量分配策略差异都不明显.

4.5.3 路由成功率

从图9 可以观察到:

(1) 在所有情形下,6 种机制按路由成功率从高到低依次排列为:SRCF-G>SRCF>MSPF>SOPF>SPT-G>SPT,即便在CERNET2,GéANT 和INTERNET2 的高负载情形下,SRCF-G 的路由成功率依然分别保持在92.1%,88.4%和84.5%;

(2) 在GéANT 和INTERNET2 的高负载情形下,SRCF-G 和SRCF 之间的路由成功率差距以及SPT-G 和SPT 之间的路由成功率差距都并不明显.

对于情况(1):SRCF-G 的路由成功率最高,是因为它在全局视图下路由时考虑了QoS 需求,剔除了不满足QoS 最低要求的边,而且局部视图下的的流量分配策略也提高了路由成功率.SPT 的路由成功率最低,是因为它在路由时没有考虑任何QoS 参数.MSPF 为在最大链路利用率和路径长度的QoS 约束下的最短多路径路由机制,但其未考虑延迟抖动出错率等QoS 关键参数,这些特征使其路由成功率低于SRCF 而高于仅在带宽约束下的最短单路径路由机制SOPF.而SOPF 的路由成功率总是高于SPT-G,表明在全局视图下路由时,考虑QoS 对路由成功率的贡献优于局部视图下的流量分配策略.

对于情况(2):这是由于此时大部分网元均已被使用且剩余可用容量均较小,因此局部视图下的流量分配策略对路由成功率的贡献微乎其微.

4.5.4 运行时间

从图10 可以观察到:

(1) 在所有情形下,SPT 的运行时间均是最小的,SPT-G 次之;

(2) 在INTERNET2 中、高负载和GéANT 高负载情形下,剩余4 个机制的运行时间从大到小依次排列为MSPF>SOPF>SRCF-G>SRCF;

(3) 在INTERNET2 低负载和GéANT 中负载情形下,剩余4 个机制的运行时间从大到小依次排列为MSPF>SRCF-G>SRCF>SOPF;

(4) 在其他情形下,剩余4 个机制的运行时间从大到小依次排列为SRCF-G>SRCF>MSPF>SOPF;

(5) 随着拓扑结构复杂度升高和流量负载变大,各机制的运行时间呈现出不同幅度的增长:

对于情况(1):SPT 运行时间最小是由其固有的运算复杂度决定的,SPT-G 次之表明,局部视图下的G-BFD 算法较SRCF,SOPF 和MSPF 有更低的运算复杂度.这是由于SRCF 不仅对每个流量需求进行路由时都要检验是否满足QoS 需求,而且不满足时还要重新选取新路径再次检验,因此运行时间较长;而SOPF 和MSPF 均首先通过最短路径路由所有流量需求而产生网络子图,然后使用贪婪启发式算法对子图中的每条边进行逐一试探,以判断其中的物理链路是否可以被关闭,在最后还需进一步执行贪婪启发式检验阶段——通过不断恢复已关闭物理链路而检验是否可以关闭更多的物理链路,这个阶段有着与先前路由阶段相同的运算复杂度,因此运行时间也较长.

对于情况(2)～情况(4):随着网络拓扑复杂度和流量负载的增加,MSPF 和SOPF 中的贪婪启发式算法运算开销迅速攀升,使得这两个机制的运行时间急剧恶化(其中,多路径路由的MSPF 尤为严重),直至超过SRCF 和SRCF-G.

对于情况(5):我们能够得出结论:运算复杂度越高的机制,运行时间增长/减少率越依赖于网络拓扑复杂度和流经其上的流量负载变化,敏感性越高.

5 总结

本文从网络级粒度出发,研究了主干网绿色节能机制.本文设计了基于捆绑链路的功率感知功耗模型;提出了一种全局路由算法——SRCF 算法,这使得我们得到一个初步的网络子图,完成了初步的节能;之后,进一步提出了一种在捆绑链路内部的局部流量分配算法——G-BFD 算法,这使得在每条捆绑链路内部开启的物理链路数最小.这样,我们得到了一个更小的网络子图,完成了进一步的节能.此外,本文提出的机制在节能的同时兼顾用户QoS 需求,在提供QoS 保证的前提下,尽可能最大化节能收益.在机制测评中,从网络功耗和网络性能(平均路由跳数、物理链路关闭数目、路由成功率和运行时间)方面对本文机制进行了全面评估.仿真结果表明:相比其他机制,本文机制在平均路由跳数和运行时间上略有增加,但在其他方面优势明显,尤其在低负载时节能效果显著.