论文部分内容阅读
网络技术日新月异的发展正在深刻改变着现代社会与生活。然而，随之而来的一个严重问题是网络设备的过高能耗。这一问题不仅限制了网络的进一步发展，同时也阻碍着节约型社会的创建，对于经济发展和环境具有重要影响。现有的网络遵循冗余设计和超额资源供给等设计原则，以满足峰值带宽需求和网络可靠性需求。这些设计原则导致了网络设备利用率远远低于实际负载，同时，也给网络节能带来了很大的空间。如果能够使得网络设备的能耗反映其真实负载情况，那么可以达到可观的节能效果。 在网络节能这一研究领域中，过去的很多研究仅关注予单一设备的节能。与之不同，本文将在全网尺度上研究能耗效率的优化。作者将会建立网络全局的通信模型与能耗模型，基于这些模型设计网络能耗效率的全局优化算法。本文研究工作的一个重要特点为最坏情况分析。具体而言，本文对于网络能耗效率优化问题的输入所做的唯一假设是，输入是由与本文节能目标相反的敌人所产生的。相较于理想情况下的平滑网络通信模型，上述最坏情况输入可以更加准确得建模真实的网络环境中具有高不确定性及高猝发性的通信负载。通过将最坏情况分析应用到对网络能耗全局优化的研究中，本文在以下四个方面做出了贡献: 第一，针对在网络能耗全局优化领域中受到广泛关注的NP-难问题一代价函数为超线性幂函数的路由问题，本文首次在计算复杂性领域中研究并给出了此问题的困难度因子。在本文研究的路由问题中，每条链路e关联有一个代价函数f(le）=（le）α，其中le表示链路e上的通信负载。此问题之目标为，为每一个通信请求计算一条路径，从而使得总代价∑ef(le)最小化。由于采用了速率缩放这种节能技术的网络设备功耗与其负载满足超线性幂函数关系，研究上述路出问题对于从全局角度优化网络能耗有着重要意义。本文以一个难以近似的限制满足问题作为归约起点，证明了除非NP(∈)ZPP(npolylog(n))，否则上述路由问题的困难度因子为Ω（（log|E|/loglog|E|）α·|E|-1/4)。 第二，针对代价函数为超线性幂函数的路由问题，本文设计了一种竞争比具有对数多项式级紧确度的遗忘性整数路由算法，并将其扩展为一个可以广泛适用的通用框架。遗忘性路由算法的特点为，其为每个通信请求做出的路由决策不能依赖于网络中的其他任何通信请求。这种路由策略可以在大规模高速互联网中，以完全分布式的方式高效实现，因此受到了来自研究人员和工程人员的广泛关注。然而，当路由问题的代价函数为超线性函数时，针对其设计遗忘性整数路由算法变得极具挑战性。形式化地，本文证明没有任何遗忘性整数路由算法可以在代价函数为f（le）=（le）α且整数限制必须被遵守的情况下保证竞争比为o(|E|α-1/α+1)。相应地，基于随机化技术，本文设计了一个遗忘性整数路由算法ROI-Routing，其竞争比的紧确度为O(log2α/α+2|V|·logα-1 D)，其中D表示通信请求的最大流量需求。更进一步地，本文将ROI-Routing算法扩展为一个通用框架MATRIX，可以用来产生并分析遗忘性整数路由算法。为了证明这一通用框架的意义，本文应用此框架产生了一个新的遗忘性整数路由算法，其在扩展图与超立方网络上的竞争比分别为O(logα|V|· logα-1 D)与O(log3α|V|· logα-1 D)。 第三，针对包交换网络，本文给出了一种具有普适稳定性的节能调度协议，并证明在能耗效率方面，此协议之近似比为常数。在包交换网络中，调度协议由数据包传输次序策略与设备速率调节策略共同组成，其中数据包传输次序策略负责在数据包排队争用链路时，从队列中挑选数据包进行传输;而设备速率调节策略则需要决定采用了速率缩放技术的网络链路的工作速率。为了验证节能调度协议的稳定性，本文首先设计了一种新的敌对排队论模型。与经典敌对排队模型相比，本文模型的特点在于能够允许不同的数据包具有不同的长度，并允许网络链路动态调节其工作速率。基于此敌对排队论模型，本文将数据包争用链路的问题转化为了一个广义车间调度问题，并提出了一个算G-FSA对其进行求解。本文进一步设计了一个基于时间区间划分算法的速率调节策略，将之与G-FSA相结合，产生了本文中的包交换网络调度协议。已经证明，此调度协议可以在面对任何敌对输入时保持稳定，且其在能耗效率方面的近似比上界为O((2+ε)α1)，其中ε为大于0的任意常数。 第四，针对WDM全光网络，本文设计了一个分布式在线节能算法为通信请求动态建立光路，并证明此算法在能耗效率方面的竞争比可以被对数多项式界定。本文研究了光网络中通信请求可以在任意的时间点到达、离开，且沿着光纤铺设的光网络设备可以在光纤被闲置时自动转入体眠状态的情况。在此动态场景下，本文研究了如何为通信请求在线分配波长与光纤，以最小化沿着活跃光纤铺设的网络设备的总功耗。本文证明，在动态场景下，一个局部优化的贪心算法将会给出一个较差的竞争比Ω(μ）。与之相对，本文设计了一个随机化的波长分配与光纤分配算法，其能够保证在能耗效率方面的竞争比为O(logμ·log Hmax)。其中，μ是一条光纤中所承载的波长数，而Hmax代表最长的通信请求持续时间。对于每个通信请求，本文所设计的算法可以在O(1)的时间内为其分配一个波长，并在O(μlogB+log Hmax)的时间内，在每条链路上为其分配一条光纤。参数B代表在任意时间点，通过任意链路的通信请求数量的最大值。