Примеры сетевых топологий


Сетевой протокол времени NTP - часть 34


Алгоритм кластеризации сортирует список кандидатов по кодам слоя и расстояния синхронизации. Системная переменная 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 endpointtype;

Ниже приведенный алгоритм представляет собой адаптированную версию 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/* обращение ко всем кандидатам */




Начало  Назад  Вперед