Re: aggregate6 - a fast versatile prefix list compressor

[Job Snijders]

On Fri, Dec 01, 2017 at 12:35:13PM -0500, Aliaksei Sheshka wrote:
> On Thu, Nov 30, 2017 at 3:07 PM, Job Snijders  wrote:
> > I re-implemented the venerable 'aggregate' tool (by Joe Abley & co)
> > in python under the name of 'aggregate6'. The 'aggregate6' tool is
> > faster and also has IPv6 support.
> >
> > https://github.com/job/aggregate6
>
> Nice!
> "-t" from the "classic" IPv4 "aggregate" would be nice. I've sent a
> pull request.

That's best approach to get things done: make suggestions and submit
patches. Thank you!

Kind regards,

Job

Re: aggregate6 - a fast versatile prefix list compressor

[Aliaksei Sheshka]

On Thu, Nov 30, 2017 at 3:07 PM, Job Snijders  wrote:
> Dear NANOG,
>
> I re-implemented the venerable 'aggregate' tool (by Joe Abley & co) in
> python under the name of 'aggregate6'. The 'aggregate6' tool is faster
> and also has IPv6 support.
>
> https://github.com/job/aggregate6
>

Nice!
"-t" from the "classic" IPv4 "aggregate" would be nice. I've sent a
pull request.

Re: aggregate6 - a fast versatile prefix list compressor

[Steve Atkins]

> On Dec 1, 2017, at 2:16 AM, Elmar K. Bins  wrote:
> 
> na...@studio442.com.au (Julien Goodwin) wrote:
> 
>>> The first optimisation is to remove any supplied prefixes which are
>>> superfluous because they are already included in another supplied
>>> prefix. For example, 2001:67c:208c:10::/64 would be removed if
>>> 2001:67c:208c::/48 was also supplied.
>>> 
>>> The second optimisation identifies adjacent prefixes that can be
>>> combined under a single, shorter-length prefix. For example,
>>> 2001:67c:208c::/48 and 2001:67c:208d::/48 can be combined into the
>>> single prefix 2001:67c:208c::/47. As an IPv4 exampl: 10.0.0.0/24 and
>>> 10.0.1.0/24 can be joined into 10.0.0.0/23.
>> 
>> Will it catch cases like:
>> 10.0.0.0/24 10.0.1.0/24 10.0.2.0/23 -> 10.0.0.0/22
> 
> I guess the developers will have implemented a loop that runs until no
> more optimizations have been found. Which would of course catch it as
> 
> Iteration 1
> 10.0.0.0/24 + 10.0.1.0/24
> -> 10.0.0.0/23
> 
> Iteration 2
> 10.0.0.0/23 + 10.0.2.0/23
> -> 10.0.0.0/22
> 

The usual trick is to build a prefix tree then walk the tree, which catches
this sort of case in one step.

Cheers,
  Steve

Re: aggregate6 - a fast versatile prefix list compressor

[Job Snijders]

On Fri, Dec 01, 2017 at 09:09:38PM +1100, Julien Goodwin wrote:
> Will it catch cases like:
> 10.0.0.0/24 10.0.1.0/24 10.0.2.0/23 -> 10.0.0.0/22

Yes it does!

hanna:~ job$ echo 10.0.0.0/24 10.0.1.0/24 10.0.2.0/23 | aggregate6
10.0.0.0/22
hanna:~ job$

Kind regards,

Job

Re: aggregate6 - a fast versatile prefix list compressor

[Elmar K. Bins]

na...@studio442.com.au (Julien Goodwin) wrote:

> > The first optimisation is to remove any supplied prefixes which are
> > superfluous because they are already included in another supplied
> > prefix. For example, 2001:67c:208c:10::/64 would be removed if
> > 2001:67c:208c::/48 was also supplied.
> > 
> > The second optimisation identifies adjacent prefixes that can be
> > combined under a single, shorter-length prefix. For example,
> > 2001:67c:208c::/48 and 2001:67c:208d::/48 can be combined into the
> > single prefix 2001:67c:208c::/47. As an IPv4 exampl: 10.0.0.0/24 and
> > 10.0.1.0/24 can be joined into 10.0.0.0/23.
> 
> Will it catch cases like:
> 10.0.0.0/24 10.0.1.0/24 10.0.2.0/23 -> 10.0.0.0/22

