ネットワークへのフローの受付を制御する方法およびネットワーク
ネットワークのリンク内またはネットワーク内で要求される最大容量の正確かつ確実な推定を、低い計算コストで可能とするために、ネットワーク、特にＷｉＭＡＸ（Worldwide Interoperability for Microwave Access）ネットワークへのフローの受付を制御する方法が提供される。リソースの少なくとも１つのＱｏＳ（サービス品質）予約付きでネットワークに入ることを要求しているフローが受付可能かどうかを検査するために、ネットワークのリンク内および／またはネットワーク内で要求される最大容量の推定が、ＱｏＳ予約のすべてのペア、すなわち、リンク内および／またはネットワーク内ですでに受け入れられているＱｏＳ予約と、フローによって要求された前記少なくとも１つのＱｏＳ予約と、の間の交わりの第１の集合を求めることによって実行される。本方法は、ＱｏＳ予約の交わりの行列を作成することにより、求められた交わりの集合を構造化し、前記行列に基づき、各交わりに含まれるＱｏＳ予約に関して得られる情報に基づいて、求められた交わりの間の交わりの集合の残部を導出することを特徴とする。また、対応するネットワーク、好ましくは上記方法を実行するネットワークが提供される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク、特にＷｉＭＡＸ（Worldwide Interoperability for Microwave Access）ネットワークへのフローの受付を制御する方法に関する。リソースの少なくとも１つのＱｏＳ（サービス品質）予約付きでネットワークに入ることを要求しているフローが受付可能かどうかを検査するために、ネットワークのリンク内および／またはネットワーク内で要求される最大容量の推定が、ＱｏＳ予約のすべてのペア、すなわち、リンク内および／またはネットワーク内ですでに受け入れられているＱｏＳ予約と、フローによって要求された少なくとも１つのＱｏＳ予約と、の間の交わりの第１の集合を求めることによって実行される。
【０００２】
また、本発明は、ネットワーク、特にＷｉＭＡＸネットワークに関する。リソースの少なくとも１つのＱｏＳ予約付きでネットワークに入ることを要求しているフローが受付可能かどうかを検査するために、ネットワークのリンク内および／またはネットワーク内で要求される最大容量の推定が、ＱｏＳ予約のすべてのペア、すなわち、リンク内および／またはネットワーク内ですでに受け入れられているＱｏＳ予約と、フローによって要求された少なくとも１つのＱｏＳ予約と、の間の交わりの第１の集合を求めることによって実行される。
【背景技術】
【０００３】
ネットワークへのフローの受付を制御する方法および対応するネットワークが既知である。特に、ＷｉＭＡＸネットワークは、重要な将来のブロードバンドワイヤレス技術を提供しており、非特許文献１に記載されている。ＯＦＤＭＡ（直交周波数分割多元接続）の概念により、サービスプロバイダは、さまざまな移動および固定通信環境における多様な非リアルタイムおよびリアルタイムのアプリケーションをサポートすることが可能である。ＷｉＭＡＸにおいて、アプリケーションは、相異なるＱｏＳ保証を提供する複数のスケジューリングサービスのいずれかに割り当てられることが可能である。例えば、ＵＧＳ（Unsolicited Grant Service）は厳格なＱｏＳ保証を提供するが、他のｒｔＰＳ（real-time Polling Service）やｎｒｔＰＳ（non real-time Polling Service）は、より厳格でないＱｏＳレベルを提供する。最後に、ＢＥ（ベストエフォート）は保証を提供しない。提供されるサービスの需要のＱｏＳ要求に従うことはサービスプロバイダの義務であり、このため、システムの容量を正確に推定することが必要である。正確な容量推定技術により、効率的な受付制御のアルゴリズムおよび方法の設計が可能となる。
【０００４】
ＷｉＭＡＸに対する受付制御に関する最近の文献では、非常に異なるレベルの精度および計算負荷を達成するさまざまなオプションが提案されている。非特許文献２には、アプリケーションが需要として指定する平均データレートに主として基づく単純なアプローチが記載されている。このような知識により、所定の優先順序に従って、相異なるサービスからのコネクションがＷｉＭＡＸシステムで順次受け付けられることが可能である。このようなアプローチは、計算リソースをほとんど必要としない。しかし、このようなアプローチは、動画や活動検出付き音声のような代表的アプリケーションの時間変動性も、これらのリソースが要求される期間も考慮していない。したがって、実際に利用可能なリソースが未使用となる可能性がある。この解法は、最悪の場合とみなすことができる。
【０００５】
別のアプローチが非特許文献３に記載されている。この文献には、フローの帯域幅要求の分散が、アプリケーション要求をより良好に記述する統計量として提案されている。しかし、分散がすべてのトラフィックタイプについて良好な記述量であることの証明はない。著者はさらにこの方法を非特許文献４で拡張している。この文献では、あるしきい値を超えて遅延するパケットの予測される割合を考慮している。このような知識を用いて、特定のフローに対するＱｏＳ要求を満たすことができるかどうかを評価することができる。
【０００６】
非特許文献５には、特定のフローのブロッキング確率を予測するための、ファジー論理に基づくコントローラが記載されている。リアルタイムアプリケーションの時間変動性は、「ルールに基づく」コントローラによって考慮することができると説明されている。しかし、さまざまなタイプのトラフィックに対してこのようなコントローラの妥当性を拡張することが依然として必要である。最後に、非特許文献６には、スループットおよび遅延の両方の要求を考慮した、動画フローに対する正確な受付制御アルゴリズムが記載されている。しかし、このアプローチは、その計算負荷のために実際には使用可能でないため、代替案が必要である。
【０００７】
ＷｉＭＡＸネットワークは、動的サービス追加要求（Dynamic Service Addition request, ＤＳＡ−ＲＥＱ）メッセージを通じて、新たなフローがシステムへの加入を申し込むことを可能にすることによって、リソースのＱｏＳ予約をサポートする。この要求は、要求されるサービスに応じて相異なる義務的情報を含むＱｏＳパラメータセットを含む。これらのパラメータに基づいて、各予約ｉごとに、ＱｏＳ要求の最小のセットを次のようにサービスに対して導出することができる：与えられた開始時刻ｔｉに対して、ある量の容量Ｂｉ（ビット）が、時間間隔Ｔｉ内にフローｉのデータを送信するために周期的に予約されるべきである。
【０００８】
新たな予約ｉがシステムへの受け入れを要求する場合を考える。受付制御のアルゴリズムまたは方法は、すでに受け入れられている予約のＱｏＳ合意に依然として従いながら、その新たな予約要求を満たすためにネットワーク内に利用可能な十分な容量があるかどうかを評価しなければならない。このような要求は、次のように、振幅Ｂｉのクロネッカー・デルタの周期的離散系列としてモデル化することができる。
【数１】
【０００９】
ＷｉＭＡＸシステムは、ＱｏＳ要求Ｃａｖのデータに対して利用可能な容量を有し、Ｎ個の予約がすでに受け入れられていると仮定すると、新たな予約ｉは、次の条件が満たされる場合に、ネットワークに受け入れることができる。
【数２】
ただし、Ａ（ｔ）は、システムに受け付けられているＮ個のフローの予約と、１つの要求している加入との組合せによって形成される信号エンベロープの振幅に対応する。
【００１０】
ネットワークのリンク内および／またはネットワーク内で要求される最大容量を推定する以下の方法が既知である。
【００１１】
Ａ．最悪の場合
ｍａｘ（Ａ（ｔ））を求めるためには、さまざまなアプローチを考えることができる。最も簡単ではあるが、より悲観的な近似（以下、最悪の場合（Worst Case）という）は、受け付けられた予約が同時にサービスされる必要があると仮定するものである。すなわち、フローが実際にサービスされることが必要とされる時刻を考慮しない。
【数３】
【００１２】
このようなアプローチは、非特許文献２に記載されているものと類似している。このアプローチでは、利用可能な容量の大部分が十分に利用されない場合がある。
【００１３】
Ｂ．ヒューリスティック法
Ａ（ｔ）に対する正確な解は、Ａ（ｔ）のすべての値をその周期内で計算することによって得ることができる（式（４）参照）。なお、Ａ（ｔ）はＮ＋１個の周期的予約からなるので、その周期は、予約の周期の最小公倍数（ＬＣＭ）に対応する。このアプローチを、以下、本明細書においてヒューリスティック（Heuristic）法と呼ぶ。
【数４】
【００１４】
ヒューリスティック法は、システムにおける予約のＬＣＭに依存する。このＬＣＭは、このような周期に許容される粒度に応じて、予約数とともに指数関数的に増大する可能性があるため、計算量に関して高価になりすぎる。したがって、このような解法は、実際には実施可能でない場合がある。
【００１５】
Ｃ．ディオファントス法
ヒューリスティック法でのＬＣＭ依存性を除去するため、ディオファントス理論に基づく別の解法が考えられる。これは、一般的に、変数に整数のみが許される不定多項方程式を扱うものである。以下、本明細書において、このアプローチをディオファントス法と呼ぶ。上記のように、これは可能な解法として、非特許文献６で考察されている。
【００１６】
ディオファントス解法は次のように定義される。システムにすでに受け入れられているフローがリソース予約Ｂｉ・δ（ｔｉ＋ｎｉ・Ｔｉ）で記述され、ネットワークに入ることを要求している新たなフローがＢｊ・δ（ｔｊ＋ｎｊ・Ｔｊ）で特徴づけられる場合を考える。両方の予約の組合せＢｉ＋Ｂｊの最大リソース要求は、次のときに起こる。
【数５】
【００１７】
ｎｉおよびｎｊに対する解の集合（以下、交わりの集合と呼ぶ）を求めるため、条件（５）を、次のように、２変数の線型ディオファントス方程式として表すことができる。
【数６】
【００１８】
すると、線型ディオファントス方程式論によれば、次の条件が成り立つときに、ｎｉおよびｎｊに対する整数解の集合が存在することが知られている。
【数７】
ただし、ｄ＝ｇｃｄ（Ｔｉ，Ｔｊ）であり、ｇｃｄは最大公約数を表す。
【００１９】
前記の条件が成り立つとき、拡張ユークリッドアルゴリズムにより、予約の特定のペアに対応する解の集合を求めることができる。これにより、次式を満たすようなａとｂが求められる。
【数８】
【００２０】
システムにおける予約のすべてのペアにディオファントス解法を適用するとともに、求められた解に再帰的にディオファントス解法を適用することにより、ＬＣＭ長とは独立なＡ（ｔ）に対する厳密解を求めることができる。
【００２１】
ディオファントス解法は、システムにおける予約のすべてのペアと、求められた交わりの集合とに対するｇｃｄを計算することを必要とする。結果として、その計算量は、予約数の増大とともに顕著に増大し、ヒューリスティック解法の場合のように、実際には実施不可能となる可能性がある。
【００２２】
新たなフローが特定のＱｏＳ保証でシステムに入ることを要求するときに、リンク内および／またはネットワーク内で要求される最大容量を推定することは、リソースの使用に関して非常に重要である。このような推定は、新たなフローに対して要求されるＱｏＳ保証と、すでに受け付けられている関連するすべてのフローに提供されるＱｏＳ保証の考慮とに基づくべきである。
【００２３】
予想される最大リソース要求を正確に予測することによって、ＱｏＳ保証付きのフローをより多くネットワークに受け入れることが可能となるため、有料サービスに対する利用可能なネットワークリソースの使用を増大させることができる。厳密なピーク容量要求は、求められる交わりにおいて再帰的に線型ディオファントス理論を適用することで求めることができるが、その計算量は膨大である。したがって、実際に実施可能でない。
【００２４】
要約すると、従来技術は、最悪の場合、すなわち、すべてのＢの和をそれらのｔｉおよびＴｉとは無関係に考えているか、あるいは、実際には実施可能でないような計算量の解法を提案しているかのいずれかである。
【先行技術文献】
【非特許文献】
【００２５】
【非特許文献１】IEEE 802.16 Working Group, "IEEE Standard for Local and Metropolitan Area Networks. Part 16: Air Interface for Broadband Wireless Access Systems," IEEE Standard 802.16-2009, May 2009
【非特許文献２】H. Wang, W. Li, and D. P. Agrawal, "Dynamic Admission Control and QoS for 802.16 Wireless MAN," in Proceeding of Wireless Telecommunications Symposium (WTS), Pomona, USA, April 2005
【非特許文献３】A. Teh and P. Pudney, "Efficient Admission Control Based on Predicted Traffic Characteristics," in Proceeding of Personal Indoor Mobile Radio Communications (PIMRC), Athens, Greece, September 2007
【非特許文献４】A. Teh, A. Jayasuriya, and P. Pudney, "Admission Control in Wireless Infrastructure Networks Based on the Predicted Percentage of Delayed Packets," in Proceeding of Asia-Pacific Conference on Communications (APCC), Tokyo, Japan, October 2008
【非特許文献５】S. Ghazal, Y. H. Aoul, J. B. Othman, and F. Nait-Abdesselam, "Applying a Self-Configuring Admission Control Algorithm in a New QoS Architecture for IEEE 802.16 Networks," in Proceedings of IEEE Symposium on Computers and Communications (ISCC), Marrakech, Morocco, July 2008
【非特許文献６】O. Yang and J. Lu, "Call Admission Control and Scheduling Schemes with QoS support for Real-time Video Applications in IEEE 802.16 Networks," In IEEE Journal of Multimedia, May 2006
【発明の概要】
【発明が解決しようとする課題】
【００２６】
したがって、本発明の目的は、ネットワークへのフローの受付を制御する方法および対応するネットワークにおいて、ネットワークのリンク内および／またはネットワーク内で要求される最大容量の正確かつ確実な推定が、低い計算コストで可能となるような改良およびさらなる展開を行うことである。
【課題を解決するための手段】
【００２７】
本発明によれば、上記の目的は、請求項１に記載の方法によって達成される。この請求項１に記載の通り、本方法は、ＱｏＳ予約の交わりの行列を作成することにより、求められた交わりの集合を構造化し、前記行列に基づき、各交わりに含まれるＱｏＳ予約に関して得られる情報に基づいて、求められた交わりの間の交わりの集合の残部を導出することを特徴とする。
【００２８】
また、上記の目的は、請求項１６に記載のネットワークによって達成される。この請求項１６に記載の通り、本ネットワークは、ＱｏＳ予約の交わりの行列を作成することにより、求められた交わりの集合を構造化し、前記行列に基づき、各交わりに含まれるＱｏＳ予約に関して得られる情報に基づいて、求められた交わりの間の交わりの集合の残部を導出する手段を備えたことを特徴とする。
【００２９】
本発明によって認識されたこととして、計算コストの低減は、要求される最大容量の推定に関する精度の重大な損失なしに可能である。ＱｏＳ予約のすべてのペアの間の交わりの第１の集合を求めた後、求められた交わりの集合が、ＱｏＳ予約の交わりの行列を作成することにより構造化される。さらに、本発明によれば、求められた交わりの間の交わりの集合の残部が導出される。このような導出は、前記行列に基づき、各交わりに含まれるＱｏＳ予約に関して得られる情報に基づく。
【００３０】
本発明による方法は、既知のアプローチに対する拡張を提供する。要求される最大容量の正確かつ確実な推定が、低い計算コストで可能となる。したがって、有料サービスに対する利用可能なネットワークリソースの使用を増大させることができる。
【００３１】
具体的実施形態において、要求される容量は帯域幅要求に関する。
【００３２】
好ましくは、行列の作成は、予約の各ペアごとに、求められた交わりの集合をたどることによって実行してもよい。これは、高い計算コストのない、非常に簡単な方法ステップである。
【００３３】
さらに好ましくは、行列の作成は、線型ディオファントス方程式論を用いて実行してもよい。線型ディオファントス方程式論に基づいて、要求される最大容量の非常に正確かつ確実な推定が可能である。したがって、交わりの第１の集合を求める本発明の方法の最初の部分は、ディオファントス法と同一としてもよい。しかし、交わりの第１の集合がいったん求められたら、交わりの行列が、本発明により計算される。
【００３４】
好ましくは、交わりの集合の残部は、各予約ごとに交わりの行列をたどり、以下の定理１および２を適用することによって不能解を捨てることにより、導出してもよい。
定理１：求められた交わりの集合の任意のペアに対して、両方の解が１つの予約を共有し、他の２つの予約が互いに交わるとき、それらの集合は互いに交わる。
定理２：求められた交わりの任意の集合に対して、交わりの両方の集合に含まれるすべての予約が互いに交わるとき、かつそのときに限り、その集合は交わりの別の集合と交わる。
【００３５】
上記の定理１および２を使用することにより、既知のディオファントス法の拡張が可能であり、以下Ｅ（enhancement）−ディオファントス法と呼ぶ。これは、Ａ（ｔ）の最大値を求める際に、ディオファントス解法と同じ精度を、はるかに低い計算コストで達成する。
【００３６】
本発明の方法の具体的実施形態において、交わりの集合の残部の導出は、解の分枝を有する解ツリーに従ってもよい。好ましくは、解の分枝は、可能な最大値による降順で順序づけされてもよく、分枝の完全な探索を必要とせずに解が見つかるときには、分枝の探索を終了してもよい。このことは、本方法の計算負荷をさらに低減するために、解のツリーの完全な探索に対して最適化を提供することができる。
【００３７】
さらに好ましい実施形態において、解の分枝は、精度と計算時間とのトレードオフのための特定のポリシーに従って部分的にのみ探索されてもよい。例えば、最大容量を含む確率が最大となるような、全分枝数の所定の割合の分枝のみを探索してもよい。
【００３８】
別の最適化法として、帯域幅要求Ｂｉを所定の帯域幅要求Ｂｒｅｆの倍数としてモデル化し、Ｂｒｅｆよりも大きい予約をＢｉ／Ｂｒｅｆ個の予約としてモデル化してもよい。この場合、本方法は、実際の帯域幅要求の要求値を考慮する必要はなく、交わりの総数のみを考慮すればよい。
【００３９】
マルチホップリレーの場合に関して、ＭＲ−ＢＳ（Multi-Relay Base Station, マルチリレー基地局）またはＲＳ（Relay Station, リレー局）から次のＲＳへの入来フローは、リソースの少なくとも１つのＱｏＳ予約付きでネットワークに入ることを要求しているフローとみなしてもよい。すなわち、このような入来フローは、Ｅ−ディオファントス解法によって、ＱｏＳ要求付きの追加フローと全く同様に考えてもよい。このため、Ｅ−ディオファントス解法自体は、それを使用する受付制御方法以外の拡張を必要としない。
【００４０】
好ましくは、フローがネットワークに入ることを要求しているとき、本方法は、ダウンリンク要求の場合には宛先、またはアップリンク要求の場合にはソースが、ＲＳに関連しているかどうかを判定するステップを有してもよい。そしてそのような場合、本方法は、最大容量の推定のためにそのフローを考慮するステップをさらに有してもよい。
【００４１】
具体的には、新たなフロー要求に関連するＲＳがない場合、Ｅ−ディオファントス解法を直接適用してもよい。ＲＳが関連している場合、ソースからその宛先までのフローパスに含まれるすべてのＢＳおよびＲＳに対して、要求される最大容量の推定を実行してもよい。
【００４２】
後者の場合、新たなフローデータパス内の最初のＢＳまたはＲＳからネットワーク内の最後のＭＲ−ＢＳまたはＲＳまで、新たな最大容量要求を順次計算してもよい。すなわち、要求される最大容量の推定は、１ステップずつ順次実行してもよい。
【００４３】
好ましくは、いずれかのステップで、要求される最大容量が最大利用可能容量の値を超えた場合には、要求を拒否してもよい。
【００４４】
関連する各ＭＲ−ＢＳおよびＲＳでの新たな最大容量要求を計算するため、システムまたはネットワークにすでに受け入れられているフローと、新たなフローとの集合を考慮する必要がある。このため、各追加ステップまたはホップで、ＭＲ−ＢＳおよび／またはＲＳの処理能力に従って、ＷｉＭＡＸフレーム継続時間の整数倍または他の任意数だけ、予約開始時刻を増大させてもよい。
【００４５】
一般的に、リンク内および／またはネットワーク内の最大利用可能容量の値は、事業者によって規定されてもよく、あるいは、事業者ポリシーに基づいて規定されてもよい。すなわち、この値は、リンク内および／またはネットワーク内の実際の利用可能容量に必ずしも対応している必要はない。
【００４６】
本発明の解法は、「純粋な」線型ディオファントス解法と同程度に正確であるが、その計算負荷ははるかに低い。さらに、上記の交わりの行列に基づく部分的ツリー探索を、精度と計算時間とのトレードオフのために利用してもよい。
【００４７】
本発明は、ＱｏＳ要求付きの新たなフローを受け入れる際に、最大リソース要求の正確な予測を提供する。ほとんどの場合に、計算負荷は、他の解法を下回る。また、本発明は、マルチホップの場合の透過的なサポートを提供する。
【００４８】
上記のＥ−ディオファントス法は、マルチホップリレーの場合に対するＩＥＥＥ８０２．１６ｊ標準に適用可能となるように拡張することができる。
【００４９】
また、本発明は、帯域幅要求だけでなく、ジッタ、パケット損失、使用されるスケジューラ等の他のパラメータを考慮するように拡張可能である。
【００５０】
本発明を好ましい態様で実施するにはいくつもの可能性がある。このためには、一方で請求項１に従属する諸請求項を参照しつつ、他方で図面により例示された本発明の好ましい実施形態についての以下の説明を参照されたい。図面を用いて本発明の好ましい実施形態を説明する際には、本発明の教示による好ましい実施形態一般およびその変形例について説明する。
【図面の簡単な説明】
【００５１】
【図１】本発明によるネットワークへのフローの受付を制御する方法の一実施形態による予約の交わりの行列の例を示す図である。
【図２】本発明による拡張ディオファントス法に対する交わりの解のツリーを例示する図である。
【図３ａ】アルゴリズム性能比較を例示するグラフである。
【図３ｂ】アルゴリズム性能比較を例示するグラフである。
【図４】ＩＥＥＥ８０２．１６ｊマルチホップリレーの場合を例示する図である。
【発明を実施するための形態】
【００５２】
ヒューリスティック解法およびディオファントス解法の両方に対して指摘した実現可能性の問題を考慮して、本発明の実施形態では、ディオファントス法の拡張（以下、Ｅ−ディオファントス法という）を提示する。これは、Ａ（ｔ）の最大値を求める際に、ディオファントス解法と同じ精度を、はるかに低い計算コストで達成する。
【００５３】
提案するＥ−ディオファントス解法では、最初に、ディオファントス法の場合と全く同様に、考慮対象の予約のすべてのペアの間の交わりの集合を求める。このステップの後、求められた交わりのすべての集合に対して再帰的にプロセスを反復する代わりに、結果を、１０個の予約の例の場合に図１に示すような、予約の交わりの行列に構造化する。この交わりの行列に基づいて、求められた解の間の交わりの集合の残部を、各交わりに含まれる予約に関して得られる情報に基づいて導出する。以下、設計したＥ−ディオファントスアルゴリズムまたは方法を可能にする定理および証明を提供する。
【００５４】
Ａ．交わりの２個の集合の交わり
定理１：求められた交わりの集合の任意のペアに対して、両方の解が１つの予約を共有し、他の２つの予約が互いに交わるとき、それらの集合は互いに交わる。
【００５５】
証明：予約ｉおよびｊに対して、次のように定義される交わりの集合が存在するとする。
【数９】
ここで、最小のｎｉ，ｎｊ∈Ｚは次式を満たす。
【数１０】
また、予約ｊおよびｋに対して、次のように定義される交わりの別の集合が存在するとする。
【数１１】
ここで、最小のｎｊ，ｎｋ∈Ｚは次式を満たす。
【数１２】
【００５６】
求められた両方の交わりの集合の間の交わりの集合は、ｎｉｊ，ｎｊｋ∈Ｚの集合が次式を満たす場合に存在する。
【数１３】
【００５７】
ｔｉｊおよびｔｊｋがそれぞれｔｊ＋ｎｊ・Ｔｊおよびｔｊ＋ｎ′ｊ・Ｔｊと表せることを考慮すると、式（１３）を次のように展開することができる。
【数１４】
【００５８】
これは、次のようにも表すことができる。
【数１５】
【００５９】
そこで、
【数１６】
および
【数１７】
であるので、予約ｉとｋが交わる場合には、式（１５）の条件が成り立つようなｎｉｊ，ｎｊｋ∈Ｚに対して解が存在することが確かめられる。そこで、予約ｉ、ｊおよびｋに対して結果として得られる交わりの集合が次のように定義される。
【数１８】
【００６０】
Ｂ．交わりのＮ＋１個の集合の交わり
定理２：求められた交わりの任意の集合に対して、交わりの両方の集合に含まれるすべての予約が互いに交わるとき、かつそのときに限り、その集合は交わりの別の集合と交わる。
【００６１】
証明：次のように定義される交わりのＮ個の集合の交わりの集合を仮定する。
【数１９】
【００６２】
なお、交わりの集合に対する記法は、読みやすくするために簡略化して、予約の任意のペアの交わりの集合を、関連する２つの予約の代わりに単一の下付き添字で示している。
【００６３】
交わりの追加的な集合ＩＮ＋１がＩＮと交わるためには、次式を満たすようなｎＮ，ｎＮ＋１∈Ｚの集合が存在しなければならない。
【数２０】
【００６４】
ここで、次を考慮する。
【数２１】
【００６５】
すると、次式のとき、かつそのときに限り、交わりの集合ＩＮ＋１はＩＮと交わる。
【数２２】
【００６６】
Ｃ．Ｅ−ディオファントスアルゴリズム
アルゴリズム３：システムにすでに受け入れられているＮ個の予約の集合について、対応する開始時刻ｔ＝（ｔ１...ｔＮ）、周期Ｔ＝（Ｔ１...ＴＮ）および要求Ｂ＝（Ｂ１...ＢＮ）を考慮して、開始時刻ｔＮ＋１、周期ＴＮ＋１および要求ＢＮ＋１の新たな予約ｒＮ＋１に対する最大リソース要求を求めるためのＥ−ディオファントスアルゴリズム
1: それぞれの新たな予約要求に対して実行される呼び出し
2: for i = 1 to N+1 do
3: for j = i+1 to N+1 do
4: if solution_exists(ｔｉ,ｔｊ,Ｔｉ,Ｔｊ) then
5: intersections ← find_inters_dioph(ｔｉ,ｔｊ,Ｔｉ,Ｔｊ)
6: end if
7: end for
8: end for
9: intersections ← group_intersections(intersections)
10: m_inters = compute_matrix_inters(intersections)
11: for i = 1 to N+1 do
12: solutions_tree ← compute_inters_inters(m_inters, i)
13: end for
14: if find_maximum(solutions_tree,Ｂ)≦Ｃａｖ then
15: return accept_request(ｒＮ＋１)
16: else
17: return reject_request(ｒＮ＋１)
18: end if
【００６７】
アルゴリズム３は、Ｅ−ディオファントス解法が従うステップの詳細を示している。アルゴリズムの最初の部分では、交わりの第１の集合を求めているが、これはディオファントスアルゴリズムと同一である。交わりの第１の集合がいったん求められたら、交わりの行列が計算される。この操作は、アルゴリズム３における関数compute_matrix_inters(.)に対応する。図１は、１０個の予約の集合に対して求められた交わりの行列の例を示している。このような交わりの行列は、予約の各ペアごとに、アルゴリズムの最初の部分で得られた交わりの集合を単にたどるだけで得ることができる。
【００６８】
交わりの行列に基づいて、Ｅ−ディオファントスアルゴリズムは、各予約ごとに交わりの行列をたどり、定理１および２を適用することによって不能解を捨てることにより、追加的な交わりの残部を求める。この操作は、関数compute_matrix_inters(.)に対応し、いわゆる解のツリー（solutions_tree）を生じる。図２は、図１に示した交わりの行列に基づいて求められた解のツリーを例示している。スペースの制限から、それぞれの第２レベル分枝について１つの解だけを示している。例として、予約１の場合、予約２を有する解の分枝はない。というのは、交わりの行列によれば、予約１は予約２と交わらないからである。解の分枝１→３→４の場合、予約５の分枝への継続はやはり捨てられる。というのは、予約３は５と交わらないからである。
【００６９】
明らかに、アルゴリズムの計算負荷をさらに低減するために、解のツリーの完全な探索に対する最適化が可能である。例えば、交わりの行列に基づいて、探索すべき解の分枝は、可能な最大値による降順で順序づけされてもよく、完全な探索を必要とせずに解が見つかるときには、探索を終了してもよい。別の最適化法として、帯域幅要求Ｂｉを任意に選択された帯域幅要求Ｂｒｅｆの倍数としてモデル化してもよい。この場合、Ｂｒｅｆよりも大きい予約を［Ｂｉ／Ｂｒｅｆ］個の予約としてモデル化すれば、アルゴリズムは、実際の帯域幅要求の要求値を考慮する必要はなく、交わりの総数のみを考慮すればよい。
【００７０】
Ｄ．アルゴリズム性能比較
最悪の場合、ヒューリスティック法、ディオファントス法およびＥ−ディオファントス法の間の性能差を検証・評価するため、これらのアルゴリズムをＭＡＴＬＡＢで実装し、以下の実験を実行した。その結果を図３にまとめる。１０〜１００個の予約を有するシステムを考え、各予約ごとにｔｉおよびＴｉを一様分布からランダムに選択した。一様分布の範囲は、考慮される粒度に応じて選択した。すなわち、粒度１の場合は１〜１００、粒度５の場合は１〜２０、粒度１０の場合は１〜１０とした。例示のため、Ｂｉはすべての場合に１とした。
【００７１】
図３ａは、それぞれのアプローチによって要求される最大リソース数の推定値の間の差を示している。観察できるように、差は、予約数の増大とともに増大するだけでなく、ディオファントス法およびＥ−ディオファントス法以外のすべてのアプローチでは、より大きい粒度を考慮するときに差が増大する。ディオファントス法の値が厳密解なので基準にとると、予想されるように、最悪の場合の解は、実際の値との差が最大となり、差は３００％を超える。使用される実際の要求と比べてこのように大きい差があると、明らかに、ＱｏＳ要求付きのサービスによるネットワークの使用が、可能な使用量よりもはるかに低くなるので、ネットワーク事業者にとっては、可能な収入が低くなる。ヒューリスティック法の場合、粒度が大きいほど、現実の実装において考慮可能な最大のＬＣＭ値（われわれのシステムでは１０７）における制限のために、実際の値からの差が大きくなる。さらに悪いことに、推定値は実際の値を下回るので、受付制御目的で使用すると、ネットワークにおけるＱｏＳ保証を損なう可能性がある。他方、Ｅ−ディオファントス法の推定値は、ディオファントス法の推定値に常に等しいことから、定理１および２の正しさが確認される。
【００７２】
図３ｂは、計算負荷における対応する差をヒューリスティック法と比べて示している。ヒューリスティック法は実装が簡単なので、ここでは基準としてとっている。最悪の場合は考慮していない。というのは、その計算負荷は明らかに無視できるほどであるが、図３ａに示したように、使用される実際のリソースの推定値もまた、ＱｏＳ要求付きのサービスによるネットワークの使用がはるかに低くなるからである。図から観察できるように、ディオファントス解法は、厳密ではあるが、考慮されている代替解法の計算負荷をはるかに超えるので、実際には実施可能でない。例えば、３０個の予約の場合、２×クアッドコアのシミュレーションサーバにおいてかかった計算時間は１０００秒を超えた。考慮される最低の粒度の場合、ヒューリスティック法は、精度の損失なしでＥ−ディオファントス解法を計算時間において明らかに凌駕する。しかし、考慮される粒度が増大すると、Ｅ−ディオファントス法の性能は、ほとんどの場合、ヒューリスティック法よりも３桁程度高速であると同時に、予想される最大要求の厳密な推定値が得られるのに対して、ヒューリスティック法は、特に粒度１の場合に、明らかに過小推定となる。これらの結果に基づいて、以下、本明細書では、提案するＥ−ディオファントス解法の分析のみに集中する。
【００７３】
Ｅ．マルチホップリレーへの拡張
Ｅ−ディオファントス解法は、マルチホップリレーの場合に対するＩＥＥＥ８０２．１６ｊ標準に適用可能となるように拡張することができる。以下、提案するＥ−ディオファントス法のマルチホップリレーへの拡張について詳細に説明する。
【００７４】
ＩＥＥＥ８０２．１６ｊのマルチホップリレーの場合、ＭＲ−ＢＳまたはＲＳから次のＲＳへの入来フローは、Ｅ−ディオファントス解法によって、ＱｏＳ要求付きの追加フローと全く同様に考えることができる。このため、Ｅ−ディオファントス解法自体は、それを使用する受付制御アルゴリズム以外の拡張を必要としない。新たなフローがシステムに入ることを要求しているとき、受付制御アルゴリズムは、ダウンリンク要求の場合には宛先、またはアップリンク要求の場合にはソースが、ＲＳに関連しているかどうかを判定すべきである。そしてそのような場合、以下のようにして、最大容量要求計算のためにそのフローを考慮する。
【００７５】
まず、２つの場合を区別する必要がある。新たなフロー要求に関連するＲＳがない場合、Ｅ−ディオファントス解法を直接適用することができる。他方、ＲＳが関連している場合、その宛先までのフローパスに含まれる基地局およびリレー局に対して、最大容量要求の増大をチェックする必要がある。後者の場合、新たなフローデータパス内の最初の基地局またはＲＳからローカルＷｉＭＡＸネットワーク内の最後のＭＲ−ＢＳまたはＲＳまで、新たな最大容量要求を順次計算する。そして、いずれかのステップで、利用可能な最大容量を超えるとみなされる場合、要求を拒否する。関連する各ＭＲ−ＢＳおよびＲＳでの新たな最大容量要求を計算するため、システムにすでに受け入れられているフローと、新たなフローとの集合を考慮する必要がある。この際、それぞれの次のＭＲ−ＢＳまたはＲＳへのフローの到着が、ＭＲ−ＢＳおよびＲＳの処理能力に従って、ＷｉＭＡＸフレーム継続時間Ｎｆの整数倍だけ増大することを考慮する。図４に、アップリンクおよびダウンリンクの通信を有するマルチホップリレーの場合の例を示す。
【００７６】
ダウンリンク
ダウンリンクの場合、ＷｉＭＡＸコアネットワークから来るＱｏＳ要求付きのフローの集合を考える。それらの予約は、ＲＣＮ＝｛ｒＣＮ１，ｒＣＮ２，...，ｒＣＮＮ｝で定義される。それぞれの後続のＲＳに対して、受け入れを要求している新たなフローを含めて、その宛先までのフローパスにおける各リレーによって考慮されるべきフローの集合ＲＲＳＭは、次のように表すことができる。
【数２３】
そして、リレーＲｉ∈ｉ＝１..Ｍにおける任意の予約ｊ∈Ｒに対する周期的な帯域幅要求は、次のように表すことができる。
【数２４】
【００７７】
こうして、Ｅ−ディオファントス解法は、各ＲＳにおいて、予約の対応する部分集合ＲＣＮおよび増大する開始時刻ｔｊ＋ｉ・Ｎｆを考慮することによって、最大予想リソース要求を取得することに適用可能である。
【００７８】
アップリンク
アップリンクの場合は、ダウンリンクの場合とは異なり、ソースからそれぞれの次ホップにおいて、最大リソース要求を求めるために考慮すべき予約数は増大する可能性がある。リレーｉに関連するＳＳによって発信されたＱｏＳ要求付きのフローの集合を考える。それらの予約は、ＲＳＳＲｉ＝｛ｒＳＳ１，ｒＳＳ２，...，ｒＳＳＮ｝で定義される。それぞれの後続のＲＳに対して、受け入れを要求している新たなフローを含めて、ＭＲ−ＢＳまでのフローパスにおける各リレーによって考慮されるべき予約の集合ＲＢＳは、次のように表すことができる。
【数２５】
そして、リレーＲｉ∈ｉ＝１..ＭまたはＭＲ−ＢＳ（ｉ＝Ｍ＋１）における任意の予約ｊ∈Ｒに対する周期的な帯域幅要求は、次のように表すことができる。
【数２６】
【００７９】
こうして、ダウンリンクの場合と同様に、Ｅ−ディオファントス解法は、各ＲＳおよびＭＲ−ＢＳにおいて、予約の対応する部分集合ＲＢＳおよび増大する開始時刻ｔｊ＋（ｉ−１）・Ｎｆを考慮することによって、最大予想リソース要求を取得することに適用可能である。
【００８０】
上記の説明および添付図面の記載に基づいて、当業者は本発明の多くの変形例および他の実施形態に想到し得るであろう。したがって、本発明は、開示した具体的実施形態に限定されるものではなく、変形例および他の実施形態も、添付の特許請求の範囲内に含まれるものと解すべきである。本明細書では特定の用語を用いているが、それらは総称的・説明的意味でのみ用いられており、限定を目的としたものではない。
【技術分野】
【０００１】
本発明は、ネットワーク、特にＷｉＭＡＸ（Worldwide Interoperability for Microwave Access）ネットワークへのフローの受付を制御する方法に関する。リソースの少なくとも１つのＱｏＳ（サービス品質）予約付きでネットワークに入ることを要求しているフローが受付可能かどうかを検査するために、ネットワークのリンク内および／またはネットワーク内で要求される最大容量の推定が、ＱｏＳ予約のすべてのペア、すなわち、リンク内および／またはネットワーク内ですでに受け入れられているＱｏＳ予約と、フローによって要求された少なくとも１つのＱｏＳ予約と、の間の交わりの第１の集合を求めることによって実行される。
【０００２】
また、本発明は、ネットワーク、特にＷｉＭＡＸネットワークに関する。リソースの少なくとも１つのＱｏＳ予約付きでネットワークに入ることを要求しているフローが受付可能かどうかを検査するために、ネットワークのリンク内および／またはネットワーク内で要求される最大容量の推定が、ＱｏＳ予約のすべてのペア、すなわち、リンク内および／またはネットワーク内ですでに受け入れられているＱｏＳ予約と、フローによって要求された少なくとも１つのＱｏＳ予約と、の間の交わりの第１の集合を求めることによって実行される。
【背景技術】
【０００３】
ネットワークへのフローの受付を制御する方法および対応するネットワークが既知である。特に、ＷｉＭＡＸネットワークは、重要な将来のブロードバンドワイヤレス技術を提供しており、非特許文献１に記載されている。ＯＦＤＭＡ（直交周波数分割多元接続）の概念により、サービスプロバイダは、さまざまな移動および固定通信環境における多様な非リアルタイムおよびリアルタイムのアプリケーションをサポートすることが可能である。ＷｉＭＡＸにおいて、アプリケーションは、相異なるＱｏＳ保証を提供する複数のスケジューリングサービスのいずれかに割り当てられることが可能である。例えば、ＵＧＳ（Unsolicited Grant Service）は厳格なＱｏＳ保証を提供するが、他のｒｔＰＳ（real-time Polling Service）やｎｒｔＰＳ（non real-time Polling Service）は、より厳格でないＱｏＳレベルを提供する。最後に、ＢＥ（ベストエフォート）は保証を提供しない。提供されるサービスの需要のＱｏＳ要求に従うことはサービスプロバイダの義務であり、このため、システムの容量を正確に推定することが必要である。正確な容量推定技術により、効率的な受付制御のアルゴリズムおよび方法の設計が可能となる。
【０００４】
ＷｉＭＡＸに対する受付制御に関する最近の文献では、非常に異なるレベルの精度および計算負荷を達成するさまざまなオプションが提案されている。非特許文献２には、アプリケーションが需要として指定する平均データレートに主として基づく単純なアプローチが記載されている。このような知識により、所定の優先順序に従って、相異なるサービスからのコネクションがＷｉＭＡＸシステムで順次受け付けられることが可能である。このようなアプローチは、計算リソースをほとんど必要としない。しかし、このようなアプローチは、動画や活動検出付き音声のような代表的アプリケーションの時間変動性も、これらのリソースが要求される期間も考慮していない。したがって、実際に利用可能なリソースが未使用となる可能性がある。この解法は、最悪の場合とみなすことができる。
【０００５】
別のアプローチが非特許文献３に記載されている。この文献には、フローの帯域幅要求の分散が、アプリケーション要求をより良好に記述する統計量として提案されている。しかし、分散がすべてのトラフィックタイプについて良好な記述量であることの証明はない。著者はさらにこの方法を非特許文献４で拡張している。この文献では、あるしきい値を超えて遅延するパケットの予測される割合を考慮している。このような知識を用いて、特定のフローに対するＱｏＳ要求を満たすことができるかどうかを評価することができる。
【０００６】
非特許文献５には、特定のフローのブロッキング確率を予測するための、ファジー論理に基づくコントローラが記載されている。リアルタイムアプリケーションの時間変動性は、「ルールに基づく」コントローラによって考慮することができると説明されている。しかし、さまざまなタイプのトラフィックに対してこのようなコントローラの妥当性を拡張することが依然として必要である。最後に、非特許文献６には、スループットおよび遅延の両方の要求を考慮した、動画フローに対する正確な受付制御アルゴリズムが記載されている。しかし、このアプローチは、その計算負荷のために実際には使用可能でないため、代替案が必要である。
【０００７】
ＷｉＭＡＸネットワークは、動的サービス追加要求（Dynamic Service Addition request, ＤＳＡ−ＲＥＱ）メッセージを通じて、新たなフローがシステムへの加入を申し込むことを可能にすることによって、リソースのＱｏＳ予約をサポートする。この要求は、要求されるサービスに応じて相異なる義務的情報を含むＱｏＳパラメータセットを含む。これらのパラメータに基づいて、各予約ｉごとに、ＱｏＳ要求の最小のセットを次のようにサービスに対して導出することができる：与えられた開始時刻ｔｉに対して、ある量の容量Ｂｉ（ビット）が、時間間隔Ｔｉ内にフローｉのデータを送信するために周期的に予約されるべきである。
【０００８】
新たな予約ｉがシステムへの受け入れを要求する場合を考える。受付制御のアルゴリズムまたは方法は、すでに受け入れられている予約のＱｏＳ合意に依然として従いながら、その新たな予約要求を満たすためにネットワーク内に利用可能な十分な容量があるかどうかを評価しなければならない。このような要求は、次のように、振幅Ｂｉのクロネッカー・デルタの周期的離散系列としてモデル化することができる。
【数１】
【０００９】
ＷｉＭＡＸシステムは、ＱｏＳ要求Ｃａｖのデータに対して利用可能な容量を有し、Ｎ個の予約がすでに受け入れられていると仮定すると、新たな予約ｉは、次の条件が満たされる場合に、ネットワークに受け入れることができる。
【数２】
ただし、Ａ（ｔ）は、システムに受け付けられているＮ個のフローの予約と、１つの要求している加入との組合せによって形成される信号エンベロープの振幅に対応する。
【００１０】
ネットワークのリンク内および／またはネットワーク内で要求される最大容量を推定する以下の方法が既知である。
【００１１】
Ａ．最悪の場合
ｍａｘ（Ａ（ｔ））を求めるためには、さまざまなアプローチを考えることができる。最も簡単ではあるが、より悲観的な近似（以下、最悪の場合（Worst Case）という）は、受け付けられた予約が同時にサービスされる必要があると仮定するものである。すなわち、フローが実際にサービスされることが必要とされる時刻を考慮しない。
【数３】
【００１２】
このようなアプローチは、非特許文献２に記載されているものと類似している。このアプローチでは、利用可能な容量の大部分が十分に利用されない場合がある。
【００１３】
Ｂ．ヒューリスティック法
Ａ（ｔ）に対する正確な解は、Ａ（ｔ）のすべての値をその周期内で計算することによって得ることができる（式（４）参照）。なお、Ａ（ｔ）はＮ＋１個の周期的予約からなるので、その周期は、予約の周期の最小公倍数（ＬＣＭ）に対応する。このアプローチを、以下、本明細書においてヒューリスティック（Heuristic）法と呼ぶ。
【数４】
【００１４】
ヒューリスティック法は、システムにおける予約のＬＣＭに依存する。このＬＣＭは、このような周期に許容される粒度に応じて、予約数とともに指数関数的に増大する可能性があるため、計算量に関して高価になりすぎる。したがって、このような解法は、実際には実施可能でない場合がある。
【００１５】
Ｃ．ディオファントス法
ヒューリスティック法でのＬＣＭ依存性を除去するため、ディオファントス理論に基づく別の解法が考えられる。これは、一般的に、変数に整数のみが許される不定多項方程式を扱うものである。以下、本明細書において、このアプローチをディオファントス法と呼ぶ。上記のように、これは可能な解法として、非特許文献６で考察されている。
【００１６】
ディオファントス解法は次のように定義される。システムにすでに受け入れられているフローがリソース予約Ｂｉ・δ（ｔｉ＋ｎｉ・Ｔｉ）で記述され、ネットワークに入ることを要求している新たなフローがＢｊ・δ（ｔｊ＋ｎｊ・Ｔｊ）で特徴づけられる場合を考える。両方の予約の組合せＢｉ＋Ｂｊの最大リソース要求は、次のときに起こる。
【数５】
【００１７】
ｎｉおよびｎｊに対する解の集合（以下、交わりの集合と呼ぶ）を求めるため、条件（５）を、次のように、２変数の線型ディオファントス方程式として表すことができる。
【数６】
【００１８】
すると、線型ディオファントス方程式論によれば、次の条件が成り立つときに、ｎｉおよびｎｊに対する整数解の集合が存在することが知られている。
【数７】
ただし、ｄ＝ｇｃｄ（Ｔｉ，Ｔｊ）であり、ｇｃｄは最大公約数を表す。
【００１９】
前記の条件が成り立つとき、拡張ユークリッドアルゴリズムにより、予約の特定のペアに対応する解の集合を求めることができる。これにより、次式を満たすようなａとｂが求められる。
【数８】
【００２０】
システムにおける予約のすべてのペアにディオファントス解法を適用するとともに、求められた解に再帰的にディオファントス解法を適用することにより、ＬＣＭ長とは独立なＡ（ｔ）に対する厳密解を求めることができる。
【００２１】
ディオファントス解法は、システムにおける予約のすべてのペアと、求められた交わりの集合とに対するｇｃｄを計算することを必要とする。結果として、その計算量は、予約数の増大とともに顕著に増大し、ヒューリスティック解法の場合のように、実際には実施不可能となる可能性がある。
【００２２】
新たなフローが特定のＱｏＳ保証でシステムに入ることを要求するときに、リンク内および／またはネットワーク内で要求される最大容量を推定することは、リソースの使用に関して非常に重要である。このような推定は、新たなフローに対して要求されるＱｏＳ保証と、すでに受け付けられている関連するすべてのフローに提供されるＱｏＳ保証の考慮とに基づくべきである。
【００２３】
予想される最大リソース要求を正確に予測することによって、ＱｏＳ保証付きのフローをより多くネットワークに受け入れることが可能となるため、有料サービスに対する利用可能なネットワークリソースの使用を増大させることができる。厳密なピーク容量要求は、求められる交わりにおいて再帰的に線型ディオファントス理論を適用することで求めることができるが、その計算量は膨大である。したがって、実際に実施可能でない。
【００２４】
要約すると、従来技術は、最悪の場合、すなわち、すべてのＢの和をそれらのｔｉおよびＴｉとは無関係に考えているか、あるいは、実際には実施可能でないような計算量の解法を提案しているかのいずれかである。
【先行技術文献】
【非特許文献】
【００２５】
【非特許文献１】IEEE 802.16 Working Group, "IEEE Standard for Local and Metropolitan Area Networks. Part 16: Air Interface for Broadband Wireless Access Systems," IEEE Standard 802.16-2009, May 2009
【非特許文献２】H. Wang, W. Li, and D. P. Agrawal, "Dynamic Admission Control and QoS for 802.16 Wireless MAN," in Proceeding of Wireless Telecommunications Symposium (WTS), Pomona, USA, April 2005
【非特許文献３】A. Teh and P. Pudney, "Efficient Admission Control Based on Predicted Traffic Characteristics," in Proceeding of Personal Indoor Mobile Radio Communications (PIMRC), Athens, Greece, September 2007
【非特許文献４】A. Teh, A. Jayasuriya, and P. Pudney, "Admission Control in Wireless Infrastructure Networks Based on the Predicted Percentage of Delayed Packets," in Proceeding of Asia-Pacific Conference on Communications (APCC), Tokyo, Japan, October 2008
【非特許文献５】S. Ghazal, Y. H. Aoul, J. B. Othman, and F. Nait-Abdesselam, "Applying a Self-Configuring Admission Control Algorithm in a New QoS Architecture for IEEE 802.16 Networks," in Proceedings of IEEE Symposium on Computers and Communications (ISCC), Marrakech, Morocco, July 2008
【非特許文献６】O. Yang and J. Lu, "Call Admission Control and Scheduling Schemes with QoS support for Real-time Video Applications in IEEE 802.16 Networks," In IEEE Journal of Multimedia, May 2006
【発明の概要】
【発明が解決しようとする課題】
【００２６】
したがって、本発明の目的は、ネットワークへのフローの受付を制御する方法および対応するネットワークにおいて、ネットワークのリンク内および／またはネットワーク内で要求される最大容量の正確かつ確実な推定が、低い計算コストで可能となるような改良およびさらなる展開を行うことである。
【課題を解決するための手段】
【００２７】
本発明によれば、上記の目的は、請求項１に記載の方法によって達成される。この請求項１に記載の通り、本方法は、ＱｏＳ予約の交わりの行列を作成することにより、求められた交わりの集合を構造化し、前記行列に基づき、各交わりに含まれるＱｏＳ予約に関して得られる情報に基づいて、求められた交わりの間の交わりの集合の残部を導出することを特徴とする。
【００２８】
また、上記の目的は、請求項１６に記載のネットワークによって達成される。この請求項１６に記載の通り、本ネットワークは、ＱｏＳ予約の交わりの行列を作成することにより、求められた交わりの集合を構造化し、前記行列に基づき、各交わりに含まれるＱｏＳ予約に関して得られる情報に基づいて、求められた交わりの間の交わりの集合の残部を導出する手段を備えたことを特徴とする。
【００２９】
本発明によって認識されたこととして、計算コストの低減は、要求される最大容量の推定に関する精度の重大な損失なしに可能である。ＱｏＳ予約のすべてのペアの間の交わりの第１の集合を求めた後、求められた交わりの集合が、ＱｏＳ予約の交わりの行列を作成することにより構造化される。さらに、本発明によれば、求められた交わりの間の交わりの集合の残部が導出される。このような導出は、前記行列に基づき、各交わりに含まれるＱｏＳ予約に関して得られる情報に基づく。
【００３０】
本発明による方法は、既知のアプローチに対する拡張を提供する。要求される最大容量の正確かつ確実な推定が、低い計算コストで可能となる。したがって、有料サービスに対する利用可能なネットワークリソースの使用を増大させることができる。
【００３１】
具体的実施形態において、要求される容量は帯域幅要求に関する。
【００３２】
好ましくは、行列の作成は、予約の各ペアごとに、求められた交わりの集合をたどることによって実行してもよい。これは、高い計算コストのない、非常に簡単な方法ステップである。
【００３３】
さらに好ましくは、行列の作成は、線型ディオファントス方程式論を用いて実行してもよい。線型ディオファントス方程式論に基づいて、要求される最大容量の非常に正確かつ確実な推定が可能である。したがって、交わりの第１の集合を求める本発明の方法の最初の部分は、ディオファントス法と同一としてもよい。しかし、交わりの第１の集合がいったん求められたら、交わりの行列が、本発明により計算される。
【００３４】
好ましくは、交わりの集合の残部は、各予約ごとに交わりの行列をたどり、以下の定理１および２を適用することによって不能解を捨てることにより、導出してもよい。
定理１：求められた交わりの集合の任意のペアに対して、両方の解が１つの予約を共有し、他の２つの予約が互いに交わるとき、それらの集合は互いに交わる。
定理２：求められた交わりの任意の集合に対して、交わりの両方の集合に含まれるすべての予約が互いに交わるとき、かつそのときに限り、その集合は交わりの別の集合と交わる。
【００３５】
上記の定理１および２を使用することにより、既知のディオファントス法の拡張が可能であり、以下Ｅ（enhancement）−ディオファントス法と呼ぶ。これは、Ａ（ｔ）の最大値を求める際に、ディオファントス解法と同じ精度を、はるかに低い計算コストで達成する。
【００３６】
本発明の方法の具体的実施形態において、交わりの集合の残部の導出は、解の分枝を有する解ツリーに従ってもよい。好ましくは、解の分枝は、可能な最大値による降順で順序づけされてもよく、分枝の完全な探索を必要とせずに解が見つかるときには、分枝の探索を終了してもよい。このことは、本方法の計算負荷をさらに低減するために、解のツリーの完全な探索に対して最適化を提供することができる。
【００３７】
さらに好ましい実施形態において、解の分枝は、精度と計算時間とのトレードオフのための特定のポリシーに従って部分的にのみ探索されてもよい。例えば、最大容量を含む確率が最大となるような、全分枝数の所定の割合の分枝のみを探索してもよい。
【００３８】
別の最適化法として、帯域幅要求Ｂｉを所定の帯域幅要求Ｂｒｅｆの倍数としてモデル化し、Ｂｒｅｆよりも大きい予約をＢｉ／Ｂｒｅｆ個の予約としてモデル化してもよい。この場合、本方法は、実際の帯域幅要求の要求値を考慮する必要はなく、交わりの総数のみを考慮すればよい。
【００３９】
マルチホップリレーの場合に関して、ＭＲ−ＢＳ（Multi-Relay Base Station, マルチリレー基地局）またはＲＳ（Relay Station, リレー局）から次のＲＳへの入来フローは、リソースの少なくとも１つのＱｏＳ予約付きでネットワークに入ることを要求しているフローとみなしてもよい。すなわち、このような入来フローは、Ｅ−ディオファントス解法によって、ＱｏＳ要求付きの追加フローと全く同様に考えてもよい。このため、Ｅ−ディオファントス解法自体は、それを使用する受付制御方法以外の拡張を必要としない。
【００４０】
好ましくは、フローがネットワークに入ることを要求しているとき、本方法は、ダウンリンク要求の場合には宛先、またはアップリンク要求の場合にはソースが、ＲＳに関連しているかどうかを判定するステップを有してもよい。そしてそのような場合、本方法は、最大容量の推定のためにそのフローを考慮するステップをさらに有してもよい。
【００４１】
具体的には、新たなフロー要求に関連するＲＳがない場合、Ｅ−ディオファントス解法を直接適用してもよい。ＲＳが関連している場合、ソースからその宛先までのフローパスに含まれるすべてのＢＳおよびＲＳに対して、要求される最大容量の推定を実行してもよい。
【００４２】
後者の場合、新たなフローデータパス内の最初のＢＳまたはＲＳからネットワーク内の最後のＭＲ−ＢＳまたはＲＳまで、新たな最大容量要求を順次計算してもよい。すなわち、要求される最大容量の推定は、１ステップずつ順次実行してもよい。
【００４３】
好ましくは、いずれかのステップで、要求される最大容量が最大利用可能容量の値を超えた場合には、要求を拒否してもよい。
【００４４】
関連する各ＭＲ−ＢＳおよびＲＳでの新たな最大容量要求を計算するため、システムまたはネットワークにすでに受け入れられているフローと、新たなフローとの集合を考慮する必要がある。このため、各追加ステップまたはホップで、ＭＲ−ＢＳおよび／またはＲＳの処理能力に従って、ＷｉＭＡＸフレーム継続時間の整数倍または他の任意数だけ、予約開始時刻を増大させてもよい。
【００４５】
一般的に、リンク内および／またはネットワーク内の最大利用可能容量の値は、事業者によって規定されてもよく、あるいは、事業者ポリシーに基づいて規定されてもよい。すなわち、この値は、リンク内および／またはネットワーク内の実際の利用可能容量に必ずしも対応している必要はない。
【００４６】
本発明の解法は、「純粋な」線型ディオファントス解法と同程度に正確であるが、その計算負荷ははるかに低い。さらに、上記の交わりの行列に基づく部分的ツリー探索を、精度と計算時間とのトレードオフのために利用してもよい。
【００４７】
本発明は、ＱｏＳ要求付きの新たなフローを受け入れる際に、最大リソース要求の正確な予測を提供する。ほとんどの場合に、計算負荷は、他の解法を下回る。また、本発明は、マルチホップの場合の透過的なサポートを提供する。
【００４８】
上記のＥ−ディオファントス法は、マルチホップリレーの場合に対するＩＥＥＥ８０２．１６ｊ標準に適用可能となるように拡張することができる。
【００４９】
また、本発明は、帯域幅要求だけでなく、ジッタ、パケット損失、使用されるスケジューラ等の他のパラメータを考慮するように拡張可能である。
【００５０】
本発明を好ましい態様で実施するにはいくつもの可能性がある。このためには、一方で請求項１に従属する諸請求項を参照しつつ、他方で図面により例示された本発明の好ましい実施形態についての以下の説明を参照されたい。図面を用いて本発明の好ましい実施形態を説明する際には、本発明の教示による好ましい実施形態一般およびその変形例について説明する。
【図面の簡単な説明】
【００５１】
【図１】本発明によるネットワークへのフローの受付を制御する方法の一実施形態による予約の交わりの行列の例を示す図である。
【図２】本発明による拡張ディオファントス法に対する交わりの解のツリーを例示する図である。
【図３ａ】アルゴリズム性能比較を例示するグラフである。
【図３ｂ】アルゴリズム性能比較を例示するグラフである。
【図４】ＩＥＥＥ８０２．１６ｊマルチホップリレーの場合を例示する図である。
【発明を実施するための形態】
【００５２】
ヒューリスティック解法およびディオファントス解法の両方に対して指摘した実現可能性の問題を考慮して、本発明の実施形態では、ディオファントス法の拡張（以下、Ｅ−ディオファントス法という）を提示する。これは、Ａ（ｔ）の最大値を求める際に、ディオファントス解法と同じ精度を、はるかに低い計算コストで達成する。
【００５３】
提案するＥ−ディオファントス解法では、最初に、ディオファントス法の場合と全く同様に、考慮対象の予約のすべてのペアの間の交わりの集合を求める。このステップの後、求められた交わりのすべての集合に対して再帰的にプロセスを反復する代わりに、結果を、１０個の予約の例の場合に図１に示すような、予約の交わりの行列に構造化する。この交わりの行列に基づいて、求められた解の間の交わりの集合の残部を、各交わりに含まれる予約に関して得られる情報に基づいて導出する。以下、設計したＥ−ディオファントスアルゴリズムまたは方法を可能にする定理および証明を提供する。
【００５４】
Ａ．交わりの２個の集合の交わり
定理１：求められた交わりの集合の任意のペアに対して、両方の解が１つの予約を共有し、他の２つの予約が互いに交わるとき、それらの集合は互いに交わる。
【００５５】
証明：予約ｉおよびｊに対して、次のように定義される交わりの集合が存在するとする。
【数９】
ここで、最小のｎｉ，ｎｊ∈Ｚは次式を満たす。
【数１０】
また、予約ｊおよびｋに対して、次のように定義される交わりの別の集合が存在するとする。
【数１１】
ここで、最小のｎｊ，ｎｋ∈Ｚは次式を満たす。
【数１２】
【００５６】
求められた両方の交わりの集合の間の交わりの集合は、ｎｉｊ，ｎｊｋ∈Ｚの集合が次式を満たす場合に存在する。
【数１３】
【００５７】
ｔｉｊおよびｔｊｋがそれぞれｔｊ＋ｎｊ・Ｔｊおよびｔｊ＋ｎ′ｊ・Ｔｊと表せることを考慮すると、式（１３）を次のように展開することができる。
【数１４】
【００５８】
これは、次のようにも表すことができる。
【数１５】
【００５９】
そこで、
【数１６】
および
【数１７】
であるので、予約ｉとｋが交わる場合には、式（１５）の条件が成り立つようなｎｉｊ，ｎｊｋ∈Ｚに対して解が存在することが確かめられる。そこで、予約ｉ、ｊおよびｋに対して結果として得られる交わりの集合が次のように定義される。
【数１８】
【００６０】
Ｂ．交わりのＮ＋１個の集合の交わり
定理２：求められた交わりの任意の集合に対して、交わりの両方の集合に含まれるすべての予約が互いに交わるとき、かつそのときに限り、その集合は交わりの別の集合と交わる。
【００６１】
証明：次のように定義される交わりのＮ個の集合の交わりの集合を仮定する。
【数１９】
【００６２】
なお、交わりの集合に対する記法は、読みやすくするために簡略化して、予約の任意のペアの交わりの集合を、関連する２つの予約の代わりに単一の下付き添字で示している。
【００６３】
交わりの追加的な集合ＩＮ＋１がＩＮと交わるためには、次式を満たすようなｎＮ，ｎＮ＋１∈Ｚの集合が存在しなければならない。
【数２０】
【００６４】
ここで、次を考慮する。
【数２１】
【００６５】
すると、次式のとき、かつそのときに限り、交わりの集合ＩＮ＋１はＩＮと交わる。
【数２２】
【００６６】
Ｃ．Ｅ−ディオファントスアルゴリズム
アルゴリズム３：システムにすでに受け入れられているＮ個の予約の集合について、対応する開始時刻ｔ＝（ｔ１...ｔＮ）、周期Ｔ＝（Ｔ１...ＴＮ）および要求Ｂ＝（Ｂ１...ＢＮ）を考慮して、開始時刻ｔＮ＋１、周期ＴＮ＋１および要求ＢＮ＋１の新たな予約ｒＮ＋１に対する最大リソース要求を求めるためのＥ−ディオファントスアルゴリズム
1: それぞれの新たな予約要求に対して実行される呼び出し
2: for i = 1 to N+1 do
3: for j = i+1 to N+1 do
4: if solution_exists(ｔｉ,ｔｊ,Ｔｉ,Ｔｊ) then
5: intersections ← find_inters_dioph(ｔｉ,ｔｊ,Ｔｉ,Ｔｊ)
6: end if
7: end for
8: end for
9: intersections ← group_intersections(intersections)
10: m_inters = compute_matrix_inters(intersections)
11: for i = 1 to N+1 do
12: solutions_tree ← compute_inters_inters(m_inters, i)
13: end for
14: if find_maximum(solutions_tree,Ｂ)≦Ｃａｖ then
15: return accept_request(ｒＮ＋１)
16: else
17: return reject_request(ｒＮ＋１)
18: end if
【００６７】
アルゴリズム３は、Ｅ−ディオファントス解法が従うステップの詳細を示している。アルゴリズムの最初の部分では、交わりの第１の集合を求めているが、これはディオファントスアルゴリズムと同一である。交わりの第１の集合がいったん求められたら、交わりの行列が計算される。この操作は、アルゴリズム３における関数compute_matrix_inters(.)に対応する。図１は、１０個の予約の集合に対して求められた交わりの行列の例を示している。このような交わりの行列は、予約の各ペアごとに、アルゴリズムの最初の部分で得られた交わりの集合を単にたどるだけで得ることができる。
【００６８】
交わりの行列に基づいて、Ｅ−ディオファントスアルゴリズムは、各予約ごとに交わりの行列をたどり、定理１および２を適用することによって不能解を捨てることにより、追加的な交わりの残部を求める。この操作は、関数compute_matrix_inters(.)に対応し、いわゆる解のツリー（solutions_tree）を生じる。図２は、図１に示した交わりの行列に基づいて求められた解のツリーを例示している。スペースの制限から、それぞれの第２レベル分枝について１つの解だけを示している。例として、予約１の場合、予約２を有する解の分枝はない。というのは、交わりの行列によれば、予約１は予約２と交わらないからである。解の分枝１→３→４の場合、予約５の分枝への継続はやはり捨てられる。というのは、予約３は５と交わらないからである。
【００６９】
明らかに、アルゴリズムの計算負荷をさらに低減するために、解のツリーの完全な探索に対する最適化が可能である。例えば、交わりの行列に基づいて、探索すべき解の分枝は、可能な最大値による降順で順序づけされてもよく、完全な探索を必要とせずに解が見つかるときには、探索を終了してもよい。別の最適化法として、帯域幅要求Ｂｉを任意に選択された帯域幅要求Ｂｒｅｆの倍数としてモデル化してもよい。この場合、Ｂｒｅｆよりも大きい予約を［Ｂｉ／Ｂｒｅｆ］個の予約としてモデル化すれば、アルゴリズムは、実際の帯域幅要求の要求値を考慮する必要はなく、交わりの総数のみを考慮すればよい。
【００７０】
Ｄ．アルゴリズム性能比較
最悪の場合、ヒューリスティック法、ディオファントス法およびＥ−ディオファントス法の間の性能差を検証・評価するため、これらのアルゴリズムをＭＡＴＬＡＢで実装し、以下の実験を実行した。その結果を図３にまとめる。１０〜１００個の予約を有するシステムを考え、各予約ごとにｔｉおよびＴｉを一様分布からランダムに選択した。一様分布の範囲は、考慮される粒度に応じて選択した。すなわち、粒度１の場合は１〜１００、粒度５の場合は１〜２０、粒度１０の場合は１〜１０とした。例示のため、Ｂｉはすべての場合に１とした。
【００７１】
図３ａは、それぞれのアプローチによって要求される最大リソース数の推定値の間の差を示している。観察できるように、差は、予約数の増大とともに増大するだけでなく、ディオファントス法およびＥ−ディオファントス法以外のすべてのアプローチでは、より大きい粒度を考慮するときに差が増大する。ディオファントス法の値が厳密解なので基準にとると、予想されるように、最悪の場合の解は、実際の値との差が最大となり、差は３００％を超える。使用される実際の要求と比べてこのように大きい差があると、明らかに、ＱｏＳ要求付きのサービスによるネットワークの使用が、可能な使用量よりもはるかに低くなるので、ネットワーク事業者にとっては、可能な収入が低くなる。ヒューリスティック法の場合、粒度が大きいほど、現実の実装において考慮可能な最大のＬＣＭ値（われわれのシステムでは１０７）における制限のために、実際の値からの差が大きくなる。さらに悪いことに、推定値は実際の値を下回るので、受付制御目的で使用すると、ネットワークにおけるＱｏＳ保証を損なう可能性がある。他方、Ｅ−ディオファントス法の推定値は、ディオファントス法の推定値に常に等しいことから、定理１および２の正しさが確認される。
【００７２】
図３ｂは、計算負荷における対応する差をヒューリスティック法と比べて示している。ヒューリスティック法は実装が簡単なので、ここでは基準としてとっている。最悪の場合は考慮していない。というのは、その計算負荷は明らかに無視できるほどであるが、図３ａに示したように、使用される実際のリソースの推定値もまた、ＱｏＳ要求付きのサービスによるネットワークの使用がはるかに低くなるからである。図から観察できるように、ディオファントス解法は、厳密ではあるが、考慮されている代替解法の計算負荷をはるかに超えるので、実際には実施可能でない。例えば、３０個の予約の場合、２×クアッドコアのシミュレーションサーバにおいてかかった計算時間は１０００秒を超えた。考慮される最低の粒度の場合、ヒューリスティック法は、精度の損失なしでＥ−ディオファントス解法を計算時間において明らかに凌駕する。しかし、考慮される粒度が増大すると、Ｅ−ディオファントス法の性能は、ほとんどの場合、ヒューリスティック法よりも３桁程度高速であると同時に、予想される最大要求の厳密な推定値が得られるのに対して、ヒューリスティック法は、特に粒度１の場合に、明らかに過小推定となる。これらの結果に基づいて、以下、本明細書では、提案するＥ−ディオファントス解法の分析のみに集中する。
【００７３】
Ｅ．マルチホップリレーへの拡張
Ｅ−ディオファントス解法は、マルチホップリレーの場合に対するＩＥＥＥ８０２．１６ｊ標準に適用可能となるように拡張することができる。以下、提案するＥ−ディオファントス法のマルチホップリレーへの拡張について詳細に説明する。
【００７４】
ＩＥＥＥ８０２．１６ｊのマルチホップリレーの場合、ＭＲ−ＢＳまたはＲＳから次のＲＳへの入来フローは、Ｅ−ディオファントス解法によって、ＱｏＳ要求付きの追加フローと全く同様に考えることができる。このため、Ｅ−ディオファントス解法自体は、それを使用する受付制御アルゴリズム以外の拡張を必要としない。新たなフローがシステムに入ることを要求しているとき、受付制御アルゴリズムは、ダウンリンク要求の場合には宛先、またはアップリンク要求の場合にはソースが、ＲＳに関連しているかどうかを判定すべきである。そしてそのような場合、以下のようにして、最大容量要求計算のためにそのフローを考慮する。
【００７５】
まず、２つの場合を区別する必要がある。新たなフロー要求に関連するＲＳがない場合、Ｅ−ディオファントス解法を直接適用することができる。他方、ＲＳが関連している場合、その宛先までのフローパスに含まれる基地局およびリレー局に対して、最大容量要求の増大をチェックする必要がある。後者の場合、新たなフローデータパス内の最初の基地局またはＲＳからローカルＷｉＭＡＸネットワーク内の最後のＭＲ−ＢＳまたはＲＳまで、新たな最大容量要求を順次計算する。そして、いずれかのステップで、利用可能な最大容量を超えるとみなされる場合、要求を拒否する。関連する各ＭＲ−ＢＳおよびＲＳでの新たな最大容量要求を計算するため、システムにすでに受け入れられているフローと、新たなフローとの集合を考慮する必要がある。この際、それぞれの次のＭＲ−ＢＳまたはＲＳへのフローの到着が、ＭＲ−ＢＳおよびＲＳの処理能力に従って、ＷｉＭＡＸフレーム継続時間Ｎｆの整数倍だけ増大することを考慮する。図４に、アップリンクおよびダウンリンクの通信を有するマルチホップリレーの場合の例を示す。
【００７６】
ダウンリンク
ダウンリンクの場合、ＷｉＭＡＸコアネットワークから来るＱｏＳ要求付きのフローの集合を考える。それらの予約は、ＲＣＮ＝｛ｒＣＮ１，ｒＣＮ２，...，ｒＣＮＮ｝で定義される。それぞれの後続のＲＳに対して、受け入れを要求している新たなフローを含めて、その宛先までのフローパスにおける各リレーによって考慮されるべきフローの集合ＲＲＳＭは、次のように表すことができる。
【数２３】
そして、リレーＲｉ∈ｉ＝１..Ｍにおける任意の予約ｊ∈Ｒに対する周期的な帯域幅要求は、次のように表すことができる。
【数２４】
【００７７】
こうして、Ｅ−ディオファントス解法は、各ＲＳにおいて、予約の対応する部分集合ＲＣＮおよび増大する開始時刻ｔｊ＋ｉ・Ｎｆを考慮することによって、最大予想リソース要求を取得することに適用可能である。
【００７８】
アップリンク
アップリンクの場合は、ダウンリンクの場合とは異なり、ソースからそれぞれの次ホップにおいて、最大リソース要求を求めるために考慮すべき予約数は増大する可能性がある。リレーｉに関連するＳＳによって発信されたＱｏＳ要求付きのフローの集合を考える。それらの予約は、ＲＳＳＲｉ＝｛ｒＳＳ１，ｒＳＳ２，...，ｒＳＳＮ｝で定義される。それぞれの後続のＲＳに対して、受け入れを要求している新たなフローを含めて、ＭＲ−ＢＳまでのフローパスにおける各リレーによって考慮されるべき予約の集合ＲＢＳは、次のように表すことができる。
【数２５】
そして、リレーＲｉ∈ｉ＝１..ＭまたはＭＲ−ＢＳ（ｉ＝Ｍ＋１）における任意の予約ｊ∈Ｒに対する周期的な帯域幅要求は、次のように表すことができる。
【数２６】
【００７９】
こうして、ダウンリンクの場合と同様に、Ｅ−ディオファントス解法は、各ＲＳおよびＭＲ−ＢＳにおいて、予約の対応する部分集合ＲＢＳおよび増大する開始時刻ｔｊ＋（ｉ−１）・Ｎｆを考慮することによって、最大予想リソース要求を取得することに適用可能である。
【００８０】
上記の説明および添付図面の記載に基づいて、当業者は本発明の多くの変形例および他の実施形態に想到し得るであろう。したがって、本発明は、開示した具体的実施形態に限定されるものではなく、変形例および他の実施形態も、添付の特許請求の範囲内に含まれるものと解すべきである。本明細書では特定の用語を用いているが、それらは総称的・説明的意味でのみ用いられており、限定を目的としたものではない。
【特許請求の範囲】
【請求項１】
ネットワーク、特にＷｉＭＡＸ（Worldwide Interoperability for Microwave Access）ネットワークへのフローの受付を制御する方法において、リソースの少なくとも１つのＱｏＳ（サービス品質）予約付きでネットワークに入ることを要求しているフローが受付可能かどうかを検査するために、ネットワークのリンク内および／またはネットワーク内で要求される最大容量の推定が、ＱｏＳ予約のすべてのペア、すなわち、リンク内および／またはネットワーク内ですでに受け入れられているＱｏＳ予約と、フローによって要求された前記少なくとも１つのＱｏＳ予約と、の間の交わりの第１の集合を求めることによって実行され、
ＱｏＳ予約の交わりの行列を作成することにより、求められた交わりの集合を構造化し、
前記行列に基づき、各交わりに含まれるＱｏＳ予約に関して得られる情報に基づいて、求められた交わりの間の交わりの集合の残部を導出する
ことを特徴とする、ネットワークへのフローの受付を制御する方法。
【請求項２】
要求される容量が帯域幅要求に関することを特徴とする請求項１に記載の方法。
【請求項３】
行列の作成が、予約の各ペアごとに、求められた交わりの集合をたどることによって実行されることを特徴とする請求項１または２に記載の方法。
【請求項４】
行列の作成が、線型ディオファントス方程式論を用いて実行されることを特徴とする請求項１ないし３のいずれか１項に記載の方法。
【請求項５】
交わりの集合の残部が、各予約ごとに交わりの行列をたどり、以下の定理１および２、すなわち、
定理１：求められた交わりの集合の任意のペアに対して、両方の解が１つの予約を共有し、他の２つの予約が互いに交わるとき、それらの集合は互いに交わる
定理２：求められた交わりの任意の集合に対して、交わりの両方の集合に含まれるすべての予約が互いに交わるとき、かつそのときに限り、その集合は交わりの別の集合と交わる
を適用することによって不能解を捨てることにより、導出されることを特徴とする請求項１ないし４のいずれか１項に記載の方法。
【請求項６】
交わりの集合の残部の導出が、解の分枝を有する解ツリーに従うことを特徴とする請求項１ないし５のいずれか１項に記載の方法。
【請求項７】
解の分枝が、可能な最大値による降順で順序づけされ、分枝の完全な探索を必要とせずに解が見つかるときには、分枝の探索を終了することを特徴とする請求項６に記載の方法。
【請求項８】
解の分枝が、精度と計算時間とのトレードオフのための特定のポリシーに従って部分的にのみ探索され、例えば、最大容量を含む確率が最大となるような、全分枝数の所定の割合の分枝のみを探索することを特徴とする請求項６に記載の方法。
【請求項９】
帯域幅要求Ｂｉを所定の帯域幅要求Ｂｒｅｆの倍数としてモデル化し、Ｂｒｅｆよりも大きい予約をＢｉ／Ｂｒｅｆ個の予約としてモデル化することを特徴とする請求項１ないし８のいずれか１項に記載の方法。
【請求項１０】
マルチホップリレーの場合に、ＭＲ−ＢＳ（マルチリレー基地局）またはＲＳ（リレー局）から次のＲＳへの入来フローが、リソースの少なくとも１つのＱｏＳ予約付きでネットワークに入ることを要求しているフローとみなされることを特徴とする請求項１ないし９のいずれか１項に記載の方法。
【請求項１１】
フローがネットワークに入ることを要求しているとき、該方法は、ダウンリンク要求の場合には宛先、またはアップリンク要求の場合にはソースが、ＲＳに関連しているかどうかを判定するステップを有し、そのような場合、該方法は、最大容量の推定のために該フローを考慮するステップをさらに有することを特徴とする請求項１０に記載の方法。
【請求項１２】
ＲＳが関連している場合、ソースからその宛先までのフローパスに含まれるすべてのＢＳおよびＲＳに対して、要求される最大容量の推定が実行されることを特徴とする請求項１０または１１に記載の方法。
【請求項１３】
要求される最大容量の推定が、１ステップずつ順次実行されることを特徴とする請求項１２に記載の方法。
【請求項１４】
いずれかのステップで、要求される最大容量が最大利用可能容量の値を超えた場合に、要求が拒否されることを特徴とする請求項１３に記載の方法。
【請求項１５】
各追加ステップまたはホップで、ＭＲ−ＢＳおよび／またはＲＳの処理能力に従って、ＷｉＭＡＸフレーム継続時間の整数倍または他の任意数だけ、予約開始時刻を増大させることを特徴とする請求項１０ないし１４のいずれか１項に記載の方法。
【請求項１６】
リンク内および／またはネットワーク内の最大利用可能容量の値が、事業者によって、または、事業者ポリシーに基づいて規定されることを特徴とする請求項１ないし１５のいずれか１項に記載の方法。
【請求項１７】
ネットワーク、好ましくは請求項１ないし１６のいずれか１項に記載の方法を実行するネットワーク、特にＷｉＭＡＸ（Worldwide Interoperability for Microwave Access）ネットワークにおいて、リソースの少なくとも１つのＱｏＳ（サービス品質）予約付きでネットワークに入ることを要求しているフローが受付可能かどうかを検査するために、ネットワークのリンク内および／またはネットワーク内で要求される最大容量の推定が、ＱｏＳ予約のすべてのペア、すなわち、リンク内および／またはネットワーク内ですでに受け入れられているＱｏＳ予約と、フローによって要求された前記少なくとも１つのＱｏＳ予約と、の間の交わりの第１の集合を求めることによって実行され、該ネットワークが、
ＱｏＳ予約の交わりの行列を作成することにより、求められた交わりの集合を構造化し、
前記行列に基づき、各交わりに含まれるＱｏＳ予約に関して得られる情報に基づいて、求められた交わりの間の交わりの集合の残部を導出する手段
を備えたことを特徴とするネットワーク。
【請求項１】
ネットワーク、特にＷｉＭＡＸ（Worldwide Interoperability for Microwave Access）ネットワークへのフローの受付を制御する方法において、リソースの少なくとも１つのＱｏＳ（サービス品質）予約付きでネットワークに入ることを要求しているフローが受付可能かどうかを検査するために、ネットワークのリンク内および／またはネットワーク内で要求される最大容量の推定が、ＱｏＳ予約のすべてのペア、すなわち、リンク内および／またはネットワーク内ですでに受け入れられているＱｏＳ予約と、フローによって要求された前記少なくとも１つのＱｏＳ予約と、の間の交わりの第１の集合を求めることによって実行され、
ＱｏＳ予約の交わりの行列を作成することにより、求められた交わりの集合を構造化し、
前記行列に基づき、各交わりに含まれるＱｏＳ予約に関して得られる情報に基づいて、求められた交わりの間の交わりの集合の残部を導出する
ことを特徴とする、ネットワークへのフローの受付を制御する方法。
【請求項２】
要求される容量が帯域幅要求に関することを特徴とする請求項１に記載の方法。
【請求項３】
行列の作成が、予約の各ペアごとに、求められた交わりの集合をたどることによって実行されることを特徴とする請求項１または２に記載の方法。
【請求項４】
行列の作成が、線型ディオファントス方程式論を用いて実行されることを特徴とする請求項１ないし３のいずれか１項に記載の方法。
【請求項５】
交わりの集合の残部が、各予約ごとに交わりの行列をたどり、以下の定理１および２、すなわち、
定理１：求められた交わりの集合の任意のペアに対して、両方の解が１つの予約を共有し、他の２つの予約が互いに交わるとき、それらの集合は互いに交わる
定理２：求められた交わりの任意の集合に対して、交わりの両方の集合に含まれるすべての予約が互いに交わるとき、かつそのときに限り、その集合は交わりの別の集合と交わる
を適用することによって不能解を捨てることにより、導出されることを特徴とする請求項１ないし４のいずれか１項に記載の方法。
【請求項６】
交わりの集合の残部の導出が、解の分枝を有する解ツリーに従うことを特徴とする請求項１ないし５のいずれか１項に記載の方法。
【請求項７】
解の分枝が、可能な最大値による降順で順序づけされ、分枝の完全な探索を必要とせずに解が見つかるときには、分枝の探索を終了することを特徴とする請求項６に記載の方法。
【請求項８】
解の分枝が、精度と計算時間とのトレードオフのための特定のポリシーに従って部分的にのみ探索され、例えば、最大容量を含む確率が最大となるような、全分枝数の所定の割合の分枝のみを探索することを特徴とする請求項６に記載の方法。
【請求項９】
帯域幅要求Ｂｉを所定の帯域幅要求Ｂｒｅｆの倍数としてモデル化し、Ｂｒｅｆよりも大きい予約をＢｉ／Ｂｒｅｆ個の予約としてモデル化することを特徴とする請求項１ないし８のいずれか１項に記載の方法。
【請求項１０】
マルチホップリレーの場合に、ＭＲ−ＢＳ（マルチリレー基地局）またはＲＳ（リレー局）から次のＲＳへの入来フローが、リソースの少なくとも１つのＱｏＳ予約付きでネットワークに入ることを要求しているフローとみなされることを特徴とする請求項１ないし９のいずれか１項に記載の方法。
【請求項１１】
フローがネットワークに入ることを要求しているとき、該方法は、ダウンリンク要求の場合には宛先、またはアップリンク要求の場合にはソースが、ＲＳに関連しているかどうかを判定するステップを有し、そのような場合、該方法は、最大容量の推定のために該フローを考慮するステップをさらに有することを特徴とする請求項１０に記載の方法。
【請求項１２】
ＲＳが関連している場合、ソースからその宛先までのフローパスに含まれるすべてのＢＳおよびＲＳに対して、要求される最大容量の推定が実行されることを特徴とする請求項１０または１１に記載の方法。
【請求項１３】
要求される最大容量の推定が、１ステップずつ順次実行されることを特徴とする請求項１２に記載の方法。
【請求項１４】
いずれかのステップで、要求される最大容量が最大利用可能容量の値を超えた場合に、要求が拒否されることを特徴とする請求項１３に記載の方法。
【請求項１５】
各追加ステップまたはホップで、ＭＲ−ＢＳおよび／またはＲＳの処理能力に従って、ＷｉＭＡＸフレーム継続時間の整数倍または他の任意数だけ、予約開始時刻を増大させることを特徴とする請求項１０ないし１４のいずれか１項に記載の方法。
【請求項１６】
リンク内および／またはネットワーク内の最大利用可能容量の値が、事業者によって、または、事業者ポリシーに基づいて規定されることを特徴とする請求項１ないし１５のいずれか１項に記載の方法。
【請求項１７】
ネットワーク、好ましくは請求項１ないし１６のいずれか１項に記載の方法を実行するネットワーク、特にＷｉＭＡＸ（Worldwide Interoperability for Microwave Access）ネットワークにおいて、リソースの少なくとも１つのＱｏＳ（サービス品質）予約付きでネットワークに入ることを要求しているフローが受付可能かどうかを検査するために、ネットワークのリンク内および／またはネットワーク内で要求される最大容量の推定が、ＱｏＳ予約のすべてのペア、すなわち、リンク内および／またはネットワーク内ですでに受け入れられているＱｏＳ予約と、フローによって要求された前記少なくとも１つのＱｏＳ予約と、の間の交わりの第１の集合を求めることによって実行され、該ネットワークが、
ＱｏＳ予約の交わりの行列を作成することにより、求められた交わりの集合を構造化し、
前記行列に基づき、各交わりに含まれるＱｏＳ予約に関して得られる情報に基づいて、求められた交わりの間の交わりの集合の残部を導出する手段
を備えたことを特徴とするネットワーク。
【図１】
【図２】
【図３ａ】
【図３ｂ】
【図４】
【図２】
【図３ａ】
【図３ｂ】
【図４】
【公表番号】特表２０１３−５０４２３３（Ｐ２０１３−５０４２３３Ａ）
【公表日】平成２５年２月４日（２０１３．２．４）
【国際特許分類】
【出願番号】特願２０１２−５２７２５０（Ｐ２０１２−５２７２５０）
【出願日】平成２２年９月１４日（２０１０．９．１４）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／００５６１７
【国際公開番号】ＷＯ２０１１／０２９６２７
【国際公開日】平成２３年３月１７日（２０１１．３．１７）
【出願人】（５０８３４２１８３）エヌイーシー ヨーロッパ リミテッド (101)
【氏名又は名称原語表記】ＮＥＣ ＥＵＲＯＰＥ ＬＴＤ．
【Ｆターム（参考）】
【公表日】平成２５年２月４日（２０１３．２．４）
【国際特許分類】
【出願日】平成２２年９月１４日（２０１０．９．１４）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／００５６１７
【国際公開番号】ＷＯ２０１１／０２９６２７
【国際公開日】平成２３年３月１７日（２０１１．３．１７）
【出願人】（５０８３４２１８３）エヌイーシー ヨーロッパ リミテッド (101)
【氏名又は名称原語表記】ＮＥＣ ＥＵＲＯＰＥ ＬＴＤ．
【Ｆターム（参考）】
[ Back to top ]