What is LINE?

LINE is an open-source software package to analyze queueing models via analytical methods or simulation.

LINE is developed by the QORE lab at Imperial College London and distributed under the BSD-3 license.

Main features

The tool offers solution algorithms and a domain-specific language 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, and BuTools.

Getting started

LINE is available for download in the following release:

Resources: Installation, User manual, Examples, Wiki, JMT integration.

Acknowledgement

If you use LINE for a research paper, you must 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).

Downloads

2.0.x (May 2019-Present)

Latest stable release:

Latest dev release source code:

git clone https://github.com/imperial-qore/line-solver.git line-solver

New features:
  • Major tool overhaul and refactoring, not backward compatible with 0.x.x and 1.0.x versions.
  • New modelling language to describe extended queueing networks and layered models.
  • New engine featuring solvers for extended queueing networks (CTMC, MVA, SSA, JMT, FLUID) and layered queueing models (LQNS, LN).
  • Automated import of models specified in JMT using JSIMgraph or JSIMwiz.
  • New user manual, wiki, and examples.

1.0.0 (June 2016)

This version can be used with Palladio Bench and SPACE4Cloud.

Binaries and source code: New features:
  • LINE now offers support for both synchronous and asynchronous calls. This is achieved by extending the transformation from LQN models to incorporate asynchronous calls, and by extending the analysis to differentiate how these two types of calls account for remote execution time.
  • This version includes beta versions of solvers for two extended types of execution: simultaneous resource possession (SRP) and synchronous calls with blocking (SCP). These can be used at the script level.
  • This version has undergone a naming revision, simplifying names of scripts.

Latest release

LINE 2.0.x user manual

Older releases

LINE 1.0.0 user manual

Algorithms

This page lists the solution methods available in the LINE solvers. For detailed bibliographic references please refer to the user manual (Table 5.1).

Solver Method Description
CTMC default Solution based on global balance
CTMC gpu Solution based on global balance run on GPU
Fluid default Mean field fluid ODEs
Fluid matrix Alias for the default method
Fluid closing Fluid with closing method for open classes
JMT default Alias for the jsim method
JMT jmva Alias for the jmva.mva method
JMT jmva.mva Exact MVA in JMVA
JMT jmva.recal Exact RECAL algorithm in JMVA
JMT jmva.comom Exact CoMoM algorithm in JMVA
JMT jmva.amva Approximate MVA, alias for jmva.bs.
JMT jmva.aql AQL algorithm in JMVA
JMT jmva.bs Bard-Schweitzer algorithm in JMVA
JMT jmva.chow Chow algorithm in JMVA
JMT jmva.dmlin De Souza-Muntz Linearizer in JMVA
JMT jmva.lin Linearizer algorithm in JMVA
JMT jmva.ls Logistic sampling in JMVA
JMT jsim Exact discrete-event simulation in JSIM
MAM default Matrix-analytic solution of structured QBDs
MAM dec.source Decomposition with arrivals as from the source
MAM dec.poisson Decomposition based on Poisson arrival flows
MVA default Approximate MVA, same as qd option
MVA amva Approximate MVA, same as qd option
MVA aql Aggregate queue length approximate MVA
MVA bs Bard-Schweitzer approximate MVA
MVA fli Wang-Sevcik fraction line approximate MVA
MVA lin Linearizer approximate MVA
MVA qd Queue-dependent approximate MVA
MVA qdaql Queue-dependent Aggregate queue length (AQL) approximate MVA
MVA qdlin Queue-dependent Linearizer approximate MVA
MVA qli Wang-Sevcik queue line approximate MVA
MVA exact Exact solution, method depends on model
MVA mva Alias for the mva.amva method
MVA aba.upper Asymptotic bound analysis (upper bounds)
MVA aba.lower Asymptotic bound analysis (lower bounds)
MVA bjb.upper Balanced job bounds (upper bounds)
MVA bjb.lower Balanced job bounds (lower bounds)
MVA gb.upper Geometric square-root bounds (upper bounds)
MVA gb.lower Geometric square-root bounds (lower bounds)
MVA pb.upper Proportional bounds (upper bounds)
MVA pb.lower Proportional bounds (lower bounds)
MVA sb.upper Simple bounds (upper bounds, Thm. 3.2)
MVA sb.lower Simple bounds (lower bounds, Eq. 1.6)
MVA gig1.allen Allen-Cunneen formula - GI/G/1
MVA gig1.heyman Heyman formula - GI/G/1
MVA gig1.kingman Kingman upper bound- GI/G/1
MVA gig1.klb Kramer-Langenbach-Belz formula - GI/G/1
MVA gig1.kobayashi Kobayashi diffusion approximation - GI/G/1
MVA gig1.marchal Marchal formula - GI/G/1
MVA gigk Kingman approximation - GI/G/k
MVA mg1 Pollaczek-Khinchine formula - M/G/1
MVA mm1 Exact formula - M/M/1
MVA mmk Exact formula - M/M/k (Erlang-C)
NC default Alias for the adaptive method
NC adaptive Automated choice of deterministic method
NC exact Automated choice of exact solution method.
NC brute Brute force summation over all the state space
NC ca Multiclass convolution algorithm (exact)
NC comom Class-oriented method of moments (exact)
NC cub Grundmann-Moeller cubature rules
NC mva Product of throughputs on MVA lattice (exact)
NC imci Improved Monte carlo integration sampler
NC kt Knessl-Tier asymptotic expansion
NC le Logistic asymptotic expansion
NC ls Logistic sampling
NC mom Method of moments (exact)
NC mmint2 McKenna-Mitra integral (2-station models only)
NC nr.logit Norlund-Rice integral with logit transformation
NC nr.probit Norlund-Rice integral with probit transformation
NC pana Panacea asymptotic expansion
NC propfair Product of proportionally fair throughputs
NC rd Reduction heuristic
NC rgf Recursive generating function
NC sampling Automated choice of sampling method
SSA default Alias for the serial method
SSA serial CTMC stochastic simulation on a single core
SSA serial.hash Same as serial but with state hashing (slower, less memory)
SSA para Parallel simulations (independent replicas)
SSA para.hash Same as para but with state hashing (slower, less memory)
SSA taussa Java-based SSA simulation
SSA tauleap Java-based SSA simulation with tau leaping

Resources

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

Papers

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

The following papers extend or use LINE across different applications:

Presentations

Videos

YouTube channel

Demos that illustrate the practical use of LINE are available on our YouTube channel.

LINE 2.0.0

Solving a M/M/1 queue via JMT

This example shows the solution of a M/M/1 queue specified in LINE with JMT and how to export to JSIMgraph and JSIMwiz (the video has no audio):

Importing a JMT model into LINE

The following example viceversa shows the automated import into LINE of a M/M/1 queue specified with JMT (the video has no audio):