Ordonnancement PDF

## Ordonnancement ### Introduction * Les réseaux de données permettent aux utilisateurs de partager des ressources. * Le partage provoque toujours la contention. * L'ordonnancement permet de résoudre la contention: * Qui est le suivant? * Étant donné un ensemble de paquets dans une file de...

## Ordonnancement ### Introduction * Les réseaux de données permettent aux utilisateurs de partager des ressources. * Le partage provoque toujours la contention. * L'ordonnancement permet de résoudre la contention: * Qui est le suivant? * Étant donné un ensemble de paquets dans une file de service (multiplexage statistique), le serveur utilise une discipline d'ordonnancement pour déterminer quel paquet transmettre. * L'ordonnancement est la clé pour un partage équitable des ressources et une garantie de performance. ### Fonctions d'ordonnancement * Une discipline d'ordonnancement réalise 2 fonctions: * Décide l'ordre de service des requêtes de transmission. * Gère la file d'attente de service. ### Exemple: serveur web * Ensemble de requêtes en attente d'un serveur web. * La discipline d'ordonnancement décide l'ordre de service → différents délais d'attente moyens pour différentes requêtes. * Si les requêtes arrivent plus rapidement que la capacité du service, elles seront stockées dans la file d'attente. Si l'espace de stockage est plein, il faut éventuellement rejeter des requêtes. * La discipline d'ordonnancement décide quelle requête rejeter → différents taux de perte pour différents utilisateurs. ### Où ? * À chaque endroit où la contention peut arriver. * À chaque couche de la pile des protocoles. * Souvent étudié dans la couche réseau, au niveau des tampons de sortie des commutateurs. * Nouveaux problèmes: * Systèmes OFDMA dans les réseaux 4G (WiMax ou LTE): le problème d'ordonnancement est lié au problème d'allocation de ressources. * Ordonnancement multicast des services multicast/Broadcast dans les réseaux 4G: Multimedia Broadcast Multicast Service (MBMS). ### Besoin d'une discipline d'ordonnancement * Les applications ont différentes exigences de QoS. * Deux grandes classes d'applications: * BE (élastique, non temps réel): e.g., e-mail, FTP,... * Service garanti (temps réel): e.g., VoIP, Vidéo interactive,... * Ce qu'une discipline d'ordonnancement peut réaliser: * Fournir à différents utilisateurs différentes QoS. * Allouer la bande passante, délai et perte. * Déterminer le niveau d'équité du réseau. ## Exigences d'une discipline d'ordonnancement ### Exigences * Une discipline d'ordonnancement idéale doit: * être facile à implémenter. * être équitable. * fournir des bornes de performance. * faciliter les décisions de contrôle d'admission. ### Exigence 1: Facilité d'implémentation * La discipline d'ordonnancement doit prendre une décision une fois par quelques με (paquet) ou ms (e.g., 1ms LTE, 5ms WiMAX). * Doit avoir une faible complexité (peu d'instructions). * Le traitement par paquet doit être aussi indépendant que possible du nombre de connexions. * Si un commutateur sert _N_ connexions simultanées, une complexité par paquet de _O(N)_ n'est pas acceptable, on préfère _(1)_. * Un routeur de cœur du réseau peut servir 100 000 connexions simultanées! ### Exigence 2: Équité * Une allocation non équitable est le résultat d'une compétition non contrôlée entre les utilisateurs sur la même ressource. * La discipline d'ordonnancement permet de faire ce contrôle. * Parfois on veut augmenter l'équité tout en supportant la priorité des utilisateurs premium. * Il y a souvent un compromis entre équité et optimalité. ### Équité vs. Optimalité * Un réseau simple de 3 noeuds et 2 arcs de capacité 1 chacun. * 3 flots avec une demande 1: A→B, A→C, B→C. * Allocation optimale du débit: YAB = BC = 1 et YAC. This is a description of the provided image, excluding the image itself.