一种有线网络中高效节能的拓扑控制机制

吴江海

摘要：最近几年，节能网络的观念迅速传播并获得了越来越多的关注。 一方面，节能网络能够在一定程度上缓解日益严峻的环境恶化问题，另一方面由于互联网消耗着数量巨大的能量并有迅速增长的趋势，节能网络可以为电信商和因特网服务提供商（ISP）带来巨大的经济效益。网络节能的通常做法是将网络中的路由器和链路休眠，但这种做法明显会降低网络性能。该文试图从整个网络拓扑层面考虑网络节能问题，提出了在保证网络性能满足限定阈值条件的情况下的最优化网络节能拓扑控制模型。针对这个模型，该文提出了一种启发式算法，试图在保证一定网络性能的条件下休眠网络节点和链路最小化网络能耗。通过网络模拟实验证明了该方法可以在保证一定网络Qos的情况下有效地降低網络耗能。

关键词：节能网络；互联网；网络拓扑；网络性能

中图分类号：TP393.02 文献标识码：A 文章编号：1009-3044（2014）32-7820-05

Abstract： Recently， the concept of energy-saving networking has been widely propagated and gaining an increasing amount of concern. On one hand， energy-efficient networking can alleviate the increasingly serious problem of environment pollution to some extent. On the other hand， energy-saving networking can provide Telecom and ISP huge economic benefits for the current Internet consumes a great amount of energy every year and this trend is becoming increasingly significant. The general method of energy-saving networking is to put some routes and links to sleep mode. However， this strategy will undermine the performance of networks evidently. In this paper， the energy saving of networks is considered on the whole network class and an optimal network topology model for energy savings with some constraints of network performance is proposed. A heuristic algorithm is proposed which is aimed at minimizing the network energy consumption with some Qos constraints by turning off network nodes and links. The simulation experiments demonstrate this strategy can effectively reduce the energy consumption of the network while the Qos is guaranteed to some extent.

Key words： energy-saving networking； Internet； network topology； network performance

1 概述

能量问题是制约无线网络生命期的一个重要因素，因此关于无线网络的节能问题从很早开始就已经有大量的研究[1-4]，而有线网的节能问题直到近些年来才受到学术和工业界的关注。近些年来，随着互联网的迅猛发展，有线网的耗能也迅速增长。现在，互联网耗能已经占到总耗能的1%，在未来这一数字将会增长到4%[5]。即使能够节约一小部分的网络耗能，也能够带来巨大的经济效益，并减少大量的二氧化碳排放量。

文献[6]最早提出了互联网节能的问题，它提出可以使路由器或交换机等网络设备在网络空闲情况下进行休眠，以达到一定节能效果，并通过网络中路由器流量的统计规律，证明了这种方法的可行性。在文献[6]之后，文献[7-10] 进一步研究和分析了如何通过休眠网络设备达到节能目的。在文献[7]中，作者提出了一种估测未来数据包到来的时间的方法，并据此让网络接口进入休眠状态。文献[8] 提出并比较了两种网络节能的方法。第一种方法是将网络部件在空闲状态下调整到休眠状态以减少在无数据包的时候的能耗；第二种方法是通过调整网络操作的速率以减少数据包处理过程中的能耗。这些方法都是从单个节点的角度考虑网络节能的问题。

从整个网络层面考虑网络节能问题是绿色网络研究的一个重要方面。文献[11-12]从路由协议角度考虑网络节能的问题。它们建立了网络链路耗能与链路流量之间的函数关系，在路由选路的时候，试图选择那些能使耗能最少的链路，然后让空闲的链路休眠以实现网络节能。这种方法在一定程度上能够降低网络能耗，但一方面没有考虑休眠节点和链路可以带来更大的节能效果，另一方面没有考虑节能给网络性能造成的影响。现在的英特网骨干网提供了比实际流量大的多的处理能力[13]，并且网络一天中的流量随着时间会显著地变化[6]。因此，我们可以在适当的时候让网络流量调整到可以替换的路径上的链路上，并让空闲的链路休眠，以达到节能效果。网络节能与性能本身就是一对折中的问题。因此，在本文中，我们试图在保证一定网络性能的前提下节约网络的耗能。该文提出了一种基于休眠骨干网络由器和链路的拓扑配置的最优化网络耗能模型。该最优化模型的目标是最大化休眠节点和链路的数目，限制条件是保证接入节点的连接性和链路利用率变化在一定范围内。该问题是是一个NP难解性问题，因此，我们提出了一种启发式的节能拓扑调整算法以获得近似最优解。通过网络模拟实验验证了该方法具有很好的节能效果。

本文按如下的结构进行组织：在第二章，提出的节能策略可以归结为一个在一定限定条件下的最优化问题；在第三章，提出了启发式的节能算法；在第四章，展示了在不同网络拓扑结构和负载条件下的实验结果；第五部分给出了一些结论。

2 最优化的节能网络拓扑模型

3 算法描述

第2章提出的最优化问题是一类多商品流问题，众所周知多商品流问题是NP难解性问题[14]。该问题在网络规模很大的时候，很难在有限的时间内找到最优解。我们提出了一种启发式的算法，以获得能耗近似最优的网络拓扑。由于一个网络节点的能耗比单个链路的能耗大很多，因此休眠一个网络节点比休眠一条单独的链路所节約的能耗大。因此，该文提出的算法首先试图找到可以休眠的最大数目的节点，然后寻找可以休眠的最大数目的链路。

