(57)【要約】【課題】本発明はコンピュータネットワークの動作を検査および予測する方法に関連する。【解決方法】その方法は、ａ）ルータと、それぞれがソースに関連したトラフィッククラスを含むネットワーク構成の使用とを含むネットワークを記憶し、ｂ）ネットワーク内での速度の展開をシミュレーションするために、選択した初期条件（４００）に基づいて、トラフィック展開の付加的増加かつ倍数的減少モデル（４１０、４２０）を反復的に付加し、各々の瞬間において、一組のクラスまたはソース速度変数を記憶し、ｃ）工程ｂ）での反復によって周期軌道（４３０）が生じた場合には、遭遇した一連のルータを損失に対して反応可能であるものとして検査しながら、既に遭遇した一組のクラスまたはソース速度変数へと戻ることで、各クラスまたはソース（４５０）によって得た速度を評価することで構成されている。
2005510129.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータネットワークの動作を検査および予測する方法であって、
ａ）一方で、ルータ（ｒ）と、その特定の送信特性（Ｃ、Ａ１−２）と、ルータ間の推移回数とを備えたネットワーク（８）の表示を記憶し、他方で、トラフィッククラスを備えたネットワーク（９）の使用構成を記憶し、前記トラフィッククラスのそれぞれには多数のソース（ＳＮ、Ａ２−３）とルータを通る経路（ＳＲ、Ａ２−４）とが割り当てられた状態であり、
ｂ）前記ネットワーク内のスループット速度の展開をシミュレーションするために、選択した初期条件（４００）に基づいて、付加的増加かつ倍数的減少タイプのトラフィック展開モデル（４１０、４２０）を反復的に適用し、それぞれの瞬間において一組のクラスまたはソース速度変数を記憶し、
ｃ）工程ｂ）で反復が周期軌道（４３０）をもたらす場合には、既に遭遇した一組のクラスまたはソース速度変数に実質的に戻り、各クラスまたはソース（４５０）によって得られた速度を評価するための損失の原因になるように遭遇したルータの級数を検査することを特徴とする方法。
【請求項２】
前記工程ｂの反復回数がしきい値（４３０）に達すると、前記工程ｃ）が実施されることを特徴とする請求項１に記載の方法。
【請求項３】
前記工程ｂ）が、
ｂ１）各ルータについて、仮想内部混雑時間（ｔａｕ＿ｎ〔ｒ〕，Ａ３−６）を計算および記憶することをさらに有することを特徴とする請求項１または２に記載の方法。
【請求項４】
前記工程ｂ１）が、前記ネットワーク（ｔａｕ＿ｎ〔ｒ〕，Ａ３−５）の効率的な内部混雑時間として最小仮想内部混雑時間を計算することをさらに有することを特徴とする請求項３に記載の方法。
【請求項５】
前記工程ｂ）が、
ｂ２）各々の所定の瞬間において、前記経路が、混雑したルータ（ｘ＿ｎ〔ｓ〕、ｘ＿ｎ〔ｓ〕）を通過するクラスのうち少なくとも１個の速度を計算および記憶することをさらに有することを特徴とする請求項３または４に記載の方法。
【請求項６】
前記工程ｂ２）において前記混雑したルータが選択されて、前記混雑したルータが所定の条件を確認可能なようにし、該条件には、前記ネットワーク（ｔａｕ＿ｎ，Ａ３−５）の内部混雑時間が、この混雑したルータの仮想内部混雑時間（ｔａｕ＿ｎ〔ｒ〕，Ａ３−６）に等しいことを含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記工程ｂ２）における前記所定の条件は、前記ルータがトラフィッククラスによって規定された所定の経路上に在るルータのうちの１個であることを含むことを特徴とする請求項５または６に記載の方法。
【請求項８】
前記工程ａ）が、各ルータについて、容量値（Ｃ，Ａ１−２）と、バッファメモリサイズ値（Ｂ，Ａ１−３）と、タイプ表示（ＲＴ，Ａ１−５）とを、ルータ間の真の伝播時間の値と共に備えていることを特徴とする請求項１〜７のうちいずれか１項に記載の方法。
【請求項９】
前記工程ａ）は、各トラフィッククラスについて、クラス（ＳＮ，Ａ２−３）毎の多数のソースと、ソースから宛先（ＳＲ，Ａ２−４）までの経路と、タイプ表示（ＳＴ，Ａ２−２）とを備えるとともに、一方でソースとアクセスルータ（ＳＢ，Ａ２−５）との間の伝播時間の値、および、他方で端末アクセスルータと宛先（ＳＥ，Ａ２−６）との間の伝播時間の値とを共に備えていることを特徴とする請求項１〜８のうちいずれか１項に記載の方法。
【請求項１０】
前記工程ｂ）における前記トラフィック展開モデルは、所定のルータ（Ｎ〔ｒ〕，Ａ３−３）を使用するソースの個数と、前記ソースから前記宛先までの規定されたクラスのラウンドトリップ時間（ｒｔｔ，Ａ３−４）とを含む変数を備えることを特徴とする請求項１〜９のうちいずれか１項に記載の方法。
【請求項１１】
前記工程ｂ）における前記トラフィック展開モデルは、初期条件に従って規定される変数を含み、前記変数は、ルータのスループット速度の平均値と、このルータを共用する各ソースに論理的に使用可能な値（ｃ（ｒ），Ｂ０−２）と、ルータを共用する前記ソースの総数に対するクラス内の多数のソースを表す比率値（ａ（ｓ，ｒ），Ｂ０−３）と、前記ソースから、二乗された宛先までのラウンドトリップ時間に対する比率値の割合のクラスの合計を表すルータの加速度（ｍ−ｒｔｔ〔ｒ〕，Ｂ０−４）と、同期速度（ｐ，Ｃ１−１；Ｃ２−１）とを含むことを特徴とする請求項１〜１０のうちいずれか１項に記載の方法。
【請求項１２】
前記工程ｂ）が、付録Ｂ１−３と本質的に一致する数学公式を含むことを特徴とする請求項１〜１１のうちいずれか１項に記載の方法。
【請求項１３】
前記同期速度が、前記速度と無関係に予測されることを特徴とする請求項１０に記載の方法。
【請求項１４】
前記同期速度が、パケット損失の可能性Ｌを含めて、付録Ｃ１−１で示された前記数学公式と一致するように予測されることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記同期速度（ｐ）が、付録Ｃ１−１中の数学公式に従って前記速度に依存するように予測されることを特徴とする請求項１０に記載の方法。
【請求項１６】
前記同期速度（ｐ）が、パケット損失Ｌの可能性を含めて、付録Ｃ２−１中の前記数学公式に従って予測されることを特徴とする請求項１５に記載の方法。
【請求項１７】
前記パケット損失Ｌの可能性が、付録Ｃ１−２中の数学公式に従って予測されることを特徴とする請求項１２または１４に記載の方法。
【請求項１８】
前記パケット損失Ｌの可能性が、付録Ｃ３−１中の数学公式に従って予測されることを特徴とする請求項１５または１６に記載の方法。
【請求項１９】
前記同期速度が、独立したシミュレーションによって計算されることを特徴とする請求項１〜１８のうちのいずれか１項に記載の方法。
【請求項２０】
前記セッションが、ＴＣＰタイプのプロトコルによって制御されるフローを表すことを特徴とする請求項１〜１９のうちのいずれか１項に記載の方法。
【請求項２１】
前記工程ｂ）が、各ルータおよび各クラスについて反復的に実行されることを特徴とする請求項３に記載の方法。
【請求項２２】
コンピュータネットワークの動作を検査および予測する装置であって、
メモリ（４）と処理モジュール（３）を備えており、
前記メモリ（４）が、
ルータ（ｒ）と、その特定の送信特性（Ｃ，Ａ１−２）と、ルータ間の推移回数とを含む前記ネットワーク（８）のパラメータと、
それぞれが多数のソース（ＳＮ，Ａ２−３）と前記ルータを通る経路（ＳＲ，Ａ２−４）とに関連されるトラフィッククラスを含む前記ネットワーク（９）の使用構成パラメータと、
付加的増加かつ倍数的減少タイプ（ＡＩＭＤ）のトラフィック展開モデルに基づいた計算モジュール（５）とを記憶するように設計されており、
前記処理モジュール（３）が、
選択した初期条件に基づいて、ネットワーク内のスループット速度の展開をシミュレーションするために、各々の瞬間において一組のクラスまたはソース速度変数（Ｉ）を記憶する際に、前記付加的増加かつ倍数的減少タイプ（ＡＩＭＤ）のトラフィック展開モデルを反復的に付加するように設計され、
既に遭遇した一組のクラスまたはソース速度変数（Ｉ）へ実質的に回帰する周期軌道が得られると、前記トラフィック展開モデルの反復的な適用を中止するように設計され、
各クラスまたはソースによって得られた前記速度を評価するための損失の原因となるように遭遇されたルータの級数を検査するように設計されていることを特徴とする装置。
【請求項２３】
前記処理モジュール（３）は、反復回数がしきい値に達すると、前記トラフィック展開モジュールの反復的な適用を停止するように設計されていることを特徴とする請求項２２に記載の装置。
【請求項２４】
前記処理モジュール（３）は、各ルータについて仮想内部混雑時間（ｔａｕ＿ｎ〔ｒ〕、Ａ３−６）を計算および記憶するように設計されていることを特徴とする請求項２２または２３に記載の装置。
【請求項２５】
前記処理モジュールは、前記ネットワークの効率的な内部混雑時間（ｔａｕ＿ｎ，Ａ３−５）として最小の仮想内部混雑時間を計算および記憶するように設計されていることを特徴とする請求項２４に記載の装置。
【請求項２６】
前記処理モジュールはさらに、経路が混雑したルータを通過するクラスの速度値（ｘ＿ｎ〔ｓ〕，Ｘ＿ｎ〔ｓ〕）を計算および記憶するように設計されていることを特徴とする請求項２４または２５に記載の装置。
【請求項２７】
選択された前記ルータは、前記ネットワークの内部混雑時間（ｔａｕ＿ｎ，Ａ３−５）が、そのルータの仮想内部混雑時間（ｔａｕ＿ｎ〔ｒ〕，Ａ３−６）に等しいことを含む所定の条件を証明できるように選択されていることを特徴とする請求項２６に記載の装置。
【請求項２８】
前記所定の条件は、前記ルータがトラフィッククラスによって規定された所定の経路上に在るルータのうちの１個であることを有することを特徴とする請求項２７に記載の装置。
【請求項２９】
各ルータが、容量値（Ｃ，Ａ１−２）と、バッファメモリサイズ値（Ｂ，Ａ１−３）と、タイプ表示（ＲＴ，Ａ１−５）とを、ルータ間の正の伝播時間の値と共に有することを特徴とする請求項２２〜２８のうちのいずれか１項に記載の装置。
【請求項３０】
各トラフィッククラスが、クラス毎の多数のソース（ＳＮ，Ａ２−３）と、ソースから宛先までの経路（ＳＲ，Ａ２−４）と、タイプ表示（ＳＴ，Ａ２−２）とを備えるとともに、一方でソースとアクセスルータの間（ＳＢ，Ａ２−５）の伝播時間の値と、他方で端末アクセスルータと宛先との間（ＳＥ，Ａ２−６）の伝播時間の値とを共に有することを特徴とする請求項２２〜２９のいずれか１項に記載の装置。
【請求項３１】
前記トラフィック展開モデルは、所定のルータを使用するソースの個数を含む変数（Ｎ〔ｒ〕，Ａ３−３）と、前記ソースから宛先まで規定されたクラスのラウンドトリップ時間（ｒｔｔ、Ａ３−４）とを有することを特徴とする請求項２２〜３０のうちのいずれか１項に記載の装置。
【請求項３２】
前記トラフィック展開モデルが、初期条件に従って規定された変数を含み、前記変数は、ルータのスループット速度の平均値と、このルータを共用している各ソースに理論的に使用可能な値（ｃ（ｒ）、Ｂ０−２）と、ルータを共用しているソースの総数に対するクラス内のソースの数を表す比例値（ａ（ｓ，ｒ），Ｂ０−３）と、前記ソースから、二乗された宛先までのラウンドトリップ時間に対する比率値の比率のクラスの合計を表すルータの加速値と、同期速度とを有することを特徴とする請求項２２〜３１のうちのいずれか１項に記載の装置。
【請求項３３】
経路が混雑したルータを通過するクラスの比率値（ｘ＿ｎ〔ｓ〕＝Ｘ＿ｎ〔ｓ〕）の前記計算および記憶が、付録Ｂ１−５と本質的に一致する数学公式に従って実行されることを特徴とする請求項１２に記載の装置。
【請求項３４】
前記同期速度が前記速度と無関係に予測されることを特徴とする請求項１０に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複合システムの監視およびシミュレーションに関する。顕著なものとしてインターネットタイプの通信ネットワークにおけるフロー制御と混雑制御に関連して、ネットワークパラメータのインパクトの決定を考慮してフロー分析が実施される。
【背景技術】
【０００２】
様々な提案が提起されてきた。これらのうち最新のものには以下を含む：
［１］Mathis, M., Semske, J., Mahdavi, J., Ott, T. (1997) "The Macroscopic Behavior of the TCP Congestion Communication Review", 27(3), No. 4155, July 97
［２］国際特許出願WO 01/65 772 A1
［３］Baccelli, F. and Hong, D. "A.I.M.D., Fairness and Fractal Scaling of TCP Traffic", Technical Report, RR-1455, INRIA Rocquencourt, April 2001
［４］Hong, D., Lebedev D., "Many TCP User Asymptotic Analysis of the AIMD Model", Technical Report, RR-4229, INRIA, Rocquencourt, July 2001
［１］はパケット損失の可能性に関連して、ＴＣＰにより制御されたソースのスループット速度を評価するための定式を提案する。
〔２〕は、通信ネットワークのような複合システムと、とりわけフロー制御および混雑制御との、いわゆる「マックスプラス」代数による表示を提案する。この「マックスプラス」代数により、複数のノードを考慮しながら、ネットワークパラメータのランダムキャラクタを可能にする手段が得られる。しかしながら、〔２〕は、ＴＣＰタイプのプロトコルを用いる単一のソースのみを考慮する。
文献〔３〕および〔４〕は、共通のルータを共用する一組のＴＣＰソースにおけるスループット速度の組み合わせ展開を理解するように設計されたエレメンタリモデルを提案する。提案された付加的増加かつ倍数的減少モデル（additive increase and multiplicative decrease）（ＡＩＭＤ）によって、共用ルータの損失の同期による性能ペナルティを評価することが可能になる。しかしながら、１個のパラメータ、つまりこの同期の確立関数の可能性は未知のままである。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
さらに、提案されたモデルは、数台のルータと１個の制御されたソースとの表示、または、ＴＣＰで制御された数個のソース間で共用される１台のルータのいずれかに限定される。
【０００４】
さらに、これらＴＣＰ制御されたネットワークの監視およびシミュレーションシステムは、ソースによって得られたスループット速度の予測に関連して独自のものではない。すなわち、これらは、例えば、〔１〕または〔２〕における損失の可能性、あるいは、〔３〕または〔４〕における同期原理のような、実際のネットワーク上で行われる物理的監視の必要性を欠いては実現不可能である。したがって、特にワイドエリアネットワーク内で、信頼の合理的な程度を有する可能性のケースの全てを網羅することは殆ど不可能である。
【課題を解決するための手段】
【０００５】
本発明はこの状況を改善することを目的とする。
【０００６】
本発明は、コンピュータネットワークの動作を検査および予測する方法に関するものであり、その方法は、
ａ）一方で、ルータと、その特定の送信特性と、ルータ間の推移回数とを備えたネットワークの表示を記憶し、他方で、トラフィッククラスを備えたネットワークの使用構成を記憶し、前記トラフィッククラスのそれぞれには多数のソースとルータを通る経路とが割り当てられた状態であり、
ｂ）前記ネットワーク内のスループット速度の展開をシミュレーションするために、選択した初期条件に基づいて、付加的増加かつ倍数的減少タイプのトラフィック展開モデルを反復的に適用し、それぞれの瞬間において一組のクラスまたはソース速度変数を記憶し、
ｃ）工程ｂ）で反復が周期軌道をもたらす場合には、既に遭遇した一組のクラスまたはソース速度変数に実質的に戻り、各クラスまたはソースによって得られた速度を評価するための損失の原因になるように遭遇したルータの級数を検査することを特徴とする。
【０００７】
本発明はさらにコンピュータネットワークの動作を検査および予測する装置に関する。
【０００８】
本発明の主要な特徴は、
メモリと処理モジュールを備えており、
前記メモリが、
ルータと、その特定の送信特性と、ルータ間の推移回数とを含む前記ネットワークのパラメータと、
それぞれが多数のソースと前記ルータを通る経路とに関連されるトラフィッククラスを含む前記ネットワークの使用構成パラメータと、
付加的増加かつ倍数的減少タイプのトラフィック展開モデルに基づいた計算モジュールとを記憶するように設計されており、
前記処理モジュールが、
選択した初期条件に基づいて、ネットワーク内のスループット速度の展開をシミュレーションするために、各々の瞬間において一組のクラスまたはソース速度変数を記憶する際に、前記付加的増加かつ倍数的減少タイプのトラフィック展開モデルを反復的に付加するように設計され、
既に遭遇した一組のクラスまたはソース速度変数へ実質的に回帰する周期軌道が得られると、前記トラフィック展開モデルの反復的な適用を中止するように設計され、
各クラスまたはソースによって得られた前記速度を評価するための損失の原因となるように遭遇されたルータの級数を検査するように設計されていることを特徴とする。
【０００９】
本発明のこれ以外の特徴および利点は、添付の図面を参照しながら、以下の詳細な記述を理解することで明白になるだろう。
【発明を実施するための最良の形態】
【００１０】
添付図面および付録には、本質的に、特性の点で確かな要素が含まれる。したがって、これらは、本明細書の記述を理解する上で補助となるだけでなく、適用可能な本発明の定義にも貢献する。
【００１１】
以下の記述は、使用される付加的増加かつ倍数的減少（ＡＩＭＤ）モデルのタイプに関して文献[２]を言及する。この基本モデルを使用して、或るコンピュータネットワーク内で共通のルータを共用する１組のＴＣＰソースのスループット速度の組み合わせ展開を表示する。
【００１２】
記述中で、表記ｖ[ｊ]は、各々の値ｊに対してある値を有するテーブル変数またはベクトル（「アレイ」）を示す。２次元ｖ[ｉ,ｊ]を伴う変数はマトリックスとして表される。
【００１３】
図１は、モニタ７と、キーボードまたはマウスのような入力装置６とに接続されたシステムユニット１を備える計算環境を示している。システムユニット１はさらに、モニタ７上でのデータの表示を扱うように設定されたグラフィックカードＧＵＩ２とも接続されている。本発明によれば、システムユニット１は、メモリ４に接続された処理モジュール３に関連して動作することが可能である。メモリ４は、ネットワーク表示に関するデータ８と、ネットワークの使用構成に関するデータ９とを記憶する。これらのデータは以下でより詳細に説明される。メモリ４は、処理モジュール３に関連して動作する計算モジュール５を備えている。この処理モジュール３は、付加的増加かつ倍数的減少タイプのトラフィック展開モデルを反復的に付加して、ネットワークルータにおけるスループット速度の展開をシミュレーションするように設計されている。各々のアプリケーション（応用）では、処理モジュールは、１組のネットワーク速度変数の記憶を要求して、次の混雑期間を予測しこの予測される混雑を改善する位置にあるように設計されている。この記述は主に、例えばＴＣＰフローのようなフロー性能の予測と、マルチルータトポロジーにおけるサービス品質（ＱｏＳ）とに関する。換言すれば、本発明の装置および方法は、とりわけ、例えばＴＣＰタイプのプロトコルによって制御される多数のソースが数台のルータを共用している場合に使用される。このシミュレーションは、付加的増加かつ倍数的減少（ＡＩＭＤ）タイプモデルの流動的な記述に基づいている。
【００１４】
図２は、本発明で使用されるタイプのコンピュータネットワークを示す。したがって、ネットワークは数台のルータｒ０、ｒ１、ｒ２、ｒ３、およびｒ４で構成されており、ルータｒ０はアクセスルータである。ルータはリンクによって相互接続され、Ｔ１がｒ０をｒ３に接続し、ｔ２がｒ０をｒ２に接続し、Ｔ３がｒ３をｒ４に接続し、Ｔ４がｒ０をｒ４に接続し、Ｔ５がｒ３をｒ４に接続し、Ｔ６がｒ０をｒ１に接続するにしている。
【００１５】
符号Ｉ１、Ｉ２、Ｉ３で表された多数のソース１、２、３と、符号Ｄ１、Ｄ２、Ｄ３で表された宛先１、２、３とが図２で示されている。ソースは、アクセスルータｒ０を介してネットワークに接続されている。その宛先は、アクセスルータｒ４、ｒ２、ｒ３を介してネットワークにそれぞれ接続されている。
【００１６】
本発明の記述は、（トラフィックの）クラスの概念を使用している。さしあたり、クラスは、経路と、その経路上で進み得る送信の特定の性質とによって定義される。
【００１７】
異なる経路を取ってソースを宛先に接続することができる。同一経路を異なるクラスに関連付けることが可能である。経路はクラスの「タイプ」に関連する。クラス「タイプ」は、経路を定義する１組のクラス、または、あるクラスの同じエンド・トゥー・エンド経路に関連する（付録Ａ２およびＡ３）。したがって、ソースＳのうち１個をＤ１に接続する経路に対して、少なくとも２個のクラスタイプが定義される。つまり、一方は経路（Ｔ４）を定義し、他方は経路（Ｔ５、Ｔ３）を定義し中間ルータｒ３を通過する。また、ソースＳのうち１個をＤ２に接続する経路に対して、少なくとも２個のクラスタイプが定義される。つまり、一方は経路（Ｔ２）を定義し、他方は経路（Ｔ１、Ｔ２）を定義し中間ルータｒ２を通過する。ソースＳのうち１個をＤ３に接続する経路に対して、少なくとも２個のクラスタイプが定義される。つまり、一方は経路（Ｔ５）を定義し、他方は経路（Ｔ４、Ｔ３）を定義し中間ルータｒ４を通過する。
【００１８】
クラスは経路、セッションタイプ、伝播時間、および多数のソースによって定義される。付録Ａ２を参照すると、クラスは、例えばデータセットＳＴ、ＳＮ、ＳＲ、ＳＢ、ＳＥによって定義される。より明確には、所定のクラス‘ｓ’において、ＳＮ〔ｓ〕＝１００である場合、クラスＶに属する１００個のソースが以下のように同じ特性を有する：
同一のセッションタイプＦＴＰ（ファイル転送プロトコル）またはＨＴＴＰ（ハイパーテキスト転送プロトコル）、
同一のエンド・トゥー・エンド経路、したがって、特に、ＲＴＴ（＝ｒｔｔ〔ｓ〕）で与えられる同一のラウンドトリップ時間（付録Ａ３およびＡ４）。
【００１９】
この記述の残りの部分では、クラスが変数ｓで示され、ルータが変数ｒで示される。クラスｓ、ｓ’の各々が、以前に図示されているように、同一のソースから同一の宛先まで延びる経路を定義するが、異なるセッションを有する場合には、同一のソースがクラスｓのソース、および、クラスｓ’のソースとして指定可能である。さらに、同じクラスに対して幾つかのソースが存在する。すなわち、それらの宛先に到達する同一の経路を有する幾つかのソースが存在する。
【００２０】
用語「混雑エポックｎ」は、各クラスｓのスループット速度が計算される（これらの速度はクラスｓの各ソースｉと等しい）瞬間ｎを表すものである。この「混雑エポックｎ」はさらに、ネットワークルータが「混雑する」または「混雑状態」にあるとされる瞬間、つまり、１個またはそれ以上のパケット損失を経験するルータを表す。
【００２１】
付録ＡのパートＡ１を参照すると、ネットワークパラメータは、Ａ１−１、Ａ１−２、Ａ１−３、Ａ１−４、Ａ１−５で定義されたルータのパラメータを示している。したがって、そのパケットのスループット速度を扱う能力によって定義されたルータは、出力フローを上回る入力フローの一部を保持する役割を持ったバッファメモリまたはバッファを含むことができる。ルータｒがバッファメモリを備えていない場合には、ルータのバッファメモリのサイズはゼロ、すなわちＢ〔ｒ〕＝０である。ルータは、例えば以下に示すような異なるタイプのものであってよい：
キューからオーバフローしたパケットを捨てる役割を果たすルータのタイプを表し、テールドロップとも呼ばれるＦＩＦＯ（先入れ先出し）またはＦＱ（フェアキュー）；
キューがオーバフローする際に、事前にパケットを破棄することが可能なルータのタイプを表すＲＥＤ（ランダムアーリー検出）。
【００２２】
付加的増加かつ倍数的減少（ＡＩＭＤ）タイプのトラフィック展開モデルの例では、変数が、付録ＡのパートＡ３を参照して定義される。
【００２３】
図３は、本発明によるネットワーク分析のシュミレーション処理を行う例示的な実施の形態を示す。この処理は、先行の例で提案されたＡＩＭＤトラフィック展開モデルに関して付録Ａ、Ｂ、Ｃ、およびＤに言及する。
【００２４】
したがって、ステップ４００で付録ＢのパートＢ０を参照すると、モデルの特定変数が以下のように初期化される：
Ｂ０−１において、マトリックスｐ〔ｓ、ｒ〕の各要素はパケット損失の同期の可能性（確立）を表しており、その可能性は、この場合にはベルヌーイの法則に従って事前に定義されたと考えられる０と１の間で定義される同期速度として呼ばれる。０．５に等しいランダム変数ガンマ〔ｓ、ｒ〕の値は、「先頭または後尾」タイプの可能性法則を表し；
Ｂ０−２において、ベクトルｃ〔ｒ〕の各要素は、或るルータの総容量がルータｒを使用してソース間で理想的に共用された場合に、ソースがそのルータから得ることができる容量（１秒当たりのパケット数）を表し；
Ｂ０−３において、マトリックスａ〔ｓ、ｒ〕の各要素は、ルータｒを使用したソース個数に対するクラスｓのソース個数の比例を表し；
Ｂ０−４において、ベクトルｍ−ｒｒｔ〔ｒ〕の各要素は、要素ａ〔ｓ、ｒ〕のｓの合計を表し、それぞれは、二乗されていると思われるクラス内のその最小ラウンドトリップ時間によって分割され；
Ｂ０−５において、マトリックスｇ〔ｓ、ｒ〕の各要素は、同期速度に関して計算された０と１の間の整数を表し；
Ｂ０−６において、初期化位相は、初期条件を記述する所定関数Ｆ（）を使って全クラスと、１〜Ｎ（ｎおよびＮは整数）まで変化する全ての混雑エポックｎとについての平均スループット速度を初期化することを伴う。この関数は、全てのクラスｓについて、例えば、ｆ（ｓ）＝０となるようにすることが可能である。ｆ（）には１つの制約がある：この関数は、任意の‘ｒ’に対して付録Ｂ０で定義されるようなステップ１にてｔａｕ＿１〔ｘ〕が正あるいはゼロでなければならない。これが意味することは、初期ロードがネットワーク容量と互換性がなければならないことである。
【００２５】
以下の仮定がなされた場合には公式Ｂ０およびＢ１が事前に定義される：
ルータがヌルサイズのバッファメモリを有する。
【００２６】
さらに、この処理の実施の形態の例では、Ａ１−５において使用されるルータのタイプはＦＩＦＯタイプであり、Ａ２−２においてセッションタイプはＦＴＰである。
【００２７】
ステップ４１０、４２０、４３０は、以下で定義されるステップ１、２、３の各々の混雑期間において付録Ｂ１−０に従って反復を示す。
【００２８】
ステップ４１０において、各ルータｒについて変数の処理が実行される。そのため、付録Ｂ１−１中のステップ１は、混雑エポックｎにおける各ルータｒについて、混雑期間ｎ−１に基づいて全クラスのクラスソース速度の合計を定義する。したがって、ｓｏｍ＿ｎ〔ｒ〕は、先行の反復の最後でルータ‘ｒ’上のロード（または速度）の合計を表す（最初の反復では、ｓｏｍ＿１〔ｒ〕は、初期条件によって定義されたルータ‘ｒ’上の合計ロードを示す）。ｔａｕ-ｎ〔ｒ〕の計算により、所定の混雑エポックｎ−１と、連続する混雑エポックｎとの間の時間が定義され、その時間は、各ルータＲの仮想内部混雑時間と呼ばれる。換言すれば、ｔａｕ-ｎ〔ｒ〕は、ルータ‘ｒ’の内部混雑の仮想期間であり、この仮想期間は、例えば、他の全てのルータが無限の容量も持つ（ｃ〔ｒ〕）場合には有効となる。
【００２９】
付録Ｂ１−２におけるステップ２は、ルータｒの一組の仮想内部混雑時間における最小内部混雑時間を決定するために使用され、また、ネットワーク内部混雑時間ｔａｕ＿ｎとも呼ばれる。この最小内部混雑時間は、古い混雑エポックと最新の混雑エポックとの間の時間を示す。換言すれば、ｔａｕ＿ｎの値によりネットワークの内部混雑時間が与えられる。
【００３０】
ステップ４２０において、各クラスｓについて平均スループット速度が処理される。そのため、付録Ｂ１−２中のステップ２において、ｎ番目の混雑エポックにおける各クラスｓについて最新の平均スループットｘ＿ｎ〔ｓ〕が（１）にて計算される。（１）は、全てのソースに、直線的増加のメカニズム（ＡＩＭＤモデルを表す文書中に記述されているＡＩ）を適用する。ネットワークのｎ番目の混雑の絶対日付が、ｔｅｍｐｓ＿ｎの値によって与えられる。
【００３１】
それから、その仮想内部混雑時間がネットワークの内部損失時間と等しくクラス経路に属する（クラスのエンド・トゥー・エンド経路とも呼ばれる）ｎ番目のルータ、または、瞬間ｎでの混雑したルータと呼ばれるルータについて、当該混雑エポックｎにて定義された各クラスｓの新規の平均スループット速度ｘ＿ｎ〔ｓ〕が、付録Ｂ１−３のステップ３の（２）において計算される。混雑エポックｎの最中に、混雑したルータ（１台または複数台）で混雑、パケット損失、または、他の問題を回避するために、この新規に計算された平均速度ｘ＿ｎ〔ｓ〕は先行の平均速度よりも低くなる。新規の平均速度ｘ＿ｎ〔ｓ〕は、同期速度と、対応する古い平均速度とに関して計算される。付録Ｂ１-３中の（２）は、混雑したルータを通過するソースに、ＡＩＭＤメカニズムの倍数的減少（ＭＤ）メカニズムを平均として適用している。
【００３２】
ステップ４３０では、算出した速度が、既に遭遇されたスループット状態と一致するか否か、または、ステップ４１０、４２０での反復回数が指定反復回数（Ｂ１-０中のステップ０における変数Ｍａｘ＿ｉｔｅｒにより定義された回数）に達したか否かを決定するためにチェックが行われる。負の応答が得られた場合には、ステップ４１０、４２０の反復を継続してルータの次の最小内部仮想時間と、対応するスループット速度とを決定する。このステップ４１０、４２０の反復は、或るルータの内部混雑時間を計算するためのクラス合計と、複数のルータの内部混雑時間から見出される最小とを含む付録Ｄの数学的公式を例示し、各混雑エポックについてこれらの動作が繰り返される。したがって、γn+1で表示される同期マトリックスによって平均スループット速度が算出される。
【００３３】
ステップ４３０において正の反応が得られると、ベクトル漸化式は、ステップ４４０での周期軌道である解（所定の特定な仮定）を有する。この理論により、このような有限軌道の一意性および存在性が確保される。実際には、各ルータで混雑イベント（損失を生じる）が無限に頻繁に発生する場合、付録Ｄの公式に対する一意的な解が存在し、その解はベクトルｘ＿ｎ[]の初期条件とは無関係の有限期間ｎを有する。この解はいわゆる周期軌道として定義され、それは新規の反復サイクルの場合に見出される。この軌道は、タイプＢ１−４の有限級数によって特長付けられ、そのタイプの級数にはｒ＿ｎが混雑の生じたルータの級数（１個または複数個のパケット損失を生じる）であり、ｘ＿ｎ〔ｓ〕がクラスｓの平均速度の級数であり、ｔａｕ＿ｎがネットワークの内部混雑時間の級数であり、これらの級数はｎ個の混雑エポックで定義される。この離散的な時間軌道は、付録Ｂ１-５で定義した速度の線形によって、連続的な軌道を完全に定義する。これにより、瞬間速度処理の「スケルトン」が定義される。
【００３４】
本発明の変形では、この軌道を使って付加的増加かつ倍数的減少モデル以外のトラフィック展開モデルを決定することができる。
【００３５】
ステップ４５０では、平均速度が分析される。したがって、このステップでは、クラス毎のソース数が高い（ＳＮ）場合に、確率的なアプローチを用いて瞬間スループット速度が算出される。この場合には、瞬間スループット速度が、得られた平均速度の級数から計算される。先行の瞬間速度ｘ＿[ｎ−１]〔ｓ，ｉ〕に、瞬間ｎにおけるネットワークの内部混雑時間が加算される公式Ｂ２−１を用いて瞬間速度ｘ＿ｎ〔ｓ，ｉ〕が算出され、これが各クラスｓと各ソースｉとに対して行われる。クラスｓのＳＲ〔ｓ〕によって定義された経路に含まれる級数ｒ-ｎでの各々のルータについて、公式Ｂ２−２を用いて新規の瞬間速度ｘ＿ｎ〔ｓ，ｉ〕が算出される。ランダム可変ガンマ〔ｓ，ｒ〕が、混雑直前および直後にｘ＿ｎ〔ｓ，ｉ〕の速度の比率に対応している。
【００３６】
したがって、各クラスの瞬間速度の展開を決定し、それによってネットワークの性能を予測することが可能である。
【００３７】
最大反復数Ｍａｘ＿ｉｔｅｒの前に周期軌道が見つかった場合には、このように得られた軌道の処理から定常状態モードの結果が導出される。さらに、一時的モードの結果（例えば、定常状態モードを達成するのに必要とされる時間）も獲得可能である。最大反復数がＭａｘ＿ｉｔｅｒに達した時に反復が停止した場合には、周期軌道を見つけることなくｘ＿ｎの展開を追跡することにより定常モードがほぼ達成されたか否かを視覚的に見ることができる。この視覚化が難しい場合には、今もなお処理可能な一時的モードが得られる。この場合にも、定常モードへの収束時間が、シミュレーション時間ｔｅｍｐｓ＿[Ｍａｘ＿ｉｔｅｒ]よりも長い。最大反復数の典型的な値は、ネットワークのサイズとソースの数とに依存して１０3〜１０6の間である。
【００３８】
図４では、クラスｓの経路に属するルータの平均速度ｘの変化のグラフが、反復数４に対して算出された平均速度を表している。混雑エポックｎ＝１において、クラスｓの平均速度はｘ−１である。混雑エポックｎ＝２において、ポイントＡにおける平均速度が計算される。この例において、当該のルータの仮想内部混雑時間は、混雑エポック１と混雑エポック２との間でのネットワークの内部混雑時間に等しい。したがって、混雑エポックｎ＝２でクラスｓの経路に属する当該ルータについては、ルータの平均速度ｘ−２が、同期速度に関して計算され、ポイントＡ’に対応する。
【００３９】
混雑エポックｎ＝３では、ポイントＢにおける平均速度が算出される。この例では、当該のルータの仮想内部混雑時間は、混雑エポック２と混雑エポック３との間のネットワーク内部混雑時間に等しい。したがって、混雑エポックｎ＝３において当該クラスｓの経路に属するこのルータに対して、同期速度に関してポイントＢ’でルータの平均速度ｘ−３が計算される。
【００４０】
混雑エポックｎ＝４では、ポイントＣにおける平均速度が計算される。この例では、ルータの仮想内部混雑時間は、混雑エポック３と混雑エポック４との間のネットワークの内部混雑時間に等しくない。したがって、当該クラスｓの経路に属するこのルータについては、混雑（パケット損失により生じるもの）は発生せず、平均速度ｘ−４はポイントＣで計算されたものである。
【００４１】
混雑エポックｎ＝５では、ポイントＤにおける平均速度が計算される。この例では、ルータの仮想内部混雑時間は、混雑エポック４と混雑エポック５との間のネットワークの仮想内部混雑時間に等しい。したがって、混雑エポックｎ＝５において、当該クラスｓの経路に属するこのルータについて、同期速度に関してポイントＤ’でルータの平均速度が計算される。
【００４２】
この平均速度ｘ−５が平均速度ｘ−１に等しいので、および、このルータが属する他のクラスと、ネットワーク内の他のルータとに平均速度ｘ−５が当てはまるので、捜し求められた周期軌道を一組の平均速度が規定する。
【００４３】
次に、図３に示すフロー図の変形例が、付録Ｂ３およびＢ４を参照しながら説明される。提案されたアルゴリズムは、クラスＳＮごとにソースの数が小さい値である場合、つまり、１００個のソースよりも低い値である場合に、瞬間速度を計算するための直接的な手順である。
【００４４】
したがって、付録Ｂ３中のステップ０において瞬間速度の初期化が実行される。各々の瞬間速度ｘ−ｎ〔ｓ，ｉ〕は関数Ｆ（ｓ，ｉ）の値を取る。この値は、所定の固定値、またはランダム選択によって得た値のいずれかである。先行と同様に、付録Ｂ４-０における反復は、付録Ｂ４-１、Ｂ４-２、Ｂ４-３におけるステップ１、２、３の反復に対応している。この代替的な実施の形態では、周期軌道が得られるまで待機しない。最大反復数の値Ｍａｘ＿ｉｔｅｒは、例えばネットワークが分析される時間長（ｔｅｍｐｓ＿[Ｍａｘ＿ｉｔｅｒ]）に従って変化し、または、シミュレーション時間のような実際の制約に関して変化する。先行と同様に、「後天的な」ビジュアルグラフィック観察により、定常状態モードが達成されたか否かに関して何らかの概念が与えられる。
【００４５】
したがって、付録Ｂ４-１におけるステップ１は、各ルータの仮想内部混雑時間を計算し、速度ｘ＿ｎは（０ｂにおいて）確立論的になる。付録Ｂ４-２におけるステップ２は、ネットワークの仮想内部混雑時間を計算し、また、（１ｂ）においてｎ番目の混雑エポックでの各クラスの最新瞬間速度ｘ＿ｎ〔ｓ〕を計算する。（１ｂ）は、線形的な増加のメカニズム（ＡＩＭＤモデルを表す文書中に記載されたＡＩ）を全てのソースに適用する。
【００４６】
付録Ｂ４-３におけるステップ３では、ＡＩＭＤメカニズムの倍数的減少要素（ＭＤ）が、（２ｂにおける）混雑したルータを通過するソースの瞬間速度に適用される。
【００４７】
次に、図３に示すフロー図のさらなる変形例が、付録Ｂ５およびＢ６を参照しながら説明される。付録Ｂ３およびＢ４を言及するアルゴリズム２と同様に、付録Ｂ５およびＢ６におけるアルゴリズム３は、クラスＳＮごとにソース数が小さい値であり、無視できないバッファメモリの場合に対応する（Ｂ〔〕＞０）瞬間スループット速度を計算するための直接的な手順である。
【００４８】
アルゴリズム３は、アスタリスクを前に付けられたアルゴリズム要素が追加されたアルゴリズム２に対応する。以下に示す変数も、ルータのバッファメモリに関して追加されている：
ｂｂ＿ｎ〔ｒ〕：ステップｎにおける中間キューサイズ
ｂｎ＿ｎ〔ｒ〕：ステップｎにおけるルータ‘ｒ’のキューサイズ
ｔａｕ０＿ｎ〔ｒ〕は、アルゴリズム２のｔａｕ＿ｎ〔ｒ〕を示し、つまり、他のルータが無限の容量ｃ〔ｒ〕を有する場合に、および、当該のルータ‘ｒ’がバッファメモリ（バッファ）を備えていない場合に獲得された仮想内部混雑時間を示す。
【００４９】
したがって、付録Ｂ５におけるステップ０において、アルゴリズム２に追加されたアルゴリズム要素は、キューサイズｂｂ＿ｎ〔ｒ〕およびｂｎ＿ｎ〔ｒ〕のゼロ初期化である。
【００５０】
付録Ｂ５-１におけるステップ１では、混雑エポックｎにおけるルータの仮想内部混雑時間の計算が、バッファメモリを持たないルータの仮想内部混雑時間と、そのルータの中間キューサイズの計算とを考慮して実行される。
【００５１】
付録Ｂ５-２におけるステップ２では、混雑エポックｎにおけるネットワークの内部混雑時間ｔａｕ＿ｎを計算するとともに速度を更新した後に、混雑エポックｎと所定のルータとに対してネットワークの内部混雑時間が時間ｔａｕ０＿ｎ〔ｒ〕よりも大きいか否かに依存して、キューｂｎ-ｎ〔ｒ〕が更新される。
【００５２】
以下に本発明の他の実施の形態が考察される。
【００５３】
そのため、事前に定義を行う代わりに、以下の説明では同期速度が評価（推定）される。いくつかの評価が可能である。
【００５４】
同期がスループット速度（ケースＲＩ）と無関係であると仮定すると、タイプＣ１−１の同期速度の近似を行うことが可能になる。Ｌは、フルバッファメモリ（バッファ）から開始したデルタ〔ｓ，ｒ〕の継続期間に渡ってのパケット損失の可能性であり、デルタは、損失に対するプロトコル例えばＴＣＰの反応時間である。この公式は、比率Ｂ〔ｒ〕/Ｃ〔ｒ〕が、各ルータに対しての仮想内部混雑時間ｔａｕ＿ｎ〔ｒ〕の平均値を相当に下回るという近似、要するに、Ｂ〔ｒ〕/Ｃ〔ｒ〕＜＜（ｔａｕ＿ｎ〔ｒ〕）の平均値であるという近似によって得られる。
【００５５】
ルータへの入力速度が同一のルータからの出力速度と実際的に等しい場合、および、バッファメモリＢ〔ｒ〕のサイズが無視できる場合には、公式Ｃ１−１の変数が以下のとおりに計算される：
パケット損失の可能性ＬがＣ１−２に従って計算され、および
デルタ〔ｓ，ｒ〕が、ルータｒの位置に依存するクラスｓのラウンドトリップ時間ｒｔｔ〔ｓ〕の比率として計算される。
【００５６】
ルータの入力速度が同一のルータの出力速度と異なっている場合、および、バッファメモリＢ〔ｒ〕のサイズが無視できない場合には、公式Ｃ１−１の変数が以下のとおりに計算される：
Ｃ３−１に提案されているような変更がＬに加えられなけらばならず、ここにおいてｒｈｏはルータの出力速度に対する入力速度の比率を表す。
【００５７】
同期が速度と無関係である場合には、ランダム変数ガンマ〔ｓ，ｒ〕が、例えば前出のベルヌーイの法則に従って決定される。同期が速度に依存すると仮定した場合（ケースＲＩ）には、タイプＣ２−１の近似によって同期速度が計算される。
【００５８】
全ての評価ケースにおいて、各ルータと、このルータが属する各クラスとに対して同期速度が評価される。全ての評価ケースにおいて、ランダム変数ガンマ〔ｓ，ｒ〕は、例えば、線形モデルに従って決定され、または、指数関数的または多項式的な速度関数としてのモデルに従って決定される。
【００５９】
上述した方法は、ネットワークパラメータと、各ＴＣＰソースのパラメータとが与えられていると仮定している。
【００６０】
装置と、その対応方法とは、以下の典型的な応用を有している。
【００６１】
１つの直接的な応用は、所定のネットワーク構成において典型的なユーザの接続性能を予測することである。捜し求められる性能は、例えば、ユーザによって得られる平均速度であり、より一般的には、接続時間の特定比率に対する保証速度、損失比率、または、瞬間速度の一時的な変化に依存する他の値である。別の直接的な応用は、最適化されたＴＣＰトラフィック発生器の実現である。
【００６２】
また、他の間接的な応用は、前述の応用のうちの最初の応用から導出される。したがって、局所的なアーキテクチャが、以下により一定の性能目的にとって最適化可能になる：
ルータ容量の最適なサイズに分け、および
バッファメモリの最適なサイズに分ける。
【００６３】
また、以下のことが最適化可能である：
ルータの幾何学的配置（階層的構造）、
ルータについての接続性の選択（階層的またはピア・トゥー・ピア）、および
性能に従ってルータを分類することで全体アーキテクチャの理解および診断と、「ボトルネック」タイプのルータの場所とである。
【００６４】
本発明は、検査工程で使用される関数を含むソフトウェア製品を網羅する。また、本発明は、本発明による装置の処理モジュールの要素を規定するソフトウェア製品に及ぶ。本発明が、上述した形態に限定されるものではなく、これ以外の他の実施の形態に及びことは理解されるべきである。
【００６５】
したがって、本発明の他の実施の形態においては、ソースはＨＴＴＰタイプのものである。また、或る別の実施の形態では、同期速度が、無関係なシミュレーションによって直接的に推定される。また、別の実施の形態では、ルータはフェアキューイング(ＦＱ)タイプのものである。
【００６６】
また、このシミュレーションは、コンピュータネットワーク以外の応用、例えば、様々な分野（ロードネットワーク、ウォータウェイネットワーク等）における任意タイプのネットワークトポロジーに提供可能である。
2005510129.tif 000003
2005510129.tif 000004
2005510129.tif 000005
2005510129.tif 000006
2005510129.tif 000007
2005510129.tif 000008
2005510129.tif 000009
2005510129.tif 000010
【図面の簡単な説明】
【００６７】
【図１】本発明による処理モジュールを備えた計算装置を示す。
【図２】一組のセッション間で共用されるルータで構成されたコンピュータネットワークを示す。
【図３】本発明によるネットワーク分析のシミュレーション工程のフロー線図である。
【図４】或るクラスの経路に属するルータにおける平均スループット速度のパターンを示すグラフである。
【００６８】
付録Ａは、詳細な説明で参照されているネットワークパラメータ、ソースパラメータ、およびモデルの変数を提供する。
【００６９】
付録Ｂは、詳細な説明で参照されているモデルに関連したアルゴリズムの計算ステップを提供する。
【００７０】
付録Ｃは、特定の仮定に基づいて同期速度を推測する。
【００７１】
付録Ｄは、詳細な説明で参照されている数学的公式化を提供する。
【符号の説明】
【００７２】
１    システムユニット
２    グラフィックカードＧＵＩ
３    処理モジュール
４    メモリ
５    計算モジュール
６    入力装置
７    モニタ
８    ネットワーク表示
９    データ
【図１】
2005510129.tif 000011
【図２】
2005510129.tif 000012
【図３】
2005510129.tif 000013
【図４】
2005510129.tif 000014
【国際調査報告】
2005510129.tif 000015
2005510129.tif 000016
2005510129.tif 000017
2005510129.tif 000018
2005510129.tif 000019
2005510129.tif 000020