Résumé

  • Le round robin classique égalise les occasions d’émettre, pas les octets transmis. DRR attribue un quantum à chaque file, débite la taille des paquets entiers et conserve le solde lorsqu’une file toujours active ne peut pas servir le paquet suivant.
  • L’équité obtenue concerne le débit à long terme entre les files et poids configurés. DRR de base ne borne pas la latence d’un paquet, ne classe pas les usagers, ne régule pas les arrivées et ne constitue ni AQM ni contrôle de congestion.

Deux tours égaux, deux services inégaux

Le round robin rassure parce que sa procédure est visible. Une liste de files actives, un pointeur qui avance, un paquet servi à chaque étape : aucune file ne semble pouvoir monopoliser l’ordonnanceur. La structure est également séduisante pour le chemin rapide, car elle évite de rechercher sans cesse le prochain paquet dans un ordre global complexe.

La symétrie casse dès que les paquets n’ont pas la même taille. Si la file A présente toujours 1 500 octets et la file B 500, l’alternance A-B distribue bien un paquet à chacune, mais trois octets à A pour un à B. Le dispositif compte des enveloppes tandis que le lien dépense des bits.

C’est ce décalage que M. Shreedhar et George Varghese ont isolé dans leur rapport de 1994 puis dans l’article publié après SIGCOMM. Les variantes proches du fair queuing idéal offraient une bonne précision au prix d’un traitement plus coûteux ; les solutions cycliques simples restaient rapides mais pouvaient devenir injustes face aux tailles variables. Leur question n’était pas de supprimer le cycle, mais de lui donner une mémoire exprimée dans la bonne unité.

Le solde qui refuse de disparaître

Chaque file DRR reçoit un quantum Q_i et possède un compteur de déficit DC_i. Lorsqu’une file active est visitée, son quantum s’ajoute au compteur. Le paquet en tête peut partir si sa taille tient dans le crédit disponible ; sa longueur est alors soustraite, et l’opération continue tant qu’un nouveau paquet tient encore.

Si le paquet suivant est trop grand, il n’est ni découpé ni envoyé à découvert. Lorsque la file demeure chargée, le solde reste attaché à celle-ci. Au tour suivant, un nouveau quantum vient s’y ajouter. Ainsi, avec un quantum de 1 000 octets, un paquet de 1 500 peut attendre un tour, accumuler 2 000, partir entier et laisser 500 unités disponibles.

Le mot « déficit » prête parfois à une lecture morale. Le compteur n’enregistre pourtant ni dommage subi par un client ni dette contractuelle du réseau. C’est un état comptable interne : le service que cette file n’a pas pu consommer dans le cadre de la discipline. Si la file se vide, le compteur revient à zéro. Une source restée inactive ne peut donc pas thésauriser indéfiniment du crédit puis réclamer une rafale future.

Le quantum est une décision de poids

Avec des quanta égaux, des files continuellement chargées visent des parts égales à long terme. Des quanta différents expriment des poids : le rapport entre eux organise les parts relatives, sous réserve de la granularité des paquets et de la population active.

L’analyse de Shreedhar et Varghese borne le service autour du nombre d’occasions multiplié par le quantum, avec une erreur liée à la taille maximale d’un paquet. Cette formulation compte davantage qu’une promesse vague de perfection. Sur un intervalle court, l’indivisibilité d’un paquet peut placer une file en avance. Le compteur conservé permet ensuite de compenser sans effacer l’histoire à chaque passage.

L’économie de calcul vient de cette simplicité : une liste active, un déplacement cyclique, une addition, une comparaison et une soustraction. L’algorithme n’a pas besoin d’ordonner toutes les files selon un horodatage virtuel. Le papier revendique une équité de débit presque parfaite avec un travail O(1) par paquet et une structure adaptée au matériel, dans le cadre de ses hypothèses sur quantum et taille maximale.

O(1) ne signifie pas que chaque ASIC, hiérarchie de files ou fonction de classification consomme exactement le même nombre de cycles. Il décrit la façon dont le coût de l’opération d’ordonnancement évolue. De même, la borne d’équité ne transforme pas des paquets entiers en fluide divisible.

L’équité commence au classificateur

