4. Algoritmi di Filtraggio e Selezione

Un fattore molto importante che influenza l'accuratezza e l'affidabilità della distribuzione del tempo è il complesso di algoritmi utilizzati per ridurre l'effetto degli errori statistici e dei falsi cronometristi (falsetickers) dovuti al guasto di vari componenti della sottorete, fonti di riferimento o mezzi di propagazione. Gli algoritmi suggeriti in questa sezione sono stati sviluppati e perfezionati nel corso di diversi anni di funzionamento su Internet sotto topologie, velocità e regimi di traffico ampiamente variabili. Sebbene questi algoritmi siano ritenuti i migliori disponibili al momento, non sono una parte integrante della specifica NTP, poiché altri algoritmi con prestazioni simili o superiori potrebbero essere ideati in futuro.

Tuttavia, è importante osservare che non tutti i server di tempo o client in una sottorete di sincronizzazione NTP devono implementare questi algoritmi. Ad esempio, workstation semplici possono rinunciare a uno o entrambi nell'interesse della semplicità se i requisiti di accuratezza e affidabilità lo giustificano. Ciononostante, ci si aspetterebbe che un server NTP che fornisce sincronizzazione a una comunità considerevole, come un campus universitario o un laboratorio di ricerca, sia tenuto a implementare questi algoritmi o altri con funzionalità equivalente dimostrata. Una discussione completa dei principi di progettazione e delle prestazioni è fornita in [MIL91a].

Affinché gli algoritmi di filtro e selezione NTP operino efficacemente, è utile avere una misura della varianza recente dei campioni registrata per ciascun peer. La misura adottata si basa su differenze di primo ordine, che sono facili da calcolare ed efficaci per gli scopi previsti. Ci sono due misure, una chiamata dispersione del filtro (filter dispersion) ε_σ e l'altra dispersione di selezione (select dispersion) ε_ξ. Entrambe sono calcolate come la somma ponderata degli offset dell'orologio in un elenco temporaneo ordinato per distanza di sincronizzazione. Se θ_i (0 <= i < n) è l'offset della i-esima voce, allora la differenza del campione ε_ij della i-esima voce rispetto alla j-esima voce è definita ε_ij = |θ_i - θ_j|. La dispersione rispetto alla j-esima voce è definita ε_j e calcolata come la somma ponderata:

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

dove w è un fattore di ponderazione scelto per controllare l'influenza della distanza di sincronizzazione nel budget di dispersione. Negli algoritmi NTP, w è scelto inferiore a 1/2: w = NTP.FILTER per la dispersione del filtro e w = NTP.SELECT per la dispersione di selezione. La dispersione (assoluta) ε_σ e ε_ξ utilizzata negli algoritmi NTP è definita rispetto alla 0-esima voce ε_0.

Vengono descritte due procedure nel seguito, la procedura di filtro dell'orologio (clock-filter procedure), che viene utilizzata per selezionare i migliori campioni di offset da un dato orologio, e la procedura di selezione dell'orologio (clock-selection procedure), che viene utilizzata per selezionare il miglior orologio tra un insieme gerarchico di orologi.

4.1. Procedura di Filtro dell'Orologio

La procedura di filtro dell'orologio viene eseguita all'arrivo di un messaggio NTP o di un altro evento che risulta in nuovi campioni di dati. Prende argomenti della forma (θ, δ, ε), dove θ è una misurazione del campione di offset dell'orologio e δ e ε sono il ritardo di andata e ritorno e la dispersione associati. Determina l'offset dell'orologio filtrato (peer.offset), il ritardo di andata e ritorno (peer.delay) e la dispersione (peer.dispersion). Aggiorna anche la dispersione dei campioni già registrati e salva il tempo corrente (peer.update).

La base della procedura di filtro dell'orologio è il registro a scorrimento del filtro (peer.filter), che consiste di NTP.SHIFT stadi, ciascuno stadio memorizzando una 3-tupla [θ_i, δ_i, ε_i], con indici numerati da zero a sinistra. Il filtro viene inizializzato con il valore [0, 0, NTP.MAXDISPERSE] in tutti gli stadi dalla procedura di pulizia. I nuovi campioni di dati vengono spostati nel filtro dall'estremità sinistra, causando prima NULL e poi vecchi campioni a cadere dall'estremità destra. La procedura del pacchetto fornisce campioni della forma (θ, δ, ε) quando arrivano nuovi aggiornamenti, mentre la procedura di trasmissione fornisce campioni della forma [0, 0, NTP.MAXDISPERSE] quando due intervalli di polling trascorrono senza un aggiornamento fresco. Sebbene gli stessi simboli (θ, δ, ε) siano usati qui per gli argomenti, il contenuto del filtro dell'orologio e le variabili del peer, il significato sarà chiaro dal contesto. Il seguente pseudo-codice descrive questa procedura.

