nanog mailing list archives
Re: aggregate6 - a fast versatile prefix list compressor
From: Steve Atkins <steve () blighty com>
Date: Fri, 1 Dec 2017 10:09:00 -0800
On Dec 1, 2017, at 2:16 AM, Elmar K. Bins <elmi () 4ever de> wrote: nanog () 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/22I 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
Current thread:
- aggregate6 - a fast versatile prefix list compressor Job Snijders (Dec 01)
- Re: aggregate6 - a fast versatile prefix list compressor Job Snijders (Dec 01)
- Re: aggregate6 - a fast versatile prefix list compressor Julien Goodwin (Dec 01)
- Re: aggregate6 - a fast versatile prefix list compressor Job Snijders (Dec 01)
- Re: aggregate6 - a fast versatile prefix list compressor Elmar K. Bins (Dec 01)
- Re: aggregate6 - a fast versatile prefix list compressor Steve Atkins (Dec 01)
- Re: aggregate6 - a fast versatile prefix list compressor Julien Goodwin (Dec 01)
- Re: aggregate6 - a fast versatile prefix list compressor Job Snijders (Dec 01)
- Re: aggregate6 - a fast versatile prefix list compressor Aliaksei Sheshka (Dec 01)
- Re: aggregate6 - a fast versatile prefix list compressor Job Snijders (Dec 01)