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

Previous: 4.4.14.5 Программа Sendmail UP: 4.4.11 Протоколы маршрутизации (обзор, таблицы маршрутизации, вектор расстояния)
Down: 4.5 Процедуры Интернет
Next: 4.4.16 Протокол SNTP

4.4.15 Сетевой протокол времени NTP
Семенов Ю.А. (ГНЦ ИТЭФ)

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

Древнеегипетский календарь имел 12 30-дневных лунных месяцев, но был привязан к сезонному появлению звезды Сириус (sirius – sothis). Для того чтобы примирить этот календарь с солнечным годом, был изобретен гражданский календарь, в котором добавлено 5 дней, доводящих длительность года до 365 дней. Однако со временем было замечено, что гражданский год примерно на одну четверть дня короче, чем солнечный год. Выбранная длительность года обеспечивала полное совпадение с солнечным годом раз за 1460 лет. Этот период называется циклом Сотиса (sothic-цикл). Так же как и shang chinese, древние египтяне установили длительность солнечного года равной 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 часам первого дня нашей эры.

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

Сетевой протокол задания времени NTP (network time protocol; 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].

Маршрутный протокол fuzzball [MIL83b], иногда называемый hellospeak, встраивает синхронизацию непосредственно в алгоритм маршрутного протокола. Он не является протоколом из стека IP.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Следуя принципам, принятым в телефонной промышленности [BEl86], точность каждого сервера определяется номером слоя (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) принимают значения, перечисленные в таблице 4.4.15.1:

Таблица 4.4.15.1 Значения кодов индикатора LI

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

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

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

Таблица 4.4.15.2. Значения кодов Режим

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

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

Таблица 4.4.15.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-строка, выровненная по левому краю и дополненная при необходимости нулями, например:

Таблица 4.4.15.4. Коды идентификаторов часов

Слой	Код	Значение
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) - число с фиксированной запятой, индицирующее максимальную ошибку часов партнера по отношению к локальным часам с учетом сетевой задержки в секундах. Допускаются только значения больше нуля.

Переменные аутентификации

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

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

Бит аутентификации (peer.authentic) - бит, индицирующий то, что последнее сообщение, полученное от партнера, было корректно аутентифицировано.

Идентификатор ключа (peer.hostkeyid, peer.peerkeyid, pkt.keyid) - целое число, идентифицирующее криптографический ключ, использованный при генерации аутентификационного кода сообщения.

Криптографические ключи (sys.key) - набор 64-битных ключей DES. Каждый ключ создается в соответствии с берклиевскими UNIX-распределениями, которые состоят из 8 октетов, где 7 младших бит каждого октета соответствуют битам des 1-7, а старший бит соответствует биту четности DES.

Контрольная крипто-сумма (pkt.check) - криптографическая контрольная сумма, вычисляемая процедурой шифрации.

Параметры

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

