https://gitlab.com/qratorlabs/plag.git

# plag

Plag is a couple of tools to optimize a list of IP (v4 or v6) prefixes.
The tools read prefix list on stdin and output the result to stdout.

 - plagmax - returns a minimal superset of prefixes (loose mode)
 - plageq - aggregates to equal set of prefixes with submasks

## plagmax

`plagmax` aggregates prefixes in loose mode, in case where all subprefixes
are also allowed.
So in the output all subprefixes are ignored and neighbour prefixes are folded.

### Example

Input:

```
10.0.0.0/24
10.0.1.0/24
10.0.2.0/24
10.0.2.1/32
10.0.3.0/24
```

Output:

```
10.0.0.0/22
```

## plageq

`plagmax` aggregates prefixes in strict mode.
So it does not add or remove prefixes, but aggregates sets of subprefixes
with the same mask into larger prefixes with a submask.
It tries to get the minimal number of prefixes in its output.

### Example

Input:

```
10.0.0.0/24
10.0.1.0/24
10.0.2.0/24
10.0.2.1/32
10.0.3.0/24
```

Output:

```
10.0.0.0/22{24,24}
10.0.2.1/32
```

# Building

You will need only a C compiler and a standard library to build the tools.
A simple `make` run should do the job.

```bash
$ make
gcc -O3 -o lib.o -c lib.c
gcc -O3 -o plagmax plagmax.c lib.o
gcc -O3 -o plageq plageq.c lib.o
```

# Running

The tools read stdin where they expect IP prefixes one per line.
Prefixes are of the standard form: `<IP>[/<mask>]`.
Both IPv4 and IPv6 are allowed, you can freely mix them
and the input doesn't need to be sorted.
Mask part is optional, in this case prefix is considered a single IP
and the default of `32` for IPv4 and `128` for IPv6 is used.

`plagmax` outputs simple prefixes in the same format and
`plageq` outputs prefixes with added submask range:  
`<IP>/<mask>{<low>,<high>}`  
This matches all prefixes, having masks in range `<low>`-`<high>`
(inclusive) that lie inside the prefix `<IP>/<mask>`.
In case `<mask> = <low> = <high>` the submasks part is omitted.
This notation of submasks is used in `bird` routing daemon.

You can use [bgpq4](https://github.com/bgp/bgpq4) tool for example
to fetch the list of prefixes and pipe its output to the tools:

```bash
bgpq4 -4 -F '%n/%l\n' as-set-name | ./plageq > as-set-name.ipv4.strict.txt
bgpq4 -6 -F '%n/%l\n' as-set-name | ./plagmax > as-set-name.ipv6.loose.txt
```

Tools also output to stderr some statistics of using preallocated memory.

# Benchmarks

Here are some performance tests. You can see how effective and fast
the tools are. The times are not throughly measured, so take it as indicative
only. The tools have also been compared with the analogous functions of
[bgpq4](https://github.com/bgp/bgpq4) tool.
It also aggregates and does it amost as fast, and almost as good.
But still its aggregation is not perfect.

Test sets:

 - ripe{4,6}: route attributes from route objects in the RIPE DB (unsorted)
 - radb{4,6}: route attributes from route objects in the RADB (unsorted)
 - ntt{4,6}: AS2914:AS-GLOBAL snapshot taken with bgpq4 (sorted)

Test cases (for bgpq4 a local cache of the real response is used):

 - uniq: `sort -u <source | wc -l`
 - plageq/plagmax: `plageq <source | wc -l`
 - bgpq4 (eq): `bgpq4 -4 -A -F '%n/%l{%a,%A}\n' AS-TEST | wc -l` for IPv4
 - bgpq4 (max): `bgpq4 -4 -R 32 -r 1 -A -F '%n/%l\n' AS-TEST | wc -l` for IPv4

## Number of prefixes

|             |  ripe4  | ripe6  |   radb4   |  radb6  |   ntt4    |  ntt6   |
| :---------- | ------: | -----: | --------: | ------: | --------: | ------: |
| source      | 424 813 | 52 506 | 1 351 748 | 166 172 | 2 038 959 | 540 047 |
| uniq        | 394 241 | 49 568 | 1 086 347 | 149 782 | 2 038 959 | 540 047 |
| plageq      | 129 678 | 28 657 |   259 805 |  37 919 |   395 831 |  79 875 |
| bgpq4 (eq)  | 135 690 | 28 830 |   269 235 |  38 341 |   414 558 |  80 764 |
| plagmax     |  41 447 | 18 636 |    87 643 |  19 733 |    99 794 |  38 023 |
| bgpq4 (max) |  66 040 | 18 692 |   101 174 |  19 786 |   128 522 |  38 193 |

## Processing time (user)

|             | ripe4 | ripe6 | radb4 | radb6 | ntt4 | ntt6 |
| :---------- | :---- | :---- | :---- | :---- | :--- | :--- |
| uniq        |  0.15 |  0.01 |  0.57 |  0.03 | 0.59 | 0.12 |
| plageq      |  0.19 |  0.05 |  0.53 |  0.12 | 0.87 | 0.31 |
| bgpq4 (eq)  |  0.36 |  0.05 |  0.99 |  0.15 | 0.94 | 0.3  |
| plagmax     |  0.1  |  0.02 |  0.31 |  0.03 | 0.37 | 0.15 |
| bgpq4 (max) |  0.45 |  0.06 |  1.12 |  0.18 | 0.81 | 0.29 |

## Memory usage

|             | ripe4 | ripe6 | radb4 | radb6 | ntt4 | ntt6 |
| :---------- | ----: | ----: | ----: | ----: | ---: | ---: |
| source size |  6.4M |  0.9M |   21M |  3.1M |  31M |  10M |
| plageq      |  8.5M |  2.7M |   21M |  4.8M |  35M |  14M |
| plagmax     |  1.1M |  1.0M |  2.4M |  1.2M | 2.3M | 2.1M |