Joel C. Maslak

NAME

Range::Merge - Merges ranges of data including subset/superset ranges

VERSION

version 1.002

SYNOPSIS

  use Range::Merge qw(merge);
  my $output = merge($inrange);

DESCRIPTION

Many problems require merging of ranges. For instance, one can parse a BGP route table where there are a combinatrion of routes and produce ranges that reduce the table size. For instance, an ISP might announce both 192.0.2.0/28 and 192.0.2.16/28 - these could be consolidated as 192.0.2.0/27 (assuming that other constraints, such as having identical data, are met).

IP addresses are one example of this type of data - many variations exist. Because IP addresses can be represented as integers, it is possible to write a generic range merging alogirthm that operates on integers.

FUNCTIONS

merge($ranges)

This is the soul of the Range::Merge module - it merges an array reference of ranges (passed in as the sole argument). The output is an array reference of the merged ranges.

merge_ipv4($cidr)

This is functionally similar to the merge function, except for the type of input it takes. The $cidr parameter must consist of an array reference of array references. Each of the child array references reference of ranges (passed in as the sole argument). The output is an array reference of the merged ranges.

The output is then turned back into CIDRs.

RANGE DATA DEFINITION

Range data is defined as two integers, a start and an end, along with optional data elements. This is represented as an array reference of array references. Note that the "most specific" elements are used for the desired values for a piont on a range. For instance, this is range data:

  [ [0,12,'foo'], [4,8,'bar'] ]

In this case, the desired output of "merged" data would be:

  [ [0,3,'foo'], [4,8,'bar'], [9,12,'foo'] ]

This example is invalid range data:

  [ [0,12,'foo'], [8,14,'bar'] ]

The above data is invalid because of an ambiguity - Does 12 have the value of 'foo' or the value of 'bar'? Thus, an exception will be thrown.

Note that multiple data elements or no data elements can be present, so long as the start and end integers exist for each range value. Thus, this is valid:

  [ [0,12], [4,8] ]

This, too is valid:

  [ [0,12,'foo','baz'], [4,8,'bar','baz'] ]

In this case, we would expect the merged output to look like:

  [ [0,3,'foo','baz'], [4,8,'bar,'baz'], [9,12,'foo','baz'] ]

There is also a variation on this where, instead of a start and end integer, there is an IP address (IPv4 only at this point). For example:

  [ [ '0.0.0.0/4' ], [ '128.0.0.0/1' ] ]

This form is used by the merge_ipv4() function.

AUTHOR

Joel Maslak <jmaslak@antelope.net>

COPYRIGHT AND LICENSE

This software is copyright (c) 2016 by Joel Maslak.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.