面向网络能效优化的动态权重队列管理算法

摘要：针对流量传输过程中能效优化的问题，提出一种面向网络能效优化的动态权重队列管理算法DW_WFQ。该算法在加权公平队列（WFQ）的基础上通过动态地分配各类业务流的权重，以更加灵活的方式分配各类业务流的服务速率，进而与连续流速度缩放模型的能效函数相结合，推导出了该调度算法的能耗模型并且对其进行了能效优化。通过Matlab仿真，进行了DW_WFQ、先到先服务（FCFS）和WFQ三种算法的能耗对比，仿真结果表明：所提的流量调度算法在满足业务流服务质量（QoS）约束的基础上，能够有效降低系统能耗。

关键词：网络能耗；动态权重；服务质量

中图分类号：TP393.0 文献标志码：A

0引言

随着互联网的高速发展，网络给人们带来了前所未有的便捷，但是其能量消耗巨大。统计表明，全球互联网消耗的能源约占全球的3%，每年的碳排放量约占全球的2%，甚至超过了全世界航空行业每年的碳排放量，并有持续的增长势头[1-6]。具体地，2011年全球数据中心的耗电量占全球总耗电量的1.1%～1.5%[7]，并预测到2020年该百分比将增长到8%[8]；2012年思科公司估计全球数据流量将以每年70%的增长率递增[9]；美国AT&T的移动数据流量则在2008―2010年增长了5000%[10]。然而传统网络系统设计的两个原则，即超额资源供给和冗余设计，造成了网络的链路节点利用率和能耗效率低下[11]。因此，在保证服务质量（Quality of Service， QoS）的前提下，如何提高网络链路利用率、降低网络能耗成为目前网络研究的一个热点。

一些传统的研究主要是为了提高网络QoS性能，不少学者提出了多种多样的分组调度算法：先到先服务（First Come First Service，FCFS）即是一种特别典型的调度算法，该算法原理简单，易于硬件实现，但是随着互联网的高速发展，FCFS已经无法满足当前QoS的要求并且其能效利用率也相当低下；文献[12]提出了一种比较经典的队列管理算法RED（Random Early Detection），该算法主要解决了由于实时性业务流突发而造成网关偏袒引起的算法不公平性的问题；文献[13]提出的基于比特流模型的公平类调度算法――通用处理器共享（Generalized Processer Sharing， GPS）算法，它为公平类调度提供了理论基础，但是由于它是基于理想流模型把数据包无限细分为无穷小的数据元，而在实际系统中，分组数据的传输是瞬时的，并且数据都是作为数据块间断发送，因此GPS算法只能作为一种理论分析算法；文献[14]提出了一种近似逼近GPS的调度算法――逐一分组通用处理器共享（Packetbypacket Generalized Processor Sharing， PGPS），它把流量包作为处理的最小的数据元按照GPS的处理过程来处理每一个分组；在PGPS的基础上，文献[15]提出了一种针对路由主动队列调度算法――加权公平队列（Weighted Fair Queuing， WFQ），WFQ通过引入了虚拟时钟和虚拟时间函数来近似逼近GPS的一种公平调度算法，但该算法不区分业务流的优先级，业务流严格按照权值比例公平地享有带宽和服务速率。

虽然上述几种算法能够在一定程度上改进网络性能，使业务流QoS得到保障，但是却没有考虑到网络能耗的问题，然而那种只关注性能而不考虑能效的网络将渐渐被绿色网络所取代。在WFQ的基础上，本文推导出一种面向能效优化的流量调度算法――动态权重公平队列（Dynamic Weight_WFQ， DW_WFQ）。该算法针对单节点数据转发场景，在保证了业务流的QoS的前提下，仿真结果表明本文提出的DW_WFQ算法有效地降低了系统能耗。

3仿真结果及分析

本章主要是对DW_WFQ调度算法能耗的分析，然后针对该系统模型进行仿真验证。

不失一般性，考察场景假设为：有服从泊松分布的数据包到达，首先系统分类器根据获取到达的数据包头部信息区分各类服务等级进行分类排队，在此，假设到达的数据包共分为三类（实时的语音业务流C0、实时的视频业务流C1和非实时的普通业务流C2）；然后经分类排队的业务流按照DW_WFQ流量调度算法权重关系式（13）分配各个服务等级的权重，由式（14）分配各类业务流的服务速率；最后由系统的能耗模型计算出各类服务的能耗。相关参数设置如表1所示。

仿真主要包括两个方面的结果：首先，对比三种不同调度策略（FCFS、WFQ、DW_WFQ）下的业务流能耗情况，结果如图3～5所示。从图3可知，能耗随着数据包大小的增加而增大，且这种趋势增大的趋势随着数据包大小的增加变得越来越陡峭；从图4所示的30次抽样情况可看出，DW_WFQ算法每次仿真所需能耗都比FCFS和WFQ算法低；从图5所示的时延与能耗间关系可看出，随着时延的增加能耗逐渐减少，直至慢慢地趋于平缓。从图3～5可看出：在这三种调度策略下，DW_WFQ调度算法在能效方面有着显著的优势。

