Mailing List Archive

On Mon, May 19, 2003 at 07:30:54PM +0200, Piotr Marecki wrote:
> Lightly OT , but i'm very curious . Given that IP2 is able to make 40
> million L3 lookups per second - so how many memory accesses it is doing
> per lookup and how this alghoritm may looks like ?

I believe the actual L3 lookup done with an mtrie (the same data structure
as CEF) implemented in the IP2. I seem to recall someone saying that the
Juniper implementation was 16-1-1-1-1-1-1-1-1 vs Cisco's 16-8-8, but they
could have been full of it. If you're looking for something to run on a
general purpose processor, you should probably stick to the way CEF does
it.

--
Richard A Steenbergen <ras@e-gerbil.net> http://www.e-gerbil.net/ras
GPG Key ID: 0xF8B12CBC (7535 7F59 8204 ED1F CC1C 53AF 4C41 5ECA F8B1 2CBC)

On Mon, 2003-05-19 at 19:50, Richard A Steenbergen wrote:
> I believe the actual L3 lookup done with an mtrie (the same data structure
> as CEF) implemented in the IP2. I seem to recall someone saying that the
> Juniper implementation was 16-1-1-1-1-1-1-1-1 vs Cisco's 16-8-8, but they
> could have been full of it. If you're looking for something to run on a
> general purpose processor, you should probably stick to the way CEF does
> it.
>
I suppose cisco implementation is also hw specific (for example on 1000x
esr "show hardware pxf cpu cef" gives "Shadow 12-8-4-4-4 Toaster Mtrie".
Also . it's kind funny that ( in my experience ) Cisco wasn't able to
provide decent and fast gear for ISP ( let command "show pxf crash" be
an example ... ) in last years given ( i think so ) lot's of more cash
for R&D .

regards

Piotr Marecki

On Mon, May 19, 2003 at 08:07:45PM +0200, Piotr Marecki wrote:
> I suppose cisco implementation is also hw specific (for example on 1000x
> esr "show hardware pxf cpu cef" gives "Shadow 12-8-4-4-4 Toaster Mtrie".
> Also . it's kind funny that ( in my experience ) Cisco wasn't able to
> provide decent and fast gear for ISP ( let command "show pxf crash" be
> an example ... ) in last years given ( i think so ) lot's of more cash
> for R&D .

For pxf perhaps, but most older stuff is implemented with general purpose
processors... A simple 256-way mtrie is like 40 lines of code tops.

Obviously if you want 40Mpps, you're going to be desigining custom ASICs.
If you want decent performance on cheap hardware (7206-like performance),
the mtrie on a general purpose CPU is still the simplest way to go.
Cisco's CEF problems usually relate to dCEF.

--
Richard A Steenbergen <ras@e-gerbil.net> http://www.e-gerbil.net/ras
GPG Key ID: 0xF8B12CBC (7535 7F59 8204 ED1F CC1C 53AF 4C41 5ECA F8B1 2CBC)

I believe in Juniper's case the Tree in fact is called...

... <drums> ...

<cymbals!>

Jay-tree! :)

Further details seem to have slipped from my memory - sorry. :)

On Mon, May 19, 2003 at 02:16:51PM -0400, Richard A Steenbergen wrote:

[skippety-skip]

---end quoted text---

SY,
--
D.K.

On Mon, May 19, 2003 at 01:50:39PM -0400, Richard A Steenbergen wrote:
| On Mon, May 19, 2003 at 07:30:54PM +0200, Piotr Marecki wrote:
| > Lightly OT , but i'm very curious . Given that IP2 is able to make 40
| > million L3 lookups per second - so how many memory accesses it is doing
| > per lookup and how this alghoritm may looks like ?
|
| I believe the actual L3 lookup done with an mtrie (the same data structure
| as CEF) implemented in the IP2. I seem to recall someone saying that the
| Juniper implementation was 16-1-1-1-1-1-1-1-1 vs Cisco's 16-8-8, but they
| could have been full of it. If you're looking for something to run on a
| general purpose processor, you should probably stick to the way CEF does
| it.

