近些年, 随着互联网用户数持续增长和云存储、物联网等新技术和新模式的不断涌现和发展, 急剧增长的互联网流量呈现出全球化趋势, 预计全球网络年流量将从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.

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

2 模型建立 2.1 网络模型

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

2.2 节点模型

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

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

2.3 链路模型

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

2.4 功耗模型

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

$ P_i^{node} = \\\left( \begin{array}{l} P_i^{ctrl} + P_i^{sch} + \sum\limits_{k = 1}^{N_i^{chass}} {\left( \begin{array}{l} P_{i, k}^{chass} \times ChaSt_i^k + \sum\limits_{lc = 1}^{N_{i, k}^{lc}} {((P_{i, k, lc}^{ford} + P_{i, k, lc}^{repl}) \times LcdSt_{i, k}^{lc})} \end{array} \right)} \end{array} \right) \times NodeS{t_i} $

(1)

其中, $P_i^{node}$表示节点v_i的功耗; $P_i^{ctrl}$表示节点v_i主控引擎的功耗; $P_i^{sch}$表示节点v_i调度引擎的功耗; $P_{i, k}^{chass}$表示节点v_i中第k个底架(背板交换结构的功耗计入到对应的底架中, 数据总线功耗忽略不计)的基准功耗(不插任何线卡时底架的功耗); $P_{i, k, lc}^{ford}$表示节点v_i中第k个底架上第lc个线卡的转发引擎的功耗; $P_{i, k, lc}^{repl}$表示节点v_i中第k个底架上第lc个线卡的复制引擎的功耗; $N_i^{chass}$表示节点v_i的底架总数; $N_{i, k}^{lc}$表示节点v_i中第k个底架上的线卡总数; NodeSt_i, $ChaSt_i^k$和$LcdSt_{i, k}^{lc}$分别表示节点v_i的开关标识符、节点v_i中第k个底架的开关标识符和节点v_i中第k个底架上第lc个线卡的开关标识符, 这3个标识符都是二进制变量, 其值为“1”表示对应的节点或器件处于正常工作的活动“开”状态, 其值为“0”表示对应的节点或器件处于休眠“关”状态.

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

$ P_{ij}^{BL} = \sum\limits_{k = 1}^{{n_j}} {P_{{i_k}{j_k}}^{link}} =\\ \sum\limits_{k = 1}^{{n_j}} {((P_{{i_k}}^{port} + P_{{j_k}}^{port} + ({P_{PA}} + {P_{ILA}} \times N_{{i_k}{j_k}}^{ILA} + {P_{REG}} \times N_{{i_k}{j_k}}^{REG} + {P_{PREA}})) \times LinkSt_{ij}^k)} $

(2)

其中, $P_{ij}^{BL}$表示节点v_i和节点v_j之间的捆绑链路BL_ij的功耗; $P_{{i_k}{j_k}}^{link}$表示组成捆绑链路BL_ij的物理链路$l_{ij}^k$的功耗; P_PA表示功率放大器的功耗; P_ILA表示在线放大器的功耗; P_REG表示光再生器的功耗; P_PREA表示前置放大器的功耗; $N_{{i_k}{j_k}}^{ILA}$和$N_{{i_k}{j_k}}^{REG}$分别表示物理链路$l_{ij}^k$中在线放大器和光再生器的数目; $LinkSt_{ij}^k$是物理链路$l_{ij}^k$的开关标识符, 这个标识符是二进制变量, 其值为“1”表示该物理链路及其两端端口处于活动状态, 其值为“0”表示该物理链路及其两端端口处于休眠状态; $P_{{i_k}}^{port}$和$P_{{j_k}}^{port}$分别表示物理链路$l_{ij}^k$的入端口$Port_{{i_k}}^{ij}$和出端口$Port_{{j_k}}^{ij}$的功率.

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

$ {P^{net}} = \sum\limits_{i \in V} {P_i^{node}} + \sum\limits_{(i, j) \in E} {P_{ij}^{BL}} $

(3)

3 网络级绿色节能机制 3.1 QoS保证

对于不同的网络应用, 用户有着不同的QoS需求.本文基于差分服务模型^[30], 并参考国际电信联盟相关标准ITU-T Y.1540^[31]和ITU-T Y.1541^[32], 将网络应用划分为K种类型:type₁, type₂, …, type_K.对于每种类型的应用, 关注4个QoS参数:带宽、延迟、延迟抖动和出错率.对于第k类应用, 需要网络提供的带宽、延迟、延迟抖动和出错率分别为$b{w_{classk}} \ge bw_{classk}^{\min }, d{l_{classk}} \le dl_{classk}^{\max }, j{t_{classk}} \le jt_{classk}^{\max }$和$e{r_{classk}} \le er_{classk}^{\max }$, 其中, 1≤k≤K.

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

$ b{w_P} = \min \{ b{w_l}|l \in P\} , d{l_P} = \sum\limits_{l \in P} {d{l_l}} , j{t_P} = \sum\limits_{l \in P} {j{t_l}} , e{r_P} = 1 - \prod\limits_{l \in P} {(1 - e{r_l})} $

