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

• Поурочне планування курсу "Основи Інтернет – технологій", 88.8kb.
• Работа nat введение, 150.17kb.
• 1. Сервіси Internet, 731.38kb.
• 1. Сервіси Internet, 347.99kb.
• Internet Information Services (iis). Понимание организации сетей, tcp/ip и Domain Name, 17.07kb.
• Что такое Internet? Ресурсы Internet*, 347.7kb.
• Лабораторна робота №19 ”Internet”, 103.46kb.
• Е. Е. Израилевич Практическая грамматика английского языка с упражнениями и ключами, 14711.83kb.
• Математическая логика сквозь школьные предметы, 133.29kb.
• Мифы и реальности Internet известные и скрытые возможности сети Что такое Internet, 306.75kb.

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 только кандидаты, которые остаются в результате описанного выше отбора, могут участвовать в последующей обработке. Список кандидатов преобразуется к форме [расстояние, индекс], где расстояние вычисляется на основе кода слоя и расстояния синхронизации  партнера. Масштабный коэффициент позволяет реализовать механизм весового учета вкладов от кодов слоя и расстояния. Обычно, код слоя доминирует, если только один или более кандидатов имеют слишком большие расстояния. Список упорядочивается согласно величине расстояния.

m <- 0;

for (each peer) begin

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

if (low ≤  ≤ high) begin

 <- distance (peer);

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

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

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

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

while begin

for (each survivor [distance, index]) begin

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

find index i for max _i};
find index j for min _j;
endfor
if (_i} ≤ _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-битовый идентификатор. Для системных переменных используется идентификатор нуль. Управляющий объект может затребовать текущий список идентификаторов с тем, чтобы их использовать в дальнейшем. При попытке употребить уже недействительный идентификатор будет прислан соответствующий отклик, после чего необходимо запросить список идентификаторов еще раз.

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