(Publisher of Peer Reviewed Open Access Journals)

International Journal of Advanced Computer Research (IJACR)

ISSN (Print):2249-7277    ISSN (Online):2277-7970
Volume-9 Issue-40 January-2019
Full-Text PDF
Paper Title : Optimal path calculation for virtual networks using genetic algorithm
Author Name : Man Soo Han
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.

Keywords : PCE, Genetic algorithm, Shortest path, Virtual network.
Cite this article : Han MS. Optimal path calculation for virtual networks using genetic algorithm. International Journal of Advanced Computer Research. 2019; 9 (40): 28-36. DOI:10.19101/IJACR.SOC20.
References :
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[3]Shahin AA. Memetic elitist pareto evolutionary algorithm for virtual network embedding. Computer and Information Science. 2015; 8(2):73-88.
[Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[6]Gonen B. Genetic algorithm finding the shortest path in networks. Reno: University of Nevada. 2006.
[Google Scholar]
[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.
[Crossref] [Google Scholar]
[8]Han MS. Optimal routing path calculation for SDN using genetic algorithm. International Journal of Hybrid Information Technology. 2018; 11(3): 7-12.
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[12]Malis A, Wilson B, Clapp G, Shukla V. Requirements for very fast setup of GMPLS LSPs, RFC-7709; 2015:1-9.
[Crossref] [Google Scholar]
[13]Farrel A, Ayyangar A, Vasseur J. Inter-domain MPLS and GMPLS traffic engineering, RFC-5151; 2008.
[Google Scholar]
[14]Awduche D, Malcolm J, Agogbua J, ODell M, McManus J. Requirements for traffic engineering over MPLS, RFC-2702. 1999:1-29.
[Crossref] [Google Scholar]
[15]Awduche D, Berger L, Gan D, Li T, Srinivasan V, Swallow G. RSVP-TE: extensions to RSVP for LSP tunnels. 2001.
[Crossref] [Google Scholar]