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

许多新的互联网应用程序都有极其严格的可靠性和时效性限制。例如，当试图远程操纵对象时(例如在远程机器人手术中)，为了提供无缝反馈，连接需要基本上不中断并且具有最多130毫秒的延迟。实现这一点的一种方法是建立覆盖网络：战略上位于世界各地的数据中心的少量计算机，它们通过互联网相互通信，其设计方式旨在提高可靠性，同时保持及时性。该项目寻求通过选择网络的子集而不是沿最佳路径发送消息来提供及时性和可靠性，并选择具有成本效益的子集。成功地设计这种技术将使需要及时、可靠服务的应用程序得以实现，远远超出当前最先进的互联网所能提供的范围。除了实际的好处外，这项研究还将显著提高我们对覆盖网络理论和网络设计的理解：现有的算法和技术不能提供所需的强有力的保证，因此我们需要开发新的算法和新的数学工具来分析这些算法。因此，这项研究也将对网络数学和理论的发展产生重大影响。本项目将为弹性路由开发新的理论和实用的体系结构。自那以后，人们一直在为相关的随机故障下的可靠性问题设计近似算法，并针对特定的图类进行研究。然而，几乎没有关于这些问题的网络设计版本的工作，这些问题构成了该提案的理论方面。因此，这项工作的结果将是容错网络设计的重要一步。此外，拟议的研究将通过在完全现实的环境中评估在不同抽象级别下开发的解决方案，促进对如何对实际网络问题进行建模以及如何将理论解决方案转化为具体系统的理解。

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.