Abstract

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

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  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]

2011 (1)

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]

2010 (4)

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]

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]

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]

T. Stidsen, B. Petersen, S. Spoorendonk, M. Zachariasen, and K. Rasmussen, "Optimal routing with failure-independent path protection," Networks 2, (55), 125‒137 (2010).

2009 (3)

B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, 1291‒1308 (2009).
[CrossRef]

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]

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]

2007 (1)

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]

2005 (2)

A. Jaiszczyk, "Automatically switched optical networks: Benefits and requirements," IEEE Commun. Mag. 43, (2), S10‒S15 (2005).
[CrossRef]

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]

2003 (2)

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]

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]

2000 (2)

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).

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).

1984 (1)

J. Suurballe and R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks 14, 325‒336 (1984).
[CrossRef]

1974 (1)

J. Suurballe, "Disjoint paths in a network," Networks 14, 125‒145 (1974).
[CrossRef]

1959 (1)

E. Dijkstra, "A note on two problems in connexion with graphs," Numer. Math. 1, 269‒271 (1959).
[CrossRef]

Anedda, P.

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]

Buysse, J.

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]

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.

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.

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.

Chvatal, V.

V. Chvatal, Linear Programming, Freeman, 1983.

Colle, D.

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]

De Leenheer, M.

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.

De Maesschalck, S.

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]

Demeester, P.

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]

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]

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.

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.

Derkacz, J.

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]

Develder, C.

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]

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]

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.

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.

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.

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.

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.

Dhoedt, B.

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]

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]

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.

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.

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.

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.

Dijkstra, E.

E. Dijkstra, "A note on two problems in connexion with graphs," Numer. Math. 1, 269‒271 (1959).
[CrossRef]

Dutta, R.

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).

Gaggero, M.

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]

Guo, W.

Hu, W.

Hulsermann, R.

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]

Inkret, R.

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]

Jaeger, M.

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]

Jäger, M.

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]

Jaiszczyk, A.

A. Jaiszczyk, "Automatically switched optical networks: Benefits and requirements," IEEE Commun. Mag. 43, (2), S10‒S15 (2005).
[CrossRef]

Jaumard, B.

B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, 1291‒1308 (2009).
[CrossRef]

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]

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.

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.

Jiang, T.

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]

Jue, J. P.

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).

Koster, A.

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]

Lasdon, L.

L. Lasdon, Optimization Theory for Large Systems, MacMillan, New York, 1970.

Lee, Y. C.

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]

Leenheer, M.

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.

Leenheer, M. D.

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]

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.

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.

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.

Leo, S.

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]

Lievens, I.

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]

Liu, X.

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]

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]

Manca, S.

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]

Mauz, C.

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]

Meyer, C.

B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, 1291‒1308 (2009).
[CrossRef]

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]

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.

Mikac, B.

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]

Mukherjee, B.

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]

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]

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).

Ou, C.

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]

Petersen, B.

T. Stidsen, B. Petersen, S. Spoorendonk, M. Zachariasen, and K. Rasmussen, "Optimal routing with failure-independent path protection," Networks 2, (55), 125‒137 (2010).

Pickavet, M.

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]

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.

Qiao, C.

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]

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]

Rasmussen, K.

T. Stidsen, B. Petersen, S. Spoorendonk, M. Zachariasen, and K. Rasmussen, "Optimal routing with failure-independent path protection," Networks 2, (55), 125‒137 (2010).

Rouskas, G.

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).

Sato, K.-I.

K.-I. Sato, Advances in Transport Network Technologies: Photonic Networks, ATM and SDH, Artech House Publishers, 1996.

Shaikh, A.

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.

Spoorendonk, S.

T. Stidsen, B. Petersen, S. Spoorendonk, M. Zachariasen, and K. Rasmussen, "Optimal routing with failure-independent path protection," Networks 2, (55), 125‒137 (2010).

Stevens, T.

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.

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.

Stidsen, T.

T. Stidsen, B. Petersen, S. Spoorendonk, M. Zachariasen, and K. Rasmussen, "Optimal routing with failure-independent path protection," Networks 2, (55), 125‒137 (2010).

Suurballe, J.

J. Suurballe and R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks 14, 325‒336 (1984).
[CrossRef]

J. Suurballe, "Disjoint paths in a network," Networks 14, 125‒145 (1974).
[CrossRef]

Tarjan, R.

J. Suurballe and R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks 14, 325‒336 (1984).
[CrossRef]

Thiongane, B.

B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, 1291‒1308 (2009).
[CrossRef]

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]

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.

Turck, F. D.

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.

Wang, T.

Wei, W.

Wu, M.-Y.

Yu, D.

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]

Yu, X.

Zachariasen, M.

T. Stidsen, B. Petersen, S. Spoorendonk, M. Zachariasen, and K. Rasmussen, "Optimal routing with failure-independent path protection," Networks 2, (55), 125‒137 (2010).

Zanetti, G.

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]

Zang, H.

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]

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).

Zomaya, A. Y.

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]

