Improved lightpath (wavelength) routing in large WDM networks

We address the problem of efficient circuit switching in wide area networks . The solution provided is based on finding optimal routes for lightpaths a nd semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several ligh tpaths together, using wavelength conversion at their junctions. The proble m thus is to find an optimal lightpath/setnilightpath in the network in ter ms of the cost of wavelength conversion and the cost of using the wavelengt hs on links. In this paper, we first present an efficient algorithm for the problem which runs in time O(k(2)n + km + kn log(kn)), where n and m are t he number of nodes and links in the network, and k is the number of wavelen gths. We then analyze that the proposed algorithm requires O(d(2)nk(0)(2)mk(0) log n) time for a restricted version of the problem in which the nuln her of available wavelengths for each link is bounded by k(0) and k(0) = o( n), where d is the maximum in-degree or out-degree of the network. It is su rprising to have found that the time complexity for this case is independen t of k. It must be mentioned that our algorithm can be implemented efficien tly in the distributed computing environment. The distributed version requi res O(kn) time and O(km) messages. Compared with a previous O(k(2)n + kn(2) ) time algorithm, our algorithm has the following advantages. 1) We take in to account the physical topology of the network which makes our algorithm o utperform the previous algorithm. In particular, when k is small [e.g., k = O(log n)] and m = O(n), our algorithm runs in time O(n log(2) n), while th e previous algorithm runs in time O(n(2) log n). 2) Since our algorithm has high locality, it can be implemented on the network distributively.