Raw Firewall Address-list Performance

RouterOS General
1

As Mikrotik doesn’t want to support Flow-Spec, I’m looking into what we can do to work around that.

How scalable are address-lists? Say I have a DDoS detection appliance that drops offending IPs into an address list. Say it puts 10k, 100k, 500k IPs in there during an attack. Would ROS on a reasonable platform handle it well? It’d be going to a firewall rule similar to:

/ip firewall raw
add action=drop chain=prerouting dst-port=53 protocol=udp src-address-list=UDP_53

I don’t know specifically what actions as I haven’t implemented the detection appliance yet to know exactly how it would classify each attack and thus how to mitigate. I’d have one of these for each type of attack.

  • syn_flood: TCP packets with enabled SYN flag
  • udp_flood: flood with UDP packets (so recently in result of amplification)
  • icmp flood: flood with ICMP packets
  • ip_fragmentation_flood: IP packets with MF flag set or with non zero fragment offset
  • DNS amplification
  • NTP amplification
  • SSDP amplification
  • SNMP amplification

Would a CCR1036-8G-2S+ or CCR1072-1G-8S+ be sufficient or am I looking at CHR on a stout x86 box? I would already have CHRs up for the main routing. I’d likely have these scrubbing boxes setup on the side and trigger a new route from the PEs to the scrubbing boxes for the affected IPs. Other traffic would pass through the normal paths to their destinations, without the encumbrance of the scrubbing box.

2

In RE of address list performance:

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.

We don’t know 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
The Brother’s Wisp