对于CEF的简单理解

阅了很多CEF的相关资料，包括其他厂商对于CEF的研究材料（这些都是机密，便于开发基于某厂商的XEF技术），发现实在是很不全面。看看书本上对于CEF的讲解，那就叫一个疼啊。网上搜搜CEF，发现尽是书本上的一些PPT外加文字内容。

参考了多厂商资料，结合一些自己的理解，对CEF有自己的一些看法，这里共同学习一下。

注，CEF技术本身就比较的私有，所以关于这个技术的详尽说明估计在CISCO网站上是没法找的出来的。可以发现，只要是CISCO的私有玩意儿基本上配置都很简单，原因就是让客户用用就好，别深究，我不会承认对错的。所以这也是为什么我说CEF小气了。

好吧，我们开始。

路由器转发数据包的模式从目前能够接触到的产品中可以分为进程交换，基于缓存的快速交换及基于拓扑的快速交换。当然，有的厂商提出了什么多线程，多核CPU协同处理等技术基本上也是对这些交换模式的优化。

路由器收到一个数据包，这个数据包会放入IO/MEM，当然，接下来CPU会判定是否处理这个包，假设需要处理，那么这个包的内容将被Copy至Processor MEM中（CISCO设备上可以灵活的配置IO和Processor占用物理内存的比例）。

CPU接下里啊就开始Schedule一个IP_Input进程，这个进程启动后，他会参考路由表信息决定Next-hop和Outgoing Interface，继而查询ARP缓存，若没有缓存，会做ARP查询工作。

得到了相关的L2信息后，进程会重写包的L2地址，然后将其报文放入对应端口的Out队列中，接下来，出接口就会将这个报文发送至网络。（注意，QOS技术中的队列技术就是应用在这个流程上）

而基于缓存的快速交换其机制和上面的差不多，只是在CPU接收到报文之后，他不会直接的处理IP_Input，而是查找相对应的Route-Cache，看看Cache中有没有对应的L2重写信息，如果有，直接根据信息中的内容从新配置数据包并发送，若没有，继续使用CPU进程。也就是说，CPU做了一次处理之后，会把对应的结果放入Cache中便于下次使用。这种模型看似可以，但是对于网络经常变化的环境，很明显就不太适用了。

不过，上面所说的两种转发模式和CPU的关系还是比较的紧密，换句话说，CPU在这里还是很厚道的执行FIFO原则，什么意思呢？假定CPU现在正在处理1+1等于几，突然来了个IP包，那CPU只能把IP包缓存起来，等1+1出了结果之后再处理报文，这样很明显会对报文处理影响很大，那么对于专用的包转发设备来说，最好还是优先处理包，手上如果有任务，先放放，把包处理完了再去处理别的。（细心的TX可能意识到了这个问题，尤其在做GNS3时，如果ping包过多，路由协议可能会莫名其妙的失效一下。）这种模型我们给个概念：Interupt Context Switching，注意，关键字是Interupt，中断，抢断！！！！

我们要讲的CEF实际上就是上述模型的一种分支。其实出了CEF之外，还是有不少转发技术是基于Interupt Context Switching的，虽然Interupt Context Switching可以有效提升转发效率，但是作为不同的转发技术，其实在构造数据索引时方法还是有点区别的，正是这点区别，让我们的转发效率越来越高。

这里不得不谈到一个无聊的概念，N叉树（x-way mtree）。我们常见的树是2叉树，因为计算机习惯使用二进制。
看看2叉树是什么样，手画一个：

假设现在路由器要找一个数字5，换成Binary就是0101，注意这里检索的时候不会考虑首位0，所以接下来就是检索101，首先查到右侧分支1，在查到左侧分支10，最后又是右侧分支1，最终得到101，并且得到这个树的具体位置，而目的上标记的就是一些转发消息，这个流程就完毕了。

当然，如果说是处理IP地址，那么使用2叉树就需要32层，这样的话查询次数就很多了。所以，能否再优化呢？
假设这时候我们提出一个256叉树，那么这个图就应该变为：


看看，上面这个图，如果说针对IP地址，4次查找就有结果了。

批注一下，这个256叉树肯定会大量占用内存资源，但是，现在内存便宜如白菜，所以，“以空间换时间”这种理论目前看来绝对行之有效，因为它节省了检索周期。

速度越来越快了，而且针对IPv4，一般3层就能出结果。

快速交换使用了抢断式模型，又优化了存储器中的数据结构，但是这种优化仍然停留在表面，当检索到目的地对应信息之后，路由器接下来仍然会进行下一跳查找，重写信息计算等繁琐事项，这样又会再次的占用CPU周期。

后来CEF果断出现，它不仅采用上述快速交换的模型和数据结构，同时它也单独维护了一个Adjacency Table。对于256叉树的结尾事实上指向了一个Adjacency Table中的具体条目，厉害的是，这个Adjacency Table可以理解为Pre-Built，也就是说是在路由器未进行数据转发之前通过ARP等机制预先建立的信息，那么一旦有个预先建立的重写信息（包括新的Src Mac，Dst Mac，TTL，CHKSUM）路由器可以快速的将报文进行重新封装处理实现快速交换。

---------------------------------------------------

路过占楼而已

我是个凑数的。。。

支持一下:lol

谢谢楼主，共同发展

没看完~~~~~~ 先顶，好同志

好好 学习了 确实不错