Sustaining the Internet with Hyperbolic Mapping

Marian Boguna; Fragkiskos Papadopoulos; Dmitri Krioukov

Source-linked AI summary

Sustaining the Internet with Hyperbolic Mapping

Marian Boguna, Fragkiskos Papadopoulos, Dmitri Krioukov

arXiv:1009.0267v2Sep 1, 2010cs.NIcond-mat.dis-nncond-mat.stat-mechcs.SIphysics.soc-ph

TL;DR

The Internet’s growth makes globally distributed routing information increasingly costly. This paper infers hyperbolic coordinates for Autonomous Systems and uses them to guide greedy forwarding, achieving high routing success and map patterns aligned with the model and geopolitical structure.

Problem
Global topology knowledge creates growing routing overheads as the Internet expands, challenging the scalability of existing routing architecture.
Method
The paper uses statistical inference to assign each AS radial and angular coordinates in a hyperbolic space, maximizing likelihood with a scalable degree-thresholded optimization strategy.
Results
97% success ratio is achieved by simple greedy forwarding on the Internet map, while sophisticated greedy forwarding can reach 100%.
Takeaways & Limitations
The released map supports routing with information proportional to AS degree and no routing-information exchange after dynamic topology changes.

Abstract

from arXiv · show

The Internet infrastructure is severely stressed. Rapidly growing overheads associated with the primary function of the Internet---routing information packets between any two computers in the world---cause concerns among Internet experts that the existing Internet routing architecture may not sustain even another decade. Here we present a method to map the Internet to a hyperbolic space. Guided with the constructed map, which we release with this paper, Internet routing exhibits scaling properties close to theoretically best possible, thus resolving serious scaling limitations that the Internet faces today. Besides this immediate practical viability, our network mapping method can provide a different perspective on the community structure in complex networks.

I. INTRODUCTION

The Internet’s rapid growth makes globally distributed topology knowledge increasingly costly for routing, motivating a geographic-like hyperbolic map. The paper presents statistical inference of AS coordinates so greedy forwarding can avoid per-destination routing information and support scalable routing.

The number of Autonomous Systems grows by approximately 2,400 per year, while routing must continually recompute paths using global Internet topology.
Current routing scales poorly because every AS must maintain current global topology information and process updates for all possible destinations.
Growing Internet size and dynamics create rapidly increasing routing overheads, raising concerns that the existing architecture may not sustain another decade.
Greedy forwarding requires only neighbor coordinates, avoids per-destination information, and keeps coordinates unchanged when the topology changes.
The paper infers hyperbolic coordinates for each AS, targeting efficient and robust greedy forwarding while revealing geographically and politically close AS communities.

II. THE MODEL

The model combines node geometry with heterogeneous expected degrees by representing Internet-like networks in negatively curved hyperbolic space. Exponential area growth and distance-dependent connectivity jointly produce scale-free topology.

A spherical or circular geometric model with uniformly distributed nodes fails to capture the Internet’s scale-free degree distribution.
The Newtonian model connects nodes using distance rescaled by the product of their expected degrees, combining geometric distance with topological degree.
The Einsteinian model transforms node degrees into geometric coordinates, making the network purely geometric in negatively curved hyperbolic space.
Hyperbolic disc area grows as A(r) ∼e^r, so uniformly distributed nodes have Euclidean density that increases exponentially with distance from the center.
The connection probability depends on hyperbolic distance, disc radius, and temperature; increasing node density and decreasing average degree together yield a power-law degree distribution.
The Poincaré disc tessellation in Fig. 1 illustrates hyperbolic space’s exponential expansion using equal-sized figures placed on the hyperbolic floor.

III. THE MAPPING METHOD

The mapping method infers AS radial and angular coordinates by maximizing the likelihood of the observed adjacency matrix under the hyperbolic model. A degree-thresholded, layerwise heuristic makes optimization more practical on the Internet.

