[c-nsp] ASR 1002-X FIB scalability

[Beck, Andre]

Re,

On Tue, May 28, 2013 at 04:21:00PM -0400, Pete Lumbis wrote:
> > According to my "research" so far, the ASR1k does use TCAM but *not*
> > for the actual FIB. It's used for ACLs and QoS stuff, though.
> 
> You are 100% correct. TCAM for features, QFP memory for FIB.

Fits my observation that I'm currently using 8 TCAM cells no matter
if there is just a handful prefixes, 450k or 3.34M of them.
 
> > [...] But is the 3.3M prefixes FIB really condensed to those 316MB
> > of PLU Mgr stuff (and what does PLU stand for)?
> 
> Yeah, it condenses way down. I'm not sure exactly what the magic is, but
> I'm sure it has to do with only storing a prefix and next hop adjacency
> instead of additional information about the route itself.

Yep, I remember reading papers in the late 90s or early 00s about an
algorithm that could condense a FIB of almost then-current DFZ dimensions
(some 60k prefixes or so) to something that would fit the cache of a
Pentium, enabling extremly fast forwarding. It's still an interesting
area for research, see papers like
http://conferences.sigcomm.org/hotnets/2012/papers/hotnets12-final13.pdf
(Compressing IP Forwarding Tables for Fun and Profit). And 3.34M prefixes
in 316M means it's close to 100Byte/Prefix - seen this way, it's not
even in need of any sophisticated compression to FIB entropy limits,
and probably much faster as a result. BTW, a 450k prefix FIB results
in 64MB of PLU, while the baseline (handful of prefixes directly after
a reload) is 8MB.

> The PLU is "Pointer Lookup Unit". Also know as the forwarding lookup
> process.

Ah, that makes a lot of sense. I assume that it's actually about
avoiding real pointers and using indexes instead, with the PLU
optimizing the lookup process. Avoiding pointers (full addresses
of 32 or, let alone, 64bit width) is very helpful for compaction
and cache efficiency even on general purpose CPUs, and the QFP is
specifically designed for that...

Thanks,
Andre.
-- 
                    Cool .signatures are so 90s...

-> Andre Beck    +++ ABP-RIPE +++      IBH IT-Service GmbH, Dresden <-