Allocation max-min équitable

Ordonnancement

• Le sujet porte sur l'ordonnancement dans les réseaux de données.
• Les réseaux de données permettent aux utilisateurs de partager des ressources.
• Le partage provoque des contentions.
• L'ordonnancement résout les contentions en déterminant le suivant à servir.
• 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 deux fonctions :
  • Décide l'ordre des requêtes de transmissions
  • Gère la file d'attente des services.
• L'exemple d'un serveur web est mentionné.
• L'ensemble des requêtes en attente d'un serveur web est géré par l'ordonnancement.
• Le temps d'attente moyen varie selon les requêtes.
• Si la capacité de service est dépassée, les requêtes sont mises en attente.
• L'espace de stockage peut être plein, nécessitant le rejet des paquets.
• Différents taux de perte selon les utilisateurs.

Où?

• La contention se produit à chaque endroit où elle peut arriver.
• On étudie la contention souvent dans la couche réseau, au niveau des tampons de sortie des commutateurs de réseaux.
• Les systèmes OFDMA dans les réseaux 4G (WiMax ou LTE) présentent des problèmes d'ordonnancement liés à l'allocation de ressources.
• L'ordonnancement multicast des services multicast/Broadcast dans les réseaux 4G (MBMS) est aussi abordé.

Besoins d'une discipline d'ordonnancement

• Les applications ont des exigences de qualité de service (QoS) variées.
• Deux grandes classes d'applications sont distinguées :
  • Les applications élastiques (non temps réel) : exemples : email, FTP…
  • Les applications temps réel : exemples : VoIP, vidéo interactive.
• L'ordonnancement permet de fournir des QoS différentes aux utilisateurs.
• L'allocation de la bande passante et la gestion du délai sont des fonctionnalités centrales de l'ordonnancement.
• L'équité de l'accès au réseau est un élément crucial de l'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

• Une discipline d'ordonnancement doit prendre une décision rapidement, par exemple en quelques microsecondes (µs) ou millisecondes (ms).
• La complexité du traitement par paquet doit être faible afin de ne pas ralentir le réseau.
• Le traitement par paquet doit être indépendant du nombre de connexions.

Exigence 2 : Équité

• Une allocation non équitable est le résultat d'une compétition non contrôlée.
• L'ordonnancement permet de contrôler cette compétition.
• L'équité des utilisateurs est à prendre en considération également, avec la prise en compte de la priorité éventuelle des utilisateurs premium.
• Il faut souvent faire des compromis entre l'équité et l'optimalité.

Équité vs. Optimalité

• Un réseau simple de 3 noeuds et 2 arcs de capacité 1 chacun.
• Illustre la demande de flux de 1 (A→B, A→C, B→C)
• L'allocation optimale du débit est YAB = YBC = 1 et YAC = 0.

Qu'est-ce qu'une allocation équitable?

• Tous les utilisateurs doivent avoir le même débit.
• Tous les utilisateurs doivent avoir la même quantité de ressources sur le réseau.
• Chaque utilisateur reçoit un débit proportionnel à la quantité de dommages causés aux autres utilisateurs.

Exemple

• Illustration d'un réseau à ressource unique de capacité 30.
• Demande de ressources (A=20, B=20, C=20) qui est une allocation équitable triviale.
• Illustre que l'allocation dans le cas complexe (A=4, B=20, C=20) pourrait être différente.

Équité Max-Min

• Une allocation est équitable si elle satisfait le critère d'allocation max-min.
• Une connexion n'aura pas plus de ressources que sa demande.
• L'excès sera partagé de manière égale.
• Les ressources sont allouées dans l'ordre croissant des demandes croissantes.
• Les sources ayant des demandes insatisfaites reçoivent une allocation égale des ressources.

Exemple Allocation Max-Min Équitable

• Calculer l'allocation max-min équitable de 4 sources (A=2, B=2.6, C=4, D=5) sur une ressource de capacité 10.

Généralisation à un réseau

