(57)【要約】  本発明の１つの例示的実施形態は、分散された組のプロセス間で多種多様な資源を割り当てる方法であって、資源を分割するためのその組のプロセスから１つのプロセスを選択するステップと、選択されたプロセスで資源を分割するステップと、分割の結果をその組の他のプロセスと分けるステップとを含み、前記他のプロセスが分割された資源から分割部分を選択し、選択されたプロセスが、分割部分を選択した他のプロセスに続いて分割部分を選択することができる、方法を説明する。該方法はまた、すべての現在関係するプロセスが利用可能な資源の選択された分割部分によって満足させられるまで、上記ステップを繰り返す。さらに、複数のプロセスが同じ分割部分を争う場合、資源を割り当てられなかった次のプロセスが、現在満足させられていないプロセスによる選択のために残りの資源を再分割する。
2009515255.tif 000002
【特許請求の範囲】
【請求項１】
分散された組のプロセス間で多種多様な資源を割り当てる方法であって、
ａ）前記資源を分割するために前記組のプロセスから１つのプロセスを選択するステップと、
ｂ）前記選択されたプロセスで前記資源を分割するステップと、
ｃ）前記分割の結果を前記組の他のプロセスと分け、前記他のプロセスが前記分割された資源から１つの分割部分を選択するステップと、
ｄ）前記選択されたプロセスが１つの分割部分を選択した前記他のプロセスに続いて１つの分割部分を選択することができるステップと
を含む、方法。
【請求項２】
すべての現在関係するプロセスが利用可能な資源の選択された分割部分によって満足させられるまで、前記ａ）、ｂ）、ｃ）およびｄ）のステップが繰り返される、請求項１に記載の方法。
【請求項３】
複数のプロセスが同じ分割部分を争う場合、資源を割り当てられていない次のプロセスが、現在満足させられていないプロセスによる選択のために残りの資源を再分割する、請求項１に記載の方法。
【請求項４】
前記分割が評価関数によって実行される、請求項１に記載の方法。
【請求項５】
前記評価関数が、プロセスがそのプロセスが公平であると信じるものによって資源を分割することができるようにする、請求項４に記載の方法。
【請求項６】
通信ネットワーク内の分散された組のプロセスによる使用のための多種多様な資源の非仲介型分割のための方法であって、
前記資源を分割するための前記組のプロセスから１つのプロセスを選択するステップと、
前記選択されたプロセスで前記資源を分割するステップとを含み、
資源を分割することに責任を負うプロセスが、分割が他のすべての関与するプロセスに通知され、前記プロセスが分割された資源から選択する機会を持った後でのみ分割された資源から選択することができるようにされる、方法。
【請求項７】
１つのプロセスを選択する前記ステップ、前記資源を分割する前記ステップ、および分割された資源を選択する前記ステップが、すべての残りのプロセスが満足な分割された資源を選択するまで繰り返され、前に選択された資源が利用不可能であり、満足させられたプロセスが次に続く繰り返しにもう関与しない、請求項６に記載の方法。
【請求項８】
複数のプロセスが同じ分割部分を争う場合、資源を割り当てられなかった次のプロセスが現在満足させられていないプロセスによる選択のために残りの資源を再分割する、請求項６に記載の方法。
【請求項９】
通信ネットワーク内の分散された組のプロセスによる使用のための多種多様な資源の非仲介型分割のための機器であって、
前記プロセスによる使用のための前記資源を分割するように動作可能であり、
資源を分割することに責任を負う機器が、分割が他のすべての関与するプロセスに通知され、前記プロセスが分割された資源から選択する機会を持った後でのみ分割された資源から選択することができるようにされる、機器。
【請求項１０】
前記組の資源が、ＩＰアドレス、ＭＰＬＳラベルスイッチパス（ＬＳＰ）、いくつかの帯域幅のユニット、およびいくつかのストレージのユニットから成るグループから選択される、請求項６に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、例えば、通信ネットワークにおける資源割当ての分野、より詳細には、完全に分散された環境における資源の非仲介型分割に関する。
【背景技術】
【０００２】
マルチメディアサービス（ＩＰ電話またはＩＰ  ＴＶなど）をサポートする次世代ネットワークは、分散された環境で稼働するアプリケーションプロセスおよびシステムプロセスの間での多種多様なネットワーク資源（帯域幅、インターネットプロトコルアドレス、物理回路、またはＭＰＬＳラベルスイッチパスなど）の割当ておよび分割のための機構を必要とする。
【０００３】
（ＩＥＴＦ資源予約プロトコル［ＲＳＶＰ］および差別化サービス［ＤＩＦＦＳＥＶ］などの）様々なサービス品質（ＱｏＳ）プロトコル、および（ＩＴＵ−Ｔの次世代ネットワークの資源割当て制御機能［ＲＡＣＦ］などの）アーキテクチャに関して業界では多くの努力が払われてきて、この努力は、ポリシー駆動型制御のためのオペレーティングシステムおよび機構の分野で開発された資源割当て機構と組み合わせられて、資源予約のための豊富なサービス構築ブロックの組を作り出してきた。
【０００４】
それにもかかわらず、われわれの知る限りでは、これらすべての機構は、特定のセットの資源が所与のプロセスに割り当てられることができるかどうかについて判定するための何らかの種類の中央機構を仮定する。特に、プロセス間で１組の資源を分割する問題は、中央制御または仲介を必要とせずには解決されていない。そのような中央制御の欠点は以下の通りである。
１．単一の障害点の存在、
２．中央に大量の状態情報を維持する必要性、
３．プロセスのニーズの動的変化に対応する際の困難、
４．自然に限定されたスケーラビリティ。
【０００５】
したがって、プロセス間での資源の分割および割当てのための集中制御機能を必要としない代替方法が必要である。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、すべてのプロセスが分割の結果に満足させられることになり、そのような分割のために中央仲介が必要とされないやり方で、関係するプロセスがそれら自体の間で予め定義された組の多種多様な資源を分割することができるようにする方法を説明する。
【課題を解決するための手段】
【０００７】
本発明の例示的な一実施形態は、分散された組のプロセス間で多種多様な資源を割り当てる方法であって、資源を分割するためにその組のプロセスから１つのプロセスを選択するステップと、選択されたプロセスで資源を分割するステップと、分割の結果をその組の他のプロセスと分け、上記他のプロセスが分割された資源から１つの分割部分を選択するステップと、選択されたプロセスが１つの分割部分を選択したその他のプロセスに続いて１つの分割部分を選択することができるステップとを含む、方法を説明する。
【０００８】
該方法はまた、すべての現在関係するプロセスが利用可能な資源の１つの選択された分割部分によって満足させられるまで、上記ステップを繰り返す。さらに、複数のプロセスが同じ分割部分を争う場合、資源を割り当てられていない次のプロセスが、現在満足させられていないプロセスによる選択のために残りの資源を再分割する。
【０００９】
本発明の他の実施形態は、通信ネットワーク内の分散された組のプロセスによる使用のための多種多様な資源の非仲介型分割のための方法であって、上記資源を分割するためのその組のプロセスから１つのプロセスを選択するステップと、上記選択されたプロセスで資源を分割するステップとを含み、資源を分割することに責任を負うプロセスが、分割が他のすべての関与するプロセスに通知され、上記プロセスが分割された資源から選択する機会を持った後でのみ分割された資源から選択することができるようにされる、方法を説明する。
【００１０】
本発明の他の実施形態は、通信ネットワーク内の分散された組のプロセスによる使用のための多種多様な資源の非仲介型分割のための機器を含む。該機器は、上記プロセスによる使用のための資源を分割するように動作可能であり、資源を分割することに責任を負う機器は、分割が他のすべての関与するプロセスに通知され、上記プロセスが分割された資源から選択する機会を持った後でのみ分割された資源から選択することができるようにされる。
【発明を実施するための最良の形態】
【００１１】
本発明のより完全な理解が、同様の要素は同様の参照符号で表される図面と併せて本発明の以下の詳細な説明を考察することから得られることができる。
【００１２】
従来技術に対する改良が、集中制御の必要を排除し、資源の分割のための純粋に分散された方法およびプロトコルを導入することにより、本発明によって行われる。
【００１３】
図１を参照して、プロセス｛Ｐ１、Ｐ２、…、Ｐｎ｝を有するネットワーク１００は、所与の時点で、例えば、いくつかのＩＰアドレス、ＭＰＬＳラベルスイッチパス（ＬＳＰ）、いくつかの帯域幅のユニット、およびいくつかのストレージのユニットを含む資源１０２のプールを有すると仮定する。当業者によって理解されるであろうように、資源１０２のプールは、各プロセスのニーズに応じて異なるプロセスのための異なる値を有する多種多様な資源から成る。資源を争うプロセスは、各プロセスが資源のミックスを必要とする可能性があるが、非常に明確に、それぞれ異なるニーズを有する。例えば、帯域幅ではなくむしろＩＰアドレスを必要とする可能性があるプロセスもあり、ＩＰアドレスやストレージなどではなくＬＳＰを必要とするであろうプロセスもある。集中制御機能がそのような情報を追跡し、プロセス間で資源を分割することができるシステムを設計することは比較的容易であるが、この集中機能の資源評価情報の更新は、必ずしも最も効率のよいアプローチではない大量のトラフィックを必要とする。
【００１４】
この目的のために、本発明は、プロセスがそれら自体の間で予め定義された１組の多種多様な資源を以下のやり方で分割することができるようにする。
ａ）すべてのプロセスが分割の結果に満足させられることになり、
ｂ）そのような分割のための中央仲介が全く必要とされない（本発明を本当に分散されたプロトコルにする）。
【００１５】
本発明を説明するために、ｎプロセス、｛Ｐ１、Ｐ２、…、Ｐｎ｝、がそれら自体の間で１組Ｒの資源を公平に分割することを必要とする完全に分散されたシステムを仮定する。この説明のために、公平という用語は、すべてのプロセスが満足させられるように、かつ必ずしもすべての資源が同様に分割されるようにではなく、分割することを意味することができる。公平さは、評価関数
【数１】
2009515255.tif 000003
によって定義され、
式中、
【数２】
2009515255.tif 000004
は１組の非負実数であり、
ｅ（Ａ∪Ｂ）＝ｅ（Ａ）＋ｅ（Ｂ）、Ａ∩Ｂ＝φである。
【００１６】
各資源についてｒ∈Ｒ、ｅ’（ｒ）＝ｅ（｛ｒ｝）を定義することは自然である。簡単のために、常に、ｅ’の代わりにｅと書く。
【００１７】
以下で、われわれは、１組の対のプロセスおよびそれらのそれぞれの評価関数｛［Ｐ１，ｅ１］、［Ｐ２，ｅ２］，…，［Ｐｎ，ｅｎ］｝が与えられれば、
ｅｉ（Ｒｉ）≧ｅｉ（Ｒｊ）であり、ここでｉ＝１、…、ｎ
であるように、公平な分割Ｒ＝Ｒ１∪Ｒ２∪…∪Ｒｎを達成することが可能であることを示す。
【００１８】
言い換えれば、われわれは、各プロセスが、それが公平な扱いであると信じるものを得るようにプロセス間で資源を分割することが可能であることを示す。さらに、分割する方法は、中央コントローラなどのいかなる他のパーティまたは参加物をも必要としない、すなわち、事実上、プロセスがそれら自体の間で資源を分割する。
【００１９】
簡単のために、われわれは、ｅ（Ｒ１）＝ｅ（Ｒ２）＝…＝ｅ（Ｒｋ）であるように、各自然数ｋ＜ｎに関して、ｋより小さくない要素を有するすべてのサブセットＳ⊂Ｒをｋサブセット、｛Ｓ１、Ｓ２…Ｓｋ｝に分割することが可能であると仮定する。（この仮定は、必須ではない。この仮定は、分割プロセス中に評価関数の値を「微調整すること」によって処理されることができる。そうすることができなければ、上記の等式の系をｅ（Ｒ１）≒ｅ（Ｒ２）≒…≒ｅ（Ｒｋ）と書き直すことによって近似表記を利用することができる）。
【００２０】
次に図２に関して、流れ図２００によって本発明の方法を定義する（そして、本発明の正しさを帰納法によって証明する）。
ｎ＝２の場合、
本発明の方法における第１のステップ２０２として、１つのプロセスが、例えばランダムに選択される。（例えば、各プロセスは擬似乱数を計算し、それを他のプロセスに送る。両方の数が同じ場合は、このステップはそれらが異なるまで繰り返す。）
ステップ２０４で、選択されたプロセス、例えばＰ１、は資源Ｒを、ｅ１（Ｒ１）＝ｅ１（Ｒ２）であるように、Ｒ１およびＲ２に分割し、この分割をメッセージでＰ２に送る、２０６。
ステップ２０８で、分割を受け取るとすぐ、Ｐ２はそれが好む部分、ｅ２（Ｒ１）＞ｅ２（Ｒ２）であればＲ１を、または、そうでなければＲ２を選択し、その選択をメッセージでＰ１に知らせる。
構成では、達成された分割は公平である。
【００２１】
本発明の１つの重要な態様は、本発明が、各プロセスのニーズによって変化する異なる様々な値を有する多種多様な資源の分割を可能にすることである。本発明の他の重要な態様は、資源を分割することに責任を負うプロセスが、分割が他のすべての関与するプロセスに通知され、これらのプロセスが分割された資源から選択する機会を持つまで、分割された資源から選択することができるようにされないことである。説明されるように、複数のプロセスが同じ資源を争う場合、資源のさらに別の分割が次のプロセスによって遂行される。図３は、５つのプロセスＰ１〜Ｐ５を含む状況を示し、資源ＲはＲ１〜Ｒ５に分割されている。図示されているように、Ｐ２とＰ３の両方が資源Ｒ２を争い、Ｐ４とＰ５がＲ３を争っている。Ｐ５だけがＲ４を選択している。この場合、Ｒ４以外の資源は別の次のプロセスによって再分割され、残りの資源は新たに再分割された資源から選択する機会を持つ。
【００２２】
本発明の方法は、ｎ＝２の場合に関して説明されてきた。われわれは、そのようなアルゴリズムはｎ＜ｍ＋１に関して存在すると仮定し、図４を参照し、ｎ＝ｍ＋１の場合について考察する。
ステップ４０２で、１つのプロセスが、例えばランダムに選択される。（例えば、各プロセスは擬似乱数を計算し、それを残りのプロセスにマルチキャストする。例えば、複数のプロセスが最小数を計算した場合、この数を選択したプロセスは、最小数がただ１つのプロセスによって計算されるまで、このステップを繰り返す。次いで、そのプロセスが選択される。選択されるプロセスは最大数を有するプロセスでもよく、ランダムプロセス選択の他の知られている方法が利用されてもよいことが理解されるであろう。）一般性を失うことなく、このプロセスはＰ１であると仮定する。
ステップ４０４で、Ｐ１が、ｅ１（Ｒｉ）＝ｅ１（Ｒｊ）であり、ここでｉ、ｊ＝１、…、ｍ＋１であるように、資源Ｒ：
【数３】
2009515255.tif 000005
を分割し、この分割を残りのプロセス――Ｐ２、…、Ｐｍ＋１――にマルチキャストする（または、何らかのやり方で分ける）、４０６。分割を受け取るとすぐ、これらのプロセスはそれぞれ、それぞれが好む部分を選択し、それをアナウンスする、４０８。各プロセスＰｉは、
ｅｉ（Ｒ＊ｉ）＝ｍａｘ｛ｅｉ（Ｒｉ）｜ｔ＝１，…ｍ＋１｝、ここでｉ＝１、…、ｍ＋１
であるようにＲ＊ｉを選択し、その選択を残りのプロセスにマルチキャストする。
ステップ４１０で、すべてのプロセスが異なる分割部分を選択したかどうかに関する判定が行われる。すべてのプロセスが異なる分割部分を選択した場合、Ｐ１は、残りの分割を取り、４１２、タスクは終了する、４１４。そうでなければ、
ステップ４１６で、Ｒは以下のように考えられることができる。
Ｒ＝Ｒ’∪Ｒ’’∪Ｒ’’’、式中、
Ｒ’は、選択されなかった分割部分の（非エンプティの）組であり、
Ｒ’’は、それぞれが１つのプロセスだけによって選択された分割部分の（多分エンプティの）組であり、それぞれのプロセスの（多分エンプティである）組をΠ’’によって示し、
Ｒ’’’は、それぞれが複数のプロセスによって選択された分割部分の（非エンプティの）組であり、それぞれのプロセスの（非エンプティの）組をΠ’’’によって示す。
ステップ４１６で、Ｐ１は分割部分をＲ’から、（例えば、乱数を計算し、そのリマインダモジュール｜Ｒ’｜を取ることにより）、ランダムに選択する。この時点で、Ｐ１およびΠ’’内のすべてのプロセスのニーズが満たされる。
問題は、そのパワーがｍより小さいかまたはｍに等しいプロセスの組、Π’’’、および残りの資源の組に対して低減された。これで、前述の方法による再分割が生じることができる。
【００２３】
理解されるであろうように、本発明の分割法は、すべてのプロセスが異なる分割部分を選択するまで、繰り返し適用されることができる。
【００２４】
図５は、本発明による装置５００の例示的ブロック図を示す。一般に、該装置は、プロセッサ５０２を含めて、少なくとも２つの機能ブロックを含む。次のブロック５０４は、例えばソフトウェア内の命令を格納し、次いで、本発明の方法を実施するために格納されたデータを更新するための１つまたは複数の記憶装置である。プロキシ装置はまた、入力ポートおよび出力ポート５０６、５０８を含む。
【００２５】
説明を明確にするために、本発明の例示的実施形態は、個々の機能ブロックおよび／またはボックスを含むように記載されてきた。これらのブロックおよび／またはボックスが示す機能は、ソフトウェアを実行することができるハードウェアを含むがそれに限定されない共用または専用どちらのハードウェアの使用によってでも提供されることができる。用語「プロセッサ」の使用は、ソフトウェアを実行することができるハードウェアを排他的に指すと解釈されるべきではない。さらに、例示的実施形態は、デジタル信号プロセッサ（ＤＳＰ）ハードウェア、以下で議論される動作を実行するソフトウェアを格納するための読み出し専用メモリ（ＲＯＭ）、およびＤＳＰの結果を格納するためのランダムアクセスメモリ（ＲＡＭ）を含んでもよい。さらに、超大規模集積回路（ＶＬＳＩ）ハードウェア実施形態、ならびに汎用ＤＳＰ回路と組み合わせたカスタムＶＬＳＩ回路が提供されてもよい。
【００２６】
前述の説明は本発明の原理を例示するだけである。したがって、本明細書に明示的に記載または示されていないが、本発明の原理を実施し本発明の主旨および範囲に含まれる様々な構成を当業者は考案することができることが理解されるであろう。例えば、本発明は通信ネットワークのための資源の分割に関連して説明されているが、本発明はまた、そのような非集中分散が適用可能な場合は、食料品、建築材料、リリーフエイド、自然資源などの有形資源、およびコンピューティング資源などの無形資源を含めて、分散された環境内のほとんどのいかなるタイプの資源をも分割するために利用されることができることが理解されるであろう。さらに、前述のすべての実施例および条件付言語は、明示的に本発明の原理および当技術を推進するために本発明者によって提供された概念を読者が理解するのを助けるための説明目的のためだけであることを主に意図するものであり、そのような具体的に述べられた実施例および条件に限定されないと解釈されるべきである。さらに、本発明の原理、態様、および実施形態、ならびにそれらの特定の実施例を述べる本明細書内のすべての記述は、それらの構造的等価物と機能的等価物の両方を包含することを意図するものである。さらに、そのような等価物は、現在知られている等価物、ならびに将来開発される等価物、すなわち構造に関係なく同じ機能を実行する開発されるいかなる要素をも含むことを意図するものである。
【００２７】
本発明の特許請求の範囲に記載の請求項では、特定の機能を実行するための手段として示されているいかなる要素も、例えば、ａ）その機能を実行する回路要素の組合せ、または、ｂ）したがって、機能を実行すべきそのソフトウェアを実行するための適切な回路と組み合わされたファームウェア、マイクロコードなどを含めていかなる形のソフトウェア、をも含むその機能を実行するいかなる方法をも含むことを意図するものである。そのような請求項によって定義される本発明は、様々な前述の手段によって提供される機能が、請求項が要求するやり方で組み合わされ結び付けられることにある。したがって、出願者は、それらの機能を提供することができるいかなる手段をも本明細書に示された機能と等価であるとみなす。本発明の原理の他の多くの変更形態および利用形態が、当業者には明らかであり、本明細書内の教示によって企図されうる。したがって、本発明の範囲は、特許請求の範囲に記載の請求項によってのみ限定される。
【図面の簡単な説明】
【００２８】
【図１】多種多様な資源を有するネットワークを示す図である。
【図２】本発明の一実施形態のための流れ図である。
【図３】プロセス間で競合する例示的資源選択を示す図である。
【図４】本発明の方法のための他の例示的流れ図である。
【図５】本発明の方法を実施するための機器のブロック図である。
【図１】
2009515255.tif 000006
【図２】
2009515255.tif 000007
【図３】
2009515255.tif 000008
【図４】
2009515255.tif 000009
【図５】
2009515255.tif 000010
【国際調査報告】
2009515255.tif 000011
2009515255.tif 000012