4. フィルタリングと選択アルゴリズム

時間配信の精度と信頼性に影響を与える最も重要な要因は、さまざまなサブネットコンポーネント、参照ソース、または伝播メディアの障害による統計的エラーと誤計時器（falsetickers）の影響を減らすために使用されるアルゴリズムの複合体です。このセクションで提案されるアルゴリズムは、さまざまなトポロジー、速度、およびトラフィック体制の下でインターネット上で数年間の運用を通じて開発および改良されました。これらのアルゴリズムは現時点で利用可能な最良のものと考えられていますが、将来的に同様またはより優れた性能を持つ他のアルゴリズムが考案される可能性があるため、NTP仕様の不可欠な部分ではありません。

ただし、NTP同期サブネット内のすべてのタイムサーバーまたはクライアントがこれらのアルゴリズムを実装する必要があるわけではないことを観察することが重要です。たとえば、精度と信頼性の要件が正当化される場合、単純なワークステーションは簡素化のためにそれらの一方または両方を省略できます。それにもかかわらず、大学キャンパスや研究所などのかなりのコミュニティに同期を提供するNTPサーバーは、これらのアルゴリズムまたは同等の機能を持つことが証明された他のアルゴリズムを実装することが期待されます。設計原理と性能の包括的な議論は[MIL91a]に示されています。

NTPフィルターおよび選択アルゴリズムが効果的に動作するためには、各ピアについて最近のサンプル分散の測定値を記録することが有用です。採用される測定値は一次差分に基づいており、計算が容易で意図された目的に効果的です。2つの測定値があり、1つはフィルター分散（filter dispersion）ε_σと呼ばれ、もう1つは選択分散（select dispersion）ε_ξと呼ばれます。両方とも、同期距離でソートされた一時リスト内のクロックオフセットの加重和として計算されます。θ_i（0 <= i < n）がi番目のエントリのオフセットである場合、i番目のエントリのj番目のエントリに対するサンプル差ε_ijはε_ij = |θ_i - θ_j|と定義されます。j番目のエントリに対する分散はε_jと定義され、加重和として計算されます：

ε_j = Σ(i=0 to n-1) ε_ij w^(i+1)

ここで、wは分散予算における同期距離の影響を制御するために選択される重み係数です。NTPアルゴリズムでは、wは1/2未満に選択されます：フィルター分散の場合はw = NTP.FILTER、選択分散の場合はw = NTP.SELECTです。NTPアルゴリズムで使用される（絶対）分散ε_σおよびε_ξは、0番目のエントリε_0に対して定義されます。

以下では2つの手順が説明されています。クロックフィルター手順（clock-filter procedure）は、特定のクロックから最良のオフセットサンプルを選択するために使用され、クロック選択手順（clock-selection procedure）は、階層的なクロックセットの中から最良のクロックを選択するために使用されます。

4.1. クロックフィルター手順

クロックフィルター手順は、NTPメッセージの到着または新しいデータサンプルをもたらす他のイベント時に実行されます。これは（θ, δ, ε）の形式の引数を取ります。ここで、θはサンプルクロックオフセット測定値であり、δとεは関連する往復遅延と分散です。これは、フィルター処理されたクロックオフセット（peer.offset）、往復遅延（peer.delay）、および分散（peer.dispersion）を決定します。また、すでに記録されているサンプルの分散を更新し、現在の時刻（peer.update）を保存します。

クロックフィルター手順の基礎は、フィルターシフトレジスタ（peer.filter）で、NTP.SHIFT段で構成され、各段には単一の観測に関連する測定遅延、測定オフセット、および計算された分散からなる3タプル[θ_i, δ_i, ε_i]が格納されます。インデックスは左からゼロで番号付けされます。フィルターは、クリア手順によってすべての段で値[0, 0, NTP.MAXDISPERSE]で初期化されます。新しいデータサンプルは左端からフィルターにシフトされ、最初にNULL、次に古いサンプルが右端から落ちます。パケット手順は、新しい更新が到着すると（θ, δ, ε）の形式のサンプルを提供し、送信手順は2つのポーリング間隔が経過しても新しい更新がない場合に[0, 0, NTP.MAXDISPERSE]の形式のサンプルを提供します。引数、クロックフィルターの内容、およびピア変数に同じ記号（θ, δ, ε）が使用されていますが、意味は文脈から明らかになります。以下の疑似コードがこの手順を説明しています。

