## Fast Exact ILP Decompositions for Ring RWA |

Journal of Optical Communications and Networking, Vol. 3, Issue 7, pp. 577-586 (2011)

http://dx.doi.org/10.1364/JOCN.3.000577

Enhanced HTML Acrobat PDF (540 KB) | Spotlight

### 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: Year | Journal | Reset

### References

- J. M. Simmons, Optical Network Design and Planning, Springer, 2008.
- R. Dutta, A. E. Kamal, and G. N. Rouskas, ed., Traffic Grooming in Optical Networks: Foundations, Techniques, and Frontiers, Springer, 2008.
- R. Dutta and G. N. Rouskas, "Traffic grooming in WDM networks: past and future," IEEE Network 16, (6), 46‒56 (2002). [CrossRef]
- K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun. 20, (1), 122‒133 (2002). [CrossRef]
- S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave Technol. 21, (4), 870‒883 (2003). [CrossRef]
- S. Ramamurthy and B. Mukherjee, "Survivable WDM mesh networks, part I—protection," Proc. of INFOCOM ’99, Mar. 1999, pp. 744‒751.
- 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]
- W. Su and G. Sasaki, "Scheduling periodic transfers with flexibility," Proc. of 41st Allerton Conf., Oct. 2003.
- 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.
- 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]
- 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).
- 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).
- 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]
- R. Ramaswami and K. Sivarajan, "Routing and wavelength assignment in all-optical networks," IEEE/ACM Trans. Netw. 3, (5), 489‒500 (1995). [CrossRef]
- A. Mehrotra and M. Trick, "A column generation approach for graph coloring," INFORMS J. Comput. 8, (4), 344‒354 (1996). [CrossRef]
- 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]
- B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, (6), 1291‒1308 (2009). [CrossRef]
- 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.