• Étant donné un réseau de noeuds et d'arcs, chaque arc a une capacité.
• Augmenter les flots de façon égale jusqu'à la saturation d'un lien ou un flot aura toute sa demande.
• Fixer le débit des flots goulots d'étranglement.
• Continuer avec les flots non fixés.

Exemple

• Illustre un réseau avec 3 noeuds et les capacités des liens entre eux (T(AB), T(AC), T(BC)).

Première itération

• Illustration de l'allocation de ressources à tous les flots.
• Les demandes BC sont satisfaites.

Deuxième itération

• Illustration pour l'augmentation du trafic de façon égale.
• Le lien (A, B) est saturé par un flot de 5 quand AB et AC ont chacun 5.

Discussion

• L'équité est intuitivement une bonne idée.
• L'équité protège les flux.
• L'équité crée des firewalls autour des flux volumineux.
• L'équité est un objectif global mais l'ordonnancement est local.

Exigence 3 : Bornes de performance

• Une façon d'obtenir un niveau de service désiré.
• Les performances peuvent être déterminées de façon déterministe ou statistique.
• Les paramètres de performance sont la bande passante, le délai et la gigue.

Exigence 4 : Facilité du contrôle d'admission

• Le contrôle d'admission est nécessaire pour fournir la QoS.
• Une ressource surchargée ne peut pas garantir la performance.
• Le choix de la discipline d'ordonnancement affecte la complexité de l'algorithme de contrôle d'admission.

Choix fondamentaux

• Nombre de niveaux de priorité.
• Oisiveté (avec/sans).
• Degré d'agrégation.
• Ordre de service dans le même niveau.

Choix 1 : Priorité

• Un paquet est servi à partir d'un niveau de priorité seulement s'il n'existe aucun paquet dans les niveaux supérieurs
• Le niveau supérieur aura le plus faible délai.
• Surveiller la famine!
• Association des niveaux de priorité aux classes de délai.
• Facile à implémenter.

Choix 2 : Sans oisiveté vs. avec oisiveté

• Un ordonnanceur non oisif est libre uniquement quand aucun paquet n'est en attente de service.
• Un ordonnanceur oisif peut être libre même s'il y a des paquets en attente.
• À première vue, un ordonnanceur oisif ne semble pas logique.
• Pourquoi laisser la ligne libre, perdant des ressources alors qu'on peut en profiter?

Choix 3 : Degré d'agrégation

• Plus d'agrégation, meilleure qualité de service mais moins d'états et moins cher.
• Moins d'agrégation, plus d'individualisation mais un traitement par flot.
• Agrégation à une classe : les membres d'une classe ont le même niveau de performance.
• Pas de protection au sein d'une même classe.

Choix 4 : Service dans un niveau de priorité

• Dans l'ordre d'arrivée (FIFO) ou selon un ordre tag.
• Besoin de trier la file d'attente, ce qui peut être coûteux.
• Ne permette pas aux paquets de haut priorités de passer en tête de la file.
• Ce n'est pas max-min équitable.
• Avec un choix approprié, on peut imposer des bornes de délai et assurer la protection.

Weighted Round Robin (WRR)

• Servir un paquet de chaque file non vide à tour de rôle.
• Non équitable si les paquets ont des longueurs ou des poids différents.
• Si les poids sont différents mais les longueurs de paquets sont les mêmes, servir plus d'un paquet par visite après normalisation.

Problèmes avec Weighted Round Robin

• Si la source ne peut pas prédire la taille moyenne des paquets, WRR ne peut pas allouer les ressources équitablement.
• Avec des paquets de tailles variables et poids différents, il faut connaître la taille moyenne des paquets à l'avance.
• WFQ =équitable seulement sur une échelle de temps supérieure à du cycle.

Ordonnancement des connexions BE

