(57)【要約】本発明は、ピアツーピア・オーバーレイ・ネットワーク（Ｎ）内のルーティング経路を決定する方法と、前記方法を実行するためのネットワーク・ノード（２０）およびコンピュータ・プログラム製品に関する。ピアツーピア・オーバーレイ・ネットワーク（Ｎ）は、複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）を備える。前記複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）の第１のノード（２０）が実行される物理ハードウェアが識別される。第１のノード（２０）と同じ物理ハードウェア上で実行される前記複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）のうちの少なくとも１つの第２のノード（１１２、２１１）が識別される。前記少なくとも１つの第２のノード（１１２、２１１）の識別子を指定するデータセットが生成される。前記データセットは、第１のノード（２０）に関連するゼロ経路テーブルとして格納される。前記ルーティング経路を決定するとき、前記データセットがアクセスされ、前記ゼロ経路テーブルに基づく前記第１のノード（２０）と、前記少なくとも１つの第２のノード（１１２、２１１）との間のリンク（ＺＬ１、ＺＬ２）が選択される。
2011525767.tif 000002
【特許請求の範囲】
【請求項１】
複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）を備えるピアツーピア・オーバーレイ・ネットワーク（Ｎ）内のルーティング経路を決定する方法であって、
前記複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）のうちの第１のノード（２０）が実行される物理ハードウェアを識別するステップと、
前記第１のノード（２０）と同じ物理ハードウェア上で実行される前記複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）のうちの少なくとも１つの第２のノード（１１２、２１１）を決定するステップと、
前記少なくとも１つの第２のノード（１１２、２１１）の識別子を指定するデータセットを生成するステップと、
前記データセットを前記第１のノード（２０）に関連するゼロ経路テーブル（ＺＰＴ）として格納するステップと、
前記ルーティング経路を決定するときには、前記データセットにアクセスし、前記ゼロ経路テーブル（ＺＰＴ）に基づいて前記第１のノード（２０）と前記少なくとも１つの第２のノード（１１２と２１１）との間のリンク（ＺＬ１、ＺＬ２）を選択するステップとを備える、方法。
【請求項２】
前記ゼロ経路テーブル（ＺＰＴ）に基づいて前記第１のノード（２０）と前記少なくとも１つの第２のノード（１１２、２１１）との間の前記リンク（ＺＬ１、ＺＬ２）に、前記第１のノード（２０）と、その識別子が前記ゼロ経路テーブル（ＺＰＴ）に含まれていない前記複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）のうちのノード（５０、８７、１７９）との間のリンクよりも小さい経路長を割り当てるステップと、
前記決定されたルーティング経路の最小総経路長をもたらす前記複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）間の１つまたは複数のリンクを選択することによって前記ルーティング経路を決定するステップとをさらに備える、請求項１に記載の方法。
【請求項３】
前記ゼロ経路テーブル（ＺＰＴ）と前記第１のノード（２０）のショートカット・テーブル（ＳＣＴ）を組み合わせて前記第１のノード（２０）の結合ルーティング・テーブル（ＣＲＴ）にするステップをさらに備え、前記ショートカット・テーブル（ＳＣＴ）が、前記ピアツーピア・オーバーレイ・ネットワーク（Ｎ）のトポロジ構造に関して前記第１のノード（２０）がショートカット・リンクを維持する前記複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）のうちの１つまたは複数のノード（５０、８７、１１２、１７９）の識別子を指定し、さらに、
前記ゼロ経路テーブル（ＺＰＴ）内のエントリに対応する前記結合ルーティング・テーブル（ＣＲＴ）内のエントリにプレファレンスを割り当てるステップと、
前記ルーティング経路を決定するときには、前記結合したルーティング・テーブル（ＣＲＴ）にアクセスし、前記第１のノード（２０）と、前記プレファレンスを考慮して前記結合ルーティング・テーブル（ＣＲＴ）内で指定されたノード（５０、８７、１１２、１７９、２１１）との間のリンクを選択するステップとをさらに備える、請求項１に記載の方法。
【請求項４】
それぞれ前記第１のノード（２０）および／または前記少なくとも１つの第２のノード（１１２、２１１）のプラットフォームから情報を取り出すことによって、前記第１のノード（２０）が実行される前記物理ハードウェアを識別し、および／または前記少なくとも１つの第２のノード（１１２、２１１）を決定するステップをさらに備える、請求項１に記載の方法。
【請求項５】
それぞれ前記第１のノード（２０）および／または前記少なくとも１つの第２のノード（１１２、２１１）のプラットフォームから取り出された前記情報が、それぞれ前記第１のノード（２０）および／または前記少なくとも１つの第２のノード（１１２、２１１）が実行される前記物理ハードウェアに関連するデータである、中央制御装置の識別子、ＭＡＣアドレス、ＩＰアドレス、位置のうちの少なくとも１つを備える、請求項４に記載の方法。
【請求項６】
それぞれ前記第１のノード（２０）および／または前記少なくとも１つの第２のノード（１１２、２１１）にリンクされた外部管理ユニットから情報を取り出すことによって、前記第１のノード（２０）が実行される前記物理ハードウェアを識別し、前記少なくとも１つの第２のノード（１１２、２１１）を決定するステップをさらに備える、請求項１に記載の方法。
【請求項７】
前記ピアツーピア・ネットワーク（Ｎ）のネットワーク・オペレータ、および／または、それぞれ前記第１のノード（２０）のユーザおよび／または前記少なくとも１つの第２のノード（１１２、２１１）のユーザから対応する情報を取り出すことによって、前記第１のノード（２０）が実行される前記物理ハードウェアを識別し、前記少なくとも１つの第２のノード（１１２、２１１）を決定するステップをさらに備える、請求項１に記載の方法。
【請求項８】
前記ピアツーピア・オーバーレイ・ネットワーク（Ｎ）のアプリケーション層上の待ち時間測定によって、前記第１のノード（２０）が実行される前記物理ハードウェアを識別し、前記少なくとも１つの第２のノード（１１２、２１１）を決定するステップをさらに備える、請求項１に記載の方法。
【請求項９】
複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）を備えるピアツーピア・オーバーレイ・ネットワーク（Ｎ）の第１のノード（２０）であって、前記第１のノード（２０）が、前記第１のノード（２０）が実行される物理ハードウェアを識別し、前記第１のノード（２０）と同じ物理ハードウェア上で実行される前記複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）のうちの少なくとも１つの第２のノード（１１２、２１１）を決定し、前記少なくとも１つの第２のノード（１１２、２１１）の識別子を指定するデータセットを生成し、前記データセットを前記第１のノード（２０）に関連するゼロ経路テーブル（ＺＰＴ）として格納することを開始し、前記ルーティング経路を決定するとき、前記データセットにアクセスし、前記ゼロ経路テーブル（ＺＰＴ）に基づいて前記第１のノード（２０）と前記少なくとも１つの第２のノード（１１２、２１１）との間のリンクを選択するように適応された制御ユニットを備える第１のノード（２０）。
【請求項１０】
複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）を備えるピアツーピア・ネットワーク（Ｎ）内のルーティング経路を決定するためのコンピュータ・プログラム製品であって、前記複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）のうちのノードによって実行されるとき、
前記複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）のうちの第１のノード（２０）が実行される物理ハードウェアを識別するステップと、
前記第１のノード（２０）と同じ物理ハードウェア上で実行される前記複数のノード（０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０）のうちの少なくとも１つの第２のノード（１１２、２１１）を決定するステップと、
前記少なくとも１つの第２のノード（１１２、２１１）の識別子を指定するデータセットを生成するステップと、
前記データセットを前記第１のノード（２０）に関連するゼロ経路テーブル（ＺＰＴ）として格納するステップと、
前記ルーティング経路を決定するとき、前記データセットにアクセスし、前記ゼロ経路テーブル（ＺＰＴ）に基づいて前記第１のノード（２０）と前記少なくとも１つの第２のノード（１１２、２１１）との間のリンクを選択するステップとを実施する、コンピュータ・プログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ピアツーピア・オーバーレイ・ネットワーク内のルーティング経路を決定する方法、ならびに前記方法を実行するためのネットワーク・ノードおよびコンピュータ・プログラム製品に関する。
【背景技術】
【０００２】
ピアツーピア（Ｐ２Ｐ：ｐｅｅｒ−ｔｏ−ｐｅｅｒ）オーバーレイ・ネットワークは、ＶｏＩＰ（Ｖｏｉｃｅ  ｏｖｅｒ  Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ：ボイス・オーバー・インターネット・プロトコル）（たとえばＳｋｙｐｅ）やファイル共有（たとえばｅＭｕｌｅ）など、複数の幅広いアプリケーションに使用される。高いスケーラビリティ、自己構成およびフォルト・トレランスなどの特徴が、集合的に提供され使用されるリソースへの分散型のアーキテクチャおよびデータ・ストレージによって達成される。Ｐ２Ｐネットワークは、ピアとして、すなわちネットワークのクライアントとサーバの両方として働くノードからなる。以下の説明では、用語「ノード」と「ピア」は、区別なく用いられる。ネットワークの各ノードは、他のノードへの１つまたは複数の論理的なリンクを維持し、これらの論理的リンクは、オーバーレイ・アルゴリズムに関して確立され、メッセージ送信のために使用される。
【０００３】
最先端技術のＰ２Ｐネットワークは、基礎となるネットワーク基盤にとらわれないオーバーレイ特有のアルゴリズムに基づいて論理的なトポロジ構造を構築する。それぞれのノードは、他のノードへの１つまたは複数のリンクを維持し、これらのリンクは、ブロードキャスト式（非構造化オーバーレイ、たとえばＧｎｕｔｅｌｌａ）で、またはＩＤ（ｉｄｅｎｔｉｆｉｃａｔｉｏｎ／ｉｄｅｎｔｉｆｉｅｒ：識別／識別子）ベースの手法（分散ハッシュテーブル（ＤＨＴ：Ｄｉｓｔｒｉｂｕｔｅｄ  Ｈａｓｈ  Ｔａｂｌｅ）を使用した構造化オーバーレイ、たとえばＣｈｏｒｄ）でメッセージ・ルーティングを行うのに使用される。一部のシステムは、非構造化ピア・グループを有するハイブリッド・アーキテクチャを使用し、これらのグループは、より大きいトポロジ（たとえばＳｋｙｐｅ）では構造化される。ルーティング・アルゴリズムは、論理オーバーレイ内の中間転送側ピアのホップ・カウントを最小限に抑えるように最適化される。
【０００４】
図１ａは、複数のノード０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０を備える従来技術の構造化Ｐ２Ｐオーバーレイ・ネットワークＮを示している。具体的には、図１ａは、ＣｈｏｒｄリングＮを示している。ＣｈｏｒｄリングＮ内のルーティングは、ノード２０が複数の隣接ノード０、５０、８７、１１２、１７９に対して維持するリンクＰＬ、ＳＬ、ＳＣ１、ＳＣ２、ＳＣ３、ＳＣ４に基づく。これらのリンクは、宛先ピアに向けてメッセージをホップ・バイ・ホップで転送するために使用される。ソースと宛先ピアとの間に直接の接続は必要ない。Ｃｈｏｒｄでは、諸ノードは、その前ノードおよび後ノードへの直接接続を維持し、それによってリング・トポロジがもたらされる。たとえば図１ａに示されたＣｈｏｒｄリングＮで、ノード２０は、その前ノード０への直接接続ＰＬおよびその後ノード５０への直接接続ＳＬを維持している。さらに、諸ノードは、メッセージ・ルーティングのために使用される追加のショートカットを含むフィンガー・テーブルを維持し、ＩＤ空間内で２のべき乗距離でそのピアに続くノードからなる。たとえば、図１ａに示されたＣｈｏｒｄリングＮでは、ノード２０は、ノード５０、８７、１１２、１７９へのショートカット・リンクＳＣ１、ＳＣ２、ＳＣ３、ＳＣ４を維持する。図１ｂは、ノード２０に関連するフィンガー・テーブルＦＴを示しており、このテーブルには、ノード２０がショートカット・リンクを維持するノードがリストされている。フィンガー・テーブルＦＴを維持することによって、Ｃｈｏｒｄアーキテクチャを有するネットワーク内のノードは、ｎをネットワーク内のノード数として、ｌｏｇ  ｎのオーダ、すなわちＯ（ｌｏｇ  ｎ）の最大ホップ・カウント数を達成する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、ピアツーピア・オーバーレイ・ネットワーク内のルーティング経路を決定する改良型の方法を提供することである。さらに、本発明の目的は、この改良型の方法を実行するための対応するネットワーク・ノードおよび対応するコンピュータ・プログラム製品を提供することである。
【課題を解決するための手段】
【０００６】
本発明の目的は、複数のノードを備えるピアツーピア・オーバーレイ・ネットワーク内のルーティング経路を決定する方法によって達成され、この方法は、前記複数のノードのうちの第１のノードが実行される物理ハードウェアを識別するステップと、第１のノードと同じ物理ハードウェア上で実行される前記複数のノードのうちの少なくとも１つの第２のノードを決定するステップと、前記少なくとも１つの第２のノードの識別子を指定するデータセットを生成するステップと、前記データセットを第１のノードに関連するゼロ経路テーブルとして格納するステップと、前記ルーティング経路を決定するとき、前記ゼロ経路テーブルに基づいて、前記データセットにアクセスし、前記第１のノードと前記少なくとも１つの第２のノードとの間のリンクを選択するステップとを備える。さらに、本発明の目的は、複数のノードを備えるピアツーピア・オーバーレイ・ネットワークの第１のノードによって達成され、第１のノードが、第１のノードが実行される物理ハードウェアを識別し、第１のノードと同じ物理ハードウェア上で実行される前記複数のノードのうちの少なくとも１つの第２のノードを決定し、前記少なくとも１つの第２のノードの識別子を指定するデータセットを生成し、前記データセットを第１のノードに関連するゼロ経路テーブルとして格納することを開始し、前記ルーティング経路を決定するとき、前記ゼロ経路テーブルに基づいて、前記データセットにアクセスし、前記第１のノードと前記少なくとも１つの第２のノードとの間のリンクを選択するように適応された制御ユニットを備える。また本発明の目的は、複数のノードを備えるピアツーピア・ネットワーク内のルーティング経路を決定するためのコンピュータ・プログラム製品によって達成され、コンピュータ・プログラム製品が、前記複数のノードのうちのノードによって実行されるとき、前記複数のノードのうちの第１のノードが実行される物理ハードウェアを識別するステップと、第１のノードと同じ物理ハードウェア上で実行される前記複数のノードのうちの少なくとも１つの第２のノードを決定するステップと、前記少なくとも１つの第２のノードの識別子を指定するデータセットを生成するステップと、前記データセットを第１のノードに関連するゼロ経路テーブルとして格納するステップと、前記ルーティング経路を決定するとき、前記ゼロ経路テーブルに基づいて、前記データセットにアクセスし、前記第１のノードと前記少なくとも１つの第２のノードとの間のリンクを選択するステップとを実施する。
【０００７】
本発明は、オーバーレイ・トポロジの詳細に基づくルーティング・アルゴリズムを取り入れるが、同時に、Ｐ２Ｐオーバーレイ・ネットワークの基礎となる物理ハードウェアについて考慮する。本発明は、ネットワークのノードがＰ２Ｐシステムの複製アルゴリズム内で実行されている物理ハードウェアに関する情報を含むネットワーク・ノード（＝論理ピア）について述べる。
【０００８】
（たとえば、オペレーティング・システム、たとえばＸＥＮ、ＶＭｗａｒｅの仮想化によって）同じ物理マシンに置かれたノードがこれを認識しない従来技術とは異なり、本発明は、ネットワーク・ノードのうちの１つまたは複数が実行されている物理ハードウェアを識別し、ルーティング経路の決定のために物理ハードウェアに関するこの情報を考慮するルーティング・システムを提示する。
【０００９】
本発明は、同じマシン上でホストされたノード間のゼロ経路リンクをオーバーレイ・ルーティング層に取り入れる。したがって、本発明は、同じ物理ハードウェア（たとえば物理マシン、パーソナル・コンピュータ）上にあるが、それぞれ異なるＩＰ（インターネット・プロトコル）アドレスを有する２つの異なる仮想マシン内でホストされた２つのノードが、いくつかの外部ピアを介して中継され転送される可能性が最も高いメッセージをオーバーレイを介して交換するという事実によって、従来技術のシステム内で引き起こされる、システムへの不必要に大きいネットワーク・トラフィックおよびメッセージ待ち時間を回避する。
【００１０】
ルーティング・アルゴリズムがオーバーレイの詳細に基づく現在のＰ２Ｐオーバーレイとは対照的に、本発明は、Ｐ２Ｐネットワークのオーバーレイ・トポロジ作成およびルーティング最適化のための分散型の物理ハードウェア基盤の上で仮想化ソリューションについて考慮する解決策を提供する。
【００１１】
従来技術、たとえば最先端技術のＣｈｏｒｄトポロジでは、フィンガー・テーブルは、オーバーレイ内のノードのＩＤに依存して構築される。これらのＩＤは、ランダムに生成され、物理ネットワーク・トポロジを表すものではない。それぞれ異なる仮想ＩＰアドレスを有する仮想化プラットフォームの上でピアが実行されている場合にはノードＩＤの構成にピアのＩＰアドレスを使用することが機能しないので、同じ物理マシン上でホストされるノード間のメッセージは、宛先に達する前にいくつかの中間ピアを介してネットワーク上で転送される可能性が高い。本発明は、Ｐ２Ｐオーバーレイ・ネットワーク内に存在する物理ハードウェアを考慮に入れることによって従来技術のこの問題を回避する。
【００１２】
本発明は、ネットワーク・インターフェースおよびネットワーキング・スタックの負荷を減少させ、クラスタ相互接続の帯域幅使用を減少させ、メッセージング待ち時間の減少によってシステム速度を向上させるのに役立つ。
【００１３】
さらに、本発明は、サーバ・クラスタや純粋なＰ２Ｐ電話通信など、分散環境で有益に使用できる基本技術への改良について述べる。具体的には、この種類の技術は、ＩＥＴＦ（Ｉｎｔｅｒｎｅｔ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｔａｓｋ  Ｆｏｒｃｅ：インターネット技術特別調査委員会）Ｐ２Ｐ−ＳＩＰ（Ｓｅｓｓｉｏｎ  Ｉｎｉｔｉａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ：セッション開始プロトコル）に含まれ得る。
【００１４】
さらなる利点は、従属クレームによって示された本発明の実施形態によって達成される。
【００１５】
本発明の好ましい一実施形態によれば、前記ゼロ経路テーブルに基づいて、前記第１のノードと、前記ゼロ経路テーブル内にその識別子が含まれていない複数のノードのうちのノードとの間のリンクよりも小さい経路長が、前記第１のノードと前記少なくとも１つの第２のノードとの間のリンクに割り当てられる。好ましくは、前記割当ては、第１のノードによって行われる。発信元ノードから宛先ノードへの前記ルーティング経路の決定では、ルーティング経路は、ルーティング経路を構成する前記複数のノード間の１つまたは複数のリンクが、決定されたルーティング経路の最小の総経路長をもたらすように選択される。好ましくは、前記選択は、第１のノードによって実施される。
【００１６】
本発明の別の好ましい実施形態によれば、前記ゼロ経路テーブルと前記第１のノードのショートカット・テーブルは組み合わされて、第１のノードの結合ルーティング・テーブルとなる。好ましくは、前記組合せは、第１のノードによって実施される。前記ショートカット・テーブルは、ピアツーピア・オーバーレイ・ネットワークのトポロジ構造に関して前記第１のノードがショートカット・リンクを維持する前記複数のノードのうちの１つまたは複数のノードの識別子を指定する。たとえば、ピアツーピア・オーバーレイ・ネットワークのトポロジ構造は、Ｐ２Ｐオーバーレイ・ネットワークのノードに割り当てられたＩＰアドレスを含むＩＰアドレス空間である。ゼロ経路テーブル内のエントリに対応する、結合ルーティング・テーブル内のエントリが、プレファレンス、たとえばプレファレンスを表すフラグやマーキングに割り当てられる。好ましくは、前記割当ては、第１のノードによって実施される。発信元ノードから宛先ノードへの前記ルーティング経路の決定では、前記結合ルーティング・テーブルがアクセスされ、前記第１のノードと、前記結合ルーティング・テーブル内に指定されたノードとの間のリンクが、前記プレファレンスを考慮して選択される。好ましくは、前記アクセスおよび選択は、第１のノードによって実施される。
【００１７】
第１のノードがそれ自体のハードウェア、およびネットワークの他のノードのハードウェアに関する情報を検出することが可能である。この検出の目標は、複数のネットワーク・ノードのうちのどのノードが同じ物理ハードウェア上で実行されているか見つけ出すことである。同じ物理ハードウェア上で実行されるが、それぞれ異なるＩＰアドレスを有するノード間のリンクは、「ゼロ経路リンク」と呼ばれる。物理ハードウェアを検出するためのいくつかの可能な手法がある。
【００１８】
本発明の好ましい実施形態によれば、第１のノードが実行される前記物理ハードウェアは、第１のノードのプラットフォームから情報を取り戻すことにより決定される。好ましくは、前記取出しは、第１のノードによって実施される。第１のノードが実行される前記物理ハードウェアの決定に加えて、またはその代わりに、第１のノードと同じ物理ハードウェア上で実行される前記少なくとも１つの第２のノードが、少なくとも１つの第２のノードのプラットフォームから情報を取り出すことによって決定される。好ましくは、前記取出しは、第１のノードによって実施される。プラットフォームは、第１のノードおよび／または少なくとも１つの第２のノードが実行される物理ハードウェア、たとえばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ：中央処理装置）、コンピュータ、ネットワーク・ユニットなどであってよい。情報は、第１のノードおよび／または少なくとも１つの第２のノードのプラットフォームに関連する、たとえばＣＰＵ  ＩＤ、ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ：メディア・アクセス制御）アドレス、位置、ＩＰアドレス、位置などであってよい。これは、ネットワーク・ノードのオペレーティング・システム（複数可）の助けを得てソフトウェア・アプリケーションが見つけ出すことができるどんな情報をも含む。たとえば、ＭＡＣアドレスは通常、物理ホストを決定する相対的に安全な手法であるが、しかし、ハードウェア仮想化技術が使用される場合にはこれはそうでないことがある。
【００１９】
本発明の別の好ましい実施形態によれば、第１のノードが実行される前記物理ハードウェアは、第１のノードにリンクされ、またはそれに関連する外部管理ユニットから情報を取り出すことによって決定される。好ましくは、前記取出しは、第１のノードによって実施される。第１のノードが実行される前記物理ハードウェアの決定に加えて、またはその代わりに、第１のノードと同じ物理ハードウェア上で実行される前記少なくとも１つの第２のノードが、第２のノードにリンクされた、またはそれに関連する外部管理ユニットから情報を取り出すことによって決定される。好ましくは、前記取出しは、第１のノードによって実施される。外部管理ユニットは、外部クラスタ管理エンティティとすることもでき、用語「クラスタ」は、ネットワーク・ノードのクラスタとしてＰ２Ｐオーバーレイ・ネットワークに言及する。
【００２０】
外部クラスタ管理エンティティは、たとえばノードＩＤの構成に使用可能である場合、クラスタの物理トポロジに関する情報を提供することもできる。外部クラスタ管理エンティティは、中央登録サーバ、ブートストラップ・サーバ、またはネットワーク管理および監視サーバであってよい。
【００２１】
ソフトウェア・アプリケーションが必要なハードウェア情報を検出できない場合、ノードの管理者によってノードを手動で（事前）構成することが一解決策である。好ましくは、第１のノードが実行される前記物理ハードウェアは、対応する情報をピアツーピア・ネットワークのネットワーク・オペレータから、かつ／または第１のノードのユーザから取り出すことによって決定される。好ましくは、前記取出しは、第１のノードによって実施される。第１のノードが実行される前記物理ハードウェアの決定に加えて、またはその代わりに、第１のノードと同じ物理ハードウェア上で実行される前記少なくとも１つの第２のノードが、対応する情報をピアツーピア・ネットワークのネットワーク・オペレータから、かつ／または少なくとも１つの第２のノードのユーザから取り出すことによって決定される。好ましくは、前記取出しは、第１のノードによって実施される。
【００２２】
好ましい実施形態では、第１のノードが実行される前記物理ハードウェアは、第１のノードに関連するアプリケーション層上の測定によって決定される。好ましくは、前記決定は、第１のノードによって実施される。第１のノードが実行される前記物理ハードウェアの決定に加えて、またはその代わりに、第１のノードと同じ物理ハードウェア上で実行される前記少なくとも１つの第２のノードが、第２のノードに関連するアプリケーション層上の測定によって決定される。好ましくは、前記決定は、第１のノードによって実施される。
【００２３】
アプリケーション層上の前記測定は、「ｐｉｎｇ」メッセージ交換など、アプリケーション・レベルのプローブ機構であってよい。前記ｐｉｎｇメッセージ交換に基づいて、ノードは、他のノードが同じ装置上でホストされているかどうかを接続待ち時間から推定することができる。さらに、他の既に知られている方法を使用して、ノードが同じハードウェア上にあるかどうか推定することもできる。たとえば、ネットワーク調整システムは、すべてのリンクの明示的な測定を必要とせずに、ノード間待ち時間を測定することによって、基礎となるネットワークに関する知識を得ようと試みる。これによって、物理トポロジ内でノードが互いに近くにある場合には論理オーバーレイ内でそれらを互いに近くに置くことが可能となる。別の例は、他のノードへの待ち時間を測定することによって、局所性に合わせてそのルーティング・テーブルを連続的に調整するＰａｓｔｒｙである。
【００２４】
本発明の別の好ましい実施形態によれば、前記ゼロ経路テーブル（いわゆる「ゼロ経路リンク」）に基づく前記第１のノードと前記少なくとも１つの第２のノードとの間のリンクが、好ましくはルーティング・アルゴリズムによって、前記第１ノードからの次のホップとして選ばれる。
【００２５】
本発明のこれらのおよびさらなる特徴および利点は、添付の図面と併せ読まれる現在の好ましい例示的な実施形態についての以下の詳細な説明を読むことによってよりよく理解される。
【図面の簡単な説明】
【００２６】
【図１ａ】複数のノードを備える従来技術の構造化Ｐ２Ｐオーバーレイ・ネットワークを示す図である。
【図１ｂ】従来技術の、ノードに関連するフィンガー・テーブルＦＴを示す図である。
【図２】本発明の一実施形態によるＰ２Ｐオーバーレイ・ネットワークを示す図である。
【図３ａ】図２に示されたＰ２Ｐオーバーレイ・ネットワーク内のゼロ経路リンクを示す図である。
【図３ｂ】図２に示されたＰ２Ｐオーバーレイ・ネットワーク内のノードに関連するゼロ経路テーブルを示す図である。
【図４ａ】図２に示されたＰ２Ｐオーバーレイ・ネットワーク内のノードに関連する結合ルーティング・テーブルによるリンクを示す図である。
【図４ｂ】本発明の一実施形態による結合ルーティング・テーブルを示す図である。
【発明を実施するための形態】
【００２７】
図２は、本発明の一実施形態によるＰ２Ｐオーバーレイ・ネットワークを示している。具体的には、図２は、本発明の一実施形態によるＣｈｏｒｄリングＮを示している。ＣｈｏｒｄリングＮは、複数のノード０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０を備え、ただし、参照符号０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０は、ノード０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０のノードＩＤを表すためのものでもある。ノードのノードＩＤは、オーバーレイ特有のＤＨＴアルゴリズムによって割り当てられており、たとえば登録サーバに基づいてもよいし、ノード自体によってランダムに選択されてもよい。それぞれのノードは、ＣｈｏｒｄリングＮのピアを表す。
【００２８】
この方法の第１のステップで、第１のノード２０は、それがどの物理ハードウェア上で実行されているか決定する。また第１のノード２０は、ＣｈｏｒｄリングＮのうちのどの物理ハードウェア上で他のノード０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０が実行されているか決定する。
【００２９】
第１のノード２０は、相互リンクされた１つまたは複数のコンピュータ、すなわちハードウェア・プラットフォームと、ハードウェア・プラットフォームに基づくソフトウェア・プラットフォームと、ソフトウェアおよびハードウェア・プラットフォームによって形成されたシステム・プラットフォームによって実行された複数のアプリケーション・プログラムとからなる。第１のノード２０の機能性は、これらのアプリケーション・プログラムを実行することによって提供される。アプリケーション・プログラムまたはこれらのアプリケーション・プログラムの選択された部分は、システム・プラットフォーム上で実行されるとき、下記に述べられるルーティング・サービスを提供するコンピュータ・ソフトウェア製品を構成する。さらに、こうしたコンピュータ・ソフトウェア製品は、これらのアプリケーション・プログラムまたはアプリケーション・プログラムの前記選択された部分を格納する記憶媒体によって構成される。
【００３０】
機能的視点から、第１のノード２０は、第１のノードの機能を制御するための制御ユニットと、データを格納するための記憶媒体と、他のノードと情報を交換するためのインターフェースとを備える。
【００３１】
物理ハードウェアの決定では、第１のノード２０は、それが実行されている物理ハードウェアを識別するのに役立つ任意の使用可能な情報を使用してよい。第１のノード２０がそれ自体のプラットフォーム、たとえばＣＰＵ  ＩＤ、ＭＡＣアドレス、位置、ＩＰアドレスなどから情報を収集することによって、それが実行されている物理ハードウェアに関する情報を取り出すことが可能である。次いで、第１のノード２０は、ＣｈｏｒｄリングＮの他のノード０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０から対応する情報を収集し、収集された情報を比較することができる。たとえば、第１のノード２０が実行されているコンピュータのＣＰＵ  ＩＤが、ノード１１２が実行されているコンピュータのＣＰＵ  ＩＤと等しい場合、第１のノード２０は、第１のノード２０が実行されている物理ハードウェアが、ノード１１２が実行されている物理ハードウェアと同一であるという結果に達する。
【００３２】
それ自体のプラットフォーム（たとえばＣＰＵ  ＩＤ、ＭＡＣアドレス、位置、ＩＰ、・・・）から得られる情報に加えて、第１のノード２０は、外部管理エンティティから取り出される情報、第１のノード２０が実行されているハードウェアのユーザによって実施された手動構成によって提供される情報、アプリケーション層の測定によって収集される情報などを使用することができる。同様に、他のノード０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０はそれぞれ、それが実行されている物理ハードウェアを識別するのに役立つ任意の使用可能な情報を使用することができる。他のノード０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０がそれぞれ、各々の物理ハードウェアに関する収集された情報を第１のノード２０に伝達することが可能である。第１のノード２０が、他のノード０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０が実行されている物理ハードウェアにアクセスし、他のノード０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０からその各々の物理なハードウェアに関する情報を収集するということも可能である。
【００３３】
物理ハードウェアを分類するこのステップの結果が図２に示されており、この図２は、ハードウェア分類を示しており、ノード０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０についてそれぞれ異なるアイコン形状でこれを示している。それぞれの形状は、別の物理マシンを表す。それは、ノード０、５０、１４０、２００および２２３が第１のマシン上で実行されることを意味する。ノード２０、１１２および２１１は、第２のマシン上で実行される。ノード８７、１７９および２４０は、第３のマシン上で実行される。
【００３４】
分類手順の後、ノード２０は、同じマシン上でホストされる第２のノード１１２および２１１へのゼロ経路リンク・テーブルを維持する。好ましくは、ＣｈｏｒｄリングＮの各ノード０、２０、５０、８７、１１２、１４０、１７９、２００、２１１、２２３、２４０は、各々のノードと同じマシン上でホストされるノードへの各々のゼロ経路リンク・テーブルを維持する。
【００３５】
図３ａは、第１のノード２０と、第１のノード２０と同じ物理ハードウェア上で実行される第２のノード１１２、２１１との間のゼロ経路リンクＺＬ１、ＺＬ２を示している。ゼロ経路リンクＺＬ１、ＺＬ２を介して送信されるメッセージは、ネットワークＮ上で送信される必要はないが、単一の物理ハードウェアで使用可能な接続を介して交換される。したがって、ゼロ経路リンクＺＬ１、ＬＺ２経由で送信されるメッセージは、ネットワークＮの基盤に負担をかけず、最小の待ち時間で送信することができる。
【００３６】
識別子、すなわちノード１１２、２１１のノードＩＤ  １１２、２１１は、ノード２０によって、図３ｂに示されたゼロ経路テーブルＺＰＴ内に維持される。ノード２０が、ゼロ経路テーブルＺＰＴをノード２０の記憶装置、たとえばＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ：ランダム・アクセスメモリ）に格納することが可能である。
【００３７】
第１のノード２０は、図４ｂに示されたように、フィンガー・テーブルＦＴとゼロ経路テーブルＺＰＴを統合して、結合ルーティング・テーブルＣＲＴにする。フィンガー・テーブルＦＴとゼロ経路テーブルＺＰＴを統合して結合ルーティング・テーブルＣＲＴにすることによって、第１のノード２０は、ゼロ経路リンクＺＬ１、ＺＬ２を利用することができる。第１のノード２０は、ゼロ経路リンクＺＬ１、ＺＬ２にプレファレンスを割り当てる。プレファレンスは、ショートカット・リンクＳＣ１〜ＳＣ４に関連する量よりも有利な量をゼロ経路リンクＺＬ１、ＺＬ２に関連付けることによって割り当てることができる。
【００３８】
たとえば、ゼロ経路リンクＺＬ１、ＺＬ２には、０に等しい経路長、すなわち１に等しい経路長に割り当てられ得るショートカット・リンクＳＣ１〜ＳＣ４よりも小さい経路長が割り当てられる。ルーティング経路を決定するとき、第１のノード２０は、ソース・ノードから宛先ノードに到達する使用可能なルーティング代替案の総経路長を計算する。ルーティング経路の総経路長は、ルーティング経路を共に形成する経路部分の経路長の和として計算することができる。次いで、第１のノード２０は、最小の総経路長を有するルーティング経路を選択する。ゼロ経路リンクＺＬ１、ＺＬ２には、０に等しい経路長が割り当てられるので、ゼロ経路リンクＺＬ１、ＺＬ２のうちの１つを介したルーティング経路が、ショートカット・リンクＳＣ１〜ＳＣ４のうちの１つを介したルーティング経路よりも多分選ばれる。
【００３９】
第１のノード２０がゼロ経路リンクＺＬ１、ＺＬ２にゼロのホップ数、すなわち１ホップが割り当てられるショートカット・リンクＳＣ１〜ＳＣ４よりも小さいホップ数を割り当てることも可能である。ルーティング経路を決定するとき、第１のノード２０は、ソース・ノードから宛先ノードに到達する使用可能なルーティング代替案に必要なホップを計算する。次いで、第１のノード２０は、最小ホップ数を有するルーティング経路を選択する。ゼロ経路リンクＺＬ１、ＺＬ２にゼロ・ホップが割り当てられるので、ショートカット・リンクＳＣ１〜ＳＣ４のうちの１つを介したルーティング経路よりも、ゼロ経路リンクＺＬ１、ＺＬ２のうちの１つを介したルーティング経路が多分選ばれる。
【００４０】
図４ａは、結合ルーティング・テーブルＣＲＴによる、第１のノード２０が使用可能なリンクを示している。ショートカット・リンクＳＣ３は、ゼロ経路リンクＺＬ１と同一である。標準ショートカット・リンクに優る利点によりゼロ経路リンクが好まれるので、このリンクは、結合ルーティング・テーブルＣＲＴ内に、ショートカット・リンクＳＣ２としてではなく、ゼロ経路リンクＺＬ１としてリストされる。
【００４１】
ＤＨＴルーティング・アルゴリズムは、オーバーレイ・ホップ・カウントに関して最適化される。ネットワーク・メトリクス（たとえば遅延、ＩＰホップ・カウント、・・・）は、ルーティング・アルゴリズムによって指定された次のホップに影響を及ぼさない。これは、それぞれのピアが、その隣接ピア（次のホップ）へのリンクに関する知識だけを有しており、メッセージの総経路についての知識をもたないという事実による。ネットワーク・メトリクスに関する次ホップの選択では、総経路に関する性能の向上は保証されない。
【００４２】
しかし、周期的なリンク・プローブおよびルーティング・テーブルの更新によってネットワーク局所性に関して隣接ピアを選択する、ＰａｓｔｒｙのようなＤＨＴアルゴズムがある。ここでは、本発明によって提供されるようなゼロ経路リンクに関する知識が、それらが特定のＩＤ空間への最適なリンクであるので含まれてよい。特定のＩＤ空間へのゼロ経路リンクが見つかる場合、プローブおよび更新は不必要になる。
【００４３】
ルーティング・アルゴリズムが経路長やホップ・カウントのようなメトリクスではなく、オーバーレイ特有のＩＤだけを解釈するＰ２Ｐアルゴリズムでは、ゼロ経路リンクがルーティング・アルゴリズムによって結合ルーティング・テーブルを介して次のホップとして選択される場合には最先端技術Ｐ２Ｐアルゴリズムと比べてネットワーク・トラフィックが減少し、メッセージ待ち時間が向上するので、ゼロ経路リンクは依然として有効である。
【００４４】
本発明による参加アルゴリズムは、ゼロ経路リンクの一貫性を保証するために最先端技術の手法に関して修正される。本発明による参加アルゴリズムの説明では、ピアがどのハードウェア上で実行されているかそれが決定する手順は、上述されたように既に完了していると仮定する。したがって、参加するピアは、どのピアが同じ物理ハードウェア上に位置するか知っている。したがって、参加プロセスの間、それは、同じ物理ハードウェア上に位置するピアに向かって直接のゼロ経路リンクを確立する。さらに、それは、これらのピアに、新しく確立されたリンクがゼロ経路リンクであるが、ショートカット・リンクではないことを通知する。したがって、参加プロセスが終了した後、すべてのピアは、最新のゼロ経路テーブルを維持する。
【図１ａ】
2011525767.tif 000003
【図１ｂ】
2011525767.tif 000004
【図２】
2011525767.tif 000005
【図３ａ】
2011525767.tif 000006
【図３ｂ】
2011525767.tif 000007
【図４ａ】
2011525767.tif 000008
【図４ｂ】
2011525767.tif 000009
【国際調査報告】
2011525767.tif 000010
2011525767.tif 000011
2011525767.tif 000012