3

Mostly in all routers and operating systems the Longest Prefix Match algorithm is used for searching the trie of IPv4 addresses.
Packet filters like Iptables don't need some special data structure for finding IPv4 addresses.

I need to implement some data structure, where I could efficiently (log(N)) find IPv4 addresses, which are specified in firewall rules. But there could also be IPv4 address prefixes and ranges. These ranges could be intersected and have exclusions (exclude one range or IP from another one). But I think exclusions could be resolved in time of constructing (deploying) data structure.
For each entry (IP-address or range or subnet prefix) I need to store a pointer to bit-vector which represents firewall rule-set. So the first set bit in this vector is the first rule that matches this source IP (e.g.).
Thus the Longest Prefix Match doesn't fit.
I was considering the Interval Tree or Red-Black tree but I'm not sure that these are the most efficient ways.

P.S. inserting and deleting is not a big problem but it would be good to be also log(N)

0
1

Your problem is somewhat underspecified as you don't clearly describe what you want to associate with a CIDR range. Do you just care for presence/absence of an entry for some IP address or range, or do you need to store more info, like a router?

If you only store one bit of information, you may without loss of generality use non-overlapping CIDR ranges which can be stored in a suitable sorted data structure (tree, sorted array, whatever) yielding log(N) lookup times. Inserting ranges can make use of the fact that CIDR ranges can be merged when they have the same prefix length and their prefixes only differ in the last bit. When deleting ranges, you would find overlapping ranges which are either smaller or equal to the range being deleted, otherwise you get a larger range that needs to be split into halves and then work on the half overlapping the range to be deleted. It is very likely that a tree structure has both log(N) lookup times as well as better than O(N) insert and delete times, but I've not looked at it rigorously.

5
  • For each entry (IP-address or range or subnet) I need to store a bit-vector which represents firewall rule-set. So the first set bit in this vector is the first rule that matches this source IP (e.g.)
    – red0ct
    Jul 25 '21 at 13:17
  • The user of firewall (who create the rules) can design rules with IP ranges with intersections and exclusions
    – red0ct
    Jul 25 '21 at 13:24
  • "or do you need to store more info, like a router" - I didn't get what you mean. I want to store a pointer to bit-vector. Each IP address / range / prefix points to bit-vector data structure which represents firewall rule set.
    – red0ct
    Jul 26 '21 at 8:37
  • That's what I meant - you don't need a simple one-bit value but more data, so my approach doesn't work directly. Jul 26 '21 at 8:43
  • Thanks anyway! Have you any other ideas, clarifications?
    – red0ct
    Jul 26 '21 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.