Запаренко Ю. В.
Національний Технічний Університет України «Київський Політехнічний Інститут»
СТАТИСТИЧНА СИНХРОНІЗАЦІЯ ЧАСУ У КОМП'ЮТЕРНИХ МЕРЕЖАХ
Вступ
Існує безліч задач - таких як проведення аукціонів, підтримка роботи бірж, синхронне зчитування і правильна часова інтерпретація свідчень з датчиків, підключених до мережі, і велика кількість інших - які вимагають того, щоб локальні годинники на всіх пристроях було синхронізовані.
Більшість електронних пристроїв мають вбудований годинник. Проте ці годинники, як правило кварцові, не є точними, та «розходяться» з часом один відносно одного.
Синхронізація часу - це процес пошуку загального базису часу у розподіленій системі.
Припустимо, що два вузли у мережі мають синхронізуватися між собою.
Один вузол посилає повідомлення зі своїм часом іншому вузлу. Тоді, якщо немає затримки при передачі повідомлення, сусідній вузол відразу дізнається, яка різниця між показаннями його годинника, та годинником свого сусіда.
Нажаль, у реальній комп'ютерній мережі різні затримки впливають на час доставки повідомлень, що робить синхронізацію часу набагато складнішою, ніж здається на перший погляд. Взагалі, необхідно переслати серію повідомлень, щоб оцінити відносні зміщення часу між вузлами. У певному сенсі синхронізацію часу в мережі можна розглядати як процес видалення недетермінірованих затримок у часі передачі повідомлень по мережевих каналах.
Більшість протоколів синхронізації на практиці засновані виключно на детермінованих алгоритмах. Перевагою детермінованих методів є те, що вони зазвичай гарантують верхню межу помилки при оцінці часової різниці. Однак, коли системні ресурси вкрай обмежені, така гарантія точності синхронізації може привести до необхідності пересилати велику кількість повідомлень. У цих випадках ймовірнісні (статистичні) алгоритми можуть забезпечити достатню точність синхронізації з меншими накладними витратами, ніж детерміновані протоколи.
З іншого погляду, у критично важливих додатках (наприклад, моніторингу на атомних станціях), імовірнісних гарантій на точність може бути недостатньо.
Математична модель
Розглянемо модель двостороннього обміну повідомленнями для синхронізації двух вузлів.
Синхронізація між вузлами відбувається через передачу часових повідомлень у обох напрямках.
Повний варіант тексту за посиланням