A Learning Approach to Minimum Delay Routing in Stochastic Queueing Networks
A Learning Approach to Minimum Delay Routing in Stochastic Queueing Networks
复制标题
DOI：
10.1109/infocom53939.2023.10229039
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Xinzhe Fu;E. Modiano
中科院分区：
文献类型：
--
作者：
Xinzhe Fu;E. Modiano
考虑随机排队网络中的最小延迟路由问题，其目标是找到使网络平均延迟最小的最优静态路由策略。先前关于最小延迟路由的工作依赖于将路由策略映射到相应平均延迟的延迟函数的知识，由于延迟函数对网络链路分布特征的复杂依赖，这在随机排队网络中通常是不可用的。在本文中，我们提出了一种最小延迟路由问题的学习方法，即通过观察来学习延迟函数，而不是依赖于延迟函数的先验信息。我们设计了一种算法，利用网络队列长度的有限时间观测值来近似延迟函数的值，使用近似值来估计延迟函数的梯度，并基于估计的梯度执行梯度下降来优化路由策略。证明了当延迟函数为凸时，算法收敛于最优静态路由策略，这在实际设置中是合理的条件。我们进行了大量的模拟来评估我们的算法的经验性能，证明了它优于静态策略甚至动态策略（如join -the- short - queue和BackPressure）的延迟性能。
We consider the minimum delay routing problem in stochastic queueing networks where the goal is to find the optimal static routing policy that minimizes the average delay in the network. Previous works on minimum delay routing rely on knowledge of the delay function that maps the routing policies to their corresponding average delay, which is typically unavailable in stochastic queueing networks due to the complex dependency of the delay function on the distributional characteristics of network links. In this paper, we propose a learning approach to the minimum delay routing problem, whereby instead of relying on aprior information on the delay function, we seek to learn the delay function through observations. We design an algorithm that leverages finite-time observations of network queue lengths to approximate the values of the delay function, uses the approximate values to estimate the gradient of the delay function, and performs gradient descent based on the estimated gradient to optimize the routing policy. We prove that our algorithm converges to the optimal static routing policy when the delay function is convex, which is a reasonable condition in practical settings. We conduct extensive simulations to evaluate the empirical performance of our algorithm, demonstrating its superior delay performance over static policies and even dynamic policies such as Join-the-Shortest-Queue and BackPressure.