AntNet Algorithm for NS-2

STANFORD “ANTNET”: LE FORMICHE LAVORANO COME INTERNET

2012-08-30T07:28:00.000-07:00

"Apparentemente le formiche e Internet non hanno molto in comune, tuttavia due ricercatori di Stanford hanno scoperto che invece il sistema usato dalle formiche per raccogliere il cibo è concettualmente uguale agli algoritmi usati per il funzionamento di Internet.

Deborah Gordon, docente di Biologia dell’università, studia le formiche da oltre 20 anni e per capire in che modo le formiche determinano quante formiche servono per trasferire una fonte di cibo, ha contattato Balaji Prabhakar, docente di informatica ed esperto nel trasferimento dei dati.

Grazie a questa singolare collaborazione, è stato possibile determinare la somiglianza tra il sistema adoperato dalle formiche e il protocollo TCP (Transmission Control Protocol), ovvero quella serie di regole che determinano come devono essere trasferiti i dati su Internet...

Continua a leggere questa notizia su pianetatech.it. "

Online AntNet Simulator

2012-08-02T17:53:00.001-07:00

http://w3.ualg.pt/~pcardoso/antnet_simulator/main.html

Examples of the algorithm Reviewed AntNet: Data Structures

2012-08-02T16:50:00.002-07:00

Routing Table
For any one destination d, and for each neighbor node n, is likely Pnd, which represents the "trend" to choose the node n as part of the path to the destination d.
Local Traffic Statistics
Contains information about the distribution of traffic across the network.

AntNet: Description of the algorithm
At each time interval t, at each node n is created an ant (Forward Ant), with a pseudo-random target (dependent on traffic patterns).
The goal of each ant is to find a path from origin to destination, and let each node visited, useful information for future ants. Each Forward Ant saves in its memory, which we visited and the time spent between each one.

Artificial ants (AntNet)

2012-08-02T16:49:00.004-07:00

AntNet is an algorithm to adapt the best effort routing in IP networks.
AntNet's design is based on ant colony optimization (ACO), which explores the mechanisms behind the behavior of ants, using the shortest way to define a meta-heuristic inspired by nature for combinatorial optimization.
The ACO is characterized by a multi-agent using estigmergia communication between agents (distributed transactions), using a stochastic policy decision to build solutions, estigmergia learning the parameters of the policy decision. It has been successfully applied to a variety of combinatorial problems. AntNet was the first algorithm
ACO for routing in packet-switched networks. This work is based on the work of Dr. Gianni Di Caro in AntNet, under the supervision of Prof. Marco Dorigo.
AntNet, as well as most other algorithms based on ACO, displays a series of interesting properties: it works in a fully distributed, it is highly adaptable to changing network and traffic, uses lightweight mobile agents (called ants) for sampling path assets, is robust to failures of the agent, has several routing paths, and automatically takes care of loading data from spreading.

The performance of AntNet has been extensively tested in simulations, considering the different networks and traffic patterns, and compared to various routing algorithms (state-of-the-art). In the vast majority of situations, AntNet far surpassed all its competitors, showing excellent adaptability and robustness. AntNet has also been tested in small physical networks, confirming the good results and performance in real world tests.

Real ants

2012-08-02T16:49:00.002-07:00

The behavior in search of food in many societies of ants is based on indirect communication based on pheromones.
While walking from the nest to food sources and vice versa, ants leave a chemical trail (pheromone) forming a trail for other ants.

Metrics and goals of the routing

2012-08-02T16:45:00.002-07:00

The metrics can be defined as delay in the delivery of packets (seconds), service quality, speed at which packets are sent (bits / second), the network resources used. Have the goals may be too much load, increase the amount of packets sent on the same average delay, with low (decreasing the average delay of each packet).

ACO - Algorithm Routing in Networks

2012-08-02T16:44:00.002-07:00

The routing algorithm is distributed throughout the network, you must choose the best path to take the packages to your destination and avoid congestion. Most algorithms using data structures in the nodes (Routing Tables), these structures are both databases and local models of global state, the information such as store and update depends on the algorithm used.

Estigmergia

2012-08-02T16:43:00.002-07:00

Term introduced by the French zoologist Pierre-Paul Grasse in 1959.
Estigmergia: Greek stigma (mark, sign) + ergon (action, work), the term refers to the notion that an action of a particular agent ceases signals in the environment, and this signal can be perceived by other agents (usually the same species) in order to incite or determine its subsequent actions. In real ants, this signal (or communication) is made by deposition of pheromone in the environment.
The shortest paths emerge from the collective behavior through:
A choice location and probability of each ant on where to move, and most likely paths that have more pheromones.
An indirect way of communication (Estigmergia), when the ants leave a trail of pheromone, modify how the next ants shall go see the local terrain, influencing the choice of the next way forward ants.
When reading / writing the pheromone chemical signal in a local ants are communicating indirectly via the environment

