On-Line Optimal Wavelength Assignment in WDM Networks With Shared Wavelength Converter Pool

摘要

In this paper, we study on-line wavelength assignment in wavelength-routed WDM networks under both unicast and multicast traffic where nodes in the networks have wavelength conversion ability. Since wavelength converters are still expensive and difficult to implement, we consider the case where nodes in networks have only a limited number of converters that are shared by all input channels. We study the problem of setting up connections in such networks using minimum number of wavelength converters. For unicast traffic, we first study the problem of setting up a lightpath on a given link-path with minimum number of conversions. We give a simple algorithm that solves it in O(tk) time where t is the number of links on the path and k is the number of wavelengths per fiber, as compared to the best known existing method that needs to construct an auxiliary graph and apply the Dijkstra's algorithm. We also consider the problem of setting up a lightpath while using wavelength converters at nodes with fewer available converters only when necessary, and give an O(tk) time algorithm. We then generalize this technique to WDM networks with arbitrary topologies and give an algorithm that sets up an optimal lightpath network-wide in O(Nk+Lk) time, where N and L are the number of nodes and links in the network, respectively. We also consider multicast traffic in this paper. Finding an optimal multicast light-tree is known to be NP-hard and is usually solved by first finding a link-tree then finding a light-tree on the link-tree. Finding an optimal link-tree is also NP-hard and has been extensively studied. Thus, we focus on the second problem which is to set up a light-tree on a given link-tree with minimum number of conversions. We propose a new multicast conversion model with which the output of the wavelength converter is split-table to save the usage of converters. We show that under this model the problem of setting up an optimal light-tree is NP-hard and then give efficient- heuristics to solve it approximately