Challenge Problem: Merging Network Addressesby Dominus (Parson)
|on Oct 12, 2001 at 01:09 UTC||Need Help??|
Dominus has asked for the
wisdom of the Perl Monks concerning the following question:
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:
18.104.22.168/30then they should be replaced with this line:
22.214.171.124/29because the output 126.96.36.199/29 is exactly equal to the union of the three inputs.
If those three lines had been these instead:
188.8.131.52/30then the output would be the same as the input, because there are no complete larger networks that are unions of these. 184.108.40.206/29 is ruled out because the original input did not include the address 220.127.116.11.
If the input contained these lines instead:
18.104.22.168/31then the output would be
22.214.171.124/31These two networks cannot be merged into 126.96.36.199/29 because the original input does not include the address 188.8.131.52.
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, 184.108.40.206/29 will never appear; if this network is in the input, it will be represented as 220.127.116.11/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:
18.104.22.168/32represents the IP address 22.214.171.124 only.
126.96.36.199/31represents the two addresses 188.8.131.52 and 184.108.40.206.
220.127.116.11/30represents the four addresses 18.104.22.168, 22.214.171.124, 126.96.36.199, and 188.8.131.52.
184.108.40.206/30represents the four addresses 220.127.116.11, 18.104.22.168, 22.214.171.124, and 126.96.36.199.
Sometimes two netblocks can be combined into a single one. For example, the two netblocks
188.8.131.52/30happen to represent the same set of addresses as
184.108.40.206/29If 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.