基于约束路由的绿色虚拟拓扑设计算法

伍元胜，郭兵，沈艳，王继禾，刘啸滨

(1. 四川大学 计算机学院, 四川 成都 610065；2. 成都信息工程学院 控制工程学院, 四川 成都 610225)

1 引言

近年来，Internet的流量逐年指数增长。从2007～2011年，Internet的流量和带宽的年平均增长率分别达到了56%和58%[1]。流量和带宽的增长导致了Internet的能耗上升。据估计，2007年Internet的电力消耗达到了宽带接入国家（其平均接入带宽为30 Mbit/s）总电量的1%，当平均接入带宽达到300 Mbit/s时，这个比例将超过4%[2]。按照目前的增长速度，到2050年网络领域的耗电量将达到2006年的13倍[3]。Internet能耗的快速增长不仅导致电力成本的持续上升，同时也造成温室气体的加速排放。因此，提高能量效率和降低能耗已成为Internet面临的重大研究课题。目前，随着网络的扁平化发展，Internet的层次变得更加简单，逐渐演变成由接入网和核心网两部分组成。由于接入网的“光进铜退”以及核心网对接入网流量的汇聚，核心网正经历比接入网更快的能耗增长。研究表明到2017年核心网能耗将超过接入网[4]。因此，在整个Internet中，核心网的节能研究正变得日益重要。

网络按照峰值业务需求超额供给[5]网络资源，并通过冗余设计来提高网络的可靠性，这导致了网络资源的平均利用率低下，而当前利用率对网络资源的功耗影响却较小[6～8]，因此，提高网络资源利用率并将空闲的网络资源关闭（或转入低功耗睡眠状态）是目前降低核心网能耗的一个重要途径。目前，主要有如下文献研究此问题。Chabarek等人[9]利用混合整数线性规划(MILP, mixed integer linear programming)技术建模功率感知的网络设计和路由问题，通过为网络节点选择合适数量和类型的线卡最小化IP网络的功耗，但却没有设计有效的启发式算法来求解NP难的MILP模型。文献[10]将IP网络的绿色流量工程形式化为一个MILP模型，并提出了一种启发式算法，通过预先为每对节点计算k条候选最短路径来降低MILP问题的解空间和求解时间，但是，解空间依然随节点对的数量指数增长。文献[11]提出了一种基于拉格朗日松弛的启发式算法，将建立的形式化模型分解为容易求解的子问题，为链路设定合适的权值进行动态路由，关闭尽可能多的链路以降低IP网络的能耗。与文献[9～11]改变已有的网络拓扑不同，文献[12,13]考虑核心网的层次结构，通过改变IP层的虚拟拓扑降低网络能耗。其中，文献[12]考虑光收发器和电交换的功耗，将功率感知的虚拟拓扑设计形式化为MILP问题，并提出一个简单的贪婪算法和遗传算法求解。该遗传算法并没有相应的机制保证得到的后代个体满足MILP模型的约束条件，而是简单的舍弃不满足约束的个体，这会导致算法有时找不到可行解。文献[13]只考虑线卡的功耗，将最小化能耗的虚拟拓扑设计问题形式化为一个简单的整数线性规划(ILP,integer linear programming)模型，并提出了一个两阶段的启发式算法。由于只考虑了线卡的功耗，建立的ILP模型过于简单，网络倾向于建立一个星型虚拟拓扑，最小化链路的数量。

笔者认为，现有工作存在以下不足。首先，这些文献都只考虑网络设备的部分组件的功耗，如链路、收发器或线卡，忽略了其他部分的功耗，这样使得最终得到的解只能使整个网络中的这些组件的功耗最低，而不是整个网络的功耗最低。其次，核心网络的网络设备通常采用模块化设计，现有的工作没有考虑网络设备的模块化结构。第三，由于问题的复杂性（NP问题），现有工作要么建立的形式化模型过于复杂，以至于不能有效求解，如文献[9,10,12]，要么建立的模型过于简化而忽略重要特性，如文献[11,13]只考虑链路或线卡功耗，忽略了IP路由器处理流量的功耗。本文研究的内容与文献[12,13]相似，即以最小化网络功耗为目标的绿色虚拟拓扑设计(GVTD, green virtual topology design)问题。本文首先对GVTD进行形式化建模，该模型（即GVTD模型）通过业务路由实现对业务流的汇聚和疏导以提高网络资源利用率，根据网络资源的实际利用按需地配置网络资源以实现网络设备的多粒度睡眠，根据网络资源配置动态地建立虚拟拓扑，从而达到降低网络能耗的目的。GVTD模型考虑整个网络设备的功耗，目的是降低整个网络的功耗。其次，GVTD模型考虑了网络设备的模块化结构，利用多粒度睡眠机制配置网络资源。第三，GVTD模型根据功耗与业务负载的依赖关系，同时考虑了不依赖业务负载的静态功耗和依赖业务负载的动态功耗。最后，GVTD模型是一个NP难的ILP问题，只能在问题规模很小时精确求解，本文提出了一个基于约束路由的启发式算法，即CBR-GVTD算法。本文的主要贡献如下。

