(57)【要約】【課題】ユーザ毎の契約帯域を守りつつ、特定ユーザの低遅延パケットを優先的に転送する。【解決手段】契約帯域は一定で遵守しつつ、ＶＬＬパケットに対する優先転送（揺らぎ）を許容する為、リーキーバケツ方式を拡張し、ＬＬＱ以外のパケット（例えばＷＦＱパケット）の送出を許可する閾値１５０９の他に、ＬＬＱパケットの送出を許可するための閾値１５０９より大きな閾値１５０１を備える（２閾値リーキーバケツ方式）。これによりＷＦＱが送信できない場合でもＬＬＱは優先的に送信可能となり、且つ、ＷＦＱとＬＬＱの合計帯域、すなわちＶＬＬの帯域は揺らぎを含みつつも契約帯域を遵守する事ができる。この２閾値リーキーバケツ方式の回路を、ＬＬＱ送信予定時刻計算回路とＷＦＱ送信予定時刻計算回路内に備え、それぞれの送信予定時刻を計算し、送信予定時刻に基づき優先度を考慮してＬＬＱ／ＷＦＱを選択し、パケットを選択する。【選択図】図７
2008263430.tif 000002
【特許請求の範囲】
【請求項１】
送信帯域が予め定められた仮想コネクションを介して第１優先クラスのパケットと第２優先クラスのパケットが通信されるネットワークにおいて、送信帯域と優先クラスに従いパケットを送信するためのトラヒックシェーピング回路であって、
受信した第１優先クラスのパケットを記憶する第１キューと、受信した第２優先クラスのパケットを記憶する第２キューとを有するパケットバッファ部と、
前記第１キューの第１送信予定時刻を求める第１送信予定時刻計算部と、
前記第２キューの第２送信予定時刻を求める第２送信予定時刻計算部と、
求められた第１送信予定時刻と、求められた第２送信予定時刻と、前記第１及び第２キューから出力されるパケットのパケット長に応じた水量が増加し、及び、前記仮想コネクションの送信帯域に応じた水量ずつ減少するバケツの水位とが記憶されるメモリと、
前記第１キューの第１送信予定時刻と、前記第２キューの第２送信予定時刻とに基づき、前記第１キュー及び第２キューが現在時刻で送信可能かそれぞれ判断し、前記第１キューが送信可能な場合には該第１キューを優先して選択し、前記第２キューが送信可能であり、かつ、前記第１キューが送信可能でない場合には該第２のキューを選択し、選択された第１キューの第１キュー識別子又は第２キューの第２キュー識別子を前記パケットバッファに通知して、前記パケットバッファの該第１キュー識別子に対応する第１キューからパケットが読み出されて出力され、又は、前記パケットバッファの該第２キュー識別子に対応する第２キューからパケットが読み出されて出力されるための送信制御部と
を備え、
前記第１送信予定時刻計算部は、前記送信制御部により前記第１キューが選択されると、前記メモリのバケツの水位と第１優先クラスに対する予め定められた第１閾値とに基づき、該第１キューの次回の第１送信予定時刻を求め、求められた次回の第１送信予定時刻を前記メモリに記憶し、
前記第２送信予定時刻計算部は、前記送信制御部により前記第２キューが選択されると、前記メモリのバケツの水位と、第１閾値よりも小さい、第２優先クラスに対する第２閾値とに基づき、該第２キューの次回の第２送信予定時刻を求め、求められた次回の第２送信予定時刻を前記メモリ記憶し、及び、
前記第１又は第２送信予定時刻計算部は、前記第１又は第２キューから送信したパケットのパケット長と、該仮想コネクションの送信帯域に基づき、前記メモリのバケツの水位を更新する前記トラヒックシェーピング回路。
【請求項２】
送信帯域が予め定められた複数の仮想コネクションがひとつの回線に束ねられ、該仮想コネクションを介して第１優先クラスのパケットと第２優先クラスのパケットが通信されるネットワークにおいて、送信帯域と優先クラスに従いパケットを送信するためのトラヒックシェーピング回路であって、
受信した第１優先クラスのパケットを記憶する仮想コネクション毎の複数の第１キューと、受信した第２優先クラスのパケットを記憶する仮想コネクション毎の複数の第２キューとを有するパケットバッファ部と、
前記複数の第１キュー毎の第１送信予定時刻を求める第１送信予定時刻計算部と、
前記複数の第２キュー毎の第２送信予定時刻を求める第２送信予定時刻計算部と、
前記第１キューを識別する第１キュー識別子に対応して、求められた第１送信予定時刻が記憶され、記憶された第１送信予定時刻と前記第１キューにパケットが存在するか否かに基づき、優先してパケットを送信する前記第１キューをひとつ選択する第１ソーティング部と、
前記第２キューを識別する第２キュー識別子に対応して、求められた第２送信予定時刻が記憶され、記憶された第２送信予定時刻と前記第２キューにパケットが存在するか否かに基づき、優先してパケットを送信する前記第２キューをひとつ選択する第２ソーティング部と、
選択された前記第１キューの第１送信予定時刻と、選択された前記第２キューの第２送信予定時刻とに基づき、選択された前記第１キュー及び第２キューが現在時刻で送信可能かそれぞれ判断し、選択された前記第１キューが送信可能な場合には該第１キューを優先して選択し、選択された前記第２キューが送信可能であり、かつ、選択された前記第１キューが送信可能でない場合には該第２のキューを選択し、該第１キューの第１キュー識別子又は第２キューの第２キュー識別子を前記パケットバッファに通知して、前記パケットバッファの該第１キュー識別子に対応する第１キューからパケットが読み出されて出力され、又は、前記パケットバッファの該第２キュー識別子に対応する第２キューからパケットが読み出されて出力されるための送信制御部と
を備え、
前記第１送信予定時刻計算部は、前記送信制御部により前記第１キューが選択されると、
選択された前記第１キューに対応する仮想コネクションのバケツであって、該仮想コネクションに対応する前記第１及び第２キューから出力されるパケットのパケット長に応じた水量が増加し、及び、前記仮想コネクションの送信帯域に応じた水量ずつ減少する前記バケツの水位と、第１優先クラスに対する予め定められた第１閾値とに基づき、該第１キューの次回の第１送信予定時刻を求め、及び、
求められた次回の第１送信予定時刻を、第１キュー識別子に対応して前記第１ソーティング部に記憶し、
前記第２送信予定時刻計算部は、前記送信制御部により前記第２キューが選択されると、
選択された前記第２キューに対応する仮想コネクションの前記バケツの水位と、第１閾値よりも小さい、第２優先クラスに対する第２閾値とに基づき、該第２キューの次回の第２送信予定時刻を求め、及び、
求められた次回の第２送信予定時刻を、第２キュー識別子に対応して前記第２ソーティング部に記憶する前記トラヒックシェーピング回路。
【請求項３】
前記第１送信予定時刻計算部は、前記送信制御部により前記第１キューが選択されると、
選択された前記第１キューに対応する仮想コネクションのバケツの水位と、第１優先クラスに対する予め定められた第１閾値を比較し、該水位が第１閾値を超えない場合は、該第１キューの次回の第１送信予定時刻を現在時刻とし、及び、該水位が第１閾値を超える場合は、該次回の第１送信予定時刻を、該水位から該仮想コネクションの送信帯域に応じた水量を引いていくことにより水位が第１閾値以下になる時刻とする請求項２に記載のトラヒックシェーピング回路。
【請求項４】
前記第１送信予定時刻計算部は、
選択された前記第１キューに対応する仮想コネクションのバケツの水位を、前記第１キューから送信したパケットのパケット長と、該仮想コネクションの送信帯域に基づき更新する請求項２に記載のトラヒックシェーピング回路。
【請求項５】
前記第１のソーティング部は、第１キュー識別子に対応して、該第１キューに対応する仮想コネクションのバケツの水位がさらに記憶され、
前記第２のソーティング部は、第２キュー識別子に対応して、該第２キューに対応する前記仮想コネクションのバケツの水位がさらに記憶され、
前記第１送信予定時刻計算部は、
前記第１のソーティング部に記憶された該仮想コネクションのバケツの水位と、前記第２のソーティング部に記憶された該仮想コネクションのバケツの水位の双方を更新する請求項４に記載のトラヒックシェーピング回路。
【請求項６】
仮想コネクション毎にバケツの水位が記憶されるメモリ
をさらに備え、
前記第１送信予定時刻計算部は、
前記メモリに記憶された該仮想コネクションのバケツの水位を更新する請求項４に記載のトラヒックシェーピング回路。
【請求項７】
前記第２送信予定時刻計算部は、前記送信制御部により前記第２キューが選択されると、
選択された前記第２キューに対応する仮想コネクションのバケツの水位と、第１の識別子よりも小さい、第２優先クラスに対する第２閾値を比較し、該水位が第２閾値を超えない場合は、該第２キューの次回の第２送信予定時刻を現在時刻とし、及び、該水位が第２閾値を超える場合は、該次回の第２送信予定時刻を、該水位から該仮想コネクションの送信帯域に応じた水量を引いていくことにより水位が第２閾値以下になる時刻とする請求項２に記載のトラヒックシェーピング回路。
【請求項８】
前記第２送信予定時刻計算部は、
選択された前記第２キューに対応する仮想コネクションのバケツの水位を、前記第２キューから送信したパケットのパケット長と、該仮想コネクションの送信帯域に基づき更新する請求項２に記載のトラヒックシェーピング回路。
【請求項９】
前記第１のソーティング部は、第１キュー識別子に対応して、該第１キューに対応する仮想コネクションのバケツの水位がさらに記憶され、
前記第２のソーティング部は、第２キュー識別子に対応して、該第２キューに対応する前記仮想コネクションのバケツの水位がさらに記憶され、
前記第２送信予定時刻計算部は、
前記第１のソーティング部に記憶された該仮想コネクションのバケツの水位と、前記第２のソーティング部に記憶された該仮想コネクションのバケツの水位の双方を更新する請求項８に記載のトラヒックシェーピング回路。
【請求項１０】
仮想コネクション毎にバケツの水位が記憶されるメモリ
をさらに備え、
前記第２送信予定時刻計算部は、
前記メモリに記憶された該仮想コネクションのバケツの水位を更新する請求項８に記載のトラヒックシェーピング回路。
【請求項１１】
前記パケットバッファ部は、パケットを受信するとパケットヘッダを参照して、仮想コネクションと優先クラスを判別し、判別された仮想コネクションと優先クラスに従い、該当する仮想コネクションの前記第１キュー又は前記第２キューに受信されたパケットを書き込む請求項２に記載のトラヒックシェーピング回路。
【請求項１２】
前記パケットバッファ部から読み出され及び出力されたパケットのパケット長を識別し、前記第１送信予定時刻計算部及び／又は前記第２送信予定時刻計算部にパケット長情報を出力するパケット長識別部
をさらに備えた請求項２に記載のトラヒックシェーピング回路。
【請求項１３】
前記第１ソーティング部は、
前記第１キュー識別子に対応して、該第１キューに送信待ちのパケットが存在するか否かを示す第１判別ビットがさらに記憶され、
該第１判別ビットが、パケットが存在することを示す複数の前記第１キューの中から優先してパケットを送信する第１キューを選択する請求項２に記載のトラヒックシェーピング回路。
【請求項１４】
前記第１ソーティング部は、
第１キュー識別子と、第１送信予定時刻と、第１判別ビットとを二分木構造で管理する手段を備え、過去のソーティング結果を利用して送信すべき前記第１キューを選択する請求項１３に記載のトラヒックシェーピング回路。
【請求項１５】
前記第２ソーティング部は、
前記第２キュー識別子に対応して、該第２キューに送信待ちのパケットが存在するか否かを示す第２判別ビットがさらに記憶され、
該第２判別ビットが、パケットが存在することを示す複数の前記第２キューの中から優先してパケットを送信する第２キューを選択する請求項２に記載のトラヒックシェーピング回路。
【請求項１６】
前記第２ソーティング部は、
第２キュー識別子と、第２送信予定時刻と、第２判別ビットとを二分木構造で管理する手段を備え、過去のソーティング結果を利用して送信すべき前記第２キューを選択する請求項１５に記載のトラヒックシェーピング回路。
【請求項１７】
前記送信制御部は、
選択された前記第１キューの第１送信予定時刻が現在時刻を基準として過去、又は、現在時刻と同時刻であれば、選択された前記第１キューは送信可能と判断し、及び、
選択された前記第２キューの第２送信予定時刻が現在時刻を基準として過去、又は、現在時刻と同時刻であれば、選択された前記第２キューは送信可能と判断する請求項２に記載のトラヒックシェーピング回路。
【請求項１８】
送信帯域が予め定められた複数の仮想コネクションがひとつの回線に束ねられ、該仮想コネクションを介して第１優先クラスのパケットと第２優先クラスのパケットが通信されるネットワークにおいて、送信帯域と優先クラスに従いパケットを送信するための端末装置であって、
請求項２に記載のトラヒックシェーピング回路を有する回線インタフェース部と、
処理部と
を備え、
前記トラヒックシェーピング回路は、前記処理部からのパケットを、送信帯域及び優先クラスに従い網に送信する端末装置。
【請求項１９】
端末装置に対する第１回線インタフェース部と、
網に対する第２回線インタフェース部と
前記第１回線インタフェース部及び前記第２回線インタフェース部とそれぞれ接続されたスイッチ部と
を備え、
前記第２回線インタフェースは、
請求項２に記載のトラヒックシェーピング回路を有し、
該トラヒックシェーピング回路は、前記スイッチ部からのパケットを、送信帯域及び優先クラスに従い網に送信するネットワークノード。
【請求項２０】
端末装置に対する第１回線インタフェース部と、
網に対する第２回線インタフェース部と、
請求項２に記載のトラヒックシェーピング回路と、
前記第１回線インタフェース部と、前記第２回線インタフェース部と、前記トラヒックシェーピング回路にそれぞれ接続されたスイッチ部と、
を備え、
前記スイッチ部は、前記第１回線インタフェース部からのパケットを前記トラヒックシェーピング回路に転送し、及び、前記トラヒックシェーピング回路により送信帯域及び優先クラスに従い出力されたパケットを前記第２の回線インタフェース部を介して網に転送するネットワークノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トラヒックシェーピング回路、端末装置及びネットワークノードに係り、特に、固定長・可変長パケットの送信端末、またはネットワークノード（ルータ等）におけるトラヒックシェーピング回路、その送信端末及びネットワークノードに関する。
【背景技術】
【０００２】
ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ）交換機やルータ等を用いたパケット通信で通信品質制御機能（以下、ＱｏＳ機能）の重要性が増している。代表的な品質制御機能には、例えば、優先制御（低遅延時間転送）、廃棄制御（低廃棄率転送）、帯域制御（最大または最小の帯域幅確保転送）等がある。この中で、帯域制御は、物理的な回線帯域を論理的な帯域（論理帯域）に分離してパケットを送受信する機能であり、例えばユーザと網間の契約に基づいて一定の帯域を提供する帯域提供サービスに必要な通信品質制御である。例えば、コンテンツ配信やストーレッジのバックアップ時において、目標時間内にサービスの完了を保証する場合に有効である。
【０００３】
ＡＴＭ交換機やルータ等のパケットを用いた送信回線では、セルやパケットと呼ばれる情報の固まり（以下、パケット）をシェーピング回路の備える一定の規則（シェーピング方式）に従ってポートに出力することにより、上述の通信品質制御が行われる。シェーピング回路は、装置内の同一ポートに出力される多様なパケットをフローの種類毎に分類し、複数のキューイングバッファに一旦蓄積し、キューイングバッファから優先度や帯域目標値に従って出力する。シェーピング方式としては、例えば、優先制御方式、帯域制御方式、多段の階層シェーピング方式が知られている。
【０００４】
まず、優先制御方式は、同一の回線に出力される複数のキューの内、高優先度キューのパケットを他のキューのパケットに対して優先的に出力する事により、装置内での滞留時間を短くする事で低遅延転送を実現する方式である。この優先制御方式により高優先度のパケットの通信品質を守る事は、例えば、音声・映像等の低遅延転送やミッションクリティカルなデータの低廃棄率転送に適している。しかし、複数の契約者（ユーザ）間での契約帯域に基いた公平な帯域サービスを提供することは困難であった（従来技術１）。
【０００５】
次に、帯域制御方式は、例えば、同一の回線に出力される複数のパケットキューに対し、それぞれのキュー毎の論理帯域値を設定し、その帯域値に基づいてキューを切り替えながらパケットを出力することにより、各々のキュー毎の論理帯域値を守った転送を実現する方式である。次のパケット送信予定時刻の計算は、例えばリーキーバケット（Ｌｅａｋｙ  Ｂｕｃｋｅｔ）方式を用いて行う。リーキーバケット方式に関しては、例えば「Ｔｈｅ  ＡＴＭ  Ｆｏｒｕｍ  ＴＭ４．０    Ｎｏｒｍａｔｉｖｅ  Ａｎｎｅｘ  Ｃ：  Ｔｒａｆｆｉｃ  Ｃｏｎｔｒａｃｔ  Ｒｅｌａｔｅｄ  Ａｌｇｏｒｉｔｈｍｓ  ａｎｄ  Ｐｒｏｃｅｄｕｒｅｓ、Ｐ．６２、６３」（非特許文献１）に述べられている。帯域制御方式では、帯域提供サービス、すなわち同一の回線帯域を複数の契約者（ユーザ）の契約帯域（論理帯域）で分け合うＳＬＡ（Ｓｅｒｖｉｃｅ  Ｌｅｖｅｌ  Ａｇｒｅｅｍｅｎｔ）管理サービスは提供出来るが、契約帯域内での低遅延転送すべきパケットに対して選択的に優先制御を提供することは困難であった（従来技術２）。
【０００６】
階層シェーピング方式は、上述の従来技術１や２等の複数の規則を組合せた方式と捕らえる事もできる。従来技術３は例えば特許文献１に記載されている。特許文献１の実施例４では、例えば、同一ポートへ出力する複数ユーザからの可変長パケットに対して、網とのユーザ間の各々の契約帯域を複数ユーザに対して割り当てる。また、割り当てられた該契約帯域内で、同一ユーザからのパケットを優先度制御回路１５２１０において、転送先毎、優先度毎等の情報に基づいて判定した転送優先度に対応する複数のキューに振り分け、キュー毎に優先制御する。これにより、同一回線を複数ユーザで契約帯域に分けつつ、同時に契約帯域内での優先制御サービスを提供することができる。ユーザの低遅延パケットは、同一回線の契約帯域内で他の優先度のパケットより優先して転送され、低遅延時間転送が提供される。該回線帯域およびユーザ毎の契約帯域内を有効に利用することが可能なパケット送信端末またはパケット交換機向けのトラヒックシェーピング装置を提供することができる。
【０００７】
【特許文献１】特開２０００−３１９７４号公報
【非特許文献１】「Ｔｈｅ  ＡＴＭ  Ｆｏｒｕｍ  ＴＭ４．０    Ｎｏｒｍａｔｉｖｅ  Ａｎｎｅｘ  Ｃ：  Ｔｒａｆｆｉｃ  Ｃｏｎｔｒａｃｔ  Ｒｅｌａｔｅｄ  Ａｌｇｏｒｉｔｈｍｓ  ａｎｄ  Ｐｒｏｃｅｄｕｒｅｓ」、Ｐ．６２、６３、１９９６年４月
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記の様に、帯域制御回路は特定のパケットを優先的に送信したり、送信帯域を論理帯域値に抑えたり、さらにこれらを組み合わせて階層シェーピングを行う事が出来る。
階層シェーピング方式（従来技術３）では、契約ソーティング部、優先度ソーティング部を備え、網とのユーザ間の契約帯域を守りつつ、契約帯域内でさらに同一ユーザからのパケットを複数の優先度毎のキューに分け、優先制御することができ、これにより低遅延パケットに対して低遅延転送を実現する事が出来る。
【０００９】
本発明の解決しようとする課題を、図１２等を用いて説明する。
図１２は、トラヒックシェーピング回路を備えた送信端末（ユーザ端末）に通信サービスを提供する網である。ユーザがパケット通信網としてキャリアイーサ網（例えば広域イーサ網）を利用する際に、網とユーザ間の帯域の契約帯域で課金する。ここでは最もシンプルなサービス例として、この帯域単位での契約を相手方拠点毎に行う場合について述べる。図１２では、キャリアイーサ網３４０に、端末３００、１９０１、１９０２、１９０３が接続されている様子を示している。例えば、端末３００が端末１９０１に向けて契約帯域以上でパケットを送信すると、端末１９０１に向けたキャリアイーサ網３４０の出口でパケットが廃棄されてしまう。そこで、端末３００が各端末１９０１、１９０２、１９０３と通信を行うとき、端末３００は各端末１９０１、１９０２、１９０３に向けて契約帯域以下でパケットを送信する。
【００１０】
このように、ユーザ側は契約帯域以下になる様、帯域を遵守し、網側は通信品質（契約帯域）を守る通信サービスを、ここでは仮想専用線サービス（ＶＬＬ：Ｖｉｒｔｕａｌ  Ｌｅａｓｅｄ  Ｌｉｎｅ）と呼び、以下ＶＬＬと記す。これはＡＴＭ網やＩＰ網の様な複数ユーザが使用する通信網を使って、事実上、専用線と同じ、高品質（帯域保証）・高信頼のサービスを提供するものである。常に回線を確保する訳では無いので、従来の専用線よりかなり低価格でサービスを受けられる。ユーザ側はＶＬＬ内の帯域を有効活用し各種アプリケーションの特性に合った様に送るため、優先転送や帯域分配転送のクラスを設ける。ＶＬＬは帯域制御を活用したパケット交換網における仮想的な帯域のコネクションの概念であり、図１２のパケット通信網は特定のプロトコルには依存しない。イーサパケットにも、ＩＰパケットにも、ＭＰＬＳパケットにも、ＡＴＭセルにも応用することができる。ここではイーサパケットに応用した場合について述べる。
【００１１】
図１２では、例えば、端末３００−端末１９０１間はＶＬＬ（０）２１０として６０Ｍｂｐｓを帯域確保し、端末３００−端末１９０２間はＶＬＬ（１）２２０として、２０Ｍｂｐｓを帯域確保し、端末３００−端末１９０３間はＶＬＬ（２）２３０として、２０Ｍｂｐｓを帯域確保しているとする。このＶＬＬ（０）〜ＶＬＬ（２）を端末３００−イーサスイッチ３５０との間を結んでいる１００Ｍｂｐｓの回線に束ねて送信する。逆に、各端末１９０１、１９０２、１９０３も端末３００に向けて上記ＶＬＬ（０）〜ＶＬＬ（２）の帯域で送信する。なお、ＶＬＬ（ｉ）の送受双方向の帯域値は異なっていても良い。
【００１２】
図３に、階層シェーピング方式の例を示す。
図３は、回線２００と、契約帯域に従って送信するＶＬＬ（Ｖｉｒｔｕａｌ  Ｌｅａｓｅｄ  Ｌｉｎｅ：仮想専用線の略）との関係、及び、ＶＬＬ内の２つの優先クラスであるＬＬＱ（Ｌｏｗ  Ｌａｔｅｎｃｙ  Ｑｕｅｕｉｎｇ：低遅延キューの略）と、ＷＦＱ（Ｗｅｉｇｈｔｅｄ  Ｆａｉｒ  Ｑｕｅｕｉｎｇ：重み付けフェアキューの略）との関係を示す概念図である。ＬＬＱは、遅延優先度の高いパケット（音声パケット等）が詰まれるキューである。ＷＦＱは、送信優先度が低いデータパケットが詰まれるキューである。図３では、６０ＭｂｐｓのＶＬＬ（０）２１０内にＬＬＱ２１１とＷＦＱ２１２の２本が束ねられている。同様に、２０ＭｂｐｓのＶＬＬ（１）２２０内にＬＬＱ２２１、ＷＦＱ２２２が束ねられ、２０ＭｂｐｓのＶＬＬ（２）２３０内にＬＬＱ２３１、ＷＦＱ２３２が束ねられている。
【００１３】
この様に契約帯域（ＶＬＬ）内での優先転送制御が実現できる。しかし、ユーザ毎の契約帯域を守ることを優先しつつクラス内の帯域を制御するため、契約帯域毎（ＶＬＬ毎）の転送時間に依存する遅延時間を短縮することは困難である。例えば、特定ユーザのキュー内に送信パケットがあると、他のユーザの割当て帯域が消費されるまで特定ユーザに対する低遅延パケットの送信タイミングは待たされることがあり、割当て帯域分に依存した遅延時間分は増加することがある。例えば、ＶＬＬ（０）が割当て帯域を消費した時点で低遅延転送クラスのパケットの送信要求が生じた場合、他のユーザ（ＶＬＬ（１、２）のキュー内に低優先度のＷＦＱパケットであっても、帯域を守るため上記低遅延転送クラスのパケットが待たされる。
すなわち、同一回線で転送するユーザ数が増加するにつれ、この割当て帯域分に依存した遅延時間が大きくなってしまうことが課題となっていた（本発明の課題１）。
【００１４】
この課題を図８（ａ）のタイムチャートで説明する。
図８（ａ）のタイムチャートは、ＶＬＬ毎の帯域分配とＶＬＬ内での音声パケットとデータパケットの送信時間関係の一例である。例えば、ＶＬＬ（０）の送信時間が過ぎた時点でＶＬＬ（０）の遅延優先度の高いパケット（音声パケット（０）等）がＬＬＱで送信待ち状態になった場合、他のＶＬＬからの送信時間分、その音声パケット（０）は送信待ちになり、次のＶＬＬ（０）の送信時間まで待たされてしまう。これは、たとえ、送信優先度が低いデータパケットが他のＶＬＬのＷＦＱに積まれ送信されている場合でも同様である。従来技術３では、他のユーザの割当て帯域が消費され、送信タイミングが該当するＶＬＬ（０）に廻って来るまで、ＶＬＬ（０）ユーザの低遅延パケットの送信タイミングは待たされると言う課題があった（本発明の課題１）。
【００１５】
そこで、ＶＬＬ（０）以外のユーザ（ＶＬＬ（ｋ）、ｋは０以外）のパケットがベストエフォートのデータパケットである場合、ＶＬＬ（ｋ）の低遅延時間転送クラスに対する要求はないので、上記データパケットの代わりに、ＶＬＬ（０）ユーザのＬＬＱの低遅延パケットを先に転送する。こうしたとしてもベストエフォートの通信品質には影響が無い。図８（ｂ）に示す様に、ＶＬＬ（０）ユーザの低遅延パケット（例えば、音声パケット（０））を先に転送できれば、遅延時間の増加を抑える事が出来る。しかし、逆に特定ユーザＶＬＬ（０）が割り当て帯域を既に消費したにも拘わらず、さらにＬＬＱパケットを先に転送すると、契約帯域の条件を超えて帯域を消費してしまい、契約帯域を遵守する事ができない課題があった。また、補間のために次のＶＬＬ（０）の送信帯域をＬＬＱパケット分だけ減じる必要がある、という課題があった（本発明の課題２）。
【００１６】
以上述べた課題を纏めると、契約帯域を遵守しつつ、同時に契約帯域を優先して遵守した場合に生じる低遅延転送クラスの遅延時間も最小化する、パケット送信端末及びパケット交換機のトラヒックシェーピング装置が求められている。
【００１７】
本発明は、以上の点に鑑み、複数の帯域契約者（ユーザ等）が同一媒体（イーサ回線や無線ＬＡＮの様に共用の無線帯域でも可）の帯域を共有してパケットを転送する場合、ユーザ毎の契約帯域を守りつつ、特定ユーザの低遅延パケットを優先的に転送し、遅延時間の増加を抑えるトラヒックシェーピング回路、送信端末及びネットワークノードを提供することを目的とする。
【課題を解決するための手段】
【００１８】
契約帯域は一定で遵守しつつ、ＶＬＬパケットに対する優先転送（揺らぎ）を許容する為、前述のリーキーバケツ方式を拡張し、ＬＬＱ以外のパケット（例えば、ＷＦＱパケット）の送出を許可する閾値１５０９の他に、ＬＬＱパケットの送出を許可する閾値１５０１（閾値１５０９より大きな値に設定）を備える（２閾値リーキーバケツ方式：図７）。これにより、ＷＦＱが送信できない場合でもＬＬＱは優先的に送信可能となり、且つ、ＷＦＱとＬＬＱの合計帯域、すなわちＶＬＬの帯域は揺らぎを含みつつも契約帯域を遵守する事ができる（手段１）。
この２閾値リーキーバケツ方式の回路をＬＬＱ送信予定時刻計算回路１３０とＷＦＱ送信予定時刻計算回路１４０内に備え、それぞれの送信予定時刻を計算する（手段２、手段３）。
【００１９】
全ＬＬＱの内、送出すべきＬＬＱを検出するＬＬＱソーティング部（手段４）と、全ＷＦＱの内、送出すべきＷＦＱを検出するＷＦＱソーティング部（手段５）を備える。また、ＬＬＱソーティング部とＷＦＱソーティング部の双方のソーティング結果を優先度を考慮して決定する送信制御部１２０（手段６）を備える。
【００２０】
本発明のトラヒックシェーピング回路は、例えば、パケットまたはセルを送信する回線におけるトラヒックシェーピング機能で該契約帯域内に複数の優先クラスを備え、クラス間の優先制御機能を有する階層型トラヒックシェーピング装置において、リーキーバケツモデルの送信タイミング決定回路を備え、その閾値として優先度に対応した二つ以上の閾値を備える。
【００２１】
上述のトラヒックシェーピング回路は、複数の優先度に対応した送信予定時刻決定回路を備え、該送信予定時刻決定回路内に優先度に対応した閾値を備えたリーキーバケツモデルの送信タイミング決定回路を備える。
【００２２】
上述のトラヒックシェーピング回路は、優先度毎の送出パケットソーティング回路を備え、複数の該送出パケットソーティング回路の出力を受け、優先度に従って送出パケットを決定する送信制御部を備える。
【００２３】
上述のトラヒックシェーピング回路は、パケット送信後の対応するリーキーバケツの水位の補正を、優先度に対応した送信予定時刻決定回路内のそれぞれの該優先度に対応した閾値を備えたリーキーバケツモデルの送信タイミング決定回路に反映する。
【００２４】
本発明の第１の解決手段によると、
送信帯域が予め定められた仮想コネクションを介して第１優先クラスのパケットと第２優先クラスのパケットが通信されるネットワークにおいて、送信帯域と優先クラスに従いパケットを送信するためのトラヒックシェーピング回路であって、
受信した第１優先クラスのパケットを記憶する第１キューと、受信した第２優先クラスのパケットを記憶する第２キューとを有するパケットバッファ部と、
前記第１キューの第１送信予定時刻を求める第１送信予定時刻計算部と、
前記第２キューの第２送信予定時刻を求める第２送信予定時刻計算部と、
求められた第１送信予定時刻と、求められた第２送信予定時刻と、前記第１及び第２キューから出力されるパケットのパケット長に応じた水量が増加し、及び、前記仮想コネクションの送信帯域に応じた水量ずつ減少するバケツの水位とが記憶されるメモリと、
前記第１キューの第１送信予定時刻と、前記第２キューの第２送信予定時刻とに基づき、前記第１キュー及び第２キューが現在時刻で送信可能かそれぞれ判断し、前記第１キューが送信可能な場合には該第１キューを優先して選択し、前記第２キューが送信可能であり、かつ、前記第１キューが送信可能でない場合には該第２のキューを選択し、選択された第１キューの第１キュー識別子又は第２キューの第２キュー識別子を前記パケットバッファに通知して、前記パケットバッファの該第１キュー識別子に対応する第１キューからパケットが読み出されて出力され、又は、前記パケットバッファの該第２キュー識別子に対応する第２キューからパケットが読み出されて出力されるための送信制御部と
を備え、
前記第１送信予定時刻計算部は、前記送信制御部により前記第１キューが選択されると、前記メモリのバケツの水位と第１優先クラスに対する予め定められた第１閾値とに基づき、該第１キューの次回の第１送信予定時刻を求め、求められた次回の第１送信予定時刻を前記メモリに記憶し、
前記第２送信予定時刻計算部は、前記送信制御部により前記第２キューが選択されると、前記メモリのバケツの水位と、第１閾値よりも小さい、第２優先クラスに対する第２閾値とに基づき、該第２キューの次回の第２送信予定時刻を求め、求められた次回の第２送信予定時刻を前記メモリ記憶し、及び、
前記第１又は第２送信予定時刻計算部は、前記第１又は第２キューから送信したパケットのパケット長と、該仮想コネクションの送信帯域に基づき、前記メモリのバケツの水位を更新する前記トラヒックシェーピング回路が提供される。
【００２５】
本発明の第２の解決手段によると、
送信帯域が予め定められた複数の仮想コネクションがひとつの回線に束ねられ、該仮想コネクションを介して第１優先クラスのパケットと第２優先クラスのパケットが通信されるネットワークにおいて、送信帯域と優先クラスに従いパケットを送信するためのトラヒックシェーピング回路であって、
受信した第１優先クラスのパケットを記憶する仮想コネクション毎の複数の第１キューと、受信した第２優先クラスのパケットを記憶する仮想コネクション毎の複数の第２キューとを有するパケットバッファ部と、
前記複数の第１キュー毎の第１送信予定時刻を求める第１送信予定時刻計算部と、
前記複数の第２キュー毎の第２送信予定時刻を求める第２送信予定時刻計算部と、
前記第１キューを識別する第１キュー識別子に対応して、求められた第１送信予定時刻が記憶され、記憶された第１送信予定時刻と前記第１キューにパケットが存在するか否かに基づき、優先してパケットを送信する前記第１キューをひとつ選択する第１ソーティング部と、
前記第２キューを識別する第２キュー識別子に対応して、求められた第２送信予定時刻が記憶され、記憶された第２送信予定時刻と前記第２キューにパケットが存在するか否かに基づき、優先してパケットを送信する前記第２キューをひとつ選択する第２ソーティング部と、
選択された前記第１キューの第１送信予定時刻と、選択された前記第２キューの第２送信予定時刻とに基づき、選択された前記第１キュー及び第２キューが現在時刻で送信可能かそれぞれ判断し、選択された前記第１キューが送信可能な場合には該第１キューを優先して選択し、選択された前記第２キューが送信可能であり、かつ、選択された前記第１キューが送信可能でない場合には該第２のキューを選択し、該第１キューの第１キュー識別子又は第２キューの第２キュー識別子を前記パケットバッファに通知して、前記パケットバッファの該第１キュー識別子に対応する第１キューからパケットが読み出されて出力され、又は、前記パケットバッファの該第２キュー識別子に対応する第２キューからパケットが読み出されて出力されるための送信制御部と
を備え、
前記第１送信予定時刻計算部は、前記送信制御部により前記第１キューが選択されると、
選択された前記第１キューに対応する仮想コネクションのバケツであって、該仮想コネクションに対応する前記第１及び第２キューから出力されるパケットのパケット長に応じた水量が増加し、及び、前記仮想コネクションの送信帯域に応じた水量ずつ減少する前記バケツの水位と、第１優先クラスに対する予め定められた第１閾値とに基づき、該第１キューの次回の第１送信予定時刻を求め、及び、
求められた次回の第１送信予定時刻を、第１キュー識別子に対応して前記第１ソーティング部に記憶し、
前記第２送信予定時刻計算部は、前記送信制御部により前記第２キューが選択されると、
選択された前記第２キューに対応する仮想コネクションの前記バケツの水位と、第１閾値よりも小さい、第２優先クラスに対する第２閾値とに基づき、該第２キューの次回の第２送信予定時刻を求め、及び、
求められた次回の第２送信予定時刻を、第２キュー識別子に対応して前記第２ソーティング部に記憶する前記トラヒックシェーピング回路が提供される。
【００２６】
本発明の第３の解決手段によると、
送信帯域が予め定められた複数の仮想コネクションがひとつの回線に束ねられ、該仮想コネクションを介して第１優先クラスのパケットと第２優先クラスのパケットが通信されるネットワークにおいて、送信帯域と優先クラスに従いパケットを送信するための端末装置であって、
上述のトラヒックシェーピング回路を有する回線インタフェース部と、
処理部と
を備え、
前記トラヒックシェーピング回路は、前記処理部からのパケットを、送信帯域及び優先クラスに従い網に送信する端末装置が提供される。
【００２７】
本発明の第４の解決手段によると、
端末装置に対する第１回線インタフェース部と、
網に対する第２回線インタフェース部と
前記第１回線インタフェース部及び前記第２回線インタフェース部とそれぞれ接続されたスイッチ部と
を備え、
前記第２回線インタフェースは、
上述のトラヒックシェーピング回路を有し、
該トラヒックシェーピング回路は、前記スイッチ部からのパケットを、送信帯域及び優先クラスに従い網に送信するネットワークノードが提供される。
【００２８】
本発明の第５の解決手段によると、
端末装置に対する第１回線インタフェース部と、
網に対する第２回線インタフェース部と、
上述のトラヒックシェーピング回路と、
前記第１回線インタフェース部と、前記第２回線インタフェース部と、前記トラヒックシェーピング回路にそれぞれ接続されたスイッチ部と、
を備え、
前記スイッチ部は、前記第１回線インタフェース部からのパケットを前記トラヒックシェーピング回路に転送し、及び、前記トラヒックシェーピング回路により送信帯域及び優先クラスに従い出力されたパケットを前記第２の回線インタフェース部を介して網に転送するネットワークノードが提供される。
【発明の効果】
【００２９】
本発明によれば、複数の帯域契約者（ユーザ等）が同一媒体（イーサ回線や無線ＬＡＮの様に共用の無線帯域でも可）の帯域を共有してパケットを転送する場合、ユーザ毎の契約帯域を遵守しつつ、同時に特定ユーザの低遅延パケットを優先的に転送し、遅延時間の増加を抑えるトラヒックシェーピング回路を提供できる。
【発明を実施するための最良の形態】
【００３０】
図２は、イーサ送信端末の構成図である。
以下では、実施の形態のひとつとして、図２の端末３００に、トラヒックシェーピング装置を適用した例を詳細に説明する。本トラヒックシェーピング装置では、イーサ送信端末がＶＬＬシェーピングと優先制御を同時に行う。ＶＬＬ（ｋ）（仮想コネクション）内に例えば２つのクラスＬＬＱ（ｋ）（第１優先クラス、第１キュー）、ＷＦＱ（ｋ）（第２優先クラス、第２キュー）を設け、クラス間の優先制御を行うケースを想定した（実施例１）。
【００３１】
前述の様に、ＶＬＬやＬＬＱ、ＷＦＱは帯域制御を活用したパケット交換網における仮想的な論理帯域の概念であり、特定のプロトコルには依存しない。従って、本実施の形態は、イーサパケットにも、ＩＰパケットにも、ＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ）パケットにも、ＡＴＭセルにも応用することができる。ＶＬＬ識別子としてＭＰＬＳのＳｈｉｍラベルやＩＰパケットヘッダやＶＬＡＮ−Ｔａｇ（Ｖｉｒｔｕａｌ  ＬＡＮ  Ｔａｇ）を適用する事も出来る。ここではイーサパケットに応用した場合について述べる。ここでは例えばＶＬＡＮ−ＴａｇをＶＬＬ識別子として適用し、ＶＬＡＮ−Ｔａｇ内のＵｓｅｒ  Ｐｒｉｏｒｉｔｙビットを優先転送クラスＬＬＱ、ＷＦＱの識別子として適用する場合を想定して説明する。
【００３２】
図２は、イーサ送信端末３００の構成図である。
イーサ送信端末３００は、例えば、ＣＰＵとメモリを有する上位層処理部３６０と、キャリアイーサ網３４０に対する回線インタフェース部３２４とを備える。上位層処理部３６０は、イーサ網を用いて情報を転送するための上位プロトコル（例えばＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ））が動作し、上位プロトコルが認識し得る上位パケットを生成・終端する。
【００３３】
回線インタフェース部３２４は、更に、イーサＤＭＡＣ（Ｄｙｎａｍｉｃ  Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）３５０と、トラヒックシェーピング部１００と、ＭＡＣ＆光モジュール３７４とを有する。イーサＤＭＡＣ３５０は、上位層処理部３６０で生成された上位パケットとイーサパケット（６４バイトから１５００バイト可変長）の送受信を行う。トラヒックシェーピング部１００は、キャリアイーサ網３４０と契約した帯域を守った送信間隔でパケットを送信する。ＭＡＣ＆光モジュール３７４は、イーサパケットを光ファイバ等の物理回線に対応した信号に変換して送信する。
【００３４】
図１は、トラヒックシェーピング部１００の構成を示すブロック図である。また、図４は、トラヒックシェーピング部１００の動作フロー図である。
トラヒックシェーピング部１００は、例えば、パケットバッファ部１１０と、ＬＬＱ送信予定時刻計算回路（第１送信予定時刻計算部）１３０と、ＬＬＱソーティング部（第１ソーティング部）１３５と、ＷＦＱ送信予定時刻計算部（第２送信予定時刻計算部）１４０と、ＷＦＱソーティング部（第２ソーティング部）１４５と、送信制御部１２０とを備える。
【００３５】
パケットバッファ部１１０は、パケットをＬＬＱ、ＷＦＱ毎のキューにキューイングする。送信制御部１２０は、最終的なパケット送信を決定し、パケットバッファ部１１０に伝える。ＬＬＱ送信予定時刻計算回路１３０は、ＬＬＱの契約帯域に従い、送信予定時刻を計算する。送信予定時刻の詳細は図７（ｂ）に記載しており、詳細は後述する。また、バケツ１５０３（後述）の水位を計算する。ＬＬＱソーティング部１３５は、ＬＬＱの中で、最も優先して送信するＬＬＱを選び出す。
【００３６】
ＷＦＱ送信予定時刻計算部１４０は、ＬＬＱの送信帯域と併せたＶＬＬの契約帯域に従い、送信予定時刻を計算する。送信予定時刻の詳細は図７（ｂ）に記載しており、詳細は後述する。また、バケツ１５０３（後述）の水位を計算する。ＷＦＱソーティング部１４５は、全ＷＦＱの中で最も優先して送信するＷＦＱを選び出す。
【００３７】
更に、詳細な構成要素を示すと、以下の様になる。
まず、パケットバッファ部１１０は、パケットバッファ１１１と、パケットバッファアドレスメモリ１１２と、パケットバッファ書込み制御回路１１３と、パケットバッファ読出し制御回路１１４とを有する。
【００３８】
パケットバッファ１１１は、パケットを一時的に蓄積しておくバッファである。パケットバッファアドレスメモリ１１２は、パケットバッファ内でＬＬＱ、ＷＦＱ毎のキューイングを実現するためのパケットバッファアドレスを記憶しておく。また、ＬＬＱ、ＷＦＱ毎のキュー長の情報も記憶しておく。パケットバッファ書込み制御回路１１３は、受信したパケットをパケットバッファに書込む。パケットバッファ読出し制御回路１１４は、パケットバッファから送信すべきパケットを読み出す。
【００３９】
また、ＬＬＱソーティング部１３５は、例えば、ＬＬＱ二分木ソート回路１３６とＬＬＱソーティング情報メモリ１３７を有する。
ＬＬＱ二分木ソート回路１３６は、パケット受信、または送信が行われたＬＬＱの送信予定時刻の変更を受けて、最も早い時刻に送信するＬＬＱを選び出す。ＬＬＱソーティング情報メモリ１３７は、ＬＬＱ二分木ソート回路１３６がソーティングを行うのに必要な情報（ＬＬＱ識別番号、ＬＬＱ送信予定時刻、ＬＬＱのＶＬＤ（以下、この三つをまとめてＬＬＱソーティング情報と呼ぶ））と、バケツの水位が記憶されている。ＬＬＱのＶＬＤは、例えば、該ＬＬＱに送信待ちパケットが存在するか否かを示すフラグである。ＶＬＬソーティング情報は二分木で管理されており、そのメモリマップを図５に示す（詳細は後述）。ＬＬＱソーティング情報メモリ１３７は、ＬＬＱ送信予定時刻計算回路１３０から、パケット受信、または送信が行われたＬＬＱの送信予定時刻の変更を受けて更新された送信予定時刻とバケツの水位を受信し、記憶する。
【００４０】
ＷＦＱソーティング部１４５は、例えば、ＷＦＱ二分木ソート回路１４６と、ＷＦＱソーティング情報メモリ１４７を有する。
ＷＦＱ二分木ソート回路１４６は、パケット受信、または送信が行われたＷＦＱの送信予定時刻の変更を受けて全ＷＦＱの中で最も優先して送信するＷＦＱを選び出す。ＷＦＱソーティング情報メモリ１４７は、ＷＦＱ二分木ソート回路１４６がソーティングを行うのに必要な情報（ＷＦＱ識別番号、ＷＦＱ送信予定時刻、ＷＦＱのＶＬＤ（以下、この三つをまとめてＷＦＱソーティング情報と呼ぶ））と、バケツの水位とが記憶されている。ＷＦＱのＶＬＤは、例えば、該ＷＦＱに送信待ちパケットが存在するか否かを示すフラグである。ＷＦＱソーティング情報も二分木で管理されており、そのメモリマップを図６に示す（詳細は後述）。ＷＦＱソーティング情報メモリ１４７は、ＷＦＱ送信予定時刻計算回路１４０から、パケット受信、または送信が行われたＷＦＱの送信予定時刻の変更を受けて更新された送信予定時刻とバケツの水位を受信し、記憶する。
【００４１】
本実施の形態のトラヒックシェーピング部１００は、１パケット処理時間に図４に示す次の６つの処理を繰り返すことによって、１パケット処理時間内に一つのパケットを受信し、一つのパケットを送信する。
（１）受信パケット判定処理
（２）送信予定時刻計算（パケット受信時）
（３）ソーティング処理（パケット受信時）
（４）送信ＬＬＱ選択処理
（５）送信予定時刻計算（パケット送信時）
（６）ソーティング処理（パケット送信時）
以上６つの処理の内、（１）〜（３）はパケット受信時の処理、（４）〜（６）はパケット送信時の処理である。以下に、それぞれの処理を、図１、図４に基づいて詳細に説明する。また、以下では、複数のＶＬＬ、ＬＬＱ、ＷＦＱを識別するために、識別番号ｋを付して、ＶＬＬ（ｋ）、ＬＬＱ（ｋ）、ＷＦＱ（ｋ）と表記する。
【００４２】
（１）受信パケット判定処理
トラヒックシェーピング部１００に到着したパケットは、ＬＬＱ毎、ＷＦＱ毎に設けられたキュー（第１キュー、第２キュー）に一時的に蓄積される。
本実施の形態のトラヒックシェーピング装置においては、パケットバッファ書込み回路１１３で、例えば、イーサＤＭＡＣ３５０から受信したイーサパケットのヘッダを参照し、該受信パケットの、ＶＬＬ情報（転送先）、ＬＬＱやＷＦＱの情報（優先度）を決定する。パケットバッファ書込み回路１１３は、パケットバッファ１１１内に転送先毎、かつ優先度毎に設けられたキューに、受信パケットをキューイングする。より具体的には、まず、パケットバッファ書込み制御回路１１３において、受信したパケットのヘッダ部に記述してあるＶＬＬＩ（Ｖｉｒｔｕａｌ  Ｌｅａｓｅｄ  Ｌｉｎｅ  Ｉｄｅｎｔｉｆｉｅｒ、ＶＬＬ識別子）、具体的にはＶＬＬを構成するＬＬＱＩ（ＬＬＱ  Ｉｄｅｎｔｉｆｉｅｒ、ＬＬＱ識別子）、ＷＦＱＩ（ＷＦＱ  Ｉｄｅｎｔｉｆｉｅｒ、ＷＦＱ識別子）を基に、該パケットが属するＶＬＬ、ＬＬＱあるいはＷＦＱを判別する。次に、受信パケットがＬＬＱの場合、ＬＬＱ毎のキューイングを行うためのパケットバッファのアドレスをパケットバッファアドレスメモリ１１２から読み出し、パケットバッファ内の該パケットバッファアドレスが示す領域（キュー）にパケットを書込む（図４の４００、４０１）。なお、受信パケットがＷＦＱの場合も同様に、ＷＦＱ毎のキューイングを行うためのアドレスに従い、パケットを書き込む。上述のパケットバッファアドレスは、パケットバッファアドレスメモリ１１２に記憶される。
【００４３】
また、パケットバッファ書込み制御回路１１３は、パケットを受信すると、パケットを受信したことを示すパケット受信信号９９を、ＬＬＱ送信予定時刻計算回路１３０とＷＦＱ送信予定時刻計算回路１４０に通知する。パケットバッファ書込み制御回路１１３は、パケット受信信号９９を送る際に、ＬＬＱパケットの場合、ＬＬＱ送信予定時刻計算回路１３０に向けてはＬＬＱ識別番号（第１キュー識別子）を通知し、ＷＦＱパケットの場合、ＷＦＱ送信予定時刻計算回路１４０に向けてはＷＦＱ識別番号（第２キュー識別子）を通知する。
【００４４】
次に、品質クラスがＬＬＱかＷＦＱかの判定を行い（図４の４３１）、判定結果に従い、図４の処理４０２又は図１４の処理１４０２に移る。
（２）送信予定時刻計算（パケット受信時）
まず、受信パケットがＬＬＱであった場合について述べる。
パケット受信信号９９及びＬＬＱ識別番号を受けたＬＬＱ送信予定時刻計算回路１３０は、ＬＬＱ識別番号ｋに基づき、ＬＬＱソーティング情報メモリ１３７からＬＬＱ（ｋ）のＶＬＤ（判別ビット）を読み出し、読み出されたＬＬＱ（ｋ）のＶＬＤ（図５の５０２）が‘０’であるか‘１’であるかを調べる（図４の４０２）。ＶＬＤが‘１’であるときは、既に該ＬＬＱ（ｋ）に送信待ちパケットが存在していることを示しており、送信予定時刻を変更してはいけない。一方、ＶＬＤが‘０’であるときは、既に計算してあるＬＬＱ（ｋ）のＬＬＱ送信予定時刻５０１をＬＬＱソーティング情報メモリ１３７から読み出し、該時刻が現在時刻を基準としたときに未来となっているか、過去あるいは現在時刻と同じになっているかを調べる（図４の４０４）。前者（未来）の場合にはＬＬＱ送信予定時刻５０１を変更しない。後者（過去あるいは現在）の場合には、例えば、
ＬＬＱ送信予定時刻＝現在時刻＋１
とする（図４の４０５）。また、変更されたＬＬＱ送信予定時刻をＬＬＱソーティング情報メモリ１３７のＬＬＱ（ｋ）の識別番号に対応して記憶する、なお、以上のいずれの場合にも、パケット受信信号９９を受けた場合には、該ＬＬＱ（ｋ）のＶＬＤ＝‘１’にセットする（図４の４０３）。
図１４は、受信パケットがＷＦＱであった場合のフローチャートである。図１４の各処理１４０２〜１４０８は、上述の図４の処理４０２〜４０８と同様であり、ＬＬＱがＷＦＱに変わったものである。
【００４５】
（３）ソーティング処理（パケット受信時）
各ＬＬＱのＬＬＱソーティング情報は二分木によって管理している（図５参照）。ＬＬＱ（ｋ）のＬＬＱ送信予定時刻が更新されると、全ＬＬＱの中で最も早くパケットを送信すべきＬＬＱ（以下、暫定送信ＬＬＱ）が変化している可能性があるので、ＬＬＱ二分木ソート回路１４６において暫定送信ＬＬＱを求めるためのソーティングを行う（図４の４０８）。ＬＬＱ用二分木の根には、全ＬＬＱの中で最優先に送信すべきＬＬＱのＬＬＱ識別番号５００、ＬＬＱ送信予定時刻５０１、ＶＬＤ５０２（図５参照）が記憶される。なお、ＷＦＱについても同様である。
【００４６】
本実施の形態のＶＬＬ（ＬＬＱ、ＷＦＱ）のソーティング処理規則は、以下のようになっている。
［１］子のＶＬＤが共に‘１’のときは、送信予定時刻がより過去である子を選択する。時刻が同じ場合はどちらでもよい。
［２］一方の子のＶＬＤが‘１’、他方が‘０’のときは、無条件にＶＬＤが‘１’である方を選択する。
［３］子のＶＬＤが共に‘０’のときは、送信予定時刻がより過去である子を選択する。時刻が同じ場合はどちらでもよい。
（４）送信ＬＬＱ選択処理
【００４７】
以下では、現在時刻とＬＬＱ送信予定時刻（あるいはＷＦＱ送信予定時刻）を比較した結果、現在時刻を基準としてＬＬＱ送信予定時刻が過去または現在時刻と同時刻であるとき、該ＬＬＱは送信可能状態と呼ぶことにする。ＷＦＱについても同様である。ＬＬＱ二分木ソート回路１３６によって選ばれた暫定送信ＬＬＱをＬＬＱ（ｉ）とする。同様に、暫定送信ＷＦＱをＷＦＱ（ｊ）とする。
【００４８】
送信制御回路１２０は、常時ＬＬＱ（ｉ）及びＷＦＱ（ｊ）が送信可能状態になったか否かを監視している（図４の４０９）。ＬＬＱ（ｉ）とＷＦＱ（ｊ）が共に送信可能状態でないときは、いかなるパケットも送信しない。ＬＬＱ（ｉ）、ＷＦＱ（ｊ）のいずれか又は双方が送信可能状態であるとき、ＬＬＱ（ｉ）を優先として、ＬＬＱ（ｉ）またはＷＦＱ（ｊ）のパケットを送信する（図４の４１０）。
【００４９】
具体的には、送信許可信号９５が、例えば、選択されたＬＬＱの識別番号ｉ又はＷＦＱの識別番号ｊとともに、送信制御回路１２０からパケットバッファ読出し制御回路１１４に送られる。送信許可信号９５を受けたパケットバッファ読出し制御回路１１４は、パケットバッファアドレスメモリ１１２から読み出したパケットバッファアドレスを用いて、パケットバッファ１１０からパケットを読み出して、回線インタフェース部３２４からパケットを送信する（図４の４１１）。また、送信制御回路１２０は、パケット送信信号９８を、ＬＬＱ送信時刻計算回路１３０およびＷＦＱ送信時刻計算回路１４０に送信する。
【００５０】
（５）送信予定時刻計算（パケット送信時）
以下、図４の処理４１３〜４１５について説明する。
パケット送信信号９８を受けたＬＬＱ送信時刻計算回路１３０およびＷＦＱ送信時刻計算回路１４０では、バケツの水位を更新し、契約帯域に従った次のパケット送信予定時刻を計算する（図４の４１３、４１４）。例えば、ＬＬＱ送信時刻計算回路１３０は、パケット送信信号９８とともに、選択されたＬＬＱの識別番号ｉを受信し、ＬＬＱ（ｉ）について次のパケットの送信予定時刻を計算する。なお、ＷＦＱについても同様である。次パケット送信予定時刻の計算は、例えばリーキーバケット方式を用いて行うことができる。リーキーバケット方式に関しては、例えば、「Ｔｈｅ  ＡＴＭ  Ｆｏｒｕｍ  ＴＭ４．０    Ｎｏｒｍａｔｉｖｅ  Ａｎｎｅｘ  Ｃ：  Ｔｒａｆｆｉｃ  Ｃｏｎｔｒａｃｔ  Ｒｅｌａｔｅｄ  Ａｌｇｏｒｉｔｈｍｓ  ａｎｄ  Ｐｒｏｃｅｄｕｒｅｓ、Ｐ．６２、６３」（非特許文献１）に述べられている。あるいは、他のパケット送信予定時刻の計算方法として、契約帯域に対応する送信間隔値（パケット長に依存するが）を記憶しておき、以下の計算を行っている。
【００５１】
非特許文献１に基づく送信ケースでは、例えば、次式で求める。
次のパケット送信予定時刻＝今回のパケット送信予定時刻＋送信間隔値
（送信間隔値は非特許文献１に従う）
パケット送信信号９２を受けたＬＬＱ送信予定時刻計算回路１３０とＷＦＱ送信予定時刻計算回路１４０では、非特許文献１のＡＴＭセルの場合と同様に契約帯域に従った次のパケット送信予定時刻を計算する。
【００５２】
本実施の形態においては、パケット長識別回路１９９を備え、パケットバッファ読出し回路１１４が、パケットバッファ１１１からイーサパケットを読み出したときに、ＩＰパケットヘッダに記述されているパケット長情報からイーサパケット長を算出する。算出したパケット長情報９１は、ＬＬＱ信予定時刻計算回路１３０及びＷＦＱ送信予定時刻計算回路１４０に伝えられる。パケット長情報９１を受けたＬＬＱ送信予定時刻計算回路１３０およびＷＦＱ送信予定時刻計算回路１４０では、例えば以下の計算を行い、予定送信時刻計算に用いる送信間隔を決定する。
送信間隔＝（契約帯域による最小イーサパケットの送信間隔）×（送信イーサパケット長）／（最小イーサパケット長）
【００５３】
この様に最小イーサパケット長で正規化することで、パケット長が短いイーサパケットを送信した場合には次のパケット送信までの時間は短く、パケット長が長いイーサパケットを送信した場合には次のパケット送信までの時間を長く空けることができる。
【００５４】
本実施の形態ではリーキーバケット方式に対する新方式として、図７（ａ）のリーキーバケツ１５０３の概念モデルを用いる。本リーキーバケツ１５０３は上述のＡＴＭ−Ｆｏｒｕｍのリーキーバケツと異なり、ＬＬＱ（ｋ）に対する閾値（第１の閾値）１５０１と、ＷＦＱ（ｋ）に対する閾値（第２の閾値）１５０９の２つの閾値を備えている。
【００５５】
リーキーバケツ１５０３には穴が開いており、ＶＬＬの契約帯域に応じた水量で水が漏れ続ける（水漏れ１５０２）。また、送信したパケットのパケット長に応じた水量１５０５が注ぎ込まれる。リーキーバケツ１５０３は、例えば、ＶＬＬ毎に備えられる。各ＶＬＬのバケツ１５０３の水位は、ＬＬＱソーティング情報メモリ１３７、ＷＦＱソーティング情報メモリ１４７のＬＬＱ識別番号、ＷＦＱ識別番号に対応して記憶されることができる（図５、図６参照）。なお、バケツの水位は、ＶＬＬの識別子に対応して、適宜のメモリに記憶されてもよい。
【００５６】
ＬＬＱ、ＷＦＱに対する送信予定時間や送信後の水位の計算は図７（ｂ）のアルゴリズムに基づいて行われる。
まず、ＬＬＱに対するアルゴリズムであるが、送信後の水位がＬＬＱ（ｋ）に対する閾値１５０１を超えない場合、ＬＬＱ送信予定時刻を現在時刻とし、送信後の水位と共にＬＬＱソーティング情報メモリ１３７に書込む。一方、閾値１５０１を超える場合は閾値１５０１以下になる将来時刻を算出し、送信後の水位と共にＬＬＱソーティング情報メモリ１３７に書込む。これにより水位が閾値に対して余裕がある場合は遅延時間なしで送信できる。余裕が無い場合はＬＬＱが想定帯域を超えている場合であり、割り当て帯域を遵守する時間を算出し、その時間まで送出を待たせることとなる。
【００５７】
ＷＦＱパケットに対するバケツ１５０３の閾値１５０９と比較してＷＦＱパケットが直ちに送出できない場合でも、次のパケットがＬＬＱパケットである場合、閾値１５０１が高く設定されている為、水位が余裕があればＬＬＱパケットは送信する事が可能になる。この判断が次のＬＬＱソーティング４１５において全ＬＬＱにおける優先順位付けを行い、優先度が高い場合、他のＷＦＱを抑えて次のサイクルの４０９に於いて送信が許可される。また、ＬＬＱに対するバケツ１５０３もＷＦＱに対するバケツ１５０３も同じバケツであるため、同一ＶＬＬ内のＬＬＱ、ＷＦＱどちらのパケットが送信されても、そのパケット分だけ水位は増すことになり、帯域は消費される。これにより、ＬＬＱパケットの優先転送と言う揺らぎはあるものの、該ＶＬＬ全体としては契約帯域を守った帯域サービスの提供が可能になる。
【００５８】
ＷＦＱに対するアルゴリズムは、送信後の水位がＷＦＱ（ｋ）に対する閾値１５０９を超えない場合、ＷＦＱ送信予定時刻を現在時刻とし、ＷＦＱソーティング情報メモリ１４７に書込む。一方、閾値１５０９を超える場合は閾値１５０９以下になる時刻を算出し、ＷＦＱソーティング情報メモリ１４７に書込む。同一ＶＬＬのＬＬＱパケットが送出された場合にも水位はパケット分上昇するので、次のパケットがＷＦＱパケットである場合は送信時間が水位上昇の影響を受け（次のパケットの送信判定し、閾値を超える可能性が増し）、ＬＬＱパケット分だけＷＦＱ送信帯域が減少するので、結果としてＶＬＬ帯域（ＬＬＱ帯域とＷＦＱ帯域の合計）は契約帯域に応じた水量１５０２に一致する（図４の４１３）。
【００５９】
（６）ソーティング処理（パケット送信時）
ソーティングの詳細は、パケット受信時と全く同様である。パケット送信予定時刻を修正した場合には、暫定送信ＬＬＱが変化している可能性があるので、ＬＬＱ二分木ソート回路１４６においてソーティングを行う（図４の４１５）。
以上の（１）〜（６）の処理が１パケット処理時間内に行われ、再び（１）の処理から繰り返す。
【００６０】
次に、ＬＬＱソーティング情報、ＷＦＱソーティング情報の管理方法について、図５、図６を用いて説明する。以下では、サポートできるＬＬＱ、ＷＦＱ数をＭ（＝２のｍ乗）とする。まず図５のＬＬＱに関して説明する。
ＬＬＱ用二分木の各要素と、ＬＬＱソーティング情報メモリ１３７のアドレスの関係は、以下に示す通りである。以下では、アドレスは２進数（ｍ＋１ビット）で示すこととする。
［１］二分木の根に対応するアドレスは、０００…００１番地である。
［２］アドレス：ｘｙｙ…ｙｙｚ番地の要素の親のアドレスは０ｘｙ…ｙｙｙ番地であり、二つの子のアドレスはｙｙｙ…ｙｚ０番地とｙｙｙ…ｙｚ１番地である。
【００６１】
上記［１］［２］の規則に従って情報を記憶していくと、二分木の葉に対応するアドレスは、１００…０００番地から１１１…１１１番地（全部で２のｍ乗＝Ｍ個）に記憶される。以上の規則でメモリのアドレスを管理していると、ソーティング時に行うメモリアクセスのためのアドレス生成回路を簡単に構成することができる。すなわち、ｘｙｙ…ｙｙｚ番地の比較相手はｘｙｙ…ｙｙ（ｚ’）番地に記憶してある情報（（ｚ’）はｚの‘０’←→‘１’反転を示す）であり、その比較結果を書込むのは０ｘｙ…ｙｙｙ番地である。従って、Ｍ個の要素のソーティングを、ｍ回のシフト演算とｍ回の反転演算で行うことができる。例として、８ＬＬＱ（ｍ＝３）の場合のＬＬＱソーティング情報メモリ１３７のメモリマップを図５に示す。前述の様に、ＬＬＱソーティング情報メモリ１３７には、ＬＬＱ識別番号５００、ＬＬＱ送信予定時刻５０１、およびＬＬＱのＶＬＤ５０２が記憶されている。図６のＷＦＱに関する説明も同様である。
【００６２】
なお、上記実施例１ではＶＬＬ内の優先度クラスとして、ＬＬＱとＷＦＱの２つの例を説明したが、２つ以上の優先度クラスを備えたシェ−ピング回路に対しても簡単に拡張でき、同様に有効である。
【００６３】
上述の例は、ひとつの回線に複数のＶＬＬが束ねられる例について説明したが、ＶＬＬはひとつでもよい。また、ＬＬＱソーティング情報メモリ、ＷＦＱソーティング情報メモリはひとつのメモリで構成されてもよい。例えば、ＶＬＬがひとつの場合は、ＬＬＱソーティング情報メモリ、ＷＦＱソーティング情報メモリはひとつのメモリで構成し、ＬＬＱ送信予定時刻と、ＷＦＱ送信予定時刻と、バケツの水位が記憶されてもよい。
【００６４】
（イーサスイッチ）
また、上述の例では、本実施の形態のトラヒックシェーピング装置をイーサ送信端末に適用した例を示したが、先に述べた様に、トラヒックシェーピング装置はイーサ送信端末の他にも、私設網から公衆網への中継点等の網内の要所に設置することがある（実施例２）。
【００６５】
図９に、本実施の形態のトラヒックシェーピング装置をキャリアイーサ網３４０に接続されているイーサスイッチ３０１に適用した構成図を示す。
イーサスイッチ３０１は、例えば、イーサ端末３３０、３３１に対する回線インタフェース部３２０、３２１、スイッチ部３１０、キャリアイーサ網３４０に対する回線インタフェース部３２５を備える。回線インタフェース部３２５は、キャリアイーサ網に対応したトラヒックシェーピング部１００と、ＭＡＣ＆光モジュール３７５を有する。
例えば、イーサ端末３３０から網へ第１のＶＬＬが設定され、イーサ端末３３１から網へ第２のＶＬＬが設定される。トラヒックシェーピング部１００は、各ＶＬＬの送信帯域と、ＬＬＱ／ＷＦＱに従い、端末からのパケットを網に転送する。
【００６６】
本実施の形態の他の例として、複数回線のトラヒックシェーピングを一つのトラヒックシェーピング装置で行うトランク方式のトラヒックシェーピング装置について説明する（実施例３）。
図１０は、トランク方式のトラヒックシェーピング装置としてイーサスイッチを構成した例を示している。
【００６７】
端末３３２、３３３で生成されたパケットフローは、イーサスイッチ３０２の回線インタフェース部３２２、３２３を介してスイッチ部３１１に入力される。スイッチ部３１１でいずれの出力先回線が決定された場合でも、パケットは一時的にトラヒックシェーピング部１０１に転送される。トラヒックシェーピング部１０１では、実施例１のトラヒックシェーピング部１００の各処理（例えば、ＶＬＬソーティング）と同じ動作を行う。トラヒックシェーピング部１０１の出力パケットは、再びスイッチ部３１１を介して、各出力回線の回線インタフェース部３２６、３２７からキャリアイーサ網３４０に送信される。トラヒックシェーピング部１０１から出力されたパケットがスイッチのパケットバッファに蓄積されると、トラヒックシェーピング部１０１の行ったトラヒックシェーピング処理が無意味なものとなってしまうために、トラヒックシェーピング部１０１から送信されたパケットは最優先で網まで転送されなければならない。
【００６８】
（無線帯域制御）
また、本実施の形態の他の実施例として、回線内の帯域を制御する方式に代わって、無線帯域を制御するトラヒックシェーピング装置について説明する（実施例４）。
図１１は、無線ＬＡＮ基地局３０３と複数の無線ＬＡＮ端末３０４間の無線帯域を、複数の無線ＬＡＮ端末３０４間の帯域制御で共用しつつ、トラヒックシェーピングを行うトラヒックシェーピング装置の構成例を示している。
【００６９】
無線ＬＡＮ基地局３０３は、ルータ３０４を介してインターネット網３４２に接続している。この場合、無線ＬＡＮ基地局３０３から無線ＬＡＮ端末３０４方向（以下Ｒｘ方向と呼ぶ）への帯域は無線ＬＡＮ基地局３０３で制御できるので、実施例１のトラヒックシェーピング装置と同様の機能と構成で良い。しかし、逆方向の無線ＬＡＮ端末３０４への帯域から無線ＬＡＮ基地局３０３方向（以下Ｔｘ方向と呼ぶ）への帯域は、複数存在する無線ＬＡＮ端末では全体の送信要求が把握できない。無線帯域は共用されているので、このＴｘ方向の帯域制御を行う調停機能（実施例１のトラヒックシェーピング回路１００に相当する）が必要であり、これがＴｘトラヒックシェーピング部１４１００−Ｒと１４１００−Ａに分かれて実現されている。
【００７０】
すなわち、各無線ＬＡＮ端末３０４は回線インタフェース部（図２の３２４に相当）内のトラヒックシェーピング部としてトラヒックシェーピング部１４１００−Ｒを備える。トラヒックシェーピング部１４１００−Ｒは、パケットバッファ１４１１０（図１のパケットバッファ部１１０に相当）を備える。
【００７１】
また、無線ＬＡＮ基地局３０３の回線インタフェース部（回線インタフェース部３２４に相当）は、複数の無線ＬＡＮ端末３０４から無線帯域へのパケット送信要求の調停（アービトレーション）を行なう機能として、トラヒックシェーピング部１４１００−Ａを備える。トラヒックシェーピング部１４１００−Ａは、図１のトラヒックシェーピング部１００からパケットバッファ部１１０を除いた機能を備え、かつＶＬＬやＬＬＱ、ＷＦＱに対する帯域制御の他に複数の無線ＬＡＮ端末３０４間の帯域制御も行う（実施例３に相当する）。Ｔｘトラヒックシェーピング部１４１００−Ｒと１４１００−Ａ間は、例えば、パケット送信用の帯域の他に、パケット送信要求と許可をやり取りする無線の制御チャネル帯域があり、そのチャネル上で、パケット受信信号１４０９９（パケット受信信号９９に相当）、パケット送信信号１４０９２（パケット送信信号９２に相当）、送信許可信号１４０９５（送信許可信号９５に相当）がやり取りされる。Ｔｘトラヒックシェーピング部１４１００−Ａは、複数のＴｘトラヒックシェーピング部１４１００−Ｒからのパケット受信信号１４０９９とパケット送信信号１４０９２によって、各無線ＬＡＮ端末３０４の各Ｔｘトラヒックシェーピング部１４１００−Ｒの状況を把握し、次に許可すべき送信要求を送信制御部内の調停機構によって決定し、選択された無線ＬＡＮ端末３０４の選択されたＶＬＬの選択されたＶＳ（優先クラス）に対する送信許可を送信許可信号１４０９５で通知する。
【００７２】
なお、例えば、送信制御部は、送信許可信号１４０９５を選択された無線ＬＡＮ端末３０４に送信するようにしてもよい。また、例えば、全ての無線ＬＡＮ端末３０４に送信して、無線ＬＡＮ端末３０４のパケットバッファ読出し制御回路が自端末に対する送信許可信号かを判断してもよい。
【００７３】
以上はパケット送信用（Ｔｘ方向）の無線帯域について説明したが、パケット送信用（Ｔｘ方向）の無線帯域とパケット受信用（Ｒｘ方向）の無線帯域、さらには上記制御チャネル帯域は共用されていても良い。この場合、Ｔｘ方向の帯域アービトレーションとＲｘ方向の帯域アービトレーションが送信制御部１４０９５内で統合されて実行される。
【００７４】
また、イーサパケットを対象に無線ＬＡＮ網に対する本実施の形態を示したが、本実施の形態は、イーサに特化したものではなく、携帯電話や衛星通親等の無線帯域を共用するパケット通信に対しても同様にトラヒックシェーピングを行い、同様の効果を得る事ができる。
【００７５】
（共通回線）
さらに、本実施の形態の網での他の例として、例えば、インターネット等の様に、共用回線を利用して複数の網を接続し、それらの網毎に共用回線を契約している場合を考える。図１３にこの様な形態の網を示す（実施例５）。
【００７６】
図１３において、網Ａ１８１０と網ａ１８２０はプロバイダＡが所有し、端末１８１１、１８２１はプロバイダＡのユーザとする。同様に、網Ｂ１８３０と網ｂ１８４０はプロバイダＢが所有し、端末１８３１、１８４１はプロバイダＢのユーザとする。また、網Ａ、網ａ、網Ｂ、網ｂはそれぞれルータＲによって網Ｃ１８００に接続されている。プロバイダＡ、プロバイダＢは、それぞれ網Ｃとの間に送信帯域を契約し、網Ｃの中では共用回線１８０１をプロバイダＡ、プロバイダＢが共用で使用している。この様な網環境で、端末１８１１と端末１８２１が通信を行う場合、また端末１８３１と端末１８４１が通信を行う場合には、共用回線１８０１の入口では、共用回線を契約した帯域を守りつつ（ＡＴＭでいうところの固定帯域サービスのＶＰに相当）、該契約帯域内で転送されているパケット毎に優先度を設けて（例えば、ＴＥＬＮＥＴ用のパケットは、電子メール用のパケットよりも優先する等。なお、優先度情報はＩＰパケットヘッダのＴＯＳバイトに反映されても良い）、帯域を管理できる（ＡＴＭでいうところのＶＣに相当）ことが望ましい。以上の様な帯域を有効活用する形態は、プロバイダによる回線の共用のみではなく、複数の企業が長距離通信回線を共用する場合、あるいは同一企業内でも部課毎のトラヒックを管理したい場合等、様々な運用形態が考えられる。
【００７７】
また、ここでは同一回線に出力される帯域をＶＬＬとＶＳの２階層に分類し、ＶＬＬはユーザの契約帯域（網管理者とユーザなど相互にサービスを契約する関係）の単位に、ＶＳはその契約帯域をユーザがより有効に活用する為のユーザの要求に従って制御する帯域制御単位として説明した。本実施の形態は、２階層に限定されるものではなく、更に階層が多いケースにも容易に拡張できる。
【産業上の利用可能性】
【００７８】
本発明は、例えば、固定長・可変長パケットの送信端末、またはネットワークノード（ルータ等）におけるトラヒックシェーピング回路等に関する産業に利用可能である。特に、低遅延揺らぎの転送品質を要求する音声サービスを含み、帯域に於いてはユーザ毎の（重み付け）公平性を要求するサービスを行うサービスエッジノードに適する。
【図面の簡単な説明】
【００７９】
【図１】本発明のトラヒックシェーピング回路全体の構成図。
【図２】本発明のトラヒックシェーピング回路を端末装置に実装した場合の構成図。
【図３】本発明のトラヒックシェーピング回路がシェーピングする帯域構成を示すイメージ図。
【図４】本発明のトラヒックシェーピング回路の処理フロー図。
【図５】本発明のトラヒックシェーピング回路のＬＬＱソーティング情報メモリ構造図。
【図６】本発明のトラヒックシェーピング回路のＷＦＱソーティング情報メモリ構造図。
【図７】本発明のトラヒックシェーピング回路のＬＬＱ（ｋ）予想時刻計算回路１３１、ＷＦＱ（ｍ）予定時刻計算回路１４１内の判定アルゴリズムイメージ図（ＷＦＱに対する閾値の他にＬＬＱに対する閾値を備える）。
【図８】本発明のトラヒックシェーピング回路により解決すべき遅延時間が増加する場合と増加しない場合のタイムチャート。
【図９】本発明のトラヒックシェーピング装置をキャリアイーサ網３４０に接続されているイーサスイッチ３０１に適用した構成図。
【図１０】トランク方式のトラヒックシェーピング装置としてイーサスイッチを構成した例。
【図１１】無線ＬＡＮ基地局３０３と複数の無線ＬＡＮ端末３０４間の無線帯域を、複数の無線ＬＡＮ端末３０４間の帯域制御で共用しつつ、トラヒックシェーピングを行うトラヒックシェーピング装置の構成例。
【図１２】トラヒックシェーピング回路を備えた送信端末（ユーザ端末）に通信サービスを提供する網。
【図１３】共用回線を利用して複数の網を接続し、それらの網毎に共用回線を契約している。
【図１４】受信パケットがＷＦＱの場合のフローチャート。
【符号の説明】
【００８０】
１００  トラヒックシェーピング部
１１０  パケットバッファ部
１１１  パケットバッファ
１１２  パケットバッファアドレスメモリ
１１３  パケットバッファ書込み制御回路
１１４  パケットバッファ読出し制御回路
１２０  送信制御部
１３０  ＬＬＱ送信予定時刻計算回路
１３５  ＬＬＱソーティング部
１３６  ＬＬＱ二分木ソート回路
１３７  ＬＬＱソーティング情報メモリ
１４０  ＷＦＱ送信予定時刻計算部
１４５  ＷＦＱソーティング部
１４６  ＷＦＱ二分木ソート回路
１４７  ＷＦＱソーティング情報メモリ
１９９  パケット長識別回路
３００  イーサ送信端末
３０１  イーサスイッチ
３０３  無線ＬＡＮ基地局
３０４  無線ＬＡＮ端末
３１０、３１１  スイッチ部
３２０、３２１、３２２、３２３、３２５、３２６、３２７  回線インタフェース部
３６０  上位層処理部
３４０  キャリアイーサ網
３２４  回線インタフェース部
３５０  イーサＤＭＡＣ
３７４  ＭＡＣ＆光モジュール
１５０１  ＬＬＱ（ｋ）に対する閾値
１５０２  契約帯域に応じた水漏れ
１５０３  リーキーバケツ１
１５０５  パケット長に応じた水量
１５０９  ＷＦＱ（ｋ）に対する閾値
１４１００−Ｒ、１４１００−Ａ  Ｔｘトラヒックシェーピング部
【図１】
2008263430.tif 000003
【図２】
2008263430.tif 000004
【図３】
2008263430.tif 000005
【図４】
2008263430.tif 000006
【図５】
2008263430.tif 000007
【図６】
2008263430.tif 000008
【図７】
2008263430.tif 000009
【図８】
2008263430.tif 000010
【図９】
2008263430.tif 000011
【図１０】
2008263430.tif 000012
【図１１】
2008263430.tif 000013
【図１２】
2008263430.tif 000014
【図１３】
2008263430.tif 000015
【図１４】
2008263430.tif 000016