peer.offsetおよびpeer.delay変数は、ピアクロックに対するローカルクロックのクロックオフセットと往復遅延を表します。これらは両方とも精密量であり、通常、バイアス蓄積なしに精度と安定性を向上させるために長い間隔で平均化できます（付録Hを参照）。peer.dispersion変数は、測定エラー、スキューエラー蓄積、およびサンプル分散による最大エラーを表します。3つの変数すべてが、同期に使用されるピアクロックを選択し、表示の精度と安定性を最大化するために、クロック選択およびクロック結合手順で使用されます。

4.2. クロック選択手順

クロック選択手順は、ピア変数THETA、DELTA、EPSILON、およびτを使用し、これらの変数が変更されたとき、または到達可能性ステータスが変更されたときに呼び出されます。これは、交差アルゴリズム（intersection algorithm）とクラスタリングアルゴリズム（clustering algorithm）の2つのアルゴリズムで構成されます。交差アルゴリズムは、同期ソースになる資格のある候補ピアのリストを構築し、それぞれの信頼区間を計算し、MarzulloとOwicki [MAR85]から適応された技術を使用して誤計時器を排除します。クラスタリングアルゴリズムは、ストラタムと同期距離の順序で生き残った候補のリストをソートし、最も正確で、精密で、安定した生存者のみが残るまで、選択分散に基づいて繰り返し外れ値を排除します。各生存者に対して選択プロセスの結果を示すビットが設定されます。システム変数sys.peerは、最も可能性の高い生存者がいる場合はそれを指すポインタとして設定され、そうでない場合はNULL値に設定されます。

4.2.1. 交差アルゴリズム

交差アルゴリズムは、ループの回避と例外的にノイズの多いデータの使用を回避するために設計されたいくつかの健全性チェックに合格した場合にのみ、各ピアを順番に検証してエンドポイントリストに追加します。健全性チェックに合格したピアがない場合、手順は同期ソースを見つけずに終了します。m個の生存者のそれぞれについて、形式[エンドポイント、タイプ]の3つのエントリがエンドポイントリストに追加されます：[THETA - LAMBDA, -1]、[THETA, 0]、および[THETA + LAMBDA, 1]。リストには3m個のエントリがあり、エンドポイントの増加順にソートされます。

4.2.2. クラスタリングアルゴリズム

元のDTSアルゴリズムでは、クロック選択手順は、計算された交差[low, high]の中間に推定される正しい時刻を設定してこの時点で終了します。ただし、個々のピア統計が失われるため、これは精度と安定性のかなりの損失につながる可能性があります。したがって、NTPでは、前のステップを生き延びた候補がさらに処理されます。候補リストは[距離、インデックス]の形式のエントリで再構築されます。ここで、距離は（スケールされた）ピアストラタムと同期距離LAMBDAから計算されます。スケーリング係数は、ストラタムと距離の組み合わせを重み付けするメカニズムを提供します。通常、生存者の1つ以上が例外的に高い距離を持っていない限り、ストラタムが支配的になります。次に、リストは距離の増加順にソートされます。

このアルゴリズムは、最も低いストラタムと距離にあり、おそらく最も正確で安定した時間を提供できる候補リストの先頭近くのピアを優先するように設計されています。重み係数v（NTP.SELECTとも呼ばれる）を適切に選択すると、少数の外れ値が残りのエントリに対して大幅に異なる場合を除き、エントリはリストの末尾からトリミングされます。この場合、最初に外れ値が破棄されます。終了条件は、統計的に正当化されない場合に同期ソース間の不必要な切り替えを回避するように設計されていますが、低ストラタム、低距離のピアへのバイアスを維持します。