Medindo a latência de rede unidirecional

20

Este é um quebra-cabeça sobre como medir a latência da rede que eu criei. Acredito que a solução é que é impossível, mas os amigos discordam. Estou procurando explicações convincentes de qualquer maneira. (Embora seja apresentado como um quebra-cabeça, acho que se encaixa neste site devido à sua aplicabilidade ao design e à experiência de protocolos de comunicação, como em jogos online, sem mencionar o NTP.)

Suponha que dois robôs estejam em duas salas, conectadas por uma rede com latências unidirecionais diferentes, conforme mostrado no gráfico abaixo. Quando o robô A envia uma mensagem ao robô B, leva 3 segundos para chegar, mas quando o robô B envia uma mensagem ao robô A, leva 1 segundo para chegar. As latências nunca variam.

Os robôs são idênticos e não possuem um relógio compartilhado, embora possam medir a passagem do tempo (por exemplo, eles têm cronômetros). Eles não sabem qual deles é o robô A (cujas mensagens estão atrasadas em 3s) e qual é o robô B (cujas mensagens estão atrasadas em 1s).

Um protocolo para descobrir o tempo de ida e volta é:

whenReceive(TICK).then(send TOCK)

// Wait for other other robot to wake up
send READY
await READY
send READY

// Measure RTT
t0 = startStopWatch()
send TICK
await TOCK
t1 = stopStopWatch()
rtt = t1 - t0  //ends up equalling 4 seconds

Existe um protocolo para determinar os atrasos nas viagens de ida? Os robôs podem descobrir qual deles tem o atraso de envio de mensagens mais longo?

Dois robôs uma rede assimétrica

Craig Gidney
fonte
5
Consulte Sincronização de relógio em uma rede com atrasos assimétricos (que solicita algo factível com a infraestrutura típica da Internet). Acho que pelo que vimos ao discutir respostas erradas para essa pergunta, a resposta é que é impossível.
Gilles 'SO- stop being evil'
Devemos mesclar as perguntas ou elas são diferentes o suficiente no alvo para se manterem separadas?
Craig Gidney
Não, são perguntas diferentes. Sua pergunta estabelece que é impossível em uma configuração de duas máquinas apenas com passagem de mensagens. Espero soluções com base em, por exemplo, informações de latência disponíveis para alguns links intermediários na rota entre o cliente e o servidor e ter alguma maneira de propagar essas informações para o cliente.
Gilles 'SO- stop being evil'
3
Se houvesse uma maneira de fazer isso, a teoria da relatividade de Einstein não funcionaria, uma vez que depende do fato de que dois observadores separados por espaço e com latências unidirecionais desconhecidas não podem concordar com o tempo adequado.
Peter Shor
O NTP de fato permite / implementa a medição desse atraso diferencial com base em máquinas que enviam seu tempo e não apenas rastreando o tempo de envio / recebimento de suas próprias mensagens, mas também os outros servidores através do conteúdo de mensagens, veja a resposta na pergunta de gilles
vzn

Respostas:

14

O diagrama a seguir, de uma postagem de blog que escrevi , é uma prova visual de que é impossível:

Deslizando a inclinação do relógio exatamente compensada pela assimetria da latência

Observe como os tempos de chegada de pacotes em cada lado permanecem os mesmos, mesmo quando as latências unidirecionais mudam (e até se tornam negativas!). O primeiro pacote sempre alcança o servidor às 1,5s no relógio do servidor, o segundo sempre alcança o cliente às 2s no relógio do cliente, etc. O conteúdo do pacote e os horários locais de chegada são as únicas coisas em que um protocolo pode se basear, mas o O conteúdo e os tempos de chegada podem ser mantidos constantes, pois a assimetria varia, variando também a inclinação do relógio inicial.

Basicamente, a assimetria nas latências unidirecionais parece exatamente como a inclinação do relógio. Como o problema indica que não começamos a conhecer a inclinação do relógio inicial ou a assimetria de latência unidirecional, e variar um parece variar o outro para que seus efeitos sejam indistinguíveis, não podemos separar suas contribuições para resolver o problema. assimetria de latência unidirecional. É impossível.

Mais formalmente, você não pode resolver comprimentos de arestas quando determinados apenas os comprimentos dos ciclos. A base do ciclo possui graus de liberdade, correspondendo a n - 1 inclinação desconhecida do relógio em relação a um dos participantes. Você sempre pode ocultar as latências unidirecionais, mesmo quando há muitos participantes:n-1n-1

Doença do mar

Se você não é tão visualmente inclinado, tenho outro argumento intuitivo. Imagine um portal do tempo para cem anos no futuro. Ao conversar com alguém do outro lado, você percebe que a conversa é totalmente normal, apesar da assimetria de cem anos em atrasos unidirecionais. Qualquer efeito observável teria sido óbvio nessa escala!

