CAVER的意义在于利用全局信息进行选路。
背景
现有负载均衡方法
降低颗粒度。
- 逐包选路：引入乱序，RDMA性能下降
- 根据包间隔时间拆分一个流为多个小单位进行选路：RDMA发包均匀，难以切分
- 一对网卡建立多个QP拆分流量：路径先随机指派，后续依赖轮询以及对网络拥塞有限的感知，不会去选新的拥塞少的路。
方法
使用ACK包来携带路径和拥塞情况
和以往做法的差别
以往的做法在主机上处理ACK包，受限于已有流的数量。ACK包实际上会穿过大部分的链路，如果有交换机的支持，到同一目的地的不同流可以共享信息，能更有效地发现路径。
CAVER组成
路径信息的收集(非ToR)
CAVER可以在交换机上共享多个流的信息，这一交流允许我们探测包实际没有经过的路径的拥塞程度通过将每跳之间的信息进行组合拼接
三张表：
- DRETable按端口存拥塞度
- BestTable将IP映射到最佳路径
- GoodTable将IP映射到可接受路径
拥塞程度计算
用CE用32-bit Discounting Rate Estimator即DRE计算
DRE是累加端口发出数据大小，定时乘以小于1的系数来衰减
$$CE = \frac{DRE}{C} \times 255$$
C是链路带宽，最终会得到带宽利用率
BestTable存储
-
Path: 32位，记录出向端口，每个8位，三层胖树足够。 -
CE:8位 -
Time: 32位，最后更新时间
信息传递（Give-and-Take）
一个ACK包携带当前经过的路径和CE，ACK是ECMP的，所以路径选择多，用Give-and-Take策略与交换机交换拥塞信息，交换机与本地信息比较来维护BestTable和GoodTable
存储的时候Acceptable Path也只存一条
ACK包进来，看携带的路径，如果是不可接受的，先用best path换掉，再和good table交换。如果是可接受的，不用best path替换，而是直接和good table的path交换。这样ack中信息的交换更频繁，并且用best path进行替换的过程也保证了不会传播垃圾信息。
找Acceptable Path
255减去CE(代表占用率)，乘上一个系数，大于这个值的认为可以接受
选路(ToR)
选路时，不能像HULA那样只考虑一个流最优，需要多条可接受路径。
信息的来源是ToR，集合了最好路径和可接受路径。
维护四张表：
- DRETable 同上
- BestTable 同上
- PathTable 为每个目的地存储
K个可接受路径 - FlowTable 根据flowId存下为每个流选了什么路
FlowTable的存储
- 五元组哈希：16位
- 选路还是ECMP：1位
- 路径选择：32位
ToR如何处理ACK
发送方：带上CE然后ECMP
接收方：看看BestTable要不要更新，如果Good Path可接受，就加到PathTable
发送数据
首先检查是不是老流。这里用了FlowId作为索引的位数组，对应1/0标识
由于PathTable基于目标路由存储，所以就算哈希冲突，不过是走了旧路，不会发错。
为了缓解哈希碰撞，位数组有老化机制
新流的话，选路结果会写入包头
路径选择原则：
- 不要重复
- 新路优先
选路时，每张PathTable（对应一个目标），用top和counter来实现循环存储。选路时会检查添加时间有没有比阈值旧，太老的话会ECMP
阅读参考
DCQCN（数据中心量化拥塞通知） 是运行在服务器网卡之间的端到端传输层拥塞控制算法，它通过ECN标记和CNP通知包让发送端“快降慢升”地调节速率，从源头消除拥塞。
PFC（优先级流量控制） 是运行在相邻交换机之间的逐跳链路层反压机制，它通过PAUSE帧直接暂停上游设备发送，用“急刹车”的方式防止缓冲区溢出丢包。
过往的负载均衡研究
CONGA(2014)
需要专用硬件
- 粒度：流
- 乱序：避让，在数据流的空闲间隙换路（不适用于RDMA）
方法：包头加路径和CE拥塞标签，Spine队列深度超过阈值，将CE更新,下游Leaf收到，用ACK向原发送端，原发送端存入表中记录该路径拥塞情况。原Leaf要记录通往一个目的地的多个路径的拥塞情况
HULA(2016)
每一跳记录通往目标的最佳下一跳
- 粒度: 流
- 乱序：避让，在数据流的空闲间隙换路（不适用于RDMA）
正向探测包发过去，每一跳检查本地队列深度，更新拥塞率，反向回来的时候更新路径上的每一跳
ConWeave(2023)
适用于RDMA
路径是由ECMP生成的，因为是二层Spine-Leaf，路径少。
注：CAVER设定考虑三层Fat-Tree
- 探测：定时从流中选取包打上
RTT_REQUEST，在超时时间里没有拿到RTT_REPLY将这条路放进黑名单。目标ToR收到ECN则通知上游，上游也将其设为不可用 - 选新路：在备选路径里选两条，只要有一条不在黑名单，就用它
- 防止乱序：要换新路的时候，旧路径最后一个包打上标签，新路径新包打上新标签，目的ToR收到旧流最后一个包之前先把新流的包存下，之后再恢复。