Cogent service

Petri Helenius pete at he.iki.fi
Sat Sep 21 07:54:01 UTC 2002


Stephen Sprunk wrote:
>
> FIBs did not exist (in production routers) at the time MPLS aka tag switching
> was invented.  The problem was that the day's cache-based routers could not
> handle the growing number of destinations on the Internet and crumbled under the
> load of creating and aging cache entries.  In networks with limited
> destinations, this technology still works well in the tens of Mpps range.
>
Yes, however to get the full picture one must understand that C shipped tag-switching
with the requirement of running CEF. So the cache-problem was solved conviniently
at the same time tag-switching came in. 
 
> >  Given that a lot of
> > routes are aggregated, and the ubiquity of fast data caches (which can
> > safely hold 3 top levels of full FIB) the average number of memory reads
> > needed by a general-purpose CPUs available in mid-90s to do route lookup
> > is (surprise) - about 1.2
> 
> Let's see:
> 
> 250kpps
> 1.2rds/packet
> 128bytes/FIB entry
> 8bytes/read
> 1read/4cycles
> 
> That comes out to 4*16*1.2*250k = 19.2M cycles on the FSB just doing route
> lookups.  CPUs of the day had 33MHz and slower FSB's.  Not going to happen.

What bits are in the 128 bytes on a FIB entry you have to read? Sounds like
1-1-1-1-... tree would be more optimal with the neccessity of reading only
one word for lookup than the 16 read per node tree you're proposing.
> 
> You're also way off on how much FIB fits in cache; the first level of vendor C's
> FIB is in the *megs* and no CPU of that era had that much on-die cache; it's
> rare even on CPUs today.

And cache does not help you that much anyway because usually you end up doing
queue management on the same CPU and keeping the "interesting stuff" in the cache
is challenging at best. 
> 
> Sure, you can make the FIB a lot smaller to fit the cache, but then you have to
> turn the mtrie+ into a plain mtrie, throw out load-sharing, etc.  I've done it,
> and it doesn't bear any resemblance to a *real* FIB implementation you can sell.
> 
Is lookup performance consistency or the depth of host-prefix lookups the main
reasons why you say that it wouldn't work? In any case, usually you look up 
less than 1% of your nodes >90% of the time. Having a root node of 13-16 bits
cuts your lookups in less than half without increasing cache pollution.

> > In fact, full-featured IP forwarding (including Fair Queueing and packet
> > classification) at 120 kpps was demonstrated using a 133MHz Pentium MMX.
> > Did beat crap out of 7000's SSE.  Wasn't that hard, too; after all it is
> > more than 1000 CPU cycles per packet.  The value proposition of ASIC-based
> > packet routing (and use of CAMs) was always quite dicey.
> 
> If you think you can make a gigabit router with PC parts, feel free.
> 
I think somebody just announced that they've shipped 250000 routers built out 
of PC parts :-)

Pete



More information about the NANOG mailing list