Zusammenfassung

  • Gewöhnliches Paket-Round-Robin verteilt Sendemöglichkeiten, nicht übertragene Bytes. Beim DRR von Shreedhar und Varghese erhält jede Warteschlange ein Quantum, bezahlt daraus vollständige Pakete und nimmt ein nicht verbrauchtes Defizitguthaben in die nächste Runde mit, solange sie belegt bleibt.
  • Der Mechanismus zielt auf begrenzte Abweichung bei langfristiger Durchsatzfairness und geringen Aufwand pro Paket. Fair sind die konfigurierten Schlangen und Gewichte; Basis-DRR garantiert keine Paketlatenz und übernimmt weder Klassifikation, Shaping, AQM, Überlastregelung noch Ende-zu-Ende-QoS.

Ein vollkommen gerechter Zeiger kann unfair abrechnen

Die Symmetrie von Round Robin ist überzeugend: Der Zeiger besucht jede aktive Warteschlange einmal und kehrt erst danach zurück. Bei gleich großen Arbeitseinheiten wäre damit auch die Ressource gleich verteilt. IP-Pakete sind aber unterschiedlich lang. Wer jeder Schlange genau ein Paket erlaubt, kann ihre Paketzahl ausgleichen und zugleich ihre Byteanteile dauerhaft auseinanderlaufen lassen.

Auf einem Link ist nicht der Besuch des Zeigers knapp, sondern die Zeit, in der Bits übertragen werden. Ein 1.500-Byte-Paket bindet bei gleicher Leitungsrate ungefähr dreimal so viel davon wie ein 500-Byte-Paket. Eine Betriebsansicht, die nur gesendete Pakete zählt, kann deshalb perfekte Gleichheit anzeigen, während eine Klasse den dreifachen Durchsatz erhält. Der Fehler steckt nicht in der Ausführung, sondern in der Maßeinheit.

Eine sehr genaue Fair-Queuing-Annäherung kann einen idealisierten flüssigen Server modellieren und für jedes unteilbare Paket eine virtuelle Fertigstellungszeit berechnen. Dafür sind Sortierung und weitere Arbeit im schnellen Pfad nötig. Shreedhar und Varghese suchten eine andere Balance: Die Abweichung von der idealen Byteverteilung sollte begrenzt bleiben, ohne bei jedem Paket eine teure globale Rangfolge zu pflegen.

Das Guthaben überlebt den Besuch

DRR hält für jede aktive Warteschlange einen deficit counter. Wenn sie besucht wird, addiert der Scheduler ihr konfiguriertes Quantum. Passt das Paket am Kopf vollständig in den Saldo, wird es gesendet und seine Länge abgezogen. Passt auch das nächste, folgt es im selben Besuch. Reicht der Saldo nicht, wird das Paket nicht geteilt; der Zeiger geht weiter.

Bleibt die Warteschlange belegt, wird der Rest nicht verworfen. Beim nächsten Besuch kommt ein weiteres Quantum hinzu. Daher kann auch ein Paket, das größer als ein einzelnes Quantum ist, nach mehreren Runden genügend Guthaben erhalten. Leert sich die Schlange, wird der Zähler zurückgesetzt. Neu eintreffender Verkehr soll keinen Anspruch erben, der während einer früheren, inzwischen abgeschlossenen Belegung entstanden ist.

„Defizit“ ist dabei keine Schuld des Kunden. Der Wert ist weder Überlastpreis noch Vertragsstrafe, weder Kreditwürdigkeit noch Entschädigung. Er ist lokaler Buchungszustand für Dienst, der zugeteilt, wegen der Unteilbarkeit des Kopf-Pakets aber noch nicht genutzt wurde. Erst zusammen mit Quantum, Paketlänge und Backlog bekommt die Zahl eine Bedeutung.

Bei zwei dauerhaft belegten Schlangen mit gleichem Quantum kann die Kleinstpaket-Schlange während eines Besuchs mehrere Pakete senden. Die Großpaket-Schlange setzt vielleicht einmal aus, sammelt aber den Rest. Einzelne Runden wirken ungleich; über viele Runden nähert sich der Byte-Dienst dem Zielanteil, und der verbleibende Fehler hängt von der maximalen Paketgröße ab. DRR verspricht also keine identischen Momentaufnahmen, sondern eine begrenzte Differenz über die Dienstgeschichte.

