Time-varying graphs are a useful model for networks with dynamic connectivity such as vehicular networks, yet, despite their great modeling power, many important features of time-varying graphs are still poorly understood. In this paper, we study the survivability properties of time-varying networks against unpredictable interruptions. We first show that the traditional definition of survivability is not effective in time-varying networks, and propose a new survivability framework. To evaluate the survivability of time-varying networks under the new framework, we propose two metrics that are analogous to MaxFlow and MinCut in static networks. We show that some fundamental survivability-related results such as Menger's Theorem only conditionally hold in time-varying networks. Then we analyze the complexity of computing the proposed metrics and develop several approximation algorithms. Finally, we conduct trace-driven simulations to demonstrate the application of our survivability framework to the robust design of a real-world bus communication network.
Despite the extensive research on time-varying graphs, there is very little literature on survivability of time-varying networks. The closest work to ours was done by Berman @cite_18 and Kleinberg @cite_9 . They discussed vulnerability in so-called edge-scheduled networks" or temporal networks" where each link is active for exactly one slot and only permanent failures happen. Our work considers a more general graph model while leveraging the temporal features of failures, thus generalizing their results. Scellato @cite_13 investigated a similar problem in random time-varying graphs and proposed a metric called temporal robustness". By comparison, our framework is deterministic, thus guaranteeing the worst-case survivability. Li @cite_32 studied a related but different problem in time-varying networks; specifically, they proposed heuristic algorithms to find the the min-cost subgraph of a probabilistic time-varying graph such that the probability that the subgraph is temporally connected exceeds a certain threshold.
@cite_9 @cite_18 @cite_13 @cite_32
2049706966 2093109628 2066466703
An edge-scheduled network N is a multigraph G = (V, E), where each edge e ϵ E has been assigned two real weights: a start time α(e) and a finish time β(e). Such a multigraph models a communication or transportation network. A multiedge joining vertices u and v represents a direct communication (transportation) link between u and v, and the edges of the multiedge represent potential communications (transportations) between u and v over a fixed period of time. For a, b ϵ V, and k a nonnegative integer, we say that N is k-failure ab-invulnerable for the time period [0, t] if information can be relayed from a to b within that time period, even if up to k edges are deleted, i.e., “fail.” The k-failure ab-vulnerability threshold νab(k) is the earliest time t such that N is k-failure ab-invulnerable for the time period [0, t] [where νab(k) = ∞ if no such t exists]. Let κ denote the smallest k such that νab(k) = ∞. In this paper, we present an O(κ|E|) algorithm for computing νab(i), i = 0, …, κ −1. The latter algorithm constructs a set of κ pairwise edge-disjoint schedule-conforming paths P0, …, Pκ −1 such that the finish time of Pi is νab(i), i = 0, 1, …, κ −1. (A path P = ae1u1e2 ··· Upp−1epb is schedule-conforming if the finish time of edge ei is no greater than the start time of the next edge ei + 1.) The existence of such paths when α(e) = β(e) = 0, for all e ϵ E, implies Menger's Theorem. In this paper, we also show that the obvious analogs of these results for either multiedge deletions or vertex deletions do not hold. In fact, we show that the problem of finding k schedule-conforming paths such that no two paths pass through the same vertex (multiedge) is NP-complete, even for k = 2. © 1996 John Wiley & Sons, Inc. The application of complex network models to communication systems has led to several important results: nonetheless, previous research has often neglected to take into account their temporal properties, which in many real scenarios play a pivotal role. At the same time, network robustness has come extensively under scrutiny. Understanding whether networked systems can undergo structural damage and yet perform efficiently is crucial to both their protection against failures and to the design of new applications. In spite of this, it is still unclear what type of resilience we may expect in a network which continuously changes over time. In this work, we present the first attempt to define the concept of temporal network robustness: we describe a measure of network robustness for time-varying networks and we show how it performs on different classes of random models by means of analytical and numerical evaluation. Finally, we report a case study on a real-world scenario, an opportunistic vehicular system of about 500 taxicabs, highlighting the importance of time in the evaluation of robustness. Particularly, we show how static approximation can wrongly indicate high robustness of fragile networks when adopted in mobile time-varying networks, while a temporal approach captures more accurately the system performance. Delay tolerant networks (DTNs) recently have drawn much attention from researchers due to their wide applications in various challenging environments. Previous DTN research mainly concentrates on information propagation and packet delivery. However, with possible participation of a large number of mobile devices, how to maintain efficient and dynamic topology becomes crucial. In this paper, we study the topology design problem in a predictable DTN where the time-evolving topology is known a priori or can be predicted. We model such a time-evolving network as a weighted directed space-time graph which includes both spacial and temporal information. Links inside the space-time graph are unreliable due to either the dynamic nature of wireless communications or the rough prediction of underlying human device mobility. The purpose of our reliable topology design problem is to build a sparse structure from the original space-time graph such that (1) for any pair of devices, there is a space-time path connecting them with a reliability higher than the required threshold; (2) the total cost of the structure is minimized. Such an optimization problem is NP-hard, thus we propose several heuristics which can significantly reduce the total cost of the topology while maintain the “reliable” connectivity over time. In this paper, we consider both unicast and broadcast reliability of a topology. Finally, extensive simulations are conducted on random DTNs, a synthetic space DTN, and a real-world DTN tracing data. Results demonstrate the efficiency of the proposed methods.