Abstract

With the advent of software- defined networks, network virtualization becomes a key technology to implement software-defined networks. Network virtualization requires a path computation element (PCE) to calculate virtual paths to connect virtual network nodes. The Dijkstra’s algorithm has been widely used in the PCE to calculate the shortest path between two virtual nodes. In this paper, we address that the Dijkstra’s algorithm cannot be applicable when a non-linear cost metric is used in the path cost evaluation. This paper proposes a new genetic algorithm (GA) to find the shortest path when a non-linear metric is used. The proposed GA generates the immigrants from ordinary chromosomes not from the elite chromosome for the genetic diversity. Also, the proposed GA does not use the sorting process to replace the worst chromosomes. The proposed GA uses the random replacing mechanism to decrease the path computation time. Using simulations, we showed that the proposed method is better than existing algorithms.

Keyword

PCE, Genetic algorithm, Shortest path, Virtual network.

Cite this article

Refference

[1][1]Fischer A, Botero JF, Beck MT, De Meer H, Hesselbach X. Virtual network embedding: a survey. IEEE Communications Surveys & Tutorials. 2013; 15(4):1888-906.

[2][2]Paolucci F, Cugini F, Giorgetti A, Sambo N, Castoldi P. A survey on the path computation element (PCE) architecture. IEEE Communications Surveys & Tutorials. 2013; 15(4):1819-41.

[3][3]Shahin AA. Memetic elitist pareto evolutionary algorithm for virtual network embedding. Computer and Information Science. 2015; 8(2):73-88.

[4][4]Zhang Z, Cheng X, Su S, Wang Y, Shuang K, Luo Y. A unified enhanced particle swarm optimization‐based virtual network embedding algorithm. International Journal of Communication Systems. 2013; 26(8):1054-73.

[5][5]Fajjari I, Saadi NA, Pujolle G, Zimmermann H. VNE-AC: virtual network embedding algorithm based on ant colony metaheuristic. In international conference on communications 2011 (pp. 1-6). IEEE.

[6][6]Gonen B. Genetic algorithm finding the shortest path in networks. Reno: University of Nevada. 2006.

[7][7]Ahn CW, Ramakrishna RS. A genetic algorithm for shortest path routing problem and the sizing of populations. IEEE Transactions on Evolutionary Computation. 2002; 6(6):566-79.

[8][8]Han MS. Optimal routing path calculation for SDN using genetic algorithm. International Journal of Hybrid Information Technology. 2018; 11(3): 7-12.

[9][9]Yang S. Genetic algorithms with elitism-based immigrants for changing optimization problems. In workshops on applications of evolutionary computation 2007 (pp. 627-36). Springer, Berlin, Heidelberg.

[10][10]Gladwin D, Stewart P, Stewart J. A controlled migration genetic algorithm operator for hardware-in-the-loop experimentation. Engineering Applications of Artificial Intelligence. 2011; 24(4):586-94.

[11][11]Cheng H, Yang S. Multi-population genetic algorithms with immigrants scheme for dynamic shortest path routing problems in mobile ad hoc networks. In European conference on the applications of evolutionary computation 2010 (pp. 562-71). Springer, Berlin, Heidelberg.

[12][12]Malis A, Wilson B, Clapp G, Shukla V. Requirements for very fast setup of GMPLS LSPs, RFC-7709; 2015:1-9.

[13][13]Farrel A, Ayyangar A, Vasseur J. Inter-domain MPLS and GMPLS traffic engineering, RFC-5151; 2008.

[14][14]Awduche D, Malcolm J, Agogbua J, ODell M, McManus J. Requirements for traffic engineering over MPLS, RFC-2702. 1999:1-29.

[15][15]Awduche D, Berger L, Gan D, Li T, Srinivasan V, Swallow G. RSVP-TE: extensions to RSVP for LSP tunnels. 2001.