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, and queueing models in random environments. Models are solved in LINE either natively or via external solvers, such as JMT, LQNS, MAMSolver, 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

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).

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

Supported Models

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

  • M/M/1 queues
  • M/M/c multiserver queues
  • 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
  • G/G/1 queues
  • G/G/c 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
  • 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

LINE Native Solvers

The following solvers are implemented natively in LINE:

Solver Description
CTMC Constructs and solves the underlying Markov chain using the global-balance equations and uniformization.
DES Discrete-event simulator implemented using the SSJ library in the JAR backend and SimPy in Python.
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.

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 prodcut-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. [21]
KPC-Toolbox A MATLAB toolbox for fitting Markovian Arrival Processes developed at William & Mary. [10]
MAMSolver A tool for matrix-analytic methods developed at William & Mary. [31]
SSJ A library for stochastic simulation developed at Université de Montréal. [24]
SimPy A discrete-event simulation framework for Python. [27]
Q-MAM A MATLAB toolbox for matrix-analytic methods in queueing theory developed at University of Antwerp. [28]
SMCSolver A solver for structured Markov chains in queueing models developed at University of Pisa and University of Antwerp. [5]

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—
autoHeuristic-based automatic selection—
heurCustom heuristic selection—
simPrefer simulation-based solvers—
exactPrefer exact analytical solvers—
fastPrefer fast approximate methods—
accuratePrefer accurate methods over speed—

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[5]
gpuGPU-accelerated solution—

DES (Discrete Event Simulation)

The DES solver is a discrete-event simulator implemented using the SSJ library in the JAR backend and SimPy in the Python implementation. It has 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 (SSJ in JAR, SimPy in Python)—

ENV (Blending Solver)

The ENV solver analyzes queueing systems operating in random environments with multiple operational stages. The solver uses stage-dependent analysis where system parameters vary according to the current environmental state. Performance metrics are computed as ensemble averages over all environmental stages, enabling modeling of systems subject to external conditions or failures.

MethodAlgorithmReference
defaultAutomatic environment-aware analysis—

FLD (Fluid)

The FLD 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
defaultAutomatic method selection—
matrixODE-based mean field approximations[24], [28]
pnormPolynomial normalization ODE approximation—
statedepKurtz's mean field ODEs for closed models[24]
closingFLD with closing method for open classes[5]
softminSmoothed statedep with softmin functions—
diffusionDiffusion approximation via Euler-Maruyama SDEs—
mfqMarkovian fluid queueing systems[20]

JMT (Java Modelling Tools)

The JMT solver is a wrapper for the Java Modelling Tools suite [4], 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
defaultAutomatic method selection—
jsimDiscrete-event simulation in JSIM[4]
closingClosing approximation—
jmvaJava MVA analysis[4]
jmva.amvaApproximate MVA in JMVA—
jmva.mvaExact MVA in JMVA[25]
jmva.recalRECAL algorithm (exact)[14]
jmva.comomCoMoM algorithm (exact)[7]
jmva.bsBard-Schweitzer (approximate)[5]
jmva.linLinearizer (approximate)[12]
jmva.dmlinDe Souza-Muntz Linearizer[15]
jmva.chowChow algorithm[13]

LN (Layered Network Solver)

The LN solver analyzes layered queueing networks using iterative decomposition methods. It decomposes the network into layers and solves them iteratively, updating metrics and parameters until convergence. This approach is particularly effective for analyzing software architectures with multiple service layers and task dependencies.

MethodAlgorithmReference
defaultAutomatic layer analysis and iteration—
moment3Three-moment process matching for layer sychronization—
molMethod of Layers iteration—

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
defaultAutomatic LQNS method selection—
lqnsLQNS exact analytical solution—
srvnStochastic Rendezvous Network (SRVN) analysis—
exactmvaExact MVA solution—
srvn.exactmvaSRVN with exact MVA solution—
simLQNS simulation mode—
lqsimLQNS simulator (lqsim)—
lqnsdefaultLQNS default method—

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 [18], Q-MAM, MAMSolver, and SMCSolver. Native algorithms for parametric decomposition of queueing networks are integrated with this solver.

