1 Fat-Tree网络拓扑

Fat - Tree（胖树）是一种分层的网络拓扑结构，主要用于构建高性能的计算机网络，尤其是在数据中心网络（Data Center Network，DCN）和高性能计算（High - Performance Computing，HPC）环境中有广泛应用。

DC的网络实现有两种方式：

  • 专有硬件和协议：Infiniband
  • 利用通用以太网交换机和路由器连接集群机器

现在的方案一般是使用基于以太网的RDMA，结合两种方法。

DC的网络拓扑或者说架构期望的属性是：

  • 可扩展互联带宽
  • 成本较低，可大规模建设部署
  • 与运行以太网的主机后向兼容

早期的网络拓扑存在OverSubscription，在成本和可扩展性上都存在问题。而Fat-Tree是满足上述条件的网络拓扑，因此在提出后逐渐广泛应用于数据中心和高性能计算集群。其拓扑结构如下：

image-20250512170117719

Fat-tree拓扑有k个pods，每个pod有两层的k/2个交换机。每个k端口交换机在底层直接连接到k/2个主机，剩余的k/2个端口连接到核心层。核心层的每个交换机都连接到k个pod，共(k/2)^2个，提供任意两个主机之间(k/2)^2条最短路径。Fat-tree专注于设计k=48的整体架构，整个网络有27648个主机（每个底层交换机连接24个主机，底层24个交换机，共48个pods，27648=24*24*48），每个子网有24个主机。Fat-Tree提供了多路径路由、高带宽和良好的可扩展性。

地址格式

  • 网络中的所有IP地址都位于私有的10.0.0.0/8地址块内。采用层次化的地址分配策略。

  • Pod交换机的地址格式为10.pod.switch.1，地址分配基于Pod和交换机的位置，确保地址的唯一性和可管理性。

    • pod表示pod编号（范围在[0, k-1]），
    • switch表示该交换机在pod中的位置（范围在[0, k-1]），从左到右、从下到上编号。

  • 核心交换机的地址格式为10.k.j.i，其中：

    • j和i表示该交换机在(k/2)^2核心交换机网格中的坐标（每个坐标范围在[1, (k/2)]），从上到下（优先）从左到右开始编号（1.1 2.1 1.2….）。

两级路由表

Fat-tree采用两级的路由表，第一级是左前缀查询，如果表中直接给出端口则为终止前缀，否则查询第二级路由表，二级路由表是右后缀查询。任何Pod交换机的路由表将包含不超过 k/2 个前缀和 k/2 个后缀。通过将路由表分为两级，可以减少路由表的大小，从而提高查找效率。

image-20250512180647776

路由算法

对于pod内部通信，只需要查询一个指向目标子网的终止前缀完成转发。对于跨pod的通信，指向一个匹配主机ID的次级路由表，使用主机ID作为确定性熵的来源，使流量均匀分布在通往核心交换机的链路。核心交换机只需要（10.pod.0.0/16, port）的前缀就可以转发到目标pod。一旦数据包到达目标Pod，接收的上层Pod交换机还会包含一个(10.pod.switch.0/24, port)前缀，以将数据包引导至目标子网交换机，最终转发到目标主机。

生成聚合层交换机路由表的算法如下，对于下层交换机，z的范围是0-(k/2-1)，并省略3-5行。

image-20250512182218955

生成核心交换机路由表的算法如下。到k/2-1是因为整个拓扑是对称的。

image-20250512182252666

路由算法Example

假设源IP为10.0.1.2，目标IP为10.2.0.3，首先数据包到达底层交换机，根据pod号可以确认路由是跨pod的，因此会走二级路由表。对于二级路由表，目标主机的host ID是3，所在底层交换机编号为1，所以i=3，z=1，可得端口为2。会路由到上层的10.0.2.1交换机。（端口号似乎也是从左到右，从下到上映射）

image-20250512193432694

image-20250512193626864

到达上层交换机后，仍然使用二级路由，还是上面的6 7 8行算法，会得到转发端口为3，转发到10.4.1.2。

image-20250512194229990

