1. Introduzione

Questo documento costituisce una specifica formale del Protocollo di Tempo di Rete (Network Time Protocol, NTP) Versione 3, che viene utilizzato per sincronizzare la gestione del tempo tra un insieme di server di tempo e client distribuiti. Definisce le architetture, gli algoritmi, le entità e i protocolli utilizzati da NTP ed è destinato principalmente agli implementatori. Un documento di accompagnamento [MIL91a] riassume i requisiti, i modelli analitici, l'analisi algoritmica e le prestazioni in condizioni Internet tipiche. Un altro documento [MIL91b] descrive la scala temporale NTP e la sua relazione con altre scale temporali standard attualmente in uso. NTP è stato descritto per la prima volta in RFC-958 [MIL85c], ma da allora si è evoluto in modi significativi, culminando nella più recente NTP Versione 2 descritta in RFC-1119 [MIL89]. È costruito sul Protocollo Internet (IP) [DAR81a] e sul Protocollo Datagramma Utente (UDP) [POS80], che forniscono un meccanismo di trasporto senza connessione; tuttavia, è facilmente adattabile ad altre suite di protocolli. NTP si è evoluto dal Protocollo di Tempo (Time Protocol) [POS83b] e dal messaggio di timestamp ICMP (ICMP Timestamp message) [DAR81b], ma è specificamente progettato per mantenere accuratezza e robustezza, anche quando utilizzato su percorsi Internet tipici che coinvolgono più gateway, ritardi altamente dispersivi e reti inaffidabili.

L'ambiente di servizio è costituito dal modello di implementazione (implementation model) e dal modello di servizio (service model) descritti nella Sezione 2. Il modello di implementazione si basa su un'architettura di sistema operativo multi-processo, sebbene possano essere utilizzate anche altre architetture. Il modello di servizio si basa su un design a tempo restituibile (returnable-time) che dipende solo dagli offset di orologio misurati (clock offsets), ma non richiede la consegna affidabile dei messaggi. La sottorete di sincronizzazione (synchronization subnet) utilizza una configurazione gerarchica master-slave auto-organizzata (hierarchical-master-slave configuration), con percorsi di sincronizzazione determinati da un albero di copertura a peso minimo (minimum-weight spanning tree). Sebbene possano esistere più master (server primari, primary servers), non vi è alcun requisito per un protocollo di elezione.

NTP stesso è descritto nella Sezione 3. Fornisce i meccanismi di protocollo per sincronizzare il tempo in linea di principio a precisioni dell'ordine dei nanosecondi preservando al contempo una data non ambigua fino al prossimo secolo. Il protocollo include disposizioni per specificare le caratteristiche e stimare l'errore dell'orologio locale e del server di tempo al quale può essere sincronizzato. Include anche disposizioni per il funzionamento con un certo numero di fonti di riferimento primarie gerarchicamente distribuite e reciprocamente sospette come orologi sincronizzati via radio.

La Sezione 4 descrive algoritmi utili per la rimozione di glitch (deglitching) e il livellamento di campioni di offset di orologio raccolti su base continua. Questi algoritmi si sono evoluti da quelli suggeriti in [MIL85a], sono stati raffinati come risultato di esperimenti descritti in [MIL85b] e si sono ulteriormente evoluti in condizioni operative tipiche negli ultimi tre anni. Inoltre, come risultato dell'esperienza nell'operare sottoreti multi-server che includono orologi radio in diversi siti negli Stati Uniti e con client negli Stati Uniti e in Europa, sono stati sviluppati algoritmi affidabili per selezionare buoni orologi da una popolazione che include possibilmente orologi difettosi [DEC89], [MIL91a] e sono descritti nella Sezione 4.