Номер версии (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 и дисперсии. Переменные, относящиеся к партнерам, обычно обозначаются строчными греческими буквами, а для первичного эталона времени используются прописные буквы. Эти алгоритмы базируются на параметре, называемом расстояние синхронизации (l) и вычисляемом с использованием rtt и дисперсии.

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

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

q = peer.offset,
d = peer.delay,
e = peer.dispersion = r + jt + e_s,
l = e + |d|/2,

где d = rtt, q - сдвиг часов, jt - накопление сбоя, j = ntp.maxskew/ntp.maxage, t - момент времени передачи исходной временной метки (на основе t вычисляется q и d), e _s - дисперсия фильтра. Переменные, относящиеся к партнеру i, определяются следующим образом:

q _i = j _i,
d _i = peer.rootdelay + d _i,
e _i = peer.rootdispersion + e _i + j t_i (максимальная дисперсия часов партнера),
l_i= e_i + |d_i|/2,

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

q = комбинированное окончательное смещение (combined final offset),
d = d_i,
e = e_i + e_x + q,
l = l_i,

где e_x дисперсия выбора (select dispersion).

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

Процедура передачи

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

Нижеприведенный фрагмент программы инициализирует пакетный буфер и копирует пакетные переменные.

pkt.peeraddr <- peer.hostaddr;

/* копирование системных и партнерских переменных */

pkt.peerport <- peer.hostport;
pkt.hostaddr <- peer.peeraddr;
pkt.hostport <- peer.peerport;
pkt.leap <- sys.leap;
pkt.version <- ntp.version;
pkt.mode <- peer.mode;
pkt.stratum <- sys.stratum;
pkt.poll <- peer.hostpoll;
pkt.precision <- sys.precision;
pkt.rootdelay <- sys.rootdelay;
if (sys.leap = 11₂ or (sys.clock - sys.reftime) > ntp.maxage)
skew <- ntp.maxskew;
else
skew <- j (sys.clock - sys.reftime);
{pkt.rootdispersion <- sys.rootdispersion + (1 << sys.precision)} + skew;
pkt.refid <- sys.refid;
pkt.reftime <- sys.reftime;

Временная метка передачи pkt.xmt будет использована позднее, для того чтобы проконтролировать отклик. Таким образом, программа должна сохранить точное переданное значение. Кроме того, порядок копирования временных меток должен быть выбран так, чтобы не понизить точность.

pkt.org <- peer.org;

/* копирование временных меток */

pkt.rec <- peer.rec;
pkt.xmt <- sys.clock;
peer.xmt <- pkt.xmt;

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

peer.reach <- peer.reach <<1;

/* актуализация доступности */

if (peer.reach = 0 and peer.config =0)
begin
ликвидируем ассоциацию;
exit;
endif

Если корректные данные введены в сдвиговый регистр фильтра хотя бы раз за время предыдущих двух периодов рассылки (младший бит peer.reach равен 1), счетчик корректных данных увеличивается на 1. После восьми таких удачных периодов интервал рассылки увеличивается. Процедура выбора часов вызывается, если необходимо заменить источник синхронизации.

if (peer.reach & 6 ≠ 0)	/* Проверка младших двух бит */
if (peer.valid << ntp.shift)	/* получены корректные данные */

peer.valid <- peer.valid + 1;
else peer.hostpoll <- peer.hostpoll + 1;
else begin

peer.valid <- peer.valid - 1;

/* ничего не слышно */

peer.hostpoll <- peer.hostpoll - 1;
call clock-filter(0, 0, ntp.maxdisperse);

call clock-select;

/* выбираем источник синхронизации */

endif
call poll-update;
end transmit procedure;

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

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

begin receive procedure
if (pkt.version ≠ ntp.version>) exit;
#ifdef (control messages implemented)
if (pkt.mode = 6) call control-message;
#endef

for (all associations)

/* Здесь выполняется управление доступом */

match addresses and ports to associations;
if (no matching association)

call receive-instantiation procedure;

/* создаем ассоциацию */

Вызов процедуры дешифровки осуществляется только в случае применения аутентификации.

#ifdef (authentication implemented)
call decrypt;
#endef

Если код режима пакета не равен нулю, он определяет режим на следующем этапе; в противном случае, режим определяется по номеру порта.

if (pkt.mode = 0)

/* для совместимости со старыми версиями */

mode;
else
mode <- pkt.mode;
case (mode, peer.hostmode)

В случае ошибки пакет просто игнорируется, а ассоциация, если она не была предварительно сконфигурирована, ликвидируется.

error: if (peer.config = 0) demobilize association;
break;

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

recv: call packet;	/* обработать пакет */
if (valid header) begin	/* если правильный заголовок, актуализовать внутренние часы */

peer.reach <- peer.reach | 1;
if (valid data) call clock-update;
endif
else
if (peer.config = 0) ликвидировать ассоциацию;
break;

В случае xmit, пакет обрабатывается и посылается промежуточный отклик. Ассоциация затем ликвидируется.

xmit: call packet;	/* обработать пакет */
peer.hostpoll <- peer.peerpoll;	/* послать немедленно отклик */

call poll-update;
call transmit;
if (peer.config = 0) ликвидировать ассоциацию;
break;

В случае pkt, пакет обрабатывается, а ассоциация помечается как достижимая при условии, что тесты 5-8 (правильный заголовок), перечисленные в пакетной процедуре, прошли успешно. Если, кроме того, прошли тесты 1-4 (корректные данные), вызывается процедура коррекции показаний локальных часов. В противном случае, если ассоциация не была предварительно сконфигурирована, она сразу после отклика ликвидируется.

pkt: call packet;	/* обработка пакета */
if (valid header) begin	/* если заголовок правилен, поправляется показание местных часов */

peer.reach <- peer.reach | 1;
if (valid data) call clock-update;
endif
else if (peer.config = 0) begin

peer.hostpoll <- peer.peerpoll;

/* послать немедленно отклик */

call poll-update;
call transmit;
ликвидировать ассоциацию;
endif
endcase
end receive procedure;

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

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

begin packet procedure

peer.rec <- sys.clock;

/* забрать полученную временную метку */

if (pkt.mode ≠ 5) begin

test1 <- (pkt.xmt ≠ peer.org);	/* Тест 1 */
test2 <- (pkt.org = peer.xmt);	/* Тест 2 */

endif
else begin

pkt.org <- peer.rec;

/* потеря временной метки из-за ошибки */

pkt.rec <- pkt.xmt;

test1;

/* ложные тесты */

test2;
endif

peer.org <- pkt.xmt;	/* актуализация исходной временной метки */
peer.peerpoll <- pkt.poll;	/* скорректировать период рассылки */

call poll-update(peer.hostpoll);

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

test3 <- (pkt.org ≠ 0 and pkt.rec ≠ 0); /* Тест 3 */

rtt и временное смещение по отношению партнера вычисляется следующим образом. Пусть i четное целое число.
Тогда t_i-3, t_i-2, t_i-1 и t_i - содержимое переменных pkt.org, pkt.rec, pkt.xmt и peer.rec, соответственно. Смещение часов j, rtt=d и дисперсия e ЭВМ по отношению к партнеру равны:

d = (t_i - t_i-3) - (t_i-1 - t_{i - 2}),
j = ((t_{i - 2} - t_i-3) + ( t_i-1 - t_i))/2,
e = (1 << sys.precision) + j (t_i - t_i-3),

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

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

Тест 4 требует, чтобы вычисленная задержка лежала в допустимых пределах:

test4 <- (|d| < ntp.maxdisperse И e

Тест 5 используется, только если реализован механизм аутентификации. Он требует, чтобы либо аутентификация была явно блокирована, либо чтобы аутентификатор в точности соответствовал тому, что описано в процедуре дешифровки.

#ifdef (authentication implemented) /* Тест 5 */
test5 <- ((peer.config = 1 и peer.authenable = 0) или peer.authentic = 1);
#endef

Тест 6 требует, чтобы часы партнера были синхронизованы, и время с момента последней коррекции было положительным и меньше чем ntp.maxage.

Тест 7 гарантирует, что ЭВМ не будет синхронизовано от партнера с большим кодом номера слоя.

Тест 8 требует, чтобы заголовок содержал соответствующие коды в полях pkt.rootdelay и pkt.rootdispersion.

test6 <- (pkt.leap ≠ 11₂ and

/* Тест 6 */

{pkt.reftime ≤ pkt.xmt << pkt.reftime + ntp.maxage})

test7 <- {pkt.stratum ≤ sys.stratum} and

/* Тест 7 */

{pkt.stratum << ntp.maxstratum};

test8 <- (| pkt.rootdelay | << ntp.maxdisperse and

/* Тест 8 */

{pkt.rootdispersion << ntp.maxdisperse});

С точки зрения последующей обработки пакеты содержат корректные данные, если успешно проходят тесты 1-4 (test1 & test2 & test3 & test4 = 1), вне зависимости от результатов других тестов. Только пакеты с корректными данными могут использоваться для вычисления смещения (offset), задержки (delay) и дисперсии. Пакеты имеют корректные заголовки, если успешно проходят тесты 5-8 (test5 & test6 & test7 & test8 = 1), вне зависимости от результатов остальных тестов. Только пакеты с корректными заголовками могут использоваться для определения того, может ли партнер быть выбран в качестве источника синхронизации. Заметим, что тесты 1-2 не используются в широковещательном режиме.

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

if (not valid header) exit;

peer.leap < pkt.leap;

/* Копирование переменных пакета */

peer.stratum <- pkt.stratum>;
peer.precision <- pkt.precision>;
peer.rootdelay <- pkt.rootdelay>;
peer.rootdispersion <- pkt.rootdispersion>;
peer.refid <- pkt.refid>;
peer.reftime <- pkt.reftime>;

if (valid data) call clock-filter(q, d, e);

/* обработка данных */

end packet procedure;

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

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

begin clock-update procedure

call clock-select;

/* Выбор базовых часов */

if (sys.peer ≠ peer) exit;

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

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

l andistance(peer);

/* обновление системных переменных */

if (l ≥ ntp.maxdistance) exit;
sys.leap <- peer.leap;
sys.stratum <- peer.stratum + 1;
sys.refid <- peer.peeraddr;
call local-clock;

if (local clock reset) begin

/* если сброс, очистить системные переменные */

sys.leap <- 11₂;
for (all peers) call clear;
endif
else begin

sys.peer <- peer;

/* если нет, то подстроить локальные часы */

sys.rootdelay <- d;
sys.rootdispersion <- e + max (e_x + |t|, ntp.mindisperse);
endif
sys.reftime <- sys.clock;
end clock-update procedure;

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

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

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

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

begin primary-clock-update procedure

peer.leap <- "from" radio or operator;

/* Копирование переменных */

peer.peeraddr <- ascii identifier;
peer.rec <- radio timestamp;
peer.reach <- 1;

call clock-filter({sys.clock - peer.rec, 0, 1 << peer.precision});		/* образец процесса */
call clockupdate;	/* коррекция локальных часов */

end primary-clock-update procedure;

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

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

begin initialization procedure
#ifdef (authentication implemented)
sys.keys <- as required;
#endef;

sys.leap <- 11₂;

/* копирование переменных */

sys.stratum <- 0 (undefined);
sys.precision <- host~precision;
sys.rootdelay <- 0(undefined);
sys.rootdispersion <- 0 (undefined);
sys.refid <- 0 (undefined);
sys.reftime <- 0 (undefined);
sys.clock <- external reference;
sys.peer <- null;
sys.poll <- ntp.minpoll;

for (all configured peers)

/* создание конфигурированных ассоциаций */

call initialization-instantiation procedure;
end initialization procedure;

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

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

begin initialization-instantiation procedure
peer.config <- 1;
#ifdef (authentication implemented)
peer.authenable <- 1 (suggested);
peer.authentic <- 0;
peer.hostkeyid <- as required;
peer.peerkeyid <- 0;
#endef;

peer.peeraddr <- peer ip address;

/* копирование переменных */

peer.peerport <- ntp.port;
peer.hostaddr <- host ip address;
peer.hostport <- ntp.port;
peer.mode <- host mode;
peer.peerpoll <- 0 (undefined);
peer.timer <- 0;
peer.delay <- 0 (undefined);
peer.offset <- 0 (undefined);

call clear;

/* инициализация ассоциации */

end initialization-instantiation procedure;

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

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

begin receive-instantiation procedure
#ifdef (authentication implemented)
peer.authenable <- 0;
peer.authentic <- 0;
peer.hostkeyid <- as required;
peer.peerkeyid <- 0;
#endef

peer.config <- 0;

/* Копирование переменных */

peer.peeraddr <- pkt.peeraddr;
peer.peerport <- pkt.peerport;
peer.hostaddr <- pkt.hostaddr;
peer.hostport <- pkt.hostport;

if (pkt.mode = 3)

/* Определение режима */

peer.mode <- 4;
else
peer.mode <- 2;
peer.peerpoll <- 0 (undefined);
peer.timer <- 0;
peer.delay <- 0 (undefined);
peer.offset <- 0 (undefined);

call clear;

/* инициализация ассоциации */

end receive-instantiation procedure;

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

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

begin clock-instantiation procedure

peer.config <- 1;

/* копирование переменных */

peer.peeraddr <- 0 undefined;
peer.peerport <- 0 (not used);
peer.hostaddr <- 0 (not used);
peer.hostport <- 0 (not used);
peer.leap <- 11₂;
peer.mode <- 0 (not used);
peer.stratum <- 0;
peer.peerpoll <- 0 (undefined);
peer.precision <- clock precision;
peer.rootdelay <- 0;
peer.rootdispersion <- clock dispersion;
peer.refid <- 0 (not used);
peer.reftime <- 0 (undefined);
peer.timer <- 0;
peer.delay <- 0 (undefined);
peer.offset <- 0 (undefined);

call clear;

/* инициализация ассоциации */

end clock-instantiation procedure;

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

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

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

begin clear procedure

peer.org <- 0 (undefined);

/* пометка неопределенных временных меток */

peer.rec <- 0 (undefined);
peer.xmt <- 0 (undefined);

peer.reach <- 0;	/* сброс переменных состояния */
peer.filter <- [0, ,0, ntp.maxdisperse];		/* все ступени */

peer.valid <- 0;
peer.dispersion <- ntp.maxdisperse;

{peer.hostpoll <- ntp.minpoll};

/* первичная установка периода рассылки */

call poll-update;

call clock-select;

/* Выбор эталонных часов */

end clear procedure;

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

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

begin poll-update procedure

temp <- peer.hostpoll;

/* определение периода запросов ЭВМ */

if (peer = sys.peer)
temp <- min (temp, {sys.poll, ntp.maxpoll)};
else
temp <- min (temp, ntp.maxpoll);
peer.hostpoll <- max (temp, ntp.minpoll);
temp <- 1 <

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

if (peer.timer = 0)

/* сброс таймера партнера */

peer.timer <- temp;
else if (peer.timer >temp)
peer.timer <- (sys.clock & (temp - 1)) + 1;
end poll-update procedure;

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

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

begin distance(peer) procedure;
d <- {peer.rootdelay + |peer.delay|};
e <- {peer.rootdispersion + peer.dispersion + f (sys.clock - peer.update)};
l<-e + |d|/2;
end distance procedure;

Заметим, что, в то время как d может быть в некоторых случаях отрицательной, e и l всегда положительны.

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

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

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

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

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

Для того чтобы NTP алгоритмы фильтрации и отбора работали эффективно, полезно иметь меру вариации для каждого из партнеров. Принятая мера вариации базируется на разностях первого порядка, которые легко вычислить. Существует две меры, одна называемая дисперсией фильтра e_s, и другая дисперсия выбора (select dispersion) e_z. Обе меры вычисляются как взвешенные суммы смещений из списка, сформированного на основе расстояний синхронизации. Если q_i (0Ј i < n) смещение i-ой записи, тогда разность e_ij i-ой записи по отношению к j-ой записи определяется как |q_i - q _j|. Дисперсия относительно j-ой записи определяется как e_j = , где w - весовой коэффициент, который служит для учета влияния расстояния синхронизации на дисперсию. В алгоритмах NTP w выбирается меньше 1/2: w = ntp.filter для дисперсии фильтра (filter dispersion) и w = NTP.SELECT для дисперсии выбора (select dispersion).
Дисперсия e_s и e_x определены относительно 0-ой записи e₀.

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

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

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

Процедура часового фильтра использует сдвиговый регистр (peer.filter), который состоит из NTP.SHIFT каскадов, каждый каскад содержит значения q_i, d_i и e _i, которые пронумерованы, начиная с нуля, слева направо. Фильтр инициализируется процедурой очистки при этом заносятся значения [0, 0, NTP.MAXDISPERSE] во всех каскадах. Новые данные записей вдвигаются в фильтр с левого конца. Пакетная процедура выдает записи в формате (q ,d, e), когда приходят новые корректирующие данные, в то время как процедура передачи выдает записи в форме [0, 0, NTP.MAXDISPERSE], когда истекает два периода запроса без поступления свежих данных. Когда одни и те же символы (q, d, e) используютсядля аргументов, содержимого часового фильтра и переменных партнера, их значения обычно понятно из контекста. Ниже представлена псевдопрограмма, поясняющая работу данной процедуры.

begin clock-filter procedure (q, d, e)

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

for (i from ntp.size 1 to 1) begin

/* коррекция дисперсии */

[q_i, d_i, e_i] <- [q_{i-1}, d_{i-1}, e_{i-1}];
/* shift stage right */
e_i = e_i + ft;
add [l_i ≡ e_i + {|d_i|}/2, i] to temporary list;
endfor;

[q₀, d₀, e₀] <- [q, d, e];

/* ввести новую запись */

add [l ≡ e + {|d|}/2, 0] to temporary list;

peer.update <- sys.clock;

/* сбросить показание часов */

sort temporary list by increasing [distance ||index];

где [distance ||index] представляет собой объединение полей расстояния и индекса (расстояние занимает старшую позицию). Дисперсия фильтра e_s вычисляется и включается в дисперсию партнера. Заметим, что временный список для этой цели уже упорядочен.

e_s <- 0;

for (i from ntp.shift-1 to 0)

/* вычисление дисперсии фильтра */

if (peer.dispersion_index[i] ≥ NTP.MAXDISPERSE or |q_i - q₀ > NTP.MAXDISPERSE)
e_s <- (e_s + NTP.MAXDISPERSE) * NTP.FILTER;
else
e_s <- (e_s + |q_i - q₀|) * NTP.FILTER;

Смещение партнера q₀, задержка d₀ и дисперсия e₀ выбираются как величины, соответствующие записи с минимальным расстоянием; другими словами, записи, соответствующей первому элементу временного списка (в данной нотации имеет индекс 0).

peer.offset <- q₀;

/* корректировка переменных партнера */

peer.delay <- d₀;
peer.dispersion <- min(e₀ + e_s, NTP.MAXDISPERSE);
end clock-filter procedure

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

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

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

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

begin clock-selection procedure

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

m <- 0;

for (each peer)

/*обращение ко всем партнерам */

if ({peer.reach ≠ 0 and peer.dispersion < ntp.maxdisperse} and not (peer.stratum > 1 И peer.refid = peer.hostaddr)) begin
l

andistance (peer);

/* запись в список */

add [q - l, -1] to endpoint list;
add [q, 0] to endpoint list;
add [q + l, 1] to endpoint list;
m <- m + 1;
<B>endif
endfor

if (m = 0) begin

/* уход, если кандидаты отсутствуют */

sys.peer <- null;
sys.stratum <- 0 (undefined);
exit;
endif
sort endpoint list by increasing endpoint||type;

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

for (f from 0 to f ≥ m/2) begin

/* обращение ко всем кандидатам */

c <- 0;
i <- 0;

for (each [endpoint, type] from lowest) begin

/* нахождение нижней границы */

i <- i - type;
low <- endpoint;
if (i ≥ m - f) break;
if (type = 0) c <- c + 1;
endfor;
i <- 0;

for (each [endpoint, type] from highest) begin

/* нахождение верхней границы */

i <- i + type;
high <- endpoint;
if (i ≥ m - f) break;
if (type = 0 ) c <- c + 1;
endfor;

if (c ≤ f) break;

/* продолжить, пока не будут найдены все ложные кандидаты */

endfor;

if (low > high) begin

/* завершить, если не найдено ни одного пересечения */

sys.peer <- null;
exit;
endif;

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

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

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

m <- 0;

for (each peer) begin

/* обращение ко всем партнерам */

if (low ≤ q ≤ high) begin

l <- distance (peer);

/* сформировать запись в списке */

dist <- {peer.stratum * NTP.MAXDISPERSE + l}
add [dist, peer] to candidate list;
m <- m + 1;
endif;
endfor;
sort candidate list by increasing dist;

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

Заметим, что e_xi представляет собой дисперсию относительно i-го партнера из списка кандидатов, которая может быть вычислена методом дисперсии фильтра, описанным выше. e_j - дисперсия j-ого партнера из списка, включающая в себя вклады от ошибок измерения, от накопления дрейфа и из-за дисперсии фильтра. Если максимальное значение e_xi больше чем минимальное значение e_j, а число кандидатов больше чем ntp.minclock, i-ый партнер удаляется из списка и процедура повторяется. Если текущий источник синхронизации является одним из членов списка и нет других кандидатов из более низкого слоя, процедура прерывается, и никакие другие последующие шаги не предпринимаются. В противном случае в качестве источника синхронизации берется первый кандидат из списка. В ниже приведенном тексте i, j, k, l - индексы партнеров, k - индекс текущего источника синхронизации (нуль, если такой источник отсутствует), l - индекс первого кандидата в списке.

while begin

for (each survivor [distance, index]) begin

/* вычисление дисперсии */

find index i for max e_{xi};
find index j for min e_j;
endfor
if (e_{xi} ≤ e_j or m ≤ NTP.MINCLOCK) break;

peer.survivor [i] <- 0;

/* отбрасывание i-го партнера */

if (i = k) sys.peer <- null;
delete the ith peer from the candidate list;
m <- m - 1;
endwhile
if (peer.survivor [k] = 0 or peer.stratum [k] >> peer.stratum [l]) begin
sys.peer <- l; /* новый источник часов */
call poll-update;
endif
end clock-select procedure;

Алгоритм сконструирован так, чтобы отдавать предпочтение партнерам из головной части списка, которые размещены в более низком слое, имеют наименьшее расстояние и могут обеспечить наибольшую точность и стабильность. С помощью правильного выбора весового коэффициента 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 - число начальных нулей в коде счетчика W@atchdog. Тогда 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), биты добавления делаются равными 112 (не синхронизовано) и вызывается процедура очистки часовых фильтров и переменных состояния для всех партнеров. На практике необходимость корректировать показания часов скачкообразно случается крайне редко, когда, например, локальные часы или эталон перезагружаются.

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

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

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

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

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

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

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

Рис. 4.4.15.1. Формат сообщения NTP.

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

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

Слой (Stratum) - 8-битовое поле, определяющее код слоя, где работают локальные часы. Коды слоя представлены в таблице 4.4.15.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 не специфицирован, предлагаются ascii- идентификаторы, приведенные в таблице 4.4.15.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-сообщений показан на рис. 4.4.15.2. Этот заголовок располагается непосредственно вслед за UDP-заголовком.

Рис. 4.4.15.2. Формат управляющего сообщения ntp

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

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

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

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

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

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

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

Таблица 4.4.15.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) - двухбитовое поле предупреждения о предстоящем добавлении/вычитании секунды к последней минуте текущего дня. Значения этих битов смотри в таблице 4.4.15.1.

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

Таблица 4.4.15.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.

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

Таблица 4.4.15.7. Коды системных событий

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

Статусное слово партнера

Статусное слово партнера возвращается в статусном поле отклика на команду чтения статуса, а также чтения или записи переменных. Это слово появляется в списке идентификаторов ассоциации и статусных слов, присылаемых в ответ на команду чтения статуса с нулевым идентификатором ассоциации. Формат статусного слова партнера содержит следующие поля (рис. 4.4.15.3)

Рис. 4.4.15.3. Форматы статусных слов

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

Таблица 4.4.15.8. Коды состояния партнера

Значение кода	Функция
0	Сконфигурирован (peer.config)
1	Разрешена аутентификация (peer.authenable)
2	Аутентификация успешна (peer.authentic)
3	Партнер доступен (peer.reach)
4	Зарезервировано на будущее

Выбор партнера (Sel) - 3-битный код, говорящий о состоянии партнера, определенного в результате процедуры выбора часов. Значения кодов представлены в таблице 4.4.15.9.

Таблица 4.4.15.9. Коды выбора партнера

Значение кода	Функция
0	Отклонен
1	Проверка соответствия прошла успешно (тесты 1 - 8)
2	Прошел проверки корректности (алгоритм пересечения)
3	Прошел проверки, как кандидат
4	Проверка ресурсов прошла успешно (алгоритм кластеризации)
5	Текущий источник синхронизации; превышено максимальное расстояние (если используются предельные проверки)
6	Текущий источник синхронизации; максимальное расстояние в пределах нормы
7	Зарезервировано на будущее

Счетчик событий партнера - 4-битовое число событий (exception) партнера, которые имели место со времени последнего получения статусного слова в рамках отклика или сообщения TRAP. Счетчик сбрасывается при занесении кода в поле статуса отклика, и перестает изменяться при достижении значения 15.

Код события партнера - 4-битовое целое число, идентифицирующее последнее событие партнера. Новое значение переписывает предыдущее. Значения кодов представлены в таблице 4.4.15.10.

Таблица 4.4.15.10. Коды события партнера

Значение кода	Функция
0	Не специфицировано
1	IP-ошибка партнера
2	Ошибка аутентификации партнера (бит peer.authentic был равен 1, а теперь =0)
3	Партнер не достижим (peer.reach стал равен нулю)
4	Партнер достижим (peer.reach стал не равен нулю)
5	Проблема с часами партнера
6-15	Зарезервировано на будущее

Слово состояния часов

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

Состояние часов - 8-битовое число, характеризующее текущее состояние часов. Допустимые значения этого числа и их смысл представлены в таблице 4.4.15.11.

Таблица 4.4.15.11. Коды состояния часов

Код	Функция
0	Работа часов в пределах нормы
1	Таймаут ответа
2	Плохой формат ответа
3	Сбой оборудования или программы
4	Потеря при передаче
5	Неверный формат или значение даты
6	Неверный формат или значение времени
7-255	Зарезервировано на будущее

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

