路由器

路由器是网络层设备，基于网络层数据报中的首部字段值做出转发决定

转发

路由器有多个输入端口和输出端口，输入的数据报经过转发结构进入特定的输出端口

基于目的地的转发

IP地址有32位，假定路由器有四个输出端口，所有的$2^{32}$个目的地都应当唯一地对应于某一个端口，最终会形成这样一张表

目的地范围	端口
11001000 00010111 00010000 00000000~11001000 00010111 00010111 1111111	0
11001000 00010111 00011000 00000000~11001000 00010111 00011000 1111111	1
11001000 00010111 00011001 00000000~11001000 00010111 00011111 1111111	2
其他	3

实际上只需要使用前缀匹配即可，即像这样

前缀	端口
11001000 00010111 00010	0
11001000 00010111 00011000	1
11001000 00010111 00011	2
其他	3

如果存在多个匹配，则使用最长前缀匹配规则，将数据包转发到最长匹配前缀对应的端口

交换结构

交换结构有三种实现方式：经内存交换，经总线交换，经互联网络交换

• 经内存交换：数据包拷贝到系统内存中进行交换，由CPU控制，每个数据包需要穿过系统内存两次，交换速度受限于系统内存

  在现代路由器中，目的地址的查找和数据包的存储是由输入线路卡处理的，输出端口从指定内存地址读取数据包，而不经过CPU，像共享内存的多处理器

• 经总线交换：输入端口为分组指定一个端口，然后经一个共享总线传递到所有端口，只有指定的端口收到分组后才保存它

  这样不需要经过CPU，但是同一时刻只有一个分组能被转发，因为总线是共享的

• 经互联网络交换：如纵横式交换机，只要目的端口不同，分组可以被并行转发，是非阻塞的

排队

输入排队

如果交换结构不够快，那么输入端口将出现排队。输入排队会带来问题

• 队头阻塞(HOL)：队头的分组会阻塞其后面所有分组的转发
• 丢包：输入队列溢出时会导致丢包

当交换结构的速率能达到所有输入端口的速率和时，就不会出现输入排队

输出排队

多个输入端口同时向一个输出端口发送时，会在输出端口形成排队，这样的排队是不可避免的

当输出队列满时，出现丢包。虽然增大输出队列能缓解丢包，但是更大的输出队列意味着更大的延迟，延迟太大的包终究会被重传，丢就丢了。因而输出队列并不是越长越好

分组丢弃

当队列满时，丢弃分组可以有以下的策略

• 弃尾：丢弃后到的分组
• 按照优先级：丢弃低优先级分组
• 随机：随机挑选一个幸运分组丢弃

还可以在队列满之前就开始丢弃分组，称为主动队列管理。一种策略是RED(Ramdom Early Detection 随机早检测)，它的策略是这样的：

• 路由器维护每个端口上的输出队列平均长度，按照下面的公式更新

  $$Len=(1-\alpha)\times Len+\alpha\times SampleLen$$

• 当平均长度达到较小阈值时，按照概率$p$丢弃后到的分组

  分组队列越长，距离上一次丢弃时间越长，$p$越大

• 当平均长度达到最大阈值时，丢弃到达的每一个分组

这与TCP的拥塞控制计是配合的

调度策略

调度即输出端口从队列中选择要发送更多分组，它有三种策略：先进先出，优先权排队，加权公平排队

• 先进先出：先到的分组先被传输
• 优先权排队：优先传输优先级高的分组，相同优先级的分组先进先出。在非抢占式优先权排队下，分组一旦开始传输就不能中断
• 加权公平排队(WFQ)：将到达的分组分类，每个类别具有独立的队列，并具有一个权值，按照权值循环地选择某个分类进行传输，应保证每个分类都能分到其权值的带宽。这样各个权值的分组都有机会进行传输，权值高的分组传输的机会更多