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

Héctor Cancela and Louis Petingi

Omega, 2007, vol. 35, issue 6, 659-670

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).

Keywords: Reliability; Networks; Diameter; Domination (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305-0483(06)00055-7
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:35:y:2007:i:6:p:659-670

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().