Im Quantum steckt das Gewicht

Gleiche Quanten formulieren das Ziel gleicher Byteanteile. Sind sie im Verhältnis zwei zu eins gesetzt und bleiben beide Schlangen belegt, strebt auch der langfristige Dienst ungefähr dieses Verhältnis an. Das Quantum ist deshalb kein neutraler Performance-Regler. Es übersetzt eine Entscheidung über knappe Kapazität in die Arithmetik des Schedulers.

Seine Größe beeinflusst zugleich die Körnung. Ist ein Quantum klein gegenüber dem erwarteten Maximalpaket, muss Guthaben womöglich mehrere Runden anwachsen, und der Scheduler besucht die aktive Liste häufiger. Ein großes Quantum kann in einem Besuch mehr Bytes freigeben und sichtbarere Dienst-Bursts erzeugen. Eine Auditakte mit dem Eintrag „DRR aktiviert“ ist unvollständig; nötig sind mindestens Quanten je Schlange, Paketgrößenannahmen, Reset-Regel und Version der aktiven Konfiguration.

Der technische Bericht von 1994 und die spätere SIGCOMM-Veröffentlichung von Shreedhar und Varghese beschreiben das Ziel als nahezu perfekte Durchsatzfairness, O(1)-Komplexität und einfache Hardwareumsetzung. O(1) bezieht sich auf die Scheduler-Operationen. Es bedeutet nicht, dass Klassifikation, Speicher für beliebig viele Warteschlangen oder die Beobachtung des Gesamtsystems kostenlos wären. Der Gewinn liegt darin, für die Auswahl nicht fortwährend eine globale Prioritätsordnung nachzuführen.

Der Klassifikator bestimmt, wer überhaupt verglichen wird

DRR sieht fertige Warteschlangen. Es weiß nicht, ob eine davon einen Kunden, einen Flow, einen Tunnel, eine Anwendung oder ein großes Aggregat repräsentiert. Teilen sich zehn Mandanten eine Schlange und besitzt ein elfter eine eigene, dann teilen gleiche Quanten die Kapazität zwischen zwei Schlangen — nicht unter elf Mandanten. Die Rechnung kann exakt sein, obwohl die gewählte Bevölkerung fragwürdig ist.

Auch innerhalb einer FIFO-Schlange löst der Defizitzähler keine Trennung. Ein massiver Transfer kann dort interaktive Pakete warten lassen. Eine falsche Markierung kann Verkehr in eine günstigere Klasse versetzen. Nicht zugeordnete Pakete können in einem großzügig gewichteten Default landen. Keinen dieser Sachverhalte erkennt der Scheduler; er vollzieht die Grenzen, die Klassifikation und Konfiguration ihm übergeben.

Die Aussage „Wir verwenden DRR“ benötigt daher Ergänzungen: Welche Felder wählen die Schlange? Was bedeutet ihre Identität? Wie werden unbekannte Pakete behandelt? Wer bestimmt Quanten? Wann tritt eine Schlange in die aktive Liste ein und wieder aus? Was geschieht mit dem Zustand bei Failover oder Rekonfiguration? Erst diese Antworten definieren, für wen die mathematische Fairness gilt.

Entsprechend muss Evidenz beide Seiten verbinden. Port-Gesamtdurchsatz verbirgt interne Anteile, reine Paketzählung wiederholt den Ausgangsfehler. Prüffähig wird der Dienst, wenn Version des Klassifikators, Schlangenmitgliedschaft, Quanten, Aktivitätsintervalle, Paketgrößen, ausgereihte Bytes und übertragene Defizite gemeinsam erhalten bleiben.

Fairer Durchsatz ist keine Uhr für jedes Paket

