在两个IPv4地址之间查找CIDR表示法下的IPv4网络的算法

Question

我想找出那两个网络之间以CIDR表示法表示的所有IPv4网络。

10.11.3.64-10.11.3.127
10.11.52.0-10.11.52.255

IPv4网络应该尽可能使用短的子网掩码。

将 10.11.3.127 转换成二进制，加上 1 并再次转换回十进制，即可获得网络的第一个地址。然后将 10.11.52.0 转换成二进制，减去 1 并再次转换为十进制，即可获得网络的最后一个地址。然而，对于如何找出 10.11.3.128-10.11.51.255 范围内的CIDR块，有什么聪明的算法建议吗？只是一些方向上的建议应该就足够了 :)

- Martin

---

解释：IPv4网络应该尽可能使用较短的子网掩码。 - hek2mgl

@hek2mgl 这意味着IPv4前缀应尽可能大。例如，网络范围10.11.3.128-10.11.51.255可以用10.11.3.128/25的CIDR表示法表示，然后使用/24前缀从10.11.4.0/24到10.11.51.0/24，而实际上这些/24可以聚合。 - Martin

使用32位前缀，从10.11.3.128/0到10.11.51.255/0进行IPV4地址转换。这是最大可能的前缀，因此我才会问。 - hek2mgl

在我看来，“IPv4网络的子网掩码应该尽可能短”这句话是明确的。它的意思是网络掩码部分应该尽可能短，即包含尽可能少的“1”。 - Martin

什么算法？您已经分配了10.11.3.X，这意味着在您转移到10.12.X.X之前，任何子网都不能大于/24。#L2subnet - Sammitch

Answer 1

我非常喜欢这个问题，昨晚研究了一下并决定尝试一下。目前我已经有一个概念证明的shell脚本在运行。

免责声明：

1. 这只是一个概念证明
2. 我在这里重新发明了轮子，因为我没有使用任何TCP/IP库
3. 我没有实现输入验证
4. 如果用编程语言而不是bash编写，这段代码可能会更快，但对于这个特定的网络范围来说并不是很慢

另外值得一提的是，我的理解是：

IPv4网络应该尽可能使用最短的子网掩码。

也就是说，我们应该从保留8位网络位开始，一直到提供的最大cidr，即25。

好的，让我们看看脚本的运行情况：

[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

以下是代码：

#! /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

编辑：解释一下这些变量可能是个好主意：

1. snet_cidr：CIDR表示法中的起始网络
2. enet_cidr：CIDR表示法中的结束网络
3. snet_dec：十进制表示法中的起始网络
4. enet_dec：十进制表示法中的结束网络
5. sbc_ip：起始广播IP
6. ebc_ip：结束广播IP
7. sbc_dec：十进制表示法中的起始广播IP
8. ebc_dec：十进制表示法中的结束广播IP

无论何时看到tnet或tbc，都是临时网络、临时广播，因为它们在循环内部。

- Tiago Lopo

Answer 2

如果您想要最短的掩码（最大的网络），请从最低地址开始（10.11.3.128），并戴上尽可能小的掩码，从下一个地址开始并戴上尽可能小的掩码，以此类推。只需不超过范围的最大地址即可：

1. 10.11.3.128/25（10.11.3.128到10.11.3.255），任何更小的都是无效的。
2. 10.11.4.0/22（10.11.4.0到10.11.7.255），任何更小的都是无效的。
3. 10.11.8.0/21（10.11.8.0到10.11.15.255），任何更小的都是无效的。
4. 10.11.16.0/20（10.11.16.0到10.11.31.255），任何更小的都是无效的。
5. 10.11.32.0/20（10.11.32.0到10.11.47.255），/19是有效的，但会超出范围。
6. 10.11.48.0/22（10.11.48.0到10.11.51.255），/20和/21是有效的，但会超出范围。

看到二进制代码, 就很明显了。掩码与子网进行与运算（任何具有零位的位置都会变成零; 只有在子网和掩码中都有一的位才会变成一）。如果您对一个子网和掩码执行与运算，结果不等于子网，则它是无效的。

所有IP地址计算都需要使用二进制进行。十进制点表示法可以用于人类可读性，但不应用于IP地址计算。

- Ron Maupin