The method seeks radial and angular AS coordinates that maximize greedy-forwarding efficiency, rather than embedding only Internet distances or graph structure.
Coordinates are inferred by maximizing the likelihood relating observed adjacency entries to connection probabilities determined by the coordinates.
Figure 2 illustrates the Einsteinian model’s exponential radial density, decreasing average degree, geodesics, and network shortest path within a hyperbolic disc.
Standard maximum-likelihood methods perform poorly and scale badly on the Internet because the optimization landscape contains many local maxima.
Figure 3 visualizes only ASs with degree above 3 and links with p(x) > 0.5, scaling node and country-label sizes logarithmically.
The method first optimizes a small high-degree subgraph, then progressively adds lower-degree AS layers using existing coordinates as a reference frame.
Figure 4 compares binned empirical connection probabilities against the Einsteinian prediction using R = 27 and T = 0.69.

IV. MAPPING RESULTS

The inferred Internet map closely follows the Einsteinian connection-probability model and places many geographically or politically related ASs near one another. These patterns emerge despite the mapping method being geography-agnostic.

The empirical connection probability in the Internet map closely follows the theoretical Einsteinian model across hyperbolic distances.
The map places many geographically or politically close countries near one another despite using no geographic information during inference.
ASs belonging to the same country are generally localized in narrow angular regions, with broader distributions for the US, EU, and UK.
Higher internal connection density attracts ASs within a group, while sparse external connections repel disconnected nodes in the likelihood model.

V. ROUTING RESULTS

The mapped Internet supports greedy forwarding with high success, low stretch, and resilience to node, link, and long-term growth dynamics. Its performance remains strong despite failures and fixed coordinates, while measured results are lower bounds because topology data omit links.

Static performance: 97% of greedy paths reach their destinations, while sophisticated forwarding techniques can boost the success ratio to 100%.The success ratio is the percentage of greedy paths that successfully reach their destinations.
Static performance: 1.1 average stretch shows that greedy paths are close to shortest paths, averaging 3.86 hops versus 3.49 for shortest paths.
Robustness: Up to 10% simultaneous removal of AS links or nodes causes only minor degradation, although targeted hub removals are more detrimental.Greedy forwarding remains efficient under random failures, while highest-degree hub removals have a stronger effect.
Robustness: High path diversity and congruency between hyperbolic geodesics and topologically shortest paths explain the efficiency of greedy forwarding under random failures.Both path types can pass through the network’s high-degree core before exiting toward the destination.
Growth: Existing AS coordinates can remain fixed while newly joining ASs compute coordinates locally, without significantly degrading forwarding performance over long time scales.Existing coordinates can stay unchanged for years.
Measurement caveat: Routing results should be treated as lower bounds for practical performance because topology measurements miss some AS links.Additional unseen links could provide shortcuts when greedy forwarding operates in practice.

VI. CONCLUSION

The paper constructs and releases a hyperbolic Internet map that supports highly scalable routing and offers a continuous perspective on network communities. The map is robust to substantial topology perturbations, although likelihood-based mapping remains potentially prohibitive for substantially larger networks.

The released hyperbolic map supports essentially infinitely scalable Internet routing.Routing information is proportional to AS degree, while topology changes require no routing-information exchange.
Routing efficiency is close to theoretically optimal and resolves serious Internet scaling limitations.
The generic mapping method applies to complex networks with metric structure and heterogeneous degree distributions.It represents similarity continuously through hyperbolic distances rather than requiring discrete community sets.
The Internet map is robust to substantial topology perturbations and can therefore be computed only once because it is essentially static.
Mapping the Internet takes approximately a day on a modern computer, but substantially larger networks may still have prohibitive running times.The authors identify alternative methods that do not rely on likelihood maximisation as desirable.

Appendix B: Mapping methods

The mapping method fits the Internet’s observed AS graph to the Newtonian–S1 model, then uses its equivalence with Einsteinian–H2 to obtain hyperbolic coordinates. Maximum-likelihood estimation determines hidden degrees and angles, while the angular objective balances connected and disconnected node pairs.

