Efficient Routing in the Internet and other Complex Networks using Hyperbolic Metric Spaces

View Statistics Email Alert RSS Feed

Information

Primary Data

Project title

Code

ComplexNetRouting

Project Coordinator

Papadopoulos, Fragkiskos

Start date

03-01-2011

Expected Completion

02-01-2015

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.

Keyword(s)

Scientific Research

Efficient Routing in the Internet and other Complex Networks using Hyperbolic Metric Spaces

Primary Data

Description