ACO: Pseudo-code

2012-08-02T16:42:00.001-07:00

1: Initialize parameters
2: Initialize array heuristic
3: Initialize the pheromone matrix
4: while stopping conditions not satisfied do
5: to build solutions
6: Apply Local Search (optional)
7: Pheromone Update
8: end while
9: View best solution
10: Stop

Introduction ACO AntNet

2012-08-02T16:41:00.003-07:00

Currently, researchers around the world propose new methods to solve classical problems or complex, so simple and / or efficient.
A simple proof of this are the new optimization techniques based on swarm intelligence, where through cooperation between individuals, directly or indirectly, can be a better adaptation of the environment.
An example of a swarm intelligence technique is the ant colony optimization (ACO), inspired by the behavior of agents (artificial ants) in search of alimento.A ant colony optimization, originally described by Dorigo (1992), has idea primarily as indirect communication among its subjects, through the path made by each ant during the exploration of the search space. This track is made using a kind of artificial pheromone, which acts as an attraction for them, serving as information perceived by the ants which is modified to reflect your current search experience.

The motivation of this work is to implement and evaluate the feasibility of a new target for heuristic called Ant Colony Optimization (ACO - Ant Colony Optimization), in solving routing problem in IP networks. Inspired by the behavior of some species of ants the analogy of the problem is that the ants would seek the best path with lower cost and time (effort) for moths acceptable computational routes.

The whole context was simulated by me using the NS-2 algorithm with AntNet integrated three topologies were adopted, 3x4 mesh networks, ring topology using three nodes and an arbitrary topology using 12 nodes

ACO

2012-08-02T16:40:00.002-07:00

I present this site, a stochastic meta-heuristic inspired by nature, based on Ant Colony Optimization for (ACO), originally formulated for combinatorial optimization problems, and a Genetic Algorithm (AntNet) to solve the problem of routing in IP networks. Solving the problem of routing in IP networks is complex because it involves a search in a huge search space that grows as the number of nodes, making it impractical to use exact methods. The proposed algorithm is Antnet to obtain good results, so as to circumvent the question of the complexity of the problem.
The ant colony optimization (ACO) is a new meta-heuristic that mimics the behavior of a population of agents (ants) in search of food. Through the use of cooperation mechanisms and adaptation, this technique emulates nature so as to obtain promising solutions with simple ideas.
With this, the ACO is proving to be a competitive approach in relation to other strategies presented in the literature. Regarding the application of this technique, the same can be applied in a wide range of problems, being among the best known, for example, the problem of vehicle routing, restoration of electrical power systems, routing in IP networks.

Antnet abstract

2012-08-02T15:31:00.002-07:00

AntNet

AntNet is an algorithm for adaptive best-effort routing in IP networks. AntNet’s design is based on the Ant Colony Optimization (ACO) framework, which exploits the mechanisms behind the shortest path behavior observed in ant colonies to define a Nature-inspired metaheuristic for combinatorial optimization. ACO features a multi-agent organization, stigmergic communication among the agents, distributed operations, use of a stochastic decision policy to construct solutions, stigmergic learning of the parameters of the decision policy, and so on. It has been applied with success to a large variety of combinatorial problems. AntNet has been the first ACO algorithm for routing in packet-switched networks. My first work on AntNet dates back to 1997. AntNet, as well as most of the other ACO routing algorithms designed after AntNet, exhibits a number of interesting properties: it works in a fully distributed way, is highly adaptive to network and traffic changes, uses lightweight mobile agents (called ants) for active path sampling, is robust to agent failures, provides multipath routing, and automatically takes care of data load spreading. AntNet’s performance has been extensively tested, considering different networks and traffic patterns, and compared to several state-of-the-art routing algorithms. In the great majority of the considered situations, AntNet has largely outperformed all its competitors, showing excellent adaptivity and robustness.

More information

Download AntNet

2012-08-02T15:30:00.003-07:00

Download the Antnet Algorithm

https://github.com/richardsonlima/antnet/downloads

AntNet Algorithm on Google+

2012-08-02T15:29:00.000-07:00

AntNet is an algorithm for adaptive best-effort routing in IP networks.

https://plus.google.com/b/108902716282114833896/108902716282114833896/posts

Gianni Di Caro publication about AntNet implementation for NS-2

2012-08-02T15:26:00.004-07:00

Gianni Di Caro ,senior researcher at Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA), in Lugano, Switzerland says [ Software implementations of AntNet ] "Lavina Jain made an implementation of AntNet for NS-2 (that can be also downloaded here). Starting from Jain's code, Richardson Lima has released a revised and updated version of AntNet for NS-2.33. Since I'm not an NS-2 user, I haven't checked these implementations, but I guess the Lima's implementation can be used as a good starting point. If you plan to use Lima's code, please feel free to contact me to check/improve the quality of the implementation."

