拥塞控制算法的 Utility-Function

网络效能最大化(Network Utility Maximization) 是一种在网络资源分配和优化等领域广泛应用的理念和技术手段,旨在通过合理分配网络资源(如带宽),使网络整体效用最大化,而效用则通过 Utility-Function U ( x ) U(x) U(x) 来度量。

NUM 最大化意味着 Σ U ( x i ) \Sigma U(x_i) ΣU(xi) Σ x i < = C \Sigma x_i<=C Σxi<=C 的约束下达到最大,这是一个独立的计算领域,本文只谈 U ( x ) U(x) U(x) 本身。

U ( x ) U(x) U(x) 形式一般(几乎一定)是上凹的,背后是边际效益递减在起作用,意味着 U ( x ) U(x) U(x) 是一个递增的,但增长速度递减的函数,log,arctan 均符合该特征,有意思的是,从各拥塞控制算法本身而不是 NUM 的概念出发,推导出 U ( x ) U(x) U(x) 符合 log,arctan 的形式是自然而然的,边际效益递减符合类第一性原理: y = log ⁡ a x y=\log_ax y=logax y = arctan ⁡ ( x ) y=\arctan(x) y=arctan(x) y = 1 − e − x y=1-e^{-x} y=1ex y = x 0.5 y=x^{0.5} y=x0.5.

Loss-based AIMD Utility-Function 推导:

设 p 为丢包率,w 为 cwnd,a, b 为 AIMD 参数,看 Loss-based AIMD 的微分方程:

d w d t = ( 1 − p ) ∗ a w − p ∗ b ∗ w \dfrac{dw}{dt}=(1-p)*\dfrac{a}{w}-p*b*w dtdw=(1p)wapbw

稳定状态下 d w d t = 0 \dfrac{dw}{dt}=0 dtdw=0,于是:

( 1 − p ) ∗ a w = p ∗ b ∗ w (1-p)*\dfrac{a}{w}=p*b*w (1p)wa=pbw

设 x 为发送速率,d 为时延,有 x = W d x=\dfrac{W}{d} x=dW,于是:

p = a a + b ⋅ W 2 = a a + b ⋅ x 2 ⋅ d 2 p=\dfrac{a}{a+b\cdot W^2}=\dfrac{a}{a+b\cdot x^2\cdot d^2} p=a+bW2a=a+bx2d2a

网络效能由于 p 而变化,于是:

U ′ ( x ) = p = a a + b ⋅ x 2 ⋅ d 2 U'(x)=p=\dfrac{a}{a+b\cdot x^2\cdot d^2} U(x)=p=a+bx2d2a

积分可得:

U ( x ) = a b ⋅ d ⋅ arctan ⁡ ( b a ⋅ d ⋅ x ) U(x)=\sqrt{\dfrac{a}{b}}\cdot d\cdot\arctan{(\sqrt{\dfrac{b}{a}}\cdot d\cdot x)} U(x)=ba darctan(ab dx)

总结 Loss-based AIMD,丢包率独立于 buffer 单独起作用,需区别对待 buffer 溢出和其它丢包(万年难题)。

Delay-based Vegas Utility-Function 推导:

设 D 为实际 rtt,d 为 minrtt,w 为 cwnd,看 Delay-based Vegas 的 diff 公式:

d i f f = α = w d − w D diff=\alpha=\dfrac{w}{d}-\dfrac{w}{D} diff=α=dwDw

排队时延 d - D 度量排队 Delay,设发送速率为 x:

D − d = α ⋅ d w D = α ⋅ d x D-d=\dfrac{\alpha\cdot d}{\dfrac{w}{D}}=\dfrac{\alpha\cdot d}{x} Dd=Dwαd=xαd

网络效能由于排队 Delay 而变化,于是:

U ′ ( x ) = D − d = α ⋅ d x U'(x)=D-d=\dfrac{\alpha\cdot d}{x} U(x)=Dd=xαd

积分可得:

U ( x ) = α ⋅ d ⋅ log ⁡ ( x ) U(x)=\alpha\cdot d\cdot \log(x) U(x)=αdlog(x)

等式 x ⋅ ( D − d ) = α ⋅ d x\cdot(D-d)=\alpha\cdot d x(Dd)=αd 左边是 queuing 数据量,右边是约束。具体细节参考 Understanding TCP Vegas: A Duality Model

总结 Vegas,链路上的 buffer 中保留一定量的数据,网络便可高效能传输。

BDP-based BBR Utility-Function 推导:

设 d 为最小测量 rtt,B 为最大带宽(maxbw)下的有效(不算排队时延) BDP:

