Los pares mínimos (o MP) es un protocolo de medición activo para estimar en tiempo real el menor de los retardos de red unidireccionales (OWD) hacia adelante y hacia atrás . [1] Está diseñado para funcionar en entornos hostiles, donde un conjunto de tres nodos de red puede estimar un límite superior de OWD entre ellos y un cuarto nodo que no es de confianza. Los cuatro nodos deben cooperar, aunque no se requiere la cooperación honesta del cuarto nodo. El objetivo es realizar tales estimaciones sin involucrar a los nodos que no son de confianza en la sincronización del reloj , y de una manera más precisa que simplemente la mitad del tiempo de ida y vuelta (RTT) . El protocolo MP se puede utilizar en aplicaciones sensibles al retraso (como la colocación de réplicas de CDN ) o paraGeolocalización de Internet .
Metodología
El protocolo MP requiere que los tres nodos de red de confianza sincronicen sus relojes y tengan acceso seguro a sus claves públicas, lo que podría lograrse a través de un sistema de infraestructura de clave pública (PKI) cerrada . El nodo que no es de confianza no necesita seguir su ejemplo porque no se supone que coopere honestamente. Para estimar un límite superior al más pequeño del OWD directo e inverso entre el nodo A y el nodo X que no es de confianza (ver la figura para la notación), X primero establece una conexión de capa de aplicación a los tres nodos. Esto se puede hacer de forma transparente a través del navegador utilizando, por ejemplo, Web-sockets . Luego, los tres nodos se turnan para intercambiar marcas de tiempo firmadas digitalmente .
Suponiendo que el nodo A comienza, envía una marca de tiempo firmada a X. El nodo X reenvía ese mensaje a los otros dos nodos. Cuando se recibe el mensaje, se registra su hora de recepción. El nodo receptor luego verifica la firma y calcula el tiempo que le tomó al mensaje atravesar la red desde su originador hasta el receptor que pasa por el nodo que no es de confianza. Esto se hace restando la marca de tiempo en el mensaje de la hora de recepción. El nodo B luego repite el proceso, seguido por el nodo C. Después de que los tres nodos se hayan turnado, terminan con seis estimaciones de retardo correspondientes a los enlaces:
- A → X → B y B → X → A
- A → X → C y C → X → A
- B → X → C y C → X → B
Para estimar el menor de los OWD directo e inverso en los tres enlaces de red entre A, B, C y X, se toma el mínimo de cada uno de los pares anteriores (es decir, se descarta el mayor). Cada uno de los tres pares representa una aproximación al OWD más pequeño en cada enlace, lo que genera un sistema de tres ecuaciones en tres incógnitas. Si se resuelven simultáneamente para a, byc (ver figura) se obtiene la estimación del retardo.
Ejemplo numérico
Suponga que los retrasos reales (por ejemplo, en milisegundos) al nodo X desde los nodos A, B y C y viceversa son los siguientes:
A | B | C | |
---|---|---|---|
Al nodo X | 5 | 8 | 2 |
Desde el nodo X | 6 | 4 | 4 |
Esos son los retrasos desconocidos. Necesitamos estimar el menor entre el avance y el retroceso en cada uno de los tres enlaces. En este ejemplo, el menor es 5 ms, 4 ms y 2 ms en los enlaces entre X y los tres nodos de confianza, respectivamente (A, B y C). Cuando los nodos intercambian los mensajes de marca de tiempo, solo pueden ver lo siguiente:
- A → X → B = 9ms y B → X → A = 14ms (9ms es el menor)
- A → X → C = 9ms y C → X → A = 8ms (8ms es el menor)
- B → X → C = 12ms y C → X → B = 6ms (6ms es el menor)
El sistema de ecuaciones se convierte así en:
lo que da como resultado estimaciones para los OWD más pequeños de:
En este caso, los errores absolutos son , , y en los tres enlaces respectivamente. En comparación, el RTT promedio calcularía el OWD en los tres enlaces como 5.5ms, 6ms y 3ms, dando como resultado errores absolutos de 0.5ms, 2ms y 1ms respectivamente. Por lo tanto, el protocolo MP es más preciso en este ejemplo.
Análisis
La inyección de retrasos artificiales, por ejemplo, reteniendo el mensaje durante un tiempo en lugar de reenviarlo rápidamente, permite que el nodo que no es de confianza aumente los OWD estimados. Por lo tanto, el protocolo MP puede estimar un límite superior para los OWD en los tres enlaces colectivamente entre los nodos confiables y el no confiable. Por ejemplo, si los retrasos estimados (hacia adelante o hacia atrás) fueron de 30 ms, 40 ms y 50 ms, el real no puede ser 60 ms, 70 ms y 80 ms porque eso significa que el nodo no confiable logró reducir los tres juntos, lo cual es difícil de lograr ya que los retrasos son limitado por las características físicas de los medios de transmisión. Sin embargo, tenga en cuenta que el nodo que no es de confianza puede, en algún caso, reducir un subconjunto de enlaces, pero no todos, retrasando selectivamente algunos de los enlaces.
En comparación con el promedio (es decir, RTT / 2), el protocolo MP nunca devuelve una estimación al menor de los OWD directo e inverso que sea mayor que el devuelto por el método de promedio. Además, la distribución de probabilidad del error absoluto para el protocolo MP se ha obtenido [2] en función de la distribución de retardo subyacente. Esto es útil ya que permite el cálculo del error esperado conociendo la naturaleza de las demoras en los enlaces entre el nodo no confiable y los confiables.
Ver también
Referencias
- ^ Abdou, AbdelRahman (2015). "4". Verificación de ubicación en Internet: desafíos y soluciones (Ph.D.). Universidad de Carleton.
- ^ Abdou, AbdelRahman; Matrawy, Ashraf; van Oorschot, Paul (mayo de 2015). "Estimación precisa del retraso unidireccional con menor confiabilidad del cliente". Cartas de comunicaciones de IEEE . 19 (5): 735–738. CiteSeerX 10.1.1.696.7425 . doi : 10.1109 / LCOMM.2015.2411591 .