Source-linked AI summary
On Compact Routing for the Internet
Dmitri Krioukov, kc claffy, Kevin Fall, Arthur Brady
TL;DR
The paper asks whether compact routing can provide logarithmic scaling on Internet-like topologies while supporting topology dynamics or topology-independent addressing. Using analytic arguments and simulations, it finds fundamental limits: dynamic updates require at least linear communication, and flat addressing causes polynomial routing-table lower bounds. The authors conclude that scalable routing requires a fundamental re-examination of current models and abstractions.
Problem
Existing Internet routing lacks satisfactory flexibility and provable scalability, while topology dynamics and topology-independent addressing are central requirements for future architectures.
Method
The paper combines analytic arguments about routing communication costs with simulations comparing name-independent and name-dependent compact routing.
Results
Routing control messages per topology change cannot scale slower than linearly, while flat addressing requires routing-table lower bounds of Ω(n) for shortest paths, Ω(√n) for stretch-3, and Ω(n^(1/k)) for stretch 2k−1.
Takeaways & Limitations
Routing that dynamically reacts through topology updates cannot guarantee the required scalability, motivating convergence-free or “updateless” routing ideas.
Takeaways & Limitations
Logarithmic scaling is available only for static, topology-aware routing on observed Internet topologies, not when name-independence or topology dynamics is required.
Abstract
from arXiv · showhide
While there exist compact routing schemes designed for grids, trees, and Internet-like topologies that offer routing tables of sizes that scale logarithmically with the network size, we demonstrate in this paper that in view of recent results in compact routing research, such logarithmic scaling on Internet-like topologies is fundamentally impossible in the presence of topology dynamics or topology-independent (flat) addressing. We use analytic arguments to show that the number of routing control messages per topology change cannot scale better than linearly on Internet-like topologies. We also employ simulations to confirm that logarithmic routing table size scaling gets broken by topology-independent addressing, a cornerstone of popular locator-identifier split proposals aiming at improving routing scaling in the presence of network topology dynamics or host mobility. These pessimistic findings lead us to the conclusion that a fundamental re-examination of assumptions behind routing models and abstractions is needed in order to find a routing architecture that would be able to scale ``indefinitely.''
1. INTRODUCTION
The paper argues that Internet routing needs a fundamental re-examination because existing architectures lack satisfactory flexibility and provable scalability. It examines compact routing, topology dynamics, and topology-independent addressing to identify fundamental limits.
- The paper re-examines routing assumptions because existing architectures lack both flexibility and mathematically provable scalability.
- Compact routing schemes trade routing-table size against path stretch and generally do not guarantee shortest paths.
- Static, topology-aware routing can achieve logarithmic scaling on observed Internet topologies, but topology dynamics and flat addressing challenge that behavior.
- Scalability is only one of the current Internet routing architecture’s problems; security, isolation, and configuration control are also concerns.
- Analytic arguments show that routing communication costs on Internet-like topologies are fundamentally unscalable, while simulations examine routing-table and stretch consequences for locator-identifier split proposals.
2. INTERNET ROUTING TODAY
The current Internet routing architecture faces inflexibility and poor scaling: topology-dependent addressing conflicts with mobility and multihoming, while BGP routing tables and communication overhead grow rapidly. The paper therefore seeks rigorous bounds for routing with topology-independent addressing on Internet-like graphs.
- Topology-dependent address aggregation conflicts with node mobility, multihoming, and traffic engineering that requires address-block de-aggregation.
- BGP’s routing-table size appears to grow exponentially, while its communication overhead is known to be exponential.
- De-aggregation driven by business relationships, traffic engineering, and address-allocation policies is the primary cause of super-linear BGP routing-table growth.
- Polylogarithmic scaling is the intended meaning of the paper’s shorthand term “logarithmic scaling.”
- Routing on AS numbers can reduce today’s routing-table size by an order of magnitude, but only as a constant-factor reduction rather than a scaling change.
- The paper frames the problem through rigorous lower and upper bounds for algorithms operating on Internet-like topologies with topology-independent node addressing.
3. ROUTING STRETCH
Routing stretch measures worst-case route length relative to shortest paths, distinct from policy-driven path inflation in today’s Internet. The section explains why practical routing must preserve shortest paths to neighbors and why stretch greater than one creates concerns.
- Routing stretch is the maximum route-to-shortest-path length ratio over all node pairs and supported graphs.
- Average stretch instead averages the same route-length ratio across source-destination pairs.
- Algorithmic stretch differs from contemporary Internet path inflation caused by routing policies and mismatches among topology abstractions.
- Widely used routing protocols are stretch-1 by default, although policy configurations can prevent BGP from selecting actual shortest paths.
- A stretch-greater-than-one algorithm can omit direct-neighbor routes on complete graphs, motivating explicit practical requirements for shortest paths to neighbors.
- Manual reinsertion of omitted neighbor information would counter routing-table reduction and require operator intervention.
- Stretch-1 routing requires complete topology knowledge or individualized optimal next hops for every possible destination.
4. HIERARCHICALROUTING, ADDRESSING, AND THEIR ALTERNATIVES
Hierarchical routing reduces tables through aggregation, but its stretch benefits depend on graph structure and distance growth. Grids and trees support logarithmic scaling through specialized addressing, whereas scale-free Internet-like graphs lack the required regularity and make hierarchical aggregation inefficient.
- Hierarchical routing and addressing: Hierarchical routing aggregates nearby nodes into clusters and super-clusters, reducing remote routing information to one entry per super-cluster.
- Hierarchical routing and addressing: The hierarchy’s stretch is satisfactory only when average shortest-path distance grows quickly with network size.
- Alternatives to hierarchy: Coordinate-based addressing can provide logarithmic routing-table scaling on grids without requiring aggregation.
- Alternatives to hierarchy: Graphs with bounded doubling dimension extend logarithmic scaling through distance scales or coordinate maps.
- Alternatives to hierarchy: Regular and arbitrary trees can achieve logarithmic routing-table scaling using hierarchical aggregation or DFS-based address encodings.
- Scale-free graphs: Internet topologies are scale-free, with heavy-tailed degree distributions and strong clustering rather than tree or grid structure.
- Scale-free graphs: Hierarchical aggregation is inefficient on Internet-like topologies because they lack abundant remote nodes and regular b-ary-tree structure.
- Scale-free graphs: Applying hierarchical routing to an Internet AS-level topology incurs approximately 15-times path-length increase and can trigger routing-table growth through manual reinsertion.
5. UNIVERSAL COMPACT ROUTING
Universal compact routing schemes trade path optimality for bounded stretch and sublinear routing tables, but their guarantees depend on graph coverage and addressing assumptions. Name-independent schemes add distributed identifier-to-locator mapping to an underlying name-dependent scheme, while retaining comparable worst-case bounds.
- Definitions: A compact routing scheme uses logarithmic address and header sizes, sublinear routing tables, and constant-bounded stretch.Universal schemes must satisfy these guarantees on all graphs.
- Name-independent schemes: Name-independent routing supports arbitrary flat labels, but known universal schemes retain essentially the same worst-case bounds as name-dependent schemes.Their routing process combines an underlying name-dependent scheme with dictionary tables that translate identifiers into locators.
- Name-dependent schemes: Thorup–Zwick improved Cowen’s maximum-stretch-3 scheme from ˜O(n^2/3) to ˜O(n^1/2) routing-table size.Both schemes use landmarks, clusters, and shortest-path forwarding.
- Name-independent schemes: Name-independent routing counts mapping and forwarding together, so routing tables include both underlying tables and identifier-to-locator dictionaries.Total stretch includes travel to a name-resolution node before the locator-based route.
6. COMPACT ROUTING ON SCALE-FREE GRAPHS
Scale-free graphs support unusually strong compact-routing performance in static settings: specialized schemes achieve logarithmic tables and very low stretch. However, these favorable guarantees do not by themselves extend to dynamic networks.
- Performance on scale-free graphs: Universal stretch-3 routing performs far better on scale-free graphs on average than its worst-case guarantees suggest.For TZ, average routing tables were about 50 entries and average stretch was 1.1 on the AS-level Internet, versus worst-case bounds near 2200 and 3.
- Specialized schemes: Scale-free graphs appear structurally favorable for routing, motivating specialized schemes that exploit tree coverings with little stretch.These schemes achieve logarithmic routing-table scaling and infinitesimally small stretch on scale-free graphs.
- Specialized schemes: The BC scheme guarantees maximum routing-table size O(log^2 n) by routing over a small collection of shortest-path trees.One tree is rooted at the highest-degree node, with additional trees covering fringe edges.
- Scope: Static scale-free graphs can therefore exhibit essentially “infinite” scalability, raising the question of whether comparable scaling is possible under topology dynamics.The favorable conclusion is explicitly limited to static networks.
7. DYNAMIC ROUTING ON SCALE-FREE GRAPHS
Dynamic routing must pay communication costs to reconverge after topology changes, and these costs are a central scalability measure. For scale-free graphs, the paper derives a near-linear lower bound, placing Internet-like topologies among the worst cases.
- Dynamic assumptions: Dynamic routing algorithms may need to recompute their view of the entire graph after each topology change.Algorithms requiring a full topology view can effectively restart their calculations on the changed graph.
- Dynamic assumptions: Communication cost measures the number of control messages required to converge after a topology change.It complements routing-table size and stretch as a basic dynamic-performance parameter.
- Consequences: High update costs can produce delay, instability, churn, and long convergence times; BGP examples include exponential or even infinite communication costs.Maintaining coherent topology views requires timely routing updates and table recalculation.
- Lower bound: ˜Ω(n) communication cost is a lower bound for scale-free graphs, so Internet-like graphs behave as worst cases for dynamic routing across topologies.This combines Korman and Peleg’s results with analytic estimates, extending the general Ω(n) lower bound.
8. LOCATOR-IDENTIFIER SPLIT (LIS)
Locator-identifier split architectures do not improve routing scalability under the paper’s analysis. Their aggregation assumptions fail on scale-free topologies, while identifier-to-locator mapping adds distributed state and worsens average performance experimentally.
- LIS motivation: LIS separates topology-independent identifiers from topology-following locators, expecting locator changes to support aggregation after topology changes.The architecture also aims to preserve other functions independently of location.
- LIS limitations: LIS cannot improve routing-table scaling because aggressive locator aggregation is impossible on scale-free topologies.This is one of two independent reasons given against improved LIS scalability.
- LIS limitations: Even without aggregation, LIS adds a distributed identifier-to-locator database alongside locator routing tables.The added database must also be maintained and updated.
- LIS interpretation: Name-independent routing naturally implements LIS and cannot have better average scaling than name-dependent routing because it adds mapping machinery.The name-independent design is treated as a name-dependent scheme plus additional functionality.
- Experimental results: Experiments on skitter and DIMES topologies found significantly worse average stretch and routing-table characteristics for name-independent schemes than for name-dependent schemes.The comparison included BC, TZ, TZ/BC, and Abraham schemes.
- Supporting result: Name-independent routing on trees cannot scale better than on general graphs because local dictionary neighborhoods cannot remain small enough.The paper identifies trees as worst-case graphs for universal name-independent routing.
9. CONCLUSION
Compact routing achieves logarithmic routing-table scaling only under static, topology-aware addressing, while topology-independent addressing and topology dynamics impose polynomial or linear lower bounds. The resulting impasse motivates routing architectures that avoid topology updates and full topology views.
- Compact routing seeks matching lower and upper bounds that expose fundamental routing scalability limits.
- Existing compact schemes reduce Internet-like routing-table growth from exponential to logarithmic, but only for static, topology-aware routing.
- Topology-independent addressing imposes lower bounds of Ω(n) for shortest-path routing, Ω(√n) for stretch-3 routing, and Ω(n1/k) for stretch 2k −1.
- Routing control messages per topology change cannot scale slower than linearly on Internet-like topologies.
- Linear communication scaling does not satisfy the requirement of indefinite scalability, despite improving on exponential deployed-protocol costs.
- The authors conclude that scalable dynamic routing requires radically new, convergence-free approaches that do not depend on full topology views.
APPENDIX
The appendix proves a near-linear communication-cost lower bound for random scale-free graphs by combining their logarithmic distances and concentrated distance distributions with local-density bounds. The proof translates graph distance structure into a lower bound on routing updates.
- ˜Ω(n) is the communication-cost lower bound established for random scale-free graphs of size n.
- Average distance grows as log n, while the distance-distribution width approaches zero as graph size increases.
- Local density is defined using the largest ball-size ratio over all nodes and radii.
- A radius-r ball B_x(r) contains nodes at distance at most r from x, and |B_x(r)| denotes its size.
- Substituting the scale-free distance structure into the local-density bound completes the proof of the communication lower bound.