Learning outcomes of the course unit
Learning of mathematical techniques for telecommunication network performance analysis, with applications.
Course contents summary
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.
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.
Notes of "Reti di Telecomunicazioni B," ac. year 2008/2009, Prof. Bononi, avaiable at the documentation center (sede didattica).
 D. P. Bertsekas, R. Gallager, Data networks, 2nd Ed. Prentice Hall, 1992.
 J. L. Hammond, P. J.P. O'Reilly, Performance analysis of Local Computer Networks. Addison Wesley, 1986.
 A. Leon-Garcia, Probability and random processes for electrical engineering, 2nd Ed. Addison Wesley, 1994.
 S. Ross, Stochastic Processes. Wiley, 1983.
 A. S. Tanenbaum, Computer Networks, 2nd Ed. Prentice-Hall, 1989.
 M. Schwartz, Telecommunication Networks. Addison-Wesley, 1987.
 J. G. Kemeny, H. Mirkil, J. L. Snell, G. L. Thompson, Finite mathematical structures. Prentice Hall, 1959.
 D. Gross, C. M. Harris, Fundamentals of Queuing Theory. Wiley, 1985.
 H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation. Volume III: Discrete-time Systems. North-Holland, Amsterdam, Holland, 1991.
Classroom teaching of theoretical aspects (75%) and lab exercise (25%).
Assessment methods and criteria
Written exam on the classroom teaching part of the course and project (with final report) for the lab portion.
The teaching and suppport material will be provided by the teacher.