DRR distribue du service entre les files qu’on lui présente. Une file peut représenter un flux, un ensemble de flux hachés, un abonné, une classe de trafic ou un ordonnanceur enfant. Si dix applications partagent une file et qu’une onzième dispose d’une file propre, DRR arbitre entre deux files ; il ne voit pas les dix identités cachées.

Dire « équitable entre les flux » suppose donc une décision préalable : quelles clés définissent un flux, combien de files existent, où vont les collisions et quel quantum reçoit chaque classe. Un classificateur déficient peut rendre socialement absurde une discipline mathématiquement correcte. L’arithmétique sait respecter un poids ; elle ne sait pas déterminer qui mérite ce poids.

La distribution des tailles fait aussi partie du reçu. L’exemple 1 500/500 démontre un mécanisme, pas une mesure prise sur un routeur Cisco ou un cœur Internet. Les paquets réels varient. Pour interpréter un compteur, il faut connaître tailles maximales, mélange observé, durée de charge et composition de la liste active.

Le débit ne donne pas l’heure d’arrivée

L’article original distingue explicitement l’équité de débit de la latence : DRR de base fournit la première sans borne pour la seconde, puis les auteurs examinent une extension. Une file peut recevoir sa part sur une longue période alors qu’un paquet attend le passage de nombreuses autres files actives. Le nombre de files, les quanta, la taille des paquets et la hiérarchie déterminent ce délai.

DRR ne décide pas non plus si le paquet aurait dû entrer. L’admission accepte ou refuse une charge ; le shaping règle un rythme ; l’AQM marque ou supprime avant saturation ; le contrôle de congestion modifie le comportement de l’émetteur. RFC 7567 cite les ordonnanceurs de fair queuing, dont DRR, mais les sépare du rôle de l’AQM.

Ces mécanismes peuvent être combinés. Les confondre détruit la valeur des mesures. Un compteur faible ne prouve pas l’absence de congestion. Un déficit élevé n’est pas une dette envers l’utilisateur. Une bonne part d’octets n’établit pas une faible latence applicative, et un paquet dequeué n’est pas encore livré de bout en bout.

Varghese dans l’histoire du chemin rapide

UCLA Samueli présente George Varghese comme Distinguished Professor of Computer Science et titulaire de la Jonathan B. Postel Chair in Networking. Ses domaines incluent network algorithmics et la vérification de réseaux : trouver un goulot d’étranglement, puis faire dialoguer algorithme, matériel et contrainte d’implémentation. Il a rejoint UCLA en 2016 après Microsoft Research et des postes universitaires à UC San Diego et Washington University in St. Louis.

ACM SIGCOMM l’a récompensé en 2014 pour des contributions durables à network algorithmics, avec un effet profond sur la recherche et l’industrie. L’Internet Hall of Fame, qui l’a admis en 2021, cite DRR et son utilisation historique dans le Cisco Gigabit Switch Router.

Cette reconnaissance n’autorise pas un récit solitaire. Le travail fondateur porte les noms de M. Shreedhar et George Varghese. Le profil de Varghese éclaire une méthode — conserver une structure rapide, identifier l’unité réellement rare, ajouter le minimum d’état pour corriger le biais — sans retirer à Shreedhar sa coautorat.

Lire un compteur sans inventer un contrat

Avec le quantum, les longueurs de paquets et l’historique de dequeue, le compteur explique pourquoi une file a pu émettre ou attendre. Il n’identifie pas un client si le classificateur ne fournit pas ce lien. Il ne voit ni congestion en aval, ni chemin complet, ni résultat applicatif.

Un audit utile conserve la population active, les quanta, l’occupation, le paquet de tête, le déficit reporté et les octets transmis. Les drops, marques ECN, états de shaping et changements de classificateur restent dans leurs propres séries. Si les parts de débit sont conformes mais que la latence de queue augmente, les deux mesures ne se contredisent pas : elles répondent à des questions distinctes.

La leçon historique tient dans l’unité de compte. Un pointeur symétrique ne suffit pas à créer l’équité. Il faut savoir ce que la ressource dépense, quelle histoire l’ordonnanceur conserve et quelles populations sont réunies derrière chaque compteur. DRR a appris au cycle à compter les octets ; il n’a pas décidé à la place de l’opérateur qui se cache dans une file.

Sources