1. Einführung
Dieses Dokument stellt eine formale Spezifikation des Netzwerkzeitprotokolls (Network Time Protocol, NTP) Version 3 dar, das zur Synchronisierung der Zeitmessung zwischen einer Gruppe verteilter Zeitserver und Clients verwendet wird. Es definiert die von NTP verwendeten Architekturen, Algorithmen, Entitäten und Protokolle und richtet sich in erster Linie an Implementierer. Ein Begleitdokument [MIL91a] fasst die Anforderungen, analytischen Modelle, algorithmische Analyse und Leistung unter typischen Internetbedingungen zusammen. Ein weiteres Dokument [MIL91b] beschreibt die NTP-Zeitskala und ihre Beziehung zu anderen derzeit verwendeten Standardzeitskalen. NTP wurde erstmals in RFC-958 [MIL85c] beschrieben, hat sich jedoch seitdem erheblich weiterentwickelt und gipfelte in der neuesten NTP-Version 2, die in RFC-1119 [MIL89] beschrieben wird. Es basiert auf dem Internetprotokoll (IP) [DAR81a] und dem Benutzerdatagrammprotokoll (UDP) [POS80], die einen verbindungslosen Transportmechanismus bereitstellen; es ist jedoch leicht an andere Protokollsuiten anpassbar. NTP hat sich aus dem Zeitprotokoll (Time Protocol) [POS83b] und der ICMP-Zeitstempelnachricht (ICMP Timestamp message) [DAR81b] entwickelt, ist jedoch speziell darauf ausgelegt, Genauigkeit und Robustheit aufrechtzuerhalten, selbst wenn es über typische Internetpfade verwendet wird, die mehrere Gateways, hochgradig dispersive Verzögerungen und unzuverlässige Netze umfassen.
Die Dienstumgebung besteht aus dem Implementierungsmodell (implementation model) und dem Dienstmodell (service model), die in Abschnitt 2 beschrieben werden. Das Implementierungsmodell basiert auf einer Mehrprozess-Betriebssystemarchitektur, obwohl auch andere Architekturen verwendet werden könnten. Das Dienstmodell basiert auf einem rückgabefähigen Zeitdesign (returnable-time), das nur von gemessenen Uhrenversätzen (clock offsets) abhängt, aber keine zuverlässige Nachrichtenübermittlung erfordert. Das Synchronisationssubnetz (synchronization subnet) verwendet eine selbstorganisierende hierarchische Master-Slave-Konfiguration (hierarchical-master-slave configuration), wobei Synchronisationspfade durch einen minimal gewichteten Spannbaum (minimum-weight spanning tree) bestimmt werden. Während mehrere Master (primäre Server, primary servers) existieren können, ist kein Wahlprotokoll erforderlich.
NTP selbst wird in Abschnitt 3 beschrieben. Es bietet die Protokollmechanismen, um die Zeit prinzipiell auf Präzisionen in der Größenordnung von Nanosekunden zu synchronisieren und gleichzeitig ein eindeutiges Datum bis weit ins nächste Jahrhundert hinein zu bewahren. Das Protokoll enthält Bestimmungen zur Spezifikation der Merkmale und zur Schätzung des Fehlers der lokalen Uhr und des Zeitservers, mit dem sie möglicherweise synchronisiert wird. Es enthält auch Bestimmungen für den Betrieb mit einer Anzahl von gegenseitig misstrauischen, hierarchisch verteilten primären Referenzquellen wie funkynchronisierten Uhren.
Abschnitt 4 beschreibt Algorithmen, die für die Entglitchung (deglitching) und Glättung von Uhrenversatz-Proben nützlich sind, die kontinuierlich gesammelt werden. Diese Algorithmen haben sich aus denen entwickelt, die in [MIL85a] vorgeschlagen wurden, wurden als Ergebnis von in [MIL85b] beschriebenen Experimenten verfeinert und entwickelten sich in den letzten drei Jahren unter typischen Betriebsbedingungen weiter. Darüber hinaus wurden aufgrund der Erfahrung beim Betrieb von Mehrfachserversubnetzen einschließlich Funkuhren an mehreren Standorten in den USA und mit Clients in den USA und Europa zuverlässige Algorithmen zur Auswahl guter Uhren aus einer Population entwickelt, die möglicherweise defekte enthält [DEC89], [MIL91a] und werden in Abschnitt 4 beschrieben.
Die mit NTP erreichbaren Genauigkeiten hängen stark von der Präzision der lokalen Uhrenhardware und der strengen Kontrolle der Geräte- und Prozesslatenzen ab. Es müssen Bestimmungen enthalten sein, um die Software-Logikuhrzeit und -frequenz als Reaktion auf von NTP erzeugte Korrekturen anzupassen. Abschnitt 5 beschreibt ein lokales Uhrendesign, das sich aus der in [MIL83b] und [MIL88b] beschriebenen Fuzzball-Implementierung entwickelt hat. Dieses Design umfasst Offset-Slewing-, Frequenzkompensations- (frequency compensation) und Entglitchungsmechanismen, die Genauigkeiten in der Größenordnung einer Millisekunde erreichen können, selbst nach längeren Zeiträumen, in denen die Synchronisierung mit primären Referenzquellen verloren gegangen ist.
Details zu NTP-Paketformaten, die mit dem Internetprotokoll (IP) und dem Benutzerdatagrammprotokoll (UDP) verwendet werden, werden in Anhang A dargestellt, während Details einer vorgeschlagenen zusätzlichen NTP-Steuerungsnachricht (NTP Control Message), die verwendet werden kann, wenn umfassende Netzwerküberwachungseinrichtungen nicht verfügbar sind, in Anhang B dargestellt werden. Anhang C enthält Spezifikations- und Implementierungsdetails eines optionalen Authentifizierungsmechanismus (authentication mechanism), der zur Zugriffssteuerung und zur Verhinderung unbefugter Datenänderungen verwendet werden kann, während Anhang D eine Auflistung der Unterschiede zwischen Version 3 von NTP und früheren Versionen enthält. Anhang E erweitert Fragen im Zusammenhang mit Präzisionszeitskalen und Kalenderdatierung, die für Computernetzwerke und NTP spezifisch sind. Anhang F beschreibt einen optionalen Algorithmus zur Verbesserung der Genauigkeit durch Kombination der Zeitversätze mehrerer Uhren. Anhang G präsentiert ein detailliertes mathematisches Modell und eine Analyse der NTP-Lokaluhrenalgorithmen. Anhang H analysiert die Quellen und die Ausbreitung von Fehlern und präsentiert Korrektheitsprinzipien (correctness principles) in Bezug auf den Zeitübertragungsdienst. Anhang I veranschaulicht C-Sprach-Codesegmente für die in Abschnitt 4 beschriebenen Uhrenfilter-, Uhrenauswahl- und verwandten Algorithmen.
1.1. Verwandte Technologie
Andere Mechanismen wurden in der Internet-Protokollsuite spezifiziert, um die Zeit aufzuzeichnen und zu übertragen, zu der ein Ereignis stattfindet, einschließlich des Daytime-Protokolls (Daytime protocol) [POS83a], des Zeitprotokolls (Time Protocol) [POS83b], der ICMP-Zeitstempelnachricht (ICMP Timestamp message) [DAR81b] und der IP-Zeitstempeloption (IP Timestamp option) [SU81]. Experimentelle Ergebnisse zu gemessenen Uhrenversätzen und Rundlaufzeiten im Internet werden in [MIL83a], [MIL85b], [COL88] und [MIL88a] diskutiert. Andere Synchronisationsalgorithmen werden in [LAM78], [GUS84], [HAL84], [LUN84], [LAM85], [MAR85], [MIL85a], [MIL85b], [MIL85c], [GUS85b], [SCH86], [TRI86], [RIC88], [MIL88a], [DEC89] und [MIL91a] diskutiert, während auf ihnen basierende Protokolle in [MIL81a], [MIL81b], [MIL83b], [GUS85a], [MIL85c], [TRI86], [MIL88a], [DEC89] und [MIL91a] beschrieben werden. NTP verwendet von ihnen entwickelte Techniken sowie lineare Systeme (linear-systems) und Übereinstimmungsmethodologien (agreement). Lineare Methoden für die digitale Telefonnetzwerksynchronisation werden in [LIN80] zusammengefasst, während Übereinstimmungsmethoden für die Uhrensynchronisation in [LAM85] zusammengefasst werden.
Der Digitale Zeitdienst (Digital Time Service, DTS) [DEC89] hat viele der gleichen Dienstziele wie NTP. Das DTS-Design legt starken Wert auf Konfigurationsverwaltung und Korrektheitsprinzipien beim Betrieb in einer verwalteten LAN- oder LAN-Cluster-Umgebung, während NTP starken Wert auf die Genauigkeit und Stabilität des in einer nicht verwalteten globalen Internetumgebung betriebenen Dienstes legt. In DTS besteht ein Synchronisationssubnetz aus Angestellten (clerks), Servern (servers), Kurieren (couriers) und Zeitanbietern (time providers). In Bezug auf die NTP-Nomenklatur ist ein Zeitanbieter eine primäre Referenzquelle, ein Kurier ist ein sekundärer Server, der dazu bestimmt ist, Zeit von einem oder mehreren entfernten primären Servern zur lokalen Umverteilung zu importieren, und ein Server ist dazu bestimmt, Zeit für möglicherweise viele Endknoten oder Angestellte bereitzustellen. Im Gegensatz zu NTP benötigt oder verwendet DTS bei der Uhrenauswahl keine Modus- oder Schichtinformationen (mode or stratum information) und enthält keine Bestimmungen zum Filtern von Zeitrauschen, zur Auswahl der genauesten aus einer Reihe vermutlich korrekter Uhren oder zur Kompensation inhärenter Frequenzfehler.
Tatsächlich haben die neuesten Überarbeitungen von NTP bestimmte Funktionen von DTS übernommen, um Korrektheitsprinzipien zu unterstützen. Dazu gehören Mechanismen zur Begrenzung der maximalen Fehler, die den Zeitübertragungsverfahren innewohnen, und die Verwendung eines nachweislich korrekten (vorbehaltlich angegebener Annahmen) Mechanismus zur Ablehnung unangemessener Peers in den Uhrenauswahlverfahren. Diese Funktionen werden in Abschnitt 4 und Anhang H dieses Dokuments beschrieben.
Das Fuzzball-Routingprotokoll (Fuzzball routing protocol) [MIL83b], manchmal Hellospeak genannt, integriert die Zeitsynchronisation direkt in das Routingprotokolldesign. Ein oder mehrere Prozesse synchronisieren sich mit einer externen Referenzquelle, wie einer Funkuhr oder einem NTP-Daemon, und der Routingalgorithmus konstruiert einen minimal gewichteten Spannbaum, der auf diesen Prozessen verwurzelt ist. Die Uhrenversätze werden dann entlang der Bögen des Spannbaums an alle Prozesse im System verteilt und die verschiedenen Prozessuhren unter Verwendung des in Abschnitt 5 dieses Dokuments beschriebenen Verfahrens korrigiert. Obwohl erkennbar ist, dass das Design von Hellospeak das Design von NTP stark beeinflusst hat, ist Hellospeak selbst kein Internetprotokoll und für die Verwendung außerhalb seiner lokalen Netzumgebung ungeeignet.
Der Unix 4.3bsd-Zeitdaemon timed [GUS85a] verwendet einen einzelnen Master-Zeitdaemon, um Versätze mehrerer Slave-Hosts zu messen und ihnen periodische Korrekturen zu senden. In diesem Modell wird der Master mithilfe eines Wahlalgorithmus (election algorithm) [GUS85b] bestimmt, der so konzipiert ist, dass Situationen vermieden werden, in denen entweder kein Master gewählt wird oder mehr als ein Master gewählt wird. Der Wahlprozess erfordert eine Broadcast-Fähigkeit, die keine allgegenwärtige Funktion des Internets ist. Während dieses Modell erweitert wurde, um hierarchische Konfigurationen zu unterstützen, bei denen ein Slave in einem Netzwerk als Master im anderen dient [TRI86], erfordert das Modell handgefertigte Konfigurationstabellen, um die Hierarchie einzurichten und Schleifen zu vermeiden. Zusätzlich zu den belastenden, aber vermutlich seltenen Overheads des Wahlprozesses erfordert der Versatzmessungs-/Korrekturprozess doppelt so viele Nachrichten wie NTP pro Aktualisierung.
Ein Schema mit ähnlichen Funktionen wie NTP wird in [KOP87] beschrieben. Dieses Schema ist für Multi-Server-LANs vorgesehen, bei denen jeder aus einem Satz von möglicherweise vielen Zeitservern seinen lokalen Zeitversatz relativ zu jedem der anderen Server im Satz unter Verwendung periodischer Zeitstempelnachrichten bestimmt und dann die lokale Uhrenkorrektur unter Verwendung des Fehlertoleranten Durchschnitts (Fault-Tolerant Average, FTA) Algorithmus von [LUN84] bestimmt. Der FTA-Algorithmus, der nützlich ist, wenn bis zu k Server fehlerhaft sein können, sortiert die Versätze, verwirft die k höchsten und niedrigsten und mittelt den Rest. Das Schema ist, wie in [SCH86] beschrieben, am besten für LAN-Umgebungen geeignet, die Broadcast unterstützen, und würde in einer Internetumgebung zu inakzeptablem Overhead führen. Darüber hinaus sind aus den in Abschnitt 4 dieses Papiers angegebenen Gründen die statistischen Eigenschaften des FTA-Algorithmus in einer Internetumgebung mit hochgradig dispersiven Verzögerungen wahrscheinlich nicht optimal.
Viel Forschung hat sich mit der Frage befasst, genaue Zeit in einer Gemeinschaft aufrechtzuerhalten, in der einige Uhren nicht vertraut werden können. Ein Wahrheitsmesser (truechimer) ist eine Uhr, die die Zeitmessgenauigkeit zu einem zuvor veröffentlichten (und vertrauenswürdigen) Standard aufrechterhält, während ein Falschmesser (falseticker) eine Uhr ist, die dies nicht tut. Die Bestimmung, ob eine bestimmte Uhr ein Wahrheitsmesser oder ein Falschmesser ist, ist ein interessantes abstraktes Problem, das mit in [LAM85] und [SRI87] zusammengefassten Übereinstimmungsmethoden angegriffen werden kann.
Eine Konvergenzfunktion (convergence function) arbeitet mit den Versätzen zwischen den Uhren in einem System, um die Genauigkeit zu erhöhen, indem Fehler, die durch Falschmesser verursacht werden, reduziert oder eliminiert werden. Es gibt zwei Klassen von Konvergenzfunktionen, solche, die interaktive Konvergenzalgorithmen (interactive-convergence algorithms) beinhalten, und solche, die interaktive Konsistenzalgorithmen (interactive-consistency algorithms) beinhalten. Interaktive Konvergenzalgorithmen verwenden statistische Clustering-Techniken wie den fehlertoleranten Durchschnittsalgorithmus von [HAL84], den CNV-Algorithmus von [LUN84], den Mehrheits-Teilmengen-Algorithmus von [MIL85a], den nicht-byzantinischen Algorithmus von [RIC88], den egozentrischen Algorithmus von [SCH86], den Schnittalgorithmus von [MAR85] und [DEC89] sowie die Algorithmen in Abschnitt 4 dieses Dokuments.
Interaktive Konsistenzalgorithmen sind so konzipiert, dass sie fehlerhafte Uhrenprozesse erkennen, die in aufeinanderfolgenden Messungen oder bei verschiedenen Lesern grob inkonsistente Versätze anzeigen könnten. Diese Algorithmen verwenden ein Übereinstimmungsprotokoll, das aufeinanderfolgende Runden von Messungen umfasst, möglicherweise weitergeleitet und möglicherweise durch digitale Signaturen erweitert. Beispiele sind der Feuerwerksalgorithmus von [HAL84] und der optimale Algorithmus von [SRI87]. Diese Algorithmen erfordern jedoch große Mengen an Nachrichten, insbesondere wenn große Mengen an Uhren beteiligt sind, und sind so konzipiert, dass sie Fehler erkennen, die in der Interneterfahrung selten gefunden wurden. Aus diesen Gründen werden sie in diesem Dokument nicht weiter betrachtet.
In der Praxis ist es nicht möglich, die Wahrheitsmesser von den Falschmessern auf einer anderen als einer statistischen Basis zu bestimmen, insbesondere bei hierarchischen Konfigurationen und einem statistisch verrauschten Internet. Obwohl es möglich ist, die maximalen Fehler in den Zeitübertragungsverfahren zu begrenzen, vorausgesetzt, ausreichend großzügige Toleranzen werden für die Hardwarekomponenten angenommen, führt dies im Allgemeinen zu ziemlich schlechten Genauigkeiten und Stabilitäten. Der in der NTP-Design und seinen Vorgängern verfolgte Ansatz beinhaltet gegenseitig gekoppelte Oszillatoren (mutually coupled oscillators) und Maximum-Likelihood-Schätzung (maximum-likelihood estimation) und Uhrenauswahlverfahren sowie ein Design, das beweisbare Aussagen über Fehlergrenzen relativ zu angegebenen Annahmen über die Korrektheit der primären Referenzquellen ermöglicht. Aus analytischer Sicht arbeitet das System verteilter NTP-Peers als Satz gekoppelter phasenverriegelter Oszillatoren (coupled phase-locked oscillators), wobei der Aktualisierungsalgorithmus als Phasendetektor und die lokale Uhr als disziplinierter Oszillator (disciplined oscillator) fungiert, jedoch mit deterministischen Fehlergrenzen, die bei jedem Schritt im Zeitübertragungsprozess berechnet werden.
Die spezifische Wahl des in Abschnitt 3 beschriebenen Versatzmessungs- und Berechnungsverfahrens ist eine Variante des in einigen digitalen Telefonnetzwerken [LIN80] verwendeten rückgabefähigen Zeitsystems. Die Uhrenfilter- und Auswahlalgorithmen sind so konzipiert, dass sich das Uhrensynchronisationssubnetz in eine hierarchische Master-Slave-Konfiguration [MIT80] selbst organisiert. In Bezug auf Zeitmessgenauigkeit und Stabilität ist die Ähnlichkeit von NTP zu digitalen Telefonsystemen kein Zufall, da solche Systeme ausführlich untersucht wurden [LIN80], [BRA80]. Was das NTP-Modell einzigartig macht, sind die adaptiven Konfigurations-, Polling-, Filter-, Auswahl- und Korrektheitsmechanismen, die die Dynamik des Systems anpassen, um zur allgegenwärtigen Internetumgebung zu passen.