(57)【特許請求の範囲】
【請求項１】
静的ルーティング・アルゴリズムに基づく並列コンピュータ・ネットワークの理論的な相互接続効率を装置がプロセッサに評価させる方法であって、
前記並列コンピュータ・ネットワークの並列コンピュータは、複数の装置を備え、
前記方法は、
−  前記プロセッサが、前記複数の装置間の複数のリンクのタイプを決定するステップ（１０５）と、
−  前記複数のリンクのタイプの少なくとも１つのサブセットの各タイプに対して、
−  前記並列コンピュータ・ネットワークのトポロジーに従って、リンク毎のルートの理論数を、前記プロセッサが、決定するステップ（１２０）と、
−  前記並列コンピュータ・ネットワークのトポロジーに従って、関連するリンク数を、前記プロセッサが、決定するステップ（１２５）と、
−  リンク毎のルート数とリンク数との組により定められる少なくとも１つの最適ルーティング・ポイントを推定するために、リンク・タイプを問わず、リンク毎のルートの各々の計算された値に関連するリンク数を決定することによって、前記決定されたリンク毎のルートの理論数と、前記関連するリンク数とを、前記プロセッサが、集計するステップであって、前記少なくとも１つの推定された最適ルーティング・ポイントは、前記並列コンピュータ・ネットワークの理論的な相互接続効率を最適化するものである、ステップ（１３５）と、を含むことを特徴とする、方法。
【請求項２】
前記少なくとも１つの最適ルーティング・ポイントを、前記プロセッサが、グラフ上にプロットするステップ（３００）を更に含む請求項１に記載の方法。
【請求項３】
静的ルーティング・アルゴリズムに基づく並列コンピュータ・ネットワークの相互接続効率を装置がプロセッサに評価させる方法であって、
前記並列コンピュータ・ネットワークの並列コンピュータは、複数の装置を備え、
前記方法は、
−  請求項１ないし２のいずれか１項に記載の方法にしたがって、前記プロセッサが、少なくとも１つの最適ルーティング・ポイントを決定するステップと、
−  前記複数のリンクのタイプの前記少なくとも１つのサブセットの各タイプに対して、
−  前記並列コンピュータ・ネットワークのトポロジーと前記静的ルーティング・アルゴリズムとに従って、前記プロセッサが、リンク毎のルートの実際の数を決定するステップと、
−  前記並列コンピュータ・ネットワークのトポロジーに従って、前記プロセッサが、関連する実際のリンク数を決定するステップと、
少なくとも１つの実際のルーティング・ポイントを推定するために、前記決定されたリンク毎のルートの実際の数と、前記関連する実際のリンク数とを前記プロセッサが、集計するステップであって、前記少なくとも１つの推定された実際のルーティング・ポイントは、前記少なくとも１つの最適ルーティング・ポイントを考慮して前記並列コンピュータ・ネットワークの前記相互接続効率を最適化するものである、ステップと、を含むことを特徴とする、方法。
【請求項４】
前記トポロジーの少なくとも１つのパラメータを、前記プロセッサが、修正し、
−  前記複数のリンクのタイプの少なくとも１つのサブセットの各タイプに対して、
−  前記並列コンピュータ・ネットワークの前記修正されたトポロジーと、前記静的ルーティング・アルゴリズムとに従って、リンク毎の前記修正された実際のルートの数を、前記プロセッサが、決定するステップと、
−  前記並列コンピュータ・ネットワークの前記修正されたトポロジーに従って、前記修正された関連する実際のリンク数を、前記プロセッサが、決定するステップと、
−  少なくとも１つの修正された実際のルーティング・ポイントを推定するために、前記決定されたリンク毎の修正された実際のルートの数と、前記修正された関連する実際のリンク数を、前記プロセッサが、集計するステップであって、前記少なくとも１つの推定され修正された実際のルーティング・ポイントは、前記少なくとも１つの最適ルーティング・ポイント及び／又は前記少なくとも１つの際のルーティング・ポイントを考慮して前記修正された並列コンピュータ・ネットワークの前記相互接続効率を最適化するものである、ステップと、を繰り返すステップを更に含む請求項１ないし３のいずれか１項に記載の方法。
【請求項５】
前記トポロジーを修正する前記ステップは、前記並列コンピュータ・ネットワークの少なくとも１つの装置を、前記プロセッサが、論理的に除去するステップを含む、請求項１ないし４のいずれか１項に記載の方法。
【請求項６】
前記少なくとも１つの装置タイプの装置の故障をシミュレーションするための前記少なくとも１つの修正された実際のルーティング・ポイントを推定する前記ステップを、前記プロセッサが、繰り返すステップを更に含む請求項１ないし５のいずれか１項に記載の方法。
【請求項７】
前記静的ルーティング・アルゴリズムの少なくとも１つのパラメータを、前記プロセッサが、修正し、
−  前記複数のリンクのタイプの少なくとも１つのサブセットの各タイプに対して、
−  前記並列コンピュータ・ネットワークのトポロジーと前記修正された静的ルーティング・アルゴリズムとに従って、リンク毎の前記修正された実際のルートの数を、前記プロセッサが、決定するステップと、
−  前記並列コンピュータ・ネットワークのトポロジーに従って、前記修正された関連する実際のリンク数を、前記プロセッサが、決定するステップと、
−  少なくとも１つの修正された実際のルーティング・ポイントを推定するために、前記決定されたリンク毎の修正された実際のルートの数と、前記修正された関連する実際のリンク数とを、前記プロセッサが、集計するステップであって、前記少なくとも１つの推定され、修正された実際のルーティング・ポイントは、前記少なくとも１つの最適ルーティング・ポイント及び／又は前記少なくとも１つの際のルーティング・ポイントを考慮して前記修正された並列コンピュータ・ネットワークの前記相互接続効率を最適化するものである、ステップと、を繰り返すステップを更に含む請求項３又は４に記載の方法。
【請求項８】
前記ルーティング・ポイントを同一のグラフの上に、前記プロセッサが、プロットするステップを更に含む請求項３ないし７のいずれか１項に記載の方法。
【請求項９】
前記複数のリンクのタイプの前記少なくとも１つのサブセットは、前記複数のリンクのタイプのすべてのタイプのリンクを含む、請求項１ないし８のいずれか１項に記載の方法。
【請求項１０】
リンク毎のルートの実際の数と関連する実際のリンク数を決定する前記ステップは、前記並列コンピュータ・ネットワークのシミュレーションの間に実行される、請求項３ないし９のいずれか１項に記載の方法。
【請求項１１】
プログラムがプログラム可能デバイスにロードされて、実行される場合に、請求項１ないし１０のいずれか１項に記載の方法の各々のステップを実行するための命令を備えるコンピュータープログラム。
【請求項１２】
請求項１ないし１０のいずれか１項に記載の方法の各々のステップを実行するのに適合した手段を備える装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、一般に、並列コンピュータ・ネットワークのパフォーマンスを評価するための方法およびシステムに関し、より具体的には、静的ルーティング・スキームに基づいた並列コンピュータ・ネットワークの相互接続効率を評価するための方法およびシステムに関する。
【背景技術】
【０００２】
プロセッサーを含む複数のノードを備える並列コンピュータにおいて、それらのノードは、スイッチ手段によるファット・トリー（ＦＡＴ  ＴＲＥＥ）のようなトポロジー・ネットワークによって互いに接続している。ノードは、異なる性質であっても良い。たとえば、計算ノードは、ユーザーのタスクを実行するのに用いられ、一方、サービス指向ノードが、例えば、ネットワーク管理、格納、入出力など、特定のタスクを取り扱う。
【０００３】
近年、インフィニバンド（ＩｎｆｉｎｉＢａｎｄ）タイプのノード相互接続が、非常に大規模なクラスタすなわち、密接に連携して動作するリンクされたコンピュータのグループに対して、
低いレイテンシと高い帯域幅を提供するそのパフォーマンスのために、ポピュラーな相互接続モデルになった。
【０００４】
インフィニバンド・は、インフィニバンド・トレード協会（ＩｎｆｉｎｉＢａｎｄ  Ｔｒａｄｅ  Ａｓｓｏｃｉａｔｉｏｎ）によって定義された広範囲な仕様に基づくパケット・スイッチング・ネットワークである。しかしながら、ＨＰＣ（高性能コンピュータ）のために設計されることは主要なものでなかったので、ダイナミック・ルーティングのようないくつかの特徴が欠如している。
【０００５】
インフィニバンド・アーキテクチャ（ＩＢＡ）は、ルーティングは、サブネット・マネージャと呼ばれる外部ソフトウェア・エージェントによって、一般的には実行されなければならないことを特定する。インフィニバンド・ネットワークのルーティングが目的地ベースであるので、ルーティング・テーブルが、ファブリックとも呼ばれるネットワークにおいて、あらゆるスイッチの中にセットアップされなければならない。ＯｐｅｎＳＭ（オープンソース・サブネット・マネージャ）は、その目的のためのルーティング・アルゴリズムを含む、多くのネットワーク・サービスを提供する。たとえば、ＯｐｅｎＳＭは、最小ホップ、アップ／ダウンおよびファット・トリー（ＦＡＴ  ＴＲＥＥ）として知られるルーティング・アルゴリズムを提供する。
【０００６】
静的ルーティングは、ネットワークにおいて競合することになることがありえるので、
それゆえに、全体的なネットワーク効率を制限して、ルーティングは慎重にセットアップされなければならない。
【０００７】
上記のように、インフィニバンド・アーキテクチャは、静的ルーティング・スキームに依存する。したがって、適応ルーティング機能の欠如を克服するために、効率的なルーティング技術が必須である。しかしながら、これらのアルゴリズムによって達成されるルーティング効率を特徴づけるために、多種多様なベンチマークを走らせることが必要である。
【０００８】
さらにまた、装置のインフィニバンド項目の、良いＭＴＢＦ（平均故障間隔）数字にもかかわらず、故障率は、ペタスケール・クラスタにおいて、もはや無視することができない。また、静的ルーティングは、ネットワーク劣化に対するクラスタ感度を強調する。したがって、装置損失の影響を評価することは、クラスタ相互接続持続性とユーザビリティのために必須である。
【０００９】
したトポロジーにインフィニバンド・トポロジーとルーティング効率を評価するために静的ルーティング・スキームに基づいた並列コンピュータ・ネットワークの相互接続効率を評価するための方法とシステムを提供する必要がある。
【発明の概要】
【００１０】
ゆえに、ここに記載するように、先行技術の欠点を直すことは、本願発明の広い目的である。
【００１１】
これらおよび他の関連した目的の成果は、静的ルーティング・スキームに基づく並列コンピュータ・ネットワークの理論的な相互接続効率を特徴づける方法によって、達成される。この並列コンピュータは、複数の装置を備え、この方法は、以下のステップから含んでいる。
−  前記装置間の複数のリンクのタイプを決定するステップと、
−  前記複数のリンクのタイプの少なくとも１つのサブセットの各タイプに対して、
○  前記並列コンピュータ・ネットワークのトポロジーに従って、リンク毎のルートの理論数を決定するステップと、
○  前記並列コンピュータ・ネットワークのトポロジーに従って、関連するリンク数を決定するステップと、
−  前記決定されたリンク毎のルートの理論数と、前記関連するリンク数とを、少なくとも１つの最適ルーティング・ポイントを推定するために、集計するステップであって、前記少なくとも１つの推定された最適ルーティング・ポイントは、前記並列コンピュータ・ネットワークの理論的効率を特徴づける、ステップ。
【００１２】
本願発明の方法は、したがって、それは、実際の並列コンピュータ・ネットワーク構成の効率を評価するのに用いることができる理論的な基準を決定することを可能にする。より正確には、本願発明の方法は、数百の装置、数千または何十万のリンクを備える並列コンピュータ・ネットワークの理論的な相互接続効率を、ほんのわずかの基準値によって特徴づけることを可能にする。
【００１３】
特定の実施形態にしたがって、その方法は、実際の並列コンピュータ・ネットワーク構成の効率を評価するのに用いることができる、その理論的な基準の視覚の表現を提供するように、グラフの上で上記の少なくとも１つの最適ルーティング・ポイントをプロットするステップを更に含む。
【００１４】
静的配線アルゴリズムに基づいて、並列コンピュータ・ネットワークの相互接続効率を特徴づける方法を提供することが、本願発明のもう一つの目的である。この並列コンピュータは、複数の装置を備え、本願方法は、以下のステップを含む。
−  上に記載した方法によって、少なくとも１つの最適ルーティング・ポイントを決定するステップと、
−  前記複数のリンクのタイプの前記少なくとも１つのサブセットの各タイプに対して、
○  前記並列コンピュータ・ネットワークのトポロジーと前記ルーティング・アルゴリズムとに従って、リンク毎のルートの実際の数を決定するステップと、
○  前記並列コンピュータ・ネットワークのトポロジーに従って、関連する実際のリンク数を決定するステップと、
−  前記決定されたリンク毎のルートの実際の数と、前記関連する実際のリンク数とを、
少なくとも１つの実際のルーティング・ポイントを推定するために、集計するステップであって、前記少なくとも１つの推定された実際のルーティング・ポイントは、
前記少なくとも１つの最適ルーティング・ポイントを考慮して前記並列コンピュータ・ネットワークの前記効率を特徴づける、ステップ。
【００１５】
したがって、本願発明の方法は、単に実際のルーティング特性を最適ルーティング特性と比較することによって、並列コンピュータ・ネットワークの効率を評価することを可能にする。
【００１６】
特定の実施形態にしたがって、その方法は更に、前記トポロジーの少なくとも１つのパラメータを修正し、
−  前記複数のリンクのタイプの少なくとも１つのサブセットの各タイプに対して、
○  前記並列コンピュータ・ネットワークの前記修正されたトポロジーと前記ルーティング・アルゴリズムとに従って、リンク毎の前記修正された実際のルートの数を決定するステップと、
○  前記並列コンピュータ・ネットワークの前記修正されたトポロジーに従って、前記修正された関連する実際のリンク数を決定するステップと、
−  少なくとも１つの修正された実際のルーティング・ポイントを推定するために、前記決定されたリンク毎の修正された実際のルートの数と、前記修正された関連する実際のリンク数とを集計するステップであって、前記少なくとも１つの推定され修正された実際のルーティング・ポイントは、前記少なくとも１つの最適ルーティング・ポイント及び／又は、前記少なくとも１つの実際のルーティング・ポイントを考慮して前記修正された並列コンピュータ・ネットワークの前記効率を特徴づける、ステップと、のステップを繰り返すステップを含む。
【００１７】
したがって、本願発明の方法は、そのパラメータの少なくとも１つを修正することによって、また、単に、変更された実際のルーティング特性を最適ルーティング特性及び／又は実際のルーティング特性と比較することによって、並列コンピュータ・ネットワークのトポロジーを最適化することを可能にする。
【００１８】
さらに、特定の実施形態にしたがって、そのトポロジーを修正するステップは、並列コンピュータ・ネットワークの少なくとも１つの装置を論理的に除去するステップを含む。したがって、本願発明の方法は、故障に直面する並列コンピュータ・ネットワークの効率を、故障をシミュレーションするためにそのパラメータの少なくとも１つを修正することによって、単に、変更された実際のルーティング特性を最適ルーティング特性、及び／又は実際のルーティング特性と比較することによって、推定することを可能にする。
【００１９】
さらに、特定の実施形態にしたがって、装置の特定のタイプの故障をシミュレーションすることを可能にする。本願方法は、更に、前記少なくとも１つの装置タイプの装置の故障をシミュレーションするための前記少なくとも１つの修正された実際のルーティング・ポイントを推定する前記ステップを繰り返すステップを含む。したがって、本願発明の方法は、特定のタイプの装置の故障に直面する並列コンピュータ・ネットワークの効率を決定することを可能にする。
【００２０】
さらに、特定の実施形態にしたがって、その方法は更に、前記ルーティング・アルゴリズムの少なくとも１つのパラメータを修正するステップと、以下のステップを含む。
−  前記複数のリンクのタイプの少なくとも１つのサブセットの各タイプに対して、
○  前記並列コンピュータ・ネットワークのトポロジーとまた、前記修正されたルーティング・アルゴリズムとに従って、リンク毎の前記修正された実際のルートの数を決定するステップと、
○  前記並列コンピュータ・ネットワークのトポロジーに従って、前記修正された関連する実際のリンク数を決定するステップと、のステップを繰り返すステップと、
−  少なくとも１つの修正された実際のルーティング・ポイントを推定するために、前記決定された修正されたリンク毎のルートの実際の数と、前記修正された関連する実際のリンク数とを集計するステップであって、前記少なくとも１つの推定され修正された実際のルーティング・ポイントは、前記少なくとも１つの最適ルーティング・ポイント及び／又は前記少なくとも１つの際のルーティング・ポイントを考慮して前記修正された並列コンピュータ・ネットワークの前記効率を特徴づける、ステップ。
【００２１】
したがって、本願発明の方法は、そのパラメータの少なくとも１つを修正することによって、単に、変更された実際のルーティング特性を最適ルーティング特性及び／又は実際のルーティング特性と、比較することによって、並列コンピュータ・ネットワークのルーティング・アルゴリズムを最適化することを可能にする。
【００２２】
本願発明の方法は、望ましくは更に、並列コンピュータ・ネットワークの効率を視覚的に、そして、すばやく決定することができるように、前記ルーティング・ポイントを同一のグラフの上にプロットするステップを含む。
【００２３】
前記複数のリンクのタイプの前記少なくとも１つのサブセットは、好適には、並列コンピュータ・ネットワーク効率が、全体の並列コンピュータ・ネットワークを考慮に入れて、評価されるように、リンクの複数のタイプのリンクのすべてのタイプを含む。
【００２４】
さらに、特定の実施形態にしたがって、リンク毎のルートの実際の数と関連する実際のリンク数を決定する前記ステップは、並列コンピュータ・ネットワークの効率を評価するときに、計算タスクを最適化するように、前記並列コンピュータ・ネットワークのシミュレーションの間に実行される。
【００２５】
プログラムがプログラム可能デバイスにロードされて、実行される場合に、上述の方法の各々のステップを実行するための命令を含むコンピュータープログラム、および、この方法の各々のステップを実行するための命令を備える装置を提供することは、本願発明の別の目的である。
【００２６】
静的ルーティング・スキームに基づく並列コンピュータ・ネットワークの相互接続効率を特徴づけるためのコンピュータープログラムと装置の特定の特性と長所は、静的ルーティング・スキームに基づいた、並列コンピュータ・ネットワークの相互接続効率を特徴づけるための方法のものと同様である。ここでは繰り返さない。
【００２７】
本願発明の更なる長所が、当業者が図面および発明の詳細な説明を調べれば、すぐに、明らかになる。いかなる追加の利点もここに組み込まれることが意図されている。
【図面の簡単な説明】
【００２８】
【図１】インフィニバンド・タイプのネットワーク・トポロジの最適効率を特徴づけるためのアルゴリズムの例を示す。
【図２】本願発明の方法にしたがって、ルーティング効率が決定できるインフィニバンド・ネットワーク・トポロジの例を示す。
【図３】図２の上で例示されたインフィニバンド・タイプのネットワークのための最適トポロジーおよびルーティングの代表を例示しているグラフを表す。
【図４】図３の上で示されるネットワークのための最適ルーティングの表現と比較して、図２の上で例示されたネットワーク・トポロジに対して、最小ホップとファット・トリー（ＦＡＴ  ＴＲＥＥ）アルゴリズムで得られる実際のルーティングの表現を例示しているグラフを表す。
【図５】最適ルーティング・ポイントおよび図２の上で表される最小ホップ・ルーティング・アルゴリズムとファット・トリー（ＦＡＴＴＲＥＥ）ネットワーク・トポロジを用いて、１つのスイッチの故障のシミュレーションから生じる、実際のルーティング・ポイントを表しているグラフの例を例示する。
【図６】シミュレーションに基づいて、ネットワーク・トポロジとルーティングを改良するのに用いることができるアルゴリズムの例を示す。
【図７】少なくとも部分的に本願発明を実行することを可能にする装置の例を示す。
【発明を実施するための形態】
【００２９】
本願発明の目的は、ネットワーク・トポロジの影響、リンク毎のルート数に基づく測定基準を使用するシミュレーションを通してルーティング効率についての低下とルーティング・アルゴリズムを特徴づけることである、
【００３０】
以下において、次のような用語を用いる。
−  ファット・トリー（ＦＡＴ  ＴＲＥＥ）トポロジーのスイッチの列は、このスイッチとリーフ・ノード、スイッチまたはルータ以外のコンポーネントであるノード（典型的なＨＰＣノードはコンピュータ・ノード、Ｉ／Ｏサーバおよび管理サーバである）、の間の最小距離である。ランク「ｉ」のスイッチは、「Ｌｉ」と呼ばれている。
−  アイランドは、ランク１とランク２とそれらのリーフ・ノードのすべてのスイッチを含むセットであり、それらのすべては、ランク３のいかなるスイッチも使用していないリーフ・ノーから到達できなければならない。ランク３以上のスイッチによるファット・トリー（ＦＡＴ  ＴＲＥＥ）は、複数のアイランドを含むことができる。
−  レベルは、アイランドの中で同じランクのすべてのスイッチを含むセットである。
−  ネットワーク・レベルは、相互接続ネットワークの中で、同じランクのすべてのスイッチを含むセットである。
−  ルートは、２つの端点の間でネットワーク・パケットによって使用されるパスを記述する、と考えられる。ＯｐｅｎＳＭの定義によれば、プライマリ・ルートは、２つのノードの間で構成されるルートである。プライマリ・ルートでないルートは、二次ルートと呼ばれる（これらのルートはスイッチ、ルータ、その他の間のいくらかの接続性を提供する。）。ノードとスイッチ（またはルータ）の間のルートは、二次ルートとも呼ばれる。
−  リンクは、２つのスイッチの間の、または、スイッチとノードの間の物理接続である。
−  リンク毎のリンク数は、リンクを通過するプライマリ・ルートの数である。
【００３１】
プライマリ・ルートは、ユーザーの観点から有用であるデータ転送に直接関与していることに留意する必要がある。プライマリ・ルートを通過するトラフィック量は多く、そのクラスタとそのロードの上で動作するアプリケーションのプロフィールに依存する。
【００３２】
二次ルートは、サブネット管理の目的のために使われるだけである。基本的に、それはサブネット・マネージャ・パケットに、そのスイッチにおけるインフィニバンド・ルーティング・テーブルを構成させ、パフォーマンスカウンタを収集することを許す。二次ルートを、他の管理目的のために使うこともできるが、しかし、これらのルートに通過しているトラフィック量は、通常少なく、エンドユーザーには見えない。
【００３３】
相互接続パフォーマンスは、一般に、ユーザーの視点から見えるようなものであるので、プライマリ・ルートだけが、以下においてルーティング効率を決定するために考慮される。しかしながら、二次ルートも、同様に考慮することができる。
【００３４】
ルーティング効率を評価するために、本願発明の方法は、最適ルートの数で、サブネット・マネージャにより生成されたルート数の間の比較に基づいている。
【００３５】
最適ルートの数を決定するために、ノードは、互いの間で均質に通信することを仮定する。そのような仮定は、ファット・トリー（ＦＡＴ  ＴＲＥＥ）アルゴリズムの現在のインプリメンテーションにおいて、ＯｐｅｎＳＭにより用いられており、それは、殆どの状況において、良いパフォーマンスを達成するのを可能にする。
【００３６】
ここで、通信が均質であると考えられているので、最適ルーティング・スキームは、相互接続ネットワークのあらゆるリンクにおいて、等しいロードを得なければならない。言い換えると、ルーティング・アルゴリズムは、ファット・トリー（ＦＡＴ  ＴＲＥＥ）の中の各々のレベルにおいて、各々のリンクのロードがおよそ同じことであるように、ルートをあらゆるリンクに広げなければならない。正確な通信スキームと各々のルートの上のトラフィック量とを、前もって決定することができないので、リンクのロードは、リンク毎のルート数の測定基準にしたがって、評価される。
【００３７】
最適にルートされたネットワークにおいて、いかなる隣接したレベルのカップルに対しても、リンク毎のルート数は、これらのレベルを接続するすべてのリンクに対するものと同じである。均質なファット・トリー（ＦＡＴ  ＴＲＥＥ）の場合において、これは、ネットワーク・レベル（相互接続の範囲）に拡張することができる。インフィニバンド・リンクが全二重であるので、各々のリンクは、リンク毎に２種類の異なるルート（各々の方向に１つ）を持っている。
【００３８】
図１は、インフィニバンド・タイプのネットワーク・トポロジの最適効率を特徴づけるためのアルゴリズム（１００）の例を示す。例示されるように、第１のステップは、リンクのタイプを決定することである（ステップ１０５）。説明のために、リンクのタイプを、転送先あるいはソース・スイッチのいくつかの特性にしたがって、定めることができる。特に、リンクのタイプを、転送先またはソース・スイッチのランク、および、それが属しているアイランドにしたがって、定めることができる。インデックスｉは、ゼロに初期化される（ステップ１１０）。
【００３９】
ついで、インデックスｉが、ｎｂ＿ｌｉｎｋ＿ｔｙｐｅと呼ばれるリンク・タイプの数に等しいかどうかを決定するために、テストが実行される（ステップ１１５）。
【００４０】
インデックスｉが、リンク・タイプの数と等しくない場合には、ｎｂ＿ｒｏｕｔｅｓ（ｉ）と呼ばれるｉタイプのリンクに対する、リンク毎のルートの総数が計算される（ステップ２１０）。ｎｂ＿ｌｉｎｋｓ（ｉ）と呼ばれるｉタイプのリンク数が決定され（ステップ１２５）、インデックスｉが、１だけインクリメントされる（ステップ１３０）。それから、プロセスは、ステップ１１５にループする。
【００４１】
インデックスｉが、リンク・タイプの数と等しい場合には（ステップ１１５）、得られたリンク毎のルート数とリンク数とが、リンクの各タイプに対して、集計される（ステップ１３５）。たとえば、その集計は、どのリンク・タイプであっても、リンク毎のルートの各々の計算された値に関連するリンク数を決定を含むことができる。集計された値は、望ましくは表示される（ステップ１４０）。
【００４２】
図１のアルゴリズムを例示するために、図２および３は、インフィニバンド・ネットワーク・トポロジと、本願発明の方法にしたがって、その効率の表現の例を表す。
【００４３】
図２は、本願発明の方法にしたがって、ルーティング効率が決定できるインフィニバンド・ネットワーク・トポロジの例を示す。
【００４４】
イラスト・トポロジ２００は、枝刈りされたものである、すなわち、ダウンリンクの数が、所定のレベルにおいて、アップリンクの数より大きいネットワーク・トポロジーである。以下を備える非均質なフラット・ツリーである。
−  １８のＬ３スイッチ２０５−１〜２０５−１８、トップ・スイッチとも呼ばれる。
−  ６つの計算アイランド（２１０−１〜２１０−６）、各々の計算アイランド２１０−ｋは、
○  １８のＬ２スイッチ（２１５−ｋ−１８〜２１５−ｋ−１）、各々Ｌ３スイッチに接続している４つのアップリンク（２２０−ｋ−１８〜２２０−ｋ−１）を有する。
○  ３２のＬ１スイッチ（２２５−ｋ−３２〜２２５−ｋ−１）、リーフ・スイッチとも呼ばれる、各々のＬ１スイッチは、計算アイランドの１８のＬ２スイッチに接続している。
○  Ｌ１スイッチ毎に１８の計算ノード、すなわち、アイランドにつき５７６の（３２ｘ  １８）計算ノード、２３０−  ｋ−ｌ−１〜２２５−ｋ−ｌ−１８と呼ばれ、ｋは、計算アイランドのインデックスを表し、は、Ｌ１スイッチのインデックスをインデックスｋの計算アイランドで表す。
−  以下を備える１つの枝刈りされていないサービス・アイランド（２３５）
○  １８のＬ２スイッチ（２４０−１〜２４０−１８）、Ｌ３スイッチに接続している各々が８つのアップリンク（２４５−１〜２４５−１８）を有する。
○  各々のＬ１スイッチがサービス・アイランドの１８のＬ２スイッチに接続している、８つのＬ１スイッチ（２５０−１〜２５０−８）
○  Ｌ１スイッチにつき１８のサービス・ノード、すなわち、２５５−１−１８〜２５５−１−１と呼ばれ、ｌは、サービス・アイランドにおけるＬ１スイッチのインデックスを表すアイランドにつき１４４の（８つのｘ  １８）計算ノードを備えるもの。
【００４５】
図２から分かるように、リンクの６つのタイプが、計算アイランドとサービス・アイランドに対して、ノードと、Ｌ１、Ｌ２、Ｌ３スイッチとの間で相互接続を表す図示されたトポロジーで使われている。これらの６つのタイプは、以下のものである。
−  計算アイランドに対して、
○  計算ノードとＬ１スイッチの間のリンク
○  Ｌ１とＬ２スイッチの間のリンク
○  Ｌ２とＬ３スイッチの間のリンク
−  サービス・アイランドに対して、
○  サービス・ノードとＬ１スイッチの間のリンク
○  Ｌ１とＬ２スイッチの間のリンク
○  Ｌ２とＬ３スイッチの間のリンク。
【００４６】
同様に、コミュニケーションの４つの以下のタイプが、識別できる。
−  イントラ・セル通信、つまり、同じＬ１スイッチに接続している２つのノードの間の通信
−  イントラ・アイランド通信、すなわち、それら自身のＬ１スイッチを介して同じＬ２スイッチに接続している２つのノードの間での通信
−  インター・アイランド通信、すなわち、それら自身のＬ１とＬ２スイッチを介して同じＬ３スイッチに接続している２つのノードの間の通信
−  Ｉ／Ｏ通信、すなわち、それら自身のＬ１、Ｌ２スイッチを介して同じＬ３スイッチに接続している計算ノードとサービス・ノードの間での通信。
【００４７】
図２の上で示されるネットワーク・トポロジを考えると、次の関係にしたがって、リンク毎のルート数を計算することができる。
【数１】
0005498575.tif 000002
ここで、
−  Ｎｂ＿Ｒｏｕｔｅｓ（ｉ，ｊ）は、ｊリンク・タイプに対してタイプｉの通信によって生成されたルート数を表す。
−  Ｎｂ＿Ｓ（ｉ）は、タイプｉの通信に対するソース・ノードの数を表す。
−  Ｎｂ＿Ｄ（ｉ）は、タイプｉの通信に対する可能なデスティネーション・ノードの数を表す。
−  Ｎｂ＿Ｌ（ｊ）は、タイプが７であるリンクの数を表す。
【００４８】
付録に記載した表１は、図２の上で例示されたファット・トリー（ＦＡＴ  ＴＲＥＥ）トポロジーの最適ルーティングに対して、すべてのタイプのリンク上で通信パターンの各々に対して発生するリンク毎のルート数を詳述する。
【００４９】
説明のために、同じＬ１スイッチに接続している２つの計算ノードの間のルートの数は、以下のように計算される。
【数２】
0005498575.tif 000003
ここで、ｉは、イントラ・セル・タイプの通信を表し、ｊは、計算ノードとＬ１スイッチの間のリンクのタイプを表す。
【００５０】
同様に、異なるＬ１スイッチを介して同じＬ２スイッチに接続している２つの計算ノードの間のルートの数は、次のように計算される。
【数３】
0005498575.tif 000004
ここで、ｉは、イントラ・アイランド・タイプの通信を表し、ｊは、計算ノードとＬ１スイッチの間のリンクのタイプを表す。
【００５１】
表１の「合計」という題の列は、すべてのコミュニケーション・タイプと特定のタイプのリンクに対して、ルートの数を与える。
【００５２】
「Ｎｂリンク」という題の列は、Ｎｂ＿Ｌ（ｊ）変数に対応し、特定の種類のリンクに対するリンク数を与える。たとえば、計算ノードとＬ１スイッチとの間のリンクを考えると、リンク数は、以下のように計算される。
【数４】
0005498575.tif 000005
ここで、１８は、Ｌ１スイッチに接続している計算ノードの数を表し、３２は、計算アイランド毎のスイッチの数を表し、６は、アイランドの数を表す。
【００５３】
表１から得られる結果は、図２の上で例示されるネットワーク・トポロジから得ることができた最適構成を表す。そのような結果は、Ｘ軸がリンク毎のルート数を表し、Ｙ軸が、以下では、リンク・カウントと呼ばれる、リンク毎のこのルート数に関連する相互接続ネットワーにおけるリンク数を表すネットワーク・ロードを表す二次元のプロットにおいて表すことができる。
【００５４】
そのために、リンク毎のルート数とリンク・カウントとの各々のカップルが、最適ルーティング・ポイントとして表される。図３は、図２の上で例示されるネットワークに対する最適ルーティングのそのような例を図示しているグラフ３００を表す。明確さのために、縦軸は、対数関数的スケールによって表される。
【００５５】
ここで、リンク毎のルート数は、各々のスイッチ・ポートに対して計算されるので、すべてのリンクは、ノードとリーフ・スイッチの間に位置するリンクは別として、二回現れることに留意しなければならない。したがって、リンク毎のルート数とリンクの数を比較するために、Ｌ１とＬ２タイプ間、および、Ｌ２とＬ３タイプ間のリンク数は、２倍にしなければならない。
【００５６】
表１で与えられる、得られたリンク毎のルート数によって、４つのポイントは、最適ルーティング・ポイントを表すと考えられる、すなわち、横軸として、３４５６、３５８２、３５９９、２４１９２とあるポイントである。この４つの横軸から、４つの対応する縦軸、それぞれ、１４４、７２００（（３４５６＋１４４）ｘ２）、３６００（３４５６＋１４４）、４３２、を決定することができる。これらの４つの最適ルーティング・ポイントは、それぞれ、３０５、３１０、３１５と３２０と呼ばれる。
【００５７】
最初の最適ルーティング・ポイント３０５は、サービス・アイランドのＬ２スイッチとＬ３スイッチとの間のリンクに対応し、第２の最適ルーティング・ポイント３１０は、Ｌ１とＬ２スイッチとの間のリンクに対応し、第３の最適ルーティング・ポイント３１５は、ノードとＬ１スイッチとの間のリンクに対応し、第４の最適ルーティング・ポイント３２０は、計算アイランドのＬ２スイッチとＬ３スイッチとの間のリンクに対応する。
【００５８】
ここで、最適ルーティング・ポイントの数は、リンク・タイプの数に等しいことができることに注目すべきである。
【００５９】
一旦最適ルーティング構成が特徴づけられると、それを、同じスキームにしたがって、ネットワーク・トポロジとルーティングを評価するのに用いることができる。
【００６０】
ネットワーク・トポロジ、したがって、ルーティングをシミュレーションするために、インフィニバンド・ネットワーク・シミュレータ、たとえば、ボルテール社によって開発されたｉｂｓｉｍソフトウェア、を使用することができる。Ｉｂｓｉｍは、ネットワークの管理ふるまいをシミュレーションするために、ネット・リスト、すなわち、ルーティング、パフォーマンスカウンタなど、を使う。たとえ実際のトラフィックの影響を評価することに直接使うことができないとしても、ＯｐｅｎＳＭを、ルーティング品質を評価するのに用いられる仮想相互接続を構成するために、ｉｂｓｉｍにプラグ・インすることができる。ルーティング効率を評価するために、新しい機能性が、リンク毎のルートの値を生成するために、ＯｐｅｎＳＭコンソールに追加される。付録で与えられる疑似コード１は、ルーティング後に得られるそのような機能性、リンク毎のルート数、すなわち、「ルート・カウンター」の値、対応するリンク数、すなわち、「リンク・カウント」の値、の例を示す。
【００６１】
リンク毎のルート数は、望ましくは、最適ルーティング・ポイントを推定するために使われるタイプによって各々のリンクのタイプを決定している。たとえば、リンク毎のルート数は、計算ノードとＬ１スイッチとの間のリンク、Ｌ１とＬ２スイッチとの間のリンク、Ｌ２とＬ３スイッチの間のリンクに対して、計算とサービス・アイランドに対して評価することができる。
【００６２】
上で開示したように、最適値の決定に関して、シミュレーションされたネットワークのトポロジーとルーティングのために実際のルーティング・ポイントを得るように、そのような結果は集計することができる、
【００６３】
説明のために、図２の上で例示されたネットワーク・トポロジに対して、最小ホップ、および、ファット・トリー（ＦＡＴ  ＴＲＥＥ）アルゴリズムで得られた実際のルーティング・ポイントが、図３の上に示される最適ルーティング・ポイントとともに、図４の上に表される。
【００６４】
ダイヤモンド・マークは、最小ホップ・アルゴリズムで得られた実際のルーティング・ポイントを表す。一方、四角マークは、ファット・トリー（ＦＡＴ  ＴＲＥＥ）アルゴリズムで得られた実際のルーティング・ポイントを表す。ファット・トリー（ＦＡＴ  ＴＲＥＥ）アルゴリズムで得られた実際のルーティング・ポイントを表している四角マークの上にそれらが重ね合わせられるので、最適ルーティング・ポイントが見えないことに留意する必要がある。
【００６５】
これらの結果を分析するために、そのルートの数が最適値より大きい場合には、リンクは、予約超過であると仮定し、そのルートの数が最適値より小さい場合には、それらは予約満杯ではないと仮定し、各々のリンクを通過するルートの数がその最適値に等しい場合には、最適ネットワーク・バンド幅が達成されたと仮定する。
【００６６】
これを考慮して、予約超過なリンクが存在しないか予約が満杯でない場合には、最適バンド幅は達成される。すなわち、実際のルーティング・ポイントが最適ルーティング・ポイントにできるだけ近接している場合である。たとえば、最小ホップ・アルゴリズム、および、ファット・トリー（ＦＡＴＴＲＥＥ）・アルゴリズムのパフォーマンスを比較することによって、リンク毎のルート数は、ファット・トリー（ＦＡＴ  ＴＲＥＥ）アルゴリズムに対する最適値と等しいように見える。しかしながら、最小ホップ・アルゴリズムは、最適な方法で、パケットをルートしない。たとえば、リンク毎におよそ５０，０００のルートを特徴づける実際のルーティング・ポイント４００は、最適ルーティング・ポイント４０５のリンク毎に、ルートの最大多数のおよそ２倍の等しい（最適ルーティング・ポイントのリンク毎のルートの最大数を表す）からである。
【００６７】
ネットワーク・トポロジとルーティングの効率を評価するための本願発明の方法は、
１つ以上のスイッチやリンクが故障となった場合に、その効率を分析するのにも用いることができる。言い換えると、リンク毎のルート数は、特定の相互接続アーキテクチャ上における所定のルーティング・アルゴリズムのルーティング効率を評価することを可能にする。それは、非常に混雑したネットワークがどれくらい効率よくルートされているかという推定を提供する。そのために、シミュレーションは、非常に混雑したクラスタの上で開始される。一旦すべてのルートが確立されたならば、１つ以上の装置が、シミュレーションされたトポロジーから取り除かれる。これは、ＯｐｅｎＳＭにネットワークのルート変更をさせ、したがって、ルートを新しい状況に適応させることになる。これは、リンク毎のルート数に直接的な影響を及ぼす。そしてそれは上述の方法論を使用して測定することができる。
【００６８】
要素、たとえばスイッチ、の故障をシミュレーションする場合に、要素シミュレーションが、故障する可能性がある要素に対して行われる。たとえば、４００のスイッチを備えるネットワークにおいてスイッチの故障をシミュレーションする場合には、４００の要素シミュレーションをおこなわなければならない。各々の要素シミュレーションに対して、結果が、対応する実際のルーティング・ポイントを決定するために集計される。好適な実施形態にしたがって、次に、すべてのシミュレーションの実際のルーティング・ポイントが、要素が故障にあう場合に、ネットワーク・トポロジとルーティングの効率を推定するように、最適ルーティング・ポイントを含むグラフの上で報告される。
【００６９】
図５は、最適ルーティング・ポイントおよび図２の上で表される最小ホップ・ルーティング・アルゴリズムとファット・トリー（ＦＡＴＴＲＥＥ）ネットワーク・トポロジを用いて、１つのスイッチの故障のシミュレーションの結果の実際のルーティング・ポイントを表す、グラフの例を示す。円マークは、最適ルーティング・ポイントを表し、故障が１つのＬ１スイッチにおいてシミュレーションされる場合、ダイヤモンド・マークは、実際のルーティング・ポイントを表し、故障が１つのＬ２スイッチにおいてシミュレーションされる場合、四角マークは、実際のルーティング・ポイントを表し、故障が１つのＬ３でシミュレーションされる場合、三角マークは、実際のルーティング・ポイントを表す。これからわかるように、到達するリンク毎のルートの最も大きな数は、リンク毎に７０，０００のルートより大きい。それは、最適値の３倍であり、５７６のリンクが、まったく使われず、多くのリンクは予約超過である（リンク毎のルート範囲４０．０００  −  ５０．０００における、四角マーク）。結論として、最小ホップ、アルゴリズムは劣化したネットワークにおいて、良好に機能しない。
【００７０】
同様に、ネットワークの複数の装置の故障、例えば２つのスイッチの故障をシミュレーションすることができる。また、要素シミュレーションが、可能なコンビネーションの各々に対して行われる。たとえば、４００のスイッチを備えるネットワークにおいて、２つのスイッチの故障がシミュレーションされる場合には、１５９０００（４００ｘ３９９）の要素シミュレーションを行わなければならない。
【００７１】
要素シミュレーションの数を考慮して、三次元の、要素シミュレーション全体での、ポイントの発生の数の表現は、複数の要素の故障をシミュレーションする場合には、各々の実際のルーティング・ポイントに好適には割り当てられる。そのような第三次元は、色でグラフの上で表すことができる。説明のために、青を、０から３３の要素シミュレーションから生じた実際のルーティング・ポイントを表すのに用いることができる。黄色を、３４から１１４８の要素シミュレーションから生じた実際のルーティング・ポイントを表すのに用ることができる。緑色を、１１４９から６６８９の要素シミュレーションから生じた実際のルーティング・ポイントを表すのに用いることができる。等々である。
【００７２】
ルーティング効率を評価するために、最もロードされたリンク、最もロードされていないリンク、および、実際のルーティング・ポイントの散らばりを、分析することができる。
【００７３】
最も予約超過であるリンク、すなわち、Ｘ軸（リンク毎のルートの数を表す）に沿って、最も高い値に対応するリンクは、ネットワークの安定度を特徴づけると考えることができる。この値が大きいほど、ルーティングが、より不安定であり、ネットワークが競合に対してより敏感である。
【００７４】
最も予約が少ないリンクは、Ｘ軸（リンク毎のルートの数を表す）に沿って最も低い値に対応し、ネットワーク・パフォーマンスを表すと考えることができる。この値がより低いほど、達成されたパフォーマンスはより低くなる。最悪のケースでは、リンク毎のルートの数は、ゼロでありえる、これは、１つ以上のリンクが、ルーティング・アルゴリズムによってまったく使われないことを意味する。
【００７５】
効率的なルーティング・アルゴリズムは、常にリンク毎のルート数を、最適値のできるだけ近くに保とうとしなければならない。したがって、実際のルーティング・ポイントは、常に、可能な限りＸ軸に沿った最適ルーティング・ポイントに近接していなければならない。Ｙ軸に沿った散らばったデータは、Ｘ軸に沿ってよりも重要でないことが見られる。
【００７６】
本願発明の方法は、また、シミュレーション結果を比較することによって最適ネットワーク・トポロジを決定することとならんで、ルーティング・アルゴリズムを選択し、ルーティング・アルゴリズム・パラメータの推定を改善することにも使用することができる。
【００７７】
図６は、シミュレーションに基づいて、ネットワーク・トポロジとルーティングを改良するのに用いることができるアルゴリズム６００の例を示す。効率のために、シミュレーションは、好適には、クラスタの上で実行される。
【００７８】
ネットワークアーキテクチャ（ステップ６０５）を決定した後に、ネットワークアーキテクチャから、ノードとスイッチ（ステップ６１０）の間のすべてのリンクを表すネット・リストを生成するために、たとえば、ネットワークアーキテクチャを表している電子ファイルを変えることによって、ネット・リストが発生される。
【００７９】
次に、生成されたネット・リストは、ネットワーク・シミュレータ、たとえばｉｂｓｉｍ、に送られ、それに応じて構成される（ステップ６１５）。この構成から、ルーティング・パラメータを、セットアップすることができる（ステップ６２０）。
【００８０】
一旦、ネットワーク・トポロジがシミュレータで構成されると、ルーティング・アルゴリズムは、セットアップされ、要素シミュレーションを、開始することができる（ステップ６２５）。同時に実行されることができる要素シミュレーションの数は、シミュレーションのために使われるクラスタに依存する。
【００８１】
一旦シミュレーション・プロセスがクラスタ・ノードの上に送られると（ステップ６３０）、シミュレーションの第１のステップは、ルーティング・ステップ（ステップ６３５）である。リンク毎のルート数とリンク・カウントは、好適には、疑似コード１への参照によって、先に述べたようにシミュレーションの間に、評価される。
【００８２】
次に、得られた結果が、グラフの上でプロットされ（ステップ６４５）、表示する（ステップ６５０）ことができる実際のルーティング・ポイントを決定するように、集計される（ステップ６４０）。
【００８３】
好適には、最適ルーティング・ポイントもまた、表示されたグラフの上でプロットするように評価される（表示されていない）。
【００８４】
実際のルーティング・ポイントを最適ルーティング・ポイントと比較することによって、シミュレーションされたネットワーク・トポロジとルーティングの効率を推定することができる。同様に、異なるネットワーク・トポロジ、ルーティング・アルゴリズム、及び／又は、使用されるルーティング・アルゴリズムのパラメータに対応するシミュレーションの実際のルーティング・ポイントを比較することによって、すなわち、異なるネットワーク・トポロジ、ルーティング・アルゴリズムやルーティング・パラメータに対してステップ６０５〜６５０を繰り返すことによって、異なるネットワーク構成の効率を比較することができる。
【００８５】
観察されたグラフに応じて、ネットワーク・トポロジ、ルーティング・パラメータおよびルーティング・アルゴリズムに関連した３種類のパラメータによって、その効率を改良するためにネットワーク構成を修正することができる（ステップ６５５）。ネットワーク・トポロジが修正されることになる場合には、アルゴリズムは、ステップ６０５に分岐し、ルーティング・パラメータが修正されることになる場合には、アルゴリズムは、ステップ６２０に分岐し、ルーティング・アルゴリズムが修正されることになる場合には、アルゴリズムは、ステップ６３５に分岐する。
【００８６】
したがって、異なるシミュレーションを走らせることによって、また、本願発明の方法による結果を比較することによって、静的ルーティング・スキームに基づいた並列コンピュータ・ネットワークの相互接続効率を最適化することができる。
【００８７】
本願発明をインプリメントする装置は、図７に示される。デバイス７００は、たとえば、マイクロコンピュータまたはワークステーションである。
【００８８】
装置７００は、以下を備える。
−  中央演算処理装置またはマイクロプロセッサー７０３（ＣＰＵ）、
−  「プログラム」、「プログラム１」および「プログラム２」のプログラムを含むことができる読出し専用メモリ７０４（ＲＯＭ）、
−  前記のプログラムの実行の間に、生成され修正される変数とパラメータを記録するのに適しているレジスタを備えるランダム・アクセス・メモリまたはキャッシュメモリ（ＲＡＭ）７０６、
−  データを送信および受信することができる、たとえばインターネット等の分散通信ネットワーク７２０に接続している通信インターフェース７１８、が接続される通信バス７０２。
特に、通信インターフェース７１８は、サービス・アイランドのノードでデータの交換を可能にする。
【００８９】
オプションとして、装置７００は、以下も備えることができる。
−  データを見て、および／または、キーボード７１０またはポインティング・デバイスのような他のいかなる手段、たとえばマウス７１１、光学スタイラス、タッチスクリーンまたは遠隔操作デバイス、を用いても、本願発明にしたがって、プログラムと対話することができるユーザーとのグラフィカル・インタフェースとして役に立つためのスクリーン７０８、
−  前記のプログラム「プログラム」、「プログラム１」、そして、「プログラム２」、および、本願発明にしたがって、処理されたか、処理されるデータを含むことができるハードディスク７１２、
−  フロッピー（登録商標）ディスク７１６を受け入れ、本願発明にしたがって、処理されたか、処理されるデータを、そこで読み書きするのに適しているディスク・ドライブ７１４、
−  本願発明にしたがって、処理されたか、処理されるデータをその上で読み書きするのに適しているメモリカードのためにリーダ。
【００９０】
通信バスは、装置７００に含まれるか、それに接続している異なる要素の間の通信と相互接続性を与える。バスの代表例は、非限定的であって、特に、中央演算処理装置は、通信命令を、装置７００のいかなる要素に対しても直接、または、装置７００の別の要素によって、可能にする。プログラム可能な装置が、本願発明にしたがって、プロセスをインプリメントすることを可能にする各プログラムの実行可能コードを、たとえば、ハードディスク７１２に、または、リードオンリー・メモリ７０４に格納することができる。
【００９１】
変形として、フロッピー（登録商標）ディスク７１６は、プログラムの実行コードとともに、一旦装置７００で読み込まれると、ハードディスク７１２に保存されるデータを含むことができる。
【００９２】
第２の変形として、プログラムの実行可能コードは、コミュニケーション・ネットワーク７２０の媒介物によって、インターフェース７１８を介して、以前に記述したのと同一のやり方で、格納するために、受け取ることができる。
【００９３】
フロッピー（登録商標）ディスクは、例えばコンパクトディスク（ＣＤ−ＲＯＭ）またはメモリカード等の、いかなる情報キャリアにも置き換えることができる。一般に、フロッピー（登録商標）ディスクは、装置に一体化された、あるいは、取り外し可能なコンピュータまたはマイクロプロセッサーで読むことができ、実行すると本願発明による方法のインプリメンテーションを許す一つ以上のプログラムを格納するのに適している、情報格納手段で置き換えることができる。
【００９４】
より一般的には、プログラムは、実行される前に、装置７００の格納手段の１つへロードすることができる。
【００９５】
中央演算処理装置７０３が、本願発明によるプログラムの命令あるいはソフトウェアコードの部分の実行を制御し、指示する。これらの命令は、ハードディスク７１２あるいは読出し専用メモリ７０４に、あるいは、他の前記した格納素子に格納されている。電源投入の際に、ハードディスク７１２または読出し専用メモリ７０４等の非揮発性メモリに格納されたプログラムは、ランダム・アクセス・メモリ７０６に転送される。それは、したがって、本願発明のインプリメンテーションのために必要な変数やパラメータを格納するためのレジスタとともに、本願発明によるプログラムの実行コードを含む。
【００９６】
本願発明にしたがって、そのデバイスを備える通信装置は、プログラムされた装置であってもよいことに留意する必要がある。この装置は、したがって、たとえば、特定用途向け集積回路（ＡＳＩＣ）に固定されたコンピュータープログラムまたはプログラムのコードを含む。
【００９７】
当然に、ローカルおよび特定の必要条件を満たすために、当業者は、上に記載したソリューションに、多くの修正と変更を適用することができる。それらのすべては、しかしながら、特許請求の範囲によって定義されるように発明の保護の範囲内に含まれる。
【００９８】
特に、効率が推定されるネットワークは、ノードとスイッチ以外の他の装置を備えることができる。そのようなネットワークにおいて、リンクのタイプは、使いされる装置、それらの性質、および、それらの装置の間のリンクの性質によって推定される。
【００９９】
［付録］
【表１】
0005498575.tif 000006
【表２】
0005498575.tif 000007
【図１】
0005498575.tif 000008
【図２】
0005498575.tif 000009
【図３】
0005498575.tif 000010
【図４】
0005498575.tif 000011
【図５】
0005498575.tif 000012
【図６】
0005498575.tif 000013
【図７】
0005498575.tif 000014