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. 9 — Sep. 1, 2011
  • pp: 767–779

Anycast Routing for Survivable Optical Grids: Scalable Solution Methods and the Impact of Relocation

Ali Shaikh, Jens Buysse, Brigitte Jaumard, and Chris Develder  »View Author Affiliations

Journal of Optical Communications and Networking, Vol. 3, Issue 9, pp. 767-779 (2011)

View Full Text Article

Enhanced HTML    Acrobat PDF (656 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



In this paper, we address the issue of resiliency against single link network failures in optical grids and show how the anycast routing principle, which is typical of grids, can be exploited in providing efficient shared path protection. We investigate two different integer linear program models for the full anycast routing problem, deciding on the primary and backup server locations as well as on the lightpaths toward them. The first model is a classical integer linear programming (ILP) model, which lacks scalability. The second model is a large-scale optimization model which can be efficiently solved using column generation techniques. We also design two new heuristics: the first one is an improvement of a previously proposed one which, although providing near optimal solutions, lacks scalability, while the second one is highly scalable, at the expense of reduced accuracy. Numerical results are presented for three mesh networks with varying node degrees. They allow an illustration of the scalability of the newly proposed approaches. Apart from highlighting the difference in performance (i.e., scalability and optimality) among the algorithms, our case studies demonstrate the bandwidth savings that can be achieved by exploiting relocation rather than using a backup path to the original (failure-free) destination site. Numerical results for varying network topologies, as well as different numbers of server sites show that relocation allows bandwidth savings in the range of 7–21%.

© 2011 OSA

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

ToC Category:
Research Papers

Original Manuscript: March 7, 2011
Revised Manuscript: July 8, 2011
Manuscript Accepted: July 26, 2011
Published: August 31, 2011

Ali Shaikh, Jens Buysse, Brigitte Jaumard, and Chris Develder, "Anycast Routing for Survivable Optical Grids: Scalable Solution Methods and the Impact of Relocation," J. Opt. Commun. Netw. 3, 767-779 (2011)

Sort:  Author  |  Year  |  Journal  |  Reset  


  1. I. Foster and C. Kesselman, ed., The Grid: Blueprint for a New Computing Infrastructure, 2nd ed., Morgan Kaufmann, San Francisco, CA, 2004.
  2. M. De Leenheer, C. Develder, T. Stevens, B. Dhoedt, M. Pickavet, and P. Demeester, "Design and control of optical grid networks," Int. Conf. Broadband Networks, Sept. 2007, pp. 107‒115.
  3. A. Jaiszczyk, "Automatically switched optical networks: Benefits and requirements," IEEE Commun. Mag. 43, (2), S10‒S15 (2005). [CrossRef]
  4. T. Stevens, M. D. Leenheer, C. Develder, F. D. Turck, B. Dhoedt, and P. Demeester, "Anycast routing algorithms for effective job scheduling in optical grids," European Conf. Optical Communications (ECOC), Sept. 2006, Cannes, France, pp. 1‒2.
  5. P. Anedda, S. Leo, S. Manca, M. Gaggero, and G. Zanetti, "Suspending, migrating and resuming HPC virtual clusters," FGCS, Future Gener. Comput. Syst. 26, (8), 1063‒1072 (2010). [CrossRef]
  6. Y. C. Lee and A. Y. Zomaya, "Rescheduling for reliable job completion with the support of clouds," FGCS, Future Gener. Comput. Syst. 26, (8), 1192‒1199 (2010). [CrossRef]
  7. J. Buysse, M. D. Leenheer, C. Develder, and B. Dhoedt, "Exploiting relocation to reduce network dimensions of resilient optical grids," 7th Int. Workshop on Design of Reliable Communication Networks (DRCN), Oct. 2009, pp. 100‒106.
  8. J. Buysse, M. D. Leenheer, B. Dhoedt, and C. Develder, "Providing resiliency for optical grids by exploiting relocation: A dimensioning study based on ILP," Comput. Commun. 34, (12), 1389‒1398 (2011). [CrossRef]
  9. J. Buysse, M. D. Leenheer, B. Dhoedt, and C. Develder, "On the impact of relocation on network dimensions in resilient optical grids," 14th Conf. on Optical Network Design and Modeling (ONDM), Feb. 2010.
  10. X. Liu, C. Qiao, D. Yu, and T. Jiang, "Application-specific resource provisioning for wide-area distributed computing," IEEE Network 24, (4), 25‒34 (2010). [CrossRef]
  11. R. Dutta and G. 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. Network Mag. 1, 47‒60 (2000).
  13. B. Jaumard, C. Meyer, and B. Thiongane, "Comparison of ILP formulations for the RWA problem," Opt. Switching Networking 4, (3–4), 157‒172 (2007). [CrossRef]
  14. B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, 1291‒1308 (2009). [CrossRef]
  15. B. Jaumard, C. Meyer, and B. Thiongane, P. Pardalos and M. Resende, ed., "ILP formulations for the RWA problem for symmetrical systems," Handbook for Optimization in Telecommunications, Kluwer, 2006, pp. 637‒678ch. 23.
  16. C. Develder, B. Mukherjee, B. Dhoedt, and P. Demeester, "On dimensioning optical grids and the impact of scheduling," Photonic Network Commun. 17, (3), 255‒265 (2009). [CrossRef]
  17. X. Liu, C. Qiao, W. Wei, X. Yu, T. Wang, W. Hu, W. Guo, and M.-Y. Wu, "Task scheduling and lightpath establishment in optical grids," J. Lightwave Technol. 27, (12), 1796‒1805 (2009). [CrossRef]
  18. T. Stidsen, B. Petersen, S. Spoorendonk, M. Zachariasen, and K. Rasmussen, "Optimal routing with failure-independent path protection," Networks 2, (55), 125‒137 (2010).
  19. A. Koster, A. Zymolka, M. Jäger, and R. Hulsermann, "Demand-wise shared protection for meshed optical networks," J. Netw. Syst. Manage. 13, (1), 35‒55 (2005). [CrossRef]
  20. B. Jaumard, J. Buysse, A. Shaikh, M. Leenheer, and C. Develder, "Column generation for dimensioning resilient optical grid networks exploiting relocation," IEEE Global Telecommunications Conf. (GLOBECOM), 2010.
  21. K.-I. Sato, Advances in Transport Network Technologies: Photonic Networks, ATM and SDH, Artech House Publishers, 1996.
  22. V. Chvatal, Linear Programming, Freeman, 1983.
  23. L. Lasdon, Optimization Theory for Large Systems, MacMillan, New York, 1970.
  24. H. Zang, C. Ou, and B. Mukherjee, "Path-protection routing and wavelength assignment RWA in WDM mesh networks under duct-layer constraints," IEEE/ACM Trans. Netw. 11, (2), 248‒258 (2003). [CrossRef]
  25. J. Suurballe, "Disjoint paths in a network," Networks 14, 125‒145 (1974). [CrossRef]
  26. J. Suurballe and R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks 14, 325‒336 (1984). [CrossRef]
  27. E. Dijkstra, "A note on two problems in connexion with graphs," Numer. Math. 1, 269‒271 (1959). [CrossRef]
  28. S. De Maesschalck, D. Colle, I. Lievens, M. Pickavet, P. Demeester, C. Mauz, M. Jaeger, R. Inkret, B. Mikac, and J. Derkacz, "Pan-European optical transport networks: An availability-based comparison," Photonic Network Commun. 5, (3), 203‒225 (2003). [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

OSA is a member of CrossRef.

CrossCheck Deposited