Till KTH:s startsida Till KTH:s startsida

PhD students

Course evaluation

https://sunet.artologik.net/kth/Survey/3128

Seminar schedule

Please register for leading the seminars in this doodle. Note, that dates may change, but the order of seminars remains. The first time slot is for the second seminar, since I lead the discussion on the first one. There should be max two students per seminar.

http://doodle.com/poll/7m359b5wqxp8t8sd

Presentation of project ideas

You have 15 minutes to present the project idea at the whiteboard, including discussion. Introduce the area, and then the specific problem you will address. Talk about the solution methodology you would like to follow, and the results you expect to get.

Expected schedule: 

I think the following times would work (mix of Wednesdays, Thursdays and other days for the last two seminars).

PhD students should join the lectures and the recitations, and meet six additional times during the course. The seminars will be ca. one hour long, and are compulsory to attend.

Proposed times: 

0. Jan 24, 12-12:30 : short introduction
1. Feb 2, 9:00-10:00, M35: Viktoria
2. Feb 8, 15:15, M31,
3. Feb 16, 15:15 V12,
4. Feb 22, 15:15 M38
5. Feb 27, 13:15-15:00, including one hour student project proposal presentation 
6. March 7, 13:15-15:00, including one hour student project proposal presentation

The last two seminars will be at the Department of Networks and Systems Engineering (old LCN) at Osquldas vag 6-8, floor 4. Ring the bell at the door, someone will let you in.

The project should be performed during the second part and after the course. Project ideas presented on seminars 5,6, based on maturity.

Material: see link "Reading material" (for logged in students)

Missed classes: if you missed a class, you need to solve a small related problem. The problems are not complex, but require the reading and understanding of the material. See the questions on the bottom of the page. You can submit the answer together with your project.

Seminar style:

Everyone prepares by reading the material. A PhD students leads the discussion, everyone follows based on his/her own notes. from the middle of the course even projects are discussed.

Topics and references:

Gross and Harris, Fundamentals of Queuing Theory. PDF is available through KTH (e.g., go to www.lib.kth.se, and write Gross and Harris in the search field...)

1. Poisson process, in one and two dimensions
Gross and Harris 1.7-1.8
In addition, let us read some sections on spatial Poisson Point Process (PPP) and percolation theory 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
II.A, IV.C are sections that are mostly interesting for us, but the rest is nice too. We only review some key properties of PPP without proof.

2. 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 it does not prove the "main theorem" on the existence of stationer solution, that is, Theorem 1.1 a,b,c on page 38. Neither the two other books I looked at. So, if you have time, please check whether you find a proof. I will keep searching too.

Also, please look at the imbedded MC with equation (1.31).  Can we derive the condition for the existence of a stationary distribution for continuous time birth-death process from this imbedded chain representation and the conditions we have for the discrete time MCs?

3. Use of generating function
M/M/1 Gross and Harris, 2.2.2
Bulk arrival: G-H 3.1, including Example 3.1 and maybe Example 3.2
Erlang-r example: G-H 3.3.3 (also phase type?)

4. M/G/1 transform forms:
G-H 5.1.2-5.1.5 (seems to me, maybe some other parts are needed too...)

5. Queuing networks, and specifically product form solutions of large markov chains.
Thomas G. Robertazzi​, Computer networks and systems : queuing theory and performance evaluation, chapters 3.2.3, 3.3 and 3.4. There are  lots of examples, you do not need to go through all of them. I suggest pages 111-112, 117-130 and 136-148.

6. Advanced topics: this year we look at a possible solution to address the performance of dependent queues. We read A. Bobbio, M. Gribaudo and M. Telek, "Analysis of Large Scale Interacting Systems by Mean Field Method," 2008 Fifth International Conference on Quantitative Evaluation of Systems,  2008"  http://webspn.hit.bme.hu/~telek/cikkek/bobb08a.pdf

Missed classes problems 

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

  • 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. Specifically, consider the limit of the binomial distribution as n-> inf, and np = constant (lambda)

2. Consider the discrete time Markov chain with two states and state transition probabilities {{1/2,1/2}{3/4,1/4}}. Show that the resulting stochastic process is ergodic (see section 1.9.6 in G-H). Calculate the state probabilities in steady state.

3. Consider the z-transform of the state probability distribution under bulk arrivals (section 3.1, below equation 3.3). Consider the specific case, where there is exactly 1 customer arriving in each “bulk”, and derive the state probabilities, through the given z-transform form.

4. Give the exact expressions for k_i, the state transition probability values of the imbedded discrete time Markov chain, when the service times are deterministic. Denote the arrival intensity with lambda, the service time with x.