Project Algorithms

Back Home Next

 

Main Routing Algorithm

 

The basic principle behind the routing algorithm for this project is to get a simple and basic routing algorithm and modify it to introduce the most basic concepts of swarm intelligence into it to improve its performance, robustness and speed.  The algorithm will be programmed and simulated with a simple built in example.  The final part of the project includes the construction of an Ant agent proposal for the more advanced NS2 network simulator.

The algorithm modified with the basic concepts of swarm intelligence was the OSPF (open shortest path first) algorithm.  This algorithm is programmed entirely in C.  The OSPF algorithm is an Interior Gateway Routing Protocol.  This algorithm is based on Dijkstra's shortest path first routing algorithm.  Initially the algorithm was constructed and divided into two subparts:

Direct Route Computation.
Indirect Routing. 

 

In the direct route computation, the "node" to "node" connections are established right after the network is constructed and configured. Following this, the indirect routes are computed via a cost function and cost delay tables.  Once this is finished the network becomes operational.  

Normal static routing algorithm's only run once and the values and routes computed are fixed throughout the network.  If a link or connection becomes unavailable, static routing algorithms cannot do anything about it and loose packets.  Up till now the algorithm described above is completely static only a bit different because of the division of computational routes.  After this, the algorithm every x seconds restarts is computations and updates the tables, based on a cost matrix.  This matrix is updated via the "Ant" agents based on swarm intelligence described below.  

 

Ant Agent Proposal

The Ant agent will be based on the ECHO (ping) packet.  It will be randomly initialized throughout the nodes in the network and sent also with a random destination.

lLaunched from 25%à40% of nodes in network.

lModifies Cost Tables

lBased partially on ICMP /ECHO requests.

lImplemented in C routing algorithm.

lFuture C++/OTCL implementation for NS2 simulator.

 

The agent will modify the cost matrixes and routing tables in the nodes it visits (direct routes).  Once the agent has modified this routes, the next time that the routing algorithm runs (once every x seconds) it will compute the new indirect routes and update all the routing tables throughout the network.  

 

Sample Ant Agent Structure

 

Source Header Destination Header Next Node List Node List Timestamps
Create Ant At Source
Initialize Headers
Set Timestamp
Send Ant from Random Node
less than 40% of nodes
At intermediate nodes:
Check Previous node.
Get cost from matrix, if not in table update table according to timestamp.
Set new timestamp
Arrive and update destination.

 

Software

The source code for this project can be found here.  Please respect the author's intellectual work and the GNU public license.  This code can be used modified and applied for non commercial purposes only and with the proper citing of the author.  The source code for the algorithm is done in C and should be run in UNIX/LINUX environments, although it should compile in any platform with a C compiler.

 

 

Back to Top

 

 

Copyright 2001: Ivan A. Escobar Broitman
For problems or questions regarding this web contact ivan@escobarb.fsnet.co.uk
Last updated: August 19, 2001.