nanog mailing list archives
Re: Cogent service
From: "Stephen Sprunk" <ssprunk () cisco com>
Date: Fri, 20 Sep 2002 21:18:21 -0500
Thus spake "Vadim Antonov" <avg () exigengroup com>
On Fri, 20 Sep 2002, Stephen Stuart wrote:Regarding CPU cycles for route lookups: Back in the mid-1990s, route lookups were expensive. There was a lot of hand-wringing, in fact, about how doing route lookups at every hop in larger and larger FIBs had a negative impact on end-to-end performance. One of the first reasons for the existence of MPLS was to solve this problem.
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. It's arguable that MPLS hasn't really caught on yet precisely because FIBs (aka CEF) removed the cache problems from the equation.
This was a totally bogus reason from the very beginning. Given that real backbones carry no prefixes longer than 24 bits the "long" lookup in 16-4-4-4-4 bit radix tree takes 5 memory reads.
What routers use a 16-4-4-4-4 radix tree? Vendor C uses a 256-way radix tree for its RIB and a 16-8-8 mtrie+ for its FIB. Vendor J uses a 20-1-1-1-1-1-1... mtrie for its FIB. Or so I've read.
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. 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. 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.
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. S
Current thread:
- Re: Cogent service, (continued)
- Re: Cogent service David Diaz (Sep 20)
- Re: Cogent service Iljitsch van Beijnum (Sep 20)
- Re: Cogent service Petri Helenius (Sep 20)
- Re: Cogent service Iljitsch van Beijnum (Sep 20)
- Re: Cogent service Petri Helenius (Sep 20)
- Re: Cogent service David Diaz (Sep 20)
- Re: Cogent service Kurt Erik Lindqvist (Sep 24)
- RE: Cogent service Mark Borchers (Sep 20)
- Re: Cogent service Stephen Stuart (Sep 20)
- Re: Cogent service Vadim Antonov (Sep 20)
- Re: Cogent service Stephen Sprunk (Sep 20)
- Re: Cogent service Petri Helenius (Sep 21)
- software routers (was: Cogent service) Vadim Antonov (Sep 21)
- Re: Cogent service Michael L. Barrow (Sep 19)
- Re: Cogent service Alex Rubenstein (Sep 19)
- Re: Cogent service Valdis . Kletnieks (Sep 19)
- RE: Cogent service jlewis (Sep 22)
- selective prepends (RE: Cogent service) E.B. Dreger (Sep 22)
- Re: selective prepends (RE: Cogent service) Olivier Bonaventure (Sep 23)