Communications of the ACM
Home/Magazine Archive/March 2006 (Vol. 49, No. 3)/Biologically Inspired Self-Adaptive Multi-Path Routing.../Full Text
Self-managed systems and services
Biologically Inspired Self-Adaptive Multi-Path Routing in Overlay Networks
Mechanisms found in biological systems are in general robust and adapt well to changes in the environment. Therefore, many techniques that mimic certain behaviors found in nature have been implemented in computer science. Some of these techniques (artificial neural networks, simulated annealing, or genetic algorithms) perform well as optimization techniques for certain problem types, especially in the presence of incomplete or fuzzy input data.
In order to foster research on new information technology based on biologically inspired approaches, a project entitled "New Information Technologies for Building a Networked Symbiosis Environment" was initiated in 2002 at Osaka University in Japan.1 Close interdisciplinary collaboration with researchers from the fields of information science, bioinformatics, and applied mathematics made it possible to find abstractions of behavioral models of various living organisms and apply them to new control methods for communication networks, especially for peer-to-peer (P2P) networks, mobile ad hoc networks (MANETs), and sensor networks.
Self-adaptiveness is an important issue in many fields of information technology, especially in telecommunications when we consider the interoperation of heterogeneous networks.
In nature, living organisms continuously face a fluctuating environment. Adaptation to such changing conditions is essential for their survival. However, due to the high dimensionality of the habitat, each environmental change rarely repeats itself during the lifetime of an individual organism. As a result, the development of adaptation rules is not always feasible because learning and evolutionary processes require multiple occurrences of events to which the organisms adapt. Pattern-based learning (commonly used in artificial neural networks, for instance) is only possible if there exist input patterns and a desired target value. When there are no input patterns available or no desired target value, the adaptation to new situations is performed in a more self-organized manner. For example, cells in a gene network can switch from one state to another depending on the availability of a nutrient [6]. These strategies are not necessarily optimal in terms of overall performance, but their main advantages lie in robustness and sustainability. This is very important for surviving in an unpredictable and fluctuating environment.
Self-adaptiveness is an important issue in many fields of information technology, especially in telecommunications when we consider the interoperation of heterogeneous networks. In this article, we propose to solve the problem of multi-path routing in overlay networks [3] by adapting the transmission of data packets to changes in the metrics of each path. The end-to-end route selection schemes typically employed in overlay routing are of a highly selfish nature, as they greedily choose paths that offer the highest performance, regardless of the implications on the performance and stability of the whole system. Several publications have investigated selfish routing using a game theoretical approach [9]. However, routing optimization is often performed with a global view of the network, using for example linear programming methods to find the best network configuration. In the solution proposed here, we only concentrate on the limited scope of information that a node can obtain from measurements of its links. As suggested by Seshadri and Katz [10], we improve the overall stability of the system by imposing some constraints on the degree of selfishness.
User-optimal or selfish routing achieves Wardrop equilibrium, which states that users do not have the incentives to unilaterally change their routes. Xie et al. [12] constructed a routing scheme that takes into account user-optimal routing and network-optimal routing; the former converges to the Wardrop equilibrium, the latter to the minimum latency. Su and de Veciana [11] propose an analytical model for multi-path routing, which leads to an optimal number of links over which dynamic multi-path routing should be conducted. They specify a policy for routing the traffic to a set of the least-loaded links and show that this is especially suitable for high-speed networks carrying bursty traffic. Another adaptive multi-path routing algorithm is proposed by Gojmerac et al. [5]; it operates with simple data structures and is independent of the underlying routing protocol. This is achieved by using local signaling and load balancing, and results in a reduction of the signaling overhead.
Another well-known, biologically inspired technique that is very efficient for routing is AntNet [4], which uses mobile agents that mimic the behavior of ant colonies. It operates by sending forward ants to probe routes and backward ants to update the routing tables at each intermediate node. Traffic is then routed along the paths with certain probabilities. The problem considered here differs from that approach, in that it focuses on the adaptive selection of already determined paths.
Adaptive Response by Attractor Selection
The biological model of Adaptive Response by Attractor Selection (ARAS) was proposed by Kashiwagi et al. [6] to model how E. coli cells adapt to changes in the availability of a nutrient for which no molecular machinery is available for signal transduction from the environment to the DNA. The appealing feature of this mechanism is that it is highly noise-tolerant and can even be stimulated by noise.
Basically, ARAS works as follows. Like all dynamic systems, the behavior of the system is characterized by a set of differential equations. Since the underlying method is very mathematical, it is easiest described with a simplified equation as shown in Equation 1.
The state of the system is given by the vector over all m, values and its dynamic behavior is influenced by the two functions f and g. When the system evolves over time, it converges to certain equilibrium points that are defined by the product of functions f and g in Equation 1. Additionally, the equilibrium points are constructed in such a way that they are stable attractors causing the system state to be automatically drawn to one of these attractors.
Furthermore, each of the M differential equations has a random component hi that corresponds to an inherent noise term found in the original gene expression model. This random noise term causes the system to be constantly in motion; however, once it has converged to an attractor, it remains there as long as the attractor is stable. In our approach, we control the selection of the appropriate attractor by an activity term a, which indicates how well the current system state corresponds to the considered influencing factors (nutrients) from the environment. The activity directly influences the differential equation system by causing attractors to become instable if the current system state is not suitable for the environmental conditions. In such a case, g(a) would become 0 causing the right-hand side of Equation 1 to be dominated by the random noise term and essentially a random walk is performed. In the course of this random search, the activity value increases again as soon as a better solution is approached and the influence of the random term is reduced (see Figure 1).
To further illustrate how this works, we can make an analogy with a set of electromagnets (attractors) to which the system state (metal ball) is drawn. Each magnet can be activated independently. At any time, only one magnet is active. The dynamic behavior of the activity corresponds to deciding whether the currently activated magnet reflects the current environment conditions. Thus, the abstract formulation of attractor selection can be seen as mapping a continuous input space to a discrete output space, as depicted in Figure 1.
Multi-Path Routing with ARAS
The technique proposed here is intrinsically applicable to the routing infrastructure of packet-switched networks. However, trying to enhance the IP routing algorithm currently used for the Internet is unrealistic. Instead, a more realistic scenario is to consider overlay routing over an underlying IP network, as for example in the Resilient Overlay Network (RON) [2] architecture. Andersen et al. [2] showed that RON can improve the loss rate and throughput over conventional Border Gateway Protocol (BGP) routing due to its faster reaction to path outages.
Applying the attractor selection scheme to the overlay routing problem can be performed in the following manner. Assume that each node has no exact knowledge of the topology and obtains all information by measurements of its links. For a certain {source, destination} pair with M transmission paths in an overlay network, one path is chosen as the primary path depending on the current environment conditions. This is the path with the best metric (smallest latency or highest available bandwidth) and over which most of the traffic of this flow is transported. The other paths are secondary paths; packets are transmitted over them with a low probability. If the situation changes, such that the current primary path is no longer the best choice, the attractor selection method decides which path to choose as the new primary path. In our model, we evaluate the current system state by mapping the measured input metrics to the activity value.
The desired behavior is shown in Figure 2. There are M paths between source s and destination d, one of which is the primary path. If a link or node fails along this path, the primary path is automatically switched to the best secondary path. The path switching should not only occur in such drastic conditions as link failures, but also when one of the secondary paths becomes more appropriate than the primary path due to changes in the network load. The basic operation of the routing algorithm consists of two phases: route setup and route maintenance.
Route Setup Phase
In the route setup phase, we use a decentralized method similar to that found in Ad hoc On-Demand Distance Vector (AODV) routing [8]. When a request for a new route to a destination arrives at the source node, it broadcasts route request messages to the network. When a neighboring node receives such a message and has no route to the destination, it continues broadcasting the packet to its neighbors. However, when it receives a route request message that it has already processed, it discards it. In case the route request message arrives at the destination node, or another node that already has a route to the destination stored in its table, this node replies with a route reply message to the source node requesting the route. As soon as the first route reply message arrives at the source, this source node knows a route to the destination node and can start using this route for packet transmission. In this way, up to M routes are collected gradually and the route maintenance phase can proceed with these M paths. Other methods for establishing disjoint routes, such as routes that do not share common links (link-disjoint) or common nodes (node-disjoint), can be used as well.
The route setup phase is initiated when a transmission request to an unknown node arrives at the source. After that, the route maintenance phase begins; the scheme operates in this phase most of the time. However, if certain paths are lost and a threshold for the minimum number of paths is reached, the route setup phase is entered again.
Route Maintenance Phase
Once the first path from source to destination has been established, the route maintenance phase is entered. In this phase, the attractor selection model is used to choose the path for transmitting packets. This selection is done according to metric values associated with each path. One example of a metric is the transmission delay, obtained by measuring the round trip time of each packet, which can be captured by inline measurements (in general, active delay measurements excessively increase network overhead).
The main problem in overlay network routing is that the best path is often chosen in an entirely selfish manner, and as a result the overall system performance is not considered. This may lead to undesired oscillations and instability in the network load. Seshadri and Katz [10] suggest imposing three constraints on this greedy behavior to improve the overall systemwide stability and performance: randomization in the route selections; route changes performed with a hysteresis threshold; and increasing the time interval between route changes. The randomization of path selections can easily be added to our model by using a probability for selecting each path. Furthermore, a hysteresis threshold is considered when mapping the changes of the path metrics to the activity term. This is included in the differential equation describing the dynamics of activity. Detailed equations as well as a comparative discussion with other randomized approaches can be found in [7].
The implementation of our approach is quite straightforward in spite of the rather complex mathematics involved. The differential equations are evaluated iteratively with the numerical Euler-Maruyama method for stochastic differential equations. The resulting terms are then normalized to yield probabilities according to which a path is selected. The only further interaction is to manage the active paths by adding and removing them after comparing them to threshold levels. Apart from that, no explicit rule is used and the system can operate completely autonomously.
An example of the time-dependent behavior of our model with M = 6 paths is given in Figure 3. In this case, we assume that, unless otherwise stated, all path metrics are equal. As a result, there is no specific preference for one path and the primary path is chosen randomly. Between 2,000 and 4,000 time steps, and after 8,000 steps, path 1 (the blue line) has the best metric and the selection is performed accordingly. In order to illustrate the resilience of our approach, path 2 (the green line) has the best metric after 4,000 time steps. However, the path fails after 6,000 steps and a new primary path is found immediately. Figure 3 shows that our proposed technique can continue operation without any difficulties even when the primary path fails. We also see that due to the random walk phase when searching for a new primary path, there is sometimes a slight transition phase necessary before a new solution is found. Additionally, the reaction delay is influenced by the time window sizes for measurements and route updates.
Conclusion
We have introduced a new biologically inspired approach for multi-path routing based on adaptive response by attractor selection. The proposed solution takes measurements of the path metrics as input and automatically selects the appropriate packet transmission probabilities for each path. The selection of the paths is done without any application of explicit rules by letting the system converge to an attractor solution. As it uses randomness to find the optimal solutions, it is tolerant of the influence of noise and capable of robust operation under varying environmental conditions. The approach can easily compensate for outages and temporary path losses. Another important advantage is that by appropriately setting the target activity level, it is possible to tune the degree of randomization in path selection. The proposed method showed good performance and high flexibility when compared to other randomized techniques (see [7] for details).
While this first study shows the behavior of a single {source, destination} pair, it can easily be extended to consider the symbiosis of interacting connections. In this case, we must consider an activity term that reflects the state of all interacting flows or a hierarchical structure of activity layers. However, this modification would make our approach less distributed, and the impact on scalability and performance remains to be investigated.
The application of the basic attractor selection method is not restricted to the problem of multi-path routing, but can also be considered as a generic optimization technique capable of adapting to a dynamic environment. The main problem is then the selection of appropriate input parameters. In our experiments, we considered the available bandwidth of packets; but the method is in fact more accurate when we define the system state by evaluating combinations of different metric values.
References
1. The 21st Century COE Program: New information technologies for building a networked symbiosis environment; www-nishio.ist.osaka-u.ac.jp/COE/english/.
2. Andersen, D., Balakrishnan, H., Kaashoek, F., and Morris, R. Resilient overlay networks. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP), (Banff, Canada, Oct. 2001).
3. Andersen, D., Snoeren, A., and Balakrishnan, H. Best-path vs. multi-path overlay routing. In Proceedings of the Internet Measurement Conference (IMC 2003), (Miami, FL, Oct. 2003).
4. Di Caro, G. and Dorigo, M. AntNet: Distributed stigmergetic control for communication networks. J. Artificial Intelligence Research 9 (1998), 317–365.
5. Gojmerac, I., Ziegler, T., Ricciato, F. and Reichl, P. Adaptive multipath routing for dynamic traffic engineering. In Proceedings of IEEE GLOBECOM (San Francisco, CA, 2003).
6. Kashiwagi, A., Urabe, I., Kaneko, K. and Yomo, T. Adaptive response of a gene network to environmental changes by attractor selection. Submitted for publication in Proceedings of the National Academy of Sciences.
7. Leibnitz, K., Wakamiya, N., and Murata, M. Resilient multi-path routing based on a biological attractor selection scheme. In Proceedings of the 2nd International Workshop on Biologically Inspired Approaches to Advanced Information Technology (BioAdit 2006), (Osaka, Japan, Jan. 2006).
8. Perkins, C. and Royer, E. Ad hoc on-demand distance vector routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing System and Applications, (New Orleans, LA, Feb. 1999).
9. Qiu, L., Yang, Y., Zhang, Y., and Shenker, S. On selfish routing in internet-like environments. In Proceedings of ACM SIGCOMM, (Karlsruhe, Germany, Aug. 2003).
10. Seshadri, M. and Katz, R. Dynamics of simultaneous overlay network routing. Tech. Rep. UCB//CSD-03-1291, University of California, Berkeley, CA, 2003.
11. Su, X. and de Veciana, G. Dynamic multipath routing: asymptotic approximation and simulations. In Proceedings of ACM SIGMETRICS, (Cambridge, MA, June 2001).
12. Xie, H., Qiu, L., Yang, Y., and Zhang, Y. On self adaptive routing in dynamic environments—An evaluation and design using a simple, probabilistic scheme. In Proceedings of the International Conference on Network Protocols (ICNP 2004), (Berlin, Germany, Nov. 2004).
Footnotes
1The technique presented in this article was inspired by the work of Tetsuya Yomo of the Department of Bioinformatics Engineering at Osaka University [6].
Figures
Figure 1. Principle of adaptive response by attractor selection.
©2006 ACM 0001-0782/06/0300 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2006 ACM, Inc.
No entries found