|
Progress - Overlay Networks - Monitoring
Virtual paths between all source destination pairs in a communication
network should be chosen such that an overall good utilization of
network resources is ensured, and hence high throughput, low loss
and low latency achieved. These paths must be continuously updated
as the traffic load changes, new paths to be almost immediately available
when paths are affected by failures, and new or repaired. Swarm intelligence
based self-management is a candidate potentially able to fulfill these
requirements. At the same time it will overcome some of the drawbacks
of the current path and fault management strategies where paths are
found off-line using static, estimated link weights.
In BISON an ant routing system called Cross-Entropy ants (CE ants)
has been modified and applied to solve the problem of finding and
maintaining virtual paths in a communication network with changing
conditions. Experiments have shown that the CE ants system applied
to path management is
- Adaptive: a few messages are needed to establish an alternative
path when link breaks or becomes overloaded
- Robust: paths are found and maintained even with a large number
of lost messages (ants)
The CE ants has been applied to various path management problems.
In BISON, we have been studied enhancement of the theoretical fundaments [HWNH04]
and various practical use of the approach, ranging from search under
strict path and resource quality requirements, [WHH03b],
via path management in Telenor's IP network [HWH05],
to online MPLS Label Switched Paths (LSPs) establishment guided by
CE ants [HHW04], and even a prototype implementation to
learn more about the challenges and bottlenecks in implementation
of an ants system in a running (software) IP router [MHW04].
Path monitoring is the performance monitoring of established
virtual paths. The performance parameters include available bandwidth,
remaining bandwidth, end-to-end delay, and loss ratio. The monitoring
information is of interest to a network provider if new, and up to
date, information of the network quality is available. For the network
users it is of interest to observe the quality of the transport service.
The CE ants algorithm is designed to establish good paths between
multiple pairs of ingress and egress nodes. In addition, it is observed
that the CEants algorithm contains control variables that change rapidly
and significantly as the network condition changes, both due to traffic
and topology changes. Hence, these can be used for monitoring of the
quality of a path and to detect changes in network conditions influencing
this quality. In BISON deliverable D5 and D7, it was observed that
in particular the control variable denoted temperature in CE ants
was a good candidate as a monitoring index for path quality.
In Table 1 a few examples are given of what indices from
the ant routing systems, which may apply to monitoring of the performance
of the paths.
Table 1:
Examples of use of indices from ant based path management systems
| Metric |
Ex. of observation |
Ex. of ``health'' |
Ex. of alarm |
| Ant route table |
Deviation from data routing table |
Misconfiguration in routing, interface overload |
Significant deviation (in time or space) |
| Pheromone values |
Increase by 20% in 1 sec. |
Node/link/path down |
Check configuration |
| Convergence index |
Decrease by 20% in 1 sec. |
New node/link/path discovered |
None |
| Cost value index |
Average over 5 sec. decreased by 10% last minute |
Aftereffect of change in network (still exploration) |
None |
| Path probability |
Close to max. for last minute |
Stable network |
None |
The simulator used in most of the BISON work on path management is
implemented in SIMULA using the DEMOS class library. The source code
and input parameters is available from
- HWNH04
-
Poul E. Heegaard, Otto Wittner, Victor F. Nicola, and Bjarne E. Helvik.
Distributed asynchronous algorithm for cross-entropy-based
combinatorial optimization.
In Rare Event Simulation & Combinatorial Optimization
(RESIM2004), Budapest, Hungary, September 2004.
[PDF],
[Bibtex].
- WHH03b
-
Otto Wittner, Poul E. Heegaard, and Bjarne E. Helvik.
Scalable distributed discovery of resource paths in telecomunication
networks using cooperative ant-like agents.
In Proceedings of the International Congress on Evolutionary
Computation, Canberra, Australia, December 2003.
[PDF],
[Bibtex].
- HWH05
-
Poul E. Heegaard, Otto Wittner, and Bjarne Helvik.
Self-managed virtual path management in dynamic networks.
In Ozalp Babaoglu, Márk Jelasity, Alberto Montresor, Christof
Fetzer, Stefano Leonardi, Aad van Moorsel, and Maarten van Steen, editors,
Self-Star Properties in Complex Information Systems, volume 3460 of
Lecture Notes in Computer Science. Springer-Verlag, 2005.
[PDF],
[Bibtex].
- HHW04
-
Nina Hesby, Poul E. Heegaard, and Otto Wittner.
Robust connections in ip networks using primary and backup paths.
In Proceedings of the 17th Nordic Teletraffic Seminar, Fornebu,
Norway, August 2004.
[PDF],
[Bibtex].
- MHW04
-
Anders Mykkeltveit, Poul Heegaard, and Otto Wittner.
Realization of a distributed route management system on software
routers.
In Proceedings of Norsk Informatikkonferanse, Stavanger,
Norway, November 2004.
[PDF],
[Bibtex].
|