Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

I'm posing this problem because it's reasonably (someone I knew really needs to do it) and because I couldn't think of a good way to do it in Perl. I wrote a solution in C in about a hundred lines, but the algorithm depended on using a pair of linked lists, and there didn't seem to be any efficient translation to Perl or to Perl's data structures.


An ISP has a file that lists all their networks, in CIDR format. (If you don't know what this is, see the explanation below.) However, some of these blocks are parts of larger networks. Where all the subnetworks of a larger network appear in the input, they should be removed and replaced with a line representing the large network.

For example, if these lines appear in the input:

209.152.214.112/30
209.152.214.116/31
209.152.214.118/31
then they should be replaced with this line:
209.152.214.112/29
because the output 209.152.214.112/29 is exactly equal to the union of the three inputs.

If those three lines had been these instead:

209.152.214.112/30
209.152.214.116/32
209.152.214.118/31
then the output would be the same as the input, because there are no complete larger networks that are unions of these. 209.152.214.112/29 is ruled out because the original input did not include the address 209.152.214.117.

If the input contained these lines instead:

209.152.214.112/31
209.152.214.116/31
209.152.214.118/31
then the output would be
209.152.214.112/31
209.152.214.116/30
These two networks cannot be merged into 209.152.214.112/29 because the original input does not include the address 209.152.214.114.

See below for more information about CIDR format network addresses.

You may assume that the input is in order, sorted by ascending IP address. You may assume that if a.b.c.d/n appears in the input, then the low-order (32-n) bits of a.b.c.d will all be 0. For example, 1.2.3.252/29 will never appear; if this network is in the input, it will be represented as 1.2.3.248/29. The input has one network per line, and the output should be in the same format as the input. The output should be minimal, so that if the output is fed back into your program, it is edmitted unchanged because there is nothing more to do.

The ISP has a file with thousands of networks, so the program should be reasonably efficient.

Sample inputs and outputs are available from my web site.


Explanation of CIDR format network addresses

A network number represents a contiguous sequence of IP addresses. It has the form a.b.c.d/m where a, b, c, and d are between 0 and 255, and m is between 2 and 32. a.b.c.d indicates a 32-bit number, as is usual with IP addresses. The netblock a.b.c.d/n represents the network comprising all the IP addresses whose first m bits match the first m bits of the number a.b.c.d, and whose remaining bits have any values at all. For example:

130.91.6.0/32
represents the IP address 130.91.6.0 only.

130.91.6.0/31
represents the two addresses 130.91.6.0 and 130.91.6.1.

130.91.6.0/30
represents the four addresses 130.91.6.0, 130.91.6.1, 130.91.6.2, and 130.91.6.3.

130.91.6.12/30
represents the four addresses 130.91.6.12, 130.91.6.13, 130.91.6.14, and 130.91.6.15.

Sometimes two netblocks can be combined into a single one. For example, the two netblocks

192.241.36.8/30
192.241.36.12/30
happen to represent the same set of addresses as
192.241.36.8/29
If the program input contains the first two netblocks, the program should recognize that and combine them into a single netblock for output.

See Subnetting and CIDR for a more detailed explanation.

--
Mark Dominus
Perl Paraphernalia


In reply to Challenge Problem: Merging Network Addresses by Dominus

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!
  • 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, 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, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            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.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others making s'mores by the fire in the courtyard of the Monastery: (3)
    As of 2014-12-27 09:52 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Is guessing a good strategy for surviving in the IT business?





      Results (176 votes), past polls