计算机网络：实现无分类路由选择

1.网络前缀

划分子网在一定程度上缓解了互联网在发展中遇到的困难，然而，直至1992年，互联网仍然面临3个必须尽早解决的问题，这就是：

（1）B类地址在1992年已分配了近一半，眼看很快就将全部分配完毕。

（2）互联网主干网上的路由表中的项目数急剧增长（从几千个增长到几万个）。

（3）整个IPv4的地址空间最终将全部耗尽。在2001年2月3日，IANA（互联网数字分配机构）宣布IPv4地址已经耗尽了。

当时预计前两个问题将在1994年变得非常严重。因此IETF很快就研究出采用无分类编址的方法来解决前两个问题。IETF认为上面的第三个问题属于更加长远的问题，因此专门成立IPv6工作组负责研究解决新版本IP的问题。

早在1987年，RFC^[1]1009就指明了在一个划分子网的网络中可同时使用几个不同的子网掩码。使用变长子网掩码（Variable Length Subnet Mask，VLSM）可进一步提高IP地址资源的利用率。在VLSM的基础上人们又进一步研究出无分类编址方法，它的正式名字是无分类域间路由选择（Classless Inter-Domain Routing，CIDR；其读音是“sider”）。

CIDR最主要的特点有两个：

（1）CIDR消除了传统的A类、B类和C类地址以及划分子网的概念，因而能更加有效地分配IPv4的地址空间，并且在新的IPv6使用之前容许互联网的规模继续增长。CIDR把32位的IP地址划分为前、后两个部分。前面部分是“网络前缀”（network-prefix）（或简称为“前缀”），用来指明网络，后面部分则用来指明主机，因此CIDR使IP地址从三级编址（使用子网掩码）又回到了两级编址，但这已是无分类的两级编址。其记法是：

CIDR还使用“斜线记法”（Slash Notation），或称为CIDR记法，即在IP地址后面加上斜线“／”，然后写上网络前缀所占的位数。

（2）CIDR把网络前缀都相同的连续的IP地址组成一个“CIDR地址块”。只要知道CI⁃DR地址块中的任何一个地址，就可以知道这个地址块的起始地址（即最小地址）和最大地址，以及地址块中的地址数。例如，已知IP地址128.14.35.7／20是某CIDR地址块中的一个地址，现在把它写成二进制表示，其中的前20位是网络前缀（用粗体和下划线表示出），而前缀后面的12位是主机号：

这个IP地址所在的地址块中的最小地址和最大地址可以很方便地得出：

最小IP地址：128.14.32.010000000 00001110 00100000 00000000；

最大IP地址：128.14.47.25510000000 00001110 00101111 11111111。

当然，以上这两个特殊地址的主机号是全0和全1的地址，一般并不使用。通常只使用在这两个特殊地址之间的地址。不难看出，这个地址块共有212个地址。可以用地址块中的最小地址和网络前缀的位数指明这个地址块。例如，上面的地址块可记为128.14.32.0／20。在不需要指出地址块的起始地址时，也可把这样的地址块简称为“／20地址块”。

为了更方便地进行路由选择，CIDR使用32位的地址掩码（Address Mask）。地址掩码由一串连续的1和一串连续的0组成，而1的个数就是网络前缀的长度。虽然CIDR不使用子网，但由于目前仍有一些网络还使用子网划分和子网掩码，因此CIDR使用的地址掩码也可继续称为子网掩码。例如，／20地址块的地址掩码是1111111 11111111 11110000 00000000（20个连续的1）。在斜线记法中，斜线后面的数字就是地址掩码中1的个数。

注意，“CIDR不使用子网”是指CIDR并没有在32位地址中指明若干位作为子网字段。但分配到一个CIDR地址块的单位，仍然可以在本单位内根据需要划分出一些子网。这些子网也都只有一个网络前缀和一台主机号字段，但子网的网络前缀比整个单位的网络前缀要长些。例如，某单位分配到地址块／20，就可以再继续划分为8个子网（即需要从主机号中借用3 bit来划分子网）。这时，每个子网的网络前缀就变成23 bit（原来的20 bit加上从主机号借来的3 bit），比该单位的网络前缀多了3 bit。

斜线记法还有一个好处就是，它除了表示一个IP地址外，还提供了一些其他重要信息，举例说明如下。

例如，IP地址192.199.170.82／27不仅表示IP地址是192.199.170.82，而且还表示这个地址块的网络的前缀有27 bit（剩下的5位是主机号），因此这个地址块包含32个IP地址（25＝32）。通过简单的计算还可得出，这个地址块的最小地址是192.199.170.64，最大地址是192.199.170.95。具体的计算方法是这样的：找出地址掩码中1和0的交界处发生在地址中的哪个字节（现在是在第四个字节），因此只要把这一个字节的十进制82用二进制表示即可。十进制82的二进制是01010010，取其前3 bit（这3 bit加上前3 Byte的24 bit等于前缀的27位），再把后面5位都写成0，即0100000，等于十进制的64。这就找出了地址块的最小地址192.199.170.64。再把地址的第四字节的最后5位都置1，即01011111，等于十进制的95，这就找出了地址块中的最大地址192.199.170.95。

由于一个CIDR地址块中有很多地址，所以在路由表中就利用CIDR地址块来查找目的网络。这种地址的聚合常称为路由聚合（Route Aggregation），它使路由表中的一个项目可以表示原来传统分类地址的很多个路由。路由聚合也称为构成超网（supernetting）。如果没有釆用CIDR，则在1994年和1995年，互联网的一个路由表就会超过7万个项目；而使用了CIDR后，在1996年一个路由表的项目数只有3万多个。路由聚合有利于减少路由器之间的路由选择信息的交换，从而提高了整个互联网的性能。

CIDR记法有多种形式，如地址块10.0.0.0／10可简写为10／10，也就是把点分十进制中低位连续的0省略。另一种简化表示方法是在网络前缀的后面加一个星号（*），如00001010 00*，意思是在*之前是网络前缀，而*表示IP地址中的主机号，可以是任意值。当前缀位数不是8的整数倍时，需要进行简单的计算才能得到一些地址信息。表4-8给出了常用的CIDR地址块。表中的K表示210，即1 024。网络前缀小于13或大于27的都较少使用。“包含的地址数”中没有把全1和全0的主机号排除在外。

表4-8　常用的CIDR地址块

续表

从表4-8中可看出，每个CIDR地址块中的地址数一定是2的整数次幂。除最后几行外，CIDR地址块都包含了多个C类地址（是一个C类地址的2n倍，n是整数）。这就是“构成超网”这一名词的来源。

使用CIDR的一个好处就是可以更加有效地分配IPv4的地址空间，可根据客户的需要分配适当大小的CIDR地址块，然而，在分类地址的环境中，向一个部门分配IP地址，就只能以／8、／16或／24为单位来进行分配，这就很不灵活。

图4-27所示为CIDR地址块分配的例子。假设某ISP已拥有地址块206.0.64.0／18（相当于有64个C类网络）。现在某大学需要800个IP地址。ISP可以给该大学分配一个地址块206.0.68.0／22，它包括1 024（即210）个IP地址，相当于4个连续的C类／24地址块，占该ISP拥有的地址空间的1／16。照此该大学可自由地为本校的各系分配地址块，而各系还可再划分本系的地址块。CIDR地址块分配有时不易看清，这是因为网络前缀和主机号的界限不是恰好出现在整数字节处。只要写出地址的二进制表示（从图中的地址块的二进制表示中可看出，实际上只需要将其中的一个关键字节转换为二进制的表示即可），弄清网络前缀的位数，就不会把地址块的范围弄错。

