基于IPv4地址的无分类编址CIDR技术研究

2017-12-02贺兴亚杨云

软件导刊 2017年11期

贺兴亚+杨云

摘要：为提高IPv4地址空间利用率，IETF提出无类域间路由CIDR地址结构。分析无分类编址CIDR与分类编址的转换、CIDR工作方式、地址分配方法与标记技术，推导最长地址前缀匹配查找算法。提出基于CIDR的快速计算地址块、网络ID与构建超网方法。研究表明，无分类编址CIDR与分类编址都是基于IPv4地址的分配方法，均可用无分类编址CIDR表示。

关键词关键词：计算机网络；无分类编址；IPv4；可变长子网掩码

DOIDOI：10.11907/rjdk.171835

中图分类号：TP393

文献标识码：A文章编号文章编号：16727800（2017）011020605

0引言

为解决IPv4地址资源匮乏、IPv4地址分类带来的资源浪费问题，IETF（因特网工程任务组）试图通过设置“内部IP地址”、“可变长子网掩码VLSM”、“无分类编址CIDR”等技术，解决IPv4地址资源管理问题，提高IPv4地址使用效率。

由于IPv4地址设计本身结构性矛盾（32位）无法解决，只有通过IPv6地址（128位）解决。而目前Internet基础设施大部分不支持IPv6，其应用推广技术遇到瓶颈，试图通过“双协议栈技术”、“隧道技术”等方法解决[1，2]。IPv4到IPv6的过渡也遇到了困难[3]：双栈技术解决了网络能力问题，但IPv4与IPv6不能互通，同时存在能用IPv4为何还要用IPv6的疑问；隧道解决了孤岛问题[4]，但IPv4与IPv6仍然不能互通，同时跨越不同网络时，必须与双栈共同使用。清华大学李星[5]教授等提出的“翻译技术”概念，试图实现IPv4与IPv6互联互通，翻译解决了互通问题，但存在单点故障及应用层协议支持问题，因此每一种过渡技术都无法单独使用。

无分类编址CIDR正式名字是“无分类域间路由CIDR （Classless InterDomain Routing）”[6]，它是目前解决IPv4地址资源匮乏、资源浪费的最好方法。无分类编址CIDR与分类编址一样，都是IPv4地址的分配方法。

1无分类编址CIDR概述

1.1CIDR研究目的

1.1.1问题提出

某企业用300台计算机构建一个局域网，要对这些主机分配IP地址，请给出一种分配方案。讨论：①分配一个C类地址。一个C类地址仅有256个IP地址，地址数量不够，使用2个C类地址，必须增加一台路由器，否则许多主机不能直接通信，同时成本增加；②分配一个B类地址。一个B类地址共有256×256个IP地址，地址数量太多，形成浪费。

1.1.2问题分析

采用的IP地址是分类编址，使得IP地址资源分配不合理。需找到一种IP地址分配方法，可以根据用户需求，自由分配或组合IP地址，不受分类地址的束缚。

CIDR是一种无分类编址技术，消除了传统A类、B类、C类地址以及划分子网的概念[7]，可以更加有效地分配 IPv4 的地址空间，解决以前分类地址策略的低效性[8]。

通过划分子网可以提高IP地址使用效率，减少了数据交换，但加重了路由器负担，路由器的路由表项呈指数级增长，影响了路由器转发效率。为了解决路由器中路由表项过多问题，通过“可变长子网掩码VLSM”可以部分緩解路由器压力，减少路由器路由表项，但不能从根本上解决路由表项过多问题，提高路由器工作效率，这是因为VLSM是基于分类的IPv4地址。

无分类编址CIDR通过“地址块”概念，可以大大减少路由器路由表项[9]。

1.2无分类编址CIDR含义

CIDR记为 IP地址：：= {<网络前缀>， <主机号>} 或CIDR地址= <网络前缀>/<主机号>

（1）IP 地址从三级编址（使用子网掩码）回到二级编址。CIDR使用各种长度的“网络前缀”代替分类地址中的网络号与子网号；使用二级编址简化了路由表结构、路由表项，可以提高路由器转发效率。

（2）“斜线记法”与分类IP地址都是IPv4地址的分配方法。CIDR不采用传统的标准IPv4地址分类方法，而采用“斜线记法”表示IP地址，但无法从地址本身直接判断网络号的长度。对于无分类IP地址：200.16.23.1/20 =11001000 00010000 00010111 00000001，/20被称为网络前缀长度（或地址前缀长度），11001000 00010000 0001被称为地址前缀比特值（或网络号），0111 00000001被称为主机号。

