Partage généralisé du processeur

Dans un réseau comme l'internet, des applications de types différents ont besoin de différents niveaux de performance. Par exemple, une application de courrier électronique se contente en définitive de stocker et de transférer des données : ce n'est pas aussi simple pour une application de vidéoconférence, puisque celle-ci a en outre besoin d'avoir une faible latence.

Lorsque les paquets sont mis en file d'attente à une extrémité d'une chaîne de traitement congestionnée, le point nodal recevant l'information (en anglais, node) dispose généralement d'une certaine marge de manœuvre pour décider de l'ordre dans lequel il doit envoyer les paquets ordonnancés. Un exemple d'ordre de renvoi est simplement le principe du "premier arrivé, premier servi". Celui-ci fonctionne très bien pour de petites files d'attente, mais peut entraîner des problèmes si des paquets sensibles aux temps de latence sont obstrués par des paquets d'applications plus vivaces, c'est-à-dire disposant d'une plus grande largeur de bande.

Dans le PGP, un ordonnanceur gérant N flux (flow en anglais, aussi appelé "classes" ou "sessions") se détermine en définissant un coefficient de pondération ${\displaystyle w_{i}}$ pour chaque flux. Considérons un flux ${\displaystyle i}$, et un certain intervalle de temps ${\displaystyle (s,t]}$, de telle sorte que, au cours de cet intervalle, les instructions s'accumulent en permanence dans le flux ${\displaystyle i}$ (c'est-à-dire que sa file d'attente ne soit jamais vide). Alors, le PGP s'assure que pour tout autre flux ${\displaystyle j}$, on ait la relation suivante :

${\displaystyle w_{j}O_{i}(s,t)\geq w_{i}O_{j}(s,t)}$

où ${\displaystyle O_{k}(s,t)}$ est la quantité de bits du flux ${\displaystyle k}$ traités au cours de l'intervalle ${\displaystyle (s,t]}$.

Il peut alors être déterminé que chaque flux ${\displaystyle i}$ recevra au moins un taux de calcul (en anglais, rate) ${\displaystyle R_{i}}$ de

${\displaystyle R_{i}={\frac {w_{i}}{\sum _{j=1}^{N}w_{j}}}R}$

où ${\displaystyle R}$ est le taux de calcul du serveur.

Il s'agit d'un taux minimal. Si un certain flux n'utilise pas sa bande passante au cours d'une période, cette capacité disponible est distribuée au reste des flux conformément à leur pondération respective. Par exemple, considérons un serveur avec un PGP de type ${\displaystyle w_{1}=2,w_{2}=w_{3}=1}$. Le premier flux recevra au moins la moitié de la capacité du processeur, là où les deux autres n'en recevront que le quart. Néanmoins, si sur un certain intervalle de temps ${\displaystyle (s,t]}$ il n'y a que les deux derniers flux qui sont actifs, alors ils recevront chacun la moitié de la capacité de calcul du processeur.

Dans le PGP, et tous les protocoles dérivés du PGP, le choix des coefficients de pondération est laissé à l'administrateur du réseau.

Le partage généralisé du processeur suppose que le trafic est fluide, c'est-à-dire divisible à l'infini, de sorte que lorsqu'un certain type d'application a des paquets dans la file d'attente, le serveur consacrera exactement la proportion adéquate (donné par la formule de la partie ci-dessus) de ses capacités à son exécution.

Cependant, le trafic n'est en réalité pas fluide et se compose de paquets aux tailles potentiellement variables. Par conséquent, le PGP est avant tout un principe théorique. Plusieurs algorithmes d'ordonnancement ont été développés afin d'approcher du PGP idéal. L'implémentation la plus connue est PPGP (en anglais PGPS), ou ordonnancement pondéré équitable, bien qu'elle ne soit pas parfaite. D'autres implémentations ont été proposées, comme le déficit accumulé au tour par tour (Deficit round robin) ou WF2Q[4].

Le PGP est considéré comme un idéal d'équité, et toutes ses approximations pratiques "l'utilisent comme une référence pour mesurer l'équité."[2] Néanmoins, d'autres mesures de l'équité existent aussi.

Le PGP ne dépend pas de la taille des paquets, puisqu'il suppose un trafic fluide.