(4)

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

3.2 SRCF路由算法

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

$ \mathit{\boldsymbol{DEMAND}} = \left[ \begin{array}{l} deman{d_{11}}{\rm{ }} \cdots {\kern 1pt} {\rm{ }}deman{d_{1|V|}}\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \vdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \ddots {\kern 1pt} {\rm{ }}{\kern 1pt} {\kern 1pt} \vdots \\ deman{d_{|V|1}}{\rm{ }} \cdots {\rm{ }}deman{d_{|V||V|}} \end{array} \right] $

(5)

算法 1. SRCF算法.

输入:DEMAND, 初始网络图G₀;

输出:ROUTE or NULL.

1:  初始化ROUTE←Ø;

2:  对流量需求矩阵中不为零的元素demand_ij(i, j∈{1, 2, …, |V|}, i≠j), 按从大到小进行排序, 得到:

$ deman{d_1}, deman{d_2}, \ldots , deman{d_{|V\left| ( \right|V| - 1)}}; $

3:  FOR i←1:|V|(|V|-1 DO

4:    删除网络图G_{-1-2-…-(i-1)}中剩余容量小于demand_i的边, 由此得到子图$G_{ - 1 - 2 - ... - (i - 1)}^{ - i}$;

5:    在$G_{ - 1 - 2 - ... - (i - 1)}^{ - i}$上使用Dijkstra算法(以边的剩余容量为权重)为demand_i计算路由路径;

6:    IF路径不存在THEN

7:      对demand_i的路由失败, RETURN NULL;

8:    ELSE

9:      对路径进行QoS检验, 剔除不合格的路径;

10:    END IF

11:    IF满足QoS的路径不存在THEN

12:      对demand_i的路由失败, RETURN NULL;

13:    ELSE IF存在多条路径THEN

14:          IF i==1 THEN

15:            IF跳数最少的路径只有1条THEN

16:              选取该路径, 记为Route_i, ROUTE←ROUTE∪{Route_i};

17:            ELSE

18:              从跳数最少的几条路径中随机选取1条, 记为Route_i, ROUTE←ROUTE∪{Route_i};

19:            END IF

20:        ELSE IF与{Route₁, Route₂, …, Route_i-1}边重叠最多的路径只有1条THEN

21:          选取该路径, 记为Route_i, ROUTE←ROUTE∪{Route_i};

22:            ELSE

23:              从与{Route₁, Route₂, …, Route_i-1}边重叠最多的几条路径中随机选取1条, 记为:Route_i, ROUTE←ROUTE∪{Route_i};

24:            END IF

25:          END IF

26:        ELSE

27:          记该路径为Route_i, ROUTE←ROUTE∪{Route_i};

28:        END IF

29:    END IF

30:    在网络图G_{-1-2-…-(i-1)}中, Route_i沿途各边中减去相应的容量(即demand_i大小), 记由此更新后的网络图为G_-1-2-…-i;

31:  END FOR

32:  RETURN ROUTE.

3.3 G-BFD算法

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

设当前网络中有n个流量需求$demand_{ij}^1, demand_{ij}^2, ..., demand_{ij}^n$流经捆绑链路BL_ij(由n_ij条物理链路组成), 它们的大小分别为$size_{ij}^1, size_{ij}^2, ..., size_{ij}^n$.使用当前可用容量分别为$ac_{ij}^1, ac_{ij}^2, ..., ac_{ij}^N$的N条物理链路来容纳这n个流量需求, 每条物理链路容纳的流量需求总和不能超过该物理链路的可用容量.目标是寻求满足以上条件, 使得所使用物理链路的数目N最小的分配解决方案$\mathit{\boldsymbol{So}}{\mathit{\boldsymbol{l}}_{\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{L}}_{ij}}}}.$

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

$ \min N({x_{ij}}) = \sum\limits_{u = 1}^{{n_{ij}}} {x_{ij}^u} $

(6)

$ \sum\limits_{v = 1}^n {size_{ij}^v \times y_{ij}^{uv}} \le ac_{ij}^u \times x_{ij}^u, \forall u \in \{ 1, 2, ..., {n_{ij}}\} $

(7)

$ \sum\limits_{u = 1}^{{n_{ij}}} {y_{ij}^{uv}} = 1, \forall v \in \{ 1, 2, ..., n\} $

(8)

$ x_{ij}^u \in \{ 0, 1\} , \forall u \in \{ 1, 2, ..., {n_{ij}}\} $

(9)

$ y_{ij}^{uv} \in \{ 0, 1\} , \forall v \in \{ 1, 2, ..., n\} $

(10)

其中, $x_{ij}^u$和$y_{ij}^{uv}$均是状态标识符:$x_{ij}^u$取值为1或0, 分别表示物理链路$l_{ij}^u$上是否承载了流量需求; $y_{ij}^{uv}$取值为1或0, 分别表示流量需求$demand_{ij}^v$是否被分配至物理链路$l_{ij}^u$承载.

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