it is neither a 16-8-8 nor a 16-1-1-1-1-1-1-1-1 mtrie;

the algorithm is documented in the patent filing:

http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=/netahtml/search-adv.htm&r=15&f=G&l=50&d=PTXT&p=1&S1=juniper.ASNM.&OS=AN/juniper&RS=AN/juniper

/hannes

i think that the patent you really want to refer to is this one.

5,909,440 - high speed variable length best match look-up in a switching device

http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=5,909,440.WKU.&OS=PN/5,909,440&RS=PN/5,909,440

when last we saw our hero (Tuesday, May 20, 2003),
Hannes Gredler was madly tapping out:
> On Mon, May 19, 2003 at 01:50:39PM -0400, Richard A Steenbergen wrote:
> | On Mon, May 19, 2003 at 07:30:54PM +0200, Piotr Marecki wrote:
> | > Lightly OT , but i'm very curious . Given that IP2 is able to make 40
> | > million L3 lookups per second - so how many memory accesses it is doing
> | > per lookup and how this alghoritm may looks like ?
> |
> | I believe the actual L3 lookup done with an mtrie (the same data structure
> | as CEF) implemented in the IP2. I seem to recall someone saying that the
> | Juniper implementation was 16-1-1-1-1-1-1-1-1 vs Cisco's 16-8-8, but they
> | could have been full of it. If you're looking for something to run on a
> | general purpose processor, you should probably stick to the way CEF does
> | it.
>
> it is neither a 16-8-8 nor a 16-1-1-1-1-1-1-1-1 mtrie;
>
> the algorithm is documented in the patent filing:
>
> http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=/netahtml/search-adv.htm&r=15&f=G&l=50&d=PTXT&p=1&S1=juniper.ASNM.&OS=AN/juniper&RS=AN/juniper
>
> /hannes
> _______________________________________________
> juniper-nsp mailing list juniper-nsp@puck.nether.net
> http://puck.nether.net/mailman/listinfo/juniper-nsp

--
steve ulrich sulrich@botwerks.org
PGP: 8D0B 0EE9 E700 A6CF ABA7 AE5F 4FD4 07C9 133B FAFC

thanks jesper,

seems that the results from the US patent office search engine
are just cached [now broken] results ...

try this one ..

http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=5909440.WKU.&OS=PN/5909440&RS=PN/5909440

/hannes

On Tue, May 20, 2003 at 01:36:26PM +0200, Jesper Skriver wrote:
| On Tue, May 20, 2003 at 12:49:48PM +0200, Hannes Gredler wrote:
| > On Mon, May 19, 2003 at 01:50:39PM -0400, Richard A Steenbergen wrote:
| > | On Mon, May 19, 2003 at 07:30:54PM +0200, Piotr Marecki wrote:
| > | > Lightly OT , but i'm very curious . Given that IP2 is able to make 40
| > | > million L3 lookups per second - so how many memory accesses it is doing
| > | > per lookup and how this alghoritm may looks like ?
| > |
| > | I believe the actual L3 lookup done with an mtrie (the same data structure
| > | as CEF) implemented in the IP2. I seem to recall someone saying that the
| > | Juniper implementation was 16-1-1-1-1-1-1-1-1 vs Cisco's 16-8-8, but they
| > | could have been full of it. If you're looking for something to run on a
| > | general purpose processor, you should probably stick to the way CEF does
| > | it.
| >
| > it is neither a 16-8-8 nor a 16-1-1-1-1-1-1-1-1 mtrie;
| >
| > the algorithm is documented in the patent filing:
| >
| > http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=/netahtml/search-adv.htm&r=15&f=G&l=50&d=PTXT&p=1&S1=juniper.ASNM.&OS=AN/juniper&RS=AN/juniper
|
| "Voltage sequencing circuit for powering-up sensitive electrical components"
|
| Interesting lookup algorithm ;-)
|
| /Jesper