1) 对绿色虚拟拓扑设计问题进行形式化建模，即GVTD模型，该模型通过业务汇聚提高网络资源利用率，按需配置网络资源和动态建立虚拟拓扑，从而达到降低网络功耗的目的。

2) 提出了一种基于约束路由的启发式算法，即CBR-GVTD算法，该算法使用基于约束的路由算法保证链路容量约束和最大路由跳数约束，在提高网络资源利用率的同时实现了虚拟拓扑对业务路由的动态适应。

3) 通过模拟实验从网络功耗、资源利用率和路由性能3个方面对CBR-GVTD算法的性能进行了评估，结果表明CBR-GVTD算法在保证路由性能的条件下获得很高的资源利用率，最多可降低62%～90%的网络功耗。

4) 探讨了网络最大路由跳数对网络功耗的影响，发现可在网络功耗无明显增加的条件下大大降低网络的最大路由跳数。

2 GVTD问题的形式化描述

本节对GVTD问题进行形式化描述，建立GVTD模型。在此之前，有必要对核心网的虚拟拓扑设计、网络设备的模块化结构和多粒度睡眠机制进行介绍。在核心网中，IP网络层通常构建于高速的TDM(time division multiplexing)网络层或者WDM(wavelength division multiplexing)网络层之上[14]，形成所谓的IP over SONET/SDH/OTN网络或IP over WDM网络。下层网络（即TDM层或WDM层）向IP层提供通道传输服务（即TDM电路服务和光路服务，电路和光路统称为传输通道），IP层通过使用下层提供的通道传输服务向其上层提供分组传输服务。IP层的链路由1条或多条具有相同源节点和目的节点的传输通道组成，这种链路不同于传统的物理链路，因此被称为逻辑链路，由逻辑链路构成的网络拓扑被称为虚拟拓扑（或逻辑拓扑）。根据给定的业务需求建立IP层逻辑链路的过程即为IP层的虚拟拓扑设计（VTD, virtual topology design）过程。对于IP层，下层提供的传输通道组成了其逻辑链路；对于下层网络，IP层请求建立的传输通道形成了其业务需求。

根据核心网的网络设备的模块化结构把网络资源注1注1： 网络资源通常具有很宽泛的含义，本文只关心与网络功耗相关的网络资源，因此，后文的网络资源特指接口、线卡和机框。注2：在网络优化中，拥塞被形式化为网络接口（或链路）的最大利用率。分成接口、线卡和机框3类：接口由一对发送/接收端口组成，每条传输通道起始于源节点的1个发送端口并终止于目的节点的1个接收端口；线卡由一组接口所共享，能够与这组接口同时处于空闲或活跃状态；除接口和线卡以外的部分全都归入机框的范畴。基于这种分类，提出一种多粒度睡眠机制来配置网络资源：当接口空闲时让接口睡眠，当线卡的所有接口都空闲时则线卡睡眠，当所有线卡都空闲时则机框睡眠。

GVTD模型假定网络资源按照峰值需求供给，即每个网络节点具有充足的接口、线卡和机框；下层网络可以提供IP层所需的传输通道。GVTD模型主要包括以下四部分。

1) 网络功耗模型，即GVTD模型的目标函数。网络功耗模型同时考虑网络设备的静态功耗和动态功耗，静态功耗指网络设备独立于业务负载的那部分功耗（即空闲状态下的功耗），动态功耗指网络设备依赖业务负载的那部分功耗。根据网络设备的模块化结构，静态功耗可以进一步细分为接口功耗、线卡功耗和机框功耗。目前利用率对网络设备功耗的影响较少，文献[14]实验测得网络交换机的功耗变动范围（即动态功耗）仅为15%。

2) 业务路由，即GVTD模型的路由约束，为了避免多径路由引发的时延抖动，GVTD模型使用单径路由。

3) 资源配置，即GVTD模型的资源约束，该约束确定每个节点的活跃网络资源，并按照多粒度睡眠机制使空闲的网络资源睡眠。

4) 虚拟拓扑设计，对应于GVTD模型的链路容量约束，该约束确定网络中需要建立的传输通道。此外，笔者通过设定接口最大利用率参数实现了对网络拥塞注2注1： 网络资源通常具有很宽泛的含义，本文只关心与网络功耗相关的网络资源，因此，后文的网络资源特指接口、线卡和机框。注2：在网络优化中，拥塞被形式化为网络接口（或链路）的最大利用率。的控制。

