Queuing Theory
EP2930  ( HF2000)
(Computer Networks, Master of Science Program)

Credits: 7,5
ECTS Credits: 7,5
Level: D
Grading: A-F
Language: Engelska / English
Time: Period 1, 2009/10
Coordinator: Armin Halilovic
office: 5046
tel. 08-790 4810
www.sth.kth.se/armin
armin@sth.kth.se

Aim

After completion of the course the student should be able to:

* Define and explain the basic concepts of the theory Markov processes, M/M/m, M/M/m/K, and M/M/m/K/C queuing systems.
* Derive and apply main formulas for some properties (such as stationary probabilities, average waiting and system time, expected number of customers in the queue, etc.) of M/M/m, M/M/m/K, and M/M/m/K/C queuing systems.
* Calculate traffic intensity, blocked traffic, and the utilization of some queuing systems.
* Solve some simple problems on queuing networks.
* Analyze and solve problems using computer aid (Maple, Matlab, or Mathematica)

Content:

* Stochastic processes. Markov chains in discrete and continuous time. Chapman-Kolmogorov equations. Stationary probabilities. Poisson process. Birth-death processes.
* Basic concepts in queuing theory. Little’s theorem.
* Arrival processes and service time. Queuing disciplines. Stationary probabilities. Offered load (traffic). Blocked load. Effective load. Utilization. Blocking probability.
* Markovian wait systems.
* M/M/m: Queuing systems with m servers, infinite number of waiting positions, and infinite number of customers.
* M/M/m/K: queuing system with m servers, limited number (=K) waiting positions, and infinite number of customers.
* M/M/m/K/C: queuing system with m servers, limited number (=K) waiting positions, and limited number of customers (=C).
* Markovian loss systems: Erlang’s loss system, Engset’s loss system, Binomial (Bernoulli’s) loss system.
* Semi-markovian M/G/1 and G/M/l queuing systems. Pollacsek-Khinchin formula.
* Survey on open and closed Jackson queuing networks.

Prerequisites
The student should posses a basic knowledge in calculus, linear algebra and mathematical statistics.

Requirements
Passed exam (TEN1; 4.5 c.), grading A-F.
Passed lab work (RED1; 3 cr.), grading P/F.

Text books and recommending reading:
QUEUEING MODELLING FUNDAMENTALS,
Ng Cheee Hock, John Wiley & Sons LTD
Recommending reading (PDF)
--------------------------

Queueing theory books ( FREE ) online

==================

A little Swedish -English glossary of basic terms in queueing theory

==================
EXERCISES AND REPETITION BEFORE THE EXAMINATION

Prelimineries:
P1. Logic, Algebra of Sets
P2. Probability
P3. Laplace transforms P3.
P4. Geometric series. Taylor series

Formula Tables
T1. Table with some discrete and continuous random variables
T2. Table with Laplace transforms
T3. Table with Z-transforms

Exercises:
1a) Discrete -Time Markov chains
1b) Poisson Process
1c) Life distributions
2) Continuous -Time Markov chains. Q matrix
2b) Birth-and-Death Process
3) M/M/1 system
4) M/M/1 system
4b) M/M/m system
5) M/M/m/K system (m servers, K waiting positions)
6) M/M/m/K system (m servers, K waiting positions)
7) M/M/m/K/C system (m servers, K waiting positions, C customers )
8) ERLANG LOSS SYSTEM (m servers, 0 waiting positions, "unlimited number of customers")
9) ENGSET LOSS SYSTEM (m servers, 0 waiting positions, C customers, C>m)
10) BINOMIAL (BERNOULLI) LOSS SYSTEM (m servers, 0 waiting positions, C customers, C<=m )
11) MIXED PROBLEMS
12) M/G/1 queueing system

------------------------------
==================

COMPUTER ASSIGNMENTS (inlämningsuppgifter) , (RED1; 3cr.) :

Group work: a maximum of two students can work together on the assignment 1.

Assignment #1
Assignment #2
Assignment #3
Assignment #4

Date and time for presentation:
13 Oct 2009, 15:15-17:15, in room 7097D
or 16 Oct 2009, 10:15-12:15, in room 5095D.
Questions related to lab work will be included in the exam.

====================

TESTS AND BONUS POINTS

Two "in-class" tests will be organized during the course.

	Date	Time	room
Test1	17 Sep	08:15-10:15	2092
Test2	8 Oct	10:15-12:00	5091

1. Correctly solved problems on tests earn bonus points that will be added on to the results of your final written examination.
2. You can get a maximum of one point per test.
3. Earned bonus points are valid until 31 Aug 2010.
-------------------------------------

The old tests with solutions:

TEST 1:
test 1, version A, 17 Sep 09
test 1, version B, 17 Sep 09

TEST2:
test 2, version A, 8 Oct 09
test 2, version B, 8 Oct 09

=========================
TEST 1:
test 1, version A, 18 Sep 08
test 1, version B, 18 Sep 08

  TEST 2:
test 2 , version A, 7 Oct 08
test 2, version B, 7 Oct 08

=========================
TEST 1: test 1: 19 Sep 06
TEST 1: test 1: Sep 05
--------------------------------------
TEST 2: test 2: 12 Oct 07
TEST 2A: test 2A: 6 Oct 06
=======================
TEST 2B: test 2B: 6 Oct 06
TEST 2: test 2: Oct 05

====================

WRITTEN EXAMINATION (TEN1; 4.5cr.)

Datum: ..............Time: ...........

Instructions:
1. Students ARE allowed to use calculators.
2. Students are NOT allowed to use tables of mathematical formulas on the exam.
3. Use of any communication device when taking this examination is strictly prohibited.
4. Grading: For each correct solution, four points will be awarded. Credit will be given or presentation and methods of solutions.
5. A maximum of 30 points (28+2 bonus points) can be earned. Points can also be deducted for unsubstantiated answers.
At least 15 points are required to pass the exam.

Grading scale: The total number of possible points is 30 (28+2 bonus points).
27 -30 points are required for an “A” grade;
24 -26 points are required for a “B” grade;
21 -23 points are required for a “C” grade;
18 - 20 points are required for a “D” grade;
15 - 17 points are required for an “E” grade;
14 points result in a “Fx”;
0-13 points result in a “F” grade.

There will be a complementary exam for those students who receive 14 points (Fx ) on the exam
The complementary exam will be different from the regularly scheduled exam, though it will cover the same material.