[93139] in North American Network Operators' Group
Re: register.com down sev0?
daemon@ATHENA.MIT.EDU (Tony Li)
Fri Oct 27 11:51:27 2006
Date: Fri, 27 Oct 2006 08:45:48 -0700
From: Tony Li <tony.li@tony.li>
To: Vadim Antonov <avg@kotovnik.com>
Cc: 'Daniel Senie' <dts@senie.com>, nanog@merit.edu
In-Reply-To: <Pine.LNX.4.44.0610270118070.9419-100000@gato.kotovnik.com>
Errors-To: owner-nanog@merit.edu
Hi Vadim!
Vadim Antonov wrote:
> On Thu, 26 Oct 2006, Tony Li wrote:
>
>> Further, uRPF is frequently a very inefficient means of implementing BCP
>> 38. Consider that you're going to either compare the source address
>> against a table of 200,000 routes...
>
> That would be, well, about 6 memory reads.
>
> Radix trees are great.
They are indeed. If a radix trie is indeed used, you would expect to
see about log2(200,000) + 1 = 19 reads on average.
>> or against a handful of prefixes that
>> you've statically configured in an ACL.
>
> Which will take much longer with line-by-line sequential matching.
Fortunately, modern ACL implementations frequently use TCAMs (1 read) or
tree based structures (log2(handful) + 1) as well.
As always, the details of a particular implementation are everything. YMMV.
Tony