GVTD模型的输入参数定义如下。N表示网络节点集合，i,j,ii,jj∈N表示网络节点，C表示接口的容量，α表示接口（或链路）所允许的最大利用率，pt表示网络资源处理单位(1 Gbit/s）业务负载的动态功耗，pi、pl和pc分别表示单个接口、线卡和机框的功耗，mi、ml分别表示每个线卡具有的接口数量和每个机框可配备的线卡数量，D表示网络的业务需求集合，d(ii,jj)∈D表示从节点ii到节点jj的业务需求。

GVTD问题的决策变量（即GVTD模型的优化参数）定义如下。

1) δ(ii,jj,i,j)∈{0,1}：业务需求d(ii,jj)的路径是否经过逻辑链路(i,j)，1表示经过，0表示不经过。

2) d'(i,j)∈Z+：逻辑链路(i,j)包含的传输通道数量，其中，Z+表示正整数集合，传输通道由下层网络提供，而且每条传输通道需要消耗一个发送端口和接收端口。

3) t(i,j)∈R+：逻辑链路(i,j)上的总业务量，其中，R+表示正实数集合。

4) ni(i)∈Z+：网络节点i的活跃接口数量。

5) nl(i)∈Z+：网络节点i的活跃线卡数量。

6) nc(i)∈Z+：网络节点i的活跃机框数量。

其中，δ(ii,jj,i,j)和t(i,j)表示网络的业务路由，d'(i,j)表示虚拟拓扑，ni(i)、nl(i)和nc(i)表示网络的资源配置。

GVTD问题可以形式化描述为

目标函数(式(1))最小化整个网络的功耗。网络功耗由静态功耗和动态功耗两部分组成，静态功耗可进一步分为机框功耗nc(i)pc、线卡功耗nl(i)pl和接口功耗ni(i)pi；笔者使用线性函数[15]近似动态功耗与业务负载的关系，即t(i,j)pt。由于网络资源的睡眠功耗远远小于活跃功耗，本文忽略网络资源的睡眠功耗。

路由约束（式(2a)～式(2e)）为经典的多品种流守恒[16]约束，业务需求d(ii,jj)经过单条路径从源节点ii到达目的节点jj。式(3)计算经过逻辑链路(i,j)的业务负载（即链路流量），链路的容量约束（式(4)）确保链路的流量不超过链路的容量。IP层的链路(,)ij为逻辑链路，由下层网络提供的'(,)dij条传输通道组成，每条传输通道的容量为C，并引入最大利用率α以应对IP业务的动态特性注3注3：业务需求的动态特性可能导致网络拥塞，将链路的最大利用率限定得越低，产生网络拥塞的概率也越低。GVTD模型通过参数 α调节链路的最大利用率以实现网络拥塞与功耗的折衷。。IP层虚拟拓扑的确立过程即为决策变量'(,)dij的值的确立过程，因此，式(4)在实现链路容量约束的同时还实现了IP层的虚拟拓扑设计，实现了IP层的逻辑链路与下层网络提供的传输通道的映射（即IP层与下层网络的层间约束）。式(5)～式(7)为资源约束。其中，式(5a)和式(5b)可确保节点提供足够的活跃接口，即活跃接口不应该少于传输通道所需的发送端口（式(5a)）和接收端口（式(5b)）。式(6)和式(7)确保节点能提供足够的活跃线卡和活跃机框，即活跃线卡和活跃机框提供的接口数不少于活跃接口数。

3 GVTD模型的求解

GVTD模型是一个ILP模型，由于ILP是NP难问题，在计算资源有限的条件下，目前只可在问题规模很小时进行精确求解。为此，本文提出一种快速有效的启发式算法，将该算法命名为CBR- GVTD算法。CBR-GVTD算法主要考虑和解决以下2个问题。

1) 如何构造可行解，即构造解时应满足GVTD模型的所有约束条件。

2) 如何提高解的质量，即构造的最终解尽可能地近似最优解。

对于第一个问题，首先需要分析各个约束条件以及各个决策变量之间的依赖关系。在GVTD模型中，根据约束条件间的关系可知决策变量存在以下依赖关系：nl(i)和nc(i)都依赖ni(i)，ni(i)依赖d'(i,j)，d'(i,j)依赖t(i,j)，t(i,j)依赖δ(ii,jj,i,j)。因此，根据以上依赖关系，本文使用单跳路由和基于约束的路由（多跳路由）确立δ(ii,jj,i,j)，t(i,j)和d'(i,j)的值，并同时满足式(2a)～式(2e)所示的路由约束、式(3)，和式(4)所示的链路容量约束。然后使用以式(8)～式(10)确立ni(i)，nl(i)和nc(i)的值。

