Sincronização de relógio em uma rede com atrasos assimétricos

38

Suponha que um computador tenha um relógio preciso que não seja inicializado. Ou seja, a hora no relógio do computador é em tempo real mais um deslocamento constante. O computador tem uma conexão de rede e nós queremos usar essa conexão para determinar o deslocamento constante B .

O método simples é que o computador envie uma consulta para um servidor de horário, anotando a hora local B+C1 . O servidor de horário recebe a consulta no horário T e envia uma resposta contendo T volta ao cliente, que a recebe no horário B+C2 . Então B+C1TB+C2 , ou seja, TC2BTC1 .

Se o tempo de transmissão da rede e o tempo de processamento do servidor forem simétricos, então B=TC1+C22 . Até onde eu sei, oNTP, o protocolo de sincronização de tempo usado em estado selvagem, opera com essa suposição.

Como a precisão pode ser melhorada se os atrasos não são simétricos? Existe uma maneira de medir essa assimetria em uma infraestrutura típica da Internet?

Gilles 'SO- parar de ser mau'
fonte
2
Há um relacionado patente mas quem quer ler os ...
Raphael
@ Rafael Obrigado. Link mais amigável do Google para a patente americana 7602873 , link oficial do USPTO .
Gilles 'SO- stop be evil' em
Primeiras reflexões: Provavelmente é impossível com 2 entidades. Usando (n2) pares de n entidades, é possível uma melhor sincronização. Em seguida, os relógios podem ser usados ​​para medir os tempos de uma viagem.
rgrig
você pode esclarecer a aplicação / contexto ou isso é principalmente uma questão teórica?
vzn

Respostas:

10

Incapacidade de medir assimetria

Não, você não pode medir a assimetria. Considere estes dois diagramas de comunicação, o primeiro com um deslocamento negativo do relógio e atrasos iguais e o segundo sem deslocamento do relógio e atrasos totalmente assimétricos (mas o mesmo tempo de ida e volta).

diagrama de comunicação

O importante a ser observado é que, da perspectiva do PC e do servidor, as duas interações são exatamente idênticas. Eles recebem mensagens ao mesmo tempo. Eles enviam mensagens ao mesmo tempo.

Você pode criar mais casos 'agarrando' a linha do tempo do PC e deslizando-a, mantendo a mensagem de enviar / receber pontos fixos em relação às respectivas linhas do tempo. As assimetrias causadas são exatamente negadas pelo deslocamento do relógio. De fato, você pode até fazer as mensagens retrocederem no tempo de uma maneira (desde que o tempo de ida e volta seja o mesmo) e o servidor / cliente AINDA não saiba!

Portanto, é impossível medir as assimetrias de latência. Na pior das hipóteses, onde você não tem informações além das latências unidirecionais positivas e somadas ao tempo de ida e volta, a precisão da sincronização do relógio é limitada ao tempo de ida e volta.

A infraestrutura intermediária pode ajudar?

Se a infraestrutura intermediária pode ou não ajudar, dependerá fortemente do seu modelo teórico da situação.

Se a assimetria for constante e a infraestrutura intermediária for os roteadores no caminho de comunicação entre você e o servidor, então não. Mesmo que cada roteador sincronizasse seu relógio com o roteador adjacente, os erros seriam compostos da mesma maneira como se você tivesse sincronizado com o servidor por meio da comunicação entre os roteadores.

No mundo real, você pode contar com atrasos que são um tanto simétricos por motivos arquitetônicos, sincronizações repetidas para reduzir a assimetria devido a atrasos de enfileiramento (etc) e vários caminhos de comunicação para reduzir outros tipos de assimetria.

Se você colocar as suposições do seu modelo em algum lugar (porque é interessante explorar o espaço do modelo, é claro), espero que o resultado também deva estar em algum lugar no meio.

