plag/README.md

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.

$ 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 tool for example to fetch the list of prefixes and pipe its output to the tools:

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 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