Introduction
The routing protocol play a very important role in calculating, choosing and selecting the relevant path for transferring the data from the source to the destination efficiently. There are already many accepted routing algorithms used to find the shortest path and also to increase the throughput of the network.
In this paper, I will explain the algorithm for selecting the path of the data packets guided by the shortest path. The goal of every network routing algorithm is to direct traffic from source to the destination maximizing the network performance. The performance measure that is usually taken into account is the throughput (bits delivered per time unit) and number of packets successfully reaching the destination. However, in my implementation I have taken the performance measure as total sum of costs between edges. The optimal solution for choosing the best shortest path is to select the one with the smallest total cost.
This paper is divided into four sections. Section 1 gives an explanation of the network routing and the problem behind it. In section 2 there is a brief explanation of the ACO, section 3 deals with the implementation I have created and results performed and finally section 4 contains the conclusion and also some future scope of work as well as references used in this paper.
1. Network routing
Network routing is the process of selecting paths in a network along which to send network traffic. [1] Communication networks can be classified as either circuit-switched or packet-switched. The example of circuit switched network is the telephone network in which the physical circuit is set up at the communication start and remains the same for the communication duration. Unlike them, in packet-switched networks, also called data networks, each data packet can follow a different route and no fixed physical circuits are established. The example of data networks are LAN and the Internet. [2] In this paper I will focus on data networks.
The main function of data networks is to assure the efficient distribution of information among its users. This is done through the exploitation of the network control system. One of the most important components of control system is routing. Routing refers to the distributed activity of building and using routing tables.
Routing table is a common component of all routing algorithms. It is used to hold information to make the local forwarding decisions. One routing table is maintained by each node in the network. It tells the nodes incoming data packets which link to use next in order to continue its travel to the destination node of that data packet.
However, one of the main aspects of the network routing problem is that it is non-stationary. Meaning that, one of the routing characteristics is that the traffic over the network changes all the time. Additionally, the nodes and links of the network can suddenly go out of the service, and new nodes and links can be added at any moment. All these characteristics have to be considered in order to create an optimal solution to this problem. The problem of shortest path.
1.1 Shortest path routing
Shortest path routing is implementing shortest path algorithm on solving the network routing problem. It's objective is to determine the shortest path (minimum cost) between two nodes, where the sum of the costs of its constituent edges is minimized.
Till today, many routing algorithms used for solving shortest path have been accepted. One of them is Dijkstra's algorithm. Dijkstra's algorithm, conceived by Dutch computer scientist Edgar Dijkstra in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge costs, producing a shortest path tree. [3]
For a given source node in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that node and every other node. It can also be used for finding costs of shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been reached. For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path first is widely used in network routing protocols, most notably OSPF (Open Short Path First) and Intermediate system to Intermediate system (IS-IS). [3]
The Dijkstra's algorithm for solving the shortest path problem is presented on the following link.
As I have mentioned, network routing is of a variable nature and nodes and links of the network can suddenly break, as well as the new one can be created. Therefore we have OSPF, which is a dynamic routing protocol and it keeps track of the complete network topology and all the nodes and links within that network.
In addition to this, if for some time the best route converges within the network, and suddenly the link failure occurs, the OSPF will detect it very quickly in the topology and will converge on the new loop-free routing structure. So to conclude with this section, we now have convergence as one of the potential problems to solve in the following sections as well as in the implementation I prepared.
2. Ant Colonies
[5],[6],[7] Ant colony optimization (ACO) is an algorithm based on the behavior of the real ants in finding the shortest path from a source to the food. It utilizes the behavior of the real ants while searching for the food. It has been observed that the ants deposit a certain amount of pheromone in its path while traveling from its nest to the food. Again, while returning to the nest, ants follow the same path marked by the pheromone and again deposit the pheromone on its path. In this way the ants following the shorter path are expected to return earlier and hence increase the amount of pheromone deposit in its path at a faster rate than the ants following a longer path.
However, the pheromone is subjected to evaporation by a certain amount at a constant rate after a certain interval and therefore the paths visited by the ants frequently, are only kept as marked by the pheromone deposit, whereas the paths rarely visited by the ants are lost because of the lack of pheromone deposit on that path and as a result the new ants are intended to follow the frequently used paths only.
Now, all the ants starting their journey can learn from the information left by the previously visitor ants and are guided to follow the shorter path directed by the pheromone deposit. In ACO, a number of artificial ants (which mimic the data packets) build solutions to the considered optimization problem and exchange information on the quality of these solutions via a communication scheme that is pheromone deposit on the path of the journey performed.
2.1 ACO in Network routing problems
ACO algorithms can be applied in the network routing problems to find the shortest path. In a network routing problem, a set of artificial ants (packets) are simulated from a source to the destination. The forward ants are selecting the next node randomly for the first time taking the information from the routing table and the ants who are successful in reaching the destination are updating the pheromone deposit at the edges visited by them by an amount (C/L), where L is the total path length of the ant and C a constant value that is adjusted according to the experimental conditions to the optimum value. The next set of the ants can now learn from the pheromone deposit feedback left by the previously visited successful ants and will be guided to follow the shortest path. [2][7]
The probability that the ant will select a node j from node i is given by the following formula:
This is of course, if the link between two nodes exists, otherwise the Pij = 0. Here, τij is the pheromone of each edge which joins the nodes i and j. ηij = (1/dij), where dij is the distance between the nodes i and j. α and β are two parameters which determine the relative influence of the pheromone trail and the heuristic information.
The main characteristic of the ACO is that the pheromone values are updated by all the ants
(packets) which have reached the destination successfully. However, before adding the pheromone
we first must perform the evaporation action. Pheromone evaporation (ρ) on the edge between
node i and node j is implemented by the formula:
τij ← (1 - ρ)τij
So, every moment of time, t={1,2,3,4...n} represents one iteration in which all the ants in the colony
will perform one move towards the selected node. That is why, after we take that in the
consideration, all the ants will, after n iterations, find the solution and leave the pheromone
calculated by the following formula:
In addition, the amount of pheromone which some ant k, add to the edge which he has not passed is
0. Otherwise, if the ant k has passed through some edge between the nodes, he will left the amount
of pheromone which is inversely proportional with the total cost of all the edges ant k has passed
on its path from the starting node to the destination node. The following formula presents this
process:
Δτijk is the amount of pheromone ant k deposits on the edges visit. It is calculated by the following
expression:
Where Ck is the total cost of all the edges ant k has passed on its path from the starting to the
destination node. This will allow for the better ant to leave more pheromone on the edge which is
the route on the shortest path.
One more advantage of the application of the ACO in network routing is that when the number of
packets increases, this algorithm can be applied for controlling congestion also. In static routing
algorithm all the packets from a starting to the destination node will after some time follow a
constant path calculated by the algorithm and therefore we can have a problem with congestion. As
a result, some of the packets will have to wait. However, in ACO as the next node is select randomly,
with the probability to chose the shortest path more, some packets will some other paths which
increases the network performance and fights congestion.
In addition to this, in dynamic circumstances, if after some time the shortest path converges and
suddenly we get the link failure and disconnection between two nodes which are on the route of the
shortest path, the ACO will quickly follow some other path and converge on it.
3. Implementation of ACO algorithm
After explaining the basic processes and terms regarding the network routing and ACO as well as their possible interconnection, in this section I will explain the implementation of the ACO algorithm for solving the shortest path in the network routing which I have created. The implementation follows the same algorithm organization as the ACO and before I explain it, I will give some more details regarding the environment and structure of the implementation I created.
The implementation is the program which I have coded as a console application in C# programming language. The programming environment is on 3.5 .NET platform in Visual Studio 2010. In order to present it as more similar as possible to the basic ACO, I have used a object oriented approach. The result of this is that in the end I finished with the two main classes: Ant and Edge. In the following section, the UML class diagram(Figure 3.1) is presented and explained.
The Ant class represents the ants in ACO as well as the data packets in the network routing problem. In order for the ant to successfully pass through the network graph, it has to have these basic properties like: antID(AID), CurrentNode(Node in which ant is located) and Name(string representation of the ant for better tracking). Besides that, in order for the ant to update passed route with the pheromone amount, it has to have a stack (LIFO) on which it will add the links, in this case edges, which it has passed. The stack used here is a generic stack which adds object instances of class Edge in itself. The stack is represented as field: path. For more process regarding the stack, Ant class contains various methods in order to satisfy the implementation of the ACO algorithm.
The Edge class represents the graph in ACO as well as the network routing table in the network routing problem. In order for the ant to move it has to have some kind of map, in this case it is a graph. The graphs which I have used for my testing purposes are all directed graphs. This graph, represented as routing table, is consisted of various number of edges, meaning it is presented as an array of class Edge object instances. Each Edge object has its properties. Some of them are important for ant stacks and some of them for creation of the graph. Those properties are: EdgeID, FirstNode(Vertex aka Node from which to start), SecondNode(Node in which FirstNode can end), Pheromone(the amount of pheromone on edge between FirstNode and SecondNode) and Cost(weight of the edge between FirstNode and SecondNode). Besides this, Edge class has one method used in order to present them in visually nice way.
After explaining the classes Ant and Edge, I will now give a short insight in the Program class which is my main program. The Program class consists of various methods used to either display results and graphs or perform some small operations needed for the functioning of the ACO algorithm in the main method (Main). In the following section I will explain the Main function and the algorithm for solving the network routing problem in my implementation.
Before proceeding to the main algorithm, I have first developed a few graphs which will be used as test cases for the ACO algorithm in the main function. The test graphs are created as methods in the main program, those are: TestGraph_1, TestGraph_2, and TestGraph_3. The graph picture of TestGraph_1 is represented on the following picture as an example of graphs used in the implementation, while the remaining two will be shown in the latter stages of this paper.
The next thing which we need before starting the ACO algorithm are ants. As they represent the data packets in network routing, they are the main actors in this play. The initial ant population which I have created consists of five ants and are implemented by the method createAnts. It returns the array of ants, presented as an Ant Colony. The following code snippet gives an insight in ants characteristics.
public static Ant[] createAnts(Ant[] ant)
{
ant[0] = new Ant(1, "Yellow ant", 1);
ant[1] = new Ant(2, "Red Harvester", 1);
ant[2] = new Ant(3, "Fire ant", 1);
ant[3] = new Ant(4, "Native Brown ant", 1);
ant[4] = new Ant(5, "Kitchen ant", 1);
return ant;
}The last step before starting the ACO algorithm is to declare and setup some important settings needed for the algorithm to function properly. Those are:
- - EvaporationAmount (double) - is the amount of evaporation in each iteration of time t={1,2...n};
- - Tstart (int)- the starting time in the time loop (presented as: 1 unit of time = 1 iteration);
- - Tend (int)- the end time in time loop;
- - Tconverge (int) - the time unit in which the link failure occur on the converged edge;
- - Convergence_On (bool) - returns true if link failure occur in order for some procedures to run, otherwise is false which is also the initial setup;
- - random (int & double) - object instance of class Random, gives random values for probability selection of the edge in the graph;
Now, after creating the environment for the ACO to operate, I will explain the ACO algorithm used in my implementation as well as give a short insight through the pseudo code in the following figure.
nt Tstart;
int Tend;
int Tconverge;
bool Convergence_On ← false;
double EvaporationAmount;
while(Tstart < Tend)
{
If(Tstart = Tconverge)
{
displayResults(graph);
ConvNum ← ChangeAfterConvergence(graph, graph.StartNode, graph.EndNode);
SetAntsToStartNode(antColony);
}
Foreach(Ant a in antColony)
{
If(a.CurrentNode == graph.EndNode)
{
a.AddPheromone(graph);
a.CurrentNode ← graph.StartNode;
a.clearTheStack();
}
Else
{
a.ToString();
While(!Convergence_On)
{
edgeNum ← chooseEdge(graph, a.CurrentNode);
if(graph.edgeNum == ConvNum)
{continue;}
Else
{
a.pushToStack(graph.edgeNum);
a.CurrentNode = graph.SecondNode;
Convergence_On ← true;
}
}
Convergence_On ← false;
}
}
Evaporation(graph, EvaporationAmount);
Tstart++;
} After performing this pseudo code in its equivalent programming representation in C#, the compilation results are displayed in a console due to the methods in the Program class. Those methods are: displayResults() and TheBestRoute(). They are started after the ACO algorithm finishes its task in the time loop.
Example 1: TestGraph_1
In the following figure we have 8 nodes, where each node is connected with some other node with edges. Each edge has its cost on it. The starting node is node 1, while the end node is node 8. We have to find the shortest path between these nodes, having in mind that the shortest path is the one with the smallest total cost of all edges creating that path between them. As this is directed graph, we can move only from the left side to the right side.
Before compiling the program I will list some of the possible solutions to this problem. It will be the list with possible paths between start and end nodes as well as total costs of each path. The best path, which is the shortest one is marked with a green highlight.
Path -> Total Cost of path
- a) 1-2-5-8 -> 10
- b) 1-2-6-8 -> 10
- c) 1-2-7-8 -> 8
- d) 1-3-5-8 -> 8
- e) 1-3-6-8 -> 8
- f) 1-3-7-8 -> 6
- g) 1-4-5-8 -> 12
- h) 1-4-6-8 -> 9
- i) 1-4-7-8 -> 12
So, the optimal solution is: 1->3->7->8 with the total cost of: 6. After performing the 100 iterations in the program I have created on this graph, we get the results as on the screenshot of the compilation calculation:
The compilation after 100 iterations will display us the results of the ACO in this graph by displaying all the edges along with the amount of pheromone on them. After that, the best iteration calculated is the same one as the one which we have listed previously by hand calculation. The result is: 1->3->7->8 and the total weight of the shortest path is: 6.
Now, we will simulate the link failure which happens in the network routing and will delete the last edge in the best route in order to break up that converged route. We will perform another 100 iterations and will get the following results:
The best aka shortest path after breaking-up the convergence is now: 1->3->5->8 with the total cost of the path equal to 8. This is the correct result if we compare it to the list of results previously mentioned.
4. Conclusion
By implementing ACO algorithm in order to solve the network routing problem, I have concluded that this algorithm could be efficiently used in order to solve one of the network routing biggest problems which is finding the shortest path between start and end node. Even though this algorithm does not always find the shortest route, it definitely brings some more positive aspects to the problem itself as it minimizes the other problems which network routing has to fight with such as congestion, convergence break up, etc..
To conclude, the future work on ACO algorithm should be performed, however, more factors should be considered when applying in a network routing problem, such as: congestion control, delay factor, different types of network routes and directions.
References
[1] - Routing - [Online Article] - Accessed on: 03.06.2011. - Link: http://en.wikipedia.org/wiki/Routing
[2] - Marco Dorigo & Thomas Stutzle - "Ant Colony Optimization" - MIT press edition, year: 2004.
[3] - Dijkstra's algorithm - [Online Article] - Accessed on: 03.06.2011. - Link: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
[4] - Prim's algorithm - [Online article] - Accessed on: 02.06.2011. - Link: http://en.wikipedia.org/wiki/Prim's_algorithm
[5] - M. Dorigo, V. Maniezzo & A. Colorni, 1996. "Ant System: Optimization by a Colony of Cooperating Agents", IEEE
[6] - Mcgraw-Hill’s Advanced Topics in Computer Science Series, New Ideas in Optimization.
[7] - Dr. Samim Konjicija - Lecture slides - SSST University, Year: 2011
[8] - Gianni Di Caro - "Ant colony optimization and its application to Adaptive routing in telecommunication networks" - year: 2004.
History & Updates
For more graphs, examples, source code and detailed info about this subject, please do reffer to my personal webpage.