（3）CIDR将剩余IP地址按可变大小的地址块分配。与传统的标准分类IP地址及子网地址划分方式相比，CIDR是以任意二进制倍数的大小来分配地址。

（4）CIDR将网络前缀都相同、连续的 IP 地址组成“CIDR地址块” 。这是理解CIDR时需要重点分析的内容，因为它直接关系到对CIDR概念的理解与对CIDR技术的掌握。①CIDR地址块。一个CIDR地址块由地址块的起始地址（地址块中地址数值最小一个）与地址块中地址数来定义。如果一个IP地址的前N位与一个CIDR地址块的前缀相同，这个地址则属于这个CIDR地址块，也可以说是与CIDR地址块的前缀匹配。因为IPv4地址度总是32位，N位长的CIDR前缀就意味着地址里32N位不匹配。这些位有232N种不同的组合，即232N个IPv4地址与CIDR地址块的前缀匹配。前缀越短就能匹配越多地址，越长就匹配得越少。一个地址可能与多个长度不同的CIDR前缀匹配；②地址聚合、路由聚合。由于一个CIDR地址块可以表示很多地址，在路由表中就利用CIDR地址块查找目的网络（这种地址的聚合称为“路由聚合”），路由聚合有利于减少路由器之间的路由选择信息交换，提高整个Internet的性能；③构建超网。将地址前缀数（网络号值）与网络前缀长度相同、个数是2的幂的地址块组成“超网”。endprint

2分类编址与无分类编址比较

本节用图例解析CIDR结构特征。

2.1分类编址表示

分类编址中每一类地址都被划分为固定数目的地址块，并且每一个地址块大小固定（见图1-图5）。

2.2用无分类编址表示分类编址

使用无分类编址可以表示分类编址中的A、B、C、D、E类地址，其对应关系见图6-图10。

3无分类编址CIDR技术

3.1工作方式

CIDR将所有IP地址与子网掩码翻译为二进制符号；将IP地址分为32个值的集合，代替在分类编址系统中使用的4个值；网络大小有了更多变化；CIDR不定义基于IP地址的缺省子网掩码，而是根据实际需要确定。

3.2以任意二进制倍数大小分配地址

从CIDR的表示可知，CIDR是通过网络前缀分配地址块，而网络前缀的取值范围为0～255。其对应关系如表1所示。

3.3CIDR地址块计算

无分类编址地址块由地址块的起始地址（地址块中数值最小）与最大地址（地址块中数值最大）定义。

首先，根据网络前缀长度确定地址前缀长度（网络号长度）与主机号长度，明确1与0的分界处（对应字节），再将IP地址中对应字节处的十进制数用二进制数表示。其次，计算最小地址，将按照网络前缀长度确定的IP地址主机号部分全部取0，计算其对应的二进制数，所得值即为最小地址；同理，计算最大地址，将按照网络前缀长度确定的IP地址主机号部分全部取1，计算其对应的二进制数，所得值即为最大地址；地址块范围为最小地址～最大地址。

对于地址162.82.0.0/11计算其所属地址块。先找出掩码中1与0的交界处，发生在第2个字节（8+3=11），再将十进制数82用二进制数表示为01010010，取其前3位，并把后5位都写成0，即010 00000，它等于十进制数64，因此，最小地址为162.64.0.0。同样将后5位都写成1，即010 11111，它等于十进制数95，最大地址为162.95.255.255。所以地址162.82.0.0/11包含在地址块162.64.0.0 /11 ～ 162.95.255.255/11中。

通过计算可以发现：斜线记法除了表示一个IP地址（或地址块）外，同时还提供了其它一些重要信息：

（1）地址块162.82.0.0/11中含有221个主机号。

（2）地址聚合：地址前缀数相同均为162.64。

162.64.0.0/11，10100010 01000000 00000000 00000000

162.82.0.0/11，10100010 01010010 00000000 00000000

162.95.255.255/11， 1010001001111111 111111111 11111111

（3）通过无分类地址可以计算网络ID，最小地址恰为子网网络地址，最大地址恰为子网广播地址。

3.4标记技术分析

3.4.1分类编址转换为无分类编址

分类编址子网掩码中，连续“1”的个数即为无分类编址的网络前缀长度（见表2）。

3.4.2無分类编址计算网络ID

根据无分类编址CIDR中网络前缀长度，确定地址前缀长度，计算出地址前缀值（最小地址）即为网络ID（见表3）。

3.4.3无分类编址最长前缀匹配

