Linux路由查找算法

由于IP是数据报网络，它是不建立连接的，因此IP分组是一跳一跳被转发，通路是通过路由信息一跳一跳的被打通的，因此路由直接关系到整个基于IP的网络的连通性。由于IP协议没有方向，甚至它都没有会话的概念，因此路由必然要是双向的，否则数据就有去无回了(有人提倡用NAT来解决反向路由问题，实际上NAT在公共核心网络上口碑十分不咋地，它甚至破坏了IP协议的原则，记住，NAT一般只用于端点)。互联网如此之大，每个路由器上的路由信息会非常之多，路由器是怎么在海量的路由信息中用最快的速度-显然很重要-检索出自己需要的呢？另外如此海量的路由信息又是怎么生成的呢？本文着重回答第一个问题，关于第二个问题请参考《Internet路由结构(第二版)》(Cisco Press,想看就赶快买，不买就买不到了，Cisco有几本书真的很火爆，总是不好买)
1.基本概念
路由的概念：路由是一种指向标，因为网络是一跳一跳往前推进的，因此在每一跳都要有一系列的指向标。实际上不仅仅是分组交换网需要路由，电路交换网在创建虚电路的时候也需要路由，更实际的例子，我们日常生活中，路由无处不在。简单的说，路由由三元素组成：目标地址，掩码，下一跳。注意，路由项中其实没有输出端口-它是链路层概念，Linux操作系统将路由表和转发表混为一谈，而实际上它们应该是分开的(分开的好处之一使得MPLS更容易实现)。
     路由项通过两种途径加入内核，一种是通过用户态路由协议进程或者用户静态配置配置加入，另一种是主机自动发现的路由。所谓自动发现的路由实际上是“发现了一个路由项和一个转发表”，其含义在主机某一个网卡启动的时候生效，比如eth0启动，那么系统生成下列路由表项/转发项：往eth0同一IP网段的包通过eth0发出。
路由表：路由表包含了一系列的表项，包括上述的三元素。
路由框架的层次：路由大致分为两个要素，也可以看成两个层次。第一个层次是路由表项的生成；第二个层次是主机对路由表项的查找。
路由表项生成算法：生成路由表项的方式有两种，第一种是管理员手工配置，第二种为通过路由协议动态生成。
路由查找算法：本文着重于主机层面上对路由表项的查询算法。毕竟这是一个纯技术活儿…相反的，路由协议的实现和配置更讲究人为的策略，如果你人为配置RIP或者OSPF只需要配几条命令就OK了，那么配一个BGP试试，它讲究大量的策略，不是纯技术能解决的。如果有时间，我会单独写一篇文章谈路由协议的，但是今天，只谈路由器/主机对路由表项的查找过程。
     这个过程很重要，如果路由器的查找算法效率提高了，那么很显然，端到端的延迟就降低了，这是一定的。
2.Linux的哈希查找算法
这是Linux操作系统的经典的路由查找算法，直到现在还是默认的路由查找算法。然而它很简单。由于它的简单性，内核(kernel)开发组一直很推崇它，虽然它有这样那样的局限性，但由于Linux内核的哲学就是“够用即可”，因为Linux几乎从来不被用于专业的核心网络路由系统，因此哈希查找法一直都是默认的选择。
2.1.查找过程
查找结构如下图所示：



查找顺序如下图所示：





为了实现最长前缀匹配，从最长的掩码开始匹配，每一个掩码都有一个哈希表，目的IP地址哈希到这些哈希表的特定的桶中，然后遍历其冲突链表得到最终结果。
     注意，哈希查找算法是基于掩码的遍历来实现严格的最长前缀匹配的，也就是说如果一条最终将要通过默认网关发出的数据报，它起码要匹配32次才能得到结果。这种方式十分类似于传统的Netfilter的filter表的过滤方式-一个一个尝试匹配，而不像HiPac的过滤方式，是基于查找的。接下来我们会看到，高性能的路由器在查找路由的时候使用的都是基于查找型数据结构的方式，最常用的就是查找树了。
2.2.局限性
我们知道，哈希算法的可扩展性一直都是一个问题，一个特定的哈希函数只适合一定数量的匹配项，几乎很难找到一个通用的哈希函数，能够适应从几个匹配项到几千万个匹配项的情形，一般而言，随着匹配项的增加，哈希碰撞也会随着增加，并且其时间复杂性不可控，这是一个很大的问题，这个问题阻止了哈希路由查找算法走向核心专用路由器，限制了Linux路由的规模，它根本不可能使用哈希来应对大型互联网络或者BGP之类的域间路由协议产生的大量路由信息。
     核心路由器上，使用哈希算法无疑是不妥的，必定需要找到一种算法，使得其查找的时间复杂度限制在一个范围(我们不关心空间复杂度，这和端到端用户的体验没有关系，只和他们花的钱多少有关，花10万买的路由器有4G内存，花100万买的路由器则支持64G内存…)。我们知道，基于树的查找算法可以做到这一点，实际上，很多的路由器都是使用基于树的查找算法来实现的。我们先从Linux的trie树开始。便于查阅代码(虽然本文不分析代码…)。
3.Linux的LC-Trie树查找算法
trie算法分为三大块，第一块是查找，第二块是插入/删除，第三块是平衡。我们首先先不管其名称为何这么叫，也不必非要去深入理解一下Trie树的概念，直接实践就是了。虽然很多的教科书都喜欢最后讲查找型数据结构的插入，而我这里却要先说插入，因为一旦你明白了插入，查找就不言自明了，另外，讲完插入之后，接下来我要说的是trie树的平衡以及多路操作，因为这样的话，最终的查找才会变得高效。我们权当高效的查找操作是一个必然结果吧。
3.1.基本理论
很不好意思，这里没什么理论，一切都很简单。我们可以通过电话号码来认识trie树，trie树本质上是一棵检索树，和全球电话号码簿一样，我们知道，电话号码有三部分组成：国家码+地区号+号码，比如086+372+5912345，如果从美国拨出这个号码，首先要决定送往哪个国家，所要做的就是用确定位数的国家码和出口交换机的转发表的国家码部分进行匹配，发现086正好是中国，然后该号码到达中国后，再匹配区号，发现要送往安阳市，最后到达安阳市，然后将请求发往5912345这个号码。
     现在的问题是，在每一个环节如何使用最快的方式检索到请求下一步要发往哪里？我想最好的方式就是使用“桶算法”，举个例子，在美国的电话请求出口处放置一张表，表项有X个，其中X代表全球所有国家和地区的总和，中国的国家码是086，那么它就是第86个表项，这样直接取第86个表项，得到相应的交换信息，电话请求通过信息中指示的链路发往中国…
     另外一个例子就是计算机的页表，这个我们在3.3节再谈。
     trie树，其实和上述的结构差不多，只不过上述结构的检索分段是固定的，比如电话号码就是3位10进制数字等，且匹配检测索引的位置也是固定的，比如电话号码的地区号就是从第4位十进制数字开始等。对于trie树而言，需要检测的位置不是固定的，它用pos表示，而检测索引的长度也不固定，它由bits表示，我们把每一个检测点定为一个CheckNode，它的结构体如下：
CheckNode{
    int pos;
    int bits;
    Node children[1<