|
ISCRIZIONE |
Elements of Queueing Theory
Instructor: Prof. Evsey Morozov
Affiliation: Institute of Applied Mathematical Research, Karelian Research Centre of the Russian Academy of Sciences, and Department of Applied Mathematics and Cybernetics, Petrozavodsk University, Petrozavodsk, Russia
Duration: 20 hours
Period: October 23 - October 27, 2006
Place: Dipartimento di Ingegneria dell'Informazione: Elettronica, Informatica, Telecomunicazioni, via G. Caruso, meeting room, ground floor
Credits: 5
Final test: yes
Contacts: Ing. Michele Pagano
Aims
Queueing theory plays an important and increasing role in the analysis and development of the modern communication networks (in particular, computer and telecommunications networks). For instance, data packets and telephone calls move among computers, buffers and switching stations, e-mail moves among PCs, signals move among processors, and so on. The most adequate and recognized mathematical models of such systems are stochastic queueing networks. Theory of stochastic networks is the basis of the most effective solutions and deep performance analysis in the area, and the knowledge of the fundamentals of the theory is an important element of the education of the modern computer and telecommunication engineers. The most important issues concerning stochastic queueing system include estimation/calculation of the average delay, loss probability, average sojourn time, quality of service (QoS) guarantee, and so on.
This series of lectures aims to give an introduction to the queueing theory including two main parts: Markovian models and regenerative approach which would be oriented to PhD students in computer and telecommunication engineering. We start with the most popular M/M/1 queue then consider applications of birth-death processes in analysis of M/M/* queues, and discuss M/G/1 –type queues using embedded Markov chains. We also study Markov workload process and discuss decomposition of the exponential networks based on the Jackson theorem. The second part includes definition of classically regenerative processes, main asymptotic results and studying the regenerative simulation for confidence estimation of a steady-state performance measure. In particular we show how regenerative approach allows to obtain effectively important stationary characteristics of the queues. It is supposed to discuss main ideas and basic models, and mathematical details will play a secondary role. Prerequisites for the course are (discrete- and continuous-time) Markov Chains and Poisson processes but it is assumed to recall main results concerning these processes. We combine theoretical material with classroom exercises.
Syllabus
- Main objectives and notions of queueing theory (1 hour)
- Discrete-time Markov chains: main results (2 hours )
- Continuous-time Markov processes (1 hour)
- M/M/1 queue: stationary distribution and main characteristics (2 hours)
- The Birth-Death (BD) process (1 hour)
- Application of the BD process to multiserver M/M/m queue (2 hours)
- M/G/1 and G/M/1 queues: embedded Markov chain method (2 hours)
- Jackson (exponential) stochastic networks: stationary distribution (2 hours)
- Regenerative queueing procesess: definitions and asymptotic results (1 hour)
- Little’s formula: connection between average workload and queue size (1 hour)
- Pollaczek-Khinchin formula for stationary mean delay (2 hours)
- Waiting time paradox (1 hour)
- Regenerative simulation: confidence estimation of the mean delay (2 hours)
