NeTS-FIND: Greedy Routing on Hidden Metric Spaces as a Foundation of Scalable Routing Architectures without Topology Updates

NeTS-FIND：隐藏度量空间上的贪婪路由作为无需拓扑更新的可扩展路由架构的基础

• 批准号: 0722070
• 负责人: Dmitri Krioukov
• 金额: --
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-10-01 至 2010-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0722070&HistoricalAwards=false
• 关键词: NeTS; FIND; Greedy; Routing; Hidden

A growing consensus among experts is that the routing system is approaching a critical architectural breaking point. The Internet Architecture Board has tried to identify the factors that limit routing scalability and reached the conclusion that the most acutely scale-limiting parameter of the current routing system is routing table size, not so much for its memory requirements as for its reaction to network dynamics. This conclusion is not surprising in light of recent research demonstrating that no routing algorithm can provide reasonable scalability bounds on dynamic Internet-like graphs. These findings offer the ominous but definitive lesson: to scale efficiently and indefinitely, we must learn how to route without topology updates. Updateless routing seems impossible at first glance, but Milgram's 1967 experiments showed that such routing is in fact a reality of greedy search strategies in social networks. Jon Kleinberg provided the first model formally demonstrating efficiency of such greedy routing strategies. However, both the Kleinberg model and its subsequent variations deal with graph topologies vastly different from scale-free topologies of observed complex networks, including the Internet. This project proposes a new model of Greedy Routing on Hidden Metrics, the GROHModel, which generalizes the Kleinberg model and naturally yields scale-free topologies. The model employs the concept of a hidden metric space (HMS) existing behind every complex network, including the Internet. The project thoroughly investigates the hypothesis that the observable scale-free structure of complex networks is a consequence of natural evolution that maximizes the efficiency of greedy routing on these HMSs. The research agenda of the project is two-fold: (1) demonstrate the existence of HMSs, thus validating the GROHModel premises; and (2) build methodologies to explicitly re-construct the HMS for the observable Internet topology, and more generally for any given complex network. As soon the Internet's HMS is reconstructed, one can use it to deliver addressing schemes for updateless, indefinitely scalable Internet routing architectures based on greedy routing strategies. The intellectual merit of this project involves concerted cross-fertilization across fields of networking, theoretical computer science, physics, and mathematics. The project develops a novel network modeling methodology that is elegantly generic in nature, mathematically sound, and promises a solution to one of the most challenging problems of future large-scale networking. Since the Internet is just one of many complex networks that form essential fabrics of human life, the potential advances of this work are profound. Navigability of complex networks, i.e., efficiency of targeted information propagation in them, has a fundamental relationship to their structure. Proved faithful to reality, the fundamental understanding advanced with the GROHModel may also result in advances in understanding of structure and function of biological, socialand language networks.Broader Impacts: the effects of scaling limits of conventional routingon current networks include performance drops, loss of reachability and high cost. As the networks grow, these are worsened. In present times,operators and enterprises are attempting a transition to IPv6 in orderto allow virtually limitless sites to connect directly to the Internet.This transition is expected to worsen routing strains. This project's innovative reexamination of the routing solution space is relevant andtimely.

专家们越来越一致地认为，路由系统正接近一个关键的体系结构临界点。互联网体系结构委员会试图确定限制路由可伸缩性的因素，并得出结论：当前路由系统最尖锐的规模限制参数是路由表大小，与其说是因为它的内存需求，不如说是因为它对网络动态的反应。这一结论并不令人惊讶，因为最近的研究表明，没有任何路由算法可以在动态的类似互联网的图上提供合理的可伸缩性界限。这些发现提供了不祥但明确的教训：为了高效和无限期地扩展，我们必须学会如何在没有拓扑更新的情况下进行路由。乍一看，无更新的路由似乎是不可能的，但米尔格拉姆1967年的实验表明，这种路由实际上是社交网络中贪婪搜索策略的现实。Jon Kleinberg提供了第一个模型，正式证明了这种贪婪路由策略的效率。然而，Kleinberg模型及其随后的变体处理的图形拓扑与所观察到的复杂网络(包括互联网)的无标度拓扑有很大的不同。该项目提出了一种新的基于隐藏度量的贪婪路由模型GROHModel，它推广了Kleinberg模型，自然地产生了无标度的拓扑。该模型采用了隐藏度量空间(HMS)的概念，该空间存在于包括互联网在内的每个复杂网络的背后。该项目深入研究了这样一个假设，即复杂网络的可观测无标度结构是自然进化的结果，该进化最大化了这些HMS上的贪婪路由的效率。该项目的研究议程有两个方面：(1)证明HMS的存在，从而验证GROHModel前提；(2)建立方法，为可观察到的互联网拓扑，更一般地为任何给定的复杂网络重新构建HMS。一旦互联网的HMS被重建，人们就可以使用它来提供寻址方案，以基于贪婪的路由策略为无更新、无限可扩展的互联网路由体系结构提供寻址方案。这个项目的智力价值涉及网络、理论计算机科学、物理和数学等领域的协调交叉。该项目开发了一种新的网络建模方法，该方法在本质上是优雅的通用的，在数学上是合理的，并承诺为未来大规模网络最具挑战性的问题之一提供解决方案。由于互联网只是构成人类生活基本结构的众多复杂网络之一，这项工作的潜在进展是深远的。复杂网络的通航性，即在复杂网络中定向信息传播的效率，与其结构有着根本的关系。事实证明，GROH模型提出的基本理解忠于现实，也可能导致对生物、社会和语言网络的结构和功能的理解的进步。更广泛的影响：传统路由的扩展限制对当前网络的影响包括性能下降、可达性损失和成本高昂。随着网络的发展，这些情况会变得更糟。目前，运营商和企业正在尝试过渡到IPv6，以便允许几乎无限的站点直接连接到互联网。这种过渡预计会加剧路由压力。这个项目对布线解决方案空间的创新重新审视是相关的和及时的。