第四章 第3节

第三节：

一、TCAM：最长前缀匹配的硬件实现

最长前缀匹配不能靠软件一条一条慢慢查，因为路由器每秒要处理大量分组。

所以高性能路由器常用：

TCAM，三态内容可寻址存储器。

TCAM 支持三种状态：

0

1

*，表示无所谓

它可以并行比较很多转发表项。

所以 TCAM 的优点是：查找速度非常快，可以硬件并行完成最长前缀匹配。

二、交换结构 switching fabric：

把分组从输入端口传到输出端口。

假设：

有 $N$ 个输入端口

每个输入端口速率为 $R$

理想情况下，交换结构速率应该达到：

这样 $N$ 个输入端口同时输入时，交换结构也不会成为瓶颈。

三、三种典型交换结构

1. 通过内存交换

第一代路由器常用这种方式。

流程是：

输入端口收到分组

分组复制到内存

CPU 查看首部，决定输出端口

分组从内存复制到输出端口

缺点：

受内存带宽限制。因为一次转发要经过内存读写，速度比较慢。

2. 通过总线交换

多个端口共享一条总线。

输入端口把分组放到总线上，输出端口从总线上取走。

缺点：总线竞争。

同一时刻总线资源有限，如果很多端口同时想传，就会争用总线。

所以交换速度受总线带宽限制。

3. 通过互联网络交换

比如：

crossbar

Clos 网络

多级交换网络

这种结构可以支持多个输入输出同时交换。

优点是：

利用并行性，交换能力强。

高性能路由器通常采用这种方式。

四、输入端口排队和 HOL 阻塞

如果交换结构速度不够快，输入端口来的分组不能及时送到输出端口，就会在输入端口排队。

HOL 阻塞，Head-of-the-Line blocking，队头阻塞。

什么是 HOL 阻塞？

假设输入队列最前面的分组想去输出端口 1，但是输出端口 1 正忙。

那么队头分组走不了。

问题是：它后面的分组即使想去一个空闲输出端口，也被它挡住了。

所以整个队列都卡住。

队头分组被阻塞，导致后面本来能走的分组也走不了。

输出端口排队

输出端口排队非常重要。

为什么输出端口会排队？

因为多个输入端口可能同时把分组送往同一个输出端口。

但是输出链路只有一个，速率有限。

所以：到达输出端口的速率可能大于输出链路发送速率。

于是分组只能在输出端口排队。

输出端口排队的结果

会带来两个问题：

排队时延增加

缓冲区满了会丢包

这和 TCP 拥塞控制联系很紧。

网络拥塞很多时候就是因为：

路由器输出端口队列太长，甚至溢出丢包。

调度 scheduling

输出端口队列中可能有很多分组。

这时候路由器要决定：下一个发哪个分组？这就是调度。

常见思想有：

先来先服务

优先级调度

公平队列

这里主要是引出概念，不一定要求深入算法。

调度决定队列中的分组发送顺序，会影响公平性和服务质量。

缓存大小

路由器需要缓存，因为分组到达速度和发送速度可能不一致。

1. 传统经验公式

传统经验认为缓存大小大约取：

其中：

：缓存大小

：典型往返时延

：链路容量

这个其实就是：带宽时延积。

2. 多流情况下的推荐公式

如果有 $N$ 个 TCP 流，可以取：

原因是多个流的流量波动可以相互平滑，不需要每个流都按最坏情况准备缓存。

3. 缓存太大的问题

缓存大可以减少丢包，但也会带来问题：时延变大。

尤其是家庭路由器中，大缓存会导致：bufferbloat，缓冲膨胀。

表现是：

不怎么丢包

但是延迟特别高

游戏、语音、视频通话体验变差

所以缓存不是越大越好。

缓存管理

缓存满了或者快满了，路由器要决定怎么处理。

1. 丢弃

最简单的是：队列满了，新来的分组直接丢弃。

这叫尾丢弃 drop-tail。

2. 优先权

有些分组可以优先保留或优先发送。

比如实时语音、视频可能优先级更高。

这属于 QoS 的思想。

3. 标记

路由器也可以不直接丢包，而是标记分组，提醒端系统：

网络开始拥塞了，该减速了。

典型机制：

ECN：显式拥塞通知

RED：随机早期检测

核心思想：不等队列满了才处理，而是在拥塞早期就让发送方知道。

通用转发和 SDN 的关系

传统 IP 转发主要是：根据目的 IP 地址查表。

而通用转发更灵活：

可以根据首部中的多个字段匹配，然后执行动作。

比如匹配：

源 IP

目的 IP

源端口

目的端口

协议类型

然后动作可以是：

转发到某个端口

丢弃

修改首部

发送给控制器

这就是 SDN/OpenFlow 中的：

match + action，匹配 + 动作。

所以 SDN 的转发表不只是传统 IP 路由表，而是更通用的流表。

前三节总结：网络层有两个功能：

路由和转发。

路由属于控制平面，负责计算路径。

转发属于数据平面，负责在路由器内部查表并转发分组。

Internet 的 IP 层提供尽力而为服务，不保证交付、顺序、延迟和带宽。

一个路由器收到分组后，先在输入端口处理，查转发表，使用最长前缀匹配决定输出端口，然后通过交换结构送到输出端口，最后在输出端口排队并发送。

如果交换结构不够快，会出现输入端口排队和 HOL 阻塞。

如果多个输入同时发往一个输出，会出现输出端口排队、时延增加、缓存溢出和丢包。

缓存可以减少丢包，但缓存太大会导致高时延和 bufferbloat。

下一节我们看IP和之后的解决方案