A Learning Approach to Minimum Delay Routing in Stochastic Queueing Networks

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.