基于区域扩展的绿色业务量疏导算法

王汝言，徐 印，吴大鹏，彭海英

(重庆邮电大学光互联网及光信息处理研究所，重庆 400065)

0 引言

随着因特网的持续发展，对网络的带宽需求日益增加。主干网络上的资源(例如，路由器)通常提供2倍于当前峰值的业务需求，以应对未来业务量的快速增长。在大多数情况下，资源处于完全激活状态。对于互联网业务来说，业务请求的产生具有突发特性。因此，资源在大多数时间内都将处于未使用状态，从而导致了不必要的功耗和操作开销。研究功耗有效性方法，有效地节约了网络功耗，减少了网络成本。然而，除了经济原因外，环境因素也是一个非常重要的缘由。据美国能源信息管理局调查统计表明，每一千瓦时的发电量平均排放1.35磅二氧化碳。因此，提倡建立一个绿色因特网成为一个社会性、政治性、商业性的问题。

文献［1-2］探讨了业务量疏导在光网络中减少网络功耗的作用。在业务传输过程中，网络元器件的功耗由与业务量不相关的固定功耗和与业务量相关的边际功耗组成，与业务量大小成正比［3］。业务量疏导可以将多个低粒度的业务请求汇聚到一个光通道中传输［4］，有效减少了单位业务量的固定功耗开销，节约了网络功耗。文献［5-9］探讨了如何限制激活元器件的数量，实现绿色网络的目标。文献［5-6］研究动态情况下，根据链路负载状况，调整链路上元器件状态，减少激活元器件数量，并且重新路由原链路上的业务请求。文献［7-9］研究静态情况下，疏导业务时，优先选用已经激活的元器件，避免激活新的元器件，减少激活元器件的数量，减少网络功耗。文献［7-8］提出以网络功耗最小为目标的业务量疏导方法，在网络功耗方面，相比传统方法有了很大的提高，但是没有仿真验证新方法对阻塞率的影响;文献［9］构造了W+5分层图模型，基于此模型，提出2种新的启发式绿色业务量疏导算法:①基于业务请求带宽大小的绿色业务量疏导算法(RSB-energy aware);②基于链路利用率的绿色业务量疏导算法(LUB-energy aware)。仿真结果表明，在网络功耗方面，新算法性能优异，但是在阻塞率方面，新算法阻塞率较高，影响了网络疏导能力。因为新算法为了最大程度地利用处于激活状态的元器件，会产生过长路由，耗用过多的网络波长资源，造成较高的阻塞率。此结果与传统经典的以最小化网络资源和最小化业务请求阻塞率为目标的业务量疏导算法相矛盾。

本文综合考虑了网络功耗和网络资源的问题，提出一种全光网络中基于区域扩展的绿色业务量疏导(green traffic grooming in zone-based scalable optical networks，GTGZ)算法，其基本思想是通过在一个区域变化的网络中寻找以功耗为代价权值的最短路由，不仅考虑了网络功耗，同时避免了产生过长的路由，有效地利用了网络资源，降低网络阻塞率。

1 GTGZ算法

1.1 网络模型

分层图模型(W+2)的作用在于它可以模拟光网络中物理元器件，波长和光路之间的关系。在此结构中，根据不同的疏导策略，调整分层图中边的权值，可以寻找到最佳路由。文献［9］提出了模块化的节点结构，用于统计光域模块的功耗，并且由此产生了一种新的分层图模型(W+5)。同传统模型相比，W+5分层图模型添加了3个模块层(chassis层，module层和port层)，当疏导业务请求时，用于统计网络消耗的总功耗。在该模型上，当赋给收发器边(transceiver edge)较大权值，计算路由，可以实现最少光路数算法(MinLP)。而根据模块chassis，module，port的实际功耗，赋给对应边相应的权值计算路由，可以实现绿色业务量疏导算法。

1.2 区域扩展

传统的绿色业务量疏导算法在追求功耗最小化时，通常是在完整的网络拓扑上使用最短路由算法寻路，在路由过程中，容易产生过长路由，导致资源利用不均衡，增加网络阻塞率。为了解决这个问题，在不改变优化目标和路由策略的前提下，采用区域扩展的方法，在一个缩小的区域网络中，使用最短路由算法，寻找最佳路由，可以有效地避免产生过长路由，降低了网络的阻塞率。区域网络的大小与每个业务请求的初始候选节点、区域的扩展次数以及每次扩展的节点个数相关。该区域网络可以根据需要动态扩大，确保光路选择的灵活性［10］。

1.2.1 初始候选节点