Слово состояния ошибки

Статусное слово ошибки присылается в поле статуса отклика, если обнаружена ошибка в формате сообщения или в его содержимом. Его присутствие указывается равенствами E (error) и R (response) битов 1. Коды ошибки и их значения собраны в таблице 4.4.15.12.

Таблица 4.4.15.12. Коды ошибки

Код ошибки	Значение
0	Не специфицировано
1	Неудачная аутентификация
2	Неверный формат или длина сообщения
3	Неверный код операции
4	Неизвестный идентификатор ассоциации
5	Неизвестное имя переменной
6	Неверное значение переменной
7	Административно запрещено
8-255	Зарезервировано на будущее

Команды

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

[=],[=],...

где представляет собой имя переменной системы или партнера в форме ASCII-последовательности, а является десятичным или шестнадцатеричным числом, или строкой, соответствующей синтаксису языка C. Для большей читаемости допускается применение пробелов (Whitespace). IP-адреса представляются в формате [n.n.n.n], где n - десятичное число. Скобки являются опционными.

Команды интерпретируются следующим образом:

Чтение статуса (1). Поле данных команды пусто или содержит список идентификаторов, разделенных запятыми. Команда работает по-разному в зависимости от значения идентификатора. Если идентификатор не равен нулю, отклик содержит идентификатор партнера и статусное слово. Если идентификатор ассоциации равен нулю, отклик содержит системный идентификатор (0) и статусное слово, в то время как поле данных содержит список пар двоичных кодов:

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

по одному на каждую, определенную в данный момент ассоциацию.

Чтение переменных (2). Поле данных команды пусто или содержит список идентификаторов, разделенных запятыми. Если идентификатор ассоциации не равен нулю, отклик включает в себя идентификатор запрашиваемого партнера и его статусное слово, в то время как в поле данных записывается список переменных партнера и их значения. Если идентификатор ассоциации равен нулю, поле данных содержит список системных переменных и их значения. Если партнер выбран в качестве источника синхронизации, отклик включает в себя идентификатор партнера и его статусное слово.

Запись переменных (3). Поле данных команды содержит список присвоений, описанный выше. Отклик идентичен отклику на команду чтения переменных.

Чтение переменных часов (4). Поле данных команды пусто или содержит список идентификаторов, разделенных запятыми. Идентификатор ассоциации выбирает переменные системных часов или партнера точно также, как в случае команды чтения переменных. Отклик включает в себя запрошенные идентификатор часов и статусное слово, а поле данных несет в себе список переменных часов и их значений, включая последний временной код, полученный от часов.

