Learning objectives
The goals of the course, in terms of knowledge and comprehension, are the following:
- to allow the student to master mathematical techniques for telecommunication networks' performance analysis;
- to provide the student the ability to abstract real application scenarios of telecommunication networks.
The abilities to use the knowledge and comprehension skills outline above can be summarized as follows:
- to analyze and describe a telecommunication network;
- to evaluate the performance of telecommunication networks.
The course has also the goal of improving the judgement autonomy and the communication skills through the preparation of a short report on a recent literature paper.
Prerequisites
- - -
Course unit content
Little’s law. Poisson processes. PASTA property. Renewal processes. M/G/1 queue. LAN performance analysis (Ideal controller. TDMA/FDMA. Aloha. Slotted Aloha). WAN performance analysis. Discrete-Time Markov Chains (DTMCs). Geo/geo/1 queue. Geo/geo/1/B queue. Slotted Aloha network. M/G/1 queue. M/G/1/B queue. (Mini)slotted Ethernet network. Absorbent Markov Chains (AMCs). Continous Time Markov Chains (CTMCs). Overview of semi-Markov processes. M/M/1 queue.performance analysis (Ideal controller. TDMA/FDMA. Aloha. Slotted Aloha). WAN performance analysis.
Discrete-Time Markov Chains (DTMCs). Geo/geo/1 queue. Geo/geo/1/B queue. Slotted Aloha network.
M/G/1 queue. M/G/1/B queue. (Mini)slotted Ethernet network. Absorbent Markov Chains (AMCs).
Continous Time Markov Chains (CTMCs). Overview of semi-Markov processes. M/M/1 queue.
Full programme
BASIC PERFORMANCE ANALYSIS
LECTURE 1: INTRODUCTION. Little's law. Examples. Traffic Intensity. Loss probability, throughput, Poisson processes and properties.
LECTURE 2: PASTA property. Renewal processes. Properties. Examples.
LECTURE 3: THE M/G/1 QUEUE. Average value analysis. Pollaczek-Khinchin formula. Extensions: (1) server with vacations; (2) server with set-up time and graphical method for residual time computation. Priority classes.
LECTURE 4: Server with set-up time: residual time computation with the total probability theorem. M/G/1 queue with priorities, non-preemptive.
LAN PERFORMANCE. Ideal controller. TDMA/FDMA. Aloha. Slotted Aloha. Comparison with TDMA.
LECTURE 5: Highest throughput of Ethernet and Token ring. Throughput and delay of polling - limited service systems. Comparison between Token-ring and TDMA-based ideal controller. Exercises on polling systems: cycles and renewals.
LECTURE 6: GEOGRAPHIC NETWORK PERFORMANCE. Kleinrock's formula. Examples of optimal routing. Throughput and delay in regular networks with uniform traffic. Topologies.
LECTURE 7: Exercise on multi-hop networks: roundabouts compared to traffic lights.
ADVANCED PERFORMANCE ANALYSIS
LECTURE 8: DISCRETE-TIME MARKOV CHAINS (DTMCs). Transition matrix. Updating rule.
LECTURE 9: Example: slotted source. Stationary distributions. Limiting distributions. State classification. Recurrence. Long-term state occupation. Ergodicity.
LECTURE 10: Limiting distribution in ergodic chains. Canonical distribution of the transition matrix.
Application to Geo/Geo/1 ED/LA queue: regime distribution, throughput, delay.
LECTURE 11: The Geo/Geo/1 ED/LA queue: flow balance.
The Geo/Geo/1/B queue: steady-state distribution, throughput, loss, delay.
The slotted Aloha network: steady-state distribution.
LECTURE 12: The slotted Aloha network: throughput, delay, internal dynamics.
The M/G/1 queue: study of the embedded DTMC, with derivation of the steady-state distribution.
LECTURE 13: Basics on moment generating function (MGF) and probability generating function (PGF). PK-transform formula.
The M/G/1/B queue, till the derivation of the steady-state distribution of the departures.
LECTURE 14: The M/G/1/B queue: derivation of the steady-state distribution seen from the arrivals. The M/M/1/B queue.
The (mini)slotted Ethernet (CSMA-CD) network: steady-state distribution.
LECTURE 15: The (mini)slotted Ethernet (CSMA-CD) network: throughput, delay, itnernal dynamics (mentioned).
LECTURE 16: Absorbing Markov chain (AMC): transient regime analysis.
LECTURE 17: Exercises on Markov chains.
LECTURE 18: Absorbing Markov chain (AMC): transient regime analysis (ctd.).
Continous-time Markov Chains (CTMCs): state updating law; infinitesimal generator matrix; stationary probabilities; global flux balance.
LECTURE 19: Semi-Markov processes (basics). The M/M/1 queue: steady-state distribution; average number of waiting clients and average waiting time; waiting time distribution with FIFO discipline; departures process.
LECTURE 20: Assignement to students of recent literature papers.
LECTURE 21: Discussion on the assigned papers.
Bibliography
Notes of "Reti di Telecomunicazioni B," ac. year 2008/2009, Prof. Bononi, avaiable at the documentation center (sede didattica).
Other references:
[1] D. P. Bertsekas, R. Gallager, Data networks, 2nd Ed. Prentice Hall, 1992.
[2] J. L. Hammond, P. J.P. O'Reilly, Performance analysis of Local Computer Networks. Addison Wesley, 1986.
[3] A. Leon-Garcia, Probability and random processes for electrical engineering, 2nd Ed. Addison Wesley, 1994.
[4] S. Ross, Stochastic Processes. Wiley, 1983.
[5] A. S. Tanenbaum, Computer Networks, 2nd Ed. Prentice-Hall, 1989.
[6] M. Schwartz, Telecommunication Networks. Addison-Wesley, 1987.
[7] J. G. Kemeny, H. Mirkil, J. L. Snell, G. L. Thompson, Finite mathematical structures. Prentice Hall, 1959.
[8] D. Gross, C. M. Harris, Fundamentals of Queuing Theory. Wiley, 1985.
[9] H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation. Volume III: Discrete-time Systems. North-Holland, Amsterdam, Holland, 1991.
Teaching methods
During the lectures variou topics related to performance analysis of telecommunication networks, as detailed in the program, will be covered. During the course exercises will also be given
Assessment methods and criteria
Written exam on the theoretical course material and discussion on a recent literature paper.
Other information
The teaching and suppport material will be provided by the teacher.
