2. 电子科技大学光纤通信国家重点实验室, 成都 610054
针对互联网中业务流量的动态变化,提出了基于预置多拓扑的节能算法.首先根据历史的业务流量数据将每天划分为多个时间片,然后在划分好的各个时间片内利用邻域搜索作节能子拓扑设计.通过优化链路权重向量使流量集中在部分链路上,同时休眠没有流量经过的链路,以实现互联网节能的目标.
2. National Key Laboratory of Optical Fiber Communication, University of Electronic Science and Technology of China, Chengdu 610054, China
To solve the problem that the traffic flow dynamically changes in Internet protocol (IP) network, a new energy saving algorithm based on pre-configured multiple topologies (ESPMT) was proposed. In the ESPMT algorithm, firstly, according to the daily traffic flow, each day is divided into multiple time slices, secondly, the energy-saving sub-topology is designed by utilizing neighboring region search for each single time slice. To achieve the purpose of energy saving, the traffic flows are concentrated on some links. The links without traffic are powered off in IP networks.
随着社交网络、移动互联网、物联网等业务领域的快速发展，互联网设备和其业务流量呈爆炸性增长，导致其消耗的能量急剧升高. 减少能耗成为目前互联网研究的一个关键问题. 据统计，美国能耗的2%～10%来自互联网能耗. 此外，互联网的能源效率(能耗与总负载流量正相关)非常低. 因此，互联网(IP网络，Internet protocol network)的节能问题受到工业界和学术界的广泛关注.
在IP网络中，开放最短路径优先(OSPF，open shortest path first)是最常用的域内路由协议. OSPF协议根据链路权重计算最短路径，这样可以通过优化链路权重来优化全网的流量分布，最大限度地实现节能. 但在IP网络中，业务流量通常是动态变化的. 一般情况下，每天的业务流量变化曲线基本相似. 利用静态业务量矩阵优化的OSPF权重无法满足实际业务流量的变化，使得节能效果不佳. 现有文献[1, 2, 3, 4]大多是根据历史的业务量在不同的时间段内节能，但并没有详细阐述时间段的划分依据和划分个数. 当划分的时间段个数较多时，能更加贴近实际的业务流量. 但业务流量在不同的时间段切换时，会导致链路的权重向量和最终休眠的链路集合不同，触发链路状态协议重新收敛成一个新的网络拓扑. 拓扑收敛的更新需要花费数十秒时间，在这段时间内容易导致网络性能下降. 因此，根据动态变化的流量合理地划分时间片段很有必要. 现有的很多节能路由文献都忽略了这个问题.
针对上述节能设计存在的问题，笔者提出了一种基于预置多拓扑的节能(ESPMT，energy saving based on pre-configured multiple topologies)算法. ESPMT算法包含两大部分. 首先，根据历史的动态业务量提出了一种时间片的分割方法. 将每天划分为多个时间片，各个时间片的流量峰值作为该时间片内的节能问题的输入. 这样使节能问题输入流量与实际流量的差值最小，即冗余的流量最小，得到更好的节能效果. 其次，在单个时间片内作节能子拓扑设计时，提出快速的启发式算法. 利用邻域搜索优化链路权重作节能子拓扑设计. 该算法与Fortz等[5]提出的邻域搜索算法都是基于OSPF链路权重的调整策略进行的，但两者之间存在目标函数差异. 因此，笔者主要研究链路权重调整的具体策略，通过链路权重的优化生成一套最优权重向量，使得在保证链路容量约束的前提下，实现单拓扑内最大限度地节能.
各部分安排如下. 第1节提出了一种划分时间片的方法，根据历史业务量将每天划分为多个时间片，减小业务量冗余；第2节提出了一种启发式邻域搜索算法，通过优化OSPF链路权重形成节能子拓扑；第3节通过仿真实验验证了ESPMT算法的性能；第4节是结束语.
1 多拓扑设计的时间分割在IP网络场景中，业务流量是动态变化的. 笔者认为，合理的节能路由技术在业务流量较低时能休眠掉部分网络链路，并将业务集中到其他网络设备上以实现节能；当业务流量变大时，开启部分网络设备以满足业务的需求. 基于此种思路，可以将每天划分为多个时间段，在各个时间段内基于特定的流量特征设计节能子拓扑. 笔者将首先研究如何合理有效地根据每天的业务量曲线特性进行时间片的划分，从而为单个时间片内节能子拓扑的设计提供依据.
由于正常的IP网络流量曲线图有1个波峰和1个波谷，同时带宽供应必须充足，因此一定存在1个时间片的供应量恰好与波峰值相等. 基于此，可以选择波峰作为划分的基准点，将网络流量曲线图分为2个阶段：业务量需求上升阶段和业务量需求下降阶段，如图 1所示. 这种方法是以波峰作为划分的入手点，因此被称为波峰分割法.
 | 图1 以波峰为基点的网络流量曲线图 |
