有负载限制的SONET环上的路由
随着互联网传输和多媒体数据通信的飞速发展，同步光学网络(SONET)作为一种更快，更有效和更低费用的传输技术现逐渐为更多的网络服务提供商所采用。同步光学网络(SONET)的基本结构是SONET环，它通过安装在环节点上的加减多路器(ADMs)来发送、接受和中继信息。这些多路器的容量决定了SONET环实际的带宽，即一般情况下，每个SONET环都存在一个带宽限制(容量)C，使得环上每个链接都不能够通过多于C单位的需求传送。
在SONET环的设计和应用中出现了许多富有挑战的问题，例如环负载问题，逆向旋转环上负载平衡的路由问题和节点容量有限的环上路由问题。这些问题实质上都是组合优化中经典的整数多商品流问题，一般是NP-困难的，但在一些特殊情形下是多项式时间可精确求解的。当SONET环是无向环时，截准则在问题求解和近似算法设计中起到了关键作用；但当SONET环是有向环时，这个准则失去了效用，此时，基于线性规划的舍入技术成为算法设计的重要方法，在逆向旋转SONET环负载平衡问题的算法研究中采用这个方法获得了一些好的结果。
本文主要考虑SONET环应用过程中提出的一个组合最优化问题：在有负载限制的逆向旋转环上，给定一组信息发送需求，每个需求都可以沿其发点和收点之间的两个可能的路径之一(顺时针或逆时针)进行传送，我们需要确定一个路由方案，即确定哪些需求被传送以及沿哪个方向传送，使其满足环容量限制并使得被传送的需求数目(通过量)达到最大。我们把这个问题称为有负载限制的逆向旋转SONET环上的路由问题(简记为LRRR)。
通过对线性规划舍入技术的精巧应用，我们给出了SONET环上LRRR问题的一个多项式时间算法。该算法在至多超出环容量一个单位的前提下，得到了一个需求通过量不少于最优值的路由方案。对这一算法的进一步修改，可以得到LRRR问题的一个性能比为1-2/c+1的近似算法，这一结果符合应用的要求。就我们所知，目前对LRRR问题的研究很少。根据该问题的特点，我们在算法设计中对现有的算法技术做了许多修改和推广，并使用了无向环中的一些技巧。这些改进在通讯网络的算法理论和实际应用中都将有很好的意义。
同步光学网络;加减多路器;负载限制;路由设计;LRRR;网络传输技术;多项式时间算法
中国海洋大学
硕士
运筹学与控制论
方奇志
2008
中文
TP393.03
35
2008-12-08（万方平台首次上网日期，不代表论文的发表时间）