Abstract
This chapter presents design of reliable networks. The exact calculation of any general network reliability measure is NP-hard. Therefore, network designers have been reluctant to use reliability as a design criterion. However, reliability is becoming an important concern to provide continuous service quality to network customers. The chapter discusses various network reliability measures and efficient techniques to evaluate them. Two genetic algorithms are presented to demonstrate how these techniques to estimate and compute network reliability can be incorporated within an optimization algorithm. Computational experiments show that the proposed approaches significantly reduce computational effort without compromising design quality.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Bibliography
H.M. Aboelfotoh and C.J. Colbourn. Series-parallel bounds for the two-terminal reliability problem. ORSA Journal on Computing, 1(4):209–22, 1989.
H.M.F. AboElFotoh and L.S. Al-Sumait. A neural approach to topological optimization of communication networks, with reliability constraints. IEEE Transactions on Reliability, 50(4):397–408, 2001.
K.K. Aggarwal, Y.C. Chopra, and J.S. Bajwa. Topological layout of links for optimising the overall reliability in a computer communication system. Microelectronics and Reliability, 22(3):347–51, 1982a.
K.K. Aggarwal, Y.C. Chopra, and J.S. Bajwa. Topological layout of links for optimizing the s-t reliability in a computer communication system. Microelectronics and Reliability, 22(3):341–5, 1982b.
A. Balakrishnan, T.L. Magnanti, and P. Mirchandani. Designing hierarchical survivable networks. Operations Research, 46(1):116–36, 1998.
M.O. Bali. Computing network reliability. Operations Research, 27:823–38, 1979.
M.O. Ball. Complexity of network reliability computations. Networks, 10(2): 153–65, 1980.
M.O. Ball, C.J. Colbourn, and J.S. Provan. Network reliability, volume 7 of Handbooks in Operations Research and Management Science, pages 673–672. Elsevier Science B.V., Amsterdam, 1995.
M.O. Ball and G.L. Nemhauser. Matroids and a reliability analysis problem. Mathematics of Operations Research, 4(2):132–43, 1979.
M.O. Ball and J.S. Provan. Calculating bounds on reachability and connectedness in stochastic networks. Networks, 13(2):253–78, 1983.
M.O. Ball and R. Van Slyke. Backtracking algorithms for network reliability analysis. Discrete Applied Mathematics, 1:49–64, 1977.
S.G. Belovich. A design technique for reliable networks under a nonuniform traffic distribution. IEEE Transactions on Reliability, 44(3):377–87, 1995.
T.B. Brecht and C.J. Colbourn. Lower bounds on two-terminal network reliability. Discrete Applied Mathematics, 21(3):185–98, 1988.
D.W. Coit and A.E. Smith. Penalty guided genetic search for reliability design optimization. Computers and Industrial Engineering, 30(4):895–904, 1996.
D.W. Coit, A.E. Smith, and D.M. Tate. Adaptive penalty methods for genetic optimization of constrained combinatorial problems. INFORMS Journal on Computing, 8(2): 173–82, 1996.
C.J. Colbourn. Combinatorics of network reliability. Oxford, New York, NY, USA, 1987.
D.L. Deeter and A.E. Smith. Economic design of reliable networks. IIE Transactions, 30(12): 1161–74, 1998.
J. deMercado, N. Spyratos, and B.A. Bowen. A method for calculation of network reliability. IEEE Transactions on Reliability, R25(2):71–6, 1976.
B. Dengiz, F. Altiparmak, and A.E. Smith. Efficient optimization of all-terminal reliable networks, using an evolutionary approach. IEEE Transactions on Reliability, 46(1): 18–26, 1997a.
B. Dengiz, F. Altiparmak, and A.E. Smith. Local search genetic algorithm for optimal design of reliable networks. IEEE Transactions on Evolutionary Computation, 1(3): 179–88, 1997b.
M.C. Easton and C.K. Wong. Sequential destruction method for monte carlo evaluation of system reliability. IEEE Transactions on Reliability, R-29(1):27–32, 1980.
T. Elperin, I. Gertsbakh, and M. Lomonosov. Estimation of network reliability using graph evolution models. IEEE Transactions on Reliability, 40(5):572–81, 1991.
G.S. Fishman. A comparison of four monte carlo methods for estimating the probability of s-t connectedness. IEEE Transactions on Reliability, R-35(2):145–55, 1986a.
G.S. Fishman. A monte carlo sampling plan for estimating network reliability. Operations Research, 34(4):581–94, 1986b.
J.N. Hagstrom. Using the decomposition tree for directed-network reliability computation. IEEE Transactions on Reliability, R-33(5):390–5, 1984.
Rong-Hong Jan. Design of reliable networks. Computers and Operations Research, 20(1):25–34, 1993.
Rong-Hong Jan, Fung-Jen Hwang, and Sheng-Tzong Chen. Topological optimization of a communication network subject to a reliability constraint. IEEE Transactions on Reliability, 42(1):63–70, 1993.
H. Kumamoto, K. Tanaka, and K. Inoue. Efficient evaluation of system reliability by monte carlo method. IEEE Transactions on Reliability, R-26(5):311–15, 1977.
H. Kumamoto, K. Tanaka, K. Inoue, and E.J. Henley. Dagger-sampling monte carlo for system unavailability evaluation. IEEE Transactions on Reliability, R-29(2): 122–5, 1980.
A. Kumar, R.M. Pathak, and Y.P. Gupta. Genetic-algorithm-based reliability optimization for computer network expansion. IEEE Transactions on Reliability, 44(1):63–72, 1995a.
A. Kumar, R.M. Pathak, Y.P. Gupta, and H.R. Parsaei. A genetic algorithm for distributed system topology design. Computers and Industrial Engineering, 28(3): 659–70, 1995b.
Y.F. Lam and V.O.K. Li. An improved algorithm for performance analysis of networks with unreliable components. IEEE Transactions on Communications, COM-34(5): 496–7, 1986.
V.O.K. Li and J.A. Silvester. Performance analysis of networks with unreliable components. IEEE Transactions on Communications, COM-32(10):1105–10, 1984.
M.V. Lomonosov and V.P. Polesskii. Lower bound of network reliability. Problemy Peredachi Informatsii, 8(2): 118–23, 1972.
M. Mazumdar, D.W. Coit, and K. McBride. A highly efficient monte carlo method for assessment of system reliability based on a markov model. American Journal of Mathematical and Management Sciences, 19(1–2): 115–33, 1999.
C.L. Monma and D.F. Shallcross. Methods for designing communications networks with certain two-connected survivability constraints. Operations Research, 37(4): 531–41, 1989.
L.B. Page and J.E. Perry. A note on computing environments and network reliability. Microelectronics and Reliability, 31(1): 185–6, 1991.
J.S. Provan and M.O. Ball. Computing network reliability in time polynomial in the number of cuts. Operations Research, 32(3):516–26, 1984.
L.I.P. Resende. Implementation of a factoring algorithm for reliability evaluation of undirected networks. IEEE Transactions on Reliability, 37(5):462–8, 1988.
M.G.C. Resende. A program for reliability evaluation of undirected networks via polygon-to-chain reductions. IEEE Transactions on Reliability, R-35(1):24–9, 1986.
B. Sanso, M. Gendreau, and F. Soumis. An algorithm for network dimensioning under reliability considerations. Annals of Operations Research, 36(1–4):263–74, 1992.
A. Satyanarayana and M.K. Chang. Network reliability and the factoring theorem. Networks, 13(1):107–20, 1983.
A. Satyanarayana and A. Prabhakar. New topological formula and rapid algorithm for reliability analysis of complex networks. IEEE Transactions on Reliability, R27(2): 82–100, 1978.
B. Singh and S.K. Ghosh. Network reliability evaluation by decomposition. Microelectronics and Reliability, 34(5):925–7, 1994.
R. Van Slyke and H. Frank. Network reliability analysis. i. Networks, 1(3):279–90, 1972.
C. Srivaree-ratana, A. Konak, and A.E. Smith. Estimation of all-terminal network reliability using an artificial neural network. Computers and Operations Research, 29(7):849–68, 2002.
C.-L. Yang and P. Kubat. Efficient computation of most probably states for communication networks with multimode components. IEEE Transactions on Communications, 37(5):535–8, 1989.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer Science+Business Media, Inc.
About this chapter
Cite this chapter
Konak, A., Smith, A.E. (2006). Network Reliability Optimization. In: Resende, M.G.C., Pardalos, P.M. (eds) Handbook of Optimization in Telecommunications. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-30165-5_26
Download citation
DOI: https://doi.org/10.1007/978-0-387-30165-5_26
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-30662-9
Online ISBN: 978-0-387-30165-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)