将流量曲线图按照上升阶段和下降阶段划分为多个时间片时，上升阶段的最后1个时间片与下降阶段的第1个时间片的供应值相等，可合并为1个时间片. 因此，在将1天的流量曲线图按照上升阶段和下降阶段划分为2K+1(其中K为正整数)个时间片时，上升阶段和下降阶段各为K+1个时间片. 若要划分为2K个时间片时，有2种划分方式：第1种为上升阶段K+1个，下降阶段K个；第2种为上升阶段K个，下降阶段K+1个. 取二者当中的更优者(更优者具有更小的供应量)作为最终划分方式. 图 1表示将流量曲线图划分为4个时间片的一种划分方式，其中上升阶段3个，下降阶段2个，靠近波峰的2个时间片合并为1个. 当2个阶段靠近波谷的时间片的供应值相等时，则直接将这2个时间片合并为1个时间片，不需要另划分1个新的时间片.
为说明如何确定划分时刻点，根据如图 2所示的多时间片划分示意图作理论证明.
 | 图2 多时间片划分示意图 |
在图 2中，将上升阶段划分为m个时间片，下降阶段划分为n个时间片，横坐标为时间轴，单位为h. 为了方便论述，上升阶段的波谷横坐标简记 为x0，波峰横坐标简记为xm，横坐标为x1,x2,…,xk,…,xm-1(k=1,2,3,…,m－1)的点将上升阶段分为m个时间片；下降阶段的波峰横坐标简记为y0(y0与xm相等)，波谷横坐标简记为yn(yn与x0实为同一个时刻点)，横坐标为y1,y2,…,yl,…,yn-1(l=1,2,3,…,n－1)的点将下降阶段划分为n个时间片. 上升阶段的曲线函数方程记为f(x)，下降阶段的曲线函数方程记为g(y). 记曲线f(x)与其上阶跃函数曲线所围成区域的面积为S，则通过微积分方法可得2条曲线围成的面积为
$S=\sum\limits_{k=1}^{m}{f\left( {{x}_{k}} \right)}\left( {{x}_{k}}-{{x}_{k-1}} \right)-\int{_{{{x}_{0}}}^{{{x}_{m}}}}f\left( x \right)dx$
(1)
为使流量曲线上升阶段供应的流量冗余最少，即使面积S最小，xk(k=1,2,3,…,m－1)需要满足
f′(xk)(xk－xk－1)+f(xk)－f(xk+1)=0
(2)
同理，得到下降阶段yl(l=1,2,3,…,n－1)需要满足
g′(yl)(yl+1－yl)+f(yl－1)－f(yl)=0
(3)
流量曲线上升阶段的每一个划分点的横坐标都应满足式(2)，上升阶段的m个划分时刻点的横坐标则构成了一个m元的方程组. 已知f(x)的函数表达式，同时其导函数f′(x)、波谷和波峰的纵坐标f(x0)和f(xm)亦可知. 因此，式(2)构成的方程组是可解的. 通过条件x0<x1<x2<…<xk<…<xm-1(k=1,2,3,…,m－1)便可得满足条件的解，从而确定上升阶段各个划分时刻点. 同理，可确定下降阶段各个划分时刻点.
2 节能子拓扑设计算法在OSPF协议中，每条链路都会被分配1个权重，流量根据这些权重计算最短路径进行路由. 而节能路由的主要设计思路是先休眠利用率低的链路集合，将本该处于休眠链路的业务流量，导向其他非休眠链路. 由于要最大限度地节能，则应该以最小数目的链路满足业务的需求，使更多的链路上没有业务量经过. 整个网络流量应该处于两级分布，使经过链路的流量要么很低，要么很高. 在IP网络中，业务根据最短路径进行转发，业务集中在最短路径上，比较空闲的链路大多不在最短路径上. 因此，链路的权重决定了业务的流量分布.
如图 3所示，网络拓扑有5个节点和7条链路，假设节点a向节点e发送6个单位的业务，经过的2条最短路径分别为a—b—d—e和a—c—b—d—e. 其中，括号左边为链路的权重，括号右边为流经链路的业务流量. 从图 3可以看出，权重与流量是负相关的关系. 通过仿真，同样也验证了权重与流量的关系：权重越小的链路其流量越大，权重越大的链路其流量越小，甚至无流量经过. 因此，可通过优化链路权重来得到需要的流量分布，从而达到节能的目的.
 | 图3 拓扑的权重与业务流量分布 |
