这是一篇命题作文。近期一直想写点东西，但一直找不到题目。正好收到一封邮件，有人问我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-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查找的算法吗？

2.2.自根而下查找

从IPv4地址空间树(简称地址树)来看，由于它是一棵二叉树，精确匹配了32位IPv4地址的每一位，因此沿着根而下，终于肯定能到达目标IP地址，而这一路上最后经过的那个路由节点(黑色)就是所要查找的路由，这是非常显然的，从带有路由的IPv4地址树上我们能够非常easy看出这一点。
      尽管沿着IPv4地址树自上而下查找浪费不了太多时间，最多也就匹配32次，然而构建一颗完整的IPv4地址树却须要太大的空间。而这是要避免的，这么大的空间不仅仅难于利用核心缓存。同一时候它真的是不必要的，由于有更加优化的方式来解决路由查找问题。为此。我们须要对这棵带有路由的IPv4地址树做一些变换。

      那棵庞大的IPv4地址树仅仅是为了给出一个理解路由查找原理的方式，实际上我们关注的应该是：怎样使得一个特定的IPv4地址，即目标地址能够高速的到达某个路由节点或者高速发现没有这样的路由节点。

要达到这样的目的，就不得不掠过非常多不带有路由项的“空心节点”，为此我们须要将这棵IP地址树进行压缩，从而终于在这棵树上仅仅保留最少数量的“空心节点”。它们存在的目的，仅仅是高速引导我们到达某一个实心的路由节点。

又一次安排压缩后的路由节点的位置

在带有路由节点的IP地址图上，我们能够发现，一个目标IP地址终于使用的路由是从根部直到叶子(即它本身)的无环路径中最后一个经过的路由节点，即越靠近叶子节点的路由项目越优先被使用，由于它更加精确。终于将IP地址树压缩后，路由节点将全部被保留，此时，我们可能会有以下的子树：

我们是怎样将此子树进行变换以更方便的进行上述的那个从根到叶子的游历过程呢？在此，我给出两种方式：
方式1：合并同样key路由节点为一个携带掩码链表的新节点

后面我们会谈到。这样的方式更加有效。BSD和Linux都採用了这样的方式。

使用这样的方式。全部的路由节点都被安排到了叶子。非常方便于Level压缩。

方式2：路由节点新增元信息，指示路径状况

可见，每个路由节点携带了几个不同的路径元信息：
Left more：左边子树是否还有新的路由项。假设有。且当前结果全然匹配并下一步要步入左边，那么继续匹配更精确的左子树。

Right more：同上，左换成右
Pre node idx：路径中上一个路由节点的索引(为此须要将全部路由项进行索引)，假设当前节点不匹配，则直接取出上一个节点来使用，假设当前节点匹配且Left/Right more为0，则使用当前节点。
由于IP地址树存在压缩(立即就会讲到)，因此这样的方式不如方式1应用广泛，由于存在压缩的情况下，即便当前路由节点不匹配，上一个也不一定匹配，再者，由于存在动态的路径压缩和Level压缩，节点间的关系也会动态变化。叶子和非叶子节点也会变化，而方式2须要不断追踪节点之间的关系，开销比較高。

IPv4地址树的压缩

前面屡次提到地址树的压缩，如今终于能够单独描写叙述它了。地址树的压缩不仅仅节省了空间，还优化了时间开销(但不常常，也不绝对，假设考虑恶性回溯，可能会恶化时间开销)。可是压缩也是有代价的，那就是在查找的时候可能须要回溯，而我们知道。在标准的完整IP地址树上查找是不须要回溯的。可是有时回溯即便在压缩的情况下也能够避免，这个不取决于算法，而是取决于你的输入IP地址，它是算法无关的。因此权衡来看。冒险是值得的。

       在我描写叙述地址树压缩的时候，有个前提，那就是一切都是基于前面一小节的方式1来变换的。关于地址树的压缩，其实它就是标准二叉树的压缩，方案有两类。路径压缩和Level压缩。

1.路径压缩

路径压缩非常简单，看一个图自然就会明确。

只是我不准备用那个及其庞大的IP地址图来开刀，它实在太大了。我仅仅是用它的上面一部分来说明原理：

能够看出，路径压缩做的事比較简单，操作也比較简单，它的目的就是忽略和路由项无关的节点。仅仅保留路由项以及路由项引导项节点。全部的输入IP地址在查找路由的时候，不必再逐位比較。而仅仅和路由项的检查位比較就可以，终于顺着一条路径到达一个叶子节点，该节点即终于找到的路由项。

      由于採用了方式1进行了路由项合并，因此须要用输入IP逐个检查叶子路由项的掩码链表，终于选出掩码最长的那个路由项。然而由于存在路径压缩，可能这一步并不会成功。我来解释一下这是为什么。请看上图的路由节点路径上的X位。对于路由项的key而言(比方192.168.1.0/24，其key就是192.168.1.0)，它将全部的被压缩的bit都假设为0或者模式同样的若干位。如都是1。都是11010等，即不检查，也就是它们被忽略了。造成的结果就是，输入IP地址的这些bit可能有不是0的，这就会造成终于的叶子节点的精确匹配不会通过。而此时，就须要回溯了。

这是下一节的主题。

       对于怎样游历而言，非常简单，每个节点都是相似以下的结构体：

struct node {
    u8 pos;
    struct node *child[2];
};

取出node的pos。然后定位到输入IP地址的pos位，假设它是0，则向左。即取child[0]，假设是1。则向右，即取child[1]。

2.Level压缩

Level压缩也不难，基本就是把一棵树从高变胖，变二叉树为N叉树。示意图例如以下：

这个Level压缩不必多讲，它其实都是标准的操作，对于数组形式存储的稀疏节点，还是不要做Level压缩，详细做还是不做，是有详细理论的。即仅仅有当从一个pos開始。其后的bits位拥有接近2的bits次方的孩子节点时，Level压缩才是必要的。

       Level压缩也面临路径压缩时的bit忽略，例如以下图所看到的：

关于Level压缩后怎样游历。和二叉树几乎相同。可是依据压缩深度不同又有些不同，每个节点相似以下的结构体：

struct node {
    u8 pos;
    u8 bits;
    struct node *child[0];
};

取出node的pos和bits。然后定位到输入IP地址的pos位，取值idx=IP_input[pos...pos+bits]，取child[idx]为node，依次向下。

为了更好支持动态Level压缩，将纯二叉树路径压缩也涵盖进来，仅仅只是其bits为1而已。
       关于Level压缩，还要说一点。那就是。我们总是希望终于的树能够规则一些，好看一点，那么在压缩之前须要对这个树做一定的变换，比方将畸形的树变成全然的树等。幸运的是，无类路由查找是最长前缀匹配的。也就是说。在IP地址树上，每个IP地址所使用的路由项是从它到树根的路径上近期的那个路由项。反过来说，每个路由项都覆盖地址树第32层叶子节点的一个范围，依据最长前缀匹配规则，假设发生覆盖范围重叠。层次深的路由项范围自己主动覆盖层次浅的路由项范围，假设我们想更好的进行Level压缩。方法也非常简单，过程例如以下：
1).将中间路由节点下移到叶子节点。

2).动态压缩或者直接压缩。
关于这个概念，还是先看一个图：

2.1).动态Level压缩
对于像Linux Trie算法而言，它使用的是动态压缩，即每个中间节点为树根的子树叉数不是固定的，视路由项分布而定，原则就是尽可能压缩空间。比方对于稀疏的同层路由项分布而言，叉数越小越好。比方维持二叉树，假设是密集连续的同层分布。那么叉数越多越好，关于这个能够參考MMU的设计思想，究竟是二级页表还是三级页表。或者为什么不是一级页表，视虚拟地址空间布局而定，考虑到多数程序不会全然占用全部的地址空间，此为一个稀疏分布，可是对于地址空间的局部部分，它的分布又是连续的，因此二级/三级页表会更好。
2.2).直接Level压缩
这个没什么好说的。直接压缩法比較直观。方便理解和硬件接管，而且你非常easy将它和区间查找联系起来。

其实。它们真的是有联系的。

       从这里開始，后面提到压缩路由树的时候。指的就是压缩变换(路径压缩+Level压缩+路由项合并前缀列表变换)了的带有路由项的IPv4地址树。
注解：Linux和BSD
在这里说详细的实现有点早，只是能够说一点。

