Responsable / In charge of : Alouf Sara (Sara.ALOUF@inria.fr)

Résumé / Abstract :
This course will expose the students to the basic concepts and tools used in probabilistic modeling, performance evaluation, optimization and control of large-scale computer networks and distributed systems. The course will cover the theory of Markov chains (discrete time, continuous time, irreducible, absorbing, birth and death processes) and the theory of queues (classical M/M/1, M/M/1/K, M/M/c, M/M/c/c, M/G/1) and product-form network of queues (Jackson networks, Kelly networks). Numerous applications will be studied throughout the class, such as the modeling of IEEE 802.11 and the modeling of Web servers.

Prérequis / Prerequisite :
• Probabilités, algèbre linéaire.

Objectifs / Objectives :
• Learn about Markov chains (discrete time, continuous time, irreducible, absorbing, birth and death processes)
• The theory of queues (classical M/M/1, M/M/1/K, M/M/c, M/M/c/c, M/G/1) and product-form network of queues (Jackson networks, Kelly networks)

Contenu / Contents :

• Introduction to modeling, discrete-time Markov chain
• Example : modeling IEEE 802.11, continuous-time Markov chain, birth and death processes
• Some exercises, absorbing Markov chains (discrete- and continuous-time)
• Queueing theory: M/M/1, M/M/1/K, M/M/c, M/M/c/c, repairman model
• Little's formula, comparison of multiprocessor systems, M/G/1 FIFO queue
• Open Jackson networks, exercises
• Kelly networks, exercises

Références / References :

• D. P. Bertsekas and R. G. Gallager, "Data Networks", (2nd edition) Prentice Hall, 1992
• E. Gelenbe and I. Mitrani, "Analysis and Synthesis of Computer Systems", Academic Press (London and New York), 1980
• • F. P. Kelly, "Reversibility and Stochastic Networks", Wiley, Chichester, 1979
• • L. Kleinrock, "Queueing Theory", Vol. 1, J. Wiley + Sons, New York, 1975
• • M. F. Neuts, "Matrix-Geometric Solutions in Stochastic Models : An Algorithmic Approach", John Hopkins University Press, 1981

Acquis / Knowledge :

• Modeling of computer networks thanks to queueing theory

Evaluation / Assessment :
6 homeworks accounting for 1/2 of the final mark - a 3h-long final-term exam accounting for 1/2 of the final mark