这是一篇命题作文。近期一直想写点东西，但一直找不到题目，正好收到一封邮件，有人问我Linux路由表的布局问题以及路由缓存的问题，加之前些日子又帮人做了一个片上路由表，所以觉得这是个好题目，索性花了多半个周末的时间，奋笔疾书。前面的套话不写命题作文已经11年了，最后一次是在高考的考场上。收到邮件时，被人要求写这种命题作文，其实我是拒绝的，因为你不能叫我写我就马上去写，首先我自己得懂这个，我又不能说到了写完了的时候贴了很多baidu出来的图片，说了很多套话，人家一看就知道我这是转载或者翻译的，又没人给我打分也得不到什么奖励，还不如不写…我得先理一下思路，发现这些内容正是我心里的东西，那思考了一个上午之后呢，我去嘉定新天地吃了顿小火锅，喝了点酒，然后回来整理图片，起码这些东西我是很熟悉的，现在每天只要有时间我还折腾这些，不光如此，我还一度引诱我的同事，朋友折腾这些，就像引诱他们研究历史一样… 事实上，当这些文字和图整理出来以后，我是欣慰的。我记得，上一次我整理这类图的时候是在2011年我的小小出生的那几天，我晚上在医院，白天换班回家休息，然后就写写随笔什么的，很多都没有发表在博客上，因为很多也是跟IT没有关系的。不过不管怎么说，这几年我也确实有所进步，虽然在某些地方也退步了不少。 最近大家都在忙着跳槽，找工作的时候，请记住第一个问题很重要，真的。格局一定要大，措词一定要专业…不过这些都是虚的，你自己能把这个问题回答得跟玩一样，还是需要一定的积累的。我不敢说自己是网络领域的什么专家，几乎就是个菜鸟，有点积累的老鸟，所以我写了这篇作文，看看能不能对那些希望在底层IP网络觅食的小伙伴们带来一点帮助。据很多大拿大咖的预测以及我自己的感觉，IP将在最近几年有大动作，这个大动作并不是指IPv6，而是别的，和物联网，云，机会网络，自组织相关的。所以，蹲好马步才能去手持弹弓准打MM屁股啊。1.IPv4地址空间树IPv4的整个地址空间可以构成一棵完美的二叉树，因为它完全占满了整个4G的地址空间。这棵树如下所示：
需要指明的是，完全画出这幅图是不可能的，如果一个节点的直径小到1mm(这意味你要拿放大镜去看小圆圈里存储的信息[我并没有在圈圈里写任何信息，我怕它们被有损压缩了…模拟情况下用放大镜可见，数字图片一旦被有损压缩，拿放大镜看到的就是一个个方块，学名阻碍进步的马赛克-希腊/罗马的遗产])，那么最下层将会有4000km长，正好是东北黑龙江的漠河到西藏日喀则的距离，如果看完整个图，相当于环中国旅行了…所以我只能画一部分，由于不可能展示整张图，所以我也没有必要将节点直径缩至1mm了。 通过这个图，你会发现，给定一个IP地址，你可以从ROOT开始，逐bit比较游历，最终在最底层找到它的位置，这个过程是如此快，只需要32步，以至于你根本不能想象漠河到日喀则的距离，但是你如果听说过纸张对折到月球，估计就彻底理解了，这就是指数的魅力和危险。脑子里装进这张图，然后在中间加入一些信息，你将彻底理解IP路由表的查找过程，我们现在就开始。以下的内容仅仅考虑IPv4。2.路由查找路由查找就是为一个目标IP地址找到一个下一跳，即找到一个路由项。路由项的key是一个bit前缀，比如192.168.0.0/16，172.16.20.0/24，1.2.3.0/28，3.4.5.6/32等，而这些key作为IP的表达方式，所不同的是它们仅仅考虑32位中的某些连续的位而不一定非要是全部，我们会发现，对于32位前缀的路由项key，它们对应最底层叶子节点的某些节点，而对于小于32位前缀的路由项key，它们正好对应一些中间结点。因此我们基于IPv4地址树而得到了一棵新的树，即带有路由节点的IP地址树：
路由查找的过程这下就很明晰了，既找到一个输入目标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-431 prefix list：node31-1，node31-2，node31-3，node31-4…30 prefix list：null29 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查找的算法吗？2.2.自根而下查找从IPv4地址空间树(简称地址树)来看，由于它是一棵二叉树，精确匹配了32位IPv4地址的每一位，因此沿着根而下，最终肯定能到达目标IP地址，而这一路上最后经过的那个路由节点(黑色)就是所要查找的路由，这是很显然的，从带有路由的IPv4地址树上我们可以很容易看出这一点。 虽然沿着IPv4地址树自上而下查找浪费不了太多时间，最多也就匹配32次，然而构建一颗完整的IPv4地址树却需要太大的空间。而这是要避免的，这么大的空间不仅仅难于利用核心缓存，同时它真的是不必要的，因为有更加优化的方式来解决路由查找问题。为此，我们需要对这棵带有路由的IPv4地址树做一些变换。 那棵庞大的IPv4地址树仅仅是为了给出一个理解路由查找原理的方式，实际上我们关注的应该是：如何使得一个特定的IPv4地址，即目标地址能够快速的到达某个路由节点或者快速发现没有这样的路由节点。要达到这样的目的，就不得不掠过很多不带有路由项的“空心节点”，为此我们需要将这棵IP地址树进行压缩，从而最终在这棵树上仅仅保留最少数量的“空心节点”，它们存在的目的，仅仅是快速引导我们到达某一个实心的路由节点。重新安排压缩后的路由节点的位置在带有路由节点的IP地址图上，我们可以发现，一个目标IP地址最终使用的路由是从根部直到叶子(即它本身)的无环路径中最后一个经过的路由节点，即越靠近叶子节点的路由项目越优先被使用，因为它更加精确。最终将IP地址树压缩后，路由节点将全部被保留，此时，我们可能会有下面的子树：
每个人心中，都会有一个古镇情怀，流水江南，烟笼人家。
