Dynamic Routing, Distributed Hash Tables and Location Services

动态路由、分布式哈希表和位置服务

• 批准号: 0830791
• 负责人: Andrea Richa
• 金额: --
• 依托单位: Arizona State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2011-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830791&HistoricalAwards=false
• 关键词: Dynamic; Routing; Distributed; Hash; Tables

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.

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