Mitigating network congestion

Carolina Osorio2010 · DOI

Abstract

Congestion is a pervasive phenomenon across diverse domains, from urban traffic and hospital bed management to cellular-level protein synthesis. This paper presents an analytical framework based on finite capacity queueing theory designed to identify and quantify network congestion. By introducing a novel state space formulation, the model provides a detailed decomposition of congestion into its sources, propagation, and dissipation rates. Validated against simulation and exact results, the framework is applied to optimize traffic signal plans in Lausanne, Switzerland, manage patient flow in Geneva, and model ribosome traffic. The results demonstrate significant improvements in performance measures and computational efficiency compared to traditional methods.

1. Introduction

Congestion arises whenever demand for a resource exceeds its capacity. While most visible in urban traffic, it equally affects prison systems, hospital wards, and biological processes. Effective management requires mathematical models that are both realistic—capturing intricate traffic interactions—and computationally tractable for use in optimization frameworks. This work addresses the gap between high-fidelity but expensive microscopic simulations and efficient but overly simplified macroscopic models.

2. Modeling Finite Capacity Networks

The core innovation of this research is a network model based on finite capacity queueing theory (FCQN). Unlike standard queueing models that assume infinite buffer space, this approach explicitly accounts for "blocking-after-service." In this state, a job (e.g., a vehicle or patient) that has completed service cannot move to the next node because that node is full, thereby occupying the current server and preventing it from processing subsequent jobs.

The model utilizes a novel state space formulation and structural parameters to describe congestion. Key features include:

  • Exogenous Topology and Capacity: Unlike previous approximations, the network structure and queue capacities are fixed inputs, ensuring stability during optimization.
  • Detailed Decomposition: Congestion is analyzed through its frequency, duration, and propagation/dissipation rates.
  • Scalability: For large-scale applications, the model can be reduced from $6n$ to $3n$ equations without significant loss of accuracy, making it suitable for entire city networks.

3. Optimization via Hybrid Metamodeling

To bridge the gap between analytical models and realistic simulations, a simulation-based optimization framework was developed. It employs a hybrid metamodel that combines a physical metamodel (structural information derived from the analytical queueing model) with a functional metamodel (general-purpose quadratic polynomials used in traditional derivative-free trust region algorithms).

This combination allows the optimizer to find high-performing solutions with a very limited computational budget. By "seeding" the optimizer with the structural logic of queueing theory, the system can identify good traffic signal plans almost immediately, overcoming the need for a substantial initial sample of simulation runs.

4. Domain Applications

4.1 Urban Traffic Control

The model was applied to the road network of Lausanne, Switzerland, using a calibrated microscopic simulation covering 652 roads and 231 intersections. By treating road segments as finite buffers, the model analytically captures "spillbacks"—where a queue at one intersection blocks the upstream intersection. Optimization of traffic signal plans using this framework delayed congestion propagation and improved travel times compared to existing city plans and standard engineering methods like Webster’s.

4.2 Healthcare Systems

In collaboration with the Geneva University Hospitals (HUG), the model investigated "bed blocking" in operative and post-operative units using data from over 25,000 patient records. The study identified three primary sources of blocking and quantified how even low-probability blocking events (e.g., 3%) can lead to significant resource tie-ups, such as 11% of beds in recovery rooms being occupied by blocked patients. This responds to a critical need for methods that quantify in-patient bed blocking.

4.3 Protein Synthesis

At the cellular scale, the traffic of ribosomes along mRNA strands was modeled as a system of linear and quadratic equations. This formulation proved numerically stable even in highly congested scenarios where previous models often became ill-conditioned. It provides a scalable tool for studying large-scale protein synthesis networks using simple numerical techniques.

5. Conclusion and Future Directions

The research demonstrates that integrating structural queueing logic into optimization frameworks significantly enhances the management of congested networks. Future work aims to extend the model to capture transient (time-varying) behavior during peak periods and to explore higher-order decompositions that capture local correlations between adjacent queues more accurately.

