Compact Routing on the Internet AS Graph
15 April 2011
/ routing
Compact routing algorithms have been presented as candidates for scalable
routing in the future Internet, achieving near-shortest path routing
with considerably less forwarding state than the Border Gateway
Protocol. Prior analyses have shown strong performance on power-law
random graphs, but to better understand the applicability of compact
routing algorithms in the context of the Internet, they must be
evaluated against real- world data. To this end, we present the first
systematic analysis of the behaviour of the Thorup-Zwick (TZ) and
Brady-Cowen (BC) compact routing algorithms on snapshots of the
Internet Autonomous System graph spanning a 14 year period. Both
algorithms are shown to offer consistently strong performance on the AS
graph, producing small forwarding tables with low stretch for all
snapshots tested. We find that the average stretch for the TZ algorithm
increases slightly as the AS graph has grown, while previous results on
synthetic data suggested the opposite would be true. We also present
new results to show which features of the algorithms contribute to
their strong performance on these graphs.