Column generation algorithm for RSA problems in flexgrid optical networks | Photonic Network Communications Skip to main content
Springer Nature Link
Log in

Column generation algorithm for RSA problems in flexgrid optical networks

  • Published:
Photonic Network Communications Aims and scope Submit manuscript

Abstract

Finding optimal routes and spectrum allocation in flexgrid optical networks, known as the RSA problem, is an important design problem in transport communication networks. The problem is \(\mathcal{NP }\)-hard, and its intractability becomes profound when network instances with several tens of nodes and several hundreds of demands are to be solved to optimum. In order to deal with such instances, large-scale optimization methods need to be considered. In this work, we present a column (more precisely, path) generation-based method for the RSA problem. The method is capable of finding reasonable sets of lightpaths, avoiding large sets of precomputed paths, and leading to high-quality solutions. Numerical results illustrating effectiveness of the proposed method for obtaining solutions for large RSA problem instances are presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Spectral grids for WDM applications: DWDM frequency grid. ITU-T G.694.1 (ed. 2.0) (2012)

  2. Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H.: Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46, 316–329 (1996)

    Article  MathSciNet  Google Scholar 

  3. Christodoulopoulos, K., Tomkos, I., Varvarigos, E.A.: Elastic bandwidth allocation in flexible OFDM-based optical networks. IEEE J. Lightw. Technol. 29(9), 1354–1366 (2011)

    Article  Google Scholar 

  4. Cugini, F., Meloni, G., Paolucci, F., Sambo, N., Secondini, M., Gerardi, L., Poti, L., Castoldi, P.: Demonstration of flexible optical network based on path computation element. IEEE J. Lightw. Technol. 30(5), 727–733 (2012)

    Article  Google Scholar 

  5. Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  6. Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962). doi:10.1145/367766.368168

    Article  Google Scholar 

  7. Geisler, D.J., Proietti, R., Yin, Y., Scott, R.P., Cai, X., Fontaine, N.K., Paraschis, L., Gerstel, O., Yoo, S.J.B.: The first testbed demonstration of a flexible bandwidth network with a real-time adaptive control plane. In: Proceedings of the ECOC. Geneva, Switzerland (2011)

  8. ILOG: CPLEX 12.2 user’s manual. ILOG (2010). ftp://ftp.software.ibm.com/software/websphere/ilog/docs/optimization/cplex/ps_usrmancplex.pdf

  9. Jaumard, B., Meyer, C., Thiongane, B.: On column generation formulations for the RWA problem. Discret. Appl. Math. 157(6), 1291–1308 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Jinno, M., Takara, H., Kozicki, B., Tsukishima, Y., Sone, Y., Matsuoka, S.: Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies. IEEE Commun. Mag. 47(11), 66–73 (2009)

    Article  Google Scholar 

  11. Klinkowski, M., Ruiz, M., Velasco, L., Careglio, D., Lopez, V., Comellas, J.: Elastic spectrum allocation for time-varying traffic in flexgrid optical networks. IEEE J. Sel. Areas Commun. 31(1), 26–38 (2013)

    Article  Google Scholar 

  12. Klinkowski, M., Walkowiak, K.: Routing and spectrum assignment in spectrum sliced elastic optical path network. IEEE Commun. Lett. 15(8), 884–886 (2011)

    Article  Google Scholar 

  13. Lasdon, L.: Optimization Theory for Large Systems. MacMillan, New York (1970)

    MATH  Google Scholar 

  14. Liu, Z., Rouskas, G.N.: A fast path-based ILP formulation for offline RWA in mesh optical networks. In: Proceedings of the IEEE Globecom. Anaheim, California (2012)

  15. MATLAB: version 7.10.0 (R2010a). The MathWorks Inc., Natick, Massachusetts (2010)

  16. Pióro, M.: Mathematical Foundations for Signal Processing, Communications, and Networking, Chap. Network Optimization Techniques. CRC Press, Boca Raton (2012)

    Google Scholar 

  17. Pióro, M., Medhi, D.: Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufman, Los Altos (2004)

    MATH  Google Scholar 

  18. Ruiz, M., Rebolo, D., Pióro, M., Żotkiewicz, M., Klinkowski, M., Velasco, L.: Detailed description of column generation algorithms for RSA problems in flexgrid optical networks. Technical report, UPC-DAC-RR-2013-15, Barcelona, Spain (2013)

  19. Velasco, L., Klinkowski, M., Ruiz, M., Comellas, J.: Modeling the routing and spectrum allocation problem for flexgrid optical networks. Photonic Netw. Commun. 24, 177–186 (2012)

    Article  Google Scholar 

  20. Wang, Y., Cao, X., Hu, Q., Pan, Y.: Towards elastic and fine-granular bandwidth allocation in spectrum-sliced optical networks. IEEE J. Opt. Commun. Netw. 4(11), 906–917 (2012)

    Article  Google Scholar 

Download references

Acknowledgments

The presented work was supported by the FP7 project IDEALIST (Grant agreement no. 317999). The work was also supported by National Science Center (Poland) under Grant 2011/01/B/ST7/02967 (M. Pióro and M. Żotkiewicz) and 2011/01/D/ST7/05884 (M. Klinkowski). M. Żotkiewicz was additionally supported by the EC European Social Fund through the Warsaw University of Technology Development Programme. Also, M. Ruiz and L. Velasco were supported by the Spanish Ministry of Science through the TEC2011-27310 ELASTIC project. The authors wish to thank David Rebolo for his valuable collaboration.

Author information

Authors and Affiliations

  1. Computers Architecture Department, Universitat Politècnica de Catalunya, c/ Jordi Girona, 31, 08034 , Barcelona, Spain

    Marc Ruiz & Luis Velasco

  2. Institute of Telecommunications, Warsaw University of Technology, Nowowiejska 15/19, 00-665 , Warszawa, Poland

    Michał Pióro & Mateusz Żotkiewicz

  3. Department of Transmission and Optical Technologies, National Institute of Telecommunications, Szachowa 1, 04-894 , Warszawa, Poland

    Mirosław Klinkowski

Authors
  1. Marc Ruiz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michał Pióro
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mateusz Żotkiewicz
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mirosław Klinkowski
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Luis Velasco
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marc Ruiz.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ruiz, M., Pióro, M., Żotkiewicz, M. et al. Column generation algorithm for RSA problems in flexgrid optical networks. Photon Netw Commun 26, 53–64 (2013). https://doi.org/10.1007/s11107-013-0408-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11107-013-0408-0

Keywords

Search

Navigation