(57)【要約】【課題】オーバレイネットワークにおける宛先識別値に基づいて、そのピアノードに対する遅延時間が規定時間以内であるか否かを即時に判定することができる遅延時間判定方法、ピアノード及びプログラムを提供する。【解決手段】各ピアノードは、遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストを有し、ルーティングテーブルに登録された次ピアノードとの間の遅延時間を計測する。中継ピアノードが、要求メッセージに対応する応答メッセージを受信した際に、その応答メッセージを送信した次ピアノードとの間の遅延時間を追記して転送する。送信元ピアノードは、応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該送信元ピアノードから順に加算して、該遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、遅延超過リストに登録する。【選択図】図５
2010087627.tif 000002
【特許請求の範囲】
【請求項１】
複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおける遅延時間判定方法であって、
各ピアノードは、１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストとを有し、
各ピアノードが、前記ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する第１のステップと、
送信元ピアノードが、宛先識別値を含む要求メッセージを、前記ルーティングテーブルに登録された次ピアノードへ送信する第２のステップと、
中継ピアノードが、受信した前記要求メッセージを、更に次ピアノードへ転送する第３のステップと、
前記中継ピアノードが、前記要求メッセージに対応する応答メッセージを受信した際に、該応答メッセージを送信した次ピアノードとの間の前記遅延時間を追記して転送する第４のステップと、
前記送信元ピアノードは、前記応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該送信元ピアノードから順に加算して、該遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、前記遅延超過リストに登録する第５のステップと、
前記送信元ピアノードが、要求メッセージを更に送信する際に、該要求メッセージの宛先識別値が、前記遅延超過リストに含まれているか否かを判定する第６のステップと
を有することを特徴とする遅延時間判定方法。
【請求項２】
前記送信元ピアノードは、第１のピアノードから受信した要求メッセージを、第２のピアノードへ転送する中継ピアノードであることを特徴とする請求項１に記載の遅延時間判定方法。
【請求項３】
前記第１のステップについて、ルーティングテーブルに登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ(Round Trip Time)値を計測し、そのＲＴＴ値から遅延時間を算出することを特徴とする請求項１又は２に記載の遅延時間判定方法。
【請求項４】
前記送信元ピアノードが、宛先識別値を含む遅延検索要求メッセージを、前記ルーティングテーブルに登録された次ピアノードへ送信するステップと、
前記中継ピアノードが、前記遅延検索要求メッセージを受信した際に、該検索要求メッセージの宛先識別値が、当該中継ピアノードの前記遅延超過リストに含まれている場合、遅延超過通知メッセージを返信するステップと
を有することを特徴とする請求項１から３のいずれか１項に記載の遅延時間判定方法。
【請求項５】
ピアノードが、次ピアノードへ、識別値空間を含むリスト要求メッセージを送信するステップと、
前記次ピアノードが、当該次ピアノードが保持する遅延超過リストの中で、前記識別値空間と重複するリスト情報を返信するステップと
を有することを特徴とする請求項１から４のいずれか１項に記載の遅延時間判定方法。
【請求項６】
前記次ピアノードが、前記リスト要求メッセージを受信した際に、前記遅延超過リストの中で識別値範囲の広いリスト情報を、優先的に返信することを特徴とする請求項５に記載の遅延時間判定方法。
【請求項７】
前記遅延超過リストは、識別値範囲のエントリ毎に登録時刻を更に含んでおり、
前記次ピアノードが、前回時刻を含む前記リスト要求メッセージを受信した際に、前記遅延超過リストの中で前回時刻以降の登録時刻が記録された識別値範囲のリスト情報を返信することを特徴とする請求項５に記載の遅延時間判定方法。
【請求項８】
前記オーバレイネットワークのプロトコルは、分散ハッシュテーブル（ＤＨＴ:Distributed Hash Table）を用いた構造化オーバレイのＣｈｏｒｄであり、
前記ルーティングテーブルは、フィンガーテーブルである
ことを特徴とする請求項１から７のいずれか１項に記載の遅延時間判定方法。
【請求項９】
複数のピアノードによって接続された物理ネットワーク上に仮想的に構成されたオーバレイネットワークにおけるピアノードであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、
遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストと、
前記ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する遅延時間計測手段と、
宛先識別値を含む要求メッセージを、前記ルーティングテーブルに登録された次ピアノードへ送信する送信元要求手段と、
受信した前記要求メッセージを、更に次ピアノードへ転送する中継側要求転送手段と、
前記要求メッセージに対応する応答メッセージを受信した際に、該応答メッセージを送信した次ピアノードとの間の前記遅延時間を追記して転送する中継側応答転送手段と、
前記応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該送信元ピアノードから順に加算して、該遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、前記遅延超過リストに登録する送信元リスト登録手段と、
要求メッセージを更に送信する際に、該要求メッセージの宛先識別値が、前記遅延超過リストに含まれているか否かを判定する送信元遅延時間判定手段と
を有することを特徴とするピアノード。
【請求項１０】
前記遅延時間計測手段は、前記ルーティングテーブルに登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ値を計測し、そのＲＴＴ値から遅延時間を算出することを特徴とする請求項９に記載のピアノード。
【請求項１１】
宛先識別値を含む遅延検索要求メッセージを、前記ルーティングテーブルに登録された次ピアノードへ送信する送信元検索手段と、
前記遅延検索要求メッセージを受信した際に、該検索要求メッセージの宛先識別値が、当該中継ピアノードの前記遅延超過リストに含まれている場合、遅延超過通知メッセージを返信する中継側遅延超過通知手段と
を有することを特徴とする請求項９又は１０に記載のピアノード。
【請求項１２】
次ピアノードへ、識別値空間を含むリスト要求メッセージを送信する遅延超過リスト要求手段と、
当該次ピアノードが保持する遅延超過リストの中で、前記識別値空間と重複するリスト情報を返信する遅延超過リスト返信手段と
を有することを特徴とする請求項９から１１のいずれか１項に記載のピアノード。
【請求項１３】
前記遅延超過リスト返信手段は、前記遅延超過リストの中で識別値範囲の広いリスト情報を、優先的に返信することを特徴とする請求項１２に記載のピアノード。
【請求項１４】
複数のピアノードによって接続された物理ネットワーク上に仮想的に構成されたオーバレイネットワークにおけるピアノードに搭載されたコンピュータを機能させるプログラムであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、
遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストと、
前記ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する遅延時間計測手段と、
宛先識別値を含む要求メッセージを、前記ルーティングテーブルに登録された次ピアノードへ送信する送信元要求手段と、
受信した前記要求メッセージを、更に次ピアノードへ転送する中継側要求転送手段と、
前記要求メッセージに対応する応答メッセージを受信した際に、該応答メッセージを送信した次ピアノードとの間の前記遅延時間を追記して転送する中継側応答転送手段と、
前記応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該送信元ピアノードから順に加算して、該遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、前記遅延超過リストに登録する送信元リスト登録手段と、
要求メッセージを更に送信する際に、該要求メッセージの宛先識別値が、前記遅延超過リストに含まれているか否かを判定する送信元遅延時間判定手段と
してコンピュータを機能させることを特徴とするピアノード用のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オーバレイネットワークにおける遅延時間判定方法、ピアノード及びプログラムに関する。
【背景技術】
【０００２】
図１は、オーバレイネットワークのシステム構成図である。
【０００３】
図１のシステムによれば、複数のピアノード１、送信元端末２及び宛先端末３が物理ネットワーク４に接続されている。その物理ネットワーク４上には、複数のピアノード１によって仮想的にオーバレイネットワーク５が構成されている。オーバレイネットワークの代表的な例として、Ｐ２Ｐ(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)をハッシュ関数に入力し、ＩＤ３９を得たとする。そして、送信元端末は、宛先端末の登録情報が登録されたＩＤ３９を検索する。
【０００９】
ここで、「サクセッサリスト」及び「フィンガーテーブル」が用いられる。「サクセッサリスト」とは、ハッシュ空間上で隣接する複数のピアノードの情報を保持する。従って、当該ピアノードの識別値ｋを与えたとき、時計回りに辿って、最初に存在するピアノードを得られる。
【００１０】
「フィンガーテーブル」には、ルーティングテーブルとして、当該ピアノードの識別値（例えばＩＤ８）に、２のｋ乗（１，２，４，８，１６・・・）を加算した数ｘと、その数ｘを入力としたサクセッサ（ｘ）のピアノードの識別値とを記憶する。
【００１１】
図２は、６ビットのハッシュ識別値空間の例であり、フィンガーテーブルの行数は６個となる（例えば、１６０ビットのハッシュ識別値空間の場合、フィンガーテーブルの行数は１６０個）。ここでは、全識別値にピアノードが割り当てられている場合を想定し、hash(bob@auone.jp)＝ＩＤ３９をルックアップする場合について説明する。
【００１２】
（ホップ１）ＩＤ８のフィンガーテーブルによれば、ＩＤ３９に最も近い数は８＋２４（１６）の２４である。ＩＤ８は、ルックアップメッセージをＩＤ２４へ転送する。
（ホップ２）ＩＤ２４のフィンガーテーブルによれば、ＩＤ３９に最も近い数は２４＋２３（８）＝３２である。そして、ＩＤ２４は、ルックアップメッセージをＩＤ３２へ転送する。
（ホップ３）ＩＤ３２のフィンガーテーブルによれば、ＩＤ３９も近い３２＋２２（４）＝３６である。そして、ＩＤ３２は、ルックアップメッセージをＩＤ３６へ転送する。
（ホップ４）ＩＤ３６のフィンガーテーブルによれば、ＩＤ３９も近い３６＋２１（２）＝３８である。そして、ＩＤ３６は、ルックアップメッセージをＩＤ３８へ転送する。
（ホップ５）ＩＤ３８のフィンガーテーブルによれば、ＩＤ３９も近い３８＋２０（１）＝３９である。そして、ＩＤ３６は、ルックアップメッセージをＩＤ３９へ転送する。
これによって、ピアノードＩＤ８は、ルックアップメッセージをＩＤ３９へ転送し、bob@auone.jpの登録情報を得ることができる。
【００１３】
ＩＥＴＦ(Internet Engineering Task Force)によれば、ＳＩＰのシグナリング制御に、Ｐ２Ｐ(Peer-to-Peer)と称される自律分散ネットワークアーキテクチャ技術を融合させた「Ｐ２ＰＳＩＰ」技術を開示している（例えば非特許文献３参照）。Ｐ２ＰＳＩＰによれば、ＳＩＰによるセッション制御機能（ＩＭＳ／ＭＭＤにおけるＣＳＣＦ機能）を、ピアノードに搭載することによって、サーバレスのシステムを実現する。Ｐ２Ｐを用いることにより、ピアノード間で情報の分散管理及び分散制御を実行するために、加入者数の増加に対してもサーバシステムの増強が不要となる。
【００１４】
オーバレイネットワーク構築時やデータ検索時に必要となるメッセージングを規定した技術がある（例えば非特許文献２参照）。具体的には、ＲＥＬＯＡＤ(REsource LOcation And Discovery)について規定する。
【００１５】
また、オーバレイネットワーク内で診断を実行する技術もある（例えば非特許文献３参照）。この技術によれば、診断を実行する送信元端末が、宛先識別値に向けてEcho要求メッセージを送信することによって、当該識別値を管理する宛先端末までの中継端末数や遅延時間を測定する。また、宛先端末でのプログラムの稼働時間（Uptime）や空きディスク容量の情報も取得することができる。更に、宛先端末のみがEcho応答メッセージを送信するPingモードに加えて、Echo要求メッセージを中継した全ピアノードが、送信元端末に対してEcho応答メッセージを送信するTracerouteモードも規定されている。このモードを用いることによって、ネットワーク内のループの検出やボトルネック箇所を特定し、且つ、Malicious端末を検出することができる。
【００１６】
【非特許文献１】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.
【非特許文献２】IETF Internet Draft: “REsource LOcation AndDiscovery (RELOAD)”, draft-ietf-p2psip-reload-00.txt
【非特許文献３】IETF Internet Draft: “Diagnose P2PSIPOverlay Network Failures”, draft-zheng-p2psip-diagnose-02
【発明の開示】
【発明が解決しようとする課題】
【００１７】
しかしながら、Ｐ２ＰＳＩＰネットワークによれば、ピアノード数が膨大となった場合、宛先端末のアドレス情報を検索する際の中継ノード数も膨大となる。特に、リアルタイム性を要するセッション制御については、セッション確立時間が増大するという問題があった。例えば、ピアノード数を１０００万台とし、ピアノード間での遅延時間を５０ｍ秒と仮定した場合、セッション確立時間は最大４.６秒になると試算される。総務省が定める事業用電気通信設備規則では、「セッション確立時間(Connection Setup-Delay)が３秒以上となる確率を０．０１以下とする」と規定しており、そのままでは事業者品質のサービスを提供できない。
【００１８】
非特許文献１及び２に記載された技術によれば、データ検索時の遅延時間を判定する技術については何ら開示していない。
【００１９】
非特許文献３に記載された技術によれば、Echoメッセージにタイムスタンプ情報を付加することで、送信元端末と宛先端末間での片方向／往復遅延の測定をすることができる。しかしながら、この測定は、オーバレイネットワーク上にEchoメッセージを送信する必要があり、宛先識別値が与えられた時点で、遅延時間を即時に判定することはできない。
【００２０】
従って、本発明は、オーバレイネットワークにおける宛先識別値に基づいて、そのピアノードに対する遅延時間が規定時間以内であるか否かを即時に判定することができる遅延時間判定方法、ピアノード及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２１】
本発明によれば、複数のピアノードによって接続された物理ネットワーク上に、仮想的に構成されたオーバレイネットワークにおける遅延時間判定方法であって、
各ピアノードは、１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストとを有し、
各ピアノードが、ルーティングテーブルに登録された次ピアノードとの間の遅延時間を計測する第１のステップと、
送信元ピアノードが、宛先識別値を含む要求メッセージを、ルーティングテーブルに登録された次ピアノードへ送信する第２のステップと、
中継ピアノードが、受信した要求メッセージを、更に次ピアノードへ転送する第３のステップと、
中継ピアノードが、要求メッセージに対応する応答メッセージを受信した際に、該応答メッセージを送信した次ピアノードとの間の遅延時間を追記して転送する第４のステップと、
送信元ピアノードは、応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該送信元ピアノードから順に加算して、該遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、遅延超過リストに登録する第５のステップと、
送信元ピアノードが、要求メッセージを更に送信する際に、該要求メッセージの宛先識別値が、遅延超過リストに含まれているか否かを判定する第６のステップと
を有することを特徴とする。
【００２２】
本発明の遅延時間判定方法における他の実施形態によれば、送信元ピアノードは、第１のピアノードから受信した要求メッセージを、第２のピアノードへ転送する中継ピアノードであってもよい。
【００２３】
本発明の遅延時間判定方法における他の実施形態によれば、ルーティングテーブルに登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ(Round Trip Time)値を計測し、そのＲＴＴ値から遅延時間を算出することも好ましい。
【００２４】
本発明の遅延時間判定方法における他の実施形態によれば、
送信元ピアノードが、宛先識別値を含む遅延検索要求メッセージを、ルーティングテーブルに登録された次ピアノードへ送信するステップと、
中継ピアノードが、遅延検索要求メッセージを受信した際に、該検索要求メッセージの宛先識別値が、当該中継ピアノードの遅延超過リストに含まれている場合、遅延超過通知メッセージを返信するステップとを有することも好ましい。
【００２５】
本発明の遅延時間判定方法における他の実施形態によれば、
ピアノードが、識別値空間を含むリスト要求メッセージを次ピアノードに送信するステップと、
次ピアノードが、当該次ピアノードが保持する遅延超過リストの中で、識別値空間と重複するリスト情報を返信するステップと
を有することも好ましい。
【００２６】
本発明の遅延時間判定方法における他の実施形態によれば、次ピアノードが、リスト要求メッセージを受信した際に、遅延超過リストの中で識別値範囲の広いリスト情報を、優先的に返信することも好ましい。
【００２７】
本発明の遅延時間判定方法における他の実施形態によれば、
遅延超過リストは、識別値範囲のエントリ毎に登録時刻を更に含んでおり、
次ピアノードが、前回時刻を含むリスト要求メッセージを受信した際に、遅延超過リストの中で前回時刻以降の登録時刻が記録された識別値範囲のリスト情報を返信することも好ましい。
【００２８】
本発明の遅延時間判定方法における他の実施形態によれば、
オーバレイネットワークのプロトコルは、分散ハッシュテーブル（ＤＨＴ:Distributed Hash Table）を用いた構造化オーバレイのＣｈｏｒｄであり、
ルーティングテーブルは、フィンガーテーブルであることも好ましい。
【００２９】
本発明によれば、複数のピアノードによって接続された物理ネットワーク上に仮想的に構成されたオーバレイネットワークにおけるピアノードであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、
遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストと、
ルーティングテーブルに登録された次ピアノード毎に遅延時間を計測する遅延時間計測手段と、
宛先識別値を含む要求メッセージを、ルーティングテーブルに登録された次ピアノードへ送信する送信元要求手段と、
受信した要求メッセージを、更に次ピアノードへ転送する中継側要求転送手段と、
要求メッセージに対応する応答メッセージを受信した際に、該応答メッセージを送信した次ピアノードとの間の遅延時間を追記して転送する中継側応答転送手段と、
応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該送信元ピアノードから順に加算して、該遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、遅延超過リストに登録する送信元リスト登録手段と、
要求メッセージを更に送信する際に、該要求メッセージの宛先識別値が、遅延超過リストに含まれているか否かを判定する送信元遅延時間判定手段と
を有することを特徴とする。
【００３０】
本発明のピアノードにおける他の実施形態によれば、遅延時間計測手段は、ルーティングテーブルに登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ値を計測し、そのＲＴＴ値から遅延時間を算出することも好ましい。
【００３１】
本発明のピアノードにおける他の実施形態によれば、
宛先識別値を含む遅延検索要求メッセージを、ルーティングテーブルに登録された次ピアノードへ送信する送信元検索手段と、
遅延検索要求メッセージを受信した際に、該検索要求メッセージの宛先識別値が、当該中継ピアノードの遅延超過リストに含まれている場合、遅延超過通知メッセージを返信する中継側遅延超過通知手段とを有することも好ましい。
【００３２】
本発明のピアノードにおける他の実施形態によれば、
次ピアノードへ、識別値空間を含むリスト要求メッセージを送信する遅延超過リスト要求手段と、
当該次ピアノードが保持する遅延超過リストの中で、識別値空間と重複するリスト情報を返信する遅延超過リスト返信手段とを有することも好ましい。
【００３３】
本発明のピアノードにおける他の実施形態によれば、遅延超過リスト返信手段は、遅延超過リストの中で識別値範囲の広いリスト情報を、優先的に返信することも好ましい。
【００３４】
本発明によれば、複数のピアノードによって接続された物理ネットワーク上に仮想的に構成されたオーバレイネットワークにおけるピアノードに搭載されたコンピュータを機能させるプログラムであって、
１ホップで通信可能な識別値を有する次ピアノードを登録したルーティングテーブルと、
遅延時間が規定時間以上となる識別値範囲を登録した遅延超過リストと、
ルーティングテーブルに登録された次ピアノードとの間の遅延時間を計測する遅延時間計測手段と、
宛先識別値を含む要求メッセージを、ルーティングテーブルに登録された次ピアノードへ送信する送信元要求手段と、
受信した要求メッセージを、更に次ピアノードへ転送する中継側要求転送手段と、
要求メッセージに対応する応答メッセージを受信した際に、該応答メッセージを送信した次ピアノードとの間の遅延時間を追記して転送する中継側応答転送手段と、
応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該送信元ピアノードから順に加算して、該遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、遅延超過リストに登録する送信元リスト登録手段と、
要求メッセージを更に送信する際に、該要求メッセージの宛先識別値が、遅延超過リストに含まれているか否かを判定する送信元遅延時間判定手段と
してコンピュータを機能させることを特徴とする。
【発明の効果】
【００３５】
本発明の遅延時間判定方法、ピアノード及びプログラムによれば、オーバレイネットワークにおける宛先識別値に基づいて、そのピアノードに対する遅延時間が規定時間以内であるか否かを即時に判定することができる。
【発明を実施するための最良の形態】
【００３６】
以下では、図面を用いて、本発明を実施するための最良の形態について詳細に説明する。
【００３７】
本発明における各ピアノードは、「ルーティングテーブル」と、「遅延超過リスト」とを有する。「ルーティングテーブル」は、当該ピアノードの識別値から、１ホップで通信可能な識別値を有する次ピアノードを登録する。Ｃｈｏｒｄの場合、フィンガーテーブルを意味する。
【００３８】
また、「遅延超過リスト」は、遅延時間が規定時間以上となる識別値範囲を登録する。当該ピアノードは、宛先識別値に対して要求メッセージを送信する前に、その宛先識別値が、遅延超過リストに登録された識別値範囲に該当するか否かを判定する。該当する場合、当該ピアノードは、その宛先識別値に対する遅延時間が規定時間以上を要することを認識することができる。
【００３９】
図３は、本発明におけるシーケンス図である。
【００４０】
図４は、図３のＳ３１のステップを表す説明図である。
【００４１】
図５は、図３のＳ３２〜Ｓ３６のステップを表す説明図である。
【００４２】
（Ｓ３１）各ピアノードが、ルーティングテーブルに登録された次ピアノード毎に、Keep-Aliveメッセージを定期的に送信し、その応答メッセージを受信する。Ｃｈｏｒｄによれば、フィンガーテーブルには、自ピアノードＩＤに２ｍ（m=159, 158, … 0）を加算した値を入力としたサクセッサのピアノードの識別値を次ピアノードとして登録している。これによって、各ピアノードは、次ピアノードとの間の遅延時間ＲＴＴを計測する。遅延時間は、そのルーティングテーブルに記憶される。
【００４３】
図３によれば、ピアノードＩＤ８は、フィンガーテーブルに登録されているＩＤ２４へ、Keep-Aliveメッセージを送信し、その応答を受信する。これによって、ピアノードＩＤ８は、ＩＤ２４との間の遅延時間Ｄ（８−２４）を計測する。
Ｄ（ｘ−ｙ）：ＩＤｘ及びＩＤｙの間の遅延時間
【００４４】
図３によれば、同様に、ピアノードＩＤ２４は、フィンガーテーブルに登録されているＩＤ３２との間の遅延時間Ｄ（２４−３２）を計測する。また、ピアノードＩＤ３２は、フィンガーテーブルに登録されているＩＤ３６との間の遅延時間Ｄ（３２−３６）を計測する。更に、ピアノードＩＤ３２は、フィンガーテーブルに登録されているＩＤ３６との間の遅延時間Ｄ（３２−３６）を計測する。更に、ピアノードＩＤ３６は、フィンガーテーブルに登録されているＩＤ３８との間の遅延時間Ｄ（３６−３８）を計測する。更に、ピアノードＩＤ３８は、フィンガーテーブルに登録されているＩＤ３９との間の遅延時間Ｄ（３８−３９）を計測する。
【００４５】
（Ｓ３２）送信元ピアノードＩＤ８が、宛先識別値を含む要求メッセージを、ルーティングテーブルに登録された次ピアノードＩＤ２４へ送信する。尚、要求メッセージを中継する中継ピアノードは、本発明における送信元ピアノードとして動作してもよい。
【００４６】
（Ｓ３３）中継ピアノードＩＤ２４は、受信した要求メッセージを、更に次ピアノードＩＤ３２へ転送する。また、中継ピアノードＩＤ３２は、受信した要求メッセージを、更に次ピアノードＩＤ３６へ転送する。更に、中継ピアノードＩＤ３６は、受信した要求メッセージを、更に次ピアノードＩＤ３８へ転送する。更に、中継ピアノードＩＤ３８は、受信した要求メッセージを、更に宛先ピアノードＩＤ３９へ転送する。
【００４７】
（Ｓ３４）宛先ピアノードＩＤ３９は、受信した要求メッセージに対して、応答メッセージを、中継ピアノードＩＤ３８へ返信する。
【００４８】
中継ピアノードＩＤ３８は、受信した応答メッセージを、中継ピアノードＩＤ３６へ転送する。このとき、中継ピアノードＩＤ３８は、その応答メッセージに、中継識別値ＩＤ３８と、ピアノードＩＤ３９の間の遅延時間Ｄ（３８−３９）とを追記する。更に、中継ピアノードＩＤ３６は、受信した応答メッセージを、中継ピアノードＩＤ３２へ転送する。このとき、中継ピアノードＩＤ３６は、その応答メッセージに、中継識別値ＩＤ３６と、ピアノードＩＤ３８の間の遅延時間Ｄ（３６−３８）とを追記する。更に、中継ピアノードＩＤ３２は、受信した応答メッセージを、中継ピアノードＩＤ２４へ転送する。このとき、中継ピアノードＩＤ３２は、その応答メッセージに、中継識別値ＩＤ３２と、ピアノードＩＤ３６の間の遅延時間Ｄ（３２−３６）とを追記する。更に、中継ピアノードＩＤ２４は、受信した応答メッセージを、中継ピアノードＩＤ８へ転送する。このとき、中継ピアノードＩＤ２４は、その応答メッセージに、中継識別値ＩＤ２４と、ピアノードＩＤ３２の間の遅延時間Ｄ（２４−３２）とを追記する。
【００４９】
（Ｓ３５）送信元ピアノードは、応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該送信元ピアノードから順に加算する。そして、その遅延時間が規定時間以上となる次ピアノード以降の識別値範囲を、遅延超過リストに登録する。
【００５０】
遅延超過リストには、識別値空間を表す開始（Ｆｒｏｍ）及び終了（Ｔｏ）と、登録時刻とを記録する。例えば、図３によれば、ピアノードＩＤ８は、自ノードから近い順（Ｄ（８−２４）→Ｄ（２４−３２）→Ｄ（３２−３６）→Ｄ（３６−３８）→Ｄ（３８−３９））に遅延時間を加算する。ここで、Ｄ（８−２４）＋Ｄ（２４−３２）の時点で、規定時間以上となったとする。そうであれば、ＩＤ３２（Ｆｒｏｍ）〜ＩＤ３９（Ｔｏ）の識別値空間は遅延超過であるとして、遅延超過リストに登録する。
【００５１】
（Ｓ３６）送信元ピアノードが、要求メッセージを更に送信する際（例えばデータ検索時）に、その要求メッセージの宛先識別値が、遅延超過リストに含まれているか否かを判定する。その宛先識別値が遅延超過リストに含まれている場合、その要求メッセージの遅延時間は、規定時間以上を要すると判定され、そうでない場合、その遅延時間は、規定時間よりも短いと判定される。そして、送信元ピアノードは、要求メッセージを次ピアノ−ドへ送信する。
【００５２】
図６は、遅延検索要求メッセージの転送を表す説明図である。
【００５３】
図６によれば、送信元ピアノードＩＤ８が、宛先識別値を含む遅延検索要求メッセージを、ルーティングテーブルに登録された次ピアノードＩＤ２４へ送信する。このとき、遅延検索要求メッセージには、宛先識別値としてＩＤ３９が含まれる。中継ピアノードとなるピアノードＩＤ２４は、遅延検索要求メッセージを受信した際に、その検索要求メッセージの宛先識別値ＩＤ３９が、当該中継ピアノードの遅延超過リストに含まれているか否かを判定する。図６によれば、ＩＤ３９は、ＩＤ２４の遅延超過リストに含まれているので、中継ピアノードＩＤ２４は、遅延超過通知メッセージをＩＤ８へ返信する。これによって、ピアノードＩＤ８は、宛先識別値ＩＤ３９に対しては規定時間を超過するものであると認識することができる。尚、ＩＤ３９が、ＩＤ２４の遅延超過リストに含まれていない場合、中継ピアノードＩＤ２４は、遅延検索要求メッセージを次ノードへ転送する。
【００５４】
図７は、リスト要求メッセージの転送を表す説明図である。
【００５５】
図７によれば、ピアノードＩＤ８が、次ピアノードＩＤ２４へ、メッセージを転送すべき識別値空間（ＩＤ２４〜ＩＤ３９）を含むリスト要求メッセージを送信する。次ピアノードＩＤ２４は、保持する遅延超過リストの中で、識別値空間（ＩＤ２４〜ＩＤ３９）と重複するリスト情報を返信する。図７によれば、ピアノードＩＤ２４は、ＩＤ３６〜ＩＤ３９を遅延超過リストに登録しているので、このエントリが、ピアノードＩＤ８へ返信される。
【００５６】
また、次ピアノードが、リスト要求メッセージを受信した際に、遅延超過リストの中で識別値範囲の広いリスト情報を、優先的に返信することも好ましい。広い識別値範囲について遅延超過が検出されている場合、その情報は、できる限り多くのピアノードで共有すべきである。
【００５７】
更に、遅延超過リストが、識別値範囲のエントリ毎に登録時刻を更に含むことも好ましい。この場合、送信元ピアノードは、リスト要求メッセージに前回時刻を含ませる。このリスト要求メッセージを受信した次ピアノードは、遅延超過リストの中で前回時刻以降の登録時刻が記録された識別値範囲のリスト情報を返信する。これによって、重複するリスト情報の転送を回避することができる。
【００５８】
また、遅延超過リストが、識別値範囲のエントリ毎に登録時刻を更に含むことによって、一定時間を経過したエントリを削除することもできる。この場合、送信元ピアノードは、定期的に要求メッセージを送信し、登録時刻を更新する必要がある。
【００５９】
図８は、本発明におけるピアノードの機能構成図である。
【００６０】
ピアノード１は、物理ネットワーク上に仮想的に構成されたオーバレイネットワークに接続される。図８によれば、ピアノード１は、ルーティングテーブル１０１と、遅延超過リスト１０２と、遅延時間計測部１０３と、送信元要求部１１１と、送信元リスト登録部１１２と、送信元遅延時間判定部１１３と、送信元検索部１１４と、中継側要求転送部１２１と、中継側応答転送部１２２と、中継側遅延超過通知部１２３と、遅延超過リスト要求部１３１と、遅延超過リスト返信部１３２とを有する。これら機能構成部は、ピアノードに搭載されたコンピュータを機能させるプログラムを実行することによって実現される。尚、オーバレイネットワークのプロトコルは、分散ハッシュテーブルを用いた構造化オーバレイのＣｈｏｒｄである。
【００６１】
ルーティングテーブル１０１は、フィンガーテーブルであって、当該ピアノードの識別値から、１ホップで通信可能な識別値を有する次ピアノードを登録する。
【００６２】
遅延超過リスト１０２は、遅延時間が規定時間以上となる識別値範囲を登録する。
【００６３】
遅延時間計測部１０３は、ルーティングテーブル１０１に登録された次ピアノードへ、定期的にKeep-Aliveメッセージを送信することによってＲＴＴ値を計測し、そのＲＴＴ値から遅延時間を算出する。
【００６４】
送信元要求部１１１は、発生したイベントの要求メッセージを、宛先識別値へ向けて、ルーティングテーブル１０１に登録された次ピアノードへ送信する。
【００６５】
送信元リスト登録部１１２は、応答メッセージを受信した際に、ホップした中継ピアノードの間の遅延時間を当該送信元ピアノードから順に加算する。そして、その遅延時間が、規定時間以上となる次ピアノード以降の識別値範囲を、遅延超過リスト１１２に登録する。
【００６６】
送信元遅延時間判定部１１３は、要求メッセージを更に送信する際に、その要求メッセージの宛先識別値が、遅延超過リストに含まれているか否かを判定する。
【００６７】
中継側要求転送部１２１は、受信した要求メッセージを、更に次ピアノードへ転送する。
【００６８】
中継側応答転送部１２２は、要求メッセージに対応する応答メッセージを受信した際に、その応答メッセージを送信した次ピアノードとの間の遅延時間を追記して転送する。
【００６９】
送信元検索部１１４は、宛先識別値を含む遅延検索要求メッセージをルーティングテーブルに登録された次ピアノードへ送信する。これに対し、中継ピアノードで遅延超過が確認された場合、その遅延超過通知メッセージを受信する。
【００７０】
中継側遅延超過通知部１２３は、遅延検索要求メッセージを受信した際に、その検索要求メッセージの宛先識別値が、当該中継ピアノードの遅延超過リストに含まれている場合、遅延超過通知メッセージを返信する。
【００７１】
遅延超過リスト要求部１３１は、次ピアノードへ、識別値空間を含むリスト要求メッセージを送信する。
【００７２】
遅延超過リスト返信部１３２は、当該次ピアノードが保持する遅延超過リストの中で、識別値空間と重複するリスト情報を返信する。また、遅延超過リスト返信部１３２は、遅延超過リストの中で識別値範囲の広いリスト情報を、優先的に返信する。
【００７３】
以上、詳細に説明したように、本発明の呼接続方法、ピアノード及びプログラムによれば、オーバレイネットワークにおける宛先識別値に基づいて、そのピアノードに対する遅延時間が規定時間以内であるか否かを即時に判定することができる。
【００７４】
遅延時間が規定時間以内であるか否かを即時に判定することによって、様々な用途に適用することができる。例えば、事業者システムであるＩＭＳ(IP Multimedia Subsystem)／ＭＭＤ (Multimedia Domain)と、ピアノードで構築したオーバレイネットワークとを連携されることによって、高品質なセッション制御を低コストで実現することができる。ＩＭＳシステム及びオーバレイネットワークの双方に接続したピアノードは、セッション確立時に、オーバレイネットワークを優先的に使用することによって、ＩＭＳシステムへの負荷を削減することができる。しかしながら、ピアノード数が膨大となる場合には、データ検索時の中継端末数も無視できなくなる。特にリアルタイム性を求められるセッション制御では、セッション確立時間が増大するという問題があった。そのため、本発明によって、送信元ピアノードが、オーバレイネットワーク上でのセッション確立処理に要する遅延時間を推定する。その遅延時間が規定時間を超える場合に、ＩＭＳシステムを介したセッションを確立する。これによって、システムとしてのセッション確立時間を保証することが可能となる。
【００７５】
前述した本発明の種々の実施形態において、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【図面の簡単な説明】
【００７６】
【図１】オーバレイネットワークのシステム構成図である。
【図２】Ｃｈｏｒｄを用いた構造化オーバレイの説明図である。
【図３】本発明におけるシーケンス図である。
【図４】図３のＳ３１のステップを表す説明図である。
【図５】図３のＳ３２〜Ｓ３６のステップを表す説明図である。
【図６】遅延検索要求メッセージの転送を表す説明図である。
【図７】リスト要求メッセージの転送を表す説明図である。
【図８】本発明におけるピアノードの機能構成図である。
【符号の説明】
【００７７】
１  ピアノード
１０１  ルーティングテーブル
１０２  遅延超過リスト
１０３  遅延時間計測部
１１１  送信元要求部
１１２  送信元リスト登録部
１１３  送信元遅延時間判定部
１１４  送信元検索部
１２１  中継側要求転送部
１２２  中継側応答転送部
１２３  中継側遅延超過通知部
１３１  遅延超過リスト要求部
１３２  遅延超過リスト返信部
２  送信元端末
３  宛先端末
４  物理ネットワーク
５  オーバレイネットワーク
【図１】
2010087627.tif 000003
【図２】
2010087627.tif 000004
【図３】
2010087627.tif 000005
【図４】
2010087627.tif 000006
【図５】
2010087627.tif 000007
【図６】
2010087627.tif 000008
【図７】
2010087627.tif 000009
【図８】
2010087627.tif 000010