在配置基于CIDR的网络时，查找路由表时可能会得到不止一个匹配结果。因为网络前缀越长，其地址块就越小，因而路由就越具体，所以应当从匹配结果中选择具有最长网络前缀的路由，这称为“最长前缀匹配”。

显然，若一个目的IP地址同时与两个（或以上）CIDR地址块匹配，则网络前缀短的地址块包含网络前缀长的地址块。

表4说明，目的IP地址为206.0.71.130的数据报，由于其与206.0.68.0/22及206.0.71.128/25均匹配，根据最长前缀匹配原则，最终路由选择为206.0.71.128/25。

匹配

目的IP地址与表项2网络前缀作与运算10.217.112.0/20匹配 √

对于表5的路由表，考虑4个目的地址10.1.0.14、10.1.4.6、10.2.1.3、10.4/16：①10.1.0.14中两条路由都符合，根据最长掩码匹配原则，下一跳地址应该是192.168.2.2；②10.1.4.6 只与第二条路由网段匹配，所以下一跳地址为192.168.3.3；③10.2.1.3 与哪条都不匹配，所以只能走默认路由，下一跳地址为192.168.1.1；③10.4/16 与哪条都不匹配，将被路由器丢弃。

当采用无分类编址进行路由转发时，若未启动IP Classless命令，若目的IP地址不在路由表中，将采取丢包策略，而不会走默认路由。

IP Classless命令最早在cisco IOS 10.0被介绍，在cisco IOS 11.3后，IP Classless就缺省有效了。其作用为：①IP classless命令作用于路由转发进程，告诉路由器在无分类环境下工作；②它能让路由器超越分类网络的边界，根据最长匹配条目转发数据包；③当目的网络没有出现在路由表中时，通过默认路由转发数据包，而不是简单丢弃；③如果路由器工作在分类编址环境下，当目的网络出现在路由表中但无具体网络匹配时，防火墙将丢弃数据包。

由于10.2.3.3是分类匹配，可以使用默认路由，而10.4/16是无分类匹配，不能使用默认路由，只能丢弃。但当启动了IP Classless命令后，10.4/16与10.2.3.3一样，都可以通过默认路由转发数据包。endprint

因此，使用了IP Classless命令，路由器成为无分类路由环境，当目的数据包到达时，不进行分类匹配，而是进行无分类匹配，即进行最长前缀匹配；当采用最长前缀匹配时，若目的IP地址不在路由表内，路由器将把它交给默认路由，通过默认路由将数据包送出。

3.4.4网络前缀设置

根据骨干网路由器路由表前缀长度的分布统计发现，路由前缀长度至少为8，路由前缀并不是按长度平均分布，路由表前缀长度在13～27之间的占98.9%，仅前缀长度为23的占50%左右，前缀长度在其它区间的很少。因此，一般网络前缀取值在13～27之间[10]，将网络前缀设置成比原来分类编址子网掩码的1比特长，其主要目的是基于无分类编址CIDR的网络与基于分类编址的网络能相互支持。

事实上，由于CIDR标记法应用范围广、使用灵活，当主机软件支持CIDR时，网络前缀可以比原来的掩码长度短，如表6所示。

由此得到结论：使用无分类编址CIDR，可以标记任意的地址块。同时，合理、科学地分配地址块显得非常重要。

3.4.5超网构建

所谓“超网”就是将若干个网络前缀长度相同、地址前缀值相等、地址个数是2的幂的IP地址进行聚合，也称为“

路由聚合”。聚合方法就是对IP地址进行“全排列运算”或“与或运算”。一个超网就是一个CIDR地址块，其中包含了多个IP地址。

根据表6，可以很方便地构建超网，建立CIDR地址块。

某公司需要600个地址，下面哪一组IP地址块可以用于这个公司构成超网？

（1）198.47.32.0，198.47.33.0，198.47.34.0

（2）198.47.32.0，198.47.42.0，198.47.52.0，198.47.62.0

（3）198.47.31.0，198.47.32.0，198.47.33.0，198.47.34.0

（4）198.47.32.0，198.47.33.0，198.47.34.0，198.47.35.0

分析：①IP地址个数不是2的幂，不能构建超网；②网络ID不连续，不能构建超网；③4个连续的IP地址，但地址前缀值不相等（即不属于同一个网络ID），不能构建超网；④可以构建超网，超网地址块为198.47.32.0/22。

一般地，根据CIDR标记特点，聚合结果总是网络ID地址最小/网络前缀。

3.5CIDR地址分配方法

主要有二叉树法与递增法。

3.5.1二叉树法

