共有リソース管理
リソース占有体(例えば、データ、人々)を利用可能なリソース(例えば、バンド幅、無線周波数スペクトル、劇場の座席)に自動割り当てするための、方法、装置、システム、及びコンピュータのためのプログラムが提供される。リソース占有体へのリソースの割り当ては、リソース占有体のサイズ、利用可能なリソース、及びリソースをリソース占有体に割り当てるための残り時間から計算される、割り当ての緊急性の指標に基づいている。1つ、2つ、又はそれ以上の時間閾値、特に、適時性閾値(これになるまで割り当て緊急性は増加し、これを過ぎると減少する)、及び腐敗性閾値(これを過ぎるとリソース占有体へのリソース割り当ては全く有用でなくなり、その後リソースが割り当てられなくなる)が、各リソース占有体に関連付けられてもよい。無線周波数スペクトルのリアルタイム割り当てのための、自動化されたオークションの方法、システム、及びプログラムも提供される。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、限られたリソースの割り当てを管理するための、装置、方法、信号、及びコンピュータのためのプログラム、及びそれを組み込むシステムに関する。
【0002】
このようなリソースには、コンピュータ及び通信システムリソース(例えば、プロセッサ時間、バンド幅、無線スペクトル等)が含まれるが、これらには限定されない。このようなリソースは、例えば、列車、航空機、又は公衆の娯楽のための座席割り当てとともに、劇場の運営、及び更には宿泊及びパッケージ休暇等の、人々によって利用され/占有される、医療/病院リソースを含むリソースをも含む。
【背景技術】
【0003】
制限されたリソースの管理は、多くのアプリケーション領域に広がる問題である。
【0004】
対象の1つの特定アプリケーションは、コンピュータ又は通信ネットワーク内でのリソース管理にある。このようなリソースは、バンド幅及びサーバ負荷を含み、このようなリソースの管理は、従来、衝突検出、輻輳検出、及び流入制御等の比較的単純なメカニズムを用いて行われてきた。ネットワークの詳細な知識及び詳細な構成情報を必要とする、複雑なサービス品質メカニズムも同様に存在する。ケーブルネットワーク及び大きなバンド幅を提供することができるネットワークにおいて、輻輳問題は、より多くのバンド幅を提供することにより単純に対応されることが時にはある。しかしながら、無線ベースのネットワークにおけるバンド幅又はバンド幅が限られている任意のネットワークのように、リソースが更に一層制約されるシステムにおいて、単純により多くのリソースを提供することは、必ずしも選択肢とは限らない。
【0005】
更に、これが技術的に実行可能な選択肢であるとさえしても、より多くのバンド幅を提供するのは、費用がかかり、また、ネットワーク管理者に、要求に遅れを取らないようにするためにネットワークを更新し続ける圧力をかける。要求が、利用可能なネットワークリソースを越える場合、ネットワーク崩壊が次に起こり、問題を解決するためのネットワーク技術者及び専門家の介入に帰着する。輻輳の期間中は、ユーザ要求も要求された情報のいずれもが優先されることはない。
【0006】
他の応用領域では、リソース占有体(resource occupier)へのリソース割り当ては、多様な方法で取り扱われる。人々が、リソース占有体(部屋、ベッド、席等の割り当て)であるシステムの場合、通常、リソース割り当ては、継続的な人間の介入により手作業で行われてもよい。
【0007】
支払意思額(WtP)を、通信ネットワーク内のリソース割り当てに用いることが、米国特許第6,4987,786号明細書及び米国特許第6,556,548号明細書から知られている。Alberto Pompermaierによる論文「A pricing mechanism for Intertemporal Bandwidth Sharing with Random Utilities and Resources」(London School of Economics,Department of Mathematics research report LSE−CDAM−2002−06,9 July,2002)は、通信ネットワーク内のバンド幅割り当てについての価格付けメカニズムに関連している。
【0008】
R.J.Gibbens及びF.P.Kellyによる「Resource Pricing and the Evolution of Congestions Control」(Automatica 35(1999),1969−1985)という名称の論文は、ユーザが輻輳を起こしたことに対して料金を請求される、ネットワーク内の輻輳価格付けの方法を説明している。
【発明の開示】
【発明が解決しようとする課題】
【0009】
知られている無線スペクトル割り当てシステムに関しては、これらは、微細時間及び長時間の両方に対して動的には、また、特に知的な方法ではリソースを管理しない。実際のユーザの相互作用は、このようなシステムにおける割り当てに対する知られているアプローチの基本的な部分には含まれておらず、サービスに対する実際の資金の請求能力も無く、リソースの割り当ての能力も無い。知られている周波数割り当てアルゴリズムは、複雑で低速である。この領域の既存の技術は、動的ではなく、代わりに静的構成に従って動作し、多くの場合、このリソースを管理するために、管理されるリソースから状態ベースの情報を収集する必要がある。更に、既存の技術は、情報レイヤ又は製品レイヤでは機能せず、代わりに、どのようにリソースが操作されるかについての下位構造のプロトコルレベルで働く。
【0010】
本発明は、特に従来技術に関連する1つ以上の問題を軽減する、改良された装置、方法、信号、及びコンピュータのためのプログラムを提供することを求める。
【課題を解決するための手段】
【0011】
本発明者らは、リソースユーザへのリソース割り当ての効用は、時間とともに変化し、或る時間を過ぎると、この効用はゼロに低下するということを認識した。
【0012】
本発明は、単純な経済学的モデル用いて、リソース割り当て及び効用に関する前から存在する膨大且つ詳細な情報を収集する必要なく、制御された方法でリソースを管理することに向けられている。リソース占有体/消費体は、優先付けされ、また、リソース割り当てのパターンは、リソース占有体/消費体に対するリソース割り当ての価値の指標に従って、制御される。コンピュータ又は通信ネットワークの場合、このアプローチは、アプリケーション層で適用してもよく、また、アプリケーションが、ネットワークがまだ動いており輻輳していないと盲目的に想定して現在動作し、結果的にアプリケーション層の崩壊とデータの喪失を起こす問題を軽減してもよい。
【0013】
特に、本発明の第1の態様によれば、リソースに複数のリソース占有体を割り当てする自動化された方法が提供され、本方法は、各リソース占有体に適時性閾値(timeliness threshord)を関連付けすることと、各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算することと、割り当てのそれぞれの緊急性指標に応答してリソースを割り当てすることとを含む。
【0014】
有利には、リソース割り当ては、所与の時間においてリソースについての最大の必要性を有するリソース占有体のために重み付けし、一方、利用可能なリソースを占有することが、有益でないとはいかないまでも、より有益性の低いリソース占有体(例えば、リソースの占有が、役に立つ時期が過ぎてしまったため、リソースを占有しても、基本的な目的を満足させられない等)へのリソース割り当てを回避してもよい。
【0015】
本方法は、また、各リソース占有体に腐敗性閾値(perishability threshord)を関連付けすることと、適時性閾値、腐敗性閾値、及びリソース占有体のサイズの指標に応答して、割り当ての緊急性の指標を計算することとを含む。
【0016】
好ましい一実施形態では、腐敗性閾値が過ぎてしまったリソース占有体へは、リソース割り当てはしない。
【0017】
好ましくは、割り当ての緊急性は、適時性閾値までは増加関数であり、増加凸関数が最も好ましい。
【0018】
好ましくは、割り当ての緊急性は、適時性閾値と腐敗性閾値との間は減少関数であり、減少凸関数が最も好ましい。
【0019】
好ましくは、割り当ての緊急性は、腐敗性閾値の後ではゼロである。
【0020】
好ましい一実施形態では、緊急性指標Aは、
【数2】
のように計算され、ここで、
Pは、優先度
ltは、時間tにおいて要求されるリソースの量
tjは、適時性閾値(これは、パラメータjの関数であってもよい)
pjは、腐敗性閾値
tは、現在時間
nは、正の数である。
【0021】
リソースは、送信バンド幅を含んでもよく、送信バンド幅は、無線スペクトルバンド幅を含んでもよい。
【0022】
リソースは、人々によって占有されるためのエンティティを含んでもよく、リソース占有体は、人々を含む。
【0023】
リソース占有体はまた、乗り物を含んでもよい。この中では、割り当ては、輻輳料金請求を用いて行うべきである。
【0024】
リソースは、支払意思額の値であってもよい。一旦割り当てされると、これらは、続いて任意の知られている方法により実際のリソースを割り当てするために用いてもよい。
【0025】
本発明は、同様に、動作中に本方法の全ての機能を実行するために構成されたリソース割り当てシステムを提供する。
【0026】
特に、リソースを複数のリソース占有体に割り当てするためのシステムが提供され、システムは、各リソース占有体に適時性閾値を関連付けする手段と、各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算する手段と、割り当てのそれぞれの緊急性指標に応答してリソースを割り当てする手段とを含む。
【0027】
本発明は、また、機械で読み取り可能な形式で、且つ、動作中に装置及び/又は方法の全ての機能を実行するように構成された、コンピュータソフトウェアを提供する。
【0028】
特に、本発明の更なる態様によれば、リソースを複数のリソース占有体に割り当てするためのコンピュータのためのプログラムが提供され、プログラムは、各リソース占有体に適時性閾値を関連付けることと、各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算することと、割り当てのそれぞれの緊急性指標に応答してリソースを割り当てすることとのために構成されたコード部分を含む。
【0029】
本発明は、また、無線スペクトルの自動化された割り当てのための、方法、システム、及びコンピュータのためプログラムを提供する。
【0030】
特に、本発明の更なる態様によれば、第1の見込みスペクトルユーザ群の間で無線スペクトルを割り当てするための自動化された方法が提供され、方法は、第1の群のメンバ間で第1の自動化オークションを実行するステップを含み、ここで、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催された第2の自動化オークションに応答して決定され、方法はさらに、第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てするステップを含む。
【0031】
好ましい一実施形態では、第1のオークション及び第2のオークションは、リアルタイムで実行される。
【0032】
いくつかの好ましい実施形態では、リソースは、本発明の上述した前の態様の方法に従って、第2の群のメンバに割り当てされる。
【0033】
本発明の更なる態様によれば、第1の見込みスペクトルユーザの群の間で無線スペクトルを割り当てするための自動化システムが提供され、システムは、第1の群のメンバ間で第1の自動化オークションを実行する手段を含み、ここで、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催される第2の自動化オークションに応答して決定され、システムはさらに、第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てする手段を含む。
【0034】
本発明の更なる態様によれば、第1の見込みスペクトルユーザの群の間で無線スペクトルを割り当てするためのコンピュータのためのプログラムが提供され、プログラムは、第1の群のメンバ間で第1の自動化オークションを実行するように構成さられたコード部分を含み、ここで、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催される第2の自動化オークションに応答して決定され、プログラムはさらに、第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てするように構成されたコード部分を含む。
【0035】
好ましい特徴は、当業者には明白なように、適切に組み合わせることができ、また、本発明の如何なる態様と組み合わせてもよい。上に示した例を超える、本発明の他の利点もまた、当業者には明白であろう。
【0036】
本発明が、どのように実行に移されるかを示すために、本発明の実施形態が、これから以下に、単に例としての目的で、添付の図面を参照して説明される。
【発明を実施するための最良の形態】
【0037】
本発明の第1の実施形態は、バンド幅が限定されている通信ネットワークに対するユーザ要求の管理に対して適用される。
【0038】
当業者には明白なように、上述の解決策の範囲は、通信システムへの応用よりもかなり広く、多くの他の同様な問題に適用され得る。
【0039】
図1を参照すると、コンピュータネットワーク10は、情報を転送するために用いることができるリソースのクラウドとして扱ってもよい。このリソースは、多数のユーザ14を扱うためのサーバ12の能力であり得る。ここでは、リソースは、バンド幅であると見なされる。ユーザは、情報を送信するためのバンド幅を買うための資金及び収入を割り当てられる。ユーザは、また、バンド幅を購入するかどうか、及び購入する場合には、どのレートで又いつにするかを判断するために用いる効用関数を有する。ネットワークエージェント16は、いつでも要求に応じてバンド幅に対する値段を計算する。バンド幅を購入するユーザについては、このユーザは、自分のバンド幅ニーズをエージェントに宣言141する必要があり、エージェントは、次に価格で応答142する。ユーザは、その後、この価格で買うか、この価格でどれだけ買うか、又は待って資金を節約するかどうかを決定することができる。これを、複数回のサイクルにわたって繰り返し、ユーザが効率的にオークションに参加するようにすることができる。実際のユーザに対する要求を省くための1つのアプローチは、価格交渉及びバンド幅の入札をユーザの代わりに行う、ローカルソフトウェアエージェント(通常このネットワーク内で)を有することである。これは、内部価格付けとして知られている。しかしながら、実際のユーザ(例えば、人間)が、ユーザインターフェースを介してより直接的にかかわることができ、また、かかわる金が実際の貨幣であり得る、アプリケーションが存在する。このような解決方法は、外部価格付けとして知られている。
【0040】
本方法を適用してもよい、多数のコンテキストが存在する。
・ 関係するアプリケーション/プロセスの即時の適時性ニーズの範囲内でバンド幅を購入するための短時間の間、ユーザがオークションに参加することを可能にする、スポットマーケットアプローチ。
・ ユーザがこの場合もオークションに参加するが、前もってバンド幅のニーズを宣言する、将来マーケットアプローチ。
・ 起こしている輻輳に対してユーザが料金請求される、Gibbens&Kelly輻輳価格付けアプローチ。
【0041】
これらのコンテキストは、もちろん、1つのコンテキストに結合することができ、スポットマーケット及び将来マーケットモデルを、Gibbens&Kellyモデルのような輻輳価格付けモデルと結合することが、本明細書で提案されている。スポットマーケット及び将来マーケットは、特定の量のリソース(この場合は、バンド幅)が利用可能だという最初の前提に基づく、フィードフォワードスケジューリング解決方法として作動する。輻輳価格付けアプローチは、最初の前提に対する誤差を修正するフィードバックメカニズムを加え、ネットワーククラウド内で何が実際に起こっているのかについての詳細を考慮に入れる方法として作動する。
【0042】
ネットワークをバンド幅クラウドとして扱うことにより、リソース(すなわちバンド幅)の利用を管理することができるようにする適時の状態情報を維持する必要性は、除去される。例えば、ネットワーク全体を通してのさまざまな地点の負荷が測定され、ユーザ送信を制御するために用いられる、適用してもよい知られている制御理論アプローチがある。このアプローチは、負荷測定が平均化されるという理由と、これらの測定を集めるのには時間がかかるという理由で、おそらく不安定さを導く。このような解決方法は、複雑でもある。本構成のように、より抽象的なレベルで(コンピュータ又は通信ネットワークの場合、アプリケーション層で)作動することにより、多くの複雑さが除去されるだけではなく、ネットワーク要求に従ってアプリケーションを見積って適応させるメカニズムが提供され、顧客の行動を含むアプリケーション層までの幅広いエンドツーエンドのトラフィック管理を提供する。
【0043】
トレーディングメカニズムの他の利点は、スケジューリングメカニズム及び急激的/爆発的飽和を避けるメカニズムを有することにより、限られた資源の利用効率の向上である。また、ユーザが有することができるリソース共有は、割り当てられた資金によって制御される。最終的に情報は、この事業又は運営に対するこれの価値に従ってエンドツーエンドに管理され得る。このような方法で、補正するには効率向上が充分ではない輻輳の期間には、低い情報価値を提供しているサービスは、停止し始めるであろう。高い情報価値を提供しているサービスは、存続するだろう。その結果、コアサービスは、周辺サービスよりも優先され、保証されることになる。また、サービスの管理は、これらのサービスが提供する情報に従って、細部にわたって影響を受ける。従って、この解決方法によって提供される主な機能は、
・ ユーザ要求管理、
・ 効率向上、
・ 情報管理、
・ アプリケーション層における料金及び入会料金コントロール、
・ エンドツーエンドトラフィック管理、
・ 対応している通信の状態又は構造についての詳細を知る必要がないこと、
・ システム内の全てのユーザが、トレーディングエージェントに登録が必要なことである。
【0044】
他のリソースが制約されたシステムにおいて、これらシステムは、均等物、すなわち、ユーザ要求管理は、顧客要求管理に相当してもよいことと、情報管理は、顧客へのサービス又は製品の管理に相当してもよいこととを有する。アプリケーション層における料金及び入会料金のコントロールは、システムの管理が、高い包括的なレベルで実行されるということを事実上意味する。エンドツーエンドトラフィック管理は、エンドツーエンドのサービス提供と見てもよい。最後に、提案されるトレーディング解決方法が機能するためには、システムの内部メカニズムのいかなる詳細な知識も必要はない。
【0045】
ユーザは、情報を転送する必要を有すると見なされており、転送している情報は、このユーザにとって価値を有すると見なされる。ユーザにとって価値の有る情報を転送するために必要なバンド幅に対する支払いをするためのコストの関数は、このバンド幅の使用の処置におけるユーザの効用を形成する。情報の価値とバランスが取れるコストが法外に高く、そのためユーザの効用が低い場合は、ユーザは、この情報をより安い料金で転送するか、又は全く転送しないことを決めることができる。一部の情報は、或る閾値未満の送信速度では価値を有さないであろうし、そのため、このユーザにとって、バンド幅をこのような閾値を下回るまで減らす効用は無いかもしれない。また、情報の価値は、転送速度の低下に伴って低下するかもしれず、従って、情報の価値とバランスが取れて、この情報を所与の速度で送信することに対するユーザにとっての効用を最大化する、バンド幅の最適価格というものがあるかもしれない。最後に、情報の価値は、おそらく多くの場合、時間の増加とともに減少し、従って、これは同様に効用関数で大きな特徴となり、また最適時間、速度、及び価格選択に影響を与える。
【0046】
不必要な要求をユーザに課すのを避けるために、このモデルは、ユーザインターフェースが、ユーザに代わって、情報を伝えるためにいつバンド幅を購入するかの決断のために作用するという考えを含む。このようにして、限定されたリソースを使うときのユーザの動作は、このユーザインターフェース及びトレーディングメカニズムを実装するソフトウェアによって制御され得る。このリソーストレーディングモデルの構成ブロックは、従って、
・ 資金 − 購入される利用可能な総リソースの表現。資金の総額は、対応する利用可能な総リソースを超えない。
・ バンド幅 − 通信ネットワークから提供されるリソース。これがどのようになされるかの詳細は、モデルには関係しない。
・ 情報価値 − 情報の中身、情報の量、配信の適時性、運用事業に対する重要性等に関する価値。
・ 効用 − ユーザが得る、資金に見合う価値を示す、コストと情報価値のバランス。
・ ユーザインターフェース − ユーザに代わって、いつ情報を伝えるためのバンド幅を購入するかについての決定を行うソフトウェア。
・ ネットワークトレーディングエージェント(NTA) − ユーザ要求及びバンド幅供給を考慮に入れて、バンド幅の使用に対する価格を計算する機能を持つサーバ。ネットワークに参加する全てのユーザは、このサーバに登録し、バンド幅利用するために支払う(サーバに)。
【0047】
上記のモデルには、かなり前の時間にリソース要求が宣言される第1のバージョンと、リソース要求が必要な時に宣言される第2のバージョンとの、2つのバージョンがある。
【0048】
第1のバージョンは、テレビ会議を予約するように、ユーザが前もって必要性を宣言することを可能にする。ここでこのモデルの構成要素は、オークションアルゴリズムを用いて適用され、ユーザデマンドがスケジュールされる。このアプローチは、将来マーケットモデルであり、ユーザとのより多くの相互作用が要求される。
【0049】
第2のバージョンは、スポットマーケットモデルであり、ここでは、例えば、eメールが5分間遅れたとしても、ユーザにおそらく心配されないように、又はウェブページのロードが5秒までならおそらく許容されるように、オークションアルゴリズムが、非常に短い時間尺度で適用される。スポットマーケットモデルでは、オークションプロセス中に、エージェントがユーザに代わって作用することから、実際のユーザは、トレーディングメカニズムが動作中であることを気が付かない。最終的に上記のアプローチは、輻輳価格付けアプローチ(例えば、Gibbens&Kellyの輻輳価格付けアプローチ)と組み合わせてもよく、これによりユーザは、輻輳を起こしたことに対してネットワークにより請求される。このようにしてネットワークは、オークションアルゴリズムにより生成された事前スケジューリング解決方法を微調整するために、フィードバック輻輳制御を行使することができる。
【0050】
図1に示すように、リソーストレーディングモデルに対する支援アーキテクチャについての2つの態様がある。バンド幅を取引するために、値付け及びバンド幅販売の役割を持つエージェントとして動作するサーバが提供される。情報の価値は、各ユーザのインターフェースによって知られている。輻輳に対して料金請求ができるように、ネットワークは、輻輳が発生する如何なる場所でも、輻輳通知を生成する必要がある。これは、ネットワーク内で、例えば、ルータインターフェースにおいて実行され得る。この支援アーキテクチャは、従って、バンド幅クラウドを支援して、ネットワークの状態に関するほんのわずかの詳細情報を最小限しか要求しない。
【0051】
送信データは、弾力性(elastic)のものと、非弾力性(inelastic)のものとの、2つのタイプの1つであると考えることができる。例えばeメール又はファイル転送のような弾力的なトラフィックは、動的な制御により、任意の速度で送信することができ、この速度は、利用可能なバンド幅に従って増減されることができる。音声やビデオ等の非弾力的なトラフィックは、固定バンド幅を必要とし、従って如何なる速度調整も、量子化ステップで行わなければならない。必要なバンド幅の量は、コールの要求品質によって決まる。
【0052】
トレーディングについての以下の議論は、より高い柔軟性を可能とする弾力的なトラフィックに主として集中する。しかしながら、このアプローチは、非弾力的なトラフィックに対しても作用する。
【0053】
人間のようなタイプの行動をモデル化するのは、決して容易な仕事ではないが、経済学の文献の中では、選択と個人の満足の概念が、効用関数を用いてしばしばモデル化されている。これらの関数は、1組の選択肢に対する個人の嗜好を表わしている。これは、ある面では、満足の尺度である。しかしながら、一般的に、これらの関数が、正確に知られる可能性は非常に低そうだということに注目すべきである。これらは、単に、本発明者らの考えを明確にし、どのようにユーザが行動するかについての単純な概念を構成する助けになるだけである。このようなモデルは、現実を記述しようとしているのではなく、より複雑な真の状況と同じ論理的な構造でもって、単純化された状況を組み立てようとしているのである。
【0054】
さて図2aを参照すると、トレーディング解決方法で用いることができる、効用関数の典型的な例が示されている。このグラフは、リソース(この場合はバンド幅)の特定の量を割り当てされた結果として、ユーザが受け取る、効用値U(x)を示している。描かれた効用関数は、弾力的なトラフィックに対する効用関数の典型であり、非弾力的なトラフィックに対応する予定であれば、対応する効用関数は、同じような形ではあろうが、滑らかなカーブというよりはむしろ、量子化されたステップを有する。一般的に、ユーザがより多くのバンド幅を割り当てされればされるほど、ユーザは、次にこのリソースをより速くデータを送信するために所有し、その後わずかな遅延を体験することになるので、このユーザはより満足する。効用曲線20は、典型的には、ユーザが追加の1単位のリソースを受け取ることから得られる追加の効用21は、正ではあるが、以前に特別なリソースの任意の単位を受け取ったことによって得られた限界効用22未満というようなものである。例示されている事例では、ユーザは、最初の数ユニットのバンド幅に対して効用の最大の増加を受け、既に多くのバンド幅ユニットを割り当てられたユーザは、更なるバンド幅ユニットを割り当てられたことによる受ける追加の効用はほんの少量である。多くの効用関数は、例えば、ln(1+x)のように、対数形式であり、その結果、個人がリソースユニットを有さないとき、都合よく効用値ゼロを与える、凹形状の関数になる。
【0055】
以下のトレーディングモデルで用いられる、効用関数の一般的な形式は、
【数3】
であり、ここでAは、ユーザにとってのリソース占有(バンド幅利用)の重要性(すなわち価値)を表すパラメータであり、値Aが高ければ高いほど、重要性が高い。第2項は、資金についての効用を導入し、Mは、ユーザにより保有されている総資金であり、cは、バンド幅当たりのコストである。従って、(M−cx)は、xユニットのバンド幅も保有するユーザの保有資金の量を与える。資金についての効用は、他の任意の製品に対する効用と同じ形式を有する。ほとんど資金を持っていない個人は、既に多くの資金を有する個人が、資金の追加の1ユニットから受けるものよりも、より多くの効用を獲得する。
【0056】
パラメータAは、個人のバンド幅占有の重要性を表し、転送する重要な情報を有するユーザは、より多くのバンド幅を購入することができるであろう。バンド幅占有の価値は、ユーザにより手動で決定することもあり得る。しかしながら、好ましい実施形態では、バンド幅占有の重要性は、情報そのものではなく、残りの送信の長さ、優先度、及び以下に説明するような適時性問題を表すパラメータに基づいている。
【0057】
優先度 − ユーザにとってのリソース占有体(この場合は、情報)の重要度についての目安を与える。これは、例えば、1及び3(ここで、1は日常的情報、及び3は緊急情報)等の、単純な指標として表され得る。一方、多くの優先度スキームは、分布以外の線形間隔ユニット(例えば、対数等を用いてもよい)に基づいている。所与のアプリケーションに対する適切なスケールは、実験的に決定され得る。
【0058】
適時性閾値 − これは、この時間までに、リソース(バンド幅)をリソース占有体(情報)に割り当てすべき、時間についての指標である。情報の適時性は、単純な優先度と混同されるべきではなく、低い優先度の情報が、短い適時性期間を有し、一方高い優先度の情報は、短い時間間隔の中では必要とされない可能性もある。
【0059】
腐敗性閾値 − これは、この後ではリソース占有体(情報)へのリソース(バンド幅)割り当てが、要求しているユーザに対し価値を有さなくなる、時間についての指標である。
【0060】
リソース占有体のサイズ − これは、リソースを未だ割り当てられていないリソース占有体のサイズ(例えば、ビットの観点での情報の長さ)についての指標である。このリソース占有体(情報)のサイズ(ビット)は、適時性閾値に達する前に、このリソース占有体全体に供給するのに割り当てられる充分なリソース(バンド幅)を、要求ユーザが要求することから、重要である。結果的に、適時性閾値に近づいたとき、リソース(バンド幅)が割り当てられるべき、残っているリソース占有体(ビット)のサイズが、まだ比較的大きい場合は、より多くのリソース(バンド幅)が、このリソース占有体(情報)に割り当てられることが重要である。これは、全体としては充分なリソースが、このリソース占有体に割り当てられて、要求されたタスク(通信媒体を介しての情報の転送)が達成されることを確実にする可能性を増進する。
【0061】
パラメータAの形式 − リソース割り当ての重要性は、多少複雑かもしれない。主要なパラメータは、優先度及び適時性閾値であり、この関数の特徴は、現在の時間が適時性閾値未満かどうか、適時性閾値と腐敗性閾値との中間かどうか、又は腐敗性閾値より大きいかどうかに応じて変化する。
【0062】
一般に、及び図2bをここで参照すると、リソース割り当ての重要性は、適時性閾値tjに近づくにつれ増加25し、適時性閾値と腐敗性閾値pjとの間で減少26し、腐敗性閾値の後で理想的にはゼロ27に落ちる。この曲線は、好ましくは適時性閾値までは凸型であり、また、好ましくは適時性閾値と腐敗性閾値との間で凸型であるが、正確な曲率は、特定の応用領域に従って変わる可能性があり、また、再び実験か他の方法により確立され得る。
【0063】
特定の例としては、Aは、通信バンド幅割り当てアプリケーションに対して、
【数4】
で定義されてもよい。
【0064】
ここで、
Pは、優先度
ltは、時間tでも未だ送信されるべきデータの総量
tjは、適時性閾値、pjは腐敗性閾値
tは、現在時間
nは、正の数(パラメータjの関数であってもよい)
である。
【0065】
図2bで概略的に例示されている例では、適時性閾値tjは9に設定され、一方腐敗性閾値Pjは15に設定されている。
【0066】
明らかに、優先度が増加するにつれ、リソース割り当ての重要性Aは増加し、適時性閾値tjに近づくにつれ、リソース割り当ての重要性は増加し、短い残り時間に大量の送信すべきデータltがあると、この重要性は同様に増加する。腐敗性閾値pjは、適時性閾値が過ぎた後に重要になり、時間が腐敗性閾値に近づくにつれ、Aは減少する。
【0067】
パラメータnは、調整を可能にし、この例では、優先度及び適時性が、腐敗性よりも優位を占めて、残りのデータが送信されるように選択される。1から100の範囲の値が調べられた。バンド幅トレーディング実施形態については、60代の数値が、より良い結果をもたらすことが分かった。
【0068】
リソースの適時な割り当ての重要度を計算することにより、ユーザは、彼らのリソース割り当て(この例では、情報転送)に対して重要度を与えることができる。ユーザは、また、彼らが有する残りの資金の量について気づくであろう。このようにして、トレーディングアルゴリズムが、バンド幅の価格を提示する時に、ユーザは、彼らの効用を最適化するであろうバンド幅を要求してもよい。必要とするバンド幅の要求は、式(1)から次のように導かれる。
【数5】
【0069】
ここで、cは、バンド幅の1ユニットのコストである。
【0070】
その後、トレーディングアルゴリズムが、リソース割り当てのための現在の要求の再計算と、リソースに対して過大な要求があるか(ネットワークが現在輻輳している)どうか、又はリソースに対して低要求(ネットワークは輻輳していない)かどうかに基づいて、バンド幅に対する新価格の提示とをするための、トレーディングアルゴリズムを用いることができる。
【0071】
トレーディング方法は、オークション手段により前もって適用することができる。このような解決方法は、スポット(短期)マーケット及び将来(長期)マーケットの両方に対して作用する。ネットワークトレーディングアルゴリズム(NTA)は、将来のタイムスロットに対する1組の価格を計算し、この後、ユーザが彼らの支払い能力と、利用可能なタイムスロットを獲得することで得られるであろう効用とに応じて、各スロットのバンド幅に対して入札する、オークションが開催される。NTAは、要求に応じて各タイムスロットにおける価格に対して調整をかける。プロセスは、均衡するまで繰り返され、この均衡により、バンド幅に対する要求が、利用可能なタイムスロットを超えることは決して無く、また、ユーザは、彼らの資金及び効用に応じてバンド幅を割り当てられたことになる。これには波及効果があるが、理由は、タイムスロットが将来にわたって、自然とより低い要求状態にある可能性があって、結果的により安価になるからである。これは次に、より安いバンド幅を使用することを待つ高い効用を有するユーザにとって、これらを潜在的により魅力的なものにする。
【0072】
さて、図3を参照すると、提案されるトレーディングアプローチは、非トレーディング解決方法を超える能率向上を提供する。トレーディング用いて時間にわたって成功裏に送信されたメッセージの数31は、トレーディング無しで達成されたメッセージの数32を超えている。
【0073】
さて、図4a及び図4bを参照すると、上で述べられた方法の使用することにより、高い割り当て重要度を有するメッセージに、より多くのリソースが比例して割り当てられる傾向にある。従って、例えば、時間325では、わずか小さい割合(およそ10%)の高優先度メッセージ41が、送信を待っているが、比例して多くのより高いバンド幅割り当て42がなされ、利用可能なバンド幅のおよそ60%を構成している。
【0074】
説明された特定の関係は、優先度の観点でのみリソース割り当てを差別化するが、上述したように、他の因子も同様にかかわる。
【0075】
Gibbens及びKellyにより説明された輻輳価格付けメカニズムは、説明されたトレーディングメカニズムと組み合わされて、どれだけのバンド幅が利用可能なのかを正確に知る必要なく、バンド幅を取引する手段を提供することができる。ユーザは、上述のトレーディングメカニズムを、バンド幅を直接購入するよりもむしろ、支払意思額(WtP)の値を買うために用いることができる。前に説明したように、高いWtP値は、ユーザへのバンド幅のより大きな割り当てを可能とするであろうことから、ユーザは、より高いWtP値を得るためにもっと多くお金を使いたいと望むであろう。リソース割り当ての本発明の方法は、またもちろん、他の知られているWtP方法と組み合わせることができる。
【0076】
このようなシステムに対するトレーディングメカニズムは、基本的には上述の通りであるが、利用可能なリソース(バンド幅)が100%であることを仮定している。各ユーザが割り当てられる割り当てバンド幅は、次に、最も高いリソース量を割り当てられるユーザが、例えば、WtP値10を与えられるように規模を設定される。他のユーザは、リソースを比例して割り当てられてもよい。例えば、ユーザAが80ユニットのバンド幅を割り当てられ、Bユーザが20ユニットのバンド幅を割り当てられている場合、ユーザAは、WtP値10を得てもよく、一方ユーザBは、WtP値2.5すなわちAの割り当ての1/4を得るであろう。実際のバンド幅の割り当ては、この後、それぞれの割り当てWtP値に基づいて、知られている方法により処理してもよい。
【0077】
さて、図5aを参照すると、従来のTCP割り当て方法に従うバンド幅割り当てに対する、送信成功率の実例は、別のトラフィックに対するリソース割り当ての相対的な重要性にもかかわらず、障害が、全てのカテゴリのトラフィックに均等に広がったような状況を引き起こす可能性がある。例示されたシナリオでは、各3つの優先度のカテゴリのトラフィックに対する結果が、示されており、低、中、高の優先度のトラフィックに対する、適時(適時性閾値の前)51、未腐敗(腐敗性閾値の前)52、及び不成功53のトラフィックのそれぞれの比率が、優先度にかかわらず広範に均一である。説明を簡単にするために、データが優先度に対してプロットされて示されているが、以上で説明したように他の重要性要素が適用されたということを再度留意されたい。
【0078】
これを、上述の本発明の方法に基づくバンド幅割り当てに関する図5bに例示された結果と比較すると、不成功トラフィック58、及び適時性閾値の後に配信されるトラフィック57は、主として低優先度、従って、黙示的にバンド幅割り当ての重要性が低いトラフィックで起こっているということに留意されたい。適時的な送信についてのより高い重要性を有する情報、従って、一般的にはユーザにとってのより高価値な情報は、優先的に取り扱われる。例示された例では、全ての高優先度のトラフィックは、適時的56aに配信され、一方、低優先度のトラフィックのわずかな部分だけが、適時的56bに配信される。
【0079】
リソース割り当ての適用の更なる例として、及び図6をここで参照するが、ネットワークのユーザ60は、リソース「クラウド」61に対して、ネットワーク周辺のコンピュータ62上のソフトウェアアプリケーションプログラムを用いることにより要求を出して、ウェブサーバ63から情報を得るか、又はファイルサーバ64にファイルを送信する。クラウドは、ルータ66とサーバ63から65のネットワークを含み、一定のバンド幅リソースがあることと、バンド幅を管理するネットワークトレーディングエージェント(NTA)65が存在することが、仮定される。バンド幅管理者は、ルータ及びサーバが、どのように接続されているかについての正確な詳細を、バンド幅に対する要求又はサーバ能力を管理するために知る必要はない。ネットワークは、一定のリソースのクラウドとして扱うことができ、これを妥当な仮定とするのは、基礎となるプロトコル及び管理システムである。この場合は、ネットワークバンド幅は、需要と供給のバランスを取ることにより取引されるリソースと見なされる。サーバの能力は同様に、ネットワーク内の限定的な要因と考えられる場合には、同様な方法で取引されることもあり得る。
【0080】
さて図7を参照すると、各ユーザ60は、NTAサーバ65に接続するためのユーザエージェント62に作用することにより、ネットワークに加わる。ユーザエージェントは、ユーザアカウント詳細71をNTAサーバに渡し、NTAサーバは、特定の情報価値72の詳細及びこの特定のユーザのための資金73の割り当てで応答する。各ユーザに割り当てられた資金は、ユーザが使用することを許可されるネットワークリソースの比率を表し、従って、ある意味では、各ユーザの相対的な重要性を反映する。情報価値は、ユーザについての、情報の相対的重要性、データの相対的適時性及び相対的腐敗性を反映する。ユーザエージェントソフトウェアの存在は、ネットワーク管理システムがこのソフトウェアからの応答を要求することにより検証され、ユーザがこれを無効にしていないことを確実にしてもよい。ユーザエージェントソフトウェアが、特定のユーザについて動作していることが確認できない場合は、好ましくは、ユーザのコンピュータは、ネットワークから締め出され、例えば、再接続のためにネットワーク管理者へのコンタクトを強制される。
【0081】
各ユーザへの資金の割り当ては、各予約マーケットトレーディング期間の初めになされる。この割り当ては、この期間(これは、月、週、日、分、秒、ミリ秒、又はアプリケーションにとって適切な任意の他の時間期間であってもよい)に対する、ユーザ資金として考えることができる。予約マーケットは、この後、次のように動作する。
【0082】
図8をここで参照すると、ユーザ61は、所定の時間間隔の間(これは、例えば、営業日ということもあり得る)に、ユーザが、ファイルサーバ64に転送したい情報、及びユーザが、ウェブサーバ65から欲しい情報を特定する。これは、スケジューラを用いてなされ、いつ情報が転送されるかの柔軟性は、代替時間及び変動耐性を提供することにより示される。例えば、ユーザは、ファイル転送について1時間はいずれにしても問題ないということを指定してもよい。
【0083】
ユーザエージェント62は、次に、タイムスロット化されたリソース要求ベクトル81を計算し、これをNTAに宣言する。NTAは、価格ベクトル82を、ネットワーク内で利用可能なバンド幅、及びユーザとサーバとの間の情報の転送を促進のサーバの負荷等の、関係する全てのリソースに対する総要求を計算することから生成される全ての価格を加算することにより計算する。
【0084】
一旦、ユーザ(又はユーザエージェント)が、タイムスロット当たりのリソースに対する価格を知れば、ユーザは、自分の要求を変更することを選択し、調整されたタイムスロット化リソース要求ベクトル83を提出し、続いてNTAから調整された価格ベクトル84を引き出してもよい。
【0085】
転送される情報(例えば、ユーザからファイルサーバへのファイル転送)については、トレーディングは、ユーザエージェントとNTAとの間で上に示したように実行される。ウェブページを要求するときのウェブサーバへの送信トラフィックを含む、全ての送信トラフィックが、このような方法でおそらく取引されるであろう。
【0086】
受信情報(例えば、ウェブサーバ63からのウェブ情報のダウンロード)については、送信トラフィックについては上述のようにトレーディングが実行されるが、この場合は、ユーザエージェント、ダウンロードのためのデータを格納するサーバ、及びNTAの全てが、取引に関与する。この場合、先行段階が追加され、ユーザは、ウェブサーバにダウンロードされる予定のファイルのサイズの目安87を要求86する。一旦、ユーザがこの情報を知ると、プロセスは上記のように進行する。これは、ファイル転送の間に受信される制御データに対する認容も含む、全ての受信情報に当てはまる。
【0087】
情報の送信及び受信のためのトレーディングは、実際には同時に起こるかもしれない。例えば、リソースベクトルは、送信及び受信に対して同時に計算されて、NTAに一緒に送られることがあり得る。NTAは、この後、送信及び受信価格ベクトルの双方によって同時に応答することができる。送信リソース又は受信リソースのいずれかに対するトレーディングは、他方よりも長くかかるかもしれないので、トレーディング停止の指示が、送信トレーディングを停止85a又は受信トレーディングを停止85b、又は双方を停止するかどうかを指示する必要がある。代替策としては、送信及び受信交渉は、無関係に進行してもよい。
【0088】
予約マーケットに参加しなかったユーザが、いくらかのリソースを得ることができるように、追加のリソースが、スポットマーケットで利用可能にされる。従って、NTAは、利用可能にされたリソースの増加に比例して価格を低減する。スポットマーケットのトレーディングは、各予約マーケットタイムスロットで実行される。例えば、それぞれの1時間が分間隔に分けられ、予約マーケットに参加したユーザらとちょうど今やってきたユーザらが競い合う微細時間トレーディングが行われる。スケジューラは、予約ユーザに対するリソースについての要求を開始し、実際のユーザは、リソースに対する要求をもたらすアプリケーションを開始する。トレーディングは、スポットマーケットに対しても、微細時間に対してではあるが、予約マーケットに対して行ったのと全く同様に機能する。ユーザは、1時間単位のタイムスロット内で例えば毎分ベースにリソースを割り当てられる。リソースに対する価格は、予約マーケットで到達した価格に基づく。予約しているユーザは、ユーザの割り当てを毎分ベースで用いなくともよく、このことは、予約しなかったユーザに対して利用可能なリソースを委ねることになる。また、毎分ベースでは、一部のデータが遅れても、これを用いるアプリケーションに影響を与えることがないかもしれず、従って、予約しなかったユーザに対するデータは、予約したユーザに対するデータとインターリーブされるということもあり得る。
【0089】
情報価値ファイルの別の部分は、予約したユーザによって用いられ、これらユーザの情報に、より高い重要性、従って高い優先度を与える。スポットマーケットユーザが、リソースの一部を取得するのは可能であるが、この優先度方法によればこれは起こりそうも無い。また、予約ユーザは、前もって彼らが必要なリソースに合意していることから、割り当てされたリソースを超えるリソースに対する効用は持つことは有りそうも無い。従って、予約マーケットにリソースを抱え込んでおき、後でこれをスポットマーケットに開放することにより、スポットマーケットユーザは利益をこうむる傾向がある。
【0090】
従って、前もってリソースに対する要求を取引する準備できたユーザは、例えば1時間間隔等の粗いタイムスロットについてスケジュールを生成する予約マーケットに参加する。全てのユーザは、より多くのリソースが、スポットマーケットユーザに便益を与えるための「売り出し」に放出される、スポットマーケットに参加する。取引は、データが、これを必要とするアプリケーションを中断することなく遅延することができる、微細時間内で行われ、予約したがもはや同じ要求は有していないユーザは、微細時間内に、スポットマーケットユーザに対してリソースを開放することができる。微細時間トレーディングを適用することにより、ユーザデータは、動的にリソースの利用を最適化するためにインターリーブされることができ、予約したユーザと待つことや計画することについての準備ができていないユーザとのリソースの共有がなされる。
【0091】
図9aに示されるこのようなシステムの1つでは、予約マーケットの中で時間スロット91は、予約マーケットの送信トラフィックに関するトレーディングの結果として、ユーザに割り当てられてもよい。割り当てバー92の厚さは、各ユーザに割り当てられた帯域幅の量に比例しており、それぞれのタイムスロット内では、同じバンド幅の総量を割り当てしてもよい。この総量は、全体の要求に応じて、実際に利用可能な総量よりも少なくしてもよい。たとえこれらの予約がなされ、価格(バンド幅に対する価格及び/又はサーバ要求に対する価格)は、従って各タイムスロット内のリソースに対して定められたとしても、トレーディングは、それでもなお、これらのリソースが使用される前にスポットマーケットで行われる。
【0092】
今度はスポットトレーディングが、予約期間(この例では各1時間)内に、例えば、1分間のタイムスロットを用いて行われ、図9bは、図9aに示すような予約マーケットの時間1内のスポットトレーディングの効果を例示している。
【0093】
予約マーケットの時間1内では、予約ユーザ1、予約ユーザ3、及び予約ユーザ6が、予約をしている。スポットマーケットの分1内では、これらの各ユーザは、実際に彼らの予約された割り当てを使用する。しかしながら、追加のリソースがスポットマーケットをサポートするために残っていることから、スポットユーザ1は、いくらかのリソースを使用することができる。分2では、ユーザ6は、実際には割り当てを使用せず、そのためスポットユーザ2が、これを落札し使用する。予約ユーザが、彼らの割り当てを使用しないとき、又は具体的にリソースがスポットマーケットのために保有されるときはいつでも、スポットマーケットユーザは、彼らが使用しているアプリケーションの必要範囲内で、できるだけうまく利用可能なリソースを共有する。例えば、スポットユーザ2が、ファイル転送を実行したい場合、これを、予約ユーザにより開放されたリソースとインターリーブしてもよいことから、うまく成功するかもしれない。スポットユーザは、しかしながら、また、互いに自分のアプリケーションで必要な範囲及び情報の相対的価値の範囲でリソースを獲得することを競い合う。従って、スポットユーザは、必要なだけ遅れを我慢して、1分ごとにリソースに対して入札する。
【0094】
スポットマーケットでの交渉により生成されたリソース価格を用いて、ユーザエージェントは、この後NTAに、各スポットマーケット間隔(この例では、1分間のスポットマーケット期間)に対する支払意思額(WtP)値102について支払い101を行う。ユーザエージェントは、この後、スポットマーケットオークションに従った合意された速度で送信する。ネットワーククラウド10は、実際には完全に均一だということはありそうもないため、一部のルータは、例えば、輻輳する可能性がある。これらのルータは、ユーザエージェントに返される、輻輳通知を発行することによりこの状態を示すことができる。ユーザエージェントは、通知を照合し、WtPに逆比例して送信速度を調整する。ネットワーククラウドが、まさに完全に均一なリソースの場合は、予約とスポットマーケットトレーディングのおかげによって、輻輳は起こらないだろうし輻輳通知もないであろう。このような1つの輻輳制御メカニズム(例えば、Gibbens&Kelly輻輳制御モデル基づくような)は、データの送信が始まるときに、スポットマーケットタイムスロット内で働く、微調整メカニズムである。輻輳に至ったクラウド内の全てのリソースは、輻輳通知で応答することができるということに留意されたい。これは、新たなスポットマーケットの割り当てが、新しいWtP値を購入するために用いられ、また送信が、輻輳通知に応答して下方に調整された新たな速度で始まる、次のスポットマーケット間隔まで続く。
【0095】
上記の予約マーケットと、スポットマーケット及び輻輳制御エレメントとの組み合わせは、以下の例により例示される作用を引き起こす。
【0096】
予約マーケットでは、全体の利用可能なリソースの或る割合は、スポットマーケット上のオークションのための最小限の利用可能なリソースを残すために、オークションにはかけられない。
1.新ユーザの登録71。ユーザエージェントは、ユーザの代わりに取引を行うソフトウェアとして配置される。
2.ネットワークトレーディングエージェントNTAは、情報価値ファイル72をエージェントに渡す。
3.NTAは、エージェントに資金及び収入を割り当て73する。
4.リソース予約の準備ができていない場合は、ステップ16に行き、そうでない場合は、情報交換要求がスケジューリングインターフェースを通して生成される。
5.リソースベクトル81が、送信される情報のためにNTAに送られる。
6.NTAは、価格ベクトル82で応答する。
7.リソース要求が、受信情報91のために情報サーバに送られる。
8.サーバは、NTAへのリソースベクトル92を代理で生成する。
9.NTAは、価格ベクトル82でユーザエージェントに応答する。
10.情報価値ファイルを用いて、ユーザは、送信及び受信リソースベクトルを更新する。
11.更新された送信及び受信リソースベクトル83をNTAに送信する。
12.NTAは、送信及び受信価格ベクトル84で応答する。
13.ステップ10を、価格ベクトルが安定するまで、又はユーザが処理を放棄するまで繰り返す。
14.情報を送信及び受信する予定時間になったら16に行く。
15.新ユーザの参加又はリソースの利用可能性が変化したら、NTAが、新たなオークションを開始(ステップ10でリスタート)するか、又は割り当てパラメータをオークション中に修正してもよい。
【0097】
一旦、長期予約オークションが完了したら、短期間のスポットマーケット割り当てを始めてもよい。スポットオークションは、概して予約マーケットオークションに酷似しているが、この場合は、利用可能なリソース全てが、オークションに使用でき、如何なる他の目的のためにも留保される必要はない。
16.新たなまたは修正されたリソースベクトルが、送信される情報のためにNTAに送られる。
17.NTAは、予約マーケットオークションから導かれた価格ベクトルで応答する。
18.新たなまたは修正されたリソース要求が、受信情報のために情報サーバに送られる。
19.サーバが、代理でNTAへのリソースベクトルを生成する。
20.NTAは、ユーザエージェントに予約マーケットオークションから導かれた価格ベクトルで応答する。
21.情報価値ファイルを用いて、ユーザは、送信リソースベクトル及び受信リソースベクトルを更新する。既にリソースを予約したユーザは、予約されていないリソースを要求するユーザよりも優先的に扱われる。
22.更新された送信リソースベクトル及び受信リソースベクトルが、NTAに送られる。
23.NTAは、送信価格ベクトル及び受信価格ベクトルで応答する。
24.価格ベクトルが安定するか、又はユーザが取引を放棄するまで、ステップ21から繰り返す。
【0098】
予約オークション及びスポットオークションが完了したとき、リソース利用に取り掛かる。輻輳価格制御が、作動し任意のリソースの過大割り当てをも修正するのは、この段階である。
25.リソースに対する同意されたオークション価格に従って、ユーザエージェントは、NTAからWtP値を購入し、且つ/又はリソース利用を予約又は優先化するQoSパラメータを購入する。
26.リソースに対する合意されたオークション価格に従って、情報サーバエージェントは、NTAからWtP値を購入し、且つ/又はリソース利用を予約又は優先化するQoSパラメータを購入する。
27.ユーザ及び情報サーバは、適切な輻輳制御方法(例えば、Gibbens&Kellyの輻輳制御方法)を用いて、受信された輻輳料金及び購入されたWtP値に従って速度を調整しながら、情報を転送する。
28.リソースが余りに輻輳状態になり、もはや継続が困難になった場合は、ステップ4にいく。
【0099】
このリソース割り当て方法は、予約マーケットとスポットマーケットの2段階の割り当ての観点で説明されたが、リソースは、単一段階モデル(実際には、スポットマーケットモデルのみだが、アプリケーションにふさわしいように任意の継続期間の時間尺度をもって)を用いて完全に割り当てされるということも有り得るし、同様に、方法が、3つ以上のずっと微細な時間間隔の割り当てレベルを含んでもよいことは明らかである。
【0100】
コンピュータ又は通信ネットワーク内でのリソース割り当ての観点で、上で詳細説明されたが、基礎をなす方法は、明らかに広範囲の分野にずっと広範な用途を有する。これらの多くは、同様にコンピュータ及び通信システムに関連し(しかし決して全てではない)、以下のものを含む(但しこれに限定されず)。
【0101】
・ 輻輳管理 − 料金請求は、輻輳が起こされた事実を数えることにより、ネットワーク利用に対して適用されることができ、輻輳が高ければ、コンピュータは、リソース割り当て方法に基づいて、この輻輳のネットワーク利用を低減させる。このことは、ネットワーク装置障害の発生を低減させることにより、及びリセットの必要性又は利用度の高さに対応するためのネットワーク能力の見直しの必要性を低減させることにより、全体としての費用を節約することになる。
【0102】
・ ディザスタリカバリ − ネットワーク上での過大要求の期間に、突然且つその結果警告無しにネットワークが故障するのではなく、むしろ制御されたやり方で劣化するように、利用を制御してもよい。
【0103】
・ コアサービス保証 − 或る企業に対して高い重要性を有するサービスを、ネットワーク及びシステムリソースの過大利用により他が機能していないときでさえ維持されることができる。コアユーザ及びコアサービスの両方が、過大要求による崩壊から保護されることができ、企業の重要サービスの損失を節減する。
【0104】
・ サービス要求管理 − 例えば、ウェブホスティングサービス等を提供するケーブルネットワークで、サーバを、サーバの崩壊につながる要求のピークから保護することができる。サーバ時間は、割り当てられたリソースである。この状況では、サーバは、ネットワークが必要以上のかなり多くのバンド幅を提供することができるような、過大要求から保護する必要のあるリソースである。サービスの停止時間とサービスの回復のためのコストとが避けられる。
【0105】
・ アプリケーション層の速度適応及び入場制御 − 本発明のリソーストレーディング解決方法は、コンピュータアプリケーションソフトウェアと密接に連動するように設計されており、また、そうすることにより、ネットワークが要求によって遅くなるが、アプリケーションソフトウェアがネットワークを使おうと試し続けてしまう、頻繁に起こる問題に対処する。これは、サービス及びコンピュータのハングアップにつながり、また、不正のためにアプリケーションを再インストール又はコンピュータソフトウェアを再構築する必要につながる可能性がある。本発明の方法をリソースの割り当てに用いることにより、アプリケーションソフトウェアデータの喪失も、回避されるかもしれない。
【0106】
・ リソース割り当て及びサーバ共有 − サーバに対するユーザの要求は、要求を共有することで管理されることができる。上述のトレーディングメカニズムは、サーバが顧客又は企業にサービスを提供するのにどれだけ忙しいかを考慮に入れて、要求を割り当てすることを可能とする。
【0107】
・ スペクトル管理 − 無線スペクトルは、動的に共有されることができる、貴重で限られたリソースである。割り当ては、トレーディングメカニズムを用いて制御されることができる。こうすることにより、アプリケーション、ネットワークオペレータ、又はエンドユーザ(例えば、携帯電話ユーザ)にサービスを提供する上で利用可能なスペクトルの最適な利用がなされ得る。
【0108】
・ 情報管理 − 価値を情報のアイテムに関連付ける単純な方法が適用される。上述の割り当て方法の適用は、高いネットワーク要求の期間に、情報の価値に従って情報を優先付けすることにつながる。これは、事業的に重要な情報又は高収益を生む情報は、ネットワークが輻輳しているときに転送され、重要でない情報は遅れさせられるということを確実にする。
【0109】
・ ユーザ要求管理 − ちょうど情報が、高ネットワーク要求の期間に優先付けされてもよいように、特定のユーザが優先されてもよい。この技術は、事業にとってのユーザの重要度と、事業(又はユーザ)にとっての情報の価値のバランスをとることを可能にし、従って、どれだけ多くのリソースを割り当てするかを判断することを可能にする。
【0110】
・ エンドツーエンドサービス管理 − 本発明の方法を用いるリソーストレーディングメカニズムを適用するためには、解決方法がサービス及びユーザに基づき、ネットワーククラウドにわたってエンドツーエンドで動作することから、ネットワークがどのように作用するのかについての内部的な詳細を理解又は知る必要が無い。従って、これは、これらリソースがどのように提供されるのかにかかわりなく、共有されるバンド幅とサービスシステムを提供するネットワーク全域にわたって、ユーザに合意されたサービス品質を提供する手段を提供することを支援する。
【0111】
・ 動的バンド幅割り当て − バンド幅は、オンザフライで、低減された構成コストで、且つ専門家の介入の必要なく、割り当て及び管理されることができる。
【0112】
・ 動的サービス料金請求 − サービス、情報、及びバンド幅利用は、利用にしたがって料金請求することができる。コスト及びトラフィックは、サービス、情報、及びバンド幅に対する要求に基づく料金に加えて含まれることができる。
【0113】
・ 衛星リンクのチャンネル管理 − リソーストレーディングメカニズムは、実際の資金を請求することにより、又はユーザとサービスとの間の共有チャンネルを含む利用可能なチャンネルの最良の利用を図る方法としてのいずれかによって、衛星リンクのチャンネル取引に適用されることができる。
【0114】
・ サービスコスト及び輻輳に敏感な、バンド幅の予備割り当て − 企業にとってのコストを節約するため、この解決方法は、別のサービスプロバイダにより提供される代替リンクを利用する企業への実際のコストの総額を考慮に入れて、用いられることができる。例えば、主インターネットリンクが輻輳になり、且つ限定された能力の代替リンクがある場合、予備として代替リンクを用いるコストが考慮され、その結果、この利用は主リンクの輻輳が軽減する時までに制限されることができる。
【0115】
・ バンド幅が限定された環境での利用効率の向上 − 無線リンクが通信を実現する主要な方法(例えば、ワイヤレスLAN)であるネットワークにおいて、リソーストレーディングは、限られた利用可能バンド幅の最適な利用を促進する。
【0116】
・ 企業プロセスに対する情報の重要性に従った、情報フローの最適化 − 転送される情報は、企業のニーズに従って動的に制御されることができ、より収益性の低いサービスについての、企業イントラネットによりサポートされるより重要性の低い企業関連するアクティビティは、企業の中核的なニーズを支配することにはならない。間接費を節約する、利益又は事業効率は、このようにして最大化され得る。
【0117】
・ 性能指標及びリソース利用及び能力計画のためのユーザ要求計算 − メカニズムが機能する方法に基本的に備わっているのは、ネットワークの使用されかたを追跡し、より多くのネットワークリソースを提供する必要性を評価するために用いることができる、性能指標である。
【0118】
・ 更新の必要性を遅らせる、レガシーネットワークにおけるトラフィック管理 − 基礎をなすネットワークとの直接的な対話の必要がないので、例えばリピータハブ等に基づくレガシーネットワークは、トレーディング解決方法が無い場合には全くサービス品質を提供する能力が無くとも、これを提供するように管理されることができる。レガシーネットワークを更新するコストは、メカニズムにより提供される指標が、必要な能力を提供するためにはそうすることが望ましいということを指し示すまで、延期され得る。停止時間のコストは、更新プログラムを計画している間、低減されることもできる。
【0119】
・ 3G及び他の無線通信システムにおける料金請求及びサービス管理 − 限られたバンド幅及びサービスリソースを最大限に活用する方法を提供するとともに、トレーディングメカニズムは、サービスに対してユーザに料金請求する直接的な方法をサポートし、これをすることにより、ユーザの行動は、彼らが支払う用意のあるサービスのレベルに従って変更され得る。
【0120】
・ 企業イントラネットへのインターネットサービスプロバイダ(ISP)リンクのような、有料サービスの利用管理 − 例えば、大学の資金の節約は、これらが自分達の内部リンク及びISPにより提供される外部リンク上で使用する、バンド幅を動的に管理することにより可能である。インターネット利用に対しISPがパケット当たりで料金請求する場合には、このメカニズムは、課された料金を管理する方法を提供する。同じ解決方法が、インターネットへのISPリンクを用いる企業イントラネットへも適用される。
【0121】
・ 予約されたが使用されず、おそらく無駄にされたであろうバンド幅の利用 − トレーディングメカニズムの1つの特徴は、全てのバンド幅は、管理された仕方で利用可能にされ、予約された能力の全てが使用された時点で、任意の使い残しのバンド幅の断片が、アドホックベースで用いられることができるようにするというものである。
【0122】
・ ポイントツーポイントトランクの最適化 − 多数のネットワークが、比較的低いバンド幅のリンクで相互接続されている場合、この解決方法は、リンク間の飽和及び犠牲の大きい故障時間を回避するため、ネットワーク間トラフィックを管理するために用いられることができる。
【0123】
・ ルートをベースとした情報フロー管理 − 情報は、ネットワークを横切って取るルートに従って管理されることができ、メカニズムは、ルートベースのトラフィック管理を提供するように適合され得る。
【0124】
・ 複数のネットワークの複合ネットワークにおける、エンドツーエンド情報フロー管理 − 複数のネットワークのネットワーク内では、リソーストレーディングは、ネットワークのそれぞれの部分内における要求を考慮に入れ、この後、複合ネットワーク全体にわたる情報フローを管理するように拡張することができる。
【0125】
・ 信頼できる分散型動的システムのセキュリティ − 全てのユーザが、NTAに登録しなければならず、また、資金を払ってネットワークリソースを利用することから、リソースへのアクセスは制御され且つ記録される。アクセスのセキュリティは、トレーディングメカニズムの帰結である。
【0126】
リソースが、比較的短い及び/又は長い時間スケールにわたって管理される必要がある他のアプリケーションは、同様に、上述の方法を適用する候補である。このような領域は、限定するものではないが、以下を含む。
・ 旅行、休日、及び催しものの会場予約システム(例えば、列車、航空機のシート、ホテルの部屋、劇場の席等への人の割り当て)
・ 道路混雑管理(例えば、道路の料金レベルの設定)
・ ユーザ要求に従う電話料金請求
・ ユーザ要求に従うオンデマンドのビデオシステム
・ 緊急性及び要求によるヘルスケア患者管理(例えば、医院や病院内の)
・ ユーティリティ供給及び/又は価格付け(例えば、デマンドドリブンの、ガス、水、電気等の供給及び/又は価格付け)管理
・ 株式分配システム
・ コールセンタ管理システム
【0127】
リソースが制約され、且つユーザ又は顧客にサービス又は製品を届けるために設計された他のシステムが、この解決方法により管理されることもあり得る。この解決方法は、従って、サービス、製品、又は施設を、多数のユーザ又は顧客又は他のリソース占有体/消費体に提供する需要がある、制約されたリソースを有する任意のシステムの管理に適用可能である。
【0128】
図11を参照すると、トレーディングシステムは、階層的及びピアツーピアトレーディング、並びにユーザ及びトレーダの地理的分散に基づくトレーディングの両方を含んでもよい。この事例では、リソース割り当て者の(従ってトレーダの)連続的なトレーディングレベル200から203が例示されている。スーパートレーダ200(例えば、国の無線スペクトル規制当局)は、多数の地域トレーダ201にリソースを割り当てしてもよく、次に地域トレーダ201は、彼らの割り当てられたリソースを区域トレーダ202にサブ割り当てする。各レベルにおけるリソース要求は、任意の所与の時間においてリソースに対して各トレーダが支払いを厭わない価格に影響を与える。
【0129】
ある場合には、同じレベルのトレーダ202a、202bは、ピアツーピアトレーディングと呼ばれる取引を彼らの間で行ってもよい。これは、現時点では又は当面は、トレーダ自身のユーザ共同体から必要とされないリソースを割り当てられたトレーダが、以前割り当てられたリソースを越えた要求を持つピアトレーダに、このリソースを再販売(状況に応じて臨時的に)することを可能にする。このようなトレーダの階層的及びピアツーピアネットワークの中で、リソース取引は、応用例とともに以下の表の中に要約された少なくとも次の方法で適用されることができる。
【0130】
これに関連して、本発明者らは、上述のようなリソーストレーディングアルゴリズムは、これを動作させることにより、しかしユーザに実際にリソースを割り当てすること無しに、リソースに対する価格を決定するために適用することができるということを観察した。このようにして、この方法は、階層的に上位の(又は同格又は他の任意の)リソース割り当て者からの自分のリソース割り当てに対して入札する時に、トレーダが用い得る入札価格を決めるために用いられることができる。これは、リソーストレーディング規模を拡大縮小することができ、且つ、以下でより詳細に説明される、さまざまなやり方の全範囲を利用可能にする。応用の領域の例は、次の表の中に示されている。
【表1】
【0131】
これらの各ケースの中で、リソーストレーディングアルゴリズムは、ローカルトレーダと取引する中央トレーダに実装することができ、又はトレーダ間の取引により実行されるということもあり得る。これらのインプリメンテーションは、リソース割り当ての取引に、及び要求に応じたリソースの取引に、必要に応じ組み合わせることができる。従って、階層的なトレーディングは、ピアツーピアトレーディング等と組み合わせることができる。
【0132】
割り当てられたリソース内でのローカルトレーディングは、詳細に説明されたように、基本的なリソーストレーディングアルゴリズムを利用する。これは、ネットワークバンド幅のような単一リソース内のデマンドを管理するためにアルゴリズムを適用する、最も基本的な方法である。
【0133】
代替リソースにわたるトレーディングは、アルゴリズムの利用を拡張する追加の1ステップを含み、ここでは、ユーザが参加及び利用できるかもしれない1より多くのリソースが存在する。例えば、ユーザが参加することを選択することができるかもしれない複数の代替ネットワークが存在するかもしれない。これは、アルゴリズムが用いられる方法の、単純な拡張である。ユーザがリソースを使用したい場合、次にユーザは、トレーダから利用可能な各代替リソースについての現在のリソース価格を要求する。トレーダは次に、各リソースに関連する現在価格で応答し、ユーザは次に、最も低い現在価格を有するリソースに対するオークションに参加する。トレーディングアルゴリズムはその後、通常のやり方で動作する。
【0134】
所与の価格でリソース又は複数のリソースの販売を申し入れている1より多くのトレーダが存在する可能性がある。その結果として、ユーザは、単一のトレーダから提供される利用可能なリソース全体はもちろんのこと、トレーダ間で最も高価ではないリソースの供給源を選択することを選ぶことができる。
【0135】
ユーザはまた、例えば、価格暴騰のため、彼らのメッセージが継続的に腐敗しているということが分かった場合は、オークションから退去することを選択することができる。退去するユーザは、より良いサービスを得るために、代替策としてより安いオークションに移動してもよい。
【0136】
サービスに対するパスを確立するための、多数のリソースにわたるピアツーピアトレーディングとの関連で、アルゴリズムは、エンドツーエンドパスに沿ってのリソースの入札に適用することができる。例えば、ユーザが、ユーザのローカルネットワーク外のリモートサーバへのアクセスを必要とする場合、ユーザは、リモートサーバに至る途中の全てのネットワークからのバンド幅に加え、ローカルネットワークからのバンド幅が必要である。これは、ネットワークが、バンド幅を必要とする通過トラフィック(すなわち、自分のローカルユーザが発信元でも宛て先でもないトラフィック)に対応する必要があるということを意味する。各ネットワークは、この後、通過バンド幅についての要求に対する価格を決定するためにアルゴリズムを適用し、(随意的に)トラフィックはローカルに所有されているものではないとして関税を適用する。従って、複数のネットワークにわたってバンド幅を購入するために入札するユーザは、自分のローカルネットワーク内のローカルバンド幅に対して支払わなければならないだろうし、同様に関連する他のネットワーク全てにわたるバンド幅に対する料金を追加しなければならないであろう。
【0137】
従って、アルゴリズムは、次のように変更してもよい。ユーザは、自分のローカルトレーダと取引して、ローカルリソースに対する見積もりを得るであろう。ユーザは、また、ピアツーピアパスに沿って必要な、他の全てのリソースに対する見積もりも得る必要があるだろう。各リモートトレーダは、このユーザの要求を「所有」していないことから、彼らが見積もる価格に関税係数が適用されてもよい。ユーザは、この後、全ての見積もりを加えることにより、アルゴリズムを適用し、どれだけの量のリソースに入札するかを決定するであろう。よって、トレーディングアルゴリズムの中でユーザにより用いられるリソースに関する総価格Pは、以下のようにとなるであろう。
【数6】
【0138】
ここで、P0は、ローカルリソースに対して見積もられた価格、Tiは、通過デマンドに対してリソースiにより適用される関税、Pnは、リソースiにより見積もられた価格である。ユーザのトレーダは、提供されるパスに沿っての全てのトレーダとユーザに直接交渉させるよりはむしろ、ユーザに代わってこの価格を組み立て得る。
【0139】
ユーザにより要求されるリソースがバンド幅であり、リソースの一部は、例えばサーバ能力ということもあり得る。従って、リソーストレーディングアルゴリズムを使って、ユーザにサービスを提供する中で関係する全てのリソースは、このような方法で、ピアツーピア、トレーダツートレーダ、エンドツーエンドで取引されることができる。
【0140】
リソースの単一割り当てに対するピアツーピアトレーディングでは、トレーダは、自分を取り巻く一部の又は全てのトレーダとリソースに対する取引を行うことにより、リソースの割り当てのために取引をする。このようにして、トレーダは、区域ごとにリソースを割り当てられてもよい。これは、次のように実現されてもよい。
【0141】
割り当てに利用可能なリソースは、サイズによって、従ってトレーダにとっての価値によって順序付けられる。これらのリソースは、他のトレーダがオークションの結果としてこれらを主張する場合、ローカルテーブルの中では利用不可とマークをつけられる。第1のリソースが利用可能だとすると、トレーダは、リソースのサイズを測り、これを自分のユーザにリソース割り当てすることなしに、アルゴリズムを動作させるために用い、そうすることによりこのリソースに対する価格を決定する。トレーダは次に、この価格を用いて周囲の全てのトレーダと競り合う。トレーダが、最高値を付けた場合、このリソースを要求してこれを自分のユーザ間で取引し始める。そうでなければ、トレーダは、自分のローカルテーブルの中ではこのリソースを利用不可とマークをつけ、リストの中の次のリソースに対して処理を繰り返す。これは、トレーダがオークションに勝つまで、又は入札するための未割り当てのリソースが無いということが分かるまで、繰り返される。後者の場合、トレーダは、今後の入札ラウンドを待たなければならない。
【0142】
各トレーダに割り当てられた資金の相対的な量(これは、次に自分のユーザ間で共有される)は、価格入札に影響を与えることから、各トレーダがリソースに対する入札にどれだけ成功するかを決定する。このことは、このプロセスを制御して、リソースが要求に応じてトレーダに割り当てされることを確実にするために用いられることができる。例えば、リソース割り当てを勝ち取れなかったこれらのトレーダに、補償金を支払い、今後の入札ラウンドで、彼らが割り当てを勝ち取る可能性を高くしてもよい。各トレーダに割り当てられる資金の量は、リソースに入札するライセンスに対してトレーダがどれだけ実際の資金を支払ったかに関連してもよい。
【0143】
他の周囲トレーダは、リスト内の任意のリソースに対して入札するために、いつでもトレーダにオークションを呼びかけることができる。トレーダは、使用するリソースをまだ主張していない場合は、他のトレーダに競争入札することにより応答する。
【0144】
リソースの複数の割り当てに対するピアツーピアトレーディングでは、トレーダは、1より多くのリソースに対して入札することができる。再度、利用可能なリソースは、ローカルテーブルの中で順序付けられることができ(例えば、サイズにより)、リソースのサイズに従って、リソースの価格を判断するためのアルゴリズムを用いて、トレーダは最初の利用可能なリソースに対して入札する。オークションに負けた全てのトレーダは、彼らのローカルテーブルにリソースは利用不可とマークする。トレーダが、入札に勝つことによりリソースを主張した時点で、このトレーダは、同じような方法で更なるリソースに対して入札を続けてもよい。しかしながら、追加の入札では、トレーダは、自分の価格を決めるときに、入札するリソースのサイズに以前に競り落としたリソース全てを加える。従って、入札価格は、トレーダがますますリソースを勝ち取るにつれ低下する。このことは、リソースに対するトレーダの要求が満足されるにつれ、他のトレーダと競り合う時に更なるリソースを勝ち取ろうとはあまり判断しないだろう、ということを意味する。このようにして、一部のトレーダは、取引するためのリソースを1つ勝ち取ってもよいし、一部のトレーダは、多く勝ち取ってもよい。一部のトレーダは、全く勝ち取れないということも有り得、今後の入札ラウンドを待たねばならないということになるであろう。
【0145】
前と同様に、各トレーダに割り当てられた資金の相対的な量は、価格入札に影響を与えることから、各トレーダがリソースに対する入札にどれだけ成功するかを決定する。このことは、このプロセスを制御して、リソースが要求に応じてトレーダに、特に、以前の入札ラウンドで完全に負けたこれらのトレーダに割り当てされることを確実にするために用いることができる。各トレーダに割り当てられる資金の量は、同様に、リソースに入札するライセンスに対してトレーダがどれだけ実際の資金を支払ったかに関連してもよい。
【0146】
任意の他の周囲トレーダは、いつでも任意の利用可能なリソースに対してオークションを働きかけることができる。先に述べたように、リソースの利用可能性は、テーブルの中に表示され、各オークションの後、入札に敗れた全てのトレーダは、リソース入札は利用不可であるとそれぞれのローカルテーブルにマークする。
【0147】
共有されるリソースの割り当てに対する階層的なトレーディングの中では、リソーストレーディングアルゴリズムが、前に説明したようにリソース価格を決定する。これは、他のトレーダと共有されるリソースの一部の割り当てについて決定するために用いられることができる。例えば、同じキャンパスネットワークLANを共有する2の部門があり、それによって、各部門は自分のユーザに異なる量の資金が割り当てられており、異なるユーザニーズを有し、従って異なるリソース要求を有するということがあり得る。各部門は、従って、利用可能なバンド幅の或る割合を共有しており、この割り当て分を自分のユーザの中で共有しているかもしれない。それで、バンド幅の1/3が、部門Aに自分のユーザ全体で取引するために割り当てられることがあり得る。残りのバンド幅は、この後、部門Bの中で取引されるであろう。
【0148】
リソースのシェアは、次のように割り当てしてもよい。各トレーダは、全てのリソースが利用可能であれば、アルゴリズムに利用可能なリソースの全てを割り当て、自分のユーザ間でリソースについて或る価格に達するために取引する。この価格は、このトレーダの市場内のリソースに対する要求を反映する。この段階ではこれらのユーザは、アルゴリズムが、リソースの販売無しに価格のみを決定するために用いられるため、リソースを買うことはできないであろう。各トレーダに割り当てられるリソースは、この後、これらの価格により分けられる。従って、2人のトレーダaとbがおり、Paがトレーダaについて決定されたリソース価格、及びPbがbについて決定されたリソース価格、そしてRaで示されるaに対するリソース割り当ては、
【数7】
によって規定されてもよく、ここで、Rtは総リソースである。
【0149】
一旦リソースのシェアが割り当てされると、リソース取引が、通常のように、割り当てられたリソースに対するシェアを使って、各トレーディングドメイン内のユーザに対して開催される。
【0150】
ピアツーピアについては、各トレーダに割り当てられた資金の相対的な量は、価格入札に影響を与えることから、各トレーダがリソースのシェアに対する入札にどれだけ成功するかを決定し、またこのことは、このプロセスを制御して、リソースが要求に応じてトレーダに割り当てされることを確実にするために用いられることができる。各トレーダに割り当てられる資金の量は、リソースに入札するライセンスに対してトレーダがどれだけ実際の資金を支払ったかに関連するかもしれない。
【0151】
単一のリソースの割り当てについての複数のリソースにわたる階層的なトレーディングでは、異なるサイズの複数のリソースが、トレーダに割り当てするために利用可能である。リソースは、サイズに従って順序付けられ、最も大きなリソースが最も価値があり、最も小さいものが最も価値がないと判断される。全てのトレーダは、それぞれのリソースに対して入札し、最大のリソースから始まって最小のものに向かって進む。最初のリソースに入札する際、各トレーダは、リソースのサイズ(すなわち、バンド幅の量)を用いてアルゴリズムを動作させ、自分が自分のユーザに対して販売するかもしれないリソースの価格を決定する。この価格は、前に述べたように、トレーダのドメイン内のリソースに対する要求を表す。この価格は、この後、リソースを要求するための入札として単に用いられる。最高値で入札した、従って入札に勝つ必要性のきわめて高いトレーダは、リソースを割り当てられる。勝利者は、この後、このリソースを、アルゴリズムを用いて自分のユーザ間で取引するために用いることができ、このオークションプロセスを抜ける。次の利用可能なリソースが、この後、残っているトレーダにわたって同じようにオークションにかけられる。このプロセスは、トレーダに取引するための全ての利用可能なリソースが割り当てされるか、又は、全てのトレーダが取引するために必要なリソースを有するまで続く。リソース割り当てを勝ち取れなかったトレーダは、次の入札ラウンドまで待たなければならない。
【0152】
前と同様に、各トレーダに割り当てられる資金の相対的な量は、価格入札に影響を与えることから、各トレーダがリソースに対する入札にどれだけ成功するかを決定し、このことは、このプロセスを制御して、リソースが要求に応じてトレーダに割り当てられ、リソースを勝ち取れなかったトレーダに補償するために用いることができる。各トレーダに割り当てられる資金の量は、リソースに入札するライセンスに対してトレーダがどれだけ実際の資金を支払ったかに関連するかもしれない。
【0153】
複数のリソースの割り当てに対する複数のリソースにわたる階層的なトレーディングにおける目的は、各トレーダが、リソースのこの1つの割り当て以上に要求することができるように、トレーダにリソースを割り当てし、そしてこの後、1より多くのリソーストレーディングアルゴリズムを動作させて、これらの複数の割り当てを自分のユーザわたって共有することである。これは、前に述べたように、割り当てされるべきリソースを順序付けすることによりなされる。上述のように、トレーダは、各トレーダが入札するであろうリソースに対する価格を決定するためにアルゴリズムを用いて、最初のリソースに対して入札する。リソースはこの後、最も高い入札者に割り当てられる。最高値入札者は、この後、次の順番のリソースに対する入札に参加することにより、更なるリソースの割り当てに対する入札を続ける。しかしながら、今回は、最初の割り当てを勝ち取った入札者は、今オークションされているリソースのサイズに、前に勝ち取ったリソースのサイズを加えることによってアルゴリズムを使用して、リソースに対する自分の価格を決定する。これは、トレーダが、既にリソース割り当てされているので、追加のリソースに対するトレーダの要求はより少なそうであり、従って価格入札はおそらくより低そうだということを意味する。従って、アルゴリズムを用い且つすでに勝ち取ったリソースを入札されるリソースに加えることにより、既にリソースを有するトレーダに対して入札価格が決定される。最高値で入札したトレーダが、この後、このオークションのリソースを割り当てられるが、このトレーダは、既にリソースを有するトレーダであってもよいし、そうでなくてもよい。全てのトレーダがこの後、次の順番のオークションに参加し、プロセスは、全てのリソースが割り当てされるまで続く。一部のトレーダは、取引するための1つのリソースを勝ち取ってもよいし、一部のトレーダが多くを勝ち取り、一部は全く勝ち取らなくてもよい。
【0154】
前と同様に、或るトレーダの入札の成功は、他のトレーダと比較して、どれだけ多くの資金が割り当てられたかによって決まる。
【0155】
本明細書中で与えられた範囲又は機器の値は、本明細書中で教示されたものを理解する当業者には明らかなように、求められる効果を失うことなく拡張又は変更してもよい。
【図面の簡単な説明】
【0156】
【図1】本発明による第1の通信システムの概略図を示す。
【図2a】本発明による効用関数の概略グラフを示す。
【図2b】本発明による割り当て関数の重要度の概略グラフを示す。
【図3】本発明によるリソース割り当てと従来技術の割り当てとを比較する概略グラフを示す。
【図4a】どのように異なる優先度のトラフィックの相対的比率が、時間と共に変化する可能性があるかを示す概略グラフである。
【図4b】本発明により、どのようにバンド幅をこれに対応して割り当てしてもよいかを示す概略グラフである。
【図5a】従来技術によるバンド幅割り当ての概略グラフを示す。
【図5b】本発明によるバンド幅割り当ての概略グラフを示す。
【図6】本発明による第2の通信システムの概略図を示す。
【図7】本発明による第1の方法の概略図を示す。
【図8】本発明による第2の方法の概略図を示す。
【図9a】本発明によるリソース割り当ての第1の例を示す。
【図9b】本発明によるリソース割り当ての第2の例を示す。
【図10】本発明による更なる方法を示す。
【図11】本発明によるやはり更なるシステムを示す。
【技術分野】
【0001】
本発明は、限られたリソースの割り当てを管理するための、装置、方法、信号、及びコンピュータのためのプログラム、及びそれを組み込むシステムに関する。
【0002】
このようなリソースには、コンピュータ及び通信システムリソース(例えば、プロセッサ時間、バンド幅、無線スペクトル等)が含まれるが、これらには限定されない。このようなリソースは、例えば、列車、航空機、又は公衆の娯楽のための座席割り当てとともに、劇場の運営、及び更には宿泊及びパッケージ休暇等の、人々によって利用され/占有される、医療/病院リソースを含むリソースをも含む。
【背景技術】
【0003】
制限されたリソースの管理は、多くのアプリケーション領域に広がる問題である。
【0004】
対象の1つの特定アプリケーションは、コンピュータ又は通信ネットワーク内でのリソース管理にある。このようなリソースは、バンド幅及びサーバ負荷を含み、このようなリソースの管理は、従来、衝突検出、輻輳検出、及び流入制御等の比較的単純なメカニズムを用いて行われてきた。ネットワークの詳細な知識及び詳細な構成情報を必要とする、複雑なサービス品質メカニズムも同様に存在する。ケーブルネットワーク及び大きなバンド幅を提供することができるネットワークにおいて、輻輳問題は、より多くのバンド幅を提供することにより単純に対応されることが時にはある。しかしながら、無線ベースのネットワークにおけるバンド幅又はバンド幅が限られている任意のネットワークのように、リソースが更に一層制約されるシステムにおいて、単純により多くのリソースを提供することは、必ずしも選択肢とは限らない。
【0005】
更に、これが技術的に実行可能な選択肢であるとさえしても、より多くのバンド幅を提供するのは、費用がかかり、また、ネットワーク管理者に、要求に遅れを取らないようにするためにネットワークを更新し続ける圧力をかける。要求が、利用可能なネットワークリソースを越える場合、ネットワーク崩壊が次に起こり、問題を解決するためのネットワーク技術者及び専門家の介入に帰着する。輻輳の期間中は、ユーザ要求も要求された情報のいずれもが優先されることはない。
【0006】
他の応用領域では、リソース占有体(resource occupier)へのリソース割り当ては、多様な方法で取り扱われる。人々が、リソース占有体(部屋、ベッド、席等の割り当て)であるシステムの場合、通常、リソース割り当ては、継続的な人間の介入により手作業で行われてもよい。
【0007】
支払意思額(WtP)を、通信ネットワーク内のリソース割り当てに用いることが、米国特許第6,4987,786号明細書及び米国特許第6,556,548号明細書から知られている。Alberto Pompermaierによる論文「A pricing mechanism for Intertemporal Bandwidth Sharing with Random Utilities and Resources」(London School of Economics,Department of Mathematics research report LSE−CDAM−2002−06,9 July,2002)は、通信ネットワーク内のバンド幅割り当てについての価格付けメカニズムに関連している。
【0008】
R.J.Gibbens及びF.P.Kellyによる「Resource Pricing and the Evolution of Congestions Control」(Automatica 35(1999),1969−1985)という名称の論文は、ユーザが輻輳を起こしたことに対して料金を請求される、ネットワーク内の輻輳価格付けの方法を説明している。
【発明の開示】
【発明が解決しようとする課題】
【0009】
知られている無線スペクトル割り当てシステムに関しては、これらは、微細時間及び長時間の両方に対して動的には、また、特に知的な方法ではリソースを管理しない。実際のユーザの相互作用は、このようなシステムにおける割り当てに対する知られているアプローチの基本的な部分には含まれておらず、サービスに対する実際の資金の請求能力も無く、リソースの割り当ての能力も無い。知られている周波数割り当てアルゴリズムは、複雑で低速である。この領域の既存の技術は、動的ではなく、代わりに静的構成に従って動作し、多くの場合、このリソースを管理するために、管理されるリソースから状態ベースの情報を収集する必要がある。更に、既存の技術は、情報レイヤ又は製品レイヤでは機能せず、代わりに、どのようにリソースが操作されるかについての下位構造のプロトコルレベルで働く。
【0010】
本発明は、特に従来技術に関連する1つ以上の問題を軽減する、改良された装置、方法、信号、及びコンピュータのためのプログラムを提供することを求める。
【課題を解決するための手段】
【0011】
本発明者らは、リソースユーザへのリソース割り当ての効用は、時間とともに変化し、或る時間を過ぎると、この効用はゼロに低下するということを認識した。
【0012】
本発明は、単純な経済学的モデル用いて、リソース割り当て及び効用に関する前から存在する膨大且つ詳細な情報を収集する必要なく、制御された方法でリソースを管理することに向けられている。リソース占有体/消費体は、優先付けされ、また、リソース割り当てのパターンは、リソース占有体/消費体に対するリソース割り当ての価値の指標に従って、制御される。コンピュータ又は通信ネットワークの場合、このアプローチは、アプリケーション層で適用してもよく、また、アプリケーションが、ネットワークがまだ動いており輻輳していないと盲目的に想定して現在動作し、結果的にアプリケーション層の崩壊とデータの喪失を起こす問題を軽減してもよい。
【0013】
特に、本発明の第1の態様によれば、リソースに複数のリソース占有体を割り当てする自動化された方法が提供され、本方法は、各リソース占有体に適時性閾値(timeliness threshord)を関連付けすることと、各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算することと、割り当てのそれぞれの緊急性指標に応答してリソースを割り当てすることとを含む。
【0014】
有利には、リソース割り当ては、所与の時間においてリソースについての最大の必要性を有するリソース占有体のために重み付けし、一方、利用可能なリソースを占有することが、有益でないとはいかないまでも、より有益性の低いリソース占有体(例えば、リソースの占有が、役に立つ時期が過ぎてしまったため、リソースを占有しても、基本的な目的を満足させられない等)へのリソース割り当てを回避してもよい。
【0015】
本方法は、また、各リソース占有体に腐敗性閾値(perishability threshord)を関連付けすることと、適時性閾値、腐敗性閾値、及びリソース占有体のサイズの指標に応答して、割り当ての緊急性の指標を計算することとを含む。
【0016】
好ましい一実施形態では、腐敗性閾値が過ぎてしまったリソース占有体へは、リソース割り当てはしない。
【0017】
好ましくは、割り当ての緊急性は、適時性閾値までは増加関数であり、増加凸関数が最も好ましい。
【0018】
好ましくは、割り当ての緊急性は、適時性閾値と腐敗性閾値との間は減少関数であり、減少凸関数が最も好ましい。
【0019】
好ましくは、割り当ての緊急性は、腐敗性閾値の後ではゼロである。
【0020】
好ましい一実施形態では、緊急性指標Aは、
【数2】
のように計算され、ここで、
Pは、優先度
ltは、時間tにおいて要求されるリソースの量
tjは、適時性閾値(これは、パラメータjの関数であってもよい)
pjは、腐敗性閾値
tは、現在時間
nは、正の数である。
【0021】
リソースは、送信バンド幅を含んでもよく、送信バンド幅は、無線スペクトルバンド幅を含んでもよい。
【0022】
リソースは、人々によって占有されるためのエンティティを含んでもよく、リソース占有体は、人々を含む。
【0023】
リソース占有体はまた、乗り物を含んでもよい。この中では、割り当ては、輻輳料金請求を用いて行うべきである。
【0024】
リソースは、支払意思額の値であってもよい。一旦割り当てされると、これらは、続いて任意の知られている方法により実際のリソースを割り当てするために用いてもよい。
【0025】
本発明は、同様に、動作中に本方法の全ての機能を実行するために構成されたリソース割り当てシステムを提供する。
【0026】
特に、リソースを複数のリソース占有体に割り当てするためのシステムが提供され、システムは、各リソース占有体に適時性閾値を関連付けする手段と、各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算する手段と、割り当てのそれぞれの緊急性指標に応答してリソースを割り当てする手段とを含む。
【0027】
本発明は、また、機械で読み取り可能な形式で、且つ、動作中に装置及び/又は方法の全ての機能を実行するように構成された、コンピュータソフトウェアを提供する。
【0028】
特に、本発明の更なる態様によれば、リソースを複数のリソース占有体に割り当てするためのコンピュータのためのプログラムが提供され、プログラムは、各リソース占有体に適時性閾値を関連付けることと、各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算することと、割り当てのそれぞれの緊急性指標に応答してリソースを割り当てすることとのために構成されたコード部分を含む。
【0029】
本発明は、また、無線スペクトルの自動化された割り当てのための、方法、システム、及びコンピュータのためプログラムを提供する。
【0030】
特に、本発明の更なる態様によれば、第1の見込みスペクトルユーザ群の間で無線スペクトルを割り当てするための自動化された方法が提供され、方法は、第1の群のメンバ間で第1の自動化オークションを実行するステップを含み、ここで、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催された第2の自動化オークションに応答して決定され、方法はさらに、第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てするステップを含む。
【0031】
好ましい一実施形態では、第1のオークション及び第2のオークションは、リアルタイムで実行される。
【0032】
いくつかの好ましい実施形態では、リソースは、本発明の上述した前の態様の方法に従って、第2の群のメンバに割り当てされる。
【0033】
本発明の更なる態様によれば、第1の見込みスペクトルユーザの群の間で無線スペクトルを割り当てするための自動化システムが提供され、システムは、第1の群のメンバ間で第1の自動化オークションを実行する手段を含み、ここで、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催される第2の自動化オークションに応答して決定され、システムはさらに、第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てする手段を含む。
【0034】
本発明の更なる態様によれば、第1の見込みスペクトルユーザの群の間で無線スペクトルを割り当てするためのコンピュータのためのプログラムが提供され、プログラムは、第1の群のメンバ間で第1の自動化オークションを実行するように構成さられたコード部分を含み、ここで、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催される第2の自動化オークションに応答して決定され、プログラムはさらに、第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てするように構成されたコード部分を含む。
【0035】
好ましい特徴は、当業者には明白なように、適切に組み合わせることができ、また、本発明の如何なる態様と組み合わせてもよい。上に示した例を超える、本発明の他の利点もまた、当業者には明白であろう。
【0036】
本発明が、どのように実行に移されるかを示すために、本発明の実施形態が、これから以下に、単に例としての目的で、添付の図面を参照して説明される。
【発明を実施するための最良の形態】
【0037】
本発明の第1の実施形態は、バンド幅が限定されている通信ネットワークに対するユーザ要求の管理に対して適用される。
【0038】
当業者には明白なように、上述の解決策の範囲は、通信システムへの応用よりもかなり広く、多くの他の同様な問題に適用され得る。
【0039】
図1を参照すると、コンピュータネットワーク10は、情報を転送するために用いることができるリソースのクラウドとして扱ってもよい。このリソースは、多数のユーザ14を扱うためのサーバ12の能力であり得る。ここでは、リソースは、バンド幅であると見なされる。ユーザは、情報を送信するためのバンド幅を買うための資金及び収入を割り当てられる。ユーザは、また、バンド幅を購入するかどうか、及び購入する場合には、どのレートで又いつにするかを判断するために用いる効用関数を有する。ネットワークエージェント16は、いつでも要求に応じてバンド幅に対する値段を計算する。バンド幅を購入するユーザについては、このユーザは、自分のバンド幅ニーズをエージェントに宣言141する必要があり、エージェントは、次に価格で応答142する。ユーザは、その後、この価格で買うか、この価格でどれだけ買うか、又は待って資金を節約するかどうかを決定することができる。これを、複数回のサイクルにわたって繰り返し、ユーザが効率的にオークションに参加するようにすることができる。実際のユーザに対する要求を省くための1つのアプローチは、価格交渉及びバンド幅の入札をユーザの代わりに行う、ローカルソフトウェアエージェント(通常このネットワーク内で)を有することである。これは、内部価格付けとして知られている。しかしながら、実際のユーザ(例えば、人間)が、ユーザインターフェースを介してより直接的にかかわることができ、また、かかわる金が実際の貨幣であり得る、アプリケーションが存在する。このような解決方法は、外部価格付けとして知られている。
【0040】
本方法を適用してもよい、多数のコンテキストが存在する。
・ 関係するアプリケーション/プロセスの即時の適時性ニーズの範囲内でバンド幅を購入するための短時間の間、ユーザがオークションに参加することを可能にする、スポットマーケットアプローチ。
・ ユーザがこの場合もオークションに参加するが、前もってバンド幅のニーズを宣言する、将来マーケットアプローチ。
・ 起こしている輻輳に対してユーザが料金請求される、Gibbens&Kelly輻輳価格付けアプローチ。
【0041】
これらのコンテキストは、もちろん、1つのコンテキストに結合することができ、スポットマーケット及び将来マーケットモデルを、Gibbens&Kellyモデルのような輻輳価格付けモデルと結合することが、本明細書で提案されている。スポットマーケット及び将来マーケットは、特定の量のリソース(この場合は、バンド幅)が利用可能だという最初の前提に基づく、フィードフォワードスケジューリング解決方法として作動する。輻輳価格付けアプローチは、最初の前提に対する誤差を修正するフィードバックメカニズムを加え、ネットワーククラウド内で何が実際に起こっているのかについての詳細を考慮に入れる方法として作動する。
【0042】
ネットワークをバンド幅クラウドとして扱うことにより、リソース(すなわちバンド幅)の利用を管理することができるようにする適時の状態情報を維持する必要性は、除去される。例えば、ネットワーク全体を通してのさまざまな地点の負荷が測定され、ユーザ送信を制御するために用いられる、適用してもよい知られている制御理論アプローチがある。このアプローチは、負荷測定が平均化されるという理由と、これらの測定を集めるのには時間がかかるという理由で、おそらく不安定さを導く。このような解決方法は、複雑でもある。本構成のように、より抽象的なレベルで(コンピュータ又は通信ネットワークの場合、アプリケーション層で)作動することにより、多くの複雑さが除去されるだけではなく、ネットワーク要求に従ってアプリケーションを見積って適応させるメカニズムが提供され、顧客の行動を含むアプリケーション層までの幅広いエンドツーエンドのトラフィック管理を提供する。
【0043】
トレーディングメカニズムの他の利点は、スケジューリングメカニズム及び急激的/爆発的飽和を避けるメカニズムを有することにより、限られた資源の利用効率の向上である。また、ユーザが有することができるリソース共有は、割り当てられた資金によって制御される。最終的に情報は、この事業又は運営に対するこれの価値に従ってエンドツーエンドに管理され得る。このような方法で、補正するには効率向上が充分ではない輻輳の期間には、低い情報価値を提供しているサービスは、停止し始めるであろう。高い情報価値を提供しているサービスは、存続するだろう。その結果、コアサービスは、周辺サービスよりも優先され、保証されることになる。また、サービスの管理は、これらのサービスが提供する情報に従って、細部にわたって影響を受ける。従って、この解決方法によって提供される主な機能は、
・ ユーザ要求管理、
・ 効率向上、
・ 情報管理、
・ アプリケーション層における料金及び入会料金コントロール、
・ エンドツーエンドトラフィック管理、
・ 対応している通信の状態又は構造についての詳細を知る必要がないこと、
・ システム内の全てのユーザが、トレーディングエージェントに登録が必要なことである。
【0044】
他のリソースが制約されたシステムにおいて、これらシステムは、均等物、すなわち、ユーザ要求管理は、顧客要求管理に相当してもよいことと、情報管理は、顧客へのサービス又は製品の管理に相当してもよいこととを有する。アプリケーション層における料金及び入会料金のコントロールは、システムの管理が、高い包括的なレベルで実行されるということを事実上意味する。エンドツーエンドトラフィック管理は、エンドツーエンドのサービス提供と見てもよい。最後に、提案されるトレーディング解決方法が機能するためには、システムの内部メカニズムのいかなる詳細な知識も必要はない。
【0045】
ユーザは、情報を転送する必要を有すると見なされており、転送している情報は、このユーザにとって価値を有すると見なされる。ユーザにとって価値の有る情報を転送するために必要なバンド幅に対する支払いをするためのコストの関数は、このバンド幅の使用の処置におけるユーザの効用を形成する。情報の価値とバランスが取れるコストが法外に高く、そのためユーザの効用が低い場合は、ユーザは、この情報をより安い料金で転送するか、又は全く転送しないことを決めることができる。一部の情報は、或る閾値未満の送信速度では価値を有さないであろうし、そのため、このユーザにとって、バンド幅をこのような閾値を下回るまで減らす効用は無いかもしれない。また、情報の価値は、転送速度の低下に伴って低下するかもしれず、従って、情報の価値とバランスが取れて、この情報を所与の速度で送信することに対するユーザにとっての効用を最大化する、バンド幅の最適価格というものがあるかもしれない。最後に、情報の価値は、おそらく多くの場合、時間の増加とともに減少し、従って、これは同様に効用関数で大きな特徴となり、また最適時間、速度、及び価格選択に影響を与える。
【0046】
不必要な要求をユーザに課すのを避けるために、このモデルは、ユーザインターフェースが、ユーザに代わって、情報を伝えるためにいつバンド幅を購入するかの決断のために作用するという考えを含む。このようにして、限定されたリソースを使うときのユーザの動作は、このユーザインターフェース及びトレーディングメカニズムを実装するソフトウェアによって制御され得る。このリソーストレーディングモデルの構成ブロックは、従って、
・ 資金 − 購入される利用可能な総リソースの表現。資金の総額は、対応する利用可能な総リソースを超えない。
・ バンド幅 − 通信ネットワークから提供されるリソース。これがどのようになされるかの詳細は、モデルには関係しない。
・ 情報価値 − 情報の中身、情報の量、配信の適時性、運用事業に対する重要性等に関する価値。
・ 効用 − ユーザが得る、資金に見合う価値を示す、コストと情報価値のバランス。
・ ユーザインターフェース − ユーザに代わって、いつ情報を伝えるためのバンド幅を購入するかについての決定を行うソフトウェア。
・ ネットワークトレーディングエージェント(NTA) − ユーザ要求及びバンド幅供給を考慮に入れて、バンド幅の使用に対する価格を計算する機能を持つサーバ。ネットワークに参加する全てのユーザは、このサーバに登録し、バンド幅利用するために支払う(サーバに)。
【0047】
上記のモデルには、かなり前の時間にリソース要求が宣言される第1のバージョンと、リソース要求が必要な時に宣言される第2のバージョンとの、2つのバージョンがある。
【0048】
第1のバージョンは、テレビ会議を予約するように、ユーザが前もって必要性を宣言することを可能にする。ここでこのモデルの構成要素は、オークションアルゴリズムを用いて適用され、ユーザデマンドがスケジュールされる。このアプローチは、将来マーケットモデルであり、ユーザとのより多くの相互作用が要求される。
【0049】
第2のバージョンは、スポットマーケットモデルであり、ここでは、例えば、eメールが5分間遅れたとしても、ユーザにおそらく心配されないように、又はウェブページのロードが5秒までならおそらく許容されるように、オークションアルゴリズムが、非常に短い時間尺度で適用される。スポットマーケットモデルでは、オークションプロセス中に、エージェントがユーザに代わって作用することから、実際のユーザは、トレーディングメカニズムが動作中であることを気が付かない。最終的に上記のアプローチは、輻輳価格付けアプローチ(例えば、Gibbens&Kellyの輻輳価格付けアプローチ)と組み合わせてもよく、これによりユーザは、輻輳を起こしたことに対してネットワークにより請求される。このようにしてネットワークは、オークションアルゴリズムにより生成された事前スケジューリング解決方法を微調整するために、フィードバック輻輳制御を行使することができる。
【0050】
図1に示すように、リソーストレーディングモデルに対する支援アーキテクチャについての2つの態様がある。バンド幅を取引するために、値付け及びバンド幅販売の役割を持つエージェントとして動作するサーバが提供される。情報の価値は、各ユーザのインターフェースによって知られている。輻輳に対して料金請求ができるように、ネットワークは、輻輳が発生する如何なる場所でも、輻輳通知を生成する必要がある。これは、ネットワーク内で、例えば、ルータインターフェースにおいて実行され得る。この支援アーキテクチャは、従って、バンド幅クラウドを支援して、ネットワークの状態に関するほんのわずかの詳細情報を最小限しか要求しない。
【0051】
送信データは、弾力性(elastic)のものと、非弾力性(inelastic)のものとの、2つのタイプの1つであると考えることができる。例えばeメール又はファイル転送のような弾力的なトラフィックは、動的な制御により、任意の速度で送信することができ、この速度は、利用可能なバンド幅に従って増減されることができる。音声やビデオ等の非弾力的なトラフィックは、固定バンド幅を必要とし、従って如何なる速度調整も、量子化ステップで行わなければならない。必要なバンド幅の量は、コールの要求品質によって決まる。
【0052】
トレーディングについての以下の議論は、より高い柔軟性を可能とする弾力的なトラフィックに主として集中する。しかしながら、このアプローチは、非弾力的なトラフィックに対しても作用する。
【0053】
人間のようなタイプの行動をモデル化するのは、決して容易な仕事ではないが、経済学の文献の中では、選択と個人の満足の概念が、効用関数を用いてしばしばモデル化されている。これらの関数は、1組の選択肢に対する個人の嗜好を表わしている。これは、ある面では、満足の尺度である。しかしながら、一般的に、これらの関数が、正確に知られる可能性は非常に低そうだということに注目すべきである。これらは、単に、本発明者らの考えを明確にし、どのようにユーザが行動するかについての単純な概念を構成する助けになるだけである。このようなモデルは、現実を記述しようとしているのではなく、より複雑な真の状況と同じ論理的な構造でもって、単純化された状況を組み立てようとしているのである。
【0054】
さて図2aを参照すると、トレーディング解決方法で用いることができる、効用関数の典型的な例が示されている。このグラフは、リソース(この場合はバンド幅)の特定の量を割り当てされた結果として、ユーザが受け取る、効用値U(x)を示している。描かれた効用関数は、弾力的なトラフィックに対する効用関数の典型であり、非弾力的なトラフィックに対応する予定であれば、対応する効用関数は、同じような形ではあろうが、滑らかなカーブというよりはむしろ、量子化されたステップを有する。一般的に、ユーザがより多くのバンド幅を割り当てされればされるほど、ユーザは、次にこのリソースをより速くデータを送信するために所有し、その後わずかな遅延を体験することになるので、このユーザはより満足する。効用曲線20は、典型的には、ユーザが追加の1単位のリソースを受け取ることから得られる追加の効用21は、正ではあるが、以前に特別なリソースの任意の単位を受け取ったことによって得られた限界効用22未満というようなものである。例示されている事例では、ユーザは、最初の数ユニットのバンド幅に対して効用の最大の増加を受け、既に多くのバンド幅ユニットを割り当てられたユーザは、更なるバンド幅ユニットを割り当てられたことによる受ける追加の効用はほんの少量である。多くの効用関数は、例えば、ln(1+x)のように、対数形式であり、その結果、個人がリソースユニットを有さないとき、都合よく効用値ゼロを与える、凹形状の関数になる。
【0055】
以下のトレーディングモデルで用いられる、効用関数の一般的な形式は、
【数3】
であり、ここでAは、ユーザにとってのリソース占有(バンド幅利用)の重要性(すなわち価値)を表すパラメータであり、値Aが高ければ高いほど、重要性が高い。第2項は、資金についての効用を導入し、Mは、ユーザにより保有されている総資金であり、cは、バンド幅当たりのコストである。従って、(M−cx)は、xユニットのバンド幅も保有するユーザの保有資金の量を与える。資金についての効用は、他の任意の製品に対する効用と同じ形式を有する。ほとんど資金を持っていない個人は、既に多くの資金を有する個人が、資金の追加の1ユニットから受けるものよりも、より多くの効用を獲得する。
【0056】
パラメータAは、個人のバンド幅占有の重要性を表し、転送する重要な情報を有するユーザは、より多くのバンド幅を購入することができるであろう。バンド幅占有の価値は、ユーザにより手動で決定することもあり得る。しかしながら、好ましい実施形態では、バンド幅占有の重要性は、情報そのものではなく、残りの送信の長さ、優先度、及び以下に説明するような適時性問題を表すパラメータに基づいている。
【0057】
優先度 − ユーザにとってのリソース占有体(この場合は、情報)の重要度についての目安を与える。これは、例えば、1及び3(ここで、1は日常的情報、及び3は緊急情報)等の、単純な指標として表され得る。一方、多くの優先度スキームは、分布以外の線形間隔ユニット(例えば、対数等を用いてもよい)に基づいている。所与のアプリケーションに対する適切なスケールは、実験的に決定され得る。
【0058】
適時性閾値 − これは、この時間までに、リソース(バンド幅)をリソース占有体(情報)に割り当てすべき、時間についての指標である。情報の適時性は、単純な優先度と混同されるべきではなく、低い優先度の情報が、短い適時性期間を有し、一方高い優先度の情報は、短い時間間隔の中では必要とされない可能性もある。
【0059】
腐敗性閾値 − これは、この後ではリソース占有体(情報)へのリソース(バンド幅)割り当てが、要求しているユーザに対し価値を有さなくなる、時間についての指標である。
【0060】
リソース占有体のサイズ − これは、リソースを未だ割り当てられていないリソース占有体のサイズ(例えば、ビットの観点での情報の長さ)についての指標である。このリソース占有体(情報)のサイズ(ビット)は、適時性閾値に達する前に、このリソース占有体全体に供給するのに割り当てられる充分なリソース(バンド幅)を、要求ユーザが要求することから、重要である。結果的に、適時性閾値に近づいたとき、リソース(バンド幅)が割り当てられるべき、残っているリソース占有体(ビット)のサイズが、まだ比較的大きい場合は、より多くのリソース(バンド幅)が、このリソース占有体(情報)に割り当てられることが重要である。これは、全体としては充分なリソースが、このリソース占有体に割り当てられて、要求されたタスク(通信媒体を介しての情報の転送)が達成されることを確実にする可能性を増進する。
【0061】
パラメータAの形式 − リソース割り当ての重要性は、多少複雑かもしれない。主要なパラメータは、優先度及び適時性閾値であり、この関数の特徴は、現在の時間が適時性閾値未満かどうか、適時性閾値と腐敗性閾値との中間かどうか、又は腐敗性閾値より大きいかどうかに応じて変化する。
【0062】
一般に、及び図2bをここで参照すると、リソース割り当ての重要性は、適時性閾値tjに近づくにつれ増加25し、適時性閾値と腐敗性閾値pjとの間で減少26し、腐敗性閾値の後で理想的にはゼロ27に落ちる。この曲線は、好ましくは適時性閾値までは凸型であり、また、好ましくは適時性閾値と腐敗性閾値との間で凸型であるが、正確な曲率は、特定の応用領域に従って変わる可能性があり、また、再び実験か他の方法により確立され得る。
【0063】
特定の例としては、Aは、通信バンド幅割り当てアプリケーションに対して、
【数4】
で定義されてもよい。
【0064】
ここで、
Pは、優先度
ltは、時間tでも未だ送信されるべきデータの総量
tjは、適時性閾値、pjは腐敗性閾値
tは、現在時間
nは、正の数(パラメータjの関数であってもよい)
である。
【0065】
図2bで概略的に例示されている例では、適時性閾値tjは9に設定され、一方腐敗性閾値Pjは15に設定されている。
【0066】
明らかに、優先度が増加するにつれ、リソース割り当ての重要性Aは増加し、適時性閾値tjに近づくにつれ、リソース割り当ての重要性は増加し、短い残り時間に大量の送信すべきデータltがあると、この重要性は同様に増加する。腐敗性閾値pjは、適時性閾値が過ぎた後に重要になり、時間が腐敗性閾値に近づくにつれ、Aは減少する。
【0067】
パラメータnは、調整を可能にし、この例では、優先度及び適時性が、腐敗性よりも優位を占めて、残りのデータが送信されるように選択される。1から100の範囲の値が調べられた。バンド幅トレーディング実施形態については、60代の数値が、より良い結果をもたらすことが分かった。
【0068】
リソースの適時な割り当ての重要度を計算することにより、ユーザは、彼らのリソース割り当て(この例では、情報転送)に対して重要度を与えることができる。ユーザは、また、彼らが有する残りの資金の量について気づくであろう。このようにして、トレーディングアルゴリズムが、バンド幅の価格を提示する時に、ユーザは、彼らの効用を最適化するであろうバンド幅を要求してもよい。必要とするバンド幅の要求は、式(1)から次のように導かれる。
【数5】
【0069】
ここで、cは、バンド幅の1ユニットのコストである。
【0070】
その後、トレーディングアルゴリズムが、リソース割り当てのための現在の要求の再計算と、リソースに対して過大な要求があるか(ネットワークが現在輻輳している)どうか、又はリソースに対して低要求(ネットワークは輻輳していない)かどうかに基づいて、バンド幅に対する新価格の提示とをするための、トレーディングアルゴリズムを用いることができる。
【0071】
トレーディング方法は、オークション手段により前もって適用することができる。このような解決方法は、スポット(短期)マーケット及び将来(長期)マーケットの両方に対して作用する。ネットワークトレーディングアルゴリズム(NTA)は、将来のタイムスロットに対する1組の価格を計算し、この後、ユーザが彼らの支払い能力と、利用可能なタイムスロットを獲得することで得られるであろう効用とに応じて、各スロットのバンド幅に対して入札する、オークションが開催される。NTAは、要求に応じて各タイムスロットにおける価格に対して調整をかける。プロセスは、均衡するまで繰り返され、この均衡により、バンド幅に対する要求が、利用可能なタイムスロットを超えることは決して無く、また、ユーザは、彼らの資金及び効用に応じてバンド幅を割り当てられたことになる。これには波及効果があるが、理由は、タイムスロットが将来にわたって、自然とより低い要求状態にある可能性があって、結果的により安価になるからである。これは次に、より安いバンド幅を使用することを待つ高い効用を有するユーザにとって、これらを潜在的により魅力的なものにする。
【0072】
さて、図3を参照すると、提案されるトレーディングアプローチは、非トレーディング解決方法を超える能率向上を提供する。トレーディング用いて時間にわたって成功裏に送信されたメッセージの数31は、トレーディング無しで達成されたメッセージの数32を超えている。
【0073】
さて、図4a及び図4bを参照すると、上で述べられた方法の使用することにより、高い割り当て重要度を有するメッセージに、より多くのリソースが比例して割り当てられる傾向にある。従って、例えば、時間325では、わずか小さい割合(およそ10%)の高優先度メッセージ41が、送信を待っているが、比例して多くのより高いバンド幅割り当て42がなされ、利用可能なバンド幅のおよそ60%を構成している。
【0074】
説明された特定の関係は、優先度の観点でのみリソース割り当てを差別化するが、上述したように、他の因子も同様にかかわる。
【0075】
Gibbens及びKellyにより説明された輻輳価格付けメカニズムは、説明されたトレーディングメカニズムと組み合わされて、どれだけのバンド幅が利用可能なのかを正確に知る必要なく、バンド幅を取引する手段を提供することができる。ユーザは、上述のトレーディングメカニズムを、バンド幅を直接購入するよりもむしろ、支払意思額(WtP)の値を買うために用いることができる。前に説明したように、高いWtP値は、ユーザへのバンド幅のより大きな割り当てを可能とするであろうことから、ユーザは、より高いWtP値を得るためにもっと多くお金を使いたいと望むであろう。リソース割り当ての本発明の方法は、またもちろん、他の知られているWtP方法と組み合わせることができる。
【0076】
このようなシステムに対するトレーディングメカニズムは、基本的には上述の通りであるが、利用可能なリソース(バンド幅)が100%であることを仮定している。各ユーザが割り当てられる割り当てバンド幅は、次に、最も高いリソース量を割り当てられるユーザが、例えば、WtP値10を与えられるように規模を設定される。他のユーザは、リソースを比例して割り当てられてもよい。例えば、ユーザAが80ユニットのバンド幅を割り当てられ、Bユーザが20ユニットのバンド幅を割り当てられている場合、ユーザAは、WtP値10を得てもよく、一方ユーザBは、WtP値2.5すなわちAの割り当ての1/4を得るであろう。実際のバンド幅の割り当ては、この後、それぞれの割り当てWtP値に基づいて、知られている方法により処理してもよい。
【0077】
さて、図5aを参照すると、従来のTCP割り当て方法に従うバンド幅割り当てに対する、送信成功率の実例は、別のトラフィックに対するリソース割り当ての相対的な重要性にもかかわらず、障害が、全てのカテゴリのトラフィックに均等に広がったような状況を引き起こす可能性がある。例示されたシナリオでは、各3つの優先度のカテゴリのトラフィックに対する結果が、示されており、低、中、高の優先度のトラフィックに対する、適時(適時性閾値の前)51、未腐敗(腐敗性閾値の前)52、及び不成功53のトラフィックのそれぞれの比率が、優先度にかかわらず広範に均一である。説明を簡単にするために、データが優先度に対してプロットされて示されているが、以上で説明したように他の重要性要素が適用されたということを再度留意されたい。
【0078】
これを、上述の本発明の方法に基づくバンド幅割り当てに関する図5bに例示された結果と比較すると、不成功トラフィック58、及び適時性閾値の後に配信されるトラフィック57は、主として低優先度、従って、黙示的にバンド幅割り当ての重要性が低いトラフィックで起こっているということに留意されたい。適時的な送信についてのより高い重要性を有する情報、従って、一般的にはユーザにとってのより高価値な情報は、優先的に取り扱われる。例示された例では、全ての高優先度のトラフィックは、適時的56aに配信され、一方、低優先度のトラフィックのわずかな部分だけが、適時的56bに配信される。
【0079】
リソース割り当ての適用の更なる例として、及び図6をここで参照するが、ネットワークのユーザ60は、リソース「クラウド」61に対して、ネットワーク周辺のコンピュータ62上のソフトウェアアプリケーションプログラムを用いることにより要求を出して、ウェブサーバ63から情報を得るか、又はファイルサーバ64にファイルを送信する。クラウドは、ルータ66とサーバ63から65のネットワークを含み、一定のバンド幅リソースがあることと、バンド幅を管理するネットワークトレーディングエージェント(NTA)65が存在することが、仮定される。バンド幅管理者は、ルータ及びサーバが、どのように接続されているかについての正確な詳細を、バンド幅に対する要求又はサーバ能力を管理するために知る必要はない。ネットワークは、一定のリソースのクラウドとして扱うことができ、これを妥当な仮定とするのは、基礎となるプロトコル及び管理システムである。この場合は、ネットワークバンド幅は、需要と供給のバランスを取ることにより取引されるリソースと見なされる。サーバの能力は同様に、ネットワーク内の限定的な要因と考えられる場合には、同様な方法で取引されることもあり得る。
【0080】
さて図7を参照すると、各ユーザ60は、NTAサーバ65に接続するためのユーザエージェント62に作用することにより、ネットワークに加わる。ユーザエージェントは、ユーザアカウント詳細71をNTAサーバに渡し、NTAサーバは、特定の情報価値72の詳細及びこの特定のユーザのための資金73の割り当てで応答する。各ユーザに割り当てられた資金は、ユーザが使用することを許可されるネットワークリソースの比率を表し、従って、ある意味では、各ユーザの相対的な重要性を反映する。情報価値は、ユーザについての、情報の相対的重要性、データの相対的適時性及び相対的腐敗性を反映する。ユーザエージェントソフトウェアの存在は、ネットワーク管理システムがこのソフトウェアからの応答を要求することにより検証され、ユーザがこれを無効にしていないことを確実にしてもよい。ユーザエージェントソフトウェアが、特定のユーザについて動作していることが確認できない場合は、好ましくは、ユーザのコンピュータは、ネットワークから締め出され、例えば、再接続のためにネットワーク管理者へのコンタクトを強制される。
【0081】
各ユーザへの資金の割り当ては、各予約マーケットトレーディング期間の初めになされる。この割り当ては、この期間(これは、月、週、日、分、秒、ミリ秒、又はアプリケーションにとって適切な任意の他の時間期間であってもよい)に対する、ユーザ資金として考えることができる。予約マーケットは、この後、次のように動作する。
【0082】
図8をここで参照すると、ユーザ61は、所定の時間間隔の間(これは、例えば、営業日ということもあり得る)に、ユーザが、ファイルサーバ64に転送したい情報、及びユーザが、ウェブサーバ65から欲しい情報を特定する。これは、スケジューラを用いてなされ、いつ情報が転送されるかの柔軟性は、代替時間及び変動耐性を提供することにより示される。例えば、ユーザは、ファイル転送について1時間はいずれにしても問題ないということを指定してもよい。
【0083】
ユーザエージェント62は、次に、タイムスロット化されたリソース要求ベクトル81を計算し、これをNTAに宣言する。NTAは、価格ベクトル82を、ネットワーク内で利用可能なバンド幅、及びユーザとサーバとの間の情報の転送を促進のサーバの負荷等の、関係する全てのリソースに対する総要求を計算することから生成される全ての価格を加算することにより計算する。
【0084】
一旦、ユーザ(又はユーザエージェント)が、タイムスロット当たりのリソースに対する価格を知れば、ユーザは、自分の要求を変更することを選択し、調整されたタイムスロット化リソース要求ベクトル83を提出し、続いてNTAから調整された価格ベクトル84を引き出してもよい。
【0085】
転送される情報(例えば、ユーザからファイルサーバへのファイル転送)については、トレーディングは、ユーザエージェントとNTAとの間で上に示したように実行される。ウェブページを要求するときのウェブサーバへの送信トラフィックを含む、全ての送信トラフィックが、このような方法でおそらく取引されるであろう。
【0086】
受信情報(例えば、ウェブサーバ63からのウェブ情報のダウンロード)については、送信トラフィックについては上述のようにトレーディングが実行されるが、この場合は、ユーザエージェント、ダウンロードのためのデータを格納するサーバ、及びNTAの全てが、取引に関与する。この場合、先行段階が追加され、ユーザは、ウェブサーバにダウンロードされる予定のファイルのサイズの目安87を要求86する。一旦、ユーザがこの情報を知ると、プロセスは上記のように進行する。これは、ファイル転送の間に受信される制御データに対する認容も含む、全ての受信情報に当てはまる。
【0087】
情報の送信及び受信のためのトレーディングは、実際には同時に起こるかもしれない。例えば、リソースベクトルは、送信及び受信に対して同時に計算されて、NTAに一緒に送られることがあり得る。NTAは、この後、送信及び受信価格ベクトルの双方によって同時に応答することができる。送信リソース又は受信リソースのいずれかに対するトレーディングは、他方よりも長くかかるかもしれないので、トレーディング停止の指示が、送信トレーディングを停止85a又は受信トレーディングを停止85b、又は双方を停止するかどうかを指示する必要がある。代替策としては、送信及び受信交渉は、無関係に進行してもよい。
【0088】
予約マーケットに参加しなかったユーザが、いくらかのリソースを得ることができるように、追加のリソースが、スポットマーケットで利用可能にされる。従って、NTAは、利用可能にされたリソースの増加に比例して価格を低減する。スポットマーケットのトレーディングは、各予約マーケットタイムスロットで実行される。例えば、それぞれの1時間が分間隔に分けられ、予約マーケットに参加したユーザらとちょうど今やってきたユーザらが競い合う微細時間トレーディングが行われる。スケジューラは、予約ユーザに対するリソースについての要求を開始し、実際のユーザは、リソースに対する要求をもたらすアプリケーションを開始する。トレーディングは、スポットマーケットに対しても、微細時間に対してではあるが、予約マーケットに対して行ったのと全く同様に機能する。ユーザは、1時間単位のタイムスロット内で例えば毎分ベースにリソースを割り当てられる。リソースに対する価格は、予約マーケットで到達した価格に基づく。予約しているユーザは、ユーザの割り当てを毎分ベースで用いなくともよく、このことは、予約しなかったユーザに対して利用可能なリソースを委ねることになる。また、毎分ベースでは、一部のデータが遅れても、これを用いるアプリケーションに影響を与えることがないかもしれず、従って、予約しなかったユーザに対するデータは、予約したユーザに対するデータとインターリーブされるということもあり得る。
【0089】
情報価値ファイルの別の部分は、予約したユーザによって用いられ、これらユーザの情報に、より高い重要性、従って高い優先度を与える。スポットマーケットユーザが、リソースの一部を取得するのは可能であるが、この優先度方法によればこれは起こりそうも無い。また、予約ユーザは、前もって彼らが必要なリソースに合意していることから、割り当てされたリソースを超えるリソースに対する効用は持つことは有りそうも無い。従って、予約マーケットにリソースを抱え込んでおき、後でこれをスポットマーケットに開放することにより、スポットマーケットユーザは利益をこうむる傾向がある。
【0090】
従って、前もってリソースに対する要求を取引する準備できたユーザは、例えば1時間間隔等の粗いタイムスロットについてスケジュールを生成する予約マーケットに参加する。全てのユーザは、より多くのリソースが、スポットマーケットユーザに便益を与えるための「売り出し」に放出される、スポットマーケットに参加する。取引は、データが、これを必要とするアプリケーションを中断することなく遅延することができる、微細時間内で行われ、予約したがもはや同じ要求は有していないユーザは、微細時間内に、スポットマーケットユーザに対してリソースを開放することができる。微細時間トレーディングを適用することにより、ユーザデータは、動的にリソースの利用を最適化するためにインターリーブされることができ、予約したユーザと待つことや計画することについての準備ができていないユーザとのリソースの共有がなされる。
【0091】
図9aに示されるこのようなシステムの1つでは、予約マーケットの中で時間スロット91は、予約マーケットの送信トラフィックに関するトレーディングの結果として、ユーザに割り当てられてもよい。割り当てバー92の厚さは、各ユーザに割り当てられた帯域幅の量に比例しており、それぞれのタイムスロット内では、同じバンド幅の総量を割り当てしてもよい。この総量は、全体の要求に応じて、実際に利用可能な総量よりも少なくしてもよい。たとえこれらの予約がなされ、価格(バンド幅に対する価格及び/又はサーバ要求に対する価格)は、従って各タイムスロット内のリソースに対して定められたとしても、トレーディングは、それでもなお、これらのリソースが使用される前にスポットマーケットで行われる。
【0092】
今度はスポットトレーディングが、予約期間(この例では各1時間)内に、例えば、1分間のタイムスロットを用いて行われ、図9bは、図9aに示すような予約マーケットの時間1内のスポットトレーディングの効果を例示している。
【0093】
予約マーケットの時間1内では、予約ユーザ1、予約ユーザ3、及び予約ユーザ6が、予約をしている。スポットマーケットの分1内では、これらの各ユーザは、実際に彼らの予約された割り当てを使用する。しかしながら、追加のリソースがスポットマーケットをサポートするために残っていることから、スポットユーザ1は、いくらかのリソースを使用することができる。分2では、ユーザ6は、実際には割り当てを使用せず、そのためスポットユーザ2が、これを落札し使用する。予約ユーザが、彼らの割り当てを使用しないとき、又は具体的にリソースがスポットマーケットのために保有されるときはいつでも、スポットマーケットユーザは、彼らが使用しているアプリケーションの必要範囲内で、できるだけうまく利用可能なリソースを共有する。例えば、スポットユーザ2が、ファイル転送を実行したい場合、これを、予約ユーザにより開放されたリソースとインターリーブしてもよいことから、うまく成功するかもしれない。スポットユーザは、しかしながら、また、互いに自分のアプリケーションで必要な範囲及び情報の相対的価値の範囲でリソースを獲得することを競い合う。従って、スポットユーザは、必要なだけ遅れを我慢して、1分ごとにリソースに対して入札する。
【0094】
スポットマーケットでの交渉により生成されたリソース価格を用いて、ユーザエージェントは、この後NTAに、各スポットマーケット間隔(この例では、1分間のスポットマーケット期間)に対する支払意思額(WtP)値102について支払い101を行う。ユーザエージェントは、この後、スポットマーケットオークションに従った合意された速度で送信する。ネットワーククラウド10は、実際には完全に均一だということはありそうもないため、一部のルータは、例えば、輻輳する可能性がある。これらのルータは、ユーザエージェントに返される、輻輳通知を発行することによりこの状態を示すことができる。ユーザエージェントは、通知を照合し、WtPに逆比例して送信速度を調整する。ネットワーククラウドが、まさに完全に均一なリソースの場合は、予約とスポットマーケットトレーディングのおかげによって、輻輳は起こらないだろうし輻輳通知もないであろう。このような1つの輻輳制御メカニズム(例えば、Gibbens&Kelly輻輳制御モデル基づくような)は、データの送信が始まるときに、スポットマーケットタイムスロット内で働く、微調整メカニズムである。輻輳に至ったクラウド内の全てのリソースは、輻輳通知で応答することができるということに留意されたい。これは、新たなスポットマーケットの割り当てが、新しいWtP値を購入するために用いられ、また送信が、輻輳通知に応答して下方に調整された新たな速度で始まる、次のスポットマーケット間隔まで続く。
【0095】
上記の予約マーケットと、スポットマーケット及び輻輳制御エレメントとの組み合わせは、以下の例により例示される作用を引き起こす。
【0096】
予約マーケットでは、全体の利用可能なリソースの或る割合は、スポットマーケット上のオークションのための最小限の利用可能なリソースを残すために、オークションにはかけられない。
1.新ユーザの登録71。ユーザエージェントは、ユーザの代わりに取引を行うソフトウェアとして配置される。
2.ネットワークトレーディングエージェントNTAは、情報価値ファイル72をエージェントに渡す。
3.NTAは、エージェントに資金及び収入を割り当て73する。
4.リソース予約の準備ができていない場合は、ステップ16に行き、そうでない場合は、情報交換要求がスケジューリングインターフェースを通して生成される。
5.リソースベクトル81が、送信される情報のためにNTAに送られる。
6.NTAは、価格ベクトル82で応答する。
7.リソース要求が、受信情報91のために情報サーバに送られる。
8.サーバは、NTAへのリソースベクトル92を代理で生成する。
9.NTAは、価格ベクトル82でユーザエージェントに応答する。
10.情報価値ファイルを用いて、ユーザは、送信及び受信リソースベクトルを更新する。
11.更新された送信及び受信リソースベクトル83をNTAに送信する。
12.NTAは、送信及び受信価格ベクトル84で応答する。
13.ステップ10を、価格ベクトルが安定するまで、又はユーザが処理を放棄するまで繰り返す。
14.情報を送信及び受信する予定時間になったら16に行く。
15.新ユーザの参加又はリソースの利用可能性が変化したら、NTAが、新たなオークションを開始(ステップ10でリスタート)するか、又は割り当てパラメータをオークション中に修正してもよい。
【0097】
一旦、長期予約オークションが完了したら、短期間のスポットマーケット割り当てを始めてもよい。スポットオークションは、概して予約マーケットオークションに酷似しているが、この場合は、利用可能なリソース全てが、オークションに使用でき、如何なる他の目的のためにも留保される必要はない。
16.新たなまたは修正されたリソースベクトルが、送信される情報のためにNTAに送られる。
17.NTAは、予約マーケットオークションから導かれた価格ベクトルで応答する。
18.新たなまたは修正されたリソース要求が、受信情報のために情報サーバに送られる。
19.サーバが、代理でNTAへのリソースベクトルを生成する。
20.NTAは、ユーザエージェントに予約マーケットオークションから導かれた価格ベクトルで応答する。
21.情報価値ファイルを用いて、ユーザは、送信リソースベクトル及び受信リソースベクトルを更新する。既にリソースを予約したユーザは、予約されていないリソースを要求するユーザよりも優先的に扱われる。
22.更新された送信リソースベクトル及び受信リソースベクトルが、NTAに送られる。
23.NTAは、送信価格ベクトル及び受信価格ベクトルで応答する。
24.価格ベクトルが安定するか、又はユーザが取引を放棄するまで、ステップ21から繰り返す。
【0098】
予約オークション及びスポットオークションが完了したとき、リソース利用に取り掛かる。輻輳価格制御が、作動し任意のリソースの過大割り当てをも修正するのは、この段階である。
25.リソースに対する同意されたオークション価格に従って、ユーザエージェントは、NTAからWtP値を購入し、且つ/又はリソース利用を予約又は優先化するQoSパラメータを購入する。
26.リソースに対する合意されたオークション価格に従って、情報サーバエージェントは、NTAからWtP値を購入し、且つ/又はリソース利用を予約又は優先化するQoSパラメータを購入する。
27.ユーザ及び情報サーバは、適切な輻輳制御方法(例えば、Gibbens&Kellyの輻輳制御方法)を用いて、受信された輻輳料金及び購入されたWtP値に従って速度を調整しながら、情報を転送する。
28.リソースが余りに輻輳状態になり、もはや継続が困難になった場合は、ステップ4にいく。
【0099】
このリソース割り当て方法は、予約マーケットとスポットマーケットの2段階の割り当ての観点で説明されたが、リソースは、単一段階モデル(実際には、スポットマーケットモデルのみだが、アプリケーションにふさわしいように任意の継続期間の時間尺度をもって)を用いて完全に割り当てされるということも有り得るし、同様に、方法が、3つ以上のずっと微細な時間間隔の割り当てレベルを含んでもよいことは明らかである。
【0100】
コンピュータ又は通信ネットワーク内でのリソース割り当ての観点で、上で詳細説明されたが、基礎をなす方法は、明らかに広範囲の分野にずっと広範な用途を有する。これらの多くは、同様にコンピュータ及び通信システムに関連し(しかし決して全てではない)、以下のものを含む(但しこれに限定されず)。
【0101】
・ 輻輳管理 − 料金請求は、輻輳が起こされた事実を数えることにより、ネットワーク利用に対して適用されることができ、輻輳が高ければ、コンピュータは、リソース割り当て方法に基づいて、この輻輳のネットワーク利用を低減させる。このことは、ネットワーク装置障害の発生を低減させることにより、及びリセットの必要性又は利用度の高さに対応するためのネットワーク能力の見直しの必要性を低減させることにより、全体としての費用を節約することになる。
【0102】
・ ディザスタリカバリ − ネットワーク上での過大要求の期間に、突然且つその結果警告無しにネットワークが故障するのではなく、むしろ制御されたやり方で劣化するように、利用を制御してもよい。
【0103】
・ コアサービス保証 − 或る企業に対して高い重要性を有するサービスを、ネットワーク及びシステムリソースの過大利用により他が機能していないときでさえ維持されることができる。コアユーザ及びコアサービスの両方が、過大要求による崩壊から保護されることができ、企業の重要サービスの損失を節減する。
【0104】
・ サービス要求管理 − 例えば、ウェブホスティングサービス等を提供するケーブルネットワークで、サーバを、サーバの崩壊につながる要求のピークから保護することができる。サーバ時間は、割り当てられたリソースである。この状況では、サーバは、ネットワークが必要以上のかなり多くのバンド幅を提供することができるような、過大要求から保護する必要のあるリソースである。サービスの停止時間とサービスの回復のためのコストとが避けられる。
【0105】
・ アプリケーション層の速度適応及び入場制御 − 本発明のリソーストレーディング解決方法は、コンピュータアプリケーションソフトウェアと密接に連動するように設計されており、また、そうすることにより、ネットワークが要求によって遅くなるが、アプリケーションソフトウェアがネットワークを使おうと試し続けてしまう、頻繁に起こる問題に対処する。これは、サービス及びコンピュータのハングアップにつながり、また、不正のためにアプリケーションを再インストール又はコンピュータソフトウェアを再構築する必要につながる可能性がある。本発明の方法をリソースの割り当てに用いることにより、アプリケーションソフトウェアデータの喪失も、回避されるかもしれない。
【0106】
・ リソース割り当て及びサーバ共有 − サーバに対するユーザの要求は、要求を共有することで管理されることができる。上述のトレーディングメカニズムは、サーバが顧客又は企業にサービスを提供するのにどれだけ忙しいかを考慮に入れて、要求を割り当てすることを可能とする。
【0107】
・ スペクトル管理 − 無線スペクトルは、動的に共有されることができる、貴重で限られたリソースである。割り当ては、トレーディングメカニズムを用いて制御されることができる。こうすることにより、アプリケーション、ネットワークオペレータ、又はエンドユーザ(例えば、携帯電話ユーザ)にサービスを提供する上で利用可能なスペクトルの最適な利用がなされ得る。
【0108】
・ 情報管理 − 価値を情報のアイテムに関連付ける単純な方法が適用される。上述の割り当て方法の適用は、高いネットワーク要求の期間に、情報の価値に従って情報を優先付けすることにつながる。これは、事業的に重要な情報又は高収益を生む情報は、ネットワークが輻輳しているときに転送され、重要でない情報は遅れさせられるということを確実にする。
【0109】
・ ユーザ要求管理 − ちょうど情報が、高ネットワーク要求の期間に優先付けされてもよいように、特定のユーザが優先されてもよい。この技術は、事業にとってのユーザの重要度と、事業(又はユーザ)にとっての情報の価値のバランスをとることを可能にし、従って、どれだけ多くのリソースを割り当てするかを判断することを可能にする。
【0110】
・ エンドツーエンドサービス管理 − 本発明の方法を用いるリソーストレーディングメカニズムを適用するためには、解決方法がサービス及びユーザに基づき、ネットワーククラウドにわたってエンドツーエンドで動作することから、ネットワークがどのように作用するのかについての内部的な詳細を理解又は知る必要が無い。従って、これは、これらリソースがどのように提供されるのかにかかわりなく、共有されるバンド幅とサービスシステムを提供するネットワーク全域にわたって、ユーザに合意されたサービス品質を提供する手段を提供することを支援する。
【0111】
・ 動的バンド幅割り当て − バンド幅は、オンザフライで、低減された構成コストで、且つ専門家の介入の必要なく、割り当て及び管理されることができる。
【0112】
・ 動的サービス料金請求 − サービス、情報、及びバンド幅利用は、利用にしたがって料金請求することができる。コスト及びトラフィックは、サービス、情報、及びバンド幅に対する要求に基づく料金に加えて含まれることができる。
【0113】
・ 衛星リンクのチャンネル管理 − リソーストレーディングメカニズムは、実際の資金を請求することにより、又はユーザとサービスとの間の共有チャンネルを含む利用可能なチャンネルの最良の利用を図る方法としてのいずれかによって、衛星リンクのチャンネル取引に適用されることができる。
【0114】
・ サービスコスト及び輻輳に敏感な、バンド幅の予備割り当て − 企業にとってのコストを節約するため、この解決方法は、別のサービスプロバイダにより提供される代替リンクを利用する企業への実際のコストの総額を考慮に入れて、用いられることができる。例えば、主インターネットリンクが輻輳になり、且つ限定された能力の代替リンクがある場合、予備として代替リンクを用いるコストが考慮され、その結果、この利用は主リンクの輻輳が軽減する時までに制限されることができる。
【0115】
・ バンド幅が限定された環境での利用効率の向上 − 無線リンクが通信を実現する主要な方法(例えば、ワイヤレスLAN)であるネットワークにおいて、リソーストレーディングは、限られた利用可能バンド幅の最適な利用を促進する。
【0116】
・ 企業プロセスに対する情報の重要性に従った、情報フローの最適化 − 転送される情報は、企業のニーズに従って動的に制御されることができ、より収益性の低いサービスについての、企業イントラネットによりサポートされるより重要性の低い企業関連するアクティビティは、企業の中核的なニーズを支配することにはならない。間接費を節約する、利益又は事業効率は、このようにして最大化され得る。
【0117】
・ 性能指標及びリソース利用及び能力計画のためのユーザ要求計算 − メカニズムが機能する方法に基本的に備わっているのは、ネットワークの使用されかたを追跡し、より多くのネットワークリソースを提供する必要性を評価するために用いることができる、性能指標である。
【0118】
・ 更新の必要性を遅らせる、レガシーネットワークにおけるトラフィック管理 − 基礎をなすネットワークとの直接的な対話の必要がないので、例えばリピータハブ等に基づくレガシーネットワークは、トレーディング解決方法が無い場合には全くサービス品質を提供する能力が無くとも、これを提供するように管理されることができる。レガシーネットワークを更新するコストは、メカニズムにより提供される指標が、必要な能力を提供するためにはそうすることが望ましいということを指し示すまで、延期され得る。停止時間のコストは、更新プログラムを計画している間、低減されることもできる。
【0119】
・ 3G及び他の無線通信システムにおける料金請求及びサービス管理 − 限られたバンド幅及びサービスリソースを最大限に活用する方法を提供するとともに、トレーディングメカニズムは、サービスに対してユーザに料金請求する直接的な方法をサポートし、これをすることにより、ユーザの行動は、彼らが支払う用意のあるサービスのレベルに従って変更され得る。
【0120】
・ 企業イントラネットへのインターネットサービスプロバイダ(ISP)リンクのような、有料サービスの利用管理 − 例えば、大学の資金の節約は、これらが自分達の内部リンク及びISPにより提供される外部リンク上で使用する、バンド幅を動的に管理することにより可能である。インターネット利用に対しISPがパケット当たりで料金請求する場合には、このメカニズムは、課された料金を管理する方法を提供する。同じ解決方法が、インターネットへのISPリンクを用いる企業イントラネットへも適用される。
【0121】
・ 予約されたが使用されず、おそらく無駄にされたであろうバンド幅の利用 − トレーディングメカニズムの1つの特徴は、全てのバンド幅は、管理された仕方で利用可能にされ、予約された能力の全てが使用された時点で、任意の使い残しのバンド幅の断片が、アドホックベースで用いられることができるようにするというものである。
【0122】
・ ポイントツーポイントトランクの最適化 − 多数のネットワークが、比較的低いバンド幅のリンクで相互接続されている場合、この解決方法は、リンク間の飽和及び犠牲の大きい故障時間を回避するため、ネットワーク間トラフィックを管理するために用いられることができる。
【0123】
・ ルートをベースとした情報フロー管理 − 情報は、ネットワークを横切って取るルートに従って管理されることができ、メカニズムは、ルートベースのトラフィック管理を提供するように適合され得る。
【0124】
・ 複数のネットワークの複合ネットワークにおける、エンドツーエンド情報フロー管理 − 複数のネットワークのネットワーク内では、リソーストレーディングは、ネットワークのそれぞれの部分内における要求を考慮に入れ、この後、複合ネットワーク全体にわたる情報フローを管理するように拡張することができる。
【0125】
・ 信頼できる分散型動的システムのセキュリティ − 全てのユーザが、NTAに登録しなければならず、また、資金を払ってネットワークリソースを利用することから、リソースへのアクセスは制御され且つ記録される。アクセスのセキュリティは、トレーディングメカニズムの帰結である。
【0126】
リソースが、比較的短い及び/又は長い時間スケールにわたって管理される必要がある他のアプリケーションは、同様に、上述の方法を適用する候補である。このような領域は、限定するものではないが、以下を含む。
・ 旅行、休日、及び催しものの会場予約システム(例えば、列車、航空機のシート、ホテルの部屋、劇場の席等への人の割り当て)
・ 道路混雑管理(例えば、道路の料金レベルの設定)
・ ユーザ要求に従う電話料金請求
・ ユーザ要求に従うオンデマンドのビデオシステム
・ 緊急性及び要求によるヘルスケア患者管理(例えば、医院や病院内の)
・ ユーティリティ供給及び/又は価格付け(例えば、デマンドドリブンの、ガス、水、電気等の供給及び/又は価格付け)管理
・ 株式分配システム
・ コールセンタ管理システム
【0127】
リソースが制約され、且つユーザ又は顧客にサービス又は製品を届けるために設計された他のシステムが、この解決方法により管理されることもあり得る。この解決方法は、従って、サービス、製品、又は施設を、多数のユーザ又は顧客又は他のリソース占有体/消費体に提供する需要がある、制約されたリソースを有する任意のシステムの管理に適用可能である。
【0128】
図11を参照すると、トレーディングシステムは、階層的及びピアツーピアトレーディング、並びにユーザ及びトレーダの地理的分散に基づくトレーディングの両方を含んでもよい。この事例では、リソース割り当て者の(従ってトレーダの)連続的なトレーディングレベル200から203が例示されている。スーパートレーダ200(例えば、国の無線スペクトル規制当局)は、多数の地域トレーダ201にリソースを割り当てしてもよく、次に地域トレーダ201は、彼らの割り当てられたリソースを区域トレーダ202にサブ割り当てする。各レベルにおけるリソース要求は、任意の所与の時間においてリソースに対して各トレーダが支払いを厭わない価格に影響を与える。
【0129】
ある場合には、同じレベルのトレーダ202a、202bは、ピアツーピアトレーディングと呼ばれる取引を彼らの間で行ってもよい。これは、現時点では又は当面は、トレーダ自身のユーザ共同体から必要とされないリソースを割り当てられたトレーダが、以前割り当てられたリソースを越えた要求を持つピアトレーダに、このリソースを再販売(状況に応じて臨時的に)することを可能にする。このようなトレーダの階層的及びピアツーピアネットワークの中で、リソース取引は、応用例とともに以下の表の中に要約された少なくとも次の方法で適用されることができる。
【0130】
これに関連して、本発明者らは、上述のようなリソーストレーディングアルゴリズムは、これを動作させることにより、しかしユーザに実際にリソースを割り当てすること無しに、リソースに対する価格を決定するために適用することができるということを観察した。このようにして、この方法は、階層的に上位の(又は同格又は他の任意の)リソース割り当て者からの自分のリソース割り当てに対して入札する時に、トレーダが用い得る入札価格を決めるために用いられることができる。これは、リソーストレーディング規模を拡大縮小することができ、且つ、以下でより詳細に説明される、さまざまなやり方の全範囲を利用可能にする。応用の領域の例は、次の表の中に示されている。
【表1】
【0131】
これらの各ケースの中で、リソーストレーディングアルゴリズムは、ローカルトレーダと取引する中央トレーダに実装することができ、又はトレーダ間の取引により実行されるということもあり得る。これらのインプリメンテーションは、リソース割り当ての取引に、及び要求に応じたリソースの取引に、必要に応じ組み合わせることができる。従って、階層的なトレーディングは、ピアツーピアトレーディング等と組み合わせることができる。
【0132】
割り当てられたリソース内でのローカルトレーディングは、詳細に説明されたように、基本的なリソーストレーディングアルゴリズムを利用する。これは、ネットワークバンド幅のような単一リソース内のデマンドを管理するためにアルゴリズムを適用する、最も基本的な方法である。
【0133】
代替リソースにわたるトレーディングは、アルゴリズムの利用を拡張する追加の1ステップを含み、ここでは、ユーザが参加及び利用できるかもしれない1より多くのリソースが存在する。例えば、ユーザが参加することを選択することができるかもしれない複数の代替ネットワークが存在するかもしれない。これは、アルゴリズムが用いられる方法の、単純な拡張である。ユーザがリソースを使用したい場合、次にユーザは、トレーダから利用可能な各代替リソースについての現在のリソース価格を要求する。トレーダは次に、各リソースに関連する現在価格で応答し、ユーザは次に、最も低い現在価格を有するリソースに対するオークションに参加する。トレーディングアルゴリズムはその後、通常のやり方で動作する。
【0134】
所与の価格でリソース又は複数のリソースの販売を申し入れている1より多くのトレーダが存在する可能性がある。その結果として、ユーザは、単一のトレーダから提供される利用可能なリソース全体はもちろんのこと、トレーダ間で最も高価ではないリソースの供給源を選択することを選ぶことができる。
【0135】
ユーザはまた、例えば、価格暴騰のため、彼らのメッセージが継続的に腐敗しているということが分かった場合は、オークションから退去することを選択することができる。退去するユーザは、より良いサービスを得るために、代替策としてより安いオークションに移動してもよい。
【0136】
サービスに対するパスを確立するための、多数のリソースにわたるピアツーピアトレーディングとの関連で、アルゴリズムは、エンドツーエンドパスに沿ってのリソースの入札に適用することができる。例えば、ユーザが、ユーザのローカルネットワーク外のリモートサーバへのアクセスを必要とする場合、ユーザは、リモートサーバに至る途中の全てのネットワークからのバンド幅に加え、ローカルネットワークからのバンド幅が必要である。これは、ネットワークが、バンド幅を必要とする通過トラフィック(すなわち、自分のローカルユーザが発信元でも宛て先でもないトラフィック)に対応する必要があるということを意味する。各ネットワークは、この後、通過バンド幅についての要求に対する価格を決定するためにアルゴリズムを適用し、(随意的に)トラフィックはローカルに所有されているものではないとして関税を適用する。従って、複数のネットワークにわたってバンド幅を購入するために入札するユーザは、自分のローカルネットワーク内のローカルバンド幅に対して支払わなければならないだろうし、同様に関連する他のネットワーク全てにわたるバンド幅に対する料金を追加しなければならないであろう。
【0137】
従って、アルゴリズムは、次のように変更してもよい。ユーザは、自分のローカルトレーダと取引して、ローカルリソースに対する見積もりを得るであろう。ユーザは、また、ピアツーピアパスに沿って必要な、他の全てのリソースに対する見積もりも得る必要があるだろう。各リモートトレーダは、このユーザの要求を「所有」していないことから、彼らが見積もる価格に関税係数が適用されてもよい。ユーザは、この後、全ての見積もりを加えることにより、アルゴリズムを適用し、どれだけの量のリソースに入札するかを決定するであろう。よって、トレーディングアルゴリズムの中でユーザにより用いられるリソースに関する総価格Pは、以下のようにとなるであろう。
【数6】
【0138】
ここで、P0は、ローカルリソースに対して見積もられた価格、Tiは、通過デマンドに対してリソースiにより適用される関税、Pnは、リソースiにより見積もられた価格である。ユーザのトレーダは、提供されるパスに沿っての全てのトレーダとユーザに直接交渉させるよりはむしろ、ユーザに代わってこの価格を組み立て得る。
【0139】
ユーザにより要求されるリソースがバンド幅であり、リソースの一部は、例えばサーバ能力ということもあり得る。従って、リソーストレーディングアルゴリズムを使って、ユーザにサービスを提供する中で関係する全てのリソースは、このような方法で、ピアツーピア、トレーダツートレーダ、エンドツーエンドで取引されることができる。
【0140】
リソースの単一割り当てに対するピアツーピアトレーディングでは、トレーダは、自分を取り巻く一部の又は全てのトレーダとリソースに対する取引を行うことにより、リソースの割り当てのために取引をする。このようにして、トレーダは、区域ごとにリソースを割り当てられてもよい。これは、次のように実現されてもよい。
【0141】
割り当てに利用可能なリソースは、サイズによって、従ってトレーダにとっての価値によって順序付けられる。これらのリソースは、他のトレーダがオークションの結果としてこれらを主張する場合、ローカルテーブルの中では利用不可とマークをつけられる。第1のリソースが利用可能だとすると、トレーダは、リソースのサイズを測り、これを自分のユーザにリソース割り当てすることなしに、アルゴリズムを動作させるために用い、そうすることによりこのリソースに対する価格を決定する。トレーダは次に、この価格を用いて周囲の全てのトレーダと競り合う。トレーダが、最高値を付けた場合、このリソースを要求してこれを自分のユーザ間で取引し始める。そうでなければ、トレーダは、自分のローカルテーブルの中ではこのリソースを利用不可とマークをつけ、リストの中の次のリソースに対して処理を繰り返す。これは、トレーダがオークションに勝つまで、又は入札するための未割り当てのリソースが無いということが分かるまで、繰り返される。後者の場合、トレーダは、今後の入札ラウンドを待たなければならない。
【0142】
各トレーダに割り当てられた資金の相対的な量(これは、次に自分のユーザ間で共有される)は、価格入札に影響を与えることから、各トレーダがリソースに対する入札にどれだけ成功するかを決定する。このことは、このプロセスを制御して、リソースが要求に応じてトレーダに割り当てされることを確実にするために用いられることができる。例えば、リソース割り当てを勝ち取れなかったこれらのトレーダに、補償金を支払い、今後の入札ラウンドで、彼らが割り当てを勝ち取る可能性を高くしてもよい。各トレーダに割り当てられる資金の量は、リソースに入札するライセンスに対してトレーダがどれだけ実際の資金を支払ったかに関連してもよい。
【0143】
他の周囲トレーダは、リスト内の任意のリソースに対して入札するために、いつでもトレーダにオークションを呼びかけることができる。トレーダは、使用するリソースをまだ主張していない場合は、他のトレーダに競争入札することにより応答する。
【0144】
リソースの複数の割り当てに対するピアツーピアトレーディングでは、トレーダは、1より多くのリソースに対して入札することができる。再度、利用可能なリソースは、ローカルテーブルの中で順序付けられることができ(例えば、サイズにより)、リソースのサイズに従って、リソースの価格を判断するためのアルゴリズムを用いて、トレーダは最初の利用可能なリソースに対して入札する。オークションに負けた全てのトレーダは、彼らのローカルテーブルにリソースは利用不可とマークする。トレーダが、入札に勝つことによりリソースを主張した時点で、このトレーダは、同じような方法で更なるリソースに対して入札を続けてもよい。しかしながら、追加の入札では、トレーダは、自分の価格を決めるときに、入札するリソースのサイズに以前に競り落としたリソース全てを加える。従って、入札価格は、トレーダがますますリソースを勝ち取るにつれ低下する。このことは、リソースに対するトレーダの要求が満足されるにつれ、他のトレーダと競り合う時に更なるリソースを勝ち取ろうとはあまり判断しないだろう、ということを意味する。このようにして、一部のトレーダは、取引するためのリソースを1つ勝ち取ってもよいし、一部のトレーダは、多く勝ち取ってもよい。一部のトレーダは、全く勝ち取れないということも有り得、今後の入札ラウンドを待たねばならないということになるであろう。
【0145】
前と同様に、各トレーダに割り当てられた資金の相対的な量は、価格入札に影響を与えることから、各トレーダがリソースに対する入札にどれだけ成功するかを決定する。このことは、このプロセスを制御して、リソースが要求に応じてトレーダに、特に、以前の入札ラウンドで完全に負けたこれらのトレーダに割り当てされることを確実にするために用いることができる。各トレーダに割り当てられる資金の量は、同様に、リソースに入札するライセンスに対してトレーダがどれだけ実際の資金を支払ったかに関連してもよい。
【0146】
任意の他の周囲トレーダは、いつでも任意の利用可能なリソースに対してオークションを働きかけることができる。先に述べたように、リソースの利用可能性は、テーブルの中に表示され、各オークションの後、入札に敗れた全てのトレーダは、リソース入札は利用不可であるとそれぞれのローカルテーブルにマークする。
【0147】
共有されるリソースの割り当てに対する階層的なトレーディングの中では、リソーストレーディングアルゴリズムが、前に説明したようにリソース価格を決定する。これは、他のトレーダと共有されるリソースの一部の割り当てについて決定するために用いられることができる。例えば、同じキャンパスネットワークLANを共有する2の部門があり、それによって、各部門は自分のユーザに異なる量の資金が割り当てられており、異なるユーザニーズを有し、従って異なるリソース要求を有するということがあり得る。各部門は、従って、利用可能なバンド幅の或る割合を共有しており、この割り当て分を自分のユーザの中で共有しているかもしれない。それで、バンド幅の1/3が、部門Aに自分のユーザ全体で取引するために割り当てられることがあり得る。残りのバンド幅は、この後、部門Bの中で取引されるであろう。
【0148】
リソースのシェアは、次のように割り当てしてもよい。各トレーダは、全てのリソースが利用可能であれば、アルゴリズムに利用可能なリソースの全てを割り当て、自分のユーザ間でリソースについて或る価格に達するために取引する。この価格は、このトレーダの市場内のリソースに対する要求を反映する。この段階ではこれらのユーザは、アルゴリズムが、リソースの販売無しに価格のみを決定するために用いられるため、リソースを買うことはできないであろう。各トレーダに割り当てられるリソースは、この後、これらの価格により分けられる。従って、2人のトレーダaとbがおり、Paがトレーダaについて決定されたリソース価格、及びPbがbについて決定されたリソース価格、そしてRaで示されるaに対するリソース割り当ては、
【数7】
によって規定されてもよく、ここで、Rtは総リソースである。
【0149】
一旦リソースのシェアが割り当てされると、リソース取引が、通常のように、割り当てられたリソースに対するシェアを使って、各トレーディングドメイン内のユーザに対して開催される。
【0150】
ピアツーピアについては、各トレーダに割り当てられた資金の相対的な量は、価格入札に影響を与えることから、各トレーダがリソースのシェアに対する入札にどれだけ成功するかを決定し、またこのことは、このプロセスを制御して、リソースが要求に応じてトレーダに割り当てされることを確実にするために用いられることができる。各トレーダに割り当てられる資金の量は、リソースに入札するライセンスに対してトレーダがどれだけ実際の資金を支払ったかに関連するかもしれない。
【0151】
単一のリソースの割り当てについての複数のリソースにわたる階層的なトレーディングでは、異なるサイズの複数のリソースが、トレーダに割り当てするために利用可能である。リソースは、サイズに従って順序付けられ、最も大きなリソースが最も価値があり、最も小さいものが最も価値がないと判断される。全てのトレーダは、それぞれのリソースに対して入札し、最大のリソースから始まって最小のものに向かって進む。最初のリソースに入札する際、各トレーダは、リソースのサイズ(すなわち、バンド幅の量)を用いてアルゴリズムを動作させ、自分が自分のユーザに対して販売するかもしれないリソースの価格を決定する。この価格は、前に述べたように、トレーダのドメイン内のリソースに対する要求を表す。この価格は、この後、リソースを要求するための入札として単に用いられる。最高値で入札した、従って入札に勝つ必要性のきわめて高いトレーダは、リソースを割り当てられる。勝利者は、この後、このリソースを、アルゴリズムを用いて自分のユーザ間で取引するために用いることができ、このオークションプロセスを抜ける。次の利用可能なリソースが、この後、残っているトレーダにわたって同じようにオークションにかけられる。このプロセスは、トレーダに取引するための全ての利用可能なリソースが割り当てされるか、又は、全てのトレーダが取引するために必要なリソースを有するまで続く。リソース割り当てを勝ち取れなかったトレーダは、次の入札ラウンドまで待たなければならない。
【0152】
前と同様に、各トレーダに割り当てられる資金の相対的な量は、価格入札に影響を与えることから、各トレーダがリソースに対する入札にどれだけ成功するかを決定し、このことは、このプロセスを制御して、リソースが要求に応じてトレーダに割り当てられ、リソースを勝ち取れなかったトレーダに補償するために用いることができる。各トレーダに割り当てられる資金の量は、リソースに入札するライセンスに対してトレーダがどれだけ実際の資金を支払ったかに関連するかもしれない。
【0153】
複数のリソースの割り当てに対する複数のリソースにわたる階層的なトレーディングにおける目的は、各トレーダが、リソースのこの1つの割り当て以上に要求することができるように、トレーダにリソースを割り当てし、そしてこの後、1より多くのリソーストレーディングアルゴリズムを動作させて、これらの複数の割り当てを自分のユーザわたって共有することである。これは、前に述べたように、割り当てされるべきリソースを順序付けすることによりなされる。上述のように、トレーダは、各トレーダが入札するであろうリソースに対する価格を決定するためにアルゴリズムを用いて、最初のリソースに対して入札する。リソースはこの後、最も高い入札者に割り当てられる。最高値入札者は、この後、次の順番のリソースに対する入札に参加することにより、更なるリソースの割り当てに対する入札を続ける。しかしながら、今回は、最初の割り当てを勝ち取った入札者は、今オークションされているリソースのサイズに、前に勝ち取ったリソースのサイズを加えることによってアルゴリズムを使用して、リソースに対する自分の価格を決定する。これは、トレーダが、既にリソース割り当てされているので、追加のリソースに対するトレーダの要求はより少なそうであり、従って価格入札はおそらくより低そうだということを意味する。従って、アルゴリズムを用い且つすでに勝ち取ったリソースを入札されるリソースに加えることにより、既にリソースを有するトレーダに対して入札価格が決定される。最高値で入札したトレーダが、この後、このオークションのリソースを割り当てられるが、このトレーダは、既にリソースを有するトレーダであってもよいし、そうでなくてもよい。全てのトレーダがこの後、次の順番のオークションに参加し、プロセスは、全てのリソースが割り当てされるまで続く。一部のトレーダは、取引するための1つのリソースを勝ち取ってもよいし、一部のトレーダが多くを勝ち取り、一部は全く勝ち取らなくてもよい。
【0154】
前と同様に、或るトレーダの入札の成功は、他のトレーダと比較して、どれだけ多くの資金が割り当てられたかによって決まる。
【0155】
本明細書中で与えられた範囲又は機器の値は、本明細書中で教示されたものを理解する当業者には明らかなように、求められる効果を失うことなく拡張又は変更してもよい。
【図面の簡単な説明】
【0156】
【図1】本発明による第1の通信システムの概略図を示す。
【図2a】本発明による効用関数の概略グラフを示す。
【図2b】本発明による割り当て関数の重要度の概略グラフを示す。
【図3】本発明によるリソース割り当てと従来技術の割り当てとを比較する概略グラフを示す。
【図4a】どのように異なる優先度のトラフィックの相対的比率が、時間と共に変化する可能性があるかを示す概略グラフである。
【図4b】本発明により、どのようにバンド幅をこれに対応して割り当てしてもよいかを示す概略グラフである。
【図5a】従来技術によるバンド幅割り当ての概略グラフを示す。
【図5b】本発明によるバンド幅割り当ての概略グラフを示す。
【図6】本発明による第2の通信システムの概略図を示す。
【図7】本発明による第1の方法の概略図を示す。
【図8】本発明による第2の方法の概略図を示す。
【図9a】本発明によるリソース割り当ての第1の例を示す。
【図9b】本発明によるリソース割り当ての第2の例を示す。
【図10】本発明による更なる方法を示す。
【図11】本発明によるやはり更なるシステムを示す。
【特許請求の範囲】
【請求項1】
リソースに複数のリソース占有体を割り当てする自動化された方法であって、
各リソース占有体に適時性閾値を関連付けすることと、
各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算することと、
割り当てのそれぞれの緊急性の指標に応答してリソースを割り当てすることとを含む方法。
【請求項2】
各リソース占有体に腐敗性閾値を関連付けすることと、
適時性閾値、腐敗性閾値、及びリソース占有体のサイズの指標に応答して、割り当ての緊急性の指標を計算することとを含む、請求項1に記載の方法。
【請求項3】
腐敗性閾値が過去に位置するリソース占有体にはリソースを割り当てしない、請求項2に記載の方法。
【請求項4】
割り当ての緊急性は、適時性閾値までは増加凸関数である、請求項1から3のいずれか一項に記載の方法。
【請求項5】
割り当ての緊急性は、適時性閾値と腐敗性閾値との間は減少凸関数である、請求項1から4のいずれか一項に記載の方法。
【請求項6】
割り当ての緊急性は、腐敗性閾値の後ではゼロである、請求項1から5のいずれか一項に記載の方法。
【請求項7】
緊急性指標Aは、
【数1】
のように計算され、ここで、
Pは、優先度
ltは、要求されるリソースの量
tjは、適時性閾値
pjは、腐敗性閾値
tは、現在時間
である、請求項1から6のいずれか一項に記載の方法。
【請求項8】
リソースは、送信バンド幅を含む、請求項1から7のいずれか一項に記載の方法。
【請求項9】
リソースは、無線スペクトルバンド幅を含む、請求項1から8のいずれか一項に記載の方法。
【請求項10】
リソースは、人々によって占有されるためのエンティティを含んでもよく、またリソース占有体は人々を含む、請求項1から7のいずれか一項に記載の方法。
【請求項11】
リソース占有体は、乗り物を含む、請求項1から7のいずれか一項に記載の方法。
【請求項12】
リソースは、支払意思額の値を含む、請求項1から11のいずれか一項に記載の方法。
【請求項13】
リソースを複数のリソース占有体に割り当てするためのシステムであって、
各リソース占有体に適時性閾値を関連付けする手段と、
各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算する手段と、
割り当てのそれぞれの緊急性の指標に応答してリソースを割り当てする手段とを含むシステム。
【請求項14】
リソースを複数のリソース占有体に割り当てするためのコンピュータのためのプログラムであって、
各リソース占有体に適時性閾値を関連付け、
各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算し、
割り当てのそれぞれ緊急性の指標に応答してリソースを割り当てするように構成されたコード部分を含むプログラム。
【請求項15】
第1の見込みスペクトルユーザ群の間で無線スペクトルを割り当てするための自動化された方法であって、
第1の群のメンバ間で第1の自動化オークションを実行するステップを含み、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催される第2の自動化オークションに応答して決定され、前記方法がさらに、
第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てするステップを含む方法。
【請求項16】
第1のオークション及び第2のオークションは、リアルタイムで実行される、請求項15に記載の方法。
【請求項17】
リソースは、請求項1から12のいずれか一項に記載の方法に従って、第2の群のメンバに割り当てされる、請求項15または16に記載の方法。
【請求項18】
第1の見込みスペクトルユーザの群の間で無線スペクトルを割り当てするための自動化システムであって、
第1の群のメンバ間で第1の自動化オークションを実行する手段を含み、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催される第2の自動化オークションに応答して決定され、前記システムがさらに、
第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てする手段を含むシステム。
【請求項19】
第1の見込みスペクトルユーザの群の間で無線スペクトルを割り当てするためのコンピュータのためのプログラムであって、
第1の群のメンバ間で第1の自動化オークションを実行するように構成されたコード部分を含み、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催される第2の自動化オークションに応答して決定され、前記プログラムがさらに、
第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てするように構成されたコード部分を含むプログラム。
【請求項1】
リソースに複数のリソース占有体を割り当てする自動化された方法であって、
各リソース占有体に適時性閾値を関連付けすることと、
各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算することと、
割り当てのそれぞれの緊急性の指標に応答してリソースを割り当てすることとを含む方法。
【請求項2】
各リソース占有体に腐敗性閾値を関連付けすることと、
適時性閾値、腐敗性閾値、及びリソース占有体のサイズの指標に応答して、割り当ての緊急性の指標を計算することとを含む、請求項1に記載の方法。
【請求項3】
腐敗性閾値が過去に位置するリソース占有体にはリソースを割り当てしない、請求項2に記載の方法。
【請求項4】
割り当ての緊急性は、適時性閾値までは増加凸関数である、請求項1から3のいずれか一項に記載の方法。
【請求項5】
割り当ての緊急性は、適時性閾値と腐敗性閾値との間は減少凸関数である、請求項1から4のいずれか一項に記載の方法。
【請求項6】
割り当ての緊急性は、腐敗性閾値の後ではゼロである、請求項1から5のいずれか一項に記載の方法。
【請求項7】
緊急性指標Aは、
【数1】
のように計算され、ここで、
Pは、優先度
ltは、要求されるリソースの量
tjは、適時性閾値
pjは、腐敗性閾値
tは、現在時間
である、請求項1から6のいずれか一項に記載の方法。
【請求項8】
リソースは、送信バンド幅を含む、請求項1から7のいずれか一項に記載の方法。
【請求項9】
リソースは、無線スペクトルバンド幅を含む、請求項1から8のいずれか一項に記載の方法。
【請求項10】
リソースは、人々によって占有されるためのエンティティを含んでもよく、またリソース占有体は人々を含む、請求項1から7のいずれか一項に記載の方法。
【請求項11】
リソース占有体は、乗り物を含む、請求項1から7のいずれか一項に記載の方法。
【請求項12】
リソースは、支払意思額の値を含む、請求項1から11のいずれか一項に記載の方法。
【請求項13】
リソースを複数のリソース占有体に割り当てするためのシステムであって、
各リソース占有体に適時性閾値を関連付けする手段と、
各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算する手段と、
割り当てのそれぞれの緊急性の指標に応答してリソースを割り当てする手段とを含むシステム。
【請求項14】
リソースを複数のリソース占有体に割り当てするためのコンピュータのためのプログラムであって、
各リソース占有体に適時性閾値を関連付け、
各リソース占有体に対して、適時性閾値とリソース占有体のサイズについての指標とに応答して割り当ての緊急性の指標を計算し、
割り当てのそれぞれ緊急性の指標に応答してリソースを割り当てするように構成されたコード部分を含むプログラム。
【請求項15】
第1の見込みスペクトルユーザ群の間で無線スペクトルを割り当てするための自動化された方法であって、
第1の群のメンバ間で第1の自動化オークションを実行するステップを含み、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催される第2の自動化オークションに応答して決定され、前記方法がさらに、
第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てするステップを含む方法。
【請求項16】
第1のオークション及び第2のオークションは、リアルタイムで実行される、請求項15に記載の方法。
【請求項17】
リソースは、請求項1から12のいずれか一項に記載の方法に従って、第2の群のメンバに割り当てされる、請求項15または16に記載の方法。
【請求項18】
第1の見込みスペクトルユーザの群の間で無線スペクトルを割り当てするための自動化システムであって、
第1の群のメンバ間で第1の自動化オークションを実行する手段を含み、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催される第2の自動化オークションに応答して決定され、前記システムがさらに、
第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てする手段を含むシステム。
【請求項19】
第1の見込みスペクトルユーザの群の間で無線スペクトルを割り当てするためのコンピュータのためのプログラムであって、
第1の群のメンバ間で第1の自動化オークションを実行するように構成されたコード部分を含み、第1の群の第1のメンバにより提供される入札価格は、第1の群の第1のメンバに関連する第2の見込みスペクトルユーザの群のメンバ間で開催される第2の自動化オークションに応答して決定され、前記プログラムがさらに、
第1の自動化オークションに応答して第1の群のメンバにスペクトルを割り当てするように構成されたコード部分を含むプログラム。
【図1】
【図2a】
【図2b】
【図3】
【図4a】
【図4b】
【図5a】
【図5b】
【図6】
【図7】
【図8】
【図9a】
【図9b】
【図10】
【図11】
【図2a】
【図2b】
【図3】
【図4a】
【図4b】
【図5a】
【図5b】
【図6】
【図7】
【図8】
【図9a】
【図9b】
【図10】
【図11】
【公表番号】特表2008−512757(P2008−512757A)
【公表日】平成20年4月24日(2008.4.24)
【国際特許分類】
【出願番号】特願2007−530758(P2007−530758)
【出願日】平成17年9月2日(2005.9.2)
【国際出願番号】PCT/GB2005/003405
【国際公開番号】WO2006/027557
【国際公開日】平成18年3月16日(2006.3.16)
【出願人】(501352882)キネテイツク・リミテツド (93)
【公表日】平成20年4月24日(2008.4.24)
【国際特許分類】
【出願日】平成17年9月2日(2005.9.2)
【国際出願番号】PCT/GB2005/003405
【国際公開番号】WO2006/027557
【国際公開日】平成18年3月16日(2006.3.16)
【出願人】(501352882)キネテイツク・リミテツド (93)
[ Back to top ]