From the point of view of the FIB, this direct lookup
People either trying to achieve massive expansion of the IPv4 and IPv6 "global routing tables" - or trying to figure out a way of limiting their growth and devising new protocols to achieve multihoming and traffic engineering without relying on BGP - may wish to become involved in two lists: The RAM list, arising from the IAB's RAW workshop last year: http://www1.ietf.org/mailman/listinfo/ram http://tools.ietf.org/html/draft-iab-raws-report http://www.iab.org/about/workshops/routingandaddressing/ RRG - the IRTF's Routing and Research Group: http://www.irtf.org/charter?gtype=rg&group=rrg http://psg.com/lists/rrg/2007/ There is also a closed list which is worth watching: IETF Routing and Addressing Directorate http://www.ietf.org/IESG/content/radir.html http://www1.ietf.org/mail-archive/web/radir/current/ Guidance on which list is best for which topic is: http://www1.ietf.org/mail-archive/web/ram/current/msg01428.html RADIR is working on a Problem Statement I-D and the RRG is working on a Design Goals I-D. With IPv4 with a /24 limit on BGP advertisements it is relatively easy and very fast to do the FIB with a single lookup into RAM - provided you have enough fast RAM. Some high-end routers such as the CRS-1, M120 and MX960 probably have enough RAM to do it already. Beyond some number of prefixes (wild guess 500,000) it would be more memory- efficient to do a direct lookup into RAM with 24 bits of address than with Tree-Bitmap or similar ASIC + RAM based algorithms which use a single memory access for every 3 or 4 bits of address which needs to be classified. My proposal for direct RAM lookups is: http://www.firstpr.com.au/ip/sram-ip-forwarding/ but Reduced Latency DRAM would be fine too. The idea was first proposed in 1998 by Nick McKeown, Pankaj Gupta and Steven Lin: Routing Lookups in Hardware at Memory Access Speeds. (IEEE INFOCOM April 1998, Vol 3, pp. 1240-1247.) http://tiny-tera.stanford.edu/%7Enickm/papers/Infocom98_lookup.pdf My proposal extends the idea to IPv6, but with a significant restriction in the address range. There would still be plenty of space. proposal would enable IPv4 or IPv6 space to be assigned without any concern about route aggregation. This would mean that address space could be assigned in smaller chunks for shorter-term demand, which means it could be used much more efficiently. An optimised FIB proposal such as mine doesn't make much sense unless BGP can cope with millions of prefixes. On the RAM list earlier this year, it seems no-one had much hope of achieving this - so most of the discussion was about LISP, a proposal for "Locator/ID Separation Protocol" to achieve TE and multihoming without BGP and without changing host software. But LISP has its difficulties and is at a very early stage of development. Now there is some discussion on the RRG list about significant improvements to BGP. Here are some URLs relating to improving BGP: http://tools.ietf.org/html/draft-li-bgp-stability http://www.sigcomm.org/sigcomm2005/paper-SubCae.pdf http://www.ieee-icnp.org/2006/papers/s4a4.pdf http://www.ieee-icnp.org/2006/papers/s8a2.pdf http://www.beyondbgp.net/pubs/2005/bbgp_comnet05.pdf I have a list of such documents at: http://www.firstpr.com.au/ip/sram-ip-forwarding/#BGP_improvements Please suggest additions to this list. - Robin