LINE is an open source solver for simulation and analytical solution of queueing models. The tool is developed by the QORE lab at Imperial College London and distributed under the BSD-3 license.

Getting started

PythonPython

Download IconDownload 3.0.7

MatlabMatlab

Download IconDownload 3.0.7

JavaJava

Download IconDownload 3.0.7

C++C++

Download IconDownload 3.0.7

Notes:

The integrated version including all four codebases can be downloaded from SourceForge.

The C++ port ships as source: unpack the archive and build it with ./make.sh at its root.

MCP Integration

LINE is available as a Model Context Protocol (MCP) server, enabling LLM tools to build and solve queueing models through natural language. Install with pip install line-solver, which puts a line-mcp command on your path for the client to launch, and see the MCP Getting Started Guide for details.

Acknowledgement

If you use LINE for a research paper, please cite the following article:

Supported Models

LINE supports 180 modeling features: node types (queues, delays, caches, fork-join, routers, Petri-net places and transitions), 39 scheduling disciplines (FCFS, LCFS, PS, priority variants, polling, order-independent), distributions (Erlang, hyperexponential, MAP, MMPP, phase-type, matrix-exponential, and the time-inhomogeneous MAPt and PHt), 7 cache replacement policies (RR, FIFO, SFIFO, LRU, h-LRU, CLIMB, q-LRU), finite capacity, impatience (balking, reneging), retrial queues, batch arrivals, server breakdowns and setup times, dependencies (load, class, joint), and layered network constructs.

LINE can evaluate several types of queueing models and systems, including:

  • M/M/1 queues
  • M/M/c multiserver queues
  • G/G/1 queues
  • G/G/c queues
  • Matrix analytic methods
    • M/G/1 queues
    • M/G/c queues
    • PH/PH/1 queues
    • ME/ME/1 queues
    • PH/PH/c queues
    • MAP/MAP/1 queues
    • MAP/MAP/c queues
    • RAP/RAP/1 queues
    • BMAP/BMAP/1 queues
  • BCMP product-form queueing networks
    • open
    • closed
    • mixed
    • load-dependent
    • class-dependent
    • class switching
  • Extended queueing networks
    • fork-join
    • priority
    • blocking
    • state-dependent routing
    • random environments
    • polling
    • finite-capacity regions
    • order-independent stations
    • retrial, balking and reneging
    • server breakdowns and setup times
  • G-networks with signals
    • negative customers
    • triggers and replies
    • catastrophes
  • Stochastic Petri nets
    • timed and immediate transitions
    • marking-dependent firing rates
    • queueing Petri nets
  • Loss networks with finite capacity and blocking
  • Cache models with LRU, FIFO, and other replacement policies
  • Layered networks
    • Layered queueing networks (LQN)
    • Layered cache-queueing models (LCQ)

Latest release

LINE 2.0.x user manual

Older releases

LINE 1.0.0 user manual

Solvers

Each solver page lists all methods, aliases, model restrictions and configuration fields. See shared solver options for common defaults and usage.

LINE Native Solvers

The following solvers are implemented natively in LINE:

Solver Description
AG Agent-based reversed-rate fixed points for cooperating processes and G-networks.
BA Throughput, queue-length and response-time bounds, including blocking and Petri-net relaxations.
CTMC Constructs and solves the underlying Markov chain using the global-balance equations and uniformization.
LDES Discrete-event simulator built on the SSJ library, available as a native C++ engine and as a Java engine. MATLAB and Python drive either through a JSON subprocess interface.
FLD Solves models using fluid/mean-field approximation based on ODEs.
MAM Applies matrix-analytic methods and parametric decomposition for quasi-birth-death processes.
MVA Implements exact and approximate mean value analysis for closed and mixed networks.
NC Computes performance metrics, including probability distributions, by estimating normalizing constants.
SSA Performs discrete-event simulation using Gillespie's algorithm and the next reaction method.

LINE Native Meta-Solvers

Meta-solvers analyze complex models by coordinating the execution of other solvers.

Solver Description
AUTO Automatically selects the most appropriate solver based on model characteristics.
ENV Analyzes queueing models operating in random environments with multiple operational stages.
LN Analyzes layered queueing networks using iterative decomposition.
UQ Quantifies parameter uncertainty by propagating a prior distribution through a model and aggregating the results into posterior performance metrics.

LINE Wrappers

LINE provides wrapper solvers that integrate external tools for specialized analysis:

Solver Description
JMT A wrapper for the Java Modelling Tools suite enabling execution of JMVA and JSIM.
LQNS A wrapper for the LQNS solver for layered queueing networks.
QNS A wrapper for the qnsolver library within the LQNS suite aimed at product-form network analysis.

External Tools Integration

LINE integrates with several external performance modeling tools to extend its analysis capabilities:

Tool Description Reference
BuTools A collection of tools for phase-type distributions and Markovian arrival processes developed at Budapest University of Technology. [22]
JMT Java Modelling Tools, an open-source suite for performance evaluation developed at Politecnico di Milano. LINE uses a custom build: JAR, sources. [4]
KPC-Toolbox A MATLAB toolbox for fitting Markovian Arrival Processes developed at William & Mary. [9]
MAMSolver A tool for matrix-analytic methods developed at William & Mary. [33]
Q-MAM A MATLAB toolbox for matrix-analytic methods in queueing theory developed at University of Antwerp. [29]
rmf_tool A library for computing refined mean field approximations for density-dependent population processes, developed at Inria by Nicolas Gast. [19]
SMCSolver A solver for structured Markov chains in queueing models developed at University of Pisa and University of Antwerp. [5]
SSJ A library for stochastic simulation developed at Université de Montréal. [25]

Interoperability

LINE supports cross-language execution, model transformations, and integration with external tools. See the Interoperability page.

Solver Details

CTMC (Continuous Time Markov Chain)

CTMC methods and configuration options

JMT (Java Modelling Tools)

JMT methods and configuration options

LN (Layered Network Solver)

LN methods and configuration options

LQNS (Layered Queueing Network Solver)

LQNS methods and configuration options

MAM (Matrix Analytic Methods)

MAM methods and configuration options

MVA (Mean Value Analysis)

MVA methods and configuration options

NC (Normalizing Constant)

NC methods and configuration options

QNS (Queueing Network Solver)

QNS methods and configuration options

SSA (Stochastic Simulation Algorithm)

SSA methods and configuration options

UQ (Uncertainty Quantification)

UQ methods and configuration options

Additional references: AG, BA, UQ and shared options.