第二个问题涉及如何使目标函数（式(1)）尽可能小。首先，只要能找到目标函数的一个足够大的下界值，通常情况下，可认为该下界值对应的解（不一定可行）与最优解十分接近，因此，在此基础上构造出的可行解通常质量较好。本文通过以下方法计算目标函数的下界值。

下面考虑如何在目标函数下界值LB的基础上构造可行解。由于都依赖d'(i,j)，只需要在的基础上构造可行的即解决业务路由和虚拟拓扑设计2个子问题。通常，网络的总业务量越大，网络需要的活跃接口越多，网络的静态功耗（包括接口、线卡和机框功耗）越大，网络的动态功耗也越大（与总业务量成正比）。因此，对业务需求进行路由时尽可能使用单跳路由，减少网络的总业务量。但是对于较小的业务需求，单跳路由会导致链路的利用率低，造成带宽资源的浪费，因此需要对较小的业务需求使用多跳路由，进行充分的业务疏导。在业务路由方面，本文按从大到小的顺序对业务需求进行业务路由，对较大的业务需求使用单跳路由，对较小的业务需求使用基于约束的路由算法进行多跳路由，并对网络的最大路由跳数进行限制，以实现路由性能与网络功耗的折衷。在虚拟拓扑设计上，本文根据业务路由动态按需建立网络的虚拟拓扑，实现虚拟拓扑对业务路由的适应。

3.1 基于约束路由的Dijkstra算法——CBR-Dijkstra算法

基于约束路由的Dijkstra（CBR-Dijkstra, constraint-based routing dijkstra）算法计算满足链路容量约束和最大路由跳数约束的最短路径（即跳数最少的路径）。CBR-Dijkstra算法与标准的Dijkstra算法的不同之处有以下3点。1）CBR-Dijkstra算法在网络的一个拓扑子图上，使用Dijkstra算法计算跳数最少的路径。该拓扑子图去除了网络中所有可用带宽小于业务需求所需带宽的链路，其中，链路去除是在路由计算过程中通过考虑被处理链路的可用带宽的方式实现。2）在获得最短路径后，判定路径跳数是否小于网络的最大跳数，如果超过最大跳数则表明路由失败。3）当发现有多条跳数相同且都满足链路容量约束的路径时，算法将优先选择可用带宽最小的路径，以提高链路的利用率。

CBR-Dijkstra算法的伪代码如下所示。在本文的伪代码中，语句块以左花括号{开始，以右花括号加end 和对应的关键字结束，如 }end if, }end for, }end while。

此算法的输入包括业务需求d(i,j)、网络节点集合N、网络链路集合E、网络链路的可用带宽集合B和网络的最大路由跳数H。算法输出为d(i,j)的路径。在算法中，predecessor(v)记录节点v的前驱节点，hops(v)记录从源节点i到节点v的最小跳数，visited(v)标识节点v是否已被访问，pb(v)表示从节点i到节点v的路径的可用带宽，b(u,v)∈B表示链路(u,v)的可用带宽，Q为候选节点列表。算法的1)～7)行首先进行一些初始化工作，然后从源节点i开始(第8)行)，计算源节点i的最短路径生成树，直到计算出到目标节点j的路径时停止(第9)～25)行)。算法只考虑可用带宽大于业务需求的链路（第12行），当跳数相同时，优先选择可用带宽最小的路径(第18)～22)行)。算法最后判定计算的最短路径是否小于网络的最大跳数H(第26)行)，如果路由成功，则返回前驱节点表示的最短路径(第27)行)，否则返回空值NIL(第28)行)。

在CBR-Dijkstra算法伪代码中，第一个for循环的执行次数等于网络的节点数，while循环中的for循环最多执行次数等于网络有向边数，对于连通图有，因此，CBR-Dijkstra算法的时间复杂度仅为

3.2 基于约束路由的绿色虚拟拓扑设计算法——CBR-GVTD算法

基于约束路由的绿色虚拟拓扑设计（CBR-GVTD,constraint-based routing green virtual topology design）算法的伪代码如下所示。

此算法的输入包括N、D、α、C、pt、pi、pl、pc、mi、ml和H，其中，H为网络的最大路由跳数，其他符号已在第3节中定义。算法的输出为网络功耗和第3节定义的决策变量。CBR-GVTD算法分2个阶段，即：1）从目标函数下界值构造可行解（第1)～16)行）；2）通过移除利用率低的传输通道对可行解进行优化（第17)～27)行）。

