当 BBR 面对时延抖动

这篇具有很好参考价值的文章主要介绍了当 BBR 面对时延抖动。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

写在前面:

涉及启发式的策略一般倾向于设置 alpha,beta 参数,比如 Vegas:

cwnd / basertt - cwnd / rtt < alpha; cwnd ++
cwnd / basertt - cwnd / rtt > beta; cwnd –

难点在于调参,每个环境都要调一组参数,费时良久。

就着一个实际的 RTT 抖动场景,一个新想法是按比例分配平滑 RTT 和瞬时 RTT 对当下的作用,这个比例是抖动相关的函数,提高抗抖能力,更丝滑。

更进一步,我希望有能力从历史散点数据中获得更多信息,更精细指导当前决策,但这就不是一个公式能覆盖的了,需要 AI 来搞,但这是后面的事。

正文:

以下是我的手机上 ping Wi-Fi 网关的结果:
当 BBR 面对时延抖动
​问题:我应该把这里面最小的 5.18 ms 喂给 BBR 吗?如果不妥,怎么办?

Wi-Fi 场景,由于 CSMA/CA,成功传输报文的时间是个统计分布,比如连续采样 5 次,结果可能是 3ms,10ms,1ms,5ms,18ms。此样本中的 1ms 并不意味着 buffer 被排空,可能只是运气好,同样,18ms 也并不意味着拥塞,可能只是碰撞多,运气差。运气再差点,达到退避次数极限仍不成功,就丢包了,即便如此,也可能没有任何拥塞。

Wi-Fi 场景不使用连续 buffer 排队假设,需要一个 RTT 的平滑度来平滑统计值。

不光 Wi-Fi,在有线网络,如果短 burst 居多,也会造成时延抖动。在时延抖动场景,小 RTT 可能只是偶然,完全不能匹配拥塞控制的假设,这也是 BBR 望时延抖动的弱网而兴叹的原因。

对 BBR,抖动比丢包更可怕,它直接掀翻了 BBR 的 maxbw,minrtt 测量设施,而 BBR 却完全依赖这个设施。

遗憾的是,绝大多数人无脑接受拥塞控制算法作者的假设,企图基于连续长流模型对算法做优化,他们甚至不知道连续长流意味着什么,更别提短 burst 了。即便 BBR 的作者也通篇不谈 burst,抖动。涉及 burst,抖动的算法遍布各大会议论文,却都不实用。

绝大多数人意识到了 burst,抖动,却很少有人测量,量化它们去发掘一些统计信息。更甚者,面对几个来回结束的 KB 级短流,缺失了长流式反馈,似乎只能是听天由命。

我提议将短 burst 快照保存,下一次 burst 时用做历史参考,试图找到规律。反驳我的理由 “上次 burst 的快照已经过去了” 非常讽刺,回应者意识不到在长流中自己完全依赖的上一个 RTT 的快照同样也是历史。

用下面的命令可以很容易模拟时延抖动:

# 为 netem delay 配置 JITTER 参数。(同时后面还可以加入 distribution,显得更真实) 
tc qdisc add dev eth0 root netem delay 1ms 4ms

结果如下:
当 BBR 面对时延抖动

没有任何排队,但却产生了大时延,这不是 BBR 意义上的合格样本,所以下面的代码在这种场景下是错的:

