有负载限制的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问题的研究很少。根据该问题的特点，我们在算法设计中对现有的算法技术做了许多修改和推广，并使用了无向环中的一些技巧。这些改进在通讯网络的算法理论和实际应用中都将有很好的意义。

目录

文摘

英文文摘

声明

第1章引言

1.1组合优化

1.2通讯网络中的组合优化

1.3环上路由问题

1.4本文的主要结构

第2章一些概念和结论

2.1复杂性理论的基本概念

2.2 NP-最优化问题和近似算法

2.3多商品流和边不相交的路

第3章环上路由问题及其发展现状

3.1介绍

3.2环负载问题

3.3逆向旋转环上的负载平衡路由问题

3.4节点容量有限的环上路由问题

第4章有负载限制的逆向旋转环上的路由问题

4.1模型和符号

4.2多项式时间算法

4.2.1 LRRR的线性规划松弛

4.2.2平行路由

4.2.3半不可分路由

4.2.4不可分路由

4.3结论

参考文献

致谢

攻读硕士学位期间完成的文章