论文部分内容阅读
随着互联网的迅速发展，互联网所产生的巨大能耗不但成为制约网络发展的一大关键问题，而且是影响环境和社会发展的重要问题。传统网络遵循资源超额供给、冗余设计等设计原则，并没有将节能作为设计目标或约束条件。因此，传统网络的设计特点为网络节能提供了很大空间。针对网络节能的研究，称为“绿色网络”，它可以分为设备级别的节能研究以及全网级别的节能研究。绿色网络研究初期，大量工作围绕设备级的节能技术展开。近两年来，逐渐开始有相关工作从全网的角度通过改变路由策略来进行节能，这些工作大多采用集中式的优化方法做全局能耗最小的路径计算，当最优化问题是NP难时，采用启发式或其他近似算法进行集中式求解。集中式策略具有一些优势，例如可以较方便地得到全局最优或近似最优解，利于统一规划调度;然而，集中式的控制方式在实际网络中并不可行，尤其在大型分布式网络中难以实现。这是因为，集中式策略的计算代价高、依赖全局信息的获取和可靠的中央控制机制。 随着网络规模的飞速增长，相比于集中式控制，分布式策略是一个更加可行易扩展的选择。然而目前在全局网络节能领域还鲜有相关研究。如何采用分布式的路由方式来提高网络能效是一个既有理论价值又有实际意义的问题。本文重点研究并解决该问题，主要贡献如下: 第一，从路由的角度出发，提出了一个同时最小化网络全局总能耗和数据包总延迟的双目标优化模型。与目前大多数以能耗为优化目标、性能为限制条件的工作不同，本文采用标量化的方法，提出对于能耗与延迟的双目标优化问题，并提出了求解双目标帕累托最优解的充分条件。本文所提出的方法可以同时优化能耗和延迟两个目标，并找到一系列针对能耗和延迟的最优权衡关系。 第二，本文提出了一个分布式无环的路由方法，从路由的角度对网络能耗和传输延迟进行全局优化。与集中式路由策略以及目前网络中最常用的最短路径路由策略（如，开放式最短路径优先，Open Shortest Path First）不同，本文的路由策略是完全分布式的，每个节点只掌握邻居的拓扑信息和本地流量信息，根据局部信息来建立更新本地路由表，避免了节点对于全局信息的依赖性，也不需要进行统一的全网路由决策，却能够实现能耗和延迟的全局优化目标。本文证明了该分布式路由机制的收敛性。针对网络流量的动态特性，本文还提出了基于周期的动态路由算法，根据网络流的动态变化，该算法可以周期性进行路由表的更新。 第三，本文提出了一个分布式无环多路径寻找算法，该算法是分布式路由算法的预处理阶段，算法基于节点的“高度”生成原网络拓扑图的最大有向无环子图，能够保证分布式路由算法的无环特性。不同于现有的路由无环策略，本文的算法通信代价小，且比常用的最短路径树无环策略具有更多的路径选择，更加节能、具有更好的流量均衡特性。本文给出了该算法的无环特性及可以生成最大有向无环图的理论证明。 最后，本文在真实网络数据集上对分布式路由技术进行了模拟实验。实验结果表明该路由策略可以快速收敛到近似全局最优值。相比于最短路径路由，在延迟相近的情况下可以达到30％的节能。在动态流下，本文的周期性动态路由算法与理论的全局最优值接近，比现有网络中应用最广的最短路径路由算法效果有较大提高，在最佳情况下可以达到接近20％的节能。