A major concern in IP networks is to ensure that any topology changes, whether planned or unplanned, do not disrupt network performance. IP Fast Reroute (IP FRR) is a general approach to address this issue by promptly forwarding an IP packet to a predetermined alternate next-hop as soon as the primary next-hop to the destination becomes unavailable. Among the numerous IP FRR schemes proposed to date, the simplest ones do not guarantee protection against every component failure, while more sophisticated ones tend to be difficult to implement due to various inherent complexities, such as nontrivial modifications of IP packets or high resource requirements. This paper presents a simple and efficient IP FRR scheme called DisPath, which leverages several fundamental properties of minimum-cost node-disjoint paths for determining the alternate next-hop toward a given destination. We show that DisPath ensures full coverage, meaning protection against all single link or node failures, with low computational overhead and without the practical complications encountered by other schemes that offer the same level of protection. Our simulations on several realistic instances reveal that DisPath usually creates shorter (and, at worst, not much longer) alternative paths than existing solutions adopted by the industry. Combined with the aforementioned protection guarantee and simplicity of implementation, these results provide strong evidence that DisPath is a most compelling choice of IP FRR scheme.

Reliable delivery of network services is critically for numerous real-time applications, such as video conferencing, broadcast TV and content distribution, in which time sensitive content is delivered to a single or multiple destinations. Failure protection in connection-oriented networks can be realized using local protection schemes, such as fast reroute (FRR), or using end-to-end protection schemes, like redundant trees. In this paper we study the trade-offs between local and end-to-end protection schemes from several key aspects such as protection availability, management complexity and in particular the resource reservation efficiency of the two approaches.

We propose a computationally efficient link-coloring based scheme that facilitates end-to-end protection for dynamic multicast and unicast connections. For a given source node, links are colored as red or blue such that, for any destination node, the red and blue paths are guaranteed to be node disjoint. Red and blue trees, constructed using only the red and blue links, respectively, always form redundant trees (RTs) independent of the used tree selection method. RTs connect the source of a multicast connection to all its destinations in such a way that in the event of a single link or node failure in the network, every destination is still connected to the source in at least one of the two trees. In network topologies where such RTs cannot be constructed due to lack of required path diversity, our scheme constructs two multicast trees such that the red and blue paths to any destination node only share cut links or nodes. To our knowledge, our scheme is the first that can construct such RTs. Although finding the optimal RTs is known to be NP-complete, extensive simulations show that our scheme calculates near optimal RTs and substantially outperforms other solutions.

A major concern in IP networks is to ensure that any topology changes, whether planned or unplanned, do not disrupt network performance. IP Fast Reroute (IP FRR) is a general approach to address this issue, by promptly forwarding an IP packet to a predetermined alternate next hop as soon as the primary next hop to the destination becomes unavailable. Among the numerous IP FRR schemes proposed to date, the simplest ones do not guarantee protection against every component failure, while more sophisticated ones tend to be difficult to implement due to various inherent complexities, such as nontrivial modifications of IP packets or high resource requirements.

Multicast is getting increasingly popular to support critical business services such as IPTV, video conferencing and content distribution. To meet the stringent availability requirements, a highly fault resilient multicast infrastructure is critically important. Redundant Steiner trees (RST) are one mechanism for realizing such infrastructure. RSTs are a pair of Steiner trees that ensure that for any single link or node failure in the network, every destination node of a multicast connection is reachable from the source on at least one of these two trees. In this paper, we consider the problem of constructing optimal RSTs in a directed graph, which is NP-complete. In light of this, we propose a simple and efficient scheme to construct near-optimal RSTs. The scheme ensures an approximation ratio of 2k for general directed graphs, where k denotes the number of destination nodes. We compare the performance of our scheme with an linear program (LP) formulation of the problem that provides a lower bound on the optimal solution. Our simulations illustrate that our scheme constructs near optimal RSTs independent of the number of destination nodes and significantly outperforms other approaches proposed in prior literature.

We show that existing methods for primary-backup replication may disrupt the timing behavior of an underlying service to the extent of making it unusable. We prove that the problem is inherent to the primary-backup model.

