OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editors: K. Bergman and V. Chan
  • Vol. 3, Iss. 7 — Jul. 1, 2011
  • pp: 577–586

Fast Exact ILP Decompositions for Ring RWA

Emre Yetginer, Zeyu Liu, and George N. Rouskas  »View Author Affiliations


Journal of Optical Communications and Networking, Vol. 3, Issue 7, pp. 577-586 (2011)
http://dx.doi.org/10.1364/JOCN.3.000577


View Full Text Article

Enhanced HTML    Acrobat PDF (540 KB) | SpotlightSpotlight on Optics Open Access





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

Wavelength division multiplexing rings are now capable of supporting more than 100 wavelengths over a single fiber. Conventional link and path formulations for the routing and wavelength assignment problem are inefficient due to the inherent symmetry in wavelength assignment and the fact that the problem size increases fast with the number of wavelengths. Although a formulation based on maximal independent sets (MIS) does not have these drawbacks, it suffers from exponential growth in the number of variables with increasing network size. We develop a new ILP (integer linear program) formulation based on the key idea of partitioning the path set and representing the MIS in the original network using the independent sets calculated in each of these partitions. This exact decomposition trades off the number of variables with the number of constraints and, as a result, achieves a much better scalability in terms of network dimension. Numerical results on ring networks of various sizes demonstrate that this new ILP decomposition achieves a decrease of several orders of magnitude in running time compared to existing formulations. Our main contribution is a novel and extremely fast technique for obtaining, in a few seconds using commodity CPUs, optimal solutions to instances of maximum size SONET rings with any number of wavelengths; such instances cannot be tackled with classical formulations without vast investments in computational resources and time.

© 2011 OSA

OCIS Codes
(060.4250) Fiber optics and optical communications : Networks
(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms

ToC Category:
Research Papers

History
Original Manuscript: January 31, 2011
Revised Manuscript: June 13, 2011
Manuscript Accepted: June 15, 2011
Published: June 27, 2011

Virtual Issues
September 27, 2011 Spotlight on Optics

Citation
Emre Yetginer, Zeyu Liu, and George N. Rouskas, "Fast Exact ILP Decompositions for Ring RWA," J. Opt. Commun. Netw. 3, 577-586 (2011)
http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jocn-3-7-577


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. J. M. Simmons, Optical Network Design and Planning, Springer, 2008.
  2. R. Dutta, A. E. Kamal, and G. N. Rouskas, ed., Traffic Grooming in Optical Networks: Foundations, Techniques, and Frontiers, Springer, 2008.
  3. R. Dutta and G. N. Rouskas, "Traffic grooming in WDM networks: past and future," IEEE Network 16, (6), 46‒56 (2002). [CrossRef]
  4. K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun. 20, (1), 122‒133 (2002). [CrossRef]
  5. S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave Technol. 21, (4), 870‒883 (2003). [CrossRef]
  6. S. Ramamurthy and B. Mukherjee, "Survivable WDM mesh networks, part I—protection," Proc. of INFOCOM ’99, Mar. 1999, pp. 744‒751.
  7. J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, and R. Douville, "A review of routing and wavelength assignment of scheduled lightpath demands," IEEE J. Sel. Areas Commun. 21, (8), 1231‒1240 (2003). [CrossRef]
  8. W. Su and G. Sasaki, "Scheduling periodic transfers with flexibility," Proc. of 41st Allerton Conf., Oct. 2003.
  9. B. Jaumard, C. Meyer, and B. Thiongane, "ILP formulations and optimal solutions for the RWA problem," Proc. of IEEE GLOBECOM’04, Vol. 3, Nov. 29–Dec. 3 2004, pp. 1918‒1924.
  10. I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: an approach to high bandwidth optical WANS," IEEE Trans. Commun. 40, (7), 1171‒1182 (1992). [CrossRef]
  11. R. Dutta and G. N. Rouskas, "A survey of virtual topology design algorithms for wavelength routed optical networks," Opt. Networks Mag. 1, (1), 73‒89 (2000).
  12. H. Zang, J. P. Jue, and B. Mukherjee, "A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks," Opt. Networks Mag. 1, (1), 47‒60 (2000).
  13. R. M. Krishnaswamy and K. N. Sivarajan, "Algorithms for routing and wavelength assignment based on solutions of LP-relaxations," IEEE Commun. Lett. 5, (10), 435‒437 (2001). [CrossRef]
  14. R. Ramaswami and K. Sivarajan, "Routing and wavelength assignment in all-optical networks," IEEE/ACM Trans. Netw. 3, (5), 489‒500 (1995). [CrossRef]
  15. A. Mehrotra and M. Trick, "A column generation approach for graph coloring," INFORMS J. Comput. 8, (4), 344‒354 (1996). [CrossRef]
  16. T. Lee, K. Lee, and S. Park, "Optimal routing and wavelength assignment in WDM ring networks," IEEE J. Sel. Areas Commun. 18, (10), 2146‒2154 (2000). [CrossRef]
  17. B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, (6), 1291‒1308 (2009). [CrossRef]
  18. C. Bron and J. Kerbosch, "Algorithm 457: finding all cliques of an undirected graph," Commun. ACM 16, (9), 575‒577 (1973). [CrossRef]

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