Ordonnancement - Chapitre 3 - PDF

EN LB Ordonnancement JE OU Yassine Boujelben EB SIN Chapitre 3...

EN LB Ordonnancement JE OU Yassine Boujelben EB SIN Chapitre 3 S YA Yassine Boujelben Ordonnancement Chapitre 3 1 / 52 Plan EN LB 1 Introduction JE 2 Exigences d’une discipline d’ordonnancement OU EB 3 Choix fondamentaux SIN 4 Ordonnancement des connexions BE S 5 Ordonnancement des connexions GS YA Yassine Boujelben Ordonnancement Chapitre 3 2 / 52  Introduction Ordonnancement EN LB Les réseaux de données permettent aux utilisateurs de partager des ressources JE Le partage provoque toujours la contention OU L’ordonnancement permet de résoudre la contention : Qui est le suivant ? EB Étant donné un ensemble de paquets dans une file de service (multiplexage statistique), le serveur utilise une discipline SIN d’ordonnancement pour déterminer quel paquet transmettre L’ordonnancement est la clé pour un partage équitable des S ressources et une garantie de performance YA Yassine Boujelben Ordonnancement Chapitre 3 3 / 52  Introduction Fonctions d’ordonnacement EN Une discipline d’ordonnancement réalise 2 fonctions : LB 1 décide l’ordre de service des requêtes de transmission ; 2 gère la file d’attente de service. JE Exemple : serveur web OU Ensemble de requêtes en attente d’un serveur web ; EB La discipline d’ordonnancement décide l’ordre de service → différents délais d’attente moyens pour différentes requêtes. SIN Si les requêtes arrivent plus rapidement que la capacité de service, elles seront stockées dans la file d’attente. Si l’espace de stockage est plein, il faut éventuellement rejeter des requêtes. S La discipline d’ordonnancement décide quelle requête rejeter → YA différents taux de perte pour différents utilisateurs. Yassine Boujelben Ordonnancement Chapitre 3 4 / 52  Introduction Où ? EN LB À chaque endroit où la contention peut arriver JE À chaque couche de la pile des protocoles Souvent étudié dans la couche réseau, au niveau des tampons de OU sortie des commutateurs Nouveaux problèmes : EB Systèmes OFDMA dans les réseaux 4G (WiMax ou LTE) : le problème d’ordonnancement est lié au problème d’allocation de SIN ressources Ordonnancement multicast des services multicast/Broadcast dans les réseaux 4G : Multimedia Broadcast Multicast Service (MBMS) S YA Yassine Boujelben Ordonnancement Chapitre 3 5 / 52  Introduction Besoin d’une discipline d’ordonnancement EN LB Les applications ont différentes exigences de QoS ; JE Deux grandes classes d’applications : OU 1 BE (élastique, non temps réel) : e.g., e-mail, FTP,... 2 Service garanti (temps réel) : e.g., VoIP, Vidéo interactive,... EB Ce qu’une discipline d’ordonnancement peut réaliser : Fournir à différents utilisateurs différentes QoS SIN Allouer la bande passante, délai et perte Déterminer le niveau d’équité du réseau S YA Yassine Boujelben Ordonnancement Chapitre 3 6 / 52  Exigences d’une discipline d’ordonnancement Exigences EN LB JE Une discipline d’ordonnancement idéale doit : OU 1 être facile à implémenter 2 être équitable EB 3 fournir des bornes de performance 4 faciliter les décisions de contrôle d’admission S SIN YA Yassine Boujelben Ordonnancement Chapitre 3 7 / 52  Exigences d’une discipline d’ordonnancement Exigence 1 : Facilité d’implémentation EN LB La discipline d’ordonnancement doit prendre une décision une fois JE par quelques µs (paquet) ou ms (e.g., 1ms LTE, 5ms WiMAX) OU Doit avoir une faible complexité (peu d’instructions) Le traitement par paquet doit être aussi indépendant que possible EB 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 O(1) SIN Un routeur de cœur du réseau peut servir 100 000 connexions simultanées ! S YA Yassine Boujelben Ordonnancement Chapitre 3 8 / 52  Exigences d’une discipline d’ordonnancement Exigence 2 : Équité EN Une allocation non équitable est le résultat d’une compétition non contrôlée entre les utilisateurs sur la même ressource LB La discipline d’ordonnancement permet de faire ce contrôle Parfois on veut augmenter l’équité tout en supportant la priorité des JE utilisateurs premium Il y a souvent un compromis entre équité et optimalité OU EB S SIN YA Yassine Boujelben Ordonnancement Chapitre 3 9 / 52  Exigences d’une discipline d’ordonnancement Équité vs. Optimalité EN LB A JE Un réseau simple de 3 noeuds γAB OU et 2 arcs de capacité 1 chacun 1 3 flots avec une demande 1 : EB B γAC A→B, A→C, B→C Allocation optimale du débit : SIN 1 γBC γAB = γBC = 1 et γAC = 0 C S YA Yassine Boujelben Ordonnancement Chapitre 3 10 / 52  Exigences d’une discipline d’ordonnancement Qu’est-ce qu’une allocation équitable ? EN A LB Tous les utilisateurs auront le JE même débit ? 1 γAD = γBC = γCD = 0.5 OU Mais, γAD aura en fait plus B de ressources (sur 3 liens) EB γBC γAD Tous les utilisateurs auront la 1 même quantité de ressources SIN réseaux ? C γBC = γCD = 0.75 γAD = 0.25 (total sur 3 S liens= 0.75) 1 γCD YA D Yassine Boujelben Ordonnancement Chapitre 3 11 / 52  Exigences d’une discipline d’ordonnancement Qu’est-ce qu’une allocation équitable ? EN A LB JE Chaque utilisateur reçoit un 1 débit proportionnel à la OU quantité de dommages B (interférence) qu’il fait sur les autres utilisateurs ? EB γBC γAD 2 1 γBC = γCD = 3 SIN 1 γAD = (interférence totale C 3 2 sur les 2 autres liens = ) S 3 1 γCD YA D Yassine Boujelben Ordonnancement Chapitre 3 12 / 52  Exigences d’une discipline d’ordonnancement Exemple EN LB JE On suppose qu’on a une seule ressource de capacité 30 OU Par exemple : un lien, une file dans un routeur, etc. Les demandes des utilisateurs : A = 20, B = 20, C = 20 EB L’allocation équitable est triviale Mais, quelle allocation lorsque A = 4, B = 20, C = 20 S SIN YA Yassine Boujelben Ordonnancement Chapitre 3 13 / 52  Exigences d’une discipline d’ordonnancement Équité max-min EN LB Une allocation est équitable s’il elle satisfait le critère d’allocation max-min. JE Intuitivement : OU une connexion n’aura pas plus qu’elle ne demande L’excès, s’il existe, sera partagé de façon égale EB Formellement : Les ressources sont allouées dans l’ordre des demandes croissantes SIN Aucune source n’aura une allocation supérieure à sa demande Les sources avec des demandes insatisfaites obtiennent une S allocation égale des ressources. YA Yassine Boujelben Ordonnancement Chapitre 3 14 / 52  Exigences d’une discipline d’ordonnancement Exemple EN LB Calculer l’allocation max-min équitable d’un ensemble de 4 sources A, B, C et D avec des demandes 2, 2.6, 4 et 5 quand la JE ressource a une capacité de 10. 1 Classer les demandes par ordre croissant (2, 2.6, 4, 5) OU 2 Allouer 2 unités à chaque source. La première demande est satisfaite EB Il reste 2 unités de capacité en excès 3 Allouer 0.6 unité aux sources B, C et D. SIN La deuxième demande est satisfaite Il reste 0.2 unité de capacité en excès 4 Allouer 0.1 unité de capacité à C et D. S 5 L’allocation finale est 2, 2.6, 2.7, 2.7 YA Yassine Boujelben Ordonnancement Chapitre 3 15 / 52  Exigences d’une discipline d’ordonnancement Généralisation à un réseau EN LB Étant donné un réseau de M noeuds et N arcs, chaque arc s a JE une capacité cs OU On a un ensemble de flots en cours. Chaque flot j a une demande rj et un chemin fixe pj EB Algorithme : Augmenter tous les flots de façon égale jusqu’à la saturation d’un lien ou un flot aura toute sa demande SIN Fixer le débit des flots goulots d’étranglement Continuer avec les flots non fixés S YA Yassine Boujelben Ordonnancement Chapitre 3 16 / 52  Exigences d’une discipline d’ordonnancement Exemple EN LB A JE 10 rAB = 6 OU B rAC = 8 10 EB SIN rBC = 2 C S YA Yassine Boujelben Ordonnancement Chapitre 3 17 / 52  Exigences d’une discipline d’ordonnancement Première itération EN LB A JE rAB = 6 OU 10 γAB = 2 Allouer 2 à tous les flots EB La demande BC est B rAC = 8 γAC = 2 satisfaite SIN 10 rBC = 2 γBC = 2 C S YA Yassine Boujelben Ordonnancement Chapitre 3 18 / 52  Exigences d’une discipline d’ordonnancement Deuxième itération EN LB A JE rAB = 6 OU Continuer à accroître le 10 γAB = 5 trafic de façon égale. EB Quand AB et AC auront B rAC = 8 γAC = 5 chacun 5, le lien (A, B) SIN est saturé 10 rBC = 2 γBC = 2 C S YA Yassine Boujelben Ordonnancement Chapitre 3 19 / 52  Exigences d’une discipline d’ordonnancement Discussion EN L’équité est intuitivement une bonne idée LB Elle assure une protection entre les flux Les sources qui se comportent mal ne peuvent pas envahir les JE autres Construit automatiquement des firewalls autour des flots OU volumineux L’équité est un objectif global, mais l’ordonnancement est local EB Chaque source doit restreindre son flot à la plus faible allocation équitable pour garantir l’équité globale SIN Dans un réseau dont le profile de trafic change rapidement, même si chaque commutateur fait des allocations localement équitables, les utilisateurs peuvent ne pas percevoir des allocations S globalement équitables YA Pendant que la source s’adapte à l’allocation courante, le trafic change ! Yassine Boujelben Ordonnancement Chapitre 3 20 / 52  Exigences d’une discipline d’ordonnancement Exigence 3 : Bornes de performance EN LB JE Une façon d’obtenir un niveau de service désiré OU Peuvent être déterminées de façon déterministe ou statistique Paramètres de performance : EB Bande passante Délai Gigue SIN Perte S YA Yassine Boujelben Ordonnancement Chapitre 3 21 / 52  Exigences d’une discipline d’ordonnancement Exigence 4 : Facilité du contrôle d’admission EN LB Le contrôle d’admission est nécessaire pour fournir la QoS JE Une ressource surchargée ne peut pas garantir la performance OU Le choix de la discipline d’ordonnancement affecte la complexité de l’algorithme de contrôle d’admission : EB Étant donné un ensemble de connexions en cours et un descripteur pour une nouvelle connexion, une entité de contrôle (routeur, switch, MCE) doit déterminer s’il est possible de satisfaire les SIN exigences d’une nouvelle connexion sans dégrader la performance des connexions en cours. S YA Yassine Boujelben Ordonnancement Chapitre 3 22 / 52  Choix fondamentaux Choix fondamentaux EN LB JE 1 Nombre de niveaux de priorité OU 2 Sans oisiveté (work conserving) vs. avec oisiveté (non-work conserving) EB 3 Degré d’agrégation 4 Ordre de service dans le même niveau S SIN YA Yassine Boujelben Ordonnancement Chapitre 3 23 / 52  Choix fondamentaux Choix 1 : Priorité EN LB JE Un paquet est servi à partir d’un niveau de priorité seulement s’il n’existe aucun paquet dans les niveaux supérieurs OU Le niveau supérieur aura le plus faible délai EB Surveiller la famine ! En général, on associe les niveaux de priorité aux classes de délai SIN Facile à implémenter S YA Yassine Boujelben Ordonnancement Chapitre 3 24 / 52  Choix fondamentaux Choix 2 : Sans oisiveté vs. avec oisiveté EN Un ordonnanceur non oisif est libre seulement quand il n’y a LB aucun paquet en attente de service JE Un ordonnanceur oisif peut être libre même s’il y a des paquets en attente OU À première vue, un ordonnanceur oisif ne fait pas de sens ! Pourquoi laisser la ligne libre, perdant des ressources, alors qu’on EB peut profiter du temps pour envoyer du trafic ? En libérant la ligne (attendre que le paquet soit éligible), SIN l’ordonnanceur oisif rend le trafic descendant plus prédictible → réduire la taille des files d’attente de sortie S réduire la gigue YA Comment choisir l’instant d’éligibilité ? Yassine Boujelben Ordonnancement Chapitre 3 25 / 52  Choix fondamentaux Choix 3 : Degré d’agrégation EN LB Plus d’agrégation → ultimement même qualité de service JE moins d’états moins cher OU MAIS, moins d’individualisation Moins d’agrégation → ultimement traitement par flot EB Solution : Degré d’agrégation intermédiaire agréger à une classe : les membres d’une classe auront le même SIN niveau de performance pas de protection au sein d’une même classe S YA Yassine Boujelben Ordonnancement Chapitre 3 26 / 52  Choix fondamentaux Choix 4 : Service dans un niveau de priorité EN LB Dans l’ordre d’arrivée (FIFO) ou dans l’ordre d’un service tag service tags : peuvent arbitrairement réorganiser la file d’attente JE Besoin de trier la file d’attente, ce qui peut être coûteux OU FIFO Ne permet pas aux paquets qui ont besoin d’un plus faible délai de EB passer en tête de la file pas de protection Ce n’est pas max-min équitable SIN Service tags Avec un choix approprié, on peut imposer des bornes de délai et S assurer la protection YA Yassine Boujelben Ordonnancement Chapitre 3 27 / 52  Ordonnancement des connexions BE Wheighted Round Robin (WRR) EN Servir un paquet de chaque file non vide à tour de rôle LB Inéquitable si les paquets ont des longueurs ou des poids différents JE Poids différents, même longueur de paquets OU servir plus d’un paquet par visite, après normalisation pour obtenir des poids entiers Ex., 3 connexions de poids 0.5, 0.75 et 1 ⇒ après normalisation, EB au aura les poids 2, 3 et 4. Poids différents, longueurs de paquets différentes SIN Normaliser les poids par la taille moyenne des paquets exemple : poids {0.5, 0.75, 1}, tailles moyennes des paquets {50, 500, 1500} S normaliser les poids : YA {0.5/50, 0.75/500, 1/1500} = {0.01, 0.0015, 0.000666}, normaliser encore {60,9,4} Yassine Boujelben Ordonnancement Chapitre 3 28 / 52  Ordonnancement des connexions BE Problèmes avec Wheighted Round Robin EN LB 1 Si la source ne peut pas prédire la taille moyenne des paquets, WRR ne peut pas allouer les ressources équitablement JE Avec des paquets de tailles variables et différents poids, on doit savoir la taille moyenne des paquets à l’avance OU 2 Équitable seulement sur une échelle de temps supérieure à la durée d’un cycle. EB Si une connexion a un poids faible ou le nombre de connexions est grand ⇒ longue période d’iniquité SIN Exemple : Considérons un lien de capacité 45 Mbps transportant 500 connexions, chacune a une taille moyenne de paquet de 500 octets, 250 connexions de poids 1 et 250 de poids 10. Si aucune S connexion ne sera libre, quelle est la longueur d’un cycle ? YA Yassine Boujelben Ordonnancement Chapitre 3 29 / 52  Ordonnancement des connexions BE Ordonnancement des connexions BE EN L’équité est la principale exigence LB Réalisable par un Generalized processor sharing (GPS) idéal Ordonnanceur théorique : JE Visiter chaque file non-vide de façon cyclique : round robin OU Servir une quantité infinitésimal de bits de chaque file non vide GPS est max-min équitable ! EB S’il y a N connexions, chacune aura 1/N de la ressource Si une connexion n’utilise pas toute son allocation, l’ordonnanceur utilise ce temps pour faire un autre round robin et servir les autres SIN connexions de façon égale C’est l’équité max-min par définition S On ne peut pas implémenter GPS, comment on peut l’émuler ? YA on veut une allocation aussi équitable que possible implémentation efficace (max throughput) Yassine Boujelben Ordonnancement Chapitre 3 30 / 52  Ordonnancement des connexions BE Weighted Fair Queueing (WFQ) EN LB WFQ émule GPS (rappel : GPS est la discipline la plus équitable) Gère mieux les tailles et poids différents JE Calcule le temps virtuel de fin de service d’un paquet avec GPS OU Servir les paquets dans l’ordre de leurs temps virtuels de fin On appelle le temps virtuel de fin de service un numéro de fin EB pour montrer que c’est tout simplement un service tag Une connexion est active lorsqu’elle a des données à transmettre SIN Le nombre de cycles détermine le nombre de cycles déjà terminés Le plus grand numéro de fin d’un paquet dans la file d’une S connexion active est supérieur au nombre de cycles courant YA Yassine Boujelben Ordonnancement Chapitre 3 31 / 52  Ordonnancement des connexions BE WFQ : Calcul du numéro de fin EN On suppose que dans chaque cycle, le serveur sert un bit de LB chaque connexion active JE R(t) : nombre de cycles à l’instant t ; F (i, k) : numéro de fin du k ème paquet de la connexion i OU P (i, k) : longueur du k ème paquet de la connexion i en bits On suppose que le cycle courant est R(t) et qu’un paquet k arrive à la file i : EB Si i est vide (inactive) : F (i, k) = R(t) + P (i, k) SIN Si i est active : F (i, k) = F (i, k − 1) + P (i, k) Donc : S F (i, k) = max{F (i, k − 1), R(t)} + P (i, k) (1) YA Servir les paquets dans l’ordre croissant des numéros de fin Yassine Boujelben Ordonnancement Chapitre 3 32 / 52  Ordonnancement des connexions BE WFQ : Calcul du nombre de cycles EN Typiquement : nombre de cycles = nombre de cycles de service complétés à un instant donné LB Si le serveur n’a pas encore servi toutes les connexions dans un JE cycle ? Si de nouvelles connexions arrivent au milieu d’un cycle ? OU Redéfinir le nombre de cycles comme une variable réelle qui croit à un taux inversement proportionnel au nombre courant de EB connexions actives n(t) : nombre de connexions actives à l’instant t ; SIN Si x est un laps de temps dans lequel le nombre de connexions actives ne change pas, alors : S x YA R(t + x) = R(t) + (2) n(t) Yassine Boujelben Ordonnancement Chapitre 3 33 / 52  Ordonnancement des connexions BE WFQ : Ajouter les poids des connexions EN LB L’ordonnanceur GPS sert chaque connexion i dans chaque cycle JE proportionnellement à son poids wi W (t) : somme des poids des connexions actives à l’instant t. OU Équations générales : EB P (i, k) F (i, k) = max{F (i, k − 1), R(t)} + (3) wi SIN x R(t + x) = R(t) + (4) W (t) S YA Yassine Boujelben Ordonnancement Chapitre 3 34 / 52  Ordonnancement des connexions BE Exemple EN LB On considère un ordonnanceur WFQ avec 3 connexions de JE mêmes poids A, B et C. Le taux de service sur le lien est de 1 unité/s. OU À l’instant 0 : des paquets de tailles 1, 2 et 2 unités arrivent à A, B et C, respectivement. EB À l’instant 4 : un paquet de taille 2 arrive à A 1 Calculer le numéro de fin de tous les paquets SIN 2 Quelle est le nombre de cycles quand le système devient inactif ? 3 Quand est-ce que cela arrive ? S YA Yassine Boujelben Ordonnancement Chapitre 3 35 / 52  Ordonnancement des connexions BE Solution : numéros de fin EN LB On commence par une simulation GPS JE À l’instant 0, R(0) = 0 OU Toutes les files sont vides, donc les numéros de fin pour les paquets sont : F (A, 1) = 1, F (B, 1) = 2 et F (C, 1) = 2 EB Noter que le numéro de fin n’est pas le temps de fin de service En effet, le 1er paquet à servir est le paquet 1 de A, qui se termine à 1. Ensuite le paquet de B ou de C. Si on choisit aléatoirement le SIN paquet B, son service se termine à l’instant 3 et finalement le paquet de C se termine à l’instant 5. S YA Yassine Boujelben Ordonnancement Chapitre 3 36 / 52  Ordonnancement des connexions BE Solution : numéros de fin EN LB Pour calculer le numéro de fin du 2nd paquet de A, on doit connaître le nombre de cycles à l’instant 4 JE À l’instant 0, on a 3 connexions, donc le nombre de cycles OU 1 augmente à un taux de unité/s 3 EB À l’instant 3 (sec) : R(3) = 1 Le paquet (A,1) termine son service et A devient inactif. SIN Entre les instants 3 et 4, on a 2 connexions actives, donc le 1 S nombre de cycles augmente à un taux unité/s 2 YA Yassine Boujelben Ordonnancement Chapitre 3 37 / 52  Ordonnancement des connexions BE Solution : numéros de fin EN LB À l’instant 4 (sec) : JE 1 R(4) = 1 + = 1.5 2 OU B et C sont toujours actives (2 > 1.5) et un nouveau paquet arrive à A. A est vide, donc : F (A, 2) = R(4) + P (A, 2) = 3.5 EB 1 Le nombre de cycles augmente de nouveau à un taux de unité/s, 3 donc ça prend encore 1.5 sec pour terminer le 2ème cycle SIN L’arrivée de ce paquet n’affecte pas les numéros de fin des paquets qui sont déjà dans B et C. S YA Yassine Boujelben Ordonnancement Chapitre 3 38 / 52  Ordonnancement des connexions BE Solution : ordonnanceur inactif EN LB À l’instant 5.5 (sec) : JE R(5.5) = 2 OU Les paquets (B,1) et (C,1) termine simultanément leurs services (rappel GPS) Le nombre de cycles commence à augmenter à un taux de 1 unité/s À l’instant 7 (sec) : R(7) = 3.5 EB SIN Le paquet (A,2) termine son service. S YA Yassine Boujelben Ordonnancement Chapitre 3 39 / 52  Ordonnancement des connexions BE Solution : ordonnanceur WFQ EN À l’instant 0 (sec) : LB Paquets en attente : F (A, 1) = 1, F (B, 1) = 2 et F (C, 1) = 2 A est servi en premier JE À l’instant 1 (sec) : OU Paquets en attente : F (B, 1) = 2 et F (C, 1) = 2 B ou C peut être servie, on choisit aléatoirement B EB À l’instant 3 (sec) : Paquets en attente : F (C, 1) = 2 SIN À l’instant 5 (sec) : Paquets en attente : F (A, 2) = 3.5 Servir A S À l’instant 7 (sec) : YA Le système devient inactif Yassine Boujelben Ordonnancement Chapitre 3 40 / 52  Ordonnancement des connexions BE Solution : ordonnanceur WFQ EN LB 4 numéro de fin A Nombre de cycles JE 3.5 3 OU 2.5 numéro de fin B,C 2 EB 1.5 1 SIN 0.5 0 0 1 2 3 4 5 6 7 8 S YA Temps Yassine Boujelben Ordonnancement Chapitre 3 41 / 52  Ordonnancement des connexions BE Autre exemple EN LB JE OU EB SIN 11 sources S1 ,... , S11 , avec S1 de poids 10 et les autres 1 S YA la source S1 a 11 paquets à transmettre, les autres 1 seul tous les paquets sont de taille 1 unité, le débit du lien est de 1 unité par sec Yassine Boujelben Ordonnancement Chapitre 3 42 / 52  Ordonnancement des connexions BE Simulation GPS EN Instant 0 : R(0) = 0 1 1 F (S1 , p11 ) = 0 + = LB 10 10 1 F (Si , pi1 ) = 0 + = 1 pour i = 2,... , 11 JE 1 1 1 R(t) augmente a un taux P = w 20 OU i actives i Ordonnanceur GPS : à l’instant 20 sec, un paquet de chaque session termine le service, ensuite le paquet 11 de S1 est servi. EB Nombre de cycles p10 1 1 SIN 1 , p2 ,... , p11 1 S YA 0 0 2 4 6 8 10 12 14 16 18 20 Temps Yassine Boujelben Ordonnancement Chapitre 3 43 / 52  Ordonnancement des connexions BE Simulation GPS EN LB JE OU EB S SIN YA Yassine Boujelben Ordonnancement Chapitre 3 44 / 52  Ordonnancement des connexions BE Ordonnanceur WFQ EN LB JE OU EB S SIN Servir les 9 premiers paquets de la source 1 YA Le 10ème paquet a le même numéro de fin que les autres : les servir séquentiellement Servir enfin le 11ème paquet de la source 1 Yassine Boujelben Ordonnancement Chapitre 3 45 / 52  Ordonnancement des connexions BE WF2 Q EN Sous WFQ, une connexion peut recevoir substantiellement plus LB de service que GPS ; d’autres auront plus de période d’attente JE Inéquitable Worst Case Fair WFQ (WF2 Q) a une meilleure équité OU On peut démontrer qu’aucun ordonnanceur paquet par paquet ne peut être plus équitable EB WFQ : À partir de tous les paquets en attente de service, servir celui qui a le plus petit numéro de fin SIN WF2 Q : À partir de tous les paquets en attente de service, servir celui qui a le plus petit numéro de fin, mais considérer uniquement S les paquets qui sont déjà en service dans le système GPS YA correspondant. Yassine Boujelben Ordonnancement Chapitre 3 46 / 52  Ordonnancement des connexions BE Retour sur l’exemple : Ordonnanceur WF2 Q EN LB JE OU EB S SIN Servir le premier paquet de la source 1 YA Quand il termine (temps=1), le paquet 2 n’a pas encore commencé sous GPS (temps=2), donc un paquet d’une autre source peut être servi Yassine Boujelben Ordonnancement Chapitre 3 47 / 52  Ordonnancement des connexions GS Ordonnancement des connexions GS EN LB JE Pour les connexions BE, l’objectif est l’équité OU Pour les connexions service garanti : Quelle garantie de performance est réalisable ? combien c’est facile de réaliser le contrôle d’admission ? EB On va étudier quelques mécanismes qui fournissent des garanties de performance. S SIN YA Yassine Boujelben Ordonnancement Chapitre 3 48 / 52  Ordonnancement des connexions GS WFQ EN LB WFQ peut aussi fournir des garantis de performance JE Borne de débit : Rapport des poids * capacité du lien OU Par ex. : des connexions de poids 1, 2 et 7 ; lien de capacité 10 les connexions auront au moins 1, 2 et 7 unités de BW chacune EB Borne de délai On suppose que la connexion envoie à débit "raisonnable" SIN Plus précisément : la connexion doit être contrôlée par un seau à jeton Nombre de bits transmis dans [t1 , t2 ] ≤ ρ(t2 − t1 ) + σ S YA Yassine Boujelben Ordonnancement Chapitre 3 49 / 52  Ordonnancement des connexions GS Théorème de Parekh-Gallager EN On considère une connexion i contrôlée par un seau à jetons (ρ(i), σ(i)), ayant une longueur max de paquet Pmax (i) LB Cette connexion passe à travers K ordonnanceurs WFQ tel que JE dans le k ème ordonnanceur il existe une BW totale r(k) et elle aura un poids ϕ(i, k) OU Soit g(i, k) le débit alloué à i par le k ème ordonnanceur, alors : EB ϕ(i, k) g(i, k) = P r(k) (5) j ϕ(j, k) SIN Soit g(i) le plus petit débit sur tous les k. On suppose g(i) ≥ ρ(i) : K−1 K σ(i) X Pmax (i) X Pmax S end − to − end − delay ≤ + + (6) g(i) g(i, k) r(k) YA |{z} |k=1 {z } |k=1 {z } (1) (2) (3) Yassine Boujelben Ordonnancement Chapitre 3 50 / 52  Ordonnancement des connexions GS Signification EN 1 représente le terme GPS (taille de paquet infinitésimale) LB Quand la taille maximale de paquet sur le réseau Pmax ≈ 0, le délai est borné par le terme (1) JE Bien que la connexion traverse une série d’ordonnanceurs, elle se OU comporte comme si elle est servie par un seul ordonnanceur d’un débit g(i) Si elle envoie un burst σ(i), elle aura un délai σ(i)/g(i) EB 2 et 3 représentent la correction GPS à WFQ 2 modélise la situation quand le paquet arrive après son instant de SIN service sous GPS (pénalité store et forward) 3 est indépendant de g(i). Si un paquet de i arrive à un ordonnanceur occupé, il devra attendre jusqu’à Pmax /r(k) avant S d’être servi, où Pmax est la longueur maximale d’un paquet YA autorisée sur le réseau. Yassine Boujelben Ordonnancement Chapitre 3 51 / 52  Ordonnancement des connexions GS Exemple EN LB JE On considère une connexion contrôlée par un seau à jetons (16384 OU octets, 150 kbps) qui traverse 10 sauts sur un réseau où tous les liens ont une BW de 45 Mbps. Si le paquet le plus grand permis sur le réseau ne doit pas dépasser 8192 octets, calculer la valeur de g qui va EB garantir un délai end-to-end de 100 ms. On supposera un délai de propagation de 30 ms. S SIN YA Yassine Boujelben Ordonnancement Chapitre 3 52 / 52