Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options

Re^2: Algorithom to find overlaping subnets (Internet IPv4)

by chrestomanci (Priest)
on Sep 20, 2011 at 13:47 UTC ( #926943=note: print w/replies, xml ) Need Help??

in reply to Re: Algorithom to find overlaping subnets (Internet IPv4)
in thread Algorithom to find overlaping subnets (Internet IPv4)

Thanks for your informative reply.

If I had know that mod::Net::IPTrie or mod::Tree::Trie existed I would have use them, unfortunately I did not know they existed and did not know the terminology to search for them on CPAN, and I thought it would take to long to implement something myself.

Instead I wrote some code using string representations of the binary bits in a database using DBIx::Class.

My DBIC table defintion looks like this:

__PACKAGE__->table('tblSubNet'); __PACKAGE__->add_columns( 'id' => { data_type=>'int', is_auto_increment=>1 + }, 'ip' => { data_type=>'varchar', size=>15 + }, 'mask' => { data_type=>'int' + }, 'name' => { data_type=>'varchar', size=>255, is_nullable=>1 + }, 'start' => { data_type=>'int' + }, # the IP address as A 32 bit number 'bitpattern' => { data_type=>'varchar', size=>32 + }, ); __PACKAGE__->set_primary_key('id'); __PACKAGE__->add_unique_constraint(['bitpattern']);

Once I have populated the table of subnets, I then search it like this:

my $order_by_size_rs = $all_subnets_rs->search({'source'=>$source},{'o +rder_by'=>{'-asc','mask'}}); while( my $network = $order_by_size_rs->next ) { my $overlaping_nets_rs = $net_rs->search({ 'mask' => { '>', $network->mask() }, 'bitpattern' => { 'like', $network->bitpattern().'%' }, }, { 'order_by'=>{'-asc',['mask','start']} }); if( $overlaping_nets_rs->count ) { printf "Subnet %s/%d (%s) has %d overlaps:\n", $network->ip, $network->mask, $network->name, $overlaping_nets_rs->count; ... # Code to add the overlaps to the report. } }

Using this algorithm I was able to search through the 50_000 subnets searching for overlaps in about 10 minutes. (On a 3GHz Linux box).

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://926943]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (6)
As of 2017-12-16 21:08 GMT
Find Nodes?
    Voting Booth?
    What programming language do you hate the most?

    Results (459 votes). Check out past polls.