DxR路由查找算法前传

你认为现在携带现代操作系统的通用计算机中哪类计算看上去是且必须是超级快的，毫无疑问，答案是内存访问。
你认为现在携带现代操作系统的通用计算机中哪类计算看上去是且理论上超级慢的，毫无疑问，答案是路由寻址。

提前放假真的很无聊！

你认为内存寻址为什么快？你认为它为什么必须要快？

因为现在操作系统基于虚拟内存地址寻址，在虚址和物理地址之间需要有一个映射，这个过程事实上减慢了内存访问的速度，但是我们拥有CPU的恩赐，即地址缓存，也就是TLB！
大 神说过，现代编程技术的核心就是寻址的技术。确实是这样。CPU核心的处理性能早就不再是瓶颈，因为CPU总是要和外设进行交流，各种总线铺设与核心之 外，路远劳顿，电磁影响，其效率事实上拖慢了整体的处理进度。CPU的各级缓存此时的作用就是尽可能地避免远途寻址，包括L1/L2/L3 Cache，TLB等，其中TLB缓存的是地址转换结果，它在数据/指令缓存L1/L2/L3未命中后最后一次努力提高效率，如果TLB也未命中，就需要 执行最慢的过程了：执行页表查找，映射到物理地址；地址总线发射物理地址；数据总线获取数据...

我们来把眼界放宽一点

如 今，整个IP网络就是一台巨大的计算机，IP地址就是你可以将其看成是内存地址，试着比较一下32位系统的内存地址和IPv4地址，你可能会想到点什么。 在如今的互联网上，CDN已经在扮演CPU Lx Cache的角色，尽可能避免远距离寻址，但是IP路由这一块的性能优化很少统一起来。为题就在这里，没有统一的解决方案是因为在网络领域，和计算机领域 正好相反，传输能力不断增强，其发展速度曾一度远超CPU的发展，网络传输技术，像爆发了一般，目前10Gbit以太网毫无压力，这些线缆可以埋在泥土 里，弯弯曲曲走在横梁上，和那些多层立交线路板上高大上整齐排列的性能还达不到10Gbit/s的板子总线相比，真是英雄不问出处。此时，如果再使用 CPU进行纯软件路由查找，那将会拖慢midbox的线速能力，CPU这种在同一板子上高大上的东西到了高速网络反而成了瓶颈。

绕开CPU的硬件转发

过 去的十几年，网络技术发展速度远超CPU能力发展速度，这主要是受限于片上Cache的整合技术，总线技术，并发技术以及锁技术，不像万兆/十万兆以太网 技术可以看成一个独立的技术，通用计算机需要考虑的是各种资源的相互配合，CPU技术，内存总线，电磁兼容...因此专业做路由器的基本都抛开了CPU， 而是直接做转发芯片。一块卡插在通用计算机上，就变身成了专业路由器。数据通路完全在卡上完成，完全绕开了CPU，这就好像在计算机中内置了一个小计算 机。通用计算机仅仅提供管理和控制功能，比如Cisco的特快转发就是这么玩的。

合久必分，分久必合

随着片上技术和板 上总线技术的整合能力的提升，通用CPU的各级Cache无论从大小，效率还是使用上均有了很大的提升，访问内存的效率也提升了。此时，CPU再次将各类 路由转发硬件卡统一在一起的机会来了。当然，并不是说所有的硬件转发技术均会被CPU转发技术取代，如果想追求更高的速度，当然还是专业的硬件转发完胜 CPU转发，但是起码，高速的CPU转发技术可以淘汰并整合掉市场上的大多数硬件转发技术。

类比虚拟地址映射技术-古老的算法

精 通Linux网络技术的应该都知道，现有的两种路由查找算法是HASH查找和TRIE树算法，这两种算法均包括复杂零散的数据结构，对于纯软件层面的构 想，它们设计地都不错；另外精通BSD协议栈的也该知道，BSD的Radix树算法在软件路由查找方面也表现不俗。但是仔细想一下，这些算法几乎都是脱胎 于硬件路由转发技术蓬勃发展的几十年，因此它们更像是隐秘力量的自留地里自发长出的萌芽，并非是大势所趋的结果。这类算法在本质上是一类通用的路由查找算 法，它们并非有针对性的利用所在硬件的硬件结构，比如CPU Cache等，也不晓得自己在什么平台上跑，这些都被OS的接口屏蔽掉了，所有的针对体系结构的优化都是以预编译宏的形式或者补丁的形式存在。

类比虚拟地址映射技术-DxR算法

把 目标IPv4地址看成一个地址空间的虚拟内存地址，把到达该目标地址的下一跳看作是对应虚拟内存地址的物理页面地址，是不是就能像构造页表那样去构造路由 表了呢？想想看，虚拟地址翻译到物理页面是多么地频繁，它的效率是多么地高！遗憾的是，CPU内部没有处理IPv4地址的MMU机制，当然作为通用 CPU，它也不该有这种机制。但是总是可以通过类比悟出一些什么。
       路由表查找的效率不在于算法本身的时间复杂度(相信很少有人用遍历法吧，能被选中作为系统查找算法的都是可接受的时间复杂度的算法)，而是在于实现中的开 销，如果能利用CPU的Cache，那么同样时间复杂度的算法和不利用Cache的算法在效率上有数量级的超越。如若想利用CPU的Cache，那么对数 据结构就有严格的要求，必须紧凑，且不能占据太多的空间，把路由表组织成页目录/页表类的结构是一个很好的想法，足够紧凑，可以载入Cache。另外做一 点优化，IPv4地址和虚拟内存地址完全可以类比，但是路由表对应页目录的部分并不以固定的IPv4地址bits来做索引，而是取K>=16，索引 到哪里呢？索引到的不是页表，而是一个range表，这个表固然也可以按照32-K来做索引，但是鉴于路由项很多都是经过聚合的，因此这里可以是一个二叉 树组织，在组织上依然是紧凑的数组。这就是DxR算法的核心。可见，并没有什么新的东西，只是对已有的算法的数据结构做了重新组织，核心思想完全可以参见 CPU的MMU实现。