Protocolo de Pares Mínimos - Enciclopedia

El protocolo de pares mínimos (o MP) es un protocolo de medición activo diseñado para estimar en tiempo real la menor de las demoras de ida y vuelta de una red (OWD). 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 no confiable. Todos los cuatro nodos deben cooperar, aunque no se requiere que el cuarto nodo coopere de manera honesta. El objetivo es realizar estas estimaciones sin involucrar a los nodos no confiables en la sincronización de relojes y de manera más precisa que simplemente la mitad del tiempo de ida y vuelta (RTT). El protocolo MP puede utilizarse en aplicaciones sensibles a la demora (como la colocación de réplicas de redes de entrega de contenido) o para la geolocalización segura de Internet.


Metodología

El protocolo MP requiere que los tres nodos de red confiables sincronicen sus relojes y tengan acceso seguro a sus claves públicas, lo cual podría lograrse a través de un sistema de infraestructura de claves públicas cerrado (PKI). El nodo no confiable no necesita seguir el mismo procedimiento porque no se asume que cooperará de manera honesta. Para estimar un límite superior a la menor de las demoras de ida y vuelta entre el nodo A y el nodo no confiable X (ver la figura para la notación), X primero establece una conexión de aplicación de nivel a todos los tres nodos. Esto se podría hacer de manera transparente a través del navegador utilizando, por ejemplo, WebSockets. Los tres nodos luego se turnan para intercambiar timestamps firmados digitalmente.

Suponiendo que el nodo A comience, envía un timestamp firmado a X. El nodo X forwarding ese mensaje a los otros dos nodos. Cuando se recibe el mensaje, se registra el tiempo de recepción. El nodo receptor luego verifica la firma y calcula el tiempo que tomó el mensaje para traversar la red desde su origen hasta el destinatario pasando por el nodo no confiable. Esto se hace restando el timestamp del mensaje al tiempo de recepción. El nodo B luego repite el proceso, seguido por el nodo C. Después de que todos los tres nodos hayan tomado turnos, terminan con seis estimaciones de demora 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 la menor de las demoras de ida y vuelta en los tres enlaces de red entre A, B, C y X, se toma el mínimo de cada par de los anteriores (es decir, se descarta el mayor). Cada uno de los tres pares representa una aproximación a la menor demora en cada enlace, lo que genera un sistema de tres ecuaciones en tres incógnitas. Solucionando estas ecuaciones simultáneamente para a, b y c (ver la figura) se obtiene la estimación de la demora.


= Ejemplo numérico =

Supongamos que las demoras reales (por ejemplo, en milisegundos) desde los nodos A, B y C hasta el nodo X y viceversa son las siguientes:

Estos son los retrasos desconocidos. Necesitamos estimar la menor de las demoras de ida y vuelta en cada uno de los tres enlaces. En este ejemplo, la menor es de 5 ms, 4 ms y 2 ms en los enlaces entre X y los tres nodos confiables respectivamente (A, B y C). Cuando los nodos intercambian mensajes de timestamp, solo pueden ver lo siguiente:

A → X → B = 9 ms y B → X → A = 14 ms (9 ms es la menor)
A → X → C = 9 ms y C → X → A = 8 ms (8 ms es la menor)
B → X → C = 12 ms y C → X → B = 6 ms (6 ms es la menor)

El sistema de ecuaciones se convierte así:



que resulta en estimaciones de las menores demoras de ida y vuelta de: