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

Sponsor: National Science Foundation (NSF)

Award Number: 1018266

Abstract:

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.

For more information, click here.