What is LINE?

LINE is an open-source software package to analyze queueing models via analytical methods or simulation. The package is developed by the QORE lab at Imperial College London and distributed under the BSD-3 license.

The package offers solution algorithms for:

  • Queueing systems (e.g., M/M/1, M/M/k, M/G/1, ...)
  • Queueing networks
  • Layered queueing networks
  • Queueing models in random environments

Models are solved in LINE either natively or via external solvers, such as JMT, LQNS, Q-MAM, SMCSolver, and BuTools.

Getting started

Download Icon Download integrated release (for Java/Kotlin, Matlab, and Python)

Manuals: Manual IconJava  Kotlin IconKotlin  Matlab IconMatlab  Python IconPython  PDF IconCheatsheet

API reference: Java IconJavadoc  Matlab IconDoxygen  Python IconSphinx

Acknowledgement

If you use LINE for a research paper, you are asked to cite the following article:

The development of LINE has been partially funded by the European Commission grants FP7-318484 (MODAClouds), H2020-644869 (DICE), H2020-825040 (RADON), and by the EPSRC grant EP/M009211/1 (OptiMAM).

Latest release

LINE 2.0.x user manual

Older releases

LINE 1.0.0 user manual

Resources

This page lists useful resources such as manuals, publications and public presentations.

Manuals

API Reference

Cheatsheet

Papers

If you use LINE for a research paper, you are asked to cite the following article:

The following papers extend or use LINE across different applications:

Solvers

LINE provides multiple solution methods for queueing models. See the detailed solver reference for algorithm options and references.

LINE Native Solvers

The following solvers are implemented natively in LINE:

  • AUTO - Automatically selects the most appropriate solver based on model characteristics.
  • CTMC (Continuous Time Markov Chain) - Constructs and solves the underlying Markov chain. Provides exact solutions for finite state spaces, supporting priorities and non-product-form behaviors.
  • DES (Discrete Event Simulation) - Java-based discrete-event simulator using SSJ library. Supports open networks with FCFS queues, delay nodes, multiserver stations, and multiclass workloads (JAR only).
  • Fluid - Solves models using fluid approximation based on ODEs. Effective for transient analysis and large populations.
  • MAM (Matrix Analytic Methods) - Applies matrix-analytic techniques for phase-type distributions and quasi-birth-death processes. Handles non-exponential service times efficiently.
  • MVA (Mean Value Analysis) - Implements exact and approximate mean value analysis for closed and mixed networks. Typically the fastest analytical solver for product-form networks.
  • NC (Normalizing Constant) - Computes normalizing constants for product-form networks using convolution and LNICE algorithms. Suitable when MVA approximations lack precision.
  • SSA (Stochastic Simulation Algorithm) - Performs discrete-event simulation using Gillespie's algorithm. Provides statistically accurate estimates with confidence intervals for intractable models.

LINE Wrappers

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

  • JMT (Java Modelling Tools) - A wrapper for the Java Modelling Tools suite providing model-to-model transformation into JMT's input XML formats. Supports both discrete-event simulation via JSIM and mean value analysis via JMVA.
  • LQNS (Layered Queueing Network Solver) - A wrapper for the LQNS solver for layered queueing networks. Provides analytical solution of complex software architectures with multiple layers of service.
  • QNS (Queueing Network Solver) - A native solver implementation for queueing network analysis with support for extended network features. Supports both exact and approximate analysis methods.

External Tools Integration

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

  • BuTools - A collection of tools for phase-type distributions and Markovian arrival processes developed at Budapest University of Technology. LINE uses BuTools for fitting distributions and performing matrix-analytic computations.
  • KPC-Toolbox - A MATLAB toolbox for fitting Markovian Arrival Processes developed at William & Mary. Provides automatic trace fitting capabilities using best-fit recipes for MAP characterization.
  • SSJ (Stochastic Simulation in Java) - A library for stochastic simulation developed at Université de Montréal. Used by the DES solver in LINE for discrete-event simulation capabilities.
  • Q-MAM - A MATLAB toolbox for matrix-analytic methods in queueing theory developed at University of Antwerp. Provides algorithms for analyzing queueing models with phase-type distributions and quasi-birth-death processes.
  • SMCSolver - A solver for structured Markov chains in queueing models developed at University of Pisa and University of Antwerp. Provides efficient algorithms for computing the stationary distribution of quasi-birth-death processes and related structured Markov chains.

Solver Details

AUTO

The AUTO solver (callable also as LINE) offers automatic choice of the other solvers implemented in LINE (CTMC, NC, MVA, etc.). Presently it relies on custom heuristics based on known features of the algorithms.

MethodAlgorithmReference
defaultAutomatic solver and method selection—

CTMC (Continuous Time Markov Chain)

The CTMC solver analyzes models by first generating the infinitesimal generator of the network and then solving the global balance equations for steady-state analysis. Transient analysis is carried out by numerically solving Kolmogorov's forward equations and value iteration for transient rewards. For models with infinite states, such as open networks, the cutoff option can be used to truncate the state space.

