Processo de sincronização
Visão geral do algoritmo
O Network Time Protocol (NTP) emprega um algoritmo de vários estágios para sincronizar relógios de clientes com servidores remotos, mitigando erros de atrasos de rede, desvios de relógio e fontes defeituosas. O processo principal começa com a coleta de dados de vários pares, seguida pela filtragem para selecionar as amostras mais precisas, seleção para identificar servidores confiáveis (truechimers) enquanto descarta os não confiáveis (falsetickers), agrupamento para refinar o conjunto de candidatos, combinação para calcular um deslocamento de consenso e, finalmente, disciplinar o relógio local por meio de ajustes de fase e frequência. Este design baseia-se em princípios estatísticos e de tolerância a falhas para alcançar uma precisão inferior a um milissegundo em condições favoráveis, assumindo que a maioria dos servidores fornece a hora correta. Esses algoritmos são especificados para NTP versão 4 (NTPv4).[17]
O algoritmo de filtro de clock opera por peer, processando amostras de ida e volta para isolar a medição de menor atraso, o que minimiza os efeitos de atraso assimétricos. Para cada associação, ele mantém um registro de deslocamento de oito estágios de tuplas de medição (deslocamento, atraso, dispersão, carimbo de data e hora), mudando em novas amostras e descartando aquelas obsoletas com mais de três intervalos de pesquisa. As amostras são classificadas por atraso crescente, e a dispersão dos pares (ε) é calculada como a soma ponderada das dispersões dos estágios: ε = Σ (ε_i / (i+1)^2) para i de 0 a 7, onde ε_i é a dispersão no estágio i; esta ponderação quadrática favorece amostras de baixo atraso. A distância de sincronização raiz (λ = δ/2 + ε, onde δ é o atraso de ida e volta) serve então como uma métrica de qualidade, aumentando ao longo do tempo na taxa φ (15 μs/s) para penalizar pares inativos. O jitter (ψ) é estimado como a raiz quadrada média (RMS) das diferenças entre o melhor deslocamento e outros deslocamentos no registro, limitado pela precisão do sistema. Essa filtragem garante que apenas amostras de alta qualidade se propaguem para estágios superiores.[18]
Na fase de seleção, o algoritmo de interseção – adaptado do algoritmo de Marzullo para consenso de intervalo – avalia todos os pares candidatos para detectar falsetickers usando princípios de falha bizantina. Para cada ponto, ele constrói um intervalo de correção [θ - λ, θ + λ], onde θ é o deslocamento medido e λ a distância raiz, representando os possíveis valores de tempo verdadeiro. O algoritmo procura a maior interseção contígua contendo pontos médios desses intervalos, exigindo acordo de pelo menos uma maioria simples (ou um mínimo configurável de 1 sobrevivente). Os pares cujos intervalos ficam fora desta interseção são descartados como falsetickers, assumindo não mais que (N-1)/2 fontes defeituosas em uma população de N (até quase 50% se N for ímpar). Esta etapa identifica de forma robusta os truechimers, mesmo na presença de servidores com falhas significativas.[19]
O algoritmo de agrupamento subsequente refina a lista de sobreviventes descartando iterativamente o outlier que mais contribui para o jitter de seleção (ψ_s) até que no máximo três (NMIN) associações permaneçam ou nenhuma redução adicional em ψ_s seja possível. Os sobreviventes são classificados por uma pontuação que combina estrato (multiplicado por MAXDIST) e distância raiz (λ), selecionando o par do sistema como a entrada de pontuação mais baixa, evitando trocas desnecessárias de pares se o novo candidato corresponder ao estrato atual. O algoritmo de combinação então calcula o deslocamento final do sistema (Θ) como uma média ponderada dos deslocamentos de sobreviventes: Θ = Σ (w_i * θ_i) / Σ w_i, onde os pesos w_i = 1 / λ_i enfatizam pares de baixa distância; o jitter do sistema (Ψ) segue como √(ψ_s^2 + ψ_p^2), com ψ_p o jitter do par RMS. Este mecanismo de consenso fornece uma estimativa robusta e resiliente a erros individuais.[20][21]
Finalmente, o algoritmo de disciplina de relógio usa um loop de feedback para ajustar o relógio local, tratando-o como um loop híbrido de bloqueio de fase (PLL) e um loop de bloqueio de frequência (FLL). O deslocamento combinado (Θ) aciona atualizações de fase, enquanto a frequência é sintonizada por meio de um oscilador de frequência variável (VFO) para minimizar o desvio. Os ajustes ocorrem via “slew” (mudança gradual) para deslocamentos abaixo de 128 ms ou “step” (correção instantânea) para deslocamentos maiores, com uma máquina de estado lidando com erros transitórios como picos. O filtro de loop calcula o deslocamento de frequência (α) e define o intervalo de pesquisa de forma adaptativa entre 64 s (2 ^ 6 s) e 131.072 s (≈36 horas, 2 ^ 17 s) com base no jitter e na estabilidade, garantindo sincronização de longo prazo dentro de 1-50 ms pela Internet.
Seleção de pares e filtragem de relógio
No Network Time Protocol (NTP), o algoritmo de filtro de relógio opera por ponto para processar amostras de tempo recebidas e selecionar a mais confiável para sincronização. Para cada associação de pares, o algoritmo mantém um registrador de deslocamento de oito estágios que armazena tuplas consistindo no deslocamento do relógio θ (a diferença de tempo estimada entre os relógios local e de pares), atraso de ida e volta δ, dispersão ε (uma medida do limite máximo de erro) e carimbo de data e hora de chegada t. Após o recebimento de um pacote NTP válido, o registrador desloca as tuplas existentes para a esquerda, descarta a entrada mais antiga e insere uma nova tupla derivada dos carimbos de data e hora do pacote, com a dispersão inicial calculada a partir da dispersão da raiz do par e do jitter de processamento da amostra.
O processo de filtragem prioriza amostras com o menor atraso de ida e volta para minimizar os efeitos de assimetria da rede, classificando os estágios de registro aumentando δ e selecionando a amostra do primeiro estágio como candidata. Os valores de dispersão no registro acumulam limites de erro, aumentando a uma taxa de PHI ≈ 15 × 10^{-6} segundos por segundo devido ao desvio do relógio local, e o algoritmo calcula uma dispersão geral de pares como uma soma ponderada ε = Σ (ε_i / (i+1)^2) para i=0 a 7, onde os estágios são classificados por atraso; esta ponderação quadrática favorece amostras recentes e de baixo atraso. O jitter ψ, representando a variação nos deslocamentos, é calculado como a raiz quadrada média (RMS) das diferenças entre o melhor deslocamento e os demais no registro, limitado pela precisão do sistema para evitar amplificação de erros. Essa seleção de baixo atraso ajuda a mitigar atrasos de caminho e garante que apenas amostras de alta qualidade contribuam para as variáveis de estado do par (deslocamento, atraso, jitter e dispersão), que são atualizadas apenas se o atraso da nova amostra for menor que o atual ou se o registro tiver menos de oito entradas.[23]
A seleção de pares ocorre no nível do sistema por meio de um processo de vários estágios que avalia todos os pares candidatos para identificar e combinar as melhores fontes de tempo, descartando as não confiáveis. O algoritmo de seleção aplica primeiro um mecanismo de detecção de falsetickers, inspirado nos princípios do acordo bizantino, para selecionar pares imprecisos (falsetickers). Para cada peer, ele constrói um intervalo de correção [θ - ρ, θ + ρ], onde ρ é a distância raiz (distância de sincronização do peer até sua referência primária, incorporando atraso, dispersão e jitter). Esses intervalos são cruzados por todos os pares; falsetickers são aqueles cujos intervalos não se sobrepõem ao maior clique (interseção majoritária) contendo mais da metade dos pares, garantindo resiliência contra até (N-1)/2 fontes defeituosas. Os sobreviventes deste estágio, denominados truechimers, representam o conjunto concordante de relógios precisos.[24]
Métodos de ajuste de relógio
O Network Time Protocol (NTP) emprega um algoritmo de disciplina de relógio para ajustar o relógio do sistema local com base em compensações de sincronização derivadas de medições de pares. Este algoritmo, um híbrido de mecanismos de loop bloqueado por fase (PLL) e loop bloqueado por frequência (FLL), estima e corrige continuamente os erros de fase (deslocamento de tempo) e de frequência (taxa de desvio) para manter a precisão da sincronização. O processo é executado em intervalos fixos, normalmente a cada segundo, e adapta o intervalo de pesquisa (τ) dinamicamente entre 64 segundos (2 ^ 6 s) e 131.072 segundos (≈36 horas, 2 ^ 17 s) para equilibrar a precisão e a carga da rede.
Os ajustes são aplicados em um dos dois métodos principais: passo a passo ou rotação, selecionados com base na magnitude do deslocamento calculado (θ). Para compensações que excedem o limite de passo (padrão 0,128 segundos), o relógio é acelerado imediatamente usando chamadas de sistema como settimeofday(), que ajusta o relógio diretamente para a hora corrigida. Este método redefine todas as associações de pares e invalida dados anteriores, pois grandes descontinuidades podem indicar erros significativos ou inicialização.[1] Se o deslocamento ultrapassar o limite de pânico (1000 segundos), o daemon normalmente é encerrado para evitar operação incorreta.[1] A revisão é rara na operação em estado estacionário, mas essencial para a sincronização inicial ou recuperação de grandes interrupções.[29]
Para deslocamentos menores abaixo do limite do passo, o clock é acelerado gradualmente usando chamadas como adjtime(), que ajusta incrementalmente a frequência do clock para amortizar o erro de fase ao longo do tempo sem introduzir descontinuidades. Isto preserva a monotonicidade na escala de tempo, evitando problemas em aplicações sensíveis a saltos de tempo. O processo de variação combina correções de fase e frequência: o deslocamento de fase θ é corrigido por meio de um termo proporcional, enquanto a frequência φ é atualizada como uma média ponderada incorporando medições recentes, como φ_k = φ_{k-1} + w (φ_k - φ_{k-1}) onde w ≈ 0,25.[1][29] O design híbrido PLL/FLL usa o PLL para intervalos de pesquisa curtos (τ ≤ 1024 segundos) para priorizar o bloqueio de fase e muda para FLL para intervalos mais longos para enfatizar a estabilidade de frequência.
O deslocamento θ em si é calculado a partir de carimbos de data e hora do pacote NTP como θ = ½[(T2 - T1) + (T3 - T4)], onde T1 a T4 representam os tempos de envio do cliente, recebimento do servidor, envio do servidor e recebimento do cliente, respectivamente; isso é refinado pelo filtro de relógio e algoritmos de seleção para selecionar as melhores medições de pares antes da aplicação.[1] O desvio de frequência é limitado por um parâmetro de tolerância (PHI = 15 ppm), e os ajustes incorporam estimativas de jitter (ψ) e dispersão (ε) para garantir a estabilidade, com a distância de sincronização raiz λ = (δ/2) + ε + PHI × (t - t0) orientando a seleção de pares. Em modos não lineares, como durante a estimativa inicial de frequência (até 15 minutos) ou rajadas de alto jitter, o algoritmo prioriza temporariamente as correções de frequência para evitar oscilações.[1] No geral, esses métodos atingem erros de sincronização normalmente inferiores a 1 milissegundo em LANs e algumas dezenas de milissegundos em WANs em condições normais.[29]