Zymolka, A.

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]

Comput. Commun. (1)

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]

Discrete Appl. Math. (1)

B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, 1291‒1308 (2009).
[CrossRef]

FGCS, Future Gener. Comput. Syst. (2)

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]

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]

IEEE Commun. Mag. (1)

A. Jaiszczyk, "Automatically switched optical networks: Benefits and requirements," IEEE Commun. Mag. 43, (2), S10‒S15 (2005).
[CrossRef]

IEEE Network (1)

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]

IEEE/ACM Trans. Netw. (1)

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]

J. Lightwave Technol. (1)

J. Netw. Syst. Manage. (1)

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]

Networks (3)

J. Suurballe, "Disjoint paths in a network," Networks 14, 125‒145 (1974).
[CrossRef]

J. Suurballe and R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks 14, 325‒336 (1984).
[CrossRef]

T. Stidsen, B. Petersen, S. Spoorendonk, M. Zachariasen, and K. Rasmussen, "Optimal routing with failure-independent path protection," Networks 2, (55), 125‒137 (2010).

Numer. Math. (1)

E. Dijkstra, "A note on two problems in connexion with graphs," Numer. Math. 1, 269‒271 (1959).
[CrossRef]

Opt. Network Mag. (1)

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).

Opt. Networks Mag. (1)

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).

Opt. Switching Networking (1)

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]

Photonic Network Commun. (2)

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]

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]

Other (10)

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.

K.-I. Sato, Advances in Transport Network Technologies: Photonic Networks, ATM and SDH, Artech House Publishers, 1996.

V. Chvatal, Linear Programming, Freeman, 1983.

L. Lasdon, Optimization Theory for Large Systems, MacMillan, New York, 1970.

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.

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.

I. Foster and C. Kesselman, ed., The Grid: Blueprint for a New Computing Infrastructure, 2nd ed., Morgan Kaufmann, San Francisco, CA, 2004.

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.

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.

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.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (7)

Fig. 1
Fig. 1

(Color online) The original pan-European network topology and two variants of it.

Fig. 2
Fig. 2

(Color online) Comparison of the performances of ILP, CG-ILP, H1 and H2 on small data sets (SPR-A protection scheme).

Fig. 3
Fig. 3

(Color online) Performances of H1 and H2 compared to CG-ILP.

Fig. 4
Fig. 4

(Color online) Running times for the SPA-R protection scheme.

Fig. 5
Fig. 5

(Color online) Comparison of the running times for different numbers of server nodes on the EU-base topology (CG-ILP algorithm).

Fig. 6
Fig. 6

(Color online) Impact of the topology connectivity (CG-ILP algorithm): running times for the SPR-A protection scheme.

Fig. 7
Fig. 7

(Color online) SPR-A versus CSP-A protection schemes with respect to the number of bandwidth units—(CSP-A − SPR-A)/CSP-A.

Equations (32)

Equations on this page are rendered with MathJax. Learn more.

min  cost  ilp ( p  w , b  b ) ,
 cost  ilp ( p  w , b  b ) = L b  b + k K p k  w .
ω + ( v ) p k  w ω ( v ) p k  w = 1  if v = v k d k v  w  if v V d 0  otherwise v V , k K .
ω + ( v ) p k  b ω ( v ) p k  b = 1  if v = v k d k v  b  if v V d 0  otherwise v V , k K .
p k  w + p k  b 1 L , k K ,
p k  w + p k  b 1 , L :  and   are opposite to each other , k K .
b  b k K δ k , L : ,
δ k p k  w + p k  b 1 k K ; , L : .
v d V d d k v  w = 1 k K ,
v d V d d k v  b = 1 k K .
d k v  b = d k v  w v V d , k K .
v s S : D s > 0 .
min  cost  cg _  ilp ( z , b  b ) ,
 cost  cg _  ilp ( z , b  b ) = L b  b + c C p c  w z c .
c C s z c D s v s S .
c C p c  w p c  b z c b  b , L : .
 cost ¯  cg _  ilp = L p  w u 1 L L : u 2 p  w p  b .
ω + ( v ) p  w ω ( v ) p  w = 1  if  v = v s d v  w  if  v V d 0  otherwise v V ,
ω + ( v ) p  b ω ( v ) p  b = 1  if  v = v s d v  b  if  v V d 0  otherwise v V .
p  w + p  b 1 L ,
p  w + p  b 1 , L :  and   are opposite to each other .
v V d d v  w = 1 ,
v V d d v  b = 1 .
d v  b = d v  w v V d .
p  w  b = p  w p  b p  w , p  b { 0 , 1 } ; , L :
p  w  b p  w + p  b 1 , L : ,
p  w p  w  b , L : ,
p  b p  w  b , L : .
 cost ¯  cg _  ilp = L p  w u 1 L L : u 2 p  w  b .
min L p  w + p  b .
b  b = max L k K p k  b p k  w .
 cost  h1  cost  cg−ilp  cost  h1 and  cost  h2  cost  cg−ilp  cost  h2 ,