Artificial intelligence network load balancing using Ant Colony Optimisation

Note: Please Scroll Down to See the Download Link.

ABSTRACT:

Ants first evolved around 120 million years ago, take form in over 11,400 different species and are considered one of the most successful insects due to their highly organised colonies, sometimes consisting of millions of ants.

One particular notability of ants is their ability to create "ant streets". Long, bi-directional lanes of single file pathways in which they navigate landscapes in order to reach a destination in optimal time. These ever-changing networks are made possible by the use of pheromones which guide them using a shortest path mechanism. This technique allows an adaptive routing system which is updated should a more optimal path be found or an obstruction placed across an existing pathway.

Computer scientists began researching the behaviour of ants in the early 1990's to discover new routing algorithms. The result of these studies is Ant Colony Optimisation (ACO) and in the case of well implemented ACO techniques, optimal performance is comparative to existing top-performing routing algorithms.

This article details how ACO can be used to dynamically route traffic efficiently. An efficient routing algorithm will minimise the number of nodes that a call will need to connect to in order to be completed thus; minimising network load and increasing reliability. An implementation of ANTNet based on Marco Dorigo & Thomas stützle has been designed and through this a number of visually aided test were produced to compare the genetic algorithm to a non-generic algorithm. The report will final conclude with a summary of how the algorithm perform and how it could be further optimised.

Background

Electronic communication networks can be categorised as either circuit-switched or packet-switched. Circuit-switched networks rely on a dedicated connection from source to destination which is made once at start-up and remains constant until the tear-down of the connection. An example of a circuit switched network would be British Telecoms telephone network. Packet-switched networks work quite differently however and all data to be transmitted is divided into segments and sent as data-packet. Data-packets can arrive out of order in a packets-switched network with a variety of paths taken through different nodes in order to get to their destination. The internet and office local area networks are both good examples of packet-switched networks.

A number of techniques can be employed to optimise the flow of traffic around a network. Such techniques include flow and congestion control where nodes action packet acknowledgements from destination nodes to either ramp-up or decrease packet transmission speed. The area of interest in this report concentrates on the idea of network routing and routing tables. These tables hold information used by a routing algorithm to make a local forwarding decision for the packet on the next node it will visit in order to reach its final destination.

One of the issues with network routing (especially in very large networks such as the internet) is adaptability. Not only can traffic be unpredictably high but the structure of a network can change as old nodes are removed and new nodes added. This perhaps makes it almost impossible to find a combination of constant parameters to route a network optimally.

Routing algorithms

Packet-switched networks dynamically guide packets to their destination via routing tables stored in a link state and are selected via a link state algorithm.

The Link state algorithm works by giving every node in the network a connectivity graph of the network. This graph depicts which nodes are directly connected. Values are stored for connected nodes in map which represent the shortest path to other nodes. One such link state algorithm used in network routing is Dijkstras algorithm. When a path between two nodes is found, its weight is updated in the table. Should a shorter path be found the new optimal weight will be updated to the table replacing the old value.

The algorithm allows traffic to be routed around the network whilst connecting to the least number nodes as possible. The system works but doesn't take into account influx of traffic and load balancing.

Introducing ANTNet

By replacing Dijkstras algorithm with a generic algorithm, paths taken by calls could be scored by how short of a path they took, that way if they were queued on a busy network they would perform badly. Consequently other paths would score relative and be chosen. This would work in real time and allow the routing system to adapt as packets are transmitted ANTNet uses virtual pheromone tables much like when an ant follows a path dropping pheromones to re-enforce it. The quicker the ants move down a path the more throughput of ants thus; a greater concentration of pheromones. In the same way pheromone tables in ANTNet allow fast routes to score a higher chance of being selected whilst the less optimal route scores a low chance of being selected.

The idea behind ANTNet is when a call is placed an Ant will traverse across the network using a link-state deterministic algorithm. Every node holds a pheromone table for all other nodes of the network. Each pheromone table holds a list of table entries containing all the connected nodes of the current node. 

SOFTWARE SPECIFICATION:-

 OPERATING SYSTEM                      :  Windows XP Professional

 FRONT END                                      :  Microsoft Visual Studio .Net 2010

 CODING LANGUAGE                       :  C# .Net

HARDWARE SPECIFICATION:-

    SYSTEM                                             :   Pentium III 700 MHz

    HARD DISK                                       :   40 GB

    MONITOR                                           :   15 VGA colour monitor

    RAM                                                   :   256MB

Click here to download Artificial intelligence network load balancing using Ant Colony Optimisation source code