Computing bounds on steady state availability of repairable computer systems

ABSTRACT

One of the most important performance measures for computer system designers is system availability. Most often, Markov models are used in representing systems for dependability/availability analysis. Due to complex interactions between components and complex repair policies, the Markov model often has an irregular structure, and closed-form solutions are extremely difficult to obtain. Also, a realistic system model often has an unmanageably large state space and it quickly becomes impractical to even generate the entire transition rate matrix. In this paper, we present a methodology that can (i) bound the system steady state availability and at the same time, (ii) drastically reduce the state space of the model that must be solved. The bounding algorithm is iterative and generates a part of the transition matrix at each step. At each step, tighter bounds on system availability are obtained. The algorithm also allows the size of the submodel, to be solved at each step, to be chosen so as to accommodate memory limitations. This general bounding methodology provides an efficient way to evaluate dependability models with very large state spaces without ever generating the entire transition rate matrix.

REFERENCES

• 1: ~BERMAN, A., AND PLEMMONS, R. J. 1979. Nonnegattt,e Matrices in the Mathematical Sciences. ~Academic Press, Orlando, Fla.
• 2: ~BURDEN, R. L., AND FAMES, J. D. 1989. Numerical Analysis. PWS-KENT Publishing Company, ~Boston, Mass.
• 3: ~CARRASCO, J. A., AND F1GUERAS, J. 1986. METFAC: Design and implementation of a software ~toll for modeling and evaluation of complex fault-tolerant computing systems. In Proceedings of ~the 16th Annual htterlzattonal Symposium on Fault-Tolerant Computing Systems (FTCS-16) ~(Vienna, Ausma, July). IEEE Computer Society Press, Washington, D.C., pp. 424-429.
• 4: ~CONWAY, A. E., AND GOYAL, A. 1987. Monte Carlo simulation of computer system availability ~and reliability models. In Proceedmgs of the {7th Annual Intertzattonal Symposium on Fault- ~Tolerant Comptttlng Systems (FTCS-17) (June), IEEE Computer Society Press, Washington, ~D.C., pp. 230 235.
• 5: ~COSTES, A., DOUCET, J. E., LANDRAULT, C., AND LAPRIE, J. C. 1981. SURF: A program for ~dependability evaluation of complex fault-tolerant computing systems. In Proceedings of the llth ~Annual Itztemattonal $}'mposium on Fault-Toleratzt Conlputmg Systems (FTCS-1I ). (June). IEEE, ~Computer Society Press, Washington, D.C,, pp. 72-78.
• 6: ~COURTOIS, P. J. 1977. Decomposabthty--Queueing and Computer System Apphcattons. Academic ~Press, Orlando, Fla.
• 7: ~COURTOIS, P. J. 1982. Error Minimization in Decomposable Stochastic Models. In Apphed ~Probability--Computer Science: The Interface VoL I. R. L. Disney and T. Ott, eds. Blrkhauser.
• 8: P.-J. Courtois , P Semal, Bounds for the Positive Eigenvectors of Nonnegative Matrices and for their Approximations by Decomposition, Journal of the ACM (JACM), v.31 n.4, p.804-825, Oct. 1984 [doi>10.1145/1634.1637]
• 9: ~COURTOIS, P. J., AND SEMAL, P. 1986 Computable bounds for conditional steady-state probabili- ~ties in large markov chains and queueing models. J. Select. Areas Commtm. 4, 6 (Sept.), ~926 937.
• 10: Edmundo de Souza e Silva , H. Richard Gail, Calculating cumulative operational time distributions of repairable computer systems, IEEE Transactions on Computers, v.35 n.4, p.322-332, April 1986 [doi>10.1109/TC.1986.1676765]
• 11: Edmundo de Souza e Silva , H. Richard Gail, Calculating availability and performability measures of repairable computer systems using randomization, Journal of the ACM (JACM), v.36 n.1, p.171-193, Jan. 1989 [doi>10.1145/58562.59307]
• 12: ~DIMITRIJEViC, D. D., AND CHEN, M. 1988. An integrated algorithm for probabilistic protocol ~verification and evaluation. IBM Teeh. Rap, RC 13001_ T. J. Watgon l~.egearch Center, It/M, ~Yorktown Heights, N.Y.
• 13: ~GEIST, R., AND TR1VEDi, K. S. 1985. Ultra-High Reliability Prediction for Fault-Tolerant ~Computer Systems. IEEE Trans. Compztt. C-32, 12 (Dec.), 1118 1127.
• 14: ~GOYAL, A., CARTER, W. C., DE SOUZA E SILVA, E., LAVENBERG, $. S., AND TRIVEDI, K. S. 1986. ~The System Avadability Estimator. In Proceedings of the 16th Mnnual International Symposzum ~on Fault-Tolerant Cornputitlg Systems (FTCS-{6) (Vienna, Austria, (July). pp. 84-89.
• 15: ~GOYAL, A., LAVENBERG, S. S., AND TRIVEDI, K, S. Probabilistic modeling of computer ~system availability. ~4nn. Oper. Res. 8 (1986), 285-306.
• 16: ~HEIDELBEROER, AND GOYAL, A. 1987. Sensitivity Analys~s of Continuous T~me Markov Chains ~Using Uniformization. In Proceedings of the 2tzd International Workz'hop on Applied Mathematics ~and Performance /Rehabihty Models of Computer/ Commzmicatton Systems (Rome, Italy, May) ~North Holland, Amsterdam, The Netherlands.
• 17: ~KEMENY, J. G., AND SNELL, J. L. 1960. Finite Markot, Chains. Van Nostrand Company. Princeton, ~N.J.
• 18: ~LEWIS, E. E., AND BOHM, F. 1989. Monte Carlo simulation of Markov unreliability models. Nucl. ~Eng. Des. 77, 1, 49-62.
• 19: ~LUI, J. C. S., AND MUNTZ, R. R. 1991. Evaluating Bounds on Steady State Availability from ~Markov Models of Repairable Systems. In Numerical Solution of Markov Chains, William J. ~Stewart, ed. Marcel Dekker, New York, pp. 435-454.
• 20: ~MAKAM, S. V., AND AVIZIENIS, A. 1982. ARIES 81: A reliability and life-cycle evaluation tool for ~fault tolerant systems. In Proceedings of the 12th Annual International Symposium on Fault- ~Tolerant Computing Systems (FTCS-12). (June), pp. 273-274.
• 21: Nicholas F. Maxemchuk , Krishan K. Sabnani, Probabilistic Verification of Communication Protocols, Proceedings of the IFIP WG6.1 Seventh International Conference on Protocol Specification, Testing and Verification VII, p.307-320, May 05-08, 1987
• 22: R. R. Muntz , E. de Souza e Silva , A. Goyal, Bounding availability of repairable computer systems, ACM SIGMETRICS Performance Evaluation Review, v.17 n.1, p.29-38, May 1989
• 23: ~EUTS, M. F. 1981. Matrix-geometric Solutions in Stochastic Models--An Algorithmic Approach. ~Johns Hopkins University Press, Baltimore, Md.
• 24: ~Ross, S. M. 1983. Stochastic Processes. Wiley series in probability and mathematical statistics. ~Wiley, New York.
• 25: ~STEWART, W. J., AND GOYAL, A. 1985. Matrix methods in large dependability models, IBM Res.
• 26: ~Rep. 11485 (Nov. 4, 1985). T. J. Watson Research Center, IBM, Yorktown Heights, N.Y.
• 27: ~TAKAHASH1, Y. 1972. Some problems for applications of Markov chains. Ph.D. dissertation, ~Tokyo Institute of Technology, Tokyo, Japan, March.
• 28: ~TAKAHASttI, Y. 1975. A lumping method for numerical calculations of stationary distributions of ~markov chains. Research Reports on Information Sciences, No. B-18. Tokyo Institute of ~Technology, Tokyo, Japan, June.
• 29: Kishar Shridharbhai Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• 30: Kishor Trivedi , Joanne Bechta Dugan , Robert Geist , Mark Smotherman, Hybrid reliability modeling of fault-tolerant computer systems, Computers and Electrical Engineering, v.11 n.2-3, p.87-108, 1984 [doi>10.1016/0045-7906(84)90004-1]
• 31: Nico M. van Dijk, Simple bounds for queueing systems with breakdowns, Performance Evaluation, v.8 n.2, p.117-128, April 1988 [doi>10.1016/0166-5316(88)90017-X]
• 32: ~VAN D1JK, N. M. 1989. The importance of bias-terms for error bounds and comparison results. ~Tech. Rep. 1989-36. Free University, Amsterdam, The Netherlands.
• 33: ~VARGA, R. 1962. Matrix Iteratit,e Analysis. Prentice-Hall, Englewood Cliffs, N.J.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Stochastic analysis

General Terms:
Algorithms, Reliability, Theory