Запись переменных часов (5). Поле данных команды содержит список присвоений, как это описано выше. Отклик имеет формат, как в случае команду чтения переменных часов.

Установка адреса/порта Trap (6). Идентификатор ассоциации команды, статус и поле данных игнорируются. Адрес и номер порта для последующих TRAP-сообщений берутся из самого управляющего сообщения. Исходное значение счетчика TRAP для сообщений откликов заимствуется из поля номера по порядку. Идентификатор ассоциации, статус и поле данных в отклике несущественны.

Отклик на TRAP (7). Это сообщение посылается, когда происходит событие (exception) в систему, у партнера или для данных часов. Код команды равен 7, а бит R=1. Содержимое trap-счетчика увеличивается на 1 для каждого сообщения данного типа. Поле номер по порядку сообщения равно содержимому этого счетчика. При посылке сообщения TRAP используется IP-адрес и номер порта, заданные командой установки адреса и порта TRAP. В случае системного TRAP идентификатор ассоциации устанавливается равным нулю, а поле статус содержит статусное слово системы. В случае TRAP партнера поле идентификатора ассоциации соответствует партнеру, а поле статус несет в себе его статусное слово. В поле данных опционно может быть включено любое символьное сообщение (ASCII).

Приложение В. Аутентификация

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

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

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

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

Процедура вычисления контрольной крипто-суммы использует алгоритм DES (Data Encryption Standard) [NBS77].

Механизм аутентификации NTP

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

Бит разрешения аутентификации (peer.authenable). Этот бит указывает, что ассоциация работает в режиме аутентификации. Для сконфигурированных партнеров этот бит определяется на фазе инициализации. Для неконфигурированных - этот бит делается равным 1, если приходящее сообщение содержит аутентификатор, в противном случае =0.

Бит аутентификации (peer.authentic). Этот бит указывает, что последнее сообщение, полученное от партнера, было корректно аутентифицировано.

Идентификатор ключа (peer.hostkeyid, peer.peerkeyid, pkt.keyid). Это целое число идентифицирует криптографический ключ, используемый для генерации кода аутентификации сообщения. Системная переменная peer.hostkeyid используется для активной ассоциации. Переменная peer.peerkeyid инициализируется нулем, когда ассоциация сформирована.

Криптографические ключи (sys.key). Это набор 64-битовых ключей DES, где 7 младших бит каждого октета соответствуют битам 1-7 DES, а старший бит соответствует биту четности 8 (сумма нечетна).

Контрольная крипто-сумма (pkt.check). Крипто-сумма вычисляется процедурой шифрования.

Поле аутентификатора состоит из двух субполей, одно содержит переменную pkt.keyid, а другое переменную pkt.check, вычисленную программой шифрования, вызываемой процедурой передачи протокола NTP, а также программой дешифровки, которая вызывается процедурой приема NTP. Ее присутствия определяется по общей длине UDP-дейтограммы. Для целей аутентификации NTP-сообщение дополняется нулями, для того чтобы сделать ее длину кратной 64 битам. Аутентификатор содержит 96 бит, куда входят 32-битовый идентификатор ключа и 64-битовая крипто-сумма. Дополнительная информация (например, о сертификате и алгоритме шифрования), если необходимо, может быть вставлена между NTP-сообщением и идентификатором ключа. Подобно аутентификатору эта информация не включается в контрольное крипто-суммирование.

Процедуры аутентификации NTP

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

Приложение Г. Временная шкала NTP и ее хронометрия

Ниже рассматривается соответствие временной шкалы NTP и UTC (Coordinated Universal Time). Синхронизация часов предполагает их согласование по частоте и времени.

Для синхронизации необходимо уметь сравнить их частоты и показания. Базовыми источниками временных стандартов традиционно являлись периоды движения Земли, Луны и других космических объектов. К сожалению, они не слишком стабильны.

Первичная частота и стандарты времени

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

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

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

Обычно часовые осцилляторы классифицируются по трем параметрам: стабильность, разброс и блуждание. Стабильность определяется систематическими вариациями частоты со временем. Синонимом нестабильности является старение и дрейф. Разброс (называемый также временным дрожанием) характеризует кратковременные случайные вариации частоты с составляющими более 10 Гц, в то время как блуждание характеризует медленные вариации частоты с составляющими менее 10 Гц.

Таблица 4.4.15.12. Точность и стабильность часов для различных слоев

Слой	Минимальная точность (за день)	Минимальная стабильность (за день)
1	1 x 10^-11	Не специфицировано
2	1.6 x 10^-8	1 x 10^-10
3	4.6 x 10^-6	3.7 x 10^-7
4	3.2 x 10^-5	Не специфицировано

Конструкция, работа и характеристики осциллятора слоя 1 предполагаются сопоставимыми с национальными стандартами времени и часто базируются на цезиевом стандарте. Часы слоя 4 соответствуют требованиям обычных цифровых каналов и систем PBX. Слои 2-3 могут использоваться для работы с мощными синхронными каналами связи.

Раздача времени и частоты

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

Американский Национальный Институт Стандартов и Технологии (NIST – National Institute of Standards and Technology) поддерживает три радиослужбы для рассылки временной информации. Одна из них использует передачу (ВЧ или CCIR диапазон 7) на частотах 2.5, 5, 10, 15 и 20 Мгц. Сигнал распространяется, отражаясь от верхних слоев атмосферы, что неизбежно приводит к непредсказуемым вариациям задержки на принимающей стороне. С 60-секундным интервалом передается временной код, который транслируется на 100 килогерцной субнесущей со скоростью передачи 1 бит/с. Этот код содержит информацию об UTC времени и дате, но не включает в себя данных о текущем годе и оповещения о добавлении/вычитании секунды для последней минуты данного дня. Существуют и другие сходные службы времени (например, в Оттаве), гарантирующие точность на уровне 1-10 мсек.

