Efficient Networks Communication Routing Using Swarm Intelligence

Published Online November 2012 in MECS DOI: 10.5815/ijitcs.2012.12.07

Communication routing in a network is a NP hard problem and evolutionary algorithms play an important role in solving routing problems. With advances in the communication technology and demands of bigger networks modern communication networks are continuously becoming more diverse (heterogeneous) systems. In such complex networking environments computing of resources is done over a number of different kinds of operating systems with different characteristics from one another using different protocols with different access technologies. The need for seamless interaction of numerous heterogeneous network components represents a formidable challenge especially for networks that have traditionally used centralized methods of network control. This is true for both packet-switched and virtual circuit networks and the Internet, which is becoming an ever more complex collection of a diversity of subnets.The need to incorporate wireless and possibly ad-hoc networks into the existing wire-link infrastructure, renders the requirement for efficient network routing even more demanding [1]. Routing algorithms currently being used faces numerous problems that have evolved with the evolution of our networking technologies. The following are factors which every routing algorithms need to follows

• (a)    Quality of service (QoS) parameter guarantee is an important performance measure of the communication routing networks. It is increasingly become more important with the development of computer networks. This is because, depending on the type of applications being used and the communication network, a user requires a guaranteed allocation of bandwidth, maximum delay, minimum hop-count, et cetera. The QoS Routing Problem consists in finding an optimal cost Path from a source to a destination subject to one or more constraints on the path. It is well known that this problem is NP-complete and several heuristics have been proposed for its solution [2] [3]

• (b)    Centralized algorithms have scalability problems i.e. with centralized, single points of failure networks are not only prone to suffer from catastrophic downtimes in case central components are out-of-order but are also limited in terms of the ways new components can be added to the existing infrastructure.

• (c)    Static algorithms have trouble keeping up-to-date with network changes and hence are unstable. Static routing assumes that the network conditions are independent of the time-variant. In addition, while calculating the shortest-path such algorithms do not assess network load over regular periods of time [4].

• (d)    Distributed algorithms often suffer from issues with time-synchronization. In addition, other algorithms that are little bit more obscure also suffer from instability. Current routing algorithms are not adequate to  tackle the increasing

complexity of such  networks   Centralized algorithms have scalability problems; static algorithms have trouble keeping up-to-date with network changes; and other distributed and dynamic algorithms have oscillations and stability problems [5]. Swarm intelligence routing techniques are geared towards providing an alternative approach to tackle issues with the traditional forms of communication networks. Swarm intelligence is the collective behavior from a group of social insects, namely ant, birds, etc., where the agents (ants) communicate in the system either directly or indirectly using a distributed problem solving approach. This approach supports an optimized routing design, avoids stagnation, and prevents centralization of the network nodes [6]. The agents used in Swarm Intelligence (SI) uses mobile network management agents. These agents (boids) are autonomous, proactive and reactive, and have capabilities to adopt, co-operate and move intelligently from one location to another within the communication network. One such biological adaptation known as ‘stigmergy’ is used in swarm intelligence to allow agent interaction and co-ordination. The principle philosophy behind this notion is that the trace left behind in the environment by an agent simulates the next action by the same or different agents. This paper is organized in following pattern. In

Unit 2 we have discussed the issues with currently used routing algorithms; in unit 3 we discussed the main principle behind swarm intelligence, in unit 4 we describes how swarm intelligence used in problem solving and its importance, in unit 5 we discussed the algorithms that uses swarm intelligence in its functioning. Finally we come to the conclusion part in unit 6 and unit 7 describes Future works.

• II.    Issues with Currently Implemented Routing Algorithms

As mentioned in the introduction part of paper routing algorithms can be classified into following types.

• A)    Static routing algorithms

• B)    Dynamic routing algorithms

• C)  Centralized routing algorithms

• D)  Distributed routing algorithms

Static Routing Algorithms: Static routing algorithms are only suitable for very small kinds of networks. Static routing manually sets up the optimal paths between source and destinations paths. Algorithms that use static routes are simple to design and work well in environments where network traffic is relatively predictable and where network design is relatively simple. Static routing is not really a routing protocol. The main issue with static routing is the process of manually entering routes into a device's routing table via a configuration file that is loaded when the routing device starts up. As an alternative, these routes can be entered by a network administrator who configures the routes manually. Since these manually configured routes don't change after they are configured (unless a human changes them) they are called 'static' routes. Static routing is also called non adaptive routing.

Dynamic Routing Algorithms: Dynamic routing protocols are supported by software applications running on the routing device (the router) which dynamically learn network destinations and how to get to them and also advertise those destinations to other routers. This advertisement function allows all the routers to learn about all the destination networks that exist and how to those networks. However dynamic routing solve many of the problems which occurs in static routing but still some issues are present in dynamic routing algorithms like, routers may need more CPU and RAM to hold routing tables and calculate dynamic routes and Dynamic routing protocols will introduce complexity to your network.

Centralized Routing Algorithms: Centralized routing model is a routing model in which routing is centrally carried out using a centralized database. In other words, the routing table is kept at a single “central” node, which should be consulted when other nodes need to make a routing decision. The major problem with centralized routing is if central node fails during communication the whole system gets shut down and networks performance degrades.

Fig. 1: Architecture of centralized routing

Distributed Routing Algorithms: In distributed routing model, each node keeps a separate routing table. The routing function is calculated in routers or nodes as packets travel across the network. Headers contain only destination address, used by routers to select output channel(s). Each router knows only its neighborhood, since the designer has encoded the whole topology distributively into individual routers. Distributed routing is especially favorable in symmetric or regular topologies, since all routers use the same routing algorithm. Routing algorithms can also be classified as minimal or non-minimal. Minimal routing allows packets to follow only minimal cost paths, while nonminimal routing allows more flexibility in choosing the path by utilizing other heuristics [7]. Minimal routing algorithms are further sub-divided into optimal routing and shortest-path routing algorithms. The former aims to optimize the mean flow of the entire-network while the goal of the latter is to find the minimum-cost path between two nodes.

• III.    Principles of Swarm Intelligence

  Swarm Intelligence (SI) is an innovative distributed intelligent paradigm for solving optimization problems that originally took its inspiration from the biological examples by swarming, flocking and herding phenomena in vertebrates [8]. The idea of swarm based intelligence was first introduced by Gerardo Beni and Jing Wang in 1989, in the context of cellular robotic systems. Swarm Intelligence appears in biological swarms of certain insect species. It gives rise to complex and often intelligent behavior through complex interaction of thousands of autonomous swarm members. Interaction is based on primitive instincts with no supervision. The end result is accomplishment of very complex forms of social behavior and fulfillment of a number of optimization and other tasks [9].The main principle behind the interactions between the members of the swarm is called 'stigmergy', or communication through the environment. The principle of stigmergy implies the interaction of simple agents through a common medium with no central control. This principle implies that querying individual agents tells one little or nothing about the emergent properties of the system. Consequently, simulation is often used to understand the emergent dynamics of stigmergic systems [10]. Stigmergic systems are typically stochastic in nature; individual actions being chosen probabilistically from a limited behavioral repertoire. Actions performed by individual agents change the nature of the environment; for example a volatile chemical called a pheromone is deposited. This chemical signal is sensed by other agents and results in modified probabilistic choice of future actions. An example to this kind of unsupervised behavior synchronizing techniques is the utilization of pheromones by ants. Pheromones are a very potent hormone sensed and utilized by ants to follow trails of other ants. Swarm intelligence boasts a number of advantages due to the use of mobile agents and stigmergy [11, 12,13] These advantageous are

• 1.    Scalability. Population of the agents can be adapted according to the network size. Scalability is also promoted by local and distributed agent interactions.

• 2.    Fault tolerance: Swarm intelligent processes do not rely on a centralized control mechanism. Therefore the loss of a few nodes or links does not result in

• 3.    Adaptation: Agents can change, die or reproduce, according to network changes.

• 4.    Speed: Changes in the network can be propagated very fast, in contrast with the Bellman-Ford algorithm [5].

• 5.    Modularity: Agents act independently of other network layers [13].

• 6.  Autonomy: Little or no human supervision is

• 7.   Parallelism: Agent’s operations  are inherently

catastrophic failure, but rather leads to graceful, scalable degradation.

required.

