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

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).