FEP3340 Stochastic Models and the Theory of Queues 9.0 credits

Basic material, covered together with master students:

1.      Stochastic processes overview. Stationary and ergodic processes. Poisson process and exponential interarrival times. The memoryless property. The main properties of the Poisson Process.

2.      Markov process, Markov chains, and the markovian property. Brief discussion of the discrete time Markov chains. Detailed discussion of continuous time Markov chains. Holding times in continuous time Markov Chains. Transient and stationary state distribution.

3.      Using Markov chains to model and analyse stochastic systems. Construction of abstract models and numerical examples.

4.      Pure birth, pure death process and relation to the Poisson process. The Birth-death process.  Markov-chains and queuing systems.

5.      Markovian queuing systems with single and multiple servers, unlimited, limited storage capacity, and unlimited, limited population. Derivation of  analytic expressions for average performance metrics and waiting time distributions.

6.      Towards non-Markovian queuing systems: non-Exponential service times with servers in series and in parallel, average performance in steady state.

7.      Analysis of Markovian queuing systems that are extensions of the basic systems covered in class. Using Markovian queuing systems to model communication related problems. Construction of abstract models and numerical examples.

8.      Non-Markovian queuing systems: queues with general service time distribution. Derivation of analytic expressions of mean performance measures (Pollaczek-Khinchin mean formulas). Use of transform forms (Pollaczek-Khinchin transform equations) for distribution of performance measures. Priorities and service with vacation.

9.      Problems including non-exponential service time distribution. Model construction and numerical examples.

10.  Queuing networks. Open and closed queuing networks. Detailed analysis of open queuing networks. The existence of product form solution, and its motivation.

11.  Queuing network model construction and numerical examples of networking related problems .

Advanced material, covered only by PhD students

A1.Poisson Process: equivalent definitions of the Poisson process, construction of a Poisson process, relationship to Geometric distribution and Uniform distribution. Extensions considering homogeneity and higher dimensions. Use of Poisson Process  assumption in the research literature.

A2.Analysis of both discrete and continuous time MCs in transient state. Ergodicity and stability, proof of conditions for these. State aggregation in large Markov chains.

A3.Use of generating functions to derive steady state characteristics. From M/M/1 to M/E_r/1 to Phase-type service distributions.

A4.Non-Markovian queuing systems, renewal theory, embedded Markov chains. The derivation of the Pollaczek-Khinchin transform equations through the use of embedded Markov chains. Examples of similar derivations from the networking literature.

A5.Queuing networks: proof of the existence of the product form solution. Solution methodologies of closed queuing networks.  The limitations of  queuing networks.

A6.Outlook: Palm calculus, Large Deviation Theory, recent trends in stochastic modelling

A7.Small project: teletraffic theory model formulation (and maybe solution of model) of a problem closely related to the research of the PhD student.

After the course the students should be able to:

• Discuss and apply the theory of discrete and continuous time Markov-processes to describe complex stochastic systems. Derive the main theorems that address Markov-processes in transient and steady state.
•  Discuss, derive and apply the theory of Markovian and simpler non-Markovian queuing systems and networks. Use generating functions to analyze systems with large or complex state diagram.  Derive analytic models of non-Markovian queuing systems with the use of embedded Markov chains.
• Derive main theoretic results for the modeling of queuing networks. Discuss the computational issues and solution approaches.
• Analyze communication, networking and networked control problems with the tools of Markov-processes and queuing models.
• Discuss recent results of teletraffic theory in relation of networking research.
• Derive new theoretic results with application in own research area.

Statistics, probability theory, sotchastic processes

D. Gross and C. M. Harris, Fundamentals of Queueing Theory, Wiley

Original publications of some classical topics, parts of queuing theory books for topics not covered by Gross and Harris.

If the course is discontinued, students may request to be examined during the following two academic years.

• EXA1 - Examination, 9.0 credits, grading scale: P, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

Active participation on seminars

30 min oral presentation on one of the seminars

80% on homework problems

Approvedproject related to the student’s own research

70% on final exam

Viktoria Fodor

• All members of a group are responsible for the group's work.
• In any assessment, every student shall honestly disclose any help received and sources used.
• In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

EP3210

Part of the course is given together with EP2200.