Abstract

Background: Several techniques are available to evaluate the two-terminal reliability (2TR) of static networks; however, the advent of dynamic networks in recent past, e.g., Delay Tolerant Networks (DTNs), has made this task extremely challenging due to their peculiar characteristics with an associated disruptive operational environment. Recently, a Cartesian product-based method has been proposed to enumerate time-stamped-minimal path sets (TS-MPS)-a precursor to compute the 2TR of such networks. However, it cannot be used to generate time-stamped-minimal cut sets (TS-MCS). TS-MCS cannot only be used as an alternative to generate 2TR but also to compute other unexplored reliability metrics in DTNs, e.g., the weakest link.

Objective: To propose a novel approach to enumerate both TS-MPS and TS-MCS of a dynamic network, thereby computing the 2TR of such networks.

Methods: The proposed technique converts the time aggregated graph model of a dynamic network into a Line Graph (LG) while maintaining the time-varying graph’s node reachability information. This LG is used thereafter to generate TS-MCS as well as TS-MPS to compute 2TR of the network.

Results: The DTN examples are presented to show the efficacy and salient features of our algorithm to obtain 2TR of such networks.

Conclusion: The terminologies and techniques used for studying/analyzing network reliability of static networks can be extended to dynamic networks as well, e.g., the notion of minimal path sets to TS-MPS or minimal cut sets to TS-MCS, to assess their network reliability-a potential area of furthering network reliability research.

Keywords: Delay tolerant networks, line graph, network reliability, sum-of-disjoint-products, time-aggregated graph, timestamped- minimal cut sets, time-stamped-minimal path sets.