Algorithom to find overlaping subnets (Internet IPv4)by chrestomanci (Priest)
|on Sep 18, 2011 at 21:43 UTC||Need Help??|
chrestomanci has asked for the
wisdom of the Perl Monks concerning the following question:
Greetings wise brothers.
I have been given a list of about 50_000 subnets, and asked to find which if any overlap. The largest is probably a /8, I don't know how small the smallest is, but I know that it must be at least a /24. I am looking for advice on an algorithm to use.
Given the large number of subnets to examine, a pairwise comparison between every pair in the list is clearly impractical.
The best algorithm I can think of, is to represent each subnet in a database as a string representing the known bits, (so 192.168.0.0/16 would be represented as the 16 known bits: 1100000010101000), and then sort by the mask and do substring searches in the database
Another idea I had was to construct a tree of up to 32 levels, and populate it with the networks according to their bit patterns. If when inserting a network I find the space taken, I would have found an overlap.
Any other ideas? Is there a standard way of doing this that google has somehow not found for me?