这是一个失败的尝试我不知道有没有人这么玩过，也许有，也许没有。但不得不先说一下本文的前提，本文中所述的设计是一个不可行的设计，它是不可能实现的！原因在于我在思考的过程中没有全盘应对。然而，虽然是一个失败的设计，也要把这个过程记录下来，因为期间的思考过程是值得保存的，即便是没有带来预期的结果。 另外，这是我在帮一个朋友的项目中所做工作的一部分，假期在旅游的间隙，酒店里做的，没有拿钱，纯粹帮忙，也没有占用工作时间，当然也没有占用旅游的时间，所以我只是记录一下而已。空间换时间时间和空间永远都在厚此薄彼，只因为设施不全，在资源匮乏的年代，只能取舍。但是如果资源丰盈，鱼与熊掌，完全可以兼得！对于路由查找而言，紧凑的数据结构占用了很小的空间，难道它就要为此付出时间的代价吗？如果我们考虑MMU设施，就会发现，紧凑的数据结构不但节省了空间，还提高了速度。 我们长期受到的教育就是取义一定要舍身这样的教育，如果不舍身，取到的不会是义，也可能会被讹诈，不怪自己被讹，只因自己没死。其实仔细想想，即便在资源不那么丰盈，，甚至资源紧缺的年代，紧凑小巧的数据结构一定会带来时间的浪费吗？或者说，速度快高效率的算法就一定要浪费内存吗？如果是这样，那么MMU是怎么会被设计出来的呢？如果真的是这样，MMU会因其维护自身所消耗的时间和空间超过了它的目标带来的收益而被无情pass掉。然而，我们都知道，它最终被设计出来了。并且，得益于CPU Cache的高效利用，MMU退化成了一个Cache不命中时才会启用的慢速路径，而通过局部性我们知道，大多数时候，执行流走的是快速路经…看来，思路该换一下了。 我知道的是，DxR算法就是这么玩的，所以这不是我个人在胡扯。但是我的玩法和DxR稍微有一点不同…将最长掩码逻辑提前到插入的时刻就Linux等通用操作系统而言，路由表的查表开销主要集中在“最长掩码匹配”上，因为在数据包执行IP路由的过程中，输入仅仅是一个IPv4地址，即IP头中提取的目标IP地址，而此时的IP路由模块并不知道路由表中哪些条目和这个IPv4地址相关，需要进行一次查找才能确定，在查找的过程中执行“最长掩码匹配”逻辑，对于HASH组织算法而言，按照掩码的长度组织hash表，匹配顺序自32位掩码依次向下，而对于TRIE组织算法而言，情况也差不多，详情参阅《Internet路由之路由表查找算法概述-哈希/LC-Trie树/256-way-mtrie树》。 对于查找而言，特别是HASH算法，难免要进行比较，比较结果要么为0要么非0，如果去除了比较的成本，理论上会节省一半的时间，对于TRIE树而言，算上回溯，节省的成本更多。当然了，不管是HASH算法还是TRIE树算法，都会围绕数据结构本身以及地址的特点做很多的优化，但是遗憾的是，这些优化治标不治本，无法从根本上将“查找”这个操作根除！好吧，消除查找/比较就是根本目标！ 将IPv4地址索引化，就是答案！IPv4地址空间总共有4G个地址，如果将每一个地址都作为一个索引，那么将会消耗巨量的内存，但是这不是本质问题，完全可以学着页表那样组织成分级索引。本质问题是如何将路由项和索引进行多对一的对应！即根据一个IPv4地址，将其作为一个索引，然后索引直接指向所有路由结果中最长掩码的那一条结果！这个倒也不难，我姑且不引入多级索引，仍然用平坦的32位IPv4地址空间做一级索引。如下图所示：
可以看出，最关键的就是用路由前缀将IPv4地址空间划分为多个区间，按照上图所示，拿着目标IP地址当索引，向右走，碰到的第一个路由项就是结果。最长掩码的逻辑完全体现在插入/删除过程中，即从左到右前缀依次变短，长前缀的路由项会盖在短前缀的路由项的前面，这就是核心思想。其实在HiPac防火墙中，也正是使用了这个思想，即区间优先级。只是合理巧妙的编排数据结构，将最长掩码逻辑提前到插入/删除的时刻，将IP地址索引化，这样会让匹配过程一步到位。 我们不能用前缀长的路由完全覆盖后面的，因为当它被删除掉的时候，后面的还是要暴露出来的。 好了，总结一下。插入/删除操作在执行的时候，保证了最长掩码的那个路由项覆盖在了它作用地址区间的最前面。路由还是交换IP互联网被设计成基于路由的而非基于交换的，这背后有一个哲学意义上理由。然而如今，人们逐渐在IP路由上加入了交换的特征，从而设计出了很多基于硬件的快速转发装置或者依靠路由表生成交换转发表实现快速转发，比如三层交换机。但是到底什么是交换？什么又是路由？简单来讲，路由是一种比较软的叫法，其执行方式为“取出协议头的字段，然后和路由表的内容做‘最长前缀匹配’，其间经历大量的访存，比较操作”，而交换则是比较硬一些的说法，其执行方式为“从协议头中取出一个‘索引字段’，直接索引交换表，然后根据索引指向的结果直接转发”。看看吧，我的玩法和DxR是不是变路由为交换了，也许你觉得这无非雕虫小技，但是生活难道不应该为这种小事情而乐呵乐呵么…设想中的实现-将“查找”变成“访问”众所周知，现代操作系统是基于虚拟内存的，更好地实现了进程之间的隔离与访问控制，但是本文不谈这些，本文要说的是基于这个原则的“一种利用”。 事实上，在运行着现代操作系统的计算机的运行过程中，每访问一个地址都要经历一番“查找”，这个查找过程是如此地快以至于大多数用户甚至程序员(系统程序员除外)都会视而不见，甚至很多人都不知道存在这么一个查找过程，这个查找过程就是MMU的虚拟/物理地址的转换过程。 如果我用IPv4路由前缀作为虚拟内存地址，将其对应的下一跳等路由结果信息作为物理页面的内容并按照此对应关系建立页表映射，那么我只需要访问一下从IP头中抽取的目标IPv4地址，就可以获取对应的物理页面的内容，内容是什么？西服吗？NO！内容就是路由的结果。我将第一节的示意图加以简化再稍微变换一下，变成了下面的样子：
他们比任何人都分毫较量，又比任何人都口是心非。他们比任何人都依赖彼此，
