Алгоритм пересечения
Алгоритм пересечения — это алгоритм согласования, используемый для выбора источников для оценки точного времени из ряда зашумленных источников времени. Он является частью современного протокола сетевого времени . Это модифицированная форма алгоритма Марзулло . [1] [2]
Хотя алгоритм Марзулло вернет наименьший интервал, соответствующий наибольшему количеству источников, [1] Возвращаемый интервал не обязательно включает центральную точку (расчетное смещение) всех источников на пересечении. Алгоритм пересечения возвращает интервал, включающий в себя интервал, возвращаемый алгоритмом Марзулло, но может быть больше, поскольку он будет включать центральные точки. Этот больший интервал позволяет использовать дополнительные статистические данные для выбора точки внутри интервала, уменьшая дрожание при повторном выполнении.
Метод
[ редактировать ]Учитывая M интервалов формы c ± r (что означает [ c − r , c + r ]), алгоритм пытается найти интервал с M − f источниками. Значение f называется количеством ложных меток, тех источников, которые содержат ошибку (фактическое значение находится за пределами доверительного интервала ). Наилучшей оценкой является та, которая предполагает наименьшее количество фальшивых билетов f . Результаты будут считаться действительными, если f < M /2, в противном случае алгоритм вместо интервала вернет ошибку.
Алгоритм пересечения начинается с создания таблицы кортежей <offset, type>. Для каждого интервала есть три записи: нижняя конечная точка, средняя точка и верхняя конечная точка, помеченные типами -1, 0 и +1 соответственно. Таким образом, интервал c ± r приводит к появлению записей < c − r ,−1>, < c ,0> и < c + r ,+1>. Эти записи затем сортируются по смещению.
Переменные: этот алгоритм использует f как количество ложных тикеров, а endcount и middlecount являются целыми числами. Нижний и верхний — значения смещений.
- [инициализировать лучший f] Начните с f = 0, предполагая, что все входные интервалы действительны. Каждый раз, когда интервал не найден, f будет увеличиваться до тех пор, пока интервал не будет найден или f ≥ M /2.
- [инициализировать] конечный счетчик = 0 и средний счетчик = 0.
- [найти нижнюю конечную точку] Начните с начала списка (наименьшее смещение), рассматривайте каждый кортеж по порядку. endcount = endcount — тип . Если endcount ≥ M − f , то low = offset и перейти к шагу 3, поскольку (возможная) нижняя конечная точка найдена. Если тип = 0, то средний счет = средний счет +1. Повторите со следующим кортежем. Если достигнут конец списка, перейдите к шагу 6.
- [найдена предварительная нижняя конечная точка, инициализируйте, чтобы найти верхнюю конечную точку] установите endcount =0.
- [определить количество средних точек] Начните с конца списка и двигайтесь к меньшим смещениям. endcount = endcount + тип . Если endcount ≥ M − f , то Upper = Offset , переходите к шагу 5. Если type = 0, то Midcount = Midcount +1. Повторите для следующего кортежа. Если достигнут конец списка, перейдите к шагу 6.
- если нижний ≤ верхний и средний счетчик ≤ f, то возвращается интервал [ нижняя конечная точка , верхняя конечная точка ] в качестве результирующего доверительного интервала.
- [увеличить количество фальшивых стикеров] f = f +1. Если f ≥ M /2, завершите операцию и верните FAILED, в противном случае перейдите к шагу 1.
Ссылки
[ редактировать ]- ^ Jump up to: а б Миллс, Д. (2013). «RFC 1305 — Спецификация, реализация и анализ протокола сетевого времени (версия 3)» . www.tools.ietf.org . дои : 10.17487/RFC1305 . Проверено 6 октября 2013 г.
Функциональная спецификация цифровой службы времени, версия T.1.0.5. Корпорация цифрового оборудования, 1989.
- ^ Функциональная спецификация цифровой службы времени, версия T.1.0.5. ЦифровойКорпорация оборудования, 1989.