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.

Conclusion

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 http://san.ee.ic.ac.uk.

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.

Acknowledgments

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.

 

References

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 (1999), 789–798.

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 York, 2006.

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), 1299–1314.

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), 205–216.

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), 2169–2186.

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), 41–76.

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. faqs.org/rfcs/rfc2453.html.

23. Moy, J. OSPF Version 2. RFC 2328, 1998; http://www. ietf.org/rfc/rfc2328.txt.

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, 2007), 964–1969.

25. Papadimitriou, C.h. and Yannakakis, M. Shortest paths without a map. Theoretical Computer Science 84, 1 (1991), 127–150.

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 ( [e-mail]) is head of the Intelligent Systems and Networks Research Group and Professor in the Dennis Gabor Chair, Electrical and Electronic Engineering Department, Imperial College London.

© 2009 ACM 0001-0782/09/0700 $10.00