Research Article
On the complexity of path traffic grooming
@INPROCEEDINGS{10.1109/ICBN.2005.1589750, author={Prashant Iyer and Rudra Dutta and Carla D. Savage}, title={On the complexity of path traffic grooming}, proceedings={2nd International ICST Conference on Broadband Networks}, publisher={IEEE}, proceedings_a={BROADNETS}, year={2006}, month={2}, keywords={}, doi={10.1109/ICBN.2005.1589750} }- Prashant Iyer
Rudra Dutta
Carla D. Savage
Year: 2006
On the complexity of path traffic grooming
BROADNETS
IEEE
DOI: 10.1109/ICBN.2005.1589750
Abstract
Traffic grooming is known to be an inherently difficult problem. It has been shown to be NP-complete for path networks, a simple topology in which wavelength assignment is tractable. In this paper, we explore the borderline between tractability and intractability by considering grooming in unidirectional path networks in which all traffic requests are destined for a single egress node. It is an open question whether the complete grooming problem is NP-hard with this restriction or not. We show that at least the problem of routing traffic on a given virtual topology to minimize electronic switching (NP-hard for path networks with arbitrary traffic matrices) becomes polynomial on the egress model. We also show that in the egress model, if the capacity constraint is relaxed, the entire problem becomes polynomial. If, in addition, traffic requests are uniform, there is an explicit combinatorial formula for the optimum solution. For the case of finite capacity and unit traffic requests, we can find in polynomial time a feasible solution which, under certain assumptions, is optimal