d = B x d=\dfrac{B}{x} d=xB

最小 rtt 的承诺度量网络效能的变化:

U ′ ( x ) = d = B x U'(x)=d=\dfrac{B}{x} U(x)=d=xB

积分可得:

U ( x ) = B ⋅ log ⁡ ( x ) U(x)=B\cdot \log(x) U(x)=Blog(x)

总结 BBR,对 minrtt 非常敏感(ProbeRTT 的重要性以及 minrtt 的使用),minrtt 的共识偏差会影响 BBR 的探测行为和收敛。

写点想法,网络质量越好,拥塞控制的意义越弱,这是边际收益递减的反面,边际成本增加(雇佣一个专家要花不少钱,但他做出来的东西却没什么鸟用),从内格尔(Nagle)的 RFC896 开始,折腾整整 40 年的拥塞控制,到现在真玩不出什么花活儿了,即将被遗忘,没有坑,工作也难找…大城市立交桥,快速路,高速公路不需要红绿灯,只有乡镇才会批量采购红绿灯…

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/922249.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

数据集-目标检测系列- 安全背心 检测数据集 safety_vests >> DataBall

数据集-目标检测系列- 安全背心 检测数据集 safety DataBall 助力快速掌握数据集的信息和使用方式&#xff0c;会员享有 百种数据集&#xff0c;持续增加中。 贵在坚持&#xff01; 数据样例项目地址&#xff1a; * 相关项目 1&#xff09;数据集可视化项目&#xff1a;gi…

C语言菜鸟入门·关键字·int的用法

目录 1. int关键字 1.1 取值范围 1.2 符号类型 1.3 运算 1.3.1 加法运算() 1.3.2 减法运算(-) 1.3.3 乘法运算(*) 1.3.4 除法运算(/) 1.3.5 取余运算(%) 1.3.6 自增()与自减(--) 1.3.7 位运算 2. 更多关键字 1. int关键字 int 是一个关键字&#xff0…

unity中:超低入门级显卡、集显(功耗30W以下)运行unity URP管线输出的webgl程序有那些地方可以大幅优化帧率

删除Global Volume&#xff1a; 删除Global Volume是一项简单且高效的优化措施。实测表明&#xff0c;这一改动可以显著提升帧率&#xff0c;甚至能够将原本无法流畅运行的场景变得可用。 更改前的效果&#xff1a; 更改后的效果&#xff1a; 优化阴影和材质&#xff1a; …

Vue + Websocket播放PCM(base64转ArrayBuffer、 字符串转ArrayBuffer)

文章目录 引言I 音视频处理相关概念和APIII 案例:基于开源库 pcm-player方式播放借助MediaSource和Audio对象播放音频流。基于原生api AudioContext 播放操作III 格式转换js字符串转ArrayBufferbase64 转 ArrayBufferIV 解决pcm-player分片播放问题引言 需求: 基于webscoket传…

【JavaEE进阶】SpringBoot 快速上⼿

了解Maven,并配置国内源 使⽤SpringBoot创建⼀个项⽬, 输出HelloWorld 一、Maven 1.什么是Maven 官⽅对于Maven的描述: Apache Maven is a software project management and comprehension tool. Based on the concept of a project object model (POM), Maven can man…

QT QFormLayout控件 全面详解

本系列文章全面的介绍了QT中的57种控件的使用方法以及示例&#xff0c;包括 Button(PushButton、toolButton、radioButton、checkBox、commandLinkButton、buttonBox)、Layouts(verticalLayout、horizontalLayout、gridLayout、formLayout)、Spacers(verticalSpacer、horizonta…

PCA算法所体现的核心数学思维

一、PCA算法的基本思想 PCA算法的核心思想是通过线性变换&#xff0c;将数据从原始的高维空间投影到低维空间&#xff0c;同时尽可能保留数据的主要变异性。这种变换是通过找到一组新的坐标轴&#xff08;即主成分&#xff09;来实现的&#xff0c;这些坐标轴是原始数据空间的…

如何解决pdf.js跨域从url动态加载pdf文档

摘要 当我们想用PDF.js从URL加载文档时&#xff0c;将会因遇到跨域问题而中断&#xff0c;且是因为会触发了PDF.js和浏览器的双重CORS block&#xff0c;这篇文章将会介绍&#xff1a;①如何禁用pdf.js的跨域&#xff1f;②如何绕过浏览器的CORS加载URL文件&#xff1f;②如何使…

C语言数据结构——详细讲解 双链表