parallel. These properties make swarm intelligence very attractive for ad-hoc wireless networks. They also render swarm intelligence suitable for a variety of other applications, apart from routing, including robotics [14, 15, 16] and optimization.

Fig. 2: Route discovery form S to D

The use of swarm intelligence in telecommunication networks has also been researched, in the form of ant based routing. This was pioneered separately by dorigo et al. And hewlett packard in the mid-1990s, with a number of variations since. Airlines have also used antbased routing in assigning aircraft arrivals to airport gates. At Southwest Airlines software program uses swarm theory, or swarm intelligence -- the idea that a colony of ants works better than one alone. Each pilot acts like an ant searching for the best airport gate. "The pilot learns from his experience what's the best for him, and it turns out that that's the best solution for the airline.

Fig. 3: Ant normal behavior during movement

Fig. 4: when interrupt comes in the movement of ants

Fig. 5: Ants adaptive environment Nature

• IV.    Swarm Emergent Problem Solving

Emergent problem solving is a characteristic of swarm systems. Emergent problem Solving is a class of problem solving where the behavior of individual agents is not goal directed; i.e. by looking at the behavior of single agents little or no information on the problem being solved can be inferred. Swarm problem solving is a bottom-up approach to controlling and optimizing distributed systems. It is a mindset rather than a technology that is inspired by the behavior of social insects that has evolved over millions of years. Peterson suggests that swarms calculate faster and organize better. Swarm systems are characterized by simple agents interacting through the environment using signals that are spatially (and temporally) distributed. By simple we mean that the agents possess limited cognition and memory; sometimes no memory at all. Furthermore, the behavior of individual agents is characterized by a small number of rules. In this document we consider the complexity (or simplicity) of an agent to be a function of the number of rules that are required to explain its behavior. To create Swarm based systems following principles must be satisfied

• 1.    Agents are independent, they are autonomous.

• 2.    Agents should be small, with simple behaviors. They should be situated and capable of dealing

• 3.    Decentralized – do not rely on global information. This makes things a lot more reliable.

• 4.    Agents should be behaviorally diverse – typically stochastic.

• 5.    Allow information to leak out of the system; i.e. introduce disorder at some rate.

• 6.    Agents must share information – locally is preferable.

• 7.    Planning and execution occur concurrently – the system is reactive.

They are not simply functions as in the case of a conventional object oriented system.

with noise. In fact, noise is a desirable characteristic.

Fig. 6: Agent interacting with environment

The above figure summarizes the interactions between agent and environment. Agent state along with environment state drives agent dynamics i.e. agent action selection. Agent action selection changes environment state through the creation or modification of signals. Environment state is used as input to environment dynamics. The dynamics of the environment causes changes to occur in environment state. What is important in the above figure is that agent state is hidden – only the agent has access to it. Environment state is visible to the agent but has to be stored by the agent if it is to be reused at some later point in time when the agent has (presumably) moved to a different location.

• V.    Swarm Intelligence Routing Algorithms Examples

A) AntNet Algorithm: Ant Colony Optimization is a model in which multiple agents (ants) parallelly try to achieve a specific task by cooperating among themselves. A natural ant generates chemical substance and deposits on its way to the food source. Since an artificial ant (packet) cannot generate chemical substance, it is modeled to carry memory with it. While moving, the ant can change the pheromone trails (probabilistic value) associated with the problem. AntNet is an ACO algorithm proposed by Gianni Di Caro and Marco Dorigo for data communication networks. Routing is determined by agents implementing forward and backward network exploration. The philosophy behind this technique is that backward ants utilize information gained by forward ants on their trip from source to destination [10]. The forward ants are not responsible for routing updates; their sole purpose is to collect raw data about network conditions and report results to backward ants. It is this data that the backward ants use to update appropriate routing tables of respective nodes (colonies).Brief description of the AntNet is given below: A forward ant is launched, at regular intervals, towards a destination ‘d’ from source ‘s’ to find a feasible path from ‘s’ to ‘d’.

• 1.    At each node, each forward ant which is going towards destination d, selects the next node to move on.

• 2.    A cycle is detected when the forward reaches a node which is already present in its memory. If a cycle is detected the nodes which are forming a cycle are removed from the memory.

