子网与超网

本文内容学习自《计算机网络》谢希仁一书。

IP地址的编址方法共经过了三个历史阶段：

(1) 分类的IP地址。这是最基本的编址方法，在1981年就通过了相应的标准协议。
(2) 子网的划分。这是对最基本的编址方法的改进，其标准RFC 950在1985年通过。
(3) 构成超网。这是比较新的无分类编址方法。1993年提出后很快就得到推广应用。

IP分类缺点

在今天看来，在ARPANET的早期，IP地址的设计确实不够合理。
存在以下问题：

IP地址空间的利用率有时很低，网络地址和主机分布不科学。
给每一个物理网络分配一个网络号会使路由表变得太大因而使网络性能变坏。
两级IP地址不够灵活，在申请到一个新的IP地址之前，新增加的网络是不能连接到因特网上工作。

为解决上述问题，从1985年起在IP地址中又增加了一个“子网号字段”，使两级IP地址变成为三级IP地址，它能够较好地解决上述问题，并且使用起来也很灵活。这种做法叫作划分子网(subnetting) [RFC 950]，或子网寻址或子网路由选择。
划分子网已成为因特网的正式标准协议。

子网划分

划分子网的基本思路

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

子网掩码

假定有一个数据报已经到达了路由器R1，这个路由器如何把它转发到子网呢？

从IP数据报的首部无法看出源主机或目的主机所连接的网络是否进行了子网的划分。
这是因为32位的IP地址本身以及数据报的首部都没有包含任何有关子网划分的信息。
因此必须另外想办法，这就是使用子网掩码(subnet mask)。

要想在路由端得到子网的网络地址，只需要将子网掩码和IP地址进行逐位的“与”运算(AND)，就能立即得出其子网网络地址。
当然，不管网络有没有划分子网，把子网掩码和IP地址进行逐位的“与”运算(AND)，都能立即得出网络地址。

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

使用子网时分组的转发

使用子网划分后，路由表必须包含以下三项内容：

目的网络地址
子网掩码
下一跳地址。

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

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

子网之后 —— 无分类编址CIDR（构成超网）

CIDR最主要的特点有两个：

(1) CIDR消除了传统的A类、B类和C类地址以及划分子网的概念

CIDR把32位的IP地址划分为两个部分。
前面的部分是“网络前缀”(network-prefix)（或简称为“前缀”），用来指明网络
后面的部分则用来指明主机。
是无分类的两级编址。

CIDR还使用“斜线记法”(slash notation)，或称为CIDR记法
即在IP地址后面加上斜线“/”，然后写上网络前缀所占的位数。

10.24.55.38/20

(2) CIDR把网络前缀都相同的连续的IP地址组成一个“CIDR地址块”

我们只要知道CIDR地址块中的任何一个地址，就可以知道这个地址块的起始地址（即最小地址）和最大地址，以及地址块中的地址数。

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

“CIDR不使用子网”是指CIDR并没有在32位地址中指明若干位作为子网字段。
但分配到一个CIDR地址块的单位，仍然可以在本单位内根据需要划分出一些子网。

（路由聚合）构成超网

由于一个CIDR地址块中有很多地址，所以在路由表中就利用CIDR地址块来查找目的网络。
这种地址的聚合常称为路由聚合(route aggregation)
它使得路由表中的一个项目可以表示原来传统分类地址的很多个（例如上千个）路由。

路由聚合也称为构成超网(supernetting)。
路由聚合有利于减少路由器之间的路由选择信息的交换，从而提高了整个因特网的性能。

CIDR 匹配与查找

最长前缀匹配

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

应当从匹配结果中选择具有最长网络前缀的路由。
这叫作最长前缀匹配(longest-prefix matching)，这是因为网络前缀越长，其地址块就越小，因而路由就越具体(more specific)。
最长前缀匹配又称为最长匹配或最佳匹配。

使用二叉线索查找路由表

使用CIDR后，由于要寻找最长前缀匹配，使路由表的查找过程变得更加复杂了。
当路由表的项目数很大时，怎样设法减小路由表的查找时间就成为一个非常重要的问题。

对无分类编址的路由表的最简单的查找算法就是对所有可能的前缀进行循环查找。
这种最简单的算法的明显缺点就是查找的次数太多。最坏的情况是路由表中没有这个路由。

为了进行更加有效的查找，通常是把无分类编址的路由表存放在一种层次的数据结构中，然后自上而下地按层次进行查找。
这里最常用的就是二叉线索。
它是一种特殊结构的树。
IP地址中从左到右的比特值决定了从根节点逐层向下层延伸的路径，而二叉线索中的各个路径就代表路由表中存放的各个地址。

二叉线索只是提供了一种可以快速在路由表中找到匹配的叶节点的机制。
但这是否和网络前缀匹配，还要和子网掩码进行一次逻辑与的运算。
为了提高二叉线索的查找速度，广泛使用了各种压缩技术，比如前缀相同的就只比较后面不相同的位数。