(57)【要約】【課題】有効フロンティアを計算するより単純な方法を提供すること。さらに、「あるソースからすべてのノードへ」問題を解く方法を提供すること。【解決手段】データ通信ネットワーク内のソース・ノードおよび複数の宛先ノードを含むノードのグループに関する効率的なパス経費の集合を導出する方法であって、グループ内のノードの間のパスのパス経費が、ネットワーク内で定義され、各パス経費が、制限的経費および加算的経費を含む方法に、まずより広い帯域幅のパスを繰り返し識別すること、等しい帯域幅の複数のパスに出会った時に、より少ない伝送遅延が関連付けられたパスを選択することが含まれる。【特許請求の範囲】
【請求項１】
データ通信ネットワーク内のソース・ノードおよび複数の宛先ノードを含むノードのグループに関する効率的なパス経費の集合を導出する方法であって、前記グループ内のノードの間のパスに関する前記パス経費が、前記ネットワーク内で定義され、各パス経費が、制限的経費および加算的経費を含み、前記方法が、
ａ）第１データ・セットに、前記ソース・ノードから前記宛先ノードのすべてへの直接パスに関する前記パス経費を記録することであって、各記録される経費が、前記第１データ・セット内で、前記対応するパスによって到達されるノードに関連付けられこと、
ｂ）前記第１データ・セットから最良のパス経費を選択することであって、前記最良のパス経費が、最良の制限的経費を含むパス経費として、あるいは、複数のパス経費が等しい制限的経費を有する場合に、最良の制限的経費および最良の加算的経費を有するパス経費として判定されること、
ｃ）ステップｂ）で選択された前記最良のパス経費を第２データ・セットに記録することであって、前記記録される経費が、前記第２データ・セット内で、前記対応するパスによって到達されるノードに関連付けられること、
ｄ）ステップｃ）で前記第２データ・セットに記録された前記経費を前記第１データ・セットから除去すること、
ｅ）前記第１データ・セットに、ステップｃ）で記録された前記経費に対応する前記パスによって到達される前記宛先ノードから前記グループ内の他のすべてのノードへの直接パスに関する累積パス経費を記録することであって、各記録される累積パス経費が、前記第１データ・セット内で、前記対応するパスによって到達される前記ノードに関連付けられること、
ｆ）関連付けられた経費がステップｅ）で第１データ・セットに記録されたノードのそれぞれについて、前記第１データ・セットおよび前記第２データ・セット内のそのノードに関連する前記経費を比較し、そのノードに到達する他のすべての経費より悪い制限的経費およびより悪い加算的経費の両方を有するノードに到達するそのような経費のすべて、または、そのノードに到達する他のすべての経費と等しい制限的経費およびより悪い加算的経費を有するノードに到達する経費のすべてを、前記第１データ・セットから除去すること、
ｇ）ステップｆ）の後で前記第１データ・セットに経費が残らなくなるまでステップｂ）ないしｆ）を繰り返すこと
を含み、結果の第２データ・セットが、効率的な経費の集合を含む
方法。
【請求項２】
各制限的経費が、前記対応するパスの帯域幅を表す値を含み、前記最良の制限的経費が、最大の帯域幅を表す経費である、請求項１に記載の方法。
【請求項３】
各加算的経費が、前記対応するパスに関連する伝送遅延を表す値を含み、前記最良の加算的経費が、最小の伝送遅延を表す経費である、請求項１または２に記載の方法。
【請求項４】
前記パスの少なくとも１つが、複数のリンクおよび少なくとも１つの中間ノードを含む、前の請求項のいずれかに記載の方法。
【請求項５】
データ処理システムのプロセッサにロードされた時に、請求項１ないし４のいずれか一項に記載の効率的なパス経費の集合を導出する方法をコンピュータに実行させるプログラム。
【請求項６】
データ通信ネットワーク内のソース・ノードおよび複数の宛先ノードを含むノードのグループに関する効率的なパス経費の集合を導出する装置であって、前記グループ内のノードの間のパスに関する前記パス経費が、前記ネットワーク内で定義され、各パス経費が、制限的経費および加算的経費を含み、前記装置が、前記パス経費の第１データ・セットおよび第２データ・セットを保管するメモリと、制御論理とを含み、前記制御論理が、
ａ）前記第１データ・セットに、前記ソース・ノードから前記宛先ノードのすべてへの直接パスに関するパス経費を記録することであって、各記録される経費が、前記第１データ・セット内で、前記対応するパスによって到達されるノードに関連付けられること、
ｂ）前記第１データ・セットから最良のパス経費を選択することであって、前記最良のパス経費が、最良の制限的経費を含むパス経費として、あるいは、複数のパス経費が等しい制限的経費を有する場合に、最良の制限的経費および最良の加算的経費を有するパス経費として判定されること、
ｃ）ステップｂ）で選択された前記最良のパス経費を前記第２データ・セットに記録することであって、前記記録される経費が、前記第２データ・セット内で、前記対応するパスによって到達されるノードに関連付けられること、
ｄ）ステップｃ）で前記第２データ・セットに記録された前記経費を前記第１データ・セットから除去すること、
ｅ）前記第１データ・セットに、ステップｃ）で記録された前記経費に対応する前記パスによって到達される前記宛先ノードから前記グループ内の他のすべてのノードへの直接パスに関する累積パス経費を記録することであって、各記録される累積パス経費が、前記第１データ・セット内で、前記対応するパスによって到達される前記ノードに関連付けられること、
ｆ）関連付けられた経費がステップｅ）で第１データ・セットに記録されたノードのそれぞれについて、前記第１データ・セットおよび前記第２データ・セット内のノードに関連する前記経費を比較し、そのノードに到達する他のすべての経費より悪い制限的経費およびより悪い加算的経費の両方を有するノードに到達するそのような経費のすべて、または、そのノードに到達する他のすべての経費と等しい制限的経費およびより悪い加算的経費を有するノードに到達する経費のすべてを、前記第１データ・セットから除去すること、
ｇ）ステップｆ）の後で前記第１データ・セットに経費が残らなくなるまでステップｂ）ないしｆ）を繰り返すこと
を行うように構成され、結果の第２データ・セットが、効率的な経費の集合を含む
装置。
【請求項７】
各制限的経費が、前記対応するパスの帯域幅を表す値を含み、前記最良の制限的経費が、最大の帯域幅を表す経費である、請求項６に記載の装置。
【請求項８】
各加算的経費が、前記対応するパスに関連する伝送遅延を表す値を含み、前記最良の加算的経費が、最小の伝送遅延を表す経費である、請求項６または７に記載の装置。
【請求項９】
前記パスの少なくとも１つが、複数のリンクおよび少なくとも１つの中間ノードを含む、請求項６ないし８のいずれかに記載の装置。
【請求項１０】
それぞれがデータ通信ネットワークのパスに接続される複数のポートと、前記ポートに結合される、請求項６ないし９のいずれかに記載の効率的なパス経費の集合を導出する装置とを含むデータ・ネットワーキング装置。
【請求項１１】
複数のパスによって相互接続される複数のノードを含むデータ・ネットワークであって、前記ノードの少なくとも１つが、請求項１０に記載のデータ・ネットワーキング装置を含む、データ・ネットワーク。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、全般的にはデータ通信ネットワークでの経費に関し、具体的には、データ通信ネットワークのノードのグループに関する効率的なパス経費の集合を導出する装置、方法、およびコンピュータ・ネットワークに関する。
【０００２】
【従来の技術】
インターネットなどの大規模ネットワークでのサービス品質（ＱｏＳ）のサポートは、異機種アプリケーションにとってますます重要になりつつある。ＱｏＳを保証するためには、エンド・ユーザを接続するパスが、所与の要件を満足しなければならない。したがって、ルーティング決定が、ＱｏＳ保証を提供する際の重要な考慮事項である。したがって、ルーティング・プロトコルは、ネットワーク内のさまざまなリンクによってサポートされるトラフィック特性を知っているべきである。
【０００３】
ＱｏＳ拡張機能が、Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ（ＯＳＰＦ）プロトコルなどの周知のルーティング・プロトコルについて提案されてきた。そのような拡張機能の例が、アポストロポーロス（Ａｐｏｓｔｏｌｏｐｏｕｌｏｓ）他著、「Ｉｍｐｌｅｍｅｎｔａｔｉｏｎａｎｄ Ｐｅｒｆｏｒｍａｎｃｅ Ｍｅａｓｕｒｅｍｅｎｔｓ ｏｆ ＱｏＳ Ｒｏｕｔｉｎｇ Ｅｘｔｅｎｓｉｏｎｓ ｔｏ ＯＳＰＦ」、Ｐｒｏｃｅｅｄｉｎｇ ｏｆＩＥＥＥ ＩＮＦＯＣＯＭ’９９， ｐｐ． ７５−８３， Ｎｅｗ Ｙｏｒｋ、１９９９年３月に記載されている。ＯＳＰＦプロトコルは、リンク状態ルーティング・プロトコルの例である。そのようなプロトコルが、大規模ネットワークで効率的に動作しないことが広く認められている。したがって、スケーラビリティに関して、ＯＳＰＦネットワークは、複数のルーティング区域に分割される。ＯＳＰＦプロトコルは、モイ（Ｍｏｙ）著、「ＯＳＰＦＶｅｒｓｉｏｎ ２」、Ｉｎｔｅｒｎｅｔ Ｅｎｇｉｎｅｅｒｉｎｇ Ｔａｓｋ Ｆｏｒｃｅ （ＩＥＴＦ） Ｒｅｑｕｅｓｔ ｆｏｒ Ｃｏｍｍｅｎｔｓ （ＲＦＣ）２３２８、１９９８年４月にさらに記載されている。
【０００４】
当技術分野で周知のもう１つの類似するルーティング・プロトコルが、「ＰｒｉｖａｔｅＮｅｔｗｏｒｋ ｔｏ Ｎｅｔｗｏｒｋ Ｉｎｔｅｒｆａｃｅ Ｓｐｅｃｉｆｉｃａｔｉｏｎ， Ｖｅｒｓｉｏｎ １．０」、ｔｈｅ ＡＴＭ Ｆｏｒｕｍ，、１９９６年３月に記載のＰｒｉｖａｔｅＮｅｔｗｏｒｋ ｔｏ Ｎｅｔｗｏｒｋ Ｉｎｔｅｒｆａｃｅ（ＰＮＮＩ）である。ＰＮＮＩプロトコルによれば、ネットワークが、複数のクラスタに分割されて、ルーティング階層が形成される。
【０００５】
グローバルに正確なパス選択を提供するために、ＯＳＰＦ区域であれＰＮＮＩクラスタであれ、使用される各ルーティング・ドメインのトラバース特性を検討しなければならない。ハオ（Ｈａｏ）他著、「Ｏｎ Ｓｃａｌａｂｌｅ ＱｏＳ Ｒｏｕｔｉｎｇ， Ｐｅｒｆｏｒｍａｎｃｅ Ｅｖａｌｕａｔｉｏｎ ｏｆ ＴｏｐｏｌｏｇｙＡｇｇｒｅｇａｔｉｏｎ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ ＩＮＦＯＣＯＭ’２０００， Ｔｅｌ Ａｖｉｖ， Ｉｓｒａｅｌ、２０００年３月、およびオーダ（Ｏｒｄａ）他著、「ＱｏＳＲｏｕｔｉｎｇ： ａ Ｐｒｅｃｏｍｐｕｔａｔｉｏｎ Ｐｅｒｓｐｅｃｔｉｖｅ」、Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ＩＥＥＥ ＩＮＦＯＣＯＭ’９９ ｐｐ．１２８−１３６， Ｔｅｌ Ａｖｉｖ， Ｉｓｒａｅｌ、２０００年３月の両方で、パス計算効率のかなりの利益を、ネットワークの階層編成を介して得られることが提案されている。
【０００６】
イリアデス（Ｉｌｉａｄｉｓ）他著、「Ｔｒａｎｓｉｔｉｏｎ ＭａｔｒｉｘＧｅｎｅｒａｔｉｏｎ ｆｏｒ Ｃｏｍｐｌｅｘ Ｎｏｄｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ ＡＴＭＷｏｒｋｓｈｏｐ’９９， ｐｐ４８９−５００， Ｋｏｃｈｉ， Ｊａｐａｎ、１９９９年５月に記載されているのが、ドメインの入口出口ノードの対ごとのパス経費を与える推移行列によってルーティング・ドメインのトラバース特性を表す方法である。推移行列の各項目は、入口出口ノードの対応する対のトラバース特性の最小限の表現である。トラバース特性は、制限的経費メトリックス、加算的経費メトリックス、またはその両方に関して記述することができる。１つのメトリックスだけに関して記述された推移特性を、１次元とみなすことができる。Ｎ個のメトリックスに関して記述された推移特性を、Ｎ次元とみなすことができる。パスの加算的メトリックスは、パス内のすべてのリンクのすべての加算的メトリックスの合計である。パスの制限的メトリックスは、パス内のすべてのリンクの制限的メトリックスの最小値である。加算的メトリックスの例に、遅延経費および管理経費が含まれる。制限的メトリックスの例に、帯域幅が含まれる。トラバース特性の最小限の表現を、当技術分野では、有効フロンティアと称する。有効フロンティアを計算する従来の技法を、簡単に説明する。これらの技法を、下記の２つの判断基準に従って分類することが可能である。
・計算結果：技法のなかには、ネットワーク内のある入口出口ノードから他のすべての入口出口ノードへの有効フロンティアを計算するものがある。技法のなかには、入口出口ノードのすべての対の間で有効フロンティアを計算するものもある。前者の範疇に属する技法を、すべての入口出口ノードに適用しなければならないことを諒解されたい。
・遅延関数：技法のなかには、固定遅延関数だけをサポートするものがある。技法のなかには、固定遅延および帯域幅依存遅延の両方に適用できるものもある。
【０００７】
下記の３つの周知のアルゴリズムを使用して、最小限の表現を計算することができる。
・ボイヤ（Ｂａｕｅｒ）他著、「Ｅｆｆｉｃｉｅｎｔ ＦｒｏｎｔｉｅｒＦｏｒｍｕｌａｔｉｏｎ ｆｏｒ Ａｄｄｉｔｉｖｅ ａｎｄ Ｒｅｓｔｒｉｃｔｉｖｅ Ｍｅｔｒｉｃｓ ｉｎ Ｈｉｅｒａｒｃｈｉｃａｌ Ｒｏｕｔｉｎｇ」、Ｐｒｏｃｅｅｄｉｎｇｓｏｆ ｔｈｅ ＩＥＥＥ ＩＣＣ’００， ｐｐ． １３５３−５９， Ｎｅｗ Ｏｒｌｅａｎｓ、２０００年６月に記載のマルチ−ダイクストラ（Ｍｕｌｔｉ−Ｄｉｊｋｓｔｒａ）アルゴリズム。
・コーメン（Ｃｏｒｍｅｎ）他著、「Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏＡｌｇｏｒｉｔｈｍｓ」、ｔｈｅ ＭＩＴ Ｅｌｅｃｔｒｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ Ｓｅｒｉｅｓ， ＭＩＴＰｒｅｓｓ， ＩＳＢＮ ０−２６２−０３１４１２−８、１９８９年、ベルマン（Ｂｅｌｌｍａｎ）著、「Ｏｎ ａ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ」、Ｑｕａｒｔｅｒｌｙｏｆ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ， Ｖｏｌ．１６， Ｎｏ．１， ｐｐ．８７−９０、１９５８年、およびフォード（Ｆｏｒｄ Ｊｒ．）他著、「Ｆｌｏｗｓｉｎ Ｎｅｔｗｏｒｋｓ”」、Ｐｒｉｎｃｅｔｏｎ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ１９６２年に記載のベルマン−フォード（Ｂｅｌｌｍａｎ−Ｆｏｒｄ）アルゴリズム。
・フロイド（Ｆｌｏｙｄ）著、「Ａｌｇｏｒｉｔｈｍ ９７ （ＳｈｏｒｔｅｓｔＰａｔｈ）」、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ， Ｖｏｌ．５， Ｎｏ．６、１９６５年に記載のフロイド−ウォーシャル（Ｆｌｏｙｄ−Ｗａｒｓｈａｌｌ）アルゴリズム。
【０００８】
この３つのアルゴリズムのすべてが、一定遅延に適用可能である。しかし、ベルマン・フォード・アルゴリズムおよびフロイド−ウォーシャル・アルゴリズムだけが、帯域幅依存遅延を扱うことができる。また、マルチ−ダイクストラ・アルゴリズムおよびベルマン−フォード・アルゴリズムだけが、あるソースからすべてのノードへの有効フロンティア問題を解くことができる。マルチ−ダイクストラ・アルゴリズムおよびフロイド−ウォーシャル・アルゴリズムは、一般に、有効フロンティアの計算に関してベルマン−フォード・アルゴリズムより複雑さが少ない。したがって、これらのアルゴリズムの間での選択は、応用分野に基づかねばならない。たとえば、少数の入口出口頂点だけがあり、一定遅延だけが検討されるようになる場合には、マルチ−ダイクストラ・アルゴリズムが、フロイド−ウォーシャル・アルゴリズムより好ましい。
【０００９】
【発明が解決しようとする課題】
一般に、ルーティング・ドメインのあるノードから他のすべてのノードへの有効フロンティアを計算する従来の技法は、計算的に複雑であり、応用分野が限られる。そのような有効フロンティアを計算するより単純な方法を提供することが望ましい。さらに、「あるソースからすべてのノードへ」問題を解く方法を提供することが望ましい。
【００１０】
【課題を解決するための手段】
本発明によれば、データ通信ネットワーク内のソース・ノードおよび複数の宛先ノードを含むノードのグループに関する効率的なパス経費の集合を導出する方法であって、前記グループ内のノードの間のパスに関する前記パス経費が、前記ネットワーク内で定義され、各パス経費が、制限的経費および加算的経費を含み、前記方法が、
ａ）第１データ・セットに、前記ソース・ノードから前記宛先ノードのすべてへの直接パスに関する前記パス経費を記録することであって、各記録される経費が、前記第１データ・セット内で、前記対応するパスによって到達されるノードに関連付けられること、
ｂ）前記第１データ・セットから最良のパス経費を選択することであって、前記最良のパス経費が、最良の制限的経費を含むパス経費として、あるいは、複数のパス経費が等しい制限的経費を有する場合に、最良の制限的経費および最良の加算的経費を有するパス経費として判定されること、
ｃ）ステップｂ）で選択された前記最良のパス経費を第２データ・セットに記録することであって、前記記録される経費が、前記第２データ・セット内で、前記対応するパスによって到達されるノードに関連付けられること、
ｄ）ステップｃ）で前記第２データ・セットに記録された前記経費を前記第１データ・セットから除去すること、
ｅ）前記第１データ・セットに、ステップｃ）で記録された前記経費に対応する前記パスによって到達される前記宛先ノードから前記グループ内の他のすべてのノードへの直接パスに関する累積パス経費を記録することであって、各記録される累積パス経費が、前記第１データ・セット内で、前記対応するパスによって到達される前記ノードに関連付けられること、
ｆ）関連付けられた経費がステップｅ）で第１データ・セットに記録されたノードのそれぞれについて、前記第１データ・セットおよび前記第２データ・セット内のそのノードに関連する前記経費を比較し、そのノードに到達する他のすべての経費より悪い制限的経費およびより悪い加算的経費の両方を有するノードに到達するそのような経費のすべて、または、そのノードに到達する他のすべての経費と等しい制限的経費およびより悪い加算的経費を有するノードに到達する経費のすべてを、前記第１データ・セットから除去すること、
ｇ）ステップｆ）の後で前記第１データ・セットに経費が残らなくなるまでステップｂ）ないしｆ）を繰り返すこと
を含み、結果の第２データ・セットが、効率的な経費の集合を含む方法が提供される。
【００１１】
これによって、有利なことに、有効フロンティアを計算するはるかに単純で高速な方法が提供される。さらに、この方法によって、「あるソースからすべてのノードへ」問題を解くことが容易になる。さらに、この方法は、一定遅延および帯域幅依存遅延の両方に適用可能である。
【００１２】
各制限的経費が、前記対応するパスの帯域幅を表す値を含むことが好ましく、前記最良の制限的経費が、最大の帯域幅を表す経費である。各加算的経費が、前記対応するパスに関連する伝送遅延を表す値を含むことが好ましく、前記最良の加算的経費が、最小の伝送遅延を表す経費である。前記パスの少なくとも１つが、複数のリンクおよび少なくとも１つの中間ノードを含むことができる。
【００１３】
本発明は、データ処理システムのプロセッサにロードされた時に、前に説明した効率的なパス経費の集合を導出する方法を実行するように前記プロセッサを構成するコンピュータ・プログラム・コード手段を含むコンピュータ・プログラム要素にも拡張される。
【００１４】
本発明を別の態様から見ると、データ通信ネットワーク内のソース・ノードおよび複数の宛先ノードを含むノードのグループに関する効率的なパス経費の集合を導出する装置であって、前記グループ内のノードの間のパスに関する前記パス経費が、前記ネットワーク内で定義され、各パス経費が、制限的経費および加算的経費を含み、前記装置が、前記パス経費の第１データ・セットおよび第２データ・セットを保管するメモリと、制御論理とを含み、前記制御論理が、
ａ）前記第１データ・セットに、前記ソース・ノードから前記宛先ノードのすべてへの直接パスに関するパス経費を記録することであって、各記録される経費が、前記第１データ・セット内で、前記対応するパスによって到達されるノードに関連付けられること、
ｂ）前記第１データ・セットから最良のパス経費を選択することであって、前記最良のパス経費が、最良の制限的経費を含むパス経費として、あるいは、複数のパス経費が等しい制限的経費を有する場合に、最良の制限的経費および最良の加算的経費を有するパス経費として判定されること、
ｃ）ステップｂ）で選択された前記最良のパス経費を前記第２データ・セットに記録することであって、前記記録される経費が、前記第２データ・セット内で、前記対応するパスによって到達されるノードに関連付けられること、
ｄ）ステップｃ）で前記第２データ・セットに記録された前記経費を前記第１データ・セットから除去すること、
ｅ）前記第１データ・セットに、ステップｃ）で記録された前記経費に対応する前記パスによって到達される前記宛先ノードから前記グループ内の他のすべてのノードへの直接パスに関する累積パス経費を記録することであって、各記録される累積パス経費が、前記第１データ・セット内で、前記対応するパスによって到達される前記ノードに関連付けられること、
ｆ）関連付けられた経費がステップｅ）で第１データ・セットに記録されたノードのそれぞれについて、前記第１データ・セットおよび前記第２データ・セット内のノードに関連する前記経費を比較し、そのノードに到達する他のすべての経費より悪い制限的経費およびより悪い加算的経費の両方を有するノードに到達するそのような経費のすべて、または、そのノードに到達する他のすべての経費と等しい制限的経費およびより悪い加算的経費を有するノードに到達する経費のすべてを、前記第１データ・セットから除去すること、
ｇ）ステップｆ）の後で前記第１データ・セットに経費が残らなくなるまでステップｂ）ないしｆ）を繰り返すこと
を行うように構成され、結果の第２データ・セットが、効率的な経費の集合を含む
装置が提供される。
【００１５】
本発明は、それぞれがデータ通信ネットワークのパスに接続される複数のポートと、前に説明した効率的なパス経費の集合を導出する装置とを含むデータ・ネットワーキング装置に拡張される。本発明は、さらに、複数のパスによって相互接続される複数のノードを含むデータ・ネットワークであって、前記ノードの少なくとも１つが、そのようなデータ・ネットワーキング装置を含む、データ・ネットワークに拡張される。
【００１６】
【発明の実施の形態】
先に進む前に、関係する用語および式を定義し、説明する。
【００１７】
表現「制限的経費」は、本明細書で、たとえば帯域幅など、リンクの次元または特性の関数として経費を記述するのに使用される。制限的経費Ｃは、たとえば、Ｃ＝最大値−帯域幅、またはＣ＝１／帯域幅として定義することができる。制限的経費の定義によれば、パスの最も弱いリンクによって、この経費が定義される。制限的経費の反対が、加算的経費である。加算的経費は、たとえばリンクの遅延に依存する。
【００１８】
単語「ノード」または「頂点」は、本明細書で、ルータ、スイッチ、ブリッジ、ブルータ、ハブ、および通信ネットワーク内で情報を送信または受信する任意の他のデータ・ネットワーキング装置に関する包括的な用語として使用される。
【００１９】
ネットワークを、有向グラフによってモデル化することができる。下記の規約を使用する。
・ネットワークのノードを、グラフの頂点と称する。
・２つのネットワーク・ノードの間のリンクを、グラフの２つの頂点の間の直接パスまたは辺と称する。
【００２０】
Ｇ（Ｖ，Ｅ）が、所与の時点でのネットワークを表す有向グラフであるものとする。Ｖは、頂点の集合であり、Ｅは、有向辺の集合である。したがって、すべてのｖｉ、ｖｊ∈Ｖについて、ｖｉとｖｊが接続される場合に、辺
【数１】
2004515120.tif 000002
が存在する。頂点を、複数の平行の辺によって接続することができる。２つの頂点ｖｉおよびｖｊを接続する辺の集合を、
【数２】
2004515120.tif 000003
と表す。表記
【数３】
2004515120.tif 000004
は、頂点ｖｉおよびｖｊを接続する任意の辺を指す。
【００２１】
ｓおよびｔが、グラフＧ（Ｖ，Ｅ）の２つの頂点であるものとする。Ｐｓ，ｔが、ｓをｔに接続するパスの集合
【数４】
2004515120.tif 000005
であるものとする。ｓからｔへのパスが存在しない場合には、Ｐｓ，ｔ＝Φである。長さ｜｜ρ｜｜＝ｎのパスρ∈Ｐｓ，ｔは、ｎ個の辺のシーケンス
【数５】
2004515120.tif 000006
であり、
ｖ０＝ｓ
ｖｎ＝ｔ
【数６】
2004515120.tif 000007
である。
【００２２】
頂点ｖは、ｖ＝ｖｉまたはｖ＝ｖｉ＋１のいずれかの辺
【数７】
2004515120.tif 000008
が存在する場合に、パスρの一部であるといわれる。
【００２３】
パスおよび辺に関するメトリックによって、ネットワーク内の使用可能なリソースに関する情報が提供される。使用可能な帯域幅および伝送遅延に関するメトリックを、これから定義する。しかし、本明細書で提示される観察が、本明細書で提供する定義にあてはまる任意の制限的メトリックまたは加算的メトリックに適用可能であることを諒解されたい。
【００２４】
辺
【数８】
2004515120.tif 000009
について、使用可能な帯域幅を、
【数９】
2004515120.tif 000010
によって表す。使用可能な帯域幅が制限的と言われるのは、パスの使用可能な帯域幅が、そのパスによってトラバースされる辺の使用可能な帯域幅の最小値になるからである。長さｎのｓからｔへの可能なパスρ、ρ∈Ｐｓ，ｔについて、使用可能な帯域幅は、次式になる。
【数１０】
2004515120.tif 000011
【００２５】
辺の伝送遅延が、要求された帯域幅ｂの関数であると仮定する。したがって、辺ε∈Ｅおよび要求された帯域幅ｂについて、伝送遅延は、
【数１１】
2004515120.tif 000012
によって与えられる。ｂ＞Ｂ（ε）の場合には、Ｄ（ε，ｂ）＝∞である。伝送遅延が加算的と言われるのは、パスの伝送遅延が、トラバースされる辺の伝送遅延の合計になるからである。長さｎのｓからｔへの可能なパスρ∈Ｐｓ，ｔについて、伝送遅延は、次式になる。
【数１２】
2004515120.tif 000013
【００２６】
辺ε∈ρについて、要求された帯域幅ｂ＞Ｂ（ε）の場合に、Ｄ（ρ，ｂ）＝∞である。そうでない場合には、Ｄ（ρ，ｂ）は有限である。
【００２７】
以下で、入口出口頂点の対の２次元推移特性を定義する。推移特性の次元は、帯域幅および遅延である。その後、入口出口頂点の集合への拡張を検討する。
【００２８】
ルーティング・ドメインを表す前述のグラフＧ（Ｖ，Ｅ）を検討されたい。ｓ，ｔ∈Ｖが、２つの入口出口頂点であるものとする。ルーティング決定を行うための当のｓからｔまでのトラバース・メトリックスが、最大使用可能帯域幅Ｂｍａｘおよび要求された帯域幅ｂに関する最大伝送遅延関数Ｄｅｆｆ（ｂ）である。この両方が、ｓをｔに接続するパスの集合Ｐｓ，ｔに依存する。具体的に言うと、次式の通りである。
【数１３】
2004515120.tif 000014
【００２９】
使用可能帯域幅および伝送遅延の定義から、ｂ≦Ｂｍａｘｓ，ｔの場合にＤｅｆｆｓ，ｔ（ｂ）＜∞、ｂ＞Ｂｍａｘｓ，ｔの場合にＤｅｆｆｓ，ｔ（ｂ）＝∞になる。したがって、Ｄｅｆｆｓ，ｔが、すべての帯域幅について最小の移転を有するパスを表すので、Ｄｅｆｆｓ，ｔは、入口出口対ｓ、ｔのトラバース・メトリックスを記述するのに十分である。Ｄｅｆｆｓ，ｔによって、ｓからｔへの使用可能帯域幅および伝送遅延に関する有効フロンティアも定義される。定義により、Ｄｅｆｆｓ，ｔは、パスの集合Ｐｓ，ｔに依存する。しかし、Ｐｓ，ｔの部分集合だけが、有効フロンティアに寄与する。以下では、この集合を、ｓおよびｔに関する有効パスまたはＰＥｓ，ｔと称する。
【数１４】
2004515120.tif 000015
【００３０】
有効フロンティアは、一連の線分とみなすことができ、この線分のそれぞれが、下記のパスの送信遅延関数に対応する。
【数１５】
2004515120.tif 000016
【００３１】
ここで、ｂｎ＝Ｂｍａｘｓ，ｔ、ｂ０＝０、であり、ｉ∈［１，ｎ］に関して、ρｉが、次式によって与えられる。
【数１６】
2004515120.tif 000017
【００３２】
式（７）を満足する複数のパスが存在する可能性があるという点で、ρｉが一意でない場合があることに留意されたい。また、いくつかの形の遅延関数に関して、単一のパスが複数の線分に寄与することがありえる。たとえば、式（６）で、いくつかのｉ≠ｊについて、ρｉ≡ρｊが可能である。
【００３３】
図１を参照すると、一定遅延パスに関する有効フロンティアの例が示されている。Ｄ（ρ，ｂ）がｂと独立であり、したがって、Ｄ（ρ）と書くことができるパスがある。この例では、ＰＥｓ，ｔが、４つのパスからなる。これらのパスの伝送遅延−帯域幅特性は、有効フロンティア上の黒い点として示されている。これらの有効パスの使用可能帯域幅および伝送遅延によって、Ｄｅｆｆｓ，ｔが完全に定義される。影付きの区域には、ＰＥｓ，ｔの一部ではない、白い点として示された、非有効解も含まれる。一定遅延パスに関して、達成可能な最小遅延を、次式として定義することが可能である。
【数１７】
2004515120.tif 000018
【００３４】
一般的な場合に、要求された帯域幅Ｂｍａｘｓ，ｔについてＤｍｉｎｓ，ｔを達成することが可能でない場合がある。これは、パスρ∈ＰＥｓ，ｔの遅延Ｄ（ρ）がすべて同一の場合に限って可能である。たとえば、ＰＥｓ，ｔに単一のパスだけが含まれる場合がそうである。したがって、すべてのネットワークについて、Ｄｅｆｆｓ，ｔ（Ｂｍａｘｓ，ｔ）＝Ｄｍｉｎｓ，ｔの場合に、「単一パス解」が存在する。
【００３５】
ここで、グラフに、Ｒ０、…、ＲＮ−１∈Ｖと呼ばれる、Ｎ個の入口出口頂点が含まれると仮定する。入口出口頂点の対Ｒｉ、Ｒｊのそれぞれについて、有効フロンティア
【数１８】
2004515120.tif 000019
が存在する。すべての有効フロンティアの集合によって、ネットワークのトラバース・メトリックスが完全に定義される。入口出口頂点のすべての対の間のすべての有効フロンティアの代数表現は、推移行列と称する行列で与えられる。推移行列を、下記のように指定することができる。
【数１９】
2004515120.tif 000020
【００３６】
推移行列は、基礎となるルーティング・ドメインのトポロジの代数表現である。これは、帯域幅メトリックスおよび遅延メトリックスに関するトラバース特性が完全に保たれるという意味で、ルーティング・ドメインの正確な表現である。
【００３７】
前に示したように、本発明が対処する問題は、推移行列の計算に関する。この問題には、特に、推移行列の各項目の計算が含まれる。図２を参照して、４つの出口入口頂点０、１、２、および３を含む例示的ネットワークを検討されたい。図３を参照すると、各項目は、入口出口頂点の各対の間の有効フロンティアである。
【００３８】
本発明の好ましい実施形態では、さまざまな頂点に対応する有効フロンティアが、並列に、「降順」の形で反復的に決定される。「降順」とは、大きい帯域幅を有する有効フロンティアの点が最初に見つけられ、等しい帯域幅の点の間で、より小さい遅延を有する点が先に見つけられることを意味する。以下で説明するｙ軸に沿って遅延、ｘ軸に沿って帯域幅を有する有効フロンティアのグラフ表現を検討すると、この手法によって、有効フロンティアを右（より広い帯域幅）から左（より狭い帯域幅）へと効果的に掃引することができる。本発明による有効フロンティアを決定する処理の好ましい例を、すぐに詳細に説明する。しかし、その前に、いくつかの予備定義を示す。
【００３９】
予備定義
Ｇ（Ｖ，Ｅ）が、所与の時点でのネットワークを表すグラフであるものとする。Ｖは、頂点の集合であり、Ｅは、有向辺の集合である。したがって、すべてのｖｉ、ｖｊ∈Ｖについて、ｖｉとｖｊが接続される場合に、辺
【数２０】
2004515120.tif 000021
が存在する。頂点を、複数の平行の辺によって接続することができる。２つの頂点ｖｉおよびｖｊを接続する辺の集合を、
【数２１】
2004515120.tif 000022
と表す。表記
【数２２】
2004515120.tif 000023
は、頂点ｖｉおよびｖｊを接続する任意の辺を指す。辺
【数２３】
2004515120.tif 000024
について、帯域幅および遅延に関するメトリック（経費）は、
【数２４】
2004515120.tif 000025
によって表され、ここで、
【数２５】
2004515120.tif 000026
および
【数２６】
2004515120.tif 000027
は、それぞれ辺に関連する使用可能帯域幅および遅延を表す。これらのメトリックは、非負の実数であると仮定する。言い換えると、
【数２７】
2004515120.tif 000028
であり、
【数２８】
2004515120.tif 000029
である。
【００４０】
２つの経費Ｃｉ＝（Ｂｉ，Ｄｉ）およびＣｊ＝（Ｂｊ，Ｄｊ）は、下記のように比較される。
・経費Ｃｉは、Ｂｉ＝ＢｊかつＤｉ＝Ｄｊである場合に限って、Ｃｊと等しい（Ｃｉ＝Ｃｊ）。そうでない場合には、経費Ｃｉは、Ｃｊと等しくない（Ｃｉ≠Ｃｊ）。
・Ｂｉ≧Ｂｊ、かつＤｉ≦Ｄｊ、かつ（Ｃｉ≠Ｃｊ）の場合に限って、経費Ｃｉは、Ｃｊよりよい、または、同等であるが、経費Ｃｊは、経費Ｃｉより悪い。
・経費Ｃｋは、Ｂｋ＝ｍｉｎ（Ｂｉ，Ｂｊ）かつＤｋ＝Ｄｉ＋Ｄｊである場合に限って、経費ＣｉおよびＣｊを拡大する（Ｃｋ＝ｅｘｔ（Ｃｉ，Ｃｊ））。
【００４１】
処理
ｖ０が、有効フロンティアがそこから計算されるソース頂点であるものとする。ｒｉ、ｉ＝１、…、Ｎ−１が、ｖ０からｖｉに到達する経費のリストであるものとする。ｆｉ、ｉ＝１、…、Ｎ−１が、頂点ｖｉに関連する有効フロンティアであるものとする。
【数２９】
2004515120.tif 000030
および
【数３０】
2004515120.tif 000031
が、それぞれ対応するリストを含むデータ・セットである、すなわち、
【数３１】
2004515120.tif 000032
かつ
【数３２】
2004515120.tif 000033
であるものとする。これらのデータ・セットは、たとえばテーブルとして配置することができる。
【００４２】
先に進む前に、下記の追加定義を与える。
ｉは、反復カウンタである。
ｖｍ（ｉ）は、ｉ回目の反復のタグを付けられたベクトルである。
Ｅｖｊは、頂点ｖｊから外に出る辺の集合である。
ｒｊは、頂点ｖ０から頂点ｖｊに到達する経費のリストである。
ｆｊは、頂点ｖｊに対応する有効フロンティアを含むリストである。
【００４３】
以下は、一連の規則）１から３）の形でのこの処理の擬似コード表現である。
【００４４】
初期化：
ｉ＝１
ｍ（１）＝０
ｆ０＝（∞，０）
【数３３】
2004515120.tif 000034
【数３４】
2004515120.tif 000035
【００４５】
ステップのｉ回目の反復：
１）集合
【数３５】
2004515120.tif 000036
に含まれる辺
【数３６】
2004515120.tif 000037
のそれぞれについて、ｄｏ
ａ）ｆｍ（ｉ）リストの最後の項目および経費
【数３７】
2004515120.tif 000038
に基づいて、拡大されたパス
【数３８】
2004515120.tif 000039
の経費Ｃｊ＝（Ｂｊ，Ｄｊ）を計算する、すなわち、
【数３９】
2004515120.tif 000040
ｂ）ｉｆ　Ｃｊが、リストｆｉのすべての項目と同一またはそれより悪い　ｔｈｅｎ　Ｃｊを破棄する。
ｃ）ｅｌｓｅ　ｉｆ　Ｃｊが、リストｒｊのすべての項目と同一またはそれより悪い　ｔｈｅｎ　Ｃｊを破棄する。
ｅｌｓｅ　ｄｏ
ｄ）　　帯域幅および遅延（帯域幅項目が等しい場合に）に従ってリストをソートされた状態に保つことによって、リストｒｊにＣｊを入力する。
ｅ）　　リストｒｊ内でＣｊより悪いすべての項目を破棄する。
ｄｏｎｅ
２）ｉｆ
【数４０】
2004515120.tif 000041
データ・セットが空である　ｔｈｅｎ　停止。
３）ｅｌｓｅ　ｄｏ
ａ）たとえばリストｒｋに含まれる、
【数４１】
2004515120.tif 000042
データ・セットの最良の項目を選択する。最良の項目は、最大の帯域幅を有する項目とみなすことができ、複数の項目がある場合には、最低の遅延を有する項目とみなすことができる。残りの同一値の項目は、たとえばホップ・カウントなどの別の判断基準に従って、または任意に優劣を決めることができる。
ｂ）リストｒｋから項目を除去し、リストｆｋに置く
ｃ）カウンタを増分する：ｉ＝ｉ＋１
ｄ）ｍ（ｉ）＝ｋをセットする（その結果、ｖｍ（ｉ）＝ｖｋになる）
ｄｏｎｅ
ステップに戻る
【００４６】
例
図４を参照して、例の４ノード・ネットワークの頂点０から残りの頂点１、２、および３への有効フロンティアを判定する、本発明を実施する方法の例を説明する。本発明が、４個より多数または４個より少数のノードを有するネットワークに同等に適用可能であることを諒解されたい。
【００４７】
ステップ１
図５を参照すると、この方法は、頂点０から開始され、頂点０からの外向きのすべての辺を検討する。３つの辺によって、それぞれ頂点１、２、および３への接続性がもたらされる。頂点０に関連する現在の経費はない。したがって、頂点１、２、および３への対応する辺の経費が、上の規則１ｄ）に従って、
【数４２】
2004515120.tif 000043
データ・セットに挿入される。
【数４３】
2004515120.tif 000044
【００４８】
【数４４】
2004515120.tif 000045
データ・セットで、帯域幅に関する最良の経費は、頂点３である：９，５。この経費は、規則３ｂ）に従って、
【数４５】
2004515120.tif 000046
データ・セットから、頂点３の有効フロンティアに移動される。
【数４６】
2004515120.tif 000047
【００４９】
この処理は、９，５の関連する経費を有する頂点３に移動する。
【００５０】
ステップ２：
図６を参照すると、頂点３は、頂点１および２への２つの辺を有する。
【数４７】
2004515120.tif 000048
データ・セットにセットされた頂点３に関連する経費（９，５）によって拡大されたこの辺の経費が、図６に示されている。これらの経費は、
【数４８】
2004515120.tif 000049
データ・セットに頂点１および２の項目がまだないので、
【数４９】
2004515120.tif 000050
データ・セットに入力される。
【数５０】
2004515120.tif 000051
【００５１】
最も広い帯域幅値が、頂点２に対応する：８，１０。この値は、
【数５１】
2004515120.tif 000052
データ・セットから、頂点２の有効フロンティアに移動される。
【数５２】
2004515120.tif 000053
【００５２】
この処理は、８，１０の関連する経費を有する頂点２に移動する。
【００５３】
ステップ３：
図７を参照すると、頂点２は、頂点１および３への２つの辺を有する。
【数５３】
2004515120.tif 000054
データ・セットにセットされた頂点２に関連する経費（８，１０）によって拡大されたこれらの辺の経費が、図７に示されている。頂点１に到達する経費は、（６，１２）と等しく、これは、ｒ１リストの経費（６，９）より悪い。したがって、規則１ｃ）に従って、これを破棄する。頂点３に到達する経費は、（１，１１）と等しく、これは、ｆ３リストの経費（９，５）より悪い。したがって、規則１ｂ）に従って、これを破棄する。最も広い帯域幅値は、頂点２に対応する：
７，６）。
【数５４】
2004515120.tif 000055
【００５４】
この値が、
【数５５】
2004515120.tif 000056
データ・セットから、頂点２の有効フロンティアに移動される。
【数５６】
2004515120.tif 000057
【００５５】
この方法は、７，６の関連する費用を有する頂点２に進む。
【００５６】
ステップ４：
図８を参照すると、頂点２は、頂点１および３への２つの辺を有する。
【数５７】
2004515120.tif 000058
データ・セットにセットされた頂点２に関連する費用（７，６）によって拡大されたこれらの辺の経費が、図８に示されている。頂点１に到達する経費は、（６，８）と等しく、これは、ｒ１のすべての項目よりよい。したがって、規則１ｄ）に従って、これが
【数５８】
2004515120.tif 000059
データ・セットに入力される。しかし、項目（６，９）は、（６，８）より悪い。したがって、規則１ｅ）に従って、これが破棄される。頂点３に到達する経費は、（１，７）と等しく、これは、ｆ３リストの経費（９，５）より悪い。したがって、規則１ｂ）に従って、これが破棄される。
【数５９】
2004515120.tif 000060
【００５７】
最も広い帯域幅値は、頂点１に対応する：６，８。この値が、
【数６０】
2004515120.tif 000061
データ・セットから頂点１の有効フロンティアに移動される。
【数６１】
2004515120.tif 000062
【００５８】
この方法は、６，８の関連する経費を有する頂点１に進む。
【００５９】
ステップ５
図９を参照すると、頂点１は、頂点２および３への２つの辺を有する。頂点２に到達する経費は、（２，９）と等しく、これは、ｆ２リストの経費（７，６）より悪い。したがって、規則１ｂ）に従って、これが破棄される。頂点３に到達する経費は、（３，１１）と等しく、これは、ｆ３リストの経費（９，５）より悪い。したがって、規則１ｂ）に従って、これが破棄される。
【数６２】
2004515120.tif 000063
【００６０】
最も広い帯域幅値は、頂点１に対応する。この値が、
【数６３】
2004515120.tif 000064
データ・セットから頂点１の有効フロンティアに移動される。
【数６４】
2004515120.tif 000065
【００６１】
この処理は、４，１の関連する経費を有する頂点１に進む。
【００６２】
ステップ６：
図１０を参照すると、頂点１は、頂点２および３への２つの辺を有する。頂点２に到達する経費は、（２，２）と等しく、これは、ｆ２のすべての項目よりよい。したがって、これが、規則１ｄ）に従って、
【数６５】
2004515120.tif 000066
データ・セットに入力される。頂点３に到達する経費は、（３，４）と等しく、これは、ｆ３のすべての項目よりよい。したがって、これが、規則１ｄ）に従って、
【数６６】
2004515120.tif 000067
データ・セットに入力される。
【数６７】
2004515120.tif 000068
【００６３】
最も広い帯域幅値は、頂点３に対応する：３，４。この値が、
【数６８】
2004515120.tif 000069
データ・セットから有効フロンティアに移動される。
【数６９】
2004515120.tif 000070
【００６４】
この方法は、３，４の関連する経費を有する頂点３に進む。
【００６５】
ステップ７：
図１１を参照すると、頂点３は、頂点１および２への２つの辺を有する。頂点１に到達する経費は、（３，８）と等しく、これは、ｆ１リストの経費（４，１）より悪い。したがって、規則１ｂ）に従って、これが破棄される。しかし、頂点２に到達する経費は、（３，５）と等しく、これは、ｆ２またはｒ２のすべての項目よりよい。したがって、規則１ｄ）に従って、これが
【数７０】
2004515120.tif 000071
データ・セットに入力される。
【数７１】
2004515120.tif 000072
【００６６】
最も広い帯域幅値は、頂点２に対応する：３，５。この値が、
【数７２】
2004515120.tif 000073
データ・セットから頂点２の有効フロンティアに移動される。
【数７３】
2004515120.tif 000074
【００６７】
この方法は、３，５の関連する経費を有する頂点２に進む。
【００６８】
ステップ８：
図１２を参照すると、頂点２は、頂点１および２への２つの辺を有する。頂点１に到達する経費は、（３，７）と等しく、これは、ｆ１リストの経費（４，１）より悪い。したがって、規則１ｂ）に従って、これが破棄される。頂点３に到達する経費は、（１，６）と等しく、これは、ｆ３リストの経費（３，４）より悪い。したがって、規則１ｂ）に従って、これが破棄される。
【数７４】
2004515120.tif 000075
【００６９】
最も広い帯域幅値は、頂点２に対応する：２，２。この値が、
【数７５】
2004515120.tif 000076
データ・セットから頂点２の有効フロンティアに移動される。
【数７６】
2004515120.tif 000077
【００７０】
この方法は、２，２の関連する経費を有する頂点２に進む。
【００７１】
ステップ９：
図１３を参照すると、頂点２は、頂点１および３への２つの辺を有する。頂点１に到達する経費は、（２，４）であり、これは、ｆ１リストの経費（４，１）より悪い。したがって、規則１ｂ）に従って、これが破棄される。しかし、頂点３に到達する経費は、（１，３）と等しく、これは、ｆ３リストのすべての項目よりよい。したがって、これが、規則１ｄ）に従って、
【数７７】
2004515120.tif 000078
データ・セットに入力される。
【数７８】
2004515120.tif 000079
【００７２】
最も広い帯域幅値は、頂点３に対応する：１，３。この値が、
【数７９】
2004515120.tif 000080
データ・セットから頂点３の有効フロンティアに移動される。
【数８０】
2004515120.tif 000081
【００７３】
この方法は、１，３の関連する経費を有する頂点３に進む。
【００７４】
ステップ１０：
図１４を参照すると、頂点３は、２つの頂点１および２への辺を有する。頂点１に到達する経費は、（１，７）と等しく、これは、ｆ１リストの経費（４，１）より悪い。したがって、規則１ｂ）に従って、これが破棄される。頂点２に到達する経費は、（１，４）と等しく、これは、ｆ２リストの経費（２，２）より悪い。その結果、規則１ｂ）に従って、これが破棄される。
【数８１】
2004515120.tif 000082
【００７５】
【数８２】
2004515120.tif 000083
データ・セットに項目が残っていないので、この処理は、規則２）に従って終了する。
【００７６】
最終結果：
頂点０から頂点１、２、および３への有効フロンティアは、次の通りである：
【数８３】
2004515120.tif 000084
【００７７】
図１５から１７に、それぞれ頂点０から頂点１、２、および３への有効フロンティアをグラフとして示す。
【００７８】
図１８を参照すると、本発明の好ましい実施形態では、コンピュータ・プログラム・コードを含むコンピュータ・プログラム要素であって、コンピュータ・プログラム・コードが、データ処理システムのプロセッサにロードされた時に、データ通信ネットワーク内のソース・ノードおよび複数の宛先ノードを含むノードのグループに関する効率的なパス経費の集合を導出する方法を実行するようにプロセッサを構成し、グループ内のノードの間のパスのパス経費が、ネットワーク内で定義され、各パス経費が、使用可能な帯域幅を表す値などの制限的経費と、伝送遅延を表す値などの加算的経費とを含む、コンピュータ・プログラム要素が提供される。
【００７９】
この方法には、ステップ１０で、データ処理システムのメモリ内の第１データ・セットに、ソース・ノードから宛先ノードのすべてへの直接パスのパス経費を記録することが含まれる。各記録された経費は、第１データ・セット内で、対応するパスによって到達されるノードに関連付けられる。
【００８０】
ステップ２０で、最良のパス経費を、第１データ・セットから選択する。最良のパス経費は、最良の制限的経費を含むパス経費として、または、複数のパス経費に等しい制限的経費が含まれる場合に、最良の制限的経費および最良の加算的経費を有するパス経費として判定される。たとえば、制限的経費が、帯域幅を表す値である場合に、最良の制限的経費は、最大の帯域幅を表す経費である。同様に、加算的経費が、伝送遅延を表す値である場合に、最良の加算的経費は、最小の伝送遅延を表す経費である。
【００８１】
ステップ３０で、ステップ２０で選択された最良のパス経費が、データ処理システムのメモリ内の第２データ・セットに記録される。記録された経費は、第２データ・セット内で、対応するパスによって到達されるノードと関連付けられる。
【００８２】
ステップ４０で、ステップ３０で第２データ・セットに記録された経費を、第１データ・セットから除去する。除去には、削除、フラグ立て、またはさらなる考慮からその経費を排除するなんらかの他の処置を含めることができる。
【００８３】
ステップ５０で、グループ内の他のノードへのステップ３０で記録された経費に対応するパスによって到達される宛先ノードからの直接パスに関する累積パス経費を、第１データ・セットに記録する。記録される累積パス経費のそれぞれが、第１データ・セット内で、対応するパスによって到達されるノードに関連付けられる。
【００８４】
ステップ６０で、ステップ５０で関連する経費が第１データ・セットに記録されたノードのそれぞれについて、第１データ・セット内および第２データ・セット内の、そのノードに関連する経費を比較する。そのノードへの到達に関する他のそのような経費より悪い制限的経費およびより悪い加算的経費の両方を有するノードに到達するそのような経費のすべて、または、そのノードへの到達に関する他のそのような経費と等しい制限的経費およびより悪い加算的経費を有するノードに到達するそのような経費のすべてが、第１データ・セットから除去される。
【００８５】
ステップ７０で、ステップ６０で第１データ・セットに経費が残っていなくなるまで、ステップ２０から６０を繰り返す。ステップ８０で、結果の第２データ・セットに、効率的な経費の集合が含まれる。言い換えると、効率的な経費の集合に、ソース・ノードに関する有効フロンティアが含まれる。データ処理システムを、ルータ、スイッチ、ブリッジ、ブルータ、ハブ、または、通信ネットワーク内で情報を送信または受信する他のデータ・ネットワーキング装置とすることができることを諒解されたい。
【００８６】
図１９を参照すると、本発明のもう１つの実施形態で、データ通信ネットワーク１７０への接続のための入出力ポート１１０、入出力ポート１１０に結合されたプロセッサ１２０、およびプロセッサに結合されたメモリ１３０を含むデータ・ネットワーキング装置１００が提供される。メモリには、第１データ・セットのストレージに割り振られた空間１４０、第２データ・セットのストレージに割り振られた空間１５０、および制御論理プログラム・コード１６０が含まれる。動作中に、データ・ネットワーキング装置は、データ通信ネットワーク内のソース・ノードおよび複数の宛先ノードを含むノード・グループに関する効率的なパス経費の集合を導出する。データ処理装置は、データ通信ネットワークのソース・ノードを実施することができる。グループ内のノードの間のパスのパス経費は、ネットワーク内で定義され、各パス経費に、制限的経費および加算的費用が含まれる。動作時に、制御論理１６０は、
ａ）前記第１データ・セット１４０に、前記ソース・ノードから前記宛先ノードのすべてへの直接パスに関するパス経費を記録することであって、各記録される経費が、前記第１データ・セット内で、前記対応するパスによって到達されるノードに関連付けられること、
ｂ）前記第１データ・セット１４０から最良のパス経費を選択することであって、前記最良のパス経費が、最良の制限的経費を含むパス経費として、あるいは、複数のパス経費が等しい制限的経費を有する場合に、最良の制限的経費および最良の加算的経費を有するパス経費として判定されること、
ｃ）ステップｂ）で選択された前記最良のパス経費を第２データ・セット１５０に記録することであって、前記記録される経費が、前記第２データ・セット内１５０で、前記対応するパスによって到達されるノードに関連付けられること、
ｄ）ステップｃ）で前記第２データ・セット１５０に記録された前記経費を前記第１データ・セット１４０から除去すること、
ｅ）前記第１データ・セット１４０に、ステップｃ）で記録された前記経費に対応する前記パスによって到達される前記宛先ノードから前記グループ内の他のすべてのノードへの直接パスに関する累積パス経費を記録することであって、各記録される累積パス経費が、前記対応するパスによって到達される前記ノードに関連付けられること、
ｆ）関連付けられた経費がステップｅ）で第１データ・セットに記録されたノードのそれぞれについて、前記第１データ・セット１４０および前記第２データ・セット１５０内のノードに関連する前記経費を比較し、そのノードに到達する他のすべての経費より悪い制限的経費およびより悪い加算的経費の両方を有するノードに到達するそのような経費のすべて、または、そのノードに到達する他のすべての経費と等しい制限的経費およびより悪い加算的経費を有するノードに到達する経費のすべてを、前記第１データ・セット１４０から除去すること、
ｇ）ステップｆ）の後で前記第１データ・セットに経費が残らなくなるまでステップｂ）ないしｆ）を繰り返すことを実行するようにプロセッサを構成する。結果の第２データ・セットに、効率的な経費の集合が含まれる。図１９に関して前に説明した本発明の実施形態では、制御論理１６０が、コンピュータ・プログラム・コードであるが、本発明の他の実施形態で、制御論理を少なとも部分的にハードウェア論理回路で実施できることを諒解されたい。パスの少なくとも１つに、複数のリンクと少なくとも１つの中間ノードを含めることができることも諒解されたい。
【００８７】
要約として、前に説明した本発明の好ましい実施形態では、効率的なパス経費の集合が、データ通信ネットワーク内のソース・ノードおよび複数の宛先ノードを含むノードのグループについて導出され、グループ内のノードの間のパスのパス経費は、ネットワーク内で定義され、各パス経費に、制限的経費および加算的経費が含まれ、まずより広い帯域幅のパスを繰り返し識別すること、等しい帯域幅を有する複数のパスに出会った時に、より少ない伝送遅延が関連付けられたパスを選択することが含まれる。
【図面の簡単な説明】
【図１】
一定遅延パスに関する有効フロンティアの例を示すグラフである。
【図２】
４つの入口出口ノードを有する例示的ネットワークの簡略化された図である。
【図３】
クラスタ・ネットワークに対応する推移行列の説明図である。
【図４】
ネットワークに対応する有向グラフである。
【図５】
ネットワークに対応する有向グラフである。
【図６】
ネットワークに対応する有向グラフである。
【図７】
ネットワークに対応する有向グラフである。
【図８】
ネットワークに対応する有向グラフである。
【図９】
ネットワークに対応する有向グラフである。
【図１０】
ネットワークに対応する有向グラフである。
【図１１】
ネットワークに対応する有向グラフである。
【図１２】
ネットワークに対応する有向グラフである。
【図１３】
ネットワークに対応する有向グラフである。
【図１４】
ネットワークに対応する有向グラフである。
【図１５】
ネットワークのノード０からノード１への有効フロンティアを示すグラフである。
【図１６】
ネットワークのノード０からノード２への有効フロンティアを示すグラフである。
【図１７】
ネットワークのノード０からノード３への有効フロンティアを示すグラフである。
【図１８】
本発明による効率的なパス経費の集合を導出する方法の例に対応する流れ図である。
【図１９】
本発明を実施するデータ・ネットワーキング装置のブロック図である。
【図１】
2004515120.tif 000085
【図２】
2004515120.tif 000086
【図３】
2004515120.tif 000087
【図４】
2004515120.tif 000088
【図５】
2004515120.tif 000089
【図６】
2004515120.tif 000090
【図７】
2004515120.tif 000091
【図８】
2004515120.tif 000092
【図９】
2004515120.tif 000093
【図１０】
2004515120.tif 000094
【図１１】
2004515120.tif 000095
【図１２】
2004515120.tif 000096
【図１３】
2004515120.tif 000097
【図１４】
2004515120.tif 000098
【図１５】
2004515120.tif 000099
【図１６】
2004515120.tif 000100
【図１７】
2004515120.tif 000101
【図１８】
2004515120.tif 000102
【図１９】
2004515120.tif 000103
【国際公開パンフレット】
2004515120.tif 000104
2004515120.tif 000105
2004515120.tif 000106
2004515120.tif 000107
2004515120.tif 000108
2004515120.tif 000109
2004515120.tif 000110
2004515120.tif 000111
2004515120.tif 000112
2004515120.tif 000113
2004515120.tif 000114
2004515120.tif 000115
2004515120.tif 000116
2004515120.tif 000117
2004515120.tif 000118
2004515120.tif 000119
2004515120.tif 000120
2004515120.tif 000121
2004515120.tif 000122
2004515120.tif 000123
2004515120.tif 000124
2004515120.tif 000125
2004515120.tif 000126
2004515120.tif 000127
2004515120.tif 000128
2004515120.tif 000129
2004515120.tif 000130
2004515120.tif 000131
2004515120.tif 000132
2004515120.tif 000133
2004515120.tif 000134
2004515120.tif 000135
2004515120.tif 000136
2004515120.tif 000137
2004515120.tif 000138
2004515120.tif 000139
【国際公開パンフレット（コレクトバージョン）】
2004515120.tif 000140
【国際調査報告】
2004515120.tif 000141
2004515120.tif 000142
2004515120.tif 000143