Le accuratezze ottenibili da NTP dipendono fortemente dalla precisione dell'hardware dell'orologio locale e dal controllo rigoroso delle latenze di dispositivo e processo. Devono essere incluse disposizioni per regolare il tempo e la frequenza dell'orologio logico software in risposta alle correzioni prodotte da NTP. La Sezione 5 descrive un design di orologio locale evoluto dall'implementazione Fuzzball descritta in [MIL83b] e [MIL88b]. Questo design include meccanismi di regolazione dell'offset (offset-slewing), compensazione della frequenza (frequency compensation) e rimozione di glitch capaci di accuratezze dell'ordine di un millisecondo, anche dopo periodi prolungati in cui la sincronizzazione con le fonti di riferimento primarie è stata persa.

I dettagli specifici dei formati di pacchetto NTP utilizzati con il Protocollo Internet (IP) e il Protocollo Datagramma Utente (UDP) sono presentati nell'Appendice A, mentre i dettagli di un Messaggio di Controllo NTP ausiliario suggerito (NTP Control Message), che può essere utilizzato quando non sono disponibili strutture di monitoraggio di rete complete, sono presentati nell'Appendice B. L'Appendice C contiene le specifiche e i dettagli di implementazione di un meccanismo di autenticazione opzionale (authentication mechanism) che può essere utilizzato per controllare l'accesso e prevenire modifiche non autorizzate dei dati, mentre l'Appendice D contiene un elenco delle differenze tra la Versione 3 di NTP e le versioni precedenti. L'Appendice E si espande su questioni relative alle scale temporali di precisione e alla datazione del calendario peculiari delle reti informatiche e di NTP. L'Appendice F descrive un algoritmo opzionale per migliorare l'accuratezza combinando gli offset di tempo di un certo numero di orologi. L'Appendice G presenta un modello matematico dettagliato e un'analisi degli algoritmi di orologio locale NTP. L'Appendice H analizza le fonti e la propagazione degli errori e presenta principi di correttezza (correctness principles) relativi al servizio di trasferimento del tempo. L'Appendice I illustra segmenti di codice in linguaggio C per il filtro dell'orologio, la selezione dell'orologio e gli algoritmi correlati descritti nella Sezione 4.

1.1. Tecnologia Correlata

Altri meccanismi sono stati specificati nella suite di protocolli Internet per registrare e trasmettere il tempo in cui si verifica un evento, inclusi il protocollo Daytime (Daytime protocol) [POS83a], il Protocollo di Tempo (Time Protocol) [POS83b], il messaggio di timestamp ICMP (ICMP Timestamp message) [DAR81b] e l'opzione di timestamp IP (IP Timestamp option) [SU81]. I risultati sperimentali sugli offset di orologio misurati e sui ritardi di andata e ritorno su Internet sono discussi in [MIL83a], [MIL85b], [COL88] e [MIL88a]. Altri algoritmi di sincronizzazione sono discussi in [LAM78], [GUS84], [HAL84], [LUN84], [LAM85], [MAR85], [MIL85a], [MIL85b], [MIL85c], [GUS85b], [SCH86], [TRI86], [RIC88], [MIL88a], [DEC89] e [MIL91a], mentre i protocolli basati su di essi sono descritti in [MIL81a], [MIL81b], [MIL83b], [GUS85a], [MIL85c], [TRI86], [MIL88a], [DEC89] e [MIL91a]. NTP utilizza tecniche evolute da essi e metodologie sia di sistemi lineari (linear-systems) che di accordo (agreement). I metodi lineari per la sincronizzazione delle reti telefoniche digitali sono riassunti in [LIN80], mentre i metodi di accordo per la sincronizzazione degli orologi sono riassunti in [LAM85].

Il Servizio di Tempo Digitale (Digital Time Service, DTS) [DEC89] ha molti degli stessi obiettivi di servizio di NTP. Il design DTS pone forte enfasi sulla gestione della configurazione e sui principi di correttezza quando operato in un ambiente LAN gestito o cluster LAN, mentre NTP pone forte enfasi sull'accuratezza e la stabilità del servizio operato in un ambiente internet globale non gestito. In DTS una sottorete di sincronizzazione è composta da impiegati (clerks), server (servers), corrieri (couriers) e fornitori di tempo (time providers). Rispetto alla nomenclatura NTP, un fornitore di tempo è una fonte di riferimento primaria, un corriere è un server secondario destinato a importare il tempo da uno o più server primari distanti per la ridistribuzione locale e un server è destinato a fornire tempo a molti nodi finali o impiegati. A differenza di NTP, DTS non necessita o utilizza informazioni di modo o strato (mode or stratum information) nella selezione dell'orologio e non include disposizioni per filtrare il rumore di temporizzazione, selezionare il più accurato da un insieme di orologi presunti corretti o compensare gli errori di frequenza inerenti.

