OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editor: Keren Bergman
  • Vol. 8, Iss. 5 — May. 1, 2009
  • pp: 454–461

Minimizing transceivers in optical path networks

Prashant Iyer, Rudra Dutta, and Carla D. Savage  »View Author Affiliations


Journal of Optical Networking, Vol. 8, Issue 5, pp. 454-461 (2009)
http://dx.doi.org/10.1364/JON.8.000454


View Full Text Article

Acrobat PDF (174 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

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

OCIS Codes
(060.4250) Fiber optics and optical communications : Networks
(060.4510) Fiber optics and optical communications : Optical communications

ToC Category:
Research Papers

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

Citation
Prashant Iyer, Rudra Dutta, and Carla D. Savage, "Minimizing transceivers in optical path networks," J. Opt. Netw. 8, 454-461 (2009)
http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jon-8-5-454


Sort:  Author  |  Year  |  Journal  |  Reset

References

  1. O. Gerstel, G. Sasaki, and R. Ramaswami, “Cost effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw. 8, 618-630 (2000). [CrossRef]
  2. R. Dutta and G. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun. 20, 110-121 (2002). [CrossRef]
  3. K. Zhu and B. Mukherjee, “Traffic grooming in optical WDM mesh networks,” IEEE J. Sel. Areas Commun. 20, 122-133 (2002). [CrossRef]
  4. X. Li, L. Liu, P. Wan, and O. Frieder, “Practical traffic grooming scheme for single hub SONET/WDM rings,” in Proceedings, 25th Annual IEEE Conference on Local Computer Networks (IEEE, 2000), pp. 556-564.
  5. X. Zhang and C. Qiao, “An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET WDM rings,” IEEE/ACM Trans. Netw. 8, 608-617 (2000). [CrossRef]
  6. P. Iyer, R. Dutta, and C. D. Savage, “Complexity of path traffic grooming,” J. Opt. Netw. 6, 1270-1281 (2007). [CrossRef]
  7. M. Brunato and R. Battiti, “A multistart randomized greedy algorithm for traffic grooming on mesh logical topologies,” in Sixth IFIP Working Conference on Optical Network Design and Modeling (ONDM 2002) (Klewer, 2002).
  8. R. Dutta and G. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network 16, 46-56 (2002).
  9. K. Zhu and B. Mukherjee, “A review of traffic grooming in WDM optical networks: architectures and challenges,” Opt. Networks Mag. 4, 55-64 (2003).
  10. E. Modiano and P. Lin, “Traffic grooming in WDM networks,” IEEE Commun. Mag. 39(7), 124-129 (2001). [CrossRef]
  11. S. Huang and R. Dutta, “Dynamic traffic grooming: the changing role of traffic grooming,” IEEE Commun. Surv. Tutorials 9, 32-50 (2007).
  12. R. Dutta, A. Kamal, and G. Rouskas, Traffic Grooming for Optical Networks: Foundations, Techniques and Frontiers (Springer, 2008).
  13. S. Huang, R. Dutta, and G. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun. 24, 66-82 (2006).
  14. P. Wan, G. Calinescu, L. Liu, and O. Frieder, “Grooming of arbitrary traffic in SONET WDM BLSRs,” IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000). [CrossRef]
  15. V. Konda and T. Chow, “Algorithm for traffic grooming in optical network to minimize the number of transceivers,” in 2001 IEEE Workshop on High Performance Switching and Routing (IEEE, 2001), pp. 218-221.
  16. A. Chiu and E. Modiano, “Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks,” J. Lightwave Technol. 18, 2-12 (2000). [CrossRef]
  17. M. Vecchi, “Broadband networks and services: architecture and control,” IEEE Commun. Mag. 33(8), 24-32 (1995).
  18. J. Kurose and K. Ross, Computer Networking: A Top Down Approach; Featuring the Internet, 3rd ed. (Addison-Wesley, 2004).
  19. P. Fishburn, “Interval graphs and interval orders,” Discrete Math. 55, 135-149 (1985). [CrossRef]
  20. M. Garey and D. Johnson, Computers and Intractability A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979).

Cited By

Alert me when this paper is cited

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

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited