Протокол минимальных пар - Minimum-Pairs Protocol

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

Методология

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

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

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

• A → X → B и B → X → A
• 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 и наоборот следующие:

	А	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 мс меньше)

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

${\displaystyle a+b=9}$${\displaystyle a+c=8}$${\displaystyle b+c=6}$

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

${\displaystyle a=5.5ms}$${\displaystyle b=3.5ms}$${\displaystyle c=2.5ms}$

В этом случае абсолютные ошибки равны ${\displaystyle |5-5.5|=0.5ms}$, ${\displaystyle |4-3.5|=0.5ms}$, и ${\displaystyle |2-2.5|=0.5ms}$ по всем трем ссылкам соответственно. Для сравнения: средний 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] как функция основного распределения задержки. Это полезно, так как позволяет рассчитывать ожидаемую ошибку, зная характер задержек на каналах между ненадежным и доверенным узлами.

Смотрите также

• Сетевая задержка
• Сквозная задержка
• Время в оба конца
• Надежная система

Рекомендации

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