IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v35y2007i6p659-670.html
   My bibliography  Save this article

Properties of a generalized source-to-all-terminal network reliability model with diameter constraints

Author

Listed:
  • Cancela, Héctor
  • Petingi, Louis

Abstract

Given the pervasive nature of computer and communication networks, many paradigms have been used to study their properties and performances. In particular, reliability models based on topological properties can adequately represent the network capacity to survive failures of its components. Classical reliability models are based on the existence of end-to-end paths between network nodes, not taking into account the length of these paths; for many applications, this is inadequate, because the connection will only be established or attain the required quality if the distance between the connecting nodes does not exceed a given value. An alternative topological reliability model is the diameter-constrained reliability of a network; this measure considers not only the underlying topology, but also imposes a bound on the diameter, which is the maximum distance between the nodes of the network. In this work, we study in particular the case where we want to model the connection between a source-vertex s and a set of terminal vertices K (for example, a video multicast application), using a directed graph (digraph) for representing the topology of the network with node set V. If the s,K-diameter is the maximum distance between s and any of vertices of K, the diameter-constrained s,K-terminal reliability of a network G, Rs,K(G,D), is defined as the probability that surviving arcs span a subgraph whose s,K-diameter does not exceed D. One of the tools successfully employed in the study of classical reliability models is the domination of a graph, which was introduced by Satyanarayana and Prabhakar. In this paper we introduce a definition and a full characterization of the domination in the case of the diameter-constrained s,K-terminal reliability when K=V, including the classical source-to-all-terminal reliability domination result as a specific case. Moreover we use these results to present an algorithm for the evaluation of the diameter-constrained s,V-terminal reliability Rs,V(G,D).

Suggested Citation

  • Cancela, Héctor & Petingi, Louis, 2007. "Properties of a generalized source-to-all-terminal network reliability model with diameter constraints," Omega, Elsevier, vol. 35(6), pages 659-670, December.
    • Handle: RePEc:eee:jomega:v:35:y:2007:i:6:p:659-670
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305-0483(06)00055-7
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Michael O. Ball, 1979. "Computing Network Reliability," Operations Research, INFORMS, vol. 27(4), pages 823-838, August.
    2. Avinash Agrawal & Richard E. Barlow, 1984. "A Survey of Network Reliability and Domination Theory," Operations Research, INFORMS, vol. 32(3), pages 478-492, June.
    3. BALL, Michael O., 1979. "Computing network reliability," LIDAM Reprints CORE 377, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Yeh, Wei-Chang, 2005. "A new approach to evaluate reliability of multistate networks under the cost constraint," Omega, Elsevier, vol. 33(3), pages 203-209, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Bigatti, A.M. & Pascual-Ortigosa, P. & Sáenz-de-Cabezón, E., 2021. "A C++ class for multi-state algebraic reliability computations," Reliability Engineering and System Safety, Elsevier, vol. 213(C).
    2. Hougaard, Jens Leth & Moulin, Hervé, 2014. "Sharing the cost of redundant items," Games and Economic Behavior, Elsevier, vol. 87(C), pages 339-352.
    3. Jane, Chin-Chia & Laih, Yih-Wenn, 2010. "A dynamic bounding algorithm for approximating multi-state two-terminal reliability," European Journal of Operational Research, Elsevier, vol. 205(3), pages 625-637, September.
    4. Jun, Tackseung & Kim, Jeong-Yoo, 2007. "Connectivity, stability and efficiency in a network as an information flow," Mathematical Social Sciences, Elsevier, vol. 53(3), pages 314-331, May.
    5. Lawrence V. Snyder & Mark S. Daskin, 2005. "Reliability Models for Facility Location: The Expected Failure Cost Case," Transportation Science, INFORMS, vol. 39(3), pages 400-416, August.
    6. Jens Leth Hougaard & Hervé Moulin, 2018. "Sharing the cost of risky projects," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 65(3), pages 663-679, May.
    7. Liu, Xiaohang & Zheng, Shansuo & Wu, Xinxia & Chen, Dianxin & He, Jinchuan, 2021. "Research on a seismic connectivity reliability model of power systems based on the quasi-Monte Carlo method," Reliability Engineering and System Safety, Elsevier, vol. 215(C).
    8. Zhang, Chi & Ramirez-Marquez, José Emmanuel & Wang, Jianhui, 2015. "Critical infrastructure protection using secrecy – A discrete simultaneous game," European Journal of Operational Research, Elsevier, vol. 242(1), pages 212-221.
    9. Zarezadeh, S. & Asadi, M. & Balakrishnan, N., 2014. "Dynamic network reliability modeling under nonhomogeneous Poisson processes," European Journal of Operational Research, Elsevier, vol. 232(3), pages 561-571.
    10. Ramirez-Marquez, Jose E. & Rocco, Claudio M. & Gebre, Bethel A. & Coit, David W. & Tortorella, Michael, 2006. "New insights on multi-state component criticality and importance," Reliability Engineering and System Safety, Elsevier, vol. 91(8), pages 894-904.
    11. Chi Zhang & Jose Ramirez-Marquez, 2013. "Protecting critical infrastructures against intentional attacks: a two-stage game with incomplete information," IISE Transactions, Taylor & Francis Journals, vol. 45(3), pages 244-258.
    12. Kozyra, Paweł Marcin, 2023. "The usefulness of (d,b)-MCs and (d,b)-MPs in network reliability evaluation under delivery or maintenance cost constraints," Reliability Engineering and System Safety, Elsevier, vol. 234(C).
    13. Yi-Kuei Lin & Cheng-Fu Huang, 2013. "Assessing reliability within error rate and time constraint for a stochastic node-imperfect computer network," Journal of Risk and Reliability, , vol. 227(1), pages 80-85, February.
    14. Yi-Kuei Lin & Thi-Phuong Nguyen & Louis Cheng-Lu Yeng, 2019. "Reliability evaluation of a multi-state air transportation network meeting multiple travel demands," Annals of Operations Research, Springer, vol. 277(1), pages 63-82, June.
    15. Lin, Yi-Kuei, 2007. "Reliability of a computer network in case capacity weight varying with arcs, nodes and types of commodity," Reliability Engineering and System Safety, Elsevier, vol. 92(5), pages 646-652.
    16. Navarro, Jorge & Rychlik, Tomasz, 2010. "Comparisons and bounds for expected lifetimes of reliability systems," European Journal of Operational Research, Elsevier, vol. 207(1), pages 309-317, November.
    17. Lin, Yi-Kuei, 2010. "A stochastic model to study the system capacity for supply chains in terms of minimal cuts," International Journal of Production Economics, Elsevier, vol. 124(1), pages 181-187, March.
    18. Yi-Kuei Lin & Cheng-Fu Huang, 2016. "Reliability evaluation according to a routing scheme for multi-state computer networks under assured accuracy rate," Annals of Operations Research, Springer, vol. 244(1), pages 221-240, September.
    19. Lin, Yi-Kuei & Yeh, Cheng-Ta, 2012. "Determining the optimal double-component assignment for a stochastic computer network," Omega, Elsevier, vol. 40(1), pages 120-130, January.
    20. Lin, Yi-Kuei, 2007. "Performance evaluation for the logistics system in case that capacity weight varies from arcs and types of commodity," International Journal of Production Economics, Elsevier, vol. 107(2), pages 572-580, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:jomega:v:35:y:2007:i:6:p:659-670. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.