最小ペアプロトコル

最小ペア(MP) は、順方向と逆方向の片方向ネットワーク遅延(OWD)のうち小さい方をリアルタイムで推定するアクティブ測定プロトコルです。 ^{[ 1 ]} これは、3 つのネットワーク ノードのセットが、自身と 4 番目の信頼できないノードとの間の OWD の上限を推定できるような、敵対的な環境で動作するように設計されています。4 つのノードすべてが協力する必要がありますが、4 番目のノードからの正直な協力は必須ではありません。目的は、クロック同期に信頼できないノードを関与させることなく、往復時間(RTT)の半分よりも正確な方法で、このような推定を実行することです。MP プロトコルは、遅延に敏感なアプリケーション (コンテンツ配信ネットワークレプリカの配置など) や、安全なインターネットの位置情報取得に使用できます。

MPプロトコルでは、信頼できる3つのネットワークノードがクロックを同期し、公開鍵に安全にアクセスできることが求められます。これは、閉鎖型の公開鍵基盤（PKI）システムによって実現できます。信頼できないノードは、誠実に協力すると想定されていないため、これに従わなくても構いません。ノードAと信頼できないノードX 間の前方OWDと後方OWDの小さい方の上限を推定するために（表記については図を参照）、Xはまず3つのノードすべてに対してアプリケーション層接続を確立します。これは、 WebSocketなどを使用してブラウザ上で透過的に行うことができます。次に、3つのノードは順番にデジタル署名付きタイムスタンプを交換します。

ノードA が開始すると仮定すると、署名付きタイムスタンプをXに送信します。ノードX はそのメッセージを他の 2 つのノードに転送します。メッセージが受信されると、その受信時刻が記録されます。受信ノードは署名を検証し、メッセージが送信元から受信者まで、信頼できないノードを経由してネットワークを通過するのにかかった時間を計算します。これは、受信時刻からメッセージのタイムスタンプを差し引くことによって行われます。次に、ノードB がこのプロセスを繰り返し、続いてノードCが行います。3 つのノードすべてが順番に処理を終えると、リンクに対応する 6 つの遅延推定値が得られます。

• A → X → BおよびB → X → A
• A → X → CおよびC → X → A
• B → X → CおよびC → X → B

A、B、C、X間の3つのネットワークリンクにおける順方向および逆方向のOWDのうち小さい方を推定するために、上記の各ペアの最小値（つまり、大きい方は破棄）が取られます。3つのペアはそれぞれ、各リンクにおける小さい方のOWDの近似値を表し、3つの未知数を含む3つの方程式のシステムが生成されます。これらの方程式をa、b、cについて同時に解くことで（図を参照）、遅延推定値が得られます。

例えば、メッセージをすぐに転送する代わりに少しの間保持するなどして、人為的な遅延を注入することで、信頼できないノードは推定OWDを増やすことができます。そのため、MPプロトコルは、信頼できるノードと信頼できないノード間の3つのリンクすべてについて、OWDの上限をまとめて推定できます。例えば、推定遅延（順方向または逆方向）が30ms  、40ms  、 50msだった場合、実際の遅延は60ms  、70ms  、 80msにはなり得ません。なぜなら、それは信頼できないノードが3つすべてをまとめて短縮できたことを意味し、遅延は伝送媒体の物理的特性によって制限されるため、これは達成が困難だからです。ただし、信頼できないノードは、一部のリンクを選択的に遅延させることで、すべてのリンクではなく、一部のリンクを短縮できる場合があることに注意してください。

平均値（すなわち RTT/2）と比較すると、MP プロトコルは、順方向および逆方向 OWD の小さい方の推定値を、平均値方式で返される値よりも大きく返すことはありません。さらに、MP プロトコルの絶対誤差の確率分布は、基となる遅延分布の関数として導出されています^{[ 2 ]}。これは、信頼できないノードと信頼できるノード間のリンク上の遅延の性質を知ることで、期待される誤差を計算できるため有用です。

• ネットワーク遅延
• 信頼できるシステム