路由器交换算法之CEF特快交换

一.CEF特快交换基本原理
路由器和交换机是基础网络中最关键的部分，路由器和交换机其最主要的目的有两个：一是如何准确的把数据包（帧）从源地址送到目标地址，二是如何更快速的送达。当然第二点的优先级要低于第一点的。
为了更好的完成这两个任务，交换机和路由器经过了多年的发展其各自交换包的方法也在不断改进，其不论如何变化都是为了更好的完成这两个根本任 务。本篇的主题是讲解CEF基本原理
www.ttep.cn
首先，先来看一下包转发的过程。一般来说对于一个路由器会有以下三步：
1. 查看这个包的目标地址是否可达
2. 决定目标地址的下一跳和接口。
3. 改写MAC的包头使得它可以成功的到达下一跳。

以上三步是路由器包交换的根本，到现在为止所有衍生出来的包交换方法都必须完成以上三个过程。

为了更好的理解CEF，再阐述一下另外两种比较著名的包交换方法：进程交换和快速转发
www.ttep.cn
进程交换
最古老的一个交换方法，被所有的平台所支持。
为了便于理解，用图来具体讲解进程交换的方式。


1. 接口进程（input interface processor）首先在网络中发现数据包，然后把它传递给“input/output memory”（输入输出内存）
2. 接口进程创建一个接到数据的中断。在这个中断过程中，中央处理器决定这个包的类型（一般是IP），如果需要的话就把它拷贝到内存中（processor memory）。最后，处理器把这个包放在一个适当的进入队列中（process’ input queue），同时中断取消。
3. 然后调度程序开始启动IP_INPUT进程 www.ttep.cn
4. 当IP_INPUT进程启动，它开始从RIB（路由表）中决定下一跳和外出接口，然后查找ARP缓存找到下一跳的MAC地址.(如果缓存中没有对应的地址的话将要进行ARP广播)
5. IP_INPUT进程重写包的MAC地址，然后把包的放在合适端口的外出队列中。
6. 把包从外出端口的外出队列中拷贝到外出端口的传输队列。
7. 外出接口处理器在外出队列中发现这个包然后把这个包传输到网络当中。

紧接着再来看第二种重要的交换方法：快速交换


1. 接口处理器发现网络中的包，然后把包传递给input/output memory
2. 接口处理器创建一个接收中断。在这个中断的过程中，中央处理器决定包的类型（假定是IP类型），然后立即开始交换这个包。
3. 处理器开始搜索路由缓存来决定是否这个包的目的地址可达，外出接口是什么以及这个包需要怎么改写MAC才能可达下一跳。
4. 然后把包拷贝到外出端口的传输队列或者外出队列（这个根据不同厂商的不同而不同）。这时接收中断取消，处理器继续做刚才没有做完的任务。
5. 外出接口处理器发现数据包在传输队列，然后把包传输到网络中。


现在，回过头来观察对比一下这两个交换方式究竟有什么不同之处。
在讲二者区别之前，先插一个概念。
到目前为止，包交换的方法有N种，其重要的有两类，第一个就是进程交换，而第二类名字叫做“Interrupt Context Switching”，而这第二类中包含的交换方法有“快速交换”、我们熟知的CEF，还有 一个是Optimum交换。
在阅读下面的文字之前一定要把这个层次关系搞明白。

所谓进程交换，顾名思义，就是要创建进程，我们知道处理器在工作的时候是按照schedule（计划）进行工作的，而进程交换就是这样的，它会创建一个名 为“IP_INPUT”（假设讨论的是IP包），然后放入到处理器的SCHEDULE中等待，什么时候排到了什么时候执行这个进程。发现什么问题了吗？排 队这样的规则从设计的角度来说是很不错的，但是对于包交换来说就有一些拖沓，假设目前处理器有其他的工作要做，这个时候其创立的进程“IP_INPUT” 就必须在SCHEDULE中等着，不能执行，只有当排到的时候才能执行，这样显然是浪费时间的。
相比之下，Interrupt Context Switching就要“霸道”很多，注意这个“INTERRUPT”，注意我的黑体字，这个交换方式跟进程交换的区别就是“不排队”，只要有包过来就先 处理它，等它处理完了，处理器再回去干它SCHEDULE中的工作。
以上就是进程交换和Interrupt Context Switching的不同点之一。
另外一个不同点，如果你看过我上一篇文章的话，你可能有印象，就是增加了“缓存”，处理器在查找目标地址可达、下一跳这些信息的时候不是直接去查找路由表而是去查找缓存。这也是不同点之二。

第一个不同点让交换增速不少，那么第二点不同的作用又是什么呢？“缓存到底有什么用？”

对于Interrupt Context Switching这一类交换方式来说有三种不同的交换方法刚才已经介绍过了，他们是
Fast Switching
Optimum Switching
Cisco Express Forwarding
这三种方法的主要区别就体现于其构建缓存方法的差别上，而正是由于这种差别才导致他们某些特性的不同。
先从最基础的快速交换（Fast Switching）谈起


如上图，这是一颗二叉树，这也是快速交换中的缓存数据结构，快速交换把外出接口信息和需要重写的MAC地址放到二叉树中相应的节点上，而需要转发到的目的地址就是二叉树上节点所代表的地址。
那么这样的遍历是如何进行呢？比如给出一个数是4，转化成二进制100，查找从最高位开始，从root节点出发，第一步走向root的右子树，因为100的第一位（最高位）是1，而后走向左子树，再继续向左子树方向走，这个时候就查找到100了。
如果这是一个真实的IPV4地址的话，最多需要32次查找便可以找到我们需要的网段是不是很快呢？鉴于IPV4地址的长度原因，快速交换的二叉树深度是32。
以上就是快速交换高速缓存中的数据结构，以及查找方法，下面我们看看由此而产生的一些特性，并且找出它的不足。
1、由于这个快速缓存是凭空建立的，并没有和路由表以及MAC缓存建立联系，所以当我们想应用快速交换进行查找的时候必须要先进行一次完整的过程交换。
2、由于在快速缓存中一个节点对应着一个地址，而且没有指针可以链接各个节点，所以无法实现递归查询。
不过这并不影响路由器使用递归查询，因为当每一个新的数据包进来之后都要进行一次进程交换，其间已经完成了递归查询。