Estimated and exact system reliabilities of a maintainable computer network

Abstract

This paper presents an algorithm to evaluate estimated and exact system reliabilities for a computer network in the cloud computing environment. From the quality of service (QOS) viewpoint, the computer network should be maintained when falling to a specific state such that it cannot afford enough capacity to satisfy demand. Moreover, the transmission time should be concerned as well. Thus, the data can be sent through several disjoint minimal paths simultaneously to shorten the transmission time. Under the maintenance budget B and time constraint T, we evaluate the system reliability that d units of data can be sent from the cloud to the client through multiple paths. Two procedures are integrated in the proposed algorithm-an estimation procedure for estimated system reliability and an adjusting procedure utilizing the branch-and-bound approach for exact system reliability. Subsequently, the estimated system reliability with lower bound and upper bound, and exact system reliability are computed by applying the recursive sum of disjoint products (RSDP) algorithm.

Keywords

System reliability / maintenance / network flows / branch-and-bound approach / estimation

References

[1] Alexopoulos C.. A note on state-space decomposition methods for analyzing stochastic flow networks. IEEE Transactions on Reliability, 1995, 44(2): 354-357.

[2] Aven T.. Reliability evaluation of multistate systems with multistate components. IEEE Transactions on Reliability, 1985, 34(5): 473-479.

[3] Bodin L.D., Golden B.L., Assad A.A., Ball M.O.. Routing and scheduling of vehicles and crews: the state of the art. Computers and Operations Research, 1982, 10(22): 63-211.

[4] Chen Y.L., Chin Y.H.. The quickest path problem. Computers and Operations Research, 1990, 17(2): 153-161.

[5] Chen G.H., Hung Y.C.. On the quickest path problem. Information Processing Letters, 1993, 46(3): 125-128.

[6] Chen G.H., Hung Y.C.. Algorithms for the constrained quickest path problem and the enumeration of quickest paths. Computers and Operations Research, 1994, 21(2): 113-118.

[7] Chen Y.L., Tang K.. Minimum time paths in a network with mixed time constraints. Computers and Operations Research, 1998, 25(10): 793-805.

[8] Clímaco J.C.N., Pascoal M.M.B., Craveirinha J.M.F., Captivo M.E.V.. Internet packet routing: application of a K-quickest path algorithm. European Journal of Operational Research, 2007, 181(3): 1045-1054.

[9] Golden B.L., Magnanti T.L.. Deterministic network optimization: a bibliography. Networks, 1977, 7(2): 149-183.

[10] Hewitt C.. ORGs for scalable, robust, privacy-friendly client cloud computing. IEEE Internet Computing, 2008, 12(5): 96-99.

[11] Hudson J.C., Kapur K.C.. Reliability bounds for multistate systems with multistate components. Operations Research, 1985, 33(1): 153-160.

[12] Hung Y.C., Chen G.H.. Distributed algorithms for the quickest path problem. Parallel Computing, 1992, 18(7): 823-834.

[13] Jane C.C., Lin J.S., Yuan J.. On reliability evaluation of a limited-flow network in terms of minimal cutsets. IEEE Transactions on Reliability, 1993, 42(3): 354-361.

[14] Jin T., Coit D.W.. Network reliability estimates using linear & quadratic unreliability of minimal cuts. Reliability Engineering & System Safety, 2003, 82(1): 41-48.

[15] Kelso, R. (2001). Innovative bandwidth arrangements for the Australian education and training sector; Stage 1: assessment of overseas approaches. RMIT University, AU. Available via DIALOG. http://www.dest.gov.au/. Cited April 14, 2011

[16] Lee D.T., Papadopoulou E.. The all-pairs quickest path problem. Information Processing Letters, 1993, 45(5): 261-267.

[17] Lin J.S., Jane C.C., Yuan J.. On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Networks, 1995, 25(3): 131-138.

[18] Lin Y.K.. Reliability of a stochastic-flow network with unreliable branches & nodes under budget constraints. IEEE Transactions on Reliability, 2004, 53(3): 381-387.

[19] Lin Y.K.. On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint. European Journal of Operational Research, 2007, 176(1): 347-360.

[20] Lin Y.K.. Spare routing reliability for a stochastic flow network through two minimal path under budget constraint. IEEE Transactions on Reliability, 2010, 59(1): 2-10.

[21] Martins E.D.Q.V., Santos J.L.E.D.. An algorithm for the quickest path problem. Operations Research Letters, 1997, 20(4): 195-198.

[22] Moreb A.A.. Allocating repairable system’s reliability subject to minimal total cost — an integer programming approach. Journal of Systems Science and Systems Engineering, 2007, 16(4): 499-506.

[23] Park C.K., Lee S., Park S.. A label-setting algorithm for finding a quickest path. Computers and Operations Research, 2004, 31(4): 2405-2418.

[24] Pascoal M.M.B., Captivo M.E.V., Clímaco J.C.N.. An algorithm for ranking quickest simple paths. Computers and Operations Research, 2005, 32(3): 509-520.

[25] Ramirez-Marquez J., Coit D.W., Tortorella M.. A generalized multistate-based path vector approach for multistate two-terminal reliability. IIE Transactions, 2006, 38(6): 477-488.

[26] Ramirez-Marquez J., Coit D.W.. Optimization of system reliability in the presence of common cause failures. Reliability Engineering & System Safety, 2007, 92(10): 1421-1434.

[27] Sethi S.P., Yeh H.M., Zhang R., Jardine A.K.S.. Optimal maintenance and replacement of extraction machinery. Journal of Systems Science and Systems Engineering, 2008, 17(4): 416-431.

[28] Xue J.. On multistate system analysis. IEEE Transactions on Reliability, 1985, 34(4): 329-337.

[29] Yarlagadda R., Hershey J.. Fast algorithm for computing the reliability of communication network. International Journal of Electronics, 1991, 70(3): 549-564.

[30] Yeh W.C.. Multistate network reliability evaluation under the maintenance cost constraint. International Journal of Production Economics, 2004, 88(1): 73-83.

[31] Yue W., Gu J., Tang X.. A performance evaluation index system for multimedia communication networks and forecasting for web-based network traffic. Journal of Systems Science and Systems Engineering, 2004, 13(1): 78-97.

[32] Zuo M.J., Tian Z., Huang H.Z.. An efficient method for reliability evaluation of multistate networks given all minimal path vectors. IIE Transactions, 2007, 39(8): 811-817.