Синхронизация часов в сети с асимметричными задержками

38

Предположим, что на компьютере установлены точные часы, которые не инициализированы. То есть время на часах компьютера - это реальное время плюс некоторое постоянное смещение. Компьютер имеет подключение к сети , и мы хотим использовать это соединение для определения смещения постоянного .B

Простой способ состоит в том, что компьютер отправляет запрос на сервер времени, отмечая местное время . Сервер времени получает запрос в момент времени и отправляет ответ, содержащий обратно клиенту, который получает его в момент времени . Тогда , т. .B+C1TTB+C2B+C1TB+C2TC2BTC1

Если время передачи по сети и время обработки на сервере симметричны, то . Насколько я знаю, NTP , протокол синхронизации времени, используемый в дикой природе, работает на этом предположении.B=TC1+C22

Как повысить точность, если задержки не симметричны? Есть ли способ измерить эту асимметрию в типичной интернет-инфраструктуре?

Жиль "ТАК - прекрати быть злым"
источник
2
Есть связанный патент, но кто хочет прочитать те ...
Рафаэль
@ Рафаэль Спасибо. Более дружелюбная ссылка Google на патент США 7602873 , официальная ссылка USPTO .
Жиль "ТАК - перестань быть злым"
Первые мысли: это возможно невозможно с 2 сущностями. Используя пары из объектов, лучшая синхронизация возможна. Затем часы могут быть использованы для измерения времени в пути. (n2)n
rgrig
Вы можете уточнить приложение / контекст или это в основном теоретический вопрос?
ВЗН

Ответы:

10

Невозможность измерить асимметрию

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

схема связи

Важно отметить, что с точки зрения как ПК, так и сервера эти два взаимодействия абсолютно идентичны. Они получают сообщения одновременно. Они отправляют сообщения одновременно.

Вы можете создавать больше дел, «захватывая» временную шкалу ПК и «скользя» по ней, удерживая точки отправки / получения сообщений фиксированными относительно их соответствующих временных шкал. Асимметрия, которую вы вызываете, точно сводится на нет смещением часов. Фактически, вы можете даже заставить сообщения отправляться НАЗАД ВРЕМЕНИ в одну сторону (при условии, что время прохождения туда-обратно все равно), а сервер / клиент ЕЩЕ НЕ может сказать!

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

Может ли промежуточная инфраструктура помочь?

Может ли промежуточная инфраструктура помочь, будет сильно зависеть от вашей теоретической модели ситуации.

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

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

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

Крейг Гидни
источник
Это должно быть ответом на ваш вопрос . Здесь я спрашиваю о более конкретной обстановке, где мы можем получить помощь от базовой инфраструктуры.
Жиль "ТАК - перестань быть злым"
Я добавил больше контента для вас.
Крейг Гидни
мне кажется, что это неправильно, и это можно заметить, заметив, что хотя время отправки и получения ПК одинаково (события верхней временной шкалы совпадают в двух случаях), время сервера отличается (нижняя строка в двух случаях) & поэтому формула, рассчитанная клиентом NTP, в обоих случаях различна. это можно лучше значения NTP для в каждом случае (где - значения, записанные во время сервера и отправленные обратно клиенту). как и в моем ответе, протокол времени NTP действительно может измерять и корректировать дляt 2 , t 3 ( t 1 - t 0 ) ( t 3 - t 2 )t1,t2,t3,t4t2,t3(t1t0)(t3t2)
vzn
@vzn Время сервера в отношении t сообщений одинаково в обоих примерах. Временная шкала сервера, перемещающаяся влево, представляет собой начальный дрейф часов, который отличается. Эффекты начального дрейфа тактовой частоты и асимметрии задержки оказываются эквивалентными, поэтому настройка их обоих в противоположных направлениях позволяет результирующему поведению быть эквивалентным.
Крейг Гидни
При дальнейшем изучении клиент / сервер может определить, когда их часы сильно не синхронизированы, по крайней мере, вне времени прохождения сигнала туда и обратно. более подробную информацию можно найти в документе Polyco и др., который я привел ниже, где они измеряют различные «однонаправленные задержки», превышающие неопределенность NTP (которая, по-видимому, меньше, чем время приема-передачи на NTP-серверы, т.е. ~ 10 мс)
vzn
2

Рассмотрим сеть серверов времени , как известно, синхронно, , и клиентская машина .Pθ={A,B,C}P

Пусть будет временем одностороннего полета от машины к машине с возможностью того, что . X Y T X YT Y XTXYXYTXYTYX

Пустьбыть мерой асимметрии между машиной X и Y .ΔXY=|TXYTYX|XY

Теперь предположим, что асимметрия между двумя синхронными машинами может быть измерена, если синхронные машины согласятся отправлять односторонние сообщения друг другу одновременно. Разница во времени прибытия составляет между этими машинами, то есть:Δ

ΔAB=|TABTBA|

ΔBC=|TBCTCB|

ΔCA=|TCATAC|

можно измерить.

Теперь рассмотрим время пролета цепей:

C A BPABP , обозначаемый ,CAB

C B APBAP , обозначается .CBA

CAB=TPA+TAB+TBP

CBA=TPB+TBA+TAP

Рассмотрим клиентскую машину для одновременного запуска обеих этих цепей и измеряем разницу во времени прибытия, :xPx

x=CABCBA=ΔPA+ΔAB+ΔBP

И и известны по ранее упомянутым измерениям, поэтому перемещаем неизвестные в левую часть:Δ БxΔAB

xΔAB=ΔPA+ΔBP

Аналогично, для и можно показать, что:{ C B C , C C B }{CAC,CCA}{CBC,CCB}

yΔBC=ΔPB+ΔCP

zΔCA=ΔPC+ΔAP

Осматривая внимательно, мы отмечаем, что . Левые части содержат значения, известные из измерений, правые части содержат 3 неизвестных в 3 уравнениях.ΔXYΔYX

Решая одновременно,

ΔAP=r+st2

ΔBP=rs+t2

ΔCP=tr+s2

где,

r=xΔAB

s=yΔBC

t=zΔCA

Бинго
источник
Как это обходит проблему, с которой сталкиваются мой ответ и другие?
Рафаэль
Хорошо, для одного я использую 3 подачи времени, не один. И для этого необходимо отправить примерно 12 сообщений: 6 для нахождения асимметрии между серверами времени и 6 для нахождения асимметрии между клиентом и серверами. Это не одномерное пространство решений, поскольку компонент состоит из трех серверов, а не одного. И это не предполагает, что время может вернуться назад.
Бинго
Он сильно зависит от 3 идеально синхронизированных серверов времени, синхронизация которых оставлена ​​читателю в качестве упражнения. ^^
Бинго
APAPPACP,PABP,PBAP,PCAP
0

Если вы контролируете только конечные точки. Ты не можешь Смотри ответ Крейга.

TXY

TAB=TBC=TCA=0ΔAP=ΔBP=ΔCP=0

x=CABCBA=ΔPA+ΔAB+ΔBP

ΔPA=|TPATAP|ΔPA=TPATAP

ΔXYΔYX

Так что ты можешь сделать? Отправить действительно хорошие часы по почте. ;)

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

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

Луис Афонсо
источник
«Вам может понадобиться учесть общую относительность». Нет, не знаю. Я прекрасно согласен с решением, которое работает, только если все задействованные часы находятся в фиксированной рамке. В распределенной системе существует относительность, но она обусловлена ​​латентностью сети, а не физикой. Его математика совершенно другая.
Жиль "ТАК - перестань быть злым"
-1

t0,t1,t2,t3

клиент после получения обратного пакета имеет все 4 значения и вычисляет фактическое смещение. как только относительное смещение вычислено между клиентом и сервером, смещение «абсолютного времени» может быть синхронизировано, т.е. клиент может точно оценить точное смещение сервера, измеренное относительно его локального смещения времени, то есть «дельта».

t0
t1
t2
t3

θ=(t1t0)+(t2t3)2

t1t0t3t2

в сетях время задержки обусловлено двумя основными факторами, в основном задержкой и пропускной способностью.

  • Задержка - это краткая задержка в маршрутизаторах при отправке новых [маленьких] пакетов и примерно одинаковая константа на каждом маршрутизаторе. это можно измерить с помощью утилиты traceroute .
  • Пропускная способность - это скорость, с которой могут отправляться большие объемы данных, например, «загрузка или время загрузки», а также может измеряться удаленными веб-сайтами «измерения пропускной способности».

t1t0t3t2

Основной алгоритм для повышения точности расчета смещения, используемого в NTP (и может корректировать некоторую степень случайной задержки в сети), состоит в том, чтобы повторять процесс несколько раз и использовать «вершину диаграммы рассеяния клина». это можно увидеть на «алгоритме фильтрации часов» на слайде 10 этого PPT по NTP Дэвида Миллса. см. также алгоритм фильтрации часов по Миллсу. (обратите внимание, что он все еще может использоваться между одним сервером и клиентом, хотя общий код написан для нескольких серверов.) Это часть «алгоритмов смягчения», описанных в архитектуре и алгоритмах NTP .

ВЗН
источник
1
Вопрос конкретно о случае, когда задержка не является симметричной. Принимая несколько мер, вы ничего не скажете о постоянной составляющей в асимметрии.
Жиль "ТАК - перестать быть злым"
вопрос на самом деле не содержит слова «латентность». если вы хотите набросать, какой случай вы имеете в виду в математической форме, а не в словах, особенно в реальных формулах NTP, это, безусловно, поможет. формулы и алгоритмы действительно могут измерять / обрабатывать / охватывать различные случаи «задержки» и «асимметрии».
ВЗН
C1C2
C1C2
t1,t2
-3

Если бы мы только могли отправлять пакеты вовремя

введите описание изображения здесь

B=Tf+TbTf2C1+C22

Предположения:

(B+C2)Tb=Tf(B+C1)

Tf(B+C2)=(B+C1)Tb

Пратик Деогхаре
источник
1
Это умное решение исключено предположением о «типичной интернет-инфраструктуре».
Жиль "ТАК - перестань быть злым"
1
@ Жиль, я знаю. : D
Pratik Deoghare
-4

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

N1N2C1C2δ=C1C2d12d21

N1T1mN2T2rC2D

T2rT1m=d12+δT1rT2m=d21δD=d12+d21

δ

1] Я думаю, что предположения являются естественными и необходимыми. Они могут быть оправданы надеждой, что соответствующие величины не изменятся слишком сильно в течение нашей попытки синхронизации.

Рафаэль
источник
(d12+δ)+(d21δ)(d12+d21)=0
@ Жиль Слишком плохо. Возможно, нам следует оставить один случай заблуждения на всеобщее обозрение?
Рафаэль
1
Я могу восстановить неправильный ответ, который я написал. Это может быть полезно из-за комментариев, сделанных Жилем.
Ран Г.