从图4-27可以清楚地看出地址聚合的概念。这个ISP共拥有64个C类网络。如果不采用CIDR技术，则在与该ISP的路由器交换路由信息的每一个路由器的路由表中，就需要有64个项目。但采用地址聚合后，就只需用路由聚合后的一个项目206.0.64.0／18就能找到该ISP。同理，这个大学共有4个系。在ISP内的路由器的路由表中，也需使用206.0.68.0／22这个项目。这个项目好比是大学的收发室，凡寄给这个大学中任何系的邮件，邮递员都不考虑大学各个系的地址，而是把这些邮件集中投递到大学的收发室，然后由大学的收发室再进行下一步的投递。这样就减轻了邮递员的工作量（相当于简化了路由表的查找）。(www.xing528.com)

图4-27　CIDR地址块划分举例

从图4-27所示表格中的二进制地址可看出，把4个系的路由聚合为大学的一个路由（即构成超网）等于将网络前缀缩短。网络前缀越短，其地址块所包含的地址数就越多。在有三级结构的IP地址中，划分子网是使网络前缀变长。

2.最长前缀匹配

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

正确的做法是从匹配结果中选择具有最长网络前缀的路由，这叫作最长前缀匹配（Lon⁃gest-prefix Matching）。这是因为网络前缀越长，其地址块就越小，因此路由就越具体。最长前缀匹配又称为最长匹配或最佳匹配。为了说明最长前缀匹配的概念，仍以前面的例子来讨论。

假定大学下属的四系希望ISP把转发给四系的数据报直接发到四系而不要经过大学的路由器，但又不愿意改变自己使用的IP地址块，因此，在ISP的路由器的路由表中，至少要有以下两个项目，即206.0.680／22（大学）和2060.71.128／25（四系）。现在假定ISP收到一个数据报，其目的IP地址为D＝206.0.71.130。把D分别和路由表中这两个项目的掩码逐位相“与”。将所得的逐位相“与”的结果按顺序写在下面。

D和11111111 11111111 11111100 00000000逐位相“与”＝206.0.68.0／22匹配。

D和11111111 11111111 11111111 10000000逐位相“与”＝206.0.71.128／25匹配。

不难看出，现在同一个IP地址D可以在路由表中找到两个目的网络（大学和四系）和该地址匹配。根据最长前缀匹配的原理，应当选择后者，把收到的数据报转发到后一个目的网络（四系），即选择两个匹配的地址中更具体的一个。

从以上的讨论可以看出，如果IP地址的分配一开始就采用CIDR，那么可以按网络所在的地理位置来分配地址块，这样就可大大减少路由表中的路由项目。例如，可以将世界划分为四大地区，每个地区分配一个CIDR地址块：

地址块194／7（194.0.0.0～195255255255）分配给欧洲。

地地址块198／7（198.0.0.0～199.255.255.255）分配给北美洲。

地址块200／7（200.0.0.0～201.255.255.255）分配给中美洲和南美洲。

地址块202／7（202.0.0.0～203.255.255.255）分配给亚洲和太平洋地区。

上面的每一个地址块包含有约3 200万个地址。这种分配地址的方法就使IP地址与地理位置相关联。它的好处是可以大大压缩路由表中的项目数。例如，凡是从中国发往北美的IP数据报（不管它是地址块198／7中的哪个地址）都先送交位于美国的一个路由器，因此在路由表中使用一个项目就行了。

但是，在使用CIDR之前，互联网的地址管理机构没有按地理位置来分配IP地址。现在要把已分配出的IP地址收回再重新分配是件十分困难的事，因为这牵涉很多正在工作的主机必须改变其IP地址。尽管这样，CIDR的使用已经推迟了IP地址耗尽的日期。

3.使用二叉线索查找路由表

