Zusammenfassung

  • In Keshavs Modell zog der langsamste ratenzuteilende Server zwei unmittelbar gesendete Pakete am stärksten auseinander. Der ACK-Abstand ergab eine verrauschte Schätzung der dieser Verbindung zugeteilten Bedienrate.
  • Die Schätzung floss in ein System mit Warteschlangen-Sollwert, unscharf angepasster exponentieller Mittelung, bedingtem Stabilitätsbeweis und einer bewussten Sendepause zur Neukalibrierung.
  • Das Paketpaar belegte keine allgemeine Internetkapazität. Es setzte eine Fair-Queueing-ähnliche Disziplin voraus, galt nicht für gewöhnliches FCFS und garantierte weder Verlustfreiheit noch Anwendungszustellung oder Dienstgüte.

Eine minimale Warteschlange als Messinstrument

Liegen bereits mehrere Pakete eines Flusses an, kann der Takt ihrer Bestätigungen den Bedientakt widerspiegeln. Bei leerer Warteschlange fehlt der Vergleich. Keshavs Problem bestand deshalb darin, gerade genug Zustand zu erzeugen, damit der Router ihn verändern musste.

In seiner Rückschau von 2019 verortet er den Einfall im Dezember 1989 in einem Café in Berkeley. Zwei Pakete sollten direkt nacheinander starten. Das erste beanspruchte einen Bedienzug, das zweite wartete dahinter. Unter mehreren Knoten würde die langsamste Bedienung dieses Flusses den größten Abstand prägen. Die Bestätigungen könnten ihn zurücktragen, ohne dass Router eine explizite Rate meldeten.

Die Quelle begrenzt diese Geschichte selbst. Sie ist eine ausdrücklich nicht begutachtete redaktionelle Notiz: Beleg für Keshavs Erinnerung, nicht für unabhängige Leistungsmessung. Zudem berichtet er, dass Samar Singh und Ashok Agrawala etwa gleichzeitig und unabhängig auf eine ähnliche Idee kamen und die Arbeiten später verbunden wurden. Der SIGCOMM-Regelungsaufsatz stammt von Keshav; das Paketpaar darf dennoch nicht zur Alleinerfinder-Erzählung werden.

Beobachtbarkeit war eine Eigenschaft des Schedulers

Der Aufsatz nahm Rate Allocating Servers an, verwandt mit Fair Queueing und Virtual Clock. Jede aktive Verbindung erhielt hinreichend regelmäßige Züge, sodass der Abstand zwischen zwei eigenen Bedienungen eine Bedeutung hatte. Er umfasste auch die Züge der anderen aktiven Verbindungen; der größte Abstand auf dem Pfad war die Engpass-Bedienzeit.

Das Paketpaar entfernte den vom Sender gewählten Abstand. Nun schrieb das Netz seinen eigenen hinein. Schnellere Server hinter dem Engpass schlossen ihn im Modell nicht wieder. Entscheidend war nicht die Zahl zwei, sondern die Semantik der Warteschlange.

Darum schloss Keshav gewöhnliche First-Come-First-Served-Netze aus. Ein fremder Burst kann dort die scheinbare Bedienung abrupt verändern. Ohne Zuteilung pro Verbindung trägt derselbe Abstand eine andere Aussage. Eine Sonde kann keine Struktur auslesen, die das System nicht anbietet.

Der Rückweg veränderte den Beleg

Der Sender sah nie die Warteschlange selbst. Die beiden ACKs konnten auf dem Rückweg unterschiedlich warten und ihren Abstand vergrößern oder verkleinern. Auch ein Knoten hinter dem Engpass auf dem Hinweg konnte die Pakete verschieden verzögern. Eine Messung beim Empfänger verringerte einen Teil des Rückwegrauschens, beseitigte aber nicht jede nachgelagerte Veränderung.

Die Bedienrate war deshalb eine verrauschte Beobachtung. Auch die tatsächlich zugeteilte Rate änderte sich, wenn Verbindungen aktiv oder inaktiv wurden. Der zuletzt gemessene Wert war schon vergangen, wenn er die nächste Entscheidung beeinflusste.