Reference: Osorio Pizano, C. (2010). Mitigating Network Congestion: Analytical Models, Optimization Methods and their Applications. PhD Thesis, École Polytechnique Fédérale de Lausanne.

Summary updated

Abstract

Congestion is a phenomenon that arises in a variety of contexts. The most familiar representation is urban traffic congestion. Nonetheless, phenomenons such as prison cell congestion, hospital bed blocking or, at a cellular scale, ribosome congestion, also arise and affect the performance of the underlying networks. The study of network congestion is therefore of interest in numerous application fields. Analytical mathematical models enable the identification and the quantification of network congestion. Furthermore, these methods can be used to identify strategies that mitigate network congestion, by integrating them within optimization frameworks. Deriving such models is an intricate task. Congested networks involve complex traffic interactions. Providing an analytical description of these intricate interactions is challenging. Furthermore, to identify traffic management strategies that indeed mitigate congestion, these models need to be realistic representations of the underlying process, while remaining computationally tractable such that efficient and operational optimization methods can be derived. This thesis presents an analytical network model based on finite capacity queueing theory. Through a novel state space formulation and the use of structural parameters, the model provides a detailed decomposition of congestion. It describes congestion in terms of its sources, its propagation and dissipation rates as well as its frequency. The model is validated versus existing methods, exact results and simulation results. Particularly tractable formulations are derived for single server bufferless queues in a tandem topology and for single server queues with finite buffers in an arbitrary topology network. Unlike existing models, the proposed model maintains the network topology and the queue capacities exogenous. An urban vehicle traffic model is formulated based on this network model. A detailed formulation, based on national transportation standards, is provided. This model is then used to perform optimization for congested road networks. A traffic signal control problem is formulated and solved for the Lausanne city road network. The signal plans derived are evaluated at the microscopic scale with a calibrated simulation model, and compared to both an existing signal plan for the city of Lausanne and to signal plans derived by other methods. The proposed plans delay the propagation of congestion, and lead to improved performance measures. The contributions in the urban transportation field are two-fold. Firstly, the proposed model considers a set of intersections and analytically captures the interactions between queues, contrarily to existing analytic queueing models for urban networks which are formulated for a single intersection, and thus do not take such interactions into account. Secondly, although there is a great variety of signal control methodologies in the literature, there is still a need for solutions that are appropriate and efficient under saturated conditions, where the performance of signal control strategies and the formation and propagation of queues are strongly related. To the best of our knowledge, the existing strategies have not taken urban spillbacks analytically into account. A framework to perform simulation-based optimization, which combines structural information from the analytical queueing model and microscopic information from an urban traffic simulation model for the city of Lausanne, is presented. The framework resorts to a derivative-free trust region algorithm. It is used to solve a traffic signal control problem. With this method well-performing signal plans can be identified given a tight computational budget. By combining a traditionally used functional metamodel with an applicationspecific analytical structural model, this algorithm overcomes the need for a substantial initial sample, and provides meaningful trial points since the very first iterations. A network model is also formulated and used to evaluate congestion for two other applications. Firstly, the phenomenon of bed blocking in a network of operative and post-operative units of the Geneva University Hospitals is investigated. Three main sources of bed blocking are identified, and their impact upon the different hospital units is quantified. We go beyond existing analytical queueing methods that have been used in the health care sector by allowing for networks with an arbitrary topology and with an arbitrary number of queues with finite capacity. Furthermore, the detailed performance measures provided by this approach respond to a recently stated need for methods that quantify in-patient bed blocking. Secondly, the model is formulated for a protein synthesis network, where the traffic of ribosomes along mRNA (messenger ribonucleic acid) strands is of interest. This protein synthesis model consists of a system of linear and quadratic equations, which is a particularly simple and tractable formulation. Unlike other protein synthesis models, this formulation is numerically well-conditioned for highly congested scenarios, suitable for large-scale instances, and can be evaluated using simple numerical techniques.
BibTeX
@misc{osorio2010mitigating,
  author = {Carolina Osorio},
  title = {{Mitigating network congestion}},
  year = {2010},
  doi = {10.5075/epfl-thesis-4615},
}
Figure