从单链表到双链表&#xff1a;数据结构的演进与优化 前言一、单链表回顾二、单链表的局限性三、什么是双链表四、双链表的优势1.双向遍历2.不带头双链表的用途3.带头双链表的用途 五、双链表的操作双链表的插入操作&#xff08;一&#xff09;双链表的尾插操作&#xff08;二&a…

Java小白成长记(创作笔记二)

目录 序言 思维导图 续 用户登录/注册 数据表 实体层 持久层 服务层 认证与授权 整合springsecurity controller注册测试 controller登录测试 跨域解决 方法 Java小白成长记&#xff08;创作笔记一&#xff09; Java小白成长记&#xff08;创作笔记二&#xff09;…

案例研究|阿特斯的JumpServer分布式部署和多组织管理实践

苏州阿特斯阳光电力科技有限公司&#xff08;以下简称为阿特斯&#xff09;是一家集太阳能光伏组件制造和为全球客户提供太阳能应用产品研发、设计、制造、销售的专业公司。 阿特斯集团总部位于加拿大&#xff0c;中国区总部位于江苏省苏州市。通过全球战略和多元化的市场布局…

20241123-四元数高阶奇异值分解-(1)

四元数高阶奇异值分解及其在彩色图像处理中的应用-(1) &#x1f4d4; 声明 &#x1f1e8;&#x1f1f3; : 1️⃣ &#x1f4c3; 原文网址链接: 四元数高阶奇异值分解及其在彩色图像处理中的应用 - ScienceDirect &#x1f517; Quaternion … image processing (arxiv.org) ​ …

游戏引擎学习第20天

视频参考:https://www.bilibili.com/video/BV1VkBCYmExt 解释 off-by-one 错误 从演讲者的视角&#xff1a;对代码问题的剖析与修复过程 问题的起因 演讲者提到&#xff0c;他可能无意中在代码中造成了一个错误&#xff0c;这与“调试时间标记索引”有关。他发现了一个逻辑问题…

python开发之Linux

文章目录 1. 基础2. 进阶链接压缩/解压缩 文件权限用户远程操作编辑文件软件安装 1. 基础 # 查看当前目录下文件 ls# 查看当前目录 pwd# 清除界面内容 clear# 切换目录 cd# 创建目录 mkdir# 创建文件 touch 文件 vi 文件# 强制删除 rm -rf # 复制文件 cp 复制文件 复制文件路径…

Docker2:docker快速入门(部署MySQL)

欢迎来到“雪碧聊技术”CSDN博客&#xff01; 在这里&#xff0c;您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者&#xff0c;还是具有一定经验的开发者&#xff0c;相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导&#xff0c;我将…

oracle的静态注册和动态注册

oracle的静态注册和动态注册 静态注册&#xff1a; 静态注册 : 指将实例的相关信息手动告知 listener 侦 听 器 &#xff0c; 可以使用netmgr,netca,oem 以及直接 vi listener.ora 文件来实现静态注册&#xff0c;在动态注册不稳定时使用&#xff0c;特点是&#xff1a;稳定&…

杰发科技AC7840——EEP中RAM的配置

sample和手册中示例代码的sram区地址定义不一样 这个在RAM中使用没有限制&#xff0c;根据这个表格留下足够空间即可 比如需要4096字节的eep空间&#xff0c;可以把RAM的地址改成E000&#xff0c;即E000-EFFF&#xff0c;共4096bytes即可。

洛谷 P1616 疯狂的采药 C语言 记忆化搜索

题目&#xff1a; https://www.luogu.com.cn/problem/P1616?contestId215526 完全背包问题&#xff0c;最后一个超出空间了。完全背包和就是无限次的拿&#xff0c;公式跟01背包差不多。 但是&#xff0c;只有当前能拿和拿不下&#xff0c;换下一个。注意要处理好边界条件。…

分布式 Data Warebase - 构筑 AI 时代数据基石

导读&#xff1a;作者以人类世界一个信息层次模型 DIKW 为出发点&#xff0c;引出对计算机世界&#xff08;系统&#xff09;处理数据过程的介绍。接着以一个民宿平台数据架构随业务发展而不断演进的过程&#xff0c;展示了这场信息革命中&#xff0c;在具体应用场景下&#xf…

zotero7 插件使用

zotero style 1、下载地址 Zotero 插件商店 | Zotero 中文社区 2、配置 在工具插件里 3、配置 style 进入高级→设置编辑器 查找 easy 设置完即可显示&#xff0c; 注1&#xff1a;easyscholar的密钥要自行申请注册&#xff0c;注册地址&#xff1a;easySchol…