NeTS: Small: New Directions in Network Dimensionality Reduction for Routing and Beyond

NeTS：小：路由及其他网络降维的新方向

• 批准号: 1018266
• 负责人: Mark Crovella
• 金额: $ 45万
• 依托单位: Trustees of Boston University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-07-01 至 2014-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1018266&HistoricalAwards=false
• 关键词: NeTS; Small; New; Directions; Network

Many important problems in computer networking depend on the observed properties of network graphs --- graphs obtained by measuring real network. These include networks of routers, autonomous systems, wireless nodes, and social relationships. Unfortunately, despite the explosion of detailed data now available, such graphs are still poorly understood, in part because of the high dimensionality of graph data. The project is developing new methods for, and applications of, dimensionality reduction of network graphs. The starting point is recent work by illustrating the power of hyperbolic geometry for the problem. Accordingly, the project has three goals: developing new methods for dimensionality reduction by embedding network graphs in hyperbolic spaces; discovering the applicability of hyperbolic embedding for a wide range of network graphs; and applying hyperbolic embedding to address practical networking questions. Among the problems being investigated is finding new methods for routing that combine the simplicity of greedy routing with the desirable properties of high success rate and efficiency of paths. The project's results will create unique software tools for the community, facilitating research in this area by others; it will shed new light on the properties of graphs that are important to networking; and it will develop new methods for routing that may be used in future networks. This project will provide training for two graduate students and its results will be disseminated in the form of both publications and freely distributed software.

计算机网络中的许多重要问题取决于网络图的观察属性——通过测量真实网络获得的图。 其中包括路由器网络、自治系统、无线节点和社会关系。 不幸的是，尽管现在可用的详细数据激增，但人们对此类图的理解仍然很少，部分原因是图数据的高维性。 该项目正在开发网络图降维的新方法和应用。起点是最近的工作，通过说明双曲几何解决该问题的力量。 因此，该项目有三个目标：通过在双曲空间中嵌入网络图来开发降维的新方法；发现双曲嵌入对于各种网络图的适用性；并应用双曲嵌入来解决实际的网络问题。 正在研究的问题之一是寻找新的路由方法，将贪婪路由的简单性与高成功率和路径效率的理想特性结合起来。该项目的成果将为社区创建独特的软件工具，促进其他人在该领域的研究；它将为对网络重要的图的属性提供新的认识；它将开发可用于未来网络的新路由方法。 该项目将为两名研究生提供培训，其结果将以出版物和免费分发软件的形式传播。