Infatti, le ultime revisioni di NTP hanno adottato alcune caratteristiche di DTS al fine di supportare principi di correttezza. Queste includono meccanismi per limitare gli errori massimi inerenti alle procedure di trasferimento del tempo e l'uso di un meccanismo dimostrabilmente corretto (soggetto ad assunzioni dichiarate) per rifiutare peer inappropriati nelle procedure di selezione dell'orologio. Queste caratteristiche sono descritte nella Sezione 4 e nell'Appendice H di questo documento.

Il protocollo di routing Fuzzball (Fuzzball routing protocol) [MIL83b], a volte chiamato Hellospeak, incorpora la sincronizzazione temporale direttamente nel design del protocollo di routing. Uno o più processi si sincronizzano con una fonte di riferimento esterna, come un orologio radio o un demone NTP, e l'algoritmo di routing costruisce un albero di copertura a peso minimo radicato su questi processi. Gli offset di orologio vengono quindi distribuiti lungo gli archi dell'albero di copertura a tutti i processi nel sistema e i vari orologi di processo vengono corretti utilizzando la procedura descritta nella Sezione 5 di questo documento. Sebbene sia evidente che il design di Hellospeak ha fortemente influenzato il design di NTP, Hellospeak stesso non è un protocollo Internet ed è inadatto per l'uso al di fuori del suo ambiente di rete locale.

Il demone di tempo Unix 4.3bsd timed [GUS85a] utilizza un singolo demone di tempo master per misurare gli offset di un certo numero di host slave e inviare loro correzioni periodiche. In questo modello, il master è determinato utilizzando un algoritmo di elezione (election algorithm) [GUS85b] progettato per evitare situazioni in cui non viene eletto alcun master o viene eletto più di un master. Il processo di elezione richiede una capacità di broadcast, che non è una caratteristica onnipresente di Internet. Sebbene questo modello sia stato esteso per supportare configurazioni gerarchiche in cui uno slave su una rete funge da master sull'altra [TRI86], il modello richiede tabelle di configurazione artigianali per stabilire la gerarchia ed evitare loop. Oltre agli oneri gravosi ma presumibilmente poco frequenti del processo di elezione, il processo di misurazione/correzione dell'offset richiede il doppio dei messaggi di NTP per aggiornamento.

Uno schema con caratteristiche simili a NTP è descritto in [KOP87]. Questo schema è destinato a LAN multi-server dove ciascuno di un insieme di molti server di tempo determina il suo offset di tempo locale relativo a ciascuno degli altri server nell'insieme utilizzando messaggi con timestamp periodici, quindi determina la correzione dell'orologio locale utilizzando l'algoritmo di Media Tollerante ai Guasti (Fault-Tolerant Average, FTA) di [LUN84]. L'algoritmo FTA, che è utile dove fino a k server possono essere difettosi, ordina gli offset, scarta i k più alti e più bassi e calcola la media del resto. Lo schema, come descritto in [SCH86], è più adatto ad ambienti LAN che supportano il broadcast e comporterebbe un overhead inaccettabile in un ambiente internet. Inoltre, per le ragioni fornite nella Sezione 4 di questo articolo, le proprietà statistiche dell'algoritmo FTA probabilmente non sono ottimali in un ambiente internet con ritardi altamente dispersivi.

Molta ricerca è stata dedicata alla questione del mantenimento di un tempo accurato in una comunità dove alcuni orologi non possono essere considerati affidabili. Un vero cronometrista (truechimer) è un orologio che mantiene l'accuratezza cronometrica rispetto a uno standard precedentemente pubblicato (e affidabile), mentre un falso cronometrista (falseticker) è un orologio che non lo fa. Determinare se un particolare orologio è un vero cronometrista o un falso cronometrista è un interessante problema astratto che può essere affrontato utilizzando metodi di accordo riassunti in [LAM85] e [SRI87].