// net/ipv4/tcp_bbr.c: bbr_update_min_rtt  
static void bbr_update_min_rtt(struct sock *sk, const struct rate_sample *rs) 
{      
    ...     
    /* Track min RTT seen in the min_rtt_win_sec filter window: */
    filter_expired = after(tcp_jiffies32,
                           bbr->min_rtt_stamp + bbr_min_rtt_win_sec * HZ);
    if (rs->rtt_us >= 0 &&
        (rs->rtt_us <= bbr->min_rtt_us ||
        (filter_expired && !rs->is_ack_delayed))) {
        bbr->min_rtt_us = rs->rtt_us;
        bbr->min_rtt_stamp = tcp_jiffies32;
    }

偶然的小 RTT 喂给 BBR,将影响 BDP 正确性,进而影响 cwnd,inflight,bw 计算,干扰 ProbeUP 过程的判断。但又不能莽然改用 SRTT,这会影响 BBR 反应灵敏度。

难点在于特定时刻 SRTT(移指平均 RTT) 占比到什么程度,IRTT(即时 RTT) 占比到什么程度。这是个连续的模型,不是二选一的问题,显然不能用静态系数去加权,但下面的想法肯定沾边:抖动越大,越趋向于使用 SRTT,抖动越小,越趋向于使用 IRTT,尽量屏蔽掉抖动。

恰好 Linux TCP 有一个 RTTVAR(现实中使用 mdev_us 字段) 可用来度量抖动程度,目前除了计算 RTO 它没有别的大用,用 RTTVAR 描述上述想法, 用公式表达如下:

RTT_for_BBR = (1 - beta / RTTVAR) * SRTT + (beta / RTTVAR) * IRTT

将喂给 BBR 的 RTT 分为两部分,抖动随着 RTTVAR 增加,IRTT 占比越低。

最简单的示例代码:

// net/ipv4/tcp_bbr.c: bbr_update_min_rtt  
filter_expired = after(tcp_jiffies32,
                       bbr->min_rtt_stamp + bbr->params.min_rtt_win_sec * HZ);
V = ((u64)tp->mdev_us - 30)*(tp->srtt_us>>3) + 30*rs->rtt_us; // beta = 30 
V = div64_long(V, tp->mdev_us); 
max = max(rs->rtt_us, tp->srtt_us>>3); 
min = min(rs->rtt_us, tp->srtt_us>>3); 
V = max(min(max, V), min);  
printk("irtt:%llu srtt:%llu var:%llu ret:%llu\n", rs->rtt_us, tp->srtt_us>>3, tp->mdev_us, tmp); 
if (rs->rtt_us >= 0 &&     
    //(rs->rtt_us < bbr->min_rtt_us ||
    (V < bbr->min_rtt_us ||
    (filter_expired && !rs->is_ack_delayed))) {
    //bbr->min_rtt_us = rs->rtt_us;         
    bbr->min_rtt_us = V;         
    bbr->min_rtt_stamp = tcp_jiffies32; 
}

同时,对 bbr_update_bw 也要做类似平滑修正:

// net/ipv4/tcp_bbr.c: bbr_update_bw 
tmp = ((u64)tp->mdev_us - 50)*(tp->srtt_us>>3) + 50*rs->interval_us; 
//bw = div64_long((u64)rs->delivered * BW_UNIT, rs->interval_us); 
bw = div64_long((u64)rs->delivered * BW_UNIT, tmp);

但这只是表达一下意思,RTT_for_BBR 缺陷很多,远非完美。

tp->mdev_us 的不规则性可能消耗除法成本且视觉上不好看,mdev_us 度量抖动程度,而非度量精度。确定一个静态数组 {2, 4, 8, 16, 32, … 2^16},只要找到 mdev_us 距哪个最近,求出索引 index 就能用 >> index 替换除法:

int a[] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768};

int main(int argc, char **argv)
{
	int b = atoi(argv[1]);
	int i, dlt, predlt;

	for (i = 0; i < sizeof(a); i ++) {
		dlt = b - a[i];
		if (dlt < 0) {
			if (a[i] - b > predlt)
				return i;
			else return i + 1;
		}
		predlt = dlt;
	}
}

上述 “预测算法” 精度有限,精度有限是固有的,甚至已触及上限,换句话说,即使你找到更好的 RTT_for_BBR 表达式,预测效果也不会好太多。因为一个连接内的信息太有限。正如一个只学懂了 50% 的学生参加考试,他的分数不会超过 70,但也不会低于 20,毕竟如果知道什么是错的,自然就知道什么是对的,信息量决定了上限和下限之间的区间。如果掌握了所有信息,那就有能力得到从 0 到 100 内的任意分数,区间长度为 0,所以不要觉得考 0 分比考 100 更容易。

用以上的引论来比较 CSMA 网络与交换网络,为什么交换网络的某一时刻排队时间是确定的,而 CSMA 却是统计分布。因为交换机拥有数据包到达的所有信息,它可以根据当前 buffer 排队情况为冲突的每一个数据包安排一个确定的位置,这就是连续 buffer 排队的假设,而 CSMA 网络没有交换机,每一个节点都是一个排队系统,每一个节点对数据包到达的信息一无所知。换句话说,交换机根据当前 buffer 用量有能力考从 0 分到 100 分的任意确定分数,CSMA 网络则可能考 0 分到 100 分之间任意不确定分数。