MethodAlgorithmReference
defaultSteady-state solution via global balance[4]
transientKolmogorov forward equations[4]

DES (Discrete Event Simulation)

The DES solver is a Java-based discrete-event simulator that uses the SSJ (Stochastic Simulation in Java) library. It has a similar support as JMT in terms of models, but it is lighter and thus tends to run faster. A wrapper to call DES is available both in MATLAB and Python.

MethodAlgorithmReference
defaultDiscrete-event simulation via SSJ—

Fluid

The Fluid solver is based on a system of ordinary differential equations (ODEs) that provide mean-field approximations for queueing networks. The approach is grounded in Kurtz's mean-field approximation theory and is particularly effective for transient analysis and models with large job populations.

MethodAlgorithmReference
default / matrixODE-based mean field approximations[22], [26]
statedepKurtz's mean field ODEs for closed models[22]
closingFluid with closing method for open classes[4]
softminSmoothed statedep with softmin functions—

JMT (Java Modelling Tools)

The JMT solver is a wrapper for the Java Modelling Tools suite [3], providing model-to-model transformation from LINE's data structures into JMT's input XML formats. It supports both discrete-event simulation via JSIM and mean value analysis via JMVA.

MethodAlgorithmReference
jsimDiscrete-event simulation in JSIM[3]
jmva.mvaExact MVA in JMVA[23]
jmva.recalRECAL algorithm (exact)[13]
jmva.comomCoMoM algorithm (exact)[6]
jmva.bsBard-Schweitzer (approximate)[4]
jmva.linLinearizer (approximate)[11]
jmva.dmlinDe Souza-Muntz Linearizer[14]
jmva.chowChow algorithm[12]
jmva.aqlAggregate Queue Length (AQL)[28]
jmva.lsLogistic sampling[8]

LQNS (Layered Queueing Network Solver)

The LQNS wrapper integrates the Layered Queueing Network Solver developed by the RADS group at Carleton University. LINE automatically exports network models to LQNS format, invokes the external LQNS tool, and imports the results back into LINE's data structures.

MethodAlgorithmReference
defaultLQNS default analytical solver—
lqnsLQNS exact analytical solution—
srvnStochastic Rendezvous Network (SRVN) analysis—
exactmvaExact Mean Value Analysis for layered networks—
srvn.exactmvaSRVN with exact MVA solution—
simStochastic simulation of layered queueing networks—
lqsimLQNS simulator (lqsim)—
lqnsdefaultLQNS default behavior with implicit method selection—

QNS (Queueing Network Solver)

The QNS wrapper exposes the corresponding tool for product-form queueing network analysis in the Layered Queueing Network Solver developed by the RADS group at Carleton University. Unlike the LQNS solver, QNS models are ordinary (non-layered) queueing networks.

MethodAlgorithmReference
defaultQNS default method with automatic selection—
conwayConway's multi-server—
roliaRolia-Sevcik multi-server—
zhouZhou-Woodside multi-server—
reiserReiser-Lavenberg exact mean value analysis—

MAM (Matrix Analytic Methods)

The MAM solver analyzes Markovian open queueing systems using matrix-analytic methods. The core solver is built on top of the BuTools library [17], Q-MAM, and SMCSolver. Native algorithms for parametric decomposition of queueing networks are integrated with this solver.

MethodAlgorithmReference
defaultMatrix-analytic solution of structured QBDs[17]
dec.mnaMatrix Network Analyzer decomposition[20]
dec.sourceDecomposition with source-like arrivals—
dec.poissonDecomposition with Poisson arrival flows—

MVA (Mean Value Analysis)

The MVA solver implements both exact and approximate mean value analysis algorithms for product-form queueing networks. The default method uses Linearizer for approximate MVA, with support for extended queueing features including non-exponential service times, multi-servers, non-preemptive priorities, and fork-join networks.

MethodAlgorithmReference
mvaExact mean value analysis[23]
bsBard-Schweitzer approximate MVA[4]
linLinearizer heuristic[11]
qdQueue-dependent approximate MVA[7]
qdlinQueue-dependent Linearizer—
aba.upper/lowerAsymptotic bound analysis[4]
bjb.upper/lowerBalanced job bounds[5]
gb.upper/lowerGeometric square-root bounds[5]
pb.upper/lowerProportional bounds[5]
sb.upper/lowerSimple bounds[16]
mm1Exact M/M/1 formula[4]
mmkErlang-C formula (M/M/k)—
mg1Pollaczek-Khinchine (M/G/1)[4]
gig1.kingmanKingman upper bound (GI/G/1)[4]
gig1.allenAllen-Cunneen formula (GI/G/1)[4]
gig1.klbKrämer-Langenbach-Belz (GI/G/1)[4]
gig1.kobayashiKobayashi diffusion approx. (GI/G/1)[4]
gig1.marchalMarchal formula (GI/G/1)[4]

NC (Normalizing Constant)

The NC solver implements algorithms based on the normalizing constant of product-form queueing networks. Unlike other solvers, NC is able to compute state and marginal probabilities in queueing networks without the need for simulation. It also offers the most accurate approximations for models including caches.

