
The course covers the fundamentals of stochastic modeling and queuing theory, including the thorough discussion of basic theoretic results and with focus on application in the area of communication networks. The course is intended for PhD students who perform research in the ICT area, but have not covered this topic in their master level courses.
The course follows the lectures and exercises of EP2200, with additional seminars, homework and small project, dedicated for PhD students.
The schedule follows the schedule of EP2200:
https://www.kth.se/social/course/EP2200/subgroup/vt-2020-298/calendar/
Course offering missing
Course offering missing for current semester as well as for previous and coming semestersInformation for research students about course offerings
usually given P3.
Content and learning outcomes
Course contents
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.
Intended learning outcomes
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.
Course Disposition
Lectures, exercises, seminars with student presentation, homework problems, small project and final exam.
Literature and preparations
Specific prerequisites
No information inserted
Recommended prerequisites
Statistics, probability theory, sotchastic processes
Equipment
No information inserted
Literature
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.
Examination and completion
If the course is discontinued, students may request to be examined during the following two academic years.
Grading scale
P, F
Examination
- EXA1 - Examination, 9,0 hp, betygsskala: 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.
Other requirements for final grade
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
Opportunity to complete the requirements via supplementary examination
No information inserted
Opportunity to raise an approved grade via renewed examination
No information inserted
Examiner
Ethical approach
- 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.
Further information
Course web
Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.
Course web FEP3340Offered by
Main field of study
No information inserted
Education cycle
Third cycle
Add-on studies
EP3210
Contact
Viktoria Fodor
Supplementary information
Part of the course is given together with EP2200.