划分子网和构造超网

1、划分子网

从二级IP地址到三级IP地址

▷ ARPANET早期的IP地址的设计不合理：

IP地址空间利用率有时很低。
给每一个物理网络分配一个网络号会使路由器变得太大因而使得网络性能差。
两级IP地址不够灵活。

为了解决上述问题，从1985年起在IP地址中又增加了一个“子网号字段”，使得二级地址变为三级地址，它能较好地解决上述问题。这种方法叫做划分子网(subnetting)，或子网寻址或子网路由选择。

▷ 划分子网的基本思路：

一个拥有许多物理网络的单位，可将所属的物理网络划分为若干个子网(subnet)。本单位外看不见这个网络由多少个子网组成，对外表现为一个网络。
划分子网的方法是从网络的主机号借用若干位作为子网号，相应的，主机号也减少了同样的位数。于是两级IP在内部就变为了三级IP。
凡是从其他网络发送给本单位某台主机的IP数据报，仍然是根据IP数据报的目的网络号找到连接在本单位网络上的路由器。但此路由器收到数据报后，再按目的网络号和子网号找到目的子网，把数据报交付给目的主机。

子网掩码

从IP数据报的首部无法看出源主机或者目的主机所连网络是否进行了子网划分。必须另外想办法，这就是使用子网掩码(subnet mask)。子网掩码和目的IP地址进行按位与(AND)运算，得出所要找的子网的网络地址。

Xie：使用子网掩码的好处就是：不管网络有没有划分子网，只要把子网掩码和IP地址进行按位与运算，就立即得出网络地址来。这样在路由器处理到来的分组时就可采用相同的算法。在不划分子网时，也要使用子网掩码，路由器的路由表中必须要有子网掩码这一栏，如果一个网络不划分子网，那么该网络的子网掩码就使用默认子网掩码。默认子网掩码的1的位置对应IP地址网络号字段。

Xie：子网掩码是一个网络或者子网的重要属性。在RFC950成为正式标准后，路由器在和相邻路由器交换路由信息时，必须把自己所在网络或子网的子网掩码告诉相邻路由器。在路由器的路由表中的每一个项目，除了要给出目的网络地址外，还必须同时给出该网络的子网掩码。

Xie：划分子网增加了灵活性，但却减少了能够连接在网络上的主机总数。

Xie：同样的IP地址和不同的子网掩码可以得出相同的网络地址。

2、使用子网时分组的转发

划分子网后，路由表必须包含三项内容：目的网络、子网掩码、下一跳地址。

划分子网情况下，路由器的分组转发算法：

从收到的数据报首部提取目的IP地址D。
先判断是否为直接交付。对路由器直接相连的网络逐个进行检查：用各网络的子网掩码和D按位与，看结果是否和相应的网络地址匹配。如果匹配，则直接交付（需要把D转换为物理地址，封装成帧发送），转发任务结束。否则就是间接交付，执行(3)。
若路由表中有目的地址为D的特定主机路由，则把数据报交付给路由表中所指明的下一跳路由器。否则执行(4)。
对路由表中每一行，用其中的子网掩码和D按位与，如果结果与该行的目的网络地址匹配，则把数据报传送给该行指明的下一跳路由器。否则执行(5)。
若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器。否则执行(6)。
报错。

3、无分类编址CIDR（构造超网）

网络前缀

划分子网在一定程度上缓解了互联网发展中遇到的一些困难。然而在1992年互联网仍然面临三个必须解决的问题：

B类地址已经快分配完了。
互联网主干网上的路由表中的项目数急剧增长。
整个IPv4地址空间最终将全部耗尽。

IETF很快就研究出采用无分类编址的方法来解决前两个问题，并成立IPv6工作组负责研究解决新版本IP协议的问题。

早在1987年，RFC1009就指明了在一个划分子网的网络中可同时使用几个不同的子网掩码，使用变长子网掩码(VLSM)可进一步提高IP地址资源的利用率。在VLSM的基础上进一步研究出了无分类编址方法，它的正式名字是无分类域间路由选择(Classless Inter-Domain ROuting, CIDR)。

CIDR的主要特点:

CIDR消除了传统的A、B、C类地址以及划分子网的概念，因而能更加有效地分配IPv4地址空间。CIDR把IP地址分为前后两个部分，前面是网络前缀(network prefix)，用来指明网络，后面部分则用来指明主机。因此CIDR使IP地址从三级编址又回归了二级编址，但是这是无分类的二级编址。（CIDR还是用斜线记法，在IP后面加上斜杠然后写上网络前缀所占位数）
CIDR把网络前缀都相同的连续IP地址组成一个“CIDR地址块”。我们只要知道CIDR地址块中任何一个地址，就可以知道这个地址块的起始地址和最大地址以及块中的地址数。

地址掩码(address mask)：

为了更方便地进行路由选择，CIDR使用32位地址掩码。地址掩码由一串1和一串0组成，1的个数就是网络前缀的位数。

虽然CIDR不使用子网了，但由于目前仍有一些网络还使用子网划分和子网掩码，因此CIDR使用的地址掩码也可以继续称为子网掩码。

构成超网(supernetting)：

由于一个CIDR地址块中有很多地址，所以在路由表中就利用CIDR地址块来查找目的网络。这种地址的聚合成为路由聚合，它使得路由表中的一个项目可以表示原来传统分类地址的很多个路由。路由聚合又称为构成超网。

路由聚合（构成超网），是将网络前缀缩短。网络前缀越短，其地址块所含的地址数就越多。而在三级结构的IP地址中，划分子网是使网络前缀变长。

最长前缀匹配(longest-prefix matching)

在使用CIDR时，由于采用了网络前缀这种记法，IP地址由网络前缀和主机号两部分组成，因此在路由表中的项目也要有相应的改变。这时，每个项目由“网络前缀”和“下一跳地址”组成。但是在查找路由表时可能会得到不止一个匹配结果。应当从匹配结果中选择最长网络前缀的路由，因为网络前缀越长，其地址快就越小，因此路由就越具体。

使用二叉线索查找路由表

使用CIDR后，由于要寻找最长前缀匹配，使路由表的查找过程变得更加复杂了。

为了进行更有效的查找，通常是把无分类编址的路由表放在一种层次的数据结构中，然后从上至下按层次查找，最常用的就是二叉线索。

从二叉线索的根节点自顶向下的深度最多有32层，每一层对应IP地址中的一位。

一个IP地址存入二叉线索的规则很简单，先检查IP地址第一位，如为0则第一层节点就在根节点左下方，如果为1，则在右下方。然后检查第二位，以此类推，直到最后一位。

（END）