Dynamic Equilibria in Fluid Queuing Networks

Roberto Cominetti, José Correa, Omar LarréarXiv 2014 · DOI · arXiv

Abstract

This paper continues the study of equilibria for flows over time in the fluid queueing model recently considered by Koch and Skutella [10]. We provide a constructive proof for the existence and uniqueness of equilibria in the case of a single origin-destination with piecewise constant inflow rates, through a detailed analysis of the static flows obtained as derivatives of a dynamic equilibrium. We also give a nonconstructive existence proof of equilibria when the inflow rates belong to $L^p$ including the extension to multiple origin-destinations.

Introduction

In real-world networks like urban traffic or the Internet, "steady-state" flow is a myth; conditions change by the second. To capture these dynamics, researchers use Flows Over Time models. A particularly challenging model is the fluid queuing model, where each edge has a fixed travel time (latency) and a maximum capacity. If flow arrives faster than the capacity, a queue forms, adding to the total travel time.

The goal is to find a Dynamic Equilibrium (DE)—a state where no "particle" of flow can reduce its arrival time at the destination by switching paths. While previous work had made strides, there was a lack of constructive proofs (algorithms to actually find the equilibrium) and a lack of clarity on whether these equilibria were unique. This paper fills those gaps.

The Fluid Queuing Model

The paper utilizes a hand-crafted network example to illustrate the mechanics of the fluid queuing model and the nuances of dynamic equilibria.

Figure 1: A sample network with nodes $s, r, t$ and edges defined by capacities $\nu$ and latencies $\tau$. This example is used to differentiate between 'strong' and 'standard' dynamic equilibria.

In this model, each edge $e$ has a capacity $\nu_e$ and a free-flow travel time $\tau_e$. If the flow rate into an edge exceeds its capacity, a queue forms at the entrance. The total time to traverse the edge is then $\tau_e$ plus the time spent in the queue. The paper delivers the first constructive proof for the existence and uniqueness of these equilibria in networks with piecewise constant inflow, while also extending existence results to more general flow conditions and multiple origin-destination pairs.

Methodology

The authors bridge the gap between complex dynamic systems and simpler static models by focusing on the derivatives of the flow.

  1. Thin Flows with Resetting: They utilize the concept of "thin flows," which describe how the equilibrium evolves at a specific instant. They refine this by adding a normalization condition, which is crucial for proving uniqueness.
  2. Fixed Point Theory: To prove that these normalized thin flows actually exist, the authors employ Kakutani’s Fixed Point Theorem. They show that finding a thin flow is equivalent to finding a fixed point in a specific set-valued map.
  3. Integration: By "stitching" these instantaneous thin flows together through integration, they reconstruct the full dynamic equilibrium over time.
  4. Variational Inequalities: For the more general case where inflow rates are less predictable (belonging to $L^p$ spaces), they use a non-constructive approach based on variational inequalities to prove that an equilibrium must exist.

Key Insights and Ideas

  • The Power of Derivatives: The most significant insight is that a complex, time-varying equilibrium can be characterized by a sequence of static "thin flow" problems. If you know how the system wants to change at any given micro-second, you can build the entire timeline.
  • Normalization is the Missing Piece: Previous definitions of thin flows led to ambiguities. By introducing a normalization condition, the authors ensured that the "labels" (which represent the rate of change in travel time) are unique.
  • Queue Logic: The paper proves a vital intuition: at equilibrium, any edge with a physical queue must be part of a current shortest path. If it weren't, selfish agents would have already stopped using it.
  • Complexity Class: The authors identify that finding a normalized thin flow belongs to the PPAD complexity class. This places the problem in the same neighborhood as finding Nash Equilibria in traditional game theory.

Key Results

  • Constructive Existence: For a single origin-destination pair with piecewise constant inflow, the authors provide an algorithmic way to build the dynamic equilibrium.
  • Uniqueness: They prove that the "earliest-time functions" (when flow reaches certain points) are unique for all right-continuous dynamic equilibria.
  • Algorithmic Foundation: The paper suggests an exponential-time algorithm to compute these flows by guessing "active" sets of links and solving the resulting linear programs.
  • Generalization: The existence of dynamic equilibria is proven for multiple origin-destination pairs and for inflow rates that are merely $p$-integrable ($L^p$), significantly broadening the scope of the theory.

Limitations and Future Work

  • Computational Efficiency: While the paper provides a constructive proof, the resulting algorithm is exponential in time. The authors conjecture that a polynomial-time algorithm might exist.
  • Steady-State Convergence: It remains an open question whether these networks eventually reach a steady state if the inflow becomes constant, or if they can oscillate indefinitely.
  • Bounded Queues: The authors mention a difficult conjecture: do queue sizes stay bounded as long as the network's total capacity is larger than the inflow?
  • Numerical Implementation: Moving from piecewise constant inflows to general $L^p$ inflows in a constructive way is difficult because the "thin flow" map is discontinuous, making standard differential equation solvers hard to apply.

Summary updated

Abstract

This paper continues the study of equilibria for flows over time in the fluid queueing model recently considered by Koch and Skutella [10]. We provide a constructive proof for the existence and uniqueness of equilibria in the case of a single origin-destination with piecewise constant inflow rates, through a detailed analysis of the static flows obtained as derivatives of a dynamic equilibrium. We also give a nonconstructive existence proof of equilibria when the inflow rates belong to $L^p$ including the extension to multiple origin-destinations.
BibTeX
@misc{cominetti2014dynamic,
  author = {Roberto Cominetti and José Correa and Omar Larré},
  title = {{Dynamic Equilibria in Fluid Queuing Networks}},
  year = {2014},
  eprint = {1401.6914},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.6914},
}
Figure