Research Article
Approximation algorithms for traffic routing in wavelength routed WDM networks
@INPROCEEDINGS{10.1109/ICBN.2005.1589597, author={Y. Aneja and A. Jaekel and S. Bandyopadhyay}, title={Approximation algorithms for traffic routing in wavelength routed WDM networks}, proceedings={2nd International ICST Conference on Broadband Networks}, publisher={IEEE}, proceedings_a={BROADNETS}, year={2006}, month={2}, keywords={}, doi={10.1109/ICBN.2005.1589597} }- Y. Aneja
A. Jaekel
S. Bandyopadhyay
Year: 2006
Approximation algorithms for traffic routing in wavelength routed WDM networks
BROADNETS
IEEE
DOI: 10.1109/ICBN.2005.1589597
Abstract
One major objective in WDM network design is to develop a logical topology and a routing that minimizes the congestion of the network. A standard approach is to decouple the problem of logical topology design and the problem of routing on this logical topology. Heuristics for finding the logical topology exist and a straight-forward linear program (LP), based on the node-arc formulation is normally used to solve the routing problem over a given logical topology. We have found that such LP formulations become computationally intractable for large networks. In this paper, we have introduced a novel approach for routing traffic over a given logical topology, using the concept of approximation algorithms. This technique allows us to efficiently route traffic for practical sized networks and obtain solutions, which are guaranteed to be within a specified bound of the optimal solution. Simulation results from different networks demonstrate that approximation algorithms can be used to quickly generate "near-optimal" solutions to the traffic routing problem in WDM networks.
