[Mikrotik] Mikrotik Digest, Vol 60, Issue 3

Justin Miller mikrotik at dynstatic.net
Thu Dec 6 09:36:17 CST 2012


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
> Mikrotik at mail.butchevans.com
> http://www.butchevans.com/mailman/listinfo/mikrotik
> 
> Visit http://blog.butchevans.com/ for tutorials related to Mikrotik RouterOS



More information about the Mikrotik mailing list