关于拥塞控制的几点思考引言拥塞控制要解决的根本问题表述起来很简单多个发送方共享一条链路如何协调各自的发送速率使得链路资源被充分利用同时避免因过载而崩溃。但这个问题没有终极答案。它之所以难不是因为数学不够精巧而是因为它本质上是在不确定的环境中做决策。你所依赖的测量信号永远是不完整的你所构建的模型永远是对现实的简化你所能做的永远是在多个互斥的目标之间寻找一个可接受的平衡。下面从六个方面展开。一、测量的互斥性拥塞控制的第一步是测量链路状态。但这里存在一个根本性的互斥你想测量什么带宽延迟需要塞满链路需要清空队列塞满→排队→延迟被污染清空→空闲→带宽测量失效你永远无法同时获知带宽和延迟的真值这是一个观测困境。任何算法都必须在这个困境中选择一个优先方向要么先测带宽接受延迟测量暂时不可靠要么先测延迟接受带宽测量暂时不可靠。没有人能同时做到两件事。这意味着所有算法从第一步开始就已经带着偏见。二、信号含义的模糊性即使你获得了测量值如何解读它也是一个难题。可能的原因观测丢包RTT增加真拥塞无线干扰浅缓存路由切换调度抖动自身突发丢包是一个物理事实但造成丢包的原因多种多样。把丢包当作拥塞信号在无线网络或浅缓存场景下会导致不必要的降速不把丢包当回事在真正拥塞时又可能让队列无限增长。RTT的增加同样模糊。一次路由切换可能让延迟永久增加几十毫秒但这与拥塞无关。一次系统时钟抖动可能产生一个异常大的RTT样本但下一毫秒就恢复正常。你无法仅从一个数字判断它背后的物理原因。算法只能做一种假设要么假定大多数异常是噪声可以过滤要么假定大多数异常是信号需要响应。没有哪种假设永远正确。三、利用率与拥塞的对立算法的第一目标是带宽利用率——用户为带宽付费自然希望用满它。但利用率与拥塞之间存在天然矛盾发送速率增加队列增长延迟增加利用率接近上限队列溢出丢包重传有效吞吐下降在达到瓶颈带宽之前利用率随发送速率线性增长。越过瓶颈之后额外流量只会增加队列长度和延迟而不会提高有效吞吐。继续增加队列溢出丢包发生重传消耗额外带宽有效吞吐甚至可能下降。所以想跑满带宽就必须接受一定程度的排队想避免丢包就必须牺牲一部分带宽。这不是算法缺陷而是物理约束。不同场景对这笔交易的接受度不同场景偏好策略实时音视频低延迟宁可丢包也不排队大文件传输高吞吐宁可排队也要压满网页浏览响应快少量排队可接受但不要丢包没有一种策略能同时满足所有场景。四、公平性的模糊边界当多条流共享同一条链路时算法还必须回答一个问题谁应该得到多少折中某种可接受的共存每条流都感觉公平总带宽未明显浪费极端2强制平均分配所有流迁就最慢者总带宽浪费极端1完全按需分配强者恒强小流可能被饿死“公平”不是一个数学概念而是一个社会性概念。不同用户、不同应用对公平的期待不同。TCP的“公平”通常指“各流平分瓶颈带宽”但这隐含了假设所有流同等重要、同等持久、同等对延迟敏感。这些假设在现实中常常不成立。一个诚实的表述是我们无法定义绝对公平只能定义一种可接受的共存状态——在这种状态下没有一条流觉得自己被恶意压制整体带宽没有被明显浪费。这个边界是模糊的不同算法划在不同的位置。五、测量工具的假设与局限任何测量工具都带有假设。算法的差异很大程度上是测量工具的差异。适用边界隐含假设测量方法滑动窗口取最小值卡尔曼滤波AIMD/丢包反馈噪声偶发信号稳定随机游走过程高斯噪声丢包是拥塞主信号其他因素可忽略低抖动网络高噪声网络需处理不确定性浅缓存/无线场景假设常被违反滑动窗口取最小值默认真实延迟是稳定的噪声只是偶尔的异常。当网络频繁抖动或路径切换时这个假设就会出问题。卡尔曼滤波假设过程是随机游走、噪声是高斯分布。这个假设在很多场景下更贴近现实但它仍然是简化——真实网络的噪声并不总是高斯的。丢包作为拥塞信号的假设在现代网络大缓存、无线、数据中心中越来越不可靠。没有万能的测量工具。每个工具都有它的适用环境而环境是会变的。六、两种思想面对上述所有不确定性算法设计大致有两种思路。设计哲学规则驱动 Rule-based模型驱动 Model-based定义明确规则增益、窗口、阈值优点行为可预测易于实现和调试缺点规则不完备总有未覆盖的 corner case建立数学模型用观测数据修正参数优点适应性强可处理不确定性缺点模型假设偏差误差可能被放大规则驱动写清楚if-then规定什么时候增加窗口、什么时候减少。这种思路偏好确定性行为可预测调试方便。但它永远面临一个问题规则无法穷尽所有情况。每发现一个新问题就要打一个新补丁。补丁多了系统变得脆弱且难以理解。模型驱动先假设网络行为可以用某个数学模型描述比如随机游走、线性系统然后用观测数据不断修正模型参数最后根据模型输出做决策。这种思路更灵活能适应环境变化。但它依赖于模型的正确性——如果模型假设偏离真实误差会被迭代放大。两种思路没有绝对优劣。它们只是对“不确定性”的不同态度一种试图通过规则来控制它另一种试图通过模型来量化它。结语拥塞控制不是一个可以“终结”的问题。网络在变应用在变硬件在变人们对“好”的定义也在变。一个在今天看来优雅的模型明天可能因为新的场景而显得简陋。一个诚实的拥塞控制算法设计者会说我不知道最优解是什么。我只能选择一个不太坏的妥协。选择激进就承受丢包选择保守就承受浪费选择公平就承受效率损失选择效率就承受不公平。承认这个局限与自己的无知可能比发明一个“完美”算法更重要。因为说到底我们是在用有限的观测、有偏的假设、互斥的目标去应对一个我们永远无法完全了解的世界。这不是技术问题这是认识论问题。这篇博客没有结论因为本来就没有结论。
关于拥塞控制的几点思考
关于拥塞控制的几点思考引言拥塞控制要解决的根本问题表述起来很简单多个发送方共享一条链路如何协调各自的发送速率使得链路资源被充分利用同时避免因过载而崩溃。但这个问题没有终极答案。它之所以难不是因为数学不够精巧而是因为它本质上是在不确定的环境中做决策。你所依赖的测量信号永远是不完整的你所构建的模型永远是对现实的简化你所能做的永远是在多个互斥的目标之间寻找一个可接受的平衡。下面从六个方面展开。一、测量的互斥性拥塞控制的第一步是测量链路状态。但这里存在一个根本性的互斥你想测量什么带宽延迟需要塞满链路需要清空队列塞满→排队→延迟被污染清空→空闲→带宽测量失效你永远无法同时获知带宽和延迟的真值这是一个观测困境。任何算法都必须在这个困境中选择一个优先方向要么先测带宽接受延迟测量暂时不可靠要么先测延迟接受带宽测量暂时不可靠。没有人能同时做到两件事。这意味着所有算法从第一步开始就已经带着偏见。二、信号含义的模糊性即使你获得了测量值如何解读它也是一个难题。可能的原因观测丢包RTT增加真拥塞无线干扰浅缓存路由切换调度抖动自身突发丢包是一个物理事实但造成丢包的原因多种多样。把丢包当作拥塞信号在无线网络或浅缓存场景下会导致不必要的降速不把丢包当回事在真正拥塞时又可能让队列无限增长。RTT的增加同样模糊。一次路由切换可能让延迟永久增加几十毫秒但这与拥塞无关。一次系统时钟抖动可能产生一个异常大的RTT样本但下一毫秒就恢复正常。你无法仅从一个数字判断它背后的物理原因。算法只能做一种假设要么假定大多数异常是噪声可以过滤要么假定大多数异常是信号需要响应。没有哪种假设永远正确。三、利用率与拥塞的对立算法的第一目标是带宽利用率——用户为带宽付费自然希望用满它。但利用率与拥塞之间存在天然矛盾发送速率增加队列增长延迟增加利用率接近上限队列溢出丢包重传有效吞吐下降在达到瓶颈带宽之前利用率随发送速率线性增长。越过瓶颈之后额外流量只会增加队列长度和延迟而不会提高有效吞吐。继续增加队列溢出丢包发生重传消耗额外带宽有效吞吐甚至可能下降。所以想跑满带宽就必须接受一定程度的排队想避免丢包就必须牺牲一部分带宽。这不是算法缺陷而是物理约束。不同场景对这笔交易的接受度不同场景偏好策略实时音视频低延迟宁可丢包也不排队大文件传输高吞吐宁可排队也要压满网页浏览响应快少量排队可接受但不要丢包没有一种策略能同时满足所有场景。四、公平性的模糊边界当多条流共享同一条链路时算法还必须回答一个问题谁应该得到多少折中某种可接受的共存每条流都感觉公平总带宽未明显浪费极端2强制平均分配所有流迁就最慢者总带宽浪费极端1完全按需分配强者恒强小流可能被饿死“公平”不是一个数学概念而是一个社会性概念。不同用户、不同应用对公平的期待不同。TCP的“公平”通常指“各流平分瓶颈带宽”但这隐含了假设所有流同等重要、同等持久、同等对延迟敏感。这些假设在现实中常常不成立。一个诚实的表述是我们无法定义绝对公平只能定义一种可接受的共存状态——在这种状态下没有一条流觉得自己被恶意压制整体带宽没有被明显浪费。这个边界是模糊的不同算法划在不同的位置。五、测量工具的假设与局限任何测量工具都带有假设。算法的差异很大程度上是测量工具的差异。适用边界隐含假设测量方法滑动窗口取最小值卡尔曼滤波AIMD/丢包反馈噪声偶发信号稳定随机游走过程高斯噪声丢包是拥塞主信号其他因素可忽略低抖动网络高噪声网络需处理不确定性浅缓存/无线场景假设常被违反滑动窗口取最小值默认真实延迟是稳定的噪声只是偶尔的异常。当网络频繁抖动或路径切换时这个假设就会出问题。卡尔曼滤波假设过程是随机游走、噪声是高斯分布。这个假设在很多场景下更贴近现实但它仍然是简化——真实网络的噪声并不总是高斯的。丢包作为拥塞信号的假设在现代网络大缓存、无线、数据中心中越来越不可靠。没有万能的测量工具。每个工具都有它的适用环境而环境是会变的。六、两种思想面对上述所有不确定性算法设计大致有两种思路。设计哲学规则驱动 Rule-based模型驱动 Model-based定义明确规则增益、窗口、阈值优点行为可预测易于实现和调试缺点规则不完备总有未覆盖的 corner case建立数学模型用观测数据修正参数优点适应性强可处理不确定性缺点模型假设偏差误差可能被放大规则驱动写清楚if-then规定什么时候增加窗口、什么时候减少。这种思路偏好确定性行为可预测调试方便。但它永远面临一个问题规则无法穷尽所有情况。每发现一个新问题就要打一个新补丁。补丁多了系统变得脆弱且难以理解。模型驱动先假设网络行为可以用某个数学模型描述比如随机游走、线性系统然后用观测数据不断修正模型参数最后根据模型输出做决策。这种思路更灵活能适应环境变化。但它依赖于模型的正确性——如果模型假设偏离真实误差会被迭代放大。两种思路没有绝对优劣。它们只是对“不确定性”的不同态度一种试图通过规则来控制它另一种试图通过模型来量化它。结语拥塞控制不是一个可以“终结”的问题。网络在变应用在变硬件在变人们对“好”的定义也在变。一个在今天看来优雅的模型明天可能因为新的场景而显得简陋。一个诚实的拥塞控制算法设计者会说我不知道最优解是什么。我只能选择一个不太坏的妥协。选择激进就承受丢包选择保守就承受浪费选择公平就承受效率损失选择效率就承受不公平。承认这个局限与自己的无知可能比发明一个“完美”算法更重要。因为说到底我们是在用有限的观测、有偏的假设、互斥的目标去应对一个我们永远无法完全了解的世界。这不是技术问题这是认识论问题。这篇博客没有结论因为本来就没有结论。
