Achieving Network Robustness with Diversity Overlay Routing

Network systems, in both wired and wireless domains, traditionally forward data along a single best routing path for communication. Given that network communication has become a major part of today's economy, it is important to guarantee the robustness of network communication toward general failures or malicious attacks. However, there are fundamental constraints on re-engineering existing network systems to use robustness mechanisms. First, network systems are not amenable to centralized solutions because they usually span multiple administrative domains. Also, it is non-trivial to modify low-layer hardware and protocols of legacy network systems to support new robustness mechanisms. To overcome the fundamental robustness challenges, we propose to adapt existing network systems into robust architectures using the concept of overlays. Layered atop the physical network, overlays provide a flexible platform for building robustness mechanisms. In particular, we seek to design distributed solutions that are amenable to nodes that can communicate with one another, but are independently operated and prefer to make local decisions on link costs and route choices. This thesis proposes to use diversity overlay routing to address two robustness problems: (1) resilient multipath routing, in which distributed algorithms are proposed to route data along multiple available network paths in order to minimize the loss of throughput due to node or link failures, and (2) network fault correction, in which an end-to-end inference approach is proposed to aggregate information from multiple paths in order to minimize the cost of diagnosing and repairing network failures. First, we develop a distributed resilient multipath solution that routes data across available network paths to improve routing resilience in wired overlay networks. Our solution allows routing decisions to be locally made by network nodes without requiring centralized information, such as the entire network topology. We devise two distributed algorithms termed the Bound-Control algorithm and the Lex-Control algorithm, with an objective of minimizing the loss of throughput due to a single-link attack. We formally prove that both algorithms converge to their respective optimal solutions. Using simulation, we show that our resilient multipath solution effectively mitigates the loss of throughput due to single-link attacks as well as multi-link attacks. We next consider the use of opportunistic routing to boost the throughput gain of routing in multi-hop wireless networks. Our goals are to overlay the 802.11 MAC layer, exploit the broadcast nature of wireless communication, and utilize the spatial diversity of a network. We consider a novel routing scheme called Stable Opportunistic Routing (SOR), which integrates the techniques of forwarder scheduling and network coding to improve the throughput gain. Using nsclick simulation, we show that SOR improves throughput when compared with traditional single-path routing and previous opportunistic routing schemes under various settings, including the scenarios where link-level measurements are inaccurate. We also verified the benefits of SOR using testbed experiments. Finally, we consider an end-to-end approach of inferring network faults in an overlay system, with an optimization goal of minimizing the expected cost of correcting (i.e., diagnosing and repairing) all faulty nodes. Conventional fault localization problems first check the most likely fault node, i.e., the node with the highest conditional failure probability given a network with faulty nodes. By taking into account the cost of correcting faulty nodes, we prove that an optimal...