Abstract

The problem of routing traffic on multihop clear optical channels and deciding the virtual topology of optical channels to form on a physical network of fibers to minimize the cost of electronic switching equipment has become known as traffic grooming in optical networks. Traffic grooming is recognized as an important research area, because the joint opto-electric routing problem is a hard one, yet necessary because of the large cost of pure electronic switching. This problem has been shown to be NP-complete (nondeterminstic polynomial complete) even for very simple practical topologies such as a path network. In previous work, we have shown that at least the subproblem of routing traffic on a given virtual topology to minimize electronic switching (NP-hard for path networks with arbitrary traffic matrices) becomes polynomial when the traffic on the path is restricted to be egress traffic, that is, all traffic requests are destined for a single egress node. In that work, the objective was to minimize the raw OEO (opto-electro-optic) metric (number of bits electronically switched per second) totaled over all network nodes. Of late, it has become clear that electronic switching equipment cost is best counted in quantized units, e.g., in the number of transceiver interfaces at network nodes. In this paper, we consider the traffic grooming problem in unidirectional, WDM path networks with the goal of minimizing the number of transceivers. We conclusively show that the problem is NP-hard, even under the restriction of the egress traffic model. In the case of egress traffic, we give a simple heuristic that will never be worse than twice the optimal.

© 2009 Optical Society of America

» View Full Text: Acrobat PDF (174 KB)

History
Original Manuscript: September 19, 2008
Manuscript Accepted: March 11, 2009
Revised Manuscript: February 9, 2009
Published: April 10, 2009

References

Please [login to View References]

Author Affiliations

Prashant Iyer, Rudra Dutta, Carla D. Savage

North Carolina State University

Cited By

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Advanced Search

Recent ToC Categories (Beta)