Long term behavior of dynamic equilibria in fluid queuing networks

Abstract

A fluid queuing network constitutes one of the simplest mod-els in which to study flow dynamics over a network. In this model wehave a single source-sink pair and each link has a per-time-unit capac-ity and a transit time. A dynamic equilibrium (or equilibrium flow overtime) is a flow pattern over time such that no flow particle has incentivesto unilaterally change its path. Although the model has been around foralmost fifty years, only recently results regarding existence and charac-terization of equilibria have been obtained. In particular the long termbehavior remains poorly understood. Our main result in this paper is toshow that, under a natural (and obviously necessary) condition on thequeuing capacity, a dynamic equilibrium reaches a steady state (afterwhich queue lengths remain constant) in finite time. Previously, it wasnot even known that queue lengths would remain bounded. The proofis based on the analysis of a rather non-obvious potential function thatturns out to be monotone along the evolution of the equilibrium. Fur-thermore, we show that the steady state is characterized as an optimalsolution of a certain linear program. When this program has a uniquesolution, which occurs generically, the long term behavior is completelypredictable. On the contrary, if the linear program has multiple solutionsthe steady state is more difficult to identify as it depends on the wholetemporal evolution of the equilibrium.