inflight 守恒算法的实现和仿真

2024-08-26 23:28

本文主要是介绍inflight 守恒算法的实现和仿真,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前面介绍过,只要某条流的 inflt 在 bdp 之外再增加一个相等的余量 I,即 inflt = bdp + I,比如 I = 2,I = 3,…,就一定会收敛到公平,且不会占据过多 buffer,因此 rtt 不会膨胀,I 的大小影响收敛速度,I 越大,收敛越快,但 buffer 占据也更多,I 越小,收敛越慢,但 buffer 占据更少,所以效率和公平的 tradeoff 在此体现。

记住这个简洁的结论,然后将 I 调整为动态的负反馈,就是一个新算法,该算法占据 “一定量” 的 buffer 而不是像 aimd 那样抖动,占据 buffer 的大小由 I 的均值决定。平稳压倒一切,抖动是低效的根源,始终占据一定量的 buffer 是可以接受的,通过调参可以将这个 “一定量” 压到尽可能小。

简单用 c 实现了一版 inflight 守恒算法,非常简洁:

#include <stdio.h>
#include <stdlib.h>#define BW_FILTER_LEN 10double RTPROP = 1;
double C = 100.0; // bottleneck_link_bw
double I = 0.0;struct es {double E;double bw;
};struct ebest_flow {int index;               /* flow identifier */int status;double I;double inflt;double min_rtt;double srtt;double sending_bw;       /* current receive bw */double receive_bw;       /* current receive bw */struct es max_e;           /* current estimated bw */struct es e_samples[BW_FILTER_LEN];int phase_offset;
};struct ebest_flow f1;
struct ebest_flow f2;
struct ebest_flow f3;
struct ebest_flow f4;int t = 0;
int bw_filter_index = 0;#define max(a, b) (a > b) ? (a) : (b)
#define min(a, b) (a < b) ? (a) : (b)void ebest_set_max_e(struct ebest_flow *f)
{int i = 0;f->max_e.bw = 0;for (i = 0; i < BW_FILTER_LEN; i++) {f->max_e.E = max(f->max_e.E, f->e_samples[i].E);f->max_e.bw = f->e_samples[i].bw;}f->I = 0.7 * f->I + 0.3 * 40 * f->min_rtt * f->max_e.bw/(20 * f->min_rtt + f->max_e.bw * f->srtt) * (f->min_rtt / f->srtt);
}void ebest_update_maxbw_minrtt(struct ebest_flow *f, double rtt)
{rtt = (rtt > RTPROP)?:RTPROP;f->e_samples[bw_filter_index].E = f->receive_bw / rtt;f->e_samples[bw_filter_index].bw = f->receive_bw;ebest_set_max_e(f);if (rtt <= f->min_rtt) {f->srtt = f->min_rtt = rtt;} else {f->srtt = rtt;}
}void ebest_update_sending_bw(struct ebest_flow *f)
{f->inflt = f->max_e.bw * f->min_rtt + f->I;printf("#### f: %d  %.3f\n", f->index, f->I);f->sending_bw = f->max_e.bw;printf("flow %d phase: %d max_bw: %.3f sending_bw: %.3f\n",f->index, 0, f->max_e.bw, f->sending_bw);
}void simulate_one_phase(int i)
{double rtt;//if (i == 1500)//  C = 160;//if (i == 2500)//  C = 40;ebest_update_sending_bw(&f1);ebest_update_sending_bw(&f2);ebest_update_sending_bw(&f3);ebest_update_sending_bw(&f4);printf("t= %04d sending: f1: %.3f f2: %.3f f3: %.3f f4: %.3f\n",t, f1.sending_bw, f2.sending_bw, f3.sending_bw, f4.sending_bw);double total_I = 0;if (i < 1000) {rtt = (f1.inflt + f2.inflt + f3.inflt) / C;f1.receive_bw = C * f1.inflt / (f1.inflt + f2.inflt + f3.inflt);f2.receive_bw = C * f2.inflt / (f1.inflt + f2.inflt + f3.inflt);f3.receive_bw = C * f3.inflt / (f1.inflt + f2.inflt + f3.inflt);f4.receive_bw = 0;f4.max_e.bw = 0;f4.inflt = 0;if (i == 999) {f4.max_e.bw = 0.1 * C;f4.inflt = 0.1 * C * RTPROP + I;f4.I = I;f4.receive_bw = 0.1 * C;printf("@@@@### time: %d  f1: %.3f  f2: %.3f  f3: %.3f  f4: %.3f \n", t, f1.inflt, f2.inflt, f3.inflt, f4.inflt);}total_I = f1.I + f2.I + f3.I;printf("t= %04d  remain: f1: %.3f f2: %.3f f3: %.3f f4: %.3f\n",t, f1.I, f2.I, f3.I, total_I);} else if (i >= 1000 && i < 2000) {rtt = (f1.inflt + f2.inflt + f3.inflt + f4.inflt) / C;f1.receive_bw = C * f1.inflt / (f1.inflt + f2.inflt + f3.inflt + f4.inflt);f2.receive_bw = C * f2.inflt / (f1.inflt + f2.inflt + f3.inflt + f4.inflt);f3.receive_bw = C * f3.inflt / (f1.inflt + f2.inflt + f3.inflt + f4.inflt);f4.receive_bw = C * f4.inflt / (f1.inflt + f2.inflt + f3.inflt + f4.inflt);if (i < 1100) {printf("@@@@### time: %d  f1: %.3f  f2: %.3f  f3: %.3f  f4: %.3f \n", t, f1.inflt, f2.inflt, f3.inflt, f4.inflt);}total_I = f1.I + f2.I + f3.I + f4.I;printf("t= %04d  remain: f1: %.3f f2: %.3f f3: %.3f f4: %.3f\n",t, f1.I, f2.I, f3.I, total_I);} else {rtt = (f1.inflt + f2.inflt) / C;f1.receive_bw = C * f1.inflt / (f1.inflt + f2.inflt);f2.receive_bw = C * f2.inflt / (f1.inflt + f2.inflt);f3.receive_bw = 0;f4.receive_bw = 0;f3.max_e.bw = 0;f4.max_e.bw = 0;f3.inflt = 0;f4.inflt = 0;total_I = f1.I + f2.I;printf("t= %04d  remain: f1: %.3f f2: %.3f f3: %.3f f4: %.3f\n",t, f1.I, f2.I, f3.I, total_I);}if (rtt < RTPROP)rtt = RTPROP;printf("t= %04d receive: f1: %.3f f2: %.3f f3: %.3f f4: %.3f\n",t, f1.receive_bw, f2.receive_bw, f3.receive_bw, f4.receive_bw);ebest_update_maxbw_minrtt(&f1, rtt);ebest_update_maxbw_minrtt(&f2, rtt);ebest_update_maxbw_minrtt(&f3, rtt);ebest_update_maxbw_minrtt(&f4, rtt);printf("t= %04d  max_bw: f1: %.3f f2: %.3f f3: %.3f f4: %.3f\n",t, f1.max_e.bw, f2.max_e.bw, f3.max_e.bw, f4.max_e.bw);printf("t= %04d  inflt: f1: %.3f f2: %.3f f3: %.3f f4: %.3f\n",t, f1.inflt, f2.inflt, f3.inflt, f4.inflt);printf("t= %04d  min_rtt: f1: %.3f f2: %.3f f3: %.3f f4: %.3f\n",t, rtt, f2.min_rtt, f3.min_rtt, f4.min_rtt);t++;bw_filter_index = (bw_filter_index + 1) % BW_FILTER_LEN;
}int main(int argc, char *argv[])
{int i = 0;if (argc > 1) I = atof(argv[1]);f1.index = 1;f2.index = 2;f3.index = 3;f4.index = 4;f1.max_e.bw = 0.9 * C;f2.max_e.bw = 0.3 * C;f3.max_e.bw = 0.6 * C;f1.max_e.E = f1.max_e.bw / RTPROP;f2.max_e.E = f2.max_e.bw / RTPROP;f3.max_e.E = f3.max_e.bw / RTPROP;f1.I = I;f2.I = I;f3.I = I;f4.I = 0;f1.srtt = f1.min_rtt = RTPROP;f2.srtt = f2.min_rtt = RTPROP;f3.srtt = f3.min_rtt = RTPROP;f4.srtt = f4.min_rtt = RTPROP;f1.inflt = 0.1 * C * RTPROP;f2.inflt = 0.3 * C * RTPROP;f3.inflt = 0.6 * C * RTPROP;f1.e_samples[BW_FILTER_LEN - 1] = f1.max_e;f2.e_samples[BW_FILTER_LEN - 1] = f2.max_e;f3.e_samples[BW_FILTER_LEN - 1] = f3.max_e;for (i = 0; i < 3000; i++) {simulate_one_phase(i);}return 0;
}

