[ppml] Longer prefixes burden the FIBs of DFZ routers

[briand at ca.afilias.info]

> TCAM can be as wide as 72 bits, and if the router has enough TCAM
> space in its FIB, it doesn't matter how many bits are looked at,
> provided they fit within the 72 or 144 bit width of the TCAM.

Not quite - the number of entries must fit in the total amount of TCAM
memory.

The specific entries themselves aren't relegated to only being
the full bitwise representation of a prefix, even if that is the simplest
scheme for storage and lookup.

E.g., alternatives that use some kind of symbol-mapping scheme, or
hash scheme, or other way of reducing the maximum number of bits
required on a lookup, are one way of reducing both total TCAM memory
used, and number of bits per entry.

But, even at 144 bits, i.e. two "slots" per v6 prefix compared to one
per v4 prefix, if the number of slots used is not unreasonable, TCAM
can do the job (and do it in one cycle).

> (However TCAM is expensive, power-hungry, must be soldered to the
> main board - can't be upgraded - and can be slow to update when the
> classification rules need to be changed.)

Expensive, yes; power hungry, yes. It is *not* the case that they *must*
be soldered to the main board - this per Cisco rep at the last NANOG.

And ditto the upgradability. They haven't been made FRUs in the past, but
there's nothing intrinsic to them that forces hard-wiring, other than
design cost on the board itself.

The TCAM standard has advanced, so that the next several generations will
have completely compatible pinouts, specifically so that they *can* become
FRUs. The main idea would be, upgrade TCAMs to higher density units, and
stack more of them in serial on the main board. More total TCAM space, in
the same number of "slots".

> There's no such thing as a 32 bit lookup unless what you need to
> find is a byte or less and if you have 4 gigabytes of RAM to hold
> the array, which no router's FIB has.

Wrong. Your idea of "what a router is", is just a little limited, which
is why you believe this to be the case.

Any reasonably big iron server, with multiple PCI-express buses,
fast and numerous CPUS, and serious enough chip set, can do the job of
"high-end router". 1 x 10GbE per PCI-E bus, nominally 4 or more,
and upwards of 512GB of memory, can be put into a (big) box that runs
routing software (such as quagga).

Been there, done that, as the saying goes, and yes, it can do DFZ level
routing and forwarding, with tons of capacity for long prefix lookups.

Besides which, there's every reason to believe that one byte can hold
enough information for the result of a route lookup. Think index into an
array of objects, each of which includes in interface index and MAC address.
One byte means 256 such objects, which is likely to be sufficient for the
majority of devices holding default-free routing tables.

Brian Dickson