4. Algorithmes de Filtrage et de Sélection
Un facteur très important affectant la précision et la fiabilité de la distribution du temps est le complexe d'algorithmes utilisés pour réduire l'effet des erreurs statistiques et des faux chronométreurs (falsetickers) dus à la défaillance de divers composants de sous-réseau, sources de référence ou médias de propagation. Les algorithmes suggérés dans cette section ont été développés et affinés au cours de plusieurs années d'exploitation sur Internet dans des topologies, vitesses et régimes de trafic très variés. Bien que ces algorithmes soient considérés comme les meilleurs disponibles à l'heure actuelle, ils ne font pas partie intégrante de la spécification NTP, car d'autres algorithmes avec des performances similaires ou supérieures peuvent être conçus à l'avenir.
Cependant, il est important d'observer que tous les serveurs de temps ou clients dans un sous-réseau de synchronisation NTP ne doivent pas nécessairement implémenter ces algorithmes. Par exemple, les postes de travail simples peuvent se passer de l'un ou des deux dans l'intérêt de la simplicité si les exigences de précision et de fiabilité le justifient. Néanmoins, on s'attendrait à ce qu'un serveur NTP fournissant une synchronisation à une communauté importante, telle qu'un campus universitaire ou un laboratoire de recherche, soit censé implémenter ces algorithmes ou d'autres ayant une fonctionnalité équivalente prouvée. Une discussion complète des principes de conception et des performances est donnée dans [MIL91a].
Pour que les algorithmes de filtre et de sélection NTP fonctionnent efficacement, il est utile d'avoir une mesure de la variance récente des échantillons enregistrée pour chaque pair. La mesure adoptée est basée sur les différences de premier ordre, qui sont faciles à calculer et efficaces pour les objectifs visés. Il existe deux mesures, l'une appelée dispersion de filtre (filter dispersion) ε_σ et l'autre dispersion de sélection (select dispersion) ε_ξ. Les deux sont calculées comme la somme pondérée des décalages d'horloge dans une liste temporaire triée par distance de synchronisation. Si θ_i (0 <= i < n) est le décalage de la i-ème entrée, alors la différence d'échantillon ε_ij de la i-ème entrée par rapport à la j-ème entrée est définie ε_ij = |θ_i - θ_j|. La dispersion par rapport à la j-ème entrée est définie ε_j et calculée comme la somme pondérée:
ε_j = Σ(i=0 to n-1) ε_ij w^(i+1)
où w est un facteur de pondération choisi pour contrôler l'influence de la distance de synchronisation dans le budget de dispersion. Dans les algorithmes NTP, w est choisi inférieur à 1/2: w = NTP.FILTER pour la dispersion de filtre et w = NTP.SELECT pour la dispersion de sélection. La dispersion (absolue) ε_σ et ε_ξ utilisée dans les algorithmes NTP est définie par rapport à la 0-ème entrée ε_0.
Deux procédures sont décrites dans ce qui suit, la procédure de filtre d'horloge (clock-filter procedure), qui est utilisée pour sélectionner les meilleurs échantillons de décalage d'une horloge donnée, et la procédure de sélection d'horloge (clock-selection procedure), qui est utilisée pour sélectionner la meilleure horloge parmi un ensemble hiérarchique d'horloges.
4.1. Procédure de Filtre d'Horloge
La procédure de filtre d'horloge est exécutée à l'arrivée d'un message NTP ou d'un autre événement qui résulte en de nouveaux échantillons de données. Elle prend des arguments de la forme (θ, δ, ε), où θ est une mesure d'échantillon de décalage d'horloge et δ et ε sont le délai aller-retour et la dispersion associés. Elle détermine le décalage d'horloge filtré (peer.offset), le délai aller-retour (peer.delay) et la dispersion (peer.dispersion). Elle met également à jour la dispersion des échantillons déjà enregistrés et enregistre l'heure actuelle (peer.update).
La base de la procédure de filtre d'horloge est le registre à décalage de filtre (peer.filter), qui consiste en NTP.SHIFT étages, chaque étage stockant un 3-uplet [θ_i, δ_i, ε_i], avec des indices numérotés de zéro à gauche. Le filtre est initialisé avec la valeur [0, 0, NTP.MAXDISPERSE] dans tous les étages par la procédure de nettoyage. De nouveaux échantillons de données sont décalés dans le filtre à l'extrémité gauche, provoquant d'abord des NULL puis de vieux échantillons à tomber de l'extrémité droite. La procédure de paquet fournit des échantillons de la forme (θ, δ, ε) lorsque de nouvelles mises à jour arrivent, tandis que la procédure de transmission fournit des échantillons de la forme [0, 0, NTP.MAXDISPERSE] lorsque deux intervalles de sondage s'écoulent sans mise à jour fraîche. Bien que les mêmes symboles (θ, δ, ε) soient utilisés ici pour les arguments, le contenu du filtre d'horloge et les variables de pair, le sens sera clair à partir du contexte. Le pseudo-code suivant décrit cette procédure.
Les variables peer.offset et peer.delay représentent le décalage d'horloge et le délai aller-retour de l'horloge locale par rapport à l'horloge du pair. Ces deux quantités sont des quantités de précision et peuvent généralement être moyennées sur de longs intervalles afin d'améliorer la précision et la stabilité sans accumulation de biais (voir Annexe H). La variable peer.dispersion représente l'erreur maximale due à l'erreur de mesure, à l'accumulation d'erreur de biais et à la variance de l'échantillon. Les trois variables sont utilisées dans les procédures de sélection d'horloge et de combinaison d'horloge pour sélectionner l'horloge(s) de pair utilisée(s) pour la synchronisation et pour maximiser la précision et la stabilité des indications.
4.2. Procédure de Sélection d'Horloge
La procédure de sélection d'horloge utilise les variables de pair THETA, DELTA, EPSILON et τ et est appelée lorsque ces variables changent ou lorsque l'état de disponibilité change. Elle consiste en deux algorithmes, l'algorithme d'intersection (intersection algorithm) et l'algorithme de regroupement (clustering algorithm). L'algorithme d'intersection construit une liste de pairs candidats éligibles pour devenir la source de synchronisation, calcule un intervalle de confiance pour chacun et rejette les faux chronométreurs en utilisant une technique adaptée de Marzullo et Owicki [MAR85]. L'algorithme de regroupement trie la liste des candidats survivants par ordre de strate et de distance de synchronisation et rejette à plusieurs reprises les valeurs aberrantes sur la base de la dispersion de sélection jusqu'à ce que seuls les survivants les plus précis, précis et stables restent. Un bit est défini pour chaque survivant pour indiquer le résultat du processus de sélection. La variable système sys.peer est définie comme un pointeur vers le survivant le plus probable, s'il y en a un, ou vers la valeur NULL sinon.
4.2.1. Algorithme d'Intersection
L'algorithme d'intersection est adapté de DTS [DEC89] et est conçu pour produire la plus grande intersection unique contenant uniquement des vrais chronométreurs. L'algorithme commence par initialiser une valeur f et des compteurs i et c à zéro. Ensuite, en partant du point d'extrémité le plus bas de la liste de points d'extrémité triée, pour chaque entrée [point d'extrémité, type] la valeur de type est soustraite du compteur i, qui est le nombre d'intersections. Si type est zéro, incrémenter la valeur de c, qui est le nombre de faux chronométreurs (voir Annexe H). Si i >= m - f pour une certaine entrée, le point d'extrémité de cette entrée devient le point d'extrémité inférieur de l'intersection; sinon, f est augmenté de un et la procédure ci-dessus est répétée. Sans réinitialiser f ou c, une procédure similaire est utilisée pour trouver le point d'extrémité supérieur, sauf que la valeur de type est ajoutée au compteur. Si après que les deux points d'extrémité aient été déterminés c <= f, la procédure continue ayant trouvé m - f vrais chronométreurs; sinon, f est augmenté de un et toute la procédure est répétée.
4.2.2. Algorithme de Regroupement
Dans l'algorithme DTS original, la procédure de sélection d'horloge se termine à ce point avec le temps présumé correct défini au milieu de l'intersection calculée [low, high]. Cependant, cela peut conduire à une perte considérable de précision et de stabilité, car les statistiques de pair individuelles sont perdues. Par conséquent, dans NTP, les candidats qui ont survécu aux étapes précédentes sont traités plus loin. La liste de candidats est reconstruite avec des entrées de la forme [distance, index], où la distance est calculée à partir de la strate de pair (mise à l'échelle) et de la distance de synchronisation LAMBDA. Le facteur d'échelle fournit un mécanisme pour pondérer la combinaison de strate et de distance. Ordinairement, la strate dominera, à moins qu'un ou plusieurs des survivants n'aient une distance exceptionnellement élevée. La liste est ensuite triée par distance croissante.
L'algorithme est conçu pour favoriser les pairs près de la tête de la liste de candidats, qui sont à la strate et à la distance les plus basses et peuvent vraisemblablement fournir le temps le plus précis et stable. Avec une sélection appropriée du facteur de poids v (également appelé NTP.SELECT), les entrées seront coupées de la queue de la liste, à moins que quelques valeurs aberrantes ne soient en désaccord significatif par rapport aux entrées restantes, auquel cas les valeurs aberrantes sont rejetées en premier. La condition de terminaison est conçue pour éviter les changements inutiles entre les sources de synchronisation lorsqu'ils ne sont pas statistiquement justifiés, tout en maintenant un biais vers les pairs de strate basse et de distance basse.