Craig Gidney
fonte
Qual a sua opinião sobre isso? software.internet2.edu/owamp
CMCDragonkai
@CMCDragonkai Lembre-se de que a declaração do quebra-cabeça é mais restritiva que a realidade. Na prática, você tem opções como medir o comprimento das linhas de fibra óptica, registrar em pontos intermediários, usar o conhecimento da topologia da rede, carregar lentamente um relógio de um lugar para o outro etc. Por exemplo, os satélites GPS se movem em órbitas conhecidas e você pode usar isso para remover graus de liberdade ao resolver. Portanto, na superfície, não vejo nenhum problema com uma ferramenta de ping unidirecional, desde que ela ou os relógios nos quais ela esteja utilizando estejam explorando algumas dessas informações doces e terciárias.
Craig Gidney
Ah, nesse caso, você poderia atualizar sua resposta com possíveis soluções alternativas?
precisa saber é o seguinte
@CMCDragonkai Tê-los nos comentários é suficiente. Eles estão além do escopo do quebra-cabeça.
Craig Gidney
A latência unidirecional é importante, por exemplo, para redes de jogos. Além disso, todo mundo diz que é impossível, mas eu posso resolver facilmente o quebra-cabeça no papel - depois que você sincroniza os relógios, tudo o que você faz é medir o atraso de A para B enviando o tempo de A para B, com o atraso A-> B igual a B's time - A's sent time, e B-> Um ser igual alatency - A->B delay
Llamageddon
1

Eu acho que é impossível descobrir a latência unidirecional apenas comparando cronômetros.

UMABCUMA1
BCB1=1
UMACUMA2=9
BCB2=5
UMAB

Talvez se você fizer uma pergunta de recompensa, alguém a decifre. Até então, parabéns.

rath
fonte
0

Eu encontrei uma maneira de AMBOS descobrir qual nó é quem (ou seja, quem tem o maior atraso na mensagem) E estimar o atraso da viagem de ida. Enquanto as outras respostas estão corretas, elas estão apenas considerando a medição direta do relógio, que obviamente não pode funcionar. No entanto, como estou provando aqui, isso é apenas parte da história, pois aqui está o meu algoritmo de trabalho para o acima:

Suponha como na vida real:

  • Links de largura de banda finita b

  • Cada nó possui um endereço exclusivo (por exemplo, A e B)

  • Tamanho do pacote p muito menor que o produto de latência de largura de banda *

  • Os nós A e B podem preencher o canal

  • Nós têm uma função random ()

Cada nó preenche o canal com seus próprios pacotes (marcados A ou B, respectivamente) OU encaminha os pacotes recebidos de outros nós da seguinte maneira:

Always fill the channel with my own packets except:
if I receive a packet from another node then
   Randomly choose to 
          either forward that packet from the other node
          or discard that packet and forward my own packet

Explicação intuitiva Como o produto de latência de largura de banda * de A é maior (porque a latência é maior), A conseguirá receber mais pacotes que B, portanto, cada Nó poderá saber quem eles são no diagrama .

Além disso, com tempo de convergência suficiente para executar acima do algoritmo, a proporção de pacotes de A para B indicará a taxa real de atraso do RTT de A para B e, portanto, o OTT desejado .

TRATAMENTO DO RESULTADO DA SIMULAÇÃO Aqui está uma simulação que comprova o exposto acima e mostra como A convergindo com sucesso para um atraso de 3 segundos e B convergindo para um atraso de 1 segundo:

Primeiros segundos de simulação

Segundos subsequentes da simulação

Explicação das figuras: Cada linha representa 1 segundo de tempo (o tamanho do pacote é escolhido para ter 1 segundo de tempo de transmissão para maior clareza). Observe que cada nó pode iniciar o algo a qualquer momento, não em uma sequência ou hora específica. As colunas são as seguintes:

  • O NÓDULO A recebe: O nó A vê em seu lado receptor (este também é P4 abaixo)

  • NODE A injeta: Qual nó A envia (observe que é A ou aleatoriamente A ou B)

  • P1, P2, P3: Os três pacotes que estão em trânsito (em ordem) entre A e B (1 segundo de transmissão significa que 3 pacotes estão em trânsito por uma latência de 3)

  • O NODE B recebe: O que B vê no seu lado receptor (este é P3)

  • O NODE B injeta: O que B envia (observe que é B, ou aleatoriamente A ou B por algo)

  • P4: O pacote em trânsito de B para A (veja também P1, P2, P3)

  • A conta A: O que A conta para os pacotes A que ele viu

  • A conta B: O que A conta para os pacotes B que ele viu

  • B conta A: O que B conta para os pacotes A que ele viu

  • B conta B: O que B conta para os pacotes B que ele viu

  • A-> B: A latência que A estima em relação a B (taxa de RTT de 4 segundos com base nos pacotes vistos)

  • B-> A: latência estimada por B em relação a A (taxa de RTT de 4 segundos com base nos pacotes vistos)

Como podemos ver os dois nós convergirem e permanecerem em torno de sua verdadeira latência (na verdade, não vemos isso em A porque são necessários mais segundos para convergir, mas converge no mesmo comportamento que B)