使用CIDR后，要寻找最长前缀匹配，这使路由表的查找过程变得更加复杂了。当路由表的项目数很大时，怎样设法减小路由表的查找时间就成为一个非常重要的问题。例如，连接路由器的线路的速率为10 Gb／s，而分组的平均长度为2 000 bit，那么路由器就应当平均每秒能够处理500万个分组（常记为5 Mp），或者说，路由器处理一个分组的平均时间只有200 ns（1 ns＝10-9 s）。因此，查找每一个路由所需的时间是非常短的。可见在路由表中必须使用很好的数据结构和使用先进的快速查找算法，这一直是人们积极研究的热门课题。

对无分类编址的路由表的最简单的查找算法就是对所有可能的前缀进行循环查找。例如，给定一个目的地址D。对每个可能的网络前缀长度M，路由器从D中提取前M个位形成一个网络前缀，然后查找路由表中的网络前缀。所找到的最长匹配就对应于要查找的路由。

这种最简单的算法的明显缺点就是查找的次数太多。最坏的情况是路由表中没有这个路由。在这种情况下，算法仍要进行32次（具有32位的网络前缀是一个特定主机路由）。即使仅寻找一个传统的B类地址（即／16），也要查找16次。对于经常使用的默认路由，这种算法都要经历31次不必要的查找。

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

如图4-28所示，用一个例子来说明二叉线索的结构。图中给出了5个IP地址。为了简化二叉线索的结构，可以先找出对应于每一个IP地址的唯一前缀（Unique Prefix）。所谓唯一前缀，就是在表中所有的IP地址中，该前缀是唯一的。这样就可以用这些唯一前缀来构造二叉线索。在进行查找时，只要能够和唯一前缀匹配就行了。

从二叉线索的根结点自顶向下的深度最多有32层，每一层对应于IP地址中的一个IP地址存入二叉线索的规则很简单。先检查IP地址左边的第一位，如为0，则第一层的结点就在根结点的左下方；如为1，则在右下方，然后再检查地址的第二位，构造出第二层的结点。依此类推，直到唯一前缀的最后一位。由于唯一前缀一般都小于32位，因此用唯前缀构造的二叉线索的深度往往不到32层。图4-28中较粗的折线就是前缀0101在这个二叉线索中的路径。二叉线索中的小圆圈是中间结点，而在路径终点的小方框是叶结点（也叫作外部结点）。每个叶结点代表一个唯一前缀。结点之间的连线旁边的数字表示这条边在唯一前缀中对应的比特是0或1。

图4-28　用5个唯一前缀构成的二叉线索

假定有一个IP地址是10011011 01111010 00000000 00000000，需要查找该地址是否在此二叉线索中。从最左边查起可以很容易发现，查到第三个字符（即前缀10后面的0）时，在二叉线索中就找不到匹配的，说明这个地址不在这个二叉线索中。

以上只是给出了二叉线索这种数据结构的用法，而并没有说明“与唯一前缀匹配”和“与网络前缀匹配”的关系。显然，要将二叉线索用于路由表中，还必须使二叉线索中的每个叶结点包含所对应的网络前缀和子网掩码。当搜索到一个叶结点时，就必须将寻找匹配的目的地址和该叶结点的子网掩码进行逐位相“与”运算，看结果是否与对应的网络前缀匹配。若匹配，就按下一跳的接口转发该分组；否则，就丢弃该分组。

总之，二叉线索只是提供了一种可以快速在路由表中找到匹配的叶结点的机制，但这是否和网络前缀匹配，还要和子网掩码进行一次逻辑“与”的运算。

为了提高二叉线索的查找速度，广泛使用了各种压缩技术。例如，图4-28中的最后两个地址，其最前面的4位都是1011。因此，只要一个地址的前4位是1011，就可以跳过前面4位（即压缩了4个层次）而直接从第5位开始比较。这样就可以缩短查找的时间。当然，制作经过压缩的二叉线索需要更多的计算，但由于每次查找路由表时都可以提高查找速度，这样做还是值得的。