Network(3) -- 路由器里面有什么？

输出端口的处理

数据包被存在输出端口的内存中，然后通过输出的连接发送出去。这包括选择和取出队列中的数据包进行传输，执行所需的链路层和物理层功能。

队列什么时候发生？

在输入端口和输出端口都可能发生队列，队列的严重程度取决于流量负载，交换结构的相对速度，以及线的速度。路由器的内存如果用完，就可能发生丢包的情况。

假设输入和输出线的速率都是R_line 个包/秒，有N个输入端口和N个输出端口。同时假设所有的包的长度都相同。定义交换结构的速率是R_switch。如果R_switch比R_line快N倍，那么输入端口就几乎不会出现排队。这是因为即使所有的N个输入端口同时接收到数据包，所有数据包都要转发到同一个输出端口，也可以及时被switching fabric清空。

输入队列

但如果交换结构不够快呢(相对于输入线的速度)？那么输入端口来的包就需要排队，等待switching fabric处理。

假设1号输入端口有两个包要传到1号输出端口，3号输入端口队列头的包也要传到1号输出端口，后面的一个包要传到2号端口，那么对于3号输入端口来说，要等待的不仅是前面那个包，后面那个包也要等着。这种现象叫做head-of-the-line (HOL) blocking.队列头阻塞————输入队列里一个排队的包因为队列头的另一个包必须要等待。这就非常容易造成丢包，即使输入的速率仅仅到达容量的58%。

输出队列

还是假设交换结构的传输速率是输入线的N倍，所有的包都指向同一个输出端口。那么在同一时间就会有N个新的数据包到达同一个输出端口。然后刚处理完一个包的时间之后，又可能有N个新的数据包到达。因此，即使switching fabric（交换结构）的速率是线的N倍，输出端口还是很可能产生队列，最终造成丢包。

当内存不足时，要么把新来的包丢掉，要么从队列的包中丢掉一个或多个包给新来的包腾个位置。有时候，在缓存满了之前就扔掉一些包更好，因为可以给发送者发信号。一些前瞻性丢包的策略，也叫active queue management(AQM)算法，已经被提出和分析。AQM算法中最广泛使用的是Random Early Detection(RED)算法。

当输出端口有队列时，就必须有packet scheduler，数据包调试器，来决定先传输队列中的哪个包。

这个缓存到底需要多长呢？缓存的数量应该等于平均的RTT乘以线的容量。

数据包调度

现在我们来思考那些排队的数据包的发送顺序问题。首先最简单的办法就是先来先服务，first-come-first-served。另一种方法是，有一个队列有较高的优先级。还可以使用轮询（round-robin）队列，先把客户按优先级分成几类，然后轮流服务每个队列。

First-in-First-Out(FIFO)

当输出链接正在发射另一个包的时候，输出队列就必须排队。如果没有充足的空间了，那个队列调度政策需要决定是把新来的包扔掉呢，还是从队列里扔掉一个腾出空间。

Priority Queuing

到达的包会先按照优先级分类，比如包括网络管理信息的包有更高的优先级，再比如实时IP语音的包有更高的优先级。当发送包时，先发送那些高优先级的队列。相同优先级的就FIFO。

Round Robin and Weighted Fair Queuing (WFQ)

最简单的Round Robin是在不同优先级的队列之间依次轮询。“持续工作队列”原则下的轮询，如果发现一个队列空了，则立即转向下一个队列。

一个广泛使用的轮询队列叫做“加权公平队列”（weighted fair queuing(WFQ)）原则。WFQ跟Round Robin类似，但不同点在于，每个队列都有一个权重，来保证它至少有一定比例的带宽。