从交通信号灯看流控和拥塞控制
创始人
2024-05-28 18:35:55
0

局部的效率和全局的公平一直都是矛盾的双方。对一个统计复用系统,局部效率由流控决定,而全局公平由拥塞控制决定。

交通信号灯是个典型的分时复用流控的实例,但我经常看到绿灯方向没有任何车辆通过,红灯方向却排成了长龙,这是个不佳的策略。如果是 Linux kernel,早有一堆人卷 patch 了。

可明明只需要实时 “观测” 统计一下流量,设置一下信号灯就行了,这么简单的操作背后还有什么考虑?

作为分时复用系统,目之所及重要的是调度策略,调度器不能忍受资源闲置,十字路口竟然闲置了一半容量,这是失败的策略。

但从拥塞控制角度看,局部转移视线到全局,如果根据实时流量切换信号灯,这种策略可能从 “心理” 上影响司机,而造成流量颠簸。

人的行为具有规律性,某司机每个工作日某时通过某路口时总是绿灯,接下来某个路口是红灯,这是每天开车上下班路上用时几乎相等的原因,周一到周五下班路上时间大概率是 40 分钟,41 分钟,38 分钟,39 分钟,43 分钟,但几乎不可能是 40 分钟,73 分钟,25 分钟,58 分钟,91 分钟,所以不要以堵车作不确定的借口。

按固定间隔调度信号灯,流量是收敛的。但根据实时流量调度,就不好收敛了。如果某司机发现空闲道路有更大概率遇到红灯,那么他可能会换另一条路,影响另一条路的流量,加剧拥塞,当绿灯道路拥堵到让司机宁可等红灯也不想排队时,流量就颠簸了,最终再次影响信号灯。

注意,从流控视角,是拥塞导致了绿灯,但从自私的拥塞控制视角,司机会颠倒因果,为了不等红灯而加入拥塞。

实时调度的流量带有博弈性质,颠簸而不收敛。

互联网流量调度大概也是如此,QoS 要看全局而非当前节点,如果某 queue 空闲,其它流量能被调度到该 queue 吗?假设可以,如果有条流 “发现” 了这个恩惠,它会发送更多数据,从而拥塞加剧,这有损全局公平性。

曾经我觉得公路交通作为一个统计复用系统,通行时间不确定,但后来我发现这个时间波动性很小,唯一可能对时间造成比较大影响的是交通事故。并道,等红灯这些时间几乎固定。每天坐地铁,你同样会发现身边的人也是同样的人,统计复用系统的行为其实非常固定,这固定的背后应该就是每个节点的固定调度策略。

但当我跟别人说这个固定模式时,没人相信我,没有人相信这是固定的。我曾经提到过一种新样式的拥塞控制算法,利用这种固定的模式来决策发送,但仔细想想,发现点有趣的端倪,如果足够多的 sender 都基于观察到的固定流量模式做决策,固定流量模式本身也就消失了,系统重新开始博弈,颠簸。

到底怎么回事?固定的策略导致固定的流量模式,但固定的流量模式却不能被利用,这是一个从阿拉丁神灯里跳出来的俄罗斯套娃。

每个路口的调度策略可以根据时段切换,但根据实时流量切换又不影响全局,难度很大,要避免他们发现这个策略,还要让他们利用这个策略疏导拥塞,这本身就是矛盾。

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

相关内容

热门资讯

强生爽身粉致癌案判赔女子约11... 据央视财经报道,当地时间12月22日,美国马里兰州陪审团作出一项裁定:强生公司需向一名因使用其婴儿爽...
牛市早报|央行:发挥增量政策和... 【市场数据】 截至12月24日收盘,上证综指涨0.53%,报3940.95点;科创50指数涨0.9%...
宁夏出台未成年人保护新规 学校... 本报讯(记者马学礼 李静楠)近日,宁夏回族自治区人大常委会表决通过《宁夏回族自治区实施〈中华人民共和...
央行货币政策委员会:加强货币政... 中国人民银行货币政策委员会2025年第四季度例会于12月18日召开。会议要求,要继续实施适度宽松的货...
秦皇岛为餐厨废弃物管理“立规矩... 12月23日,秦皇岛市新闻办举办《秦皇岛市餐厨废弃物管理条例》颁布实施新闻发布会,相关负责人介绍了有...
案无大小用心辩|蓝天彬律师《正... 近年来,大型超市越来越多,人工收银和自助收银越来越结合,有些超市甚至全部启用自助结账。 邓晓光(化...
【早知道】北京调整住房限购政策... 人民财讯12月25日电,【摘要】央行:综合运用多种工具,加强货币政策调控。八部门联合发布《关于金融支...
浙江棒杰控股集团股份有限公司关... 本公司及董事会全体成员保证信息披露的内容真实、准确、完整,没有虚假记载、误导性陈述或者重大遗漏。 重...
公安机关依法征集两名台湾居民违... 据新华社北京12月24日电(记者 李寒芳 尚昊)国务院台办发言人彭庆恩24日在例行新闻发布会上表示,...