1、无分类编址无分类编址 CIDR概述概述1.网络前缀网络前缀划分划分子网在一定程度上缓解子网在一定程度上缓解了互联网在了互联网在发展中发展中遇到遇到的的困难。然而在困难。然而在 1992 年互联网仍然年互联网仍然面临三个面临三个必须必须尽早解尽早解决的决的问题：问题：n(1)B 类地址在类地址在 1992 年已分配了近一半，眼看就要在年已分配了近一半，眼看就要在 1994 年年 3 月全部分配完毕！月全部分配完毕！n(2)互联网主干网上的路由表中的项目数急剧增长（从互联网主干网上的路由表中的项目数急剧增长（从几千个增长到几万个）。几千个增长到几万个）。n(3)整个整个 IPv4 的地址空间最终将
2、全部耗尽。的地址空间最终将全部耗尽。IP 编址问题的演进编址问题的演进 n1987 年，年，RFC 1009 就指明了在一个划分子网就指明了在一个划分子网的网络中可同时使用几个不同的子网掩码的网络中可同时使用几个不同的子网掩码。n使用使用变长子网掩码变长子网掩码 VLSM(Variable Length Subnet Mask)可进一步提高可进一步提高 IP 地址资源的利地址资源的利用率。用率。n在在 VLSM 的基础上又进一步研究出无分类编址的基础上又进一步研究出无分类编址方法，它的正式名字是方法，它的正式名字是无分类域间路由选择无分类域间路由选择 CIDR(Classless Inter-
3、Domain Routing)。CIDR 最主要的特点最主要的特点 nCIDR 消除了传统的消除了传统的 A 类、类、B 类和类和 C 类地址以类地址以及划分子网的概念，因而可以更加有效地分配及划分子网的概念，因而可以更加有效地分配 IPv4 的地址空间。的地址空间。nCIDR使用各种长度的使用各种长度的“网络前缀网络前缀”(network-prefix)来代替分类地址中的网络号和子网号。来代替分类地址中的网络号和子网号。nIP 地址从三级编址（使用子网掩码）又回到了地址从三级编址（使用子网掩码）又回到了两级编址。两级编址。无分类的两级编址无分类的两级编址 n无分类的两级编址的记法是：无分类的
4、两级编址的记法是：nCIDR 使用使用“斜线记法斜线记法”(slash notation)，它又，它又称为称为 CIDR 记记法法，即在，即在 IP 地址面加上一个斜线地址面加上一个斜线“/”，然后，然后写上网络前缀所占的位数（这个数值对应于三级编址写上网络前缀所占的位数（这个数值对应于三级编址中子网掩码中中子网掩码中 1 的个数）的个数）。例如：例如：220.78.168.0/24IP地址地址:=,(4-3)32位位网络前缀网络前缀主机号主机号CIDR 地址块地址块 nCIDR 把网络前缀都相同的连续的把网络前缀都相同的连续的 IP 地址组成地址组成“CIDR 地址块地址块”。n128.14
5、.32.0/20 表示的地址块表示的地址块共有共有 212 个地址个地址（因为（因为斜斜线后面的线后面的 20 是网络前缀的位数是网络前缀的位数，所以这个地址的主机，所以这个地址的主机号是号是 12 位）。位）。n这个地址块的起始地址是这个地址块的起始地址是 128.14.32.0。n在不需要指出地址块的起始地址时，也可将这样的地址块简在不需要指出地址块的起始地址时，也可将这样的地址块简称为称为“/20 地址块地址块”。n128.14.32.0/20 地址块的最小地址：地址块的最小地址：128.14.32.0n128.14.32.0/20 地址块的最大地址：地址块的最大地址：128.14.47
6、.255n全全 0 和全和全 1 的主机号地址一般不使用。的主机号地址一般不使用。128.14.32.0/20 表示的地址（表示的地址（212 个个地址）地址）10000000 00001110 00100000 0000000010000000 00001110 00100000 0000000110000000 00001110 00100000 0000001010000000 00001110 00100000 0000001110000000 00001110 00100000 0000010010000000 00001110 00100000 0000010110000000 0
7、0001110 00101111 1111101110000000 00001110 00101111 1111110010000000 00001110 00101111 1111110110000000 00001110 00101111 1111111010000000 00001110 00101111 11111111所有地址所有地址的的 20 位位前缀都是前缀都是一样的一样的最小地址最小地址最大地址最大地址路由路由聚合聚合(route aggregation)n一个一个 CIDR 地址块可以表示很多地址，这种地址的聚地址块可以表示很多地址，这种地址的聚合常称为合常称为路由聚合路由聚
8、合，它使得路由表中的一个项目可以，它使得路由表中的一个项目可以表示很多个（例如上千个）原来传统分类地址的路由表示很多个（例如上千个）原来传统分类地址的路由。n路由聚合有利于路由聚合有利于减少减少路由器之间的路由选择信息的交路由器之间的路由选择信息的交换，从而提高了整个互联网的性能。换，从而提高了整个互联网的性能。n路由聚合也称为路由聚合也称为构成超构成超网网(supernetting)。nCIDR 虽然不使用子网了，但仍然使用虽然不使用子网了，但仍然使用“掩码掩码”这一名这一名词（但不叫子网掩码）。词（但不叫子网掩码）。n对于对于/20 地址块，它的掩码是地址块，它的掩码是 20 个连续的个连
9、续的 1。斜线记斜线记法中的数字就是掩码中法中的数字就是掩码中1的个数。的个数。CIDR 记法的其他形式记法的其他形式 n10.0.0.0/10 可可简写简写为为 10/10，也就是把点分十进制中，也就是把点分十进制中低位连续的低位连续的 0 省略。省略。n10.0.0.0/10 隐含地指出隐含地指出 IP 地址地址 10.0.0.0 的的掩码掩码是是 255.192.0.0。此掩码可表示。此掩码可表示为：为：n网络前缀的后面加一个网络前缀的后面加一个星号星号*的表示的表示方法，如方法，如 00001010 00*，在星号，在星号*之前是网络前缀，而星号之前是网络前缀，而星号*表示表示 IP
10、地址中的主机号，可以是任意值地址中的主机号，可以是任意值。25519200掩码中有掩码中有 10 个连续的个连续的 111111111 11000000 00000000 00000000CIDR 前缀长度前缀长度点分十进制点分十进制包含的地址数包含的地址数相当于包含分类的网络数相当于包含分类的网络数/13255.248.0.0512 K8个个B类或类或2048个个C类类/14255.252.0.0256 K4个个B类或类或1024个个C类类/15255.254.0.0128 K2个个B类或类或512个个C类类/16255.255.0.064 K1个个B类或类或256个个C类类/17255.2
11、55.128.032 K128个个C类类/18255.255.192.016 K64个个C类类/19255.255.224.08 K32个个C类类/20255.255.240.04 K16个个C类类/21255.255.248.02 K8个个C类类/22255.255.252.01 K4个个C类类/23255.255.254.05122个个C类类/24255.255.255.02561个个C类类/25255.255.255.1281281/2个个C类类/26255.255.255.192641/4个个C类类/27255.255.255.224321/8个个C类类常用的常用的 CIDR 地址地址
12、块块构成超网构成超网 n前缀长度不超过前缀长度不超过 23 位的位的 CIDR 地址块都包含了多个地址块都包含了多个 C 类类地址。地址。n这些这些 C 类地址合起来就构成了超网。类地址合起来就构成了超网。nCIDR 地址块中的地址数一定是地址块中的地址数一定是 2 的整数次幂。的整数次幂。n网络前缀越短，其地址块所包含的地址数就越多。网络前缀越短，其地址块所包含的地址数就越多。而而在三级结构的在三级结构的IP地址中，划分子网是使网络前缀变长地址中，划分子网是使网络前缀变长。nCIDR 的的一个一个好处是好处是：可以可以更加有效地更加有效地分配分配 IPv4 的的地地址空间，可根据客户的需要分
13、配适当大小址空间，可根据客户的需要分配适当大小的的 CIDR 地地址址块。块。CIDR 地址块划分举例地址块划分举例 互联互联网网206.0.68.0/22206.0.64.0/18ISP大学大学 X一系一系二系二系三系三系四系四系206.0.71.128/26206.0.71.192/26206.0.68.0/25206.0.68.128/25206.0.69.0/25206.0.69.128/25206.0.70.0/26206.0.70.64/26206.0.70.128/26206.0.70.192/26206.0.70.0/24206.0.71.0/25206.0.71.0/2620
14、6.0.71.64/26206.0.71.128/25206.0.68.0/23 单位单位 地址地址块块 二进制二进制表示表示 地址数地址数 ISP 206.0.64.0/18 11001110.00000000.01*16384 大学大学 206.0.68.0/22 11001110.00000000.010001*1024 一系一系 206.0.68.0/23 11001110.00000000.0100010*512 二系二系 206.0.70.0/24 11001110.00000000.01000110.*256 三系三系 206.0.71.0/25 11001110.0000000
15、0.01000111.0*128 四系四系 206.0.71.128/25 11001110.00000000.01000111.1*128CIDR 地址块划分举例地址块划分举例 互联网互联网206.0.68.0/22206.0.64.0/18ISP大学大学 X一系一系二系二系三系三系四系四系206.0.71.128/26206.0.71.192/26206.0.68.0/25206.0.68.128/25206.0.69.0/25206.0.69.128/25206.0.70.0/26206.0.70.64/26206.0.70.128/26206.0.70.192/26206.0.70.0
16、/24206.0.71.0/25206.0.71.0/26206.0.71.64/26206.0.71.128/25206.0.68.0/23 单位单位 地址地址块块 二进制二进制表示表示 地址数地址数 ISP 206.0.64.0/18 11001110.00000000.01*16384 大学大学 206.0.68.0/22 11001110.00000000.010001*1024 一系一系 206.0.68.0/23 11001110.00000000.0100010*512 二系二系 206.0.70.0/24 11001110.00000000.01000110.*256 三系三系
17、 206.0.71.0/25 11001110.00000000.01000111.0*128 四系四系 206.0.71.128/25 11001110.00000000.01000111.1*128这个这个 ISP 共有共有 64 个个 C 类网络。如果不采用类网络。如果不采用 CIDR 技术，技术，则在与该则在与该 ISP 的路由器交换路由信息的每一个路由器的路的路由器交换路由信息的每一个路由器的路由表中，就需要有由表中，就需要有 64 个项目。但采用地址聚合后，只需个项目。但采用地址聚合后，只需用路由聚合后的用路由聚合后的 1 个项目个项目 206.0.64.0/18 就能找到该就能找
18、到该 ISP。2.最长前缀匹配最长前缀匹配n使用使用 CIDR 时，路由表中的每个项目由时，路由表中的每个项目由“网络网络前缀前缀”和和“下一跳地址下一跳地址”组成。组成。在查找路由表在查找路由表时可能会得到不止一个匹配结果。时可能会得到不止一个匹配结果。n应当从匹配结果中选择具有最长网络前缀的路应当从匹配结果中选择具有最长网络前缀的路由：由：最长前缀最长前缀匹配匹配(longest-prefix matching)。n网络前缀越长，其地址块就越小，因而路由就网络前缀越长，其地址块就越小，因而路由就越越具体具体(more specific)。n最长前缀匹配又称为最长前缀匹配又称为最长匹配最长匹
19、配或或最佳匹配。最佳匹配。最长前缀匹配举例最长前缀匹配举例收到的分组的目的地址收到的分组的目的地址 D=206.0.71.130路由表中的项目：路由表中的项目：206.0.68.0/221 206.0.71.128/252查找路由表中的第查找路由表中的第 1 个个项目：项目：AND D=206.0.01000111.130第第 1 个项目个项目 206.0.68.0/22 的掩码的掩码 M 有有 22 个连续的个连续的 1。M=11111111 11111111 11111100 00000000因此只需把因此只需把 D 的第的第 3 个字节转换成二进制。个字节转换成二进制。M=1111111
20、1 11111111 11111100 00000000206.0.01000100.0与与 206.0.68.0/22 匹配匹配!最长前缀匹配举例最长前缀匹配举例收到的分组的目的地址收到的分组的目的地址 D=206.0.71.130路由表中的项目：路由表中的项目：206.0.68.0/221 206.0.71.128/252查找路由表中的第查找路由表中的第 2 个个项目：项目：AND D=206.0.71.10000010第第 2 个项目个项目 206.0.71.128/25 的掩码的掩码 M 有有 25 个连续的个连续的 1。M=11111111 11111111 11111100 000
21、00000因此只需把因此只需把 D 的第的第 4 个字节转换成二进制。个字节转换成二进制。M=11111111 11111111 11111111 10000000206.0.71.10000000与与 206.0.71.128/25 匹配匹配!最长前缀匹配举例最长前缀匹配举例D AND(11111111 11111111 11111100 00000000)=206.0.68.0/22 匹配匹配D AND(11111111 11111111 11111111 10000000)=206.0.71.128/25 匹配匹配选择两个匹配的地址中更具体的一个，即选择选择两个匹配的地址中更具体的一个，
22、即选择最长前缀的地址最长前缀的地址。3.使用二叉线索查找路由表使用二叉线索查找路由表n当路由表的项目数很大时，怎样设法减小路由表的查找当路由表的项目数很大时，怎样设法减小路由表的查找时间就成为一个非常重要的问题。时间就成为一个非常重要的问题。n为了进行更加有效的查找为了进行更加有效的查找，通常是将无分类编址的路由，通常是将无分类编址的路由表存放在一种表存放在一种层次的数据结构层次的数据结构中，然后自中，然后自上而下地按层上而下地按层次次进行查找。这里最常用的就是进行查找。这里最常用的就是二叉二叉线索线索(binary trie)。nIP 地址中从左到右的比特值决定了从根结点逐层向下层地址中从左
23、到右的比特值决定了从根结点逐层向下层延伸的路径，而二叉线索中的各个路径就代表路由表中延伸的路径，而二叉线索中的各个路径就代表路由表中存放的各个地址。存放的各个地址。n为了提高二叉线索的查找速度，广泛使用了各种压缩技为了提高二叉线索的查找速度，广泛使用了各种压缩技术。术。用用 5 个前缀构成的二叉线索个前缀构成的二叉线索 32 位的位的 IP 地址地址 唯一唯一前缀前缀 01000110 00000000 00000000 000000000100 01010110 00000000 00000000 000000000101 01100001 00000000 00000000 0000000
24、0011 10110000 00000010 00000000 0000000010110 10111011 00001010 00000000 0000000010111000011111110从二叉线索的根节点自顶向下的深度最多有从二叉线索的根节点自顶向下的深度最多有32层，每一层对应于层，每一层对应于IP地址中的一位。一个地址中的一位。一个IP地址存入二叉线索的规则很简单。先检查地址存入二叉线索的规则很简单。先检查IP地址左边的第一位，如地址左边的第一位，如为为 0，则第一层的节点就在根节点的左下，则第一层的节点就在根节点的左下方；如方；如为为 1，则在右下方。然后再检查地址的第二位，构造出第二，则在右下方。然后再检查地址的第二位，构造出第二层的节点。依此类推，直到唯一前缀的最后一位。层的节点。依此类推，直到唯一前缀的最后一位。
