Antnet is a software agent-based routing algorithm that is influenced by the unsophisticated and individual ant’s emergent behaviour. The aim of this chapter is twofold, firstly to introduce improvements to the antnet routing algorithm and then to critically review the work that is done around antnet and reinforcement learning in routing applications. In this chapter a modified antnet algorithm for packet-based networks has been proposed, which offers improvement in the throughput and the average delay by detecting and dropping packets routed through the non-optimal routes. The effect of traffic fluctuations has been limited by applying boundaries to the reinforcement parameter. The round trip feedback information supplied by the software agents is reinforced by updated probability entries in the distance vector table. In addition, link usage information is also used to prevent stagnation problems. Also discussed is antnet with multiple ant colonies applied to packet switched networks. Simulation results show that the average delay experienced by data packets is reduced for evaporation for all cases when non-uniform traffic model traffic is used. However, there is no performance gain on the uniform traffic models. In addition, multiple ant colonies are applied to the packet switched networks, and results are compared with the other approaches. Results show that the throughput could be increased when compared to other schemes, but with no gain in the average packet delay time.
TopIntroduction
In today’s fast growing Internet traffic conditions changes and link failures occasionally occurs at some parts of the network in an unpredictable manner. Therefore, there is a need for an algorithm to manage traffic flows and deliver packets from the source to the destination in a realistic time period. The routing algorithm is the key element in networks performance and reliability, and can be seen as the “brain” of the network, which manages the traffic flow through the network. An ideal routing algorithm should be node and link independent, and be able to deliver packets to their destination with the minimum amount of delay, regardless of the network size and the traffic load. The only way to achieve this would be by employing intelligent and distributed routing algorithms. The routing algorithms currently in use lack intelligence, and need human assistance and interpretation in order to adapt themselves to failures and changes within the network. Routing is considered to be an NP-Hard optimization problem, therefore widely used optimisation problems have been applied in the literature: to name a few, Genetic Algorithms, Neural Networks, Simulated Annealing, Software Agents and the Reinforcement Learning.
In recent years, agent based systems and reinforcement learning have attracted researchers’ interest. This is because these methods do not need any supervision and are distributed in nature. Swarm intelligence particularly ant based systems (Dorigo et al., 2002), Q-learning (Boyan & Littman, 1994) methods and hybrid agent based Distance Vector algorithms (Amin & Mikler, 2004) have shown promising and encouraging results. The ant-based approach applied to the routing problem was first reported in (Schoonderwoerd, 1996), which itself was influenced by the work done in (Appleby & Steward, 1994) on the software agents used for control in telecommunication networks. An improved version of the algorithm in (Schoonderwoerd, 1996) was applied to the connection-oriented systems (Bonabeau et al., 1998). In (Subramanian et al., 1997) for the first time the ant based routing was applied to the packet based connection-less systems. In (Di Caro & Dorigo, 1997) the idea was applied to the application of mobile agents in adaptive routing, namely antnet, which is also used as the basis in this work. In real life scenario, ants deposit some kind of chemical substance called the pheromone to mark the path that they use to find food. Having found the food source ants choose the path with the most pheromones back to their colony, which is of course, is always the shortest path. Ants (nothing but software agents) in antnet are used to collect traffic information and to update the probabilistic distance vector routing table entries. Recently research has been focused on improving antnet’s performance. In (Park & Kim, 2007) performance analysis of the antnet were carried out and compared to the Open Shortest Path First (OSPF) routing algorithm. It is shown that in low traffic loads the antnet end-to-end packet delay is larger than OSPF whereas it is the opposite in heavy traffic loads. In (Strobbe et al., 2005) a simple network is implemented and compared to OSPF, where a self-tuning number of variables for the optimum performance is proposed.