在第1阶段，算法首先根据式(11)用下界值ni(i)lb初始化每个网络节点的接口数ni(i)(第1)行)，然后分两步建立网络的虚拟拓扑。第1步按照从大到小的顺序为每个业务需求d(i,j)建立从i到j的传输通道，并进行单跳路由（第4)、5)、7)行）。每个传输通道消耗源节点i的一个发送端口（sending port）和目的节点j的一个接收端口（receiving port）（第8)行），该过程将持续到接口耗尽、没有传输通道可以建立为止（第6)行）。第2步在第1步建立的虚拟拓扑的基础上，利用单跳路由的剩余带宽，对剩余的业务需求（第1步中未能完成单跳路由的业务需求）按照从大到小的顺序进行CBR-Dijkstra路由（第9)、10)行）。该路由必然是多跳路由，为了防止路由跳数过大，本文限制网络的最大跳数为H。如果业务需求d(i,j)的路由失败（第11)行），则增加节点i和j的接口（因为在第1步中已经耗尽）（第13)行），为i到j建立传输通道并消耗相应的接口数（第12)、15)行），这也意味着网络的虚拟拓扑发生了变化（第14)行）。通过第2步，所有的业务需求都成功完成路由，但是网络的虚拟拓扑可能发生了变化，通过反复迭代使这种虚拟拓扑对业务路由的适应性变化收敛（第2)、3)、14)、16)行）。

在第2阶段，算法初始化链路集合E'为当前的逻辑链路集合E(第17)行)，然后每次从E'中取出剩余带宽最大的逻辑链路(i,j)（第18)行）并将(i,j)从E'中去除（第19)行），尝试移除从i到j的一条传输通道（第20)行），并对经过逻辑链路(i,j)的所有业务需求进行CBR-Dijkstra重路由，如果重路由成功，则释放该传输通道消耗的接口（第21)、22)行），否则恢复移除的传输通道（第23)行）。其中，链路的剩余带宽b(i,j)在每次路由后进行更新，最大的b(i,j)表明链路(i,j)的某条传输通道的利用率最低。至此，虚拟拓扑设计和业务路由已经完成，即δ(ii,jj,i,j)和d'(i,j)的值已经确定。算法移除每个节点剩余（即没用使用）的接口，确立ni(i)的最终值（第24)行），通过式(3)、式(9)和式(10)分别确定t(i,j)、nl(i)和nc(i)（第25)和26)行），最后通过式(1)计算整个网络的功耗（第27)行）。

CBR-GVTD算法通过单跳路由建立虚拟拓扑，对剩余的业务需求使用CBR-Dijkstra算法进行多跳路由。由于单跳路由（算法的第5)、7)和8)行）的时间复杂度为常数级，低于多跳路由（即CBR- Dijkstra算法）的时间复杂度，因此，以CBR- Dijkstra算法为基本操作分析CBR-GVTD算法的时间复杂度。假设第2)～16)行的do-while循环了k次，则第10)行的CBR-Dijkstra算法最多执行为业务需求数）。假设网络的平均路由路数为h，所有业务需求共跳，因此，第21)行共执行次，因此CBRGVTD算法的时间复杂度为k和h通常都很小，在第4节的实验中，k不超过4，h不超过3。

4 性能评估

通过一系列模拟实验从网络功耗、网络资源（即接口、线卡和机框）利用率和路由性能（即平均跳数和最大跳数）3个方面对CBR-GVTD算法进行性能评估，并将CBR-GVTD算法和其他算法的实验结果进行比较，包括：GVTD模型的精确解、网络功耗的下界和上界以及基于拉格朗日松弛的启发式算法（即LR算法[12]）。其中，笔者使用数学工具GAMS/CPLEX[17]求解GVTD模型的精确解，

CPLEX是一种高性能的ILP求解器，采用分支定界算法求解ILP问题，由于ILP问题是NP难的，只能对规模较小的网络精确求解。网络功耗下界LB由式(11)和式(12)求得，网络的功耗上界UB由式(13)和式(14)求得。在式(13)中，每个业务需求(,)dij通过条传输通道进行单跳路由，因此得到节点的接口上界与LB的计算类似，将代入式(9)和式(10)可求得，最后将这些值代入目标函数即得到上界值UB（即式(14)）。LR算法使用拉格朗日松弛技术将ILP模型分解成容易求解的子问题，然后对每个子问题求解并使用次梯次算法求解拉格朗日对偶问题，最后对得到的解进行可行化处理。

为了全面评估CBR-GVTD算法的性能，实验充分考虑了多种不同大小的网络、多种不同大小的业务需求和多种不同大小的网络最大跳数，实验参数设定如下所示。

1) 网络规模。GVTD问题不涉及网络的物理拓扑，因此，只需节点数量即可表示各种大小的网络。实验网络的节点数量分别为10、20、30、40和50。

2) 业务需求。Internet的流量具有重尾分布特性，本文使用重力模型[17]生成重尾分布的业务需求，网络节点间的平均业务需求分别为1 Gbit/s、5 Gbit/s、10 Gbit/s、15 Gbit/s、20 Gbit/s、25 Gbit/s、30 Gbit/s、35 Gbit/s和40 Gbit/s。

