(57)【要約】  本方法は、ネットワークコンポーネント（NC-A）のクロックを、ネットワーク内で該NC-Aに通信可能に接続されている別のネットワークコンポーネント（NC-B）のクロックと同期させる方法に関連する。本方法は、NC-Aから別のNC-Bへのメッセージ伝送に対する一群の順方向伝送遅延値と、別のNC-BからNC-Aへのメッセージ伝送に対する一群の逆方向伝送遅延値とを判定すること、一群の順方向伝送遅延値の中から最小の順方向伝送遅延値（minF）を選択すること、一群の逆方向伝送遅延値の中から最小の逆方向伝送遅延値（minB）を選択すること、選択した最小の順方向伝送遅延値（minF）及び最小の逆方向伝送遅延値（minB）から、NC-Aのクロック及び別のNC-Bのクロック間のオフセットの推定値を導出すること、及びオフセットの推定値にしたがってNC-Aのクロックを調整することを含む。
2010527193.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークコンポーネントのクロックを、ネットワーク内で該ネットワークコンポーネントに通信可能に接続されている別のネットワークコンポーネントのクロックと同期させる方法であって、
前記ネットワークコンポーネントから前記別のネットワークコンポーネントへのメッセージ伝送に対する一群の順方向伝送遅延値と、前記別のネットワークコンポーネントから前記ネットワークコンポーネントへのメッセージ伝送に対する一群の逆方向伝送遅延値とを判定するステップと、
前記一群の順方向伝送遅延値の中から最小の順方向伝送遅延値を選択するステップと、
前記一群の逆方向伝送遅延値の中から最小の逆方向伝送遅延値を選択するステップと、
選択した最小の順方向伝送遅延値及び最小の逆方向伝送遅延値から、前記ネットワークコンポーネントのクロック及び前記別のネットワークコンポーネントのクロック間のオフセットの推定値を導出するステップと、
前記オフセットの前記推定値にしたがって前記ネットワークコンポーネントの前記クロックを調整するステップと
を有する方法。
【請求項２】
前記一群の順方向伝送遅延値及び前記一群の逆方向伝送遅延値を判定する前記ステップが、
一連の安定的なラウンドトリップ時間値が見出されるまで、前記ネットワークコンポーネント及び前記別のネットワークコンポーネント間の通信に対する一連のラウンドトリップ時間値を判定するステップであって、前記ラウンドトリップ時間値は、対応する順方向伝送遅延値及び対応する逆方向伝送遅延値の実質的な合計であり、前記一連の安定的なラウンドトリップ時間値は所定数個の連続的に判定されたラウンドトリップ時間値を含み、前記一連の安定的なラウンドトリップ時間値に属するラウンドトリップ時間値は、最小のラウンドトリップ時間値から所定の最大偏移量未満しか逸脱していない、ステップと、
前記一連の安定的なラウンドトリップ時間値内のラウンドトリップ時間値に対応する順方向伝送遅延値を、前記一群の順方向伝送遅延値に記録するステップと、
前記一連の安定的なラウンドトリップ時間値内のラウンドトリップ時間値に対応する逆方向伝送遅延値を、前記一群の逆方向伝送遅延値に記録するステップと
をさらに有する、請求項１記載の方法。
【請求項３】
順方向伝送遅延値及び対応する逆方向伝送遅延値を判定するステップが、
あるリクエスト時間にリクエストを前記ネットワークコンポーネントから前記別のネットワークコンポーネントへ送信するステップと、
ある応答時間に該リクエストに対する応答を前記別のネットワークコンポーネントから前記ネットワークコンポーネントへ送信するステップと、
ある応答受信時間に前記応答を前記ネットワークコンポーネントが受信するステップと、
前記応答時間から前記リクエスト時間を減算することで、前記順方向伝送遅延値を算出するステップと、
前記応答受信時間から前記応答時間を減算することで、前記逆方向伝送遅延値を算出するステップと
を有する請求項１又は２に記載の方法。
【請求項４】
前記別のネットワークコンポーネントから前記ネットワークコンポーネントへ送信される応答の各々に、前記応答時間を示すタイムスタンプを含めるステップをさらに有する、請求項３記載の方法。
【請求項５】
複数のリクエストを等しい時間間隔で送信するステップをさらに有する、請求項３又は４に記載の方法。
【請求項６】
前記リクエスト及び前記応答が、データパケットとして送信される、請求項３ないし５の何れか１項に記載の方法。
【請求項７】
前記一群の順方向伝送遅延値及び前記一群の逆方向伝送遅延値が、継続的に更新される、請求項１ないし６の何れか１項に記載の方法。
【請求項８】
ネットワーク内に設けられるネットワークコンポーネントであって、
クロックと、
ネットワーク内で少なくとも１つの別のネットワークコンポーネントに至る接続をもたらす通信手段と、
前記通信手段に接続され、リクエストを生成し、該リクエストを前記別のネットワークコンポーネントへ送信する要求手段と、
前記通信手段に接続され、前記別のネットワークコンポーネントから前記リクエストに対する応答を受信する受信手段と、
前記受信手段及び前記クロックに接続され、受信した前記応答を分析し、一群の伝送遅延を判定し、クロックオフセットの推定値を計算する分析手段と、
前記分析手段に接続され、前記一群の伝送遅延を保存するメモリと、
前記分析手段に接続され、計算したクロックオフセットの推定値にしたがって、前記クロックを調整するクロック調整手段と
を有するネットワークコンポーネント。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークコンポーネントのクロックを別のネットワークコンポーネントのクロックに同期させる方法及びネットワークコンポーネントに関連する。
【背景技術】
【０００２】
普及している多くのコンピュータアプリケーションにおいて、特にパケット交換網におけるリアルタイムアプリケーションにおいて、基準時間（例えば、情報が生成された時間）に情報を正確に合わせることは非常に重要である。例えば、パケットベースのネットワークの場合、送信するネットワークコンポーネントによりデータがリアルタイムで生成され、さらなる処理に備えて受信側のネットワークコンポーネントに送信される。この場合、データは複数のパケットに集められ、その各々はデータの一部分を含み、データは受信側のネットワークコンポーネントに送られ、それらのデータ部分はまとめられ組み立てられる。
【０００３】
伝送経路及び保留待ち行列等における変動に起因して、様々なパケットが受ける（経験する）伝送遅延は、非決定的に（non-deterministic  way）著しく異なり得る。極端な場合、先に送ったパケットが、後に送ったパケットより遅く到着するかもしれない。受信側のネットワークコンポーネントがパケットを適切に処理できるようにするため、パケット各々にタイムスタンプが付けられてもよく、そのタイムスタンプは、搬送するデータ部分に対する基準時間に対応する。この場合、受信側のネットワークコンポーネントは、データ部分を対応する基準時間に正確に合わせることができるであろう。
【０００４】
この例の場合、送信側のネットワークコンポーネントと受信側のネットワークコンポーネントのクロックが同期していなければならない。何らかの高性能コンピュータアプリケーションの配備可能にするには、一般に、高精度の時間測定が重要な前提条件になる。アプリケーションに依存して、正確な絶対的な時間基準（例えば、協定世界時間又はＵＴＣ時間）又は正確な相対的な時間基準が維持される必要がある。
【０００５】
伝送プロトコルの輻輳制御だけでなくフロー制御は、データパケットのラウンドトリップ時間（RTT：Round  Trip  Time）及び/又は伝送時間（一方向遅延、OWD:one-way  delay）の測定値をかなり当てにしており、そのデータパケットは、送信側のネットワークコンポーネント（すなわち、送信者、送信部）及び受信側のネットワークコンポーネント（すなわち、受信者、受信部）の間でやり取りされるものである。例えばタイムスタンプ形式で基準時間情報を提供すると、それには或る制約又は時間変動があるので、送信側及び受信側間の情報伝送遅延の推定は、主に、パケット交換網における時間同期の帰着する。この問題に対処するため、いわゆるネットワーク時間プロトコル（NTP:  Network  Time  Protocol）（非特許文献１）は、パケット交換網内のネットワークコンポーネントのローカルクロックが同期するように設計されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】D.L.Mill,  “The  Network  Time  Protocol  (Version  3)  Specification,  Implementation  and  Analysis”,  RFC  1305,  IEET,  March  1992
【発明の概要】
【発明が解決しようとする課題】
【０００７】
NTPの中心的な要素は、いわゆるクリスチャンアルゴリズム（CA:  Cristian  Algorithm）に基づくクロックオフセット計算ルーチンであり、以下において概説する。要求するネットワークコンポーネントは、タイムリクエストを含むデータパケットを、応答するネットワークコンポーネントへ送信時間TSにおいて送信する。応答するネットワークコンポーネントは、できるだけ速やかに回答し、リプライパケットに包含される受信タイムスタンプTRを返送し、リプライパケットは応答受信時間TRRにおいて受信される。これらの時間の値から、順方向における順方向伝送遅延すなわち一方向遅延（OWDf）及び逆方向における逆方向伝送遅延すなわち一方向遅延（OWDb）が、OWDf＝TR−TS及びOWDb＝TRR−TR  のように算出される。さらに、実質的に一方向遅延は双方向で等しいことが仮定され、OWDf及びOWDb間の相違は、単に、要求するネットワークコンポーネントのクロックと応答するネットワークコンポーネントのクロックとの間のオフセットに寄与する。この同期オフセットは、（OWDf−OWDb）/2として算出される。
【０００８】
クリスチャンアルゴリズムは致命的な欠点を持っている。それは、同期オフセットの推定が正しいのは、実際の順方向伝送遅延が実際の逆方向遅延に等しい場合だけである、ということである。すなわち、２つのネットワークコンポーネント間の通信が対称的な場合しか正確でない。非対称な遅延があった場合、演算は不正確になってしまう。実際のネットワークの場合、一方向遅延は、非対称なネットワークトポロジに起因して通常は非対称であり、例えば、非対称ディジタル加入者回線（ADSL）、非対称な経路、及び/又はネットワークコンポーネント内の統計的なパケット遅延等に起因する。リアルタイムアプリケーションの場合、非対称ネットワークトポロジに起因するシステム的な誤差は、可変の待ち行列遅延に起因する誤差のような、可変の一方向遅延による統計的なパケット遅延による誤差の場合よりもかなり深刻になる。
【０００９】
したがって本発明の課題は、異なるネットワークコンポーネントのクロック同士の間でさらに正確な同期を達成できるような方法及びネットワークコンポーネントを提供することである。
【課題を解決するための手段】
【００１０】
上記の課題は、ネットワークコンポーネントのクロックを別のネットワークコンポーネントのクロックに同期させる独立請求項１による方法、及び独立請求項８によるネットワークコンポーネントにより達成される。
【００１１】
本発明の一形態によれば、ネットワークコンポーネントのクロックを、ネットワーク内で該ネットワークコンポーネントに通信可能に接続されている別のネットワークコンポーネントのクロックと同期させる方法が使用される。本方法は、前記ネットワークコンポーネントから前記別のネットワークコンポーネントへのメッセージ伝送に対する一群の順方向伝送遅延値と、前記別のネットワークコンポーネントから前記ネットワークコンポーネントへのメッセージ伝送に対する一群の逆方向伝送遅延値とを判定するステップと、前記一群の順方向伝送遅延値の中から最小の順方向伝送遅延値を選択するステップと、前記一群の逆方向伝送遅延値の中から最小の逆方向伝送遅延値を選択するステップと、選択した最小の順方向伝送遅延値及び最小の逆方向伝送遅延値から、前記ネットワークコンポーネントのクロック及び前記別のネットワークコンポーネントのクロック間のオフセットの推定値を導出するステップと、前記オフセットの前記推定値にしたがって前記ネットワークコンポーネントの前記クロックを調整するステップとを有する方法である。
【００１２】
本発明の別の形態によればネットワークコンポーネントが使用され、該ネットワークコンポーネントは、クロックと、ネットワーク内で少なくとも１つの別のネットワークコンポーネントに至る接続をもたらす通信手段と、前記通信手段に接続され、リクエストを生成し、該リクエストを前記別のネットワークコンポーネントへ送信する要求手段と、前記通信手段に接続され、前記別のネットワークコンポーネントから前記リクエストに対する応答を受信する受信手段と、前記受信手段及び前記クロックに接続され、受信した前記応答を分析し、一群の伝送遅延を判定し、クロックオフセットの推定値を計算する分析手段と、前記分析手段に接続され、前記一群の伝送遅延を保存するメモリと、前記分析手段に接続され、計算したクロックオフセットの推定値にしたがって、前記クロックを調整するクロック調整手段とを有するネットワークコンポーネントである。
【００１３】
従来技術を上回る本発明の利点の１つは、伝送時間値の集合を得るために、伝送時間について複数回の測定が行われることであり、その集合の中から最小値が選択される。したがって、個々の測定値変動に起因するオフセット推定の誤差は、最小化される。そのような変動は、ネットワーク中のメッセージの伝送経路変更により生じるかもしれないし、或いは、例えばネットワークコンポーネントの入力及び出力待ち行列における、メッセージの様々な滞留時間に起因するかもしれない。さらに重要な特徴は、順方向及び逆方向における最小伝送遅延各々が、各自の集合から独立に選択されることである。これが意味することは、最小の順方向伝送遅延が、最小の逆方向伝送遅延に対応する順方向伝送遅延とは限らない、ということである。その理由は、一般に、最小の順方向伝送遅延を経験するメッセージが、最小の逆方向伝送遅延を経験するとは限らない、ということに起因している。したがって、オフセットの推定値が、より厳しい誤差限界とともに計算可能であるという利点を、本発明は有する。
【００１４】
逆方向伝送遅延及び対応する順方向伝送遅延に関する議論がなされるので、順方向伝送遅延及び逆方向伝送遅延は、リクエストメッセージ及びリプライメッセージを含む同じ通信サイクルに属することを意味する。例えば、あるネットワークコンポーネントに送信されたメッセージが、ある順方向伝送遅延を経験する場合、そのメッセージ対するリプライメッセージが経験する伝送遅延は、対応する逆方向伝送遅延になる。さらに、メッセージを処理してリプライを生成する際のネットワークコンポーネントにおける処理時間は無視できるものとすると、順方向伝送遅延及び対応する逆方向伝送遅延を一緒に加算することで、ラウンドトリップ時間が得られる。
【００１５】
本発明の有利な形態では、前記一群の順方向伝送遅延値及び前記一群の逆方向伝送遅延値を判定する前記ステップが、一連の安定的なラウンドトリップ時間値が見出されるまで、前記ネットワークコンポーネント及び前記別のネットワークコンポーネント間の通信に対する一連のラウンドトリップ時間値を判定するステップであって、前記ラウンドトリップ時間値は、対応する順方向伝送遅延値及び対応する逆方向伝送遅延値の実質的な合計であり、前記一連の安定的なラウンドトリップ時間値は所定数個の連続的に判定されたラウンドトリップ時間値を含み、前記一連の安定的なラウンドトリップ時間値に属するラウンドトリップ時間値は、最小のラウンドトリップ時間値から所定の最大偏移量未満しか逸脱していない、ステップと、前記一連の安定的なラウンドトリップ時間値内のラウンドトリップ時間値に対応する順方向伝送遅延値を、前記一群の順方向伝送遅延値に記録するステップと、前記一連の安定的なラウンドトリップ時間値内のラウンドトリップ時間値に対応する逆方向伝送遅延値を、前記一群の逆方向伝送遅延値に記録するステップとをさらに有する。
【００１６】
こうして、最小ラウンドトリップ時間、及び最小ラウンドトリップ時間近辺の安定領域（stable  region）が特定される。安定領域を得ると、対応する順方向及び逆方向伝送遅延を使用して、高精度にオフセット推定値を計算することを保証できる。所定の最大偏移を充分小さく選択することで、安定領域内のラウンドトリップ時間、並びに対応する順方向及び逆方向伝送遅延が、２つの通信コンポーネント間の通信における可能性のある急激な変化によって影響を受けないことを確実にする。例えば、パケットベースの通信の場合、所定の最大偏移は、数ミリ秒のオーダーに選択されてもよく、この値はパケット待ち行列が一杯である又は空であることに起因する伝送遅延変動（10−30msのオーダーになり得る）よりも充分に小さく、通信経路変更に起因する伝送遅延変動（何十ミリ秒のオーダーにもなり得る。）よりも依然として小さい。
【００１７】
本発明のさらなる形態では、順方向伝送遅延値及び対応する逆方向伝送遅延値を判定するステップが、あるリクエスト時間にリクエストを前記ネットワークコンポーネントから前記別のネットワークコンポーネントへ送信するステップと、ある応答時間に該リクエストに対する応答を前記別のネットワークコンポーネントから前記ネットワークコンポーネントへ送信するステップと、ある応答受信時間に前記応答を前記ネットワークコンポーネントが受信するステップと、前記応答時間から前記リクエスト時間を減算することで、前記順方向伝送遅延値を算出するステップと、前記応答受信時間から前記応答時間を減算することで、前記逆方向伝送遅延値を算出するステップとを有する方法である。このように、順方向及び逆方向伝送遅延を決定する簡易な方法が提供される。
【００１８】
本発明の好ましいさらなる形態は、前記別のネットワークコンポーネントから前記ネットワークコンポーネントへ送信される応答の各々に、前記応答時間を示すタイムスタンプを含めるステップをさらに有する。タイムスタンプは、さらなる計算に備えて、応答時間をネットワークコンポーネントに提供する簡易かつ効果的なツールである。タイムスタンプは、応答（リプライ）における主要な情報である。或いは、応答は他の情報を含んでもよいし、応答時間とともにネットワークコンポーネントが必要とするデータを含んでもよい。
【００１９】
本発明の好ましい形態は、複数のリクエストを等しい時間間隔で送信するステップをさらに有する。本発明の有利な形態では、前記リクエスト及び前記応答が、データパケットとして送信される。
【００２０】
本発明のさらなる形態では、前記一群の順方向伝送遅延値及び前記一群の逆方向伝送遅延値が、継続的に更新される。群（集合）を更新することは、集合全体を破棄し、新たな集合を新たなエントリとともに決定し直すことを含んでもよい。或いは、更新手順は、新たな測定が実行されている間、新たに判定された値を継続的な時間間隔で集合に加えてゆくことを含んでもよい。
【図面の簡単な説明】
【００２１】
【図１】ネットワークノードA及びB間で伝送されるパケットが経験する時間遅延を示すタイミング図。
【図２】ネットワークノードA及びB間で伝送されるパケットが経験する時間遅延を示す別のタイミング図。
【図３】ネットワークノードA及びB間で伝送される一連のパケット系列のタイミング図。
【図４】図３と同じ図に更なる事項を記述した図。
【図５】異なる方法によるラウンドトリップ時間の測定値をプロットした図。
【図６】図５に示す測定値に基づいて計算された同期オフセット推定値をプロットした図。
【図７】ラウンドトリップ時間の安定領域の測定値に基づいて計算された同期オフセット推定値をプロットした図。
【図８】３つの異なる方法を使って計算された同期オフセット推定値の誤り限界をプロットした比較図。
【図９】３つの異なる方法を使って計算された同期オフセット推定値の誤り限界をプロットした比較図。
【図１０】統計的な誤り限界をプロットした図。
【発明を実施するための形態】
【００２２】
以下、図面を参照しながら有利な実施例を用いて本発明を説明する。
【実施例１】
【００２３】
以下において、まず、ネットワークコンポーネントであるネットワークノードA（単に、ノードAと言及する）のクロックと、別のネットワークコンポーネントであるネットワークノードB（単にノードBと言及する）のクロックとの間のオフセットを推定する既存の方法を説明する。この方法は概してクリスチャンアルゴリズムとして知られている。ノードA及びノードBは、ネットワークコネクションを介して接続され、例えばインターネット環境のようなデータパケットにより通信を行う。
【００２４】
図１は、ノードA及びB間で伝送されるデータパケットのタイミング図を示す。時間変数tAの時間軸はノードAのクロックに属し、時間変数tBの時間軸はノードBのクロックに属する。一方の時間軸から他方を指す矢印は、一方のノードから他方へのパケット伝送を示す。図１に示されているように、ノードAは、タイムリクエストを含むデータパケットをノードBに時間TS（A）において送信している。ノードBはそのデータパケットを時間TR（B）において受信している。リクエストパケットの処理の後、ノードBはできるだけ速やかに応答し、応答時間TR1（B）において、あるデータパケットを（リクエストの）送信元のノードAに返し、そのデータパケットは、受信時間TR1（B）をマーキングする受信タイムスタンプを含む。タイムスタンプを伴うデータパケットは、時間TRR（A）においてノードAにより受信される。TR1（B）及びTR2（B）間の時間差は、ノードBにおける処理時間であり、通常、TRR（A）及びTS（A）間の時間差よりも充分に短く、無視してよい。したがって、TR1（B）＝TR2（B）＝TR（B）のように仮定できる。この関係は図２に示されている。
【００２５】
ノードA及びBのクロック各々により基準となる時間が測定されることに留意を要する。すなわち、時間TRR及びTSはノードAのクロックにより測定され、時間TR（B）はノードBのクロックにより測定される。一般に、クロック各自のオフセット及びスキュー（ずれ）に起因して、ノードA及びBは、同じ基準時点について異なる時間を測定してしまう。この様子は、図１及び図２において異なる時間変数tA及びtBを使用することで明確にされている。したがって、ある特定の時点において、ノードBのクロックがノードAのクロックとオフセットKだけずれていた場合、そのずれはTR（B）の測定に影響を及ぼす。そして、TS（A）、TR（B）及びTRR（A）を用いて伝送遅延や一方向遅延（OWD）が算出される場合、その値は実際の値又は新のOWDからKの値だけ異なるものになってしまう。クリスチャンアルゴリズムを使用する場合、実際に測定されるOWDとは異なり、順方向の真のOWDは逆方向の真のOWDと等しいことが、仮定されていなければならない。
【００２６】
以下において、ノードA及びノードB間の時間オフセット計算値は、Δとして示される。すなわち、ΔはKに関する推定値であることを意味する。さらに、順方向及び逆方向の一方向遅延測定値はそれぞれOWDf及びOWDbとして示される。これらは以下の数式（1）及び（2）にしたがって算出可能である。
【００２７】
OWDf＝TR（B）−TR（A）          （1）
OWDb＝TRR（A）−TR（B）          （2）
クリスチャンアルゴリズムによると、Δは以下の数式（3）により算出可能である。
【００２８】
ΔCA＝（OWDf−OWDb）/2        （3）
ΔCAがKに等しいのは、順方向及び逆方向の一方向遅延の対称性の仮定が満たされる場合のみであることに、留意を要する。しかしながら、非対称な遅延が存在する場合、順方向及び逆方向の実際のOWDは等しくはなく、その推定は誤りの多い結果を招いてしまう。上述したように、実際のネットワークOWDは、通常、非対称である。リアルタイムアプリケーションの場合、非対象ネットワークトポロジにより引き起こされるシステムエラー（systematic  error）は、可変OWD（variable  OWD）により引き起こされるエラーの場合ほどは重大ではない。実際のネットワークの場合、対称的な一方向遅延の保証は一切無いので、３つのイベントの時間的因果関係のみ、すなわちノードAによるパケットの送信、ノードBによるパケットの受信及びノードBによる応答パケットの送信のみ、を議論することができ、これは、TS（A）＜TR（B）＜TRR（A）  という不等式をもたらす。仮に、TR（B）が、TRR（A）及びTS（A）の時点の中間にあった場合、クリスチャンアルゴリズムにより推定された同期オフセットの最大計算エラー又はエラー限界δは、以下の数式（4）を満たす。
【００２９】
δ＝（TRR（A）−TS（A））/2  ＝RTT/2          （4）
以下で説明される方法による測定を実行できるようにするため、数個の前提条件を満足することが有利である。第１に、ネットワークトポロジは、測定期間の間に変わるべきでない。第２に、ノードA及びノードBのクロックのクロック周波数差に起因する時間ドリフトは、非常に小さく、測定期間の間に、クロック同士の時間差は変わらない。測定期間が数秒程度の大きさであった場合、これらの前提条件は常に満たされているものとする。
【００３０】
時間同期に関し、図２による測定が反復的に実行される。図３は、そのような測定を実行するために、ノードA及びノードB間で伝送されるリクエスト及びリプライパケットの系列を示すタイミングチャートを表す。図示の簡明化のため、４つの通信サイクルが描かれており、その各々は、ノードAからノードBへ送信されるリクエストパケット（要求パケット）と、ノードBからノードAへ送信されるリプライパケット（応答パケット）とを含む。ノードAから送信され、図３に示されているリクエストパケットは、TS（A）1、TS（A）i、TS（A）k、TS（A）lの時間に送出されている。各通信サイクルに対する一方向遅延は、上記の数式（1）及び（2）により算出できるが、ラウンドトリップ時間（RTT）は、各々のOWDの合計として、或いは簡易に  RTT＝TRR（A）i−TS（A）i  のように算出可能である。すなわち、測定される通信サイクル数は、非常に大きくなる可能性があり、例えば数百回になるかもしれない。
【００３１】
最小のラウンドトリップ時間測定値minRTT近辺の一群のRTT（RTT集合）が確認されるまで、リクエストパケット及びリプライパケットがノードA及びノードB間でやりとりされる。RTTのこの一群は、minRTT近辺の安定領域（stable  region）と言及される。このため、まず、所与のネットワークトポロジに相応しい最小領域幅wminに加えて最大偏移dmaxも選択される必要がある。minRTT近傍の安定領域は、少なくともwminの一連のサンプル（minRTTに等しいRTTのサンプルを含む）が、dmax以下の量しかminRTTから逸脱していないRTT値を有することを意味する。
【００３２】
安定領域は以下の手順により発見可能である。まず、初期設定手順の際、minRTTが無限大に設定される。次に、RTTサイクル又はリクエスト及びリプライパケットのペアの各々について、RTTが計算され、保存されているminRTT値と比較される。測定されたRTTが保存されているminRTTより小さかった場合、minRTTは測定されたRTTに設定される。さらに、現在のminRTT値からdmax未満の量しか離れていないRTT測定値の数が、記録される。minRTT値からdmax未満の量しか離れていない少なくともwminの一連のRTTが記録されると、これらのRTT値は、一群の安定的なRTT値又は安定RTT値集合（a  set  of  stable  RTT  value）として記録される。対応する一方向遅延も記録され、ノードA及びノードBのクロック同士の間の同期オフセットの推定値を求める更なる計算に使用される。
【００３３】
次の段階では、最小前方（順方向）一方向遅延（minF）及び最小後方（逆方向）一方向遅延（minB）が、以下の数式（5）及び（6）にしたがって計算される。最小前方一方向遅延は、一群の順方向の一方向遅延の中で記録された最小値であり、最小後方一方向遅延は、一群の逆方向の一方向遅延の中で記録された最小値である。ノードA及びノードB間でやりとりされるデータパケット数が増えると、データパケットが待ち行列を通過する確率が増加する。待ち行列が完全に空の場合、それらのノードにおける最小処理時間をもたらす。したがって、順方向又は逆方向の最小の一方向遅延は、それら一方向遅延における物理的制約を表現する傾向がある。物理的制約を表現するならば、待ち行列のような要因は、一方向遅延には影響しないことになる。
【００３４】
minF＝min（TR（B）j−TS（A）j），1≦j≦wmin        （5）
minB＝min（TRR（A）n−TR（B）n），1≦j≦wmin        （6）
次に、いわゆる仮想最小RTT（VirtMinRTT）が以下の数式により計算される。
【００３５】
VirtMinRTT＝minF＋minB          （7）
したがって、minF及びminBは、データパケットが経験する物理的観点から最短の一方向遅延を表す場合、ノードAからノードBへ送られ及びノードBからノードAへ返送されるパケットについて、VirtMinRTTは、物理的制約における最小ラウンドトリップ時間を規定する。
【００３６】
図５は、ノードAからノードBへ及び逆向きに送信される一連のデータパケットについて、minRTT及びVirtMinRTTをプロットした様子を示す。この場合において、横軸は測定回数を示す。測定の各々は、安定領域を見出し、minRTT及びVirtMinRTTを計算する上記のプロセスを使用して実行される。概して、VirtMinRTTはminRTTに等しくない。これは次のことを意味する：ノードAからノードBへの順方向経路において、最小の待ち行列又は処理遅延を経験したパケットは、ノードBからノードAへの逆方向経路において最小遅延を経験したパケットと同じではない。図５から理解できるように、VirtMinRTTは一貫してminRTTより低い。
【００３７】
測定期間の間ネットワークトポロジは一定であることが前提条件として仮定されているので、minF及びminBは、物理的制約による最小の一方向遅延に等しい、又は少なくとも近似的に等しい。しかしながら、ノードBのクロックがノードAのクロックに同期していなかった場合、minF及びminBは、実際の真のものとは異なる一方向遅延測定値を表すことになる。ノードBのクロックが、ノードAのクロックに対して未知のクロック同期オフセットKを持っていた場合、真の一方向遅延minFr及びminBrは、以下の数式（8）及び（9）を用いて計算されてもよい。これは次のことを意味する：minFr及びminBrは、同期オフセットKの量だけ修正されたならば、順方向及び逆方向における真の最小一方向遅延になる。
【００３８】
minFr＝minF−K      （8）
minBr＝minB＋K      （9）
数式（8）及び（9）を数式（7）に代入すると、以下の数式（10）に帰着し、これはVirtMinRTTの値は同期オフセットと独立（無関係）であることを示す。
【００３９】
VirtMinRTT＝minF＋minB＝minFr＋minBr        （10）
VirtMinRTTに関連する順方向及び逆方向の一方向遅延minF及びminBを利用して、同期オフセットの推定値を数式（11）にしたがって算出できる。
【００４０】
Δ＝（minF−minB）/2      （11）
図6は、計算したΔの値（破線）をプロットしたものを示す。同期オフセットの推定値を求めるこの方法は、改善されたクリスチャンアルゴリズム（ICA）と言及されてもよい。ただし、上記のクリスチャンアルゴリズム（CA）と大幅に相違する。まず、ICAによる方法は一連の測定値に基づいているが、CAは単独の測定値に基づいている。さらに、ICAによる計算は、順方向及び逆方向の一方向遅延の最小値、すなわちminF及びminBを独立に決定することに基づいている。これに対して、CAで使用される順方向及び逆方向の一方向遅延、すなわちOWDf及びOWDbは、ノードAからノードBへパケットを送信し、ノードAに戻ってきた１つの同じ通信サイクルで決定された値である。その結果、ΔはΔCAよりも一定であり、したがって、図６に示されているように、同期オフセットKに関するさらに正確な推定値をもたらす。図６では比較のため、同じ測定集合について計算されたΔCAの値もプロットされている。
【００４１】
代替例として、ICAにおけるVirtMinRTTの一方向遅延を使用する代わりに、最小のラウンドトリップ時間RTTに対応する順方向及び逆方向の一方向遅延を使用して、同期オフセットの別の推定値ΔCAminが計算されてもよい。この方法は、CAmin法と言及されてもよい。一群の測定値に対する計算結果は図７にプロットされており、同じ測定値群についてICAにより計算されたΔも示されている。図７から理解できるように、Δ（実線）は、一貫してΔCAmin（破線）以下の下限（lower  bound）を有する（デルタの平均に、より近い）。
【００４２】
Δの計算は、測定の3角形（measurement  triangle）の中央に推定値を置くことに基づいている。これにより、計算誤差の決定論的限界δ1は、図４に示される遅延に関するイベントTS（A）、TR（B）及びTRR（A）の時間的因果関係に基づく。決定論的な限界δ1は、数式（12）を用いて算出可能である。
【００４３】
δ1＝VirtMinRTT/2      （12）
VirtMinRTT、minRTT及びRTTi（何らかの単独のラウンドトリップ時間の値を示す）の値に関し、以下の不等式（13）が成り立つ。
【００４４】
VirtMinRTT≦minRTT≦RTTi        （13）
この不等式は、誤差限界δ1が、従来のクリスチャンアルゴリズムにより推定される誤差限界と少なくとも同程度に良いことを意味する。さらに、VirtMinRTTがminRTTに等しくなかった場合、何らかの他の測定点を用いた場合よりも、より厳しい誤差限界が得られる。この結論は提案のアルゴリズムに決定論的に適用可能なので、δ1は決定論的誤差限界と言及されてもよい。
【００４５】
図８は、従来のクリスチャンアルゴリズムによるオフセット推定の誤差限界δCAをプロットした様子を示し、図９は、上記のCAmin法及びICA法による推定の誤差限界δCAmin（粗い破線）及びδICA（細かい破線）をそれぞれプロットした様子を示す。図８及び図９の比較から分かるように、クリスチャンアルゴリズムは最大の誤差限界数になるが、ICA法は最低の誤差限界数になり、したがって（本方法は）同期オフセットの最も正確な推定値をもたらす。
【００４６】
確率論的な観点からは、イベントの時間的な範囲をさらに狭くすることができる。minF及びminBが一方向遅延の物理的限界を表す仮定が成り立つならば、以下の数式（14）に示されるように、minRTT及びVirtMinRTT間の差分の半分に等しい誤差限界を定義することができる。この誤差限界は、統計的誤差限界と言及される。
【００４７】
δ2＝（minRTT−VirtMinRTT）/2      （14）
図１０は、計算された統計的誤差限界をプロットした様子を示す。統計的誤差限界は、以下の意義を有する。推定された同期オフセットΔが、実際の同期オフセットKから統計的誤差限界δ2の範囲内にある確率は、minF及びminBの値が実際に物理的限界の一方向遅延になっている確率に等しい又はそれより大きい。すなわち、minF及びminBがパケット伝送に関する最小の物理的に可能な一方向遅延でなかったとしても、δ2は、推定された同期オフセットΔの誤差限界に対する良好な指数になる。図９及び図１０の比較から分かるように、統計的誤差限界δ2に関し、推定された同期オフセットΔは、決定論的誤差限界δ1により示されるものよりも、かなり良いKの推定値になり得る。
【００４８】
上記の説明、特許請求の範囲及び図面に示される本発明の特徴は、本発明の様々な実施形態の中でそれぞれ独自に及び所望の如何なる組み合わせによっても使用可能であることは重要である。
【図１】
2010527193.tif 000003
【図２】
2010527193.tif 000004
【図３】
2010527193.tif 000005
【図４】
2010527193.tif 000006
【図５】
2010527193.tif 000007
【図６】
2010527193.tif 000008
【図７】
2010527193.tif 000009
【図８】
2010527193.tif 000010
【図９】
2010527193.tif 000011
【図１０】
2010527193.tif 000012
【国際調査報告】
2010527193.tif 000013
2010527193.tif 000014
2010527193.tif 000015