• L'équité est la principale exigence.
• Réalisable par un Generalized processor sharing (GPS).
• Ordonnanceur théorique.
• Visiter chaque file non vide de façon cyclique (round robin).
• Servir une quantité infinitésimale de bits de chaque file non vide.
• GPS = max-min équitable.
• Si N connexions, chaque connexion 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 connexions.

Weighted Fair Queuing (WFQ)

• WFQ émule GPS (rappel : GPS est la discipline la plus équitable).
• Gère mieux les tailles et poids différents.
• Calcule le temps virtuel de fin de service d'un paquet avec GPS.
• Servir les paquets dans l'ordre de leurs temps virtuels de fin de service.
• On appelle le temps virtuel de fin de service un numéro de fin.

WFQ: Calcul du numéro de fin

• On suppose que dans chaque cycle, le serveur sert un bit de chaque connexion active.
• Calcul du numéro de fin selon la formule donnée.
• Servir les paquets par ordre croissant de leur numéro de fin.

WFQ: Calcul du nombre de cycles

• Le nombre de cycles est le nombre de cycles de service complets à un instant donné.
• Si le serveur n'a pas encore servi toutes les connexions dans un cycle, le nombre de cycles devra être re-défini selon une variable réelle qui croît.

WFQ : Ajouter les poids des connexions

• L'ordonnanceur GPS sert chaque connexion proportionnellement à son poids.
• Somme des poids des connexions actives à l'instant t.
• Calcul du numéro de fin en considérant les poids des connexions.

Exemple WFQ

• Exemple avec 3 connexions (A, B, C) de poids identiques. Un taux de service de 1 unité/seconde.
• Paquets de tailles différentes arrivent à certaines connexions, nécessitant le calcul des numéros de fin.

Solution : numéros de fin

• Simulation GPS.
• Calcul des numéros de fin pour les différents paquets.

Solution : ordonnanceur WFQ

• Calcul des numéros de fin pour chaque paquet.
• Ordonnancement en utilisant les numéros de fin croissantes, et en respectant l'activation du serveur.
• Le système devient inactif à un certain instant.

Solution : ordonnanceur WF2Q

• Le service est servi en utilisant un ordre de priorité croissant des niveaux de fin.

Ordonnancement des connexions GS

• Pour les connexions BE, l'objectif est l'équité.
• Pour les connexions service garanti :
  • Quelle garantie de performance est réalisable?
  • Combien c'est facile de réaliser le contrôle d'admission?
• On va étudier quelques mécanismes qui fournissent des garanties de performance.

WFQ

• WFQ peut aussi fournir des garanties de performance.
• Borne de débit, rapport des poids * capacité du lien.
• Borne de délai, avec une estimation de la transmission et du contrôle par un seau à jetons.

Théorème de Parekh-Gallager

• Considère une connexion contrôlée par un seau à jetons.
• Décrit le débit alloué à une connexion par l'ordonnanceur, considérant le maximum des paquets transmis par chaque ordonnanceur.

Signification

• 1 représente le GPS (taille de paquet infinitésimale).
• La taille maximale de paquet sur le réseau est bornée par Pmax et le délai est borné par (1).
• La connexion traverse une série d'ordonnanceurs et se comporte comme si elle est servie par un seul ordonnanceur d'un débit g(i).
• Si elle envoie un burst o(i), elle aura un délai o(i)/g(i).
• 2 et 3 représentent la correction GPS à WFQ, modélisant la situation quand le paquet arrive après son instant de service sous GPS.

Exemple

• Cas d'une connexion contrôlée par un seau à jetons avec une capacité et un nombre de sauts donnés.
• Calcul d'une valeur de g pour garantir un retard end-to-end de 100 ms avec un retard de propagation spécifique.

Ce quiz aborde le concept d'allocation max-min équitable, en se concentrant sur les étapes cruciales et les critères utilisés pour la distribution des ressources. Il comprend des questions sur l'ordonnancement et les réseaux, ce qui en fait un exercice essentiel pour comprendre l'allocation efficace. Testez vos connaissances et améliorez votre compréhension de ces concepts clés!