布雷斯悖论和借贷式拥塞控制

news/2024/7/24 12:39:26 标签: 网络

先看布雷斯悖论,新增一条路不但没减少交通延滞,反而降低了服务水准,下面一个简单的例子:

在这里插入图片描述

关于布雷斯悖论的讨论已经太多,我给出个新解释,这和我引出 借贷式拥塞控制 (差论证和编码)有关。

看一个不严谨但更简单实际(日常生活中常见)的例子:
在这里插入图片描述

当打通一条 “近路” 后,绝大多数流量都会自动进入近路,结果:

  • 流量进入近路,近路上 A 处拥堵。
  • 2 处分流的假象,可能引导更多流量从 1 进入。
  • 偶尔进入原始路径的流量在 3 处和近路流量汇合而拥堵。
  • 如果 2 到 3 间有入口,新流量会被 2-3 间的小流量欺骗,大量涌入后在 3 处加剧拥堵。

所有这一切都因打通了 2,3 间的近路。

进一步抽象一下,将入口 1 和 4 之间的所有可能路径设想成一个纷乱如麻的黑盒子,里面塞满了所有可能的路径(这是可能的,但不容易想象):
在这里插入图片描述

所有这些路径有直达的,有中转的,总之这简直是 full-mesh,能连接的都连在一起。假设每条路径都有流量,以下结论是显然的:

  • 总存在至少 1 条路径从入口到达出口时间最短。
  • 总存在至少 1 条路径使出口满负载运转。

现在做以下操作:

  • 上述第一点的那些路径加入集合 S,排除 S 外的其它路径。
  • 看出口是否满负载,如果不满负载,在集合 S 外找最优路径,重复 1。
  • 直到出口满负载。

集合 S 让出口满负载,这就是这个盒子的最优解:最小时延,最大带宽:
在这里插入图片描述

现在将那些不属于 S 的路径逐步添加进盒子,这等价于 “修路”,它的结果是:

  • 出口负载已满,不会再增加。
  • 入口进入的流量增加。
  • 出入不守恒,盒子内部拥塞,这表示 “整个网络的服务水准下降”。

以上就是布雷斯悖论的解释。

拥塞的根本原因在于负反馈时间过久,以至入口容量的假象欺骗太久,如果盒子巨大,溢出盒子需很久,这将导入大量无效流量。容易发现,越宽的路,堵车时越壮观,无论多宽的路,似乎总是被填满。

负反馈的延迟导致正反馈:路越宽,负反馈越久,维持欺骗的时间越久,拥塞程度越剧烈。buffer 越大,拥塞越很。

若转为主观,占便宜不花代价,大家都占便宜时,自己必须趋同,整条路都被占便宜者堵着,你能怎么办,缺乏反向激励和惩罚机制。这就是我屡次强调过的,别的流通过 probe 挤兑带宽时,自己就必须用至少一样的力度挤兑,否则将一无所有。

评价车牌拍卖制度时,我们能感受到虽然本意是减缓拥塞,车牌价格相当于拥塞税,你要开车,就要花钱,因为你不花钱就没拍照,所以花钱而已,车就越来越多。这和 cubic vs. bbr 异曲同工,想获得更多带宽,只能 probe,但也就 probe 而已,buffer 越堆越满,幸好 cubic 有 aimd 约束,当然也是为了自己。

拍牌相当于提前预付拥塞税,必须交钱才能开车,既然已经交了,就随便上路了,没有 “实时的” 反向措施作为勾引或反制。比如如果不开车转而坐公共交通,会退钱。

回到上面黑盒子,如果每人进入盒子一次收 1 元,两次收 2 元,10 人合并进入一次奖励 1 元,20 人合并进入奖励 2 元,这个盒子最终会自动识别 S 集。

再回到最上面 wiki 的例子,如果近路不再 0 成本,而是第一天收 1 元,第二天收 2 元,第一天走原路奖励 1 远,第二天走原路奖励 2 元,结合时间货币成本自行考量,新路顺利提升了通行效率。

一方亏的给了另一方,让他的收益递减他才肯主动亏,因为这能换来他的收益递增。没有动机作恶才是最好的。

总之,负反馈也好,自抑制也罢,让占便宜的收益递减,不占便宜的吃亏递增,or 占便宜的惩罚递增,不占便宜的奖励递减,系统就会自动收敛到高效和公平,结合经济规律以及人口规律的周期性,这就是我那个 借贷式拥塞控制 的缘起和初衷。

aimd 和 bbr 分别处于借贷式拥塞控制的两边,aimd 预付拥塞税,却对代价零存整取,而 bbr 则试图实时跟踪并匹配资源,虽说我们不希望 cc 工作在右边的丢包点,但左边的 bltbw/proprt 最优操作点却不可达,真实情况在二者之间。

纳什均衡可能也不是最优解,但却是最平衡的。

浙江温州皮鞋湿,下雨进水不会胖。


http://www.niftyadmin.cn/n/5149087.html

相关文章

【LeetCode:117. 填充每个节点的下一个右侧节点指针 II | DFS | BFS】

🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,…

【项目管理】项目计划中常见影响进度的风险汇总

哈喽,大家好,我是雷工。 在项目实施过程中针对项目进度的计划常常会有各种各样的的风险,相比出了问题去救火与填坑,能够提前预知风险,并提前调整计划,更能有利于项目的如期交付。 以下为项目计划中影响进度…

操作系统(28)

1. 简单说下你对并发和并行的理解? 2. 同步、异步、阻塞、非阻塞的概念 3. 进程和线程的基本概念 4. 进程与线程的区别? 5. 为什么有了进程,还要有线程呢? 6. 进程的状态转换 7. 进程间的通信方式有哪些? 8. 进程的调度…

Python项目结构布局

通过“结构”,指的是在项目中为实现其目标所做的决策。需要考虑如何充分利用Python的特性来创建清晰、高效的代码。从实际角度来看,“结构”意味着创建清晰的代码,其逻辑和依赖关系清晰明了,以及文件和文件夹在文件系统中的组织方…

Path with “WEB-INF“ or “META-INF“: [webapp/WEB-INF/NewFile.html]

2023-11-04 01:03:14.523 WARN 10896 --- [nio-8072-exec-6] o.s.w.s.r.ResourceHttpRequestHandler : Path with "WEB-INF" or "META-INF": [webapp/WEB-INFNewFile.html] spring.mvc.view.prefix:/webapp/WEB-INF/

中兴路由器、小米路由器无线信号强度对比

最近小米新推出的路由器小米AX3000T非常火,在网上看到有好多人都在安利,引起了我的兴趣,刚好老家的路由器用了这么久也是时候要换一个了,毕竟我妈老说上网卡??所以我立马就在PDD搞了一台回来,打算和我现在家里用的中…

树莓派安装64位桌面版Ubuntu教程

事实证明不用显示屏没办法连接64位桌面版的22.04Ubuntu,虽然不用显示屏可以安装64位服务器版的22.04Ubuntu.或者虽然有但是我并不知道,我也不想再花时间去知道了,因为我已经花了3天时间了。 步骤: 1:下载64位22.04Ub…

为什么路由器属于网络层

1. 路由器所属阶段 路由器属于 OSI 模型的网络层,因为它们负责根据网络层信息(第 3 层)做出路由决策。网络层是 OSI 模型中的第三层,主要负责将数据包从网络中的源路由到目的地。 Here’s a formal and precise explanation of …