Compute largest summary prefix-length with Python

by Przemek

I'm sure many of you had to compute summary network given a number of subnets. It's one of those rare occasions when you have to dust off binary maths skills that you had to pick up while learning ip address subnetting.

In this blog post I want to discuss related problem, namely working out the largest prefix length needed to encompass provided prefix lengths. I realise it's a mouthful so I'll show some examples before moving onto solution and corresponding Python code.

Contents

Problem description

Now, an explanation is in order, because it's much easier to grasp something when we know how the problem, and its solution, relate to the real world. Here we simply want to know what size of aggregate network is needed if we are provided with sizes of required subnets. This could for example apply to network sizing requirement for branch offices or server estate.

Examples

We'll run through some example to get better intuition for the problem.

Example 1

Let's say we've been told there are 4 server networks being deployed and we worked out we need the below prefixes for them:

x.x.x.x/26
x.x.x.x/26
x.x.x.x/26
x.x.x.x/26

You look at it and say, that's easy! 2 x /26 is /25 and 2 x /25 is /24. And you're right, it is! All of the prefix lengths are the same so it's immediately obvious what the resulting prefix length should be.

Example 2

This time our server guys decided that some of the networks will have less hosts than the others. After talking to them you settled down on the below prefixes:

x.x.x.x/27
x.x.x.x/27
x.x.x.x/26
x.x.x.x/26

Things are becoming more interesting, we can easily work out that 2 x /27 is /26, but then we end up with 3 x /26, or after reducing as much as we can, with 1 x /25 and 1 x /26. Luckily it's not your first rodeo and you can see that we'll need summary with prefix length /24 to fit all of these. We'll have some space left, but that's ok as long as we can fit all of the prefixes.

Example 3

Now our colleagues from branch office division want us to allocate summary prefix for a country to which the company is expanding its operations. You talk to them and find out that office sizes will vary quite a lot. Resulting prefix requirements look like so:

x.x.x.x/28
x.x.x.x/27
x.x.x.x/27
x.x.x.x/26
x.x.x.x/25
x.x.x.x/24

This is some serious stuff here. Doing it by hand is going to be error prone and certainly won't be much fun.

Wait a second, aren't we this new kind of engineers, the automate all the things/devops everything kind? Well yes, we are!

A bit of Python and some precisely aimed Google searches can surely solve this problem!

Solution and algorithm

Key to arriving at solution to our problem is the insight we gained from working out answers to above examples. It turns out that we can use some binary math in a fashion similar to computing address summaries.

Before we continue we'll establish a few facts about prefixes lengths and their representation.

Let's take /27. We know this can be represented by subnet mask 255.255.255.224. It also follows that a number of addresses for this prefix may be calculated using formula 2^(32 - pfxlen), when talking about IPv4. Taking /27 we arrive at 2^5 = 32.

This formula, 2^(address_length - prefix_length) will serve as a basis of our algorithm. It turns out that we can just add number of possible addresses for each prefixes, and then compute number of bits is needed to represent the sum.

Plugging numbers and variables into our algorithm we arrive at following pseudocode:

sum = 0
for pfx_len in prefix_lengths
    sum += 2^(address_length - prefix_length)

required_prefix_length = address_length - bit_size(sum)

With that let's go through prefix lengths from Example 1:

prefix_lengths = [26, 26, 26, 26]
sum = 0
pfx_len = 26
sum += 2^(32-26) # sum = 64
pfx_len = 26
sum += 2^(32-26) # sum = 128
pfx_len = 26
sum += 2^(32-26) # sum = 192
pfx_len = 26
sum += 2^(32-26) # sum = 256

required_prefix_length = address_length - bit_size(256) # required_prefix_length = 32 - 9 => 23

Ok, something's not right here, we computed /24 by hand but this gives us /23?

Nice catch! Since we're working with prefixes and not actual binary numbers we need to introduce a small correction to our algorithm.

Why is that? Notice that in the real world we are working with address AND prefix length, and not with prefix lengths alone. For example given address/prefix length 10.0.0.0/30 we need just 2 bits to represent 4 different addresses:

10.0.0.0
10.0.0.1
10.0.0.2
10.0.0.3

0 = b00
1 = b01
2 = b10
3 = b11

But actually 3 bits are needed to represent decimal number 4, e.g. b100 .

Our algorithm needs a tiny tweak to take this into account, and all that is needed is to subtract 1 from sum of prefix_lengths. This will correct cases where our resulting sum would equal powers of 2.

Time to make modification to our pseudocode:

sum = 0
for pfx_len in prefix_lengths
    sum += 2^(address_length - prefix_length)

required_prefix_length = address_length - bit_size(sum - 1)

And run it against Examples 1 and 2.

We already know the sum for Example 1 so we'll skip the first part of computations.

...
sum = 256

required_prefix_length = address_length - bit_size(256 - 1) # required_prefix_length = 32 - 8 => 24

Great, now the result with inputs from Example 1 matches number we computed by hand.

With our shiny, and seemingly correct, algorithm, we can move onto implementing it in Python.

Python implementation

Below is the listing of the function taking iterable of prefix lengths and computing corresponding largest prefix length. Optional flag "ipv6", set to False by default, enables computation for IPv6 prefix lengths.

def max_parent_pfx_len(pfx_lengths, ipv6=False):
    """Computes largest parent prefix length given child prefix length(s).

    >>> max_parent_pfx_len([26,27,28,29])
    24

    :param pfx_lengths: iterable: prefix lengths
    :param ipv6: bool: set to False for IPv4 prefix lengths, True for IPv6
    :return: int: computed largest prefix length
    """
    if ipv6:
        BIT_SIZE = 128
    else:
        BIT_SIZE = 32

    try:
        pfx_lengths = [int(pl) for pl in pfx_lengths]
    # One of the inputs is not a number. Catch and re-raise.
    except ValueError:
        raise ValueError("Only numbers are accepted.")

    # It only makes sense for prefix lengths to be be between 1 < pfx_len <= BIT_SIZE
    if any(True for pl in pfx_lengths if pl < 1 or pl > BIT_SIZE):
        raise ValueError(
            "Prefix length has to be between 1 < 'pfx_len' <= {}".format(BIT_SIZE)
        )

    len_sum = 0
    for pfx_len in pfx_lengths:
        len_sum += 2 ** (BIT_SIZE - int(pfx_len))

    # Compute pfx len, sub 1 to adjust for sum equal to powers of 2
    # In Python2 we might overflow int into long so need to get type(len_sum)
    pfx_len_needed = BIT_SIZE - type(len_sum).bit_length(len_sum - 1)

    if pfx_len_needed < 0:
        raise ValueError("Input prefix lengths too large to compute parent length.")

    return pfx_len_needed

Now all that's left is for you to import the function and you're all set!

I'm also including an executable script that wraps around the above function, which you can find in my Github repository @ https://github.com/progala/max-parent-pfx-length. This will allow you to provide lengths from the command line, or even compute multiple required lengths for input piped from the text file. See some usage examples below.

Example usage

  • Provide one or more prefix lengths, separated by commas
(venv) [przemek@quasar max_parent_pfx_length]$ ./max_parent_pfx_length.py 27,27,29,29,29
25

(venv) [przemek@quasar max_parent_pfx_length]$ ./max_parent_pfx_length.py 96,96,96,97,97 -ipv6
94
  • Compute max prefix lengths for multiple lines of inputs stored in a file
(venv) [przemek@quasar max_parent_pfx_length]$ cat ex_pfx_lengths_ipv4.txt | xargs -L 1 ./max_parent_pfx_length.py
26
26
24
24
23

(venv) [przemek@quasar max_parent_pfx_length]$ cat ex_pfx_lengths_ipv6.txt | xargs -L 1 ./max_parent_pfx_length.py -ipv6
119
94
78
46
29

That's it, another problem solved nicely by a bit of Python. I hope some of it will be of use for you in the future.