不要拘泥于名称。Radix树，Trie树等(所谓：道 可道，非 常道！[一般人断不好这句子，会念做“道可道，非常 道...”])，其实Linux的Trie树採用的就是路径压缩+Level压缩+合并前缀链表的混合LC-Trie算法，而BSD曾一度是标准纯二叉树路径压缩+合并前缀链表算法，尽管它也被称作Radix树算法。
3).压缩带来的问题
前面说过，压缩会带来问题。压缩是一次冒险，冒险值得与否须要权衡。当採用压缩时，就会有冒险失利的情况，因此在带有压缩的路由地址树上查找路由项的过程分为两步骤：
a.路由项的精确匹配过程
目标IP地址ip1作为路由地址表的输入，依照标准的查找过程终于到达一个孩子节点，即：
1).取出root的pos和bits，计算ip1的[pos...pos+bits]值作为孩子index，进入root->child[index]；
2).假设不是叶子，则将root->child[index]赋值给root。继续1)。
3).假设是叶子。则依据叶子的掩码链表的从长到短排序的每个前缀prefix，依次做ip1 & prefix。与叶子节点的key做比較，如若相等，则成果返回，若不等，进入b。
如今问题是，假设上述第3)步匹配成功，能保证此路由结果的前缀是全部匹配结果的最长的吗？答案当然是肯定的，其依据在于。假设没有压缩，我们到达的最后的一个路由节点肯定是最精确的，如今尽管採用了压缩。可是注意我们是在冒险，我们假设路由项中全部压缩掉的bit和我们的输入ip1的相应bit是相等的。仅仅有真的相等，才会终于匹配到叶子节点。而当终于真的匹配成功时。我们就会知道，我们冒险成功了。它们确实是相等的。而终于的叶子节点可能是诸多上层的路由节点合并的结果，然而我们已经将前缀进行了排序。保证首先匹配最长前缀的那个。

假设冒险失败呢？那就回溯，这是以下要详谈的内容。

b.前缀递减的回溯匹配过程
这个又叫最长前缀匹配，可是为了避免和路由查找的最长前缀匹配混淆，我使用前缀递减过程来替代。这个过程仅仅有在步骤a终于失败的情况下才会使用。冒险失败的惩处就是回溯，它用额外的时间开销抵偿了压缩带来的空间收益，可是细致想想，也不。假设不压缩，时间开销不也非常大么？难道不须要逐位比較么？毕竟恶性回溯是能够通过平衡操作避免掉的。比方依据上述的理论，把树压得比較胖的时候。就能避免恶性回溯。

压缩路由树的回溯过程

关于这个主题，我依旧採用局部子树的方式描写叙述。由于从漠河到日喀则的路途太遥远了。

       我一向喜欢通过一个样例来说明问题，对于这个回溯，也是一样。首先还是先看个样例，这个样例包括了精确匹配和前缀递减匹配两个过程：

好了，这就是一个完整的样例。

我尤其喜欢在阐述完一个样例后给出一个一般性的解释，可是我发现总结出一个一般的算法简直太难了，因此不得不将Linux的代码再次拿出来，抛弃掉一些细节。展示一个全面的算法：

路由树查找算法
{
    pn = 树根;
    chopped_off = 0;
    IP_prefix = 32;
    while (pn) {
        pos = pn.pos;
        bits = pn.bits;

        if (!chopped_off)
            cindex = (IP_input & IP_prefix)[pos...pos+bits];

        n = 获取pn的cindex孩子;

        if (n不存在) {
            回溯;
        }

        if (n是一个叶子路由节点) {
            // Lambda表达式
            遍历n的前缀链表prefix(prefix->{IP_input & prefix == n.key ? 匹配});
            if (没有匹配)
                回溯;
            找到并退出;
        }

        cn = n;
        // 回溯时遇到非叶子节点时显然应该一路向左
        if (IP_prefix < pos+bits) {
            if (cn.key & IP_prefix[IP_prefix...pos]
                || !(cn.child[0]))
                回溯;
        }

        pn = n;
        chopped_off = 0;
        continue;

回溯:
        chopped_off++;

        // 移除0的影响，bit0不会影响结果。此后依次化1为0
        // 比方当前的cindex为0101100
        // cindex更新的步骤依次为：
        // 0101000 -> chopped_off = 3;IP_prefix = pos+7-3
        // 0100000 -> chopped_off = 4;IP_prefix = pos+7-4
        // 0000000 -> chopped_off = 5;IP_prefix = pos+7-5

        while ((chopped_off <= pn.bits)
               && !(cindex & (1<<(chopped_off-1))))
            chopped_off++;

        // 更新IP_prefix
        if (IP_prefix > pn.pos + pn.bits - chopped_off)
            IP_prefix = pn.pos + pn.bits - chopped_off;

        if (chopped_off <= pn.bits) {
            // 一次消除1个最右边的1
            cindex &= ~(1 << (chopped_off-1));
        } else {
            parent = 获取pn的parent;
            cindex = pn.key[parent.pos...parent.pos + parent.bits];
            pn = parent;
            chopped_off = 0;
            回溯;
        }
    }
}