根据网络前缀值形成的二叉树进行地址分配。将1个网络前缀值为23 位的地址，可分为2个24 位的地址；1个24 位的地址，可分为2个25 位的地址，依此类推。这样，CIDR 地址的网络前缀由短到长依次向下形成了一个二叉树形状。

图11表示将网络192.268.2.0/23分为3个子网A、B、C，分别含有主机数为250台、50台、100台的一种二叉树法分配方案。当然，在进行二叉树划分时，必须满足“子网聚合”原则，在上述划分中，B与C 的地址中间出现间隔，说明有段IP地址没有进行分配。

图11CIDR地址分配的二叉树法

3.5.2遞增法

根据主机数进行IP 地址划分。在给定IP 地址上不断增加主机数，形成的新IP 地址就是子网IP。

由于A 网需要包含大于250 台主机地址的IP地址，而256 =28，在原地址上加256，得到下一个子网的网络号：192.268.3.0/24；C网需要包含大于100台主机地址的IP地址计划，因为26 = 64 <100 < 128 =27，因此，C网子网的网络号为：192.268.2.128/25。依此类推，可以用地址加主机数方式实现IP地址的分配，显然，得到递增的IP 地址。

3.5.3两种地址分配方法比较

二叉树法得到的子网IP地址之间存在间断，就是IP 地址分配不能够连续。对于递增法，当主机台数不相同时，如果按照问题要求的顺序，地址分配计划是：A为192.268.2.0/24；B为192.268.3.0/26；C：192.268.3.64/25。由于小的IP 地址对应的网络前缀长，而大的IP对应的网络前缀短，B与C部分地址出现了重复，IP 地址分配出现了错误。

研究发现，二叉树方法中的网络前缀是自上而下依次增大，分配的IP地址不能保证从小到大、连续，但可以避免IP地址重复。主机数递增的分配方法解决了IP地址从小到大连续的问题，但大IP地址网络前缀小于小IP地址网络前缀，会导致重复。因此，两种方法可以相互借鉴结合使用。

3.6最长地址前缀匹配查找算法

在分类地址结构体系下，可以通过目的IP地址前几个比特位的值获得该地址所对应的类，从而知道匹配地址前缀的长度，因此地址前缀查找比较简单。

在无分类地址CIDR结构体系下，路由表的规模得到了一定控制，但是地址前缀查找工作变得非常复杂。在CIDR地址结构下，地址前缀表中前缀表项长度是任意的，类的概念将不存在，所以不能从目的地址前几个比特推断出该地址所对应的地址长度，从而地址查找操作不再能简单地转化为关键字的精确匹配[11]。

CIDR地址结构下的地址前缀查找，不仅需要与前缀的比特位进行匹配查找，而且需要考虑地址前缀的长度。基于此，最长地址前缀查找可以从地址前缀值与地址前缀长度两个方面考虑。目前主要的最长地址匹配查找算法有：二进制Trie树、路径压缩Trie树、多分支Trie树（步宽为k）、前缀长度的二分查找、地址区间的二分查找等[1214]。

4结语

通过分析无分类编址CIDR地址体系结构可知，无分类编址CIDR与分类编址都是IPv4地址的分配方法，CIDR技术可以缓解IP资源紧张状况，控制路由表规模，在IP4向IP6发展过渡期有独特的重要作用[15]。但在CIDR结构体系下，地址前缀的查找变得复杂，需合理设计最长地址匹配查找算法。

参考文献参考文献：

[1]王浩.IPv4与IPv6相互转换技术研究[J].计算机与数字工程，2010，38（1）：114117.

[2]张军超.基于MPBGP扩展的4over6隧道技术的实现[J].计算机与数字工程，2012，40（12）：119122.

[3]包丛笑，李星.IPv4/IPv6过渡的核心技术标准RFC6052[J].中国教育网络，2010，12（1）：2829.

[4]张平.IPv4与IPv6隧道技术的研究及实现[J].计算机技术与发展，2012，22（8）：127130.

[5]李星.互联网核心技术创新与网络强国[C].北京：2015年第四届高等学校计算机网络类专业教育与教学研讨会，2015.

[6]吴功宜.计算机网络：第3版[M].北京：清华大学出版社，2011.

[7]姚秀情.CIDR的简单应用分析机电技术[J].机电技术，2013（4）：6365.

[8]陈宜冬.基于CIDR的网络划分方案[J].信息技术，2004，6（6）：6263.

[9]谭毓银.CIDR在IP子网划分中的应用[J].信息安全与技术，2013，4（5）：7577.