阅读笔记 | RedTE: Mitigating Subsecond Traffic Bursts with Real-time and Distributed Traffic Engineering
Reading Notes - RedTE: Reducing Subsecond Traffic Pulses through Real-Time and Distributed Traffic Engineering.
- Gui F, Wang S, Li D, et al. RedTE旨在通过实时和分布式流量工程技术减少短时流量高峰[C]//Proceedings of the ACM SIGCOMM 2024 Conference. 2024: 71-85.
背景与动机
网络流量表现出明显的波动性特点，在传输过程中容易造成时延增加以及数据包丢失等问题。另一方面而言，在传统的传输要素（TE）体系中，默认采取的是集中式架构并长期覆盖广泛的时间范围，在这种架构下容易积累并导致控制循环内的时延积累现象出现；而针对那些需要处理分钟级别甚至小时级别粒度的数据流而言这一累积效应就显得尤为明显无法及时应对快速变化中的毫秒级别突发流量变化；为此我们希望能够通过发展分布式流量工程（dTE）来有效减少传统集中式流量工程在数据采集与规则表更新过程中的开销从而有效缓解整体系统的控制循环时延问题；与此同时尽管基于线性规划（LP）的方法在某些方面具有良好的性能但其计算复杂度较高这一限制因素也制约了其在实际应用中的扩展潜力；因此我们希望进一步探索基于分布式的机器学习（ML）方法尤其是多智能体强化学习（MARL）技术能够为路由器提供一种更加高效的决策机制让路由器基于本地信息自主决策从而显著降低系统运行中的控制循环时延水平
控制循环时延 ：TE系统的控制循环一般包含三个主要环节——信息收集、计算更新以及规则表更新——每个环节都会引入时延。其中信息收集阶段主要负责获取网络中的流量需求数据（例如整体网络架构中的全局流量矩阵或各路由器内部的具体流量需求报告）。计算更新阶段则用于生成新的规则表并将其应用到网络设备上；规则表更新阶段则负责将新的配置指令加载到相关设备中以执行新的管理逻辑。
突发流量及其缓解机制
因该应用具有的突发性质以及采用的TCP拥塞控制机制和网络栈执行批量操作指令等因素，在短时间内（10至100毫秒之间）可能会急剧上升流量速率，并导致路由器处理队列堆积进而影响针对延迟敏感的应用。
存在两种传统的缓解机制，在ISP领域这些机制的效果并不理想。为了应对突发流量问题，ISP必须拥有全局流量信息视野，并且能够对传输层和应用层的变化保持透明以应对突发流量变化的有效方案。
- 终端主机机制部署于upper layer or application layer，在路径拥塞时采用提前调整终端主机发送速率的工作原理。
- 设备本地流量管理器能够将流量分配至多条路径以避免链路过载；然而它会忽视全局流量模式而导致仅追求局部最优。
基于线性规划的TE系统
TE问题通常被建模为MCF问题。如Gurobi这类全局线性规划求解器被视为其经典的解决方案。常用MLU来评估TE算法的性能。
优缺点：
该方法在理论TE能力方面具有显著的表现。
通过延长计算环节的时延，在网络规模扩大时，计算环节的延迟会急剧增加。
基于机器学习的TE系统
强化学习在基于机器学习的TE系统中得到了广泛应用。
CMAS : 合作型多智能体系统，在这一系统中每个智能体以自主式学习为基础，并通过合作实现整体目标。（另一种MAS是非合作型多智能体系统）
unstable problem stems from CMAS, which in practical deployment may lead to non-cooperative behaviors. This is primarily due to existing multi-agent reinforcement learning (MARL) algorithms lacking effective mechanisms to evaluate the impact of individual agent actions on the global objectives and balancing local interests with global strategies.
未考虑信息采集延迟及规则表更新延迟的影响：机器学习过程通常包含两个阶段：训练阶段与推理阶段。其中训练阶段所需时间较长且可在离线环境中完成，在全局线性规划框架下运行的速度非常快。然而，在TE系统中减少计算延迟后，仍有其他两个关键延迟因素对整体性能构成瓶颈。
模型与方法
假设 ：
- ISP管理WAN路由器而不管理终端主机，在本文方法RedTE中其输入基于路由器数据平面统计流量信息。
- RedTE与控制平面其他协议如
BGP和RSVP正交；一旦确定候选路径 TE系统仅需分配各候选路径间的流量分配比例。 - 假设每个OD对之间存在至少一个候选路径（即k\geq1）。
Overview :
由控制器和边缘路由器构成的物理网络是RedTE系统的两大核心组成部分。该系统体现了云网协同的基本模式，在模拟环境中定期采集历史数据以进行离线训练的MARL代理（Agent）主要负责这一过程。同时，在线收集流量需求信息以上传至中心处理器的同时也会从中心处理器下载预先训练好的RL模型用于实时推理；SDN架构下的物理网络是RedTE系统的核心组成部分之一。每个RedTE路由器均会通过整合自身端点的 局部流量需求向量 、当前运行状态下的 局部链路利用率 以及当前带宽资源状况等关键指标来动态调整路径分配策略。
核心算法 :
基于Actor-Critic强化学习中的multi-agent deep deterministic policy gradient (MADDPG)算法对agents进行训练。其中全局critic网络采集模拟网络环境的整体信息并将其作为状态输入；随后将多个actor网络输出结果拼接后的路径划分比例作为动作输入，并通过计算动作价值Q(s,a)这一指标来指导actor网络更新其策略模型；而每个actor仅接收模拟网络中由其负责管理的部分路由器的局部数据（包括流量需求向量、链路利用率及链路带宽）作为状态输入，并训练其策略模型以决定相应的操作方案（即路径流量分配比例）。
该方法表明参数为θ_i的actor网络μ_i遵循策略梯度更新规则。其具体的策略梯度更新公式如下所示：
\nabla_{\theta_i} J(\mu_i) = E_{x, a \sim D}\left[\left.\nabla_{\theta_i} \mu_i(a_i \mid o_i) \cdot \nabla_{a_i} Q_w(x, a_1, \cdots, a_N)\right|_{a_i=\mu_i(o_i)}\right.
其中全局观测信息x由多个局部观测信息o₁,o₂,...,o_N构成；a₁,a₂,...,a_N分别代表各个agent的动作；Q_w是一个仅由单个actor进行训练的价值函数网络（即每个agent独立训练自己的全局critic）。
为了缩短规则表更新时间进而降低控制循环时延该系统引入了一种新型奖励函数：
r_i = -u_{\max} - \alpha \cdot \max_{i \in (1,N)} \left\{ \sum_{j=1}^N f(d_{i,j}) \right\}
其中u_{\max}代表MLU值d_{i,j}表示边(i,j)更新所涉及的规则表条目数量f(·)是一个将条目数量转换为时间代价的函数\alpha则为惩罚系数这种设计既能有效降低MLU值又能通过降低不必要的路径调整频率来优化规则表更新效率
此外，在追求算法收敛速度方面
实验与评估
文章主要进行了详细数值仿真研究，并在真实worldwide Area网络测试平台上的实验。深入分析了RedTE在控制循环时延和鲁棒性方面的性能表现，并通过计算最大链路利用率（MLU）和最大队列长度（MQL）等关键指标来评估算法性能。
模拟实验评估
拓扑：
- AMIW
- Colt
- KDL
- Viatel
数据：
- 2k个15分钟的packet trace segments，从WIDE网络收集，2018.1-2023.12
对比方案：
LP-based solutions
global LP
POP
ML-based solutions
- TEAL: 基于强化学习机制下的全局观测数据进行集中化的决策制定
- DOTE: 采用具有监督学习能力的深度神经网络模型
- TeXCP: 一种基于分布式架构设计的在线TE协议, 用于实现资源分配效率的最大化
实验设置：
- 在各拓扑结构中进行真实数据包的模拟运行
- 模拟运行过程中，在某台路由器上持续输出一个流量突增段长达500毫秒
此外, 以加快收敛为目标, 文章还应用了循环经验重放技术. 其具体操作为: 将每次输入控制器的连续流量矩阵序列分割为若干段, 并通过反复利用每一段用于训练直至取得成效后切换到下一段流量矩阵序列, 直到完成整个收敛过程. 作者将这一经验采样回放方式命名为 循环流量矩阵重放 。
实验与评估
该研究主要通过NS3平台进行的大规模仿真实验以及在实际网络测试环境下的实验验证。研究重点分析了RedTE协议在控制循环时延和抗干扰能力方面的性能表现，并通过最大链路利用率（MLU）和最大队列长度（MQL）等指标来量化评估其算法性能。
模拟实验评估
拓扑：
- AMIW
- Colt
- KDL
- Viatel
数据：
- 2k个15分钟的packet trace segments，从WIDE网络收集，2018.1-2023.12
对比方案：
LP-based solutions
global LP
POP
ML-based solutions
- TEAL: 该算法采用强化学习原理，在集中处理的基础上借助全局观测信息实现决策过程
- DOTE: 这种方法是通过有监督的深度学习模型来进行数据处理
- TeXCP: 这种协议旨在实现资源分配的实时均衡
实验设置：
- 基于真实packet运行模拟，在所有网络拓扑中进行测试。
- 在每个网络拓扑中运行模拟时，在某个路由器上连续产生500毫秒的流量突增。
