Network Performance, Academic Year 2022/2023 - Course Program

Prof. Gianluigi Ferrari          Office: palazzina 2 sede scientifica Ingegneria, stanza 2/4

Tel: 0521 906513 

E-mail: gianluigi.ferrari@unipr.it

URL: www.tlc.unipr.it/ferrari

Office Hours

Meets with students upon phone or email (best) reservation.

 Course hours and classrooms (A.Y. 2022/2023, Fall semester)
 Video lectures (recorded in A.Y. 2015/2016, Spring semester)

Tentative Course program

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: Exercises on M/G/1.

LECTURE 7: GEOGRAPHIC NETWORK PERFORMANCE. Kleinrock's formula. Examples of optimal routing. Throughput and delay in regular networks with uniform traffic. Topologies.

LECTURE 8: Exercise on multi-hop networks: roundabouts compared to traffic lights.

ADVANCED PERFORMANCE ANALYSIS

LECTURE 8 (ctd.): 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: Exercises on polling systems, PK formula, M/G/1 queues.

LECTURE 11: Limiting distribution in ergodic chains. Canonical distribution of the transition matrix.

LECTURE 12: Application to Geo/Geo/1 ED/LA queue: regime distribution, throughput, delay.

LECTURE 13: The Geo/Geo/1 ED/LA queue: flow balance.
The Geo/Geo/1/B queue: steady-state distribution, throughput, loss, delay.

LECTURE 14: The slotted Aloha network: steady-state distribution; throughput, delay, internal dynamics.

LECTURE 15: Exercises.

LECTURE 16: The M/G/1 queue: study of the embedded DTMC, with derivation of the steady-state distribution.
Basics on moment generating function (MGF) and probability generating function (PGF). PK-transform formula.

LECTURE 17: The M/G/1/B queue. M/M/1/B queue.

LECTURE 18: The (mini)slotted Ethernet (CSMA-CD) network: steady-state distribution, throughput, delay, internal dynamics (mentioned).

LECTURE 19: Absorbing Markov chain (AMC): transient regime analysis.

LECTURE 20: Absorbing Markov chain (AMC): transient regime analysis (ctd.).

LECTURE 21: Exercises.

LECTURE 22: Continous-time Markov Chains (CTMCs): state updating law; infinitesimal generator matrix; stationary probabilities; global flow balance.

LECTURE 23: 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 24: Multi-hop network performance analysis with Matlab.


Textbook
Notes of "Reti di Telecomunicazioni B," Ac. Year 2008/2009, by Prof. Bononi, with English partial translation. The teaching material is available upon request to Prof. Ferrari and in Elly.

Reference textbooks
[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.
Exams

The exam consists in two intermediate written tests ("compitini"), each of which lasts 2 hours and consists of questions/problems related to the topics covered in the previous lectures. The regular exams last 3 hours. During the written test no personal notes can be used.

Requirements

The study of Markov chains requires knowledge of matrix analysis, including derivation of eigenvalues and eigenvectors (topics of Geometry and Linear Algebra).