然后，又对比了在DW_WFQ调度策略下三类的业务流（实时的语音业务流C0、实时的视频业务流C1和非实时的普通业务流C2）的能耗，结果如图6～7所示。从图6可看出，三种业务流的能耗均随流量包长的增加而增大，由2.2节的能效优化分析可得图中C0权重最大且对应的服务速率最大，所以其能耗最高，且这种趋势随着包长的增加而更加明显；而图7也很好地证明了这点，三种业务流均随着时延的增加其能耗在不断地下降，且在能耗相同时，C2的时延比其他两类业务流的时延都大。

从以上仿真结果可以归纳出以下两点：

1）DW_WFQ调度算法依据当前网络状态灵活地调整各类业务流的服务速率，虽然在一定程度上增加了算法的复杂度，但是却可以在满足业务流QoS的前提下有效地减少网络能耗；

2）对于DW_WFQ，非实时业务的时延最大、能耗最低，而实时语音则时延最小、能耗最高。

4结语

本文提出了一种面向网络能效优化的动态权重队列管理算法，然后结合通用能耗效用函数，推导出了DW_WFQ的能耗模型。通过Matlab的仿真验证，取得了令人比较满意的结果。但是本文并未考虑如何分析和减少端到端系统的数据流能耗问题，同时，下一步主要工作是研究如何构建端到端绿色网络体系。

参考文献：

[1]

ZOU Y， ZHU J， ZHANG R. Exploiting network cooperation in green wireless communication[J]. IEEE Transactions on Communications， 2013， 61（3）： 999-1010.

[2]

FETTWEIS G， ZIMMERMANN E. ICT energy consumption ― trends and challenges[EB/OL]. [20150210]. https：//mns.ifn.et.tudresden.de/Lists/CustomListDefinitionsRoadmapListInstance/Attachments/2/Fettweis_G_WPMC_08.pdf.

[3]

BIANZINO A P， CHAUDET C， ROSSI D， et al. A survey of green networking research[J]. IEEE Communications Surveys & Tutorials， 2012， 14（1）： 3-20.

[4]

ZHANG Y， CHOWDHURY P， TORNATORE M， et al. Energy efficiency in telecom optical networks[J]. IEEE Communications Surveys & Tutorials， 2010， 12（4）： 441-458.

[5]

RAGHAVAN B， MA J. The energy and emergy of the Internet[C]// Proceedings of the 10th ACM Workshop on Hot Topics in Networks. New York： ACM， 2011： 9.

[6]

KILPER D C， ATKINSON G， KOROTKY S K， et al. Power trends in communication networks[J]. IEEE Journal of Selected Topics in Quantum Electronics， 2011， 2（17）： 275-284.

[7]

KOOMEY J. Growth in Data Center Electricity Use 2005 to 2010 [M]. Oakland， CA： Analytics Press，2011：9.

[8]

GAO P X， CURTIS A R， WONG B， et al. Its not easy being green[J]. ACM SIGCOMM Computer Communication Review， 2012， 42（4）： 211-222.

[9]

BARNETT T， Jr. Global mobile data traffic forecast update， 2013―2018[EB/OL].[20150510]. http：///news/ciscovniglobalmobiledataforecastupdate20132018.

[10]

FORECAST C V N I. Cisco visual networking index： global mobile data traffic forecast update， 2009―2014[EB/OL]. [20150510]。http：///c/en/us/solutions/collateral/serviceprovider/visualnetworkingindexvni/white_paper_c11520862.pdf.

[11]

张法， 王林， 侯晨颖， 等.网络能耗系统模型及能效算法[J]. 计算机学报， 2012， 35（3）： 603-615.（ZHANG F， WANG L， HOU C Y， et al. Network energy consumption models and energy efficient algorithms[J]. Chinese Journal of Computers， 2012， 35（3）： 603-615.）

[12]

BRADEN B， CLARK D， CROWCROFT J， et al. Recommendations on queue management and congestion avoidance in the Internet： RFC 2309[S]. Geneva： IETF， 1998.

[13]

PAREKH A K， GALLAGHER R G. A generalized processor sharing approach to flow control in integrated services networks： the multiple node case[J]. IEEE/ACM Transactions on Networking， 1994， 2（2）： 137-150.

[14]

PAREKH A K. A generalized processor sharing approach to flow control in integrated services network： the singlenode case[J]. IEEE/ACM Transactions on Networking， 1993， 1（3）：344-357.

[15]

BENNETT J C R， ZHANG H. Hierarchical packet fair queueing algorithms[J]. IEEE/ACM Transactions on Networking， 1997， 5（5）：675-689.

[16]

ANDREWS M， ANTA A F， ZHANG L， et al. Routing for energy minimization in the speed scaling model[C]// Proceedings of the IEEE INFOCOM 2010. Piscataway， NJ： IEEE， 2010： 1-9.