(57)【特許請求の範囲】
【請求項１】
パケット・システムにおいて使用するトラフィック管理システムであって、
複数の無線エンド・ポイントを含み、該複数の無線エンド・ポイントの各々は、折衝されたネットワーク接続に準拠するように、それぞれのパケット・フローを整形するフロント・エンド・ピークレート・シェイパー（１０５）を含み、該トラフィック管理システムは、さらに、
基地局を含み、該基地局は、重み付け公平キューイング。スケジューラ（１２０）によって提供された出力パケット・フローを整形するバック・エンド・ピークレート・パケット・シェイパー（１３０）を含み、該バック・エンド・ピークレート・パケット・シェイパー（１３０）は、全体的なピークレートが通信チャネルにわたって利用可能な帯域幅を超えないことを保証するトラフィック管理システム。
【請求項２】
請求項１に記載のトラフィック管理システムにおいて、該複数の無線エンドポイントのうちの少なくとも１つが、該複数のフロント・エンド・ピークレート・シェイパーの１つをさらに含む無線端末と、データ端末装置とを含むトラフィック管理システム。
【請求項３】
パケット・システムにおいて使用するトラフィック管理システムであって、
（ａ）  パケット分類器（６０５）と、
（ｂ）  複数のユーザ・キュー（６１０）と、
各ユーザ・キューは、該パケット分類器により同定されたパケットを、各ユーザに関連するものとして格納し、
（ｃ）  複数のパケットタグ付け要素（６１５）と、
各タグ付け要素は該ユーザ・キューのうちの１つに付属され、各タグ付け要素は、該パケットに関連されるユーザ・キュー内に格納されたパケットにサービス・タグを付け、
（ｄ）  サービス・タグが付けられたパケットをパケット・クラスに応じて更に分離するための多数のクラス・キュー（６２０、６２５、６３０）と、
（ｅ）  該クラス・キュー内で待ち行列に入れられたパケットを処理するための重み付き公平キューイング・スケジューラー（６３５）と、
該処理はパケット・クラス及びサービス・タグの関数である、
（Ｆ）  通信チャネルを介して伝送するために該重み付き公平キューイング・スケジューラにより提供された処理済パケットを整形するためのバック・エンド・パケット・シェイパー（６４０）と、からなることを特徴とするパケット・システム内で使用するためのトラフィック管理システム。
【請求項４】
パケット・システムにおいて使用する方法であって、
（Ａ）  基地局へ伝送する多数の無線エンドポイントの各々からのパケット・フローをフロント・エンド整形する（１０５）ステップを含み、該フロント・エンド整形は、折衝されたネットワーク接続に準拠するように実行され、
（Ｂ）  該多数の無線エンドポイントの各々からの整形済パケット・フローを重み付き公平キューイング・スケジューラー（１２０）により処理するステップと、
（Ｃ）  出力パケット・フローを供給するために処理済パケット・フローを更にバック・エンド整形（１３０）するステップと、からなり、バック・エンド整形は、全体的なピークレートが通信チャネルにわたって利用可能な帯域幅を超えないことを保証することを特徴とするパケット・システムで使用する方法。
【請求項５】
少なくとも１つの無線エンドポイントは無線モデムを備え、該整形ステップは無線モデム内の少なくとも１つのパケット・フローを整形するステップを包含する、ことを特徴とする請求項４に記載の方法。
【請求項６】
該少なくとも１つの無線エンドポイントはデータ端末装置を備え、該整形ステップはデータ端末装置内の少なくとも１つのパケット・フローを整形するステップを包含する、ことを特徴とする請求項４に記載の方法。
【請求項７】
請求項４に記載の方法において、
それぞれのユーザ・キュー内に格納するために、複数の異なるユーザからのパケットを識別するステップと、
サービス・タグを用いて各々のユーザ・キュー内に格納されているパケットをタグ付けするするステップと、
複数のパケット・クラスのうちの１つに従って、該サービス・タグによってタグ付けされたパケットをキューに入れるステップとを含み、
重み付け公平キューイング・スケジューラ内での処理は、パケット・クラスとサービス・タグの関数となっており、フロント・エンド・ピークレート・シェイパーは、該複数のユーザ・キューの各々と関連している方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は通信に関する。更に詳細には、本発明はパケット通信システムに関する。
【０００２】
【従来の技術】
インターネットへのアクセスは現在、無線ドメインを介して行われている。例えば、現在では、Palm VII（登録商標）のような手持ちサイズの小型デバイスを購入することができる。この装置によれば、サービス・プロバイダへの無線接続を介してインターネットにアクセスすることができる。更に、少なくとも１社の装置メーカーが無線インターネット・アクセス・システム（すなわち、ルーセント・テクノロジー社の無線インターネット・アクセス・システム）を宣伝している。このような環境下において、装置メーカー及びサービス・プロバイダは、このようなサービスを顧客に提供する際に、“サービスの質(QoS)”問題に関心を持つようになってきた。QoS問題の具体例は、例えば、ビット伝送速度、遅延及びパケット紛失などに対する保証である。
【０００３】
【発明が解決しようとする課題】
従って、本発明の目的はパケットシステムにおけるサービス品質問題を解決するトラフィック管理システムを提供することである。
【０００４】
【課題を解決するための手段】
前記課題は、ピークレート・シェーパーを、多数のユーザ接続に対してサービス品質保証を提供する重み付き公平キューイング・スケジューラーと組合せることにより解決される。
【０００５】
本発明の或る実施態様では、フロント・エンド・ピークレート・シェーパーは、多数のユーザ接続に対してピークレートシェーピング及び平均帯域幅保証の両方を提供する重み付き公平キューイング・スケジューラーと組合せられる。更に、バック・エンド・ピークレート・シェーパーは、パケットが平均ダウンリンク／アップリンク帯域幅よりも高いデータ転送速度で伝送されることを保証する重み付き公平キューイング・スケジューラーと組合せられる。
【０００６】
【発明の実施の形態】
図１は、本発明による例示的なトラフィック管理システム１００からなる通信システムの部分的ブロック図である。本発明の構成に係わる構成要素以外の図１に示された構成要素は当業者に周知なので、ここでは詳述しない。例えば、重み付き公平キューイング・スケジューラーそれ自体は当業者に公知である（例えば、"A Self-Clocked Fair Queueing Scheme for Broadband Applications," J. Golestani, Proceeding of IEEE Infocom 1994, pp 5c1.1-5cl.11参照）。同様に、ピークレート・シェーパー（別名、「トラフィック・シェーパー」とも呼ばれる）それ自体も当業者に公知である（例えば、"ISDN and Broadband ISDN with Frame Relay and ATM," by W. Stallings, Prentice Hall, 1995, pp 382-406, 492-516参照）。単一のブロック構成要素として図示されているが、トラフィック管理システム１００の構成要素類は格納プログラム制御プロセッサ、メモリ及び適当なインターフェースカード（図示されていない）なども包含する。本明細書で使用されている「パケット・サーバ」と言う用語は、任意のパケットプロセッサを意味する。このパケット・サーバも、前記のトラフィック管理システム１００の構成要素類の一例である。更に、本発明のコンセプトは常用のプログラミング技法を用いて実現される。従って、前記の通り、このプログラミング技法については本明細書では詳述しない。コール・アドミッション技術は本発明のコンセプトに対して不要なので、ビット／秒（ｂｐｓ）単位の預託情報伝送速度（ＣＩＲ）を確立するために、各ユーザはコール・アドミッション・プロセス（図示されていない）と折衝するものと仮定する。特定のユーザのためのＣＩＲを本明細書ではＣＩＲiと呼ぶ。ここで、ユーザの人数はＮに等しい。従って、１≦ｉ≦Ｎである。
【０００７】
トラフィック管理システム１００は、Ｎ人のユーザを処理又はサービスする、多数の又は一組のフロント・エンド・ピークレート・シェーパー１０５−１〜１０５−Ｎを備える。各シェーパーは、関連ユーザパケットフローＵI〜ＵN、重み付き公平キューイング（ＷＦＱ）スケジューラー１２０及びバック・エンド・ピークレート・シェーパー１３０を有する。
【０００８】
フロント・エンド・ピークレート・シェーパー１０５は、各接続のピークレートがネットワークと折衝済みであることを保証するために使用される。例えば、各ピークレート・パケット・シェーパーはトークン発生器（図示されていない）、ユーザ・キュー（図示されていない）及び伝送キュー（図示されていない）を実装する。トークン発生器は最大バーストサイズ（バイト単位）についてピークレート（Ｐi）でトークン（バイト単位）を反復的に発生し、また、総平均トークンレートがこのユーザに関するＣＩＲ（すなわち、ＣＩＲi）と同等であるように、或る期間（Ｔi）中は休止している。ユーザ（ｉ）のパケットは常に各パケット・シェーパーに到着する。パケット・シェーパーが新たに到着したパケットのサイズに適合するのに十分大きなトークンを有する場合、パケットはシステムから伝送キューに通される。これと逆に、十分に大きなトークンが存在しない場合、新たに到着したパケットは、少なくともそのサイズよりも大きいか又は同等のパケットが到着するまで、ユーザキュー内の待ち行列に入れられる。フロント・エンド・ピークレート・シェーパーは、各ユーザ・パケット・フローのサービス・タグ（Ｕi）を発生するものと仮定する。このサービス・タグは、各ユーザにより折衝された平均帯域幅（ＣＩＲi）及び特定のパケットの長さに基づく。各パケット・シェーパーにより伝送キューに通過されたパケットには、これらパケットのための適当なサービス・タグが付けられる（このようなタグ付けは前掲のGolestaniの論文に詳述されている）。
【０００９】
例えば、セッションｋの各到着パケットｐkiには、このパケットは伝送キューに配置される前に、サービス・タグＦki（ここで、ｉ＝１，２，・・・であり、ｋ∈Ｂであり、Ｂは一連の進入許可接続である）が付けられる。各セッションｋについて、到着パケットのサービス・タグは下記の式（１）による反復方式で計算される。
Ｆki＝（Ｌki／ｒk）＋ｍａｘ（Ｆki-1，υ（ａki））      （１）
（前記式中、Ｆk0＝０であり、Ｌkiはパケットｐkiの長さ（バイト単位）であり、ｒkはｋthセッションの折衝速度であり、ａkiはパケットｐkiの到着時間であり、υ（ａki）は到着時間ａkiにおけるシステム仮想時間である。）「システム仮想時間」は当業者に公知である。例えば、一般的に、コンピュータ（図示されていない）が更新される時間である。
【００１０】
伝送キュー内のパケットは、関連サービスタグの増加順に、重み付き公平キューイング（ＷＦＱ）スケジューラー１２０によりサービス提供のためピックアップされる。その結果、ＷＦＱスケジューラー１２０は、各接続が、その最小の折衝済平均帯域幅を獲得することを保証する。（前記のように、前記の自己クロックされた公平キューイング（ＳＣＦＱ）方式が使用されるものと仮定する。しかし、ＳＣＦＱ方式は単なる一例であり、この方式の使用自体は本発明の必須要件ではなく、他の任意のアルゴリズムも同等に使用できる。）着信パケット・フローがサービスクラス（下記で詳細に説明する）により更に分別される場合、ＷＦＱスケジューラー１２０は、これらのサービス分類の関数としても、パケットを伝送する。
【００１１】
バック・エンド・ピークレート・シェーパーは、全体的ピークレートが通信チャネル（図１の符号１３１参照）において利用可能な帯域幅を超えないことを保証するために使用されている。バック・エンド・ピークレート・トラフィック・シェーパー１３０は次のように動作する。総帯域幅（ＢtotalＴ）のｘ％が、発信通信チャネル（図１の符号１３１参照）を介してバック・エンド・ピークレート・トラフィック・シェーパー１３０からパケット（パケットフロー（Ｐshaper）で示される）の伝送に利用できるものと仮定する。（Ｂtotalは時間間隔当たりの総帯域幅（バイト単位）を示し、Ｔは時間間隔を示す。）利用可能なバイト残量は次式（２）のように初期化される。
バイト残量＝（ｘ％／１００）（ＢtotalＴ）−システムオーバーヘッド（２）
（前記式中、「システムオーバーヘッド」はコントロールメッセージにより取り上げられるバイト数を示す。）バック・エンド・ピークレート・シェーパー１３０により送信される全てのパケットについて、バイト残量の値は次式（３）により減少される。
バイト残量＝バイト残量−（切り上げ（pktサイズ／macフラグメント）＊（macフラグメント＋ｍａｃオーバーヘッド））      （３）
（前記式中、「pktサイズ」はパケットサイズを示し、「macフラグメント」はメディア・アクセス・コントロール（ＭＡＣ）リンク層フラグメントのサイズを示し、「切り上げ（）」は所定値を超える最小の整数値をとる。すなわち、次の最高整数値へ切り上げられる。）Ｔ秒毎に、バイト残量の値は次のようにリセットされる。
（ｘ％／１００）（ＢtotalＴ）            （４）
【００１２】
バック・エンド・ピークレート・パケット・シェーパー１３０における使用方法の一例を図２に示す。図１は、例えば、インタネットから無線移動局（図示されていない）へのような、モバイル・エンドポイントへのダウンリンク通信パスの一部を示すものと仮定する。図２のステップ２０５において、バイト残量の値が初期化される。特に、例証的な総エアーリンク帯域幅は２０ミリ秒（ｍｓ）毎に４０００バイトである。すなわち、ＢtotalＴ＝４０００バイトである。このうち、ｘ＝６０％が利用可能なダウンリンク帯域幅であり、ダウンリンク方向にはシステムオーバーヘッドが存在しないものと仮定する。すなわち、バイト残量＝（６０％／１００）（４０００）−０＝２４００バイトである。ステップ２１０において、バック・エンド・ピークレート・パケット・シェーパー１３０は、伝送ダウンリンクについて利用可能であるパケットを待ち受ける。パケットが利用可能である場合、バイト残量の値はステップ２２０でチェックされる。バイト残量の値が少なくとも１個のＭＡＣＦフラグメントを送信するのに十分であれば、パケットは送信、すなわち伝送され、バイト残量の値はステップ２２５において、前記数式（３）に示されるように減少される。その後、バック・エンド・ピークレート・パケット・シェーパー１３０は別のパケットを待ち受ける。しかし、バイト残量の値が少なくとも１個のＭＡＣフラグメントを送信するのに不十分であれば、ステップ２３０で示されるように、パケットは２０ｍｓ後まで送信されない。とにかく、バイト残量の値は２０ｍｓ毎に２４００バイトにリセットされる。この実施態様では、ＭＡＣ層再伝送を行うのに必要な追加帯域幅を大切にするために、バイト残量の値を、例えば、２４００バイトの９５％を初期化することができる（ＭＡＣ層再伝送のために間接的に５％保存する）。数式（２）によれば、これは（ｘ％／１００）（ＢtotalＴ）（０．９５）−システムオーバーヘッドである。しかし、この実施態様におけるシステムオーバーヘッドの値は前記のようにゼロである。
【００１３】
別法として、図１は、例えば、無線移動局からインタネット（図示されていない）へのような、モバイル・エンドポイントからのアップリンク通信パスの一部を示し、図２に示されるような方法を使用するものと仮定する。前記のように、例証的な総利用可能エアーリンク帯域幅は４０００バイトである。このうち、ｘ＝４０％が利用可能アップリンク帯域幅であると仮定する。（前記のように、６０％は先の実施態様においてダウンリンク伝送のために取り分けられている。）この実施態様では、システムオーバーヘッドはゼロではなく、バイト残量の値は数式（２）に示されるように初期化される。ここでは、システムオーバーヘッドの値はビーコン、ＭＡＣ層肯定応答（Ａｃｋｓ）及びアップリンク方向における予約スロットメッセージにより引き起こされるオーバーヘッドの推定値に等しい。特に、バイト残量は１６００−システムオーバーヘッドに初期化される（図２のステップ２０５参照）。パケットが伝送アップリンクに利用可能であるたびごとに、バイト残量の値はチェックされる（図２のステップ２１０及び２２０参照）。バイト残量の値が少なくとも１個のＭＡＣフラグメントを送信するのに十分であれば、パケットは送信、すなわち伝送され、バイト残量の値は前記数式（３）に示されるように減少される（図２のステップ２２５参照）。しかし、バイト残量の値が少なくとも１個のＭＡＣフラグメントを送信するのに不十分であれば、ステップ２３０で示されるように、パケットは２０ｍｓ後（別名、「ドエル時間」とも呼ばれる）まで送信されない。とにかく、バイト残量の値は、数式（２）で示されるように、ドエル時間毎にリセットされる。すなわち、（１６００−システムオーバーヘッド）にリセットされる（図２のステップ２３０参照）。この実施態様では、ＭＡＣ層再伝送を行うのに必要な追加帯域幅を大切にするために、バイト残量の値を、例えば、（（１６００）（０．９５）−システムオーバーヘッド）に初期化することができる。
【００１４】
エアーリンク帯域幅がフェーディング現象により著しく変動するような場合には、利用可能なエアーリンク帯域幅を推定するために、下記の代替的な閉ループフィードバックメカニズムを使用することができる。このような推定値は、前記で使用される４０００バイト又は１６００バイトのような固定数の代わりに使用することができる。
【００１５】
例えば、下記の定義を仮定する。
「Ｂｆｉｘ」は固定エアーリンク帯域幅（これは演繹的に知られる）を示す、
「Ｔ」は複数のドエル時間として表される観察期間である。
【００１６】
ダウンリンク方向の場合、アクセスポイント（又は、アップリンク方向では、無線モデム）は次のようにしてダウンリンク（アップリンク）が利用可能エアーリンク帯域幅を推定する。
(a)期間Ｔの間にダウンリンク（アップリンク）に伝送されるバイト数を測定する、これはＢtxである，
(b)期間Ｔの間にアップリンク（ダウンリンク）に受信されるバイト数を測定する、これはＢrxである，
(c)（Ｂtx／Ｂrx）の関数（下記で詳述する）として、推定エアーリンク帯域幅（Ｂtotal）を計算する。
【００１７】
推定エアーリンク帯域幅（Ｂtotal）は様々な方法で計算することができる。例えば、２種類の例証的な計算方法を下記に説明する。第１の例証的な計算方法は下記の数式で示される。
Ｂtotal＝Ｂfix（Ｂtx／Ｂrx）           （５）
この方法は別名「独立ウインドウバージョン」とも呼ばれる。
【００１８】
第２の例証的な計算方法では「スライディング・ウインドウ」を使用する。この計算方法では、前記計算の一部を使用し、現在値を計算する。特に、
ｓｕｃｃｅｓｓ＝（Ｉ−α）ｓｕｃｃｅｓｓ＋α（Ｂtx／Ｂrx）（６）、及び
Ｂtotal＝Ｂfix（ｓｕｃｃｅｓｓ）                       （７）
前記数式において、変数ｓｕｃｃｅｓｓは（Ｂtx／Ｂrx）の最初の計算値に初期化され、αは先行計算値がどれだけ記憶されたか（すなわち、その履歴）に関するものであり、例えば、６である。
【００１９】
別法として、Ｂｆｉｘの値を使用し、アクセスポイント（無線モデム）におけるダウンリンク（アップリンク）バッファ占有率をモニタすることができる。ダウンリンク（アップリンク）バッファ占有率が或る所定の閾値を超える場合は常に、フロー・コントロール・メッセージが無線ハブ（又は末端システム、すなわち、無線モデムの場合におけるユーザ端末）が送信され、パケットの流れを停止させる。バッファ占有率が閾値以下に低下すると、別のフロー・コントロール・メッセージが送信され、パケットの流れを再起動する。
【００２０】
トラフィック管理システムの例証的応用例を図３に示す。図３において、本発明の概念を実現する無線インターネットアクセスシステムの一部３００が示されている。（本発明の概念以外の、図３に示されるような無線インターネットアクセスシステムの一例はルーセント・テクノロジー社による無線インターネットアクセスシステムである。）無線インターネットアクセスシステムの一部３００は、基地局３１５のような多数の基地局を備える。この基地局はＬ２ＴＰ（レイヤー・２・トンネリング・プロトコル）アクセス・コントロール（ＬＡＣ）を提供する無線ポイント・オブ・プレゼンス（ＰＯＰ）サーバの一例である。各基地局は無線ハブ（ＷＨ）を備える。無線ハブは複数のアクセスポイント（例えば、基地局３１５のＡＰ1、ＡＰ2、ＡＰ3及びＡＰ4）の全体区域を取り扱う。各アクセスポイントは、無線モデム３１０−１〜３１０−Ｎで示されるような複数の無線モデムと通信するための、当業者に公知の無線アクセス・コントローラを有する。（各無線モデムはユーザ・パーソナル・コンピュータ（ＰＣ）３０５−１〜３０５−Ｎで示されるような無線加入者に付属される。）（各ＰＣは、当業者に公知なように、データ端末装置（ＤＴＥ）の代表例である。）各無線モデムはアップリンクチャネル（ライン３１１で示される）及びダウンリンク（ライン３１２で示される）を介して各基地局と通信する。無線モデムとユーザＰＣの組合せは、モバイルであるか、又はモバイルではない無線エンドポイントを示す。各基地局はＴ１／Ｅ１設備を介するフレームリレーにより専用ＩＰネットワークに結合されている。無線インターネット・アクセス・ネットワークは、Ｌ２ＴＰ、ＵＤＰ／ＩＰ（ユーザ・データグラム・プロトコル／インターネット・プロトコル）などを用いてインターネット・サービス・プロバイダ（ＩＳＰ）又は会社内インターネットと通信するための当業者に公知のルータ・ファイアウォール３３５を介して、データ交換局（ＤＳＣ）３３０により公衆ＩＰネットワークに結合されている。
【００２１】
図３に示される無線インターネット・アクセス・システムは、基地局と無線エンドポイント間で半二重ＭＡＣ（メディア・アクセス・コントロール層）を使用するものと仮定する。この場合、ダウンリンク／アップリンク比は設定可能であるか又は動的に調整される（例えば、前記のように、ダウンリンク・チャネルは総チャネル帯域幅の６０％であり、アップリンクは４０％とする）。このシステムでは、各ＡＰはアップリンク伝送のためのこれらの付属無線モデムをポールする。例えば、図３に示された実施態様では、ＡＰ1は任意のアップリンク伝送用の一連のモデム３１０−１〜３１０−Ｎをポールする。（ポーリング技法は当業者に公知であり、ここでは特に説明しない。）
【００２２】
ダウンリンク方向では、トラフィック管理システム１００は無線ハブ（例えば、図３の基地局のＷＨ）内に存在する。この実施態様では、ＷＨは４個のトラフィック管理システムからなり、それぞれ基地局３１５の各ＡＰに対応する。ＷＨが特定のユーザ（例えば、ユーザＰＣ３０５−１に関連するユーザ）へ伝送するためのパケットを有する場合、ＷＨはパケットをＡＰ1に送信する前に、図２に示された方法を実行する。その後、パケットを先入れ・先出し（ＦＩＦＯ）方式で無線エンドポイントへ伝送する。
【００２３】
アップリンク方向では、トラフィック管理システム１００は多数の代替実施態様を実行できる。その一例を図４に示す。図４は、図３の無線インターネット・アクセス・ネットワークの一部を示す。各フロント・エンド・ピークレート・トラフィック・シェーパー１３０はユーザの特別な装置（例えば、無線モデム３１０−１〜３１０−Ｎ）に付属されている。（別法として、パケット・シェーパーは、図３のＰＣ３０５−１のようなユーザのＰＣ（図示されていない）の一部であることができる。ＰＣ及び無線モデムの両方とも無線エンドポイントの代表例である。）図１において説明したように、各無線モデムは、ユーザ・パケット・フローＵiを受信する。前記のように、各無線モデムのフロント・エンド・ピークレート・パケット・シェーパーはトラフィックを整形し、そして、各アクセスポイント（例えば、ＡＰ1）から伝送ポールを受信すると、アップリンク・チャネル（例えば、アップリンク・チャネル３１１）を介して、各パケット・フローＰiをこれらの各アクセスポイント（例えば、ＡＰ1）へ伝送する。ＷＦＱスケジューラ１２０はＡＰ（ここでは、図４のＡＰ1により示される）における集中方式で実行される。この場合、付属の無線モデムは、（アップリンク伝送を待っているバイト数に関する）キュー・サイズ情報を、各ＡＰ（受信Ｓ／Ｎ比のような、無線エンドポイントからの状態伝送は当業者に公知であり、ここでは特に説明しない）に送信するのに必要である。各ＡＰ（例えば、図４のＡＰ1）は前記のバック・エンド・ピークレート・シェーパーも実装しており、図２に示される前記の方法を用いてその付属無線モデムに関するポールを（ダウンリンク・チャネル３１２を介して）発行する前に、十分なアップリンク帯域幅を利用可能にすることを保証する。例えば、バイト残量の値が少なくとも１個のＭＡＣフラグメントを送信するのに不十分である場合、ＡＰ（例えば、ＡＰ1）は、次のドエルまで、伝送ポールをその無線モデム（例えば、無線モデム３１０−１）へ送信しない。バイト残量変数は前記数式（２）に従って各ドエル毎にリセットされる。
【００２４】
トラフィック管理システムの別の代替実施態様を図５に示す。図５に示されたシステムは、ＷＦＱスケジューラが分散方式で各無線モデムで実行されることを除いて、図４に示されたシステムと同様なシステムである。これは、ＡＰ（例えば、図５に示されるＡＰ1）のようなネットワーク要素はシステム仮想時間を放送し、各ＡＰ（例えば、ＡＰ1）は（例えば、３１２のようなダウンリンクチャネルを介して）、任意のアップリンク伝送（例えば、アップリンクチャネル３１１によりしめされるもの）のためのこれらの各無線モデムをポールするものと仮定する。
【００２５】
パケット・ペイロードのための利用可能なダウンリンク／アップリンク帯域幅を推定するのは困難である。なぜなら、パケット・ペイロードは総ＭＡＣオーバーヘッドと同様に、変動可能であり、それ自体がパケット・ペイロードのサイズの関数だからである。しかし、バック・エンド・ピークレート・トラフィック・シェーパーは、パケットが利用可能なダウンリンク／アップリンク帯域幅よりも高い速度で伝送されず、その結果、（無線インターネットアクセスシステムのアクセスポイントのような）その他のネットワーク要素内でキューイング遅延が起こり得ることを保証する柔軟な手段である。
【００２６】
別の代替実施態様を図６に示す。図６において、トラフィック管理システム６００は、パケット分類器６０５、多数のユーザ・キュー（ユーザ１のキュー６１０−１〜ユーザＮのキュー６１０−Ｎとして図示されている）、多数のＷＦＱタグ付け要素６１５−１〜６１５−Ｎ、ＣＩＲ（預託情報速度）クラス・キュー６３０，コントロール・クラス・キュー６２５及び最善クラス・キュー６２０により示されるような３種類のクラス・キュー、ＷＦＱスケジューラー６３５及びパケット・シェーパー６４０から構成されている。本質的に、トラフィック管理システム６００は、下記に述べる点を除いて、図１のトラフィック管理システム１００と同様な方法で機能する。
【００２７】
トラフィック管理システム６００において、パケット・トラフィックのための３種類のサービスが存在する。これらのサービス（ＣｏＳ）の種類は、預託情報速度（ＣＩＲ）、コントロール及び最善の３種類である。コントロールはコントロール情報（例えば、信号方式及び状態）を示す。ＣＩＲクラス及び最善クラスはユーザのトランスポート（すなわち、ベアラ、データ）を示す。ＣＩＲサービスを獲得するユーザの場合、サービス・プロバイダ（図示されていない）は、常用のフレーム・リレー・サービスについて指定されたパラメータと同様な、預託情報速度（ＣＩＲ）、バースト・レート（Ｂｒ）及びバースト・サイズ（Ｂｓ）を指定する。最善（ＢＥ）サービスの場合、サービス・プロバイダは個々のユーザについて最大情報速度を指定する。ユーザへのＣＩＲクラス又は最善クラスの割当ては、コール・アドミッション手順（本明細書では説明されていない）により実行される。
【００２８】
（Ｐinputにより示される）着信パケットはパケット分類器６０５に入力される。パケット分類器６０５はユーザにより着信パケットを分類又は同定し、そして、これらを適当なユーザ・キューに割り当てる。（例えば、ユーザ１からのパケットはユーザ１に関するキューに割り当てられる。図６では６１０−１で示されるキューである。）各ユーザ・キューはユーザ分類の後に、パケットを格納する。各ユーザはユーザ１のキュー６１０−１により図示されているように、３種類のトラフィックを有することができる。特に、コントロール（ＣＴＬ）、ＣＩＲ及びＢＥを有することができる。ユーザ・キューが満杯の場合、過剰量のパケットは廃棄される。各タグ付け要素（例えば、ＷＦＱタグ付け要素６１５−１）は、その各ユーザ・キュー（例えば、ユーザ１のキュー６１０−１）についてサービス・タグを割り当てる。前記のように、ＳＣＦＱアルゴリズムを使用しサービス・タグを割り当てる。ＳＣＦＱのインスタンスが各クラスについて初期化される。これらのサービス・タグは、ユーザに割り当てられたビット・レート及びパケットの長さに基づいて割り当てられる。サービス・タグはアウトバウンド・パケットの順序付きキューを生成するために使用される。（クラス及びサービス・タグにより適当に同定される）パケットはこれらの特定のクラス・キューに経路指定される。コントロールとして同定されるパケットは、コントロール・クラス・キュー６２５内で待ち行列に入れられる。ＣＩＲクラスとして同定されるパケットは、ＣＩＲクラス・キュー６３０内で待ち行列に入れられる。また、最善クラスとして同定されるパケットは、最善クラス・キュー６２０内で待ち行列に入れられる。
【００２９】
コントロール・クラス・キュー６２５はベアラ平面内に送信されるコントロール・パケット用に使用される。このようなパケットの一例はＰＰＰ（２地点間プロトコル）コントロール・パケットである。全てのユーザが接続されると、ユーザは、たとえ高負荷状態であっても、ＰＰＰ折衝が成功裏に終わることを保証するために、このキューを介して少量のパケットを送受信することができる。ＰＰＰ折衝段階において、全てのＣＩＲクラス・ユーザは同じ重みが割り当てられる。全ての最善クラス・ユーザも同じ速度が割り当てられる。ＰＰＰ折衝中に、ＣＩＲユーザに最善ユーザよりも高い優先度を与えるために、ＣＩＲクラスの重みは最善クラスの重みよりも高い。ＣＩＲクラス・キュー６３０内のパケットはサービス・タグ値の順に待ち行列に入れられる。同様に、最善クラス・キュー６２０内のパケットも、サービス・タグ値の順に待ち行列に入れられる。ＷＦＱスケジューラー６３５は、各クラスに割り当てられたリンク帯域幅の画分に基づいて、又はクラス間の絶対優先度（例えば、コントロール・パケットの優先度はＣＩＲパケットよりも高く、ＣＩＲパケットの優先度はＢＥパケットの優先度よりも高い）に基づいて、３種類のクラス・キューからパケットを伝送する。前記のように、重み付き公平キューイングはこの機能のために使用される。これは、各クラスが、リンクの利用可能な帯域幅の公平な占有率を獲得することを保証する。
【００３０】
パケット・シェーパー６４０は、物理リンクによる最大データ伝送速度を制限するために、前記のようなバック・エンド・ピークレート・パケット整形機能を実行する。これにより、異なるタイプのトラフィック（Ｐoutputにより示される）は物理リンクを共有することができる。例えば、ネットワーク管理及びベアラ・トラフィック間のフレーム・リレーＰＶＣを共有することができる。
【００３１】
図６のトラフィック管理システムは図３に示された無線インターネット・アクセス・ネットワークに応用することができる。例えば、ダウンリンク方向では、トラフィック管理システム６００は無線ハブ（例えば、図３の基地局３１５のＷＨ）内に存在する。この実施態様では、ＷＨは４個のトラフィック管理システムから構成されており、このトラフィック管理システムは基地局３１５の各ＡＰに対応する。ＷＨが特定のユーザ（例えば、ユーザＰＣ３０５−１に関連するユーザ）へ伝送するパケットを有する場合、ＷＨは、パケットをＡＰ1へ送信する前に、図２に示された方法を実行する。その後、パケットを先入れ・先出し（ＦＩＦＯ）方式で無線エンドポイントへ伝送する。
【００３２】
同様に、アップリンク方向では、トラフィック管理システム６００の例証的な実施態様を図７に示す。各フロント・エンド・ピークレート・トラフィック・シェーパーはユーザの特定の装置（例えば、無線モデム６１０−１〜６１０−Ｎ）に付属される。（別法として、パケット・シェーパーはユーザのＰＣ（図示されていない）の一部であることもできる。）図１について説明したように、各無線モデムはユーザ・パケット・フロー（図示されていない）を受信する。この実施態様では、各ベアラ・トラフィック・クラス（例えば、ＣＩＲ及び最善クラス）についてパケット整形機能が存在する。（コントロール・クラス・データは各無線モデムにより内部的に生成されるものと仮定する。）多数のクラスをサポートするために、ＭＡＣは改変されなければならない。（このような改変は簡単であり、本明細書では特に詳述しない。）前記のように、（各無線モデムの）各フロント・エンド・ピークレート・パケット・シェーパーはトラフィックを整形し、これらの各受信ポイント（例えば、ＡＰ1）からの伝送ポールを受信すると、アップリンク・チャネル（例えば、アップリンク・チャネル６１１）を介して、各パケット・フローＰiを、これらの各アクセス・ポイント（例えば、ＡＰ1）へ伝送する。
【００３３】
この実施態様では、アップリンク・トラフィックの各クラスは、各キュー内で伝送を待機する。前記のように、最高優先度のサービス・クラスはコントロール・メッセージについて使用される。（このような伝送待機パケットは各無線モデムのコントロールキュー内に格納される。）次に高い優先度のサービス・クラスは預託情報速度サービスをサポートするために使用される。（このような伝送待機パケットは各無線モデムの高優先度ベアラ・データ・キュー内に格納される。）最低優先度のサービス・クラスは最善ユーザをサポートするために使用される。（このような伝送待機パケットは各無線モデムの低優先度ベアラ・データ・キュー内に格納される。）アップリンク方向へデータを伝送することの許可を取り付けている間に、各無線モデムは、各サービス・レベルに属するそのキュー内のバイト（又はパケット）の数を、その各ＡＰへ通知する。各ＡＰは重み付きスケジューラーを実装している。この重み付きスケジューラーは、各ＷＭが伝送しなければならないアップリンク・データ及び各クラスのトラフィックに割り当てられた重みに基づいて、無線モデムへ伝送許可を割り当てる。この実施態様では、コントロール・データはＣＩＲデータよりも高く、ＣＩＲデータは最善データよりも高い。各ＡＰはＦＩＦＯ順に、無線ハブ（ＷＨ）の前記トラフィック管理システム６００に全てのパケットを伝送する。（ＡＰは伝送パケットに高優先度を与えることもできる。）
【００３４】
図８は、本発明により使用される代表的なパケット・サーバの高レベルブロック図である。パケット・サーバ８０５は蓄積プログラム制御方式のプロセッサ・アーキテクチャであり、プロセッサ８５０、メモリ８６０（例えば、図２などに示された前記の方法を実行するためのプログラム命令及びデータの格納用メモリ）及びパス８６６で示されるような１個以上の通信パスに結合するための通信インターフェース８６５を有する。
【００３５】
前記のトラフィック管理システムは、仮想リース・ライン・サービスをユーザ（別名「エンド・ユーザ」とも呼ばれる）に提供するために使用される。特に、各ユーザは、特定の平均及びピーク帯域幅を保証するサービスを購入することができる。なぜなら、前記のトラフィック管理システムはピーク速度整形及び平均帯域幅保証の両方を提供するからである。
【００３６】
無線システムについて説明してきたが、本発明はＱｏＳが問題となる全てのシステム（例えば、有線システムなど）に対しても応用可能である。同様に、半二重ＭＡＣ層について説明してきたが、全二重ＭＡＣ層に対しても応用可能である。
【００３７】
【発明の効果】
以上説明したように、本発明によれば、パケット通信システムにおける“サービスの質（ＱｏＳ）”を保証するトラフィック管理システムが得られる。
【図面の簡単な説明】
【図１】本発明によるトラフィック管理システムの一例のブロック図である。
【図２】本発明によるバック・エンド・ピークレート・シェーパーで使用する方法の一例の流れ図である。
【図３】本発明を実施する無線インターネット・アクセス・ネットワークの部分的ブロック図である。
【図４】本発明によるトラフィック管理システムのアップリンク実施態様の一例のブロック図である。
【図５】本発明によるトラフィック管理システムのアップリンク実施態様の別の例のブロック図である。
【図６】本発明によるトラフィック管理システムの他の実施態様のブロック図である。
【図７】本発明によるトラフィック管理システムの別の実施態様のブロック図である。
【図８】本発明により使用するためのパケット・サーバの一例の高レベルブロック図である。
【符号の説明】
１００  トラフィック管理システム
１０５  フロント・エンド・ピークレート・パケット・シェーパー
１２０  重み付き公平キューイング（ＷＦＱ）スケジューラー
１３０  バック・エンド・ピークレート・パケット・シェーパー
３００  無線インターネット・アクセス・システム
３０５  ユーザＰＣ
３１０  無線モデム
３１５  基地局無線ＰＯＰ
３３０  データ交換局（ＤＳＣ）
３３５  ルータ／ファイアウォール
６００  トラフィック管理システム
６０５  パケット分類器
６１０  ユーザ・キュー
６１５  ＷＦＱタグ付け要素
６２０  最善クラス・キュー
６２５  コントロール・クラス・キュー
６３０  ＣＩＲクラス・キュー
６３０  ＷＦＱスケジューラー
６４０  パケット・シェーパー
８０５  パケット・サーバ
８５０  プロセッサ
８６０  メモリ
８６５  通信インターフェース
【図１】
0004700201.tif 000002
【図２】
0004700201.tif 000003
【図３】
0004700201.tif 000004
【図４】
0004700201.tif 000005
【図５】
0004700201.tif 000006
【図６】
0004700201.tif 000007
【図７】
0004700201.tif 000008
【図８】
0004700201.tif 000009