Протоколы Internet


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


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

begin clock-selection procedure

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

m

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

<B>endif

endfor

if (m = 0) begin

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

sys.peer

sys.stratum

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

i

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

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

<


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



Книжный магазин