The Newtonian–S1 to Einsteinian–H2 transformation leaves angular coordinates unchanged and maps expected degree κ to radial coordinate r.The two models generate statistically the same network topologies, while hyperbolic geodesics better align with topologically shortest paths.
The Newtonian–S1 model distributes nodes on a circle, assigns power-law hidden expected degrees, and connects pairs using effective distance rescaled by both expected degrees.
The model uses a Fermi-Dirac connection probability as an integrable function of effective distance.
The Internet map is obtained by finding Newtonian–S1 expected degrees and angular coordinates that best match the observed AS graph statistically.The fitting uses maximum-likelihood estimation techniques.
Maximum-likelihood angular inference balances placing connected nodes close with keeping disconnected nodes far apart.The first likelihood term concerns connected pairs; the second concerns disconnected pairs.
Analytical angular maximisation is unavailable, so the method relies on approximate MLE kernels including SMH and LMH.

a. MLE kernels

The mapping uses approximate likelihood-maximisation kernels because angular inference is analytically intractable and has many local maxima. LMH localizes updates, enabling distributed deployment and coordinate inference for newly arriving ASs.

SMH randomly proposes a node’s new angular position and accepts it according to the likelihood ratio when the likelihood decreases.It samples angular configurations with probability proportional to likelihood.
LMH defines each node’s local log-likelihood as a fitness and moves nodes to positions that maximize that fitness while other coordinates remain fixed.Nodes are visited one by one in repeated rounds.
LMH requires O(N^3) overall computational complexity for sparse graphs.The per-node fitness maximization takes O(N^2) time, and convergence requires rounds on the order of the network average degree.
Both SMH and LMH yield similar good results, but LMH is preferred because its localized operation supports distributed implementation.
With LMH, a new AS can compute its coordinates using only the connection status of its neighbours, without global topology knowledge.

b. First MLE wrapper

The first MLE wrapper addresses abundant local maxima by inferring coordinates through nested high-degree subgraphs and progressively expanding the active network. On a synthetic Internet-like network, the inferred angles closely match the real ones apart from rotational phase.

b. First MLE wrapper: Naive MLE kernels may take impractically long because the local likelihood landscape contains abundant local maxima.The wrapper guides the kernel toward a good solution within reasonable time and computational resources.
b. First MLE wrapper: The wrapper exploits statistical edge independence so coordinates for a node set can be inferred from the corresponding subgraph alone.
b. First MLE wrapper: The method requires the relevant subgraph to form a single connected component, a property stated to hold for the model’s synthetic networks and the real Internet.
b. First MLE wrapper: Nested subgraphs G(k1) ⊂ G(k2) ⊂ ··· ⊂ G(km) are processed from smallest to largest, feeding inferred coordinates into later iterations.
b. First MLE wrapper: High-degree nodes above approximately N^1/2 are connected almost surely and would otherwise appear identical to the MLE kernel.The wrapper removes links among these nodes to avoid placing them at the same location.
b. First MLE wrapper: The wrapper initializes new nodes from information in the preceding subgraph, then runs the MLE kernel on all active nodes.
b. First MLE wrapper: On a synthetic Newtonian–S1 network, inferred coordinates are very close to real coordinates except for an arbitrary global phase shift.The test used γ = 2.1, β = 2, N ≈24000, and average degree ≈5 for the 250 most connected nodes.

c. Second MLE wrapper

The second MLE wrapper accelerates Internet mapping by inferring coordinates for lower-degree nodes from previously mapped higher-degree neighbors while preserving existing coordinates. Its quality remains useful across degree layers, though inference deteriorates for smaller degrees and requires separate treatment for degree-1 and degree-2 nodes.