Craig Gidney
fonte
Esta deve ser uma resposta para sua pergunta . Aqui, estou perguntando sobre uma configuração mais concreta, na qual podemos obter ajuda da infraestrutura subjacente.
Gilles 'SO- stop being evil'
Eu adicionei mais conteúdo para você.
Craig Gidney
isso me parece errado e pode ser observado ao observar que, embora o tempo de envio e recebimento do PC seja o mesmo (os eventos da linha do tempo superior coincidem nos dois casos), o tempo do servidor é diferente (linha inferior nos dois casos) & portanto, a fórmula calculada pelo cliente NTP é diferente nos dois casos. isso pode ser entendido melhor rotulando os valores NTP para em cada caso (onde são valores registrados no tempo do servidor e enviados de volta ao cliente). como na minha resposta, o protocolo NTP tempo pode realmente medir e ajustar parat 2 , t 3 ( t 1 - t 0 ) ( t 3 - t 2 )t1,t2,t3,t4t2,t3(t1t0)(t3t2)
vzn
@vzn Os tempos do servidor em relação às mensagens são os mesmos nos dois exemplos. A linha do tempo do servidor que se move para a esquerda representa o desvio do relógio inicial sendo diferente. Os efeitos do desvio inicial do relógio e da assimetria da latência são equivalentes, portanto, ajustá-los em direções opostas permite que o comportamento resultante seja equivalente.
Craig Gidney
Em um estudo mais aprofundado, o cliente / servidor pode saber quando seus relógios estão fora de sincronia pelo menos fora do tempo de ida e volta. mais informações no polycos et al ref Cito abaixo onde eles medem diferentes "unidirecionais latências" maiores que a incerteza NTP (o que parece ser inferior ao tempo de ida e volta para NTP Servidores- ie ~ 10ms)
vzn
2

Considere-se uma rede de servidores de tempo conhecidos para ser síncrono, , e uma máquina do cliente .Pθ={A,B,C}P

Seja o horário de vôo unidirecional da máquina para a máquina , com a possibilidade de . X Y T X YT Y XTXYXYTXYTYX

Letser a medida da assimetria entre a máquina e .X YΔXY=|TXYTYX|XY

Agora, considere que a assimetria entre duas máquinas síncronas pode ser medida fazendo com que as máquinas síncronas concordem em enviar uma mensagem unidirecional uma para a outra ao mesmo tempo. A diferença nos horários de chegada é entre essas máquinas, ou seja:Δ

ΔAB=|TABTBA|

ΔBC=|TBCTCB|

ΔCA=|TCATAC|

pode ser medido.

Agora considere o tempo de voo dos circuitos:

C A BPABP , denotado por ,CAB

PBAP , denotado por .CBA

CAB=TPA+TAB+TBP

CBA=TPB+TBA+TAP

Considere a máquina cliente para iniciar esses dois circuitos simultaneamente e mede a diferença nos horários de chegada, :Px

x=CABCBA=ΔPA+ΔAB+ΔBP

Ambos e são conhecidos pelas medições mencionadas anteriormente, movendo as incógnitas para o lado esquerdo:xΔAB

xΔAB=ΔPA+ΔBP

Da mesma forma, para e , pode ser mostrado que:{CAC,CCA}{CBC,CCB}

yΔBC=ΔPB+ΔCP

zΔCA=ΔPC+ΔAP

Inspecionando cuidadosamente, observamos que . Os lados esquerdo contêm valores conhecidos das medições, o lado direito contém 3 incógnitas em 3 equações.ΔXYΔYX

Resolvendo simultaneamente,

ΔAP=r+st2

ΔBP=rs+t2

ΔCP=tr+s2

Onde,

r=xΔAB

s=yΔBC

t=zΔCA