关于回溯，最后我想给出一种没有回溯的方案。
       看来回溯是为了纠正由于压缩而导致的错误。错误在于压缩掉了的bit属于模糊匹配而非精确匹配，其实就是走错路了，例如以下图所看到的：

为了弥补这个错误，前面讲到，我们须要回溯。请看以下的两种弥补方式，当中之中的一个没有回溯。为了隔离问题，此例中我没有将路由项变换下压到叶子节点：

右边的方式是比較easy理解的，它不用回溯，而是将全部以前覆盖整个位置的路由项依照从下层到上层，也就是依照精确性递减的顺序排列在了终于的节点中，这样即便是走错路了，我们仅仅须要取整个链表中的“下一个元素”就能够了。其实这个有点像HASH冲突链表。可是这么显而易见的方式为何没有被广泛使用呢？原因在于它的维护成本太高，全部的路由项之间相互关联，插入/删除/更新一个路由项。最坏的情况能够会触及全部路由项的变动。毕竟这个算法是基于覆盖关系的，因此还是将路由项保持独立比較好。
       立即我们讲到的区间匹配，也是基于覆盖关系的。可是它的方式却截然不同。区间匹配是对路由项进行了拆分重映射，而不是简单的总体关联。

2.3.IP地址区间查找

假设再次看一下那棵带有路由节点的IP地址树，就会发现，自根向下， 最靠近叶子的路由节点。会隐含掉其到根的路径上的全部其他路由节点，即它自己全权负责了自它而下直到叶子层的全部到达叶子IP地址的路由。非常明显，这是一个区间。

非常easy证明，每个IP地址都唯一相应了一个这样的区间，一个区间由且仅由一个路由项负责。
       那么，为一个IP地址查找路由的问题就转换成了为一个IP地址查找它所相应的区间。示意图例如以下所看到的，我依旧用子树说明问题，再次给出Level压缩那一小节给出的图：

可见，仅仅要有以下的路由节点存在，就会覆盖上面已经找到的路由项。非常显然，default路由项就是ROOT。
       我们不是早就抛弃完整的地址树了吗？是的！可是对于区间查找，还真就须要一棵完整的地址树，可是我们有更好的方式构建高效的查找结构。起初。我们肯定能够构建一个静态的数组，当中元素为：

struct element {
    u32 start;
    u32 end;
    struct rt_node *node;
};

表示一个区间相应一个路由项。这个表是在路由插入期间静态构建的。果真如此。我们能够以目标IP地址作为输入，查该IP地址属于哪个地址区间，然后取出node就是结果。

果真就是这样，假设路由项为基准。那么总的数组大小就是路由项的数目。一般不会超过256(一跳可达的IP地址)，假设以区间为基准，那么数组的大小就是路由项们将整个IP地址空间切割成的区间数量，这个数量受路由条目的数量以及汇总情况，路由分布的影响，总之假设配置得当的话，也不会是个非常大的数字。

剩下的就是区间查找算法了。
       其实还有更好，更优化的方案。即DxR算法。关于这个主题，我已经写了好几篇文章了《从模拟MMU设计一个路由表的失败到DxR的回归》，《模拟MMU设计一个将IPv4地址索引化的路由表，不同于DxR》等，因此就不再赘述了，在这些文章中。我从无到有详细描写叙述了DxR的思想。总之就是切割子区间的方案造就了高效的时间和空间利用率。
       在这个小节的最后。关于区间查找。我不想描写叙述它是怎么用到路由查找中的，仅仅知道一个输入IP地址相应一个区间。而一个区间相应一个下一跳就够了。我想描写叙述一下给定一个IP地址。怎样为其定位区间，或者更加广泛的。将一个连续的域划分为若干区间。给定该域的一个数，怎样定位它属于哪个区间。我们先看一下区间：

假设这些区间都是前面闭后开的区间，即每个边界点都属于后面的那个区间。

问题如今变成了怎样构造一个单一的入口用以开启那一发不可收拾的查找过程，显然。我是带有偏见的，由于假设使用HASH算法。是不须要构造单一入口的，HASH函数已经将界限给界定了，仅仅须要解决冲突就可以，在比key少得多的冲突元素的情况下。遍历冲突链表也不是什么坏主意。

可是本文通篇都是二叉树。所以我的偏见在于，我想构建一棵二叉树，将这个区间映射到这棵树中，然后从根部开启这个自己主动的查找过程。或者说，二分查找过程。首先我将这些区间的边界点构造成叶子，然后从叶子開始，到根部为止，逆向构建这棵树：