• 3.    When the forward ant reaches the destination node, the Ant agent generates a backward ant, transfers all of its memory to it and the forward ant is killed.

• 4.   The backward ant retraces the same path the

• 5.   The backward ant updates the routing table at

forward ant traversed but in the reverse direction.

every node in the path.

Table (1) shows an example of AntNet routing table.

Intermediate quantity in the processing of the raw trip time information, we need a measure that takes on small values when the trip time is short relative to the mean and vice-versa. This quantity, r'

Where T is the trip time, µ is average of T, and C is a scaling factor, usually set to 2. Except for the routing table, each node also possesses a table with records of the mean and variance of the trip time to every destination.

Table 1: Ant Routing Table

Next hop (B, C)

	B	C
E	0.15	0.85
F	0.75	0.25

Destination Nodes (E, F)

In this table we see E, F are the destination nodes and B, C are the next hop nodes. These entries in the routing table have probabilities associated with them. These probabilities serve a dual purpose: - (i) these allow backward agents to choose next hop to a destination, (ii) the data packets select the path with the highest probability for the next hop.

Fig. 7: (a) Forward ant movement (b) Backward ant movement

• B)    Ant Based Control Routing Algorithm: Ant based control (ABC) is another stigmergy based ant algorithm designed for telephone networks. It shares many similarities with AntNet, but also incorporates certain differences. The basic principle relies on mobile routing agents, which randomly explore the network and update the routing tables according to the current network state. The routing table, storing probabilities instead of pheromone concentrations, is exactly the same as in AntNet. Also probability balanced randomness of the ants’ path selection is employed to favor the detection of new routes. In ABC, the ants only traverse the network nodes probabilistically, while the telephone traffic follows the path of highest probability. The routing table of every node is the same as AntNet. The update philosophy of the routing table is slightly different though. There is only one class of ants, which is launched from the sources to various destinations at regular time intervals. The ants are eliminated once they reach their destination. Therefore, the probabilities of the routing tables are updated as the ant visits the nodes, based on the life of the ant at the time of the visit. One important difference applies to the use of the routing agents is; ABC only uses a single class of ants which are initiated at regular time intervals from every source to a randomly chosen destination. After arriving at a node they immediately update the routing table entries for their source node, meaning that the pheromone pointing to the previous node is increased. It is important to see that only the backward path is influenced and just packets traveling towards the ant’s source profit from that route update. The second difference Pertains to the calculation of the routing table update. The probabilities are reinforced by a simple formula without considering any goodness value. Therefore no local traffic statistics are required to be recorded at the nodes.

• C)    Multiple Round Trip Routing: Another interesting example of swarm intelligence applied to packet-switched networks is Multiple Round Trip routing [7]. As in AntNet, nodes launch forward ants in regular intervals. The basic version utilizes the cost measured by the forward ants to update the routing table entries.

The forward ant keeps track of the visited notes in a stack and of their associated cost. This cost can be the wait time and the transmission delay for each visited node n. The interesting improvement to this algorithm is based on Bellman’s principle of dynamic programming. Every node in the path of a source-destination pair s-d is considered a destination. The back-propagating agent will update the routing table of a visited node n not just for the destination, but also for the intermediate nodes. Hence the updates occur all at once.

AntNet and Multiple Trip Routing are two examples of the class of swarm intelligence algorithms that incorporate round-trip agents. In this type of algorithms, the forward ants act as investigators and the backward ants are the ones who update the routing tables. ABC is an algorithm that incorporates only forward agents, who perform the update as they travel through the network. In this type of algorithms updates are faster and more reliable, since there is no delay between the information gathering and the actual update [12].

• D)    GPS Ant Like Routing Protocols: In [16] the GPS ant like routing algorithm was introduced which makes use of location information for routing and employs ants only to accelerate the dissemination of routing information, or more precisely, the positions of nodes. All nodes have a routing table where known hosts are stored with their locations and a timestamp of this location. Nodes send out ants that carry the routing table. When a node receives an ant, it compares the

  timestamp of the entries in its routing table with that of the ant and updates the older with the newer entry. Thus, an ant leaving a node always carries the most updated routing table from the nodes’ point of view that has been already visited. Furthermore, a shortest path algorithm is applied to determine the best possible route to a destination. Unfortunately it has been pointed out by Jones et al (2001) remain vague how exactly this is achieved.

