Modèles et algorithmes des réseaux

Pratique:

Les cours et les TD ont lieu le mardi de 13h15 à 17h00 en salle Info 2.

Intervenants en 2018 - 2019
Cours : Ana Busic
TD : Ludovic Stephan

Si vous avez des questions, n'hésitez pas à nous envoyer un mail: prenom.nom@ens.fr

Devoir maison

Sujet
Date limite: 30/11/18

Mini-projets

Préséntations articles: 22 janvier 2019.
Liste des articles
- An algebraic theory of dynamic network routing. J. L. Sobrinho. IEEE/ACM Trans. Netw. 13, 5 (October 2005), 1160-1173. DOI=http://dx.doi.org/10.1109/TNET.2005.857111 PDF
- Exploring the Vickrey-Clarke-Groves Mechanism for Electricity Markets. P. G. Sessa, N. Walton, M. Kamgarpour. In IFAC-PapersOnLine, Volume 50, Issue 1, 2017, Pages 189-194. https://doi.org/10.1016/j.ifacol.2017.08.032. ArXiv PDF
- Bandwidth sharing and admission control for elastic traffic. L. Massoulié, J. Roberts. Telecommunication Systems (2000) 15: 185. https://doi.org/10.1023/A:1019138827659 PDF
- Maximizing throughput in wireless networks via gossiping. E Modiano, D Shah, G Zussman. ACM SIGMETRICS Performance Evaluation Review 34 (1), 27-38. 2006. PDF
- Interval consensus: From quantized gossip to voting. Florence Bénézit, Patrick Thiran, Martin Vetterli. ICASSP 2009: 3661-3664. PDF
- Fast Distributed Algorithms for Computing Separable Functions. D. Mosk-Aoyama and D. Shah. IEEE Transactions on Information Theory, vol. 54, no. 7, pp. 2997-3007, July 2008. doi: 10.1109/TIT.2008.924648 PDF
- Open, closed and mixed networks of queues with different classes of customers. Baskett, F.; Chandy, K. Mani; Muntz, R.R.; Palacios, F.G. (1975). Journal of the ACM. 22 (2): 248-260. PDF
- Product-form queueing networks with negative and positive customers. Gelenbe, Erol (1991). Journal of Applied Probability. 28 (3): 656-663. doi:10.2307/3214499. PDF
- Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks. L. Tassiulas and A. Ephremides. IEEE Transactions on Automatic Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992. PDF

Cours

Routage distribué et les algorithmes de plus court chemin
- Cours (11 et 18 Sep)
  - Sources :
    Rappels sur les algorithmes de plus courts chemins : Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press. 2009.
    Distributed Bellman-Ford : Chapter 5 of Dimitri P. Bertsekas and Robert G. Gallager. Data Networks (2nd Edition) . Online : http://web.mit.edu/dimitrib/www/datanets.html
    Modèle algébrique du routage : M. Gondran and M. Minoux. Graphes, dioïdes et semi-anneaux: nouveaux modèles et algorithmes. Editions Technique et Documentation, Paris, 2001.
  - Un peu d'algèbre : Monoïdes, semi-anneaux, dioïdes. . .
  - Rappel sur les algorithmes de plus court chemin
- TD
  - 18 Sep : exercices
  - 25 Sep : exercices
Chaînes de Markov et le théorème de Perron-Frobenius

Cours

Cours 25 Sep : PageRank et les chaînes de Markov
Cours 2 Oct : HITS, Gossip et le théorème de Perron-Frobenius
Sources :
PageRank : S. Brin, L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine, Computer Networks and ISDN Systems, 1998.
HITS: J.M. Kleinberg. Authoritative Sources in a Hyperlinked Environment, Journal of the ACM, 1999
Chaînes de Markov : Pierre Brémaud. Initiation aux probabilités et aux chaînes de Markov, Springer, 2009.

TD 2 Oct :
- exercices
- Notebook

Propriétés de stabilité et politique MaxWeight
- Cours 9 et 16 Oct : théorème de Foster; politique MaxWeight. Applications : commutateurs (switches) et réseaux P2P sans fil.
  - Transparents
  - Reversibilité
- TD 16 Oct

Simulation à événements discrets
- Cours 23 Oct : Schémas de Matthes et simulation à événements discrets, Processus de Poisson
  - Transparents
- TD 6 Nov : Notebook

Processus de Markov et les files d'attente
- Cours 13 Nov : Processus de Markov, reversibilité, file M/M/1 et le théorème de Burke
- Cours 20 Nov : Formule de Little, PASTA, réseaux de Jackson

Contrôle de congestion
- Cours 27 Nov : Modèle de partage de ressources, équité max-min, équité proportionnelle, allocation utilitaire
- Cours 4 Dec : Stabilité d'un système dynamique et allocation dynamique de ressources
- Cours 11 Dec : Protocole TCP, les enchères et les jeux