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:
- Giuliano Casale. Integrated Performance Evaluation of Extended Queueing Network Models with LINE. Proceedings of the 2020 Winter Simulation Conference, ACM Press, December 2020.
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:- Windows 64 bits. Requires MATLAB MCR version 2013a.
- Linux 64 bits. Requires MATLAB MCR version 2013a.
- 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.
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:
- G. Casale. Integrated Performance Evaluation of Extended Queueing Network Models with LINE. Winter Simulation Conference, ACM Press, December 2020.
- G. Casale, Y. Gao, Z. Niu, L. Zhu. LN: A Flexible Algorithmic Framework for Layered Queueing Network Analysis. ACM TOMACS, to appear in 2024.
- G. Casale. Automated Multi-paradigm Analysis of Extended and Layered Queueing Models with LINE. ACM/SPEC ICPE, 2019.
- J. F. Perez and G. Casale. LINE: Evaluating Software Applications in Unreliable Environments. IEEE Transactions on Reliability, 66(3), pp. 837 - 853, Sept 2017.
- C. Muller, P. Rygielski, S. Spinner and S. Kounev. Enabling Fluid Analysis for Queueing Petri Nets via Model Transformation. Intl. Workshop on Practical Applications of Stochastic Modelling (PASM), 2016.
- D. J. Dubois and G. Casale. OptiSpot: minimizing application deployment cost using spot cloud resources. IEEE CLOUD, 2016.
- R. Osman, J. F. Perez and G. Casale. Quantifying the Impact of Replication on the Quality-of-Service in Cloud Databases. IEEE Intl. Conference on Software Quality, Reliability, and Security (QRS), 2016.
- D. J. Dubois and G. Casale. OptiSpot: minimizing application deployment cost using spot cloud resources. Cluster Computing, 2016.
- J. F. Perez and G. Casale, Assessing SLA compliance from Palladio component models, in Proceedings of the 2nd Workshop on Management of resources and services in Cloud and Sky computing (MICAS), IEEE Press, 2013. [IEEE Xplore]
Presentations
-
This presentation provides an overview of LINE and its application to cloud applications:
- G. Casale. Quality-driven development of multi-cloud applications, July 2016.