Seminars

Seminar 1, topics 1-3: Feb 17 15:15-17, Teknikringen 33, floor 3, room Laila Ohlgren

Seminar 2, discussion of project ideas: Feb 24 15:15-17, room Laila Ohlgren

Seminar 3: topics 4-5: March 4 15:15-17, room Laila Ohlgren

Self study and problem solving

You have to read the suggested material, and answer the questions. Everyone has to hand in a solutions for each topic.

Reporting is done in two seminars, for topics 1-3 and 4-5. At the seminar one or two students present their solution, while the others check whether their solution is similar, and participate in the discussion.

Topics for self study and presentations

A1. Poisson Process (1 student presents)

A2. Markov chains (2 students present)

A3. Steady state via generating function (1 student presents)

A4. Non-Markovian queuing systems (2 students present)

A5. Optimal control of queues, Lyapunov optimization (2 students presents)

Literature

(G-H) Donald Gross, John F Shortle, James M Thompson, Carl M Harris, Fundamentals of Queueing Theory, 2013, 4th edition.
Available for KTH through KTH Lib, or maybe even directly at http://onlinelibrary.wiley.com.focus.lib.kth.se/book/10.1002/9781118625651

(Boudec) Jean-Yves Le Boudec, Performance Evaluation of Computer and Communication Systems, 2010, available at: http://perfeval.epfl.ch/

(Lakatos) László Lakatos, László Szeidl, Miklós Telek, Introduction to Queueing Systems with Telecommunication Applications, 2013, available at https://link.springer.com/book/10.1007/978-3-030-15142-3

(Neely) M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010. https://link.springer.com/book/10.1007/978-3-031-79995-2

(Tijms) H. Tijms, Stochastic Modelling and Analysis - A Computational Approach, Wiley, 1986, pdf

Topics and assignments

A1. Poisson process, in one and two dimensions

We read Gross and Harris 1.7-1.8

In addition, let us read some sections on spatial Poisson Point Process (PPP) here:
Haenggi, M.; Andrews, J.G.; Baccelli, F.; Dousse, O.; Franceschetti, M., "Stochastic geometry and random graphs for the analysis and design of wireless networks," IEEE Journal on Selected Areas in Communications, , vol.27, no.7, pp.1029,1046, September 2009
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5226957
Sections II-III are sections that are mostly interesting for us, but the rest is nice too.

Written assignment:

1. Prove the following two properties of the Poisson process:

Given that there are k arrivals in time period T, the arrival times are uniformly distributed in interval T (proof is in the Gross and Harris notes).
The limit of a binomial distribution is Poisson distribution. Specifically, consider the limit of the binomial distribution as n-> inf, and np = constant (lambda)

2. Consider the two dimensional Poisson Point Process as defined in the Haneggi paper. Define the displacement theorem and the Slivnyak's theorem. Motivate why are they useful.

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

We read Chapter 1.9 in Gross and Harris. Unfortunately proofs are missing. For proofs check Lakatos, Chapter 3.2. For additional missing proofs, look for sources.

Written assignment: Consider discrete time MCs. Collect the definitions and related theorems that are needed to prove Theorem 1.1.a in Gross and Harris (page 38).

A3. Analysing Markov chains with the help of generating functions - how to solve the system of balance equations for chains more complicated that a B-D process?

Read G-H 2.2.2, 3.1, 3.3.1-3.3.3.

Written assignment: Derive the state probability distribution of the M/E_r/1 queue with the help of generating functions (z-transforms). Explain each non-trivial step. Show that the derivation and the results would work for the M/M/1 queue.

A4. Non-Markovian queuing systems, M/G/1 transform forms:

Read: G-H 5.1.2-5.1.5 (seems to me, maybe some other parts are needed too...)

Written assignment:

1. List the main steps to derive the Pollaczek-Khintchin (there are many ways to write this name....) transform equations for the number of customers in the system and for the waiting time distribution.

2. Check how some of the steps work for the M/D/1 queue. What is the state probability distribution at departure times? What is the state probability distribution given by the transform form? Express p_0, p_1, p_2.

A5. Optimal control of queues, Lyapunov optimization.

Read Neely, Chapter 1 Introduction 1.1-1.3, 1.8, Chapter 2, Chapter 3

Written assignment (May be updated to a small numerical example instead, please wait for the update.)

We concentrate on Chapter 3. Summarize the line of reasoning in this section, by summarizing and connecting the results of the sections and subsections.