NETWORK PERFORMANCE
cod. 1005251

Academic year 2021/22
1° year of course - First semester
Professor
FERRARI Gianluigi
Academic discipline
Telecomunicazioni (ING-INF/03)
Field
Ingegneria delle telecomunicazioni
Type of training activity
Characterising
48 hours
of face-to-face activities
6 credits
hub: PARMA
course unit
in ENGLISH

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.

LECTURE 4: Server with set-up time: residual time computation with the total probability theorem.
LAN PERFORMANCE: Ideal controller. TDMA/FDMA. Aloha. Slotted Aloha. Comparison with TDMA.

LECTURE 5: LAN PERFORMANCE: 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 and exercises on intersection with traffic lights.

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.

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

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

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

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

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, till the derivation of the steady-state distribution seen from the arrivals. The M/M/1/B queue.

LECTURE 18: The (mini)slotted Ethernet (CSMA-CD) network: steady-state distribution.

LECTURE 19: The (mini)slotted Ethernet (CSMA-CD) network: throughput, delay, itnernal dynamics (mentioned).
Absorbing Markov chain (AMC): transient regime analysis.

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

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

LECTURE 22: Seminar

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.

Bibliography

Notes of "Reti di Telecomunicazioni B," ac. year 2008/2009, Prof. Bononi (avaiable at the documentation center, sede didattica, and/or provideed by the teacher).
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 with open answers. The possibility of having intermediate tests (midterm and final) is considered, with final grade given by the arithmetic average of the grades of the intermediate tests. During each written test (complete or intermediate) all questions have the same weight. It is not allowed to bring any support material during the tests.

Other information

The teaching and suppport material will be provided by the teacher.