2005-1, good or bad? [Was: Re: Shim6 vs PI addressing]

Edward B. DREGER eddy+public+spam at noc.everquick.net
Thu Mar 2 23:17:52 UTC 2006

AO> Date: Thu, 02 Mar 2006 21:42:49 +0100
AO> From: Andre Oppermann

AO> Doing longest-prefix match for high pps rates and high prefix counts
AO> in hardware is complex and expensive.

True, but...

AO> Way more so than doing perfect match on 32 bits (giving 4bn
AO> routeable slots).

...how many routers' FIBs are 32-bit perfect match right now?  Or even a 
24+8 radix tree?

That said, one can use a hybrid

	{ array + { btree | skip list } }

for O(k + log(N)) FIB lookups when hardware doesn't support full exact 
match.  Transition workload from logarithmic to scalar as technology 

Classful routing is simple.  Simplicity is good.  However, it's still 
not quite time to get carried away with huge tables.  (Of course, IPv6 
is a good chance to "start over" with a defragmented table in which a 
full table would have _fewer_ routes than IPv4.)

Everquick Internet - http://www.everquick.net/
A division of Brotsman & Dreger, Inc. - http://www.brotsman.com/
Bandwidth, consulting, e-commerce, hosting, and network building
Phone: +1 785 865 5885 Lawrence and [inter]national
Phone: +1 316 794 8922 Wichita
DO NOT send mail to the following addresses:
davidc at brics.com -*- jfconmaapaq at intc.net -*- sam at everquick.net
Sending mail to spambait addresses is a great way to get blocked.
Ditto for broken OOO autoresponders and foolish AV software backscatter.

More information about the NANOG mailing list