3) 网络设备的相关参数以Cisco CRS3-8/S 路由器的规格说明为参考，具体设定如表1所示。

表1 网络设备相关的参数

4) 网络最大路由跳数H的取值分别为1、2、3、4、5和∞，其中，H=∞表示不限制网络的最大路由跳数。

本文对网络规模、业务需求和网络最大路由跳数的多种取值的各种组合（共5×9×6=270种）分别进行实验。为了减小重力模型生成业务需求过程中随机因素可能对实验结果的影响，以上每种组合的实验重复进行10次（共2 700次），每次实验的业务需求使用不同的随机数种子生成，结果取平均值。为了公平地比较CBR-GVTD与GAMS/CPLEX、LU、UB和LR的实验结果，这些算法都使用完全相同的实验参数（包括网络规模、业务需求和网络设备相关参数）。网络最大跳数H为CBR-GVTD算法所独有，在5.1节和5.2节的实验中，网络最大跳数都不受限，即H=∞，在5.3节中将展示H的其他取值下的实验结果，并探讨如何设定H的值。

4.1 网络功耗

GVTD的目标是最小化网络的功耗，考虑到网络业务需求的变化，在理想的情况下，网络功耗应该与网络业务需求成正比，即网络应该具有能量匀增特性[9]。为了评估CBR-VTD算法求得的网络功耗与GVTD形式化模型最优值的差距，首先对规模较小（即10个节点）的网络进行模拟实验，使用GAMS/CPLEX计算GVTD模型的最优解（相对误差限为2%），并将求得的网络功耗与CBR-VTD算法、LR算法以及网络功耗的下界(LB)和上界(UB)进行比较，结果如图1所示。在图1中，网络功耗的上界（UB）和下界LB，CBR-GVTD、LR算法和GAMS/CPLEX求得的网络功耗与业务需求呈现几乎线性增长的函数关系，即表现出一定的能量匀增特性。其中，网络功耗下界(LB)与最优解CPLEX比较接近，这表明LB作为网络功耗下界是十分紧致的，因此，在网络规模更大时（此时，无法用GAMS/CPLEX获得最优解），LB可用于评估CBR-GVTD算法的性能。在图1中，CBR-GVTD介于LR与CPLEX之间，这表明CBRGVTD算法求得的网络功耗比LR算法的更低且更接近于GAMS/CPLEX求得的最优值。

图1 10个节点的网络功耗：CBR-GVTD算法与CPLEX、LR、LB和UB算法的比较

为了进一步评估在其他规模的网络上，CBRGVTD算法求得的网络功耗的性能，本文分别在节点数为20、30、40和50的网络上进行模拟实验，实验结果如图2所示。由图2可知，无论网络节点数为多少，CBR-GVTD都位于LR与LB之间，这说明CBR-GVTD算法求得的网络功耗始终比LR算法的更低，更接近于网络功耗下界(LB)。总之，在网络功耗方面，图1和图2表明CBR-GVTD算法具有比LR算法更优的性能，能够获得接近最优值的网络功耗。Internet按照峰值需求供应网络资源（即超额供给）导致网络资源的平均利用率较低，因此，在大多数时间里业务需求都处于非高峰期，图3为各种规模的网络在业务非高峰期时CBR-GVTD算法节省的最大功耗，即CBR-GVTD算法在业务低峰期(1 Gbit/s)时与业务高峰期(40 Gbit/s)时相比节省的网络功耗。由图3可知，在业务非高峰期时，CBR-GVTD算法最多可节省62%～90%的网络功耗，且该比例随着网络规模的增大不断上升。

图3 不同规模网络在业务非高峰期时节省的最大功耗

4.2 网络资源利用率

GVTD降低网络功耗的一个主要原因在于提高网络资源的利用率，下面从资源利用率方面评估CBR-GVTD算法的性能。图4为CBR-GVTD算法和LR算法在30个节点的网络上求得的网络资源平均利用率，由于节点数为10、20、40和50的网络的资源利率与图4类似，本文仅以30个节点的网络为例说明。在图4中，CBR-GVTD算法和LR算法求得的网络资源的平均利用率都随着网络业务需求的增加而增大，而且，接口和线卡的平均利用率都保持在较高的水平。对于机框和线卡的平均利用率，CBR-GVTD算法和LR算法差别不大，但是，CBR-GVTD算法对应的接口平均利用率比LR算法更高，基本维持在80%～90%的范围内，而LR算法对应的接口平均利用率基本在70%～80%左右，这解释了为什么CBRGVTD对应的网络功耗小于LR算法的网络功耗。总之，图4表明在资源利用率方面，CBR-GVTD算法的性能也优于LR算法，CBR-GVTD算法可以获得很高的资源利用率。

