引言
本篇将介绍无分类编址CIDR的概念、最长前缀匹配、使用二叉线索查找路由表
CIDR
CIDR（Classless Inter-Domain Routing）无分类域间路由选择
划分子网在一定程度上缓解了因特网发展中遇到的困难，但其仅仅是对分类编址方式的改进，A、B、C类IP网络号都为8的倍数，其划分不够精细，存在很大程度的浪费，基于此，无分类编址方式CIDR应运而生。
分类编址的问题
1992年因特网面临三个必须尽早解决的问题
- B类地址在1992年分配了近一半，眼看很快就将全部分配完毕
- 因特网主干网上的路由表中的项目数急剧增长（由几千个增长至几万个）
- 整个IPV4的地址空间最终将全部耗尽，在2011年2越3日，IANA宣布IPV4地址已经耗尽了
IETF研究采用无分类编址的方法来解决前两个问题，其认为第三个问题属于更加长远的问题，因此专门成立IPV6工作组负责研究新版本IP协议的问题
CIDR最主要的两个特点
- CIDR消除了传统的A类、B类和C类地址及划分子网的概念，因此可以更加有效地分配IPv4的地址空间，并且在新的IPv6使用前容许因特网的规模继续增长
CIDR把32位的IP地址划分为两个部分，前面的部分是网络前缀，用来指明网络，后面的部分则用来指明主机，其与分类编址最大的不同，便是网络前缀不局限于8的倍数。因此CIDR使IP地址从三级编址（使用子网掩码）又回到两级地址，但这已经是无分类的两级编址。CIDR在IP地址后面加上斜线“/”，然后写上网络前缀所占的位数。
IP地址 :: = {<网络前缀>，<主机号>}
- CIDR把网络前缀都相同的连续IP地址组成一个“CIDR地址块”。我们只要知道CIDR地址块中的任何一个地址，就可以知道这个地址块的起始地址（最小地址）和终止地址（最大地址），以及地址块中的地址数
例如，已知IP地址为128.14.35.7/20是某CIDR地址块中的一个地址，现在把它写成二进制形式，其中前20位是网络前缀，而后面的12位是主机号：
128.14.35.7/20 = 10000000 00001110 00100011 00000111
这个地址块的最小地址为：10000000 00001110 00100000 00000000
这个地址块的最大地址为：10000000 00001110 00101111 11111111
CIDR的地址掩码
为了更方便地进行路由选择，CIDR使用32位的地址掩码（address mask）。地址掩码由一串1和一串0组成，而1的个数就是网络前缀的长度。虽然CIDR不使用子网了，但由于目前一些网络还使用子网划分和子网掩码，因此CIDR使用的地址掩码也可继续称为子网掩码
例如，/20地址块的地址掩码是：11111111 11111111 11110000 00000000（20个连续的1）。斜线记法中，斜线后面的数字就是地址掩码中1的个数
CIDR不划分子网的理解
另外，“CIDR不使用子网”，是指CIDR中并没有在32位地址中指明若干位作为子网字段。但分配到一个CIDR地址块的单位，仍然可以在本单位内根据需要划分出一些子网。这些子网也都只有一个网络前缀和一个主机地址号，但子网的网络前缀比整个单位的网络前缀要长一些
例如，某单位分配到地址块/20，就可以继续划分为8个子网（即需要从主机号中借用3位来划分子网）。这时，每一个子网的网络前缀就变成23位（原来的20位加上主机号借来的3位），比该单位的网络前缀多了3位
路由聚合的概念
由于一个CIDR地址块有很多地址，所以在路由表中就利用CIDR地址块来查找目的网络。这种地址的聚合常称为路由聚合（Route aggregation）,它使得路由表中的一个项目可以表示原来传统分类网络地址的很多个路由。路由聚合也称为构成超网（supernettig）
如果没有采用CIDR，则在1994年和1995年，因特网一个路由器就回超过7万个项目，而使用了CIDR以后，在1996年一个路由表的项目数菜只有3万多个。路由聚合有利于减少路由器之间的路由选择信息交换，提高整个网络性能
最长前缀匹配
最长前缀匹配的概念
在使用CIDR时，由于采用了网络前缀这种记法，IP地址由网络前缀和主机号这两个部分组成，因此在路由表中的项目也要做相应的改变。这时，每个项目由“网络前缀”和下一跳地址组成。但是在查找路由表时可能得到不止一个匹配结果。这样就带来一个问题：我们应当从这些匹配的结果中选择哪一条路由呢？
正确的答案是：应当从匹配结果中选择具有最长网络前缀的路由。这叫作最长前缀匹配（longest-prefix matching）,这时因为网络前缀越长，其地址块就越小（因为主机位数越少），因而路由就越具体。最长前缀匹配又称为最佳匹配或最长匹配
依据地址位置划分地址快
如果IP地址的分配从一开始就采用CIDR，那么我们可以按网络所在的地理位置来分配地址块，这样就可以大大减少路由表中的项目数
例如，可以将世界划分为四大地区，每一个地区分配一个CIDR地址块：
地址块194/7(194.0.0.0至195.255.255.255)分配给欧洲
地址块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)分配给亚洲和太平洋地区
上面一个地址块包含约3200万个地址($2^{32}-7$)。这种分配方法使得IP地址与地理位置关联，它的好处是可以大大压缩路由表中的项目数。例如从中国发往北美的数据报（不管它是地址块198/7中的哪一个地址）都先送到美国的一个路由器，因此在路由表中使用一个项目就行了。
但是，在使用CIDR之前，因特网的地址管理机构并没有按照地理位置来分配IP，现在要把已分配的IP地址回收再重新分配是十分困难的事情，因为这牵涉很多正在工作的主机必须改变其IP地址。所以基于地址位置划分地址块仅仅停留在想法
使用二叉搜索树查找路由表
当路由表的项目数很大时，怎样设法减小路由表的查找时间就成为一个非常重要的问题。 为了进行更加有效的查找，通常是将无分类编址的路由表存放在一种层次的数据结构中，然后自上而下地按层次进行查找。这里最常用的就是二叉线索(binary trie)
IP 地址中从左到右的比特值决定了从根结点逐层向下层延伸的路径，而二叉线索中的各个路径就代表路由表中存放的各个地址
