Search algorithm for IPv4 networks in CIDR notation between two IPv4 addresses

Question

I would like to know all IPv4 networks in CIDR notation between these two networks:

10.11.3.64-10.11.3.127 10.11.52.0-10.11.52.255 

IPv4 networks should have as little subnet mask as possible.

It’s easy enough to convert 10.11.3.127 to a binary file, add 1 and convert it back to decimal to get the first network address. Then convert 10.11.52.0 to binary, subtract 1 and convert back to decimal to get the last network address. However, any suggestions which algorithms are smart to use to find out the CIDR blocks within the range 10.11.3.128-10.11.51.255 ? Just a suggestion in which direction, in my opinion, it would be enough to hope :)

Answer 1

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

• 10.11.3.128/25 (10.11.3.128 - 10.11.3.255) nothing less is invalid
• 10.11.4.0/22 ​​(10.11.4.0 - 10.11.7.255) nothing less is invalid
• 10.11.8.0/21 (10.11.8.0 - 10.11.15.255) nothing less is invalid
• 10.11.16.0/20 (10.11.16.0 - 10.11.31.255) nothing less is invalid
• 10.11.32.0/20 (10.11.32.0 - 10.11.47.255) / 19 valid but will be too far
• 10.11.48.0/22 ​​(10.11.48.0 - 10.11.51.255) / 20 and / 21 are valid, but will be too far

Looking at it in binary, it becomes obvious. Masks have ANDed with a subnet (any position with zero in the subnet or mass becomes equal to zero, the position must be both in the subnet and in the mask). If you are both a subnet and a mask, and it does not match the subnet, it is invalid.

All IP address calculations must be in binary format. The dotted decimal notation is great for human reading, but should not be used to perform IP address calculations.

Answer 2

I really like this problem, I took a look last night and decided to do it. At this point, I have proof of work of the shell script shell.

Denial of responsibility:

• This is just a proof of concept.
• I kind of reinvented the wheel here, since I did not use any TCP / IP library
• I did not implement input validation
• This code can be much faster if it is written in a programming language rather than bash, although for this particular range of network the network is not so slow

Another thing worth mentioning is that my understanding:

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

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

OK, let's 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 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 

Change Perhaps it is a good idea to explain what these variables are:

• snet_cidr: start network in cidr notation
• enet_cidr: end net in cidr
• snet_dec: start network in decimal
• enet_dec: end net in decimal
• sbc_ip: start ip broadcast
• ebc_ip: end broadcast ip
• sbc_dec: start ip broadcast
• ebc_dec: end broadcast ip

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