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提供了第一个正式证明这种贪婪路由策略效率的模型。然而，克莱因伯格模型及其后续的变体处理的图拓扑与观察到的复杂网络（包括互联网）的无标度拓扑有很大的不同。该项目提出了一个新的隐藏节点上的贪婪路由模型，GROH模型，它推广了Kleinberg模型，并自然产生无标度拓扑。该模型采用了隐藏度量空间（HMS）的概念存在于每个复杂网络，包括互联网。该项目深入研究了一个假设，即复杂网络的可观察到的无标度结构是自然进化的结果，它最大限度地提高了这些HMS上贪婪路由的效率。该项目的研究议程有两个方面：（1）证明HMS的存在，从而验证GROHModel的前提;（2）建立方法来明确地为可观察的互联网拓扑结构重新构建HMS，更一般地为任何给定的复杂网络。一旦互联网的HMS被重建，人们可以使用它来提供寻址方案的更新，无限可扩展的互联网路由架构的基础上贪婪的路由策略。该项目的智力价值涉及网络、理论计算机科学、物理和数学领域的协调交叉。该项目开发了一种新颖的网络建模方法，该方法具有优雅的通用性，数学上合理，并有望解决未来大规模网络中最具挑战性的问题之一。由于互联网只是构成人类生活基本结构的许多复杂网络之一，这项工作的潜在进展是深远的。复杂网络的可导航性，即，有针对性的信息传播的效率，有一个基本关系到他们的结构。GROH模型被证明是忠实于现实的，它的基本理解也可能导致对生物、社会和语言网络的结构和功能的理解的进步。更广泛的影响：传统路由对当前网络的扩展限制的影响包括性能下降、可达性损失和高成本。 随着网络的发展，这些问题变得更加严重。 目前，运营商和企业正在尝试向IPv6过渡，以允许几乎无限的站点直接连接到Internet。 这个项目对路由解决方案空间的创新性重新审视是相关的和及时的。