1. Introduction

Ce document constitue une spécification formelle du Protocole de Temps Réseau (Network Time Protocol, NTP) Version 3, qui est utilisé pour synchroniser la gestion du temps parmi un ensemble de serveurs de temps et de clients distribués. Il définit les architectures, algorithmes, entités et protocoles utilisés par NTP et est destiné principalement aux implémenteurs. Un document d'accompagnement [MIL91a] résume les exigences, les modèles analytiques, l'analyse algorithmique et les performances dans des conditions Internet typiques. Un autre document [MIL91b] décrit l'échelle de temps NTP et sa relation avec d'autres échelles de temps standard actuellement utilisées. NTP a été décrit pour la première fois dans RFC-958 [MIL85c], mais a depuis évolué de manière significative, culminant dans la version la plus récente NTP Version 2 décrite dans RFC-1119 [MIL89]. Il est construit sur le Protocole Internet (IP) [DAR81a] et le Protocole de Datagramme Utilisateur (UDP) [POS80], qui fournissent un mécanisme de transport sans connexion; cependant, il est facilement adaptable à d'autres suites de protocoles. NTP a évolué à partir du Protocole de Temps (Time Protocol) [POS83b] et du message d'horodatage ICMP (ICMP Timestamp message) [DAR81b], mais est spécifiquement conçu pour maintenir la précision et la robustesse, même lorsqu'il est utilisé sur des chemins Internet typiques impliquant plusieurs passerelles, des délais hautement dispersifs et des réseaux non fiables.

L'environnement de service se compose du modèle d'implémentation (implementation model) et du modèle de service (service model) décrits dans la Section 2. Le modèle d'implémentation est basé sur une architecture de système d'exploitation multi-processus, bien que d'autres architectures puissent également être utilisées. Le modèle de service est basé sur une conception de temps retournable (returnable-time) qui ne dépend que des décalages d'horloge mesurés (clock offsets), mais ne nécessite pas de livraison de message fiable. Le sous-réseau de synchronisation (synchronization subnet) utilise une configuration hiérarchique maître-esclave auto-organisée (hierarchical-master-slave configuration), avec des chemins de synchronisation déterminés par un arbre couvrant de poids minimum (minimum-weight spanning tree). Bien que plusieurs maîtres (serveurs primaires, primary servers) puissent exister, il n'y a pas d'exigence pour un protocole d'élection.

NTP lui-même est décrit dans la Section 3. Il fournit les mécanismes de protocole pour synchroniser le temps en principe à des précisions de l'ordre des nanosecondes tout en préservant une date non ambiguë jusqu'au siècle prochain. Le protocole comprend des dispositions pour spécifier les caractéristiques et estimer l'erreur de l'horloge locale et du serveur de temps auquel il peut être synchronisé. Il comprend également des dispositions pour fonctionner avec un certain nombre de sources de référence primaires hiérarchiquement distribuées et mutuellement suspectes telles que les horloges synchronisées par radio.

La Section 4 décrit des algorithmes utiles pour le dégrossissage (deglitching) et le lissage des échantillons de décalage d'horloge collectés sur une base continue. Ces algorithmes ont évolué à partir de ceux suggérés dans [MIL85a], ont été affinés en fonction des résultats d'expériences décrites dans [MIL85b] et ont continué d'évoluer dans des conditions de fonctionnement typiques au cours des trois dernières années. De plus, à la suite de l'expérience dans l'exploitation de sous-réseaux multi-serveurs incluant des horloges radio à plusieurs sites aux États-Unis et avec des clients aux États-Unis et en Europe, des algorithmes fiables pour sélectionner de bonnes horloges parmi une population incluant possiblement des horloges défectueuses ont été développés [DEC89], [MIL91a] et sont décrits dans la Section 4.