试图优化传输质量,但掌握的信息有限(或许说到底还是 TCP 那么一点信息),对于 30% 的连接,可能效果非常棒,可另外 30% 的连接反而会劣化,综合来看就是没效果。难点不是给定场景如何优化,而是把场景识别出来。我上面的 “算法” 有点这个识别场景的意思,但注定达不到什么高度。

我倾向于盘查历史数据,挖掘其中的模式,但没有共鸣,反对者觉得这不是真技术。当我问到 “那为什么每个人都知道流量晚高峰的时间段?”,对方回答这个信息与传输优化无关。

人们倾向于预测未来,却鄙视历史,现实也被这理念粉饰。包括 CUBIC/BBR 在内,明明在使用过去一个 RTT 的历史快照,偏偏骗自己这个快照描述了当前,进而相信它可以延续到未来。

预测抖动等效于预测 burst,这是排队论的结论,后者并非完全不可预测,但完全不可测准。正视这问题不可解,就很容易推进优化方法,否则只会在寻找根本不存在的算法而 spin 的过程中错过一切 “不是真技术” 的真技术。

Homa 在 RPC 场景应对 icast 的方法值得一提:

Homa solves the incast problem by taking advantage of the fact that incast is usually self-inflicted: it occurs when a node issues many concurrent RPCs to other nodes, all of which return their results at the same time. Homa detects impending incasts by counting each node’s outstanding RPCs. Once this number exceeds a threshold, new RPCs are marked with a special flag that causes the server to use a lower limit for unscheduled bytes in the response message (a few hundred bytes).

在大多数人眼里,这只是个不闭环的 trick,而对此不屑一顾,但 Homa 正视问题并提供兜底:

Incast can also occur in ways that are not predictable; for example, several machines might simultaneously decide to issue requests to a single server. However, it is unlikely that many such requests will synchronize tightly enough to cause incast problems. If this should occur, Homa’s efficient use of buffer space still allows it to support hundreds of simultaneous arrivals without packet loss.

事实上,没有精确预测 “用 incast,burst,时延抖动描述的问题” 的算法,所有的预测都只有统计意义。无论是 DC RPC,还是广域网直播,点播,时延抖动本质上均来源于多个报文同时到达。

Wi-Fi 网络以运气主导的退避行为描述抖动,而有线网络以排队行为描述抖动。有线网络两个报文到达 buffer 那一刻的时间上已经坍缩,那是真正同时到达,这就是连续 buffer 排队假设,而 Wi-Fi 网络的同时到达被时间延展,两个 sender 无法判断是否同时到达,除了发生碰撞,Wi-Fi 网络把仲裁交给了概率,时延并非因连续 buffer 排队引入,要取平均时延才有意义。

唯一解决延时抖动问题的方法就是利用历史数据猜,并且整个世界都在这么做。只是人们不习惯利用离线历史数据,而企图在一个 “TCP 连接” 内解决问题。

还是那个例子,我在 cong_control 回调函数里对 1000 多 IP 的每一个或每几个配置独立的 rate/cwnd 获得了不错的效果,因为我分析了 10000 份散点数据,发现每天特定 IP 地址在特定时间对应的 cwnd 上限就是 x,多了就不再有收益甚至有损,我发现某些特定 IP 无论怎么 “优化”,都更糟,我自然知道接下来如何处置它们。

周末帮朋友测了一下 Wi-Fi 时延抖动对 BBR 的影响,无论 maxbw 还是 minrtt 的测量均受到了致命影响,完全偏离模型。BBR update minrtt 完全信赖一个 RTT 瞬时值,这一点本身是个非常难以满足的约束,而该瞬时值将影响 BBR 整个状态机的转换。连同上周以及周末做得测试,BBR 就是一个瓷娃娃,cwnd 依然在起着极其重要的作用,因为无论 maxbw 还是 minrtt 都太过理想,非常容易被吊偏。

浙江温州皮鞋湿,下雨进水不会胖。文章来源地址https://www.toymoban.com/news/detail-409758.html

