時刻同期のアルゴリズム

ネットワークの世界では、時刻同期がとても重要視されます。時刻同期はとても簡単に言うと「みんなで同じ時計(時間)をみている」ことです。今回は時刻同期のプロトコルそのものではなく、時刻同期の本質とアルゴリズムについて考えてみます。

時計の時間がばらばらだと起こること

突然ですが問題です。

Q1.Aliceは家の時計で8:00に家を出発し、学校の時計で8:20に学校に到着しました。家と学校の移動時間は何分でしょう?

Q2.AliceとBobは、8:00に待ち合わせをしました。しかしながらAliceの時計は10分遅れていて、Bobの時計は5分進んでいます。
それぞれが自分の時計の時間通りに来たと仮定した場合、結局Bobはどれだけ待つことになるのでしょう?

A1.これは、家の時計と学校の時計が同じではないので、回答できません。学校の時計は家の時計に比べて進んでいるかもしれませんし遅れているかもしれません。この回答が「20分」であるためには、家と学校の時計があっている必要があります。

A2.実際の計算は「15分」ですが、これ、実際に起こったら非常に不便ですよね。2人だけならまだしも、これが100人になると何がなんだかわかりません。

Q1.のケースで、家の時計と学校の時計があっている場合、「家と学校の時刻は同期がとれている」と表現します。ネットワーク運用では、常に時刻同期を意識する必要があります。

時刻同期の方法

実際のネットワークでは、同じ時計を持つことは不可能です。ですので、みんなが「基準となる時計」に自分の時計をあわせるようにします。
時刻同期の方法には、主にふたつの方法があります。

  • 時報(のような仕組み)で合わせる方法
  • お互いの時刻から調整して時刻を合わせる方法

ネットワーク(WAN、LAN)の時刻同期として一般的によく使用されるプロトコルは、「NTP」と「PTP」です。
この2つは、仕様、精度、使える環境によりそれぞれ違った特長があります。NTPとPTPの違いは、検索すればたくさんの情報が出てきますので今回は割愛しますが、これらはともにお互いの時刻から調整して時刻を合わせる方法を採用しています。

お互いの時刻から調整するアルゴリズム

NTPやPTPが行っているお互いの時刻から調整するアルゴリズムについて解説します。
AliceとBobの間で時刻をあわせるとします。AliceからBob、BobからAliceへそれぞれメッセージを送信した際、4つの時刻が存在することになります。

時刻同期

t1 : AliceがBobへ送信したAliceの時刻
t2 : BobがAliceから受信したBobの時刻
t3 : BobがAliceへ送信したBobの時刻
t4 : AliceがBobから受信したAliceの時刻

その際、AliceからBob、BonからAliceへのメッセージの送信時間が同じだと過程した場合、往復時間は、

AliceとBobのメッセージの往復時間 (Round Trip Time) = (t2-t1) + (t4-t3)

ここでAliceの時計にBobが合わせるとした場合、Bobの差分は、

AliceとBobの時刻の差分 (Offset) = { (t2-t1) - (t4-t3) } / 2

となります。

ここで再び問題です。

Q3.Aliceは家の時計で8:00に家を出発し、学校の時計で8:20に学校に到着しました。その後学校の時計で8:30に出発して、家の時計で9:00に到着しました。
さて、家と学校の片道の移動時間は何分でしょう?ただし、行きと帰りの時間は同じとします。

A3.こちらはもう簡単ですね。上の公式と同じ考え方で、数字をあてはめればいいだけです。
まず往復時間を計算すると、(8:20 - 8:00) + (9:00 - 8:30) = 50分
これを片道で計算した場合、半分の25分となります。
このように、片道の時間(片側遅延)をはかるためには、行きと帰りの差分で計算することができます。

この仕組みを利用すれば、複数台の時計のずれを簡単に調整することが可能です。
たとえば、SYNESISのMFAという機能は、この仕組みで異なるデバイスでキャプチャしたpcapファイルの時刻を調整しています。

時刻同期の重要性

時刻同期がされていなかったためにアプリケーションデータを失う、セキュリティ攻撃を受けてもログが追跡できない、などのトラブルが発生するリスクが高まります。現在、社会インフラの多くがネットワークを介したシステムで稼働している以上、時刻同期は、利用されているシステムの運用、安全、品質に大きく関わってきます。
ですので、「みんなで同じ時計を見て行動する」ことは非常に重要です。

IETF参考ページ

NTP Standards Track

RFC7822 - Network Time Protocol Version 4 (NTPv4) Extension Fields

RFC5905 - Network Time Protocol Version 4: Protocol and Algorithms Specification

NTP Best Current Practice

RFC8633 - Network Time Protocol Best Current Practices

IETF Datatracker

NTPv5 use cases and requirements

あとがき

今回あらためて時刻同期関連の一次ソース情報を確認してみました。NTPはIETF、PTPはIEEEでそれぞれ標準化されています。
PTPは、IEEE1588で規定されていますが、IEEEの情報の多くは有償となっていますので、あまり詳細には確認できませんでした。(そのあたりがRFCと違い難しいです…。)
NTPは非常に古いプロトコルで、最初に標準化されたRFC958は1985年に発行されています。NTPはその後アップデートを繰り返し現在Ver.4が使用されています。また、すでにIETFではVer.5のドラフトが公開されています。NTPは現在においても現役で大活躍なプロトコルだということです。