Les précisions réalisables par NTP dépendent fortement de la précision du matériel d'horloge locale et du contrôle strict des latences de dispositif et de processus. Des dispositions doivent être incluses pour ajuster le temps et la fréquence de l'horloge logique logicielle en réponse aux corrections produites par NTP. La Section 5 décrit une conception d'horloge locale évoluée à partir de l'implémentation Fuzzball décrite dans [MIL83b] et [MIL88b]. Cette conception comprend des mécanismes d'ajustement de décalage (offset-slewing), de compensation de fréquence (frequency compensation) et de dégrossissage capables de précisions de l'ordre d'une milliseconde, même après de longues périodes pendant lesquelles la synchronisation avec les sources de référence primaires a été perdue.

Les détails spécifiques aux formats de paquets NTP utilisés avec le Protocole Internet (IP) et le Protocole de Datagramme Utilisateur (UDP) sont présentés dans l'Annexe A, tandis que les détails d'un Message de Contrôle NTP auxiliaire suggéré (NTP Control Message), qui peut être utilisé lorsque des installations de surveillance réseau complètes ne sont pas disponibles, sont présentés dans l'Annexe B. L'Annexe C contient les spécifications et les détails d'implémentation d'un mécanisme d'authentification optionnel (authentication mechanism) qui peut être utilisé pour contrôler l'accès et empêcher la modification non autorisée des données, tandis que l'Annexe D contient une liste des différences entre la Version 3 de NTP et les versions précédentes. L'Annexe E développe les questions liées aux échelles de temps de précision et à la datation calendaire particulières aux réseaux informatiques et à NTP. L'Annexe F décrit un algorithme optionnel pour améliorer la précision en combinant les décalages de temps d'un certain nombre d'horloges. L'Annexe G présente un modèle mathématique détaillé et une analyse des algorithmes d'horloge locale NTP. L'Annexe H analyse les sources et la propagation des erreurs et présente des principes de correction (correctness principles) relatifs au service de transfert de temps. L'Annexe I illustre des segments de code en langage C pour le filtre d'horloge, la sélection d'horloge et les algorithmes connexes décrits dans la Section 4.

1.1. Technologie Connexe

D'autres mécanismes ont été spécifiés dans la suite de protocoles Internet pour enregistrer et transmettre l'heure à laquelle un événement se produit, y compris le protocole Daytime (Daytime protocol) [POS83a], le Protocole de Temps (Time Protocol) [POS83b], le message d'horodatage ICMP (ICMP Timestamp message) [DAR81b] et l'option d'horodatage IP (IP Timestamp option) [SU81]. Les résultats expérimentaux sur les décalages d'horloge mesurés et les délais aller-retour sur Internet sont discutés dans [MIL83a], [MIL85b], [COL88] et [MIL88a]. D'autres algorithmes de synchronisation sont discutés dans [LAM78], [GUS84], [HAL84], [LUN84], [LAM85], [MAR85], [MIL85a], [MIL85b], [MIL85c], [GUS85b], [SCH86], [TRI86], [RIC88], [MIL88a], [DEC89] et [MIL91a], tandis que les protocoles basés sur eux sont décrits dans [MIL81a], [MIL81b], [MIL83b], [GUS85a], [MIL85c], [TRI86], [MIL88a], [DEC89] et [MIL91a]. NTP utilise des techniques évoluées à partir de ceux-ci et des méthodologies de systèmes linéaires (linear-systems) et d'accord (agreement). Les méthodes linéaires pour la synchronisation des réseaux téléphoniques numériques sont résumées dans [LIN80], tandis que les méthodes d'accord pour la synchronisation des horloges sont résumées dans [LAM85].

Le Service de Temps Numérique (Digital Time Service, DTS) [DEC89] a beaucoup des mêmes objectifs de service que NTP. La conception DTS met fortement l'accent sur la gestion de la configuration et les principes de correction lorsqu'il fonctionne dans un environnement LAN géré ou de cluster LAN, tandis que NTP met fortement l'accent sur la précision et la stabilité du service fonctionnant dans un environnement internet global non géré. Dans DTS, un sous-réseau de synchronisation se compose d'employés (clerks), de serveurs (servers), de courriers (couriers) et de fournisseurs de temps (time providers). En ce qui concerne la nomenclature NTP, un fournisseur de temps est une source de référence primaire, un courrier est un serveur secondaire destiné à importer le temps d'un ou plusieurs serveurs primaires distants pour une redistribution locale et un serveur est destiné à fournir le temps à de nombreux nœuds finaux ou employés. Contrairement à NTP, DTS n'a pas besoin ou n'utilise pas d'informations de mode ou de strate (mode or stratum information) dans la sélection d'horloge et n'inclut pas de dispositions pour filtrer le bruit de synchronisation, sélectionner le plus précis parmi un ensemble d'horloges présumées correctes ou compenser les erreurs de fréquence inhérentes.

