# NETWORK PERFORMANCE

## 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.

## Course contents

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.

## Recommended readings

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

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.

## Other informations

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