(57)【要約】  効率的なポリサーベースの重み付け均等化帯域幅分配システムが開示される。このシステムは複数のポリサーおよび単一のキューに基づいている。公平性を実現するために、パケットをキューに入れる速度は適応的に制御される。具体的には、まずキュー占有率が決定され、次にそれを使用して減衰（Ａｔｔｎ）値を計算する。この値に各ポリサーの超過情報速度（ＥＩＲ）が乗じられ、順守されるべき新しいＥＩＲを得る。
2009534885.tif 000002
【特許請求の範囲】
【請求項１】
重み付け均等化ポリシングを実行することにより、複数のデータフローの帯域幅を公平に分配する方法であって、
複数のソースから生じる複数のデータパケットをキュー構造で受け取るステップ
を含み、
キュー構造（２００）が、１個のデータキュー（２２０）に接続された複数のポリサー（２１０）を備え、前記ポリサーのそれぞれが順守されるべきそれぞれの超過情報速度（ＥＩＲ）が割り当てられたことを特徴とし、
前記キュー（２２０）について減衰（Ａｔｔｎ）値を計算するステップであって、前記減衰値が前記キュー（２２０）へのポリサー（２１０）について現在の輻輳を決定するステップと、
前記減衰値を使用して前記ポリサー（２１０）の超過情報速度（ＥＩＲ）を適応的に変更するステップと
によりさらに特徴づけられる、方法。
【請求項２】
前記Ａｔｔｎ値を計算するステップが、
キューの占有率をモニタするステップと、
キュー占有率および減衰関数を使用して、前記Ａｔｔｎ値を決定するステップと
をさらに含む、請求項１に記載の方法。
【請求項３】
キュー占有率をモニタするステップが、
キューの平均長を測定するステップ
を含む、請求項２に記載の方法。
【請求項４】
前記ＥＩＲを適応的に変更するステップが、
複数のポリサー（２１０）で前記減衰値を受け取るステップと、
前記複数のポリサーのそれぞれにより順守されるべき新しいＥＩＲ値を計算するステップと
をさらに含む、請求項１に記載の方法。
【請求項５】
通信ネットワークにおける複数のデータフローの帯域幅を公平に分配する重み付け均等化ポリシングシステムであって、
順守されるべき超過情報速度をそれぞれが適応的に変更することができ、単一のキュー（２２０）に接続されており、異なるソースに結合されることが可能であり、前記複数のソースのそれぞれが異なる優先順位を割り当てられている、複数のポリサー（２１０）と、
前記キュー（２２０）および前記複数のポリサー（２１０）に結合された帯域幅調整モジュール（２３０）であって、前記キュー（２２０）へのポリサー（２１０）について現在の輻輳を決定する、前記キュー（２２０）の減衰（Ａｔｔｎ）値を計算することができ、前記ポリサー（２１０）が前記減衰値（Ａｔｔｎ）を使用してそれらの超過情報速度（ＥＩＲ）を適応的に変更するように構成された、帯域幅調整モジュール（２３０）と
を備える、重み付け均等化ポリシングシステム。
【請求項６】
優先順位がより高いキューのＡｔｔｎ値が、少なくとも優先順位がより低いキューのＡｔｔｎ値に基づいている、請求項５に記載のＷＦＰシステム。
【請求項７】
前記Ａｔｔｎ値がそれぞれのキューにおける複数の認定情報速度（ＣＩＲ）パケットの数に応じている、請求項５に記載のＷＦＰシステム。
【請求項８】
前記複数のポリサーのそれぞれのＥＩＲが前記Ａｔｔｎ値に線形比例して変更される、請求項５に記載のＷＦＰシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に通信ネットワークに関し、より具体的には通信ネットワークにおけるデータトラフィックのキューイングについての技術に関する。
【背景技術】
【０００２】
無線ネットワークへのアクセスおよびその使用は、ビジネス上の、社会的な、およびレクリエーション的な用途にとってますます重要になり、普及してきている。無線ネットワークの使用者は今では、音声およびデータの両方の通信について無線ネットワークに頼っている。さらに、サービスおよび性能の拡大、ならびにインターネットサーフィンなどの活動のための帯域幅の拡大の両方を要求する使用者が絶えず増加している。新しいサービスと帯域幅拡大のための要求に取り組んで応えるために、無線通信業界は、サービスの数およびそれらの無線ネットワークのスループットを改善しようと絶えず努めている。付加的なサービスおよびより高い帯域幅を提供するのに必要なインフラストラクチャを拡大および改善することは、コストを要し、人的資源を集中させる事業である。さらに、高い帯域幅のデータストリームが、リアルタイムのオーディオビジュアルのダウンロード、および２人以上の間でのライブのオーディオビジュアル通信などの機能を支援するよう消費者によって最終的に要求されるであろう。将来は、それゆえ現在のシステムをアップグレードしようとするのではなく、次世代無線システムを導入することが必要になり、および／またはそうすることがより高い費用効果をもたらすであろう。
【０００３】
この目的のために、無線通信業界は、それが依拠する技術の機能を改善し続け、次世代システムの配備によりその顧客にとって利用可能になるようにすることを意図している。無線の顧客の開発要求を満たすように設計されている次世代標準のプロトコルは、第３世代移動体通信システムの標準化プロジェクト（３ＧＰＰ、３ｒｄ  Ｇｅｎｅｒａｔｉｏｎ  Ｐａｒｔｎｅｒｓｈｉｐ  Ｐｒｏｊｅｃｔ）により標準化されつつある。このプロトコルのセットは、全体として国際移動体通信システム（ＵＭＴＳ、Ｕｎｉｖｅｒｓａｌ  Ｍｏｂｉｌｅ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｙｓｔｅｍ）として知られている。
【０００４】
インターネットの現在の状況では、保証された帯域幅の公平性および複数のレベルの待ち時間に対する支援という問題点は、ますます重要になってきている。
【０００５】
保証された帯域幅の公平性は、いわゆる「均等化キューイング（Ｆａｉｒ  Ｑｕｅｕｉｎｇ）」アルゴリズムを使用して一般に実現される。これらのアルゴリズムは、ある一定のリンク（または仮想リンク）の帯域幅がその多様なフローの間で公平に配分されることを保証する。均等化キューイングアルゴリズムは、均等化キューイング（または帯域幅）スケジューラを使用するネットワークシステムに組み込まれる。これらのスケジューラは、挙動の好ましくないソースの存在下においてさえ輻輳を制御しようと試み、その結果、パケットを十分に高速にゲートウェイに送る単一のソースが、出力ラインの任意に高い部分の帯域幅を取り込むことができない。帯域幅の保証を行うことは重要であるが、待ち時間が重要なトラフィックフロー（Ｖｏｉｃｅ  Ｏｖｅｒ  ＩＰおよびＶｉｄｅｏ  Ｏｖｅｒ  ＩＰなど）が経験する待ち時間を可能な限り少なくすることもまた重要である。待ち時間が重要なフローが経験する待ち時間が少なくなるようにトラフィックフローを優先順位付けすることは、優先順位（または待ち時間）スケジューラにより現在行われている。
【０００６】
従来のネットワークソリューションは、均等化キューイングおよび優先順位スケジューリングの両方を解決しようとしてきており、この２つの問題の間の固有の相反関係にもかかわらず、何らかの形で両方の機能をネットワークシステムに組み込むことに成功してきた。
【０００７】
重み付け均等化キューイング（Ｗｅｉｇｈｔｅｄ  Ｆａｉｒ  Ｑｕｅｕｉｎｇ，ＷＦＱ）は、例えば米国特許第６８１０４２６号明細書または米国特許第６８５０５４０号明細書で開示されているように、よく知られているフローベースのキューイング技術である。ＷＦＱは応答時間を減少させるために、キューの先頭への対話式トラフィックを同時にスケジューリングして、高い帯域幅のフローの間の残りの帯域幅を公平に分配する。
【０００８】
図１は、１１０−１から１１０−ＮのＮ個のキューを含む、先行技術における従来のＷＦＱシステム１００を示す。各キュー１１０は単一のソース（または接続）を供給し、それぞれの重みを割り当てられている。それぞれのキュー１１０を離れる各パケットは出力チャネル１２０に直接送られる。ＷＦＱシステム１００において実行されるスケジューリング方法は、キュー１１０におけるパケットの待機時間が常にキューの重みに比例することを確実にする。
【０００９】
例えば、ＷＦＱシステムは３個のキューＱ１、Ｑ２およびＱ３を有し、重みＷ１  ＝  ５、Ｗ２  ＝  ２およびＷ３  ＝  ３がそれぞれに割り当てられている。出力チャネルの最大の許容できる速度は１０ＭＢ／秒である。この例示のシステムでは、全てのキューがパケットを待機させている場合、Ｑ２およびＱ３は２ＭＢ／秒および３ＭＢ／秒の保証された帯域幅をそれぞれ受け取り、Ｑ１は５ＭＢ／秒の保証された帯域幅を受け取る。Ｑ１がどのパケットも待機させていない場合、余剰帯域幅は５ＭＢ／秒に等しい。ＷＦＱシステムでは、余剰帯域幅は、パケットを待機させているキューの対応づけられた重みに比例して再分配される。すなわち、キューＱ１がパケットを待機させていないとき、余剰帯域幅はキューＱ２およびＱ３に比例して再分配され、その結果、それらはここで４ＭＢ／秒および６ＭＢ／秒の帯域幅をそれぞれ受け取る。
【００１０】
ＷＦＱ技術の１つの利点はエンドツーエンド遅延の保証であり、すなわち各パケットはストリームにおける各パケットフローについてある一定の速度を保証される。別の利点は、フローが特に突発的なアイドル時間であるとき、容量の使用が抑えられることである。このような場合、作業保存特性を保持するように、ＷＦＱ技術により未使用の帯域幅の再分配が容易になる。
【００１１】
米国特許第６１９２０３２号明細書は、ビデオフレームパケット送信速度を調整するトラフィックスムーザと、ネットワークに対するビデオフレームパケットの入力を制御するトラフィックポリシング装置と、トラフィックスムーザと連動して機能する、ポリシング装置のための機構を提供する送信速度減衰器とを有するビデオフレーム送信機を記載している。一般に、ポリシング装置およびトラフィックスムーザは別々に機能し、パケットの優先順位を落とす原因となる。米国特許第６１９２０３２号明細書の教示によれば、ビデオフレームの送信速度を減少させることにより、ポリシング装置はより多くのトークンを作り出すことが可能になり、その結果、ビデオフレーム内の全てのパケットがどの優先順位も落とさずに送信される。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
ＷＦＱ技術の欠点はその実施においてなおも残っている。従来のＷＦＱシステムは複数のキューに基づいており、この設定はコストがかかり複雑である。さらに、キューベースのシステムは各パケットの状態を保持することを必要とする。この要件はほとんどの通信ネットワークに準拠しない。それゆえ、効率的な重み付け均等化帯域幅分配システムを提供することは有益であろう。
【課題を解決するための手段】
【００１３】
以下に述べるこれらおよび他の目的は、請求項１に記載の重み付け均等化ポリシング方法により、および請求項５に記載の重み付け均等化ポリシング（ＷＦＰ）システムにより実現される。有益な改善は従属請求項に記載される。
【発明を実施するための最良の形態】
【００１４】
本発明は、重み付け均等化帯域幅分配ができる効率的な重み付け均等化ポリシング（ＷＦＰ）システムを開示する。このシステムは複数のポリサー（ｐｏｌｉｃｅｒ）および単一のキューに基づいている。公平性を実現するために、ポリシングされるパケットの速度は適応的に制御される。
【００１５】
図２は、本発明の一実施形態を開示するＷＦＰシステム２００の非限定的で例示のブロック図を示す。ＷＦＰシステム２００は、単一のキュー２２０に接続されたＭ個のポリサー２１０−１から２１０−Ｍ、帯域幅調整モジュール２３０、および出力チャネル２４０を含む。各ポリサー２１０は入力速度（ＩｎＲａｔｅ）および最大超過情報速度（ＥＩＲｍａｘ）によりパラメータ設定される。ポリサーは、所定のあるしきい値速度より大きい瞬間的な速度でそのポリサーに到着するデータパケットを拒絶する速度制限装置である。具体的には、各ポリサー２１０は単一のデータフローを処理して、順守されるべき新しいＥＩＲを計算することができる。すなわち、それぞれのデータフローのパケットは、それらの瞬間的な速度が新しく計算されたＥＩＲに等しい速度を超えない場合、ポリサー２１０からキュー２２０に転送される。新しいＥＩＲは次の数式により計算される。
ＥｌＲｎｅｗ  ＝  Ａｔｔｎ＊ＥｌＲｍａｘ；                          （１）
【００１６】
ここで「Ａｔｔｎ」パラメータは、より詳細に以下に説明される減衰関数により決定される。ＥＩＲｍａｘはポリサーが転送できる最大の帯域幅である。実際、ＥＩＲｍａｘはＷＦＰアルゴリズムの重みを決定する、事前に設定された値である。ポリサーを通るデータパケットの流れは、ＩｎＲａｔｅを超えることができない。ポリサー２１０についての実施例は、「Ａ  Ｐｏｌｉｃｅｒ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｒｅｓｏｕｒｃｅ  Ｂｕｎｄｌｉｎｇ」という表題の、ＺｅｉｔａｋによるＰＣＴ出願第ＰＣＴ／１１２００４／００７８１号明細書で見出すことができ、この出願は共通の譲受人に譲渡されており、それが含む全てについて、本明細書に参照により組み込まれている。
【００１７】
出力チャネル２４０の出力速度は最大の許容できる速度（以下「ＲＡＴＥｍａｘ」）パラメータによって決定される。ポリサー２１０が許可する合計速度がＲＡＴＥｍａｘを超過するときは常に輻輳が発生する。帯域幅調整モジュール２３０はキュー占有率およびキュー進入速度（以下「Ｑｏｃｃ」）をモニタし、減衰関数を使用してＡｔｔｎ値を計算する。図３は減衰関数３１０の非限定的で例示のグラフを示す。見ての通り、Ａｔｔｎ値は０から１の間で変動し、ここでキュー２２０が空であるとき値は１であり、キュー２２０がいっぱいであるとき値は０である。Ａｔｔｎ値はポリサー２１０のそれぞれに送られ、ポリサー２１０のそれぞれが順守されるべきＥｌＲｎｅｗを順番に計算する。減衰関数（ＡＴ）の例示の実施形態は次のようになる。
【数１】
2009534885.tif 000003
ここでＴｈ２はキューの最大占有率（バイトでの）を決定する正規化ファクタであり、Ｔｈ１はα＊Ｔｈ２に等しいしきい値である。パラメータαは設定可能であり、例示の実施形態では０．６に設定されている。
【００１８】
ポリサーが帯域幅に基づいており、したがってポリサーは重み付け均等化キューイングをエミュレートすることができないことを、当業者には理解されたい。しかし、キュー占有率を使用して各ポリサーの帯域幅を適応的に直接制御することは、最大の許容できる速度に関して公平性を確実にする。すなわち、ポリサーの帯域幅を制御することにより、そのＥＩＲｍａｘ未満である速度で送信するソースが、未分配のトラフィックを配信し続けることが可能であり、そうでなければＥＩＲｍａｘは減少させられる。
【００１９】
図４は、本発明の一実施形態を開示する重み付け均等化キューイングを実行するための方法を説明する非限定的な流れ図４００を示す。この方法は、輻輳が検出されたときのみ適用される。Ｓ４１０でキュー２２０のＱｏｃｃ値が決定される。一実施形態において、Ｑｏｃｃはキューの平均長としてある期間にわたって計算される。このことは、パケットがキューに挿入されるかまたはキューから削除されるたびに、キューに格納されるバイトの数を測定することにより実行される。キュー長を平均することは、Ｑｏｃｃの安定した値をもたらす。Ｓ４２０で、減衰関数に基づいてＱｏｃｃを使用してＡｔｔｎ値が計算される。Ａｔｔｎ値は数式２を用いて計算されてよい。Ａｔｔｎ値がその平衡点に到達するまでわずかに変更されうることを、発明者は指摘する。次の数式が満たされるとき、この点が実現される。
【数２】
2009534885.tif 000004
別法として、輻輳がない場合は、次の数式が満たされるとき平衡点である。
【数３】
2009534885.tif 000005
Ｓ４３０で、Ａｔｔｎ値がポリサー２１０のそれぞれに送られる。Ｓ４４０で示されるように、Ａｔｔｎ値を用いて、入ってくるパケットについてＥｌＲｎｅｗを計算し、順守する。ＥｌＲｎｅｗは数式１を用いて計算されてよい。
【００２０】
以下は、本発明により実行される重み付け均等化キューイングを説明する非限定的な実施例である。図５は、キュー５２０に接続された３個のポリサー５１０−１、５１０−２、および５１０−３を含む例示のＷＦＰシステム５００を示す。ポリサー５１０−１、５１０−２、および５１０−３のそれぞれは、例えば、３０ＭＢ／秒に等しいＥＩＲｍａｘ値で設定される。ソースＡはポリサー５１０−１を介して、例えば、１０ＭＢ／秒に等しい速度でパケットを送信し、ソースＢはポリサー５１０−２を介して、例えば、２０ＭＢ／秒に等しい速度でパケットを送信し、ソースＣの出力速度は、例えば、３０ＭＢ／秒である。出力チャネル５４０のＲＡＴＥｍａｘは、例えば、３０ＭＢ／秒である。この例示の設定で輻輳が発生することは明らかである。
【００２１】
入力ソースのパケットを公平にスケジューリングするために、Ａｔｔｎ値が計算される。上述の実施例では、Ａｔｔｎ値が１／３であるとき、平衡点が実現される。この値は、ＥｌＲｎｅｗ値を計算するポリサー５１０−１、５１０−２、および５１０−３に送られる。ポリサー５１０−１、５１０−２、および５１０−３の全ての計算されたＥｌＲｎｅｗ値は１０ＭＢ／秒に等しい。ポリサー５１０は計算されたＥｌＲｎｅｗを超える速度でパケットを送信できず、それゆえポリサーは全体的にＲＡＴＥｍａｘを超える速度でパケットを配信できない。
【００２２】
Ａｔｔｎは入力ソースのトラフィック速度により適応的に変更されることに留意されたい。例えば、ソースＡがパケット送信を中断するとき、キュー５２０の長さは減少し、それゆえ新しいＡｔｔｎ値が生成される。ここで、Ａｔｔｎ値が１／２に等しいとき平衡が実現される。したがって、ポリサー５１０−１および５１０−２のＥｌＲｎｅｗ値は１０ＭＢ／秒に設定される。
【００２３】
本発明の別の実施形態では、本明細書で開示されるＷＦＰ技術の原理が、複数のキューを有し、各キューがそれ自身の優先順位を有するシステムにおいて使用されることが可能である。図６は、キュー６２０−１、６２０−２および６２０−３に接続されたＮ個のポリサー６１０−１から６１０−Ｎを含む例示のシステム６００を示す。キュー６２０−１、６２０−２および６２０−３に割り当てられた優先順位は、それぞれ高、低、中である。この優先順位はキューにおけるパケットの待機時間を決定する。すなわち、優先順位が高いキューのパケットは、優先順位が低いキューのパケットよりも比較的短い時間でキューに入れられる。この実施形態では、異なる減衰関数が各キューに対応づけられる。優先順位が低いキュー６２０−３のＡｔｔｎ関数（ＡＴＬ）は、そのキューのＱｏｃｃに基づいている。すなわちＡＴＬ＝  Ｆ［ＱｏｃｃＬ］である。優先順位が中のキュー６２０−２のＡｔｔｎ関数（ＡＴＭ）は、そのキューのＱｏｃｃ（ＱｏｃｃＭ）、および優先順位が低いキュー６２０−３におけるＣＩＲバイトのＱｏｃｃＬＣの占有率に基づいている。すなわちＡＴＭ  ＝  Ｆ［ＱｏｃｃＭ，  ＱｏｃｃＬＣ］である。優先順位が高いキュー６２０−１のＡｔｔｎ関数（ＡＴＭ）は、キュー６２０−１のＱｏｃｃ、ならびに優先順位が低いキュー６２０−３におけるＣＩＲバイトのＱｏｃｃＬＣの占有率、および優先順位が中のキュー６２０−３におけるＣＩＲバイトのＱｏｃｃＭＣの占有率に基づいている。すなわちＡＴＭ  ＝  Ｆ［ＱｏｃｃＭ，  ＱｏｃｃＭＣ，  ＱｏｃｃＬＣ］である。認定情報速度（ＣＩＲ：ｃｏｍｍｉｔｔｅｄ  ｉｎｆｏｒｍａｔｉｏｎ  ｒａｔｅ）を有するパケットを優先順位がより低いキューから配信するために、優先順位がより高いキューの値を設定するのに優先順位がより低いキューのＣＩＲ占有率値の使用が実行される。実際、優先順位が低いキューと中のキューのＱｏｃｃ＿Ｃは、それぞれのキューにおけるＣＩＲバイトの数に応じている。
【図面の簡単な説明】
【００２４】
【図１】従来のＷＦＱシステム（先行技術）の図である。
【図２】本発明の一実施形態を開示する効率的な重み付け均等化システムの非限定的で例示のブロック図である。
【図３】減衰関数の非限定的で例示のグラフである。
【図４】開示された重み付け均等化システムの操作の例の図である。
【図５】本発明の一実施形態を開示する重み付け均等化ポリシングを実行するための方法を説明する非限定的な流れ図である。
【図６】本発明の一実施形態を開示する優先順位付けされたキューを有する効率的な重み付け均等化ポリシングシステムの非限定的で例示の図である。
【図１】
2009534885.tif 000006
【図２】
2009534885.tif 000007
【図３】
2009534885.tif 000008
【図４】
2009534885.tif 000009
【図５】
2009534885.tif 000010
【図６】
2009534885.tif 000011
【国際調査報告】
2009534885.tif 000012
2009534885.tif 000013