I guess the developers will have implemented a loop that runs until no
more optimizations have been found. Which would of course catch it as

Iteration 1
10.0.0.0/24 + 10.0.1.0/24
-> 10.0.0.0/23

Iteration 2
10.0.0.0/23 + 10.0.2.0/23
-> 10.0.0.0/22

Re: aggregate6 - a fast versatile prefix list compressor

[Julien Goodwin]

On 01/12/17 07:27, Job Snijders wrote:
> Someone suggested I should clarify what 'aggregate6' actually does :-)
> 
> aggregate6 takes a list of IPv4 and/or IPv6 prefixes in conventional
> format, and performs two optimisations to attempt to reduce the length
> of the prefix list.
> 
> The first optimisation is to remove any supplied prefixes which are
> superfluous because they are already included in another supplied
> prefix. For example, 2001:67c:208c:10::/64 would be removed if
> 2001:67c:208c::/48 was also supplied.
> 
> The second optimisation identifies adjacent prefixes that can be
> combined under a single, shorter-length prefix. For example,
> 2001:67c:208c::/48 and 2001:67c:208d::/48 can be combined into the
> single prefix 2001:67c:208c::/47. As an IPv4 exampl: 10.0.0.0/24 and
> 10.0.1.0/24 can be joined into 10.0.0.0/23.

Will it catch cases like:
10.0.0.0/24 10.0.1.0/24 10.0.2.0/23 -> 10.0.0.0/22

> The above two optimalisations are useful in context of firewall rule
> generation or generation of BGP prefix-list filters.

Or being a nice citizen and rationalising your announcements.

Re: aggregate6 - a fast versatile prefix list compressor

[Job Snijders]

Someone suggested I should clarify what 'aggregate6' actually does :-)

aggregate6 takes a list of IPv4 and/or IPv6 prefixes in conventional
format, and performs two optimisations to attempt to reduce the length
of the prefix list.

The first optimisation is to remove any supplied prefixes which are
superfluous because they are already included in another supplied
prefix. For example, 2001:67c:208c:10::/64 would be removed if
2001:67c:208c::/48 was also supplied.

The second optimisation identifies adjacent prefixes that can be
combined under a single, shorter-length prefix. For example,
2001:67c:208c::/48 and 2001:67c:208d::/48 can be combined into the
single prefix 2001:67c:208c::/47. As an IPv4 exampl: 10.0.0.0/24 and
10.0.1.0/24 can be joined into 10.0.0.0/23.

The above two optimalisations are useful in context of firewall rule
generation or generation of BGP prefix-list filters.

Kind regards,

Job

aggregate6 - a fast versatile prefix list compressor

[Job Snijders]

Dear NANOG,

I re-implemented the venerable 'aggregate' tool (by Joe Abley & co) in
python under the name of 'aggregate6'. The 'aggregate6' tool is faster
and also has IPv6 support.

https://github.com/job/aggregate6

Installation is can be done through 'pip', or your operating system's
package manager (if they carry the 'aggregate6' tool). 

$ pip install aggregate6

Example use:

$ echo 10.0.0.0/16 10.0.0.0/24 2000::/4 3000::/4 | aggregate6
10.0.0.0/16
2000::/3

Note that 'aggregate6' can also be imported as module in your own python
project:

>>> import from aggregate6 import aggregate
>>> aggregate(["10.0.0.0/8", "10.0.0.0/24"])
['10.0.0.0/8']
>>>

Related to the above example, NTT uses 'aggregate6' as library in their
network automation toolchain to help compress firewall rules.

When using a dump from the IPv4 Default-Free Zone, it appears that
'aggregate6' can deaggregate that list ~ 50 times faster than
'aggregate'. However the tradeoff is that 'aggregate6' uses a bit more
memory.

Aggregate6 has been tested with pypy, python2 and python3; and can be
used both from the command line or as python module. Aggregate6 is
published under the 2-Clause BSD license.

Kind regards,

Job