On compact routing for the internet

Abstract

The Internet's routing system is facing stresses due to its poor fundamental scaling properties. Compact routing is a research field that studies fundamental limits of routing scalability and designs algorithms that try to meet these limits. In particular, compact routing research shows that shortest-path routing, forming a core of traditional routing algorithms, cannot guarantee routing table (RT) sizes that on all network topologies grow slower than linearly as functions of the network size. However, there are plenty of compact routing schemes that relax the shortest-path requirement and allow for improved, sublinear RT size scaling that is mathematically provable for all static network topologies. In particular, there exist compact routing schemes designed for grids, trees, and Internet-like topologies that offer RT sizes that scale logarithmically with the network size.

In this paper, we demonstrate 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 RT 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.

References

1. D. Meyer, L. Zhang, and K. Fall (Eds.). Report from the IAB workshop on routing and addressing. IRTF, Internet Draft, 2007. http://www.ietf.org/internet-drafts/draft-iab-raws-report-02.txt.
2. A. Doria, E. Davies, and F. Kastenholz (Edts.). Requirements for inter-domain routing. IRTF, Internet Draft, 2006.
3. C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed Internet routing convergence. Transactions on Networking, 9(3), 2001.
4. BGP Table Data, http://bgp.potaroo.net/.
5. G. Huston. Scaling inter-domain routing -- a view forward. The Internet Protocol Journal, 4(4), 2001.
6. G. Huston. Commentary on inter-domain routing in the Internet. IETF, RFC 3221, 2001.
7. A. Broido, E. Nemeth, and kc claffy. Internet expansion, refinement, and churn. European Transactions on Telecommunications, 13(1):33--51, 2002.
8. H. Narayan, R. Govindan, and G. Varghese. The impact of address allocation and routing on the structure and implementation of routing tables. In SIGCOMM, 2003.
9. Beyond BGP. http://www.beyondbgp.net/. Nodes
10. P. Verkaik, A. Broido, kc claffy, R. Gao, Y. Hyun, and R. van der Pol. Beyond CIDR aggregation. Technical Report TR-2004-1, CAIDA, 2004.
11. Internet Engineering Task Force (IETF). Site multihoming in IPv6. Working Group.
12. F. Kastenholz. ISLAY: A new routing and addressing architecture. IRTF, Internet Draft, 2002.
13. I. Castineyra, N. Chiappa, and M. Steenstrup. The nimrod routing architecture. IETF, RFC 1992, 1996.
14. R. Gummadi, R. Govindan, N. Kothari, B. Karp, Y. -J. Kim, and S. Shenker. Reduced state routing in the Internet. In HotNets, 2004.
15. L. Subramanian, M. Caesar, C. T. Ee, M. Handley, M. Mao, S. Shenker, and I. Stoica. HLP: A next generation inter-domain routing protocol. In SIGCOMM, 2005.
16. M. Caesar, T. Condie, J. Kannan, K. Lakshminarayanan, I. Stoica, and S. Shenker. ROFL: Routing on at labels. In SIGCOMM, 2006.
17. C. Gavoille and S. Pérennès. Memory requirement for routing in distributed networks. In PODC, 1996.
18. N. Spring, R. Mahajan, and T. Anderson. Quantifying the causes of path in ation. In SIGCOMM, 2003.
19. J. Behrens and J. J. Garcia-Luna-Aceves. Distributed, scalable routing based on link-state vectors. In SIGCOMM, 1994.
20. L. Kleinrock and F. Kamoun. Hierarchical routing for large networks: Performance evaluation and optimization. Computer Networks, 1:155--174, 1977.
21. I. Abraham, C. Gavoille, A. Goldberg, and D. Malkhi. Routing in networks with low doubling dimension. In ICDCS, 2006.
22. P. Indyk and J. MatouŠek. Handbook of Discrete and Computational Geometry, chapter 8, Low-Distortion Embeddings of Finite Metric Spaces. Chapman & Hall/CRC, Boca Raton, 2004.
23. I. Abraham, Y. Bartal, T. -H. H. Chan, K. Dhamdhere, A. Gupta, J. Kleinberg, O. Neiman, and A. Slivkins. Metric embeddings with relaxed guarantees. In FOCS, 2005.
24. P. Fraigniaud and C. Gavoille. Routing in trees. In ICALP, 2001.
25. M. Thorup and U. Zwick. Compact routing schemes. In SPAA, 2001.
26. J. MatouŠek. Lectures on Discrete Geometry, chapter 15, Embedding Finite Metric Spaces into Normed Spaces. Springer, New York, 2002.
27. R. Krauthgamer and J. R. Lee. Algorithms on negatively curved spaces. In FOCS, 2006.
28. R. Kleinberg. Geographic routing using hyperbolic space. In INFOCOM, 2007.
29. P. Mahadevan, D. Krioukov, M. Fomenkov, B. Huffaker, X. Dimitropoulos, kc claffy, and A. Vahdat. The Internet AS-level topology: Three data sources and one definitive metric. Computer Communication Review, 36(1), 2006.
30. F. Chung and L. Lu. The average distance in a random graph with given expected degrees. Internet Mathematics, 1(1):91--114, 2003.
31. J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: Densification laws, shrinking diameters and possible explanations. In KDD, 2005.
32. D. Krioukov, K. Fall, and X. Yang. Compact routing on Internet-like graphs. In INFOCOM, 2004.
33. C. Gavoille and M. Genegler. Space-efficiency for routing schemes of stretch factor three. Journal of Parallel and Distributed Computing, 61(5):679--687, 2001.
34. M. Thorup and U. Zwick. Approximate distance oracles. In STOC, 2001.
35. L. Cowen. Compact routing with minimum stretch. Journal of Algorithms, 38(1):170--183, 2001.
36. I. Abraham, C. Gavoille, D. Malkhi, N. Nisan, and M. Thorup. Compact name-independent routing with minimum stretch. In SPAA, 2004.
37. M. Arias, L. Cowen, K. A. Laing, R. Rajaraman, and O. Taka. Compact routing with name independence. In SPAA, 2003.
38. A. Brady and L. Cowen. Compact routing on power-law graphs with additive stretch. In ALENEX, 2006.
39. S. Carmi, R. Cohen, and D. Dolev. Searching complex networks efficiently with minimal information. Europhysics Letters, 74:1102--1108, 2006.
40. T. Griffin and G. Wilfong. An analysis of BGP convergence properties. In SIGCOMM, 1999.
41. T. Griffin and G. Wilfong. Analysis of the MED oscillation problem in BGP. In ICNP, 2002.
42. Y. Afek, E. Gafni, and M. Ricklin. Upper and lower bounds for routing schemes in dynamic networks. In FOCS, 1989.
43. A. Korman and D. Peleg. Dynamic routing schemes for general graphs. In ICALP, 2006.
44. CAIDA. Macroscopic topology AS adjacencies. http://www.caida.org/tools/measurement/skitter/as adjacencies.xml.
45. The DIMES project. http://www.netdimes.org/.
46. K. A. Laing and R. Rajaraman. A space lower bound for name-independent compact routing in trees. In SPAA, 2005.
47. I. Abraham, C. Gavoille, and D. Malkhi. On space-stretch trade-offs: Lower bounds. In SPAA, 2006.
48. S. Milgram. The small world problem. Psychology Today, 1:61--67, 1967.
49. S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin. Metric structure of random networks. Nuclear Physics B, 653(3):307--422, 2003.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

      • Network flows

• Networks

  • Network properties

    • Network structure

  • Network protocols

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows