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.