The impact of address allocation and routing on the structure and implementation of routing tables

ABSTRACT

The recent growth in the size of the routing table has led to an interest in quantitatively understanding both the causes (eg multihoming) as well as the effects (eg impact on router lookup implementations) of such routing table growth. In this paper, we describe a new model called ARAM that defines the structure of routing tables of any given size. Unlike simpler empirical models that work backwards from effects (eg current prefix length distributions), ARAM approximately models the causes of table growth (allocation by registries, assignment by ISPs, multihoming and load balancing). We show that ARAM models with high fidelity three abstract measures (prefix distribution, prefix depth, and number of nodes in the tree) of the shape of the prefix tree --- as validated against 20 snapshots of backbone routing tables from 1997 to the present. We then use ARAM for evaluating the scalability of IP lookup schemes, and studying the effects of multihoming and load balancing on their scaling behavior. Our results indicate that algorithmic solutions based on multibit tries will provide more prefixes per chip than TCAMs (as table sizes scale toward a million) unless TCAMs can be engineered to use 8 transistors per cell. By contrast, many of today's SRAM-based TCAMs use 14-16 transistors per cell.

REFERENCES

• 1: V. Srinivasan, G. Varghese. Fast Address Lookups Using Controlled Prefix Expansion. ACM Transactions on Computer Systems, Volume 19, Number 4, November 2001.
• 2: M. Waldvogel, G. Varghese, J. Turner, B. Plattner. Scalable High-Speed Prefix Matching. ACM Transactions on Computer Systems, Volume 17, Issue 1, February 1999.
• 3: David E. Taylor, Jonathan S. Turner, John W. Lockwood, Todd S. Sproull, David B. Parlour. Scalable IP Lookup for Internet Routers. IEEE Journal on Selected Areas in Communications, Volume 21, Number 4, May 2003.
• 4: H. Narayan, R. Govindan, G. Varghese. The Impact of Address Allocation and Routing on the Structure and Implementation of Routing Tables. University of California,San Diego Tech Report CS 2003-0749.
• 5: E. Zegura, K. Calvert, S. Bhattacharjee. How to Model an Internetwork. Proceedings of INFOCOM 1996.
• 6: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 7: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.175-187, August 28-September 01, 2000, Stockholm, Sweden
• 8: C. Labovitz, R. Malan, F. Jahanian. Origins of Internet Routing Instability. Proceedings of INFOCOM 1999.
• 9: Lightreading. www.lightreading.com.
• 10: T. Bu, L. Gao and D. Towsley. On Characterizing Routing table growth. Proceedings of GlobalInternet 2002.
• 11: Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.3-14, September 14-18, 1997, Cannes, France
• 12: W. Eatherton et.al. Tree Bitmap : Hardware/Software IP Lookups with Incremental Updates. Available at www.eathertons.com/sigcomm-withnames.PDF
• 13: IANA /8 delegations. www.iana.org/assignments/ipv4-address-space
• 14: Policies for IPv4 address space management in the Asia Pacific region. www.apnic.net/docs/policy/add-manage-policy.html
• 15: ARIN Policies. www.arin.net/policy/index.html
• 16: M. Kühne, N. Nimpuno, P. Rendek, S. Wilmot. IPv4 Address Allocation and Assignment Policies in the RIPE NCC Service Region. www.ripe.net/docs/ipv4-policies.html
• 17: Daniel Golding. Private Communication.
• 18: Mark Prior. Private Communication.
• 19: FreeIPDB - The Next Generation IP Database. www.freeipdb.org
• 20: Northstar IP Management Tool. www.brownkid.net/NorthStar.
• 21: J. J. Ramsden and Gy. Kiss-Haypal, Company Size Distribution in Different Countries, Physica A, vol 277, pp. 220-227, 2000.
• 22: James Sybert. Private Communication.
• 23: Mike Loevner. Private Communication.
• 24: ARIN Allocations. ftp://ftp.arin.net/pub/stats/arin/
• 25: APNIC allocations. ftp://ftp.apnic.net/pub/stats/apnic/
• 26: RIPE Allocations. ftp://ftp.ripe.net/ripe/stats/
• 27: University of Oregon Route Views Project www.routeviews.org
• 28: Olaf Maennel , Anja Feldmann, Realistic BGP traffic for test labs, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 29: Richard Jimmerson. Private Communication.
• 30: Son Tran. Private Communication.
• 31: Leo Vegoda. Private Communication.
• 32: Ratified Policy 2001-2: Reassignments to multihomed downstream customers Policy. www.arin.net/policy/2001_2.html
• 33: Gerard Ross. Private Communication.
• 34: A. Lord. Proposal for IPv4 allocations by LIRs to ISPs. APNIC Open Policy Meeting, September 2002. www.apnic.net/meetings/14/sigs/policy/docs/addrpol-out-apnic-sub-alloc.pdf
• 35: A. Lord. Downstream Allocations by LIRs: A proposal. RIPE 43 Meeting, September 2002. www.ripe.net/ripe/meetings/archive/ripe-43/index.html
• 36: M. Ruiz-Sanchez, E. Biersack, W. Dabbous. phSurvey and Taxonomy of IP Lookup Algorithms. IEEE Network. Vol. 15. Issue 2. 2001.
• 37: G. Huston. phAnalyzing the Internet's BGP Routing Table. Internet Protocol Journal. Volume 4, Number1, March 2001.
• 38: Prefix Taxonomy Ongoing Measurement & Inter Network Experiment (ptomaine). http://www.ietf.org/html.charters/ptomaine-charter.html
• 39: G. Huston. phNOPEER community for BGP scope control. draft-ietf-ptomaine-nopeer-00.txt April 2002.
• 40: O. Bonaventure, S. DeCnodder, J. Haas, B. Quoitin, R. White. Controlling the redistribution of BGP routes. draft-ietf-ptomaine-bgp-redistribution-01.txt. August 2002.
• 41: S. Bellovin, R. Bush, T. Griffin, J. Rexford. Slowing Routing Table Growth by Filtering Based on Address Allocation Policies. www.research.att.com/ jrex/papers/filter.pdf
• 42: T. Bates and Y. Rekhter. phScalable Support for Multi-homed Multi-provider Connectivity. RFC 2260.
• 43: Eddie Kohler , Jinyang Li , Vern Paxson , Scott Shenker, Observed structure of addresses in IP traffic, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637242]
• 44: Anindya Basu and Girija Narlikar. Fast Incremental Updates for Pipelined Forwarding Engines. Proceedings of Infocom 2003.
• 45: D. Shah and P. Gupta. Fast Updates on Ternary CAMs for Packet Lookups and Classification. Hot Interconnects 8.
• 46: Zhiguo Xu, Xiaoqiao Meng, Cathy Wittbrodt, Songwu Lu, Lixia Zhang. Address Allocation and the Evolution of the BGP routing table. Technical Report CSD-TR03009, UCLA Computer Science Depratment, 2003. http://www.cs.ucla.edu/wing/pdfdocs/address_tr.ps

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

General Terms:
Measurement, Performance

Keywords:
IP lookups, modeling, routing tables