Indexed ranged search algorithm for IP Addresses

Question

Given an ACL list with 10 billion IPv4 ranges in CIDR notiation or between two IPs:

x.x.x.x/y
x.x.x.x - y.y.y.y

What is an effecient search/indexing algorithm for testing that a given IP address meets the critera of one or more ACL ranges?

Lets assume most ACL range definitions span a great number of class C blocks.

Indexing points via hash tables is easy but try as I might have not been able to come up with a reasonable method for detecting which points are covered by a large list of "lines".

Had some thoughts like indexing hints at a certain level of detail -- say pre-computing at the class C level each ACL that covered that point but the table would be too large.. Or some sort of KD tree to dynamically set levels of detail.

Also had the thought that maybe there are collision detection algorithms out there that can address this.

Any hints or pointers in the right direction?

Answer 1

You can look at the Interval tree to find all intervals that overlap with any given interval or point.

For non-overlapping ip-ranges, you can use a b-tree or compact-tries like Judy arrays (64-bits) for indexing and searching (Store the start-ip as key and the end-ip as value).

Answer 2

The simple Radix Tree which has been used in the longest prefix match Internet route lookups, can be scaled to hold nodes that represent the larger CIDR subnets that overlap other smaller ones. A longest match lookup will traverse these nodes which will also be selected to get the entire set of CIDR subnets that match an IP address.

Now, to hold the IP ranges in the same tree, we can convert each range into a set of CIDR subnets. This can be always done though the set may have lots of subnets (and even some host IPs -- that is, IP/32 kind CIDR addresses).

Answer 3

You have 10 billion rules to match 4 billion possible addresses?

Make a table of 4 billion addresses. For each of the 10 billion rules, 'paint' the addresses it applies to, doing something sensible when two or more rules apply to the same address.