MethodAlgorithmReference
defaultMatrix-analytic solution of structured QBDs[18]
exactExact matrix-analytic solution—
dec.mnaMatrix Network Analyzer traffic decomposition[21]
dec.sourceTraffic decomposition with source-like arrival process as flow—
dec.mmapTraffic decomposition with marked Markovian arrival process as flows—
dec.poissonTraffic decomposition with Poisson arrival flows—
inapIterative Numerical Algorithm for Product-forms[22]
inapplusWeighted Iterative Numerical Algorithm for Product-forms[3]

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
defaultAutomatic method selection—
exactExact mean value analysis[25]
mvaExact mean value analysis[25]
amvaApproximate MVA with Linearizer[12]
bsBard-Schweitzer approximate MVA[5]
amva.bsApproximate MVA with Bard-Schweitzer[5]
linLinearizer approximate MVA[12]
qnaQueuing Network Analyzer—
qdQueue-dependent approximate MVA[8]
amva.qdApproximate MVA queue-dependent[8]
qdlinQueue-dependent Linearizer—
amva.qdlinApproximate MVA with queue-dependent Linearizer—
qliQueue-Linearizer iteration—
amva.qliApproximate MVA with queue-Linearizer iteration—
sqniSingle-server queue approximation iteration—
aba.upper/lowerAsymptotic bound analysis[5]
bjb.upper/lowerBalanced job bounds[6]
gb.upper/lowerGeometric square-root bounds[6]
pb.upper/lowerProportional bounds[6]
sb.upper/lowerSimple bounds[17]
mm1Exact M/M/1 formula[5]
mmkErlang-C formula (M/M/k)—
mg1Pollaczek-Khinchine (M/G/1)[5]
gig1.kingmanKingman upper bound (GI/G/1)[5]
gig1.allenAllen-Cunneen formula (GI/G/1)[5]
gig1.klbKrämer-Langenbach-Belz (GI/G/1)[5]
gig1.kobayashiKobayashi diffusion approx. (GI/G/1)[5]
gig1.marchalMarchal formula (GI/G/1)[5]

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
defaultAutomatic normalizing constant method selection—
exactExact normalizing constant computation—
imciImproved Monte Carlo integration[29]
lsLogistic sampling (Monte Carlo)[9]
leLogistic asymptotic expansion[9]
mmint2Multivariate moment integration (order 2)—
gleintGauss-Legendre integration—
panaceaPanacea asymptotic expansion[23], [27]
caMulticlass convolution algorithm (exact)—
ktKnessl-Tier asymptotic expansion[19]
samplingGeneric sampling method—
propfairProportional fairness approximation—
comomClass-oriented method of moments (exact)[7]
cubGrundmann-Moeller cubature rules[9]
rdReduction heuristic[11]
nrpNörlund-Rice integral (Probit)[11]
nrlNörlund-Rice integral (Logit)[11]
gmGrundmann-Moeller method—

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
defaultDefault QNS method—
conwayConway's multi-server—
roliaRolia-Sevcik multi-server—
zhouZhou-Woodside multi-server—
suriSuri approximation—
reiserReiser-Lavenberg exact mean value analysis—
schmidtSchmidt method—

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
defaultDefault SSA method—
ssaStochastic simulation algorithm[16]
serialGillespie's direct method (single core)[16]
paraParallel independent replications—
parallelParallel execution mode—
nrmNext Reaction Method[2]

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. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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
  25. 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
  26. 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.
  27. Matloff, N. (2008). Introduction to Discrete-Event Simulation and the SimPy Language. https://web.cs.ucdavis.edu/~matloff/matloff/public_html/156/PLN/DESimIntro.pdf
  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

Manuals

API Reference