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

20

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

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

Роботы идентичны и не имеют общих часов, хотя они могут измерять ход времени (например, у них есть секундомеры). Они не знают, кто из них робот A (чьи сообщения задерживаются на 3 с), а какой робот 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

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

Два робота одна асимметричная сеть

Крейг Гидни
источник
5
См. Синхронизация часов в сети с асимметричными задержками (которая требует чего-то выполнимого с обычной интернет-инфраструктурой). Я думаю, что из того, что мы увидели при обсуждении неправильных ответов на этот вопрос, ответ на ваш вопрос заключается в том, что это невозможно.
Жиль "ТАК - перестань быть злым"
Должны ли мы объединить вопросы, или они достаточно различны по цели, чтобы разделить их?
Крейг Гидни
Нет, это разные вопросы. Ваш вопрос устанавливает, что это невозможно в настройке с двумя машинами только с передачей сообщений. Я надеюсь, что решения, основанные, скажем, на информации о задержке, которая будет доступна для некоторых промежуточных каналов на маршруте между клиентом и сервером, и будут иметь какой-то способ распространения этой информации для клиента.
Жиль "ТАК - перестань быть злым"
3
Если бы был способ сделать это, теория относительности Эйнштейна не сработала бы, поскольку она зависит от того факта, что два наблюдателя, которые разделены в пространстве и имеют неизвестные односторонние задержки, не могут договориться о надлежащем времени.
Питер Шор
NTP действительно позволяет / реализует измерение этой дифференциальной задержки на основе того, что машины отправляют друг другу свое время, а не просто отслеживает время отправки / получения своих собственных сообщений, но также и других серверов через содержимое сообщений, см. Ответ на вопрос
Gilles

Ответы:

14

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

Скользящее скольжение часов точно компенсируется латентной асимметрией

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

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

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

Морская болезнь

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

Крейг Гидни
источник
Что вы думаете об этом? software.internet2.edu/owamp
CMCDragonkai
@CMCDragonkai Имейте в виду, что утверждение головоломки является более строгим, чем реальность. На практике у вас есть такие опции, как измерение длины волоконно-оптических линий, регистрация в промежуточных точках, использование знаний о топологии сети, медленное перемещение часов из одного места в другое и т. Д. Например, спутники GPS перемещаются по известным орбитам, и вы может использовать это, чтобы удалить степени свободы при решении. Так что на первый взгляд я не вижу никаких проблем с инструментом одностороннего пинга, пока он или часы, на которые он полагается, используют какую-то эту сладкую сладкую третичную информацию.
Крейг Гидни
О, в таком случае, не могли бы вы обновить свой ответ с возможными обходными путями?
CMCDragonkai
@CMCDragonkai Достаточно иметь их в комментариях. Они выходят за рамки головоломки.
Крейг Гидни
Односторонняя задержка имеет значение, например, для сетевых игр. Кроме того, все говорят, что это невозможно, но я легко могу решить загадку на бумаге - как только вы синхронизируете часы, все, что вы делаете, это измеряете задержку от A до B, отправляя время A в B, с задержкой A-> B, равной B's time - A's sent time, и B-> A равняетсяlatency - A->B delay
Лламагеддон
1

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

B C A 1 B C B 1 = 1 A C A 2 = 9 B C B 2 = 5 A BA посылает свои часы , допустим, его значение равно 5. подтверждает сообщение в момент времени снова отправляет свои часы, (начальная + задержка туда-обратно). получает в момент времени . И так далее. Ни ни могут понять, когда другой робот получил сообщение об их часах.BCA1
BCB1=1
ACA2=9
BCB2=5
AB

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

Рат
источник
0

Я нашел способ ОБА обнаружить, какой узел есть кто (т.е. у кого более длинная задержка сообщения) И оценить задержку одностороннего отключения. В то время как другие ответы верны, они ТОЛЬКО рассматривают прямое измерение тактовой частоты, которое, конечно, не может работать. Однако, поскольку я доказываю здесь, это только часть истории, поскольку вот мой рабочий алгоритм для вышеупомянутого:

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

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

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

  • Размер пакета p намного меньше, чем пропускная способность * задержка продукта

  • Узлы А и В способны заполнить канал

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