目前，优化IP网络链路权重的启发式算法有很多种. 笔者选择Fortz等[5]提出的邻域搜索算法来优化链路权重，建立以最小化最大链路利用率为优化目标的数学模型，使用与链路利用率呈正相关的函数作为评估代价的准则. 同时，使用基于链路权重的向量邻域搜索方式. 而笔者的目标是希望流量集中在某些链路上，其余的链路上没有流量经过. 两者之间存在目标函数的差异，但均衡负载和节能的过程是相似的，笔者仍可用邻域搜索的方法来节能，只是权重的搜索和调整方法发生了改变.
邻域搜索的主要思想是初始化1套权重向量，进行能耗评估，根据权重调整策略对初始权重向量进行调整，一直迭代，调整权重找到更优的解(即最小的能耗). 基于启发式领域搜索的节能算法如下.
1) 初始化权重向量(设为1)和其他变量，搜索次数z=0，搜索面积q=0；
2) 根据权重调整策略对链路权重进行调整，生成1套新的权重向量；
3) z=z+1，判断是否达到搜索次数，如果是，转入步骤8)；如果否，转入步骤4)；
4) 根据最短路径算法计算业务节点对之间的最短路径，得到整个网络的流量分布，从而可知各条链路的开关状态(休眠流量为0的链路)，根据式(4)的目标函数得到此权重向量下的能耗；
5) 对得到的能耗进行评估，判断是否同时满足式(7)的链路容量约束和小于当前的最小能耗，如果同时满足，则更新当前最小能耗，并更新当前最优权重向量，更新q=0，转入步骤7)；如果否，转入步骤6)；
6) q=q+1，判断是否达到搜索面积，如果否，转回步骤2)；如果是，进行权重向量扰动，z=z+1，转入步骤7)；
7) 判断是否达到搜索次数，如果否，转回步骤2)；如果是，转入步骤8)；
8) 算法结束.
在步骤6)中进行权重向量扰动，是因为邻域搜索算法主要是一种对权重向量进行搜索得到最优解的算法，并不是搜索全局最优解的算法. 因此，当算法在权重向量的搜索过程中，一直不能得到更优的解，就需要对权重向量进行扰动，避免陷入局部最优解. 具体做法是以一定的概率p来改变每条链路的权重，得到新的权重向量，重新进行能耗评估.
对于步骤2)的链路权重调整策略将在下面详细说明.
由式(3)可知，链路利用率为l/c. 其中：l为链路负载，c为链路容量. 在IP网络中，链路权重与业务负载呈负相关的关系，可根据链路利用率来调整权重：对于链路利用率较高(超过某个利用率门限值，设为Thigh)的链路，尝试增加其权重，使其被业务选择作为转发路径的概率减少，从而达到降低该条链路的利用率、避免拥塞的目的；对于链路利用率较低(低于某个利用率门限值，设为Tlow)的链路，也尝试增加其权重，降低其被业务选择作为转发路径的概率，使该条链路的利用率能朝着0的方向移动，当链路利用率为0时，休眠该条链路；对于利用率在两者之间的链路，尝试减少其权重，增加其被业务选择作为转发路径的概率. 总体上，低利用率和高利用率的链路上的业务向中间利用率的链路上移动，使流量呈两级分布，集中在中间利用率的链路上. 由此，既能保证链路容量约束，又能最大限度地节能.
笔者将链路的高利用率门限Thigh取值9/10，低利用率门限Tlow取值1/3，是因为利用率超过9/10的链路已经比较拥塞，耗费的代价明显增大，而利用率低于1/3的链路花费的代价是一样的，都较小. 利用率超过100%再增加权重，链路仍有可能还是拥塞的，达不到预期消除拥塞的效果，且耗费的代价剧增，链路拥塞又会影响网络性能，所以应在链路利用率超过9/10时就增加权重. 总体来说，权重增加或减少的幅度不宜过大，小幅度的调整权重不易漏掉最优解. 由于初始化链路权重设为1，权重的增幅单位可设为1，具体链路权重的增减方式为
$\left. \begin{align}
&w‘=1+{{w}_{l}},l/c>9/10 \\
&w‘=1+{{w}_{l}},l/c<1/3 \\
&w‘={{w}_{l}}-1,1/3<l/c>9/10 \\
\end{align} \right\}$
(4)
为了验证所提ESPMT算法的性能，下面将ESPMT算法分别在时间片的划分和节能子拓扑设计方面与现有的算法进行仿真对比分析.
3.1 时间片划分对比分析下面通过Matlab将ESPMT算法与等时间片划分法进行对比分析. 2种算法各个时间片划分下的冗余流量变化如图 4所示.
 | 图4 不同时间片下的冗余流量变化 |