Una funzione di convergenza (convergence function) opera sugli offset tra gli orologi in un sistema per aumentare l'accuratezza riducendo o eliminando gli errori causati dai falsi cronometristi. Esistono due classi di funzioni di convergenza, quelle che coinvolgono algoritmi di convergenza interattiva (interactive-convergence algorithms) e quelle che coinvolgono algoritmi di coerenza interattiva (interactive-consistency algorithms). Gli algoritmi di convergenza interattiva utilizzano tecniche di clustering statistico come l'algoritmo di media tollerante ai guasti di [HAL84], l'algoritmo CNV di [LUN84], l'algoritmo del sottoinsieme di maggioranza di [MIL85a], l'algoritmo non-bizantino di [RIC88], l'algoritmo egocentrico di [SCH86], l'algoritmo di intersezione di [MAR85] e [DEC89] e gli algoritmi nella Sezione 4 di questo documento.

Gli algoritmi di coerenza interattiva sono progettati per rilevare processi di orologio difettosi che potrebbero indicare offset grossolanamente incoerenti in letture successive o a lettori diversi. Questi algoritmi utilizzano un protocollo di accordo che coinvolge turni successivi di letture, possibilmente ritrasmesse e possibilmente aumentate da firme digitali. Gli esempi includono l'algoritmo dei fuochi d'artificio di [HAL84] e l'algoritmo ottimale di [SRI87]. Tuttavia, questi algoritmi richiedono grandi numeri di messaggi, specialmente quando sono coinvolti grandi numeri di orologi, e sono progettati per rilevare guasti che sono stati raramente trovati nell'esperienza Internet. Per questi motivi non sono considerati ulteriormente in questo documento.

In pratica non è possibile determinare i veri cronometristi dai falsi cronometristi su una base diversa da quella statistica, specialmente con configurazioni gerarchiche e un Internet statisticamente rumoroso. Sebbene sia possibile limitare gli errori massimi nelle procedure di trasferimento del tempo, assumendo che siano adottate tolleranze sufficientemente generose per i componenti hardware, questo generalmente risulta in accuratezze e stabilità piuttosto scarse. L'approccio adottato nel design NTP e nei suoi predecessori coinvolge oscillatori accoppiati mutuamente (mutually coupled oscillators) e procedure di stima della massima verosimiglianza (maximum-likelihood estimation) e selezione dell'orologio, insieme a un design che consente di fare affermazioni dimostrabili sui limiti di errore relativi ad assunzioni dichiarate sulla correttezza delle fonti di riferimento primarie. Dal punto di vista analitico, il sistema di peer NTP distribuiti opera come un insieme di oscillatori a fase bloccata accoppiati (coupled phase-locked oscillators), con l'algoritmo di aggiornamento che funge da rivelatore di fase e l'orologio locale come oscillatore disciplinato (disciplined oscillator), ma con limiti di errore deterministici calcolati ad ogni passo nel processo di trasferimento del tempo.

La particolare scelta della procedura di misurazione e calcolo dell'offset descritta nella Sezione 3 è una variante del sistema a tempo restituibile utilizzato in alcune reti telefoniche digitali [LIN80]. Gli algoritmi di filtro e selezione dell'orologio sono progettati in modo che la sottorete di sincronizzazione dell'orologio si auto-organizzi in una configurazione gerarchica master-slave [MIT80]. Per quanto riguarda l'accuratezza e la stabilità del cronometraggio, la somiglianza di NTP ai sistemi telefonici digitali non è accidentale, poiché sistemi come questo sono stati studiati estensivamente [LIN80], [BRA80]. Ciò che rende unico il modello NTP sono i meccanismi di configurazione adattiva, polling, filtraggio, selezione e correttezza che adattano le dinamiche del sistema per adattarsi all'ambiente Internet onnipresente.