对流经每个捆绑链路BL_ij(i, j∈{1, 2, …, |V|}, i≠j)的n个流量需求$demand_{ij}^v$(v∈{1, 2, …, n}), 使用G-BFD算法获取流量分配解决方案$\mathit{\boldsymbol{So}}{\mathit{\boldsymbol{l}}_{\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{L}}_{ij}}}}$, 其伪代码如算法2所示.

算法 2. G-BFD算法.

输入:$B{L_{ij}}, demand_{ij}^1, demand_{ij}^2, ..., demand_{ij}^n, size_{ij}^1, size_{ij}^2, ..., size_{ij}^n, ac_{ij}^1, ac_{ij}^2, ..., ac_{ij}^{{n_{ij}}}$;

输出:$\mathit{\boldsymbol{So}}{\mathit{\boldsymbol{l}}_{\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{L}}_{ij}}}}$.

1:  初始化$\mathit{\boldsymbol{So}}{\mathit{\boldsymbol{l}}_{\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{L}}_{ij}}}} \leftarrow \varnothing $;

2:  对$demand_{ij}^{v}$(v∈{1, 2, …, n}), 按从大到小降序排列, 记为$A_{ij}^{demand}:demand_{ij}^{{{\max }_{1}}}, demand_{ij}^{{{\max }_{2}}}, ..., demand_{ij}^{{{\max }_{n}}}$, 将当前已开启的物理链路, 按可用容量从小到大升序排列, 记为$A_{ij}^{active}:l_{ij}^{activ{{e}_{1}}}, l_{ij}^{activ{{e}_{2}}}, ..., l_{ij}^{activ{{e}_{{{n}_{a}}}}}$, 将当前未开启的物理链路, 按容量从小到大升序排列, 记为$A_{ij}^{sleeping}:l_{ij}^{sleepin{{g}_{1}}}, l_{ij}^{sleepin{{g}_{2}}}, ..., l_{ij}^{sleepin{{g}_{{{n}_{s}}}}}$;

3:  FOR $demand_{ij}^{{{\max }_{v}}}$(v=1;v≤n; v++) DO

4:    IF已开启的物理链路$l_{ij}^{activ{{e}_{{{n}_{a}}}}}$尚且不能容纳当前流量需求$demand_{ij}^{{{\max }_{v}}}$ THEN

5:      从$A_{ij}^{sleeping}$中顺序查找能容纳$demand_{ij}^{{{\max }_{v}}}$的第1个物理链路, 记为$l_{ij}^{sleepin{{g}_{{{v}_{s}}}}}$, 将该物理链路从$A_{ij}^{sleeping}$中剔除, 将$demand_{ij}^{{{\max }_{v}}}$分配至该物理链路, 并依据其剩余可用容量将其加入到$A_{ij}^{active}$中的相应位置:

$ \mathit{\boldsymbol{So}}{\mathit{\boldsymbol{l}}_{\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{L}}_{ij}}}} \leftarrow \mathit{\boldsymbol{So}}{\mathit{\boldsymbol{l}}_{\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{L}}_{ij}}}} \cup \{ l_{ij}^{sleepin{g_{{v_s}}}} \leftarrow demand_{ij}^{{{\max }_v}}\} $

6:    ELSE

7:      从$A_{ij}^{active}$中顺序查找能容纳$demand_{ij}^{{{\max }_{v}}}$的第一个物理链路, 记为$l_{ij}^{activ{{e}_{{{v}_{a}}}}}$, 将该流量需求分配至该物理链路, 更新该物理链路的可用容量及其在整个排序中的位置, $\mathit{\boldsymbol{So}}{\mathit{\boldsymbol{l}}_{\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{L}}_{ij}}}} \leftarrow \mathit{\boldsymbol{So}}{\mathit{\boldsymbol{l}}_{\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{L}}_{ij}}}} \cup \{ l_{ij}^{activ{e_{{v_a}}}} \leftarrow demand_{ij}^{{{\max }_v}}\} $;

8:    END IF

9:  END FOR

10: RETURN $\mathrm{So}{{\mathrm{l}}_{\mathrm{B}{{\mathrm{L}}_{ij}}}}$.

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.

●   流量数据集

对于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.

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)    随着拓扑结构复杂度升高和流量负载变大, 各机制的运行时间呈现出不同幅度的增长:

$ \Delta {T_{MSPF}} > \Delta {T_{SOPF}} > \Delta {T_{SRCF - G}} > \Delta {T_{SRCF}} > \Delta {T_{SPT - G}} > \Delta {T_{SPT}}. $

对于情况(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保证的前提下, 尽可能最大化节能收益.在机制测评中, 从网络功耗和网络性能(平均路由跳数、物理链路关闭数目、路由成功率和运行时间)方面对本文机制进行了全面评估.仿真结果表明:相比其他机制, 本文机制在平均路由跳数和运行时间上略有增加, 但在其他方面优势明显, 尤其在低负载时节能效果显著.