Project title
Efficient Routing in the Internet and other Complex Networks using Hyperbolic Metric Spaces
Funding code
ComplexNetRouting
Start date
January 3, 2011
Expected Completion
2015-01-02
Description
The lack of predictive power over complex systems, either designed by humans or evolved by nature, is a foundational problem in contemporary science. The Internet offers a paradigmatic example: nothing in its architecture and design explains its complex large-scale structure, unexpectedly discovered decades after its inception. We face an unsettling truth: the Internet has acquired emergent properties that are beyond our full understanding, much less control. As scientists, we are compelled to explore how the peculiar structure relates to the function(s) of complex networks. Many complex networks in nature share the peculiar structural character of the Internet, but they also manifest phenomenal behavior: they efficiently route information without any routing communication protocol, i.e., without any knowledge of the global network topology. This achievement is currently beyond the reach of man-made networks; the Internet still uses a 30-year old routing architecture with fundamentally unscalable overhead requirements. The only known mechanism for efficient routing without global topology knowledge is greedy routing in a network embedded in a metric space. We propose to explore the hypothesis that beneath the observable topologies of complex networks reside hidden hyperbolic metric spaces, which could be used to facilitate maximally efficient routing with scalability characteristics either equal, or close to, theoretically best possible.