如何使用二叉线索查找路由表

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

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

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

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