Измерение одной стороны задержки сети

Question

Это загадка по поводу измерения задержки сети, которую я создал. Я считаю, что решение в том, что это невозможно, но друзья не согласны. Я ищу убедительные объяснения в любом случае. (Несмотря на то, что он представляет собой загадку, я думаю, что она вписывается в этот веб -сайт из -за его применимости к дизайну и опыту протоколов связи, таких как в онлайн -играх, не говоря уже о NTP.)

Предположим, что два робота находятся в двух комнатах, соединенных сетью с разными односторонними задержками, как показано на рисунке ниже. Когда робот А отправляет сообщение роботу Б, для его прибытия требуется 3 секунды, но когда робот B отправляет сообщение роботу А, на прибытие требуется 1 секунда. Задержки никогда не различаются.

Роботы идентичны и не имеют общих часов, хотя они могут измерить время (например, у них останавливаются часы). Они не знают, кто из них является роботом А (чьи сообщения задерживаются 3S), а какой робот B (сообщения которого задерживаются 1 с).

Протокол, чтобы обнаружить время поездки в оба конца:

whenReceive(TICK).then(send TOCK)

// Wait for other other robot to wake up
send READY
await READY
send READY

// Measure RTT
t0 = startStopWatch()
send TICK
await TOCK
t1 = stopStopWatch()
rtt = t1 - t0  //ends up equalling 4 seconds

Есть ли протокол для определения задержек поездки с одним способом? Могут ли роботы обнаружить, у кого из них более длинная задержка отправки сообщения?

Answer 1

Следующая диаграмма, из сообщение в блоге, которое я написал, это визуальное доказательство того, что это невозможно:

Обратите внимание, как время прибытия пакета с каждой стороны остается неизменным, даже когда изменяются односторонние задержки (и даже становятся отрицательными!). Первый пакет всегда достигает сервера на уровне 1,5S на часах сервера, второй всегда достигает клиента в 2S на часах клиента и т. Д. Содержимое пакета и время локального прибытия - это только вещи Протокол может быть основан на том, что содержимое и время прибытия могут быть постоянными, так как асимметрия варьируется в зависимости от исходного перекоса.

По сути, асимметрия в односторонних задержках выглядит в яблочко Как перекоситься. Поскольку проблема гласит, что мы не начинаем, зная, что начальные перекосы с часами или одностороннюю асимметрию задержки, и меняется, что одно выглядит как различное, поэтому их последствия неразличимы, мы не можем разделить их вклад, чтобы решить для Асимметрия с односторонней задержкой. Это невозможно.

Более формально, вы не можете решить длину краев, когда дают только длины циклов. На основе цикла есть степень свободы $ N-1, соответствующие $ N-1 $ неизвестными перекосами по сравнению с одним из участников. Вы всегда можете скрыть односторонние задержки, даже если их участники:

Если вы не так визуально склонны, у меня есть другой интуитивно понятный аргумент. Представьте себе портал времени до ста лет в будущем. Когда вы общаетесь с этим с кем-то на другой стороне, вы понимаете, что разговор совершенно нормальный, несмотря на столетнюю асимметрию в односторонних задержках. Любой наблюдаемый эффект был бы очевиден в этом масштабе!

Answer 2

Я думаю, что невозможно выяснить одностороннюю задержку, просто сравнивая секундомерные часы.

$ A $ отправляет $ b $ его часы $ c_ {a1} $, допустим, ее стоимость 5.
$ B $ подтверждает сообщение в момент времени $ c_ {b1} = 1 $
$ A $ снова отправляет свои часы, $ c_ {a2} = 9 $ (начальная + задержка в обратном пути).
$ B $ получает в момент времени $ c_ {b2} = 5 $.
И так далее. Ни $ a $ или $ b $ не выясните, когда другой робот получил сообщение в отношении их часов.

Может быть, если вы сделаете это награжденным вопросом, кто -то взломает его. До тех пор, слава.

Answer 3

Я нашел способ оба обнаружить, какой узел - кто (т. Е. У кого более длинная задержка сообщения) и оценить задержку поездки с одним способом. Хотя другие ответы верны, они рассматривают только прямое измерение часов, которое, конечно, не может работать. Однако, как я доказываю здесь, это только часть истории, так как здесь мой рабочий алгоритм для вышеизложенного:

Предположим, как в реальной жизни:

• Ссылки конечной полосы пропускания B

• Каждый узел имеет уникальный адрес (например, A и B)

• Размер пакета P намного меньше, чем продукт задержки полосы пропускания*

• Узлы A и B способны заполнять канал

• Узлы имеют случайный() функция

Каждый узел заполняет канал собственными пакетами (помеченными A или B соответственно) или пересылает пакеты, полученные из других узлов следующим образом:

Always fill the channel with my own packets except:
if I receive a packet from another node then
   Randomly choose to 
          either forward that packet from the other node
          or discard that packet and forward my own packet

Интуитивное объяснениеПоскольку продукт задержки полосы пропускания A выше (потому что задержка выше) A сможет получить больше пакетов, чем B, поэтому, следовательно, поэтому B. Каждый узел может знать, кто они на диаграмме.

Более того, с достаточным временем сходимости бега над алгоритмом соотношение пакетов A к B будет обозначать Фактическое соотношение задержки RTT от A к B и, следовательно, желаемой OTT.

След и результат моделированияВот симуляция, которая доказывает вышеупомянутое и показывает, как успешно сходятся к 3 -секундной задержке, и B сходился около 1 секунды: задержка:

Объяснение фигур:Каждая строка представляет 1 секунду времени (размер пакета выбирается, чтобы иметь 1 секундное время передачи для ясности). Обратите внимание, что каждый узел может запустить Algo в любое время, а не в какой -либо конкретной последовательности или времени. Столбцы следующие:

• Узел получает получение: что Узел А видит в своей приемной стороне (это также P4 ниже)

• Узел A инъекции: что отправляет узел А (обратите внимание, что это или случайно a или b)

• P1, P2, P3: Три пакета, которые находятся в транзите (по порядку) между A и B (1 секундная передача означает 3 пакета находится в транзите для задержки 3)

• Узел B получает: что B видит в своей приемной стороне (это P3)

• Узел B инъекции: что B отправляет (обратите внимание, что это B, или случайно A или B на алго)

• P4: пакет в пути от B к A (см. Также P1, P2, P3)

• Подсчет A: Что за счет пакетов, которые он видел

• Подсчет Б: Что за счет пакетов B, которые он видел

• B считается A: Что B считает пакеты, которые он видел

• B Считается B: Что B считается для пакетов B, которые он видел

• A-> B: задержка, которая оценивает в B (соотношение RTT 4 секунды на основе пакетов)

• B-> a: задержка, которая оценивает B к A (соотношение RTT 4 секунды на основе пакетов)

Как мы видим, что оба узла сходится и оставаемся вокруг их истинной задержки (на самом деле мы не видим этого для A, потому что для сходимости требуется больше секунд, но он сходится на то же поведение, что и B)

Лучшие фильтры могут сходиться быстрее, но мы можем ясно видеть, как они оба сходятся вокруг правильных значений для своих задержек, поэтому они могут в яблочко Знайте их задержку (хотя я показываю их оценку только для иллюстрации).

Кроме того, даже если полоса пропускания между ссылками различны, метод выше все еще может содержать (хотя нужно будет думать об этом больше, чтобы быть более уверенным), используя пары пакетов, чтобы выяснить оценки полосы пропускания, а затем просто применить к приведенному выше уравнению доли.

ВыводМы предоставили алгоритм для A и B, чтобы узнать их положение в сети и знать их задержку с другим узлом для вышеуказанной диаграммы. Мы использовали метод оценки измерения сети, а не подходы на основе тактовых данных, которые действительно не могут привести к решению из-за рекурсивной проблемы синхронизации часов.

Примечание Теперь я отредактировал этот ответ, предоставив все симуляции, потому что никто не поверил бы мне, что я решил его, насколько вы можете увидеть в первых комментариях. Надеемся, что с этими результатами кто -то может быть более убежденным и одобрить, чтобы помочь всем, по крайней мере, найти одну ошибку или правильность в этой головоломке измерения сети!

Answer 4

Это ответ на @user3134164, но слишком большой для комментария.

Вот моя попытка показать, почему это не может работать (математический подход). Давайте позвоним в $ p_x $ вероятность того, что Robot $ x $ выберет свои собственные пакеты, когда он получает один из пакетов другого робота, и $ r_x $ вероятность того, что пакетный робот $ x $ получен его. После достижения стационарного режима (то есть после «бесконечного» количества времени, т.е. вся конвергенция сделана), у нас есть следующее:

• $ R_1 = (1 - r_2) times (1 - p_2) $, и аналогично $ r_2 = (1 - r_1) times (1 - p_1) $. Идея состоит в том, что если робот получает один из своих собственных пакетов, это означает, что другой робот получил его вместо одного из своих (отсюда $ 1 - r_2 $) и что он все еще решил отправить его вместо одного из своих ( Отсюда и продукт на 1 доллар - P_2 $).
• Это дает систему из двух уравнений с двумя неизвестными, $ r_1 $ и $ r_2 $. Вы можете решить это, но это не имеет значения. Фактически, соотношения, которые вы ищете, соответственно $ frac {r_1} {1 - r_1} $ и $ frac {r_2} {1 - r_2} $. Как вы можете заметить, единственные термины, которые появляются в этих выражениях, - это вероятности, по которым каждый робот выбирает свой собственный пакет над другими. Задержки даже не появляются в формуле просто потому, что оба робота постоянно выкачивают пакеты, поэтому оба постоянно получают пакеты. Они действительно получат различные соотношения пакетов, но это будет зависеть только от вышеупомянутых вероятностей.

Вот почему я считаю, что это не приведет вас никуда. Пожалуйста, укажите на любую ошибку, которую я мог сделать во время этой рассуждения.