Dynamic Routing, Distributed Hash Tables and Location Services

这个项目解决了动态分布式网络中的高效和可扩展的路由问题。 我们的目标是设计紧凑的路由方案（即，计划与低内存开销）与本地敏感的节点加入，离开和移动操作（即，节点移动操作的成本应该是成比例的距离节点移动）。 路由的一个重要应用是设计对象定位服务和分布式哈希表。 这项研究的新功能包括提高边界的路由路径的质量，能够有效地处理高度动态的节点操作，和容错。 此外，一个重要的目标是提供优雅的降级：如果违反或放松路由和定位方案工作的假设，则故障不应该是突然的，相反，性能只会随着假设放宽的程度而变差。互联网的发展所激发的新的计算范式导致将计算机网络本身视为计算机，并要求对分布在大规模和非结构化网络中的计算的理解，其中许多节点能够独立执行计算。 这种系统中的一个基本操作是路由：节点应该能够相互发送消息，而不必拥有关于网络的完整信息。消息应该沿着沿着有效的路由发送，并且不应该要求单个节点存储太多关于网络结构的信息。 此外，网络可以随时间改变，节点加入或离开，或者在网络内移动。 当考虑容错时，出现了额外的复杂性，因为即使存在故障，系统也必须能够继续正确地工作。 该项目将促进我们对日常生活中所依赖的网络结构的理解，提高计算机网络和应用程序的效率并减少其脆弱性，从而有助于开发和部署安全的网络应用程序和基础设施。PI在分布式对象定位方面的早期工作已经集成到现实世界的系统中。 由于该项目的重点是更现实的场景，但同样重要的问题，它很可能会导致进一步的实施和广泛适用的系统。

This project addresses the problem of efficient and scalable routing in dynamic distributed networks. The goal is to design compact routing schemes (that is, schemes with low memory overhead) with locality-sensitive node join, leave and move operations (that is, the cost of a node move operation should be proportional to the distance the node moves). An important application of routing is the design of object location services and distributed hash tables. The novel features of this research include improved bounds on the quality of routing paths, the ability to efficiently deal with highly dynamic node operations, and fault tolerance. Further, an important goal is to provide graceful degradation: if the assumptions under which the routing and location scheme works are violated or relaxed, the failure should not be abrupt, but instead the performance should worsen only as a function of the degree to which the assumptions were relaxed.New paradigms of computation motivated by the development of the Internet lead to viewing the computer network itself as a computer and require an understanding of computation distributed across a large-scale and unstructured networks, whose many nodes are capable of performing computations independently. A basic operation in such a system is routing: nodes should be able to send each other messages without necessarily having complete information about the network. The messages should be sent along efficient routes, and individual nodes should not be required to store too much information about the network structure. Further, the network may change over time, with nodes joining or leaving, or moving within the network. An additional complication arises when fault tolerance is considered, since the system must be able to continue working correctly even in the presence of faults. This project will advance our understanding of the structure of networks that we rely on in everyday life, improve the efficiency and reduce the vulnerability of computer networks and applications, thus contributing to the development and deployment of secure network applications and infrastructure. The PIs' earlier work on distributed object location has been integrated in real-world systems. Since the focus of this project is on more realistic scenarios but problems just as important, it is likely that it will lead to further implementations and systems of wide applicability.