Filtros melhores podem convergir mais rapidamente, mas podemos ver claramente como ambos convergem em torno dos valores corretos para seus atrasos; portanto, eles podem saber exatamente o atraso (mesmo que eu esteja mostrando sua estimativa apenas para ilustração).

Além disso, mesmo que as larguras de banda entre os links sejam diferentes, o método acima ainda pode se manter (embora seja necessário pensar mais para ter mais certeza) usando pares de pacotes para descobrir estimativas de largura de banda e aplicar apenas à equação de proporção acima.

Conclusão Fornecemos um algoritmo para que A e B saibam sua posição na rede e sua latência para o outro nó no diagrama acima. Utilizamos um método de estimativa de medição de rede em vez de abordagens baseadas em relógio que, de fato, não podem levar a uma solução devido a um problema de sincronização de relógio recursivo.

Observe que agora eu editei esta resposta, fornecendo todas as simulações, porque ninguém acreditaria em mim. Eu a resolvi até onde você pode ver nos primeiros comentários. Felizmente, com esses resultados, alguém pode estar mais convencido e aprovar para ajudar todos pelo menos a encontrar um erro ou correção neste quebra-cabeça de medição de rede!

user3134164
fonte
3
Eu não acho que isso funciona. Como a largura de banda é a mesma, a única diferença que A e B vêem é que, se eles começaram ao mesmo tempo, B esperaria 3s antes de receber qualquer dado e A esperaria 1s. Mas eles não têm um relógio compartilhado e não sabem que começaram ao mesmo tempo. Talvez A não ouça nada por dez anos, porque ele começou a executar o protocolo primeiro.
David Richerby
Não há nenhum requisito para iniciar ao mesmo tempo em que alguém pode iniciar a qualquer momento. Eles apenas precisam executar por algum tempo. Agradeço que você reserve um tempo para revisar, mas leia novamente. Este é um método estatístico e envolve convergência. Não estou dizendo que estou 100%, é absolutamente correto, pois não simulei, mas apenas o comentário que você fez não se aplica na minha opinião. Talvez isso explique a ideia mais geral: se você aceitar que a largura de banda * atraso produto é diferente para as duas ligações, em seguida, um link será na verdade contêm mais pacotes - e que pode ser detectada por algo acima ...
user3134164
Acho que não entendi direito, mas é possível. Você concorda que a largura de banda é a mesma para que ambos A e B recebam dados na mesma taxa? Nesse caso, os dois não convergirão exatamente para a mesma coisa?
David Richerby
Sim, é claro que eles recebem na mesma proporção, isso não significa que eles convergem para a mesma coisa. Existem pacotes A e B na rede. A questão é qual é a proporção de pacotes A vs B. Fiz algumas simulações simples agora e recebo o viés o tempo todo. Para ter uma idéia, já que acho que não posso postar tudo aqui, assuma que b é tal que 1 pacote leva uma segunda transmissão. Sempre há 4 pacotes em trânsito. Aplicar algoritmo e boom, conseguimos medir o OTT, evitando métodos de relógio / eventos sincronizados que não funcionam com métodos de convergência estatística!
user3134164
Qual é "a proporção de pacotes de A vs B"?
Gilles 'SO- stop be evil'
0

Esta é uma resposta para @ user3134164, mas é muito grande para um comentário.

PxxRxx

  • , e da mesma forma R 2 = ( 1R1=(1-R2)×(1-P2)R2=(1-R1)×(1-P1)1-R21-P2
  • R1R2R11-R1R21-R2

É por isso que acredito que isso não levará a lugar algum. Por favor, indique qualquer erro que eu possa ter cometido durante esse raciocínio.

Matrefeytontias
fonte
Bem-vindo à Ciência da Computação ! Sua resposta parece boa, mas, como você afirma, é um comentário aprofundado sobre a observação de @ user3134164. Eu acho que você pode resolver esse problema das seguintes maneiras 1) Tente expandir sua resposta para que esta também seja uma resposta para a pergunta real. ou 2) Crie uma nova pergunta que indique essencialmente o principal equívoco do comentário e resposta automática do usuário3134164 com uma resposta semelhante a essa. Qual é apropriado é com você. Eu acho que talvez fazer uma nova pergunta seja uma boa idéia, mas talvez você possa expandir mais do que eu acho. Pergunte se você tiver mais perguntas.
Lagarto discreto
É claro que @ user3134164 também é livre para 'promover' o comentário em uma pergunta,
Lagarto discreto
"Px a probabilidade de o robô x escolher seus próprios pacotes quando recebe um dos pacotes do outro robô" vem de uma função aleatória () do computador, como na suposição - por exemplo, para dois tipos de pacotes, sempre será 0,5. Se a função random () for suficientemente uniforme, a "taxa real de atraso do RTT de A para B" pode ser calculada. Pela sua definição de R, acho que R1 = (1-R2) * 0,5, portanto a razão é conhecida. Então ainda acredito que minha resposta funciona bem. Muito obrigado por reservar um tempo para investigar.
user3134164