Assessing reliability within error rate and time constraint for a stochastic node-imperfect computer network

Abstract

In order to maintain the stability of a computer network, the assessment of system reliability is an important issue for the supervisor. A computer network can be modeled as a network topology with edges and nodes, in which each edge denotes a transmission line such as coaxial cables or fiber cables, and each node denotes a transmission station such as router or switch. For a real-life computer network, the capacity of each component (edge or node) should be stochastic owing to complete failure, partial failure, etc. Hence, the computer network with imperfect components is also stochastic and is named a stochastic node-imperfect computer network. Different from the quickest path problem considering deterministic capacity, this article concentrates on a stochastic node-imperfect computer network to evaluate the probability that d units of data can be transmitted within tolerable error rate and time constraint. Such a probability, called system reliability, is a performance indicator to provide to managers for further improvement. An efficient algorithm in terms of the approach of minimal paths to evaluate the system reliability is proposed.

Keywords

System reliability imperfect nodes tolerable error rate stochastic capacity time constraint

Get full access to this article

View all access options for this article.

References

Carrigy

Ramirez-Marquez

Rocco

. Multistate stochastic network interdiction via reliability modelling and evolutionary optimization. Proc IMechE, Part O: J Risk and Reliability 2010; 224(1): 27–42.

Rocco

Ramirez-Marquez

Salazar

. Implementation of multi-objective optimization for vulnerability analysis of complex networks. Proc IMechE, Part O: J Risk and Reliability 2010; 224(2): 87–95.

Aven

. Reliability evaluation of multistate systems with multistate components. IEEE Trans Reliab 1985; 34(5): 473–479.

Lin

. A simple algorithm for reliability evaluation of a stochastic-flow network with node failure. Comput Oper Res 2001; 28(13): 1277–1285.

Lin

. Reliability of a stochastic-flow network with unreliable branches & nodes under budget constraints. IEEE Trans Reliab 2004; 53(3): 381–387.

Lin

. Reliability evaluation for an information network with node failure under cost constraint. IEEE Trans Syst Man Cybern Part A: Syst Hum 2007; 37(2): 180–188.

Lin

. On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint. Eur J Oper Res 2007; 176(1): 347–360.

Levitin

Lisnianski

. A new approach to solving problems of multi-state system reliability optimization. Qual Reliab Eng Int 2001; 17(2): 93–104.

Lin

Jane

Yuan

. On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Network 1995; 25(3): 131–138.

10.

Lin

. Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network. Comput Oper Res 2003; 30(4): 567–575.

11.

Lin

. Time version of the shortest path problem in a stochastic-flow network. J Comput Appl Math 2009; 228(1): 150–157.

12.

Xue

. On multistate system analysis. IEEE Trans Reliab 1985; 34(4): 329–337.

13.

Yeh

. Multistate network reliability evaluation under the maintenance cost constraints. Int J Prod Econ 2004; 88(1): 73–83.

14.

Yeh

. A new approach to evaluating reliability of multistate networks under the cost constraint. Omega 2005; 33(3): 203–209.

15.

Chen

Chin

. The quickest path problem. Comput Oper Res 1990; 17(2): 153–161.

16.

Chen

Hung

. On the quickest path problem. Inf Process Lett 1993; 46(3): 125–128.

17.

Chen

Hung

. Algorithms for the constrained quickest path problem and the enumeration of quickest paths. Comput Oper Res 1994; 21(2): 113–118.

18.

Chen

. Finding the k quickest simples paths in a network. Inf Process Lett 1994; 50(2): 89–92.

19.

Chen

Tang

. Minimum time paths in a network with mixed time constraints. Comput Oper Res 1998; 25(10): 793–805.

20.

Clímaco

JCN

Pascoal

MMB

Craveirinha

JMF

. Internet packet routing: application of a K-quickest path algorithm. Eur J Oper Res 2007; 181(3): 1045–1054.

21.

Lee

Papadopoulou

. The all-pairs quickest path problem. Inf Process Lett 1993; 45(2): 261–267.

22.

Park

Lee

Park

. A label-setting algorithm for finding a quickest path. Comput Oper Res 2004; 31(14): 2405–2418.

23.

Postel

. RFC 768: User datagram protocol. Internet Engineering Task Force, August 1980.

24.

Amer

. A measurement center for the NBS local area computer network. IEEE Trans Comput 1982; 31(8): 723–729.

25.

Jain

Routhier

. Packet trains: measurements and a new model for computer network traffic. IEEE J Sel Areas Commun 1986; 4(6): 986–995.

26.

Mori

Takine

Pan

. Identifying heavy-hitter flows from sampled flow statistics. IEICE Trans Commun 2007; 90(11): 3061–3072.

27.

Feldmann

Greenberg

Reingold

. Deriving traffic demands for operational IP networks: Methodology and experience. IEEE-ACM Trans Netw 2001; 9(3): 265–279.

28.

Zuo

Tian

Huang

. An efficient method for reliability evaluation of multistate networks given all minimal path vectors. IIE Trans 2007; 39(8): 811–817.

29.

Al-Ghanim

. A heuristic technique for generating minimal paths and cutsets of a general network. Comput Ind Eng 1999; 36(1): 45–55.

30.

Kobayashi

Yamamoto

. A new algorithm in enumerating all minimal paths in a sparse network. Reliab Eng Syst Saf 1999; 65(1): 11–15.