核心交换机10.4.1.2会根据目标pod 2将其转发到端口2，发送到交换机10.2.2.1。此时交换机进行路由已经是在pod内路由了，目标子网i为0，所以直接查到终止前缀，发送给10.2.0.1。

image-20250512194815211

下层交换机10.2.0.1直接将其交给目标主机10.2.0.3。

image-20250512194934625

2 协议

2.1 MPTCP(Multipath TCP)

多路径传输控制协议是TCP的一种扩展协议，利用多个网络路径来提高传输的可靠性和效率。其设计目标为：

  • 能够为单一连接使用多个网络路径。
  • 能够至少像常规 TCP 一样使用可用的网络路径，但不会饿死 TCP。
  • 对现有应用程序来说，使用起来和常规 TCP 一样（无需更改终端主机）。

MPTCP的协议层级为套接字接口和TCP子流之间：

image-20250514171335922

在TCP的三次握手中加入MP_CAPABLE key来使用，每次的三次握手会建立一个子流。MPTCP 需要能够将每个子流链接到现有的 MPTCP 连接。为此，MPTCP 为每个连接分配一个本地唯一的令牌。SYN 段中的 MP_JOIN 选项包含关联 MPTCP 连接的令牌。

image-20250514171442925

常规TCP的拥塞控制算法：

  • 每个 ACK，将拥塞窗口 w 增加 1/w，这导致每个 RTT 增加一个数据包。
  • 每次丢包，将 w 减少 w/2。

w 可以被视为“飞行中的数据包”（已发送但尚未确认的数据包）。在一个 RTT 内，如果发送并确认了 w 个数据包，窗口大小增加 w×1/w=1（单位为最大报文段MSS），即每个 RTT 增加一个数据包。这被称为加性增/乘性减(AIMD)。

如果直接使用原始的TCP算法，MPTCP的流会因为有多个子流而获得更多的带宽，损害网络的公平性，所以MPTCP有自己的拥塞控制算法，每个子流r∈R维护自己的拥塞窗口wr。一个简单的维护公平的算法是EWTCP(Equally-Weighted TCP)拥塞控制算法：

image-20250514173753615

