(57)【特許請求の範囲】
【請求項１】
ノードおよび相互接続するリンクのコンテンツ配信ツリーネットワークにおいて帯域幅を公平に割り当てる方法であって、
情報がノード相互で交換されながら、独立して前記ノードの各々で計算を実行するステップであって、前記ノードでは、ツリーのルートが、前記ツリー全体に複数のプログラムをブロードキャストするサーバを有する、ステップと、
公平な帯域幅の割り当ての問題を、問題ＥＢＡＭによって定義するステップであって、前記ネットワークの各リンク上で伝送される複数のプログラム相互において帯域幅を公平に割り当てる方法が、ＥＢＡＭのための分散方法によって特定される、ステップと
を備え、
前記ＥＢＡＭのための分散方法は、
ａ．前記ネットワークの各リンク上で伝送されるプログラムの集合を計算するステップであって、集合の計算が前記ツリーネットワークのリーフノードで再帰的に始まり、ツリーノードに沿って上方に移動して行われる、ステップと、
ｂ．その他のノードで実行される計算から独立して、発信リンク上で伝送される複数のプログラム相互での一時的な公平な帯域幅の割り当てを、そのノードから各発信リンクごとの各ノードにおいて、計算するステップであって、リンク（ｉ，ｊ）における複数のプログラム相互での前記割り当てが、単一リンク帯域幅割当モデルの問題、問題ＳＬＢＡＭ−（ｉ，ｊ）を解くことによって計算され、
【数１】
0005563717.tif 000027
式１によって
【数２】
0005563717.tif 000028
式２となり、すべての
【数３】
0005563717.tif 000029
に対し、
【数４】
0005563717.tif 000030
である、ステップと、
ｃ．前記リーフノードから計算を開始し、前記ツリーノードに沿って上方に移動する再帰的な計算を通じて、前記ツリーネットワークにおけるボトルネックリンクを判定するステップと、
ｄ．前記ボトルネックリンク上で伝送されるプログラムへ、最終的に、帯域幅を公平に割り当てるステップと、
ｅ．ルートノードが前記ボトルネックリンクのヘッドノードであるサブツリーに含まれる、リンク上のプログラムへ、最終的に、帯域幅を公平に割り当てるステップと、
ｆ．前記ボトルネックリンクのテイルノードに、前記ツリーネットワークの前記ルートノードを結ぶ経路上に含まれるリンク上のプログラムへ、最終的に、帯域幅を公平に割り当てるステップと、
ｇ．いくつかのリンクに対する新たな一時的に公平な帯域幅の割り当てを計算することをステップｂで開始し、分散計算による新たな反復を継続するステップであって、すべてのリンク上でのすべてのプログラムに対して、最終的に、帯域幅を公平に割り当てると、前記方法が終了する、ステップと
を備えたことを特徴とする方法。
【請求項２】
複数のパフォーマンス関数を備える辞書的マクシミン目的関数によって、各プログラムとノードの組み合わせごとに１つ、問題ＥＢＡＭを解決するステップをさらに備え、前記パフォーマンス関数が連続かつ狭義の単調増加関数であり、任意の特定プログラムに対して、前記パフォーマンス関数がすべてのノードで同一であることを特徴とする請求項１に記載の方法。
【請求項３】
リンク上で伝送されるすべてのプログラムの割り当てられた帯域幅の合計が、前記リンクの利用可能帯域幅の容量を超えないように、各リンクの帯域幅容量の制約によって、問題ＥＢＡＭを解決するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項４】
リンク上で伝送される各プログラムに割り当てられた帯域幅が、特定の下限を下回らず、かつ、ツリーのルートノードから目的地ノードへの経路に沿って、各プログラムに割り当てられた帯域幅が、１つのリンクから次のリンクへと減少し、増加しないような制約を適用することによって、問題ＥＢＡＭを解決するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項５】
前記ＥＢＡＭのための分散方法を使用して、リンク上で伝送される各プログラムに割り当てられた帯域幅に課せられる追加の上限により、問題ＥＢＡＭを解決するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項６】
複数のツリーを有するネットワークのための問題ＥＢＡＭを解決するステップをさらに備え、各ツリーのルートで、サーバが複数のプログラムと、異なるツリーの共有リンクとをブロードキャストし、公平な解がＥＢＡＭのための分散方法によって得られることを特徴とする請求項１に記載の方法。
【請求項７】
動的環境においていくつかの入力パラメータが変化するときに、ＥＢＡＭのための分散方法を繰り返し適用して、新しい公平な解を計算するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項８】
ノードおよび相互接続するリンクのコンテンツ配信ツリーネットワークにおいて帯域幅を公平に割り当てる方法を、コンピュータに実行させるコンピュータ可読プログラムを有するコンピュータ可読記憶媒体であって、
前記方法は、
情報がノード相互で交換されながら、独立して前記ノードの各々で計算を実行するステップであって、前記ノードでは、ツリーのルートが、前記ツリー全体に複数のプログラムをブロードキャストするサーバを有する、ステップと、
公平な帯域幅の割り当ての問題を、問題ＥＢＡＭによって定義するステップであって、前記ネットワークの各リンク上で伝送される複数のプログラム相互において帯域幅を公平に割り当てる方法が、ＥＢＡＭのための分散方法によって特定される、ステップと
を備え、
前記ＥＢＡＭのための分散方法は、
ａ．前記ネットワークの各リンク上で伝送されるプログラムの集合を計算するステップであって、集合の計算が前記ツリーネットワークのリーフノードで再帰的に始まり、ツリーノードに沿って上方に移動して行われる、ステップと、
ｂ．その他のノードで実行される計算から独立して、発信リンク上で伝送される複数のプログラム相互での一時的な公平な帯域幅の割り当てを、そのノードから各発信リンクごとの各ノードにおいて、計算するステップであって、リンク（ｉ，ｊ）における複数のプログラム相互での前記割り当てが、単一リンク帯域幅割当モデルの問題、問題ＳＬＢＡＭ−（ｉ，ｊ）を解くことによって計算され、
【数５】
0005563717.tif 000031
式１によって
【数６】
0005563717.tif 000032
式２となり、すべての
【数７】
0005563717.tif 000033
に対し、
【数８】
0005563717.tif 000034
である、ステップと、
ｃ．前記リーフノードから計算を開始し、前記ツリーノードに沿って上方に移動する再帰的な計算を通じて、前記ツリーネットワークにおけるボトルネックリンクを判定するステップと、
ｄ．前記ボトルネックリンク上で伝送されるプログラムへ、最終的に、帯域幅を公平に割り当てるステップと、
ｅ．ルートノードが前記ボトルネックリンクのヘッドノードであるサブツリーに含まれる、リンク上のプログラムへ、最終的に、帯域幅を公平に割り当てるステップと、
ｆ．前記ボトルネックリンクの前記リーフノードに、前記ツリーネットワークの前記ルートノードを結ぶ経路上に含まれるリンク上のプログラムへ、最終的に、帯域幅を公平に割り当てるステップと、
ｇ．いくつかのリンクに対する新たな一時的に公平な帯域幅の割り当てを計算することをステップｂで開始し、分散計算による新たな反復を継続するステップであって、すべてのリンク上でのすべてのプログラムに対して、最終的に、帯域幅を公平に割り当てると、前記方法が終了する、ステップと
を備えたことを特徴とするコンピュータ可読記憶媒体。
【請求項９】
複数のパフォーマンス関数を備える辞書的マクシミン目的関数によって、各プログラムとノードの組み合わせごとに１つ、問題ＥＢＡＭを解決するステップをさらに備え、前記パフォーマンス関数が連続かつ狭義の単調増加関数であり、任意の特定プログラムに対して、前記パフォーマンス関数がすべてのノードで同一であることを特徴とする請求項８に記載のコンピュータ可読記憶媒体。
【請求項１０】
リンク上で伝送されるすべてのプログラムの割り当てられた帯域幅の合計が、前記リンクの利用可能帯域幅の容量を超えないように、各リンクの帯域幅容量の制約によって、問題ＥＢＡＭを解決するステップをさらに備えることを特徴とする請求項８に記載のコンピュータ可読記憶媒体。
【請求項１１】
リンク上で伝送される各プログラムに割り当てられた帯域幅が、特定の下限を下回らず、かつ、ツリーのルートノードから目的地ノードへの経路に沿って、各プログラムに割り当てられた帯域幅が、１つのリンクから次のリンクへと減少し、増加しないような制約を適用することによって、問題ＥＢＡＭを解決するステップをさらに備えることを特徴とする請求項８に記載のコンピュータ可読記憶媒体。
【請求項１２】
前記ＥＢＡＭのための分散方法を使用して、リンク上で伝送される各プログラムに割り当てられた帯域幅に課せれる追加の上限により、問題ＥＢＡＭを解決するステップをさらに備えることを特徴とする請求項８に記載のコンピュータ可読記憶媒体。
【請求項１３】
複数のツリーを有するネットワークのための問題ＥＢＡＭを解決するステップをさらに備え、各ツリーのルートで、サーバが複数のプログラムと、異なるツリーの共有リンクとをブロードキャストし、公平な解がＥＢＡＭのための分散方法によって得られることを特徴とする請求項８に記載のコンピュータ可読記憶媒体。
【請求項１４】
動的環境においていくつかの入力パラメータが変化するときに、ＥＢＡＭのための分散方法を繰り返し適用して、新しい公平な解を計算するステップをさらに備えることを特徴とする請求項８に記載のコンピュータ可読記憶媒体。
【請求項１５】
相互接続するリンクのコンテンツ配信ツリーにおいて帯域幅を公平に割り当てるシステムであって、
情報がノード相互で交換されながら、独立して前記ノードの各々で計算を実行する手段であって、前記ノードでは、ツリーのルートが、前記ツリー全体に複数のプログラムをブロードキャストするサーバを有する、手段と、
公平な帯域幅の割り当ての問題を、問題ＥＢＡＭによって定義する手段であって、前記ネットワークの各リンク上で伝送されるの複数のプログラム相互において帯域幅を公平に割り当てる方法が、ＥＢＡＭのための分散方法によって特定される、手段と
を備え、
前記ＥＢＡＭのための分散方法は、
ａ．前記ネットワークの各リンク上で伝送されるプログラムの集合を計算するステップであって、集合の計算が前記ツリーネットワークのリーフノードで再帰的に始まり、ツリーノードに沿って上方に移動して行われる、ステップと、
ｂ．その他のノードで実行される計算から独立して、発信リンク上で伝送される複数のプログラム相互での一時的な公平な帯域幅の割り当てを、そのノードから各発信リンクごとの各ノードにおいて、計算するステップであって、リンク（ｉ，ｊ）における複数のプログラム相互での前記割り当てが、単一リンク帯域幅割当モデルの問題、問題ＳＬＢＡＭ−（ｉ，ｊ）を解くことによって計算され、
【数９】
0005563717.tif 000035
式１によって
【数１０】
0005563717.tif 000036
式２となり、すべての
【数１１】
0005563717.tif 000037
に対し、
【数１２】
0005563717.tif 000038
である、ステップと、
ｃ．前記リーフノードから計算を開始し、前記ツリーノードに沿って上方に移動する再帰的な計算を通じて、前記ツリーネットワークにおけるボトルネックリンクを判定するステップと、
ｄ．前記ボトルネックリンク上で伝送されるプログラムへ、最終的に、帯域幅を公平に割り当てるステップと、
ｅ．ルートノードが前記ボトルネックリンクのヘッドノードであるサブツリーに含まれる、リンク上のプログラムへ、最終的に、帯域幅を公平に割り当てるステップと、
ｆ．前記ボトルネックリンクの前記リーフノードに、前記ツリーネットワークの前記ルートノードを結ぶ経路上に含まれるリンク上のプログラムへ、最終的に、帯域幅を公平に割り当てるステップと、
ｇ．いくつかのリンクに対する新たな一時的に公平な帯域幅の割り当てを計算することをステップｂで開始し、分散計算による新たな反復を継続するステップであって、すべてのリンク上でのすべてのプログラムに対して、最終的に、帯域幅を公平に割り当てると、前記方法が終了する、ステップと
を備えたことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツ配信ネットワークに関する。特に、本発明は、ネットワークの複数のノードにて独立して計算される分散決定方法を使用して、コンテンツ配信のために利用可能な帯域幅の割り当てに関する。
【背景技術】
【０００２】
多くの通信ネットワークサービスプロバイダ、ケーブルテレビ事業者、および通信機器プロバイダは、ビデオオンデマンド（ＶＯＤ）等のコンテンツ配信サービスを供給することに大きな関心を示している。主な応用分野は、オンデマンドホームエンターテインメント、遠隔学習やトレーニング、ビデオ会議、およびニュースオンデマンドを含む。これらのサービスは、時間の経過とともに大きく成長し、サービスプロバイダのための重要な収入源になることが期待されている。しかし、適切なサービスを提供するために、かなりの帯域幅のリソースが利用可能でなければならならす、これは大規模な設備投資を意味する。例えば、ニアＶＯＤ（near-VOD）の応用において、サーバは人気のある映画のコピーを５分ごとにブロードキャストすることができるが、顧客は平均で２．５分、待つ場合があることを意味する。そして、映画の長さが１００分であれば、ネットワークは同時に映画の２０個のコピーを伝送するであろうし、これはかなりの帯域幅のリソースを必要とするであろう。ネットワークの利用可能な帯域幅リソースは、映画の次のコピーのための顧客の待ち時間の観点から、ニアＶＯＤの応用において提供されるサービスに影響する。ほぼ瞬時にＶＯＤ配信を提供するその他の配信技術において、どのプログラムにも帯域幅の割り当てをすることは、ユーザーに提供されるビデオの品質を変更することにより制御することが可能である。顧客が期待する品質は応用方法に依存し得る。例えば、映画のブロードキャストは、ビデオ会議のマルチキャストよりも優れたビデオ品質を必要とする。
【０００３】
有向リンクを有し、ツリーのルートノードが複数のプログラムを格納し、かつブロードキャストして、ツリーの複数のノードでのプログラムの要求を提供するサーバを有する、ツリーネットワークを考える。各リンクの帯域幅容量が制限されている故に、様々なノードで要求されたすべてのプログラムを十分に提供するためには、慎重な帯域幅の割り当てが必要とされる。特に、ツリーネットワークのすべてのリンクに沿った様々なプログラム間の公平な帯域幅の割り当てを達成することが重要である。これは、特定のプログラムのリンクに割り当てられた帯域幅がルートノードからエンドノードへの経路内の１つのリンクから次へと低下し、増大することがないので、困難な目標である。
【０００４】
ツリーネットワークおいて帯域幅を割り当てるいくつかの方法が公開されている。非特許文献１は、スループットを表す線形性能関数のためのツリーのリンクに沿った公平な割り当てのための方法を提案する。非特許文献２は、離散的な帯域幅の割り当てにモデルを拡張している。拡張されたモデルはＮＰ完全問題であり、著者らは、公平な解を近似する、簡略化された目的関数のアルゴリズムを提供した。非特許文献３および非特許文献４はまた、離散的な割り当てのためのアルゴリズムを提供する。そのアルゴリズムは、公平な解の近似値を求める目的関数に対する発見的方法を提供する。上記のすべての参照文献は、公平なスループットを見つけることに制限されるアルゴリズムを提示している。これらのアルゴリズムは、決定変数としてのソース−目的地（また、“仮想セッション”と呼ばれる）に割り当てられた帯域幅を使用している。
【０００５】
非特許文献５（また、特許文献１）は、同一の公平な帯域幅の割り当て問題のためのアルゴリズムを提示したが、これらは異なって定式化される。決定変数は、リンク（目的地に関係なく）上のプログラムに対する帯域幅の割り当てである。各プログラムのため決定変数は、ルートノードから遠くへ移動するときに、プログラムごとに、割り当てられた帯域幅が１つのリンクから次へと増やすことができないことを保証する、ツリー状順序付けの制約を満たさなければならない。モデルはまた、受信ノードに依存し得る各プログラムのための一般的なパフォーマンス関数（連続的に厳密に増加するが、必ずしも直線的にではない）を仮定している。提供される帯域幅が増加するときに、非線形のパフォーマンス関数が、例えば、満足度の増加の減少率を表す場合があるので、非線形のパフォーマンス関数は重要である。
【０００６】
非特許文献６（また特許文献２）は、パフォーマンス関数がプログラムに依存し得るが、特定のプログラムのために、それらはすべてのノードで同一であると仮定している。Ｌｕｓｓは、線形のおよび特定の非線形のパフォーマンス関数のための多項式時間で最適解をもたらすアルゴリズムを提供する。アルゴリズムは、計算時間が解の要求精度に依存するが、より一般的なパフォーマンス関数のために使用され得る。
【０００７】
参照文献のいくつかにおいて根本的な問題は、複数のマルチキャストセッションの観点から説明され、その他の参照文献が複数のプログラムのブロードキャストとして根本的な問題を説明していることに留意されたい。それにもかかわらず、これらの問題は本質的に同一である。
【０００８】
本発明において、非特許文献６のアルゴリズムは、最小限の情報のみがノード相互で交換されている間に、集中的な計算が独立してノードの各々で行われる分散型環境に拡張される。分散方法（distributed method）は、それが中央のコンピューティング装置の必要性を排除しているので、魅力的となる。それはまた、新しいプログラムの導入や既存のプログラムの削除等の時系列的な変化に対して、非常に迅速な適応を容易にする。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許第７、６６４、０２０号（H. Luss, Bandwidth Allocation for Video-on-Demand Networks）
【特許文献２】米国特許公開公開第２００９／０２１３８７５号（H. Luss, Method for Equitable Bandwidth Allocation for Content Distribution Networks）
【非特許文献】
【００１０】
【非特許文献１】S. Sarkar and L. Tassiulas, Distributed Algorithms for Computation of Fair Rates in Multirate Multicast Trees, Proceedings of IEEE INFOCOM 2000, 52-62, Tel Aviv, March, 2000
【非特許文献２】S. Sarkar and L. Tassiulas, Fair Bandwidth Allocation for Multicasting in Networks with Discrete Feasible Set, IEEE Transactions on Computers 53, 785-797, 2004
【非特許文献３】C. Y. Lee, Y. P. Moon, and Y. J. Cho, A Lexicographically Fair Allocation of Discrete Bandwidth for Multirate Multicast Traffics, Computers and Operations Research 31, 2349-2363, 2004
【非特許文献４】C. Y. Lee and H. K. Cho, Discrete Bandwidth Allocation Considering Fairness and Transmission load in Multicast Networks, Computers and Operations Research 34, 884-899, 2007
【非特許文献５】H. Luss, An Equitable Bandwidth Allocation Model for Video-on-Demand Networks, Networks and Spatial Economics. 8, 23-41, 2008
【非特許文献６】H. Luss, Equitable Bandwidth Allocation in Content Distribution Networks, Naval Research Logistics, published on-line, DOI 10.1002/nav.20400, January 2010
【非特許文献７】H. Luss, On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach, Operations Research 47, 361-378, 1999
【非特許文献８】H. Luss and D. R. Smith, Resource Allocation Among Competing Activities: A Lexicographic Minimax Approach, Operations Research Letters 5, 227-231, 1986
【非特許文献９】C. S. Tang, A Max-MM Allocation Problem: Its Solutions and Applications, Operations Research 36, 359-367, 1988
【非特許文献１０】H. Luss, An Algorithm for Separable Non-Linear Minimax Problems, Operations Research Letters 6, 159-162, 1987
【非特許文献１１】H. Luss, A Nonlinear Minimax Allocation Problem with Multiple knapsack Constraints, Operations Research Letters 10, 183-187, 1991
【発明の概要】
【００１１】
本発明は、ツリーのルートがツリー全体に複数のプログラムをブロードキャストする、サーバを有するツリーネットワークの各リンクで、利用可能な帯域幅の最適な割り当てのための分散方法を提供する。その分散方法においては、最小限の情報のみがノード相互で交換されつつ、集中的な計算は独立してノードの各々で行われる。リンクは制限された容量である。故に、慎重な帯域幅の割り当ての決定は、関連リンクの各プログラムごとに行わなければならない。帯域幅の割り当て問題は、種々のノードで要求されたすべてのプログラムのために、公平なサービスのパフォーマンスを提供する辞書的マクシミン目的関数により、公平なリソース割り当て問題として定式化される。制約は、リンク容量制約と各プログラムに課せられたツリー状順序付けの制約がある。順序付けの制約は、プログラムごとに、ルートノードから遠くへ移動するときに、割り当てられた帯域幅が１つのリンクから次へと増大させることができないことを保証する。
【００１２】
非特許文献６（また、特許文献２）は、辞書的マクシミン解を判定するアルゴリズムを提供する。本発明は、非特許文献６のアルゴリズムを拡張して、最小限の情報のみがノード間で交換されつつ、独立して集中的な計算が各ノードで実行され、分散された環境においてアルゴリズムを実行することができるようにしている。この分散方法は、中央のコンピューティング装置の必要性を排除するので、魅力的である。異なるノードでの計算を並列に行うことができるので、それはまた、新しいプログラムの導入や既存のプログラムの削除等、時系列的な変化に対して非常に迅速な適応を容易にする。
【００１３】
分散方法の主なステップは次のとおりである。最初に、ノードからリンクの各々上で伝送されるプログラムの集合が、再帰的な計算を使用して導出される。次に、リンク間のツリー状順序付けの制約を無視して、各ノードにおいて、その発信リンクの各々上の提案される帯域幅の割り当てが、計算される。これらの分散計算（distributed computations）は、その発信リンクごとに、ノードの各々で独立して実行される。次に、ボトルネックリンクが情報の交換を通じて判定される。これは、ボトルネックリンク上で最適な帯域幅の割り当てが判定された後に続く。これらの確定された決定は、その他のリンク上での帯域幅の最適な割り当てを決定することの更なる確定につながる可能性があり、それでツリー状順序付けの制約が満足されるようになる。次に、この方法は、以前に提案された帯域幅の割り当ての決定が修正されるノードの部分集合において、分散計算の新しい反復を継続する。この方法は、いったんすべてのリンクの上のすべての帯域幅の割り当ての決定が確定されると、終了する。最適解は、有限回の反復での分散方法により得られる。
【００１４】
以下の説明は、添付の図面と併せて読まれるとき、本発明をより明確に理解されるであろう。
【図面の簡単な説明】
【００１５】
【図１】複数のプログラムをブロードキャストするツリーのルートにあるサーバを有するコンテンツ配信ツリーネットワークのための帯域幅の割り当て問題の一例を示している。
【図２】ツリーネットワークにおけるコンテンツ配信のための公平な帯域幅の割り当てを決定する本発明を具体化する分散方法のフローチャートである。
【発明を実施するための形態】
【００１６】
図、特に図１を参照すると、有向リンクを有する７つのノード（０、１、２、３、４、５、および６）を備えるツリーネットワークの例１００が示される。ルートノード（ノード０）は、複数のプログラムを保存し、かつブロードキャストするサーバを有する。本発明の例では、プログラム１、２、３、および４（１０１）は複数のノードでのプログラムの要求に対してサービスを提供する。リンクに沿った番号が、ブロードキャストで利用可能なリンクの帯域幅容量である。従って、リンク（０，２）は、１３０の単位（例えば、Ｍｂｐｓ）（１０２）の容量を有する。本例では、ノード１、２、３、４、５、および６の各々は、いくつかのプログラムの要求を有することができる（要求のないノードがある場合もある）。例えば、ノード２は、プログラム３および４（１０３）の要求を有する。各リンクの帯域幅容量が制限されている故に、様々なノードで要求されたすべてのプログラムを提供するために、慎重な帯域幅の割り当てが必要とされる。ノード間の方法によって実行され、かつ交換される情報は、双方向にすることができるが、リンクがブロードキャストの目的のために向けられていることに留意されたい。ノード相互で最小限の量のみの情報を交換しながら、帯域幅の割り当てを判定するために実行される集中的な計算は、ノードごとに独立して実行される。この目的を達成するために、好ましくは計算を実行するためのコンピューティング手段が各ノードに配置される。具体的には、これらの計算は、リンク（１０４）の各々のテールノードによってなされる。従って、例えば、ノード１は、リンク（１，３）および（１，４）のための計算をなすであろう。特定のプログラムのためにリンクへ割り当てられた帯域幅は、ルートノードからエンドノードへの経路内の１つのリンクから次へと、減少し得るが、増加しない場合があるので留意されたい。これらの制約は、ノードにて独立して実行される集中計算の間には無視されるツリー状順序付けの制約として表現される。それにもかかわらず、これらの順序付けの制約は、アルゴリズムが終了した時点で満たされなければならない。図１の例は、本発明の分散方法を説明する以下の記載において使用される。前述の記載は例示の目的であり、本発明の限定のためではないことが理解されるであろう。
【００１７】
ノードで要求されたプログラムの配信品質から得られる満足度は、ノードへの着信リンク上のプログラムに割り当てられた帯域幅により、連続して厳密に増加するパフォーマンス関数を通じて特定される。例えば、プログラム１のためのパフォーマンス関数、およびリンク（２、６）上のプログラム１に割り当てられる帯域幅は、プログラム１のためのノード６の満足値を判定する。目的は、公平な方法で帯域幅を割り当てることであり、すなわち、目的は、ベクトルの要素が非減少順にソートされる、パフォーマンス関数値の辞書式最大可能ベクトルを判定することである。直感的には、連続的な決定変数のために、公平な解は、減少前の値が増加前の前者の値を超えないいくつかのパフォーマンス関数の値を低下させることなく、パフォーマンス関数値のいずれもが適当に増加することがないものとすることである。非特許文献７は、公平なリソース割り当ての問題に関する解説的な論文を提示する。特定のプログラムに割り当てられる帯域が、ルートノードから離れる経路に沿って１つのリンクから次へ増加させることができないことを保証する順序付けの制約をも、容量の制約だけでなく、実行可能解が満たさなければならないことに留意されたい。その他の制約はまた、そのプログラムを伝送するいずれかのリンク上の特定のプログラムに割り当てられた帯域幅の上限および下限として課され得る。
【００１８】
公平な帯域幅の割り当て問題の数学的定式化が以下に提供される。ツリーネットワークＴ（Ｎ，Ａ）を考えてみると、Ｎはノードの集合であり、Ａは相互接続する有向リンクの集合である。ノードは指数ｉ，ｊ、およびｋで表され、リンクはエンドノード（ｉ，ｊ）のダブルトンで表され、ここで、ｉがリンクのテールノードで、ｊがヘッドノードである。リンク（ｉ，ｊ）は利用可能な帯域幅の容量限界ｃ（ｉ，ｊ）を有する。サーバはプログラム集合Ｐを有するルートノードに位置される。プログラムは、指標ｐで表される。各ノードｉ∈Ｎ＼０（すなわち、ノード０以外のＮ内のノード）は、プログラムの部分集合Ｐi、Ｐi∈Ｐの要求を有し、ここで、Ｐiは空であるとすることができる（ルートノードで要求されるプログラムは、それらが任意のリンク帯域幅を使用せずに直接提供されるので考慮されない）。表記法を説明するために図１を考慮されたい。ノードの集合はＮ＝｛０，１，．．．，６｝であり、リンクの集合はＡ＝｛（０，１），（０，２），（１，３），（１，４），（２，５），（２，６）｝であり、プログラムの集合はＰ＝｛１，２，３，４｝である。利便性のために、Ｎにおけるノードは番号が付けられ、それで任意のリンク（ｉ，ｊ），ｊ＞ｉにおいても、リンク容量がｃ（０，１）＝１２０，ｃ（０，２）＝１３０、ｃ（１，３）＝５０，ｃ（１，４）＝１００，ｃ（２，５）＝９０，ｃ（２，６）＝８０となる。
【００１９】
プログラムｐがノードｊにて要求された場合、集合ＮＰ＝｛（ｊ，ｐ）｜ｐ∈Ｐj，ｊ∈Ｎ｝、すなわち、ダブルトン（ｊ，ｐ）∈ＮＰとする。図１において、ＮＰ＝｛（１，２），（２，３），（２，４），（３，１），（３，３），（４，２），（４，３），（５，１），（５，２），（６，１），（６，３）｝である。
【００２０】
分散アルゴリズムにおいて、各ノードは、そのローカル環境、すなわち、着信リンクおよび発信リンク、発信リンクの各々の容量、およびノードで要求されたプログラムを認識する。例えば、図１では、ノード２は、着信リンク（０，２）、発信リンク（２，５）（容量９０）および（２，６）（容量８０）、ならびに、ノード２で要求されたプログラム（プログラム３および４）を認識する。Ｄ(i,j)はリンク（ｉ，ｊ）上に伝送されるプログラムの集合とする。例えば、Ｄ(0,1)＝｛１，２，３｝およびＤ(1,4)＝｛２，３｝である。分散アルゴリズムにおいては、後述するように集合Ｄ(i,j)がノードｊで計算されて、そこからノードｉへ提供される。ノードｉは、リンク（ｉ，ｊ）上の帯域幅の割り当てのための分散計算を実行する。プログラムは有向リンクに沿ってブロードキャストされることに留意されたい。しかし、分散アルゴリズムは、両方の方向に一定の情報の交換を必要とする。これは、ツリーネットワークは有向リンクに沿ってだけでなく、反対の方向に沿って、この情報を移動させる能力を有すると仮定される。
【００２１】
決定変数およびパフォーマンス関数
ｘ(i,j)p＝プログラムｐのためのリンク（ｉ，ｊ）上に割り当てられた帯域幅、ここで、ｘ(i,j)pは連続しており、そして、ｘ(i,j)p≧Ｂp、ここで、Ｂpがプログラムｐに必要な帯域幅の下限である。例えば、図１のリンク（０，２）は、帯域幅をプログラム１、２、３および４に割り当てており、ここで、プログラム１はノード５および６で要求されており、プログラム２はノード５で要求されており、プログラム３はノード２および６で要求されており、プログラム４はノード２で要求されている。
【００２２】
ｘ＝決定変数のベクトルｘ(i,j)p、（ｊ，ｐ）∈ＮＰ。
【００２３】
Ｆjp（ｘ(i,j)p）＝ノードｊで要求されるプログラムｐに関連付けられたパフォーマンス関数、ここで、ｘ(i,j)pがリンク（ｉ，ｊ）上の、したがって、ノードｊへのプログラムｐに割り当てられる帯域幅である。例えば、図１のノード５でのパフォーマンス関数は、Ｆ51（ｘ(2,5)1）およびＦ52（ｘ(2,5)2）である。パフォーマンス関数は、ノードｊにおけるプログラムｐのための帯域幅ｘ(i,j)pにより顧客の満足度を表す。Ｆjp（ｘ(i,j)p）が連続する狭義の単調増加関数であると仮定される。また、任意の特定のプログラムｐのために、Ｆjp（ｘ(i,j)p）がプログラムｐの要求を有するすべてのノードで同一であると仮定される。従って、パフォーマンス関数の表記はＦp（ｘ(i,j)p）に簡略化される。
【００２４】
線形パフォーマンス関数が満足度を測定する唯一の合理的な方法であることに留意されたい。例えば、凹パフォーマンス関数（例えば、対数関数等）は、提供される帯域幅が増加するときに、当該関数が満足度での増加率の減少を呈するので、しばしば、特定の応用例に応じて、より適切な場合がある。
【００２５】
帯域幅の割り当ての問題は、種々の制約を満たさなければならない。リンクの各々上に伝送されるすべてのプログラムに割り当てられた帯域幅の合計は、利用可能な帯域幅容量を超えることはできない。一方で、各プログラムに割り当てられる帯域幅は下限を満たす必要がある。また、リンク（ｉ，ｊ）上の任意のプログラムＰのために割り当てられる帯域幅は、プログラムＰを伝送するノードｊからのすべての発信リンク上のプログラムｐに割り当てられる帯域幅と少なくとも同じ大きさでなければならない。後者の制約は、ツリー状順序付けの制約として表現される。
【００２６】
目的は、すべての制約を満たしながら、すべての（ｊ，ｐ）∈ＮＰに対して公平な帯域幅の割り当てを判定することである。非減少順にソートされたすべての（ｊ，ｐ）∈ＮＰに対するすべてのパフォーマンス関数値のベクトルＦp（ｘ(i,j)p）を考えてみる。公平な解は、これらの順序付けられたパフォーマンス関数の値の辞書式最大のベクトルを提供する解として定義される。
【００２７】
Ｆ(NP)（ｘ）がすべての（ｊ，ｐ）∈ＮＰに対して、パフォーマンス関数のベクトルＦp（ｘ(i,j)p）であるとし、ここで、所定のベクトルｘに対し、これらのパフォーマンス関数が非減少順にソートされる。従って、
【００２８】
【数１】
0005563717.tif 000002
【００２９】
ここで、
【００３０】
【数２】
0005563717.tif 000003
【００３１】
公平な解は、すべての制約を満たす最大の辞書式ベクトルＦ(NP)（ｘ）である。公平な解は、いかなる要求のパフォーマンス関数値も、すでに等しく劣った、またはより悪化した別の要求のパフォーマンス関数値を劣化させずに、実用可能に改善され得ないことを意味する。その結果の問題は辞書的マクシミン最適化問題と呼ばれている。我々が最小のパフォーマンス関数値だけでなく、二番目に小さいもの、および三番目に小さいものなどをも最大化することを必要されるように、辞書的マクシミン解はマクシミン解の概念を拡張する。
【００３２】
公平な帯域幅の割り当てモデル（Equitable bandwidth allocation Model）（問題ＥＢＡＭ）は、辞書的マクシミン最適化問題として定式化される。いくつかの更なる表記が追加される。ＳＵＣ（ｊ）が、ノードｊの直接の後続ノードの集合であるとし、例えば、図１ではＳＵＣ（２）＝｛５，６｝。もしプログラムｐがリンク（ｉ，ｊ）上に伝送される場合、集合ＬＰ＝｛［（ｉ，ｊ），ｐ］｜ｐ∈Ｄ(i,j)、（ｉ，ｊ）∈Ａ｝；すなわち、ダブルトン［（ｉ，ｊ），ｐ］∈ＬＰとする。図１において、ＬＰ＝｛［（０，１），１］，［（０，１），２］，［（０，１），３］，［（０，２），１］，［（０，２），２］，［（０，２），３］，［（０，２），４］，［（１，３），１］，［（１，３），３］，［（１，４），２］，［（１，４），３］，［（２，５），１］，［（２，５），２］，［（２，６），１］，［（２，６，３）］｝。
【００３３】
問題ＥＢＡＭ
【００３４】
【数３】
0005563717.tif 000004
【００３５】
その結果、（１．１）および（１．２）が満たされ、そして、
【００３６】
【数４】
0005563717.tif 000005
【００３７】
【数５】
0005563717.tif 000006
【００３８】
【数６】
0005563717.tif 000007
【００３９】
【数７】
0005563717.tif 000008
【００４０】
で、問題ＥＢＡＭに対して実行可能な解が存在すると仮定する。目的関数（２．１）（（１．１）および（１．２）付きの）は、公平な解を提供するベクトルを特定する。制約（２．２）の各リンク上に帯域幅容量の制約を適用する。制約（２．３）は、ルートノードから遠くに移動するときに割り当てられた帯域幅が、１つのリンクから次へと増大させることができないことを、プログラムごとに保証する順序付けの制約を適用する。制約（２．４）は、帯域幅の割り当てに対する下限を適用する。問題ＥＢＡＭが、実行可能な解を有し、リソースの制約（２．２）が正だけの係数を有するので、それは容易に公平な解が存在することを示すことができる。決定変数の最適値は、上付き文字Ｌで示されている。
【００４１】
分散アルゴリズムの核心となるのは、単一リンク帯域幅割り当て問題の繰り返し解である。この問題は、ツリーネットワークのリーフノードを除く、ノードの各々にて１回以上解決されるであろう。図１において、かかる問題は、ノード０、１、２にて解決されるであろう。問題ＳＬＢＡＭ−（ｉ，ｊ）と呼ばれるリンク（ｉ，ｊ）のための単一リンク帯域幅割り当てモデル（Single-Link Bandwidth Allocation Model）の定式化は以下のとおりである。
【００４２】
問題ＳＬＢＡＭ−（ｉ，ｊ）
【００４３】
【数８】
0005563717.tif 000009
【００４４】
それで、
【００４５】
【数９】
0005563717.tif 000010
【００４６】
【数１０】
0005563717.tif 000011
【００４７】
問題ＳＬＢＡＭ−（ｉ，ｊ）が、いかなる順序付けの制約をも含んでいないことに留意されたい。Ｔjがルートとしてノードｊを有するサブツリーＴ（Ｎ，Ａ）として、そこから始まり、それがノードｊから到達できるノード、および対応するリンクを含むとする。例えば、図１においては、Ｔ2はノード２、５および６、ならびにリンク（２，５）および（２，６）を含む。明らかに、Ｔ0は全体のツリーである。特定のリンク（ｉ，ｊ）を考慮されたい。目的関数（３．１）は、そのプログラムの要求がサブツリーＴのノードに存在する場所に関係なく、そのリンク上で伝送されるすべてのプログラムｐのパフォーマンス関数を含むことに留意されたい。例えば、図１の問題ＳＬＢＡＭ−（０，２）の目的関数は、プログラム１と２はノード２で要求されていないが、プログラム１、２、３および４を考慮する。最適な変数の値は、上付き文字の＊を付している。
【００４８】
問題ＳＬＢＡＭ−（ｉ，ｊ）は広く研究されており、この問題を解決するため、種々の効率的なアルゴリズムが公開されている。下記参照文献におけるアルゴリズムは、すべてのｍに対しΣnａmnｘmn≦ｃmの形式「ただし、すべてａmn≧０およびすべてｃm≧０が所定のパラメータである（ｍはリソースの指標である）」の複数のリソース制約（単一のリソース制約（３．２）に代わる）のある多くの一般的な問題を解決している。非特許文献８および非特許文献９は、線形パフォーマンス関数のためのアルゴリズムを提供する。非特許文献１０は、特定の非線形の連続で厳密に増加するパフォーマンス関数のアルゴリズムを提供しており、そこで、下限制約（３．３）のない問題ＳＬＢＡＭ−（ｉ，ｊ）の緩和版の解が閉形式表現の計算によって達成され得るとしている。非特許文献１１は、より一般的な、連続的な、非線形厳密に増加するパフォーマンス関数のアルゴリズムを提供する。これらのアルゴリズムは、すべての計算を繰り返すことなく、問題は若干改定され（例えば、新しいプログラムが追加される）、新たな最適解を計算するために使用され得る。この事柄は、非特許文献７で説明されている。問題ＳＬＢＡＭ−（ｉ，ｊ）は、しばしば厳密に減少するパフォーマンス関数の低下に伴うミニマックス最適化問題として定式化されて、同一アルゴリズムが適用されることに留意されたい。
【００４９】
図２を参照すると、分散方法において問題ＥＢＡＭを解決する本発明の分散方法のフローチャート２００が示されており、最小限の情報のみがツリーネットワークのノード間で交換されている間、他のすべてのノードから独立して、集中的な計算が各ノードで実行されることを意味する。この方法はＥＢＡＭのための分散方法と呼ばれている。方法のステップの各々は、以下に記載される。
【００５０】
ＥＢＡＭのための分散方法
プログラムの集合を計算する（２０１）
各ノードｉ∈Ｎは（ツリーのエンドノードを除く）、ノードからの発信リンクの各々のための分散計算を担当している。そのために、ノードｉは、各ｊ∈ＳＵＣ（ｉ）に対して利用可能な集合Ｄ(i,j)を有する必要がある。ＬＥＡＦはＴ（Ｎ、Ａ）内のリーフノードの集合であるとされ（図１においては、ＬＥＡＦ＝｛３，４，５，６｝）、pre（ｊ）はノードｊの先行ノード（例えば、図１では、ノード２＝pre（５））であるとされる。
【００５１】
リーフノードｊ∈ＬＥＡＦから始め、以下の漸化式が使用され、ｉ＝pre（ｊ）のためのノードｊにて集合Ｄ(i,j)を計算する。そして、ノードｉは、各ノードｊ∈ＳＵＣ（ｉ）から集合Ｄ(i,j)を受信する。いったんノード０がすべてのその後続ノードから集合を受信すると、計算は完了する。漸化式は、以下のとおりである。
【００５２】
【数１１】
0005563717.tif 000012
【００５３】
【数１２】
0005563717.tif 000013
【００５４】
図１を考えてみる。式（４．１）から、
【００５５】
【数１３】
0005563717.tif 000014
【００５６】
Ｄ(2、6)およびＤ(2、5)はノード２に送信され、Ｄ(1、4)およびＤ(1、3)はノード１に送信される。
ノード２は、方程式（４．２）を使用して、Ｄ(0,2)＝Ｐ２∪（Ｄ(2,6)∪Ｄ(2,5)）＝｛１，２，３，４｝を計算する。
ノード１は、方程式（４．２）を使用して、Ｄ(0,1)＝Ｐ１∪（Ｄ(1,4)∪Ｄ(1,3)＝｛１，２，３｝を計算する。
ノード２およびノード１は、情報をノード０へ送信し、情報の計算と伝達とが完了する。
【００５７】
帯域幅割り当てを計算する（分散計算）（２０２）。
【００５８】
各ノードｉ∈Ｎ＼ＬＥＡＦにおいて、各ｊ∈ＳＵＣ（ｉ）に対して問題ＳＬＢＡＭ−（ｉ，ｊ）解決する。問題は、前に提供された参照文献の公知の方法を用いて解決される。
【００５９】
図１を考えてみる。パフォーマンス関数はＦ1（ｙ）＝Ｆ4（ｙ）＝２ｙおよびＦ2（ｙ）＝Ｆ3（ｙ）＝ｙであり、ここで、ｙが汎用引数であると仮定する。下限はＢ1＝３０でかつＢ2＝Ｂ3＝Ｂ4＝０であると仮定する。各ノードで実行される問題の解は以下のとおりである。
【００６０】
【数１４】
0005563717.tif 000015
【００６１】
ボトルネックリンクを判定する（２０３）
ボトルネックリンクは、Ｖ*（ｉ，j）の最小値をもたらすリンクである。ＦｋがサブツリーＴｋ内におけるリンク間の最小値Ｖ*（ｉ，ｊ）とし、かつ、ｂ（Ｔｋ）がＴｋ内におけるリンク間のボトルネックリンクであるとする。ツリー全体のネットワークＴ０のボトルネックリンクＢ（Ｔ０）＝（ｉ０，ｊ０）はリーフノードから計算を開始し、ツリーノードに沿って上方に移動し、以下の漸化式を用いて判定される。
【００６２】
【数１５】
0005563717.tif 000016
【００６３】
【数１６】
0005563717.tif 000017
【００６４】
ノードｋ∈ＬＥＡＦが発信リンクを有していないので、Ｆkの対応する値は無限大に等しくなるように設定される。Ｔk内のボトルネックリンクは式（５．２）で識別される。最小値がカッコ内の第１の項の中から例えばｊ1に対してであれば、ボトルネックリンクはｂ（Ｔk）＝ｂ（Ｔj1）である。最小値はブラケットの第２の項の中から例えばｊ2に対してであれば、ボトルネックリンクはｂ（Ｔk）＝（ｋ、ｊ2）である。
図１を考えてみる。
【００６５】
【数１７】
0005563717.tif 000018
【００６６】
いったんノード０がボトルネック（ｉ0，ｊ0）＝（１，３）を決定したら、それはこの情報をノードｉ0＝１に送信する。
【００６７】
ボトルネックリンクでの最適帯域幅割り当てを判定する（２０４）
ボトルネックリンクが（ｉ０，ｊ０）であると仮定する。ノードｉ０は次のようにリンク（ｉ０，ｊ０）上の最適な割り当てを確定する（上付き文字Ｌが最適な公平な割り当てを意味すること想起されたい）。
【００６８】
【数１８】
0005563717.tif 000019
【００６９】
ここで、単一リンク最適値ｘ*(i0,j0)pが問題ＳＬＢＡＭ−（ｉ0，ｊ0）の解としてステップ２０２において判定された。リンク上に、確定された帯域幅を有するプログラムは、その後Ｄ(i0,j0)から削除される。従って、Ｄ(i0,j0)＝φでかつ、リンク（ｉ0，ｊ0）のすべての判定が完了する。ノードｉ0は、このリンクのための決定が完了しているノード０を通知する。
【００７０】
問題ＥＢＡＭにおいて、（１．１）−（１．４）によって定式化されているように、すべての帯域幅の割り当ての判定は、リンク（ｉ0，ｊ0）で確定されているが、この定式の変形が存在して、ボトルネックリンクの変数はそれらの最適値にすべて確定されているわけではない。例は後で提示する。（１，３）＝（ｉ0，ｊ0）を有する図１の例では、ノード１がリンク（１，３）の割り当てを確定している。具体的には、
【００７１】
【数１９】
0005563717.tif 000020
【００７２】
ボトルネックリンク下方の最適帯域幅割り当てを判定する（２０５）
ツリーＴj0を考えてみる（ステップ２０４内のリンク（ｉ0，ｊ0）はボトルネックリンクとして確定されたことを想起されたい）。リンク（ｉ0，ｊ0）上で確定されたすべてのプログラムは、そのプログラムを伝送するＴj0内のその他のすべてのリンク上の同一値に確定される。従って、
【００７３】
【数２０】
0005563717.tif 000021
【００７４】
ノードｉ0から開始して、関連情報がツリーＴj0内において、１つのノードから次のへ、すべてのノードへと送信される。確定された任意の変数は、対応する集合Ｄ(i,j)から削除される。Ｄ(i,j)＝φとした場合、対応するノードｉはリンク上のすべての判定が完了していることをノード０に通知する。問題ＥＢＡＭにおいて、（２．１）−（２．４）によって定式化されているように、すべての変数はＴj0内のリンクの各々の上で、このステップで確定されている（他の例については後述する）ことに留意されたい。
【００７５】
図１の例では、リンク（１、３）が発信リンクではないので、このステップは実行されない。このステップの例を表１および表２に後述する。
【００７６】
ボトルネックリンク上方の最適帯域幅割り当てを判定する（２０６）
いくつかの割り当ての判定は、ノード０およびｉ0を接続するリンク上で確定することができる。その経路に沿っていくつかのリンク（ｉ，ｊ）を考えてみると、もし、プログラムｐのための割り当てがリンク（ｉ0、ｊ0）上で確定されかつ、ｐがＴj0内のノードを除いてｊＴの任意のノードによって要求されていない場合、ノードｉとノードｉ0を接続するすべてのリンク上の最適割り当てはリンク（ｉ0，ｊ0）上のそのプログラムへの割り当てと同一である。これらの判定は、リンク（pre（ｉ0），ｉ0）から始まり、そしてノード０へ向かって逆方向に進行する、一度に１つのリンクごとに対し、以下のステップを使用して行われる（Ｐｒｏｃｅｄｕｒｅ  ＦＩＸＡＢＯＶＥと呼ぶ）。
【００７７】
【数２１】
0005563717.tif 000022
【００７８】
もし、Ｄ(i,j)＝φであれば、対応するノードｉはそのリンク上のすべての決定が完了していることをノード０に通知する。図１の例では、（ｉ0、ｊ0）＝（１、３）を想起されたい。このように、ノード１はリンク（１、３）の割り当てを固定する。具体的には、ｘL(1、3)1＝３０およびｘL(1、3)3＝２０。前述のリンクは、リンク（０、１）である。リンク（１、４）がプログラム２および３を伝送し、かつノード１がプログラム２のみを要求するので、プログラム１は、プログラム２又は３ではなくリンク（０、１）上に固定されることができる。従って、ｘL(0、1)1＝３０。
【００７９】
必要に応じて新しい反復の開始する（２０７−２１０）
いったん、すべての割り当ての決定がいったん完了すると、ノード０は、すべてのリンクが割り当ての判定を完了したかどうかを認識する。
【００８０】
いくつかのリンクがすべての割り当てを完了していない場合（２０７）、新たな反復が開始される（２０８）。すべての集合Ｄ(i,j)はすでに更新されていることに留意されたい。新しい反復は、更新されたＤ(i,j)＝φでリンクのために問題ＳＬＢＡＭ−（ｉ，ｊ）を再解決することから始まり（２０２）、ここで、集合Ｄ(i,j)が変更されていないリンクが再解決される必要はない。すべての割り当てがすべてのリンク上でいったん完了したら、問題ＥＢＡＭに対する解が得られ（２０９，２１０）、そして分散アルゴリズムが、すべてのリンク上の公平な帯域幅の割り当てで終了する。下の表は、図１の例についての反復の各々におけるボトルネックリンクとプログラムの割り当てを示している。
【００８１】
【表１】
0005563717.tif 000023
【００８２】
第１の反復はすでに説明されている。第２の反復では、リンク（０，２）はボトルネックになっている。これは、リンク（２，５）および（２，６）と同様にリンク（０，２）上のすべての判定の割り当てを確定することを導いた。わずか７０単位の容量がリンク（２，５）および（２，６）の各々で使用されている間に、リンク（０，２）の容量が十分に使用されることに留意されたい。第３の反復では、リンク（０，１）がボトルネックリンクである。割り当てｘL(0,1)1＝３０が既に第１の反復で固定されていることを想起されたい。反復３では、プログラム２および３の割り当てがリンク（０，１）上に確定される。また、プログラム２および３の割り当てはリンク（１，４）上で確定される。余分な容量がリンク（１，４）、（１，５）および（１，６）上で利用できる一方で、リンク（０，１）、（０，２）および（１，３）上の容量が十分に使用されていることに留意されたい。余分な容量は、満たされなければならない順序付けの制約から生じる。
【００８３】
種々の拡張は、ＥＢＡＭのための分散方法を使用して本発明によって容易に処理することができる。
【００８４】
帯域幅の割り当ての上限の考察
帯域幅の割り当ての決定変数の上限を課す付加的な制約を有する問題ＥＢＡＭを考慮してみる。従って問題ＥＢＡＭの定式には以下の制約を追加する。
【００８５】
【数２２】
0005563717.tif 000024
【００８６】
ここで、Ｕpは上限パラメータである。付加された上限制約ｘ(i,j)p≦Ｕpを有する問題ＳＬＢＡＭ−（ｉ，ｊ）を考えてみる。上限はまず上限なしで問題を解くことによって処理される。ＶUB(i,j)とも呼ばれる、上限を有するマクシミン目標値は、
【００８７】
【数２３】
0005563717.tif 000025
【００８８】
のように計算される。ここで、図２におけるステップ２０３を考慮すると、或る反復においてリンク（ｉ0，ｊ0）がボトルネックリンクとして選択されると仮定する。もし、ＶUB(i0,j0)＝Ｖ*(i0,j0)の場合、リンク（ｉ0，ｊ0）に関連付けられる変数が上限値を超えず、図２のステップ２０４で指定されるようにリンク（ｉ0，ｊ0）におけるすべての変数が確定される。それ以外の場合は、ＶUB(i0,j0)＝ｍｉｎp∈D(i0,j0)Ｆp（Ｕp）、および、パフォーマンス関数値がＶUB(i0,j0)に等しい変数だけは、ステップ２０４内でそれらの最適値で確定される（従って、これらの変数はそれらの上限で確定される）。その後、ステップ２０５および２０６は、ボトルネックリンクに固定されたプログラムに対してのみ実行される。更新された集合Ｄ(i,j)（ボトルネックリンクのためおよびボトルネックの下のリンクのためを含む）が空ではないことがあり得ることに留意されたい。
【００８９】
複数のツリー
全体のネットワークの一部である指定されたツリーネットワーク上にて、サーバの各々が、複数のプログラムをブロードキャストする複数のサーバを有するネットワークを考える。同一プログラムを複数のサーバからブロードキャストすることが可能で、ここで、所定のノードでの特定のプログラムの要求は、指定されたサーバにより提供される。従って、ノードで要求されたプログラムの入力は、プログラムごとにその供給サーバを指定する。ネットワークリンクの各々は、異なるサーバからブロードキャストされたプログラムを伝送する可能性があることに留意されたい。このモデルは、非特許文献５（また、特許文献１）に記載されている。ＥＢＡＭのための分散方法は、複数のツリーで構成されるネットワークへの非常に小さな変更を加えて適用することができる。具体的には、上限が存在しない場合でさえも、ボトルネックリンクの下にあるリンクのためにステップ２０５で決定された更新された集合Ｄ(i,j)は空でなくてもよい、なぜなら、これらのリンクが、ボトルネックリンクを含まないブロードキャストのツリーを有するサーバからプログラムを伝送することがあり得るからである。
【００９０】
動的環境における最適な決定
問題ＥＢＡＭのための分散アルゴリズムは、静的な集合（setting）で説明された。実際には、問題は時間の経過とともに変化する。例えば、様々のノードで要求された一連のプログラムが変わる可能性があり、新しいプログラムがサーバに追加されつつ他のプログラムが削除され、様々なリンクで利用可能な容量が変わる等々がある。更される可能性等の変更が発生するたびに、分散アルゴリズムが再度解決されなければならない。
【００９１】
図１の例を考えてみる。プログラム４の要求がノード３で集合Ｐ３に追加されたと仮定する。図２に記載されているように方法は、計算の一部は再実行する必要はないものの、再度実行されなければならない。集合Ｐ３が変わったので、ステップ２０１での集合Ｄ（１，３）およびＤ(0、1)が変わりつつ他のすべての集合Ｄ(i,j)は変わらないままで残る。従って、ステップ２０２における分散計算は、リンク（１，３）および（０，１）のみのために再実行される。いくつかのノードでプログラムを追加する局所の変化がボトルネックリンクの順序付けに影響を与え、他のリンク上のプログラムに割り当ての最適な帯域幅を変えることがあるので留意されたい。以下の表は、新しい解を提供する。我々の例においては、ボトルネックリンクの順序付けが変更されていない。しかし、最適な割り当ては、ノード３での要求を満たすためのプログラム４を今伝送するリンク上だけでなく、プログラム２および３のためのリンク（０，１）上の減少された割り当てによるリンク（１，４）上において、変更される。
【００９２】
【表２】
0005563717.tif 000026
【００９３】
本開示の種々の態様は、コンピュータ、プロセッサ、および／又はマシン上で実行されたとき、コンピュータや機械に方法の各ステップを実行させる、コンピュータやマシンに利用可能または読み取り可能な媒体において具現化される、プログラム、ソフトウェア、又はコンピュータ命令として具現化することができる。
【００９４】
本発明のシステムおよび方法は、汎用コンピュータ又はコンピュータシステム上で実装され、かつ実行され得る。コンピュータシステムは、既知の又は知られるであろうシステムの任意のタイプであってもよく、そして、プロセッサ、メモリ素子、記憶装置、入力／出力装置、内部バス、および／又は、通信ハードウェアやソフトウェア連動して他のコンピュータシステムと通信するための通信インターフェース、等を一般的に含んでもよい。モジュールは、装置のコンポーネント、ソフトウェア、プログラム、又は、ソフトウェア、ハードウェア、ファームウェア、電子回路、等々として具現化することができるいくつかの“機能性”を実装したシステム、であってもよい。
【００９５】
本出願で使用され得る用語「コンピュータシステム」および「コンピュータネットワーク」は、固定および／又はポータブルコンピュータのハードウェア、ソフトウェア、周辺機器、ならびにストレージ装置のさまざまな組み合わせを含んでもよい。コンピュータシステムは、共同で実行するネットワーク又は別の方法でリンクされる個々の複数のコンポーネントを含んでもよく、または１つもしくは複数のスタンドアロンコンポーネントを含んでもよい。本願のコンピュータシステムのハードウェアとソフトウェアのコンポーネントは、デスクトップ、ラップトップ、サーバ、および／又は組込システム等の固定や携帯機器内に含んでもよく、かつ含まれてもよい。
【００９６】
ネットワーク内の公平な帯域幅の割り当てのための分散方法を説明し、例示してきたが、ここに添付された請求項の範囲によってのみ制限される本発明の原理および広範な教示から逸脱することなく、変更および修正が可能であることは当業者には明らかであろう。
【図１】
0005563717.tif 000039
【図２】
0005563717.tif 000040