User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Intra-domain traffic engineering with shortest path routing protocols

Primary tabs

Altin, Aysegul Fortz, Bernard [UCL] Thorup, Mikkel Umit, Hakan [UCL]

Throughout the last decade, extensive deployment of popular intra-domain routing protocols such as open shortest path first and intermediate system-intermediate system, has drawn an ever increasing attention to Internet traffic engineering. This paper reviews optimization techniques that have been deployed for managing intra-domain routing in networks operated with shortest path routing protocols, and the state-of-the-art research that has been carried out in this direction.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2009
Language Anglais
Journal information "4 O R : quarterly journal of the Belgian, French and Italian operations research societies" - Vol. 7, no. 4, p. 301-335 (2009)
Peer reviewed yes
Publisher Springer Heidelberg (Heidelberg)
issn 1619-4500
e-issn 1614-2411
Publication status Publié
Affiliations UCL - SSH/LIDAM/CORE - Center for operations research and econometrics
UCL - ESPO/IAG - Département d'administration et de gestion
Louvain School of Management - Operations and Information
Keywords OSPF ; IS-IS ; Internet traffic engineering ; Shortest path routing
Links
  1. Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs
  2. Altın A, Belotti P, Pınar M (2006) OSPF routing with optimal oblivious performance ratio under polyhedral demand uncertainty. Technical report, Bilkent University
  3. Altın A, Fortz B, Ümit H (2008) Oblivious OSPF routing with weight optimization under polyhedral demand uncertainty. Technical report 588, ULB Computer Science Department, http://www.ulb.ac.be//di/publications/RT_2008.html
  4. Altın A, Fortz B, Ümit H (2009) Oblivious OSPF routing with weight optimization under polyhedral uncertainty. In: Proceedings of the 3rd international network optimization conference (INOC 2009), Pisa, Italy
  5. Applegate D, Cohen E (2003) Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs. In: SIGCOMM ’03: proceedings of the 2003 conference on applications, technologies, architectures, and protocols for computer communications, ACM, New York, NY, USA, pp 313–324, doi: 10.1145/863955.863991
  6. Applegate D, Cohen E (2006) Making routing robust to changing traffic demands: algorithms and evaluation. IEEE/ACM Trans Netw
  7. Balon S, Leduc G (2008) Combined intra- and inter-domain traffic engineering using hot-potato aware link weights optimization. In: SIGMETRICS ’08: proceedings of the 2008 ACM SIGMETRICS international conference on measurement and modeling of computer systems, ACM, New York, NY, USA, pp 441–442, doi: 10.1145/1375457.1375511
  8. Balon S, Leduc G (2009) BGP-aware IGP link weight optimization in presence of route reflectors. In: Proceedings of IEEE INFOCOM, Rio de Janeiro, Brazil, pp 316–324
  9. Balon S, Skivée F, Leduc G (2006) How well do traffic engineering objective functions meet TE requirements? In: Proceedings of IFIP Networking 2006, vol 3976, Coimbra, Springer LNCS
  10. Bauer D, Yuksel M, Carothers C, Kalyanaraman S (2006) A case study in understanding OSPF and BGP interactions using efficient experiment design. In: PADS ’06: proceedings of the 20th workshop on principles of advanced and distributed simulation, IEEE Computer Society, Washington, DC, USA, pp 158–165, doi: 10.1109/PADS.2006.6
  11. Bean James C., Genetic Algorithms and Random Keys for Sequencing and Optimization, 10.1287/ijoc.6.2.154
  12. Bellman R (1958) On a routing problem. Q Appl Math 16(1): 87–90
  13. Belotti P, Pınar M (2008) Optimal oblivious routing under statistical uncertainty. Optim Eng 9(3): 257–271
  14. Ben-Ameur W (2002) Multi-hour design of survivable classical IP networks. Int J Commun Syst 15: 553–572
  15. Ben-Ameur W, Gourdin E (2003) Internet routing and related topology issues. SIAM J Discrete Math 17(1): 18–49
  16. Ben-Ameur W, Kerivin H (2005) Routing of uncertain demands. Optim Eng 3: 283–313
  17. Ben-Ameur W, Gourdin E, Liau B, Michel N (2000a) Dimensioning of Internet networks. In: Proceedings international workshop on design of reliable communication networks (DRCN’2000), Munich, Germany, pp 56–61
  18. Ben-Ameur W, Gourdin E, Liau B, Michel N (2000b) Optimizing administrative weights for efficient single-path routing. In: Proceedings of Networks
  19. Blanchy F, Mélon L, Leduc G (2003) Routing in a MPLS network featuring preemption mechanisms. In: Proceedings of 10th international conference on telecommunications (ICT’2003), IEEE Press, Papeete, Tahiti, pp 253–260
  20. Bley A (2003) A Lagrangian approach for integrated network design and routing in ip networks. In: Proceedings of the 1st international network optimization conference (INOC 2003), Paris, France, pp 107–113
  21. Bley A (2005) Finding small administrative lengths for shortest path routing. In: Proceedings of international network optimization conference (INOC 2005), pp 121–128, Lisbon, Portugal
  22. Bley A (2007a) Inapproximability results for the inverse shortest paths problem with integer lengths and unique shortest paths. Networks 50(1): 29–36
  23. Bley A (2007b) Routing and capacity optimization for IP networks. PhD thesis, Technische Univertität Berlin
  24. Bley A, Koch T (2002) Integer programming approaches to access and backbone IP-network planning. Technical report ZR-02-41, ZIB, to appear. In: Proceedings of 3rd international conference on high performance scientific computing, 2006, Hanoi
  25. Bley A, Grötschel M, Wessäly R (2000) Design of broadband virtual private networks: model and heuristics for the bwin. Robust Commun Netw: Interconnect Surviv 53: 1–16
  26. Bley A, Fortz B, Gourdin E, Holmberg K, Pióro M, Tomaszsewski A, Ümit H (2009) Graphs and algorithms (COST 293). Springer (in preparation)
  27. Broström P, Holmberg K (2005) Design of IP/OSPF networks using a Lagrangean heuristic on an in-graph based model. In: Gouveia L, Mourao C (eds) Proceedings of INOC 2005, University of Lisbon, Lisbon, Portugal, pp 702–709
  28. Broström P, Holmberg K (2008) Valid cycles: a source of infeasibility in open shortest path first routing. Networks 52(4):206–215, doi: 10.1002/net.v52:4
  29. Buriol L, Resende M, Ribeiro C, Thorup M (2005) A hybrid genetic algorithm for the weight setting problem in OSPF/IS–IS routing. Networks 46(1): 36–56
  30. Buriol LS, Resende MGC, Thorup M (2008) Speeding up dynamic shortest-path algorithms. INFORMS J Comput 20(2): 191–204. doi: 10.1287/ijoc.1070.0231
  31. Cerav-Erbas S, Delcourt O, Fortz B, Quoitin B (2006) The interaction of igp weight optimization with bgp. In: Internet surveillance and protection, international conference on, IEEE Computer Society, Los Alamitos, CA, USA, vol 0, p 9, doi: 10.1109/ICISP.2006.33
  32. CISCO (2009) Tunnel builder pro. http://www.cisco.com/
  33. De Giovanni L, Fortz B, Labbé M (2005) A lower bound for the Internet protocol network design problem. In: Gouveia L (ed) Proceedings of INOC 2005, pp 401–407
  34. Degrande N, Hoey GV, de la Vallée-Poussin P, van den Busch S (2003) Inter-area traffic engineering in a differentiated services network. J Netw Syst Manage 11(4): 427–445
  35. Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1: 269–271
  36. Elwalid A, Jin C, Low S, Widjaja I (2001) MATE: MPLS adaptive traffic engineering. In: Proceedings of IEEE INFOCOM, pp 1300–1309
  37. Ericsson M, Resende M, Pardalos P (2002) A genetic algorithm for the weight setting problem in OSPF routing. J Comb Optim 6: 299–333
  38. Farago A, Szentesi A, Szviatovszki A (2003) Inverse optimization in high-speed networks. Discrete Appl Math 129: 83–98
  39. Feldmann A, Rexford J (2001) IP network configuration for intradomain traffic engineering. IEEE Netw Mag 15: 46–57
  40. Feldmann A, Greenberg A, Lund C, Reingold N, Rexford J (2000) Netscope: traffic engineering for IP networks. IEEE Netw Mag 11–19
  41. Ford LR, Fulkerson DR (1962) Flows in networks. Princeton University Press, Princeton
  42. Fortuny C (2008) Estimation du trafic, planification et optimisation des ressources pour l’ingénierie des réseaux IP/MPLS. PhD thesis, Université de Toulouse III—Paul Sabatier, UFR Mathématiques, Informatique, Gestion
  43. Fortuny C, Brun O, Garcia JM (September 2005) Metric optimization in IP networks. In: Proceedings of 19th international teletraffic congress, Beijing, China, pp 1225–1234
  44. Fortz B, Thorup M (2000) Internet traffic engineering by optimizing ospf weights. In: Proceedings of 19th IEEE Conference on Computer Communications (INFOCOM), pp 519–528
  45. Fortz B, Thorup M (2002) Optimizing OSPF/IS–IS weights in a changing world. IEEE J Sel Areas Commun 20(4): 756–767
  46. Fortz B, Thorup M (2003) Robust optimization of OSPF/IS–IS weights. In: Ben-Ameur W, Petrowski A (eds) Proceedings of INOC 2003, pp 225–230
  47. Fortz B, Thorup M (2004) Increasing Internet capacity using local search. Comput Optim Appl 29(1): 13–48
  48. Gajowniczek O, Pióro M, Szentesi A, Harmatos J, Jüttner A (2000) Solving an OSPF routing problem with simulated allocation. In: Proceedings of 1st Polish-German teletraffic symposium, Dresden, Germany, pp 177–184
  49. Hawkinson J (1996) RFC 1930—guidelines for creation, selection, and registration of an autonomous system (AS)
  50. Holmberg K, Yuan D (2000) A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Oper Res 48: 461–481
  51. Holmberg K, Yuan D (2004) Optimization of Internet protocol network design and routing. Networks 43(1): 39–53
  52. Inc CS: (2000) Internetworking technologies handbook. 3. Cisco Press, Indianapolis
  53. Jüttner A, Szentesi A, Harmatos J, Pióro M (2000) On solvability of an OSPF routing problem. In: Proceedings 15th Nordic Teletraffic Seminar, Lund
  54. Kodialam M, Lakshman T (2000) Minimum interference routing with applications to mpls routing. In: Proceedigs of IEEE INFOCOM, pp 884–893
  55. Leduc G, Abrahamsson H, Balon S, Bessler S, D’Arienzo M, Delcourt O, Domingo-Pascual J, Cerav-Erbas S, Gojmerac I, Masip X, Pescaph A, Quoitin B, Romano S, Salvatori E, Skivée F, Tran H, Uhlig S, H (2006) An open source traffic engineering toolbox. Comput Commun 29(5): 593–610
  56. MATE C (2009) http://www.cariden.com/products/
  57. Mortier R (2002) Internet traffic engineering. Tech. Rep. 532. University of Cambridge, Cambridge
  58. Moy J (1998) RFC 2328—OSPF version 2
  59. Mulyana E, Killat U (2002) An alternative genetic algorithm to optimize OSPF weights. In: 15th ITC specialist seminar, Würzburg, Germany, pp 186–192
  60. Mulyana E, Killat U (2005) Optimizing IP networks for uncertain demands using outbound traffic constraints. In: Proceedings of INOC 2005, pp 695–701
  61. Parmar A, Ahmed S, Sokol J (2006) An integer programming approach to the OSPF weight setting problem. Technical report, School of Industrial & Systems Engineering, Georgia Technology
  62. Pióro M, Medhi D (2004) Routing, flow, and capacity design in communication and computer networks. Morgan Kaufman
  63. Pióro M, Szentesi A, Harmatos J, Jüttner A (2000) On OSPF related network optimization problems. In: 8th IFIP workshop on performance modelling and evaluation of ATM & IP Networks, Ilkley, UK, pp 70/1–70/14
  64. QoSDesign (2009) NEST: Network Engineering and Simulation Tool. http://www.qosdesign.com
  65. Ramalingam G, Reps T (1996) An incremental algorithm for a generalization of the shortest-path problem. J Algorithms 21(2): 267–305
  66. Smit H, Li T (2003) IS–IS extensions for traffic engineering. Technical report, Network Working Group, IETF
  67. Srivastava S, Agrawal G, Pióro M, Medhi D (2005) Determining link weight system under various objectives for OSPF networks using a Lagrangian relaxation-based approach. IEEE e-Trans Netw & Serv Manage 2(1): 9–18
  68. Tanenbaum AS (2003) Computer networks. 4. Prentice Hall PTR, Upper Saddle River
  69. Tomaszevski A, Pióro M, Dzida M, Mycek M, Zagozdzon M (2007) Valid inequalities for a shortest-path routing optimization problem. In: Proceedings of INOC 2007
  70. Tomaszewski A, Pióro M, Dzida M, Zagozdzon M (2005) Optimization of administrative weights in IP networks using the branch-and-cut approach. In: Proceedings of INOC 2005, vol 2, pp 393–400
  71. Ümit H (2005) A column generation approach for IGP weight setting problem. In: Proceedings of CoNEXT 2005, Toulouse, France, pp 294–295
  72. Ümit H, Fortz B (2007) Fast heuristic techniques for intra-domain routing metric optimization. In: Proceedings of the 2nd international network optimization conference (INOC 2007), Spa, Belgium
  73. Wang Y, Wang Z, Zhang L (2001) Internet traffic engineering without full mesh overlaying. In: Proceedings of IEEE INFOCOM, pp 565–571
  74. Wang H, Xie H, Qiu L, Yang YR, Zhang Y, Greenberg A (2006) Cope: traffic engineering in dynamic networks. In: SIGCOMM ’06: proceedings of the 2006 conference on applications, technologies, architectures, and protocols for computer communications, ACM, New York, NY, USA, pp 99–110, doi: 10.1145/1159913.1159926
  75. Waxman B (1988) Routing of multipoint connections. IEEE J Sel Areas Commun 6(9): 1617–1622
  76. Zhang C (2006) Comparison on objective functions of the unique shortest path problem. In: Proceedings of the eighth INFORMS telecommunications conference, Dallas, Texas, USA
  77. Zhang C, Rodosek R (2005) Modelling and constraint hardness characterisation of the unique-path OSPF weight setting problem. In: Proceedings ICCS-5th international conference, Atlanta, GA, USA
  78. Zhang C, Liu Y, Gong W, Kurose J, Moll R (2005) On optimal routing with multiple traffic matrices. In: Proceedings of 24th IEEE Conference on Computer Communications (INFOCOM)
Bibliographic reference Altin, Aysegul ; Fortz, Bernard ; Thorup, Mikkel ; Umit, Hakan. Intra-domain traffic engineering with shortest path routing protocols. In: 4 O R : quarterly journal of the Belgian, French and Italian operations research societies, Vol. 7, no. 4, p. 301-335 (2009)
Permanent URL http://hdl.handle.net/2078.1/35960