Network survivability performance evaluation:: a quantitative approach with applications in wireless ad-hoc networks

ABSTRACT

Network survivability reflects the ability of a network to continue to function during and after failures. Our purpose in this paper is to propose a quantitative approach to evaluate network survivability. We perceive the network survivability as a composite measure consisting of both network failure duration and failure impact on the network. A wireless ad-hoc network is analyzed as an example, and the excess packet loss due to failures (ELF) is taken as the survivability performance measure. To obtain ELF, we adopt a two phase approach consisting of the steady-state availability analysis and transient performance analysis. Assuming Markovian property for the system, this measure is obtained by solving a set of Markov models. By utilizing other analysis paradigms, our approach in this paper may also be applied to study the survivability performance of more complex systems.

REFERENCES

• 1: Network reliability steering committee annual report 2000. http://www.atis.org/pub/nrsc/2000Rpt.pdf.
• 2: U. S. Department of Commerce, National Telecommunications and Information Administration, Institute for Telecommunications Services, Federal Standard 1037C.
• 3: T1A1.2 Working Group on Network Survivability Performance, Technical report on enhanced network survivability performance, February 2001.
• 4: A. Avizienis. Design diversity - the challenge of the eighties. In Digest of FTCS-12, pages 44--45.
• 5: D.-Y. Chen, Y. Hong, and K. S. Trivedi. Classification of faults, errors and failures in communication systems. In Submitted for publication.
• 6: Philip Francis Chimento, Jr. , K. S. Trivedi, System performance in a failure prone environment, 1988
• 7: Gianfranco Ciardo , Jogesh K. Muppala , Kishor S. Trivedi, SPNP: Stochastic Petri Net Package, The Proceedings of the Third International Workshop on Petri Nets and Performance Models, p.142-151, December 11-13, 1989
• 8: F. Cristian, H. Aghili, R. Strong, and D. Dolev. Atomic broadcast: From simple message diffusion to Byzantine agreement. In Proceedings of the 15th International Conference on Fault-Tolerant Computing, Silver Spring, Maryland, 1985. IEEE Computer Society.
• 9: B. Ellison, D. Fisher, R. Linger, H. Lipson, T. Longstaff, and N. Mead. Survivable network systems: An emerging discipline. Technical Report CMU/SEI-97-TR-013, Software Engineering Institute, Carnegie Mellon University, November 1997.
• 10: A. I. Elwalid and D. Mitra. Statistical multiplexing with loss priorities in rate-based congestion control of high-speed networks. IEEE Transactions on Communications, 42(11):2989--3002, November 1994.
• 11: G. Horton, V. G. Kulkarni, D. M. Nicol, and K. S. Trivedi. Fluid stochastic Petri nets: Theory, applications, and solution techniques. European Journal of Operational Research, (105):184--201, 1998.
• 12: M. Kalyanakrishnan , R. K. Iyer , J. U. Patel, Reliability of internet hosts: a case study from the end user's perspective, Selected papers of the 6th international conference on Computer communications and networks, p.47-57, January 1999
• 13: J. Knight, K. J. Sullivan, M. C. Elder, and C. Wang. Survivability architectures: Issues and approaches. In DARPA Information Survivability Conference and Exposition (DISCEX 2000), Hilton Head, SC, January 2000.
• 14: J. C. Knight and K. J. Sullivan. On the definition of survivability. Technical Report CS-TR-33-00, University of Virginia, Department of Computer Science, 2000.
• 15: Craig Labovitz , Abha Ahuja , Farnam Jahanian, Experimental Study of Internet Stability and Backbone Failures, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.278, June 15-18, 1999
• 16: Markov regenerative models, Proceedings of the International Computer Performance and Dependability Symposium on Computer Performance and Dependability Symposium, p.134, April 24-26, 1995
• 17: D. Logothetis and K. S. Trivedi. Transient analysis of the leaky bucket rate control scheme under poisson and on-off sources. In INFOCOM'94, volume~2, pages 490--497, 1994.
• 18: V. Marbukh and M. W. Subbarao. Framework for maximum survivability routing for a MANET. In MILCOM 2000, volume~1, pages 282--286.
• 19: A. M. Noll. Private Networks and Public Objectives, chapter Network Security and Reliability: Emergencies in Decentralized Networks, pages 343--356. Elsevier Science, Amsterdam, The Netherlands, 1996.
• 20: C. G. Omidyar, editor. Survivability analysis of Ad Hoc wireless network architecture, volume 1818 of Lecture Notes in Computer Science. Springer, 2000.
• 21: B. C. Research. Reliability and quality measurements for telecommunications systems (rqms). Technical report, Bellcore, 1998.
• 22: Andrew P. Snow , Upkar Varshney , Alisha D. Malloy, Reliability and Survivability of Wireless and Mobile Networks, Computer, v.33 n.7, p.49-55, July 2000 [doi>10.1109/2.869370]
• 23: D. Tipper, T. Dahlberg, H. Shin, and C. Charnsripinyo. Providing fault tolerance in wireless access networks. IEEE Communications Magazine, 40(1):58--64, 2002.
• 24: D. Tipper, J. Hammond, S. Sharma, A. Khetan, and K. B. S. Menon. An analysis of the congestion effects of link failures in wide area networks. IEEE Journal on Selected Areas in Communications, 12(1), January 1994.
• 25: D. Tipper, S. Ramaswamy, and T. Dahlberg. PCS network survivability. In Proceedings of IEEE Wireless Communications and Networking Conference (WCNC'99), pages 1028--1032, New Orleans, LA, 1999.
• 26: D. Tipper and M. Sundaresan. Numerical methods for modeling computer networks under non-stationary conditions. IEEE Journal on Selected Areas in Communications, 8(9):1682--1695, 1990.
• 27: Kishor S. Trivedi, Probability and statistics with reliability, queuing and computer science applications, John Wiley and Sons Ltd., Chichester, UK, 2001
• 28: M. Veeraraghavan, N. Cocker, and T. Moors. Support of voice services in IEEE 802.11 wireless LANs. In Proceedings of INFOCOM'01, 2001.
• 29: Chenxi Wang , Jonathan Hill , John C. Knight , Jack W. Davidson, Protection of Software-Based Survivability Mechanisms, Proceedings of the 2001 International Conference on Dependable Systems and Networks (formerly: FTCS), p.193-202, July 01-04, 2001
• 30: C.-Y. Wang, D. Logothetis, K. S. Trivedi, and I. Viniotis. Transient behavior of ATM networks under overloads. In Proceedings of the IEEE INFOCOM'96, San Francisco, March 1996.
• 31: Y. H. Wang, W. S. Soh, M. Y. Tsai, and H. S. Kim. Survivable wireless ATM network architecture. In Ninth International Conference on Computer Communications and Networks, pages 368--373, 2000.
• 32: A. Zolfaghari and F. J. Kaudel. Framework for network survivability performance. IEEE Journal on Selected Areas in Communications, 12(1):46--51, January 1994.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Performance, Reliability

Keywords:
Markov models, availability, survivability, transient analysis, wireless ad-hoc networks