这个启发式算法可以分三个部分进行描述： （a）找到最大数目的可以休眠的路由器；（b）找到可以休眠的最大数目的链路；（c）根据在某一段时间T内的链路利用率的变化，决定网络拓扑结构因为网络状况的改变是否需要重新配置。算法的程序可以具体按下面的步骤进行描述。在选择尝试休眠节点和链路的时候，我们尝试了两种不同的方法，一种方法是选择流量最小的部件，另一种方法是选择功耗最大的部件。我们比较了这两种休眠方法的节能效果。选择休眠节点和链路的大致步骤图1所示。

具体的算法描述如下：

我们假定一天中网络中的流量呈现正弦变化的特点，网络的节能效果随流量变化也呈现正弦变化的趋势。由图4可以看出，在凌晨2点的时候，网络节能比例最大。这是因为此时，网络中的流量最小，网络平均利用率最低，可以有更多的节点和链路休眠。随后网络的节能比例逐渐降低，到下午2点的时候降到最低。这是因为从2点到下午2点的时候，网络流量会逐渐增大，到下午2点的时候增到最大点，此时可以休眠的节点和链路也最少。随后，网络节能效果又逐渐增大，直到凌晨2点达到最大值。这是由于网络流量在下午2点以后逐渐减小，直到凌晨2点降低到最小。类似地，流量最小优先的方法比能耗最大优先和随机算法的节能效果明显大很多。

5 结论

本文从整个网络层面考虑了有线网络节能的问题。考虑到有线网有较高的冗余，并且流量普遍偏低，我们可以把有线网中的流经部分骨干网节点和链路的流量调整到其他节点和链路上，并让空闲的节点和链路休眠。基于这个基本想法，该文提出了一种能量最优的网络拓扑调整模型，试图在节能和网络性能之间达到一定的平衡，并提出了求解该模型的启发式算法。通过网络模拟实验，验证了该机制的合理性和有效性。

参考文献：

[1] Anastasia G，Contib M，Francescoa M，Passarellab A. “Energy conservation in wireless sensor networks： A survey， Ad Hoc Networks”[M].2009，7（3）：537-568.

[2] Arindam K，Das， Robert J.Marks， Mohamed El-Sharkawi， Payman Arabshahi， Andrew Gray， “Minimum power broadcast trees for wireless networks： integer programming formulations”[M].003：1001-1010.

[3] 赵保华，李婧，张炜，屈玉贵.基于MIMO 的节能无线传感器网络[J].电子学报，2006，34（8）：1415-1419.

[4] Baghaie M，Krishnamachari B. Delay constrained minimum energy broadcast in cooperative wireless networks[M].INFOCOM， Shanghai， China，2011（5）：864- 872.

[5] J. Baliga， K. Hinton， and R. Tucker. “Energy consumption of the Internet，”Joint International Conference on Optical Internet 2007 and the 32nd Australian Conference on Optical Fiber Technology[M]， COIN-ACOFT， pages 24-27， Melbourne， Australia，2007.

[6] M. Gupta and S. Singh. “Greening of the Internet，” in SIGCOMM 03： Proceedings of the 2003 conference on Applications， technologies， architectures， and protocols for computer communications[M].New York， NY， USA： ACM， 2003：19-26.

[7] M. Gupta， S. Grover， and S. Singh. “A feasibility Study for Power management in Lan switches”[M].in Proc. IEEE ICNP， Berlin， Germany， October， 2004： 361-371.

[8] S.Nedevschi，L.Popa，G.Iannaccone，D.Wetherall，S.Ratnasamy. “Reducing network energy consumption via sleeping and rate-adaptation”[M].Proc. 5th USENIX Symp on Networked Systems Design and Implementation（NSDI 08）， San Francisco， CA， 2008：323-336.

[9] J. Chabarek， J. Sommers， et al. “Power awareness in network design and routing”[M].proceedings of INFOCOM， Phoenix， Arizona， U.S.A， Apr，2008：15-17.

[10] L. Chiaraviglio， M. Mellia， and F. Neri. “Energy-aware networks： Reducing power consumption by switching of network element”[M].FEDERICAPhosphorus tutorial and workshop， Bruges， Belgium， May. 18，2008.

[11] J. Restrepo， C. Gruber， C. Mas Pachuca. “Energy Profile Aware Routing， First International Workshop on Green Communications IEEE International Conference on Communications （ICC）”[M].June 2009.

[12] S.Antonakopoulos，S.Fortune，L.Zhang.“Power-aware routing with rate-adaptive network elements”[M]， GLOBECOM Workshops， Miami，Florida，Dec，2010：1428- 1432.

[13] International Internet Statistics. TeleGeography Research， 2005.Available at http：//www.itu.int/dms pub/itu-d/md/02/isap2b.1.1/c/D02-ISAP2B.1.1-C-0025！！PDF-E.pdf

[14] T. G. Crainic， M. Gendreau， I. Ghamlouche. “Cycle-based neighborhoods for fixed-charge capacitated multicommodity network design”[M]， Technical report CRT-2001-01， Centre de recherche sur les transports， Universite de Montreal， pages 855.