An Intelligent Network Routing Algorithm by a Genetic Algorithm

19 slides
9.33 MB

Similar Presentations

Presentation Transcript


An Intelligent Network Routing Algorithm by a Genetic AlgorithmMasaharu Munetomo, Yoshiaki Takai, and Yoshiharu Sato Hokkaido University, JAPAN.


In this paper, we propose…..An adaptive routing algorithm which employs genetic operators to realize an intelligent routing which directly observes communication latency of the routes. Path genetic operators for the routing algorithm which generates alternative routes based on the network topology.


Routing Algorithms in the InternetEach node forwards communication packets based on its Routing Table. Routing Algorithms generate routing tables based on network topology. Two major categories of routing algorithms Interior Gateway Protocols (IGP) Exterior Gateway Protocols (EGP)


Interior Gateway Protocol (IGP)Routing protocols inside an autonomous system (AS) such as a Local Area Network We have two major protocols for the IGPs commonly used in the Internet: Routing Information Protocols (RIP) Shortest Path First Protocols (SPF) or Open SPF (OSPF)


Exterior Gateway Protocol (EGP)Routing protocols outside an AS which exchanges routing information among AS’s. Recently, BGP (Border Gateway Protocols) become popular in the Internet. The BGP4 employs a source routing approach which determines all the nodes along a route in the source node instead deciding only its next hop.


Routing Information Protocol (RIP)A distributed algorithm Each node broadcasts its routing table. Each node recalculates distances in the routing table on receiving a routing table from its neighbors. Broadcast


Shortest Path First protocol (SPF)Each node broadcasts its link status. Each node stores network topology generated from the received link status information and calculates shortest paths by using the Dijkstra’s Shortest Path First Algorithm. The algorithm can reduce communication overhead by broadcasting only link status not all the routing tables.


Problems of the RIP and the SPFNot scalable: they increase their communication overhead in larger networks. Not efficient when they need to collect load status of links repeatedly to consider delay along a route to be minimized.Communication Overhead(n : # of nodes in the network)


Genetic-Based Routing (GBR)Employing source routing and only maintain a set of alternative routes frequently used in communication. Alternative routes are generated by Path Genetic Operators we propose. Observing communication latency for the limited number of routes to greatly reduce communication overhead for the routing.


Overview of the GBR


Path Genetic Algorithm (pGA)Encoding paths(routes) by listing up node ID’s, for example, (0 12 5 8 2 9). We have two path genetic operators: - Path Mutation - Path Crossover Selection is performed by deleting routes not frequently used in the routing table.


Path Mutation1. We select a node (nm) from the original route. 2. Another node (n’m) is selected from neighbor of nm. 3. Connecting source to n’m and n’m to destination.


Path Crossover--- Exchanges sub-routes among a pair of routes.


Fitness evaluation and SelectionEach node periodically sends delay query packets to observe communication latency along a route. Fitness value is calculated from the delay di : delay of route iSelection is invoked when routing table is overflowed.


Execution flow of the GBR1. When we need to send a packet, we select a route randomly according to fitness value of routes (roulette wheel selection). 2. After sending a specified number of routes, we send delay query packet to evaluate fitness. 3. After a specified number of delay query, we apply path genetic operators to generate alternative routes in the routing table. 4. If the number of routes exceeds a limit, we perform a selection by deleting routes with maximum delay.


Simulation ExperimentsUsing a network simulator written in C++. Sample network is taken from Japanese geographical info. Simulation time is 3000s. Genetic operators are invoked at every 30 evaluation of delay.


Mean arrival time of packets The GBR achieves much smaller mean arrival time of communication packets a than those of RIP, SPF and an adaptive SPF. An adaptive SPF which directly observes communication latency of links is not efficient in lightly-loaded networks.


Load status of LinksGBRSPFRIP Thickness of a link stands for its mean queue length. GBR achieves much less overhead of links, especially on the link 11 <=> 13 <=> 19.


ConclusionsPath Genetic Algorithm (pGA) we propose creates alternative routes in routing tables. A genetic based routing (GBR) algorithm can effectively forward communication packets, which leads to smaller arrival time. Load balancing among links is realized by the GBR algorithm.

Browse More Presentations

Last Updated: 8th March 2018

Recommended PPTs