4. Filter- und Auswahlalgorithmen

Ein sehr wichtiger Faktor, der die Genauigkeit und Zuverlässigkeit der Zeitverteilung beeinflusst, ist der Komplex von Algorithmen, die verwendet werden, um die Auswirkungen statistischer Fehler und Falschmesser (falsetickers) aufgrund des Ausfalls verschiedener Subnetzkomponenten, Referenzquellen oder Ausbreitungsmedien zu reduzieren. Die in diesem Abschnitt vorgeschlagenen Algorithmen wurden über mehrere Jahre Betrieb im Internet unter stark variierenden Topologien, Geschwindigkeiten und Verkehrsregimen entwickelt und verfeinert. Während diese Algorithmen als die derzeit besten verfügbaren angesehen werden, sind sie kein integraler Bestandteil der NTP-Spezifikation, da in Zukunft andere Algorithmen mit ähnlicher oder überlegener Leistung entwickelt werden könnten.

Es ist jedoch wichtig zu beachten, dass nicht alle Zeitserver oder Clients in einem NTP-Synchronisationssubnetz diese Algorithmen implementieren müssen. Beispielsweise können einfache Workstations im Interesse der Einfachheit auf einen oder beide verzichten, wenn Genauigkeits- und Zuverlässigkeitsanforderungen dies rechtfertigen. Dennoch würde erwartet, dass ein NTP-Server, der einer beträchtlichen Gemeinschaft wie einem Universitätscampus oder Forschungslabor Synchronisation bereitstellt, diese Algorithmen oder andere mit nachgewiesener äquivalenter Funktionalität implementiert. Eine umfassende Diskussion der Designprinzipien und Leistung wird in [MIL91a] gegeben.

Damit die NTP-Filter- und Auswahlalgorithmen effektiv arbeiten, ist es nützlich, ein Maß für die jüngste Stichprobenvarianz für jeden Peer aufgezeichnet zu haben. Das angenommene Maß basiert auf Differenzen erster Ordnung, die leicht zu berechnen und für die beabsichtigten Zwecke effektiv sind. Es gibt zwei Maße, eines genannt Filterdispersion (filter dispersion) ε_σ und das andere Auswahldispersion (select dispersion) ε_ξ. Beide werden als gewichtete Summe der Uhrenversätze in einer temporären Liste berechnet, die nach Synchronisationsdistanz sortiert ist. Wenn θ_i (0 <= i < n) der Versatz des i-ten Eintrags ist, dann ist die Stichprobendifferenz ε_ij des i-ten Eintrags relativ zum j-ten Eintrag definiert als ε_ij = |θ_i - θ_j|. Die Dispersion relativ zum j-ten Eintrag ist definiert als ε_j und berechnet als gewichtete Summe:

ε_j = Σ(i=0 to n-1) ε_ij w^(i+1)

wobei w ein Gewichtungsfaktor ist, der gewählt wird, um den Einfluss der Synchronisationsdistanz im Dispersionsbudget zu steuern. In den NTP-Algorithmen wird w kleiner als 1/2 gewählt: w = NTP.FILTER für Filterdispersion und w = NTP.SELECT für Auswahldispersion. Die (absolute) Dispersion ε_σ und ε_ξ, wie sie in den NTP-Algorithmen verwendet wird, ist relativ zum 0-ten Eintrag ε_0 definiert.

Es werden zwei Verfahren im Folgenden beschrieben, das Uhrenfilterverfahren (clock-filter procedure), das verwendet wird, um die besten Versatzproben von einer gegebenen Uhr auszuwählen, und das Uhrenauswahlverfahren (clock-selection procedure), das verwendet wird, um die beste Uhr unter einem hierarchischen Satz von Uhren auszuwählen.

4.1. Uhrenfilterverfahren

Das Uhrenfilterverfahren wird beim Eintreffen einer NTP-Nachricht oder eines anderen Ereignisses ausgeführt, das zu neuen Datenproben führt. Es nimmt Argumente der Form (θ, δ, ε), wobei θ eine Stichprobe der Uhrenversatzmessung ist und δ und ε die zugehörige Rundlaufverzögerung und Dispersion sind. Es bestimmt den gefilterten Uhrenversatz (peer.offset), die Rundlaufverzögerung (peer.delay) und die Dispersion (peer.dispersion). Es aktualisiert auch die Dispersion von bereits aufgezeichneten Proben und speichert die aktuelle Zeit (peer.update).

Die Basis des Uhrenfilterverfahrens ist das Filterschieberegister (peer.filter), das aus NTP.SHIFT Stufen besteht, wobei jede Stufe ein 3-Tupel [θ_i, δ_i, ε_i] speichert, mit Indizes, die von links beginnend bei Null nummeriert sind. Der Filter wird durch das Löschverfahren in allen Stufen mit dem Wert [0, 0, NTP.MAXDISPERSE] initialisiert. Neue Datenproben werden am linken Ende in den Filter verschoben, wodurch zuerst NULLs und dann alte Proben am rechten Ende herausfallen. Das Paketverfahren liefert Proben der Form (θ, δ, ε), wenn neue Aktualisierungen eintreffen, während das Übertragungsverfahren Proben der Form [0, 0, NTP.MAXDISPERSE] liefert, wenn zwei Abfrageintervalle ohne neue Aktualisierung vergehen. Während hier die gleichen Symbole (θ, δ, ε) für die Argumente, Uhrenfilterinhalte und Peer-Variablen verwendet werden, wird die Bedeutung aus dem Kontext klar. Der folgende Pseudocode beschreibt dieses Verfahren.

Die Variablen peer.offset und peer.delay repräsentieren den Uhrenversatz und die Rundlaufverzögerung der lokalen Uhr relativ zur Peer-Uhr. Beide sind Präzisionsgrößen und können normalerweise über lange Intervalle gemittelt werden, um Genauigkeit und Stabilität ohne Bias-Akkumulation zu verbessern (siehe Anhang H). Die Variable peer.dispersion repräsentiert den maximalen Fehler aufgrund von Messfehler, Schiefe-Fehlerakkumulation und Stichprobenvarianz. Alle drei Variablen werden in den Uhrenauswahl- und Uhrenkombinationsverfahren verwendet, um die für die Synchronisation verwendete(n) Peer-Uhr(en) auszuwählen und die Genauigkeit und Stabilität der Anzeigen zu maximieren.

4.2. Uhrenauswahlverfahren

Das Uhrenauswahlverfahren verwendet die Peer-Variablen THETA, DELTA, EPSILON und τ und wird aufgerufen, wenn sich diese Variablen ändern oder wenn sich der Erreichbarkeitsstatus ändert. Es besteht aus zwei Algorithmen, dem Schnittalgorithmus (intersection algorithm) und dem Clustering-Algorithmus (clustering algorithm). Der Schnittalgorithmus konstruiert eine Liste von Kandidaten-Peers, die berechtigt sind, die Synchronisationsquelle zu werden, berechnet ein Konfidenzintervall für jeden und verwirft Falschmesser unter Verwendung einer von Marzullo und Owicki [MAR85] adaptierten Technik. Der Clustering-Algorithmus sortiert die Liste der überlebenden Kandidaten in der Reihenfolge von Schicht und Synchronisationsdistanz und verwirft wiederholt Ausreißer auf der Grundlage der Auswahldispersion, bis nur die genauesten, präzisesten und stabilsten Überlebenden übrig bleiben. Für jeden Überlebenden wird ein Bit gesetzt, um das Ergebnis des Auswahlprozesses anzuzeigen. Die Systemvariable sys.peer wird als Zeiger auf den wahrscheinlichsten Überlebenden gesetzt, falls vorhanden, oder auf den NULL-Wert, falls nicht.

4.2.1. Schnittalgorithmus

Der Schnittalgorithmus ist von DTS [DEC89] adaptiert und ist darauf ausgelegt, den größten einzelnen Schnitt zu produzieren, der nur Wahrheitsmesser enthält. Der Algorithmus beginnt mit der Initialisierung eines Werts f und der Zähler i und c auf Null. Dann wird, beginnend vom niedrigsten Endpunkt der sortierten Endpunktliste, für jeden Eintrag [Endpunkt, Typ] der Wert von Typ vom Zähler i subtrahiert, der die Anzahl der Schnitte ist. Wenn Typ Null ist, wird der Wert von c erhöht, der die Anzahl der Falschmesser ist (siehe Anhang H). Wenn i >= m - f für einen Eintrag gilt, wird der Endpunkt dieses Eintrags zum unteren Endpunkt des Schnitts; andernfalls wird f um eins erhöht und das obige Verfahren wiederholt. Ohne f oder c zurückzusetzen, wird ein ähnliches Verfahren verwendet, um den oberen Endpunkt zu finden, außer dass der Wert von Typ zum Zähler addiert wird. Wenn nach der Bestimmung beider Endpunkte c <= f gilt, fährt das Verfahren fort, nachdem m - f Wahrheitsmesser gefunden wurden; andernfalls wird f um eins erhöht und das gesamte Verfahren wiederholt.

4.2.2. Clustering-Algorithmus

Im ursprünglichen DTS-Algorithmus endet das Uhrenauswahlverfahren an diesem Punkt mit der vermuteten korrekten Zeit, die in der Mitte des berechneten Schnitts [low, high] gesetzt wird. Dies kann jedoch zu einem erheblichen Verlust an Genauigkeit und Stabilität führen, da die einzelnen Peer-Statistiken verloren gehen. Daher werden in NTP die Kandidaten, die die vorhergehenden Schritte überlebt haben, weiter verarbeitet. Die Kandidatenliste wird mit Einträgen der Form [Distanz, Index] rekonstruiert, wobei die Distanz aus der (skalierten) Peer-Schicht und der Synchronisationsdistanz LAMBDA berechnet wird. Der Skalierungsfaktor bietet einen Mechanismus zum Gewichten der Kombination von Schicht und Distanz. Normalerweise wird die Schicht dominieren, es sei denn, einer oder mehrere der Überlebenden haben eine außergewöhnlich hohe Distanz. Die Liste wird dann nach steigender Distanz sortiert.

Der Algorithmus ist so konzipiert, dass er die Peers nahe dem Kopf der Kandidatenliste bevorzugt, die sich auf der niedrigsten Schicht und Distanz befinden und vermutlich die genaueste und stabilste Zeit liefern können. Mit geeigneter Auswahl des Gewichtsfaktors v (auch NTP.SELECT genannt) werden Einträge vom Ende der Liste getrimmt, es sei denn, einige wenige Ausreißer weichen in Bezug auf die verbleibenden Einträge signifikant ab, in welchem Fall die Ausreißer zuerst verworfen werden. Die Abbruchbedingung ist so konzipiert, dass unnötiges Wechseln zwischen Synchronisationsquellen vermieden wird, wenn dies statistisch nicht gerechtfertigt ist, während gleichzeitig eine Voreingenommenheit gegenüber den Niedrig-Schicht-, Niedrig-Distanz-Peers beibehalten wird.