Medición de latencia de red unidireccional

Este es un rompecabezas sobre la medición de la latencia de red que creé. Creo que la solución es que es imposible, pero los amigos no están de acuerdo. Estoy buscando explicaciones convincentes de cualquier manera. (Aunque se plantea como un rompecabezas, creo que encaja en este sitio web debido a su aplicabilidad al diseño y la experiencia de los protocolos de comunicación, como en los juegos en línea, sin mencionar NTP).

Suponga que dos robots están en dos habitaciones, conectados por una red con latencias unidireccionales diferentes, como se muestra en el siguiente gráfico. Cuando el robot A envía un mensaje al robot B, tarda 3 segundos en llegar, pero cuando el robot B envía un mensaje al robot A, tarda 1 segundo en llegar. Las latencias nunca varían.

Los robots son idénticos y no tienen un reloj compartido, aunque pueden medir el paso del tiempo (por ejemplo, tienen cronómetros). No saben cuál de ellos es el robot A (cuyos mensajes se retrasan 3s) y cuál es el robot B (cuyos mensajes se retrasan 1s).

Un protocolo para descubrir el tiempo de ida y vuelta es:

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 un protocolo para determinar los retrasos en el viaje de ida? ¿Pueden los robots descubrir cuál de ellos tiene el retraso de envío de mensajes más largo?

El siguiente diagrama, de una publicación de blog que escribí , es una prueba visual de que es imposible:

Observe cómo los tiempos de llegada de paquetes en cada lado permanecen iguales, incluso cuando las latencias unidireccionales cambian (¡e incluso se vuelven negativas!). El primer paquete siempre llega al servidor a las 1.5 s en el reloj del servidor, el segundo siempre llega al cliente a las 2 s en el reloj del cliente, etc. El contenido del paquete y las horas de llegada locales son las únicas cosas en las que se puede basar un protocolo, pero el los contenidos y los tiempos de llegada pueden mantenerse constantes ya que la asimetría varía al variar también la inclinación inicial del reloj.

Básicamente, la asimetría en las latencias unidireccionales se ve exactamente como la inclinación del reloj. Dado que el problema indica que no comenzamos conociendo el sesgo inicial del reloj o la asimetría de latencia unidireccional, y variar uno parece variar el otro para que sus efectos sean indistinguibles, no podemos separar sus contribuciones para resolver el problema. asimetría de latencia unidireccional. Es imposible.

$n-1$$n-1$

Si no eres tan visualmente inclinado, tengo otro argumento intuitivo. Imagine un portal de tiempo para cien años en el futuro. Cuando conversas con alguien del otro lado, te das cuenta de que la conversación es totalmente normal a pesar de la asimetría de cien años en retrasos unidireccionales. ¡Cualquier efecto observable habría sido obvio en esa escala!

Creo que es imposible determinar la latencia unidireccional simplemente comparando cronómetros.

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

Tal vez si lo conviertes en una pregunta de recompensa, alguien lo resolverá. Hasta entonces, felicitaciones.

He encontrado una manera de AMBOS descubrir qué nodo es quién (es decir, quién tiene el retraso de mensaje más largo) Y estimar el retraso de viaje de ida. Si bien las otras respuestas son correctas, SOLO están considerando la medición directa del reloj que, por supuesto, no puede funcionar. Sin embargo, como estoy demostrando aquí, esto es solo una parte de la historia, ya que aquí está mi algoritmo de trabajo para lo anterior:

Asumir como en la vida real:

• Enlaces de ancho de banda finito b

• Cada nodo tiene una dirección única (por ejemplo, A y B)

• Tamaño de paquete p mucho más pequeño que el ancho de banda * producto de latencia

• Los nodos A y B pueden llenar el canal

• Los nodos tienen una función aleatoria ()

Cada nodo llena el canal con sus propios paquetes (marcados con A o B respectivamente) O reenvía los paquetes que recibió de otros nodos de la siguiente manera:

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

