这是一篇命题作文。近期一直想写点东西，但一直找不到题目，正好收到一封邮件，有人问我Linux路由表的布局问题以及路由缓存的问题，加之前些日子又帮人做了一个片上路由表，所以觉得这是个好题目，索性花了多半个周末的时间，奋笔疾书。
前面的套话
1.IPv4地址空间树
IPv4的整个地址空间可以构成一棵完美的二叉树，因为它完全占满了整个4G的地址空间。这棵树如下所示：
路由查找的过程这下就很明晰了，既找到一个输入目标IP地址在游历整棵树过程中经过的那个最精确的路由项节点。我们可以发现，越靠近叶子的路由项越精确，因为它“马上就要到达目的地”了。
路由节点作为中间结点或者叶子节点，我们有两种方式得达到它。
2.1.自叶子而上查找
假设我们已经知道了输入IP地址在最底层的位置，那么向ROOT游历，遇到的第一个路由节点肯定是最精确的。然而假设并不代表实际，这是一种执果索因法，我们并不知道输入IP的实际位置，我们也不想从漠河游历到日喀则，因此如何缩短路径就是要解决的问题。我们的问题是：
1).有32位前缀的精确路由吗果有，里面有没有和输入IP地址一样的呢果有，那就是它了，如果没有的话…
2).有31位前缀的路由吗果有，有哪个或者哪些(负载均衡量..)的前31位值和输入IP的前31位相等呢果有，那就是它了，如果没有的话…
3).有30位前缀的路由吗果有，有哪个或者哪些(负载均衡量..)的前30位值和输入IP的前30位相等呢果有，那就是它了，如果没有的话…
4).有29位前缀的路由吗果有，有哪个或者哪些(负载均衡量..)的前29位值和输入IP的前30位相等呢果有，那就是它了，如果没有的话…
…
逻辑是简单的，问题是我们怎么知道到底有没有，算法上如何去实施。答案当然也很显然。那就是把所有的路由项按照前缀自大到小进行排序，每个前缀拥有一个链表，每个链表节点都是一个路由项，如下：
32 prefix list：node32-1，node32-2，node32-3，node32-4
31 prefix list：node31-1，node31-2，node31-3，node31-4…
30 prefix list：null
29 prefix list：node29-1，node29-2
…
最简单的方式就是拿输入IP地址依次从上到下，每个链表从左到右去遍历上述结构。然而事情到了如此明了的地步，是个人应该都可以想到使用HASH来加快计算效率的吧。因此上述结构变成了：
32 prefix hashlist：hash1(node32-1，node32-4)，hash2(node32-3)，hash3(node32-2)
31 prefix hashlist：hash1(node31-8，node31-5，node31-3)，hash2(node31-1)，hash3(…)
30 prefix hashlist：hash1(null)，hahs2(null)，hash3(null)
29 prefix hashlist：hash1(node29-2)，hash1(null)，hash2(node29-2)
…
这下就免除了每个前缀链表遍历的困境，只需要计算bucket=hashcalc(IP_input)，然后在每一个前缀hash表的hash[bucket]冲突链表中遍历一小部分就好了。
自下而上查找总是从最精确的前缀开始的，旨在找到第一个匹配的路由项，而下面要详细描述的自上而下的查找则是从最不精确的前缀开始，旨在找到最后一个匹配的路由项，咋一看，自下而上占了优势，然而事实上，自上而下的方案也不赖。
自下而上的算法是如此显然，以至于再多增加一些笔墨就显得多余，所以接下来的大部分篇幅，我想留给另外一种截然相反的算法。
注解：自下而上的算法难道不就是Linux路由表hash查找的算法吗br>
2.2.自根而下查找
从IPv4地址空间树(简称地址树)来看，由于它是一棵二叉树，精确匹配了32位IPv4地址的每一位，因此沿着根而下，最终肯定能到达目标IP地址，而这一路上最后经过的那个路由节点(黑色)就是所要查找的路由，这是很显然的，从带有路由的IPv4地址树上我们可以很容易看出这一点。
虽然沿着IPv4地址树自上而下查找浪费不了太多时间，最多也就匹配32次，然而构建一颗完整的IPv4地址树却需要太大的空间。而这是要避免的，这么大的空间不仅仅难于利用核心缓存，同时它真的是不必要的，因为有更加优化的方式来解决路由查找问题。为此，我们需要对这棵带有路由的IPv4地址树做一些变换。
那棵庞大的IPv4地址树仅仅是为了给出一个理解路由查找原理的方式，实际上我们关注的应该是：如何使得一个特定的IPv4地址，即目标地址能够快速的到达某个路由节点或者快速发现没有这样的路由节点。要达到这样的目的，就不得不掠过很多不带有路由项的“空心节点”，为此我们需要将这棵IP地址树进行压缩，从而最终在这棵树上仅仅保留最少数量的“空心节点”，它们存在的目的，仅仅是快速引导我们到达某一个实心的路由节点。
重新安排压缩后的路由节点的位置
在带有路由节点的IP地址图上，我们可以发现，一个目标IP地址最终使用的路由是从根部直到叶子(即它本身)的无环路径中最后一个经过的路由节点，即越靠近叶子节点的路由项目越优先被使用，因为它更加精确。最终将IP地址树压缩后，路由节点将全部被保留，此时，我们可能会有下面的子树：
后面我们会谈到，这种方式更加有效。BSD和Linux都采用了这种方式。使用这种方式，所有的路由节点都被安排到了叶子，非常方便于Level压缩。
方式2：路由节点新增元信息，指示路径状况
可以看出，路径压缩做的事比较简单，操作也比较简单，它的目的就是忽略和路由项无关的节点，仅仅保留路由项以及路由项引导项节点。所有的输入IP地址在查找路由的时候，不必再逐位比较，而仅仅和路由项的检查位比较即可，最终顺着一条路径到达一个叶子节点，该节点即最终找到的路由项。
由于采用了方式1进行了路由项合并，因此需要用输入IP逐个检查叶子路由项的掩码链表，最终选出掩码最长的那个路由项。然而由于存在路径压缩，可能这一步并不会成功。我来解释一下这是为什么。请看上图的路由节点路径上的X位，对于路由项的key而言(比如192.168.1.0/24，其key就是192.168.1.0)，它将所有的被压缩的bit都假设为0或者模式相同的若干位，如都是1，都是11010等，即不检查，也就是它们被忽略了，造成的结果就是，输入IP地址的这些bit可能有不是0的，这就会造成最终的叶子节点的精确匹配不会通过。而此时，就需要回溯了。这是下一节的主题。
对于如何游历而言，很简单，每一个节点都是类似下面的结构体：
取出node的pos，然后定位到输入IP地址的pos位，如果它是0，则向左，即取child[0]，如果是1，则向右，即取child[1]。
2.Level压缩
Level压缩也不难，基本就是把一棵树从高变胖，变二叉树为N叉树。示意图如下：
关于Level压缩后如何游历，和二叉树差不多，但是根据压缩深度不同又有些不同，每一个节点类似下面的结构体：
取出node的pos和bits，然后定位到输入IP地址的pos位，取值idx=IP_input[pos…pos+bits]，取child[idx]为node，依次向下。为了更好支持动态Level压缩，将纯二叉树路径压缩也涵盖进来，只不过其bits为1而已。
关于Level压缩，还要说一点，那就是，我们总是希望最终的树可以规则一些，好看一点，那么在压缩之前需要对这个树做一定的变换，比如将畸形的树变成完全的树等。幸运的是，无类路由查找是最长前缀匹配的，也就是说，在IP地址树上，每个IP地址所使用的路由项是从它到树根的路径上最近的那个路由项，反过来说，每一个路由项都覆盖地址树第32层叶子节点的一个范围，根据最长前缀匹配规则，如果发生覆盖范围重叠，层次深的路由项范围自动覆盖层次浅的路由项范围，如果我们想更好的进行Level压缩，方法也很简单，步骤如下：
1).将中间路由节点下移到叶子节点。
2).动态压缩或者直接压缩。
关于这个概念，还是先看一个图：
好了，这就是一个完整的例子。我尤其喜欢在阐述完一个例子后给出一个一般性的解释，但是我发现总结出一个一般的算法简直太难了，因此不得不将Linux的代码再次拿出来，抛弃掉一些细节，展示一个全面的算法：
关于回溯，最后我想给出一种没有回溯的方案。
看来回溯是为了纠正由于压缩而导致的错误，错误在于压缩掉了的bit属于模糊匹配而非精确匹配，事实上就是走错路了，如下图所示：
右边的方式是比较容易理解的，它不用回溯，而是将所有曾经覆盖整个位置的路由项按照从下层到上层，也就是按照精确性递减的顺序排列在了最终的节点中，这样即便是走错路了，我们只需要取整个链表中的“下一个元素”就可以了。事实上这个有点像HASH冲突链表。但是这么显而易见的方式为何没有被广泛使用呢因在于它的维护成本太高，所有的路由项之间相互关联，插入/删除/更新一个路由项，最坏的情况可以会触及所有路由项的变动，毕竟这个算法是基于覆盖关系的，因此还是将路由项保持独立比较好。
马上我们讲到的区间匹配，也是基于覆盖关系的，但是它的方式却截然不同，区间匹配是对路由项进行了拆分重映射，而不是简单的整体关联。
2.3.IP地址区间查找
如果再次看一下那棵带有路由节点的IP地址树，就会发现，自根向下， 最靠近叶子的路由节点，会隐含掉其到根的路径上的所有其它路由节点，即它自己全权负责了自它而下直到叶子层的所有到达叶子IP地址的路由。很明显，这是一个区间。很容易证明，每一个IP地址都唯一对应了一个这样的区间，一个区间由且仅由一个路由项负责。
那么，为一个IP地址查找路由的问题就转换成了为一个IP地址查找它所对应的区间。示意图如下所示，我依然用子树说明问题，再次给出Level压缩那一小节给出的图：
该错误必须靠回溯重试来给与纠正，但是由于该匹配失败的节点已经是“尽可能”精确的节点了，所以在回溯的时候要从右到左不断化1为0不断扩大匹配范围。
区间匹配算法由于分离了路由项的key前缀和下一跳，可以多对一共享下一跳，它不需要压缩，因为模糊性给了区间，即根本不需要输入IP地址对应到第32层叶子节点的精确位置，对应到一个区间即可，而这个区间对应一个已经和路由项分离了的下一跳，这就算是找到了路由-其实是找到了下一跳，而事实上，此时已经没有完整的路由项了，路由项早就化身为了一个区间和一个下一跳。
不管怎样，模糊性是肯定要存在的，因为你不可能保存一棵完整的IP地址树，所以就需要牺牲它的精确性，带来一点模糊性，这个模糊性存在于哪里，带来的是算法的本质不同。
对于自下而上的查找而言，模糊性在于，你事先根本不知道输入IP地址会落在哪个位置，甚至哪个区间都不知道，因此你必须将所有的路由项按照前缀自长而短一个一个试，而HASH算法，只是帮助这个尝试的过程更快结束而已，它并不是查找算法必须的，你完全可以将HASH算法更换成任何一种你认为比HASH更快的查找算法。自下而上查找的本质在于路由项按照前缀长度递减的顺序被尝试，而不是HASH算法。
2).以路由项为主还是以输入IP为主
压缩路由树的查找用输入IP地址去迎合路由项，旨在找到一个完整的最精确的路由项(包括前缀和下一跳)和它匹配，由于路由项的数量是确定的，因此在回溯的时候，不断以路由项的POS为基准，将输入IP地址的bits位从右到左不断化1为0，期待匹配到某个路由项，而路由项的分布保证了一旦匹配到，肯定是最精确的。
区间查找算法将路由项拆分，每一区间对应唯一的下一跳，因此只要将输入IP地址对应到某个区间，查找过程就结束了，因为完整的没有压缩过且没有变换过的IP地址树构造保证了一个区间唯一对应一个最精确的下一跳，即最靠近叶子层的那个路由项的下一跳。
2.5.路由查找的后续
我们听说过很多操作系统的路由查找算法，也许你会认为BSD的Radix查找以及Linux的Hash/Trie查找只是未竟全功，只实现了逻辑，没有考虑编码，也许你会觉得只有DxR才是一个高效完美的路由表编码方案！是这样吗认为不！
BSD和Linux实现的方案都是通用的方案。它并没有假设你有任何的Cache可以利用，它们都是纯算法级别的，它们可以让你分析其时间复杂度和空间复杂度，但是DxR却不能，DxR更多的是一种实现方式而非算法本身，因为它利用了太多可以让你利用的东西。如果我将DxR算法作为转发表的实现方案，或许会更好些吧。
此外，关于名称，我是拒绝讨论的。如果有面试官问起你来，你就说你只懂算法不知道叫什么名字。很早以前，我听说BSD的算法叫做Radix树算法，后来又有人叫它PC-Trie，而Linux的算法叫做LC-Trie，后来我被这些名字搞晕了，索性也就不在乎它们到底叫什么了，爆炸！
3.纷繁的查找实例
3.1.分类
哈希查找
路径压缩Trie树
Level压缩Trie树
Oh，NO！！！爆炸
3.2.查找时间复杂度总结
4.路由表和转发表，路由缓存
我不得不再次扯到OpenVPN！
OpenVPN被我搞成了多线程的，偶尔会segment fault。然而整个multi_instance表还是全局的。我们知道，OpenVPN全靠multi_instance表来路由数据包，这个表就是一张路由表！每一个mi中存放着某个客户端的虚拟IP地址，真实IP地址，虚拟MAC地址(tap模式)…过来一个TUN字符设备的数据包，需要用目标MAC地址或者目标虚拟IP地址(或者iroute地址)作为key查找multi_instance表，以便获取对应客户端的真实IP地址以及端口，反过来也是一样的。可以看到，multi_instance表在OpenVPN中的地位就是一张路由表。
多线程版本的OpenVPN中多个线程同时操作这张表是经常的，鉴于它不会经常被写入，我使用了读写锁对其进行保护，这是一种很好的思想，起码我当时觉得。然而，如果系统中保留一份全局的multi_instance表，然后将这个表优化成更加利于查找的结构，复制给每一个线程，岂不是更好吗样就没有锁操作了。这个无锁的思想也正是ZeroMQ的思想：别指望一群喝醉的人可以安全共享一瓶酒。这个复制后的本地表称为转发表，而那个全局的表称为路由表。转发表由路由表生而成之。在我预计启动的OpenVPN重构计划中，我将设计一个全局的multi_insance表，然后在各个线程中基于它构造一个转发表，完全使用ZeroMQ…说的有点跑题了…爆炸
这将把代码带到一个无锁的世界，既然有一群醉汉，干嘛不给他们一人一瓶酒呢实上，在核心的路由器上，正是采用了这样的设计。
路由缓存的意义大吗是和应用类型有关的，在以往固定节点 络的TCP长连接的年代，比如Telnet，FTP等，数据流的时间局部性非常明显，甚至在像HTTP这类多 文短连接(长连接更好)协议，时间局部性也是可以利用的，但是现在以及未来就有所不同了，P2P 络，机会 络，随机 络，自组织 络，移动 络，这类 络中节点与节点的通信路径是让人捉摸不定的，即便是长连接协议，也会因为节点的快速移动而使在上一次的位置节点路由器上缓存下来的路由项再也不会有机会命中，甚至，即便我们不考虑移动性，考虑一些信令协议，或者纷繁复杂的应用…
Linux现在已经取消了路由缓存的支持，而我本人在它取消路由缓存的支持之前也因为另外的原因采用另外的办法取消了路由缓存的支持，路由缓存的取消主要有两方面的原因，其一是路由项已经没有必要被缓存-它们八辈子不会用到一次，其二-需要维护缓存一致性，这第二个原因是不合理的，因为，因为IP协议本身就不需要维护状态，因此也就不需要什么缓存一致性。而我，正是因为这第二个原因取消了路由缓存，但是我也不是明知故犯，而是，而是我使用了Linux Netfilter的conntrack机制，而conntrack机制和IP配合的总是不太好。因此，我承认，我为此付出了代价。
…
后记
这篇作文我本来应该继续写得更长一些，就像我昨天中午和家人一起吃小火锅时喝了点酒后炫耀的那样：如今提笔就是8000字…想当初，每当周三上语文课，一想到要写600字的作文，我就极端的郁闷，感觉像是这道坎过不去了…相信很多人都和我一样。不过，现在不了，真的，我真的提笔8000字。如今没人逼着自己写东西了，倒是挺怀念中学时光，其实现在想一想，600字算什么，那多多少少只是一个历练…没有想法怎么都不行啊。如今我们没什么机会写文字了，真的，估计也就不外乎年终总结，项目总结，会议纪要，述职 告，入党申请书，求职简历，忏悔录…还有像我这样的时不时写写博客。但是，你真的会写吗然，搬砖的认为写文字的都是不现实的，但是他们没看过《天将雄师》里的罗马军团不用搬砖就能盖出城堡；虽然，商人卖东西的觉得数字才是重要的，那是他们的偏见；虽然，程序员觉得我写的这些都没用；虽然，军人觉得只要能打就行；虽然，也有人觉得，只要能喊即可…但是，所有这些难道不是文字传播的吗想借助文字可以表达一切，剩下的只是编码问题，这又扯到了路由表和转发表的问题。道 可道，非 常道……这也可以作为我终于在历时将近两个月结掉的《希腊人》的读后感。
提一下我自己，我不会编程，但也不是绝对不会，我稍微会一些，我会编程，但不狠，也编得不好，我精通世界历史，但不是什么都知道，也有不懂的，我深谙世事懂厚黑，但平时什么都说，我不拘小节，但心里什么都明白，我爱喝酒，曾经天天喝，但喝多了也吐，我于人不解，与人不聊，酒不聚众，聚不沾酒，厚德博学,止于至善，始终修元正本，造福苍生，不敢说为人师表，起码是懂hello world，真的懂，且很精通，甚至知道不用main和_start启动它，或者，直接在BIOS里启动它，甚至，直接拿个粉笔在我家小区广场的地面上启动它，前两个，我估计你也可以，但是最后一个，我估计你不敢。 文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34296 人正在系统学习中
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！