Second MLE wrapper: The wrapper adds lower-degree nodes in layers, assigning coordinates from existing nodes without rerunning the MLE kernel for every new node.New nodes infer coordinates using coordinates from existing layers, while existing-node coordinates remain unchanged.
Second MLE wrapper: O(N^2) steps complete the remaining mapping after coordinates for a relatively small number of high-degree nodes are inferred.This reduces total Internet-mapping time to a few hours on a standard computer.
Second MLE wrapper: Nodes of degree 1 and 40% of degree-2 nodes lack triangles, so the MLE kernel cannot reliably infer their metric attributes.The procedure is applied only down to nodes of degree 3 before these cases are analyzed separately.
Second MLE wrapper: Assigning a new node the angular coordinate of its highest-degree neighbor is especially sensible for degree-1 nodes, whose only path is through that neighbor.Forwarding to such nodes is therefore equivalent to forwarding to their neighbors.
Second MLE wrapper: Inference quality deteriorates for smaller degrees, but a majority of coordinates remain correctly inferred even in the worst tested case.The synthetic-network tests add layers with degrees k ≥ 8, 6, 5, 4, and 3 without running the MLE kernel for those nodes.
Second MLE wrapper: The inferred connection probability agrees well with the generating probability for high-degree subgraphs and deteriorates slightly for low-degree nodes at large effective distances χ.The comparison uses coordinates inferred by the second MLE wrapper.

Appendix F: Traffic and congestion considerations

The paper evaluates traffic under greedy forwarding by comparing normalized betweenness with shortest-path forwarding and by accounting for AS size and router counts. The comparison targets whether greedy forwarding imposes similar traffic loads and congestion implications.

Traffic and congestion considerations: Greedy forwarding’s normalized betweenness is compared directly with shortest-path forwarding to assess the traffic load handled by ASs.Source and destination AS pairs are sampled uniformly for the initial comparison.
Traffic and congestion considerations: Figure 11 reports standard normalized betweenness above and normalized betweenness divided by router count below.The upper comparison includes shortest-path and greedy forwarding; the lower calculation samples source and destination ASs proportional to router counts.
Traffic and congestion considerations: The traffic model is refined by making AS traffic generation and consumption proportional to AS size, measured by router count.AS size is roughly proportional to AS degree, and larger ASs can handle larger transit volumes.

Appendix G: Dealing with new-coming AS’s

The paper tests whether fixed coordinates for existing ASs and locally inferred coordinates for new ASs preserve greedy-forwarding performance during Internet growth. Over more than 2.5 years, success ratio and stretch vary only slightly.

Dealing with new-coming AS’s: New ASs receive coordinates locally with the LMH kernel while existing AS coordinates remain fixed during successive historical embeddings.The experiment replays AS growth from January 2007 through June 2009 in three-month steps.
Dealing with new-coming AS’s: The experiment uses 11 historical AS topologies, beginning with 17,258 ASs and ending with the June 2009 topology.New-AS counts are recorded at each three-month time step, and each newly appearing AS keeps its computed coordinates thereafter.
Dealing with new-coming AS’s: The success ratio decreases by less than 1%, while success ratio and stretch show only minor variation over more than 2.5 years.The authors conclude that greedy forwarding with the hyperbolic AS map is robust to historical Internet growth.

Appendix H: Sensitivity to missing links

The paper examines missing-link sensitivity by removing measured links before mapping and then comparing forwarding on incomplete versus link-restored graphs. Greedy-forwarding success remains robust, and restored links improve navigability.

Sensitivity to missing links: Existing Internet topology measurements miss AS links, so the paper tests forwarding under emulated missing-link conditions.The emulation removes up to 30% of links among nodes with degree above 5; 30% in that subgraph equals 14% of all network links.
Sensitivity to missing links: The first scenario maps and navigates the graph after links are removed, while the second navigates the complete graph using the map built from the incomplete graph.These scenarios distinguish direct effects of incomplete measurements from the practical use of links absent during mapping.
Sensitivity to missing links: The success ratio decreases by less than 5% when up to 14% of topology links are removed before mapping.This result supports robustness to missing links in the tested setting.
Sensitivity to missing links: Adding removed links back increases success ratio, so reported routing results are lower bounds for success achievable in practice.The improvement from re-adding links tends to increase with the number of removed links.
Sensitivity to missing links: The approach avoids topology-update communication overhead even when AS nodes and links fail, because ASs retain their hyperbolic coordinates.This distinguishes it from AS-level approaches requiring route recomputation on the dynamic AS graph.