从图 4可以看出，随着时间片数目的增加，无论是等时间片划分法，还是ESPMT算法，得到的预估流量都越来越小. 在同样时间片划分个数的条件下，采用ESPMT算法比采用等时间片划分法所得的冗余流量更小，更符合实际的业务流量. 当时间片个数达到一定数目时，ESPMT算法相比等时间片划分法的性能优势在逐步下降直至完全相同.
3.2 节能子拓扑设计对比分析为了更好地验证ESPMT算法的节能效果，下面利用C+ +仿真将其与能量感知路由(EAR，energy-aware routing)算法、基于代数连通度节能(ESACON，energy saving based on algebraic connectivity)算法、最小流量(LF，least flow)算法[1, 2, 3, 4]进行对比. EAR算法选择部分路由器的最短路径树用做路由路径，没有参与路由的链路进入休眠状态. ESACON算法以网络的连通性作为第一目标，关闭对网络连通性影响小的链路来节能. 但上述2种方法并没有考虑链路的容量约束，在业务流量高的情况下，网络可能遭受链路拥塞的风险. LF算法基于最小流策略，根据链路的负载对全网链路按升序排列，逐一地关闭空闲链路，直到网络连通性无法满足或有工作链路拥塞为止. 上述策略无法对全网工作链路上的流量进行引导，可能会出现某些链路拥塞，而其他链路利用率很低的情况. 在算法的执行过程中，为了满足链路容量约束，不能持续关闭低利用率的链路，导致无法实现最大限度地节能.
仿真拓扑包括具有20个节点、32条链路的APARNET网络和具有24个节点、42条链路的USANET网络，所有的链路都是双向链路. 邻域扰动的权重是随机产生的，范围为1~40. 搜索次数设为3000，搜索面积设为100. 在邻域扰动中，以p=0.3的概率来改变权重向量的分量. 业务量矩阵根据各个时间片的峰值业务量得到，链路的容量则根据峰值业务量来设置. 假设每条链路开启时的能耗是相等的，此时的目标函数可从最小化能耗简化为最小化工作链路数的总和.
由于ESPMT算法是利用波峰来划分时间片的，该算法从上午5：00开始将1d划分为6个时间片，依次命名为1～6. 然后在每个单独的时间片上分别取其峰值业务量作节能设计，其中时间片4取的是1d中的最大业务量. 图 5所示为ESACON、LF、EAR和笔者提出的ESPMT 4种节能算法在2个网络拓扑中1d内不同时间片下的能耗对比. 从图 5可以看出，ESPMT算法的节能效果优于其他3种节能算法，EAR和ESACON的能耗没有随着流量的变化发生改变，LF和ESPMT的能耗随着业务的增加也相应地增加. 这是因为EAR和ESACON都没有考虑流量的需求. EAR将路由器分类，然后休眠不在最短路径树上的链路，只适用于流量低的时间段内；ESACON只针对拓扑的本身结构，关闭对网络连通性影响小的链路来节能，与业务流量无关；LF虽然考虑了业务和物理容量约束的需求，但只是在满足连通性和最大链路利用率约束的情况下才关闭链路，并没有对链路的流量进行引导，导致不能最大限度节能；ESPMT算法则根据给定的流量矩阵，不仅确定了网络的拓扑结构，还通过调整权重生成1套最优的权重向量，对全网链路的流量朝着节能方向进行引导，因此可以最大限度地节能，其节能效果优于其他3种算法.
 | 图5 2个网络拓扑能耗对比 |
