IP fast reroute methods are used to recover packets in the data plane upon link failures. Previous work provided methods that guarantee failure recovery from at most two-link failures. We develop an IP fast reroute method that employs rooted arc-disjoint spanning trees to guarantee recovery from up to k-1 link failures in a k-edge-connected network. As arc-disjoint spanning trees may be constructed in sub-quadratic time in the size of the network, our approach offers excellent scalability. Through experimental results, we show that employing arc-disjoint spanning trees to recover from multiple failures reduces path stretch in comparison with previously known techniques.

The introduction of coherent optics and wavelength division multiplexing (WDM) in telecommunication networks has led to unprecedented gains in backbone capacity. The increase in optical layer capacity inadvertently exacerbates the problem of traffic loss due to optical component failures. IP networks are designed over optical backbone networks, where each IP link traverses a multihop optical lightpath. Therefore, the failure of optical components often lead to multiple link failures in the IP network. In this paper, we develop an IP fast reroute mechanism using rooted arc-disjoint spanning trees that guarantees recovery from (k-1) link failures in a k-edge-connected network. As arc-disjoint spanning trees may be constructed in sub-quadratic time in the size of the network, our approach offers excellent scalability. Through experimental results, we show that employing arc-disjoint spanning trees to recover from multiple failures reduces path stretch in comparison with previously known techniques.

In order to achieve resilient multipath routing, we introduce the concept of independent directed acyclic graphs (IDAGs) in this paper. Link-independent (node-independent) DAGs satisfy the property that any path from a source to the root on one DAG is link-disjoint (node-disjoint) with any path from the source to the root on the other DAG. Given a network, we develop polynomial-time algorithms to compute link-independent and node-independent DAGs. The algorithm developed in this paper: 1) provides multipath routing; 2) utilizes all possible edges; 3) guarantees recovery from single link failure; and 4) achieves all these with at most one bit per packet as overhead when routing is based on destination address and incoming edge. We show the effectiveness of the proposed IDAGs approach by comparing key performance indices to that of the independent trees and multiple pairs of independent trees techniques through extensive simulations.

This paper develops a new resilient multipath routing technique, referred to as SPT-DAG, that has the following characteristics: (1) provides multipath routing over directed acyclic graphs (DAG); (2) the shortest path tree is guaranteed to be part of the DAG; and (3) provides guaranteed recovery from single link failures. We develop polynomial time algorithm to compute the SPT-DAG and a routing protocol to forward packets over the SPT-DAG using one overhead bit in the packet. We consider different load-balancing approaches for forwarding a packet when the packet has not encountered a failure. Through extensive flow-based simulations, we show that the SPT-DAG performs significantly better than those approaches that exclusively target load balancing or resiliency.

Country risk - the likelihood that a state will weaken or fail - and the methods of assessing it continue to be of serious concern to the international community. Country risk has traditionally been assessed by monitoring economic and financial indicators. However, social media (such as forums, blogs, and websites) are now important transporters of citizens' daily conversations and opinions, and as such may carry discernible indicators of risk, but they have been as yet little-used for this task. The Geopolitical Web project is a research effort with the ultimate goal of developing computational approaches for monitoring public opinion in regions of conflict, assessing country risk indicators in the social media of fragile or weakening states, and correlating these risk signals with commonly accepted quantitative geopolitical risk assessments. This paper presents the initial motivation for this data-driven project, collection procedures adopted, preliminary results of an automated topical analysis of the collection's content, and expected future work. By catching and deciphering possible signals of country risk in social discourse we hope to offer the international community an additional means of assessing the need for intervention in or support for fragile or weakening states.

In this paper, we introduce the concept of Independent Directed Acyclic Graphs (IDAGs) to achieve resilient multipath routing. Link- independent (Node-independent) DAGs satisfy the property that any path from a source to the root on one DAG is link-disjoint (node-disjoint) with any path from the source to the root on the other DAG. Given a network, we develop polynomial time algorithms to compute link-independent and node-independent DAGs. The algorithm developed in this paper: (1) achieves multipath routing; (2) guarantees recovery from single link failure; (3) utilizes all possible edges; and (4) achieves all these with at most one bit per packet as overhead when routing is based on destination address and incoming link. We demonstrate the effectiveness of the proposed IDAGs approach by comparing key performance indices to that of the independent trees technique.