ACO algorithms for adaptive routing

This chapter introduces four novel algorithms for routing in telecommunication networks (AntNet, AntNet-FA, AntNet+SELA, and AntHocNet), a general framework for the design of routing algorithms (Ant Colony Routing), and reviews related work on ant-inspired routing algorithms. AntNet 119,125,121,122,118,115 and AntNet-FA 124 are two ACO algorithms for adaptive best-effort routing in wired datagram networks (extensive experimental results for these two algorithms are presented in the next...

Wired networks

Schoonderwoerd, Holland, Bruten and Rothkrantz (1996, 1997) 382, 381 were the firsts to consider routing as a possible application domain for algorithms inspired by the behavior of ant colonies. Their approach, called ABC, has been intended for routing in telephone networks, and differs from AntNet in many respects that are discussed here with some detail to acknowledge the impact of ABC during the first phase of AntNet's development. The major differences between the two algorithms are a...

Summary

In this chapter we have reported an extensive set of experimental results based on simulation about the performance of AntNet, AntNet-FA, and AntHocNet. Concerning AntNet and AntNet-FA, to which the majority of results refer to, in order to provide significance to our studies, we have investigated several different traffic patterns and levels of workload for six different types of networks both modeled on real-world instances and artificially designed. The performance of our algorithms have...

Ant NetSELA description of the algorithm

In AntNet+SELA the node managers make use of ant-like agents in order to proactively update their link-state database, take routing decision using fresh information about the candidate paths, and split and reroute the applications if useful necessary. In particular, node managers make use of two sets of active perceptions. The perceptions in one set behave exactly like AntNet-FA ants, and are aimed at proactively building and maintaining pheromone tables for the perceptions (ants) in the second...

Parameter values

All the implemented algorithms depend on their own set of parameters. For all the algorithms the size of their routing packets and the related elaboration time must be properly set. Settings for these specific parameters are shown in Table 8.1. Table 8.1 Characteristics of routing packets for the implemented algorithms, except for the Daemon algorithm, which does not generate routing packets. Nh is the incremental number of hops made by the forward ant, Nn is the number of neighbors of the...

Two additional examples of Ant Colony Routing algorithms

Both AntNet and AntNet-FA can be seen as instances of the more general ideas of the ACR framework. On the other hand, in both AntNet and AntNet-FA all the ants are generated according to the same fixed proactive scheme, have the same characteristics and behavior, and the notion of node manager has not been made explicit, such that there is little intelligence at the nodes. In a sense, AntNet and AntNet-FA results in a rather natural way from the general ACO's guidelines and from the adaptation...

Ant NetFA improving Ant Net using faster ants

In AntNet, forward ants make use of the same queues that are used by data packets. In this way they behave like data packets and experience the same traveling time that a data packet would experience. In this sense, forward ants faithfully simulate data packets. The problem with this approach is that, in case of congestion along the path that is being followed, it will take a significantly long time to the forward ant to reach its destination. This fact will have two major consequences the...

Data structures maintained at the nodes

Antnet Diagram

In any routing algorithm, the final quality of the routing policy critically depends on the characteristics of the information maintained at the network nodes. Figure 7.1 graphically summarizes the data structures used by AntNet at each node k, that are as follows Figure 7.1 Node data structures used the ant agents in AntNet for the case of a node with L neighbors and a network with N nodes. For simplicity the identifiers of the neighbors are supposed to be 1, 2, L. Both the ant-routing and...

Wireless and mobile ad hoc networks

Matsuo and Mori 2001 302 have proposed Accelerated Ants Routing, which is an extension to MANETs of the ideas of Subramanian et al. 411 . They add the rule that uniform ants do not return to an already visited node, and make these ants to hold the history about the n last visited nodes. In this way, routing information can be updated not only toward the source, but all the intermediate nodes. The algorithm heavily rely on the uniform ants, and no on-demand actions are taken. It has been...

Experimental settings and results for Ant HocNet

We report in this section some preliminary experimental results for AntHocNet. As simulation software we have used Qualnet 354 , a discrete-event packet-level simulator developed by Scalable Networks Inc. as a follow-up of GloMoSim, which was a shareware simulator designed at University of California, Los Angeles. Qualnet is specifically optimized to simulate large-scale MANETs, and comes with correct implementations of the most important protocols for all the network layers and for routing in...

Experimental results for ACO routing algorithms

This chapter is devoted to the presentation of extensive experimental results concerning AntNet, AntNet-FA, and AntHocNet. The majority of the results concern AntNet and AntNet-FA and refer to the case of best-effort routing in wired IP networks. As discussed in Subsection 7.1.1, failure events are not taken into account, the focus being on the study of traffic-adaptiveness and on the effective use of multiple paths. Some preliminary results concerning AntHocNet and routing mobile ad hoc...

Contents

1.1 Goals and scientific 1.1.1 General goals of the 1.1.2 Theoretical and practical relevance of the 1.1.3 General scientific 1.2 Organization and published sources of the 1.3 ACO in a nutshell a preliminary and informal 1 From real ant colonies to the Ant Colony Optimization metaheuristic 21 2 Ant colonies, the biological roots of Ant Colony Optimization 23 2.1 Ants colonies can find shortest paths 2.2 Shortest paths as the result of a synergy of ingredients 27 2.3 Robustness, adaptivity, and...