Model-Predictive Control for Discrete-Time Queueing Networks With Varying Topology

In this article, we equip the conventional discrete-time queueing network with a Markovian input process which, in addition to the usual short-term stochastics, governs the mid- to long-term behavior of the links between the network nodes. This is reminiscent of the so-called Jump-Markov Systems in control theory, allowing the network topology to change over time and, thus, facilitating to model a plethora of useful applications in wireless communication, traffic, or logistics. We argue that the common back-pressure control policy is inadequate to control such network dynamics and propose a novel control policy inspired by the paradigms of Model-Predictive Control. Specifically, by defining a suitable but arbitrary prediction horizon, our policy takes into account future network states and possible control actions. This stands in clear contrast to most other policies which are myopic, i.e., only consider the immediate next state. We show numerically that such an approach can significantly improve the control performance and introduce several variants of the policy, thereby trading off performance versus computational complexity. In addition, we prove so-called throughput optimality of our policy, which guarantees stability for all network flows that can be maintained by the network topology. Interestingly, in contrast to general stability proofs in model-predictive control, our proof does not require the assumption of a terminal set, i.e., the prediction horizon is not required to be large enough as to reach a predetermined set of states with special properties. Finally, we provide several illustrating examples, one of which being a network of assembly-queues. This network, in particular, constitutes an interesting system class for which our policy exerts superiority over general backpressure policies, with the latter ones even losing their throughput optimality.