与传统路由方法不同，区域扩展的方法首先需要确定一组候选节点，由这些候选节点集合构造一个区域辅助图，再根据需要不断地添加新的节点直到寻找到合适路由为止。通常而言，选择物理拓扑的最短路由节点集合作为区域的初始拓扑大小。但是，随着业务请求数量的增加，物理拓扑的链路代价值不断变化，在高负载的情况下，最短路由会很长，它所包含的节点数量也会很多，造成了区域扩展对网络阻塞率性能的改善效果不理想，因此，选择源节点和目的节点作为初始候选节点集合。

1.2.2 邻近节点

如果在区域辅助图中寻找通路失败，首先在虚拓扑上选择邻近节点集合，扩展辅助图。

(1)式中:PW(i，V)表示虚拓扑上节点i到集合V中的每一个节点j的所有最小功耗的平均功耗值;PW0(i，j)表示虚拓扑上节点i到节点j的最小功耗值;V表示当前辅助图节点集合。N(q，V)表示虚拓扑上与集合V相邻的q个节点的集合。根据P(i，V)大小关系，对所有非V集合中的节点升序排列，选择P(i，V)值最小的 q个节点，确定 N(q，V)。

当在虚拓扑中出现了比较多的平均功耗值相同的节点时，优先选择路由中物理链路条数最少的节点作为邻近节点。当前网络状况如图1所示，假设一个源节点为8，目的节点为6，带宽大小为r的业务请求(8，6，r)等待被传输。当前网络中已经存在的光路为l1～l7，假设每次扩展节点个数q等于2，根据公式(1)得到虚拓扑上的节点 7，9，10，11，12，14，20的平均功耗值均为(1×Pchassis+1×Pmodule+1×Pport)×0.5，此时，根据优先选择源与目的节点物理链路跳数最少的节点的原则，对节点依次排序，确定N(q，V)。此处，优先选择节点7或节点9。

当虚拓扑上所有节点都加入到辅助图后，在辅助图上仍然无法成功寻找到通路，则需要从物理拓扑中选择邻近节点集合，扩展辅助图。

(2)式中:p(i，V)表示物理拓扑上节点i到集合V中业务请求数与网络中的业务请求总数之比。

网络功耗:在给定的网络拓扑和业务需求下，成功疏导业务请求所使用的元器件功耗的总和。

平均功耗:在给定的网络拓扑和业务需求下，成功疏导业务请求时单个业务请求使用的平均功耗。

图3 算法流程图Fig.3 Algorithm flowchart

2.2 仿真分析

本文采用C/C++语言搭建仿真平台，对算法建立的网络功耗、阻塞率和平均功耗进行仿真统计。采用24节点网络作为仿真拓扑，如图4所示。每个节点最多分配2个 chassis，2个module/chassis和2个port/module，在Cisco Catalyst 6500系列产品中，每个元器件的功耗大约为 375W/chassis，315 W/module，3 W/port［11］。网络中每条链路的波长数都为8，每个波长支持的带宽粒度为OC－192。网络中业务请求采用多带宽粒度，分别为OC－3，OC－12，OC－48和OC－96，各带宽粒度的业务请求个数的比例为1∶3∶3∶1。业务需求矩阵随机产生，业务请求均匀分布到所有节点对中。

2.2.1 阻塞率

GTGZ算法在阻塞率方面的性能表现如图5所示。当扩展次数K逐渐增大时，阻塞率不断减小。传统业务量疏导算法、RSB-Energy aware算法和GTGZ算法在阻塞率性能上的比较如图6所示。对比发现，随着网络负载的增加，由于RSB-Energy aware算法在寻路时，需要最大程度重复使用已激活的元器件，产生了较长的路由，从而导致网络资源的过度消耗，在阻塞率方面的性能最差。而GTGZ算法通过网络扩展的方式，限制每次寻路时网络拓扑的大小，减少了路由长度，从而节约了网络的波长资源，有效地降低了阻塞率。随着扩展次数K值不断增大，算法在阻塞率方面的性能优势会越来越明显。当扩展次数K值较大时，网络每次扩展的幅度更小，路由相对更短，消耗的网络资源更少，在阻塞率方面的性能更加优异。图6中，当K=22时，GTGZ算法的阻塞率优于传统业务量疏导算法。

2.2.2 网络功耗

传统业务量疏导算法，RSB-Energy aware算法和GTGZ算法在网络功耗性能上的比较如图7所示。对比发现，RSB-Energy aware算法在网络功耗方面的性能最好，而在GTGZ算法中，当扩展次数K为1时，算法过程同RSB-Energy aware相同，所以达到的性能效果完全一样，但是，当扩展次数K不断增加时，每一次区域网络扩展的幅度会逐渐地变小，寻找到的最优路由会激活更多的元器件，造成网络功耗的增加。