MethodAlgorithmReference
caMulticlass convolution algorithm (exact)—
comomClass-oriented method of moments (exact)[6]
mvaProduct of throughputs on MVA lattice (exact)[24]
leLogistic asymptotic expansion[8]
ktKnessl-Tier asymptotic expansion[18]
panaceaPanacea asymptotic expansion[21], [25]
lsLogistic sampling (Monte Carlo)[8]
cubGrundmann-Moeller cubature rules[8]
imciImproved Monte Carlo integration[27]
nr.logitNörlund-Rice integral (logit transform)[10]
nr.probitNörlund-Rice integral (probit transform)[10]
rdReduction heuristic[10]

SSA (Stochastic Simulation Algorithm)

The SSA solver is a stochastic simulator for continuous-time Markov chains. The state space is not generated upfront but is built during simulation starting from the initial state. The solver offers both serial and parallel execution modes, with the latter supporting independent replications across multiple cores.

MethodAlgorithmReference
serialGillespie's direct method (single core)[15]
nrmNext Reaction Method[2]
paraParallel independent replications—

Bibliography

  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. Bertoli, M., Casale, G., & Serazzi, G. (2007). JMT: Performance evaluation software. ACM SIGMETRICS Performance Evaluation Review, 35(1), 10-15. https://doi.org/10.1109/ANSS.2007.35
  4. 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
  5. Casale, G., Muntz, R. R., & Serazzi, G. (2008). Geometric bounds on queueing systems. IEEE Transactions on Computers, 57(4), 508-521. https://doi.org/10.1109/TC.2008.37
  6. Casale, G. (2009). CoMoM: A class-oriented method of moments for queueing networks. IEEE Transactions on Software Engineering, 35(5), 692-709. https://doi.org/10.1109/TSE.2008.63
  7. Casale, G., Pérez, J. F., & Wang, W. (2015). Deconvolving system load from queue length snapshots. Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 159-171. https://dl.acm.org/doi/10.1145/2825236.2825251
  8. Casale, G. (2017). Analytical modelling of data-parallel applications on asymmetric multicore processors. In 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS) (pp. 2330-2336). https://dl.acm.org/doi/10.1145/3078505.3078512
  9. 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
  10. Casale, G., Harrison, P. G., & Hong, Z. (2021). An efficient algorithm for the Nörlund-Rice integral with application to rare event simulation. Performance Evaluation, 150, 102203. https://doi.org/10.1016/j.peva.2021.102203
  11. 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
  12. Chow, W. M. (1983). The cycle time distribution of exponential queueing networks. Performance Evaluation, 3(4), 220-230. https://doi.org/10.1016/0166-5316(83)90013-0
  13. 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
  14. de Souza e Silva, E. G., & Muntz, R. R. (1990). Approximate solutions for a class of non-product-form queueing networks. Performance Evaluation, 12(4), 221-235. https://doi.org/10.1109/12.53607
  15. 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
  16. Harel, A., Namn, S. M., & Sturm, R. (1999). Performance and reliability of communication networks. Kluwer Academic Publishers. https://doi.org/10.1023/a:1019102112869
  17. Horváth, G., & Telek, M. (2017). BuTools: Burstiness and heavy traffic modeling. IEEE Communications Surveys & Tutorials. https://doi.org/10.4108/eai.25-10-2016.2266400
  18. Knessl, C., & Tier, C. (1992). Asymptotic approximations for queueing systems. IEEE Transactions on Computers, 41(6), 771-790. https://doi.org/10.1109/12.135560
  19. 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
  20. Li, X., & Casale, G. (2024). Matrix Network Analyzer: Compositional queueing network analysis. Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. https://doi.org/10.1145/3629527.3651431
  21. McKenna, J., & Mitra, D. (1984). Asymptotic expansions and integral representations of moments of queue lengths in M/G/1 queues with server vacations. Journal of the ACM, 31(2), 346-360. https://doi.org/10.1145/800057.808676
  22. Pérez, J. F., & Casale, G. (2017). Decoupling transient and steady-state analysis in closed-form solutions of Markovian queueing networks. IEEE Transactions on Reliability, 66(3), 625-638. https://doi.org/10.1109/TR.2017.2655505
  23. 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
  24. 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
  25. 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
  26. Ruuskanen, V., Helin, H., & Casale, G. (2021). Transient mean-field approximations in closed queueing networks. Performance Evaluation, 150, 102231. https://doi.org/10.1016/j.peva.2021.102231
  27. Wang, W., Casale, G., & Sutton, C. (2016). Improved Monte Carlo integration for asymptotic counting in queueing networks. ACM Transactions on Modeling and Computer Simulation, 26(4), 22. https://doi.org/10.1145/2893480
  28. Zahorjan, G. J., Eager, D. L., & Sweillam, H. M. (1988). Dynamic load balancing in distributed systems for the l_p norm. IEEE Transactions on Software Engineering, 14(10), 1477-1489. https://doi.org/10.1016/0166-5316(88)90018-1

← Back to Solvers Overview