switching probability). Thus if P = 1 all
recommended path switches occur;
when P = 0.001 only one of every 1,000
recommended path switches actually
takes place. Thus the top curve shows
how the switching probability affects
path oscillations, starting with a given
path and returning to it again; as the
switching probability increases so does
the rate at which paths oscillate. The effect of P on the packet drop rate at the
output resequencing buffer is shown
in the bottom chart in the figure.
Figure 12 indicates that improvement in QoS (delay in this case) can be
achieved with a small switching probability (P = 0.01 or a little higher). Path
switching improves average delay (and
is why CPN attempts to switch paths),
though it comes at the cost of packet
loss. However, one can mitigate this
loss by probabilistically limiting the
switching while retaining the benefit of
improved QoS by lowering packet delay.
The SAN programmer can also limit
oscillations by setting a threshold that
allows a path switch only when the projected QoS improvement exceeds the
threshold. A small threshold allows
more frequent switches and hence potentially more oscillations, but a large
threshold may hurt QoS. Figure 13
shows that if the threshold is small, the
observed packet delay is large, and as
the threshold increases delay improves,
but packet delay increases again for
larger thresholds. For small threshold
values, longer packet delays indicate
that switching occurs based on “noise”
rather than on real gain. Increasing
the threshold in Figure 14 would reduce the oscillations, though the effect
would level out quickly. The threshold
thus limits the negative effect of switching but preserves the advantages of self-awareness and adaptation.
The approach to developing self-aware
networks presented here gives end users the means to explore the state of
the network so as to find the best ways
to meet their communication needs.
Focusing on the primary function of
packet routing, I have tried to answer
a number of questions concerning
the feasibility of such networks and
whether reliable communications
is possible in largely unknown networks. I have also addressed whether
there is a risk of unstable behavior in
such systems due to constant “
changes of mind” and oscillations as new information becomes available to users
and whether a user’s ability to adapt
to changing circumstances in the network reduces the consequences of
network failure. The experiments reported relate to small (up to 46-node)
networks; more results are available at
The Internet consists of hierarchically organized autonomous systems of
relatively small size, and one can imagine that routing inside and among them
would benefit from the techniques discussed here. Future research is likely to
investigate how these ideas can be integrated into existing networks, how they
scale to large networks, how they might
be able to withstand the malicious behavior of users and network nodes, and
how they can support mobile users.
Research sponsored by the U.K. Engineering and Physical Sciences Research Council Grant GR/S52360/01
on self-aware networks and quality of
service; and by E.U. FP6 Projects on
self-aware networks, performance,
and adaptivity and componentware
for autonomic situation-aware communications and dynamically adaptable services.
1. Bennett, J.C.R., Partridge, C., and Shectman, N.
Packet reordering is not pathological network
behavior. IEEE/ACM Transactions on Net works 7, 6
2. Boyan, J.A. and Littman, M.L. Packet routing in
dynamically changing networks: A reinforcement
learning approach. In Proceedings of the Advances in
Neural Information Processing Systems Conference
(Denver). Morgan kaufmann, San Francisco, 1994.
3. Chen, G., Branch, J., and Szymanski, B.k. A self-selection technique for flooding and routing in
wireless ad-hoc networks. Journal of Network and
Systems Management 14, 3 (2006), 359–380.
4. Di Caro, G. and Dorigo, M. Antnet: Distributed
stigmergetic control for communication networks.
Journal of AI Research 9 (1998), 317–365.
5. Dobson, S. Denazis, S., Fernández, A., Gaïti, D.,
Gelenbe, E., Massacci, F., Nixon, P., Saffre, F., Schmidt,
N., and zambonelli, F. A survey of autonomic
communications. ACM Transactions on Autonomous
and Adaptive Systems 1, 2 (2006), 223–259.
6. Gao, R., Dovrolis, C. and zegura, E. Avoiding
oscillations due to intelligent route control systems.
In Proceedings of the 25th IEEE International
Conference on Computer Communications
(Barcelona, Catalunya, Apr. 23–29). IEEE Press, New
7. Gelenbe, E., Sakellari, G., and D’Arienzo, M. Admission
of QoS-aware users in a smart network. ACM
Transactions on Autonomous and Adaptive Systems 3,
1 (Mar. 2008), 1–28.
8. Gelenbe, E. A diffusion model for packet travel time
in a random multihop medium. ACM Transactions on
Sensor Networks 3, 2 (June 2007).
9. Gelenbe, E. and Loukas, G. A self-aware approach
to denial-of-service defence. Computer Networks:
The International Journal of Computer and
Telecommunications Networking 51, 5 (Apr. 2007),
10. Gelenbe, E., Liu, P., and Lainé, J. Genetic algorithms for
route discovery. IEEE Transactions on Systems, Man,
and Cybernetics B 36, 6 (Dec. 2006), 1247–1254.
11. Gelenbe, E., Lent, R., and Nunez, A. Self-aware
networks and QoS. Proceedings of the IEEE 92, 9
(Sept. 2004), 1478–1489.
12. Gelenbe, E. and Lent, R. Power-aware ad hoc cognitive
packet net works. Ad Hoc Networks 2, 3 (July 2004),
13. Gelenbe, E., Gellman, M., Lent, R., Liu, P., and Su,
P. Autonomous smart routing for network QoS. In
Proceedings of the First International Conference on
Autonomous Computing (May 17–19). IEEE Computer
Society Press, New York, 2004, 232-239.
14. Gelenbe, E., Lent, R., and Xu, z. Measurement
and performance of a cognitive packet network.
International Journal of Computer and
Telecommunications Networking 37 (2001), 691–791.
15. Gelenbe, E. Learning in the recurrent random neural
network. Neural Computation 5, 1 (1993), 154–164.
16. Gellman, M. Oscillations in self-aware networks.
Proceedings of the Royal Society A 464, 2096 (2008),
17. keralapura, R., Chuah, C.N., Taft, N., and Iannaccone,
G. Can coexisting overlays inadvertently step on each
other? In Proceedings of the 13th IEEE International
Conference on Network Protocols (Boston, Nov. 6–9).
IEEE Computer Society, New York, 2005, 201–214.
18. khanna, A. and zinky, J. The revised Arpanet routing
metric. SIGCOMM Review 19, 4 (1989), 45–56.
19. koenig, S., Szymanski, B.k., and Liu, Y. Efficient
and inefficient ant coverage methods. Annals of
Mathematics and Artificial Intelligence 31, 1–4 (2001),
20. Labovitz, C., Malan, G.R., and Jahanian, F. Internet
routing instability. IEEE/ACM Transactions on
Networks 6, 5 (1998), 515–528.
21. Liu, P. and Gelenbe, E. Recursive routing in the
cognitive packet network. In Proceedings of the Third
International Conference on Testbeds and Research
Infrastructures for the Development of Networks and
Communities (May 21–23, 2007, Trento, Italy), 21–23.
22. Malkin, G. RIP Version 2. RFC 2453, 1998; http://www.
23. Moy, J. OSPF Version 2. RFC 2328, 1998; http://www.
24. Öke, G. G., Loukas, G., and Gelenbe, E. Detecting denial-of-service attacks with Bayesian classifiers and the
random neural network. In Proceedings of the IEEE
International Conference on Fuzzy Systems (London,
25. Papadimitriou, C.h. and Yannakakis, M. Shortest paths
without a map. Theoretical Computer Science 84, 1
26. Ranadive, U. and Medhi, D. Some observations on the
effect of route fluctuation and network link failure
on TCP. In Proceedings of the 10th International
Conference on Computer Communications and
Networks (Oct. 15–17, 2001), 460–467.
27. Sakellari, G. and Gelenbe, E. Adaptive resilience of the
cognitive packet network in the presence of network
worms. In Proceedings of the NATO Symposium
on C3I for Crisis, Emergency and Consequence
Management (May 11–12, 2009, Bucharest, Romania).
28. Shaikh, A., Varma, A., kalampoukas, L., and
Dube, R. Routing stability in congested networks:
Experimentation and analysis. In Proceedings of
SIGCOMM 2000, (Stockholm, Aug. 29–Sept. 2). ACM
Press, New York, 2000, 163–174.
29. Thorup, M. and zwick, U. Compact routing schemes.
In Proceedings of the 13th Annual ACM Symposium
on Parallel Algorithms and Architectures (heraklion,
Crete Island, Greece, July 4–6). ACM Press, New
York, 2001, 1–10.
Erol Gelenbe ( email@example.com) is head of
the Intelligent Systems and Networks Research Group
and Professor in the Dennis Gabor Chair, Electrical and
Electronic Engineering Department, Imperial College
© 2009 ACM 0001-0782/09/0700 $10.00