论文部分内容阅读
Internet的迅猛发展极大地推动了光网络研究的进展,随着波分复用(WDM)技术的日趋成熟,限制光网络传输容量的因素已不再是光纤带宽,而是网络中路由器、交换机和复用器等电子设备的处理速度造成的瓶颈.流量疏导技术的出现为解决这些问题提供了一种有效途径。流量疏导是当今光网络研究中的一个前沿和热点问题,流量疏导研究的是如何将不同速率、不同类型的低速业务流打包成高速数据流,复用到一个波长上的过程。例如,一个OC-48 SONET环的一条光路可以同时支持16个OC-3的通信请求。全光网络中利用的波分复用技术,是指一条光纤可以同时传输几种信号,每个信号使用不同的波长。因此,波长分配问题就是为每对通信请求找到一条光路并为之分配一个波长,且使得共享一条链路的两条光路分配不同的波长。用图论的术语讲,波长分配问题可以抽象为路染色问题,即为给定的一个路径集合指定颜色,使得共享一条边的路径具有不同的颜色。一般,通信请求有一个粒度g,称为疏导因子。有效的路染色问题就是指至多有共享一条边的g条路径使用相同的颜色着色。给定一个有效的路染色,一个ADM至多可以被使用相同颜色着色的2g条路径共享。显然,最小化ADM数是流量疏导问题的一个特例(g=1)。1998年,O.Gerstel,R.Ramaswami和G.Sasaki等人提出了环形网络中流量疏导问题的概念,并证明了其对一般的疏导因子g,流量疏导问题是NP-完全的。过去对流量疏导问题的研究主要集中于环形网络,通过相关的证明得出了一些有意义的结果。2006年,M.Shalom和S.Zaks等人讨论了具有圈长至多是l的预处理情形的近似算法,并给出了其算法的性能保证及相关证明。本文主要研究最小化ADM数问题和各种拓扑结构中的流量疏导问题.共分为五章。本文讨论的问题大部分都是NP-难问题,因此,我们主要集中于近似算法的研究。第一章简要介绍全光网络、SONET环和流量疏导问题的基本概念,并给出了本文的研究内容及组织结构。第二章主要研究最小化ADM数问题,对具有预处理阶段的近似算法进一步改善分析,给出了一个更好的性能保证。第三章研究单向SONET/WDM环中的多播流量疏导问题,提出了具有更好近似比的近似算法,并证明了所使用的ADM数与网络中节点数的关系。第四章研究将应用于环形网络中的近似算法进一步改善分析应用于解决单向SONET/WDM环及一般拓扑结构中的流量疏导问题,得到了相似的结果。第五章总结全文,并提出下一步有待解决的问题。