En fait, les dernières révisions de NTP ont adopté certaines fonctionnalités de DTS afin de soutenir les principes de correction. Celles-ci incluent des mécanismes pour limiter les erreurs maximales inhérentes aux procédures de transfert de temps et l'utilisation d'un mécanisme prouvablement correct (sous réserve d'hypothèses énoncées) pour rejeter les pairs inappropriés dans les procédures de sélection d'horloge. Ces fonctionnalités sont décrites dans la Section 4 et l'Annexe H de ce document.

Le protocole de routage Fuzzball (Fuzzball routing protocol) [MIL83b], parfois appelé Hellospeak, intègre la synchronisation temporelle directement dans la conception du protocole de routage. Un ou plusieurs processus se synchronisent sur une source de référence externe, telle qu'une horloge radio ou un démon NTP, et l'algorithme de routage construit un arbre couvrant de poids minimum enraciné sur ces processus. Les décalages d'horloge sont ensuite distribués le long des arcs de l'arbre couvrant à tous les processus du système et les diverses horloges de processus sont corrigées en utilisant la procédure décrite dans la Section 5 de ce document. Bien qu'il soit évident que la conception de Hellospeak a fortement influencé la conception de NTP, Hellospeak lui-même n'est pas un protocole Internet et est inadapté pour une utilisation en dehors de son environnement réseau local.

Le démon de temps Unix 4.3bsd timed [GUS85a] utilise un seul démon de temps maître pour mesurer les décalages d'un certain nombre d'hôtes esclaves et leur envoyer des corrections périodiques. Dans ce modèle, le maître est déterminé à l'aide d'un algorithme d'élection (election algorithm) [GUS85b] conçu pour éviter les situations où aucun maître n'est élu ou plusieurs maîtres sont élus. Le processus d'élection nécessite une capacité de diffusion, qui n'est pas une caractéristique omniprésente d'Internet. Bien que ce modèle ait été étendu pour prendre en charge les configurations hiérarchiques dans lesquelles un esclave sur un réseau sert de maître sur l'autre [TRI86], le modèle nécessite des tables de configuration fabriquées à la main afin d'établir la hiérarchie et d'éviter les boucles. En plus des frais généraux onéreux mais vraisemblablement peu fréquents du processus d'élection, le processus de mesure/correction de décalage nécessite deux fois plus de messages que NTP par mise à jour.

Un schéma avec des fonctionnalités similaires à NTP est décrit dans [KOP87]. Ce schéma est destiné aux LAN multi-serveurs où chacun d'un ensemble de nombreux serveurs de temps détermine son décalage de temps local par rapport à chacun des autres serveurs de l'ensemble en utilisant des messages horodatés périodiques, puis détermine la correction d'horloge locale en utilisant l'algorithme de Moyenne Tolérante aux Pannes (Fault-Tolerant Average, FTA) de [LUN84]. L'algorithme FTA, qui est utile où jusqu'à k serveurs peuvent être défaillants, trie les décalages, rejette les k plus élevés et les plus bas et fait la moyenne du reste. Le schéma, tel que décrit dans [SCH86], convient mieux aux environnements LAN qui prennent en charge la diffusion et entraînerait une surcharge inacceptable dans un environnement internet. De plus, pour les raisons données dans la Section 4 de cet article, les propriétés statistiques de l'algorithme FTA ne sont probablement pas optimales dans un environnement internet avec des délais hautement dispersifs.

Beaucoup de recherches ont été consacrées à la question du maintien d'un temps précis dans une communauté où certaines horloges ne peuvent pas être fiables. Un vrai chronométreur (truechimer) est une horloge qui maintient la précision de chronométrage à une norme précédemment publiée (et fiable), tandis qu'un faux chronométreur (falseticker) est une horloge qui ne le fait pas. Déterminer si une horloge particulière est un vrai chronométreur ou un faux chronométreur est un problème abstrait intéressant qui peut être attaqué en utilisant des méthodes d'accord résumées dans [LAM85] et [SRI87].

Une fonction de convergence (convergence function) opère sur les décalages entre les horloges d'un système pour augmenter la précision en réduisant ou en éliminant les erreurs causées par les faux chronométreurs. Il existe deux classes de fonctions de convergence, celles impliquant des algorithmes de convergence interactive (interactive-convergence algorithms) et celles impliquant des algorithmes de cohérence interactive (interactive-consistency algorithms). Les algorithmes de convergence interactive utilisent des techniques de regroupement statistique telles que l'algorithme de moyenne tolérante aux pannes de [HAL84], l'algorithme CNV de [LUN84], l'algorithme de sous-ensemble majoritaire de [MIL85a], l'algorithme non-Byzantin de [RIC88], l'algorithme égocentrique de [SCH86], l'algorithme d'intersection de [MAR85] et [DEC89] et les algorithmes de la Section 4 de ce document.

Les algorithmes de cohérence interactive sont conçus pour détecter les processus d'horloge défaillants qui pourraient indiquer des décalages grossièrement incohérents dans des lectures successives ou à différents lecteurs. Ces algorithmes utilisent un protocole d'accord impliquant des tours successifs de lectures, éventuellement relayées et éventuellement augmentées de signatures numériques. Les exemples incluent l'algorithme de feux d'artifice de [HAL84] et l'algorithme optimal de [SRI87]. Cependant, ces algorithmes nécessitent un grand nombre de messages, en particulier lorsque de nombreuses horloges sont impliquées, et sont conçus pour détecter des pannes qui ont rarement été trouvées dans l'expérience Internet. Pour ces raisons, ils ne sont pas considérés plus loin dans ce document.

En pratique, il n'est pas possible de déterminer les vrais chronométreurs des faux chronométreurs sur une base autre que statistique, en particulier avec des configurations hiérarchiques et un Internet statistiquement bruyant. Bien qu'il soit possible de borner les erreurs maximales dans les procédures de transfert de temps, en supposant que des tolérances suffisamment généreuses sont adoptées pour les composants matériels, cela entraîne généralement des précisions et des stabilités plutôt médiocres. L'approche adoptée dans la conception NTP et ses prédécesseurs implique des oscillateurs couplés mutuellement (mutually coupled oscillators) et des procédures d'estimation du maximum de vraisemblance (maximum-likelihood estimation) et de sélection d'horloge, ainsi qu'une conception qui permet de faire des affirmations prouvables sur les limites d'erreur par rapport aux hypothèses énoncées sur la correction des sources de référence primaires. Du point de vue analytique, le système de pairs NTP distribués fonctionne comme un ensemble d'oscillateurs à verrouillage de phase couplés (coupled phase-locked oscillators), l'algorithme de mise à jour fonctionnant comme un détecteur de phase et l'horloge locale comme un oscillateur discipliné (disciplined oscillator), mais avec des limites d'erreur déterministes calculées à chaque étape du processus de transfert de temps.

Le choix particulier de la procédure de mesure et de calcul du décalage décrit dans la Section 3 est une variante du système de temps retournable utilisé dans certains réseaux téléphoniques numériques [LIN80]. Les algorithmes de filtre et de sélection d'horloge sont conçus de sorte que le sous-réseau de synchronisation d'horloge s'auto-organise en une configuration hiérarchique maître-esclave [MIT80]. En ce qui concerne la précision et la stabilité du chronométrage, la similitude de NTP avec les systèmes téléphoniques numériques n'est pas accidentelle, car des systèmes comme celui-ci ont été étudiés de manière extensive [LIN80], [BRA80]. Ce qui rend le modèle NTP unique, ce sont les mécanismes de configuration adaptative, de sondage, de filtrage, de sélection et de correction qui adaptent la dynamique du système pour s'adapter à l'environnement Internet omniprésent.