Medindo a latência de rede unidirecional

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?

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

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-1$$n-1$

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!

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

$A$$B$$C_{A1}$
$B$$C_{B1}=1$
$A$$C_{A2}=9$
$B$$C_{B2}=5$
$A$$B$

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

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:

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!

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

$P_x$$x$$R_x$$x$

• , e da mesma forma R 2 = ( $R_1 = (1 - R_2) \times (1 - P_2)$$R_2 = (1 - R_1) \times (1 - P_1)$$1 - R_2$$1 - P_2$
• $R_1$$R_2$$\frac{R_1}{1 - R_1}$$\frac{R_2}{1 - R_2}$

É 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.