Earliest Departure Time
1. 基于 queue 的流量整形
- 主机 egress 流量经过分类器(classifier)进行分类;
- 流量经过分类后分别放入不同的 queue ,各 queue 的发送速率限制可能是不同的;
- 某个调度器(scheduler)负责统一调度以上所有 queue 的发包,将包从 queue 中取出放到主机网卡的 TX queue 中;
- 网卡将 TX queue 中包无差别地发送出去。
三个组件:classifier、queue、scheduler
1.1. 延迟和丢包
在过去25年内,以太网带宽 从 10Mbps 演进到 100Gbps,发送速率上限取决于主机侧。当希望发送更快时,只需要将网卡及网线从 100Mbps 换成 1000Mbps,非常简单直接。 主机外面的东西不用担心,自然会有人和技术能支撑主机的发送。
摩尔定律说:每18个月带宽就能翻一番。
但到2003年,Intel 突然告诉我们下一代处理器不能快一倍了 ——甚至实际上还会慢一点, 然后通过多核来提升整体性能。
带来的影响:
- 服务器的网卡带宽追平了交换机之间的互联带宽,我们无法造出速度永远比网卡快一个数量级的交换机了。
- 原来单核或单主机能完成的事情,现在只能分发到多核、多主机上去。
- 之前通过升级硬件设施来避免延迟和丢包,现在行不通了。甚至愿意忍受更大的延迟也无法避免丢包。
过去,流量管理在中间设备(路由器/交换机),基于缓冲队列(queue)实现,已无法适用当前的网络现状了。
1.2. 基于 queue 存在什么问题?
- CPU开销随 queue 数量 线性增长;
- 多个CPU共享多个queue,导致CPU之前竞争开销(锁);
2. 基于 time 的流量整形
Google 的解决思路是:感知网络瓶颈,以瓶颈处的最大发送速率发送数据包。
依赖的最重要因素不再是 queue,而是时间(time)。
引入了 EDT(earliest departure time)模型:
- 给每个包(skb)打上一个 Earliest Departure Time (EDT) 时间戳;;
- 用一个时间轮调度器(timing-wheel scheduler)代替原来缓冲队列(queue),根据时间戳控制 egress 发包。
- 调度复杂度 O(1),待发送的包是按时间戳排好序的;
- 调度器能直接给 socket 反压,控制 socket 发送速率;
- 每个CPU一个 shaper,无锁;
好处:
- 缓存友好 (没有指针链了);
- RCU友好(单槽更新);
- Qdisc 变成了纯计算模块,不需要维护内部队列了;