Two-stage cut saturation algorithm for designing all-optical networks
Two-stage cut saturation algorithm for designing all-optical networks
复制标题
用于设计全光网络的两阶段切割饱和算法
DOI：
--
复制
发表时间：
2001
影响因子：
8.3
通讯作者：
Kwok
中科院分区：
文献类型：
--
作者：
Gaoxi Xiao;Y. Leung;Kwok
我们设计并优化了全光网络的物理拓扑结构。在电子通信网络中，由于波长连续的约束，该问题比传统的问题更具挑战性，它涉及到路由和波长分配。在这个问题中，我们给出了每个节点对所需的光路数量和成本规格，我们的目标是确定一个最小成本的物理拓扑。我们将该问题形式化，证明了它是NP-难的，并设计了一个有效的算法--两阶段切割饱和算法，在第一阶段，我们放松了波长连续的约束，并应用切割饱和方法的主要思想来确定一个好的初始网络。在第二阶段，我们施加波长连续约束并执行路由和波长分配以在初始网络上建立指定的光路。当一些光路不能建立时，我们应用切割饱和方法的主要思想来优化插入额外的链接到网络中。仿真结果表明：（1）该算法可以有效地设计出低成本、高利用率的网络;（2）如果有波长转换器支持全波长转换，则链路的总成本可以显著降低。
We design and optimize the physical topology of all-optical networks. This problem is more challenging than the traditional one for electronic communication networks, because of the wavelength-continuous constraint and it involves routing and wavelength assignment. In this problem, we are given the number of lightpaths required by every node pair and a cost specification, and our objective is to determine a physical topology of minimal cost. We formulate the problem, prove that it is NP-hard, and design an efficient algorithm called two-stage cut saturation algorithm for it. In the first stage, we relax the wavelength-continuous constraint and apply the main idea of the cut saturation method to determine a good initial network. In the second stage, we impose the wavelength-continuous constraint and perform routing and wavelength assignment to establish the specified lightpaths on the initial network. When some lightpaths cannot be established, we apply the main idea of the cut saturation method to optimize the insertion of additional links into the network. Simulation results show the following: (1) the proposed algorithm can efficiently design networks with low costs and high utilization and (2) if wavelength converters are available to support full wavelength conversion, the total cost of the links can be significantly reduced.