Сетевой протокол времени NTP

Время — самый важный и невосполнимый ресурс любого человека. Проблема эта занимала людей всегда, и уже более 4 тысяч лет они пытаются как-то упорядочить учет расходования этого ресурса, создавая различные календарные системы и устройства измерения времени. Календарные системы древнего мира отражали сельскохозяйственные, политические и ритуальные нужды, характерные для того времени. Астрономические наблюдения для установления зимнего и летнего солнцестояния производились еще 4000 лет тому назад. Проблема создания календаря возникала только в обществах, где государственная стабильность поддерживалась в течение достаточно долгого времени (Китай, Египет, государство майя). В 14-ом столетии до Рождества Христова в Китае была определена длительность солнечного года — 365.25 дней и лунного месяца — 29.5 дней. Солнечно-лунный календарь действовал на ближнем востоке (за исключением Египта) и в Греции, начиная с 3-го тысячелетия до нашей эры. Ранние календари использовали либо 13 лунных месяцев по 28 дней, либо 12 месяцев с чередующейся протяженностью 29 и 30 дней.

Древнеегипетский календарь имел 12 30-дневных лунных месяцев, но был привязан к сезонному появлению звезды Сириус (sirius — sothis). Для того, чтобы примирить этот календарь с солнечным годом, был изобретен гражданский календарь, в котором добавлено 5 дней, доводящих длительность года до 365 дней. Однако со временем было замечено, что гражданский год примерно на одну четверть дня короче, чем солнечный год. Выбранная длительность года обеспечивала полное совпадение с солнечным годом раз за 1460 лет. Этот период называется циклом Сотиса (sothic-цикл). Так же, как и китайцы, древние египтяне установили длительность солнечного года равной 365,25 дней, что с точностью 11 минут совпадает с результатами современных вычислений. В 432 году до рождества Христа, почти на сто лет позже китайцев, греческий астроном Метон вычислил, что 110 лунных месяцев по 29 дней и 125 лунных месяцев по 30 дней соответствуют 6940 солнечным дням, и это лишь немного превышает 19 лет. 19-летний цикл, названный циклом Метона, установил длительность лунного месяца равной 29,532 солнечных дней, что с точностью до 2 минут совпадает с результатами современных измерений.

В древнем Риме использовался лунный календарь. Юлий Цезарь пригласил александрийского астронома Сосигенса, который разработал календарь (по понятным причинам называнный юлианским), принятый в 46 году до Рождества Христова. Календарь содержал 365 дней в году с добавлением одного дня каждые 4 года. Однако первые 36 лет по ошибке дополнительный день добавлялся каждые три года. В результате набежало лишних три дня, которые пришлось компенсировать вплоть до 8 года нашей эры.

Семидневная неделя была введена лишь в четвертом столетии нашей эры императором Константином I.

Во время романской эры 15-летний цикл переписи использовался при исчислении налогов. Последовательность имен дней недели воспроизводится через 28 лет, этот период называется солнечным циклом. Таким образом, учитывая 28-летний солнечный цикл, 19-летний цикл Метона и 15-летний переписи, получаем суперцикл протяженностью 7980-лет, называемый юлианской эрой, которая начинается в 4713 году до Рождества Христова.

К 1545 году расхождение между юлианским календарем и солнечным годом достигло 10 дней. В 1582, астрономы Кристофер Клавиус и Луиджи Лилио предложили новую схему календаря. Папа Григорий XIII выпустил буллу, в которой среди прочего указывалось, что в году содержится 365.2422 дней. Для того, чтобы более точно аппроксимировать эту новую величину, только столетние годы, которые делятся без остатка на 400, объявляются високосными, что предполагает длительность года 365,2425 дней. В настоящее время григорианский календарь принят большинством стран мира.

Но чтобы мерить расширение вселенной или распад протона, необходимо ввести стандартную схему нумерации дней. По решению Международного астрономического Союза был принят стандарт секунды и юлианская система нумерации дней (jdn). Стандартный день содержит 86,400 стандартных секунд, а стандартный год состоит из 365,25 стандартных дней.

В схеме (JDN), предложенной в 1583 французским ученым Джозефом Юлиусом Скалигером, JDN 0.0 соответствует 12 часам (полдень) первого дня юлианской эры — 1 января 4713 до нашей эры. Годы до нашей эры подсчитываются согласно юлианскому календарю, в то время как годы нашей эры нумеруются по календарю григорианскому. 1 января 1 года после Рождества Христова в григорианском календаре соответствует 3 января 1 года юлианского календаря [DER90], в JDN 1.721.426,0 день соответствует 12 часам первого дня нашей эры.

Эталоном времени может стать любой циклический процесс с достаточно стабильным периодом. Для измерения времени сначала использовали солнечные часы (Вавилон, 3,5 тысячи лет назад), которые были пригодны только днем при безоблачном небе. Им на смену пришли водяные часы, способные работать круглые сутки (если позволял объем сосуда). Позднее были изобретены песочные часы (появились примерно тысячу лет назад), которые могли обеспечить точность около 15-20 минут за сутки. Именно от этого типа часов пошла морская единица измерения времени — "склянки". Революцию в сфере измерения времени вызвало изобретение механических часов (Вестминстерские куранты 1288 год). Первые часы с маятником были изготовлены Х. Гюйгенсом в 1657 году, через 13 лет был изобретен анкерный механизм. Механическим хронометрам человечество обязано великим географическим открытиям 18 века (Дж. Кук). Первые часы с использованием электричества был разработаны А. Бейном в 1840 году, а первые кварцевые часы увидели свет в 1918 году. В 1937 году кварцевые часы Л.Эссена были установлены в Гринвичской лаборатории (GMT), они имели точность 2 мсек в сутки. В 1944 году радиостанция BBC стала передавать сигналы точного времени с погрешностью около 0,1 мсек/сутки. Сейчас кварцевые часы можно увидеть на запястьях людей и в любом компьютере. Первые атомные часы были изготовлены в 1949 году. Без этих технологических свершений технический прогресс 20-го века был бы невозможен. Кварцевые часы побывали в космосе и на Луне.

В 1967 году был принят цезиевый (Cs¹³³) стандарт времени, где одна секунда соответствует 9192631770 периодам перехода между уровнями в атоме цезия UTC (Universal Time Coordinated). UTC почти в миллион раз точнее астрономического среднего времени по Гринвичу. Ошибка UTC составляет менее 0,3 нсек/сутки.

Не исключено, что со временем эталоном времени станет излучение миллисекундного пульсара (открыт в 1982 году), имеющего период 1,55780645169838 миллисекунды. Этот пульсар предположительно имеет массу Солнца, радиус 10 км и вращается со скоростью 642 оборота в секунду.

С 1 января 2001 года английским правительством было официально объявлено о новом стандарте времени Grinwich e-time (GET), который будет использоваться для обеспечения глобальных электронных платежей через Интернет.

Для оценки времени природа снабдила человека, как и некоторых других живых существ, так называемыми биологическими часами. Эти часы отсчитывают циклы длительностью около 24 часов. У нас, правда, есть природный генератор — это сердце, с периодом около 1 секунды. За отсчет времени ответственен теменной участок коры больших полушарий мозга. Механизмы оценки коротких временных интервалов и упорядочение наших жизненных событий происходят разными способами. Но эти механизмы хороши, пожалуй, лишь для определения времени обеда.

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

Сетевой протокол задания времени NTP (Network Time Protocol Version 3 Specification, Implementation and Analysis, David L. Mills, RFC-1305, March 1992) служит для осуществления синхронизации работы различных процессов в серверах и программах клиента. Он определяет архитектуру, алгоритмы, объекты и протоколы, применяемые для указанных целей. NTP был впервые определен в документе RFC-958 [MIL85c], но с тех пор несколько раз переделан и усовершенствован (RFC-1119 [MIL89]). Протокол использует для транспортных целей UDP [POS80]. Целью протокола является обеспечение максимально возможной точности и надежности, несмотря на значительный разброс задержек при прохождении через большое число промежуточных маршрутизаторов.

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

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

Существует ряд механизмов в Интернет, которые позволяют передавать и записывать время, когда произошло какое-то событие. Это протокол daytime [POS83a], time protocol [POS83b], сообщения ICMP "временная метка" [DAR81b] и опция IP "временная метка" [SU81].

Юниксовский (4.3BSD) времязадающий демон [GUS85a] измеряет временные сдвиги различных клиентских процессов и рассылает им соответствующие поправки.

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

Архитектура системы

(рис 7.1)

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

Под стабильностью подразумевается степень постоянства задающей частоты часов, а под точностью — соответствие этой частоты национальным стандартам времени. Если не указано обратного, под временным сдвигом между часами подразумевается разница показаний этих часов, в то время как под сбоем (skew) подразумевается различие их рабочих частот (первая производная). Настоящие часы имеют конечную стабильность частоты (вторая производная не равна нулю). Нестабильность частоты называется дрейфом, но в рамках протокола NTP дрейф предполагается равным нулю.

Протокол NTP создан с целью определения трех величин: смещения часов (clock offset), RTT и дисперсии; все они вычисляются по отношению к выбранным эталонным часам. Смещение часов определяет поправку, которую необходимо внести в показания местных часов, чтобы результат совпал с показанием эталонных часов. Дисперсия характеризует максимальную ошибку локальных часов по отношению к эталонным.

В протоколе NTP нет средств для нахождения партнера или управления. Целостность данных обеспечивается с помощью IP и UDP контрольных сумм. Система может работать в симметричном режиме, когда сервер и клиент неразличимы, и в режиме клиент-сервер, где сервер выполняет только то, что требует клиент. Используется только один формат сообщений NTP. В рамках модели необходимо определить минимально возможную частоту коррекций часов, обеспечивающую требуемую временную точность.

Реализация модели

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

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

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

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

Конфигурации сети

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

Следуя принципам, принятым в телефонной промышленности, точность каждого сервера определяется номером слоя (stratum), наивысший уровень (для первичного сервера) имеет номер 1. На современном уровне технологий (радио-часы) точность однократной сверки имеет порядок одной миллисекунды.

Точность однократной сверки падает по мере роста значения RTT и его разброса. Для того, чтобы избежать сложных расчетов [BRA80], необходимых для оценки точности в каждом конкретном случае, полезно предположить, что средняя ошибка измерения пропорциональна RTT и ее дисперсии. Предполагая, что первичные серверы синхронизованы стандартами времени с известной точностью, можно получить вполне надежную оценку точности синхронизации субсети.

Дополнительным фактором является то, что каждый переход от одного слоя к другому предполагает наличие ненадежного сервера времени, который вносит дополнительные ошибки. Алгоритм выбора серверов времени использует разновидность алгоритма маршрутизации Беллмана-Форда, при этом формируется дерево минимальных весов, основанием которого являются первичные серверы. Метрикой расстояния служит номер слоя плюс расстояние синхронизации, которое характеризуется суммой дисперсии и половины абсолютного значения задержки.

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

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

Форматы данных

Все арифметические операции в рамках протокола выполняются в формате с фиксированной запятой. По этой причине все переменные в NTP имеют именно этот формат. Биты пронумерованы слева направо (со старшего бита), начиная с нуля. Жестких требований на число разрядов после запятой не установлено. Если не оговорено обратного, все числа не имеют знака и занимают всё отведенное для них поле (при необходимости в качестве заполнителей старших разрядов используются нули).

Временные метки NTP представляют собой 64-битные числа с фиксированной запятой без знака, которое указывает число секунд с нуля часов 1-го января 1900 года. Целая часть содержит первые 32 разряда, а дробная часть — остальные 32 разряда. Этот формат не совпадает с форматом меток ICMP, где время измеряется в миллисекундах. Точность представления составляет 200 пикосекунд, что должно удовлетворить самым экзотическим требованиям.

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

Заметим, что с 1968 года старший бит (бит 0 целой части) равен единице, а где-то в 2036 году 64-битовое поле переполнится.

Переменные состояния и параметры

Ниже приводится обзор различных переменных и параметров, используемых протоколом. Они распределены по классам системных переменных, которые имеют отношение к операционной среде и механизму реализации местных часов. Сюда входят переменные партнеров, которые характеризуют состояние протокольных машин участников обмена, переменные пакетов, описывающие содержимое пересылаемых NTP -сообщений, а также параметры, задающие конфигурацию текущей версии программного обеспечения. Имена переменных записываются строчными буквами, а имена параметров — прописными.

Общие переменные

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

Адрес партнера ( peer.peeraddr, pkt.peeraddr ), порт партнера ( peer.peerport, pkt.peerport ). 32-битный IP-адрес и 16-битный номер порта партнера.

Адрес ЭВМ ( peer.hostaddr, pkt.hostaddr ), порт ЭВМ ( peer.hostport, pkt.hostport ). 32-битный IP-адрес и 16-битный номер порта ЭВМ. Эти переменные включаются в переменные состояния для поддержки мультиинтерфейсных систем.

Индикатор приращения ( sys.leap, peer.leap, pkt.leap ) — это двухбитный код предупреждения о включении дополнительных секунд во временную шкау NTP. Эти биты устанавливаются до 23:59 дня добавления и сбрасываются после 00:00 следующего дня. В результате день, для которого проведена эта процедура, окажется длиннее или короче на одну секунду. Для вторичных серверов эти биты устанавливаются протоколом NTP. Биты 0 и 1 ( LI ) принимают значения, перечисленные в таблице 7.1.

Значения кодов индикатора LI

LI	Величина	Значение
00	0	предупреждения нет
01	1	последняя минута содержит 61 секунду
10	2	последняя минута содержит 59 секунд
11	3	аварийный сигнал (часы не синхронизованы)

Во всех случаях, за исключением аварийного сигнала (alarm = 112), протокол NTP никак не изменяет эти биты, а только передает их программам преобразования времени, которые не являются частью протокола. Аварийная ситуация возникает, когда по какой-либо причине локальные часы оказываются не синхронизованными. Это может случиться в ходе инициализации системы или в случае, когда первичные часы оказываются недоступны в течение длительного времени.

Режим ( peer.mode, pkt.mode ) — это целое 3-битовое число, обозначающее код режима ассоциации, который может принимать значения, приведенные в таблице 7.2.

Значения кодов Режим

Режим	Значение
0	Зарезервировано
1	симметричный активный
2	симметричный пассивный
3	Клиент
4	Сервер
5	широковещательный
6	для управляющих сообщений NTP
7	зарезервировано для частного использования

Слой ( sys.stratum, peer.stratum, pkt.stratum ) — это целое число, указывающее код слоя локальных часов, который может принимать значения, приведенные в таблице 7.3.

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

Слой	Значение
0	Не специфицирован или недоступен
1	Первичный эталон (например, радио-часы)
2-15	Вторичный эталон (через NTP или sntp)
16-255	Зарезервировано на будущее

Для целей сравнения значение нуль для кода слоя считается выше, чем любая другая величина. Заметим, что максимальное значение целого, закодированное как пакетная переменная, ограничено параметром ntp.maxstratum.

Период обмена ( sys.poll, peer.hostpoll, peer.peerpoll, pkt.poll ). Это целая переменная со знаком, которая указывает минимальный интервал между передаваемыми сообщениями, измеренный в секундах и представленный как степень 2. Например, значение 6 указывает на минимальный интервал в 64 секунды.

Точность ( sys.precision, peer.precision, pkt.precision ). Это целая переменная со знаком, обозначающая точность часов в секундах и выраженная как ближайшая степень числа 2. Значение должно быть округлено в большую сторону до ближайшего значения степени 2, например, сетевой частоте 50-Гц (20 мс) или 60-Гц (16.67 мс) будет поставлена в соответствие величина -5 (31.25 мс), в то время как кварцевой частоте 1000-Гц (1 мс) будет поставлено в соответствие значение -9 (1.95 мс).

Базовая задержка ( sys.rootdelay, peer.rootdelay, pkt.rootdelay ). Это число с фиксированной запятой со знаком, которое указывает на величину полной циклической задержки (RTT) до первичного эталона частоты, выраженной в секундах.

Базовая дисперсия ( sys.rootdispersion, peer.rootdispersion, pkt.rootdispersion ). Это число с фиксированной запятой больше нуля, указывающее на максимальное значение временной ошибки по отношению к первичному эталону в секундах.

Идентификатор эталонных часов ( sys.refid, peer.refid, pkt.refid ). Это 32-битовый код, идентифицирующий конкретные эталонные часы. В случае слоя 0 (не специфицирован) или слоя 1 (первичный эталонный источник), это 4-октетная ASCII-строка, выровненная по левому краю и дополненная при необходимости нулями, например:

Коды идентификаторов часов

Слой	Код	Значение
0	dcn	Протокол маршрутизации dcn
0	dts	Цифровая служба времени (digital time service)
0	nist	Общий модем nist
0	tsp	Временной протокол tsp
1	atom	Атомные часы (калиброванные)
1	vlf	vlf-радио (omega, и пр.)
1	callsign	Общее радио
1	gps	gps УВЧ позиционирование спутников
1	lorc	loran-c радионавигация
1	wwvb	Радио wwvb НЧ (диапазон 5)
1	goes	Спутник goes УВЧ (диапазон 9)
1	wwv	Радио wwv ВЧ (диапазон 7)

В случае слоя 2 и выше (вторичный эталон) — это 4-октетный IP-адрес партнера, выбранного для синхронизации.

Эталонная временная метка ( sys.reftime, peer.reftime, pkt.reftime ) — локальное время в формате временных меток, соответствующее моменту последней коррекции показаний часов. Если локальные часы не были синхронизованы, переменная содержит нуль.

Базовая временная метка ( peer.org, pkt.org ) — локальное время в формате временных меток, соответствующее моменту посылки последнего NTP -сообщения. Если партнер недостижим, переменная принимает нулевое значение.

Временная метка получения ( peer.rec, pkt.rec ) — локальное время в формате временных меток, которое соответствуюет моменту прихода последнего NTP -сообщения, полученного от партнера. Если партнер недостижим, переменная принимает нулевое значение.

Временная метка передачи ( peer.xmt, pkt.xmt ) — локальное время в формате временных меток, соответствующее моменту отправки NTP -сообщения.

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

Следующие переменные используются операционной системой для синхронизации локальных часов.

Переменная локальные часы ( sys.clock ) содержит показание локальных часов в формате временных меток. Локальное время получается от аппаратных часов конкретной ЭВМ и дискретно увеличивается с конструктивно заданными приращениями.

Переменная Базовые часы ( sys.peer ) представляет собой селектор, идентифицирующий используемый источник синхронизации. Обычно это указатель на структуру, содержащую переменные партнера. Значение нуль указывает, что в настоящее время источник синхронизации отсутствует.

Переменные партнера

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

Бит конфигурации ( peer.config ) — бит, индицирующий, что ассоциация была сформирована на основе конфигурационной информации и не должна быть расформирована, когда партнер становится недоступен.

Временная метка актуализации ( peer.update ) — локальное время в формате временной метки, отмечающее момент, когда было получено последнее NTP сообщение. Переменная используется для вычисления дисперсии временного сдвига.

Регистр достижимости ( peer.reach ) — сдвиговый регистр битов ntp.window, используемых для определения статуса достижимости партнера. Ввод данных производится со стороны младших бит (справа). Партнер считается достижимым, если как минимум один бит этого регистра равен 1.

Таймер партнера ( peer.timer ) — целочисленный счетчик, используемый для управления интервалом между последовательно посылаемыми NTP -сообщениями. После установки значения счетчика его содержимое уменьшается на 1 (1сек), пока не достигнет нуля. При этом вызывается процедура передачи. Заметим, что работа этого таймера не должна зависеть от локальных часов.

Пакетные переменные

Номер версии ( pkt.version ) — целое число, индицирующее номер версии отправителя. NTP -сообщения всегда посылаются с текущим значением версии ntp.version и будут восприняты лишь при условии совпадения кодов версии ( ntp.version ). Исключения допускаются лишь при смене номера версии.

Переменные фильтра часов

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

Регистр фильтра ( peer.filter ) — сдвиговый регистр каскадов ntp.shift, где каждый каскад запоминает значения измеренной задержки, смещения и вычисленной дисперсии, соответствующих одному наблюдению. Эти три параметра вводятся со стороны старших разрядов и сдвигаются в направлении младших разрядов (направо). При получении результатов нового наблюдения старые результаты теряются.

Счетчик корректных данных ( peer.valid ) — целочисленный счетчик, указывающий на корректные образцы, остающиеся в регистре фильтра. Он используется для определения состояния доступности и для управления увеличением и уменьшением периода рассылки сообщений.

Смещение ( peer.offset ) — число с фиксированной запятой со знаком, индицирующее значение смещение часов партнера по отношению к локальным часам в секундах.

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

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

Параметры

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

Номер версии ( ntp.version ) — текущий номер версии NTP (3).

Порт NTP ( ntp.port ) — стандартный номер порта (123), присвоенный протоколу NTP.

Максимальный номер слоя ( ntp.maxstratum ) — максимальный номер слоя, который может быть использован при кодировании пакетной переменной. Этот параметр обычно интерпретируется как определение бесконечности (недостижимости для протокола маршрутизации в субсети).

Максимальный возраст часов ( ntp.maxage ) — максимальный интервал в секундах, в течение которого эталонные часы будут рассматриваться как корректные после последней сверки.

Максимальный сбой ( ntp.maxskew ) — максимальная ошибка смещения, связанная со сбоем локальных часов за время ntp.maxage, в секундах. Отношение ntp.maxskew к ntp.maxage интерпретируется как максимальный сбой, вызванный всей совокупностью факторов.

Максимальное расстояние ( ntp.maxdistance ) — максимально допустимое расстояние между партнерами при синхронизации с использованием алгоритма отбора.

Минимальный период рассылки ( ntp.minpoll ) — минимальный период рассылки, допустимый для любого из партнеров в сети Интернет. Этот период выражается в секундах и представляет собой степень 2.

Максимальный период рассылки ( ntp.maxpoll ) — максимальный период рассылки, допустимый для любого из партнеров в сети Интернет. Этот период выражается в секундах и представляет собой степень 2.

Минимум избранных часов ( ntp.minclock ) — минимальное число партнеров, необходимое для синхронизации (при использовании алгоритма отбора).

Максимум избранных часов> ( ntp.maxclock ) — максимальное число партнеров, необходимое для организации отбора (при использовании алгоритма селекции).

Минимальная дисперсия ( ntp.mindisperse ) — минимальное значение приращения дисперсии для каждого из слоев в секундах (при использовании алгоритма фильтрации).

Максимальная дисперсия ( ntp.maxdisperse ) — максимальная дисперсия в секундах с учетом потерянных данных (при использовании алгоритма фильтрации).

Размер регистра доступности ( ntp.window ) — размер регистра доступности ( peer.reach ) в битах.

Размер фильтра ( ntp.shift ) — размер сдвигового регистра фильтра часов ( peer.filter ) в каскадах.

Вес фильтра ( ntp.filter ) — вес, используемый при вычислении дисперсии фильтра (применяется при работе с алгоритмом фильтрации).

Выбранный вес ( ntp.select ) — вес, используемый при вычислении выбранной дисперсии (применяется при работе алгоритма селекции).

Режимы работы

За исключением широковещательного режима, NTP -ассоциация формируется, когда два партнера обмениваются сообщениями и один или оба из них создает и поддерживает протокольную машину, называемую ассоциацией. Ассоциация может работать в одном из 5 режимов, заданных переменной peer.mode: симметрично активный, симметрично пассивный, клиент, сервер и широковещательный:

Симметрично активный (1). ЭВМ, работающая в этом режиме, периодически посылает сообщения вне зависимости от достижимости или слоя своего партнера. При работе в этом режиме ЭВМ оповещает о своем намерении синхронизовать и быть синхронизованной партнером.

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

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

Сервер (4). Этот тип ассоциации первоначально создается по прибытии запроса клиента и существует только для отклика на этот запрос. После отклика ассоциация ликвидируется. При работе в этом режиме ЭВМ (обычно рабочая сетевая станция) оповещает о намерении синхронизовать партнера.

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

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

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

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

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

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

Обработка событий

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

Обозначения

Алгоритмы фильтрации и селекции NTP используют несколько переменных для хранения значений сдвига часов, RTT и дисперсии. Переменные, относящиеся к партнерам, обычно обозначаются строчными греческими буквами, а для первичного эталона времени используются прописные буквы. Эти алгоритмы базируются на параметре, называемом расстояние синхронизации ( $$\lambda$$ ) и вычисляемом с использованием RTT и дисперсии.

Дисперсия партнера ( $$\varepsilon$$ ) содержит вклады от ошибок измерения ( $$\rho$$ ) и накопления ошибок дрейфа (skew-error).

Каждый раз, когда соответствующие переменные партнеров изменяются, значения дисперсии корректируются. Ниже приводятся основные определения переменных и формулы их вычисления:

$$\theta = peer.offset, \\ \delta = peer.delay, \\ \varepsilon = peer.dispersion = \rho + \varphi \tau + \varepsilon _{\sigma }, \\ \lambda = \varepsilon + |\delta |/2,$$

где $$\delta = RTT$$, $$\theta$$ — сдвиг часов, $$\varphi \tau$$ — накопление сбоя, $$\varphi = ntp.maxskew/ntp.maxage$$, $$\tau$$ — момент времени передачи исходной временной метки (на основе $$\tau$$ вычисляется $$\theta$$ и $$\delta$$ ), $$\varepsilon _{\sigma }$$ — дисперсия фильтра. Переменные, относящиеся к партнеру i, определяются следующим образом:

$$\theta _{i} = \varphi _{i}, \\ \delta _{i} = peer.rootdelay + \delta _{i}, \\ \varepsilon _{i} = peer.rootdispersion + \varepsilon _{i} + \varphi \tau _{i} (максимальная\ дисперсия\ часов\ партнера), \\ \lambda _{i}= \varepsilon _{i} + |\delta _{i}|/2,$$

Окончательно, предполагая, что для синхронизации выбран i-ый партнер, система переменных определяется следующим образом:

$$\theta = комбинированное\ окончательное\ смещение\ (combined\ final\ offset), \\ \delta = \delta _{i}, \\ e = \varepsilon _{i} + \varepsilon _{\xi } + \theta , \\ \lambda = \lambda _{i}, \\ где\ \varepsilon _{\xi } — дисперсия\ выбора\ (select\ dispersion).$$

Процедура получения

Процедура получения выполняется после прихода NTP -сообщения. Она проверяет сообщения, интерпретирует различные режимы и вызывает другие процедуры для фильтрации данных и выбора источника синхронизации. Если номер версии в пакете не соответствует текущей версии, сообщение может быть отброшено. Если получено управляющее сообщение NTP и код режима пакета равен 6 (управление), вызывается процедура управляющего сообщения. IP-адреса отправителя и адресата, а также номера портов устанавливаются соответствующими заданному партнеру. Если соответствия нет, производится новая инсталляция протокольной машины и формируется новая ассоциация.

Пакетная процедура

Пакетная процедура проверяет корректность сообщения, вычисляет задержку/смещение и вызывает другие процедуры для отбора данных и выбора источника синхронизации. При этом проверяется, чтобы переданная временная метка отличалась от последней, полученной от того же партнера. Кроме того, проверяется, чтобы исходная временная метка соответствовала последней метке, посланной тому же партнеру. В случае широковещательного режима (5) RRT =0 и полная точность операции передачи времени будет недостижимой. Однако полученная точность может быть вполне приемлемой для многих целей. Процедура вызова коррекции времени использует в качестве параметра peer.hostpoll ( peer.peerpoll может быть изменено).

Контролируется, чтобы исходная и полученная временные метки не были равны нулю. Если любая из них равна нулю, ассоциация не синхронизирована или потеряла доступ в одном или обоих направлениях.

RTT и временное смещение по отношению к партнеру вычисляется следующим образом.

Пусть i — четное целое число.

ti-3, ti-2, ti-1 и ti — содержимое переменных pkt.org, pkt.rec, pkt.xmt и peer.rec, соответственно. Смещение часов $$\phi,$$ $$RTT =\delta$$ и дисперсия $$\varepsilon$$ ЭВМ по отношению к партнеру равны:

$$\delta = (t_{i} - t_{i-3}) - (t_{i-1} - t_{i-2}), \\ \varphi = ((t_{i-2} - t_{i-3}) + ( t_{i-1} - t_{i}))/2, \\ \varepsilon = (1 << sys.precision) + \varphi (t_{i} - t_{i-3}),$$

где, как и прежде, $$\varphi = ntp.maxskew/ntp.maxage. <<$$ - обозначает сдвиг кода влево. Значение $$\varepsilon$$ представляет собой максимальную ошибку или дисперсию, связанную с ошибкой измерения на стороне ЭВМ, а также накопление ошибок из-за дрейфа локальных часов за время после отправки последнего сообщения, посланного партнером. Дисперсия корректируется процедурой фильтра часов (clock-filter).

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

Процедура "часовой фильтр" вызывается для вычисления задержки ( peer.delay ), смещения ( peer.offset ) и дисперсии ( peer.dispersion ) для партнера. Спецификация алгоритма часового фильтра не является составной частью протокола NTP. По этой причине описания, приводимые ниже, следует рассматривать как рекомендательные.

Процедура коррекции показаний часов

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

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

Процедура расстояния вычисляет базовую (root) задержку $$\delta,$$ базовую дисперсию $$\varepsilon$$ и базовое расстояние синхронизации $$\lambda.$$ ЭВМ не будет синхронизовать выбранного партнера, если расстояние больше, чем ntp. maxdistance.

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

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

Работа первичных часов (primary-clock procedure)

Когда ЭВМ связана с первичным эталоном времени, таким, как радио-часы, удобно ввести информацию об этих часах в базу данных, как если бы это был обычный партнер. В процедуре первичных часов часы запрашиваются раз в минуту или около того, полученный же временной код используется для корректировки показаний местных часов. Когда обнуляется peer.timer для первичного партнера, процедура передачи не вызывается, а посылается запрос радио-часам с использованием ASCII-последовательности, предусмотренной для этого случая. Когда получен корректный временной код от радио-часов, он преобразуется в формат временной метки NTP и корректируются соответствующие переменные партнера. Величина peer.leap устанавливается в зависимости от состояния бита оповещения временного кода, если таковой имеется, или вручную оператором. Значение для peer.peeraddr, которое становится равно sys.refid, когда вызывается процедура корректировки показаний часов, делается равным ASCII-строке, описывающей часы.

Процедуры инициализации

Процедура инициализации вызывается при перезагрузке системы или при повторном запуске демона NTP. Состояние локальных часов при загрузке предполагается неопределенным; однако, некоторые виды оборудования обеспечивают доступ к локальным часам, как в ходе загрузки, так и сразу после нее. Переменная точности определяется внутренней архитектурой оборудования локальных часов.

Процедура initialization-instantiation

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

Процедура receive-instantiation

Процедура receive-instantiation вызывается процедурой приема, когда обнаруживается новый партнер. Она инициализирует переменные партнера и формирует ассоциацию. Если сообщение получено от партнера, работающего в режиме клиента (3), ЭВМ переводится в режим сервера (4); в противном случае, она устанавливается в симметрично пассивный режим (2).

Процедура primary clock-instantiation

Эта процедура вызывается из процедуры инициализации для того, чтобы установить переменные состояния для первичных часов. Значение peer.precision определяется из спецификации радио-часов и аппаратного интерфейса. Значение peer.rootdispersion номинально равно удесятеренной максимальной ошибке радио-часов, например, 10 мсек для WWVB или радио-часов GOES и 100 мсек для менее точных радио-часов WWV.

В некоторых конфигурациях, включающих в себя атомные часы или приемники LORAN-C, первичный эталон может выдавать только секундные импульсы и не предоставлять полного временного кода (числа секунд и пр.). В этих конфигурациях нумерация секунд может быть получена из других источников, таких, как радио-часы или даже другие NTP -партнеры. Здесь переменные первичных часов должны отражать особенности первичного эталона, а не источника нумерации секунд. Однако если источник нумерации секунд отказал или работает некорректно, актуализация локальных часов от первичного эталона должна быть заблокирована.

Процедура очистки

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

Процедура запроса-коррекции (poll-update)

Процедура запроса-коррекции реализуется, когда происходит событие, которое может вызвать изменение периода запросов (рассылки) или таймера партнера. Она проверяет значения периода запросов ЭВМ ( peer. hostpoll ) и партнера ( peer.peerpoll ), а также устанавливает их в заданных пределах.

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

Процедура расстояния синхронизации (synchronization distance)

Процедура расстояния вычисляет расстояние синхронизации на основе переменных партнеров.

Заметим, что, в то время как $$\delta$$ может быть в некоторых случаях отрицательной, $$\varepsilon$$ и $$\lambda$$ всегда положительны.

Замечания о контроле доступа

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

Если требуется более надежная модель, система может базироваться на списке доступа, в который включаются 32-битовый IP-адрес, 32-битовая маска и 3-битовый код режима работы. Если логическое И адреса эталона ( pkt.peeraddr ) и маски на входе ЭВМ соответствуют определенному адресу и режиму ( pkt.mode ), доступ разрешается, в противном случае отправителю запроса присылается ICMP-сообщение об ошибке. Список управления доступом служит фильтром, определяющим, какой из партнеров может сформировать ассоциацию.

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

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

Чтобы NTP алгоритмы фильтрации и отбора работали эффективно, полезно иметь меру вариации для каждого из партнеров. Принятая мера вариации базируется на разностях первого порядка, которые легко вычислить. Существует две меры, одна — называемая дисперсией фильтра $$\varepsilon _{\sigma }$$, и другая — дисперсия выбора (select dispersion) $$\varepsilon _{\xi }$$. Обе меры вычисляются как взвешенные суммы смещений из списка, сформированного на основе расстояний синхронизации. Если $$\theta _{i} (0\le i < n)$$ — смещение i-ой записи, тогда разность $$\varepsilon _{ij}$$ i-ой записи по отношению к j-ой записи определяется как $$|\theta _{i} - \theta _{j}|$$. Дисперсия относительно j-ой записи определяется как:

$$\epsilon_j=\sum_{i=1}^{n-1}\epsilon_{ij}w_{i+1}$$

где w — весовой коэффициент, который служит для учета влияния расстояния синхронизации на дисперсию. В алгоритмах NTP w выбирается меньше 1/2: w = ntp.filter для дисперсии фильтра (filter dispersion) и w = NTP.SELECT для дисперсии выбора (select dispersion). Дисперсия $$\varepsilon _{\sigma }$$ и $$\varepsilon _{\xi }$$ определены относительно 0-ой записи $$\varepsilon _{0}$$.

Существует две процедуры, описанные ниже: процедура "часовой-фильтр" (clock-filter), которая применяется для выбора лучших записей смещения для данных часов, и процедура "выбора часов" (clock-selection), которая применяется, чтобы выбрать наилучшие часы среди иерархического набора часов.

Процедура часовой фильтр (clock-filter)

Процедура часовой фильтр исполняется по прибытии сообщения NTP или другого события, в результате которого получены новые данные. Она использует аргументы ( $$\theta , \delta , \varepsilon$$ ), где $$\theta$$ — результат измерения смещения часов, содержащийся в записи, а $$\delta$$ и $$\varepsilon$$ соответственно — RTT и дисперсия. Процедура определяет значение отфильтрованного смещения часов ( filtered clock offset — peer.offset ), RTT ( peer.delay ) и дисперсии ( peer.dispersion ). Она также корректирует дисперсию хранящихся записей и текущее показание часов ( peer.update ).

Процедура часового фильтра применяет сдвиговый регистр (peer.filter), который состоит из NTP.SHIFT каскадов, каждый каскад содержит значения $$\theta _{i}, \delta _{i} и \varepsilon _{i}$$, которые пронумерованы, начиная с нуля, слева направо. Фильтр инициализируется процедурой очистки при этом заносятся значения [0, 0, NTP.MAXDISPERSE] во всех каскадах. Новые данные записей вдвигаются в фильтр с левого конца. Пакетная процедура выдает записи в формате ( $$\theta , \delta , \varepsilon$$ ), когда приходят новые корректирующие данные, в то время как процедура передачи выдает записи в форме [0, 0, NTP. MAXDISPERSE], когда истекает два периода запроса без поступления свежих данных. Когда одни и те же символы ( $$\theta , \delta , \varepsilon$$ ) используются для аргументов, содержимого часового фильтра и переменных партнера, их значение обычно понятно из контекста.

Дисперсия $$\varepsilon _{i}$$ для всех корректных записей в регистре фильтра должна корректироваться, с тем, чтобы отражать накопление смещения со времени последней коррекции. Эти записи заносятся также во временный список, следуя стандартному формату записей [расстояние, индекс]. Записи в регистре сдвигаются вправо, новые записи вводятся слева, а самая правая запись теряется. Временный список сортируется по значению расстояния. Если в списке не остается записей, процедура прерывается без корректировки переменных партнера.

Смещение партнера $$\theta _{0}$$, задержка $$\delta _{0}$$ и дисперсия $$\varepsilon _{0}$$ выбираются как величины, соответствующие записи с минимальным расстоянием; другими словами, записи, соответствующей первому элементу временного списка (в данной нотации имеет индекс 0).

Переменные peer.offset и peer.delay представляют смещение шкалы часов и RTT для локальных часов, измеренные относительно часов партнера. Обе они усредняются по большому числу измерений в течение длительного периода времени. Переменная peer.dispersion характеризует максимальную ошибку из-за неточности измерений, дрейфа и вариации записей. Все три переменные используются при выборе часов для синхронизации.

Процедура выбора часов

Процедура выбора часов использует переменные партнера $$\theta , \delta , \varepsilon$$ и $$\tau,$$ она вызывается, когда эти переменные изменились или изменился статус доступности. Процедура включает в себя две составные части: алгоритм пересечения (intersection algorithm) и алгоритм кластеризации (clustering algorithm). Алгоритм пересечения подготавливает список кандидатов партнеров, могущих стать источниками синхронизации и вычисляет доверительный интервал для каждого из них. Алгоритм кластеризации сортирует список кандидатов по кодам слоя и расстояния синхронизации. Системная переменная sys.peer представляет собой указатель на наиболее вероятного кандидата, если таковой имеется, или на нулевую величину в противном случае.

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

Каждый из партнеров просматривается последовательно и добавляется в конец списка, если он прошел ряд тестов. Для каждого из m кандидатов в список заносятся 3 записи в форме $$[указатель, тип]: [\theta - lambda;, - 1], [\theta , 0]$$ и $$[\theta + \lambda , 1]$$. В результате в списке будет 3m записей, которые будут позднее упорядочены.

Нижеприведенный алгоритм представляет собой адаптированную версию DTS [DEC89] и сконструирован так, чтобы отбирать только истинных кандидатов. Алгоритм начинается с инициализации значения f и занесения нуля в счетчики i и c. Затем, начиная с конца упорядоченного, для каждой записи [указатель, тип] значение типа вычитается из кода счетчика i, который содержит число пересечений. Если код типа равен нулю, инкрементируется значение c, которое регистрирует число ложных кандидатов. Если для некоторых записей i >= m - f, конец записи становится нижней границей пересечения; в противном случае, f увеличивается на 1 и процедура повторяется. Без сброса значений f или c аналогичная процедура используется для нахождения верхней границы, за исключением того, что значение кода тип добавляется к счетчику. Если после того как обе границы определены c <= f, процедура продолжается для найденных m - f кандидатов, в противном случае, f увеличивается на 1 и вся процедура повторяется.

Заметим, что работа продолжается далее данной точки, только если имеется более m/2 пересечений. Однако возможно, но не слишком вероятно, что в области пересечения окажется менее m/2 кандидатов.

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

В исходном алгоритме DTS процедура выбора часов прерывается в данной точке с выбором кандидатов из центра области пересечения. Однако это ведет к заметной потере точности и стабильности, так как не учитываются индивидуальные статистические свойства партнеров. Следовательно, в NTP только кандидаты, которые остаются в результате описанного выше отбора, могут участвовать в последующей обработке. Список кандидатов преобразуется к форме [расстояние, индекс], где расстояние вычисляется на основе кода слоя и расстояния синхронизации $$\lambda$$ партнера. Масштабный коэффициент позволяет реализовать механизм весового учета вкладов от кодов слоя и расстояния. Обычно код слоя доминирует, если только один или более кандидатов имеют слишком большие расстояния. Список упорядочивается согласно величине расстояния.

Последующие шаги служат для того, чтобы отсеять кандидатов со слишком большими дисперсиями. Практика показывает, что число кандидатов может быть достаточно велико. Это может привести к большому числу циклов повторения процедуры отбора, которые не дадут какого-либо улучшения результатов. Длина списка кандидатов ограничивается переменной ntp.maxclock.

Заметим, что $$\varepsilon _{\xi i}$$ представляет собой дисперсию относительно i-го партнера из списка кандидатов, которая может быть вычислена методом дисперсии фильтра, описанным выше. $$\varepsilon _{j}$$ — дисперсия j-ого партнера из списка, включающая в себя вклады от ошибок измерения, от накопления дрейфа и из-за дисперсии фильтра. Если максимальное значение $$\varepsilon _{\xi i}$$ больше, чем минимальное значение $$\varepsilon _{j}$$, а число кандидатов больше, чем ntp.minclock, то i-ый партнер удаляется из списка и процедура повторяется. Если текущий источник синхронизации является одним из членов списка и нет других кандидатов из более низкого слоя, процедура прерывается и никакие другие последующие шаги не предпринимаются. В противном случае в качестве источника синхронизации берется первый кандидат из списка.

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

Локальные часы

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

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

Реализация "пушистый шарик" (Fuzzball)

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

48-битовый часовой регистр (clock) и 32-битовый предварительный счетчик (prescaler) образуют управляемый задающий генератор с периодом 1 мс. Дробная часть кода времени представляет число миллисекунд с начала суток. 32-битовый регистр коррекций (Clock-Adjust) используется для подстройки фазы часов постепенными шагами, что исключает неоднородности временной шкалы. Его содержимое обозначается x. 32-битовый регистр компенсации дрейфа (Skew-Compensation) применяется для подстройки частоты задающего генератора с помощью добавления небольших фазовых сдвигов (0,01%). Его содержимое обозначается символом y. 16-битовый счетчик оповещения ( Watchdog ) и 32-битный регистр согласования (Compliance) нужны для определения корректности и служат также для задания периода рассылки запросов. Содержимое регистра согласования обозначается символом z. 32-битовый регистр настройки (PPS-Adjust) предназначен для подстройки точности, когда имеется точный источник сигналов с периодом в одну секунду. 2-битовый регистр флагов управляет добавлением/вычитанием секунд к показаниям часов, когда это необходимо.

Все регистры, кроме предварительного счетчика, обычно размещаются в памяти. В типовом интерфейсе часов, таком, как DEC KWV11-C, регистр prescaler реализован в виде 16-битового буферного счетчика, управляемого кварцевым генератором с частотой, кратной 1000 Гц. Переполнение счетчика вызывает прерывание процессора, которое осуществляет приращение содержимого регистра часов.

Когда наступает момент подстройки, CLOCK.ADJ секунд вычитается из содержимого PPS-счетчика, но это CLOCK.ADJ делается лишь при условии, что там лежит число больше нуля. CLOCK.ADJ добавляется к коду счетчика Watchdog. Этот код не должен превышать значения NTP. MAXAGE, поделенного на CLOCK.ADJ. Если счетчик Watchdog достигнет этой величины, часы считаются не синхронизованными, а Leap-биты устанавливаются равными 11₂.

Постепенная настройка фазы

Если локальные часы нескорректированы, они продолжают работать со смещением и частотой (при отсутствии дрейфа), установленными при последней коррекции. Корректирующая информация имеет формат 48-битного целого числа со знаком. Это число характеризует целое и дробное число миллисекунд (запятая располагается после 32-го двоичного разряда). Если полученная величина превосходит максимальное значение, заданное CLOCK.MAX, необходима постепенная пошаговая коррекция. В нормальной ситуации величина поправки вычисляется в рамках алгоритма NTP. Однако, если код счетчика PPS больше нуля, вместо него должен использоваться регистр PPS-ADJUST. Пусть u представляет собой 32-битовый код с битами 0-31, равными разрядам 16-47 корректирующего кода. Если некоторые младшие биты корректирующего кода не используются, они устанавливаются равными биту знака. Такие операции сдвигают положение запятой влево по отношению биту 16, что уменьшает влияние ошибок округления. Пусть b число начальных нулей в коде регистра Compliance и пусть c — число начальных нулей в коде счетчика Watchdog. Тогда b установится равным:

b = b - 16 + clock.comp

b не должно быть меньше нуля (это логарифм постоянной времени обратной связи). Затем установим c равным:

c = 10 - c

Величина c представляет собой логарифм времени интегрирования с момента последней коррекции. Затем вычисляются новые значения кодов для регистров CLOCK.ADJUST и Skew-Compensation.

x = u >> b,
y = y + (u >> (b + b - c)).

В заключение вычисляем экспоненциальное среднее

z = z + (u << (b + clock.mult) - z) >> clock.weight,

где сдвиг влево переносит положения запятой с целью достижения большей точности.

Для каждого периода подстройки определяется корректирующий код из двух составляющих. Первая составляющая (фаза) определяется как

x >> clock.phase,

эта величина затем вычитается из предшествующего значения регистра Clock-Adjust. Результат становится новым значением кода этого регистра. Вторая компонента — (частота) определяется как

y >> clock.freq.

Совокупность фазы и частоты представляет собой окончательный корректирующий код, который затем добавляется к коду регистра (clock). В заключение счетчик Watchdog обнуляется.

Величина b, вычисленная ранее, может использоваться для изменения величины системной переменной, характеризующей период запросов (коррекций) sys.poll.

sys.poll <- b + NTP.MINPOLL.

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

Ступенчатая подстройка фазы

Когда величина поправки превышает CLOCK.MAX, имеется возможность того, что часы окажутся настолько не синхронизованы, что наилучшим решением будет немедленная замена содержимого регистра часов. Однако, в случаях, когда вариация записи весьма высока, разумно не поверить в возможность скачкообразного изменения, если только со времени последней коррекции не прошло достаточно много времени. Следовательно, если обнаружено скачкообразное изменение, а счетчик Watchdog содержит код меньше предварительно установленного значения CLOCK.MINSTEP, корректирующее сообщение игнорируется.

Если обнаружено ступенчатое изменение, коррекция заносится непосредственно в регистры Clock, а содержимое регистров Clock-Adjust и Watchdog обнуляется. Другие же регистры остаются без изменений. Так как ступенчатое изменение показаний указывает на некорректность информации в часовых фильтрах (clock filters), биты добавления делаются равными 11₂ (не синхронизовано) и вызывается процедура очистки часовых фильтров и переменных состояния для всех партнеров. На практике необходимость корректировать показания часов скачкообразно случается крайне редко, когда, например, локальные часы или эталон перезагружаются.

Практически значения CLOCK.MAX могут быть превышены временным сервером лишь в условиях чрезмерной перегрузки канала или при сбоях оборудования. Наиболее часто встречаемый случай — это смена сервера при регистрации слишком большого числа ошибок или из-за сильной вариации задержки. Рекомендуется, чтобы реализации программ включали средства формирования значений CLOCK.MAX для особых случаев. Величина, на которую можно превысить CLOCK.MAX, не нарушая требования монотонности, зависит от значения приращения регистра часов (Clock Register).

Обсуждение реализации

Базовая модель надежности NTP предполагает, что не должно быть никаких других способов изменения показаний, кроме предусмотренных самим протоколом NTP. Системы с часами-календарем, имеющие питание от батареи или аккумулятора, считаются надежными, но менее точными, чем использующие NTP -синхронизацию. При последовательных коррекциях, если величина поправки превышает конфигурационный параметр (например, 1000 секунд), поправка отбрасывается и посылается сообщение об ошибке. Некоторые реализации периодически записывают содержимое регистра Skew-Compensation (компенсация дрейфа) в системный файл или в NVRAM (память, сохраняемая при отключении питания).

Преобразование из формата NTP в обычный информационный формат осуществляется прикладными программами. В день накануне добавления/вычитания секунды из показаний времени значение sys.leap устанавливается на первичном сервере вручную. Следует иметь в виду, что большинство радио-часов не имеет автоматических или ручных средств добавления/вычитания секунд. Но даже в случае некорректного добавления/вычитания секунды локальные часы будут вновь синхронизованы не позднее чем через число секунд, заданное CLOCK.MINSTEP.

Приложение А. Формат данных NTP — версия 3

Формат NTP -сообщения, которое следует сразу после UDP-заголовка, показан на рис 7.2.

(рис 7.2) Формат сообщения NTP.

Индикатор добавления ( LI — leap indicator) — двухбитовое поле предупреждения о предстоящем добавлении/вычитании секунды к последней минуте текущего дня. Значения этих битов смотри в таблице 7.1.

Номер версии (VN) — трехбитовое поле, указывающее на номер версии протокола NTP, в настоящее время (3).

Режим (Mode) — трехбитовое поле, определяющее режим, значения кодов режима приведены в таблице 7.2.

Слой (Stratum) — 8-битовое поле, определяющее код слоя, где работают локальные часы. Коды слоя представлены в таблице 7.3. Возможные значения кодов лежат в интервале от нуля до NTP.INFIN включительно.

Период запросов (poll interval) — 8-битовое поле, указывающее на максимальное значение интервала между запросами. Код, записанный в этом поле, интерпретируется как целое число со знаком и характеризует значение периода в секундах как ближайшее к величине степени двух. Коды, которые могут быть записаны в этом поле, должны лежать в интервале между NTP.MAXPOLL и NTP.MAXPOLL включительно.

Точность (precision) — 8-битовое поле, обозначающее точность локальных часов в секундах. Код поля интерпретируется как целая степень со знаком числа 2.

Базовая задержка (Root Delay) — 32-битовое поле, характеризующее RTT до эталонного источника в секундах. Код поля интерпретируется как число с фиксированной запятой, размещенной между битами 15 и 16. Заметим, что величина этого кода может иметь и отрицательное значение (зависит от точности часов и величины дрейфа).

Базовая дисперсия (Root Dispersion) — 32-битовое поле, определяющее максимальную ошибку по отношению к эталонному источнику в секундах. Код поля интерпретируется как число с фиксированной запятой (между 15 и 16 битами). Допустимы только положительные значения.

Идентификатор эталонных часов (Reference Clock Identifier) — 32-битовое поле, идентифицирующее конкретные эталонные часы. В случае кода слоя нуль (не специфицировано) или слоя 1 (первичный эталон) — это 4-октетная комбинация, выравнивается по левому краю и дополняется нулями (ASCII). Когда идентификатор в NTP не специфицирован, предлагаются asci -идентификаторы, приведенные в таблице 7.4.

В случае слоя 2 и больше (вторичный эталон) — это 4-октетный IP-адрес ЭВМ — первичного эталона.

Эталонная временная метка (Reference Timestamp) — поле локального времени (64-битовый формат временных меток), когда часы корректировались в последний раз.

Исходная временная метка (Originate Timestamp) определяет время, когда запрос направлен серверу (стандартный 64-битовый формат временных меток).

Получаемая временная метка (Receive Timestamp) — время, когда запрос прибыл к серверу (стандартный 64-битовый формат временных меток).

Передаваемая временная метка (Transmit Timestamp) — локальное время, когда послан отклик сервером (стандартный 64-битовый формат временных меток).

Аутентификатор (authenticator) (опционно) — поле, содержащее аутентификационную информацию. Используется лишь в случае реализации NTP -аутентификации.

Приложение Б. Сообщения управления NTP

В сетевой среде должны быть средства управления программами NTP, такие, как установка индикатора добавления секунды (Leap-Indicator) со стороны первичного сервера, настройка различных системных параметров и процедур мониторинга. Эти операции могут быть реализованы с привлечением протокола snmp и соответствующего расширения базы данных MIB. Однако в тех случаях, когда такие средства недоступны, функции могут быть реализованы с помощью специальных управляющих NTP -сообщений.

Управляющие сообщения NTP имеют код 6 в поле режима первого октета NTP -заголовка. Формат поля данных специфичен для каждой из команд или отклика. Однако в большинстве случаев формат конструируется так, чтобы облегчить его непосредственное чтение. Как правило, он состоит из ASCII-строк. Если используется аутентификатор, поле данных дополняется нулями до границы, кратной целому числу 32-битных слов.

IP-ЭВМ не должны обрабатывать дейтограммы длиннее 576 октетов; однако, некоторые команды или отклики могут содержать данные, не помещающиеся в одну дейтограмму. Для решения этой проблемы все октеты сообщения нумеруются, начиная с нуля. При передаче фрагментов сообщения номер первого октета записывается в поле смещения (offset), а число октетов в поле длины. Бит (M — more) устанавливается во всех фрагментах за исключением последнего.

Большинство контрольных функций включает посылку команды и получение отклика. Отправитель выбирает ненулевой порядковый номер и устанавливает статусное поле и биты R и E равными нулю. Получатель интерпретирует код операции и дополнительную информацию, содержащуюся в поле данных, вносит изменение в поле статуса и устанавливает бит R=1, а также возвращает три 32-битного слова заголовка вместе с другой дополнительной информацией поля данных. В случае неверного формата сообщения или ошибки в поле данных получатель заносит соответствующий код в поле статуса, устанавливает биты R и E равными 1 и опционно записывает диагностическое сообщение в поле данных.

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

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

Формат сообщений управления NTP

Формат заголовков управляющих NTP -сообщений показан на рис 7.3. Этот заголовок располагается непосредственно вслед за UDP-заголовком.

(рис 7.3) Формат управляющего сообщения NTP

Первые два бита, обозначенные ZZ, должны всегда содержать 0.

Номер версии (VN — version number) — трехбитовое поле, указывающее на номер версии протокола NTP, в настоящее время (3).

Режим (Mode) — трехбитовое поле, определяющее режим, значение кода режима для управляющих сообщений равно 6.

Бит отклика (R) — равен нулю для команд и 1 для откликов.

Бит ошибки (E) — равен нулю для нормального отклика и 1 в случае ошибки.

Бит продолжения (M — more) — равен нулю для последнего фрагмента и 1 для всех остальных.

Код операции (OP) — 5-битовое поле, определяющее код команды. Значения кодов и их функции представлены в таблице 7.5.

Коды операции управляющего сообщения

Код	Функция
0	Зарезервировано
1	чтение статуса команда/отклик
2	чтение переменной команда/отклик
3	запись переменной команда/отклик
4	чтение переменных часов команда/отклик
5	запись переменных часов команда/отклик
6	установка адреса/порта trap команда/отклик
7	отклик на Trap
8-31	Зарезервировано на будущее

Порядковый номер (Sequence) — 16-битовое поле, определяющее номер запроса или отклика и облегчающее определения их соответствия.

Статус — 16-битовое поле, содержащее код статуса системы, партнера или часов.

Идентификатор ассоциации (Association ID) — 16-битовое поле, несущее в себе идентификатор ассоциации.

Смещение (Offset) — 16-битовое поле, которое определяет положение первого октета поля данных в сообщении, передаваемом в нескольких дейтограммах (позиция задается в октетах).

Длина (Count) — 16-битовое поле, определяющее длину поля данных в октетах.

Данные — это поле содержит информацию сообщения, как для команд, так и для откликов. Максимальное число октетов в поле данных равно 468.

Аутентификатор (опционно). Поле, содержащие аутентификационную информацию. Используется лишь в случае реализации NTP -аутентификации.

Статусные слова

Статусные слова указывают на текущее состояние системы ассоциации и часов. Эти слова интерпретируются программами сетевого мониторинга и имеют 4 разных 16-битовых формата. Статусные слова партнеров и системы соответствуют откликам для всех команд за исключением случая чтения/записи переменных часов и установки адреса/порта для TRAP. Идентификатор ассоциации нуль соответствует системным статусным словам, в то время как ненулевой идентификатор указывает на какую-то конкретную ассоциацию. Статусное слово, присланное в ответ на команду чтения или записи переменной часов, указывает на состояние оборудования и кодирующего программного обеспечения.

Системные статусные слова

Системное статусное слово может присутствовать в статусном поле отклика и имеет следующий формат.

Индикатор добавления ( LI — leap indicator) — двухбитовое поле предупреждения о предстоящем добавлении/вычитании секунды к последней минуте текущего дня. Значения этих битов смотри в таблице 7.1.

Источник часов (clock source) — 6-битовое поле, указывающее на используемый в данный момент источник синхронизации. Назначение кодов этого поля описано в таблице 7.6.

Коды источников временного эталона

Код	Функция
0	Не специфицирован или неизвестен
1	Калиброванные атомные часы (напр., hp 5061)
2	vlf (диапазон 4) или НЧ (диапазон 5) радио (напр., omega, wwvb)
3	ВЧ (диапазон 7) радио (напр., chu, msf, wwv/h)
4	УВЧ (диапазон 9) спутник (напр., goes, gps)
5	Локальная сеть (напр., dcn, tsp, dts)
6	UDP/ NTP
7	UDP/time
8	eyeball-and-wristwatch
9	Телефонный модем (напр., nist)
10-63	Зарезервировано на будущее

Системный счетчик событий — четырехбитовое целое число, которое обозначает число событий, происшедших с момента последнего получения статусного слова системы. Счетчик обнуляется, когда присылается в статусном поле отклика, и остается неизменным после достижения значения 15.

Код системного события — четырехбитовое число, идентифицирующее последнее системное событие, новое значение переписывает предыдущее. Коды событий перечислены в таблице 7.7.

Коды системных событий

Код	Функция
0	Не специфицировано
1	Рестарт системы
2	Системный или аппаратный сбой
3	Новое статусное слово системы (изменение битов добавления или синхронизации)
4	Новый источник синхронизации или слой (изменение sys.peer или sys.stratum)
5	Сброс системных часов (корректирующая добавка превысила clock.max)
6	Некорректное системное время или дата
7	system clock exception
8-15	Зарезервировано на будущее

<identifier>[=<value>],<identifier> =<value> ],...

<идентификатор ассоциации> <статусное слово>,