硬件路由转发原理浅析

有人问我,对于路由转发,硬件转发表的性能真的要超出软件查表比方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处理器内部的电路,真的有可能跟我上面的这个差点儿相同。
       眼睛有点睁不开了....

原文地址:https://www.cnblogs.com/gccbuaa/p/6958875.html