AitF: EXPL: Wide-area Dissemination under Strict Timeliness, Reliability, and Cost Constraints

Johns Hopkins University, Baltimore MD

Investigators

Abstract

Many new Internet applications have extremely strict reliability and timeliness constraints. For example, when trying to remotely manipulate an object (such as in remote robotic surgery), in order to provide seamless feedback the connection needs to be essentially uninterrupted and have delay of at most 130 ms. One way of achieving this is to build an overlay network: a small number of computers, strategically positioned in datacenters around the world, which communicate with each other over the Internet in a way designed to improve reliability while maintaining timeliness. This project seeks to provide timeliness and reliability by sending messages over a select subset of the network, rather than along the best path, and to select subsets that are cost-effective. Successfully designing such techniques will enable applications that require timely, reliable service, well beyond what the current state-of-the-art can provide over the Internet. In addition to the practical benefits, this research will also significantly improve our understanding of the theory of overlay networks and network design: existing algorithms and techniques do not give the strong guarantees that are required, so we will need to develop both new algorithms and new mathematical tools to analyze these algorithms. Hence this research will also have significant impact on the state of the art in the mathematics and theory of networking. This project will develop new theory and a practical architecture for resilient routing. There has since been extensive work on designing approximation algorithms for related reliability-under-random-faults problems, as well as studying them for specific graph classes. However, there has been almost no work on the network design versions of these problems, which form the theoretical aspects of this proposal. Thus the results of this work will be a significant step forward in fault-tolerant network design. Moreover, the proposed research will advance the understanding of how to model practical networking problems and how to translate theoretical solutions into concrete systems, by evaluating solutions developed under different levels of abstraction in a fully realistic setting.