Berkrley Internet Name Domain. Иногда для этой цели выделяют специальную машину задача

Вид материала

Содержание

Подобный материал:

1 ... 30 31 32 33 34 35 36 37 ... 59

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

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

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

 = peer.offset,
 = peer.delay,
 = peer.dispersion =  +  + _,
 =  + ||/2,

где  = rtt,  - сдвиг часов,  - накопление сбоя,  = ntp.maxskew/ntp.maxage,  - момент времени передачи исходной временной метки (на основе  вычисляется  и ),  _ - дисперсия фильтра. Переменные, относящиеся к партнеру i, определяются следующим образом:

 _i =  _i,
 _i = peer.rootdelay +  _i,
 _i = peer.rootdispersion +  _i +  _i (максимальная дисперсия часов партнера),
_i= _i + |_i|/2,

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

 = комбинированное окончательное смещение (combined final offset),
 = _i,
e = _i + _ + ,
 = _i,

где _ дисперсия выбора (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 <-  (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;	/* обработка пакета */
	<>

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

<-="<-">

< послать="послать" отклик="отклик" немедленно="немедленно">

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;	< метки="метки" исходной="исходной" временной="временной" актуализация="актуализация">
<-="<-" pkt.poll;< peer.peerpoll="peer.peerpoll">	< скорректировать="скорректировать" рассылки="рассылки" период="период">

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, соответственно. Смещение часов , rtt= и дисперсия  ЭВМ по отношению к партнеру равны:

 = (t_i - t_i-3) - (t_i-1 - t_{i - 2}),
 = ((t_{i - 2} - t_i-3) + ( t_i-1 - t_i))/2,
 = (1 << sys.precision) +  (t_i - t_i-3),

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

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

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

test4 <- (|| < ntp.maxdisperse И 

Тест 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(, , );

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

end packet procedure;

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

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

begin clock-update procedure

call clock-select;

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

if (sys.peer ≠ peer) exit;

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

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

 andistance(peer);

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

if ( ≥ 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 <- ;
sys.rootdispersion <-  + max (_+ ||, 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;
 <- {peer.rootdelay + |peer.delay|};
 <- {peer.rootdispersion + peer.dispersion +  (sys.clock - peer.update)};
<- + ||/2;
end distance procedure;

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

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

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

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

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

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

Для того чтобы NTP алгоритмы фильтрации и отбора работали эффективно, полезно иметь меру вариации для каждого из партнеров. Принятая мера вариации базируется на разностях первого порядка, которые легко вычислить. Существует две меры, одна называемая дисперсией фильтра _, и другая дисперсия выбора (select dispersion) _. Обе меры вычисляются как взвешенные суммы смещений из списка, сформированного на основе расстояний синхронизации. Если _i (0 i < n) смещение i-ой записи, тогда разность _ij i-ой записи по отношению к j-ой записи определяется как |_i -  _j|. Дисперсия относительно j-ой записи определяется как _j = ,

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

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

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

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

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

begin clock-filter procedure (, , )

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

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

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

[_i, _i, _i] <- [_{i-1}, _{i-1}, _{i-1}];
/* shift stage right */
_i = _i + ;
add [_i ≡ _i + {|_i|}/2, i] to temporary list;
endfor;

[₀, ₀, ₀] <- [, , ];

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

add [ ≡  + {||}/2, 0] to temporary list;

peer.update <- sys.clock;

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

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

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

_ <- 0;

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

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

if (peer.dispersion_index[i] ≥ NTP.MAXDISPERSE or |_i - ₀ > NTP.MAXDISPERSE)
_ <- (_ + NTP.MAXDISPERSE) * NTP.FILTER;
else
_ <- (_ + |_i - ₀|) * NTP.FILTER;

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

peer.offset <- ₀;

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

peer.delay <- ₀;
peer.dispersion <- min(₀ + _, NTP.MAXDISPERSE);
end clock-filter procedure

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

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

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

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

begin clock-selection procedure

Каждый из партнеров просматривается последовательно и добавляется в конец списка, если он прошел ряд тестов. Для каждого из m кандидатов в список заносятся 3 записи в форме [указатель, тип]: [ - , - 1], [, 0] и [ + , 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


andistance (peer);

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

add [ - , -1] to endpoint list;
add [, 0] to endpoint list;
add [ + , 1] to endpoint list;
m <- m + 1;

Blog

Berkrley Internet Name Domain. Иногда для этой цели выделяют специальную машину задача

Содержание