Basis-DRR begrenzt die langfristige Dienstdifferenz relativ zu den Gewichten, setzt aber nicht automatisch eine harte Wartezeit für ein einzelnes Paket. Eine Schlange wartet auf andere aktive Schlangen; ein Paket wartet zusätzlich hinter Paketen derselben FIFO. Zahl der Konkurrenten, Quantum, maximale Länge und Ankunftsmuster verändern die Verzögerung. Die ursprüngliche Arbeit unterscheidet Durchsatzfairness ausdrücklich von Latenzgrenzen und diskutiert Erweiterungen für Verzögerungsanforderungen. Deren Eigenschaften dürfen nicht rückwirkend dem Basisschema zugeschrieben werden.

DRR formt auch nicht die Ankunftsrate, wählt nicht von sich aus Drops oder ECN-Markierungen und regelt kein Senderfenster. Shaper steuern den Zufluss, AQM steuert Warteschlangensignale, Überlastkontrolle verändert Endsystemverhalten, Routing wählt den Pfad. RFC 7567 behandelt Scheduling im Kontext von Queue Management als verwandte, aber getrennte Funktion. Gemeinsame Konfiguration an einem Interface hebt die Trennung nicht auf.

Das ist für Störungsanalysen entscheidend. Stimmen die Byteanteile, während die Tail-Latenz steigt, kann DRR seine Aufgabe korrekt erfüllen und das Problem dennoch real sein. Dann sind Backlog, gemeinsame FIFO-Nutzung, AQM und andere Pfadabschnitte zu untersuchen. Übersteigt die Gesamtlast dauerhaft die Linkkapazität, kann DRR Knappheit gemäß Gewichten verteilen, aber weder neue Kapazität erzeugen noch Überlastung beseitigen.

George Varghese und die Disziplin des schnellen Pfads

Die offizielle UCLA-Seite führt George Varghese als Distinguished Professor of Computer Science und Jonathan B. Postel Chair. Seine Forschungsfelder umfassen network algorithmics, Verifikation, Cybersicherheit und das künftige Internet. Nach seiner Promotion am MIT lehrte er an der Washington University in St. Louis und der UC San Diego, arbeitete bei Microsoft Research und wechselte 2016 an die UCLA.

Eine Biografie beweist keine Fehlergrenze. Sie macht aber eine wiederkehrende Arbeitsweise sichtbar: eine kostspielige Operation im Datenpfad bestimmen, den Zustand anders darstellen und dadurch ein theoretisches Ziel bei Leitungsgeschwindigkeit ausführbar machen. ACM SIGCOMM verlieh Varghese 2014 den SIGCOMM Award. Der Internet Hall of Fame hob bei seiner Aufnahme 2021 die Erfindung von DRR mit M. Shreedhar und die historische Nutzung unter anderem in Cisco-GSR-Systemen hervor.

Auszeichnungen und Produkteinsatz belegen Wirkung; für die technischen Aussagen bleiben Modell und Annahmen der Originalarbeit maßgeblich. Diese Trennung verhindert zwei Verkürzungen: Ein Preis ist kein Beweis, und ein Algorithmus mit sauberer Theorie ist nicht automatisch nur Theorie. Der Defizitzähler war klein genug für die Implementierung und präzise genug für eine begrenzte Aussage über Fairness.

Eine Zahl ohne Herkunft erzählt nicht ihre Ursache

Ein veränderter Zählerstand kann auf neue Quanten, andere Paketgrößen, zusätzliche aktive Schlangen, Reklassifikation oder das zwischenzeitliche Leeren einer Schlange zurückgehen. Ein einzelner Snapshot trennt diese Fälle nicht. Die Beobachtung muss mehrere Runden abdecken und mit Zeitpunkten der Konfigurationsereignisse verbunden werden.

Ebenso beweist ein passender Byteanteil keine gleiche Nutzererfahrung. Verzögerung kann sich innerhalb eines Aggregats konzentrieren, ein separates AQM kann Klassen unterschiedlich treffen, und der übrige Pfad kann dominieren. Die Evidenz von DRR ist stark, weil sie lokal und klar begrenzt ist. Wer ihre Grenze wahrt, schützt den Mechanismus vor Versprechen, die sein eigener Zustand nie tragen konnte.

Quellen