图4 网络资源利用率：CBR-GVTD算法与LR算法比较

4.3 路由性能

通常，业务的传输路径越长，端到端的网络时延也越大，因此，路径长度（即路由跳数）可用于评估CBR-GVTD算法的路由性能。图5为30个节点的网络使用CBR-GVTD算法和LR算法进行10次重复实验得到的平均跳数、最大跳数和每次实验的最大跳数的平均值（即平均最大跳数），图5中，分别用avgHop、maxHop和avgMaxHop标识，CBR-GVTD算法和LR算法的平均跳数都很小（都小于3），其中，CBR-GVTD算法的平均跳数略大于LR算法的，且都随着网络业务需求的增加而减小，表现出较好的路由性能。由图5可知，总体上，最大跳数也随网络业务需求的增加而减小。由于maxHop标识的为10次重复实验中的最大跳数，可能受随机因素的干扰，因而表现出较大的起伏；而avgMaxHop标识的是平均最大跳数，因此更加平滑，反映出最大跳数随网络业务需求增加而变小的趋势。此外，在图5中，CBR-GVTD算法的最大跳数在6～10的范围内变动，明显高于LR算法的最大跳数（变化范围为3～7）。图6为不同节点的网络在各种大小的业务需求下的平均跳数、最大跳数和平均最大跳数。在图6中，LR算法的平均跳数、最大跳数和平均最大跳数随网络节点数的增加而减小，CBR-GVTD算法的平均跳数随着网络节点数的增加几乎保持不变，但是最大跳数和平均最大跳数随着网络节点数的增加而增大。

从平均跳数来看，图5和图6都表明CBR-GVTD算法具有接近LR算法的路由性能，但是最大跳数却比LR算法的大，且随着网络节点数的增加而增大。图7进一步描述了30个节点的网络运行CBR- GVTD算法的跳数分布。在图7中，绝大部分路径的跳数都很小，只有极少数路径的跳数较大。随着网络业务需求的增加，跳数较小的路径所占比例逐渐增大。值得注意的是，在以上实验中，CBR-GVTD算法的网络最大跳数都没有限制，即实验参数H=∞，因此，实验结果也代表了CBR-GVTD算法的最坏路由性能。通过参数H，可对CBR-GVTD算法的最大跳数进行控制。本文对节点数分别为10, 20, …, 50的网络，使用CBR-GVTD算法在H=1,2,3,4,5时进行实验，并用LR算法和下界LB作比较。由于不同节点的网络的实验结果相似，下面仅以30个节点的网络为例说明，网络功耗如图8所示。在图8中，CBR-GVTD算法在H=3,4,5,∞时的网络功耗基本相同，且小于LR算法的功耗。这表明CBR-GVTD算法可在网络功耗基本不变的情况下减小网络的最大跳数，同时获得比LR算法更低的网络功耗和更好的路由性能。

图5 路由跳数与业务需求的关系：CBR-GVTD算法与LR算法比较

图6 路由跳数与网络规模的关系：CBR-GVTD算法与LR算法比较

当最大跳数H进一步减少时，通过图8可以知道，当H=2时，网络节点间的平均业务需求为1 Gbit/s和5 Gbit/s时，CBR-GVTD算法的功耗比H=3,4,5,∞时略高，但随着网络业务需求的增大，H=2时的网络功耗与H=3,4,5,∞时的功耗基本相同。由图5可知，当H=∞，网络节点间的平均业务需求为1 Gbit/s和5 Gbit/s时，CBR-GVTD算法的平均跳数大于2，因此，在图8中，最大跳数限定为2（即H=2）时，网络功耗会有所增加。当H=1时，此时网络的所有业务都使用单跳路由，CBR-GVTD算法的网络功耗即为式(14)的网络功耗上界值UB。因此，通过调节参数H的取值，可以实现网络功耗与路由性能的折衷，为了保证CBR-GVTD算法的性能，建议参数H不应该小于H=∞时CBR-GVTD算法的平均跳数。

图8 CBR-GVTD算法在H不同取值下的网络功耗

5 结束语

