[address-policy-wg] Re: 5M prefixes in the core [was: Re: [ppml] [address-policy-wg] Those pesky ULAs again ]

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.

>From the point of view of the FIB, this direct lookup
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