每个子流获取的窗口值会正比于a^2，因此当a为1，拥塞控制和原本的TCP一样，$a=\frac1{\sqrt{n}}$，共有n条流，则每个子流最多获取1/n，整个TCP的所有流就不会超过单路TCP的带宽，实现了公平性。EWTCP的子流是独立的，即使有一条subflow被阻塞了，其他的subflow也不会因此变得更加有侵略性，但是这导致EWTCP不能高效地使用链路(缺乏动态适应性例如下图的例子。

image-20250514174149142

有一种理论更有效的算法Coupled算法：

image-20250514174351688

Wtotal是一个MPTCP实体下管辖的所有subflow的发送窗口大小之和。通过求解以下方程计算：

image-20250514174637015

会解出：

image-20250514174711028

p是path r上的丢包率。在COUPLED算法中，一个MPTCP的各个subflow可以获得的总带宽之和只与链路丢包率有关，这证明了COUPLED拥有天然的带宽竞争公平性。有更高丢包率的特定path的子流会减少，窗口会最终减到0。算法总是会选择最不拥塞的路径来发送。流只会选择有最低丢包率的路径发送，只有有一些路径有相同丢包率的时候才会多路径发送，并且上述的Wtotal。

示例的解释（ref：https://blog.csdn.net/zzy980511/article/details/125187873）：

image-20250514180957343

image-20250514180939104

右边三个流最后的连接都会达到均衡，所以ABC都为(5+12+10+3)/3=10。这个图可以理解为EWTCP保证的是每个链路上面各个TCP流拿的流量是公平的，而Coupled经过动态均衡，每个TCP流在整体带宽上是公平的。

2.2 BBR: Congestion-Based Congestion Control

BBR 协议的全称时Bottleneck Bandwidth and Round-trip propagation time，是由Google开发的TCP拥塞算法，通过测量网络的瓶颈带宽和往返传播时间RTT，动态调整发送速率利用网络资源。在Youtube上使用，可用于linux和quic。

TCP的拥塞控制使用增性加乘性减，大致上发送方发送cwnd字节，等待一个RTT以接收ACK，然后发送更多的字节。发送速率的计算公式为：rate ≈ cwnd / RTT，即发送速率大约等于拥塞窗口大小除以往返时间。

image-20250517203813150

BBR的提出动机主要有以下几点：

  • 基础设施支持多Gbps的速度，但洲际距离上往往只能提供几Mbps的速率。
  • 用户可能会经历从几秒到几分钟的延迟。
  • 基于丢包的TCP拥塞控制，NICs的内存逐渐扩大，网络中的丢包往往是由于缓冲区溢出而不是拥塞。
  • 对于基于丢包的拥塞控制，例如NewReno，CUBIC，存在大的往返时间（RTT，即数据发送和确认之间的时间差）和路径上满的缓冲区。也存在大量的数据传输中（data-in-flight），称为缓冲区膨胀（bufferbloat）。导致低吞吐量，频繁的丢包、重传和拥塞窗口（cwnd）减少。

TCP连接的最慢链路为瓶颈，是队列累积的位置，决定了最大数据传输速率。有两个物理约束：

  • RTprop（往返传播时间）：没有缓冲的往返时间（RTT）。
  • BtlBw（瓶颈带宽）：瓶颈链路的带宽。

延迟带宽积：

  • BDP = RTprop × BtlBw。
  • BDP表示在没有丢包的情况下，可以在网络上传输的最大数据量。

三个区域：

  • 应用受限（App limited）：应用层没有足够的数据来填满管道，由RTprop主导。
  • 带宽受限（Bandwidth limited）：传输速率受限于瓶颈带宽，由BtlBw主导。
  • 缓冲区受限（Buffer limited）：瓶颈缓冲区限制了传输中的数据量。

图表展示了传输速率和往返时间与流量的关系：

  • 横轴：流量（amount in-flight）。
  • 纵轴：往返时间（round-trip time）和传输速率（delivery rate）。
  • BDP：带宽-延迟积，表示在没有丢包的情况下，可以在网络上传输的最大数据量。

image-20250517205332263

基于丢包的拥塞控制：

  • 在带宽受限区域的右侧边缘操作。
  • 以高延迟和频繁丢包为代价。

最佳操作点：

  • 带宽受限区域的左边缘是最佳操作点。

瓶颈的特征

TCP有最高吞吐和最低延迟有两个条件：瓶颈处的到达速率等于带宽BtlBw，速率平衡条件，带宽被100%利用。传输的数据总量等于时延带宽积，瓶颈处没有形成队列，满pipe条件。RTprop是在窗口W上的运行最小值。

image-20250517211106949

估计带宽：

image-20250517211200116

不确定性原则：当一个可以被测量时，另一个可能无法测量。

  • 测量BtlBw时取最大值。
  • 测量RTprop时取最小值。

==BBR算法核心==

当接收到ACK时，发送方更新RTprop和BtlBw过滤器。计算RTT,使用update_min_filter(RTpropFilter, rtt)更新RTprop过滤器的最小值。更新delivered变量，增加已成功传输的数据量。计算传输速率：deliveryRate = (delivered - packet.delivered) / (now - packet.delivered_time)。如果deliveryRate大于BtlBw过滤器的当前最大值，或者数据包被标记为应用受限，则更新BtlBw过滤器。（BtlBwFilter维持周期时间的最大发送速率）

image-20250518102614223

发送时计算时延带宽积，如果传输数据大于当前bdp，等待超时或ACK。如果当前时间大于等于下一个发送时间，发送下一个数据包，没有数据包可发送，将app_limited_until设置为传输中的数据量。更新数据包的发送时间，已传输的数据量和时间，并计算下一个发送时间。

image-20250518102811234

两个控制参数：

  • cwnd_gain：限制传输中的数据量
  • pacing_gain：决定发送方可以多快发送数据

BBR算法能够自动适应网络条件的变化，如瓶颈带宽的减少或往返传播延迟的增加。当瓶颈带宽减少时，BtlBw过滤器在经过一段时间的窗口后检测到这一变化，导致带宽-延迟积（BDP）降低。当往返传播延迟增加时，RTprop过滤器在经过一段时间的窗口后检测到这一变化，导致BDP增加。

ProbBW

BBR使用一个八阶段周期，每个阶段持续一个RTprop（往返传播时间），pacing_gain依次为5/4, 3/4, 1, 1, 1, 1, 1, 1。首先使用高于1的pacing_gain来探测更多的带宽。如果瓶颈带宽增加，传输速率增加，并且测量到更大的BtlBw样本，BtlBw将被更新。如果瓶颈带宽没有增加，说明瓶颈处形成了队列。使用低于1的pacing_gain来排空队列。cwnd_gain始终保持在2。

image-20250518110646981

image-20250518110802595

ProbeRTT

如果RTprop估计值在几秒钟内没有得到更低的测量值，BBR进入ProbeRTT状态，将cwnd减小到一个非常小的值。在至少200ms后，如果没有观察到更小的RTT，保持当前状态；否则，进入ProbeBW状态。BBR大部分时间（98%）处于ProbeBW状态。

Startup

快速填满网络管道，即尽快增加发送速率以利用可用带宽。将pacing_gain（控制发送速率的增益）和cwnd_gain（控制拥塞窗口的增益）设置为 2/ln2，每轮发送速率翻倍。如果传输速率的实际增加小于25%，则估计已经达到瓶颈带宽（BtlBw），并进入Drain状态。

Drain

将pacing_gain设置为 ln2/2。当传输中的数据包数量（即未被确认的数据包）达到估计的带宽-延迟积（BDP）时，进入ProbeBW状态。

image-20250518111237665

BBR VS CUBIC

image-20250518111520606

总结

BBR主要是为了在达到峰值带宽时就进行拥塞控制，避免队列形成和缓冲区溢出导致丢包的发生。于TCP相比，BBR会通过ACK和记录的发送时间记录当前测量到的瓶颈最大带宽和最小RTT，来计算出一个时延带宽积，传输中的数据量不会超过时延带宽积，从而避免拥塞。在发送的初始阶段，会使用更大的窗口和发送速率来探测峰值瓶颈带宽，达到瓶颈带宽后，排空已经形成的队列，然后维持发送速率。BBR的优势是可以根据瓶颈带宽的动态变化来进行拥塞控制，并且能够避免基于丢包的拥塞控制协议太晚干预拥塞的情况。

3 调度

3.1 PIFO

数据包调度的基本方式是FIFO，易于硬件实现并能维持线性速率。但入队时间决定出队时间，发送更多数据包的终端可占用更多带宽，无法控制带宽分配，也没有优先级，尾部数据包会被丢弃。数据包调度算法已经有非常多了，例如加权平均队列，令牌桶过滤等，这些算法需要硬编码到交换机硬件。需要能够表达广泛的数据包调度算法，以适应不同的网络需求和条件。

一个基本的数据包调度模型只需要两个组件。

  • 推入先出（PIFO）队列（The push-in first-out (PIFO) queue）：
    • 这是一个优先级队列，允许元素根据其优先级（rank）被插入到任意位置。
    • 元素从队列头部出队（dequeue），即遵循“推入先出”的原则。
    • rank较低的元素会先出队，这意味着它们会被优先处理。
  • 数据包事务：在数据包被推入PIFO队列之前，需要计算其rank。例如—Weighted Fair Queueing (WFQ)，—n flows, flow fi has a weight wi, and is assigned with a bandwidth of B× wi /Σwj。

image-20250519163834551

WFQ是一个理想中的能够保证优先级的调度。实际情况中一般实现的是近似的调度，例如—Start-time Fair Queueing (STFQ)。

image-20250519165143889

image-20250519165422387

一些算法需要改变缓冲数据包的相对顺序。例如—Hierarchical Packet Fair Queueing (HPFQ)。HPFQ首先将链路容量划分为不同的类别，然后在每个类别内递归地将子类别进一步划分，直到到达叶节点。HPFQ不能使用单一的调度事务和PIFO（Push-In First-Out，推入先出）实现，因为已经缓冲的数据包的相对调度顺序可能会随着未来数据包的到来而改变（STFQ实际上后入的数据包不会影响之前数据包的相对顺序）。

image-20250519165800030

image-20250519165953081

HPFQ在树的每一层实现了WFQ，由此构造了一颗调度树。

image-20250519170211754

树会按照当层的队列去走左或右子树，然后递归直到数据包。例如下图的队列：

image-20250519171204698

image-20250519171639581

硬件设计：

每个PIFO（Push-In First-Out）块支持64K个数据包和1024个流量。支持最多5层的层次结构。

图表展示了网络数据包在硬件中的处理流程，包括以下几个主要阶段：64个输入端口接收数据包。解析器负责解析输入的数据包，提取出以太网（Eth）、虚拟局域网（VLAN）和传输控制协议（TCP）等信息。数据包经过入口流水线的多个阶段（Stage 1和Stage 2）进行处理。每个阶段包含匹配/动作（match/action）单元，用于执行特定的操作。调度器负责根据预定义的调度策略（如WFQ、HPFQ等）对数据包进行排序和调度。数据包经过出口流水线的多个阶段（Stage 1和Stage 32）进行处理。解封装器负责将处理后的数据包重新封装，准备发送到输出端口。64个输出端口发送处理后的数据包。

image-20250519171803814

3.2 SP-PIFO

PIFO编程模型要求可编程的PIFO队列，难以在硬件中实现。如果实现严格的优先队列，一个端口有多个 FIFO 队列，每个队列都与一个优先级相关联，仅当所有具有更高优先级的队列为空时，队列才会开始传输数据包，否则，它将被暂停。

SP-PIFO希望通过动态调整数据包rank和严格优先级队列之间的映射来近似实现PIFO队列行为的方法。图中例子展示了两种不同映射下数据包调度的不同结果。共有两个队列。

image-20250521100342047

基于梯度的算法的目标是通过动态调整队列界限来最小化调度错误。具体来说，它通过计算不同队列界限的成本，并选择成本最低的队列界限来实现这一目标。成本的计算基于样本集 D 中数据包等级的概率分布，以及逆序的成本。但是这要求梯度分布是稳定的，这不合理，并且在交换机上实现复杂。

所以SP-PIFO用了一种近似算法，近似算法要解决的是：

image-20250521101233824

所以SP-PIFO的算法中，算法首先接收一个带有等级 r(p) 的数据包 p。映射过程从队列的底部开始向上扫描（bottom-up），寻找第一个满足 $r(p)≥q_i$ 的队列。这意味着数据包 p 被放入第一个其等级不小于 r(p) 的队列中。一旦找到合适的队列，算法将该队列的界限 qi 更新为数据包 p 的等级。这个过程为PUSH UP。当检测到逆序（即一个高等级的数据包在低等级的数据包之前被调度）时，算法会将所有队列的界限降低 q1−r(p)。这里的 q1 是最低rank的队列界限，r(p) 是引发逆序的数据包的等级，这个过程为PUSH DOWN，这个减操作相当于保证数据包能够进入最低rank的队列。

image-20250521101319882

Example：前6个包都是PUSH UP，最后一个是PUSH DOWN。

image-20250521102949781

3.3 PCQ

Programmable Calendar Queues for High-speed Packet Scheduling NSDI2020

背景是FIFO不支持优先级，PIFO在硬件上难实现，因为排序和比较代价高昂而数据包处理很快。使用多级优先队列则优先级远大于队列数，而且优先级会根据时间变化。

上文图中的调度器在这里被称为流量管理器，可以缓冲数据包以及对队列进行调度，每个队列可以被暂停和取消暂停。

image-20250526194750387

PCQ有N个FIFO队列，每个存储接下来N个周期的调度的数据包。PCQ包含三种操作：

  • CQ.enqueue(n)：入口流水线用来将当前数据包安排在未来的n个周期内
  • CQ.dequeue()：出口流水线使用，获取当前周期的缓冲数据包
  • CQ.rotrate()：流水线使用，推进CQ使其能够为一下一个周期传输数据包

两种不同逻辑的日历队列：

  • 物理日历队列：固定时间间隔后移动到下一个队列
  • 逻辑日历队列：当前队列为空时移动到下一个队列

image-20250526212322054

USE CASES：WeightedFairQueueing（逻辑日历队列）

image-20250526213027026

假设以下情况，每个流的数据包大小都为1：

image-20250526213430910

还可以实现其他调度算法，只要调整相应的入队策略。

PCQ机制中，队列的优先级通常基于它们对应的时间周期，对应于当前周期的队列具有最高的优先级，头队列始终处于活动状态，因为它需要随时准备处理数据包。对应于更远未来的周期的队列具有最低的优先级，并且通常处于暂停状态。这些队列只有在它们对应的周期到来时才会被激活。PCQ通过两种策略来执行旋转，从而实现优先级动态调整。对于WFQ而言，只是平等的将各个流的数据包规划到未来的周期发送。

与SP-PIFO相比，二者使用了少量的队列来实现大量的rank，但SP-PIFO是动态的调整队列的边界rank映射，而PCQ是通过旋转的方式，每个周期的头队列由最高优先级，而其他队列处于暂停状态。

3.4 AIFO

Admission-In First-Out（AIFO）队列是一种只使用一个单一先进先出队列的可编程数据包调度方案。在硬件实现上更简单，并可以利用现有的交换机。现有的交换机不支持数据层对队列排序，SP-PIFO，PCQ等方案使用严格优先级的FIFO队列，但通用交换机只有优有限数量的优先级队列，队列是稀缺的。

AIFO使用一种权限控制，直接丢弃不符合rank范围的数据包：

image-20250529101500890

AIFO的目标是尽可能的近似PIFO，并减少出队顺序的差异，不过出队顺序并没有那么重要，因为交换机缓冲区较浅，数据包之间的距离有限，差异不会太明显。AIFO的准入控制根据阈值确定丢弃数据包还是传输数据包。AIFO有两个组件：

  • 时间组件：根据到达率和发送率之间的差异更新阈值，确保接纳的数据包速率大致与离开速率相匹配
  • 空间组件：优先丢弃高rank的数据包

数据包在入流水线决定是否丢弃或者入队。而阈值是由队列长度(c)和队列大小(C)，并且使用数据包在队列中的分位点来当前数据包的相对rank。

image-20250529102745097

k用于调整队列准入策略，并使用k预留一些空间，来容忍短暂的流量突发。k越小越像PIFO，越大越像FIFO。Example：

image-20250529103120154

对于时间组件，队列长度信息是由流量管理器处理的，只有当数据包通过时得到。每一个出流水线的端口通过寄存器数组存储队列长度。并在入口流水线有副本。

image-20250529103435113

空间组件使用的是四阶段滑动窗口来进行分位数估计。每个阶段使用4个寄存器维护16个数据包等级的滑动窗口，使用索引标记模块跟踪数据包。对于下图，rank5的数据包占据了原来rank9的寄存器位置，并且有6个寄存器rank<5，所以分位点是6/16。

image-20250529104717241

实验证明在已接收的数据包中AIFO比SP-PIFO更接近PIFO。

3.5 Cebinae

Cebinae旨在增强现有网络的公平性，特别是针对那些使用遗留（传统）主机拥塞控制算法（CCAs）的网络。

TCP有很多变体，例如基于丢包的Cubic，NewReno等，基于延迟的Vegas等，混合的BBR等，但TCP永远无法实现公平，因为即使采用相同的拥塞控制，不同的RTT也会导致不公平的分配，并且依赖不同的拥塞控制算法变体和OS实现。

两个keyInsight是：

  • 在每个节点对数据包或字节级别的调度对于全局收敛是不必要的，并不是实现网络公平性所必须的
  • 对于网络来说，将带宽从已经达到或超过其公平份额的流量重分配给未达到份额的流量就足够了。这表明网络不需要对每个数据包进行精细控制，而是可以通过调整流量的带宽分配来实现公平性。

该图主要体现在不同RTT下，Cebinae能实现更稳定的吞吐量。

image-20250529112927647

Cebinae中希望达到的调度目标是：

  • Pareto-efficiency：给定一组流量速率的分配 {r1,…,r**N}，当且仅当增加任何一个速率 r**i 需要减少另一个流量的速率 r**j 时，这个分配是帕累托有效的。这种状态下，任何改变都不可能使任何一方变得更好而不使另一方变得更差。
  • 在达到帕累托效率的同时，增加任何一个流量的速率需要减少一个更小流量的速率。最大最小公平性是一种特殊的帕累托有效分配，它确保在提高任何一个流量的速率时，必须以牺牲一个已经较小的流量为代价，这样可以避免资源的不公平集中。

image-20250529114319954

即有一个流如果流量提升，一定有另一个流量更小的流流量下降。

Water-filling

Max-min公平性是由迭代的water-filling算法实现的。该算法把所有流量初始状态设定为无约束，速率为0。在每次迭代中，为所有无约束的流量增加相同的速率，模拟“水”被均匀地倒入各个容器，直到某个链路（容器）达到饱和。当某个链路饱和时，所有经过该链路的流量变为“受约束”，不再参与后续的速率分配。算法继续为剩余的无约束流量分配速率，直到所有流量都变为受约束，此时达到最大最小公平性。

image-20250529115757060

image-20250529120048666

对于每个流量 ri，存在至少一个瓶颈链路 l，该链路的容量限制了流量 ri 的速率。当链路 l 饱和时，其容量被完全利用，任何进一步的速率增加都会导致拥塞。在瓶颈链路 l 上，流量 ri 的速率不低于该链路上的其他流量。这意味着 ri 在该链路上具有优先级，确保了公平性。

上述内容提供了验证最大最小公平性的方法，如果链路未饱和，则它对于当前使用该链路的任何流量都不是瓶颈。这意味着该链路的容量未被充分利用，因此不会限制任何流量的速率。如果链路饱和，则对于该链路上的每个流量 i：如果流量 i 在本地竞争流中具有最大的速率，则该链路是 i 的瓶颈。在这种情况下，i 只能以牺牲其他流量为代价来捕获更多的带宽。如果多个流量的速率相同，则它们可以共享同一个瓶颈链路。如果流量 i 在该链路上的速率不是最大的，则该链路不是 i 的瓶颈。在这种情况下，流量 i 可能有也可能没有网络中其他地方的瓶颈链路。

Strawman Solution

Cebinae采用了一个稻草人方案，每个路由器检测本地链路是否已经饱和。对于每个饱和的链路，识别出那些占用最多带宽的流量。对识别出的大流量施加一个令牌桶（token-bucket）速率限制，以控制它们的发送速率。当网络中的总需求下降到低于链路容量时，之前施加的限制会被解除，允许流量恢复正常速率。通过这种机制，稻草人方案可以在不改变网络硬件的情况下，通过软件方式实现对流量的公平控制，防止某些流量占用过多带宽，从而保证所有流量都能获得合理的服务。

这个方案有两个限制：

  • 不能修改已经不公平的分配

例如对于一个收敛的分配—{1,1,6,1,1}，流C已经到达了其公平份额。其他流没办法提升他们自己的份额。

image-20250529153249351

  • 如果流量C的拥塞控制基于延迟，那么即使对流量C施加了令牌桶速率限制，它也不会对简单的令牌桶过滤器做出响应。此类算法不依赖数据包丢失来判断拥塞，因此即使令牌桶过滤器丢弃数据包，只要延迟未显著增加，流量C仍会继续以当前速率发送数据，认为网络未出现拥塞。

为了保证公平，Cebinae会尝试重分配一小部分流的带宽，通过对最大流收税（税率𝜏），确保其他流量也有机会获得足够的带宽。Cebinae还有延迟和ECN，允许在网络拥塞之前检测并响应。

image-20250529153701355

重分配的一个例子如下，A占了18，对A的税率是0.01，则A让出的带宽是0.18，对于剩下的B和C，B的流量占比和C的占比是10/11和1/11，将让出的带宽按比例分配给这两个流，最终B和会共占10的速率，因为I2已经无法增长了，A也无法通过税率转移流量给B和C，此时I3是A的瓶颈，而B和C都在I2上共同占满了速率，B会开始支付税率速率让出带宽给C，直到C在链路I5达到瓶颈，而B的瓶颈会为I2。

image-20250529154959070

与每数据包公平队列调度的比较

  • 不保证任意时刻的完全公平，需要时间收敛
  • 在有限时间收敛
  • 网络级别的公平
  • 有更好的可扩展性，不需要保持per-flow的状态，只需要限制瓶颈流的速率