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

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

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

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

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

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

Числовой пример

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


	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{мс}}\\b&=3{,}5~{\text{мс}}\\c&=2{,}5~{\text{мс}}\end{aligned}}

В этом случае абсолютные ошибки составляют $|5-5{,}5|=0{,}5~{\text{мс}}$ , $|4-3{,}5|=0{,}5~{\text{мс}}$ и $|2-2{,}5|=0{,}5~{\text{мс}}$ на каждом из трёх каналов. Для сравнения, средний RTT и деление пополам дадут оценки OWD как 5,5 мс, 6 мс и 3 мс, что приводит к абсолютным ошибкам 0,5 мс, 2 мс и 1 мс соответственно. Таким образом, протокол минимальных пар оказывается точнее в этом примере.

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

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

↑ Abdou, AbdelRahman (2015). “4”. Internet Location Verification: Challenges and Solutions (Ph.D.) [англ.]. Carleton University. Дата обращения 2024-06-24.
↑ Abdou, AbdelRahman; Matrawy, Ashraf; van Oorschot, Paul (май 2015). “Accurate One-Way Delay Estimation with Reduced Client-Trustworthiness”. IEEE Communications Letters [англ.]. 19 (5): 735—738. DOI:10.1109/LCOMM.2015.2411591. Дата обращения 2024-06-24. Проверьте дату в |date= (справка на английском); |access-date= требует |url= (справка)

[1] Abdou, AbdelRahman (2015). “4”. Internet Location Verification: Challenges and Solutions (Ph.D.) [англ.]. Carleton University. Дата обращения 2024-06-24.

[2] Abdou, AbdelRahman; Matrawy, Ashraf; van Oorschot, Paul (май 2015). “Accurate One-Way Delay Estimation with Reduced Client-Trustworthiness”. IEEE Communications Letters [англ.]. 19 (5): 735—738. DOI:10.1109/LCOMM.2015.2411591. Дата обращения 2024-06-24. Проверьте дату в |date= (справка на английском); |access-date= требует |url= (справка)

[1]

[2]

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

Методика

Числовой пример

Анализ

Примечания

Категории