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. We assume nodes in the networks have wavelength conversion ability. Since wavelength converters are still expensive and difficult to implement, we consider the networks that have only a limited number of converters in each node, and the converters are shared by all input channels at the node. We consider how to set up connections in such networks using as few wavelength converters as possible. For unicast traffic, we first study the problem of setting up a lightpath on a given link path with minimum number of conversions, and give a new 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 algorithm that runs in at least O(t/sup 2/k) time. We also consider the case when nodes have different conversion priorities, and give an O(tk) time algorithm for setting up a lightpath on a given link path while converting wavelength at higher priority nodes only when necessary. We then generalize this technique to WDM networks with arbitrary topologies and present an algorithm that sets up an optimal lightpath network-wide in O(Nk + Lk) time by checking the state of the entire network, where N and L are the number of nodes and links in the network, respectively. For multicast traffic, 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 a 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 and more practical multicast conversion model, where the output of the wavelength converter can be split. As can be seen, the new model can save the usage of converters considerably. We first show that this problem is NP-hard and then give efficient heuristics to solve it approximately.