本文研究Internet核心网的绿色虚拟拓扑设计（GVTD）问题。GVTD通过业务汇聚提高网络资源利用率、按需配置网络资源实现多粒度睡眠和动态建立网络的虚拟拓扑，以达到降低网络能耗的目的。笔者对GVTD问题进行了形式化描述，建立了GVTD模型。由于GVTD问题是NP难的，笔者提出一个基于约束路由的启发式求解算法，即CBR- GVTD算法。CBR-GVTD算法以网络功耗的下界为基础构造GVTD问题的解，使用CBR-Dijkstra算法以保证链路容量约束和网络最大路由跳数约束。CBR-GVTD算法按照从大到小的顺序处理网络的业务需求：对大的业务需求建立点到点的传输通道并进行单跳路由，从而确定网络的虚拟拓扑；对小的业务需求使用CBR-Dijkstra算法在虚拟拓扑的剩余带宽上进行多跳路由，通过业务疏导[19]提高网络资源利用率。CBR-GVTD算法按需配置网络资源，动态地建立虚拟拓扑，实现了虚拟拓扑对网络业务需求的动态适应，并且可通过调节网络最大路由跳数来实现对路由性能的控制。在不同大小的网络、不同大小的业务需求下，从网络功耗、资源利用率和路由性能3个方面通过模拟实验对CBR-GVTD算法进行了性能评估。实验结果表明，CBR-GVTD算法可在优异的业务路由性能和很高的资源利用率的条件下，获得接近GVTD模型最优值的解；在业务非高峰期时，对于10和50个节点的网络最多可分别降低62%和90%的网络功耗，该比例随着网络规模的增大而上升。

[1] Telegeography[EB/OL].http://www.telegeography.com/product-info/gig/index.php, 2012.

[2] BALIGA J, HINTON K, TUCKER K R S. Energy consumption of the internet[A]. Proc of COIN-ACOFT[C]. Melbourne, AU, 2007. 1-3.

[3] YUN D, LEE J. Research in green network for future Internet[J].Journal of KIISE, 2010, 28(1):41-51.

[4] LANGE C. Energy-related aspects in backbone networks[A]. Proceedings of 35th European Conference on Optical Communication(ECOC2009)[C]. Wien, AU, 2009.1-8.

[5] LIN C, TIAN Y, YAO M. Green network and green evaluation: mechanism, modeling and evaluation[J]. Chinese Journal of Computers,2011, 34(4): 593-612.

[6] HLAVACS H, COSTA G D, PIERSON J. Energy consumption of residential and professional switches[A]. Int Conf on Computational Science and Engineering (CSE’09)[C]. Vancouver, Canada, 2009. 240- 246.

[7] MELLAH H, SANSO B. Review of facts, data and proposals for a greener internet[A]. Proc of Sixth International Conference on Broadband Communications, Networks, and Systems[C]. Madrid, Spain,2009.1-5.

[8] BARROSO L A, HOLZLE U. The case for energy-proportional computing[J]. Computer, 2007, 40(12): 33-37.

[9] CHABAREK J, SOMMERS J, BARFORD P,etal. Power awareness in network design and routing[A]. Proc of the 27th IEEE Conference on Computer Communications (INFOCOM'08)[C]. Phoenix, AZ, USA,2008.457-465.

[10] ZHANG M, YI C, LIU B, etal. GreenTE: power-aware traffic engineering[A]. IEEE Int Conference on Network Protocols (ICNP)[C].Kyoto, Japan, 2010.21-30.

[11] LEE S S W, TSENG P K, CHEN A. Link weight assignment and loop-free routing table update for link state routing protocols in energy-aware internet[J]. Future Generation Computer Systems, 2011,28(2): 437-439.

[12] AHMAD A, BIANCO A, BONETTO E, etal. Power-aware logical topology design heuristics in wavelength-routing networks[A]. 2011 15th International Conference on Optical Network Design and Modeling (ONDM)[C]. Bologna, Italy, 2011.1-6.

[13] COIRO A, LISTANTI M, SQUARCIA T, etal. Energy-minimized virtual topology design in IP over WDM backbone networks[J]. Optoelectronics, IET, 2012,6(4): 165-172.

[14] BERTHOLD J, SALEH A A M, BLAIR L, etal. Optical networking:past, present, and future[J]. Lightwave Technology, 2008, 26(9): 1104-1118.

[15] SIVARAMAN V, VISHWANATH A, ZHAO Z, etal. Profiling perpacket and per-byte energy consumption in the NetFPGA gigabit router[A]. IEEE INFOCOM 2011 Workshop on Green Communications and Networking[C]. Shanghai, China, 2011.331-336.

[16] JENSEN P A, BARNES J W. Network Flow Programming[M]. Beijing: Science Press, 1988.

[17] GAMS/CPLEX[EB/OL].http://www.gams.com/solvers/solvers.htm#CPLEX, 2012.

[18] NUCCI A, SRIDHARAN A, TAFT N. The problem of synthetically generating IP traffic matrices: initial recommendations[J]. ACM SIGCOMM Computer Communication Review, 2005, 35(2) :19-32.

[19] YETGINER E, ROUSKAS G N. Power efficient traffic grooming in optical WDM networks[A]. Proceedings of the 52nd Annual IEEE Global Telecommunications Conference Workshop (GLOBECOM'09)[C]. Honolulu, Hawaii, USA, 2009.1-6.