Каждый узел заполняет канал своими собственными пакетами (помеченными соответственно 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, поэтому каждый узел может знать, кто они на диаграмме .

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

РЕЗУЛЬТАТ РЕЗУЛЬТАТА МОДЕЛИРОВАНИЯ Вот симуляция, которая подтверждает вышеприведенное и показывает, как А успешно сходится к задержке в 3 секунды, а В сходится примерно к задержке в 1 секунду:

Первые секунды симуляции

Последующие секунды симуляции

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

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

  • УЗЕЛ A вводит: Какой узел A отправляет (обратите внимание, что это 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 считает A: Что A считает для пакетов A, которые он видел

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

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

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

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

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

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

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

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

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

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

user3134164
источник
3
Я не думаю, что это работает. Поскольку пропускная способность одинакова, единственное отличие, которое видят A и B, состоит в том, что, если они начались одновременно, B будет ждать 3 с, прежде чем получит какие-либо данные, а A будет ждать 1 с. Но у них нет общих часов, поэтому они не знают, что начали одновременно. Возможно, А ничего не слышит в течение 10 секунд, потому что он начал сначала запускать протокол.
Дэвид Ричерби
Не требуется запускать одновременно, каждый может начать в любое время. Они оба должны работать какое-то время. Я ценю, что вы нашли время для обзора, но, пожалуйста, прочитайте еще раз. Это статистический метод и предполагает конвергенцию. Я не говорю, что я на 100%, это абсолютно правильно, так как я не симулировал, но просто комментарий, который вы сделали, на самом деле не применим по моему мнению. Возможно, это объясняет идею в более общем смысле: если вы принимаете, что произведение полосы пропускания * на задержку отличается для двух ссылок, то одна ссылка фактически будет содержать больше пакетов - и это может быть
обнаружено с помощью алгоритма
Я не думаю, что неправильно понял, но это возможно. Согласны ли вы с тем, что полоса пропускания одинакова, поэтому и A, и B получают данные с одинаковой скоростью? Если это так, не сходятся ли они оба в одно и то же?
Дэвид Ричерби
Да, конечно, они получают с одинаковой скоростью, это не значит, что они сходятся в одном и том же. В сети есть пакеты A и B, вопрос в том, каково соотношение пакетов A и B. Сейчас я провёл простую симуляцию и всё время получаю предвзятость. Чтобы получить представление, поскольку, я думаю, я не могу опубликовать все это здесь, предположим, что b таково, что 1 пакет занимает одну секунду передачи. Тогда всегда есть 4 пакета в пути. Применив алгоритм и бум, нам удалось измерить OTT, избегая методов синхронизированных часов / событий, которые не работают с методами статистической конвергенции!
user3134164
Что такое «доля пакетов A против B»?
Жиль "ТАК - перестать быть злым"
0

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

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

  • R 2 = ( 1 - R 1 ) × ( 1 - P 1 ) 1 - R 2 1 - P 2R1=(1R2)×(1P2) и аналогично . Идея состоит в том, что если робот получает один из своих собственных пакетов, это означает, что другой робот получил его вместо одного из своих собственных (следовательно, ), и что он все еще решил отправить его вместо одного из своих собственных (следовательно, произведение на ).R2=(1R1)×(1P1)1R21P2
  • Это дает систему из двух уравнений с двумя неизвестными, и . Вы можете решить это, но это не имеет значения. Фактически, вы ищете соотношения и . Как вы можете заметить, единственными терминами, которые появляются в этих выражениях, являются вероятности, при которых каждый робот выбирает свой собственный пакет вместо другого. Задержки даже не появляются в формуле просто потому, что оба робота постоянно откачивают пакеты, поэтому оба постоянно получают пакеты. Они действительно будут получать разные соотношения пакетов, но это будет зависеть только от вышеупомянутых вероятностей.R 2 R 1R1R2 R2R11R1R21R2

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

Matrefeytontias
источник
Добро пожаловать в информатику ! Ваш ответ выглядит неплохо, но, как вы заявляете, на самом деле это глубокий комментарий к замечанию @ user3134164. Я думаю, что вы можете решить эту проблему следующими способами: 1) Попробуйте расширить свой ответ так, чтобы это был также ответ на реальный вопрос. или 2) Создайте новый вопрос, в котором, по сути, говорится о неправильном представлении ключа из комментария и самостоятельного ответа пользователя 3134164 с ответом, подобным этому. Какой из них подходит, зависит от вас. Я думаю, что, возможно, создание нового вопроса - хорошая идея, но, возможно, вы можете расширить больше, чем я думаю. Спросите, есть ли у вас дополнительные вопросы.
Дискретная ящерица
Конечно, @ user3134164 также может свободно «продвигать» комментарий в вопрос,
Дискретная ящерица
«Вероятность того, что робот x выберет свои собственные пакеты, когда он получит один из пакетов другого робота» происходит из компьютерной функции random (), как в предположении - например, для пакетов двух типов это всегда будет 0,5. Если функция random () достаточно равномерна, то можно рассчитать «фактическое отношение задержки RTT от A до B». По вашему определению R я думаю, что R1 = (1-R2) * 0,5, так что соотношение известно. Поэтому я все еще верю, что мой ответ работает нормально. Большое спасибо, что нашли время, чтобы разобраться в этом.
user3134164