Протокол минимальных пар

Минимальные пары (или MP) — это активный протокол измерения, позволяющий в режиме реального времени оценивать меньшую из прямых и обратных односторонних сетевых задержек (OWD). ^[1] Он предназначен для работы во враждебных средах, где набор из трех сетевых узлов может оценить верхнюю границу OWD между собой и четвертым недоверенным узлом. Все четыре узла должны сотрудничать, хотя честное сотрудничество со стороны четвертого узла не требуется. Цель состоит в том, чтобы провести такие оценки без участия ненадежных узлов в тактовой синхронизации и с большей точностью, чем просто половина времени прохождения туда и обратно (RTT). Протокол MP можно использовать в приложениях, чувствительных к задержкам (например, при размещении реплик сети доставки контента ) или для безопасного определения местоположения в Интернете .

Методология [ править ]

Иллюстрация протокола МП. Число в ячейке *<i, j>* указывает рассчитанное значение OWD (например, в миллисекундах) от узла, указанного в строке i, до узла X и узла, указанного в столбце j .

Протокол MP требует, чтобы три доверенных сетевых узла синхронизировали свои часы и имели безопасный доступ к своим открытым ключам, что может быть достигнуто с помощью закрытой системы инфраструктуры открытых ключей (PKI). Недоверенному узлу не обязательно следовать этому примеру, поскольку не предполагается, что он будет сотрудничать честно. Чтобы оценить верхнюю границу меньшего из прямых и обратных OWD между узлом A и недоверенным узлом X (обозначения см. на рисунке), X сначала устанавливает соединение прикладного уровня со всеми тремя узлами. Это можно сделать прозрачно через браузер, используя, например, WebSockets . Затем три узла по очереди обмениваются метками времени с цифровой подписью .

что узел A начинается, он отправляет подписанную метку времени в X. Предполагая , Узел X пересылает это сообщение двум другим узлам. При получении сообщения фиксируется время его получения. Затем принимающий узел проверяет подпись и вычисляет время, которое потребовалось сообщению для прохождения по сети от отправителя до получателя, проходящего мимо недоверенного узла. Это делается путем вычитания временной метки сообщения из времени получения. Затем узел B повторяет процесс, а затем C. узел После того, как все три узла поменялись местами, они получают шесть оценок задержки, соответствующих ссылкам:

А → X → B и B → X → A
А → X → C и C → X → A
B → X → C и C → X → B

Чтобы оценить меньший из прямых и обратных OWD на трех сетевых каналах между A , B , C и X , берется минимум каждой такой пары, указанной выше (т. е. больший отбрасывается). Каждая из трех пар затем представляет собой приближение к меньшему OWD на каждом канале, что генерирует систему трех уравнений с тремя неизвестными. Решение их одновременно для a , b и c (см. рисунок) дает оценку задержки.

Числовой пример [ править ]

Предположим, что фактические задержки (например, в миллисекундах) до узла X из узлов A , B и C и наоборот следующие:


	А	Б	С
К узлу X	5	8	2
Из узла X	6	4	4

Это неизвестные задержки. Нам нужно оценить меньшее из прямых и обратных значений для каждого из трех звеньев. В этом примере меньшее значение составляет 5 мс, 4 мс и 2 мс на каналах между X и тремя доверенными узлами соответственно ( A , B и C ). Когда узлы обмениваются сообщениями с метками времени, они могут видеть только следующее:

A → X → B = 9 мс и B → X → A = 14 мс (9 мс — меньшее)
A → X → C = 9 мс и C → X → A = 8 мс (8 мс — меньшее)
B → X → C = 12 мс и C → X → B = 6 мс (6 мс — меньшее)

Таким образом, система уравнений принимает вид:

{\begin{aligned}a+b&=9\\a+c&=8\\b+c&=6\\\end{aligned}}

что приводит к оценкам меньших OWD:

{\begin{aligned}a&=5.5~{\text{ms}}\\b&=3.5~{\text{ms}}\\c&=2.5~{\text{ms}}\end{aligned}}

В этом случае абсолютные ошибки $|5-5.5|=0.5~{\text{ms}}$ , $|4-3.5|=0.5~{\text{ms}}$ , и $|2-2.5|=0.5~{\text{ms}}$ по всем трем ссылкам соответственно. Для сравнения, средний RTT вычислит OWD для всех трех каналов как 5,5 мс, 6 мс и 3 мс, что приведет к абсолютным ошибкам в 0,5 мс, 2 мс и 1 мс соответственно. Следовательно, протокол MP в этом примере более точен.

Анализ [ править ]

Введение искусственных задержек, например, путем удержания сообщения в течение некоторого времени вместо его быстрой пересылки, позволяет недоверенному узлу увеличить расчетные значения OWD. Таким образом, протокол MP может оценить верхнюю границу OWD для всех трех каналов вместе между доверенными и недоверенными узлами. Например, если расчетные задержки (прямые или обратные) составляли 30 мс, 40 мс и 50 мс, фактическая задержка не может составлять 60 мс, 70 мс и 80 мс, поскольку это означает, что недоверенному узлу удалось уменьшить все три вместе, что трудно достичь, поскольку задержки связаны с физическими характеристиками среды передачи. Однако обратите внимание, что недоверенный узел в некоторых случаях может сократить подмножество ссылок, но не все, путем выборочной задержки некоторых ссылок.

По сравнению со средним значением (т. е. RTT/2), протокол MP никогда не возвращает оценку меньшего из прямых и обратных OWD, которая больше, чем оценка, возвращаемая методом среднего значения. Дополнительно получено вероятностное распределение абсолютной ошибки для протокола MP. ^[2] как функция основного распределения задержки. Это полезно, поскольку позволяет рассчитать ожидаемую ошибку, зная природу задержек на каналах между недоверенным и доверенным узлами.

См. также [ править ]

Ссылки [ править ]

^ Абду, АбдельРахман (2015). «4». Проверка местоположения в Интернете: проблемы и решения (доктор философии). Карлтонский университет.
^ Абду, АбдельРахман; Матрави, Ашраф; ван Ооршот, Пол (май 2015 г.). «Точная односторонняя оценка задержки с пониженной надежностью клиента». Коммуникационные письма IEEE . 19 (5): 735–738. CiteSeerX 10.1.1.696.7425 . дои : 10.1109/LCOMM.2015.2411591 . S2CID 17100293 .

[1] Абду, АбдельРахман (2015). «4». Проверка местоположения в Интернете: проблемы и решения (доктор философии). Карлтонский университет.

[2] Абду, АбдельРахман; Матрави, Ашраф; ван Ооршот, Пол (май 2015 г.). «Точная односторонняя оценка задержки с пониженной надежностью клиента». Коммуникационные письма IEEE . 19 (5): 735–738. CiteSeerX 10.1.1.696.7425 . дои : 10.1109/LCOMM.2015.2411591 . S2CID 17100293 .

[1]

[2]