System reliability of assured accuracy rate for multi-state computer networks from service level agreements viewpoint

Abstract

From the viewpoint of service level agreements, the transmission accuracy rate is one of critical performance indicators to assess internet quality for system managers and customers. Under the assumption that each arc’s capacity is deterministic, the quickest path problem is to find a path sending a specific of data such that the transmission time is minimized. However, in many real-life networks such as computer networks, each arc has stochastic capacity, lead time and accuracy rate. Such a network is named a multi-state computer network. Under both assured accuracy rate and time constraints, we extend the quickest path problem to compute the probability that d units of data can be sent through multiple minimal paths simultaneously. Such a probability named system reliability is a performance indicator to provide to managers for understanding the ability of system and improvement. An efficient algorithm is proposed to evaluate the system reliability in terms of the approach of minimal paths.

Keywords

Assured accuracy rate / service level agreement (SLA) / transmission time / multi-state computer network (MSCN) / system reliability

References

[1] Amer PD. A measurement center for the NBS local area computer network. IEEE Transactions on Computers, 1982, C-31: 723-729.

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

[3] Chen GH, Hung YC. On the quickest path problem. Information Processing Letters, 1993, 46: 125-128.

[4] Chen GH, Hung YC. Algorithms for the constrained quickest path problem and the enumeration of quickest paths. Computers and Operations Research, 1994, 21: 113-118.

[5] Chen YL. An algorithm for finding the k quickest paths in a network. Computers and Operations Research, 1993, 20: 59-65.

[6] Chen YL. Finding the k quickest simples paths in a network. Information Processing Letters, 1994, 50: 89-92.

[7] Chen YL, Chin YH. The quickest path problem. Computers and Operations Research, 1990, 17: 153-161.

[8] Chen YL, Tang K. Minimum time paths in a network with mixed time constraints. Computers and Operations Research, 1998, 25: 793-805.

[9] Cheng ST. Topological optimization of a reliable communication network. IEEE Transactions on Reliability, 1998, 47: 225-233.

[10] Chlamtac I. Issues in design and measurement of local area networking. Proc. Comput. Measurement Group Conference CMG XI Dec, 1980 32-34.

[11] Choi BY, Park J, Zhang ZL. Adaptive random sampling for traffic load measurement. IEEE Int. Conf., on Communications (ICC’ 03), May, Anchorage, Alaska, 2003 1552-1556.

[12] Clímaco JCN, Pascoal MMB, Craveirinha JMF, Captivo MEV. Internet packet routing: application of a K-quickest path algorithm. European Journal of Operational Research, 2007, 181: 1045-1054.

[13] Chang PC, Lin YK. New challenges and opportunities in flexible and robust supply chain forecasting systems. International Journal of Production Economics, 2010, 128: 453-456.

[14] Feldmann A, Greenberg A, Reingold N, Lund C, Rexford J, True F. Deriving traffic demands for operational IP networks: Methodology and experience. IEEE/ACM Transactions on Networking, 2001, 3: 265-279.

[15] Ford LR, Fulkerson DR. Flows in Networks, 1962, New Jersy: Princeton University Press.

[16] Hung YC, Chen GH. Distributed algorithms for the quickest path problem. Parallel Computing, 1992, 18: 823-834.

[17] Jain R, Routhier SA. Packet trains: Measurements and a new model for computer network traffic. IEEE Journal on Selected Areas Communications, 1986, 4: 986-995.

[18] Jane CC, Lin JS, Yuan J. On reliability evaluation of a limited-flow network in terms of minimal cutsets. IEEE Transactions on Reliability, 1993, 42: 354-361.

[19] Jedwab J, Phaal P, Pinna B. Traffic estimation for the largest sources, on a network, using packet sampling with limited storage, 1992

[20] Lee DT, Papadopoulou E. The all-pairs quickest path problem Information. Processing Letters, 1993, 45: 261-267.

[21] Levitin G, Lisnianski A. A new approach to solving problems of multi-state system reliability optimization. Quality Reliability Engineering International, 2001, 17: 93-104.

[22] Lin JS, Jane CC, Yuan J. On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Network, 1995, 25: 131-138.

[23] Lin YK. Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network. Computers and Operations Research, 2003, 30: 567-575.

[24] Lin YK. Reliability evaluation for an information network with node failure under cost constraint. IEEE Transactions on Systems, Man and Cybernetics — Part A, Systems and Humans, 2007, 37: 180-188.

[25] Lin YK. On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint. European Journal of Operational Research, 2007, 176: 347-360.

[26] Lin YK. Time version of the shortest path problem in a stochastic-flow network. Journal of Computational and Applied Mathematics, 2009, 228: 150-157.

[27] Lin YK. System reliability of a stochastic-flow network through two minimal paths under time threshold. International Journal of Production Economics, 2010, 124: 382-387.

[28] Lin YK, Chang PC. Estimated and exact system reliabilities of a maintainable computer network. Journal of Systems Science and Systems Engineering, 2011, 20: 229-248.

[29] Martins EDQV, JLED Santos An algorithm for the quickest path problem. Operations Research Letters, 1997, 20: 195-198.

[30] Meo PD, Iera A, Terracina G, Ursino D. A multi-agent system for managing the quality of service in telecommunications networks. Journal of Systems Science and Systems Engineering, 2005, 14: 129-158.

[31] Mori T, Takine T, Pan J, Kawahara R, Uchida M, Goto S. Identifying heavy-hitter flows from sampled flow statistics. IEICE Transactions on Communications, 2007, E90-B: 3061-3072.

[32] Park CK, Lee S, Park S. A label-setting algorithm for finding a quickest path. Computers and Operations Research, 2004, 31: 2405-2418.

[33] Pascoal MMB, Captivo MEV, Clímaco JCN. An algorithm for ranking quickest simple paths. Computers and Operations Research, 2005, 32: 509-520.

[34] Sausen PS, Spohn MA, Perkusich A. Broadcast routing in wireless sensor networks with dynamic power management and multi-coverage backbones. Information Sciences, 2010, 180: 653-663.

[35] Xue J. On multistate system analysis. IEEE Transactions on Reliability, 1985, R-34: 329-337.

[36] Yeh WC. Multistate network reliability evaluation under the maintenance cost constraints. International Journal of Production Economics, 2004, 88: 73-83.

[37] Yeh WC. A new approach to evaluating reliability of multistate networks under the cost constraint. Omega, 2005, 33: 203-209.

[38] Yeh WC. A simple minimal path method for estimating the weighted multi-commodity multistate unreliable networks reliability. Reliability Engineering and System Safety, 2008, 93: 125-136.

[39] Zuo MJ, Tian Z, Huang HZ. An efficient method for reliability evaluation of multistate networks given all minimal path vectors. IIE Transactions, 2007, 39: 811-817.