(57)【特許請求の範囲】
【請求項１】
ネットワークにわたって分散されているある数のホストを有する大規模ネットワークのためのネットワーク性能測定システムであって、近接の複数のホストから自己組織化された複数の測定グループを有し、各測定グループがグループリーダを含み、各グループリーダが第1のマルチキャストグループに結合して、測定グループ間のグループ間ネットワーク性能情報を共有し、各グループリーダがその測定グループ内の第2のマルチキャストグループをさらに形成して、その測定グループ内のグループ内ネットワーク性能情報を共有することを特徴とするネットワーク性能測定システム。
【請求項２】
各前記ホストが、そのそれぞれの測定グループ内で、リモートホストに対して有するネットワーク性能情報を共有し、各前記測定グループ内のホストが、アクティブに前記ネットワーク性能を測定することなく、前記そのそれぞれの測定グループ内で共有される前記ネットワーク性能情報を利用して、前記リモートホストに対するネットワーク性能を推定することを特徴とする請求項1に記載のネットワーク性能測定システム。
【請求項３】
前記測定グループ内の1つのホストが、パケットを第2のマルチキャストグループにマルチキャストすることによりグループ内性能測定を起動し、前記グループ内の各ホストが、前記パケットに対する応答を前記第2のマルチキャストグループにマルチキャストすることによって応答し、その後、前記1つのホストが、その測定グループ内の自分自身と他のすべてのホスト間のラウンドトリップ時間(RTT)性能を測定することを特徴とする請求項1に記載のネットワーク性能測定システム。
【請求項４】
前記測定グループ内のホストが、前記第2のマルチキャストグループからの、前記1つのホストから受け取ったパケットおよび各ホストから受け取った前記応答に関係する情報を、さらにマルチキャストし、前記ホストが、その後、それらの測定グループ内のいずれかの2つのホスト間の前記RTT性能を計算することを特徴とする請求項3に記載のネットワーク性能測定システム。
【請求項５】
各前記グループリーダが、リモートホストに対して有するネットワーク性能情報を、近接の測定グループのグループリーダと共有し、各測定グループ内のホストが、近接の測定グループから共有される前記ネットワーク性能情報を利用して、このようなネットワーク性能情報がそのホストの測定グループ内の別のホストから入手可能でない場合に、前記ネットワーク性能をアクティブに測定することなく、前記リモートホストに対するネットワーク性能を推定することを特徴とする請求項1に記載のネットワーク性能測定システム。
【請求項６】
前記このようなネットワーク性能情報が前記測定グループ内からおよび前記近接の測定グループから共有されない場合に、前記ホストが、リモートホストに対する前記ネットワーク性能をアクティブに測定することを特徴とする請求項5に記載のネットワーク性能測定システム。
【請求項７】
前記ホストが、パケットトレーンをリモートホストに送り、それに対する前記ネットワーク性能を判断し、前記パケットトレーンが、2つの小さいSYNパケット、それに続き2つの大きいSYNパケット、それに続き2つの小さいSYNパケットを有することを特徴とする請求項1に記載のネットワーク性能測定システム。
【請求項８】
前記リモートホストからRSTパケットの応答パケットトレーンを受け取り、前記ホストが前記RSTパケットが前記SYNパケットに対して再順序付けされている場合に、前記ホストが、前記応答パケットトレーンを捨てることを特徴とする請求項7に記載のネットワーク性能測定システム。
【請求項９】
前記ホストが、前記リモートホストから6つのRSTパケットの応答パケットトレーンを受け取り、第3と第4のRSTパケット間の時間分散が、第1と第2、第5と第6のパケット間の時間分散より短い場合に、前記ホストが、前記応答パケットトレーンを捨てることを特徴とする請求項7に記載のネットワーク性能測定システム。
【請求項１０】
前記ホストが、自分自身とネットワーク性能情報が共有される別のホストの間の距離に基づいて、ネットワーク性能情報を逆に重み付けすることを特徴とする請求項1に記載のネットワーク性能測定システム。
【請求項１１】
前記ホストがネットワークに入ったり去ったりする時、またはネットワーク状態が変化する時に、前記測定グループが、動的に再生することを特徴とする請求項1に記載のネットワーク性能測定システム。
【請求項１２】
動的に再生された前記測定グループのグループリーダが、前記動的に再生された測定グループのほぼ論理中心にいるホストであることを特徴とする請求項11に記載のネットワーク性能測定システム。
【請求項１３】
前記動的に再生された測定グループの前記グループリーダがその現在のグループリーダより前記ホストに接近している場合に、測定グループ内のホストが、その測定グループを去り、前記動的に再生された測定グループに結合することを特徴とする請求項12に記載のネットワーク性能測定システム。
【請求項１４】
前記動的に再生された測定グループの前の、前記測定グループの前記グループリーダが、動的再生後に、前記測定グループ内のすべてのホスト間の距離を計算し、前記グループリーダが、その後、動的再生後に前記測定グループの論理中心にいるホストに、グループリーダの役割を引き受けるよう要求することを特徴とする請求項11に記載のネットワーク性能測定システム。
【請求項１５】
小さい前記測定グループが、近接の測定グループと併合して、共有ネットワーク性能情報を介してネットワーク性能を判断する効率を増加させることを特徴とする請求項1に記載のネットワーク性能測定システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、ネットワーク性能測定システムに関し、より詳細には、たとえば、インターネットなどの大規模ネットワークのための分散型性能測定インフラストラクチャに関する。
【０００２】
【従来の技術】
インターネット上のユーザの数やトラフィック量が増すにつれて、ユーザおよびネットワークサービスプロバイダの両者が共に、所与のインターネット経路の性能および信頼性についての正確かつ共通の理解ができるようになるための、1セットのネットワーク性能メトリクスおよび測定方法が入手可能であることが最も重要なこととなってきた。このような理解すべきもののなかには、所与のインターネット経路のうちのどのセグメントが、その性能および信頼性を制限しているのかについての情報が含まれていなければならない。ユーザの側から見ると、いったん1セットのネットワーク性能メトリクスおよび測定ツールが整備されれば、自身がどのような種類のサービスを受けているのかについての正確な知識を持つことが極めて容易になる。この情報により、ユーザは、さまざまなネットワークサービスプロバイダの相対性能を比較できるようになる。同様に、ネットワーク性能測定からの知識により、ネットワークプロバイダ自身も、ネットワークキャパシティを向上させるためにより強力な交換機をインテリジェントに配備することができるようになる。同じように、コンテンツベースのサービスプロバイダが、この情報を使用して、そのウェブサーバを最適な形で配備し管理することができる。
【０００３】
つまり、この性能情報が、多くのインターネットサービスおよびシステムによって使用されると、ピアツーピアシステムまたはアプリケーションレベルのマルチキャストツリーのための頑強なオーバーレイの生成が可能となり、ユーザによって使用されると、多くのサーバミラー間から1つのサーバの選択が可能となり、サービスプロバイダによって使用されると、サーバのレプリカの配置を判断して、コンテンツ配信ネットワークの性能を向上することができる。しかし、調査団体から、インターネット測定インフラストラクチャを構築するためのプロポーザルが多く出されているにもかかわらず、インターネットの規模と複雑性の両方により、このようなインフラストラクチャを、近い将来に十分に配備し動作可能にするのは困難である。
【０００４】
クライアントからの所与のサービス要求を、いくつかのインターネットサーバの1つによって満たすことができるような状況が、ますます増加してきている。その例は、ウェブサーバへの単一のウェブページのアクセスなどの一時的なインタラクションから、2つのニュース(NNTP)サーバ間の長期的なピアリング関係まで及ぶ。他のすべての条件が同じ場合、このようなすべてのインタラクションでは、低い待ち時間または高い帯域幅を有する、最も近いサーバにアクセスするのが有利である。たとえ他の条件がすべて同じわけではない場合でも、たとえば、異なるウェブサーバが異なる応答時間を有する場合に、選択を行う際の要因として、各候補ホストまでの距離を含めることは、やはり有益である。
【０００５】
ネットワーク性能測定および分析について、いくつかの調査活動が行われてきており、その教示および開示全体を、参照により本明細書に組み込んである。上記教示および開示は、たとえば、非特許文献１〜４を含む。これらのすべての活動の結果、インターネット性能測定インフラストラクチャの確立が、インターネットの最適なオペレーションおよび健全な成長のための究極のソリューションであるとの共通の理解に達した。
【０００６】
【非特許文献１】
P. Francis et al., "An Architecture for a Global Internet Host Distance Estimation Service," Proc. of IEEE INFOCOM 1999. March 1999
【０００７】
【非特許文献２】
Sandra G. Dykes, Clinton L. Jeffery, and Kay A. Robbins. "An Empirical Evaluation of Client Side Server Selection Algorithms," Proc. of IEEE INFOCOM '2000, 2000
【０００８】
【非特許文献３】
James D. Guyton and Michael F. Schwartz," Locating Neaby Copies of Replicated Internet Servers," Proc. of ACM SIGCOMM '95, pp. 288-298, 1995
【０００９】
【非特許文献４】
A. Myers, P. Dinda, and H. Zhang, "Performance Characteristics of Mirror Servers on the Internet", Proc. of IEEE INFOCOM '99, Mar. 1999
【００１０】
【発明が解決しようとする課題】
ネットワーク性能情報を得るための1つの方法が、各起動ホストが、ユニキャストまたはマルチキャストツールを使用して、ネットワーク性能自体を測定することである。しかし、多数のホストが、独立した測定を頻繁にする場合は、このことは、インターネットに厳しい影響を及ぼすことになる。残念なことに、現在のシステムにおいては、1つのホストによってなされた測定は、他のホストが入手できない。その情報を必要とする各ホストが、独立して、それを測定しなければならないため、このようなシステムの測定オーバヘッドが増加する。その結果、インターネットの規模および複雑性の両方により、このような規模の測定インフラストラクチャが、近い将来に配備され、十分に動作可能となる可能性は低い。この問題は、インターネットがなお指数関数的速度で増加し続けている事実によって、さらに、深刻化する。
【００１１】
したがって、当技術分野では、インターネットなどの大規模ネットワークに対して、スケーラブルであるが、大きい測定オーバヘッドによる負担のない、ネットワーク性能分析アーキテクチャが必要とされている。
【００１２】
【課題を解決するための手段】
本発明によるシステムおよび方法は、大規模ネットワークのための新しくて改良された測定インフラストラクチャを提供することである。より詳細には、本発明によるシステムおよび方法は、大規模ネットワークにおける測定オーバヘッドを減少させるために、分散型グループおよび共有性能評価を利用する、新しくて改良された測定インフラストラクチャを提供することである。
【００１３】
より具体的には、本発明による一実施形態が、大規模ネットワークのための、本明細書で、gMeasureと称する、測定インフラストラクチャを提供する。このインフラストラクチャは、ネットワーク内に分散して配備され、測定したネットワーク性能情報を有効に共有する、自己組織化されたプロービンググループ(測定グループまたはMeGroup)に基づいている。本発明によるインフラストラクチャの1つの特徴は、測定している個々のホストから収集されたデータおよびにその隣接のグループによって収集されたデータを最大限活用することにより、それがネットワーク全体の性能を推定/推論することである。ホストが、MeGroupに自己組織化されて、スケーラブルな階層構造を形成する。新規なマルチキャストベースのアルゴリズムが、グループ内およびグループ間の両方の性能測定に採用される。さらに、1セットの発見的アルゴリズムを使用して、グループ組織を最適化し、推定精度を向上させる。隣接間の共有作業により、測定オーバヘッドを非常に低く保ち、大規模ネットワークに対するスケーラビリティを可能にする。
【００１４】
gMeasureインフラストラクチャのいくつかの自己組織化された測定グループ(MeGroup)のそれぞれに、グループリードがある。これらの性能プロービンググループの各グループリードは、そのグループ内およびその隣接のグループ間のデータ配布を担当する。このグループリードは、グループ間性能測定の代表として働くために動的に選ばれる。ホストが、ネットワーク性能をローカル規模でアクティブに測定し、次いで、この測定した情報を同じグループ内の他のホストと共有することにより、ネットワーク性能を得る。グループリードはまた、その隣接である他のMeGroupからのグループリードと、測定した情報を交換する。
【００１５】
一実施形態では、gMeasureインフラストラクチャに、3つの一次機能が含まれている。データ収集機能は、待ち時間や帯域幅などのネットワーク状態を測定する。データ共有機能を使用すると、同じプロービンググループ内の他のホストから得られた測定したネットワーク性能情報と、隣接のグループから得られた性能情報とを共有することに基づいて、ネットワーク状態の予測ができるようになる。最後に、データ配布機能は、測定したネットワーク性能情報を同じグループ内の他のホストおよび隣接するグループと共有する。測定アーキテクチャの一特徴は、それが一部アクティブプロービングに頼っており、データ共有およびデータ予測からのネットワーク性能統計を活用して、最小オーバヘッドでネットワーク性能判断を達成する
本発明による一実施形態では、ネットワーク性能測定サービスを構築し、関係する機能を分散されたアプリケーションに提供するために、gMeasureが、ホストの自己組織化しているプロービンググループに、集約可能識別子を有するグループとネットワーク性能ベースのグループに対して主な焦点をあてるようにする。インフラストラクチャはまた、測定したネットワーク性能のためにプロービンググループ間で選定を実施するためのグループ選択メカニズムを含む。これらのメカニズムはまた、動的グループ再生をサポートする。本発明によるインフラストラクチャによって提供されるデータ配布は、プロービンググループを使用して、測定したデータ分布を最適化する。最後に、本発明によるインフラストラクチャは、データ配布ツールと統合性能モニタツールの上に構築されたキャパシティ監視メカニズムを提供する。このメカニズムは、現在入手可能なネットワーク性能のリアルタイムレポートを提供する。
【００１６】
本発明によるgMeasureインフラストラクチャの実施形態には、以下の設計機能の1つまたは複数が組み込まれている。このような特徴の1つが、インフラストラクチャが分散されていることである。つまり、プロービンググループと測定サービスを、インターネットを経由して多くの場所に配備できる。インフラストラクチャはまた、非集中型にもなる。すなわち、測定した情報が局所的に収集され分析される。決定も局所的に行われ、中央の権限を必要としない。完全非集中型システムは困難であるが、本発明による実施形態では、データ配布や性能予測などの、分散された極めて重要なアクションを行い、これは、やはりシステム全体にとって極めて有益なことである。さらに、本発明による実施形態が、自分自身を段に組織化する、協力構成要素を有する段に分かれる。各段が、システムの残りの部分知識のビュー範囲、精度、詳細、適時性の異なるトレードオフを表す。
【００１７】
本発明によるインフラストラクチャの実施形態はまた、有機的でもある。ホストがネットワークに追加されると、ホストは、自動的に統合され、ネットワーク測定インフラストラクチャは、再構成される。さらに、本発明によるインフラストラクチャは、ネットワークトラフィック分析と予測精度との間にトレードオフがあることを認識し、良いバランスを示す。一般に、測定データを多く集めれば集めるほど、より良い精度を得ることができる。ネットワークを、1時間毎に測定した場合と比べ、5分毎に測定した場合の方が、分析がより正確となるが、バランスが悪くならざるを得ない。そうでない場合は、各ホストによるネットワークの頻繁なプロービングにより、プロービング自体が、測定しようとしている、まさにネットワーク性能自体を遅らせるトラフィックソースとなる。これが、測定オーバヘッドとトラフィックプロービングの精度とバランスを発見するための分析とのトレードオフである。最後に、ネットワーク性能測定が、効率的な方法で行われる。
【００１８】
本明細書に組み込まれ、その一部を形成する添付図面は、本発明のいくつかの態様を示し、詳細な説明とともに、本発明の原理を説明するのに役立つ。
【００１９】
本発明をある好ましい実施形態とともに記述するが、本発明はこれらの実施形態に限定されるものではない。その反対に、本発明の趣旨および範囲には、特許請求の範囲で定義したように、すべての代替形態、修正形態、均等物を含むものとする。
【００２０】
次に図面を参照すると、同様の参照番号は、同様の要素を表し、本発明は、適切な計算環境内で実施されるものとして示してある。必要とされるものではないが、本発明を、パーソナルコンピュータによって実行される、プログラムモジュールなどの、コンピュータ実行可能命令の一般的な状況下で記述する。一般的に、プログラムモジュールには、特定のタスクを行い、特定の抽象データタイプを実施する、ルーチン、プログラム、オブジェクト、構成要素、データ構造などが含まれる。その上、本発明が、ハンドヘルドデバイス、マルチプロセッサシステム、マイクロプロセッサベースのまたはプログラマブルの大衆消費電子製品、ネットワークPC、ミニコンピュータ、メインフレームコンピュータなどを含む、他のコンピュータシステム構成とともに実践できることは、当業者なら理解されるであろう。本発明はまた、タスクが通信ネットワークを介してリンクされたリモート処理デバイスによって行われる、分散型計算環境内でも実践できる。分散型計算環境においては、プログラムモジュールを、ローカルとリモートの両方の記憶装置デバイス内に置くことができる。
【００２１】
【発明の実施の形態】
図1は、本発明を実施できる、適切な計算システム環境100の一例を示す図である。計算システム環境100は、適切な計算環境の一例に過ぎず、本発明の使用法および機能の範囲を限定するものではない。また、計算環境100は、オペレーティング環境100の例で示した構成要素のいずれか1つ、またどれかの組合せに関係した依存性または必要条件を有するものとは解釈されない。
【００２２】
本発明は、他の数々の汎用または専用計算システム環境または構成とともに動作可能である。本発明とともに使用するのに適切であり得る、周知の計算システム、環境および/または構成の例には、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラマブル大衆消費電子製品、ネットワークPC、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたはデバイスのいずれかを含む分散型計算環境などが含まれるが、これらに限定されるものではない。
【００２３】
本発明を、コンピュータによって実行される、プログラムモジュールなどの、コンピュータ実行可能命令の一般的な状況下で記述する。一般的に、プログラムモジュールには、特定のタスクを行うかまたは特定の抽象データタイプを実施する、ルーチン、プログラム、オブジェクト、構成要素、データ構造などが含まれる。本発明はまた、タスクが通信ネットワークを介してリンクされたリモート処理デバイスによって行われる、分散型計算環境内でも実践できる。分散型計算環境においては、プログラムモジュールを、記憶装置デバイスを含むローカルとリモートの両方のコンピュータ記憶装置媒体内に置くことができる。
【００２４】
図1を参照すると、本発明を実施するためのシステムの例に、コンピュータ110の形式の汎用計算デバイスが含まれている。コンピュータ110の構成要素には、処理ユニット120、システムメモリ130、システムメモリを含むさまざまなシステム構成要素を処理ユニット120に連結するシステムバス121が含まれるが、これらに限定されるものではない。システムバス121は、さまざまなバスアーキテクチャのどれかを使用する、メモリバスまたはメモリコントローラ、周辺バス、ローカルバスを含む、いくつかのタイプのバス構造のいずれでもあり得る。例示として、このようなアーキテクチャには、業界標準アーキテクチャ(ISA)バス、マイクロチャネルアーキテクチャ(MCA)バス、エンハンスISA(EISA)バス、ビデオ電子装置規格化協会(VESA)ローカルバス、メザニンバスとしても周知の周辺構成要素(PCI)バスが含まれるが、これらに限定されるものではない。
【００２５】
コンピュータ110には、通常、さまざまなコンピュータ読取り可能媒体が含まれる。コンピュータ読取り可能媒体は、コンピュータ110からアクセスできる、どの入手可能な媒体でも良く、揮発性および不揮発性媒体、取外し可能および取外し不可能媒体の両方を含む。例示として、コンピュータ読取り可能媒体には、コンピュータ記憶媒体と通信媒体とを備える場合があるが、これらに限定されるものではない。コンピュータ記憶媒体には、コンピュータ読取り可能命令、データ構造、プログラムモジュールまたは他のデータなどの情報を格納するための、どのような方法または技術でも実施される、揮発性および不揮発性、取外し可能および取外し不可能媒体の両方が含まれる。コンピュータ記憶媒体には、RAM、ROM、EEPROM、フラッシュメモリまたは他のメモリ技術、CD-ROM、ディジタルビデオディスク(DVD)または他の光学ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置または他の磁気記憶装置デバイス、または所望の情報を格納しコンピュータ110からアクセスできる、他のどのような媒体でも含まれるが、これらに限定されるものではない。通信媒体には、通常、搬送波または他のトランスポートメカニズムなどの変調データ信号内にコンピュータ読取り可能命令、データ構造、プログラムモジュールまたは他のデータが包含され、どのような情報配信媒体も含まれる。用語"被変調データ信号"は、その特性セットの、1つまたは複数を有するか、または信号内の情報を符号化するような方式で変更された信号を意味する。例示として、通信媒体には、ワイヤードネットワークまたは直接ワイヤード接続などのワイヤード媒体と、音響、RF、赤外および他のワイヤレス媒体などのワイヤレス媒体とを含むが、これらに限定されるものではない。上述したもののいずれの組合せも、コンピュータ読取り可能媒体の範囲内に含まれるものである。
【００２６】
システムメモリ130は、読取専用メモリ(ROM)131やランダムアクセスメモリ(RAM)132などの揮発性および/または不揮発性メモリの形式のコンピュータ記憶媒体を含む。基本入出力システム133(BIOS)が、スタートアップ中などに、コンピュータ110内の素子間で情報を転送するのに役立つ基本ルーチンを含み、通常、ROM131内に格納されている。RAM132には、通常、処理ユニット120にただちにアクセス可能なかつ/または処理ユニット120内で現在動作可能な、データおよび/またはプログラムモジュールが含まれる。例示として、図1は、オペレーティングシステム134、アプリケーションプログラム135、他のプログラムモジュール136、プログラムデータ137を示すが、これらに限定されるものではない。
【００２７】
コンピュータ110はまた、他の取外し可能/取外し不可能、揮発性/不揮発性コンピュータ記憶媒体を含む。単なる例示として、図1に、取外し不可能、不揮発性磁気媒体から読み取りそこに書き込むハードディスクドライブ141と、取外し可能、不揮発性磁気ディスク152から読み取りそこに書き込む磁気ディスクドライブ151と、CD ROMまたは他の光学媒体などの、取外し可能、不揮発性光学ディスク156から読み取りそこに書き込む光学ディスクドライブ155とを示す。オペレーティング環境の例において使用できる、他の取外し可能/取外し不可能、揮発性/不揮発性コンピュータ記憶媒体には、磁気テープカセット、フラッシュメモリカード、ディジタルビデオディスク、ディジタルビデオテープ、ソリッドステートRAM、ソリッドステートROMなどが含まれるが、これらに限定されるものではない。ハードディスクドライブ141は、通常、インターフェイス140などの取外し不可能メモリインターフェイスを介してシステムバス121に接続し、磁気ディスクドライブ151と光学ディスクドライブ155は、通常、インターフェイス150などの取外し可能メモリインターフェイスによってシステムバス121に接続する。
【００２８】
上述し、図1に示した、ドライブおよびそれに関連するコンピュータ記憶媒体は、コンピュータ110のための、コンピュータ読取り可能命令、データ構造、プログラムモジュールおよび他のデータの記憶装置を提供する。たとえば、図1には、ハードディスクドライブ141が、オペレーティングシステム144、アプリケーションプログラム145、他のプログラムモジュール146、プログラムデータ147を格納して示してある。これらの構成要素が、オペレーティングシステム134、アプリケーションプログラム135、他のプログラムモジュール136、プログラムデータ137と同じまたは異なるもののどちらでも良いことに留意されたい。オペレーティングシステム144、アプリケーションプログラム145、他のプログラムモジュール146、プログラムデータ147には、所与の異なる数字を付けてあるが、これは、最小限、異なるものであることを示す。ユーザが、コマンドおよび情報を、キーボード162や、通常マウス、トラックボールまたはタッチパッドと称するポインティングデバイス161などの入力デバイスを介してコンピュータ110に入力できる。他の入力デバイス(図示せず)には、マイクロホン、ジョイスティック、ゲームパッド、衛星放送用パラボラアンテナ、スキャナなどを含むことができる。これらのおよび他の入力デバイスは、しばしば、システムバスに結合されたユーザ入力インターフェイス160を介して処理ユニット120に接続するが、パラレルポート、ゲームポート、ユニバーサルシリアルバス(USB)などの、他のインターフェイスおよびバス構造にも接続できる。モニタ191または他のタイプのディスプレイデバイスもまた、ビデオインターフェイス190などのインターフェイスを経由してシステムバス121に接続する。モニタに加えて、コンピュータにはまた、出力周辺インターフェイス195を介して接続できる、スピーカ197やプリンタ196などの他の周辺出力デバイスも含むことができる。
【００２９】
コンピュータ110は、リモートコンピュータ180などの、1つまたは複数のリモートコンピュータへの論理接続を使用する、ネットワークされた環境内で動作できる。リモートコンピュータ180は、別のパーソナルコンピュータ、サーバ、ルータ、ネットワークPC、ピアデバイスまたは他の共通ネットワークノードであり得、通常、パーソナルコンピュータ110に関して上述した素子の多くまたはすべてを含むが、図1には、記憶装置デバイス181のみを示してある。図1に図示した論理接続は、ローカルエリアネットワーク(LAN)171とワイドエリアネットワーク(WAN)173とを含むが、他のネットワークも含むことができる。このようなネットワーキング環境が、オフィス、全社的コンピュータネットワーク、イントラネット、インターネット内で、一般化している。
【００３０】
LANネットワーキング環境内で使用される場合、パーソナルコンピュータ110は、ネットワークインターフェイスまたはアダプタ170を介してLAN17lに接続する。WANネットワーキング環境内で使用される場合、コンピュータ110は、通常、インターネットなどのWAN173を経由して通信を確立するためのモデム172または他の手段を含む。モデム172は、内部でも外部でもあり得るが、ユーザ入力インターフェイス160または他の適切なメカニズムを経由してシステムバス121に接続できる。ネットワークされた環境において、パーソナルコンピュータ110に関して図示されたプログラムモジュール、またはその一部を、リモート記憶装置デバイス内に格納できる。例示として、図1には、メモリデバイス181に常駐して、リモートアプリケーションプログラム185を示してあるが、これに限定されるものではない。示したネットワーク接続は例示のためであり、コンピュータ間で通信リンクを確立する他の手段も使用できることを理解されるであろう。
【００３１】
以下の記述においては、特にそれ以外のことが示されていない限り、1つまたは複数のコンピュータによって行われる作用、およびオペレーションの記号表示を参照しながら、本発明を記述していく。そのため、時に、コンピュータ実行と称する、このような作用およびオペレーションには、構造化形式でデータを表す電気信号のコンピュータの処理ユニットによる操作が含まれることを理解されるであろう。この操作が、コンピュータのメモリシステム内の複数の場所で、データを変換し維持し、当業者には良く理解されている方式でコンピュータのオペレーションを再構成しまたはその他の変更をする。データが維持されているデータ構造は、そのデータのフォーマットによって定義された特定のプロパティを有するメモリの物理的な場所である。しかし、本発明を上記の状況下で記述していくが、当業者なら理解されるであろうが、以下に記述するさまざまな作用およびオペレーションがハードウェア内でも実施されることに限定されるものではない。
【００３２】
本発明によるネットワーク測定インフラストラクチャにおいて、ネットワーク性能情報、距離が、待ち時間(たとえば、ラウンドトリップ遅延)、そして可能な場合には、帯域幅の面で提供される。待ち時間が、提供するのに最も容易な種類の情報であり、通常、一般的に最も有用である。待ち時間情報が、提供するのに最も容易であるのには、2つの理由がある。まず最初に、ネットワーク待ち時間のおおまかだが良い推定を出すために、ほんの少数のパケットしか必要としないという点で、測定が容易である。第2に、ネットワークを介して2つの異なる経路が、同じ待ち時間を有することがあるため、待ち時間判断のために使用されるプロービングパケットが、ユーザのデータパケットによって実際にとられた経路と同じ経路を進まない場合があるが、報告される待ち時間はやはり有用であることである。
【００３３】
帯域幅もまた、多くのアプリケーションにとって明らかに重要であるが、待ち時間と比較すると、帯域幅の方が、提供するのにより困難である。帯域幅はまた、測定するのが高価であり、正確な経路に対してよりセンシティブである。実際、ネットワーク経路内の単一の低い帯域幅リンクが、経路全体のための帯域幅を決定づける。また、待ち時間と帯域幅の間にラフなやりとりがあるようである。つまり、2つのホスト間の待ち時間が低ければ低いほど、帯域幅が高くなる可能性がある。このやりとりにより、高い帯域幅を必要とするアプリケーションが、第1の概算として最小化された待ち時間を有するサービス/サーバ/経路を選択できるようになる。大規模ネットワークにおいて帯域幅メトリックを測定するのは難しいが、本発明によるシステムは、以下に詳細に記載するように、TCPプロービングパケットを利用して、このような測定を達成する。
【００３４】
距離推定値を導出するために、本発明による一実施形態が、三角法技術を利用する。この技術を理解するために、大規模ネットワーク内のホストが、頂点Vのセットを有するグラフGを構築すると想定する。費用関数Cが、グラフ内のすべての頂点A、B、Cのための三角不式を満足すると言われている。
C(A,C)≦C(A,B)+C(B,C)                                    式1
ネットワークメトリクスC(A,B)およびC(B,C)が周知である場合は、式1の三角不式から、ネットワークメトリックC(A,C)が、C(A,B)+C(B,C)だけ上に、また│C(A,B)-C(B,C)?だけ下に限られることが分かる。つまり、
│C(A,B)-C(B,C)│≦C(A,C)≦C(A,B)+C(B,C)                  式2特に、C(A,B)が非常に小さい場合は、C(B,C)を使用して、C(A,C)=C(B,C)である、C(A,C)を推定することができる。ここで、C(A,B)<<C(B,C)である。以下の記述では、C(A,B)を表すために(A,B)を使用する。この境界から距離推定値を導出することは、P. Francis et al., "An Architecture for a Global Internet Host Distance Estimation Service," Proc. of IEEE INFOCOM 1999, March 1999"の中で三角法"と称されている。その教示および開示全体を参照により本明細書に組み込んである。この想定は、効率的なルーティングであるというさらなる想定に基づいている。効率的なルーティングとは、インターネットルーティングが、低待ち時間経路を懸命に捜そうとし、2つの近接のホストによって使用されるルートが、互いに劇的に異ならないということである。幸いなことに、大抵、ルーティング状況が、このような想定の良い基礎を提供する。
【００３５】
本発明によるシステムはまた、近接のホストが、他のホストと同様の待ち時間を有すると想定する。本インフラストラクチャの一実施形態において、AからBへのラウンドトリップ時間が、T未満、すなわち、RTT(A,B)<Tの場合は、2つのホスト、AおよびBが、互いに"近接"している。ここで、Tは、閾値として働く、小さい値である。Tは、本明細書の以下に記載する、プロービンググループ形成手順における重要なパラメータである。これは、システム全体の精度および性能に影響する。定義したように、すべての近接のホストが、特定のホストに対し低い待ち時間を有し、三角法の想定から、それぞれが互いに小さい待ち時間を有するため、各近接のホストが、他のすべての近接のホストに対し、同様のRTTを有さなければならないことが示される。
【００３６】
これらのコンセプトを明確に頭に入れた上で、次に、本発明によるインフラストラクチャ(gMeasure)に、直接、注意を向けることとする。このインフラストラクチャは、主に、インターネット上のいずれか2つの有効なIPアドレス間などの、大規模ネットワーク内のいずれか2つのホスト間のネットワーク性能の推定値を提供する。この機能は、gMeasureを、これも、ネットワーク性能情報、すなわち、
M. Stemm, R. Katz, and S. Seshan, "A Network Measurement Architecture for Adaptive Applications," Proc. of IEEE INFOCOM '00, pp. 2C-3, Mar. 2000
C. Labovitz et al., "Internet performance measurement and analysis project," url:http://www.merit.edu/ipma/, 1998
V. Paxson, J. Mahdavi, A. Adams, and M. Mathis, "An Architecture for Large-Scale Internet Measurement," IEEE Communications Magazine, vol. 36, no. 8, pp. 48-54, August 1998および
A. Adams et al., "The Use of End-to-End Multicast Measurements for Characterizing Internal Net-work Behavior," IEEE Communications Magazine, pp. 152-158, May 2000
で議論されているSPAND、IPMA、NIMI、M1NCプロジェクト(例えば、非特許文献6、7、8、9参照)を提供する、他のサービスから著しく区別する。これらのプロジェクトは、一般的なインターネットの特徴付け、維持、故障分離、エンドシステム距離評価などの、さまざまな目的に役立つ。しかし、本発明による測定インフラストラクチャは、大規模ネットワーク、たとえばインターネット内のいずれか2つの任意のポイント間でネットワーク性能情報を提供する分散型測定アーキテクチャである。
【００３７】
アプリケーション適合ポリシを進めるためのネットワーク測定サービスを生成する以前の試みにおいて、主に、分離したネットワーク統計測定に焦点を合わせていた。分離した測定とは、アプリケーションが、個々に、ネットワークの状態の測定を行い、この測定情報を他のホストとは共有しないということである。ピアツーピアファイル共有およびクライアントホステッドマルチプレイヤゲームなどの、距離情報を必要とするアプリケーションの増加とともに、この分離した集中型ネットワーク測定の集合した負荷が、ほぼN2程度で拡大する。ここで、Nは、ネットワーク内のホストの数である。この結果、大量の測定トラフィックが生じ、実際に、ネットワークが過負荷となる。
【００３８】
このような従来の方法とは全く反対に、本発明によるインフラストラクチャは、プロービンググループコンセプトに基づいてネットワーク性能を測定するが、これは、ネットワークに大きい負荷を与えない。プロービンググループが、近接のホストによって構築される。プロービンググループの、この"近接"特性は、性能測定および予測のための良い環境を提供する。上述したように、2つのホストがネットワークトポロジの面で互いに近接している場合、それらが、リモートサイトに対して同じボトルネックリンクを共有する可能性が高い。その結果、このサイトに対して測定するネットワーク性能が同様になる可能性が高い。したがって、これらのホストのそれぞれが、独立してネットワークをプローブし、この情報を発見することは、不必要でありかつ望ましくもない。本発明によるインフラストラクチャにおいては、多くの近接のホストが、測定情報を互いに共有して、必要なプロービングを最小限に押さえ、それにより、このようなプロービングの結果生じるネットワーク負荷を最小限に押さえる。
【００３９】
プロービンググループ、または測定グループ(MeGroup)が、グループのリーダと呼ばれる、特定のホストに近接している1セットのホストとして定義される。この定義には、いくつかの利点がある。まず最初に、MeGroupの"近接"特性が、測定および予測のために良い環境を提供する。これは、独立したプロービングと比べて、より効率的である。なぜなら、多くのホストが、互いに測定情報を共有できるからである。第2に、以下に詳細に記載する、MeGroupの動的特性により、本発明によるアーキテクチャが、異種のインターネットに対してよりスケーラブルになる。
【００４０】
各MeGroupが、通常、いくつかのホストを持ち、その1つが、リーダである。MeGroup内のリーダは、各グループのリーダ間の距離を測定する、グループ間測定を行う責任がある。次いで、この測定結果が、各グループメンバに配布される。さらに、MeGroupのリーダは、そのリーダのMeGroup内のホスト間の距離を測定する、グループ内測定の責任がある。本明細書の以下に詳細に記載するように、本発明による一実施形態が、この測定を行うためにマルチキャスト方法を利用する。実際、この方法は、両測定(グループ間およびグループ内)に適用して、フルメッシュネットワーク性能情報を効率的に得ることができる。したがって、好ましくは、ネットワーク全体の中の各ホストが、グループ全体のフルメッシュ性能情報である、グループ内ネットワーク性能を認識している。実際、これは、各グループ内で頻繁に測定される。ネットワーク全体の中の各ホストがまた、好ましくは、グループリーダ間のフルメッシュ性能情報である、グループ間ネットワーク性能も認識している。これは、以上に記載した近接特性に基づく隣接のグループ間のネットワーク性能を表す。この情報は、一実施形態においては、グループリーダ間で情報を交換することにより測定される。
【００４１】
図2は、大規模ネットワークl98内の本発明によるプロービンググループの簡単な例を示す図である。この図2には、6つのプロービンググループ200-2l0があり、それぞれがグループリーダ212-222を持ち、そのグループリーダが、同じグループ内および隣接のグループの中のホスト間のデータ共有を取り扱う。グループ202内のホスト224が、アクティブプロービングによってグループ208内のリモートホスト226間のネットワーク性能を得ると、ホスト224は、同じグループ202内の他のホスト214、228、230のすべてに、その情報を配布する。次いで、グループ202のためのグループリーダ214は、その隣接のグループ200、204内のグループリーダ212、216のすべてに、この性能情報を配布する。このグループ202の別のホスト230が、自分自身230とリモートホスト226の間のネットワーク状態を知る必要があるかまたは推定することを望む場合も、どのようなアクティブプロービングも行う必要はない。実際、ホスト230は、元々ホスト224によって得られそれから通信された共有情報に基づいて、ネットワーク性能を予測することができる。
【００４２】
しかし、2つのリモートグループ内のホスト間のネットワーク性能を判断する第1の実例で、すなわち、使用できる、このような性能の事前共有情報がない場合は、ホストは、性能自体を判断しなければならない。一例として、グループ202内のホスト224が、グループ208内の自分自身224とリモートホスト226間のネットワーク状態を推定することを望むと想定する。グループ202内のホストのどれもが、グループ208内の宛先(いずれかのホスト)に対するネットワーク性能を測定しなかったため、同じグループ202内で共有できる履歴情報はない。しかし、本発明によるインフラストラクチャは、共有知識を使用して、アクティブ性能測定をする必要を未然に防ごうとし、したがって、ネットワークの負荷とオーバヘッドを最小限に押さえる。
【００４３】
この特徴に従って、隣接のグループ200、204から存在するネットワーク性能情報を使用して、ネットワーク性能を推定または予測する。図3は、この段に分かれたデータ共有を示す図である。プロービンググループ202とその隣接のグループ200および204は、場当たり的に第2の段グループ232を動的に形成する。この第2の段グループ232では、グループ200と208間およびグループ204と208間の測定したネットワーク状態が、グループ200および204のグループリーダ212、216を介して、グループ202のグループリーダ214に配布される。次いで、グループ202のリーダ214は、その情報をグループ202内のホスト224、228、230に配布する。このようにして、ホスト224は、この第2の段グループ232内のグループからの情報を階層的かつ有機的に共有することにより、ネットワーク性能を予測することができる。有意義な情報がこのようにして得られなかった場合にのみ、ホスト224は、ネットワーク性能自体を判断しなければならない。
【００４４】
次に図4を参照すると、新しいホスト234がネットワーク198に入り、その結果、MeGroup改正が生じるものとして、MeGroupsの有機的な性質が記載してある。新しいホスト234がネットワークl98の一部になると、そのホスト234は、既存の近接のグループに結合するかまたは新しいグループを確立することができる。そのための判断は、新しいホスト234が、まず最初に、結合すべき近接のグループを発見するために、既存のグループリーダ212-222のすべてに対して、プロービングを行うことによってなされる。このような近接のグループが存在しない場合は、ホスト234は、新しいプロービンググループを確立し、グループリーダとして働く。図4では、新しいホスト234が、グループ206が近接のグループとしての資格があることを発見する。次いで、このホスト234は、再生されたグループ206'として指定された、このグループに結合するが、このプロセスについては、本明細書の以下にさらに十分に記載する。
【００４５】
新しいホスト234がグループ206'に結合した後、このグループ206'内に3つのホスト218、234、236がいて、ホスト218が、グループリーダとして仕える。しかし、現在グループ206'を構成する、これらのホスト218、234、236間で、たとえば、ホスト218が、現在のグループメンバに対する物理場所のせいで、グループリーダとしてもはや最良の候補ではない場合がある。グループリーダは、このグループ内のすべてのメンバホスト間にすべての共有情報を配布する必要を有するホストであり、したがって、すべてのメンバの中心にいなければならない。この中心ということはまた、リーダによって共有される待ち時間情報が、そのグループメンバのどれか1つによって見られる待ち時間に最も近似しているため、重要である。この場合、以下に記載するグループ再生ポリシに従って、ホスト236は、グループリーダとしての責任を果たす。このグループ206'の再生の後、隣接のグループ204、208内のホストは、グループリーダの変更についての通知を受ける。
【００４６】
いったんこの情報が配布されると、現在他のグループ内のメンバとなっているホストのなかに、現在の自分のメンバーシップがもはや適切ではないことを発見するものがある。これは、恐らく、再生されたグループ206'の新しいグループリーダ236が、その現在のグループリーダより接近しているからである。このような状況が図5に示してあるが、ここでは、ホスト238は、ホスト236をグループリーダにすることがより適していることを発見する。この場合、ホスト238は、グループ204を去り、再生されたグループ206"として示してあるグループに結合する。このことにより、新しいグループ204'内にはホスト216および240が残り、2つのメンバのみを有する。この動的特性により、本発明による測定アーキテクチャが、異種のインターネット198に対してよりスケーラブルになる。例示したこれらのプロセスは、新しいホストがネットワークに入り、古いホストがネットワークを去る時、連続して起きる。ネットワークに入ったりまたはそこから去ったりするホストがない場合でさえも、これらのプロセスは、ネットワーク状態が変化した場合にも起こる場合がある。
【００４７】
上記の記載は、MeGroupsの有機形成および改正をグラフ的に示したものである。以下の記載では、これらの機能の各詳細について検討していく。MeGroupの形成に関して、このようなグループのそれぞれが"近接"ホストからなることを繰り返す価値がある。そのため、MeGroupの形成するプロセスは、このような近接のホストを発見することに関係する。近接の概念については、マルチキャストソリューションが実際的でありかつ効率的である。本発明による一実施形態では、グループリーダのすべてが、一意マルチキャストグループMに結合するが、これは、ホストによって使用されて、測定グループを形成する。上記に記載したように、新しいホストがネットワークに来ると、それは、既存のグループに結合するかまたは新しいグループを確立することができる。図6に示すように、いったんこのプロセスが開始する242と、新しいホストは、グループを見つけようとする課程で、マルチキャストグループMに結合する244。次いで、新しいホストは、近接のグループを発見するために十分に大きいTTL(活動時間(Time to Live))を有する要求メッセージを送出する246。いったんグループリーダが要求メッセージを受け取ると、ただちに応答メッセージで応答する。この応答メッセージには、好ましくは、新しいホストに有益な、たとえば、グループIDやグループメンバのIPアドレスなどの、MeGroup情報が含まれる。新しいホストが、MeGroup、たとえば、MeGroupXからTの定義済み待ち時間内に応答メッセージを受け取る248と、マルチキャストグループMを去り250、MeGroupXと結合252し始めるが、この詳細については、以下に説明する。新しいホストが、Tの定義済み待ち時間内にどの応答メッセージも受け取らない248場合は、このホストは、新しいMeGroupを形成し256、グループリーダとして働く。次いで、このプロセスが終了する254。
【００４８】
図7に示したように、いったん開始する258と、MeGroupXが新しいホストを有するなどの、グループに結合するプロセスが、そのMeGroupXのマルチキャストグループに結合する260。ホストは、マルチキャストを使用して、少なくともそのlPアドレス情報を送る262ことにより、グループ全体に自己紹介する。新しいホストは、紹介マルチキャストに対する、その応答からMeGroupX内の他のメンバホストについて知る264。しかし、新しいホストが、新しいグループをセットアップすることを決定すると、図8のプロセスが開始する268。まず最初に、ホストは、マルチキャストグループMに結合270し、自分自身をグループリーダとして識別する。次いで、ホストは、この新しいグループのリーダとして働き、新しいホストが結合してくるのを待つ272。ホストは、測定データの効率的な転送のために、MeGroup内のすべてのメンバが結合する、MeGroup内でマルチキャストグループを確立する274。次いで、このプロセスが終了する276。
【００４９】
上述したように、本発明によるインフラストラクチャはまた、有機的な自己組織化により、MeGroupの改正を提供する。ここで記載した基本グループ形成アルゴリズムは、むしろ安定したグループを形成する。言い換えれば、いったんホストがグループに結合すると、その存続期間中、このグループを去ることはない。しかし、この特性は、本発明によるシステムの測定および評価ステージに対して効率的ではない。グループのメンバーシップが、ネットワーク上のホストの存続期間にわたる場合、そのグループがもはやホストの1つに適してしないせいで、グループメンバが損害を受ける場合がある。つまり、基本グループ結合アルゴリズムによれば、初期のステージでは、新しいホストが、その時の最良のグループである、結合すべきグループを発見する。しかし、時が経つにつれて、そのホストに対して、元のグループより適切な、新しいグループがいくつか生成される場合がある。以下のセッション、発見的方法では、ホストジャンピングを本発明に導入して、このような場合のシステム性能を向上させる。
【００５０】
さらに、リーダがもはやそのグループに適していないせいで、この停滞グループ内のホストが、損害を受ける場合がある。基本グループ形成アルゴリズムのグループリーダは、最初にネットワークに入って来た時に、近接のグループを発見することのできないホストである。いったんホストがグループリーダになると、基本アルゴリズムの下では、その存続期間にわたって、それが変更されい。グループメンバが変化するにつれてデータ配布および共有に役立つための、最良のホストではない場合があるため、これは、最適なソリューションではない。たとえば、それが、もはやグループの中心にいない場合がある。このことにより、グループ内の待ち時間の想定が破壊され、グループ間の共有待ち時間情報が不正確になる。以下のセッション、発見的方法では、リーダの改選を本発明に導入して、このような場合のシステム性能を向上させる。
【００５１】
さらに、グループがあまりに小さすぎて効率的にデータを共有できないために、停滞グループ内のホストが、損害を受ける場合がある。小さいプロービンググループは、分散型性能測定に対して、それ程効率的ではない。極端な場合が、そのグループ内にメンバがいないという、孤立したグループリーダがいる場合である。このような場合は、このようなグループリーダは、そのネットワーク性能情報をいずれかの他のホストと共有することによる効率が得られないため、別のグループに結合する方が良い。したがって、本発明によるインフラストラクチャの好ましい実施形態では、より良い性能を達成するために、MeGroupが、その存続期間中、動的に再生できるようになる。以下のセッション、発見的方法では、グループの組合せを本発明に導入して、このような場合のシステム性能を向上させる。
【００５２】
本発明による実施形態では、プロービンググループを再生するために、いくつかの発見的方法を利用する。一実施形態では、発見的ホストジャンピングを用いて、上述の問題を回避する。ホストが、そのグループがもはやそれに適していないことを発見すると、それは、より適切なグループにジャンプする。上記に記載したように、費用関数C(A,B)は、ホストAとB間の距離として定義される。ホストAの現在のグループリーダGが、図9に示すように、グループiのグループリーダであり、ホストAが、費用関数C(A,Gi)を判断する280ことによって開始する278。ホストAが、グループxに対する新しいグループリーダGxを見つけると、それは、費用関数C(A,Gx)を計算する282。いったんこれらを計算すると、
C(A,Gx)<C(A,Gi)                                          式3
の場合に、グループi内のホストAが、それ対するより適切なグループxを発見する284。
【００５３】
別の書き方をすると、ホストAは、自分自身のグループリーダと比べて、他のグループのリーダにより近い場合に、新しいグループに結合する286。このようにして、共有ネットワーク性能情報の使用を可能にする上記の想定が有効に保たれるか、またはその有効性が最大限に活用される。いったんホストが他のグループに結合すると、このプロセスが終了する288。
【００５４】
残念なことに、本発明によるいくつかの実施形態では、いずれかの特定のMeGroup内のホストが、自分自身から他のグループリーダまでの距離を知らない場合がある。このような実施形態では、図10のプロセスが開始する290。ホストは、自分自身とそれ自身のグループリーダの距離を知っているかまたは計算する292ことができる。このプロセスでは、ホストはまた、ステップ294で、そのグループリーダと他のグループリーダ間の距離についての知識を活用し、その情報を共有する。この情報で、ホストは、より適切な(ホスト自身よりもそのグループリーダに接近している)潜在グループを判断できる。三角不式から、
C(Gi,Gx)≦C(Gi,A)+C(A,Gx)                                式4
以下の不式が決定できる。
C(Gi,Gx)-C(Gi,A)≦C(A,Gx)                                式5
式3と比較して、以下の条件が満足される場合、
C(Gi,Gx)-C(Gi,A)>C(A,Gx)                                 式6
つまり、
C(Gi,Gx)>2C(Gi,A)                                        式7
次いで、ホストは、ステップ296で、そのグループiがもはやホストAに対する適切なグループではないことを演繹でき、終了する300前に、グループxに結合する298。言い換えれば、
C(Gi,Gx)≦2C(Gi,A)                                       式8
の場合、グループxが、ホストAに対する潜在グループであり、これは、現在グループi内にある。
【００５５】
C(Gi,Gx)およびC(Gi,A)の性能情報がホストAに対して周知であるため、いずれかのホストがその潜在グループを発見するための、式8の不等号を形成することが可能である。いったんホストがその潜在グループを知ると、各グループリーダにプローブして、式3に基づいて、このグループが本当により適切なグループかどうかを検証する。第1の適切なグループを発見した後、それは、現在のグループを去り、上記に記載した結合タスクを行う。
【００５６】
上記に示したように、グループリーダが、グループの論理中心であるべきである。しかし、特定のメンバおよびあるグループの規模が、個々のホストの結合するおよび去る挙動により、時間が経つにつれて変化する。そのため、元のグループリーダは、常にそのグループのこの論理中心にいるとは限らない。したがって、リーダを変更するために、再構築プロセスを使用する必要がある。このプロセスを十分に理解するためには、まず最初に、論理グループの中心の概念を定義する必要がある。自然な考え方として、他のグループメンバに対して最小距離を有するホストを発見することである。具体的には、論理グループの中心は、グループ内の他のホストに対する最大距離が最小であるホストである。この判断には、有利なことに、どの追加のネットワーク測定も必要としない。
【００５７】
理想的な状況においては、グループ内の各ホストがメンバ間のすべてのグループ内の距離を知っているため、グループ内の各ホストは、どのホストがそのグループにとって適切なリーダであるかを知る。しかし、十分な距離情報を有していないホストがある場合がある。予期せずにリーダ改選を試みることを回避するために、一実施形態では、元のリーダが、新しいリーダを推奨する責任をもつ。推奨するプロセスは、図11に示してある。いったん開始する302と、元のリーダが、各ホスト間の距離を計算し304、どのホストが、新しいリーダとしてグループに推奨すべき、最も適切なホストであるかを判断する306。元のリーダは、新しいリーダになる気があるかどうかを、その候補ホストに尋ねる308。そのホストが同意する310と、それが新しいリーダとなり、選択のプロセスが終了する312。そのホストが同意しない310場合、かつ現在のリーダよりグループリーダとしてより適切なホストが1つを超える数いる314場合は、現在のリーダは、次に最も適切な候補ホストに新しいリーダになるかを尋ねる308。以下、同じことが続行される。しかし、これ以上適切なホストがいない314場合、かつ現在のリーダがリーダに留まることができる316場合は、そのホストがリーダに留まったままで、プロセスが終了する312。316の場合は、現在のリーダは、リーダに留まっていることができず、MeGroupは、このプロセスを終了する前に、解散する318。この時点で、ホストは、結合すべき新しいMeGroup発見することを試みるか、または、上記に記載したようにそれ自身で形成する。
【００５８】
リーダ再構築プロセスは、グループ内のすべてのホストの性能に影響を及ぼし、そのため、リーダを頻繁に変更することは望ましくない。ここに記載した基準の下に、グループの中心にいるホストが同時にいくつかいる場合にのみ、リーダを頻繁に変更することができる。本発明による一実施形態では、再構築プロセスを行うまで、リーダが一定期間その位置に留まることが必要な場合に、別の基準を使用する。リーダ改選が必要な別の状況に、リーダが、予期せずにネットワークを去らなければならない場合がある。測定グループ内のほとんどすべてのホストが、ネットワーク状態についてのフルメッシュ情報を有しているため、一定期間、グループ内測定情報を受け取らなかった各ホストが、このリーダ再構築プロセスを発動する。
【００５９】
上記で明らかとなったであろうが、MeGroupの効率は、各グループのサイズに関係する。小さいグループは、共有測定情報も小さいため、効率的ではない。小さいグループのリーダが近接のグループを発見した場合は、グループ全体が近接のグループに結合すると、効率的であろう。このプロセスは、図12に示してある。いったん開始すると320、グループリーダは、そのグループがあまりに小さすぎて効率的でないことを判断する232。次いで、グループリーダは、結合すべき"近接"グループを探索する。リーダがこのような近接のグループを発見した234場合、グループA(小さいグループ)のグループリーダGAが、グループB(近接のグループ)のグループリーダGBに、グループAが結合することを受け入れるかどうかを尋ねる236。GBが同意した238場合は、GAは、グループBに結合するよう、グループA内のすべてのメンバに、メッセージを送る240。元々グループA内にいた各グループメンバが、グループに結合するタスクを行い、上記に記載したように、グループBのメンバに自己紹介する。GBが同意しない238場合は、グループAのリーダは、そのグループとのグループの組合せ要求を取り消し、結合すべき適切な他の近接のグループがあるかどうか234を監視する。結合すべき他のグループがない場合は、グループA(小さく非効率的な)が、終了する242前に、そのメンバを放逐し、グループを解散する244。この結果、放逐されたグループ内の各ホストが、上記に記載したように、適切なグループに結合する。もちろん、この方法により、ネットワークに対してより多くのトラフィックが生じるが、長期的には、インフラストラクチャに対してより多くの効率をもたらすこととなる。
【００６０】
これまでグループ形成/改正プロセスについて記載してきたが、次に、グループ内およびグループ間性能測定のための、本発明によるネットワーク性能測定インフラストラクチャで使用される、アルゴリズムに注意を向けることとする。ホストメンバ間のグループ内での測定は、グループ内測定として分類され、グループとグループの間の測定は、グループ間測定として分類される。それらのプロパティに従って、2つの測定分類のために異なるアルゴリズムが使用される。
【００６１】
グループ内およびグループ間測定の基本要求事項は、いずれか2つのホスト間のネットワーク性能を測定することである。これを行うために、以前のシステムでは、各ホストが、ユニキャストベースのプロービングを使用して、他のすべてのホストに対する状態を周期的に測定することを必要とする簡単な方法を使用してきた。しかし、これらの以前のシステムが、Nホストのフルメッシュプローブを行うためには、O(N2)プロービングパケットを必要とし、これは、Nがインターネットの場合のように大きい場合には、大量のトラフィックを生成する。
【００６２】
この問題を解決するために、本発明による一実施形態が、マルチキャストベースの測定方法を利用する。マルチキャストは、ユニキャストと比べて、ソースからおよびネットワークにはるかに少ないトラフィックを導入することが周知である。マルチキャスティングは、ビデオオンデマンドやテレビ会議などのグループ通信で広く使用されてきたし、本発明によるグループ内測定でも非常に有益である。パケットがさまざまな形で経路選択されるため、場合によっては、ユニキャストおよびマルチキャストベースの距離測定の結果が等しくならないことに留意されたい。それにもかかわらず、本測定は、大きい問題とはならない。なぜなら、以下に示すように、本発明によるアーキテクチャで重要なことは、絶対距離ではなく、異なるホスト対の距離間の関係だからである。
【００６３】
このマルチキャストベースのRTT測定方法には、2つの段階がある。第1の段階では、1つのホストが、パケットをグループにマルチキャストすることにより、測定を起動する。パケットを受け取った各ホストが、元のホストにフィードバックを送る。したがって、元のホストは、他のホストのいずれに対してもRTTを計算することができる。すべてのフィードバックも、マルチキャストを使用して送られることに留意されたい。これは、この段階の後、各ホストが、マルチキャストの結果として、いくつかの余分のネットワーク性能情報を他のホストから受け取るため、有利である。たとえば、4つのホスト、A、B、C、Dのグループを考えてみる。Aが、マルチキャストプローブを起動すると想定する。他のホストがこのプローブに応答した後、各ホストが、以下のテーブルに示すように、パケットを受け取る。
【００６４】
【表１】
0004226922.tif 000002
【００６５】
テーブルでは、A-Xが、ホストAからホストXに送ったプローブパケットを表す。各ホストが、マルチキャストを使用してプロービングパケットに応答するため、Aのプローブに対するホストXの応答が、他のすべてのホストによっても受け取られる。したがって、テーブル1では、ホストAのプローブに対する応答としてホストXからマルチキャストされ、ホストYによって受け取られた応答パケットは、A-X-Yとして表される。テーブルから、1つのパケットが(ホストAから)送られ、3つのパケットが各ホストによって受け取られることが容易に分かる。
【００６６】
いったんホストAが、他のホスト(パケットA-B-A、A-C-A、A-D-A)のそれぞれから応答パケットを受け取ると、ホストAは、これらの他のホストに対するRTT性能を知る。しかし、他のホストは、各受け取ったパケット間の時間間隔のみを知る(パケットを送る時間が、プロービングパケットが受け取られた時間と同時であるとして扱われることが好ましい)。そのため、各ホストは、それに関係する部分的な性能情報のみを知る。したがって、第2の段階では、各ホストが、他のすべてのホストに対してその情報をマルチキャストし、その結果、グループのフルメッシュのネットワーク性能情報を計算できるようになる。このことは、三角法アルゴリズムを使用して完成される。
【００６７】
簡単な例で、このコンセプトを示す。この例では、(X,Y)は、送信側Xから受信側Yへのワンウェイトリップとして定義される。この第2の段階の前に、以下の情報が、それぞれ、4つのホストで入手可能となる。
ホストA:
A.1:(A,B)+(B,A)
A.2:(A,C)+(C,A)
A.3:(A,D)+(D,A)
ホストB:
B.1:(A,C)+(C,B)-(A,B)
B.2:(A,D)+(D,B)-(A,B)
ホストC:
C.1:(A,B)+(B,C)-(A,C)
C.2:(A,D)+(D,C)-(A,C)
ホストD:
D.1:(A,B)+(B,D)-(A,D)
D.2:(A,C)+(C,D)-(A,D)
しかし、第2の段階では、この情報が、ホストのすべてに対してマルチキャストされる。したがって、第2の段階の後、上述の情報が、すべてのホストで入手可能となり、すべてのホスト対のRTTを計算することが容易となる。たとえば、B.1とC.1を合計すると、
[(A,C)+(C,B)-(A,B)]+[(A,B)+(B,C)-(A,C)]=(C,B)+(B,C)          式9
を得る。
これは、BとC間のRTTである。同様の計算を適用して、B.2+D.l=RTT(B,D)およびC.2+D.2=RTT(C,D)であることを発見することができる。A.l、A.2、A.3のプロービング結果で、すべてのホスト対のRTTが計算できる。このアルゴリズムを、任意の数のホストを有するグループに簡単に拡げることができる。
【００６８】
本発明による一実施形態では、ネットワーク性能測定データが、好ましくは、同じグループ内の他のすべてのホストに配布される。一実施形態では、この性能情報を配布するために使用される測定データ構造には、ソースホストIP、宛先ホストIP、宛先グループID、測定が行われる時間が含まれる。
【００６９】
好ましくは、測定データを配布するためのメカニズムが、IPマルチキャストである。このメカニズムにより、各ホストが、他のホストとの調整をする必要がなく、その測定データを送信することができるようになる。実際、同じグループ内のホストも、転送するために接続される必要がない。本発明によるインフラストラクチャでは、この測定データは、エラーフリーである必要もなく、またホスト間で同期されている必要もない。このため、IPマルチキャストの保証されていない配信特性は、問題とならない。この意味で、IPマルチキャストが、価値ある発見メカニズムとしても分布メカニズムとしても役立つ。
【００７０】
グループ内のホスト間でこのようなマルチキャストグループを形成することが適切でない、または不可能である場合は、本発明による一実施形態により、測定データをピアツーピアデータ転送モードで配信する。たとえば、スパニングツリー構造または強力な拡散構造を利用できる。
【００７１】
残されている重要な問題点は、共有測定情報を使用して、ネットワーク性能を、どのように推定し予測するかである。上記に記載したように、グループ内の各ホストが、ネットワークについての以下の情報、すなわち、グループ内のすべてのホストによってプローブされたIPアドレス、グループ内のすべてのホストによってプローブされたグループID、行われた各プローブの時間、プローブの結果を認識するようになる。測定データ拡張の原理は、近接のホストが同様のネットワーク条件を有することを想定している。そのため、この原理は、グループ内で、すべてのホストが、宛先のホストに関係するプローブデータを有効なデータとして使用して、自分自身から宛先のホストへのRTTを推定できることを示す。本発明による原理に従って、この原理の範囲を、さらに拡張できる。つまり、本発明によるインフラストラクチャでは、宛先のホストに対するRTTに関係するプローブ結果データが、宛先のホストを含むグループ内のいずれのホストに対するRTT、すなわち、グループX内のいずれかのホストからグループY内のいずれかのホストまでのRTT、または単にグループXからグループYまでのRTTと同様であると想定され、したがって、それとして使用できる。
【００７２】
本発明による評価および予測方法を適用する際に、いくつかの簡単な線形方法が良い結果を有するように、ネットワークステータスが基本的に安定していなければならないことが想定される。このアーキテクチャでは、どのような評価および予測方法も、データに適用できる。たとえば、平均ベースの方法、メジアンベースの方法、自己回帰方法が良い。さらに、ネットワーク性能データが、計算を行う前に、ホストに"プッシュ"されるため、データ不足の問題はない。すなわち、ホストが、測定データについて他のホストに相談する必要がない。以前のシステムとは異なり、ネットワーク内のホストの数が大きくなればなる程、より多くの測定データを共有でき、性能予測において、より高い精度および効率が達成される。
【００７３】
本発明による一実施形態では、測定結果が重み付けされる。一実施形態は、さまざまなタイプのプロービングデータのそれぞれを等しく取り扱うが、この実施形態は、すべてのデータが必ずしも同等ではないことを認識する。つまり、ホスト自体によるプロービングによって得られたデータは、他のホストから共有されたプロービングデータと比べて、そのホストに対してより正確である。これはまた、プロービング結果および予測結果についても、同様である。そのため、この実施形態は、異なる測定結果、または測定結果の異なる分類を、さまざまな形で重み付けする。一実施形態では、ホスト距離を使用して、測定データに適用すべき重み付けを判断する。距離が長ければ長い程、重み付けの値が小さくなる。
【００７４】
代替実施形態では、測定データの三角重み付けを適用する。これを証明するために、ホストAが評価を行うホストであり、ホストCが宛先であり、ホストBが、ホストAが常駐するグループのリーダであり、ホストDが、ホストCが常駐するグループのリーダであると想定する。上記の記述に基づいて、ホストBが、先にホストDに対して性能測定を行った。ホストBは、(B,D)と(C,D)の情報により、自分自身とホストC、(B,C)の間のネットワーク性能を推定できる。次に、ホストAについて考える。ホストAは、ホストC、(B,C)に対する性能情報を受け取り、自分自身とホストC、(A,C)間の性能を推定した、自分自身とホストB、(A,B)間のネットワーク性能について知る。上記に記載した三角不式から、(A,C)が、上に(A,B)+W*(B,C)だけ、下に|(A,B)-W*(B,C)|だけ限られ、ここで、Wは、重み付け値である。
【００７５】
本発明によるシステムはまた、測定ツール(gMeasure)を提示して、ここで記載したネットワーク性能測定を行う。インターネットの現在の状態が与えられたとすると、本発明によるgMeasureツールの好ましい実施形態が、インターネット制御メッセージプロトコル(ICMP)を使用しない。これは、ICMPパケットが、しばしば、ろ過されたり、落ちたり、またはそのクライアントの代りにISPによって返答されたりするためである。また、いくつかのオペレーティングシステム(たとえば、ソラリス)が、ICMP応答のレートを制限する。その結果、ICMPの使用により、ネットワークについての間違った性能情報が出る可能性が起きる。したがって、好ましい実施形態では、gMeasureツールが、TCPパケットを使用する。gMeasureはまた、UDPパケットを使用して、アクティブプロービングを行うことができるが、詳細については、別の適用形態で分かるであろう。
【００７６】
TCPパケットを有する非協力的な環境で性能を測定した場合、gMeasureは、TCPプロトコルの活用に頼って、上述したパケット交換のシーケンスを行う。TCPプロトコルでは、リモートマシンの非活動ポートに送ったSYNパケット対が、RSTパケット対によって返答される。正規SYNパケットは、40バイトパケットであり、ペイロードデータを有さない。gMeasureツールは、大きいペイロード(たとえば、1460バイト)をそれぞれ送ったSYNパケットにアペンドする。しかし、返答されたRSTパケットは、小さいパケット(40バイト)であり、逆経路上のボトルネックリンクで待ち行列に入れられている可能性は低い。ローカルホストで、gMeasureツールは、受け取ったRSTパケット対の時間分散を、SYNパケット対のリモートホスト時間分散に対する概算として使用する。このパケット交換が、リモートホストでの正しいTCPの実施のみに頼り、ダウンストリームのボトルネック帯域幅を測定するのに十分であることに留意されたい。あるネットワークリンク(たとえば、モデム回線)で、パケットは、リンクをトラバースする前に、圧縮される。この影響により、パケットサイズが変わり、パケット対測定の精度が損なわれる。したがって、gMeasureツールは、事前圧縮されたペイロードをSYNパケットにアペンドして、パケットサイズに対する圧縮の影響を最小限に押さえる。
【００７７】
gMeasureツールは、そのプロービングトラフィックを形作って、測定したネットワーク経路の状態についての情報を明らかにする。図13に示すように、本発明によるgMeasureツールは、その途中に大きいパケット対250a-d(たとえば、約1500バイト)が置かれている、小さい40バイトのSYNパケット248a-dのトレーン246を送る。リモートエンドホスト252は、RSTパケットの同じサイズトレーン254で返答する。gMeasureツールは、トレーン254内のパケット264-274の時間分散を分析し、クロストラフィックリンク、再順序付けリンク、またはマルチチャネルリンクの存在を判断する、2つの発見的方法を使用する。
【００７８】
第1の発見的方法では、プロービングホスト256でgMeasureツールは、RSTパケットのシーケンスナンバを使用して、送ったSYNパケットの順序付けに対して、受け取ったパケットの順序付けが、保存されているかどうかを判断する。パケットが再順序付けされた場合は、gMeasureツールは、測定を捨て、未知の推定値を返す。第2の発見的方法では、RSTパケットが再順序付けされていない場合、トレーンの途中にある、2つのRSTパケット268、270の時間分散258は、小さい方の40バイトパケット対264および266と、272および274のいずれかの分散260および262より大きくなければならない。そうでない場合は、良くないパケットが、40バイトパケット対の間に置かれる可能性が高い。このことは、プロービングオペレーションのプロービング中のクロストラフィックの存在を示している。次いで、gMeasureツールは、測定を捨て、未知の推定値を返す。
【００７９】
本発明によるさまざまな実施形態についての上記の記述は、例示および説明がその目的である。本発明を、開示されている正確な実施形態に限定したり、制限したりするものではない。上記の教示から見て、数々の修正形態や変形形態が可能である。記載した実施形態は、本発明の原理および実際的な適用形態を最も良く例示するために選び、記述したものであり、それにより、当業者は、本発明を、想定される特定の使用に合ったさまざまな実施形態およびさまざまな修正形態で利用できるようになる。このようなすべての修正形態および変形形態は、公正に、法的に、公平に権利を有する範囲内において解釈される場合に、特許請求の範囲で定められるように本発明の範囲に包含される。
【図面の簡単な説明】
【図１】本発明が常駐するコンピュータシステムの例を一般に示すブロック図である。
【図２】本発明の教示に従って、組織化され動作している、分散型プロービンググループを簡単に示す図である。
【図３】本発明の教示に従って、段に分かれた方式で組織化され動作している、図2に示した分散型プロービンググループを簡単に示す図である。
【図４】本発明の教示に従って、新しいホストを含むために組織化され動作している、図2に示した分散型プロービンググループを簡単に示す図である。
【図５】本発明の教示に従って、新しいホストを含んだ後、プロービンググループを再生するために組織化され動作している、図4に示した分散型プロービンググループを簡単に示す図である。
【図６】本発明の教示に従って、既存のプロービンググループを置く方法を簡単に示すフローチャートである。
【図７】本発明の教示に従って、プロービンググループに結合する方法を簡単に示すフローチャートである。
【図８】本発明の教示に従って、プロービンググループを形成する方法を簡単に示すフローチャートである。
【図９】本発明の教示に従って、ホストが新しいプロービンググループにジャンプする方法を簡単に示すフローチャートである。
【図１０】本発明の教示に従って、ホストが新しいプロービンググループにジャンプする代替方法を簡単に示すフローチャートである。
【図１１】本発明の教示に従って、プロービンググループのための新しいリーダを推奨する方法を簡単に示すフローチャートである。
【図１２】本発明の教示に従って、効率を向上するために、小さいプロービンググループをより大きいプロービンググループと併合する方法を簡単に示すフローチャートである。
【図１３】本発明の教示に従って、パケットトレーンプロービングアプローチを簡単に示す通信フローチャートである。
【符号の説明】
100  計算システム環境
110  コンピュータ
120  処理ユニット
121  システムバス
130  システムメモリ
131  読取専用メモリ(ROM)
132  ランダムアクセスメモリ(RAM)
133  基本入出力システム(BIOS)
134、144  オペレーティングシステム
135、145  アプリケーションプログラム
136、146  他のプログラムモジュール
137  プログラムデータ
140  インターフェイス
141  ハードディスクドライブ
147  プログラムデータ
152  取外し可能、不揮発性磁気ディスク
156  取外し可能、不揮発性光学ディスク
155  光学ディスクドライブ
160  ユーザ入力インターフェイス
161  ポインティングデバイス
162  キーボード
170  アダプタ
171  ローカルエリアネットワーク(LAN)
172  モデム
173  ワイドエリアネットワーク(WAN)
180  リモートコンピュータ
181  記憶装置デバイス
185  リモートアプリケーションプログラム
190  ビデオインターフェイス
191  モニタ
195  出力周辺インターフェイス
197  スピーカ
196  プリンタ
l98  大規模ネットワーク
200-2l0  プロービンググループ
212-222  グループリーダ
224  ホスト
226  リモートホスト
214、228、230  他のホスト
232  第2の段グループ
206'  再生されたグループ
242  プロセスが開始する
244  マルチキャストグループMに結合する
246  要求メッセージを送出する
248  応答メッセージを受け取る
250  マルチキャストグループMを去る
252  MeGroupXと結合する
248  応答メッセージを受け取らない
256  新しいMeGroupを形成する
254  プロセスが終了する
258  開始する
260  MeGroupXのマルチキャストグループに結合する
264  MeGroupX内の他のメンバホストについて知る
268  プロセスが開始する
270  マルチキャストグループMに結合する
272  新しいホストが結合してくるのを待つ
274  マルチキャストグループを確立する
276  プロセスが終了する
280  費用関数C(A,Gi)を判断する
278  プロセスが開始する
282  費用関数C(A,Gx)を計算する
284  より適切なグループxを発見する
286  新しいグループに結合する
288  プロセスが終了する
290  プロセスが開始する
292  計算する
300  終了する
298  グループxに結合する
304  ホスト間の距離を計算する
306  最も適切なホストであるかを判断する
308  新しいリーダになる気があるかどうかを、その候補ホストに尋ねる
310  同意する
312  選択のプロセスが終了する
310  ホストが同意しない
314  より適切なホストが1つを超える数いる
308  最も適切な候補ホストに新しいリーダになるかを尋ねる
314  これ以上適切なホストがいない
316  現在のリーダがリーダに留まることができる
312  プロセスが終了する
318  解散する
320  開始する
232  判断する
234  近接のグループを発見する
236  結合することを受け入れるかどうかを尋ねる
238  同意する
240  メッセージを送る
238  同意しない
242  終了する
244  グループを解散する
250a-d  大きいパケット対
248a-d  SYNパケット
252  リモートエンドホスト
254  RSTパケットの同じサイズトレーン
264-274  パケット
254  トレーン
256  プロービングホスト
268、270  RSTパケット
258、260、262  時間分散
264および266、272および274  バイトパケット対
【図１】
0004226922.tif 000003
【図２】
0004226922.tif 000004
【図３】
0004226922.tif 000005
【図４】
0004226922.tif 000006
【図５】
0004226922.tif 000007
【図６】
0004226922.tif 000008
【図７】
0004226922.tif 000009
【図８】
0004226922.tif 000010
【図９】
0004226922.tif 000011
【図１０】
0004226922.tif 000012
【図１１】
0004226922.tif 000013
【図１２】
0004226922.tif 000014
【図１３】
0004226922.tif 000015