I recently had to work on this problem, and needed a fast implementation.

I found the easiest and fastest way was to use a Trie as mentioned by rg0now.

I used the random generator which BrowserUk supplied to generate the random dataset.

My version processed the dataset in less than two seconds on my 3.8GHz Linux box.

I don't have nice sorted output though. It should be trivial to build up a data structure as you go if you need sorted output...

Here's the code:

#! /usr/bin/env perl

use strict;
use warnings;
use autodie;
use 5.10.0;

use Tree::Trie;
use Net::IP qw(ip_splitprefix ip_iptobin ip_get_mask);

my $trie = Tree::Trie->new();

while (<>) {
    chomp;
    my ($ip, $len) = ip_splitprefix($_);

    my $binip = ip_iptobin($_,4);

    my $trie_entry = substr($binip, 0, $len);

    $trie->deepsearch('prefix');
    my $data = $trie->lookup_data($trie_entry);

    if ($data) {
        say "'$_' is contained by or equals '$data'";
    }
    else {
        $trie->deepsearch('choose');
        my $data = $trie->lookup_data($trie_entry);

        if ($data) {
            say "'$_' contains '$data'";
        }
    }
    $trie->add_data($trie_entry, $_);
}

[download]

Some truncated sample output:

time ./trie_overlap.pl <50k_ips

...

'116.15.84.0/23' is contained by or equals '116.14.0.0/15'
'108.245.172.0/24' is contained by or equals '108.244.0.0/14'
'13.238.173.128/25' is contained by or equals '13.224.0.0/11'
'37.179.224.0/19' is contained by or equals '37.179.192.0/18'
'73.147.0.0/17' is contained by or equals '73.144.0.0/12'
'150.152.0.0/13' contains '150.154.0.0/18'
'171.93.16.0/22' is contained by or equals '171.0.0.0/9'
'80.246.128.0/21' is contained by or equals '80.240.0.0/13'

real    0m1.957s
user    0m1.832s
sys     0m0.124s

[download]

Anyone see any issues with this? It hasn't been completely battle tested yet :)

Best,

Jim

In reply to Re^2: Algorithom to find overlaping subnets (Internet IPv4) by jimpudar
in thread Algorithom to find overlaping subnets (Internet IPv4) by chrestomanci

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.