(57)【要約】【課題】オーバレイネットワークにおける目標ピアノードに対して、実際にメッセージを送受信して遅延時間を計測する必要性を判定する遅延超過推定方法等を提供する。【解決手段】自ピアノードから見て、目標ピアノードにおける遅延時間が、規定時間以上となるか否かを判定するために、最初に、目標ピアノードの識別値targetと、自ピアノードの識別値ownとの差である距離distanceを算出する。次に、推定中継端末数を表すホップ数eHopを初期値に設定し、乗数変数ｉを所定最大値ｉmaxに設定する。次に、距離distanceが２のｉ乗以上となる場合に、ホップ数eHopを１増分し、距離distanceから２のｉ乗を減算し、乗数変数ｉを１減分する操作を、距離distanceが閾値距離intervalよりも小さくなるまで繰り返す。最終的に得られたホップ数eHopが、閾値ホップ数よりも大きい目標ピアノードを、遅延超過リストへの登録候補として選択される。【選択図】図３
2011211292.tif 000002
【特許請求の範囲】
【請求項１】
複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおける遅延超過推定方法であって、
各ピアノードは、１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストとを有し、
自ピアノードから見て、目標ピアノードにおける遅延時間が、規定時間以上となるか否かを判定するために、
目標ピアノードの識別値targetと、自ピアノードの識別値ownとの差である距離distanceを算出する第１のステップと、
推定中継端末数を表すホップ数eHopを初期値に設定し、乗数変数ｉを所定最大値ｉmaxに設定する第２のステップと、
前記距離distanceが２のｉ乗以上となる場合に、前記ホップ数eHopを１増分し、前記距離distanceから２のｉ乗を減算し、前記乗数変数ｉを１減分する操作を、前記距離distanceが閾値距離intervalよりも小さくなるまで繰り返す第３のステップと、
最終的に得られた前記ホップ数eHopが、閾値ホップ数thresholdよりも大きい目標ピアノードを、前記遅延超過リストへの登録候補として選択される第４のステップと
を有することを特徴とする遅延超過推定方法。
【請求項２】
前記オーバレイネットワークのプロトコルは、分散ハッシュテーブル（ＤＨＴ:Distributed Hash Table）を用いた構造化オーバレイのＣｈｏｒｄであり、
前記ルーティングテーブルは、フィンガーテーブルである
ことを特徴とする請求項１に記載の遅延超過推定方法。
【請求項３】
前記自ピアノードは、前記目標ピアノードの識別値targetをランダムに複数選択し、
各目標ピアノードの識別値targetに対して、第１から第４のステップを実行することによって、前記自ピアノードから見た識別値全範囲における前記遅延超過リストを作成することを特徴とする請求項１又は２に記載の遅延超過推定方法。
【請求項４】
前記自ピアノードが、目標ピアノードの宛先識別値を含む遅延計測要求メッセージを送信する前に、第１から第４のステップを実行し、
前記遅延超過リストの登録候補として選択された目標ピアノードについて、該目標ピアノードの宛先識別値を含む遅延計測要求メッセージを送信する第５のステップを有することを特徴とする請求項１から３のいずれか１項に記載の遅延超過推定方法。
【請求項５】
各ピアノードは、前記ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測しており、
第５のステップは、
前記自ピアノードが、宛先識別値を含む遅延計測要求メッセージを、前記ルーティングテーブルに登録された次ピアノードへ送信するステップと、
中継ピアノードが、受信した前記遅延計測要求メッセージを、更に次ピアノードへ転送するステップと、
前記目標ピアノードが、前記遅延計測要求メッセージを受信した際に、応答メッセージを返信するステップと、
前記中継ピアノードが、前記応答メッセージを受信した際に、該応答メッセージを送信した次ピアノードとの間の前記遅延時間を追記し転送するステップと、
前記自ピアノードは、前記応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該自ピアノードから順に加算して、該遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、前記遅延超過リストに登録するステップと
を有することを特徴とする請求項４に記載の遅延超過推定方法。
【請求項６】
各ピアノードは、ルーティングテーブルに登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ(Round Trip Time)値を計測し、そのＲＴＴ値から遅延時間を算出することを特徴とする請求項５に記載の遅延超過推定方法。
【請求項７】
前記自ピアノードが、目標ピアノードへメッセージを送信する際に、前記目標ピアノードの識別値が、前記遅延超過リストに含まれている場合、前記オーバレイネットワーク以外の前記物理ネットワークを直接的に用いて、前記目標ピアノードへメッセージを送信することを特徴とする請求項１から６のいずれか１項に記載の遅延超過推定方法。
【請求項８】
複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおけるピアノードであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、
遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストと、
自ピアノードから見て、目標ピアノードにおける遅延時間が、規定時間以上となるか否かを判定する遅延超過候補判定手段と
を有し、
前記遅延超過候補判定手段は、
目標ピアノードの識別値targetと、自ピアノードの識別値ownとの差である距離distanceを算出し、
推定中継端末数を表すホップ数eHopを初期値に設定し、乗数変数ｉを所定最大値ｉmaxに設定し、
前記距離distanceが２のｉ乗以上となる場合に、前記ホップ数eHopを１増分し、前記距離distanceから２のｉ乗を減算し、前記乗数変数ｉを１減分する操作を、前記距離distanceが閾値距離intervalよりも小さくなるまで繰り返し、
最終的に得られた前記ホップ数eHopが、閾値ホップ数thresholdよりも大きい目標ピアノードを、前記遅延超過リストへの登録候補として選択する
ことを特徴とするピアノード。
【請求項９】
前記オーバレイネットワークのプロトコルは、分散ハッシュテーブル（ＤＨＴ:Distributed Hash Table）を用いた構造化オーバレイのＣｈｏｒｄであり、
前記ルーティングテーブルは、フィンガーテーブルである
ことを特徴とする請求項８に記載のピアノード。
【請求項１０】
前記目標ピアノードの識別値targetをランダムに複数選択し、各識別値targetに対して前記遅延超過候補判定手段を実行し、前記自ピアノードから見た識別値全範囲における遅延超過リストへの登録候補を選択することを特徴とする請求項８又は９に記載のピアノード。
【請求項１１】
目標ピアノードの宛先識別値を含む遅延計測要求メッセージを送信する前に、前記遅延超過候補判定手段を実行し、前記遅延超過リストの登録候補として選択された目標ピアノードについて、該目標ピアノードの宛先識別値を含む遅延計測要求を、前記ルーティングテーブルに登録された次ピアノードへ送信する遅延計測要求送信手段を更に有することを特徴とする請求項８から１０のいずれか１項に記載のピアノード。
【請求項１２】
前記ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する遅延時間計測手段と、
中継ピアノードとして、受信した前記遅延計測要求メッセージを、更に次ピアノードへ転送する中継要求転送手段と、
目標ピアノードとして、前記遅延計測要求メッセージを受信した際に、応答メッセージを返信する目標応答送信手段と、
中継ピアノードとして、前記応答メッセージを受信した際に、該応答メッセージを送信した次ピアノードとの間の前記遅延時間を追記し転送する中継応答転送手段と、
自ピアノードとして、前記応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該自ピアノードから順に加算して、該遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、前記遅延超過リストに登録する遅延超過リスト生成手段と
を有することを特徴とする請求項１１に記載のピアノード。
【請求項１３】
前記遅延時間計測手段は、前記ルーティングテーブルに登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ値を計測し、そのＲＴＴ値から遅延時間を算出することを特徴とする請求項１２に記載のピアノード。
【請求項１４】
前記自ピアノードが、目標ピアノードへメッセージを送信する際に、前記目標ピアノードの識別値が、前記遅延超過リストに含まれているか否かを判定し、真と判定された場合、前記オーバレイネットワーク以外の前記物理ネットワークを直接的に用いて、前記目標ピアノードへメッセージを送信する送信切替手段を更に有することを特徴とする請求項８から１３のいずれか１項に記載のピアノード。
【請求項１５】
複数のピアノードによって接続された物理ネットワーク上に仮想的に構成されたオーバレイネットワークにおけるピアノードに搭載されたコンピュータを機能させるプログラムであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、
遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストと、
自ピアノードから見て、目標ピアノードにおける遅延時間が、規定時間以上となるか否かを判定する遅延超過候補判定手段と
してコンピュータを機能させ、
前記遅延超過候補判定手段は、
目標ピアノードの識別値targetと、自ピアノードの識別値ownとの差である距離distanceを算出し、
推定中継端末数を表すホップ数eHopを初期値に設定し、乗数変数ｉを所定最大値ｉmaxに設定し、
前記距離distanceが２のｉ乗以上となる場合に、前記ホップ数eHopを１増分し、前記距離distanceから２のｉ乗を減算し、前記乗数変数ｉを１減分する操作を、前記距離distanceが閾値距離intervalよりも小さくなるまで繰り返し、
最終的に得られた前記ホップ数eHopが、閾値ホップ数thresholdよりも大きい目標ピアノードを、前記遅延超過リストへの登録候補として選択する
ようにコンピュータを機能させることを特徴とするピアノード用のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オーバレイネットワークについて、自ピアノードから目標ピアノードまでの遅延時間を検出する技術に関する。
【背景技術】
【０００２】
図１は、オーバレイネットワークのシステム構成図である。
【０００３】
図１のシステムによれば、複数のピアノード１、送信元端末２及び宛先端末３が物理ネットワーク４に接続されている。その物理ネットワーク４上には、複数のピアノード１によって仮想的にオーバレイネットワーク５が構成されている。オーバレイネットワークの代表的な例として、Ｐ２Ｐ(Peer to Peer)ネットワークがある。Ｐ２Ｐネットワークは、ＩＰ層を覆い隠して（オーバレイして）、端末間の相互接続を可能とする。図１によれば、送信元端末２及び宛先端末３が、ピアノード１に対するＳＩＰ−ＵＡ(SIP - User Agent)として機能し、オーバレイネットワークが、例えばＰ２ＰＳＩＰ(Peer to Peer - Session Initiation Protocol)によって構築されている。
【０００４】
近年、構造化オーバレイの代表例として、キーワードのハッシュ値に基づいて端末間のデータを分散管理する「分散ハッシュテーブル（ＤＨＴ:Distributed Hash Table）」の技術がある。Napster又はGunutellaに代表される従来のＰ２Ｐ技術と異なって、「分散ハッシュテーブル」は、ネットワーク全体に分散配置されたデータを高速に検索することができる。また、ピアノードの頻繁な参加・離脱に対しても、自律分散的にネットワークを再構築することができる。
【０００５】
分散ハッシュテーブルの代表例として、「Ｃｈｏｒｄ」がある（例えば非特許文献１参照）。Ｃｈｏｒｄは、時計回りに識別値（ｍビット）が増加するように構成されたリング状（環状）ハッシュ空間を用いる。識別値は、ＳＨＡ１ハッシュ関数の値である。分散ハッシュテーブルの特徴の１つに、拡張性（スケーラビティ）がある。アドレスを検索する際に中継するピアノード数は、最大値がｌｏｇ（Ｎ）であり、平均値が０．５×ｌｏｇ（Ｎ）となることが保証されている（Ｎはピアノードの総数）。従って、ピアノードが膨大な数であっても、効率的な検索が可能となる。
【０００６】
図２は、Ｃｈｏｒｄを用いた構造化オーバレイの説明図である。
【０００７】
図２によれば、オーバレイネットワークを構成する各ピアノードは、リング状ハッシュ空間内の１つの識別値にマッピングされる。ピアノードがマッピングされる識別値は、例えばピアノードのＩＰアドレス及びポート番号を入力とするハッシュ関数から得られた値を、ノード識別値として決定する。
【０００８】
例えば、送信元端末(alice@auone.jp)が、リング状ハッシュ空間におけるピアノードＩＤ８に接続されているとする。このとき、宛先端末(bob@auone.jp)の登録情報を検索するために、送信元端末は、宛先端末のアドレス(bob@auone.jp)をハッシュ関数に入力し、ＩＤ３９を得たとする。そして、送信元端末は、宛先端末の登録情報が登録されたＩＤ３９を検索する。
【０００９】
ここで、「サクセッサリスト(Successor List)」及び「フィンガーテーブル(Finger Table)」が用いられる。「サクセッサリスト」とは、ハッシュ空間上で隣接する複数のピアノードの情報を保持する。従って、当該ピアノードの識別値ｋを与えたとき、時計回りに辿って、最初に存在するピアノードを得られる。
【００１０】
「フィンガーテーブル」には、ルーティングテーブルとして、当該ピアノードの識別値（例えばＩＤ８）に、２のｋ乗（１，２，４，８，１６・・・）を加算した数ｘと、その数ｘを入力としたサクセッサ（ｘ）のピアノードの識別値とを記憶する。フィンガーテーブルを用いることによって、データを検索する際に、中継端末数を、端末総数のログオーダに抑えることができる。これは、端末総数が増加した場合であっても、効率的な検索を可能とすることを意味する。
【００１１】
図２は、６ビットのハッシュ識別値空間の例であり、フィンガーテーブルの行数は６個となる（例えば、１６０ビットのハッシュ識別値空間の場合、フィンガーテーブルの行数は１６０個）。ここでは、全識別値にピアノードが割り当てられている場合を想定し、hash(bob@auone.jp)＝ＩＤ３９をルックアップする場合について説明する。
【００１２】
（ホップ１）ＩＤ８のフィンガーテーブルによれば、ＩＤ３９に最も近い数は８＋２４（１６）の２４である。ＩＤ８は、ルックアップメッセージをＩＤ２４へ転送する。
（ホップ２）ＩＤ２４のフィンガーテーブルによれば、ＩＤ３９に最も近い数は２４＋２３（８）＝３２である。そして、ＩＤ２４は、ルックアップメッセージをＩＤ３２へ転送する。
（ホップ３）ＩＤ３２のフィンガーテーブルによれば、ＩＤ３９も近い３２＋２２（４）＝３６である。そして、ＩＤ３２は、ルックアップメッセージをＩＤ３６へ転送する。
（ホップ４）ＩＤ３６のフィンガーテーブルによれば、ＩＤ３９も近い３６＋２１（２）＝３８である。そして、ＩＤ３６は、ルックアップメッセージをＩＤ３８へ転送する。
（ホップ５）ＩＤ３８のフィンガーテーブルによれば、ＩＤ３９も近い３８＋２０（１）＝３９である。そして、ＩＤ３６は、ルックアップメッセージをＩＤ３９へ転送する。
これによって、ピアノードＩＤ８は、ルックアップメッセージをＩＤ３９へ転送し、bob@auone.jpの登録情報を得ることができる。
【００１３】
また、他の技術として、ＩＭＳ(IP Multimedia Subsystem)などの事業者ネットワークと、アクセスネットワークに接続された小型基地局をピアノードとして構成するオーバレイネットワークとを連携させたセッション制御技術がある（例えば非特許文献２参照）。この技術は、ブラックリスト方式を用いる。オーバレイネットワークを介してピアノード間で遅延時間を計測し、その遅延時間が規定時間以上となる識別値空間をブラックリストに登録する。更に、セッション確立時に、オーバレイネットワークでのルーティングに使用する識別値が、当該ブラックリストに登録されているか検索する。そして、未登録の場合には、オーバレイネットワークを介してセッションを確立し、登録されている場合には、ＩＭＳを介してセッションを確立する。これにより、オーバレイネットワークを介したセッション確立時間が規定時間以上となる割合を大幅に削減できると共に、ＩＭＳの処理負荷も軽減することができる。
【００１４】
更に、オーバレイネットワークによれば、ピアノードが動的に参加・離脱をすることができる環境も想定される。この場合、オーバレイネットワークにおけるピアノード間の経路も変化するために、ブラックリストも動的に更新する必要がある。そのため、各ピアノードは、適宜、ランダムに選択した識別値に対して、専用メッセージ（例えば遅延時間計測メッセージ）を送信する。これによって、遅延時間を計測し、遅延時間が規定時間以上となる識別値空間を検出し、ブラックリストを更新する（例えばＶＬＡ(Voluntary Latency Acquisition)方式）。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】Ion Stoica, Robert Morris, David Karger, M.Frans Kaashoek, and Hari Balakrishnan, “Chord: A Scalable Peer-to-peer LookupService for Internet Applications”, Proc. ACM SIGCOMM'01, San Diego, Sept.2001.
【非特許文献２】T. Warabino: “Session Control CooperatingCore and Overlay Networks for “Minimum Core” Architecture”, IEEE GlobalCommunications Conference (GLOBECOM 2009).
【発明の概要】
【発明が解決しようとする課題】
【００１６】
非特許文献１に記載された技術によれば、アドレス検索時における遅延時間の判定については何ら開示されていない。例えばＰ２ＰＳＩＰネットワークによれば、ピアノード数が膨大となった場合、宛先端末のアドレス情報を検索する際の中継ノード数も膨大となる。特に、リアルタイム性を要するセッション制御については、セッション確立時間が増大するという問題があった。例えば、ピアノード数を１０００万台とし、ピアノード間での遅延時間を５０ｍ秒と仮定した場合、セッション確立時間は最大４.６秒になると試算される。総務省が定める事業用電気通信設備規則では、「セッション確立時間(Connection Setup-Delay)が３秒以上となる確率を０．０１以下とする」と規定しており、そのままでは事業者品質のサービスを提供できない。そのため、オーバレイネットワーク上でセッション制御を行う場合には、セッション確立時間を保証することができない問題がある。
【００１７】
また、非特許文献２に記載された技術によれば、ランダムに選択した識別値毎に、専用メッセージを送信し、その遅延時間を計測しなければならない。ピアノード数が膨大となった場合、計測対象となる識別値はランダムであるので、ブラックリストに登録すべき識別値空間を効率的に検出することができない。このために、ブラックリスト方式の性能が劣化するという問題もある。
【００１８】
そこで、本発明は、オーバレイネットワークにおける宛先識別値に基づいて、目標ピアノードに対して、実際にメッセージを送受信して遅延時間を計測する必要があるか否かを事前に判定することができる遅延超過推定方法、ピアノード及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
本発明によれば、複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおける遅延超過推定方法であって、
各ピアノードは、１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストとを有し、
自ピアノードから見て、目標ピアノードにおける遅延時間が、規定時間以上となるか否かを判定するために、
目標ピアノードの識別値targetと、自ピアノードの識別値ownとの差である距離distanceを算出する第１のステップと、
推定中継端末数を表すホップ数eHopを初期値に設定し、乗数変数ｉを所定最大値ｉmaxに設定する第２のステップと、
距離distanceが２のｉ乗以上となる場合に、ホップ数eHopを１増分し、距離distanceから２のｉ乗を減算し、乗数変数ｉを１減分する操作を、距離distanceが閾値距離intervalよりも小さくなるまで繰り返す第３のステップと、
最終的に得られたホップ数eHopが、閾値ホップ数thresholdよりも大きい目標ピアノードを、遅延超過リストへの登録候補として選択される第４のステップと
を有することを特徴とする。
【００２０】
本発明の遅延超過推定方法における他の実施形態によれば、
オーバレイネットワークのプロトコルは、分散ハッシュテーブル（ＤＨＴ:Distributed Hash Table）を用いた構造化オーバレイのＣｈｏｒｄであり、
ルーティングテーブルは、フィンガーテーブルであることも好ましい。
【００２１】
本発明の遅延超過推定方法における他の実施形態によれば、
自ピアノードは、目標ピアノードの識別値targetをランダムに複数選択し、
各目標ピアノードの識別値targetに対して、第１から第４のステップを実行することによって、自ピアノードから見た識別値全範囲における遅延超過リストを作成することも好ましい。
【００２２】
本発明の遅延超過推定方法における他の実施形態によれば、
自ピアノードが、目標ピアノードの宛先識別値を含む遅延計測要求メッセージを送信する前に、第１から第４のステップを実行し、
遅延超過リストの登録候補として選択された目標ピアノードについて、該目標ピアノードの宛先識別値を含む遅延計測要求メッセージを送信する第５のステップを有することも好ましい。
【００２３】
本発明の遅延超過推定方法における他の実施形態によれば、
各ピアノードは、ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測しており、
第５のステップは、
自ピアノードが、宛先識別値を含む遅延計測要求メッセージを、ルーティングテーブルに登録された次ピアノードへ送信するステップと、
中継ピアノードが、受信した遅延計測要求メッセージを、更に次ピアノードへ転送するステップと、
目標ピアノードが、遅延計測要求メッセージを受信した際に、応答メッセージを返信するステップと、
中継ピアノードが、応答メッセージを受信した際に、該応答メッセージを送信した次ピアノードとの間の遅延時間を追記し転送するステップと、
自ピアノードは、応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該自ピアノードから順に加算して、該遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、遅延超過リストに登録するステップと
を有することも好ましい。
【００２４】
本発明の遅延超過推定方法における他の実施形態によれば、各ピアノードは、ルーティングテーブルに登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ(Round Trip Time)値を計測し、そのＲＴＴ値から遅延時間を算出することも好ましい。
【００２５】
本発明の遅延超過推定方法における他の実施形態によれば、自ピアノードが、目標ピアノードへメッセージを送信する際に、目標ピアノードの識別値が、遅延超過リストに含まれている場合、オーバレイネットワーク以外の物理ネットワークを直接的に用いて、目標ピアノードへメッセージを送信することも好ましい。
【００２６】
本発明によれば、複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおけるピアノードであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、
遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストと、
自ピアノードから見て、目標ピアノードにおける遅延時間が、規定時間以上となるか否かを判定する遅延超過候補判定手段と
を有し、
遅延超過候補判定手段は、
目標ピアノードの識別値targetと、自ピアノードの識別値ownとの差である距離distanceを算出し、
推定中継端末数を表すホップ数eHopを初期値に設定し、乗数変数ｉを所定最大値ｉmaxに設定し、
距離distanceが２のｉ乗以上となる場合に、ホップ数eHopを１増分し、距離distanceから２のｉ乗を減算し、乗数変数ｉを１減分する操作を、距離distanceが閾値距離intervalよりも小さくなるまで繰り返し、
最終的に得られたホップ数eHopが、閾値ホップ数thresholdよりも大きい目標ピアノードを、遅延超過リストへの登録候補として選択する
ことを特徴とする。
【００２７】
本発明のピアノードにおける他の実施形態によれば、
オーバレイネットワークのプロトコルは、分散ハッシュテーブル（ＤＨＴ:Distributed Hash Table）を用いた構造化オーバレイのＣｈｏｒｄであり、
ルーティングテーブルは、フィンガーテーブルであることも好ましい。
【００２８】
本発明のピアノードにおける他の実施形態によれば、目標ピアノードの識別値targetをランダムに複数選択し、各識別値targetに対して遅延超過候補判定手段を実行し、自ピアノードから見た識別値全範囲における遅延超過リストへの登録候補を選択することも好ましい。
【００２９】
本発明のピアノードにおける他の実施形態によれば、
目標ピアノードの宛先識別値を含む遅延計測要求メッセージを送信する前に、遅延超過候補判定手段を実行し、遅延超過リストの登録候補として選択された目標ピアノードについて、該目標ピアノードの宛先識別値を含む遅延計測要求を、ルーティングテーブルに登録された次ピアノードへ送信する遅延計測要求送信手段を更に有することも好ましい。
【００３０】
本発明のピアノードにおける他の実施形態によれば、
ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する遅延時間計測手段と、
中継ピアノードとして、受信した遅延計測要求メッセージを、更に次ピアノードへ転送する中継要求転送手段と、
目標ピアノードとして、遅延計測要求メッセージを受信した際に、応答メッセージを返信する目標応答送信手段と、
中継ピアノードとして、応答メッセージを受信した際に、該応答メッセージを送信した次ピアノードとの間の遅延時間を追記し転送する中継応答転送手段と、
自ピアノードとして、応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該自ピアノードから順に加算して、該遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、遅延超過リストに登録する遅延超過リスト生成手段と
を有することも好ましい。
【００３１】
本発明のピアノードにおける他の実施形態によれば、遅延時間計測手段は、ルーティングテーブルに登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ値を計測し、そのＲＴＴ値から遅延時間を算出することも好ましい。
【００３２】
本発明のピアノードにおける他の実施形態によれば、自ピアノードが、目標ピアノードへメッセージを送信する際に、目標ピアノードの識別値が、遅延超過リストに含まれているか否かを判定し、真と判定された場合、オーバレイネットワーク以外の物理ネットワークを直接的に用いて、目標ピアノードへメッセージを送信する送信切替手段を更に有することも好ましい。
【００３３】
本発明によれば、複数のピアノードによって接続された物理ネットワーク上に仮想的に構成されたオーバレイネットワークにおけるピアノードに搭載されたコンピュータを機能させるプログラムであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、
遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストと、
自ピアノードから見て、目標ピアノードにおける遅延時間が、規定時間以上となるか否かを判定する遅延超過候補判定手段と
してコンピュータを機能させ、
遅延超過候補判定手段は、
目標ピアノードの識別値targetと、自ピアノードの識別値ownとの差である距離distanceを算出し、
推定中継端末数を表すホップ数eHopを初期値に設定し、乗数変数ｉを所定最大値ｉmaxに設定し、
距離distanceが２のｉ乗以上となる場合に、ホップ数eHopを１増分し、距離distanceから２のｉ乗を減算し、乗数変数ｉを１減分する操作を、距離distanceが閾値距離intervalよりも小さくなるまで繰り返し、
最終的に得られたホップ数eHopが、閾値ホップ数thresholdよりも大きい目標ピアノードを、遅延超過リストへの登録候補として選択する
ようにコンピュータを機能させることを特徴とする。
【発明の効果】
【００３４】
本発明の遅延超過推定方法、ピアノード及びプログラムによれば、オーバレイネットワークにおける宛先識別値に基づいて、目標ピアノードに対して、実際にメッセージを送受信して遅延時間を計測する必要があるか否かを事前に判定することができる。
【図面の簡単な説明】
【００３５】
【図１】オーバレイネットワークのシステム構成図である。
【図２】Ｃｈｏｒｄを用いた構造化オーバレイの説明図である。
【図３】本発明における遅延超過を推定するフローチャートである。
【図４】ピアノード間のシーケンス図である。
【図５】図４のＳ４１のステップを表す説明図である。
【図６】図４のＳ４２〜Ｓ４６のステップを表す説明図である。
【図７】本発明におけるピアノードの機能構成図である。
【発明を実施するための形態】
【００３６】
以下、本発明の実施の形態について、図面を用いて詳細に説明する。
【００３７】
本発明におけるピアノードは、オーバレイネットワークのプロトコルとして、分散ハッシュテーブル（ＤＨＴ:Distributed Hash Table）を用いた構造化オーバレイのＣｈｏｒｄを実装する。また、各ピアノードは、「ルーティングテーブル」（Ｃｈｏｒｄにおける拡張されたフィンガーテーブル）と、「遅延超過リスト」（非特許文献２におけるブラックリスト）とを有する。
【００３８】
「ルーティングテーブル」は、当該ピアノードの識別値から、１ホップで通信可能な識別値を有する次ピアノードを登録する。Ｃｈｏｒｄの場合、フィンガーテーブルを意味する。例えば、以下の表１によれば、ＩＤ８から見た隣接ピアノードと、各ピアノードとの間の遅延時間と有する。隣接ピアノードは、２ｋを増分した識別値に設定される（ショートカットルーティング）。
【表１】
2011211292.tif 000003
【００３９】
また、「遅延超過リスト」は、遅延時間が規定時間以上となる識別値範囲を登録する。以下の表２によれば、ＩＤ８から見て、ＩＤ３２〜ＩＤ３９は、遅延時間が規定時間以上となることを意味する。また、その遅延時間の計測時刻も含むことも好ましい。計測時刻から所定時間を超えたエントリは、削除させるものであってもよい。
【表２】
2011211292.tif 000004
【００４０】
例えば非特許文献２によれば、この「遅延超過リスト」を作成するために、ランダムに選択した識別値毎に、実際にメッセージを送受信して遅延時間を計測しなければならない。これに対し、本発明によれば、目標ピアノードに対して、実際にメッセージを送受信して遅延時間を計測する必要があるか否かを事前に判定することができる。即ち、目標ピアノードに対して、実際にメッセージを送信する前に、その宛先識別値が、遅延超過リストへの登録候補に該当するか否かを判定する。該当する場合、当該ピアノードは、改めて、目標ピアノードの宛先識別値を含む遅延計測要求メッセージを送信する。そして、その応答メッセージを受信することによって遅延時間を計測し、ブラックリストが更新される。
【００４１】
図３は、本発明における遅延超過を推定するフローチャートである。
【００４２】
（Ｓ３０１）最初に、目標ピアノードの識別値targetIDを決定する。ここで、ブラックリストを更新するために、識別値targetIDをランダムに決定する場合、乱数randID()から得られるものであってもよい。また、乱数を用いることなく、ユーザによって予め決定されるものであってもよい。
【００４３】
（Ｓ３０２）目標ピアノードの識別値targetIDと、自ピアノードの識別値ownIDとの差である距離distanceを算出する。
【００４４】
（Ｓ３０３）次に、平均識別値空間intervalを決定する。平均識別値空間とは、１台のピアノードが管理する識別値空間の平均を意味する。平均識別値空間は、「サクセッサリスト」に登録されたピアノードが管理する識別値空間の和を、「サクセッサリスト」に登録されたピア数で除算した値である。この平均識別値空間intervalを、以下の閾値距離intervalとする。
【００４５】
（Ｓ３０４）推定中継端末数を表すホップ数eHopを初期値に設定する。
【００４６】
（Ｓ３０５）乗数変数ｉを所定最大値ｉmaxに設定する。Ｃｈｏｒｄの場合、１６０ビットのハッシュ識別値空間が表される。従って、所定最大値ｉmaxは「１５９」に設定される。
【００４７】
（Ｓ３０６）Ｓ３１２との間で、Ｓ３０７〜Ｓ３１１の処理を繰り返す。
【００４８】
（Ｓ３０７）距離distanceが、閾値距離interval以上であるか否かを判定する。距離distanceが、閾値距離intervalよりも小さい場合、ループを抜け、Ｓ３１３へ移行する。
【００４９】
（Ｓ３０８）距離distanceが、２のｉ乗以上であるか否かを判定する。距離distanceが、２のｉ乗よりも小さい場合、Ｓ３１１へ移行する。
【００５０】
（Ｓ３０９）距離distanceが、２のｉ乗以上である場合、ホップ数eHopを１増分する。
【００５１】
（Ｓ３１０）距離distanceから２のｉ乗を減算する。
【００５２】
（Ｓ３１１）乗数変数ｉを１減分する。従って、乗数変数ｉは、１５９、１５８、１５７、・・・、０の順に減分されていく。
【００５３】
（Ｓ３１２）Ｓ３０６へ移行する。
【００５４】
（Ｓ３１３）最終的に得られたホップ数eHopは、目標ターゲットまでの推定中継端末数を表す。そして、ホップ数eHopが、閾値ホップ数thresholdよりも大きいか否かを判定する。ホップ数eHopが、閾値ホップ数threshold以下である場合、処理を終了する。
【００５５】
（Ｓ３１４）ホップ数eHopが、閾値ホップ数thresholdよりも大きい場合、目標ピアノードの識別値を、遅延超過リストへの登録候補として選択される。ここで、登録候補とされた識別値（目標ピアノードの宛先識別値）を含む遅延計測要求メッセージを、隣接ピアノードへ送信する。
【００５６】
本発明によれば、Ｓ３１４によって目標ピアノードの宛先識別値を含む遅延計測要求メッセージを送信する前に、Ｓ３０１〜Ｓ３１３を実行する。また、Ｓ３０１によって、目標ピアノードの識別値targetをランダムに複数選択し、Ｓ３０２〜Ｓ３１４を繰り返すことによって、自ピアノードから見た識別値全範囲における遅延超過リストを作成することができる。
【００５７】
図４は、本発明におけるシーケンス図である。図５は、図４のＳ４１のステップを表す説明図である。図６は、図４のＳ４２〜Ｓ４６のステップを表す説明図である。
【００５８】
（Ｓ４１）各ピアノードが、ルーティングテーブルに登録された次ピアノード毎に、Keep-Aliveメッセージを定期的に送信し、その応答メッセージを受信する。Ｃｈｏｒｄによれば、フィンガーテーブルには、自ピアノードＩＤに２ｍ（m=159, 158, … 0）を加算した値を入力としたサクセッサのピアノードの識別値を次ピアノードとして登録している。これによって、各ピアノードは、次ピアノードとの間の遅延時間ＲＴＴ(Round Trip Time)を計測する。遅延時間は、そのルーティングテーブルに記憶される。
【００５９】
図３によれば、ピアノードＩＤ８は、フィンガーテーブルに登録されているＩＤ２４へ、Keep-Aliveメッセージを送信し、その応答を受信する。これによって、ピアノードＩＤ８は、ＩＤ２４との間の遅延時間Ｄ（８−２４）を計測する。
Ｄ（ｘ−ｙ）：ＩＤｘ及びＩＤｙの間の遅延時間
【００６０】
図３によれば、同様に、ピアノードＩＤ２４は、フィンガーテーブルに登録されているＩＤ３２との間の遅延時間Ｄ（２４−３２）を計測する。また、ピアノードＩＤ３２は、フィンガーテーブルに登録されているＩＤ３６との間の遅延時間Ｄ（３２−３６）を計測する。更に、ピアノードＩＤ３６は、フィンガーテーブルに登録されているＩＤ３８との間の遅延時間Ｄ（３６−３８）を計測する。更に、ピアノードＩＤ３８は、フィンガーテーブルに登録されているＩＤ３９との間の遅延時間Ｄ（３８−３９）を計測する。
【００６１】
（Ｓ４２）送信元ピアノードＩＤ８が、宛先識別値としてＩＤ３９を含む要求メッセージを、ルーティングテーブルに登録された次ピアノードＩＤ２４へ送信する。尚、要求メッセージを中継する中継ピアノードは、本発明における送信元ピアノードとして動作してもよい。
【００６２】
（Ｓ４３）中継ピアノードＩＤ２４は、受信した要求メッセージを、更に次ピアノードＩＤ３２へ転送する。また、中継ピアノードＩＤ３２は、受信した要求メッセージを、更に次ピアノードＩＤ３６へ転送する。更に、中継ピアノードＩＤ３６は、受信した要求メッセージを、更に次ピアノードＩＤ３８へ転送する。更に、中継ピアノードＩＤ３８は、受信した要求メッセージを、更に宛先ピアノードＩＤ３９へ転送する。
【００６３】
（Ｓ４４）宛先ピアノードＩＤ３９は、受信した要求メッセージに対して、応答メッセージを、中継ピアノードＩＤ３８へ返信する。
【００６４】
中継ピアノードＩＤ３８は、受信した応答メッセージを、中継ピアノードＩＤ３６へ転送する。このとき、中継ピアノードＩＤ３８は、その応答メッセージに、中継識別値ＩＤ３８と、ピアノードＩＤ３９の間の遅延時間Ｄ（３８−３９）とを追記する。更に、中継ピアノードＩＤ３６は、受信した応答メッセージを、中継ピアノードＩＤ３２へ転送する。このとき、中継ピアノードＩＤ３６は、その応答メッセージに、中継識別値ＩＤ３６と、ピアノードＩＤ３８の間の遅延時間Ｄ（３６−３８）とを追記する。更に、中継ピアノードＩＤ３２は、受信した応答メッセージを、中継ピアノードＩＤ２４へ転送する。このとき、中継ピアノードＩＤ３２は、その応答メッセージに、中継識別値ＩＤ３２と、ピアノードＩＤ３６の間の遅延時間Ｄ（３２−３６）とを追記する。更に、中継ピアノードＩＤ２４は、受信した応答メッセージを、中継ピアノードＩＤ８へ転送する。このとき、中継ピアノードＩＤ２４は、その応答メッセージに、中継識別値ＩＤ２４と、ピアノードＩＤ３２の間の遅延時間Ｄ（２４−３２）とを追記する。
【００６５】
（Ｓ４５）送信元ピアノードは、応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該送信元ピアノードから順に加算する。そして、その遅延時間が規定時間以上となる次ピアノード以降の識別値範囲を、遅延超過リストに登録する。
【００６６】
遅延超過リストには、識別値空間を表す開始（Ｆｒｏｍ）及び終了（Ｔｏ）と、計測時刻とを記録する。例えば、図３によれば、ピアノードＩＤ８は、自ノードから近い順（Ｄ（８−２４）→Ｄ（２４−３２）→Ｄ（３２−３６）→Ｄ（３６−３８）→Ｄ（３８−３９））に遅延時間を加算する。ここで、Ｄ（８−２４）＋Ｄ（２４−３２）の時点で、規定時間以上となったとする。そうであれば、ＩＤ３２（Ｆｒｏｍ）〜ＩＤ３９（Ｔｏ）の識別値空間は遅延超過であるとして、遅延超過リストに登録する。
【００６７】
（Ｓ４６）送信元ピアノードが、要求メッセージを更に送信する際（例えばデータ検索時）に、その要求メッセージの宛先識別値が、遅延超過リストに含まれているか否かを判定する。その宛先識別値が遅延超過リストに含まれている場合、その要求メッセージの遅延時間は、規定時間以上を要すると判定され、そうでない場合、その遅延時間は、規定時間よりも短いと判定される。そして、送信元ピアノードは、要求メッセージを次ピアノ−ドへ送信する。
【００６８】
また、Ｓ４６について、目標ピアノードへメッセージを送信する際に、目標ピアノードの識別値が、遅延超過リストに含まれている場合、オーバレイネットワーク以外の物理ネットワーク（例えばＩＭＳ）を直接的に用いて、目標ピアノードへメッセージを送信することも好ましい。
【００６９】
図７は、本発明におけるピアノードの機能構成図である。
【００７０】
図７によれば、ピアノード１は、物理ネットワーク上に仮想的に構成されたオーバレイネットワークに接続される。図７によれば、ピアノード１は、通信インタフェース部１００と、ＴＣＰ／ＩＰ(Transmission Control Protocol / Internet Protocol)レイヤ部１０１とを有する。通信インタフェース部１００は、物理ネットワークに接続される。ＴＣＰ／ＩＰレイヤ部１０１は、オーバレイネットワークにおける転送プロトコルとしてＴＣＰ／ＩＰを実装する。
【００７１】
また、図７によれば、ピアノード１は、ルーティングテーブル１１１と、遅延超過リスト１１２と、遅延超過候補判定部１２１と、遅延計測要求送信部１２２と、遅延超過リスト生成部１２３と、遅延時間計測部１３１と、中継要求転送部１３２と、中継応答転送部１３３と、目標応答送信部１３４と、送信切替部１３５とを有する。これら機能構成部は、ピアノードに搭載されたコンピュータを機能させるプログラムを実行することによって実現される。尚、オーバレイネットワークのプロトコルは、例えば分散ハッシュテーブル（ＤＨＴ）を用いた構造化オーバレイのＣｈｏｒｄである。
【００７２】
ルーティングテーブル１１１は、当該ピアノードの識別値から、１ホップで通信可能な識別値を有する次ピアノードを登録する（前述の表１参照）。ルーティングテーブル１１１は、Ｃｈｏｒｄにおけるフィンガーテーブルである。
【００７３】
遅延超過リスト１１２は、遅延時間が規定時間以上となる識別値範囲を登録する（前述の表２参照）。
【００７４】
遅延超過候補判定部１２１は、自ピアノードから見て、目標ピアノードにおける遅延時間が、規定時間以上となるか否かを判定する。遅延超過候補判定部１２１は、少なくとも以下のステップを実行する。
（Ｓ１）目標ピアノードの識別値targetと、自ピアノードの識別値ownとの差である距離distanceを算出する。
（Ｓ２）推定中継端末数を表すホップ数eHopを初期値に設定し、乗数変数ｉを所定最大値ｉmaxに設定する。
（Ｓ３）距離distanceが２のｉ乗以上となる場合に、ホップ数eHopを１増分し、距離distanceから２のｉ乗を減算し、乗数変数ｉを１減分する操作を、距離distanceが閾値距離intervalよりも小さくなるまで繰り返す。
（Ｓ４）最終的に得られたホップ数eHopが、閾値ホップ数thresholdよりも大きい目標ピアノードを、遅延超過リストへの登録候補として選択する。
尚、遅延超過候補判定部１２１は、目標ピアノードの識別値targetをランダムに複数選択し、各識別値targetに対して前述のステップを実行することも好ましい。これによって、自ピアノードから見た識別値全範囲における遅延超過リストへの登録候補を選択することができる。
【００７５】
遅延計測要求送信部１２２は、目標ピアノードの宛先識別値を含む遅延計測要求メッセージを送信する。ここで、宛先識別値は、遅延超過リストの登録候補として選択されたものである。遅延計測要求送信部１２２は、その遅延計測要求を、ルーティングテーブルに登録された次ピアノードへ送信する。
【００７６】
遅延超過リスト生成部１２３は、遅延計測要求メッセージに対する応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該自ピアノードから順に加算する。そして、その遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、遅延超過リストに登録する。
【００７７】
遅延時間計測部１３１は、ルーティングテーブル１１１に登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ値を計測し、そのＲＴＴ値から遅延時間を算出する。
【００７８】
中継要求転送部１３２は、中継ピアノードとして、受信した遅延計測要求メッセージを、更に次ピアノードへ転送する。
【００７９】
中継応答転送部１３３は、中継ピアノードとして、応答メッセージを受信した際に、該応答メッセージを送信した次ピアノードとの間の遅延時間を追記し転送する。
【００８０】
目標応答送信部１３４は、目標ピアノードとして、遅延計測要求メッセージを受信した際に、応答メッセージを返信する。
【００８１】
送信切替部１３５は、自ピアノードが、目標ピアノードへメッセージを送信する際に、目標ピアノードの識別値が、遅延超過リストに含まれているか否かを判定し、真と判定された場合、オーバレイネットワーク以外の物理ネットワークを直接的に用いて、目標ピアノードへメッセージを送信する。
【００８２】
以上、詳細に説明したように、本発明の遅延超過推定方法、ピアノード及びプログラムによれば、オーバレイネットワークにおける宛先識別値に基づいて、目標ピアノードに対して、実際にメッセージを送受信して遅延時間を計測する必要があるか否かを事前に判定することができる。これによって、遅延超過リスト（ブラックリスト）に登録すべき識別値空間を効率的に検出することができ、ブラックリスト方式の性能を向上させることができる。これは、ピアノードが動的に参加・離脱をすることができる環境に構成されたオーバレイネットワークに適する。
【００８３】
遅延時間が規定時間以内であるか否かを即時に判定することによって、様々な用途に適用することができる。例えば、事業者システムであるＩＭＳ(IP Multimedia Subsystem)／ＭＭＤ(Multimedia Domain)と、ピアノードで構築したオーバレイネットワークとを連携されることによって、高品質なセッション制御を低コストで実現することができる。ＩＭＳシステム及びオーバレイネットワークの双方に接続したピアノードは、セッション確立時に、オーバレイネットワークを優先的に使用することによって、ＩＭＳシステムへの負荷を削減することができる。しかしながら、ピアノード数が膨大となる場合には、データ検索時の中継端末数も無視できなくなる。特にリアルタイム性を求められるセッション制御では、セッション確立時間が増大するという問題があった。そのため、本発明によって、送信元ピアノードが、オーバレイネットワーク上でのセッション確立処理に要する遅延時間を推定する。その遅延時間が規定時間を超える場合に、ＩＭＳシステムを介したセッションを確立する。これによって、システムとしてのセッション確立時間を保証することが可能となる。
【００８４】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００８５】
１  ピアノード
１００  通信インタフェース部
１０１  ＴＣＰ／ＩＰレイヤ部
１１１  ルーティングテーブル
１１２  遅延超過リスト
１２１  遅延超過候補判定部
１２２  遅延計測要求送信部
１２３  遅延超過リスト生成部
１３１  遅延時間計測部
１３２  中継要求転送部
１３３  中継応答転送部
１３４  目標応答送信部
１３５  送信切替部
２  送信元端末
３  宛先端末
４  物理ネットワーク
５  オーバレイネットワーク
【図１】
2011211292.tif 000005
【図２】
2011211292.tif 000006
【図３】
2011211292.tif 000007
【図４】
2011211292.tif 000008
【図５】
2011211292.tif 000009
【図６】
2011211292.tif 000010
【図７】
2011211292.tif 000011