I am trying to create an algorithm to filter TCP/IP packets based on both the source and destination IP addresses as well as destination and source ports. Basically, I have a set of rules which specifies a range of IP addresses, e.g. 192.168.0.0/24, for both the destination and source IP address and an equivalent for destination and source ports ([1:65535]).
In short, given a packet, I would like to find which rules are relevant for it's IP addresses and ports. Currently the only idea I have so far is to build a Trie out of either the source or destination IP addresses which would quickly filter either one, but would still require a linear search for the rest of the parameters and result in a complexity of O(n) for nrules. Is there a better way which would reduce the time complexity?
Assuming you encode an IP as an integer in the range [0, 2^32] you can define source and destination ranges by a four dimensional rectangle
min = [src_ip_min, src_prt_min, dst_ip_min, dst_prt_min]
max = [src_ip_max, src_prt_max, dst_ip_max, dst_prt_max]
You can index multi-dimensional rectangles using a spatial index structure like an R-Tree to answer spatial queries efficiently. In your case you will need a range search (range = 0) to get all rectangles (=rules) that apply to a certain query.
4 dimensions should still be indexable pretty well, so depending on your range distribution you can expect a query time closer to O(log n)