algorithm to find IPv4 networks in CIDR notation between two IPv4 addresses

Question

I would like to find out all the IPv4 networks in CIDR notation between those two networks:

10.11.3.64-10.11.3.127
10.11.52.0-10.11.52.255

IPv4 networks should have as short subnet-mask as possible.

It's fairly easy to convert 10.11.3.127 into binary, add 1 and convert back to decimal in order to get the first address of the network. Then convert 10.11.52.0 into binary, subtract 1 and convert back to decimal in order to get the last address of the network. However, any suggestions which algorithm is clever to use in order to find out the CIDR blocks inside the 10.11.3.128-10.11.51.255 range? Just a suggestion in which direction should I think would hopefully be enough :)

Answer 1

I really like this problem, I took a look last night and decided to give it a shot. At this point I have a proof of concept shell script working.

Disclaimer:

1. This is a proof of concept only
2. I kind of reinvented the wheel here as I didn't use any TCP/IP library
3. I didn't implement input validation
4. This code could be much faster if written in a programming language rather than bash, although for this specif network range is not so slow

Another thing worth mentioning is that my understanding of:

IPv4 networks should have as short subnet-mask as possible.

is that we should try from 8 bits reserved to network up to the greatest cidr provided, in this case 25.

OK, let us see the script in action:

[root@TIAGO-TEST2 tmp]# time bash  ip.sh   10.11.3.64/25 10.11.52.0/24 
10.11.3.128/25
10.11.4.0/22
10.11.8.0/21
10.11.16.0/20
10.11.32.0/20
10.11.48.0/22

real    0m48.376s
user    0m6.174s
sys     0m34.644s

Below the code:

#! /bin/bash

function split_octet {
    sed -re "s/\./ /g" <<< "$1"
}

function dec2bin {
    perl -e 'printf "%0'"$1"'b\n",'"$2"';'
}

function bin2dec {
    perl -le 'print 0b'"$1"';'
}

function ip2bin {
    str=""
    for octet in $(split_octet $1); do
        str="${str}$(dec2bin 8 $octet)"
    done
    echo "$str"
}

function bin2ip {
    str=""
    for octet in $(grep -Eo '.{8}' <<< $1); do
        dec=$(bin2dec $octet)
        str="${str}.${dec}"
    done
    echo "$str" | sed -re 's/^\.|\.$//g'
}

function ip2dec {
    ip=$1
    bin2dec $(ip2bin $ip )
}

function dec2ip  {
    dec=$1
    bin2ip $(dec2bin 32 $dec )
}

function AND {
    perl -e '   $a=0b'"$1"' & 0b'"$2"';
                        printf "%032b\n",$a
                    '
}

function OR {
    perl -e '   $a=0b'"$1"' | 0b'"$2"';
                        printf "%032b\n",$a
                    '
}

function NOT {
    perl -le '  $a= (~ 0b'"$1"') & 0xFFFFFFFF; 
                            printf "%032b\n",$a
                     '
}

function get_network {
    ip=$1; mask=$2;

    if [ -n "$ip" -a -n "$mask" ];then
    echo $(bin2ip $(AND $(ip2bin $ip) $(ip2bin $mask)))
        return
    fi

    grep -qP "\d+\.\d+\.\d+.\d+/\d+" <<< "$ip"
    if [ "$?" == 0 ];then
        ip=$(get_ip_from_cidr $1 )
        mask=$(get_mask_from_cidr $1)
        echo $( bin2ip $(AND $(ip2bin $ip) $(ip2bin $mask)))
    fi
}

function get_broadcast {
    ip=$1; mask=$2;

    if [ -n "$ip" -a -n "$mask" ];then
        echo $( bin2ip $(OR $(ip2bin $ip) $(NOT $(ip2bin $mask) ) ))
        return
    fi

    grep -qP "\d+\.\d+\.\d+.\d+/\d+" <<< "$ip"
    if [ "$?" == 0 ];then
        ip=$(get_ip_from_cidr $1 )
        mask=$(get_mask_from_cidr $1)
        echo $( bin2ip $(OR $(ip2bin $ip) $(NOT $(ip2bin $mask) ) ))
    fi

}

function get_ip_from_cidr {
    awk -F/ '{print $1}' <<< "$1"
}

function get_mask_from_cidr {
    mask=$(awk -F/ '{print $2}' <<< "$1")
    mask=$(cidr $mask)
    mask=$(bin2ip $mask)
    echo $mask
}

function cidr {
    perl -e '
                        $n='"$1"';
                        $diff=32-$n;
                        print "1"x$n . "0"x$diff;
                    '
}


snet_cidr=$1
enet_cidr=$2

largest_cidr=$(echo -e "$snet_cidr\n$enet_cidr"| awk -F/ '{print $2}' | sort -rn | head -1 )

snet_dec=$( ip2dec $(get_ip_from_cidr $snet_cidr))
enet_dec=$( ip2dec $(get_ip_from_cidr $enet_cidr))

sbc_ip=$(get_broadcast $snet_cidr)
ebc_ip=$(get_broadcast $enet_cidr)

sbc_dec=$(ip2dec $sbc_ip)
ebc_dec=$(ip2dec $ebc_ip)

counter=$sbc_dec

while [ $counter -lt $enet_dec ];do
    tip=$(dec2ip $counter)
    for cidr in $(seq 8 $largest_cidr) ; do 
        tnet_ip=$(get_network $tip/$cidr)
        tnet_cidr=$tnet_ip/$cidr
        tbc_ip=$(get_broadcast $tnet_cidr)
        tnet_dec=$( ip2dec $(get_ip_from_cidr $tnet_cidr))
        tbc_dec=$(ip2dec $tbc_ip)
        if [ $sbc_dec -lt $tnet_dec -a $enet_dec -gt $tbc_dec ];then
            echo $tnet_cidr 
            counter=$tbc_dec
            break
        fi  
    done
    let counter++
done

Edit It's probably a good idea to explain what those variables are:

1. snet_cidr: start net in cidr notation
2. enet_cidr: end net in cidr
3. snet_dec: start net in decimal
4. enet_dec: end net in decimal
5. sbc_ip: start broadcast ip
6. ebc_ip: end broadcast ip
7. sbc_dec: start broadcast ip
8. ebc_dec: end broadcast ip

And wherever you see tnet or tbc is temp net, temp broadcast, temp because it's inside the loop.

Answer 2

If you want the shortest masks (largest networks) available, start with the lowest address (10.11.3.128) and put on the smallest mask possible, start at the next address and put on the smallest mask possible, etc. Just don't exceed the largest address of the range:

1. 10.11.3.128/25 (10.11.3.128 to 10.11.3.255) anything smaller is invalid
2. 10.11.4.0/22 (10.11.4.0 to 10.11.7.255) anything smaller is invalid
3. 10.11.8.0/21 (10.11.8.0 to 10.11.15.255) anything smaller is invalid
4. 10.11.16.0/20 (10.11.16.0 to 10.11.31.255) anything smaller is invalid
5. 10.11.32.0/20 (10.11.32.0 to 10.11.47.255) /19 is valid, but would go too far
6. 10.11.48.0/22 (10.11.48.0 to 10.11.51.255) /20 and /21 are valid, but would go too far

Looking at this in binary, it becomes obvious. Masks are ANDed with the subnet (any position with a zero in either the subnet or mask becomes a zero; a position must have ones in both the subnet and mask to have a one). If you AND a subnet and a mask, and it doesn't equal the subnet, it is invalid.

All IP address calculations need to be done in binary. The dotted-decimal notation is fine for human readability, but should not be used to do try to do IP address calculations.