其实，为了高效查找区间。还有超级多的优化方案，比方抽象哈夫曼区间树等等，我这里给出的仅仅是一种易于理解的简单原理。关于区间匹配。到此为止了。本来想就着这个小节引申到HiPac查找。可是我认为还是另外写一篇吧。

2.4.压缩路由树查找与区间查找

在这一小节，我们来讨论一下压缩路由树查找(比方LC-Trie等)与区间查找(比方DxR)背后的东西。

这两者是截然对立的。我们能够从两个參量来分析：

1).模糊性存在于哪里

压缩路由树的回溯全然是由于压缩，由于压缩将路由项之外的节点尽可能压缩掉了。这就带来输入IP地址自根而下游历时的模糊性，这个游历过程假设在不压缩的IP地址树上进行时，终于会在第32层精确相应一个位置。然而由于压缩的存在。路经在到达某个叶子路由项之前就有可能存在差错，即存在“走错路”的可能性，例如以下图所看到的：

该错误必须靠回溯重试来给与纠正。可是由于该匹配失败的节点已经是“尽可能”精确的节点了，所以在回溯的时候要从右到左不断化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.查找时间复杂度总结

我认为查找的时间复杂度最具有意义。空间复杂度意义相对不重要，由于好则越好，不好则越不好，占用空间越小，越easy利用Cache。从而带来时间的收益。我同样认为数据结构的构建时间复杂度也不重要，由于除非路由器中了毒。否则相比查找操作。插入，删除，更新永远是一些稀有事件。

因此，为了在查找的时候高效。牺牲一些构建，更新成本还是必要的。
       详细的时间复杂度请自行搜索。总之对于二叉树，基本就是N*logN，logN级别的，当然不要考虑最坏情况，那种情况早就被OS发现了，发现了之后就会进行平衡操作了，对于Level压缩的树，就要考虑每次索引的bit长度了。对于HASH算法，基本要看你选择的HASH函数有多好以及怎样解决冲突。

本文考虑的情况差点儿全部是关于查找的，没有说怎样插入，构建的，这不是本文的主题。由于主流软件路由器的关注的是查找性能，它们差点儿也不会执行复杂的动态路由协议，使能动态路由协议的差点儿都是核心路由器，起码也是个接入层的了。它们关注的是硬件的设计而不是软件的算法。在软件路由器上。查找性能必须优化到起码每秒接近千万次，对于上述的算法而言，足够了。再一个。IP路由是有规律可循的。它们并非随机的一组数让你排序什么的。另外就是，假设你真的爱上了DxR，那么你暂且把Cache寻址作为内部排序，而把内存里的排序操作权当外部排序吧，其实，转发表真的就不把内存当“希腊公民”看待，对于转发表来讲，内存就是磁盘...
       当然。也能够混合使用各种算法。比方DxR算法。它其实就是先构建了一棵两层的65535叉树，然后再在这棵树的节点上挂接一棵区间树。这样的组合的方案往往能够达到惊人的效果。
1).步骤分解
在本文中。我直接简单的给出了路由表的查询结构，可是并没有说明这些结构是怎样构建起来的，其实。说真的，这还真的非常麻烦，可是无关紧要。为什么呢？由于这些事情能够“慢慢来做”，这就意味着你有足够的时间去想办法假于物也。
2).模糊性/效率权衡
时间和空间并非二元对立的。有的时候，比方在数据统计的时候。假设并不须要特别精确的统计，你大可同一时候获得一些时间和空间收益，代价就是冒错误统计之险。此举能够先用模糊匹配过滤掉大多数的不匹配的情况，然后再用少量的精确匹配纠正错误。其实。即便不谈Bloom，路经压缩树本身就採用了这个思想。

4.路由表和转发表。路由缓存

我不得不再次扯到OpenVPN！
       OpenVPN被我搞成了多线程的，偶尔会segment fault。然而整个multi_instance表还是全局的。我们知道，OpenVPN全靠multi_instance表来路由数据包，这个表就是一张路由表！每个mi中存放着某个client的虚拟IP地址，真实IP地址，虚拟MAC地址(tap模式)...过来一个TUN字符设备的数据包，须要用目标MAC地址或者目标虚拟IP地址(或者iroute地址)作为key查找multi_instance表。以便获取相应client的真实IP地址以及port，反过来也是一样的。能够看到。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里启动它，甚至，直接拿个粉笔在我家小区广场的地面上启动它，前两个，我预计你也能够。可是最后一个。我预计你不敢。