Ein Kalman-Filter war formal naheliegend, verlangte jedoch Varianzen für System- und Beobachtungsrauschen, die erst gemessen oder simuliert werden mussten. Praktischer erschien eine exponentielle Mittelung mit Fuzzy-Regeln: mehr Gewicht für die Vergangenheit in ruhigen Phasen, mehr Gewicht für die jüngste Beobachtung bei Wandel. „Fuzzy“ ersetzte keine Evidenz; es legte offen, wie schnell alte Evidenz verfiel.

Der Stabilitätsbeweis gehörte seinem Modell

Der Regler kopierte nicht einfach die letzte geschätzte Rate. Er verband sie mit RTT, ausstehenden Paketen und einer geschätzten Engpassbelegung und wählte einen Arbeitspunkt.

B/2 war ein Analysebeispiel. Nahe null drohte ein Bedienzug ungenutzt zu bleiben; nahe voll stiegen Verzögerung und Verlustrisiko. Unter symmetrischem Rauschen lag die Hälfte dazwischen. Der Aufsatz erlaubte andere Sollwerte. Eine heutige Universalempfehlung war das nicht.

Ein erster Entwurf hatte Pole auf dem Einheitskreis und war nicht asymptotisch stabil. Ein Platzierungsparameter verschob sie im linearen Modell nach innen. Eine kontinuierliche Variante konnte mit jeder zurückkehrenden Sonde handeln statt nur einmal pro RTT. Der Beweis war substanziell, aber nicht grenzenlos: Fluidnäherung, beobachtbarer RAS-Dienst, Linearität und Rauschannahmen gehörten zu seinem Gegenstand.

Durch Stillstand wieder einen überprüfbaren Nullpunkt schaffen

Eine aus früheren Schätzungen fortgeschriebene Belegung kann driften. Interne Konsistenz verrät nicht, dass sich die Zahl von der realen Warteschlange gelöst hat.

Die vorgeschlagene Korrektur kostete sichtbar Leistung. Die Quelle sandte ein besonderes Paar und danach nichts, bis dessen Bestätigungen eintrafen. Ohne Nachfolger konnte die Warteschlange dieser Verbindung leerlaufen. Die geschätzte Belegung wurde auf null gesetzt. Der Preis betrug ungefähr eine RTT ungenutzter Bandbreite.

Die Pause war keine Ratlosigkeit, sondern Kalibrierung. Sie erzeugte eine Bedingung, in der sich Behauptung und Zustand wieder treffen konnten.

Auch Ratenregelung allein versprach keine Verlustfreiheit. Der Aufsatz ergänzte ein Fenster als konservative Obergrenze für ausstehende Pakete und nahm Puffer pro Verbindung an. Die Rate wählte den Arbeitspunkt, das Fenster begrenzte den Rand. Die Zusage des einen Mechanismus gehörte nicht dem anderen.

Was zwei Pakete nicht belegen konnten

Der Aufsatz von 1991 fasste Simulationen qualitativ zusammen, verwies Details auf andere Arbeiten und nannte Messungen in realen Netzen als Zukunftsarbeit. Er benannte Grenzen des linearen Modells, der gaußschen weißen Rauschannahmen, der Fensterinteraktion und der Betrachtung einer einzelnen Verbindung, während andere als Rauschen erschienen.

Spätere Paketdispersionsverfahren dienten häufig der Kapazitäts- oder Available-Bandwidth-Schätzung. Diese Bedeutung darf nicht rückwirkend eingesetzt werden. Keshavs Paar schätzte eine zugeteilte Bedienrate unter RAS-Bedingungen. Es bewies weder physische Leitungsrate noch freie Kapazität, Ende-zu-Ende-Durchsatz, Verlustschutz oder Anwendungserfolg.

Cambridge dokumentiert heute Keshavs Weg über Berkeley, Bell Labs, Cornell, Waterloo und Cambridge; seine eigene Seite erklärt, dass Keshav sein Vorname ist, obwohl er syntaktisch zuletzt steht. Der bleibende Wert der Arbeit liegt in der Beweiskette: Abstand, Verbindung, Scheduler, Richtung, Zeitpunkt und Unsicherheit müssen zusammenbleiben, bevor eine Zahl steuern darf.

Quellen