Network Time Protocol(NTP)
Протокол сетевого
времени

Дэвид Л.Милс

Университет в Делаваре

http://www.eecis.udel.edu/~mills

Перевел с англ. В.Н. Черненков

САО РАН

http://www.sao.ru/hq/vch

Введение

Network Time Protocol (NTP) синхронизирует системные часы компьютеров и маршрутизаторов в Интернете

Более чем 100,000 NTP серверов (peers) взаимодействуют во всем мире благодаря Интернет

Позволяет установить номинальную точность менее десятков миллисекунд в глобальной сети (WAN), субмиллисекундную в локальных сетях (LANs) и субмикросекундную, если используется прецезионный источник времени, такой как цезиевый стандарт или GPS приемник

Unix NTP-демон портирован в большинство серверных платформ и рабочих станций, на сегодняшний день - от PC до Cray - Unix, Windows, VMS, а так же встроенных систем

Излагается обзор архитектуры NTP, собственно протокола и алгоритмов

1997 год внедрения разработок NTP - клиентов и серверов в Интернет

Необходимость в синхронизации времени

Оформление биржевых сделок требует точного времени регистрации

События в сети типа обрывов и восстановления требуют ведения журналов с привязкой ко времени

Сетевой мониторинг, измерения и управление сетями

Синхронизация времени в отслеживании расписаний мультимедийного сетевого вещания

Процедуры удаленных запросов (RPC) типа “все в одной” транзакции; обработка защитных ответов; устранение неопределенности номера запросной последовательности

Исследования, экспериментальные установки, измерения и управление

Управление криптографическими ключами, их временем жизни и т.п.

NTP краткое резюме

Первичные (stratum 1) серверы синхронизированы национальными стандартами времени по радио, через спутники и модемы

Вторичные (stratum 2, ...) серверы и клиенты синхронизированы первичными серверами через иерархию подсетей

Клиенты и серверы оперируют в ведущей/ведомой (master/slave), симметричной или в мультикастовой модах с, или без криптографической аутентификации

Надежность, гарантированная резервными серверами и доступом по разным сетевыми путям

Разработанные алгоритмы сокращают фазовое дрожание (jitter), смягчают факторы наличия множества источников и отклоняют ошибочно функционирующие серверы

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

Конфигурации NTP

(a) Рабочие станции используются в мультикастовой моде с множествам серверов подразделения

(b) Серверы подразделения используют клиент/сервер моды с множеством кампусных серверов и симметричные моды друг с другом

(c) Кампусные серверы используют клиент/сервер моды с шестью верхними различными внешними первичными серверами, а также симметричные моды с остальными вторичными (равноправными) серверами

S3

S3

S3

S2

S2

S2

S2

S4

S3

S3

*

*

Рабочая станция

(a)

S1

S1

S1

S1

S2

*

*

S1

S1

*

* к коллегам (S2)

S2

S2

Клиенты

(c)

Клиенты

(b)

Как NTP работает

Множество синхронизирующих равноправных членов (peers) обеспечивают устойчивость и надежность

Фильтры выбирают лучшие часы в окне из восьми выборок смещений

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

Комбинированный алгоритм вычисляет взвешенное среднее и смещение для наилучшей точности привязки

Фазо/частотный (phase/frequency-lock) цикл обратной связи (ФАПЧ ОС) подводит время локальных часов (СЧ) и их период к максимуму точности и стабильности

NTP сообщения

Peer 1

Peer 2

фильтр 1

Peer 3

фильтр 2

фильтр 3

Алгоритмы пересече-ния и кластеризации

Алгоритм объедине-ния

Фильтр обр. связи

СЧ

Timestamps

ФАПЧ ОС

Процесс декомпозиции NTP (NTPv4)

Каждый равноправный член (peer) ассоциации имеет независимый процесс опроса через интервал (poll), определяемый системным процессом удаленного сервера

Системный процесс запускает poll-интервалы, длительностью, определяемой величиной сетевого дрожания фазы и стабильностью частоты генератора локальных часов (СЧ)

Процесс коррекции часов (сlock adjust) устанавливает первичный интервал повода часов коррекцией фазы и периода синтезатора частоты (СЧ)

удаленные серве-ры

Peer 1

Peer 2

фильтр 1

Peer 3

фильтр 2

фильтр 3

Алгоритмы селекции и кластеризации

алгоритм объедине-ния

Фильтр цикла

СЧ

Clock Adj. Proc.

Системный процесс

Peer
процессы

NTP обработка данных

Для каждого сервера вычисляется переменная смещения времени сервера , задержка  и дисперсия  времени относительно корневого (root) субдерева синхронизации

С каждым принимаемым сообщением NTP peer-процесс обновляет смещение каждого члена ассоциации задержкудисперсию и ошибку фильтрации r (NTPv4), сравнивая метку времени во входном пакете и показания часов согласно алгоритму часового фильтра

В системных poll-интервалах с помощью алгоритма выборки и объединения часов обновляются системные переменные ,  and

Дисперсии и  изменяются со временем в зависимости от величины стабильности стандарта частоты 

Серв 1



Серв 2



Peer 1



Серв 3



Peer 2



Peer 3



Алгорит-мы выборки и объединения

Сист



T1

T3

T2

T4

Наибольшее смещение точности  будет измерено при наименьшей задержке  (острие клина диаграммы рассеянья -- scattergram).

Скорректированное время  должно заключаться внутри клина 

 есть минимальное среднее из восьми последних измерений задержек (, и смещений годных для выходных данных.

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

Метрика дистанции  основана на задержке, частотной стабильности и времени с начала измерений.

Серв

Клиент

Алгоритм фильтра часов

x

0

Эффективность алгоритма фильтра часов

Графики показывают абсолютные смещения часов в полулогарифмических координатах при синхронизации между восточным и западнывм побережьями США в течение шести суток

(левый) входные отсчеты абсолютных смещений

(правый) отсчеты смещений на выходе фильтра часов

Алгоритм уменьшает ошибки смещения примерно в десять раз

Алгоритм частично эффективен для удаления выбросов

Correct NTP

Correct DTS

Алгоритм перекресечения

Некорректированный интервал DTS есть пересечение, содержащее общие точки от наибольшего числа некорректированных интервалов

NTP алгоритм выбирает середину одного из интервалов в пересечении

Сначала , устанавливается число f, число c и d равными нулю

Перебор от дальней левой конечной точки: добавление единицы к c для каждой меньшей конечной точки, вычитание единицы для каждой большей конечной точки, добавление единицы к d для каждой серединной точки

для c m  f и d m  f, объявляется завершением и выходом из процедуры

То же самое, но старт от дальней правой конечной точки

если предыдущий процесс не завершен, увеличиваем f на единицу и пробуем повторить все сначала

если f m/2, объявляем сбой

C

A

B

D

некорректированный интервал =

m = общее число часов

f = предполагаемое число ложных

A, B, C правильные

D ложные

no

yes

Алгоритм кластеризации

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

Пусть выбраны smax член с максимумом выборочной дисперсии ( относительно всех других) и smin член с минимумом дисперсии (относительно различия часов после выборки соответствующего члена).

smax  smin or n nmin

Удаление члена smax; уменьшение n на единицу

Оставшиеся участники, вычисленные по алгоритмом смешивания для использования в расчете окончательного смещения как взвешенного среднего от них

Сортировка оставшихся после алгоритма пересечения дистанций синхронизации.

Пусть n означает их общее число и nmin –минимальное значение.

Обозначения для совокупной ошибки

Системные переменные
смещение часов
root задержка
root дисперсия
s	выборочный життер
	джиттер
	интервал от последнего обновления

Peer - переменные
смещение часов
круговая задержка
дисперсия
r	джиттер фильтра n	стадия фильтрации: 8
	iинтервал от последнего обновления

Константы (peers A and B)
максимальная ошибка чтения
 максимальная частотная ошибка
w дисперсия по уровню: 0.5

Переменные пакета
B	peer root задержка
B	peer root дисперсия

Переменные выборки
T1, T2, T3, T4 временные метки по протоколу (timestamps)
x	смещение часов
y	круговая задержка
z	дисперсия
	интервал от последнего обновления

Вычисление совокупной ошибки





Переменные выборки

Peer - переменные

Peer A

Системные переменные



Peer B

NTP Version 4 совокупная ошибка

Алгоритм подвода часов

Vd

Vc

Ф/Ч предска-зание

Фильтр часов

Повод часов

Фазовый детектор

С

Vs

r+

c

NTP

Фильтр обратной связи

Vd функция разницы фазы между NTP и синтезатором (С)

Vs определяет степень подгонки в сдвиговом регистре часового фильтра

x и y обновления фазы и частоты, относительно, вычисленной функции предсказания

Процесс подвода часов запускается ежесекундно для вычисления Vc, которое управляет частотой локального синтезатора

Фаза синтезатора частоты сравнивается с NTP фазой, замыкая тем самым цепь обратной связи (ФАПЧ)

x

y

Форматы шапки и временной метки NTP протокола

Strat

Poll

LI

Mode

VN

NTP v3 и v4

Root задержка

Root дисперсия

Относительный идентификатор

Относительный Timestamp (64)

Исходный Timestamp (64)

Принятый Timestamp (64)

Переданный Timestamp (64)

Хэш сообщения (64 or 128)

NTP -шапка (32 bits)

LI	признак скачка

VN	номер версии (4)

Strat	стратум (0-15)

Poll	полл интервал (log2)

Prec	точность (log2)

Секунды (32)

доли сек. (32)

NTP Timestamp Format (64 bits)

Значение в секундах и долях

начиная с 0h 1 января 1900

Аутентификатор при использовании DES-CBC or MD5 криптосистемы

NTP шапки плюс расширение полей (NTPv4)

Key/Algorithm идентификатор

Криптоподпи-сано

Аутентификатор

(опционно)

Расширенное Поле 1 (опционно)

Расширенное Поле 2… (опционно)

NTP v4

Prec

Поле расширения

( дополненное до 32-bit границы)

Длина поля

Тип поля

Поле NTPv4 - расширения

Последнее поле дополненное до 64-bit границы

только аутентификация

День загруженного NTP-сервера

Первичный NTP (stratum 1) типовой сервер Sun IPC с SunOS 4.1.3 и поддержкой 734 клиентов, разбросанных по всему миру

Машина с NFS, NTP, RIP, IGMP кучей принтеров, радио-часами и 8-портовым сериал-мультиплексором

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

Каждый входной пакет генерирует 0.64 выходных пакета и требует всего of 2.4 мс процессорного времени для транзакции ввода/вывода

В общем, NTP сервис требует 1.54% процессорного времени и генерирует 10.5, 608-bit пакетов в секунду, или загружает 0.41% лини T1

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

Популяции серверов по стратуму(из исследования)

Популяции клиентов по стратуму (из исследования)

Источники привязки часов

В исследовании 36,479 членов найдено 1,733 первичных и запасных внешних источников

231 радио/спутниковых/модемных первичных источников

47 GPS спутниковых (глобальных), GOES спутниковых (стран запада)

57 WWVB радио (США)

17 WWV радио (США)

63 DCF77 радио (Европа)

6 MSF радио (Англия)

5 CHU радио (Канада)

7 модем тайм-сервисных (NIST и USNO (США), PTB (Германия), NPL (Англия))

25 других (точные PPS источники, и др.)

1,502 локальных запасных источников (используемых только при неисправных всех остальных)

По разным причинам, 88 из 1,733 источников оказались недоступными во время исследования

Текущее состояние и развитие

NTP Version 4, архитектура и алгоритмы

Алгоритм обратной совместимости реализован и оттестирован.

Завершена и оттестирована усовершенствованная модель локальных часов.

Просимулирована точность времени в Nanokernel-модификации ядра, реализована и протестирована со SPARC, Alpha и Intel архитектурами.

Реализован и оттестирован IETF pulse-per-second интерфейс прикладных программ для SPARC и Intel архитектур.

Самонастраивающаяся конфигурация (autoconfigure)

Мультикаст-исследование сети с с распространением коррекции реализовано и тестируется.

Мэникаст-исследование сети в значительной степени реализовано.

Распределенная add/drop распространяющаяся эвристика разработана и просимулирована.

Интервально ограниченные, иерархические группы использования NTP в распределенной моде и add/drop эвристики в процессе изучения.

Самонастраивающийся аутентификационный ключ (autokey)

Реализован и в тестировании.

Планы на будущее

Завершение реализации автоконфигурации и автогенерации ключа в NTP Version 4

Размещение, опробование и тестирование NTP Version 4 демона в DARTnet II системе отладки, на дружественных сайтах США, Европы и Азии

Пересмотр формальной спецификации NTP и и начало нового профиля стандартов

Участие в стратегии подключения с NIST, USNO, другими

Внесение стандартов в обсуждение в IETF, ANSI, ITU, POSIX

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

NTP онлайн-ресурсы

NTP спецификация и документы

Internet (Draft) NTP стандартная спецификация RFC-1305

Simple NTP (SNTP) RFC-2030

NTP Version 4 документы и отчеты http://www.eecis.udel.edu/~mills

В обсуждении ANSI, ITU, POSIX

NTP веб страничка http://www.ntp.org/

NTP Version 3 и Version 4 софт и HTML документация

Программные утилиты для удаленного мониторинга, управления и оценки производительности

Портирование на разные архитектурные платформы свыше двух десятков ОС

Поддерживаемые ресурсы

Список публичных NTP тайм серверов (первичные и вторичные)

NTP новостная группа и сборник FAQ

учебные материалы, советы и библиография

Ссылки на другой NTP софт

Дополнительная информация

Network Time Protocol (NTP): http://www.ntp.org/

Текущие NTP Version 3 and 4 софт и документы

FAQ и ссылки на другие источники, представляющие интерес

David L. Mills: http://www.eecis.udel.edu/~mills

Статьи, отчеты и меморандум в PostScript and PDF форматах

Доклады в HTML, PostScript, PowerPoint и PDF форматах

Ссылки на совместно разработанные ресурсы по аппаратуре, софту и документам

Записи речей, фото-галерея

FTP сервер ftp.udel.edu (pub/ntp directory)

Репозититорий софта и документов для текущих NTP Version 3 и 4

Репозиторий совместных ресурсов

В отношении описаний проекта исследований

смотри “Current Research Project Descriptions and Briefings” на http://www.eecis.udel.edu/~mills/status.htm

Network Time Protocol (NTP) General Overview

David Mills

2005-04-13T15:19:49