图7 GTGZ算法的网络功耗Fig.7 Power consumption of GTGZ algorithm

图6和图7表明，当K=22时，在阻塞率方面，GTGZ算法优于传统业务量疏导算法，同时，在网络功耗方面，GTGZ算法也优于传统业务量疏导算法。

2.2.3 平均功耗

传统业务量疏导算法、RSB-Energy aware算法和GTGZ算法在平均功耗性能方面的比较如图8所示。因为在疏导过程中没有考虑到网络功耗的因素，在寻找路由时，为了使用最少的光路，建立了更多新的光路，激活更多的元器件，导致了传统业务量疏导算法平均功耗最大。当负载较低时，GTGZ算法在有限区域内寻找路由，选择了较短的路由，但是仍然会比RSB-Energy aware算法激活更多的元器件，所以，它的平均功耗比RSB-Energy aware算法的平均功耗高;当负载较高时，RSB-Energy aware算法阻塞率高，疏导成功的业务请求数较少，但是GTGZ算法因为选择了较短的路由，提高了网络波长资源的利用率，降低了阻塞率，成功疏导了较多的业务请求，而且网络功耗也要比传统业务量疏导算法低，所以它的平均功耗最低。

3 结束语

功耗有效性和网络阻塞率是2个互相冲突的性能指标。在只考虑功耗有效性的算法中，为了最大化使用已激活元器件，使工作路径变得很长，波长链路资源也会相应的增加，结果导致了业务阻塞率的提高。而本研究通过在绿色业务量疏导算法中引入区域扩展的方法避免了这一问题。仿真结果表明，当扩展次数较大时，GTGZ算法在网络功耗、阻塞率和平均功耗方面的性能都优于传统业务量疏导算法。并且，当网络负载较高时，GTGZ算法的平均功耗最小。

图8 3种算法平均功耗比较Fig.8 Average power consumption comparison of three algorithm

［1］YETGINER E，ROUSKAS G N.Power efficient traffic grooming in optical WDM networks［C］//IEEE.Global Telecommunications Conference.USA:IEEE Press，2009:1-6.

［2］XIA Ming，TORNATORE M，ZHANG Yi，et al.Green Provisioning for Optical WDM Networks［J］.IEEE JSTQE，2011，17(2):437-445.

［3］CHABAREK J，SOMMERS J，BARFORD P，et al.Power awareness in network design and routing［C］//IEEE.INFOCOM'08.USA:IEEE Press，2008:457-465.

［4］JIA Peng，LI Jian，GU Wan-yi.A New Approach for Multicast Traffic Grooming in Optical Networks［J］.Journal of Beijing University of Posts and Telecommunications，2006，29(4):41-44.

［5］CERUTTI I，SAMBO N，CASTOLDI P.Distributed Support of Link Sleep Mode for Energy Efficient GMPLS Networks［C］//ECOC.2010 36th European Conference and Exhibition on Optical Communication.Italy:IEEE Press，2010:1-3.

［6］ANGELO C，MARCO L，ALESSANDRO V，et al.Reducing Power Consumption in Wavelength Routed Networks by Selective Switch Off of Optical Links［J］.IEEE JSTQE，2011，17(2):428-436.

［7］WU Y，CHIARAVIGLIO L，MELLIA M，et al.Power-Aware Routing and Wavelength Assignment in Optical Networks［C］//ECOC.2009 35th European Conference on Optical Communication.Vienna:IEEE Press，2009:1-2.

［8］CAVDAR C，BUZLUCA F，WOSINSKA L.Green Design of Survivable WDM Networks with Shared Backup［C］//IEEE.2010 GLOBECOM.USA:IEEE Press，2010:1-5.

［9］HASAN M，FARAHMAND F，PATEL A，et al.Traffic grooming in green optical networks［C］//IEEE.2010 IEEE International Conference on Communications.USA:IEEE Press，2010:1-5.

［10］DRUMMOND A C，FONSECA A S L.Fairness in Zone-Based Algorithms for Dynamic Traffic Grooming in WDM Mesh Networks［J］.IEEE Journal of Optical Communications and Networking，2010，2(6):305-308.

［11］ANANTHANARAYANAN G，KATZ R H.Greening the Switch［C］//ACM.HotPower'08 Proceedings of the 2008 Conference on Power Aware Computing and Systems.USA:USENIX Association Berkeley，2008:7-17.