IDEAS home Printed from https://ideas.repec.org/a/spr/telsys/v87y2024i4d10.1007_s11235-024-01217-3.html
   My bibliography  Save this article

Linear programming based heuristic algorithms for tunnel assignment and reconfiguration in MPLS networks

Author

Listed:
  • Seulgi Joung

    (Ajou University)

  • Jaehyeon Ryu

    (Korea Advanced Institute of Science and Technology)

  • Sun-Hyeon Kwon

    (Korea Advanced Institute of Science and Technology)

  • Jongyoon Shin

    (SK telecom)

  • Sungsoo Park

    (Korea Advanced Institute of Science and Technology)

Abstract

Multi-Protocol Label Switching (MPLS) sets up a connecting tunnel for each origin–destination pair of traffic demands to send data packets over Internet Protocol (IP) networks. We should assign each tunnel to one of the available candidate paths to achieve efficient use of the network and avoid congestion. Additionally, we need to update the bandwidths and routing of the tunnels efficiently in short periods of time to accommodate fluctuating traffic demands, which we refer to as the reconfiguration problem. In this paper, we propose formulations and linear programming-based heuristic algorithms for the tunnel assignment and reconfiguration problems arising in MPLS networks. First, we propose a formulation and algorithms for the tunnel assignment problem, considering realistic constraints such as port limitations and priority queue capacity restrictions. Our model incorporates unidirectional, bidirectional, protected, and unprotected tunnel cases altogether. Then, we present a heuristic algorithm to obtain a schedule for changing the bandwidths and routing of tunnels from the current configuration to a target configuration quickly while adhering to network capacity constraints. We report computational results using some random data from the real-life telecommunication network of the Republic of Korea.