• E)    Ant Colony based Routing Protocols: The protocol is based on swarm intelligence and especially on the ant colony based meta-heuristic. The routing protocol consists of three phases. In the first one, route discovery phase, new paths are discovered. The creation of new routes requires the use of a FANT, which establishes the pheromone track to the source node, and a BANT, which establishes the track to the destination node. FANTs are broadcasted by the sender to all its neighbors. Each FANT has a unique sequence number to avoid duplicates. A node receiving a FANT for the first time creates a record (destination address, next hop, pheromone value) in its routing table. The node interprets the source address of the FANT as destination address, the address of the previous node as next hop, and computes the pheromone value depending on the number of hops the FANT needed to reach the node. Then the node relays the FANT to its neighbors. When the FANT reaches destination, it is processed in a special way. The destination node extracts the information and then destroys the FANT. A BANT is created and sent towards the source node. In that way, the path is established and data packets can be sent. In the second phase, called route maintenance routes are improved during communication. Data packets are used to maintain the path, so no overhead is introduced. Pheromone values are changing. When a node vi relays a data packet towards destination v0 to a neighbor node vj it increases the pheromone value of the entry. The same happens in the opposite direction. The evaporation process is simulated by regular decreasing of the pheromone values. The third one handles routing failures, especially due to node mobility, a common issue in MANETs. ARA recognizes a route failure through a missing acknowledgement. The links are deactivated by setting to 0 the pheromone value. Then the node searches for an alternative link. If a second path exists, it is used otherwise neighbors are informed of the new situation. ARA fulfils the requirements of distributed operation loop freeness, on-demand operation and sleep period operation (i.e. nodes are able to sleep when their amount of pheromone reaches a threshold). Moreover, routing entries and statistic information are local to each node; several paths are maintained to reach a certain destination and, in a node with sleep mode on, only packets destined to it are processed.

Other swarm intelligent based Protocols: Ad hoc networking with swarm intelligence (ANSI), described in [23] and [24], is a hybrid protocol similar to ZRP.

Proactive ants are periodically emitted to find and maintain paths in the vicinity of a node. Reactive forward and BANTs are used if a node needs to find a path to an unknown destination. The network is clustered into colonies of nodes in [25] to reduce the number of ants. Colony ants are used to find paths between colonies, whereas local ants are used within the colonies. In [26], AODV in [27] was extended by ants to reduce route discovery latency. A fixed number of ants forage continuously and randomly within the network. They keep a history of the recently visited nodes and are only used to disseminate this route information, thus increasing the node connectivity and reducing the amount of route discoveries. Similar to DSR has been described in [28] ants are flooded throughout the network in [29], when a node does not have a route to the destination to which it has to send a packet. The ant keeps track of the followed path. A BANT is created for each FANT arriving at the destination, which travels the reverse path of the corresponding FANT and marks the path with pheromones using information about the path quality collected by the FANT. Data packets are either routed probabilistically, or deterministically based on the highest probability of the next hop.

• VI.    Future Work

Ideas for extending swarm intelligence from routing in communication networks are abundant and are still an ongoing process. Future work in swarm intelligence also includes introducing ‘covert’ leaders in mobile swarm networks, who possess knowledge about the destination and sometimes about certain control functions. Calculating the most efficient number for a particular swarm is always a challenge for research teams. Further research in this sub-domain of swarm networks include mathematically analysis of the thresholds of moving speed (for both, mobile agents and leaders) and the leader percentage for the given configuration of robot swarms.

• VII.    Conclusion

In this paper, we have presented an overview of swarm intelligence applied to network routing Inherent properties of swarm intelligence include massive system scalability emergent behavior complex global intelligence emerging from simple, local interactions, autonomy and stigmergy. Fortunately these are the properties that are also highly desirable in computer networks. Swarm Intelligence proposes a new way of thinking the solution of the non-linear complex problems. Swarm intelligent based approaches hold great promise for solving numerous problems of ad-hoc power aware networks. Swarm intelligence however is a new field and much work remains to be done.