> Who knows how Mikrotik is actually doing the comparison, but if they do it this way then after 32 IP's it's definitely faster.
They're very likely using IP sets - http://ipset.netfilter.org/ On 6 December 2012 15:36, Justin Miller <[email protected]> wrote: > >From a computer science perspective, it's faster to compare a single IP > to a large list of IPs all at once vs each IP individually. > > Because IP's are 32bits, the worst case scenario for telling if an IP is > in a list of IPs using a balanced binary search tree is 32 comparisons or > less. > > Create the tree starting with the first bit and each branch down is 0 > (left) or 1 (right), each additional level down compares the next bit in > the IP. The IP is in the list if you are able to traverse the tree 32 > levels down. Each level down removes half of the remaining IP space. You > may know if the IP isn't in the list after the first comparison, > significantly saving time. It's a 50/50 chance each level for elimination! > > There is overhead creating the list, but you've only got to create it once > for any given set of IPs. There is also insertions and deletions for trees. > > Who knows how Mikrotik is actually doing the comparison, but if they do it > this way then after 32 IP's it's definitely faster. > > A list of 1000 IPs is not necessarily more efficent then 2000 or even 200k > using this method. > > Like most algorithm, it's memory vs cpu. This one grows more in memory > then in cpu the larger the list gets. > > Justin Miller > VA SkyWire > > > On Dec 5, 2012, at 1:54 PM, Butch Evans wrote: > > > On Tue, 2012-12-04 at 15:57 -0500, David Hulsebus wrote: > >> Yes, efficiency was what I was asking. I use address lists extensively > >> but the lists are small, never more than a few hundred entries. I was > >> wondering as the list grew to 150-200K entries if it would still be as > >> efficient. We will be extending this drop list to 14 days from 3. > > > > Certainly a rule with an address list size of 1000 is more efficent than > > one with 2000 or more. However, I believe you will find that a single > > rule with 10k addresses is more efficient that 10 rules with 1000 each. > > I have a ruleset that I am testing right now and the address list grows > > to around 25k addresses and there is very little decrease in cpu > > utilization that I can see when I remove the contents of the list, but > > this is not a "scientific" observation. > > > > -- > > ******************************************************************** > > * Butch Evans * Professional Network Consultation * > > * http://www.butchevans.com/ * Network Engineering * > > * http://store.wispgear.net/ * Wired or Wireless Networks * > > * http://blog.butchevans.com/ * ImageStream, Mikrotik and MORE! * > > * NOTE THE NEW PHONE NUMBER: 702-537-0979 * > > ******************************************************************** > > > > > > > > _______________________________________________ > > Mikrotik mailing list > > [email protected] > > http://www.butchevans.com/mailman/listinfo/mikrotik > > > > Visit http://blog.butchevans.com/ for tutorials related to Mikrotik > RouterOS > > _______________________________________________ > Mikrotik mailing list > [email protected] > http://www.butchevans.com/mailman/listinfo/mikrotik > > Visit http://blog.butchevans.com/ for tutorials related to Mikrotik > RouterOS > -- Jody Botham Senior Network Engineer This E-Mail and its contents may be confidential. Access is only authorised by the intended recipient. The contents of this e-mail may not be disclosed to, or used by, anyone other than the intended recipient, or stored or copied in any medium. If you are not the intended recipient, please advise the sender immediately. Ask4 Ltd. Registered in England & Wales with company number 3980594. Registered Address: Devonshire Green House, 14 Fitzwilliam Street, Sheffield, S1 4JL -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://www.butchevans.com/pipermail/mikrotik/attachments/20121207/e73f9677/attachment.html> _______________________________________________ Mikrotik mailing list [email protected] http://www.butchevans.com/mailman/listinfo/mikrotik Visit http://blog.butchevans.com/ for tutorials related to Mikrotik RouterOS