到了这里,关于当 BBR 面对时延抖动的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 树上启发式合并(dsu on tree)

    dsu on tree dsu text{dsu} dsu 一般指 disjoint set union text{disjoint set union} disjoint set union ,即并查集。 dsu on tree text{dsu on tree} dsu on tree 指树上合并与查询操作,但它的实现和普通的并查集并无关联,两者的共同点仅仅在于都能合并集合和查询而已。 dsu on tree text{dsu on tree} d

    2024年02月16日
    浏览(41)
  • 【启发式算法】灰狼优化算法【附python实现代码】

    写在前面: 首先感谢兄弟们的订阅,让我有创作的动力,在创作过程我会尽最大能力,保证作品的质量,如果有问题,可以私信我,让我们携手共进,共创辉煌。 路虽远,行则将至;事虽难,做则必成。只要有愚公移山的志气、滴水穿石的毅力,脚踏实地,埋头苦干,积跬

    2024年02月16日
    浏览(35)
  • 非梯度类启发式搜索算法:Nelder Mead

    Hello,今天给大家介绍一种不基于梯度的优化算法 Nelder Mead。 Nelder Mead 算法通常是用来求解非线性(nonlinear)、导函数未知情况下目标函数的最大值或者最小值。学过梯度下降的同学应该知道,梯度下降类算法的每一步都需要计算当前位置的梯度,从而更新当前解使得最终逐

    2024年02月02日
    浏览(45)
  • 元启发式算法库 MEALPY 初体验-遗传算法为例

    官网: MealPY官网 开源许可: (GPL) V3 MEALPY (MEta-heuristic ALgorithms in PYthon) 是一个提供最新自然启发式元启发算法的Python模块,它是最大的此类Python模块之一。这些算法模仿自然界中的成功过程,包括生物系统以及物理和化学过程。mealPy 的目标是免费向所有人分享元启发领域的知识

    2024年04月11日
    浏览(42)
  • 求解三维装箱问题的启发式深度优先搜索算法(python)

    给定一个容器(其体积为 V V V ) 和一系列待装载的箱子,容器和箱子的形状都是长方体。问题的目标是要确定一个可行的箱子放置方案使得在满足给定装载约束的情况下,容器中包含的箱子总体积 S S S 尽可能的大,即填充率尽可能的大,这里填充率指的是 S / V ∗ 100 % S/ V * 1

    2024年02月05日
    浏览(99)
  • 【论文阅读】聚集多个启发式信号作为监督用于无监督作文自动评分

    本文提出一个新的无监督的AES方法ULRA,它不需要真实的作文分数标签进行训练; ULRA的核心思想是使用多个启发式的质量信号作为伪标准答案,然后通过学习这些质量信号的聚合来训练神经自动评分模型。 为了将这些不一致的质量信号聚合为一个统一的监督信号,我们将自动

    2024年02月16日
    浏览(39)
  • 人工大猩猩部队优化器:一种新的面向全局优化问题的自然启发元启发式算法(Matlab代码实现)

           目录 💥1 概述 📚2 运行结果 🎉3 参考文献 👨‍💻4 Matlab代码 元启发式在解决优化问题方面发挥着关键作用,其中大多数都受到自然界中自然生物集体智慧的启发。本文提出了一种新的元启发式算法,其灵感来自自然界大猩猩部队的社会智能,称为人工大猩猩部

    2024年02月01日
    浏览(43)
  • 【无码专区1】简单路径的第二大边权(启发式合并+最小生成树)

    只有std,没有自我实现,所以叫做无码专区 description 给一张无向图,多次询问,每次询问两个点之间所有简单路径(不重复经过点)中边权第二大(不是严格第二大)的权值的最小值。 数据范围: 1 0 5 10^5 1 0 5 级别 我的想法 前 50 % 50% 5 0 % 的数据 q , n ≤ 1 0 3 , m ≤ 2 × 1 0

    2024年02月08日
    浏览(35)
  • 如何进行测试分析与设计-HTSM启发式测试策略模型 | 京东云技术团队

    测试,没有分析与设计就失去了灵魂; 测试人员在编写用例之前,该如何进行测试分析与设计呢?上次在《测试的底层逻辑》中讲到了【输入输出测试模型】,还讲到了【2W+1H测试分析法】,但2W1H分析法是初步的分析方法,具体在测试中如何落地,还需要更细的设计。 今天

    2024年02月05日
    浏览(49)
  • 启发式搜索算法:A算法(全局、局部择优算法)+A*算法 解决八数码问题

    参考博客:人工智能搜索策略:A*算法 在图搜索算法中,如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序,则该搜索算法为 A算法 。由于估价函数中带有问题自身的启发性信息,因此,A算法又称为启发式搜索算法。 对启发式搜索算法,又可根据搜

    2024年02月10日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包