Le variabili peer.offset e peer.delay rappresentano l'offset dell'orologio e il ritardo di andata e ritorno dell'orologio locale rispetto all'orologio del peer. Entrambe queste sono quantità di precisione e di solito possono essere mediate su intervalli lunghi al fine di migliorare l'accuratezza e la stabilità senza accumulazione di bias (vedere Appendice H). La variabile peer.dispersion rappresenta l'errore massimo dovuto a errore di misurazione, accumulazione di errore di skew e varianza del campione. Tutte e tre le variabili sono utilizzate nelle procedure di selezione dell'orologio e di combinazione dell'orologio per selezionare gli orologi del peer utilizzati per la sincronizzazione e per massimizzare l'accuratezza e la stabilità delle indicazioni.

4.2. Procedura di Selezione dell'Orologio

La procedura di selezione dell'orologio utilizza le variabili del peer THETA, DELTA, EPSILON e τ e viene chiamata quando queste variabili cambiano o quando lo stato di raggiungibilità cambia. Consiste di due algoritmi, l'algoritmo di intersezione (intersection algorithm) e l'algoritmo di clustering (clustering algorithm). L'algoritmo di intersezione costruisce un elenco di peer candidati idonei a diventare la fonte di sincronizzazione, calcola un intervallo di confidenza per ciascuno e scarta i falsi cronometristi utilizzando una tecnica adattata da Marzullo e Owicki [MAR85]. L'algoritmo di clustering ordina l'elenco dei candidati sopravvissuti in ordine di strato e distanza di sincronizzazione e scarta ripetutamente i valori anomali sulla base della dispersione di selezione fino a quando rimangono solo i sopravvissuti più accurati, precisi e stabili. Viene impostato un bit per ciascun sopravvissuto per indicare il risultato del processo di selezione. La variabile di sistema sys.peer è impostata come un puntatore al sopravvissuto più probabile, se ce n'è uno, o al valore NULL se non ce n'è.

4.2.1. Algoritmo di Intersezione

L'algoritmo di intersezione è adattato da DTS [DEC89] ed è progettato per produrre la singola intersezione più grande contenente solo veri cronometristi. L'algoritmo inizia inizializzando un valore f e contatori i e c a zero. Quindi, partendo dall'endpoint più basso dell'elenco di endpoint ordinato, per ogni voce [endpoint, tipo] il valore di tipo viene sottratto dal contatore i, che è il numero di intersezioni. Se tipo è zero, incrementa il valore di c, che è il numero di falsi cronometristi (vedere Appendice H). Se i >= m - f per una certa voce, l'endpoint di quella voce diventa l'endpoint inferiore dell'intersezione; altrimenti, f viene aumentato di uno e la procedura sopra viene ripetuta. Senza reimpostare f o c, una procedura simile viene utilizzata per trovare l'endpoint superiore, tranne che il valore di tipo viene aggiunto al contatore. Se dopo che entrambi gli endpoint sono stati determinati c <= f, la procedura continua avendo trovato m - f veri cronometristi; altrimenti, f viene aumentato di uno e l'intera procedura viene ripetuta.

4.2.2. Algoritmo di Clustering

Nell'algoritmo DTS originale, la procedura di selezione dell'orologio esce a questo punto con il tempo presunto corretto impostato a metà nell'intersezione calcolata [low, high]. Tuttavia, questo può portare a una perdita considerevole di accuratezza e stabilità, poiché le statistiche individuali del peer vengono perse. Pertanto, in NTP i candidati che sono sopravvissuti ai passaggi precedenti vengono elaborati ulteriormente. L'elenco dei candidati viene ricostruito con voci della forma [distanza, indice], dove la distanza è calcolata dallo strato del peer (scalato) e dalla distanza di sincronizzazione LAMBDA. Il fattore di scala fornisce un meccanismo per ponderare la combinazione di strato e distanza. Ordinariamente, lo strato dominerà, a meno che uno o più dei sopravvissuti non abbiano una distanza eccezionalmente alta. L'elenco viene quindi ordinato per distanza crescente.

L'algoritmo è progettato per favorire quei peer vicino alla testa dell'elenco dei candidati, che sono allo strato e alla distanza più bassi e presumibilmente possono fornire il tempo più accurato e stabile. Con una selezione appropriata del fattore di peso v (chiamato anche NTP.SELECT), le voci verranno rimosse dalla coda dell'elenco, a meno che alcuni valori anomali non siano in disaccordo significativo rispetto alle voci rimanenti, nel qual caso i valori anomali vengono scartati per primi. La condizione di terminazione è progettata per evitare cambiamenti inutili tra le fonti di sincronizzazione quando non statisticamente giustificato, mantenendo tuttavia un bias verso i peer a basso strato e bassa distanza.