Bingo
fonte
Como isso contorna o problema que minha resposta e outras pessoas têm?
Raphael
Bem, por exemplo, estou usando três saques de tempo, não um. E requer que algo como 12 mensagens sejam enviadas - 6 para encontrar a assimetria entre os servidores de horário e 6 para encontrar a assimetria entre o cliente e os servidores. Não é um espaço de solução unidimensional porque a composição está entre 3 servidores e não um. E não assume que o tempo possa retroceder.
Bingo
Ele depende muito de três servidores de horário perfeitamente sincronizados, cuja sincronização é deixada como um exercício para o leitor. ^^
Bingo
@ Rafael Acho que entendi o seu comentário agora. A mudança de tempo não funciona porque é mais restrita. por exemplo. Mudança de tempo wrt não afeta apenas o tempo entre e mas também os circuitos , diferenças são medidas e fatoradas no cálculo. Talvez eu ainda esteja errado? Não tenho certeza: PAPAPPACP,PABP,PBAP,PCAP
Bingo
0

Se você controlar apenas os pontos finais. Você não pode. Veja a resposta de Craig.

Mesmo se você adicionar mais máquinas e um conjunto mais complexo de computadores, como na resposta do Bingo, você pode reduzir a apenas máquinas que fazem com que as sincronizadas tenham acesso instantâneo às outras (atraso = 0).TXY

Observe que se você faz , obtém .TAB=TBC=TCA=0ΔAP=ΔBP=ΔCP=0

Então, oque há de errado? x=CABCBA=ΔPA+ΔAB+ΔBP

ΔPA=|TPATAP|, nãoΔPA=TPATAP

E se você usar o segundo, não poderá usar a suposição (e se você não usar isso, suas equações finais se cancelarão).ΔXYΔYX

Então o que você pode fazer? Envie um relógio realmente bom pelo correio. ;)

Ou, se você tiver controle sobre todos os nós entre eles, poderá verificar o tempo para processar cada pacote e calcular o atraso entre cada par consecutivo, que deve ser simétrico, se usarem o mesmo meio físico nos dois sentidos.

Você pode precisar dar conta da relatividade geral e lembrar que a simultaneidade não existe.

Luiz Afonso
fonte
"Você pode precisar prestar contas da relatividade geral" Não, não preciso. Estou perfeitamente bem com uma solução que só funciona se todos os relógios envolvidos estiverem em um quadro fixo. Existe relatividade em um sistema distribuído, mas vem da latência da rede, não da física. Sua matemática é completamente diferente.
Gilles 'SO- stop be evil'
-1

Na verdade, o NTP usa 4 medições de tempo para calcular o "deslocamento". eles são os "pontos no tempo" na ida e volta do pacote do cliente para o servidor e para o cliente, mas podem ser considerados como compensações de tempo. supõe-se que o deslocamento de tempo possa ser desativado entre cliente e servidor, mas que ambos possam contar com precisão os deslocamentos de tempo decorrido local.t0,t1,t2,t3

o cliente após receber o pacote de retorno possui todos os 4 valores e calcula o deslocamento real. uma vez que o deslocamento relativo é calculado entre o cliente e o servidor, o deslocamento de "tempo absoluto" pode ser sincronizado, ou seja, o cliente pode estimar com precisão o deslocamento exato dos servidores medido pelo deslocamento de tempo local, ou seja, o "delta".

t0 = tempo [deslocamento] enviado no cliente = tempo [deslocamento] recd no servidor = tempo [deslocamento] enviado no servidor = tempo [deslocamento] recd no cliente
t1
t2
t3

a fórmula real éθ=(t1t0)+(t2t3)2

observe que esta fórmula pode lidar com o caso em que o tempo do cliente para o servidor não é o mesmo que do servidor para o cliente (mais curto ou mais longo).t1t0t3t2

nas redes, o tempo de atraso é devido a dois fatores principais, principalmente a latência e a largura de banda.

  • latência é o breve atraso nos roteadores no envio de novos [pequenos] pacotes e é aproximadamente uma constante diferente em cada roteador. pode ser medido com o utilitário traceroute .
  • largura de banda é a taxa na qual grandes quantidades de dados podem ser enviadas, por exemplo, "tempo de upload versus download" e também podem ser medidas por sites remotos de "medição de largura de banda".