References

  1. Afshari, S., Balbo, G., & Bruell, S. C. (1984). Load dependent servers in queueing networks. Performance Evaluation, 4(2), 85-100. https://doi.org/10.1016/0166-5316(84)90025-7
  2. Anderson, D. F. (2007). A modified next reaction method for simulating chemical systems with time dependent propensities and delays. The Journal of Chemical Physics, 127(21), 214107. https://doi.org/10.1063/1.2799998
  3. Balsamo, S., Dei Rossi, G.-L., & Marin, A. (2010). A Numerical Algorithm for the Solution of Product-Form Models with Infinite State Spaces. Proc. of EPEW 2010, LNCS, 6342, 191-206.
  4. Bertoli, M., Casale, G., & Serazzi, G. (2007). The JMT Simulator for Performance Evaluation of Non-Product-Form Queueing Networks. Proc. of the 40th Annual Simulation Symposium (ANSS), 3-10. https://doi.org/10.1109/ANSS.2007.35
  5. Bini, D. A., Meini, B., Steffé, S., & Van Houdt, B. (2005). Structured Markov chains solver: software tools. Proc. of SMCtools Workshop. https://doi.org/10.1145/1190366.1190370
  6. Bolch, G., Greiner, S., de Meer, H., & Trivedi, K. S. (2006). Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2nd ed.). Wiley-Interscience. https://onlinelibrary.wiley.com/doi/book/10.1002/0471200581
  7. Casale, G., Muntz, R. R., & Serazzi, G. (2008). Geometric Bounds: A Noniterative Analysis Technique for Closed Queueing Networks. IEEE Transactions on Computers, 57(6), 780-794. https://doi.org/10.1109/TC.2008.37
  8. Casale, G. (2009). CoMoM: Efficient Class-Oriented Evaluation of Multiclass Performance Models. IEEE Transactions on Software Engineering, 35(2), 162-177. https://doi.org/10.1109/TSE.2008.63
  9. Casale, G., Zhang, E. Z., & Smirni, E. (2008). KPC-toolbox: Simple yet effective trace fitting using Markovian arrival processes. Proc. of Fifth International Conference on Quantitative Evaluation of Systems (QEST), 83-92. https://doi.org/10.1109/QEST.2008.33
  10. Casale, G., Pérez, J. F., & Wang, W. (2015). QD-AMVA: Evaluating Systems with Queue-Dependent Service Requirements. Proceedings of IFIP PERFORMANCE. https://dl.acm.org/doi/10.1145/2825236.2825251
  11. Casale, G. (2017). Accelerating Performance Inference over Closed Systems by Asymptotic Methods. Proc. of ACM SIGMETRICS. https://dl.acm.org/doi/10.1145/3078505.3078512
  12. Casale, G. (2020). Integrated performance evaluation of extended queueing network models with LINE. In Proceedings of the 2020 Winter Simulation Conference (WSC) (pp. 1-15). https://doi.org/10.1109/WSC48552.2020.9383931
  13. Casale, G., Harrison, P. G., & Hong, O. W. (2021). Facilitating Load-Dependent Queueing Analysis Through Factorization. Performance Evaluation. https://doi.org/10.1016/j.peva.2021.102203
  14. Chandy, K. M., & Neuse, D. (1982). Linearizer: a heuristic algorithm for queueing network models of computing systems. Communications of the ACM, 25(2), 126-134. https://dl.acm.org/doi/10.1145/358396.358403
  15. Chow, W.-M. (1983). Approximations for large scale closed queueing networks. Performance Evaluation, 3(1), 1-12. https://doi.org/10.1016/0166-5316(83)90013-0
  16. Conway, A. E., & Georganas, N. D. (1986). RECAL: A new efficient algorithm for the exact analysis of multiple-chain queueing networks. Journal of the ACM, 33(2), 356-386. https://doi.org/10.1145/6490.6495
  17. de Souza e Silva, E., & Muntz, R. R. (1990). A Note on the Computational Cost of the Linearizer Algorithm for Queueing Networks. IEEE Transactions on Computers, 39(6), 840-842. https://doi.org/10.1109/12.53607
  18. Gillespie, D. T. (1977). Exact stochastic simulation of coupled chemical reactions. The Journal of Physical Chemistry, 81(25), 2340-2361. https://doi.org/10.1021/j100540a008
  19. Gast, N. (2017). Expected Values Estimated via Mean-Field Approximation are 1/N-Accurate. Proc. ACM Meas. Anal. Comput. Syst., 1(1), Article 17. https://doi.org/10.1145/3084454
  20. Harel, A., Namn, S., & Sturm, J. (1999). Simple bounds for closed queueing networks. Queueing Systems, 31(1-2), 125-135. https://doi.org/10.1023/a:1019102112869
  21. Horváth, G., & Telek, M. (2014). Sojourn times in fluid queues with independent and dependent input and output processes. Performance Evaluation, 79, 160-181. https://doi.org/10.1016/j.peva.2014.07.011
  22. Horváth, G., & Telek, M. (2017). BuTools 2: A Rich Toolbox for Markovian Performance Evaluation. Proc. of VALUETOOLS, 137-142. https://doi.org/10.4108/eai.25-10-2016.2266400
  23. Knessl, C., & Tier, C. (1992). Asymptotic Expansions for Large Closed Queueing Networks with Multiple Job Classes. IEEE Transactions on Computers, 41(4), 480-488. https://doi.org/10.1109/12.135560
  24. Latouche, G., & Ramaswami, V. (2000). Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM. https://link.springer.com/book/10.1007/978-0-387-22765-9
  25. L'Ecuyer, P., & Buist, E. (2005). Simulation in Java with SSJ. Proc. of the 2005 Winter Simulation Conference, 611-620. https://doi.org/10.1109/WSC.2005.1574309
  26. Li, Z., & Casale, G. (2024). Matrix Network Analyzer: A New Decomposition Algorithm for Phase-type Queueing Networks. Proc. of ACM/SPEC ICPE, 77-88. https://doi.org/10.1145/3629527.3651431
  27. Marin, A., & Bulò, S. R. (2009). A general algorithm to compute the steady-state solution of product-form cooperating Markov chains. Proc. of MASCOTS 2009, 515-524.
  28. McKenna, J., & Mitra, D. (1984). Asymptotic Expansions and Integral Representations of Moments of Queue Lengths in Closed Markovian Networks. Journal of the ACM, 31(2), 346-360. https://doi.org/10.1145/800057.808676
  29. Pérez, J. F., Van Velthoven, J., & Van Houdt, B. (2008). Q-MAM: A Tool for Solving Infinite Queues using Matrix-Analytic Methods. Proc. of 3rd International ICST Workshop on Tools for solving Structured Markov Chains (SMCtools). https://doi.org/10.4108/ICST.VALUETOOLS2008.4368
  30. Pérez, J. F., & Casale, G. (2017). LINE: Evaluating Software Applications in Unreliable Environments. IEEE Transactions on Reliability, 66(3), 837-853. https://doi.org/10.1109/TR.2017.2655505
  31. Reiser, M., & Lavenberg, S. S. (1980). Mean-value analysis of closed multichain queuing networks. Journal of the ACM, 27(2), 313-322. https://dl.acm.org/doi/10.1145/322186.322195
  32. Reiser, M. (1981). Mean-value analysis and convolution method for queue-dependent servers in closed queueing networks. Performance Evaluation, 1(1), 7-18. https://doi.org/10.1016/0166-5316(81)90003-8
  33. Riska, A., & Smirni, E. (2007). ETAQA Solutions for Infinite Markov Processes with Repetitive Structure. INFORMS Journal of Computing, 19(2), 215-228. https://doi.org/10.1287/ijoc.1060.0184
  34. Robertazzi, T. G. (2000). Computer Networks and Systems: Queueing Theory and Performance Evaluation (3rd ed.). Springer. https://link.springer.com/book/10.1007/978-0-387-22765-9
  35. Ruuskanen, J., Berner, T., Årzén, K.-E., & Cervin, A. (2021). Improving the mean-field fluid model of processor sharing queueing networks for dynamic performance models in cloud computing. Performance Evaluation, 151, 102231. https://doi.org/10.1016/j.peva.2021.102231
  36. Wang, W., Casale, G., & Sutton, C. A. (2016). A Bayesian Approach to Parameter Inference in Queueing Networks. ACM Transactions on Modeling and Computer Simulation, 27(1), 2:1-2:26. https://doi.org/10.1145/2893480
  37. Zahorjan, J., Eager, D. L., & Sweillam, H. M. (1988). Accuracy, Speed, and Convergence of Approximate Mean Value Analysis. Performance Evaluation, 8(4), 255-270. https://doi.org/10.1016/0166-5316(88)90018-1

← Back to Solvers Overview

Documentation

PythonPython

MatlabMatlab

JavaJava

C++C++

Language-independent: MCP Getting Started PDF