[opensource-wg] new open source tool: prefix list aggregator

Hi,

I made tools to aggregate prefix lists, repo is here:
https://gitlab.com/qratorlabs/plag

There are two tools:
plageq - makes strictly equal aggregation of prefixes
plagmax - maximally aggregates, discarding subsets

They should be already quite useful, so everybody is welcome to use
them and leave feedback.

I have only found some alternatives available:

1) https://github.com/job/aggregate6
This is almost the same, but it is very slow for big lists and eats
zillion bytes of memory. My tools need only a couple of seconds for
lists of ~2M prefixes and around ~100M of memory (including spare
memory, which is not used, total amount is fixed at compile time now)

2) bgpq4 can also do aggregation while fetching the prefix list. It
does it fast too, but it is not perfect. My tool on the other hand
generates perfect minimization in case of plagmax. And I suppose
minimal possible number of lines in case of plageq (actually it is
depth-limited in config now, but for deeper depthes there should be
extreme number of prefixes in the list)

Here are some examples, comparing it to bgpq4. bgpq4 spends most of
the time requesting prefix lists and waiting for a response, so do not
pay much attention to its times.

# time bgpq4 -4 -F '%n/%l\n' AS2914:AS-GLOBAL >ntt4.0
real    0m 30.38s
user    0m 4.29s
sys     0m 0.32s

# time bgpq4 -4 -A -F '%n/%l{%a,%A}\n' AS2914:AS-GLOBAL >ntt4.eb
real    0m 30.41s
user    0m 3.98s
sys     0m 0.24s

# time bgpq4 -4 -A -R 32 -r 1 -F '%n/%l\n' AS2914:AS-GLOBAL >ntt4.mb
real    0m 31.71s
user    0m 3.94s
sys     0m 0.22s

# time ./plag/plageq <ntt4.0 >ntt4.ep
max nodes: 29.03%, 3044261 / 10485760, 34.84MB / 120.00MB
real    0m 0.97s
user    0m 0.94s
sys     0m 0.03s

# time ./plag/plagmax <ntt4.0 >ntt4.mp
max nodes: 2.83%, 296843 / 10485760, 2.26MB / 80.00MB
real    0m 0.47s
user    0m 0.44s
sys     0m 0.02s

# time bgpq4 -6 -F '%n/%l\n' AS2914:AS-GLOBAL-v6 >ntt6.0
real    0m 7.25s
user    0m 1.44s
sys     0m 0.03s

# time bgpq4 -6 -A -F '%n/%l{%a,%A}\n' AS2914:AS-GLOBAL-v6 >ntt6.eb
real    0m 7.14s
user    0m 1.22s
sys     0m 0.06s

# time bgpq4 -6 -A -R 128 -r 1 -F '%n/%l\n' AS2914:AS-GLOBAL-v6 >ntt6.mb
real    0m 8.04s
user    0m 1.26s
sys     0m 0.04s

# time ./plag/plageq <ntt6.0 >ntt6.ep
max nodes: 11.38%, 1192943 / 10485760, 13.65MB / 120.00MB
real    0m 0.40s
user    0m 0.37s
sys     0m 0.02s

# time ./plag/plagmax <ntt6.0 >ntt6.mp
max nodes: 2.57%, 269912 / 10485760, 2.06MB / 80.00MB
real    0m 0.22s
user    0m 0.19s
sys     0m 0.03s

# cat ntt4.0 ntt6.0 | shuf | time ./plag/plageq >ntt.ep
max nodes: 40.41%, 4237202 / 10485760, 48.49MB / 120.00MB
real    0m 2.44s
user    0m 2.20s
sys     0m 0.07s

# cat ntt4.0 ntt6.0 | shuf | time ./plag/plagmax >ntt.mp
max nodes: 10.16%, 1065244 / 10485760, 8.13MB / 80.00MB
real    0m 1.33s
user    0m 1.04s
sys     0m 0.04s

And here are number of lines in the resulted files:

  2038959 ntt4.0 <- unaggregated ipv4 prefixes

   414558 ntt4.eb <- bgpq4 equal set
   395831 ntt4.ep <- plag equal set

   128522 ntt4.mb <- bgpq4 minimal
    99794 ntt4.mp <- plag minimal

   540047 ntt6.0 <- unaggregated ipv6 prefixes

    80764 ntt6.eb <- bgpq4 equal set
    79875 ntt6.ep <- plag equal set

    38193 ntt6.mb <- bgpq4 minimal
    38023 ntt6.mp <- plag minimal