"ノードおよび相互接続するリンクのコンテンツ配信ツリーネットワークにおける公平な帯域幅の割り当てを判定する分散方法であって、最小限の情報のみがノード相互で交換されながら、独立して前記ノードの各々で計算を実行するステップであって、前記ノードでは、ツリーのルートが、前記ツリー全体に複数のプログラムをブロードキャストするサーバを有する、ステップと、公平な帯域幅の割り当ての問題を、問題EBAMによって定義するステップであって、前記ネットワークの各リンク上の複数のプログラム相互での公平な帯域幅の割り当てを判定する分散方法が、EBAMのための分散方法によって特定される、ステップとを備えることを特徴とする方法。複数のパフォーマンス関数を備える辞書的マクシミン目的関数によって、各プログラムとノードの組み合わせごとに1つ、問題EBAMを解決するステップをさらに備え、前記パフォーマンス関数が連続かつ狭義の単調増加関数であり、任意の特定プログラムに対して、前記パフォーマンス関数がすべてのノードで同一であることを特徴とする請求項1に記載の方法。リンク上で伝送されるすべてのプログラムの割り当てられた帯域幅の合計が、前記リンクの利用可能帯域幅の容量を超えないように、各リンクの帯域幅容量の制約によって、問題EBAMを解決するステップをさらに備えることを特徴とする請求項1に記載の方法。リンク上で伝送される各プログラムに割り当てられた帯域幅が、特定の下限を下回らず、かつ、ツリーのルートノードから目的地ノードへの経路に沿って、各プログラムに割り当てられた帯域幅が、1つのリンクから次のリンクへと減少し、増加しないような制約を適用することによって、問題EBAMを解決するステップをさらに備えることを特徴とする請求項1に記載の方法。前記EBAMのための分散方法が、a.前記ネットワークの各リンク上で伝送されるプログラムの集合を計算するステップであって、集合の計算が前記ツリーネットワークのリーフノードで再帰的に始まり、ツリーノードに沿って上方に移動して行われる、ステップと、b.その他のノードで実行される計算から独立して、発信リンク上で伝送される複数のプログラム相互での一時的な公平な帯域幅の割り当てを、そのノードから各発信リンクごとの各ノードにおいて、計算するステップであって、リンクi,jにおける複数のプログラム相互での前記割り当てが、問題SLBAM-i,jを解くことによって計算される、ステップと、c.前記リーフノードから計算を開始し、前記ツリーノードに沿って上方に移動する再帰的な計算を通じて、前記ツリーネットワークにおけるボトルネックリンクを判定するステップと、d.前記ボトルネックリンク上で伝送されるプログラムへ最終的な公平な帯域幅の割り当てを判定するステップと、e.ルートノードが前記ボトルネックリンクのヘッドノードであるサブツリーに含まれる、リンク上のプログラムへ最終的な公平な帯域幅の割り当てを判定するステップと、f.前記ボトルネックリンクのテールノードに、前記ツリーネットワークの前記ルートノードを結ぶ経路上に含まれる、リンク上のプログラムへ最終的な公平な帯域幅の割り当てを判定するステップと、g.いくつかのリンクのための新しい一時的な公平な帯域幅の割り当てを計算することをステップbで開始し、分散計算による新たな反復を継続するステップであって、すべてのリンク上のすべてのプログラムのための最終的な公平な割り当ての決定がいったん行われると、前記方法が終了する、ステップとを備えることを特徴とする請求項1に記載の方法。前記EBAMのための分散方法を使用して、リンク上で伝送される各プログラムに割り当てられた帯域幅に課せられる追加の上限により、問題EBAMを解決するステップをさらに備えることを特徴とする請求項1に記載の方法。複数のツリーを有するネットワークのための問題EBAMを解決するステップをさらに備え、各ツリーのルートで、サーバが複数のプログラムと、異なるツリーの共有リンクとをブロードキャストし、公平な解がEBAMのための分散方法によって得られることを特徴とする請求項1に記載の方法。動的環境においていくつかの入力パラメータが変化するときに、EBAMのための分散方法を繰り返し適用して、新しい公平な解を計算するステップをさらに備えることを特徴とする請求項1に記載の方法。ノードおよび相互接続するリンクのコンテンツ配信ツリーネットワークにおける公平な帯域幅の割り当てを判定する、コンピュータ上で動作するコンピュータ可読プログラムコードを有するコンピュータ可読媒体であって、最小限の情報のみがノード相互で交換されながら、独立して前記ノードの各々で計算を実行するステップであって、前記ノードでは、ツリーのルートが、前記ツリー全体に複数のプログラムをブロードキャストするサーバを有する、ステップと、公平な帯域幅の割り当ての問題を、問題EBAMによって定義するステップであって、前記ネットワークの各リンク上の複数のプログラム相互での公平な帯域幅の割り当てを判定する分散方法が、EBAMのための分散方法によって特定される、ステップとを備えることを特徴とするコンピュータ可読媒体。複数のパフォーマンス関数を備える辞書的マクシミン目的関数によって、各プログラムとノードの組み合わせごとに1つ、問題EBAMを解決するステップをさらに備え、前記パフォーマンス関数が連続かつ狭義の単調増加関数であり、任意の特定プログラムに対して、前記パフォーマンス関数がすべてのノードで同一であることを特徴とする請求項9に記載のコンピュータ可読プログラムコード。リンク上で伝送されるすべてのプログラムの割り当てられた帯域幅の合計が、前記リンクの利用可能帯域幅の容量を超えないように、各リンクの帯域幅容量の制約によって、問題EBAMを解決するステップをさらに備えることを特徴とする請求項9に記載のコンピュータ可読プログラムコード。リンク上で伝送される各プログラムに割り当てられた帯域幅が、特定の下限を下回らず、かつ、ツリーのルートノードから目的地ノードへの経路に沿って、各プログラムに割り当てられた帯域幅が、1つのリンクから次のリンクへと減少し、増加しないような制約を適用することによって、問題EBAMを解決するステップをさらに備えることを特徴とする請求項9に記載のコンピュータ可読プログラムコード。前記EBAMのための分散方法が、a.前記ネットワークの各リンク上で伝送されるプログラムの集合を計算するステップであって、集合の計算が前記ツリーネットワークのリーフノードで再帰的に始まり、ツリーノードに沿って上方に移動して行われる、ステップと、b.その他のノードで実行される計算から独立して、ノードから発信リンク上で伝送される複数のプログラム相互での一時的な公平な帯域幅の割り当てを、そのノードから各発信リンクごとの各ノードにおいて、計算するステップであって、リンクi,jにおける複数のプログラム相互での前記割り当てが、問題SLBAM-i,jを解くことによって計算される、ステップと、c.前記リーフノードから計算を開始し、前記ツリーノードに沿って上方に移動する再帰的な計算を通して、前記ツリーネットワークにおけるボトルネックリンクを判定するステップと、d.前記ボトルネックリンク上で伝送されるプログラムへ最終的な公平な帯域幅の割り当てを判定するステップと、e.ルートノードが前記ボトルネックリンクのヘッドノードであるサブツリーに含まれる、リンク上のプログラムへ最終的な公平な帯域幅の割り当てを判定するステップと、f.前記ボトルネックリンクのテールノードに、前記ツリーネットワークの前記ルートノードを結ぶ経路上に含まれる、リンク上のプログラムへ最終的な公平な帯域幅の割り当てを判定するステップと、g.いくつかのリンクのための新しい一時的な公平な帯域幅の割り当てを計算することをステップbで開始し、分散計算による新たな反復を継続するステップであって、すべてのリンク上のすべてのプログラムのための最終的な公平な割り当ての決定がいったん行われると、前記方法が終了する、ステップとを備えることを特徴とする請求項9に記載のコンピュータ可読プログラムコード。前記EBAMのための分散方法を使用して、リンク上で伝送される各プログラムに割り当てられた帯域幅に課せれる追加の上限により、問題EBAMを解決するステップをさらに備えることを特徴とする請求項9に記載のコンピュータ可読プログラムコード。複数のツリーを有するネットワークのための問題EBAMを解決するステップをさらに備え、各ツリーのルートで、サーバが複数のプログラムと、異なるツリーの共有リンクとをブロードキャストし、公平な解がEBAMのための分散方法によって得られることを特徴とする請求項9に記載のコンピュータ可読プログラムコード。動的環境においていくつかの入力パラメータが変化するときに、EBAMのための分散方法を繰り返し適用して、新しい公平な解を計算するステップをさらに備えることを特徴とする請求項9に記載のコンピュータ可読プログラムコード相互接続するリンクのコンテンツ配信ツリーにおいて公平な帯域幅の割り当てを判定するシステムであって、最小限の情報のみがノード相互で交換されながら、独立して前記ノードの各々で計算を実行する手段であって、前記ノードでは、ツリーのルートが、前記ツリー全体に複数のプログラムをブロードキャストするサーバを有する、手段と、公平な帯域幅の割り当ての問題を、問題EBAMによって定義する手段であって、前記ネットワークの各リンク上の複数のプログラム相互での公平な帯域幅の割り当てを判定する分散方法が、EBAMのための分散方法によって特定される、手段とを備えることを特徴とするシステム。前記EBAMのための分散方法が、a.前記ネットワークの各リンク上で伝送されるプログラムの集合を計算する手段であって、集合の計算が前記ツリーネットワークのリーフノードで再帰的に始まり、ツリーノードに沿って上方に移動して行われる、手段と、b.その他のノードで実行される計算から独立して、ノードから発信リンク上で伝送される複数のプログラム相互での一時的な公平な帯域幅の割り当てを、そのノードから各発信リンクごとの各ノードにおいて、計算する手段であって、リンクi,jにおける複数のプログラム相互での前記割り当てが、問題SLBAM-i,jを解くことによって計算される、手段と、c.前記リーフノードから計算を開始し、前記ツリーノードに沿って上方に移動する再帰的な計算を通して、前記ツリーネットワークにおけるボトルネックリンクを判定する手段と、d.前記ボトルネックリンク上で伝送されるプログラムへ最終的な公平な帯域幅の割り当てを判定する手段と、e.ルートノードが前記ボトルネックリンクのヘッドノードであるサブツリーに含まれる、リンク上のプログラムへ最終的な公平な帯域幅の割り当てを判定する手段と、f.前記ボトルネックリンクのテールノードに、前記ツリーネットワークの前記ルートノードを結ぶ経路上に含まれる、リンク上のプログラムへ最終的な公平な帯域幅の割り当てを判定する手段と、g.いくつかのリンクのための新しい一時的な公平な帯域幅の割り当てを計算することを手段bで開始し、分散計算による新たな反復を継続する手段であって、すべてのリンク上のすべてのプログラムのための最終的な公平な割り当ての決定がいったん行われると、前記方法が終了する、手段とを備えることを特徴とする請求項17に記載のシステム。図、特に図1を参照すると、有向リンクを有する7つのノード0、1、2、3、4、5、および6を備えるツリーネットワークの例100が示される。ルートノードノード0は、複数のプログラムを保存し、かつブロードキャストするサーバを有する。本発明の例では、プログラム1、2、3、および4101は複数のノードでのプログラムの要求に対してサービスを提供する。リンクに沿った番号が、ブロードキャストで利用可能なリンクの帯域幅容量である。従って、リンク0,2は、130の単位例えば、Mbps102の容量を有する。本例では、ノード1、2、3、4、5、および6の各々は、いくつかのプログラムの要求を有することができる要求のないノードがある場合もある。例えば、ノード2は、プログラム3および4103の要求を有する。各リンクの帯域幅容量が制限されている故に、様々なノードで要求されたすべてのプログラムを提供するために、慎重な帯域幅の割り当てが必要とされる。ノード間の方法によって実行され、かつ交換される情報は、双方向にすることができるが、リンクがブロードキャストの目的のために向けられていることに留意されたい。ノード相互で最小限の量のみの情報を交換しながら、帯域幅の割り当てを判定するために実行される集中的な計算は、ノードごとに独立して実行される。この目的を達成するために、好ましくは計算を実行するためのコンピューティング手段が各ノードに配置される。具体的には、これらの計算は、リンク104の各々のテールノードによってなされる。従って、例えば、ノード1は、リンク1,3および1,4のための計算をなすであろう。特定のプログラムのためにリンクへ割り当てられた帯域幅は、ルートノードからエンドノードへの経路内の1つのリンクから次へと、減少し得るが、増加しない場合があるので留意されたい。これらの制約は、ノードにて独立して実行される集中計算の間には無視されるツリー状順序付けの制約として表現される。それにもかかわらず、これらの順序付けの制約は、アルゴリズムが終了した時点で満たされなければならない。図1の例は、本発明の分散方法を説明する以下の記載において使用される。前述の記載は例示の目的であり、本発明の限定のためではないことが理解されるであろう。ノードで要求されたプログラムの配信品質から得られる満足度は、ノードへの着信リンク上のプログラムに割り当てられた帯域幅により、連続して厳密に増加するパフォーマンス関数を通じて特定される。例えば、プログラム1のためのパフォーマンス関数、およびリンク2、6上のプログラム1に割り当てられる帯域幅は、プログラム1のためのノード6の満足値を判定する。目的は、公平な方法で帯域幅を割り当てることであり、すなわち、目的は、ベクトルの要素が非減少順にソートされる、パフォーマンス関数値の辞書式最大可能ベクトルを判定することである。直感的には、連続的な決定変数のために、公平な解は、減少前の値が増加前の前者の値を超えないいくつかのパフォーマンス関数の値を低下させることなく、パフォーマンス関数値のいずれもが適当に増加することがないものとすることである。非特許文献7は、公平なリソース割り当ての問題に関する解説的な論文を提示する。特定のプログラムに割り当てられる帯域が、ルートノードから離れる経路に沿って1つのリンクから次へ増加させることができないことを保証する順序付けの制約をも、容量の制約だけでなく、実行可能解が満たさなければならないことに留意されたい。その他の制約はまた、そのプログラムを伝送するいずれかのリンク上の特定のプログラムに割り当てられた帯域幅の上限および下限として課され得る。公平な帯域幅の割り当て問題の数学的定式化が以下に提供される。ツリーネットワークTN,Aを考えてみると、Nはノードの集合であり、Aは相互接続する有向リンクの集合である。ノードは指数i,j、およびkで表され、リンクはエンドノードi,jのダブルトンで表され、ここで、iがリンクのテールノードで、jがヘッドノードである。リンクi,jは利用可能な帯域幅の容量限界ci,jを有する。サーバはプログラム集合Pを有するルートノードに位置される。プログラムは、指標pで表される。各ノードi∈N\0すなわち、ノード0以外のN内のノードは、プログラムの部分集合Pi、Pi∈Pの要求を有し、ここで、Piは空であるとすることができるルートノードで要求されるプログラムは、それらが任意のリンク帯域幅を使用せずに直接提供されるので考慮されない。表記法を説明するために図1を考慮されたい。ノードの集合はN={0,1,...,6}であり、リンクの集合はA={0,1,0,2,1,3,1,4,2,5,2,6}であり、プログラムの集合はP={1,2,3,4}である。利便性のために、Nにおけるノードは番号が付けられ、それで任意のリンクi,j,j>iにおいても、リンク容量がc0,1=120,c0,2=130、c1,3=50,c1,4=100,c2,5=90,c2,6=80となる。プログラムpがノードjにて要求された場合、集合NP={j,p|p∈Pj,j∈N}、すなわち、ダブルトンj,p∈NPとする。図1において、NP={1,2,2,3,2,4,3,1,3,3,4,2,4,3,5,1,5,2,6,1,6,3}である。分散アルゴリズムにおいて、各ノードは、そのローカル環境、すなわち、着信リンクおよび発信リンク、発信リンクの各々の容量、およびノードで要求されたプログラムを認識する。例えば、図1では、ノード2は、着信リンク0,2、発信リンク2,5容量90および2,6容量80、ならびに、ノード2で要求されたプログラムプログラム3および4を認識する。Dはリンクi,j上に伝送されるプログラムの集合とする。例えば、D={1,2,3}およびD={2,3}である。分散アルゴリズムにおいては、後述するように集合Dがノードjで計算されて、そこからノードiへ提供される。ノードiは、リンクi,j上の帯域幅の割り当てのための分散計算を実行する。プログラムは有向リンクに沿ってブロードキャストされることに留意されたい。しかし、分散アルゴリズムは、両方の方向に一定の情報の交換を必要とする。これは、ツリーネットワークは有向リンクに沿ってだけでなく、反対の方向に沿って、この情報を移動させる能力を有すると仮定される。決定変数およびパフォーマンス関数xp=プログラムpのためのリンクi,j上に割り当てられた帯域幅、ここで、xpは連続しており、そして、xp≧Bp、ここで、Bpがプログラムpに必要な帯域幅の下限である。例えば、図1のリンク0,2は、帯域幅をプログラム1、2、3および4に割り当てており、ここで、プログラム1はノード5および6で要求されており、プログラム2はノード5で要求されており、プログラム3はノード2および6で要求されており、プログラム4はノード2で要求されている。x=決定変数のベクトルxp、j,p∈NP。Fjpxp=ノードjで要求されるプログラムpに関連付けられたパフォーマンス関数、ここで、xpがリンクi,j上の、したがって、ノードjへのプログラムpに割り当てられる帯域幅である。例えば、図1のノード5でのパフォーマンス関数は、F51x1およびF52x2である。パフォーマンス関数は、ノードjにおけるプログラムpのための帯域幅xpにより顧客の満足度を表す。Fjpxpが連続する狭義の単調増加関数であると仮定される。また、任意の特定のプログラムpのために、Fjpxpがプログラムpの要求を有するすべてのノードで同一であると仮定される。従って、パフォーマンス関数の表記はFpxpに簡略化される。線形パフォーマンス関数が満足度を測定する唯一の合理的な方法であることに留意されたい。例えば、凹パフォーマンス関数例えば、対数関数等は、提供される帯域幅が増加するときに、当該関数が満足度での増加率の減少を呈するので、しばしば、特定の応用例に応じて、より適切な場合がある。帯域幅の割り当ての問題は、種々の制約を満たさなければならない。リンクの各々上に伝送されるすべてのプログラムに割り当てられた帯域幅の合計は、利用可能な帯域幅容量を超えることはできない。一方で、各プログラムに割り当てられる帯域幅は下限を満たす必要がある。また、リンクi,j上の任意のプログラムPのために割り当てられる帯域幅は、プログラムPを伝送するノードjからのすべての発信リンク上のプログラムpに割り当てられる帯域幅と少なくとも同じ大きさでなければならない。後者の制約は、ツリー状順序付けの制約として表現される。目的は、すべての制約を満たしながら、すべてのj,p∈NPに対して公平な帯域幅の割り当てを判定することである。非減少順にソートされたすべてのj,p∈NPに対するすべてのパフォーマンス関数値のベクトルFpxpを考えてみる。公平な解は、これらの順序付けられたパフォーマンス関数の値の辞書式最大のベクトルを提供する解として定義される。Fxがすべてのj,p∈NPに対して、パフォーマンス関数のベクトルFpxpであるとし、ここで、所定のベクトルxに対し、これらのパフォーマンス関数が非減少順にソートされる。従って、ここで、公平な解は、すべての制約を満たす最大の辞書式ベクトルFxである。公平な解は、いかなる要求のパフォーマンス関数値も、すでに等しく劣った、またはより悪化した別の要求のパフォーマンス関数値を劣化させずに、実用可能に改善され得ないことを意味する。その結果の問題は辞書的マクシミン最適化問題と呼ばれている。我々が最小のパフォーマンス関数値だけでなく、二番目に小さいもの、および三番目に小さいものなどをも最大化することを必要されるように、辞書的マクシミン解はマクシミン解の概念を拡張する。公平な帯域幅の割り当てモデルEquitablebandwidthallocationModel問題EBAMは、辞書的マクシミン最適化問題として定式化される。いくつかの更なる表記が追加される。SUCjが、ノードjの直接の後続ノードの集合であるとし、例えば、図1ではSUC2={5,6}。もしプログラムpがリンクi,j上に伝送される場合、集合LP={[i,j,p]|p∈D、i,j∈A};すなわち、ダブルトン[i,j,p]∈LPとする。図1において、LP={[0,1,1],[0,1,2],[0,1,3],[0,2,1],[0,2,2],[0,2,3],[0,2,4],[1,3,1],[1,3,3],[1,4,2],[1,4,3],[2,5,1],[2,5,2],[2,6,1],[2,6,3]}。問題EBAMその結果、1.1および1.2が満たされ、そして、で、問題EBAMに対して実行可能な解が存在すると仮定する。目的関数2.11.1および1.2付きのは、公平な解を提供するベクトルを特定する。制約2.2の各リンク上に帯域幅容量の制約を適用する。制約2.3は、ルートノードから遠くに移動するときに割り当てられた帯域幅が、1つのリンクから次へと増大させることができないことを、プログラムごとに保証する順序付けの制約を適用する。制約2.4は、帯域幅の割り当てに対する下限を適用する。問題EBAMが、実行可能な解を有し、リソースの制約2.2が正だけの係数を有するので、それは容易に公平な解が存在することを示すことができる。決定変数の最適値は、上付き文字Lで示されている。分散アルゴリズムの核心となるのは、単一リンク帯域幅割り当て問題の繰り返し解である。この問題は、ツリーネットワークのリーフノードを除く、ノードの各々にて1回以上解決されるであろう。図1において、かかる問題は、ノード0、1、2にて解決されるであろう。問題SLBAM-i,jと呼ばれるリンクi,jのための単一リンク帯域幅割り当てモデルSingleLinkBandwidthAllocationModelの定式化は以下のとおりである。問題SLBAM-i,jそれで、問題SLBAM-i,jが、いかなる順序付けの制約をも含んでいないことに留意されたい。Tjがルートとしてノードjを有するサブツリーTN,Aとして、そこから始まり、それがノードjから到達できるノード、および対応するリンクを含むとする。例えば、図1においては、T2はノード2、5および6、ならびにリンク2,5および2,6を含む。明らかに、T0は全体のツリーである。特定のリンクi,jを考慮されたい。目的関数3.1は、そのプログラムの要求がサブツリーTのノードに存在する場所に関係なく、そのリンク上で伝送されるすべてのプログラムpのパフォーマンス関数を含むことに留意されたい。例えば、図1の問題SLBAM-0,2の目的関数は、プログラム1と2はノード2で要求されていないが、プログラム1、2、3および4を考慮する。最適な変数の値は、上付き文字のを付している。問題SLBAM-i,jは広く研究されており、この問題を解決するため、種々の効率的なアルゴリズムが公開されている。下記参照文献におけるアルゴリズムは、すべてのmに対しΣnamnxmn≦cmの形式ただし、すべてamn≧0およびすべてcm≧0が所定のパラメータであるmはリソースの指標であるの複数のリソース制約単一のリソース制約3.2に代わるのある多くの一般的な問題を解決している。非特許文献8および非特許文献9は、線形パフォーマンス関数のためのアルゴリズムを提供する。非特許文献10は、特定の非線形の連続で厳密に増加するパフォーマンス関数のアルゴリズムを提供しており、そこで、下限制約3.3のない問題SLBAM-i,jの緩和版の解が閉形式表現の計算によって達成され得るとしている。非特許文献11は、より一般的な、連続的な、非線形厳密に増加するパフォーマンス関数のアルゴリズムを提供する。これらのアルゴリズムは、すべての計算を繰り返すことなく、問題は若干改定され例えば、新しいプログラムが追加される、新たな最適解を計算するために使用され得る。この事柄は、非特許文献7で説明されている。問題SLBAM-i,jは、しばしば厳密に減少するパフォーマンス関数の低下に伴うミニマックス最適化問題として定式化されて、同一アルゴリズムが適用されることに留意されたい。図2を参照すると、分散方法において問題EBAMを解決する本発明の分散方法のフローチャート200が示されており、最小限の情報のみがツリーネットワークのノード間で交換されている間、他のすべてのノードから独立して、集中的な計算が各ノードで実行されることを意味する。この方法はEBAMのための分散方法と呼ばれている。方法のステップの各々は、以下に記載される。EBAMのための分散方法プログラムの集合を計算する201各ノードi∈Nはツリーのエンドノードを除く、ノードからの発信リンクの各々のための分散計算を担当している。そのために、ノードiは、各j∈SUCiに対して利用可能な集合Dを有する必要がある。LEAFはTN、A内のリーフノードの集合であるとされ図1においては、LEAF={3,4,5,6}、prejはノードjの先行ノード例えば、図1では、ノード2=pre5であるとされる。リーフノードj∈LEAFから始め、以下の漸化式が使用され、i=prejのためのノードjにて集合Dを計算する。そして、ノードiは、各ノードj∈SUCiから集合Dを受信する。いったんノード0がすべてのその後続ノードから集合を受信すると、計算は完了する。漸化式は、以下のとおりである。図1を考えてみる。式4.1から、DおよびDはノード2に送信され、DおよびDはノード1に送信される。ノード2は、方程式4.2を使用して、D=P2∪D∪D={1,2,3,4}を計算する。ノード1は、方程式4.2を使用して、D=P1∪D∪D={1,2,3}を計算する。ノード2およびノード1は、情報をノード0へ送信し、情報の計算と伝達とが完了する。帯域幅割り当てを計算する分散計算202。各ノードi∈N\LEAFにおいて、各j∈SUCiに対して問題SLBAM-i,j解決する。問題は、前に提供された参照文献の公知の方法を用いて解決される。図1を考えてみる。パフォーマンス関数はF1y=F4y=2yおよびF2y=F3y=yであり、ここで、yが汎用引数であると仮定する。下限はB1=30でかつB2=B3=B4=0であると仮定する。各ノードで実行される問題の解は以下のとおりである。ボトルネックリンクを決定する203ボトルネックリンクは、Vの最小値をもたらすリンクである。FkがサブツリーTk内におけるリンク間の最小値Vとし、かつ、bTkがTk内におけるリンク間のボトルネックリンクであるとする。ツリー全体のネットワークT0のボトルネックリンクBT0=i0,j0はリーフノードから計算を開始し、ツリーノードに沿って上方に移動し、以下の漸化式を用いて決定される。ノードk∈LEAFが発信リンクを有していないので、Fkの対応する値は無限大に等しくなるように設定される。Tk内のボトルネックリンクは式5.2で識別される。最小値がカッコ内の第1の項の中から例えばj1に対してであれば、ボトルネックリンクはbTk=bTj1である。最小値はブラケットの第2の項の中から例えばj2に対してであれば、ボトルネックリンクはbTk=k、j2である。図1を考えてみる。いったんノード0がボトルネックi0,j0=1,3を決定したら、それはこの情報をノードi0=1に送信する。ボトルネックリンクでの最適帯域幅割り当てを決定する204ボトルネックリンクがi0,j0であると仮定する。ノードi0は次のようにリンクi0,j0上の最適な割り当てを確定する上付き文字Lが最適な公平な割り当てを意味すること想起されたい。ここで、単一リンク最適値xpが問題SLBAM-i0,j0の解としてステップ202において判定された。リンク上に、確定された帯域幅を有するプログラムは、その後Dから削除される。従って、D=φでかつ、リンクi0,j0のすべての判定が完了する。ノードi0は、このリンクのための決定が完了しているノード0を通知する。問題EBAMにおいて、1.1-1.4によって定式化されているように、すべての帯域幅の割り当ての判定は、リンクi0,j0で確定されているが、この定式の変形が存在して、ボトルネックリンクの変数はそれらの最適値にすべて確定されているわけではない。例は後で提示する。1,3=i0,j0を有する図1の例では、ノード1がリンク1,3の割り当てを確定している。具体的には、ボトルネックリンク下方の最適帯域幅割り当てを判定する205ツリーTj0を考えてみるステップ204内のリンクi0,j0はボトルネックリンクとして確定されたことを想起されたい。リンクi0,j0上で確定されたすべてのプログラムは、そのプログラムを伝送するTj0内のその他のすべてのリンク上の同一値に確定される。従って、ノードi0から開始して、関連情報がツリーTj0内において、1つのノードから次のへ、すべてのノードへと送信される。確定された任意の変数は、対応する集合Dから削除される。D=φとした場合、対応するノードiはリンク上のすべての判定が完了していることをノード0に通知する。問題EBAMにおいて、2.1-2.4によって定式化されているように、すべての変数はTj0内のリンクの各々の上で、このステップで確定されている他の例については後述することに留意されたい。図1の例では、リンク1、3が発信リンクではないので、このステップは実行されない。このステップの例を表1および表2に後述する。ボトルネックリンク上方の最適帯域幅割り当てを判定する206いくつかの割り当ての判定は、ノード0およびi0を接続するリンク上で確定することができる。その経路に沿っていくつかのリンクi,jを考えてみると、もし、プログラムpのための割り当てがリンクi0、j0上で確定されかつ、pがTj0内のノードを除いてjTの任意のノードによって要求されていない場合、ノードiとノードi0を接続するすべてのリンク上の最適割り当てはリンクi0,j0上のそのプログラムへの割り当てと同一である。これらの判定は、リンクprei0,i0から始まり、そしてノード0へ向かって逆方向に進行する、一度に1つのリンクごとに対し、以下のステップを使用して行われるProcedureFIXABOVEと呼ぶ。もし、D=φであれば、対応するノードiはそのリンク上のすべての決定が完了していることをノード0に通知する。図1の例では、i0、j0=1、3を想起されたい。このように、ノード1はリンク1、3の割り当てを固定する。具体的には、xL1=30およびxL3=20。前述のリンクは、リンク0、1である。リンク1、4がプログラム2および3を伝送し、かつノード1がプログラム2のみを要求するので、プログラム1は、プログラム2又は3ではなくリンク0、1上に固定されることができる。従って、xL1=30。必要に応じて新しい反復の開始する207-210いったん、すべての割り当ての決定がいったん完了すると、ノード0は、すべてのリンクが割り当ての判定を完了したかどうかを認識する。いくつかのリンクがすべての割り当てを完了していない場合207、新たな反復が開始される208。すべての集合Dはすでに更新されていることに留意されたい。新しい反復は、更新されたD=φでリンクのために問題SLBAM-i,jを再解決することから始まり202、ここで、集合Dが変更されていないリンクが再解決される必要はない。すべての割り当てがすべてのリンク上でいったん完了したら、問題EBAMに対する解が得られ209,210、そして分散アルゴリズムが、すべてのリンク上の公平な帯域幅の割り当てで終了する。下の表は、図1の例についての反復の各々におけるボトルネックリンクとプログラムの割り当てを示している。第1の反復はすでに説明されている。第2の反復では、リンク0,2はボトルネックになっている。これは、リンク2,5および2,6と同様にリンク0,2上のすべての判定の割り当てを確定することを導いた。わずか70単位の容量がリンク2,5および2,6の各々で使用されている間に、リンク0,2の容量が十分に使用されることに留意されたい。第3の反復では、リンク0,1がボトルネックリンクである。割り当てxL1=30が既に第1の反復で固定されていることを想起されたい。反復3では、プログラム2および3の割り当てがリンク0,1上に確定される。また、プログラム2および3の割り当てはリンク1,4上で確定される。余分な容量がリンク1,4、1,5および1,6上で利用できる一方で、リンク0,1、0,2および1,3上の容量が十分に使用されていることに留意されたい。余分な容量は、満たされなければならない順序付けの制約から生じる。種々の拡張は、EBAMのための分散方法を使用して本発明によって容易に処理することができる。帯域幅の割り当ての上限の考察帯域幅の割り当ての決定変数の上限を課す付加的な制約を有する問題EBAMを考慮してみる。従って問題EBAMの定式には以下の制約を追加する。ここで、Upは上限パラメータである。付加された上限制約xp≦Upを有する問題SLBAM-i,jを考えてみる。上限はまず上限なしで問題を解くことによって処理される。VUBとも呼ばれる、上限を有するマクシミン目標値は、のように計算される。ここで、図2におけるステップ203を考慮すると、或る反復においてリンクi0,j0がボトルネックリンクとして選択されると仮定する。もし、VUB=Vの場合、リンクi0,j0に関連付けられる変数が上限値を超えず、図2のステップ204で指定されるようにリンクi0,j0におけるすべての変数が確定される。それ以外の場合は、VUB=minp∈DFpUp、および、パフォーマンス関数値がVUBに等しい変数だけは、ステップ204内でそれらの最適値で確定される従って、これらの変数はそれらの上限で確定される。その後、ステップ205および206は、ボトルネックリンクに固定されたプログラムに対してのみ実行される。更新された集合Dボトルネックリンクのためおよびボトルネックの下のリンクのためを含むが空ではないことがあり得ることに留意されたい。複数のツリー全体のネットワークの一部である指定されたツリーネットワーク上にて、サーバの各々が、複数のプログラムをブロードキャストする複数のサーバを有するネットワークを考える。同一プログラムを複数のサーバからブロードキャストすることが可能で、ここで、所定のノードでの特定のプログラムの要求は、指定されたサーバにより提供される。従って、ノードで要求されたプログラムの入力は、プログラムごとにその供給サーバを指定する。ネットワークリンクの各々は、異なるサーバからブロードキャストされたプログラムを伝送する可能性があることに留意されたい。このモデルは、非特許文献5また、特許文献1に記載されている。EBAMのための分散方法は、複数のツリーで構成されるネットワークへの非常に小さな変更を加えて適用することができる。具体的には、上限が存在しない場合でさえも、ボトルネックリンクの下にあるリンクのためにステップ205で決定された更新された集合Dは空でなくてもよい、なぜなら、これらのリンクが、ボトルネックリンクを含まないブロードキャストのツリーを有するサーバからプログラムを伝送することがあり得るからである。動的環境における最適な決定問題EBAMのための分散アルゴリズムは、静的な集合settingで説明された。実際には、問題は時間の経過とともに変化する。例えば、様々のノードで要求された一連のプログラムが変わる可能性があり、新しいプログラムがサーバに追加されつつ他のプログラムが削除され、様々なリンクで利用可能な容量が変わる等々がある。更される可能性等の変更が発生するたびに、分散アルゴリズムが再度解決されなければならない。図1の例を考えてみる。プログラム4の要求がノード3で集合P3に追加されたと仮定する。図2に記載されているように方法は、計算の一部は再実行する必要はないものの、再度実行されなければならない。集合P3が変わったので、ステップ201での集合D1,3およびDが変わりつつ他のすべての集合Dは変わらないままで残る。従って、ステップ202における分散計算は、リンク1,3および0,1のみのために再実行される。いくつかのノードでプログラムを追加する局所の変化がボトルネックリンクの順序付けに影響を与え、他のリンク上のプログラムに割り当ての最適な帯域幅を変えることがあるので留意されたい。以下の表は、新しい解を提供する。我々の例においては、ボトルネックリンクの順序付けが変更されていない。しかし、最適な割り当ては、ノード3での要求を満たすためのプログラム4を今伝送するリンク上だけでなく、プログラム2および3のためのリンク0,1上の減少された割り当てによるリンク1,4上において、変更される。本開示の種々の態様は、コンピュータ、プロセッサ、および/又はマシン上で実行されたとき、コンピュータや機械に方法の各ステップを実行させる、コンピュータやマシンに利用可能または読み取り可能な媒体において具現化される、プログラム、ソフトウェア、又はコンピュータ命令として具現化することができる。本発明のシステムおよび方法は、汎用コンピュータ又はコンピュータシステム上で実装され、かつ実行され得る。コンピュータシステムは、既知の又は知られるであろうシステムの任意のタイプであってもよく、そして、プロセッサ、メモリ素子、記憶装置、入力/出力装置、内部バス、および/又は、通信ハードウェアやソフトウェア連動して他のコンピュータシステムと通信するための通信インターフェース、等を一般的に含んでもよい。モジュールは、装置のコンポーネント、ソフトウェア、プログラム、又は、ソフトウェア、ハードウェア、ファームウェア、電子回路、等々として具現化することができるいくつかの機能性を実装したシステム、であってもよい。本出願で使用され得る用語コンピュータシステムおよびコンピュータネットワークは、固定および/又はポータブルコンピュータのハードウェア、ソフトウェア、周辺機器、ならびにストレージ装置のさまざまな組み合わせを含んでもよい。コンピュータシステムは、共同で実行するネットワーク又は別の方法でリンクされる個々の複数のコンポーネントを含んでもよく、または1つもしくは複数のスタンドアロンコンポーネントを含んでもよい。本願のコンピュータシステムのハードウェアとソフトウェアのコンポーネントは、デスクトップ、ラップトップ、サーバ、および/又は組込システム等の固定や携帯機器内に含んでもよく、かつ含まれてもよい。ネットワーク内の公平な帯域幅の割り当てのための分散方法を説明し、例示してきたが、ここに添付された請求項の範囲によってのみ制限される本発明の原理および広範な教示から逸脱することなく、変更および修正が可能であることは当業者には明らかであろう。"