图 6所示为在用2种时间片划分法下(都为6个 时间片)通过邻域搜索得到的能耗对比. 从图 6可以看出，在用ESPMT算法划分的时间片下得到的能耗比等时间片划分法更低，节能效果更好. 验证了在相同的时间片数目(不超过14个)下，ESPMT算法得到的冗余流量更小，更贴近实际的业务流量，从而有更好的节能效果.
 | 图6 2种时间片划分法下的能耗对比 |
提出了一种基于预置多拓扑的IP网络节能算法. 该算法根据日常的流量曲线提出了波峰分割法，将1天合理地划分为多个时间片，在划分好的单个时间片内，提出了基于启发式邻域搜索的节能策略作节能子拓扑设计. 通过仿真实验证明，该算法能有效地降低能耗，相比现有的IP网络节能算法，节能效果更好.
| [1] | Cianfrani A, Eramo V, Listanti M, et al. An energy saving routing algorithm for a green OSPF protocol[C]//Proceedings of the IEEE INFOCOM 2010. San Diego, CA, USA:IEEE, 2010.[引用本文:2] |
| [2] | Cuomo F, Abbagnale A, Cianfrani A, et al. Keeping the connectivity and saving the energy in the Internet[C]//Proceedings of the IEEE INFOCOM 2011. Shanghai, China:IEEE, 2011.[引用本文:2] |
| [3] | Jamakovic A, Uhlig S. On the relationship between the algebraic connectivity and graph's robustness to node and link failures[C]//NGI 2007. Trondheim, Norway:IEEE, 2007.[引用本文:2] |
| [4] | Chiaraviglio L, Mellia M, Neri F. Reducing power consumption in backbone networks[C]//Proceedings of the IEEE ICC 2009. Dresden, German:IEEE, 2009.[引用本文:2] |
| [5] | Fortz B, Thorup M. Internet traffic engineering by optimizing OSPF weights[C]//Proceedings of the IEEE INFOCOM 2000. Tel Aviv, Israel:IEEE, 2000.[引用本文:2] |