em muitas conexões modernas de Internet doméstica / comercial, a taxa de upload é muito menor que a taxa de download e isso provavelmente afetaria a vs enquanto a latência pode ser pequena ou um pouco semelhante entre cliente para servidor e servidor para servidor. cliente.t 3 - t 2t1t0t3t2

um algoritmo básico para melhorar a precisão do cálculo do deslocamento usado no NTP (e pode corrigir algum grau de latência aleatória da rede) é repetir o processo várias vezes e usar o "ápice do diagrama de dispersão de cunha". isso pode ser visto no "algoritmo do filtro de relógio" no slide 10 deste PPT no NTP por David Mills. veja também algoritmo de filtro de relógio de Mills. (observe que ainda pode ser empregado entre um único servidor e cliente, embora o código geral seja escrito para permitir vários servidores.) isso faz parte dos "algoritmos de mitigação" descritos na arquitetura e algoritmos do NTP .

vzn
fonte
11
A questão é especificamente sobre o caso em que a latência não é simétrica. Tomar várias medidas não informa nada sobre o componente constante na assimetria.
Gilles 'SO- stop being evil' em
a questão não contém realmente a palavra "latência". se você quiser esboçar o caso que você realmente tem em mente na forma matemática, em vez de palavras, especialmente as fórmulas NTP reais, certamente ajudaria. as fórmulas e algoritmos podem realmente medir / manipular / cobrir vários casos de "latência" e "assimetria".
#
C1 e são os valores de latência (eu os chamei de "atraso", as duas palavras são sinônimos neste contexto). C2
Gilles 'SO- stop be evil' em
C1 e são influenciados pela latência, mas não são realmente iguais a ela. em certo sentido, o scattergram realmente parcelas latência ....C2
vzn
note (talvez não seja totalmente óbvio na conta acima) os valores de servidor são enviados no pacote de retorno do servidor para o cliente. t1,t2
#
-3

Se pudéssemos enviar pacotes de volta no tempo

insira a descrição da imagem aqui

B=Tf+TbTf2C1+C22

Suposições:

(B+C2)Tb=Tf(B+C1)

Tf(B+C2)=(B+C1)Tb

Pratik Deoghare
fonte
11
Essa solução inteligente é descartada pelo pressuposto de uma "infraestrutura típica da Internet".
Gilles 'SO- stop being evil'
11
@ Gilles eu sei. : D
Pratik Deoghare 21/03
-4

Aqui está uma ideia que me parece absolutamente convincente e, portanto, pode estar absolutamente errada de uma maneira idiota.

Considere o seguinte cenário. Temos dois nós e com relógios e , respectivamente. Por uma questão de simplicidade, vamos supor que os relógios funcionem com a mesma velocidade; denotamos sua diferença por que é constante para nossos propósitos. Suponhamos, além disso, que os atrasos de transmissão e sejam constantes¹.N1N2C1C2δ=C1C2d12d21

Faça com que envie uma mensagem com carimbo de data e hora com para e deixe a hora atual em ao recebê-la (faça o mesmo na outra direção). Além disso, meça o tempo de ida e volta (em qualquer um dos nós) enviando uma mensagem para frente e para trás. Agora configure este sistema de equação:T m 1 N 2 T r 2 C 2 DN1T1mN2T2rC2D

T2rT1m=d12+δT1rT2m=d21δD=d12+d21

Como esse sistema consiste em três equações, possui três incógnitas e sabemos que existe uma solução, ela pode ser resolvida. Obviamente, os nós precisam trocar suas medidas para que ambos possam calcular o mesmo valor para (se necessário).δ

1] Eu acho que as suposições são naturais e necessárias. Eles podem ser justificadas com a esperança de que as respectivas quantidades não mudam muito muito para a duração da nossa tentativa de sincronização.

Rafael
fonte
(d12+δ)+(d21δ)(d12+d21)=0
@ Gilles muito ruim. Provavelmente deveríamos deixar uma instância da falácia para todos verem?
Raphael
11
Eu posso restaurar a resposta errada que escrevi. Pode ser útil devido aos comentários feitos por Gilles.
Ran G.