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: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.293-306, June 2001 [doi>10.1109/90.929852]
• 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: Harsha Narayan , Ramesh Govindan , George Varghese, The impact of address allocation and routing on the structure and implementation of routing tables, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863971]
• 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: Lakshminarayanan Subramanian , Matthew Caesar , Cheng Tien Ee , Mark Handley , Morley Mao , Scott Shenker , Ion Stoica, HLP: a next generation inter-domain routing protocol, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 16: Matthew Caesar , Tyson Condie , Jayanthkumar Kannan , Karthik Lakshminarayanan , Ion Stoica, ROFL: routing on flat labels, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 17: Cyril Gavoille , Stéphane Pérennès, Memory requirement for routing in distributed networks, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.125-133, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248075]
• 18: Neil Spring , Ratul Mahajan , Thomas Anderson, The causes of path inflation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863970]
• 19: Jochen Behrens , J. J. Garcia-Luna-Aceves, Distributed, scalable routing based on link-state vectors, Proceedings of the conference on Communications architectures, protocols and applications, p.136-147, August 31-September 02, 1994, London, United Kingdom
• 20: L. Kleinrock and F. Kamoun. Hierarchical routing for large networks: Performance evaluation and optimization. Computer Networks, 1:155--174, 1977.
• 21: Ittai Abraham , Cyril Gavoille , Andrew V. Goldberg , Dahlia Malkhi, Routing in Networks with Low Doubling Dimension, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.75, July 04-07, 2006 [doi>10.1109/ICDCS.2006.72]
• 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: Ittai Abraham , Yair Bartal , T-H. Hubert Chan , Kedar Dhamdhere Dhamdhere , Anupam Gupta , Jon Kleinberg , Ofer Neiman , Aleksandrs Slivkins, Metric Embeddings with Relaxed Guarantees, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.83-100, October 23-25, 2005 [doi>10.1109/SFCS.2005.51]
• 24: Pierre Fraigniaud , Cyril Gavoille, Routing in Trees, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.757-772, July 08-12, 2001
• 25: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]
• 26: J. MatouŠek. Lectures on Discrete Geometry, chapter 15, Embedding Finite Metric Spaces into Normed Spaces. Springer, New York, 2002.
• 27: Robert Krauthgamer , James R. Lee, Algorithms on negatively curved spaces, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.119-132, October 21-24, 2006 [doi>10.1109/FOCS.2006.9]
• 28: R. Kleinberg. Geographic routing using hyperbolic space. In INFOCOM, 2007.
• 29: Priya Mahadevan , Dmitri Krioukov , Marina Fomenkov , Xenofontas Dimitropoulos , k c claffy , Amin Vahdat, The internet AS-level topology: three data sources and one definitive metric, ACM SIGCOMM Computer Communication Review, v.36 n.1, January 2006 [doi>10.1145/1111322.1111328]
• 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: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 32: D. Krioukov, K. Fall, and X. Yang. Compact routing on Internet-like graphs. In INFOCOM, 2004.
• 33: Cyril Gavoille , Marc Gengler, Space-efficiency for routing schemes of stretch factor three, Journal of Parallel and Distributed Computing, v.61 n.5, p.679-687, May 2001 [doi>10.1006/jpdc.2000.1705]
• 34: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]
• 35: Lenore J. Cowen, Compact routing with minimum stretch, Journal of Algorithms, v.38 n.1, p.170-183, Jan. 2001 [doi>10.1006/jagm.2000.1134]
• 36: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007916]
• 37: Marta Arias , Lenore J. Cowen , Kofi A. Laing , Rajmohan Rajaraman , Orjeta Taka, Compact routing with name independence, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777442]
• 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: Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 41: Timothy Griffin , Gordon T. Wilfong, Analysis of the MED Oscillation Problem in BGP, Proceedings of the 10th IEEE International Conference on Network Protocols, p.90-99, November 12-15, 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: Kofi A. Laing , Rajmohan Rajaraman, A space lower bound for name-independent compact routing in trees, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074005]
• 47: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi, On space-stretch trade-offs: lower bounds, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148143]
• 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

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph algorithms

General Terms:
Algorithms, Design, Theory

Keywords:
compact routing, internet routing, routing scalability