Вторая служба времени NIST использует передачу (НЧ или CCIR диапазон 5) на частоте 60 КГц, она доступна на континентальной части США и вблизи берегов. Сигнал распространяется в нижней части атмосферы и по этой причине слабо подвержен вариациям времени распространения. Временной код передается с периодом в 60 секунд со скоростью 1 бит/с. Достижимая точность составляет 50 миллисекунд [BLA74]. Ряд европейских стран предлагают аналогичные службы времени (Великобритания - MSF; Германия - DCF77). Коды времени здесь включают информацию о текущем годе и предупреждение о добавляемой/вычитаемой секунде. Третья служба NIST использует передачу на частоте 468 МГц (УВЧ или CCIR диапазон 9) с геостационарных спутников GOES, три из которых перекрывают западное полушарие. Временной код перемежается с сообщениями, адресованными удаленным датчикам и состоит из 600 4-битовых слов, передаваемых с периодом в 30 секунд. Временной код содержит информацию об UTC времени-дне-годе, а также предупреждение о добавлении/вычитании секунды в конце дня. Точность этой службы составляет 0,5 мсек.

Министерство обороны США разработало глобальную систему определения координат GPS (Global Positioning System). Эта система базируется на 24 спутниках, движущихся по орбитам с периодом 12 часов. Система GPS может обеспечить точность определения времени на уровне нескольких наносекунд [VAN84].

Американская береговая охрана в течение многих лет использует службу радионавигации LORAN-C [FRA82]. Эта служба обеспечивает временную точность менее 1 мксек.

Система радионавигации военно-морского флота США и других стран OMEGA [VAS78] состоит из 8 передатчиков, работающих на частотах от 10.2 до 13.1 КГц (УНЧ или CIR диапазон 4) и перекрывающих весь земной шар 24 часа в сутки. Точность этой системы составляет около 1 мсек. Система OMEGA обеспечивает высокую точность для частоты, но не передает временного кода. По этой причине приемник должен предварительно получить географические координаты с точностью до градуса и время UTC с точностью 5 секунд от независимых источников.

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

Определение частоты

В течение многих лет наиболее важным использованием времени и частоты были всемирная навигация и космическая наука, которые зависят от наблюдений солнца, луны и звезд. За стандартную секунду (в 1957 году) принята 1/31,556,925.9747 периода вращения Земли вокруг Солнца (тропический год). Согласно этой шкалы тропический год длится 365.2421987 дней, а лунный месяц 29.53059 дней. Однако тропический год может быть определен лишь с точностью около 50 мсек.

С древнейших времен человечеству были известны три осциллятора (процесса задающих временную шкалу) - вращение земли вокруг своей оси, вращение Луны вокруг Земли и вращение Земли вокруг Солнца. К сожалению, с точки требований современных технологий все эти три осциллятора не обладают достаточной стабильностью. В 1967 стандартная секунда была переопределена и теперь равняется 9,192,631,770 периодов перехода в атоме цезия-133. С 1972 стандарты времени и частоты базируются на международном атомном времени TAI (International Atomic Time). Точность таких часов составляет около микросекунды в сутки. Важно то, что новая шкала абсолютно однородна и не подвержена дрейфам.

Определение времени и необходимости добавления/вычитания секунды

Международное бюро мер и стандартов IBWM (International Bureau of Weights and Measures) использует астрономические наблюдения, выполненные морской обсерваторией США и другими обсерваториями для определения UTC.

Для более точной временной привязки событий после 1972 года необходимо знать, когда вставлялись или удалялись секунды коррекции (удаление пока никогда не производилось). Как определено в докладе 517 CCIR, который воспроизведен в [BLA74], дополнительные секунды вставляются после 23:59:59 в последний день июня или декабря. Неоднородность во временную шкалу (TAI) помимо добавляемых секунд вносят также 100 миллисекундные коррекции UT1, называемые DUT1, которые служат для повышения точности при навигации. Следует признать, что момент добавления секунды является началом новой (однородной) временной шкалы.

Временная шкала NTP базируется на шкале UTC, но необязательно всегда совпадает с ней. В 0 часов 1 января 1972 начинается эра UTC, часы NTP были установлены на 2,272,060,800 стандартных секунд после 0 часов 1 января 1900.

Ссылки

[ABA89]	Abate, et al. AT&T's new approach to the synchronization of telecommunication networks. IEEE Communications Magazine (April 1989), 35-45.
[ALL74a]	Allan, D.W., J.H. Shoaf and D. Halford. Statistics of time and frequency data analysis. In: Blair, B.E. (Ed.). Time and Frequency Theory and Fundamentals. National Bureau of Standards Monograph 140, U.S. Department of Commerce, 1974, 151-204.
[ALL74b]	Allan, D.W., J.E. Gray and H.E. Machlan. The National Bureau of Standards atomic time scale: generation, stability, accuracy and accessibility. In: Blair, B.E. (Ed.). Time and Frequency Theory and Fundamentals. National Bureau of Standards Monograph 140, U.S. Department of Commerce, 1974, 205-231.
[BEL86]	Bell Communications Research. Digital Synchronization Network Plan. Technical Advisory TA-NPL-000436, 1 November 1986.
[BER87]	Bertsekas, D., and R. Gallager. Data Networks. Prentice-Hall, Englewood Cliffs, NJ, 1987.
[BLA74]	Blair, B.E. Time and frequency dissemination: an overview of principles and techniques. In: Blair, B.E. (Ed.). Time and Frequency Theory and Fundamentals. National Bureau of Standards Monograph 140, U.S. Department of Commerce, 1974, 233-314.
[BRA80]	Braun, W.B. Short term frequency effects in networks of coupled oscillators. IEEE Trans. Communications COM-28, 8 (August 1980), 1269-1275
[COL88]	Cole, R., and C. Foxcroft. An experiment in clock synchronisation. The Computer Journal 31, 6 (1988), 496-502.
[DAR81a]	Defense Advanced Research Projects Agency. Internet Protocol. DARPA Network Working Group Report RFC-791, USC Information Sciences Institute, September 1981.
[DAR81b]	Defense Advanced Research Projects Agency. Internet Control Message Protocol. DARPA Network Working Group Report RFC-792, USC Information Sciences Institute, September 1981.
[DEC89]	Digital Time Service Functional Specification Version T.1.0.5. Digital Equipment Corporation, 1989
[DER90]	Dershowitz, N., and E.M. Reingold. Calendrical Calculations. Software Practice and Experience 20, 9 (September 1990), 899-928.
[FRA82]	Frank, R.L. History of LORAN-C. Navigation 29, 1 (Spring 1982).
[GUS84]	Gusella, R., and S. Zatti. TEMPO - A network time controller for a distributed Berkeley UNIX system. IEEE Distributed Processing Technical Committee Newsletter 6, NoSI-2 (June 1984), 7-15. Also in: Proc. Summer USENIX Conference (June 1984, Salt Lake City).
[GUS85a]	Gusella, R., and S. Zatti. The Berkeley UNIX 4.3BSD time synchronization protocol: protocol specification. Technical Report UCB/CSD 85/250, University of California, Berkeley, June 1985.
[GUS85b]	Gusella, R., and S. Zatti. An election algorithm for a distributed clock synchronization program. Technical Report UCB/CSD 86/275, University of California, Berkeley, December 1985.
[HAL84]	Halpern, J.Y., B. Simons, R. Strong and D. Dolly. Fault-tolerant clock synchronization. Proc. Third Annual ACM Symposium on Principles of Distributed Computing (August 1984), 89-102.
[JOR85]	Jordan, E.C. (Ed). Reference Data for Engineers, Seventh Edition. H.W. Sams & Co., New York, 1985.
[KOP87]	Kopetz, H., and W. Ochsenreiter. Clock synchronization in distributed real-time systems. IEEE Trans. Computers C-36, 8 (August 1987), 933-939.
[LAM78]	Lamport, L., Time, clocks and the ordering of events in a distributed system. Comm. ACM 21, 7 (July 1978), 558-565.
[LAM85]	Lamport, L., and P.M. Melliar-Smith. Synchronizing clocks in the presence of faults. J. ACM 32, 1 (January 1985), 52-78.
[LIN80]	Lindsay, W.C., and A.V. Kantak. Network synchronization of random signals. IEEE Trans. Communications COM-28, 8 (August 1980), 1260-1266.
[LUN84]	Lundelius, J., and N.A. Lynch. A new fault-tolerant algorithm for clock synchronization. Proc. Third Annual ACM Symposium on Principles of Distributed Computing (August 1984), 75-88.
[MAR85]	Marzullo, K., and S. Owicki. Maintaining the time in a distributed system. ACM Operating Systems Review 19, 3 (July 1985), 44-54.
[MIL81a]	Mills, D.L. Time Synchronization in DCNET Hosts. DARPA Internet Project Report IEN-173, COMSAT Laboratories, February 1981.
[MIL81b]	Mills, D.L. DCNET Internet Clock Service. DARPA Network Working Group Report RFC-778, COMSAT Laboratories, April 1981.
[MIL83a]	Mills, D.L. Internet Delay Experiments. DARPA Network Working Group Report RFC-889, M/A-COM Linkabit, December 1983.
[MIL83b]	Mills, D.L. DCN local-network protocols. DARPA Network Working Group Report RFC-891, M/A-COM Linkabit, December 1983.
[MIL85a]	Mills, D.L. Algorithms for synchronizing network clocks. DARPA Network Working Group Report RFC-956, M/A-COM Linkabit, September 1985.
[MIL85b]	Mills, D.L. Experiments in network clock synchronization. DARPA Network Working Group Report RFC-957, M/A-COM Linkabit, September 1985.
[MIL85c]	Mills, D.L. Network Time Protocol (NTP). DARPA Network Working Group Report RFC-958, M/A-COM Linkabit, September 1985.
[MIL88a]	Mills, D.L. Network Time Protocol (version 1) - specification and implementation. DARPA Network Working Group Report RFC-1059, University of Delaware, July 1988.
[MIL88b]	Mills, D.L. The Fuzzball. Proc. ACM SIGCOMM 88 Symposium (Palo Alto, CA, August 1988), 115-122.
[MIL89]	Mills, D.L. Network Time Protocol (version 2) - specification and implementation. DARPA Network Working Group Report RFC-1119, University of Delaware, September 1989.
[MIL90]	Mills, D.L. Measured performance of the Network Time Protocol in the Internet system. ACM Computer Communication Review 20, 1 (January 1990), 65-75.
[MIL91a]	Mills, D.L. Internet time synchronization: the Network Time Protocol. IEEE Trans. Communications 39, 10 (October 1991), 1482-1493.
[MIL91b]	Mills, D.L. On the chronology and metrology of computer network timescales and their application to the Network Time Protocol. ACM Computer Communications Review 21, 5 (October 1991), 8-17.
[MIT80]	Mitra, D. Network synchronization: analysis of a hybrid of master-slave and mutual synchronization. IEEE Trans. Communications COM-28, 8 (August 1980), 1245-1259.
[NBS77]	Data Encryption Standard. Federal Information Processing Standards Publication 46. National Bureau of Standards, U.S. Department of Commerce, 1977.
[NBS79]	Time and Frequency Dissemination Services. NBS Special Publication 432, U.S. Department of Commerce, 1979
[NBS80]	DES Modes of Operation. Federal Information Processing Standards Publication 81. National Bureau of Standards, U.S. Department of Commerce, December 1980.
[POS80]	Postel, J. User Datagram Protocol. DARPA Network Working Group Report RFC-768, USC Information Sciences Institute, August 1980.
[POS83a]	Postel, J. Daytime protocol. DARPA Network Working Group Report RFC-867, USC Information Sciences Institute, May 1983.
[POS83b]	Postel, J. Time protocol. DARPA Network Working Group Report RFC-868, USC Information Sciences Institute, May 1983.
[RIC88]	Rickert, N.W. Non Byzantine clock synchronization - a programming experiment. ACM Operating Systems Review 22, 1 (January 1988), 73-78.
[SCH86]	Schneider, F.B. A paradigm for reliable clock synchronization. Department of Computer Science Technical Report TR 86-735, Cornell University, February 1986.
[SMI86]	Smith, J. Modern Communications Circuits. McGraw-Hill, New York, NY, 1986.
[SRI87]	Srikanth, T.K., and S. Toueg. Optimal clock synchronization. J. ACM 34, 3 (July 1987), 626-645.
[STE88]	Steiner, J.G., C. Neuman, and J.I. Schiller. Kerberos: an authentication service for open network systems. Proc. Winter USENIX Conference (February 1988).
[SU81]	Su, Z. A specification of the Internet protocol (IP) timestamp option. DARPA Network Working Group Report RFC-781. SRI International, May 1981.
[TRI86]	Tripathi, S.K., and S.H. Chang. ETempo: a clock synchronization algorithm for hierarchical LANs - implementation and measurements. Systems Research Center Technical Report TR-86-48, University of Maryland, 1986.
[VAN84]	Van Dierendonck, A.J., and W.C. Melton. Applications of time transfer using NAVSTAR GPS. In: Global Positioning System, Papers Published in Navigation, Vol. II, Institute of Navigation, Washington, DC, 1984.
[VAS78]	Vass, E.R. OMEGA navigation system: present status and plans 1977-1980. Navigation 25, 1 (Spring 1978).