Channel zapping is the act of changing from one television channel to another. Zap response time is the time it takes for the new TV channel to start playing from the time a request to zap to that channel occurs. In digital TV systems such as IPTV where TV channel content is transported as an MPEG-2 or MPEG-4 data stream encapsulated in IP packets, zap response time is a significant concern. This is due to the requirement that for an MPEG stream, which is a series of groups of pictures (GOPs), playout can only start at the beginning of a GOP. The time between the occurrence of a zap event to the time to the beginning of the next GOP, which can be anywhere from less than a second to a few seconds, is a significant contributor to zap response time. It is widely accepted that such large zap response times can significantly hamper IPTV quality of experience (QoE) and an efficient solution to this problem is therefore a business imperative. Existing solutions to this problem are bandwidth inefficient either on the last mile, or within the video distribution network, or both. We present a novel solution that is significantly efficient in terms of bandwidth utilization and zap response time. We derive and present the theoretical bounds for our solution and quantitatively demonstrate the properties of our solution through results from extensive simulations.

In this paper, we consider the problem of protection of multicast connections against single link or node failures using redundant multicast trees (RMTs). RMTs connect the source node of a multicast connection to all its destinations in such a way that in the event of a single link or node failure in the network, every destination node is still connected to the source node in at least one of the two trees. Construction of RMTs has been studied extensively for undirected graphs, but not for directed graphs. Computing RMTs in directed graphs can be important in networks, for instance, where link capacity is available in one direction but not the other. Also, none of the schemes proposed in previous work provide a solution for finding optimal (minimal-cost) RMTs even for weighted undirected graphs. We show that a whole class of earlier schemes that are based on the concept of ear-decomposition cannot find optimal redundant trees in certain network topologies. To our knowledge, we are the first to consider the problem of finding optimal RMTs in directed graphs. We present a novel efficient scheme for construction of optimal RMTs in networks modeled as weighted undirected as well as directed graphs.

We present a method for selecting test sequences for concurrent programs from labeled transitions systems (LTS). A common approach to selecting test sequences from a set of LTSs is to derive a global LTS, called the reachability graph, and then force deterministic program executions according to paths selected from the graph. However, using a reachability graph for test path selection introduces a state explosion problem. To overcome this problem, a reduced graph can be generated using incremental reachability analysis, which consists of repeatedly generating a reachability graph for a subset of LTSs, reducing this graph, and using the reduced graph in place of the original LTSs. Unfortunately, existing incremental reachability analysis techniques generate reduced graphs with insufficient information for deterministic testing. We present an incremental approach to testing concurrent programs. Incremental testing consists of incremental reachability analysis for test path selection and deterministic testing for test execution. We define a new type of reachability graph for incremental analysis, called an annotated labeled transition system (ALTS). An ALTS is an LTS annotated with information necessary for deterministic testing. We propose practical coverage criteria for selecting tests paths from an ALTS and present an ALTS reduction algorithm. The results of several case studies are reported.

Structural testing of a concurrent program P involves the selection of paths of P according to a structure-based criterion. A common approach is to derive the reachability graph (RG) of P, select a set of paths of P, derive one or more inputs for each selected path, and force deterministic executions of P according to the selected paths and their inputs. The use of RG(P) for test path selection has the state explosion problem, since the number of states of RG(P) is an exponential function of the number of processes in P.In this paper, we present a new incremental approach to structural testing of P. Based on the hierarchy of processes in P, our incremental testing approach is to integrate processes in P in a bottom-to-top manner. When a set S of processes in P at the same level are integrated, we construct a reduced RG for S such that the reduced RG contains all synchronizations involving the processes in S and some of the synchronizations involving processes at lower levels in order to connect synchronizations involving processes in S. Based on the reduced RG for S, we can select test paths to focus on the detection of interface faults involving processes in S. After the selection of paths, RG(S) is further reduced in order to retain only some of the synchronizations involving processes in S that are needed in order to connect synchronizations between S and other processes in P. Our incremental approach alleviates the state explosion problem and offers other advantages.

The authors present an incremental strategy for reachability analysis of communication protocols modeled as sets of communicating finite state machines (CFSMs) with synchronous communication and direct naming. A set of CFSMs is organized into a hierarchy. The authors present an algorithm that, for a given hierarchy of a set M of CFSMs, incrementally composes and reduces subsets of CFSMs in M and finally produces a minimum CFSM describing the external behavior of M. It is also showed that this incremental reachability analysis guarantees the detection of global deadlocks. An algorithm for selecting a hierarchy for a set of CFSMs and some empirical results are provided.>