Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2018 | OriginalPaper | Buchkapitel

38. Network Optimization

verfasst von: Luciana S. Buriol

Erschienen in: Handbook of Heuristics

Verlag: Springer International Publishing

share
TEILEN

Abstract

Several real-world problems can be modeled as graph problems. Graph algorithms and theories that have evolved for decades can be applied to solve the problem on hand. Interestingly, many of these graph problems can be solved polynomially, while small changes in a problem definition turn the problem difficult. In this chapter, we explore this path from polynomial network problems to NP-hard ones. Along the chapter, we visit several problems, dedicating more extended discussions to two real-world problems: the weight setting problem, originated from telecommunication networks, and the virtual network embedded problem, a recent stated optimization problem from the computer network area. For these two problems, we discuss their heuristic solution, since only small instances can be solved exactly within a reasonable amount of time.
Literatur
1.
Zurück zum Zitat Ahuja RK, Orlin JB, Magnanti TL (1993) Network flows: theory, algorithms, and applications. Prentice-Hall, Upper Saddle River Ahuja RK, Orlin JB, Magnanti TL (1993) Network flows: theory, algorithms, and applications. Prentice-Hall, Upper Saddle River
2.
Zurück zum Zitat Alkmim G, Batista D, da Fonseca N (2013) Mapping virtual networks onto substrate networks. J Internet Serv Appl 4:1–15 Alkmim G, Batista D, da Fonseca N (2013) Mapping virtual networks onto substrate networks. J Internet Serv Appl 4:1–15
3.
Zurück zum Zitat Bays L, Oliveira R, Buriol L, Barcellos M, Gaspary L (2012) Security-aware optimal resource allocation for virtual network embedding. In: Network and service management (CNSM), pp 378–384 Bays L, Oliveira R, Buriol L, Barcellos M, Gaspary L (2012) Security-aware optimal resource allocation for virtual network embedding. In: Network and service management (CNSM), pp 378–384
4.
Zurück zum Zitat Bays L, Oliveira R, Buriol L, Barcellos M, Gaspary L (2014) A heuristic-based algorithm for privacy-oriented virtual network embedding. In: 14th IEEE/IFIP network operations and management symposium (NOMS 2014), pp 1–8 Bays L, Oliveira R, Buriol L, Barcellos M, Gaspary L (2014) A heuristic-based algorithm for privacy-oriented virtual network embedding. In: 14th IEEE/IFIP network operations and management symposium (NOMS 2014), pp 1–8
5.
Zurück zum Zitat Bley A (2011) An integer programming algorithm for routing optimization in ip networks. Algorithmica 60(1):21–45 Bley A (2011) An integer programming algorithm for routing optimization in ip networks. Algorithmica 60(1):21–45
6.
Zurück zum Zitat Botero J, Hesselbach X, Duelli M, Schlosser D, Fischer A, de Meer H (2012) Energy efficient virtual network embedding. IEEE Commun Lett 16(5):756–759 Botero J, Hesselbach X, Duelli M, Schlosser D, Fischer A, de Meer H (2012) Energy efficient virtual network embedding. IEEE Commun Lett 16(5):756–759
7.
Zurück zum Zitat Broström P, Holmberg K (2006) Multiobjective design of survivable IP networks. Ann Oper Res 147:235–253 Broström P, Holmberg K (2006) Multiobjective design of survivable IP networks. Ann Oper Res 147:235–253
8.
Zurück zum Zitat 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:36–56 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:36–56
9.
Zurück zum Zitat 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 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
10.
Zurück zum Zitat Buriol L, Resende M, Thorup M (2007) Survivable IP network desing with OSPF routing. Networks 49(1):51–64 Buriol L, Resende M, Thorup M (2007) Survivable IP network desing with OSPF routing. Networks 49(1):51–64
11.
Zurück zum Zitat Buriol L, Resende M, Thorup M (2008) Speeding up dynamic shortest-path algorithms. INFORMS J Comput 20:191–204 Buriol L, Resende M, Thorup M (2008) Speeding up dynamic shortest-path algorithms. INFORMS J Comput 20:191–204
12.
Zurück zum Zitat Cao W, Wang H, Liu L (2014) An ant colony optimization algorithm for virtual network embedding. In: Algorithms and architectures for parallel processing. Lecture notes in computer science, vol 8630, pp 299–309 Cao W, Wang H, Liu L (2014) An ant colony optimization algorithm for virtual network embedding. In: Algorithms and architectures for parallel processing. Lecture notes in computer science, vol 8630, pp 299–309
13.
Zurück zum Zitat Chowdhury N, Boutaba R (2010) A survey of network virtualization. Comput Netw 54(5):862–876 Chowdhury N, Boutaba R (2010) A survey of network virtualization. Comput Netw 54(5):862–876
14.
Zurück zum Zitat Chowdhury NMMK, Rahman MR, Boutaba R (2009) Virtual network embedding with coordinated node and link mapping. In: INFOCOM. IEEE, pp 783–791 Chowdhury NMMK, Rahman MR, Boutaba R (2009) Virtual network embedding with coordinated node and link mapping. In: INFOCOM. IEEE, pp 783–791
15.
Zurück zum Zitat Chowdhury M, Rahman M, Boutaba R (2012) ViNEYard: virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Trans Netw 20(1):206–219 Chowdhury M, Rahman M, Boutaba R (2012) ViNEYard: virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Trans Netw 20(1):206–219
16.
Zurück zum Zitat Ericsson M, Resende M, Pardalos P (2002) A genetic algorithm for the weight setting problem in OSPF routing. J Comb Optim 6:299–333 Ericsson M, Resende M, Pardalos P (2002) A genetic algorithm for the weight setting problem in OSPF routing. J Comb Optim 6:299–333
17.
Zurück zum Zitat Even S, Itai A, Shamir A (1976) On the complexity of timetable and multicommodity flow problems. SIAM J Comput 5:691–703 Even S, Itai A, Shamir A (1976) On the complexity of timetable and multicommodity flow problems. SIAM J Comput 5:691–703
18.
Zurück zum Zitat Fajjari I, Aitsaadi N, Pujolle G, Zimmermann H (2011) Vne-ac: virtual network embedding algorithm based on ant colony metaheuristic. In: IEEE international conference on communications (ICC), pp 1–6 Fajjari I, Aitsaadi N, Pujolle G, Zimmermann H (2011) Vne-ac: virtual network embedding algorithm based on ant colony metaheuristic. In: IEEE international conference on communications (ICC), pp 1–6
19.
Zurück zum Zitat Feamster N, Gao L, Rexford J (2007) How to lease the internet in your spare time. SIGCOMM Comput Commun Rev 37(1):61–64 Feamster N, Gao L, Rexford J (2007) How to lease the internet in your spare time. SIGCOMM Comput Commun Rev 37(1):61–64
20.
Zurück zum Zitat Fortz B, Thorup M (2000) Internet traffic engineering by optimizing OSPF weights. In: INFOCOM, pp 519–528 Fortz B, Thorup M (2000) Internet traffic engineering by optimizing OSPF weights. In: INFOCOM, pp 519–528
21.
Zurück zum Zitat Fortz B, Thorup M (2004) Increasing internet capacity using local search. Comput Optim Appl 29(1):13–48 Fortz B, Thorup M (2004) Increasing internet capacity using local search. Comput Optim Appl 29(1):13–48
22.
Zurück zum Zitat Goldberg A, Tarjan R (1988) A new approach to the maximum-flow problem. J ACM 35:921–940 Goldberg A, Tarjan R (1988) A new approach to the maximum-flow problem. J ACM 35:921–940
23.
Zurück zum Zitat Goldberg A, Kaplan H, Werneck R (2007) Better landmarks within reach. In: Workshop on experimental algorithms, pp 38–51 Goldberg A, Kaplan H, Werneck R (2007) Better landmarks within reach. In: Workshop on experimental algorithms, pp 38–51
24.
Zurück zum Zitat Guerzoni R, Trivisonno R, Vaishnavi I, Despotovic Z, Hecker A, Beker S, Soldani D (2014) A novel approach to virtual networks embedding for SDN management and orchestration. In: Network operations and management symposium (NOMS 2014). IEEE, pp 1–7 Guerzoni R, Trivisonno R, Vaishnavi I, Despotovic Z, Hecker A, Beker S, Soldani D (2014) A novel approach to virtual networks embedding for SDN management and orchestration. In: Network operations and management symposium (NOMS 2014). IEEE, pp 1–7
25.
Zurück zum Zitat Hoffman A, Kruskal J (1956) Integral boundary points of convex polyhedra. Ann Math Stud 38:223–246 Hoffman A, Kruskal J (1956) Integral boundary points of convex polyhedra. Ann Math Stud 38:223–246
26.
Zurück zum Zitat Houidi I, Louati W, Ameur W, Zeghlache D (2011) Virtual network provisioning across multiple substrate networks. Comput Netw 55(4):1011–1023 Houidi I, Louati W, Ameur W, Zeghlache D (2011) Virtual network provisioning across multiple substrate networks. Comput Netw 55(4):1011–1023
27.
Zurück zum Zitat Inführ J, Raidl G (2011) Introducing the virtual network mapping problem with delay, routing and location constraints. In: Pahl J, Reiners T, VoßS (eds) Network optimization. Lecture notes in computer science, vol 6701. Springer, Berlin/Heidelberg, pp 105–117 Inführ J, Raidl G (2011) Introducing the virtual network mapping problem with delay, routing and location constraints. In: Pahl J, Reiners T, VoßS (eds) Network optimization. Lecture notes in computer science, vol 6701. Springer, Berlin/Heidelberg, pp 105–117
28.
Zurück zum Zitat Kleinberg J, Tardos E (2005) Algorithm design. Addison Wesley, Boston Kleinberg J, Tardos E (2005) Algorithm design. Addison Wesley, Boston
29.
Zurück zum Zitat Köhler E, Mühring R, Schilling H (2006) Fast point-to-point shortest path computations with arc-flags. In: 9th DIMACS implementation challenge Köhler E, Mühring R, Schilling H (2006) Fast point-to-point shortest path computations with arc-flags. In: 9th DIMACS implementation challenge
30.
Zurück zum Zitat Lauther U (2006) An experimental evaluation of point-to-point shortest path calculation on roadnetworks with precalculated edge-flags. In: 9th DIMACS implementation challenge Lauther U (2006) An experimental evaluation of point-to-point shortest path calculation on roadnetworks with precalculated edge-flags. In: 9th DIMACS implementation challenge
31.
Zurück zum Zitat Likhachev M, Ferguson D, Gordon G, Stentz A, Thrun S (2008) Anytime search in dynamic graphs. Artif Intell 172:1613–1643 Likhachev M, Ferguson D, Gordon G, Stentz A, Thrun S (2008) Anytime search in dynamic graphs. Artif Intell 172:1613–1643
32.
Zurück zum Zitat Moura L (2015) Branch & price for the virtual network embedding problem. Master’s thesis, Federal University of Rio Grande do Sul, Porto Alegre Moura L (2015) Branch & price for the virtual network embedding problem. Master’s thesis, Federal University of Rio Grande do Sul, Porto Alegre
34.
Zurück zum Zitat Orlin J (2013) Max flows in o(nm) time, or better. In: Proceedings of the forty-fifth annual ACM symposium on theory of computing, pp 765–774 Orlin J (2013) Max flows in o(nm) time, or better. In: Proceedings of the forty-fifth annual ACM symposium on theory of computing, pp 765–774
35.
Zurück zum Zitat Pioro M, Szentsi A, Harmatos J, Juttner A, Gajownicczek P, Kozdrowski S (2002) On open shortest path first related network optimization problems. Perform Eval 48(4):201–223 CrossRef Pioro M, Szentsi A, Harmatos J, Juttner A, Gajownicczek P, Kozdrowski S (2002) On open shortest path first related network optimization problems. Perform Eval 48(4):201–223 CrossRef
36.
Zurück zum Zitat Ramalingam G, Reps T (1996) An incremental algorithm for a generalization of the shortest-path problem. J Algorithms 21:267–305 MathSciNetCrossRef Ramalingam G, Reps T (1996) An incremental algorithm for a generalization of the shortest-path problem. J Algorithms 21:267–305 MathSciNetCrossRef
37.
Zurück zum Zitat Shamsi J, Brockmeyer M (2008) Efficient and dependable overlay networks. In: IEEE international symposium on parallel and distributed processing (IPDPS), pp 1–8 Shamsi J, Brockmeyer M (2008) Efficient and dependable overlay networks. In: IEEE international symposium on parallel and distributed processing (IPDPS), pp 1–8
38.
Zurück zum Zitat Stefanello F, Buriol L, Hirsch M, Pardalos P, Querido T, Resende M, Ritt M (2017) On the minimization of traffic congestion in road networks with tolls. Ann Oper Res 249:119–139 MathSciNetCrossRef Stefanello F, Buriol L, Hirsch M, Pardalos P, Querido T, Resende M, Ritt M (2017) On the minimization of traffic congestion in road networks with tolls. Ann Oper Res 249:119–139 MathSciNetCrossRef
Metadaten
Titel
Network Optimization
verfasst von
Luciana S. Buriol
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_46

Premium Partner