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.

专家之间越来越多的共识是，路由系统正在接近一个关键的建筑断裂点。 Internet架构板试图确定限制路由可伸缩性的因素，并得出这样的结论：当前路由系统的最敏锐的尺度限制参数是路由表大小，而不是其内存要求而不是其对网络动力学的反应。鉴于最近的研究表明，没有路由算法可以在动态的互联网样图上提供合理的可伸缩性界限，这并不奇怪。这些发现提供了不祥但明确的课程：为了无限地有效地扩展，我们必须学习如何在没有拓扑更新的情况下路线。乍一看，无更新的路由似乎是不可能的，但是米尔格拉姆（Milgram）的1967年实验表明，这种路线实际上是社交网络中贪婪的搜索策略的现实。乔恩·克莱恩伯格（Jon Kleinberg）提供了第一个正式证明这种贪婪路由策略效率的模型。但是，Kleinberg模型及其随后的变体都涉及图形拓扑与观察到的复杂网络（包括Internet）的无规模拓扑截然不同。该项目提出了一种关于隐藏指标Grohmodel的贪婪路由的新模型，该模型概括了Kleinberg模型，并且自然会产生无规模的拓扑结构。该模型采用了每个复杂网络（包括Internet）背后存在的隐藏度量空间（HMS）的概念。该项目彻底研究了以下假设：复杂网络的可观察到的无标度结构是自然进化的结果，它最大程度地提高了这些HMS上贪婪路由的效率。该项目的研究议程是两个方面：（1）证明HMS的存在，从而验证了Grohmodel前提； （2）构建方法论，以明确重新构建可观察到的Internet拓扑的HMS，更普遍地用于任何给定的复杂网络。一旦重建了互联网的HMS，就可以使用它来提供基于贪婪的路由策略的无限更新，无限可扩展的互联网路由体系结构的寻址方案。该项目的智力优点涉及在网络，理论计算机科学，物理和数学领域之间进行的协同交叉施用。该项目开发了一种新颖的网络建模方法，该方法本质上是优雅的，在数学上是合理的，并有望解决未来大规模网络中最具挑战性的问题之一。由于互联网只是构成人类生活基本织物的许多复杂网络之一，因此这项工作的潜在进步是深远的。复杂网络的可通道性，即目标信息传播的效率，与它们的结构具有基本关系。被证明是对现实的忠实，对Grohmodel提出的基本理解也可能导致了解生物学，社交和语言网络的结构和功能的进步。BRODER的影响：传统Routingon当前网络的扩展限制的影响包括性能下降，损失达到性能和高成本。 随着网络的增长，这些都会恶化。 在当前，运营商和企业正在尝试过渡到IPv6，以便允许几乎无限的站点直接连接到Internet。这一过渡预计会使路由菌株恶化。 该项目对路由解决方案空间的创新重新审查是相关的。