硬件路由转发原理浅析

时间：2015-07-19 00:09:42 阅读：271 评论：0 收藏：0 [点我收藏+]

有人问我，对于路由转发，硬件转发表的性能真的要超出软件查表比如Linux系统很多吗？
我怎么回答呢？给出数据吗？我没有数据，因为我的本职不是做这一块的。给出理论吗？恐怕我也没那口才。画个图？我发现我系统没有安装画逻辑电路的工具。那怎么办？这个问题的答案我真真在心里，只是难于言表，于是乎，我采用手绘图手机拍照的方式，展示一下硬件转发表的威力，由于没有实际数据，我采用相对比较的方式，让诸位看一下软件转发为什么是个垃圾。也顺便介绍一下专业的路由器交换机是怎么转发数据包的。
不过，手绘图实在是不敢恭维，所以我就照着手绘图用viso画了一个。

我是一个送货修路的

人生有多少十年？
我想成为一名送货的，修路的。我送的是IP数据报，修的是全光网络。
如今是一个浮躁的年代，大家都在争先恐后往食物链顶端爬，搞什么Android app，iOS什么的，而我始终在我自己感兴趣的领域，一混就是10年！而这个领域，就是食物链的底端。

开始前的声明

我假设你已经知道了基本的门电路的工作原理，比如与门，非门，或门，锁存器，电容存储单元，存储阵列等基本概念。接下来我用这些门来展示一下一个数据包实际的路由查询过程到底是个什么样子。在继续阅读之前请注意，
对于专家：本文不适合你，因为这是我自己想的，我为初学者着想，没有遵循CAM，TCAM的规范，空间利用也不好，总之，跟你想象中的相比，我的做法很垃圾。
对于不知情者：本文十分适合你，可以让你瞬间体会精髓，这也是我的心愿。

step by step

首先给出一幅图：

技术分享

给定一个目标IPv4地址，经过几个门就可以找到下一跳的索引，是不是很奇妙啊。事实上真的就是这样。
如果你仔细看这个图的话，你可能会发现，这有什么了不起的啊，你的译码器译码的是32bit的地址，也就是说32位的全集，4G个地址，每一个前缀都必须有4G个entry的空间，这可怎能受得了啊，但是我要说的是，这里仅仅给出一个例子，我当然知道用N路组相连的方式来组织，但是那样会加入一些比较门电路，不直观，所以我就直接用32位地址键了。也许你还会反驳，即便用软件，我建立一个4G大小的hash表，用IPv4地址本身作为hash值，不更加简单吗？不比硬件实现更加优化吗？我想说的是，NO！Why？请看一个CPU cache的普通命中过程，以下是图示：

技术分享

跟一个IPv4地址路由查找过程相比，少不了几个门。注意，这只是在访存之前的cache匹配的门电路，这还算是比较高效的，如果没有命中，访存的电路涉及到的电路自不必说，单单是CPU的执行单元这些电路就够了，如果你了解微结构，那你就会知道，一条指令的执行也是一个极其复杂的过程，CPU内部有通用执行单元，流水线等，每一个步骤都是要花费时钟周期的，那么请问，以下的代码需要多少门电路呢？
entry = bucket[destIP];
nexthop = entry->nexthop;
先把它翻译成汇编然后再看吧。更何况，你不可能创建一个如此庞大的hash表，常规的看，TRIE树查找法算是高效的了，比它更高效的是我自己的DxR Pro++结构，但是即便是DxR Pro++，和上述的硬件转发相比，也是弱爆了的了。
继续看上面的硬件路由转发原理图，译码器后面的交叉网络事实上应该画成黑盒子更加清爽些，但是我还是情不自禁地画成了不伦不类的样子，每一个交叉点上都存着1bit的数据，它非0即1。译码器译码的结果选择一根字线，然后该字线上的所有与之交叉的位线由于字线电平拉高，交叉点上的1bit数据就稀里哗啦掉下来了，这其实也是内存访问的原理。在第一个译码器后面，有一个比较重要的操作，那就是“最长前缀”的逻辑，我不知道标准的TCAM是怎么做的，但是我觉得我的上述的方式也能说明问题。引入了两个概念，反掩码和消除位，其中反掩码是掩码按位取反的结果，而消除位是为了唯一取得匹配到的“最长前缀”那一项的。最终，我们得到了匹配到的最长前缀的那一项对应的下一跳索引地址，然后再来一个译码过程，通过地址得到下一跳索引，取得胜利。
注意，所有的操作都是同时进行的，在匹配28位前缀的同时，24位，16位，10位，8位前缀也在同步匹配，它们同时经过同一组门。这就是优势！

硬件转发和CPU转发

我们发现，上面我描述的那个电路几乎不能干别的，它只能为一个IPv4地址查询下一跳(当然还有写入，删除等电路逻辑，我没有画出来)，然而就是这样一个电路，比CPU那个复杂的东西效率高多了，所谓它是专业的，而CPU只是通用的。
       CPU作为一个通用执行单元，它完全是傻瓜的，却又什么都能做，具体要做什么，是通过从内存中获取的“指令”来指示的，也就是说，指令本身就是数据的一种表现形式，编程的本质是什么？编程的本质就是从内存中获取的指令对CPU内部电路的编程。
       然而，对于硬件转发而言，它的输入是一个IPv4地址，纯粹一个数据！它没有指令，指令就是电路本身。所以，它可以同时进行这一切，就好像这条“指令”是从外部输入的一样。CPU不能执行这样的“指令”是因为这个指令它特殊了，现代处理器越来越多地向RISC发展，由程序员和编译器自己完全来决定要做什么，而不是处理器的设计者猜测程序员会用到什么功能那样子。我可以想得极端一点，如果在一款CISC处理器中，它为了对得起它的分类，它的设计者为其设计了一条“路由查询”的指令，那么该通过CISC处理器内部的电路，真的有可能跟我上面的这个差不多。
       眼睛有点睁不开了....

硬件路由转发原理浅析

原文：http://blog.csdn.net/dog250/article/details/46947959

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)