算法和建模分别参见 inflight 守恒背后的哲学 与 inflight 守恒数学建模.

这个算法的核心只需要设置 remain 余量,剩下的跟踪 E_best = max(bw / delay) 即可,因此 remain 一定是个负反馈方程:

R e m a i n = α ⋅ R T T m i n ⋅ B W w h e n _ E _ b e s t β ⋅ R T T m i n + B W w h e n _ E _ b e s t ⋅ R T T s m o o t h ⋅ R T T m i n R T T s m o o t h Remain=\dfrac{\alpha\cdot RTT_{min}\cdot BW_{when\_E\_best}}{\beta \cdot RTT_{min}+BW_{when\_E\_best}\cdot RTT_{smooth}}\cdot \dfrac{RTT_{min}}{RTT_{smooth}} Remain=βRTTmin+BWwhen_E_bestRTTsmoothαRTTminBWwhen_E_bestRTTsmoothRTTmin

效果如下:
在这里插入图片描述

明显有负反馈效果,但还是需要增加自由度,继续调参,我需要的效果是无论多少条流,所有流的 Remain 之和在一个有限范围内。

而 inflt 收敛效果如下:
在这里插入图片描述

rtt 平稳且并未膨胀:
在这里插入图片描述

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

这篇关于inflight 守恒算法的实现和仿真的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1109981

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo