1. はじめに

このドキュメントは、分散されたタイムサーバーとクライアントのセット間で時刻を同期するために使用されるネットワークタイムプロトコル（Network Time Protocol、NTP）バージョン3の正式な仕様を構成しています。これは、NTPによって使用されるアーキテクチャ、アルゴリズム、エンティティ、およびプロトコルを定義し、主に実装者を対象としています。付録ドキュメント[MIL91a]は、要件、分析モデル、アルゴリズム分析、および典型的なインターネット条件下での性能を要約しています。別のドキュメント[MIL91b]は、NTPタイムスケールと現在使用されている他の標準タイムスケールとの関係について説明しています。NTPは最初RFC-958 [MIL85c]で説明されましたが、その後大きく進化し、RFC-1119 [MIL89]で説明された最新のNTPバージョン2に至りました。これは、コネクションレストランスポートメカニズムを提供するインターネットプロトコル（IP）[DAR81a]およびユーザーデータグラムプロトコル（UDP）[POS80]上に構築されていますが、他のプロトコルスイートにも容易に適応できます。NTPは、タイムプロトコル（Time Protocol）[POS83b]およびICMPタイムスタンプメッセージ（ICMP Timestamp message）[DAR81b]から進化しましたが、複数のゲートウェイ、高度に分散した遅延、および信頼性の低いネットワークを含む典型的なインターネットパス上で使用される場合でも、精度と堅牢性を維持するように特別に設計されています。

サービス環境は、セクション2で説明される実装モデル（implementation model）とサービスモデル（service model）で構成されます。実装モデルはマルチプロセスオペレーティングシステムアーキテクチャに基づいていますが、他のアーキテクチャも使用できます。サービスモデルは、測定されたクロックオフセット（clock offsets）のみに依存し、信頼性の高いメッセージ配信を必要としない返却可能時間（returnable-time）設計に基づいています。同期サブネット（synchronization subnet）は、自己組織化された階層的マスタースレーブ構成（hierarchical-master-slave configuration）を使用し、同期パスは最小重み全域木（minimum-weight spanning tree）によって決定されます。複数のマスター（プライマリサーバー、primary servers）が存在する可能性がありますが、選挙プロトコルは必要ありません。

NTP自体はセクション3で説明されています。これは、原則として時間をナノ秒の精度に同期させながら、次の世紀まで明確な日付を保持するプロトコルメカニズムを提供します。このプロトコルには、ローカルクロックの特性を指定し、同期される可能性のあるタイムサーバーのエラーを推定する規定が含まれています。また、無線同期クロックなどの階層的に分散された相互に疑わしい複数のプライマリ参照ソースでの動作の規定も含まれています。

セクション4では、連続的に収集されたクロックオフセットサンプルのグリッチ除去（deglitching）と平滑化に役立つアルゴリズムについて説明します。これらのアルゴリズムは[MIL85a]で提案されたものから進化し、[MIL85b]で説明された実験結果に基づいて改良され、過去3年間の典型的な動作条件下でさらに進化しました。さらに、米国のいくつかのサイトで無線クロックを含む複数サーバーサブネットを運用し、米国およびヨーロッパのクライアントでの経験の結果として、故障したクロックを含む可能性のある集団から良好なクロックを選択するための信頼性の高いアルゴリズムが開発され[DEC89]、[MIL91a]、セクション4で説明されています。

NTPによって達成可能な精度は、ローカルクロックハードウェアの精度とデバイスおよびプロセス遅延の厳密な制御に大きく依存します。NTPによって生成される補正に応じてソフトウェア論理クロック時間と周波数を調整するための規定を含める必要があります。セクション5では、[MIL83b]および[MIL88b]で説明されているFuzzball実装から進化したローカルクロック設計について説明します。この設計には、オフセット調整（offset-slewing）、周波数補償（frequency compensation）、およびグリッチ除去メカニズムが含まれており、プライマリ参照ソースとの同期が失われた長期間の後でも、ミリ秒の精度を実現できます。

付録Aでは、インターネットプロトコル（IP）およびユーザーデータグラムプロトコル（UDP）で使用されるNTPパケット形式の詳細を示し、付録Bでは、包括的なネットワーク監視機能が利用できない場合に使用できる推奨補助NTP制御メッセージ（NTP Control Message）の詳細を示します。付録Cには、アクセスを制御し、不正なデータ変更を防ぐために使用できるオプションの認証メカニズム（authentication mechanism）の仕様と実装の詳細が含まれており、付録DにはNTPバージョン3と以前のバージョンとの違いのリストが含まれています。付録Eは、コンピューターネットワークとNTPに特有の精密タイムスケールとカレンダー日付に関する問題を拡張します。付録Fは、複数のクロックの時間オフセットを組み合わせることによって精度を向上させるオプションのアルゴリズムについて説明します。付録Gは、NTPローカルクロックアルゴリズムの詳細な数学モデルと分析を提示します。付録Hは、エラーのソースと伝播を分析し、時間転送サービスに関連する正確性原理（correctness principles）を提示します。付録Iは、セクション4で説明されているクロックフィルター、クロック選択、および関連アルゴリズムのC言語コードセグメントを示しています。

1.1. 関連技術

インターネットプロトコルスイートでは、イベントが発生する時刻を記録および送信するための他のメカニズムが指定されており、Daytimeプロトコル（Daytime protocol）[POS83a]、タイムプロトコル（Time Protocol）[POS83b]、ICMPタイムスタンプメッセージ（ICMP Timestamp message）[DAR81b]、およびIPタイムスタンプオプション（IP Timestamp option）[SU81]が含まれます。インターネットで測定されたクロックオフセットとラウンドトリップ遅延に関する実験結果は、[MIL83a]、[MIL85b]、[COL88]、および[MIL88a]で議論されています。他の同期アルゴリズムは[LAM78]、[GUS84]、[HAL84]、[LUN84]、[LAM85]、[MAR85]、[MIL85a]、[MIL85b]、[MIL85c]、[GUS85b]、[SCH86]、[TRI86]、[RIC88]、[MIL88a]、[DEC89]、および[MIL91a]で議論されており、それらに基づくプロトコルは[MIL81a]、[MIL81b]、[MIL83b]、[GUS85a]、[MIL85c]、[TRI86]、[MIL88a]、[DEC89]、および[MIL91a]で説明されています。NTPは、それらから進化した技術と、線形システム（linear-systems）および合意（agreement）方法論の両方を使用します。デジタル電話ネットワーク同期の線形方法は[LIN80]で要約されており、クロック同期の合意方法は[LAM85]で要約されています。

デジタルタイムサービス（Digital Time Service、DTS）[DEC89]は、NTPと同じサービス目標の多くを持っています。DTS設計は、管理されたLANまたはLANクラスター環境で動作する場合の構成管理と正確性原理に重点を置いていますが、NTPは管理されていないグローバルインターネット環境で動作するサービスの精度と安定性に重点を置いています。DTSでは、同期サブネットは事務員（clerks）、サーバー（servers）、クーリエ（couriers）、およびタイムプロバイダー（time providers）で構成されます。NTP用語に関しては、タイムプロバイダーはプライマリ参照ソースであり、クーリエはローカル再配布のために1つ以上の遠隔プライマリサーバーから時刻をインポートすることを目的としたセカンダリサーバーであり、サーバーは多数のエンドノードまたは事務員に時刻を提供することを目的としています。NTPとは異なり、DTSはクロック選択でモードまたはストラタム情報（mode or stratum information）を必要または使用せず、タイミングノイズをフィルター処理したり、推定上正しいクロックのセットから最も正確なものを選択したり、固有の周波数エラーを補償したりする規定を含みません。

実際、NTPの最新の改訂では、正確性原理をサポートするためにDTSの特定の機能を採用しています。これには、時間転送手順に固有の最大エラーを制限するメカニズムと、クロック選択手順で不適切なピアを拒否するための証明可能に正しい（規定された仮定の下で）メカニズムの使用が含まれます。これらの機能は、このドキュメントのセクション4および付録Hで説明されています。

Fuzzballルーティングプロトコル（Fuzzball routing protocol）[MIL83b]は、Hellospeakと呼ばれることもあり、時間同期をルーティングプロトコル設計に直接組み込んでいます。1つ以上のプロセスが無線クロックやNTPデーモンなどの外部参照ソースに同期し、ルーティングアルゴリズムがこれらのプロセスをルートとする最小重み全域木を構築します。次に、クロックオフセットが全域木のアークに沿ってシステム内のすべてのプロセスに配布され、このドキュメントのセクション5で説明されている手順を使用してさまざまなプロセスクロックが補正されます。Hellospeakの設計がNTPの設計に強く影響を与えたことがわかりますが、Hellospeak自体はインターネットプロトコルではなく、ローカルネット環境外での使用には適していません。

Unix 4.3bsdタイムデーモンtimed [GUS85a]は、単一のマスタータイムデーモンを使用して多数のスレーブホストのオフセットを測定し、それらに定期的な補正を送信します。このモデルでは、マスターは選挙アルゴリズム（election algorithm）[GUS85b]を使用して決定されます。これは、マスターが選出されない、または複数のマスターが選出される状況を回避するように設計されています。選挙プロセスにはブロードキャスト機能が必要ですが、これはインターネットの普遍的な機能ではありません。このモデルは、あるネットワーク上のスレーブが別のネットワーク上のマスターとして機能する階層構成をサポートするように拡張されていますが[TRI86]、モデルは階層を確立しループを回避するために手作業で構成テーブルを作成する必要があります。選挙プロセスの負担の大きいが恐らく頻度の低いオーバーヘッドに加えて、オフセット測定/補正プロセスは更新ごとにNTPの2倍のメッセージを必要とします。

[KOP87]では、NTPに似た機能を持つスキームが説明されています。このスキームは、複数のタイムサーバーのセットの各々が定期的なタイムスタンプメッセージを使用してセット内の他の各サーバーに対する相対的なローカル時刻オフセットを決定し、次に[LUN84]のフォールトトレラント平均（Fault-Tolerant Average、FTA）アルゴリズムを使用してローカルクロック補正を決定するマルチサーバーLANを対象としています。最大k個のサーバーが故障している可能性がある場合に有用なFTAアルゴリズムは、オフセットをソートし、k個の最高値と最低値を破棄し、残りを平均化します。[SCH86]で説明されているように、このスキームはブロードキャストをサポートするLAN環境に最も適しており、インターネット環境では許容できないオーバーヘッドをもたらします。さらに、この論文のセクション4で示される理由により、FTAアルゴリズムの統計的特性は、高度に分散した遅延を持つインターネット環境では最適ではない可能性があります。

一部のクロックが信頼できないコミュニティで正確な時刻を維持する問題には、多くの研究が行われてきました。真の計時器（truechimer）は、以前に公開された（信頼された）標準に対して計時精度を維持するクロックであり、偽の計時器（falseticker）はそうでないクロックです。特定のクロックが真の計時器か偽の計時器かを判断することは、[LAM85]および[SRI87]で要約されている合意方法を使用して攻撃できる興味深い抽象的な問題です。

収束関数（convergence function）は、システム内のクロック間のオフセットに作用して、偽の計時器によって引き起こされるエラーを削減または排除することによって精度を高めます。収束関数には2つのクラスがあり、対話収束アルゴリズム（interactive-convergence algorithms）を含むものと、対話整合性アルゴリズム（interactive-consistency algorithms）を含むものがあります。対話収束アルゴリズムは、[HAL84]のフォールトトレラント平均アルゴリズム、[LUN84]のCNVアルゴリズム、[MIL85a]の多数サブセットアルゴリズム、[RIC88]の非ビザンチンアルゴリズム、[SCH86]の自己中心的アルゴリズム、[MAR85]および[DEC89]の交差アルゴリズム、およびこのドキュメントのセクション4のアルゴリズムなどの統計的クラスタリング技術を使用します。

対話整合性アルゴリズムは、連続した読み取りまたは異なる読み取り装置に対して著しく一貫性のないオフセットを示す可能性のある故障したクロックプロセスを検出するように設計されています。これらのアルゴリズムは、連続したラウンドの読み取りを含む合意プロトコルを使用し、中継される可能性があり、デジタル署名によって補強される可能性があります。例には、[HAL84]の花火アルゴリズムと[SRI87]の最適アルゴリズムが含まれます。ただし、これらのアルゴリズムは、特に多数のクロックが関与する場合に大量のメッセージを必要とし、インターネットの経験ではめったに見られない障害を検出するように設計されています。これらの理由から、このドキュメントではこれらをさらに検討しません。

実際には、特に階層構成と統計的にノイズの多いインターネットを使用して、統計的基準以外で真の計時器と偽の計時器を決定することは不可能です。時間転送手順の最大エラーを制限することは可能ですが、ハードウェアコンポーネントに十分に寛大な許容値が採用されていると仮定すると、これは一般的にかなり悪い精度と安定性をもたらします。NTP設計とその前身で採用されたアプローチには、相互結合発振器（mutually coupled oscillators）と最尤推定（maximum-likelihood estimation）およびクロック選択手順、ならびにプライマリ参照ソースの正確性に関する規定された仮定に対してエラー境界に関する証明可能な主張を行うことを可能にする設計が含まれます。分析的な観点から、分散NTPピアのシステムは、結合位相同期発振器（coupled phase-locked oscillators）のセットとして動作し、更新アルゴリズムは位相検出器として機能し、ローカルクロックは規律発振器（disciplined oscillator）として機能しますが、時間転送プロセスの各ステップで決定論的エラー境界が計算されます。

セクション3で説明されているオフセット測定および計算手順の特定の選択は、一部のデジタル電話ネットワーク[LIN80]で使用される返却可能時間システム（returnable-time system）のバリアントです。クロックフィルターと選択アルゴリズムは、クロック同期サブネットが階層的マスタースレーブ構成[MIT80]に自己組織化するように設計されています。計時精度と安定性に関して、NTPとデジタル電話システムの類似性は偶然ではありません。このようなシステムは広範囲に研究されてきました[LIN80]、[BRA80]。NTPモデルをユニークにするのは、遍在するインターネット環境に適合するようにシステムのダイナミクスを調整する適応構成、ポーリング、フィルタリング、選択、および正確性メカニズムです。