Applications of meta-heuristics to traffic engineering in IP networks

[en] Intra-domain routing protocols are based on shortest path first (SPF) routing, where shortest paths arecalculated between each pair of nodes (routers) using pre-assigned link weights, also referred to as linkmetric. These link weights can be modified by network administrators in accordance with the routingpolicies of the network operator. The operator’s objective is usually to minimize traffic congestion orminimize total routing cost subject to the traffic demands and the protocol constraints. However,determining a link weights combination that best suits the network operator’s requirements is a difficulttask.This paper provides a survey of meta-heuristic approaches to traffic engineering, focusing on local searchapproaches and extensions to the basic problem taking into account changing demands and robustnessissues with respect to network failures.

Disciplines :

Quantitative methods in economics & management

Author, co-author :

Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt

Language :

English

Title :

Applications of meta-heuristics to traffic engineering in IP networks

Publication date :

2011

Journal title :

International Transactions in Operational Research

ISSN :

0969-6016

Volume :

Issue :

Pages :

131-147

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://www.scopus.com/inward/record.uri?eid=2-s2.0-84863526816&doi=10.1111%2fj.1475-3995.2010.00776.x&partnerID=40&md5=bbd669629ae4fcca11f4512a05cce500

Available on ORBi :

since 17 October 2024

Statistics

Number of views

4 (1 by ULiège)

Number of downloads

0 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Alti{dotless}n, A., Belotti, P., Pinar, M.Ç, 2006. OSPF routing with optimal oblivious performance ratio under polyhedral demand uncertainty. Technical Report, Bilkent University.
Alti{dotless}n, A., Fortz, B., Thorup, M., Ümit, H., 2009. Intra-domain traffic engineering with shortest path routing protocols. Operations Research 7, 4, 301-335.
Alti{dotless}n, A., Fortz, B., Ümit, H., 2008. Oblivious OSPF routing with weight optimization under polyhedral demand uncertainty. Technical Report 588, ULB Computer Science Department. Available at http://www.ulb.ac.be//di/publications/RT_2008.html (accessed 24 April 2010).
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, pp. 313-324.
Bean, J.C., 1994. Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing 6, 154-160.
Belotti, P., Pinar, M.Ç., 2008. Optimal oblivious routing under statistical uncertainty. Optimization and Engineering 9, 3, 257-271.
Ben-Ameur, W., Gourdin, E., Liau, B., Michel, N., 2000. Optimizing administrative weights for efficient single-path routing. In Proceedings of Networks 2000, Toronto, Canada.
Ben-Ameur, W., Kerivin, H., 2005. Routing of uncertain demands. Optimization and Engineering 3, 283-313.
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, pp. 107-113.
Buriol, L.S., Resende, M.G.C., Ribeiro, C.C., Thorup, M., 2005. A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Networks 46, 1, 36-56.
Buriol, L.S., Resende, M.G.C., Thorup, M., 2008. Speeding up dynamic shortest-path algorithms. INFORMS Journal on Computing 20, 2, 191-204.
Cisco Systems Inc. 2000. Internetworking Technologies Handbook, (3rd edn), Cisco Press, Indianapolis, IN
Ericsson, M., Resende, M.G.C., Pardalos, P.M., 2002. A genetic algorithm for the weight setting problem in OSPF routing. Journal of Combinatorial Optimization 6, 299-333.
Fortz, B., Rexford, J., Thorup, M., 2002. Traffic engineering with traditional IP routing protocols. IEEE Communications Magazine 40, 10, 118-124.
Fortz, B., Thorup, M., 2000. Internet traffic engineering by optimizing OSPF weights. In Proceedings of the 19th IEEE Conference on Computer Communications (INFOCOM), Tel-Aviv, pp. 519-528.
Fortz, B., Thorup, M., 2002. Optimizing OSPF/IS-IS weights in a changing world. IEEE Journal on Selected Areas in Communications 20, 4, 756-767.
Fortz, B., Thorup, M., 2003. Robust optimization of OSPF/IS-IS weights. In Ben-Ameur, W., Petrowski, A. (eds) Proceedings of INOC 2003. Paris, pp. 225-230.
Fortz, B., Thorup, M., 2004. Increasing internet capacity using local search. Computational Optimization and Applications 29, 1, 13-48.
Fortz, B., Ü mit, H., 2010. Efficient techniques and tools for intra-domain traffic engineering. International Transactions in Operational Research forthcoming. DOI: 10.1111/j.1475-3995.2010.00769.x.
Holmberg, K., Yuan, D., 2000. A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Operations Research 48, 461-481.
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.F., Salvatori, E., Skivée, F., Tran, H.T., Uhlig, S., Ü mit, H., 2006. An open source traffic engineering toolbox. Computer Communications 29, 5, 593-610.
Moy, J., 1998. OSPF: Anatomy of an Internet Routing Protocol. Addison-Wesley, Reading, MA.
Mulyana, E., Killat, U., 2002. An alternative genetic algorithm to optimize OSPF weights. In 15th ITC Specialist Seminar, Wü rzburg, pp. 186-192.
Mulyana, E., Killat, U., 2005. Optimizing IP networks for uncertain demands using outbound traffic constraints. In Proceedings of INOC 2005. Lisbon, pp. 695-701.
Pióro, M., Medhi, D., 2004. Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufman, San Francisco, CA.
Ramalingam, G., Reps, T., 1996. An incremental algorithm for a generalization of the shortest-path problem. Journal of Algorithms 21, 2, 267-305.