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:
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.
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
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.
Copyright 2001: Ivan A. Escobar Broitman