Explicación intuitiva Dado que el producto de latencia de ancho de banda * de A es mayor (porque la latencia es mayor) A logrará recibir más paquetes que B, por lo tanto, cada nodo puede saber quiénes son en el diagrama .

Además, con suficiente tiempo de convergencia de ejecución por encima del algoritmo, la proporción de paquetes de A a B denotará la proporción real de retraso RTT de A a B y, por lo tanto, la OTT deseada .

RASTREO DE RESULTADOS DE SIMULACIÓN Aquí hay una simulación que demuestra lo anterior y muestra cómo A converge exitosamente hacia un retraso de 3 segundos y B converge alrededor de un retraso de 1 segundo:

Explicación de las figuras: cada línea representa 1 segundo de tiempo (el tamaño del paquete se elige para tener 1 segundo de tiempo de transmisión para mayor claridad). Tenga en cuenta que cada nodo puede iniciar el algoritmo en cualquier momento, no en una secuencia o tiempo particular. Las columnas son las siguientes:

• NODO A recibe: lo que ve el nodo A en su lado receptor (esto también es P4 a continuación)

• NODO A inyecta: qué nodo A envía (tenga en cuenta que esto es A, o aleatoriamente A o B)

• P1, P2, P3: los tres paquetes que están en tránsito (en orden) entre A y B (1 segundo de transmisión significa que 3 paquetes están en tránsito para una latencia de 3)

• NODO B recibe: lo que B ve en su lado receptor (esto es P3)

• NODE B inyecta: lo que B envía (tenga en cuenta que esto es B, o aleatoriamente A o B por algo)

• P4: El paquete en tránsito de B a A (ver también P1, P2, P3)

• A cuenta A: lo que A cuenta para los paquetes A que ha visto

• A cuenta B: lo que A cuenta para los paquetes B que ha visto

• B cuenta A: lo que B cuenta para los paquetes A que ha visto

• B cuenta B: lo que B cuenta para los paquetes B que ha visto

• A-> B: La latencia que A estima hacia B (relación de RTT de 4 segundos según los paquetes vistos)

• B-> A: La latencia que B estima hacia A (relación de RTT de 4 segundos según los paquetes vistos)

Como podemos ver, ambos nodos convergen y permanecen alrededor de su latencia verdadera (en realidad no vemos eso para A porque se necesitan más segundos para converger pero sí converge el mismo comportamiento que B)

Los mejores filtros podrían converger más rápido, pero podemos ver claramente cómo ambos convergen en torno a los valores correctos para sus retrasos, por lo tanto, pueden saber exactamente cuál es su retraso (aunque estoy mostrando su estimación solo como ilustración).

Además, incluso si los anchos de banda entre los enlaces son diferentes, el método anterior podría mantenerse (aunque uno tendrá que pensarlo más para estar más seguro) al usar pares de paquetes para calcular las estimaciones de ancho de banda y luego simplemente aplicar a la ecuación de proporción anterior.

Conclusión Proporcionamos un algoritmo para que A y B conozcan su posición en la red y conozcan su latencia al otro nodo para el diagrama anterior. Utilizamos un método de estimación de medición de red en lugar de enfoques basados ​​en el reloj que, de hecho, no pueden conducir a una solución debido a un problema de sincronización del reloj recursivo.

Tenga en cuenta que ahora edité esta respuesta proporcionando todas las simulaciones porque nadie me creería. Lo resolví hasta donde puede ver en los primeros comentarios. ¡Esperemos que con estos resultados alguien pueda estar más convencido y aprobar ayudar a todos al menos a encontrar un error o corrección en este rompecabezas de medición de red!

Esta es una respuesta a @ user3134164 pero es demasiado grande para un comentario.

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

• $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 eso creo que esto no te llevará a ninguna parte. Señale cualquier error que pueda haber cometido durante este razonamiento.