AntNet Algorithm Source Code on github

2012-08-02T15:24:00.003-07:00

https://github.com/richardsonlima/antnet

AntNet Algorithm for The Network Simulator - ns-2 (www.isi.edu/nsnam/ns/)

AntNet Algorithm - Ant-based routing in networks

Antnet for NS2.34 Antnet implementation for ns2.34 based on the version for ns2.33 by Richardson Lima description available athttp://antnetalgorithm.blogspot.com.br and http://antnet.wordpress.com

Matthew Orlinski at orlinskm@cs.man.ac.uk and Richardson Lima at richardsonlimasurfjiujitsu@gmail.com with suggestions/improvements

REMEMBER, YOU NEED GCC4.0 TO INSTALL NS2.34 * *********************************************** WARNING If you have made any alterations to your NS2.34 (e.g. installing newer protocols), installing with the below instructions MAY overright your changes. If you have made alterations and you still want to use this protocol. The changelog below should be helpful to you in getting Antnet into ns2.34 without destroying your additions.

Instructions copy the files provided into NS2.34 directory as is.

Run: ./configure make

Finally, enjoy

Change log for none destructive install Additions we're made to ns2.34 to get antnet to work. The below is a guide only to be used in troubleshooting and ARE NOT COMPLETE INSTRUCTIONS. Not all changes are documented below but with these and following the clear advice on http://elmurod.net/wps/?p=157 on how to add a new routing protocol (TIP: Follow the instructions on the site substituting his protocol name "wfrp" for "antnet" and then make the changes below. This should get you antnet compiled and working)

// =========================== // queue/drop-tail.h // =========================== [Code]

public: int getlength();

[/Code] Added to the DropTail class

// =========================== // queue/drop-tail.cc // =========================== [Code]

int DropTail::getlength() { return q_->length(); } [/Code] add this method to queue/drop-tail.cc

// =========================== // queue/priqueue.cc // =========================== [Code]

case PT_ANT: if (ch->direction() == hdr_cmn::UP) { recvHighPriority(p, h); } else { Queue::recv(p, h); } break; [/Code] Added to queue/priqueue.cc instead

// =========================== // common/packet.h // =========================== [Code]

name_[PT_ANT] = "Ant"; [/Code] Basically anywhere that the WFRP tutorial (The website above) tells you to put PT_WFRP, put PT_ANT instead

// =========================== // trace/cmu-trace.cc // =========================== [Code]

include

[/Code] Remember to include this in cmu-trace.cc

[Code]

void CMUTrace::format_antnet(Packet *p, int offset) { struct hdr_ant_pkt *ah = HDR_ANT_PKT(p);

if (pt_->tagged()) {
sprintf(pt_->buffer() + offset,
    "-ant:o %d -ant:s %d -ant:l %d ",
    ah->pkt_src(), ah->pkt_seq_num(), ah->pkt_len());
}
else if (newtrace_) {
sprintf(pt_->buffer() + offset,
    "-P ant -Po %d -Ps %d -Pl %d ",
    ah->pkt_src(), ah->pkt_seq_num(), ah->pkt_len());
}
else {
sprintf(pt_->buffer() + offset,
    "[ant %d %d %d] ",
    ah->pkt_src(), ah->pkt_seq_num(), ah->pkt_len());
}

} [/Code] The trace format function in cmu-trace.cc is the above taken from the ns2.33 version by Richardson Lima

[Code]

case PT_ANT: format_antnet(p, offset); break; [/Code] Add this to the function CMUTrace::format(.....

// =========================== // tcl/lib/ns-default.tcl // =========================== [Code]

Defaults for Antnet

Agent/Antnet set numnodes_x 4 Agent/Antnet set numnodes_y 4 Agent/Antnet set numnodes 16 Agent/Antnet set rfactor 0.001 Agent/Antnet set timerant 0.03 [/Code] Add this at the end

// =========================== // tcl/lib/ns-default.tcl // =========================== [Code]

Simulator instproc get-drop-queue { n1 n2 } { $self instvar link_ set q [$link_($n1:$n2) queue] return $q } [/Code] Add this code to tcl/lib/ns-lib.tcl

AntNet Algorithm on ENSC427: COMMUNICATION NETWORKS SPRING 2011

2012-08-02T15:21:00.002-07:00

"One of the implementations for routing in MANET is Antnet, first developed by Lavina Jain and later updated by Richardson Lima[1]. Inspired by the foraging behaviour of ants when they search for food and the swarm intelligence to the optimized path between a food source and colony, each node in a MANET stores routing information for the neighbouring nodes and their usage as pheromone values and routes incoming packets to the path with the highest pheromone value. However, during initialization and route discovery phase, all the pheromone values are set equal and nodes route incoming packets randomly until the pheromone value converges to the optimum values. " http://www.sfu.ca/~ela6/ProjectReport.pdf