在数据中心网络中隔离大象流

1000 条短突发中混入几条大象流将严重影响短突发 p99 latency，造成抖动。这个我在隔离网络流以优化网络论证过了，还有另一种更直观的理解方式：

规模差异越大，算术均值越偏离中位数，即算术均值的分位数越高。

可以看出，无论洛伦兹曲线，基尼系数，或更普遍意义的 CDF 曲线，都能看出一个意思，扩大差异就拉高了均值和中位数之间的 gap，显得越发不公平。这里没有假设数据的任何分布特征，这是一般意义上的理解而不为建模，但它可以直击 p99，p90，p75 数据异常的本质。

早些年用指数分布建模的网络流量模型已不适用，现在微服务网络，AI 网络以及混杂着各种流量的云网络流量均展现出长程依赖，流量模型更符合帕累托分布，极少数大象流贡献了超过一半的流量以及绝大多数的时延抖动，因此，隔离大象流是高尚的。

还是那句话，按流的长度将不同流量装入不同的虚通道，以虚通道为粒度进行资源分配和资源隔离，就香了。

我曾建议应用程序自行用 getlength 获取数据长度，自行将流量按长度分类，但他们不肯。上层不配合提供有效信息，底层就要猜，这跟端到端拥塞控制的痛点一样痛，网络不提供有效信息，主机就要猜，所以知道 ecn 到底厉害在哪了吧。

既然猜就有误判，误判就有代价，成本是一定要支付的，所以要承认再好的启发式算法都有上限。
如果知道流量的统计分布就好办，但往往没有任何统计分布可以准确拟合数据，为了建模方便，我们假设流量的生存时间符合帕累托分布，问题显然就是给定一条流已经存活的时间 t，求它剩余寿命的期望。这是一道看起来不难，但算起来很麻烦的数学题。

帕累托分布的累积分布函数(CDF)为 $\alpha, \theta)=1 - \left(\frac{\theta}{x}\right)^{\alpha}$ ，如果一条流已经持续了时间 t（且 $\geq \theta$ ），我们想要知道在此之后的剩余寿命，我们可以考虑事件在 ( t ) 时刻还未结束的概率，这实际上是条件分布的概念。

首先，我们需要计算该流已至少持续到时间 t 的概率，即 P(X>t)。根据 CDF，它是 $\alpha, \theta) = \left(\frac{\theta}{t}\right)^{\alpha}$ ，接下来，为找到剩余寿命的条件分布，理论上需要对原始的帕累托分布进行适当缩放和规范化，使得它反映的是在 t 后的分布情况。在实践中需要依赖于数值模拟或高级统计方法来近似。

在上述理论下，如果我们已有流量长度的采样数据，就可得到一个更准确的分布(它不是建模用的帕累托分布)，我们可以看出样本长度都集中在哪些区间，比如 80% 的流都只有 200us，有 10% 的流持续 1ms，8% 的流持续 5～10ms，1.5% 的流持续 800ms～20s，0.5% 的流持续到分钟级。如果有个流已经存活了 300us，显然我们就可以非常斩钉截铁地将其踢出短突发类别，以此类推。

实现很简单，借用 linux kernel 的 nf_conntrack，记录 conntrack 创建时间 t_start，主机流量进入网络前，计算 len = t_curr - conn.t_start，如果 len 统计数据中短突发区间上四分位值(即 p75 长度)，就归入下一个类别，以此类推。

这种简单直接的做法非常有效，即使存在将流纳入大象流后它马上就结束了的可能，也不会有任何损失，首先，它已经离开了短流类别，无伤短流，其次它在该类别尚未有所作用力前就结束了，无伤自己和长流，如果它还将继续存活很久，那它将继续上升到更长的流类别中重复这样的事，在它所属某个类别的那段时间，它将和同属于该类别的其它流进入同一个虚通道。这保证了在某个特定的虚通道中，流量规模的差异很小，适合采用同一种调度策略。

如果不想借用 nf_conntrack，类似的实现逻辑也差不多，主要因为当前提到 nf_conntrack 这种老式机制太 low 了，还是要往 smartnic，ebpf，xdp，dpdk 上靠，但原理大差不差。比如实现下面的逻辑：

Mark(pkt): 
  key = hash(pkt)
  If flow[key].queue == null
    flow[key].queue = new_queue
    flow[key].queue.cnt = INIT_CNT
  flow[key].queue.cnt += pkt.pacing_gap
  flow[key].queue.len += pkt.pacing_gap
  pkt.type = flow[key].queue.len

Timer(10us):
  for each flow[i]:
      flow[i].queue.cnt -= DELTA_GAP
      if flow[i].queue.cnt == 0
          free flow[i].queue