Suggested Citation

  • Seulgi Joung & Jaehyeon Ryu & Sun-Hyeon Kwon & Jongyoon Shin & Sungsoo Park, 2024. "Linear programming based heuristic algorithms for tunnel assignment and reconfiguration in MPLS networks," Telecommunication Systems: Modelling, Analysis, Design and Management, Springer, vol. 87(4), pages 991-1013, December.
  • Handle: RePEc:spr:telsys:v:87:y:2024:i:4:d:10.1007_s11235-024-01217-3
    DOI: 10.1007/s11235-024-01217-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11235-024-01217-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s11235-024-01217-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kyungchul Park & Seokhoon Kang & Sungsoo Park, 1996. "An Integer Programming Approach to the Bandwidth Packing Problem," Management Science, INFORMS, vol. 42(9), pages 1277-1291, September.
    2. Seohee Kim & Chungmok Lee, 2021. "A branch and price approach for the robust bandwidth packing problem with queuing delays," Annals of Operations Research, Springer, vol. 307(1), pages 251-275, December.
    3. Kang, Jangha & Park, Kyungchul & Park, Sungsoo, 2004. "ATM VP-based network design," European Journal of Operational Research, Elsevier, vol. 158(3), pages 555-569, November.
    4. Klopfenstein, Olivier, 2008. "Rerouting tunnels for MPLS network resource optimization," European Journal of Operational Research, Elsevier, vol. 188(1), pages 293-312, July.
    5. Cynthia Barnhart & Christopher A. Hane & Pamela H. Vance, 2000. "Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems," Operations Research, INFORMS, vol. 48(2), pages 318-326, April.
    6. Yalçın Akçay & Haijun Li & Susan Xu, 2007. "Greedy algorithm for the general multidimensional knapsack problem," Annals of Operations Research, Springer, vol. 150(1), pages 17-29, March.
    7. Jinil Han & Kyungsik Lee & Chungmok Lee & Sungsoo Park, 2013. "Exact Algorithms for a Bandwidth Packing Problem with Queueing Delay Guarantees," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 585-596, August.
    8. Seulgi Joung & Jaeyoong Lim & Chungmok Lee & Jongyoon Shin & Ikkyun Jung & Sungsoo Park, 2020. "A linear programming based heuristic algorithm for bandwidth packing problem with scheduling," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 71(2), pages 250-263, February.
    9. Manuel Laguna & Fred Glover, 1993. "Bandwidth Packing: A Tabu Search Approach," Management Science, INFORMS, vol. 39(4), pages 492-500, April.
    10. Jakob Puchinger & Günther R. Raidl & Ulrich Pferschy, 2010. "The Multidimensional Knapsack Problem: Structure and Algorithms," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 250-265, May.
    11. Chungmok Lee & Kyungsik Lee & Kyungchul Park & Sungsoo Park, 2012. "Technical Note---Branch-and-Price-and-Cut Approach to the Robust Network Design Problem Without Flow Bifurcations," Operations Research, INFORMS, vol. 60(3), pages 604-610, June.
    12. Renata Mansini & M. Grazia Speranza, 2012. "CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 399-415, August.
    13. Navneet Vidyarthi & Sachin Jayaswal & Vikranth Babu Tirumala Chetty, 2016. "Bandwidth packing problem with queueing delays: modelling and exact solution approach," Journal of Global Optimization, Springer, vol. 65(4), pages 745-776, August.
    14. M Hifi & M Michrafy & A Sbihi, 2004. "Heuristic algorithms for the multiple-choice multidimensional knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(12), pages 1323-1332, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Seohee Kim & Chungmok Lee, 2021. "A branch and price approach for the robust bandwidth packing problem with queuing delays," Annals of Operations Research, Springer, vol. 307(1), pages 251-275, December.
    2. Kang, Jangha & Park, Kyungchul & Park, Sungsoo, 2009. "Optimal multicast route packing," European Journal of Operational Research, Elsevier, vol. 196(1), pages 351-359, July.
    3. Jinil Han & Kyungsik Lee & Chungmok Lee & Sungsoo Park, 2013. "Exact Algorithms for a Bandwidth Packing Problem with Queueing Delay Guarantees," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 585-596, August.
    4. Jayaswal, Sachin & Vidyarthi, Navneet & Das, Sagnik, 2014. "An Efficient Solution Approach for Combinatorial Bandwidth Packing Problem with Queuing Delays," IIMA Working Papers WP2014-12-05, Indian Institute of Management Ahmedabad, Research and Publication Department.
    5. Navneet Vidyarthi & Sachin Jayaswal & Vikranth Babu Tirumala Chetty, 2016. "Bandwidth packing problem with queueing delays: modelling and exact solution approach," Journal of Global Optimization, Springer, vol. 65(4), pages 745-776, August.
    6. François Lamothe & Emmanuel Rachelson & Alain Haït & Cedric Baudoin & Jean-Baptiste Dupé, 2021. "Randomized rounding algorithms for large scale unsplittable flow problems," Journal of Heuristics, Springer, vol. 27(6), pages 1081-1110, December.
    7. Vidyarthi, Navneet & Jayaswal, Sachin & Chetty, Vikranth Babu Tirumala, 2013. "Exact Solution to Bandwidth Packing Problem with Queuing Delays," IIMA Working Papers WP2013-11-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    8. Baris Yildiz & Martin Savelsbergh, 2019. "Provably High-Quality Solutions for the Meal Delivery Routing Problem," Transportation Science, INFORMS, vol. 53(5), pages 1372-1388, September.
    9. Bahram Alidaee & Vijay P. Ramalingam & Haibo Wang & Bryan Kethley, 2018. "Computational experiment of critical event tabu search for the general integer multidimensional knapsack problem," Annals of Operations Research, Springer, vol. 269(1), pages 3-19, October.
    10. Amiri, Ali, 2005. "The selection and scheduling of telecommunication calls with time windows," European Journal of Operational Research, Elsevier, vol. 167(1), pages 243-256, November.
    11. Bose, Indranil, 2009. "Bandwidth packing with priority classes," European Journal of Operational Research, Elsevier, vol. 192(1), pages 313-325, January.
    12. Amiri, Ali & Barkhi, Reza, 2011. "The combinatorial bandwidth packing problem," European Journal of Operational Research, Elsevier, vol. 208(1), pages 37-45, January.
    13. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    14. Barış Yıldız & Oya Ekin Karaşan, 2017. "Regenerator Location Problem in Flexible Optical Networks," Operations Research, INFORMS, vol. 65(3), pages 595-620, June.
    15. Changyong Zhang, 2017. "An origin-based model for unique shortest path routing," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(8), pages 935-951, August.
    16. Amiri, Ali & Rolland, Erik & Barkhi, Reza, 1999. "Bandwidth packing with queuing delay costs: Bounding and heuristic solution procedures," European Journal of Operational Research, Elsevier, vol. 112(3), pages 635-645, February.
    17. Fortz, Bernard & Gouveia, Luís & Joyce-Moniz, Martim, 2017. "Models for the piecewise linear unsplittable multicommodity flow problems," European Journal of Operational Research, Elsevier, vol. 261(1), pages 30-42.
    18. Setzer, Thomas & Blanc, Sebastian M., 2020. "Empirical orthogonal constraint generation for Multidimensional 0/1 Knapsack Problems," European Journal of Operational Research, Elsevier, vol. 282(1), pages 58-70.
    19. Lamanna, Leonardo & Mansini, Renata & Zanotti, Roberto, 2022. "A two-phase kernel search variant for the multidimensional multiple-choice knapsack problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 53-65.
    20. Kang, Jangha & Park, Kyungchul & Park, Sungsoo, 2004. "ATM VP-based network design," European Journal of Operational Research, Elsevier, vol. 158(3), pages 555-569, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:telsys:v:87:y:2024:i:4:d:10.1007_s11235-024-01217-3. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.