(57)【要約】【課題】  帯域保証の性能が改善された帯域制御装置及び帯域制御方法を提供する。【解決手段】  帯域制御装置は、要求に応じパケットのトークンを供給する供給部と、パケットのフローごとに前記供給部に前記トークンを要求し、該要求に応じ供給された前記トークンに基づき、前記フローごとにパケットの通過を制御する通過制御部と、前記フローごとのパケットの入力レートと前記フローごとに設定された設定値を比較し、該比較結果に応じて前記供給部に対する前記要求の優先度を前記フローごとに制御する優先度制御部とを有する。【選択図】図５
2017041807.tif 000002
【特許請求の範囲】
【請求項１】
要求に応じパケットのトークンを供給する供給部と、
パケットのフローごとに前記供給部に前記トークンを要求し、該要求に応じ供給された前記トークンに基づき、前記フローごとにパケットの通過を制御する通過制御部と、
前記フローごとのパケットの入力レートと前記フローごとに設定された設定値を比較し、該比較結果に応じて前記供給部に対する前記要求の優先度を前記フローごとに制御する優先度制御部とを有することを特徴とする帯域制御装置。
【請求項２】
前記優先度制御部は、前記入力レートが前記設定値以下である前記フローの前記要求の優先度を、前記入力レートが前記設定値を上回る前記フローの前記要求の優先度より高い値とすることを特徴とする請求項１に記載の帯域制御装置。
【請求項３】
前記優先度制御部は、前記要求の優先度を、前記入力レートと前記設定値の差分に応じた複数の段階に分けることを特徴とする請求項１または２に記載の帯域制御装置。
【請求項４】
前記通過制御部は、パケットを通過させるたびに前記フローごとに前記トークンを減算し、前記トークンが所定の第１閾値を下回ったとき及び前記所定の第１閾値より小さい所定の第２閾値を下回ったとき、前記トークンを要求することを特徴とする請求項１乃至３の何れかに記載の帯域制御装置。
【請求項５】
前記優先度制御部は、
前記トークンが前記所定の第２閾値を下回った前記フローの前記要求の優先度を、前記トークンが前記所定の第１閾値を下回った前記フローの前記要求の優先度より高い値とし、
前記トークンが前記所定の第２閾値を下回った前記フローのうち、前記入力レートが前記設定値以下である前記フローの前記要求の優先度を、前記入力レートが前記設定値を上回る前記フローの前記要求の優先度より高い値とすることを特徴とする請求項４に記載の帯域制御装置。
【請求項６】
前記優先度制御部は、前記所定の第１閾値と前記所定の第２閾値の差分、及び前記トークンが前記所定の第１閾値を下回ったときと前記トークンが前記所定の第２閾値を下回ったときの時間差から前記入力レートを算出することを特徴とする請求項４または５に記載の帯域制御装置。
【請求項７】
前記優先度制御部は、前記所定の第１閾値を下回ったときと前記所定の第２閾値を下回ったときの前記トークンの差分、及び前記トークンが前記所定の第１閾値を下回ったときと前記トークンが前記所定の第２閾値を下回ったときの時間差から前記入力レートを算出することを特徴とする請求項４または５に記載の帯域制御装置。
【請求項８】
前記優先度制御部は、複数回算出した前記入力レートの平均値を算出し、前記平均値と前記設定値を比較し、該比較結果に応じて前記要求の優先度を制御することを特徴とする請求項１乃至７の何れかに記載の帯域制御装置。
【請求項９】
前記通過制御部は、前記トークンに基づきパケットを廃棄し、
前記優先度制御部は、前記通過制御部における前記トークンの要求から供給までの期間ごとに前記フローごとのパケットの廃棄の有無を検出し、複数の期間における該廃棄の判定回数と前記フローごとの所定回数を比較し、該比較結果に応じて前記供給部に対する前記トークンの要求の優先度を前記フローごとに制御することを特徴とする請求項１乃至８の何れかに記載の帯域制御装置。
【請求項１０】
要求に応じパケットのトークンを供給する供給部に、パケットのフローごとに前記トークンを要求し、
該要求に応じ供給された前記トークンに基づき、前記フローごとにパケットの通過を制御し、
前記フローごとのパケットの入力レートと前記フローごとに設定された設定値を比較し、
該比較結果に応じて前記供給部に対する前記要求の優先度を前記フローごとに制御することを特徴とする帯域制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、帯域制御装置及び帯域制御方法に関する。
【背景技術】
【０００２】
ルータやレイヤ２スイッチなどの通信装置には、入力されるパケットのレートを制御するためにポリサが設けられる場合がある。ポリサは、トークンバケットに供給されるトークンを消費することでパケットを通過させ、トークンが不足する場合、パケットを廃棄することにより、入力されるパケットのフローごとに帯域を制御する。
【０００３】
フローは、パケットのＶＩＤ（VLAN(Virtual Local Area Network) Identifier）やＭＰＬＳ（Multi-Protocol Label Switching）ラベルなどで識別される。各ポリサのトークンの供給レートは、フローごとにユーザが契約した帯域などに応じて決定される。なお、特許文献１には、ユーザの送信レートが契約帯域を超えているか否かを判定するルータが開示されている。
【０００４】
例えば、ＭＥＦ（Metro Ethernet Forum）には、あるフローの余剰分のトークンを他のフローに供給するポリシングのアルゴリズムが規定されている。このアルゴリズムによると、例えば、音声信号のフロー及びデータ信号のフローが存在する場合、音声信号に割り当てられた帯域の余剰分を利用してデータ信号を通過させることができる。
【０００５】
一例として、音声信号の帯域が５（Mbps）であり、データ信号の帯域が１０（Mbps）である場合、音声信号が３（Mbps）しか流れないとすると、データ信号は１２（Mbps）（＝１０＋２）まで流すことができる。実際のポリシング処理では、上位のポリサのトークンバケットにトークンが加算されたとき、そのトークンの余剰分が下位のポリサのトークンバケットに加算される。
【０００６】
例えば特許文献２には、上述したアルゴリズムに関連する分散ポリシングの手法が開示されている。分散ポリシングでは、ユーザの契約帯域に応じてトークンが供給されるメインバケツと、フローごとのトークンを蓄積するミニバケツとが用いられ、メインバケツから各フローのミニバケツにトークンが供給される。
【０００７】
ミニバケツには閾値が設定され、トークンの蓄積量が閾値を下回った場合、メインバケツに対してトークンが要求される。複数のミニバケツは同時にトークンを要求する場合があるため、ソフトウェアなどによる低速処理でも正常にトークンが供給されるように、要求を保持する待ち合わせバッファが用いられる。
【０００８】
待ち合わせバッファには、通常用キュー及び緊急用キューが設けられている。通常用キューには、トークンの蓄積量が上記の閾値を下回ったときの要求が保持され、緊急用キューには、トークンの蓄積量が、上記の閾値より低い閾値を下回ったときの要求が保持される。メインバケツからのトークンの供給は、通常用キュー内の要求より優先して緊急用キュー内の要求に応じて行われる。これにより、トークンが枯渇しそうなミニバケツに対して、優先的にトークンが供給される。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００１−３４５８４９号公報
【特許文献２】特開２０１３−１９７８２３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
トークンの消費量は、パケットの出力レートだけでなく、入力レートにも依存する。このため、入力レートが契約帯域のレートを上回る場合、トークンを使い切りつつ、契約帯域分の出力レートだけが確保される。なお、契約帯域を超える分のパケットは廃棄される。
【００１１】
したがって、入力レートが契約帯域のレートを上回る多数のフローが存在する場合、通常は輻輳しない緊急用キューが、多数の要求により輻輳してしまう。このため、入力レートが契約帯域のレート以下であるフローのトークンの蓄積量が枯渇しそうな場合、トークンを要求しても、トークンの供給が間に合わずにパケットが廃棄されてしまう。したがって、入力レートが契約帯域のレート以下であるフローについて、契約帯域が保証されないという問題が生ずる。
【００１２】
そこで本件は上記の課題に鑑みてなされたものであり、帯域保証の性能が改善された帯域制御装置及び帯域制御方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本明細書に記載の帯域制御装置は、要求に応じパケットのトークンを供給する供給部と、パケットのフローごとに前記供給部に前記トークンを要求し、該要求に応じ供給された前記トークンに基づき、前記フローごとにパケットの通過を制御する通過制御部と、前記フローごとのパケットの入力レートと前記フローごとに設定された設定値を比較し、該比較結果に応じて前記供給部に対する前記要求の優先度を前記フローごとに制御する優先度制御部とを有する。
【００１４】
本明細書に記載の帯域制御方法は、要求に応じパケットのトークンを供給する供給部に、パケットのフローごとに前記トークンを要求し、該要求に応じ供給された前記トークンに基づき、前記フローごとにパケットの通過を制御し、前記フローごとのパケットの入力レートと前記フローごとに設定された設定値を比較し、該比較結果に応じて前記供給部に対する前記要求の優先度を前記フローごとに制御する。
【発明の効果】
【００１５】
帯域保証の性能を改善できる。
【図面の簡単な説明】
【００１６】
【図１】通信装置の一例を示す構成図である。
【図２】インターフェースカードの機能構成一例を示す構成図である。
【図３】比較例のポリサの通常時の動作例を示す図である。
【図４】比較例のポリサの異常時の動作例を示す図である。
【図５】実施例のポリサの一例を示す構成図である。
【図６】通過制御部の動作の一例を示すフローチャートである。
【図７（ａ）】トークン蓄積量の変化の一例を示すグラフである。
【図７（ｂ）】レート監視テーブルの一例を示す図である。
【図８】トークン蓄積量が第１閾値を下回ったときのポリサの動作の一例を示す図である。
【図９（ａ）】入力レート＞契約レートの場合にトークン蓄積量が第２閾値を下回ったときのポリサの動作の一例を示す図である。
【図９（ｂ）】入力レート≦契約レートの場合にトークン蓄積量が第２閾値を下回ったときのポリサの動作の一例を示す図である。
【図１０（ａ）】通常要求メッセージの出力例を示す図である。
【図１０（ｂ）】緊急要求メッセージの出力例を示す図である。
【図１１】要求判定部の動作の一例を示すフローチャートである。
【図１２（ａ）】更新前のレート監視テーブルの一例を示す図である。
【図１２（ｂ）】更新後のレート監視テーブルの一例を示す図である。
【図１３】要求判定部の動作の他例を示すフローチャートである。
【図１４（ａ）】レート監視テーブルの他例を示す図である。
【図１４（ｂ）】パケット廃棄の期間の数≦上限数の場合にトークン蓄積量が第２閾値を下回ったときのポリサの動作の一例を示す図である。
【図１４（ｃ）】パケット廃棄の期間の数＞上限数の場合にトークン蓄積量が第２閾値を下回ったときのポリサの動作の一例を示す図である。
【図１５】レート監視テーブルの更新処理の一例を示すフローチャートである。
【図１６】要求判定部の動作の他例を示すフローチャートである。
【図１７（ａ）】通常要求メッセージが入力された場合の他例の優先制御部の動作を示す図である。
【図１７（ｂ）】入力レート≦契約レートのフローの緊急要求メッセージが入力された場合の他例の優先制御部の動作を示す図である。
【図１７（ｃ）】入力レート＞契約レートのフローの緊急要求メッセージが入力された場合の他例の優先制御部の動作を示す図である。
【図１８】要求判定部の動作の他例を示すフローチャートである。
【図１９（ａ）】通常要求メッセージが入力された場合の他例の優先制御部の動作を示す図である。
【図１９（ｂ）】入力レート≦契約レート／２のフローの緊急要求メッセージが入力された場合の他例の優先制御部の動作を示す図である。
【図１９（ｃ）】契約レート／２＜入力レート≦契約レートのフローの緊急要求メッセージが入力された場合の他例の優先制御部の動作を示す図である。
【図２０（ａ）】契約レート＜入力レート≦２×契約レートのフローの緊急要求メッセージが入力された場合の他例の優先制御部の動作を示す図である。
【図２０（ｂ）】２×契約レート＜入力レートのフローの緊急要求メッセージが入力された場合の他例の優先制御部の動作を示す図である。
【図２１】要求判定部の動作の他例を示すフローチャートである。
【図２２】実施例のポリサの効果を示す図である。
【発明を実施するための形態】
【００１７】
図１は、通信装置の一例を示す構成図である。通信装置は、複数のインターフェースカード９１と、２枚のスイッチカード９２と、コントロールカード９３とを有する。各カード９１〜９３は、筐体に設けられた個別のスロットに収容され、互いに電気的に接続される。なお、本明細書では、実施例の帯域制御装置を実装した通信装置として、レイヤ２スイッチやルータなどを例に挙げるが、これに限定されず、実施例の帯域制御装置は、例えば波長多重伝送装置などの他種の通信装置にも同様に実装される。
【００１８】
通信装置は、他装置から受信したパケットを、その宛先に従って他装置に中継する。なお、本明細書において、パケットとは、伝送されるデータ（情報）の伝送単位（ＰＤＵ：Protocol Data Unit）であり、例としてイーサネット（登録商標、以下同様）フレームを挙げるが、これに限られず、ＩＰ（Internet Protocol）パケットなどの他のＰＤＵが用いられてもよい。
【００１９】
インターフェースカード９１は、それぞれ、他装置との間において、パケットを送受信する。他装置としては、例えば、パーソナルコンピュータなどの端末装置、サーバ、及びルータが挙げられる。インターフェースカード９１は、複数のポートにより光ファイバと接続され、例えば１０ＧＢＡＳＥ−ＬＲの規格に基づく通信を行う。
【００２０】
２枚のスイッチカード９２は、それぞれ、複数のインターフェースカード９１の間において、パケットを交換する。より具体的には、スイッチカード９２は、インターフェースカード９１からパケットが入力され、パケットを、その宛先に応じたインターフェースカード９１に出力する。２枚のスイッチカード９２は、例えば、ハードウェア故障などの障害に備えて、現用系及び予備系として使用される。
【００２１】
コントロールカード９３は、複数のインターフェースカード９１及び２枚のスイッチカード９２を制御する。コントロールカード９３は、ネットワーク制御装置などと接続され、ユーザーインターフェースに関する処理、各カード９１，９２に対する設定処理、及び各カード９１，９２からの情報収集処理などを行う。コントロールカード９３は、これらの処理を実行するＣＰＵ（Central Processing Unit）などのプロセッサ９３０、及び、プロセッサ９３０を駆動するプログラムを記憶するメモリ９３１を有する。
【００２２】
また、コントロールカード９３には、後述するように、所定のアルゴリズムに従いトークンが供給されるメインバケツが実装されてもよい。メインバケツに蓄積されたトークンは、要求に応じて各インターフェースカード９１に設けられたミニバケツに供給される。このような機能は、ネットワーク機能仮想化（NFV: Network Functions Virtualization）により例えばプロセッサ９３０、つまりソフトウェアにより実現される。
【００２３】
しかし、１００（Gbps）を超えるようなトラフィックの帯域制御処理をプロセッサ９３０で実現することは処理速度の観点から困難である。このため、ミニバケツを用いた帯域制御処理は、インターフェースカード９１内のハードウェアに分担させるのが好ましい。なお、帯域制御処理は、これに限定されず、その全てがインターフェースカード９１に実装されてもよい。
【００２４】
図２は、インターフェースカード９１の機能構成を示す構成図である。インターフェースカード９１は、複数の光送受信器９１０と、ＰＨＹ／ＭＡＣ部９１１と、入力処理部９１２と、出力処理部９１３と、制御部９１４と、記憶部９１５とを有する。
【００２５】
複数の光送受信器９１０は、それぞれ、他装置から光ファイバを介して受信した光信号を電気信号に変換してＰＨＹ／ＭＡＣ部９１１に出力し、また、ＰＨＹ／ＭＡＣ部９１１から入力された電気信号を光信号に変換し、光ファイバを介して他装置に送信する。つまり、複数の光送受信器９１０は、他装置との間でパケットを送受信するための複数のポート＃１〜＃Ｎ（Ｎ：正の整数）として機能する。
【００２６】
ＰＨＹ／ＭＡＣ部９１１は、他装置とのリンクの確立処理や複数の光送受信器９１０に対するパケットの分配処理などを行う。ＰＨＹ／ＭＡＣ部９１１は、複数の光送受信器９１０から入力されたパケットを入力処理部９１２に出力し、出力処理部９１３から入力されたパケットを複数の光送受信器９１０に出力する。
【００２７】
入力処理部９１２及び出力処理部９１３は、ＦＰＧＡ（Field Programmable Gate Array）やＡＳＩＣ（Application Specific Integrated Circuit）などの論理回路であり、イングレス（INGRESS）及びイーグレス（EGRESS）のパケット処理をそれぞれ行う。入力処理部９１２は、ＰＨＹ／ＭＡＣ部９１１から入力されたパケットの帯域制御処理などを行って、スイッチカード９２にパケットを出力する。
【００２８】
出力処理部９１３は、スイッチカード９２から入力されたパケットの送信レートの制御処理などを行って、ＰＨＹ／ＭＡＣ部９１１にパケットを出力する。記憶部９１５は、メモリなどの記憶手段であり、入力処理部９１２及び出力処理部９１３が処理に用いる各種のデータを記憶する。
【００２９】
制御部９１４は、コントロールカード９３と通信を行い、入力処理部９１２及び出力処理部９１３の制御を行う。制御部９１４は、ＣＰＵなどのプロセッサ及びメモリ（図示せず）を備える。制御部９１４の処理としては、例えば、入力処理部９１２及び出力処理部９１３の各種の設定処理、及び入力処理部９１２及び出力処理部９１３で検出された警報の収集処理などが挙げられる。なお、帯域制御処理の一部を、制御部９１４のソフトウェア処理により実現することも可能である。
【００３０】
図３には、比較例のポリサの通常時の動作例が示されている。ポリサは、帯域制御装置の一例であり、フローごとに入力されるパケットの帯域制御を行う。本比較例は、一例として、上記の特許文献２に開示された分散ポリシングの手法に基づくものである。
【００３１】
ポリサは、その構成を単純化した場合、メインバケツ８０と、待機処理部８１と、ミニバケツ８２とを有する。メインバケツ８０には、一例として、フロー＃１〜＃４のそれぞれについて、ユーザの契約帯域に応じたレート（以下、「契約レート」と表記）でトークンが加算される。本例では、フロー＃１〜＃３には１０（Mbps）のレートでトークンが加算され、フロー＃４には１（Gbps）のレートでトークンが加算される。なお、トークンの量は、通過を許容するパケットのデータ量（通過許容量）を表し、トークンの加算のアルゴリズムには限定はない。
【００３２】
メインバケツ８０は、高い処理速度は要求されないため、例えばコントロールカード９３のプロセッサ９３０のソフトウェア処理により実現される。このため、トークンの加算のアルゴリズムは、ソフトウェアの変更により柔軟にカスタマイズすることができる。メインバケツ８０のトークンは、要求に応じてミニバケツ８２に供給される。
【００３３】
ミニバケツ８２は、フロー＃１〜＃４ごとに設けられる。各フロー＃１〜＃４のパケットは、ミニバケツ８２内のトークン蓄積量が０より大きい場合、ポリサを通過し、トークン蓄積量が０以下である場合、廃棄される。これにより、フロー＃１〜＃４ごとの入力帯域が制御される。
【００３４】
このような通過制御の機能は、ポリサでは一般的であり、また、パケットの入力レートに応じた高い処理速度が要求されるため、ハードウェアにより構成されてもよい。ミニバケツ８２は、例えばインターフェースカード９１の入力処理部９１２に設けられる。
【００３５】
本例では、各フロー＃１〜＃４のパケットの入力レートは、契約レートと同じであると仮定する。より具体的には、フロー＃１〜＃３の入力レートは１０（Mbps）であり、フロー＃４の入力レートは１（Gbps）である。
【００３６】
このため、メインバケツ８０から各フロー＃１〜＃４のミニバケツ８２には、入力レートに対して十分なトークンが供給される。これにより、以下に述べるように、フロー＃１〜＃３には１０（Mbps）の出力レートが確保され、フロー＃４には１（Gbps）の出力レートが確保される。
【００３７】
ミニバケツ８２には閾値が設定され、トークン蓄積量が閾値を下回った場合、メインバケツ８０に対してトークンが要求される。複数のミニバケツ８２から同時にトークンを要求されると、ハードウェアとソフトウェアの処理速度の差によりトークンの供給が滞る可能性がある。このため、ハードウェア、つまり入力処理部９１２には、トークンの要求を保持し待機させる待機処理部８１が設けられる。
【００３８】
しかし、フロー＃１〜＃４のうち、出力レートが高いフロー＃４は、トークンの減少が他のフロー＃１〜＃３より早いため、待機処理部８１内で要求が輻輳した場合、トークンの供給がパケットの通過に間に合わないおそれがある。もっとも、仮に出力レートが低いフロー＃１〜＃３だけのパケットを通過させるのであれば、ミニバケツ８２の閾値とメインバケツ８０からのトークンの供給量を調整することにより、トークン供給を間に合わせることは可能である。しかし、本例のように、出力レートが高いフロー＃４と出力レートが低いフロー＃１〜＃３は混在する場合のほうが現実的である。
【００３９】
そこで、ミニバケツ８２には、第１閾値ｔｈ１と、第１閾値より小さい第２閾値ｔｈ２とが設定され、これに合わせて、待機処理部８１には、優先度の異なる優先キュー８１０及び通常キュー８１１が設けられている。トークン蓄積量が第１閾値ｔｈ１を下回った場合、通常要求メッセージが出力され、通常キュー８１１に入力される。一方、トークン蓄積量が第２閾値ｔｈ２を下回った場合、緊急要求メッセージが出力され、優先キュー８１０に格納される。
【００４０】
図３の例では、フロー＃１〜＃３のトークン蓄積量が第１閾値ｔｈ１を下回り、通常要求メッセージＲＱ＃１〜＃３が出力されて通常キュー８１１に格納される。その後、出力レートの高いフロー＃４もトークン蓄積量が第１閾値ｔｈ１を下回り、通常要求メッセージＲＱ＃４が出力されて通常キュー８１１に格納される。このとき、フロー＃４には先行するフロー＃１〜＃３の通常要求メッセージＲＱ＃１〜＃３が存在するため、フロー＃４の通常要求メッセージＲＱ＃４は通常キュー８１１の最後尾に格納され、フロー＃４のミニバケツ８２へのトークン供給はフロー＃１〜＃３の後回しとなる。
【００４１】
しかし、フロー＃４の出力レートは、他のフロー＃１〜＃３より高いため、トークンの減少が早い。このため、フロー＃４のミニバケツ８２のトークン蓄積量は、すぐに第２閾値ｔｈ２を下回り、緊急要求メッセージＲＱ’＃４が出力される。緊急要求メッセージＲＱ’＃４は、優先キュー８１０に入力され、通常キュー８１１に格納されていた通常要求メッセージＲＱ＃４は削除される（点線参照）。
【００４２】
優先キュー８１０の優先度は通常キュー８１１より高いため、優先キュー８１０内の緊急要求メッセージＲＱ’＃４は、通常キュー８１１内の通常要求メッセージＲＱ＃１〜＃３より先にメインバケツ８０に出力される。これにより、フロー＃４のミニバケツ８２には、パケットの通過に間に合うようにメインバケツ８０からトークンが供給される。
【００４３】
しかし、トークンの消費量は、パケットの出力レートだけでなく、入力レートにも依存する。このため、入力レートが契約レートを上回る場合、トークンを使い切りつつ、契約レート分の出力レートだけが確保される。なお、契約帯域を超える分のパケットは廃棄される。
【００４４】
図４には、比較例のポリサの異常時の動作例が示されている。なお、図４において、図３と共通する構成については同一の符号を付し、その説明を省略する。
【００４５】
本例において、フロー＃１〜＃３の入力レートは、契約レートの１０（Mbps）を上回る１００（Mbps）である。また、フロー＃４の入力レートは、契約レートと同じ１（Gbps）である。つまり、フロー＃１〜＃４のうち、フロー＃１〜＃３は、契約帯域を超える帯域超過フローである。このため、フロー＃１〜＃３のメインバケツ８０とミニバケツ８２は、定常的にトークンが枯渇している（「空」参照）。
【００４６】
したがって、優先キュー８１０には、定常的にフロー＃１〜＃３の緊急要求メッセージＲＱ’＃１〜＃３が入力される。また、フロー＃４の緊急要求メッセージＲＱ’＃４も同様に優先キュー８１０に入力されるが、優先キュー８１０は先行の緊急要求メッセージＲＱ’＃１〜＃３により輻輳しているため、最後尾に格納される。このため、フロー＃４のミニバケツ８２へのトークン供給が、フロー＃１〜＃３の後回しとなり、パケットの通過に間に合わず、パケットの廃棄が発生する（「廃棄」参照）。
【００４７】
このように、比較例においては、各フロー＃１〜＃４の入力レートとは無関係に緊急要求メッセージＲＱ’＃１〜＃４が出力されるため、通常は輻輳しない優先キュー８１０が輻輳してしまう。その結果、入力レートが契約レート以下のフロー＃４について、トークン供給がパケットの通過に間に合わず、パケットが廃棄されるため、出力レートが契約レートである１（Gbps）未満となる。つまり、フロー＃４の入力レートは契約レート以内であるにも関わらず、契約帯域が保証されないという問題が生ずる。
【００４８】
そこで、実施例では、要求に応じて供給されるトークンに基づき各フローのパケットの通過を制御し、フローごとのパケットの入力レートと契約帯域の比較結果に応じ要求の優先度をフローごとに制御することで、帯域保証の性能を改善する。
【００４９】
図５は、実施例のポリサの一例を示す構成図である。ポリサは、帯域制御装置の一例であり、トークン管理部１と、優先度制御部２と、通過制御部３と、フロー識別部４とを有する。
【００５０】
トークン管理部１は、供給部の一例であり、要求に応じトークンを通過制御部３に供給する。トークン管理部１は、トークン加算部１０と、メインバケツ１１と、トークン供給部１２とを有する。メインバケツ１１は、例えばメモリにより構成され、フローごとのトークンを蓄積する。トークン加算部１０は、メインバケツ１１のトークンの残量を参照し、所定のアルゴリズムでメインバケツ１１にトークンを加算する。
【００５１】
トークン供給部１２は、優先度制御部２から要求メッセージが入力されると、メインバケツ１１のトークン蓄積量を検出して、一定量のトークンを通過制御部３に出力する。トークン供給部１２は、トークンの供給後、メインバケツ１１のトークン蓄積量から一定量を減算する。
【００５２】
通過制御部３は、パケット（「ＰＫＴ」参照）のフローごとに、優先度制御部２を介してトークン管理部１にトークンを要求し、その要求に応じ供給されたトークンに基づき、フローごとにパケットの通過を制御する。通過制御部３は、フローごとに、ミニバケツ３０と、トークン要求部３２と、閾値テーブル３３と、通過判定部３１とを有する。
【００５３】
ミニバケツ３０は、例えばメモリにより構成され、トークン管理部１からトークンが供給され蓄積される。通過判定部３１は、トークン蓄積量に基づきパケットの通過の可否を判定する。より具体的には、通過判定部３１は、トークン蓄積量が０より大きい場合、パケットを通過させ、トークン蓄積量が０以下である場合、パケットを廃棄する。つまり、通過判定部３１は、トークン蓄積量に応じてパケットを通過させ、または廃棄する。
【００５４】
なお、通過判定部３１は、これに限定されず、トークン蓄積量とパケット長を比較し、トークン蓄積量≧パケット長の場合、パケットを通過させ、トークン蓄積量＜パケット長の場合、パケットを廃棄してもよい。通過判定部３１は、パケットを通過させるたびにミニバケツ３０のトークン蓄積量からパケット長分のトークンを減算する。
【００５５】
閾値テーブル３３は、例えばメモリにより構成され、比較例と同様の第１閾値ｔｈ１及び第２閾値ｔｈ２が書き込まれている。トークン要求部３２は、ミニバケツ３０のトークン蓄積量を参照し、閾値テーブル３３から読み出した第１閾値ｔｈ１及び第２閾値ｔｈ２と比較する。トークン要求部３２は、ｔｈ２≦トークン蓄積量＜ｔｈ１の場合、通常要求メッセージを優先度制御部２に出力し、トークン蓄積量＜ｔｈ２の場合、緊急要求メッセージを優先度制御部２に出力する。
【００５６】
フロー識別部４は、パケットごとにフローを識別して、パケットをフローに応じた通過判定部３１に出力する。フロー識別部４は、例えばパケットのＶＩＤ、ＭＰＬＳラベル、または入力ポート（図２参照）に基づいてフローを識別する。
【００５７】
優先度制御部２は、フローごとのパケットの入力レートと契約レートを比較し、その比較結果に応じてトークン管理部１に対する要求の優先度をフローごとに制御する。優先度制御部２は、待機処理部２０と、要求判定部２１と、レート監視テーブル２２とを有する。
【００５８】
レート監視テーブル２２は、例えばメモリにより構成されている。レート監視テーブル２２には、フローごとの契約レートが設定され、入力レートに関する情報が書き込まれている。ここで、契約レートはフローごとの設定値の一例である。なお、レート監視テーブル２２の内容の詳細は後述する。
【００５９】
要求判定部２１は、レート監視テーブル２２を参照し、待機処理部２０に設けられた優先キュー２００及び通常キュー２０１から、通常要求メッセージ及び緊急要求メッセージの出力先を選択する。より具体的には、要求判定部２１は、通常要求メッセージを通常キュー２０１に出力し、緊急要求メッセージを、入力レート≦契約レートの場合に優先キュー２００に出力し、入力レート＞契約レートの場合に通常キュー２０１に出力する。
【００６０】
待機処理部２０は、通常キュー２０１内の要求メッセージより優先して、優先キュー２００内の要求メッセージをトークン供給部１２に出力する。つまり、優先キュー２００の優先度は、通常キュー２０１より高い。
【００６１】
このように、優先度制御部２は、通常要求メッセージ及び緊急要求メッセージを通常キュー２０１または優先キュー２００に振り分けることによりトークンの要求の優先度を制御する。また、優先度制御部２は、フローごとの入力レート及び契約レートの比較結果に応じてトークン管理部１に対するトークンの要求の優先度を制御する。
【００６２】
したがって、優先度制御部２は、入力レートが契約レート以下であるフローの要求の優先度を、入力レートが契約レートより大きいフローの要求より高い値とすることができる。これにより、入力レートが契約レート以下であるフローにトークンが優先的に供給されるため、そのフローの契約帯域が保証される。
【００６３】
また、トークン管理部１の機能は、ハードウェア並みの処理速度を要求されるものではない。このため、トークン管理部１は、コントロールカード９３のプロセッサ９３０の一機能としてソフトウェアにより構成されてもよい。この場合、例えばトークン加算部１０のトークン加算のアルゴリズムは、ソフトウェアの変更により柔軟にカスタマイズすることができる。
【００６４】
一方、通過制御部３及び優先度制御部２の機能は、パケットの入力レートに応じて高い処理速度が要求される。このため、通過制御部３及び優先度制御部２は、ハードウェアとして、インターフェースカード９１の入力処理部９１２及び記憶部９１５に設けられる。このため、優先キュー２００及び通常キュー２０１のサイズは、例えばハードウェアとソフトウェアの処理速度の差に応じて決定される。なお、フロー識別部４も、入力処理部９１２に設けられ、ＰＨＹ／ＭＡＣ部９１１から入力されたパケットのフローを識別する。
【００６５】
図６は、通過制御部３の動作の一例を示すフローチャートである。本動作は、例えば定期的に実行される。
【００６６】
通過判定部３１は、パケットが入力されたか否かを判定する（ステップＳｔ１）。通過判定部３１は、パケットが入力されていない場合（ステップＳｔ１のＮｏ）、動作を終了し、パケットが入力されている場合（ステップＳｔ１のＹｅｓ）、ミニバケツ３０のトークン蓄積量が０より大きいか否かを判定する（ステップＳｔ２）。なお、通過判定部３１は、トークン蓄積量の閾値として０以外の値を用いてもよいし、あるいはトークン蓄積量をパケット長と比較してもよい。
【００６７】
通過判定部３１は、トークン蓄積量≦０の場合（ステップＳｔ２のＮｏ）、パケットを廃棄して（ステップＳｔ８）、動作を終了する。また、通過判定部３１は、トークン蓄積量＞０の場合（ステップＳｔ２のＹｅｓ）、パケットを通過させる（ステップＳｔ３）。次に、通過判定部３１は、ミニバケツ３０のトークン蓄積量から、通過したパケット長分を減算する（ステップＳｔ４）。なお、通過したパケットは、入力処理部９１２の後段を経由してスイッチカード９２に入力される。
【００６８】
次に、トークン要求部３２は、トークン蓄積量と第１閾値ｔｈ１を比較する（ステップＳｔ５）。トークン要求部３２は、トークン蓄積量≧ｔｈ１の場合（ステップＳｔ５のＮｏ）、動作を終了し、トークン蓄積量＜ｔｈ１の場合（ステップＳｔ５のＹｅｓ）、トークン蓄積量と第２閾値ｔｈ２を比較する（ステップＳｔ６）。
【００６９】
トークン要求部３２は、トークン蓄積量≧ｔｈ２の場合（ステップＳｔ６のＮｏ）、通常要求メッセージを要求判定部２１に出力し、トークン蓄積量＜ｔｈ２の場合（ステップＳｔ６のＹｅｓ）、緊急要求メッセージを要求判定部２１に出力する（ステップＳｔ７）。このようにして、通過制御部３は動作する。
【００７０】
このように、通過制御部３は、トークンが第１閾値ｔｈ１を下回ったとき及び第２閾値ｔｈ２を下回ったとき、トークンを要求する。このため、トークンの要求を通常要求メッセージと緊急要求メッセージの２段階に区別して出力でき、通常要求メッセージより緊急要求メッセージに応じて優先的にトークンを供給することができる。
【００７１】
図７（ａ）は、トークン蓄積量の変化の一例を示すグラフである。図７（ａ）において、横軸は時間を示し、縦軸はトークン蓄積量を示す。
【００７２】
トークン蓄積量は、時刻ｔ１において第１閾値ｔｈ１を下回り、その後の時刻ｔ２において第２閾値ｔｈ２を下回る。優先度制御部２は、第１閾値ｔｈ１と第２閾値ｔｈ２の差分、及びトークン蓄積量が第１閾値ｔｈ１を下回ったときとトークン蓄積量が第２閾値ｔｈ２を下回ったときの時間差Δｔ（＝ｔ２−ｔ１）から入力レートＲ（Mbps）を算出する。
【００７３】
Ｒ＝（ｔｈ１−ｔｈ２）／Δｔ     ・・・（１）
【００７４】
優先度制御部２は、上記の式（１）により入力レートＲを算出する。このとき、第１閾値ｔｈ１及び第２閾値ｔｈ２は固定値であるため、優先度制御部２は、トークン蓄積量が第１閾値ｔｈ１及び第２閾値ｔｈ２を下回った時刻ｔ１，ｔ２の時間差Δｔを、例えばカウンタなどにより計時することで、入力レートＲを概算値として容易に算出できる。
【００７５】
また、図７（ｂ）には、レート監視テーブル２２の一例が示されている。レート監視テーブル２２には、フローごとにフローＩＤ、契約レートＲｏ（Mbps）、要求時刻ｔ１（sec）、及び入力レートＲ（Mbps）が記録されている。フローＩＤは、フローを識別する識別番号（＃１、＃２、＃３、・・・）である。
【００７６】
契約レートＲｏは、ユーザの契約帯域に基づいて予め設定されており、契約内容が変更されない限り、変更されることはない。要求時刻ｔ１は、上述したように、トークン蓄積量が第１閾値ｔｈ１を下回った時刻である。要求判定部２１は、トークン蓄積量が第１閾値ｔｈ１を下回ったとき、要求時刻ｔ１を検出して、レート監視テーブル２２に記録する。その後、要求判定部２１は、トークン蓄積量が第２閾値ｔｈ２を下回ったとき、時刻ｔ２を検出し、レート監視テーブル２２から要求時刻ｔ１を読み出して、上記の式（１）から入力レートＲを算出する。算出された入力レートＲは、レート監視テーブル２２に記録される。次に、入力レートＲに基づく優先制御の動作について説明する。
【００７７】
図８には、トークン蓄積量が第１閾値ｔｈ１を下回ったときのポリサの動作の一例が示されている。図８において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【００７８】
本例において、ミニバケツ３０のトークン蓄積量は、第１閾値ｔｈ１を下回り、かつ、第２閾値ｔｈ２以上であるとする。この場合、トークン要求部３２は、通常要求メッセージを要求判定部２１に出力する。要求判定部２１は、優先キュー２００及び通常キュー２０１のうち、優先度の低い通常キュー２０１に通常要求メッセージを入力する（「ＲＱ」参照）。
【００７９】
図９（ａ）には、Ｒ＞Ｒｏの場合にトークン蓄積量が第２閾値ｔｈ２を下回ったときのポリサの動作の一例が示されている。図９（ａ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【００８０】
本例において、ミニバケツ３０のトークン蓄積量は、第２閾値ｔｈ２を下回っているとする。この場合、トークン要求部３２は、緊急要求メッセージを要求判定部２１に出力する。しかし、要求判定部２１は、該当するフローの入力レートＲが契約レートＲｏを上回るため（「Ｒ＞Ｒｏ」参照）、要求メッセージを、優先キュー２００には入力せず（×印参照）、通常キュー２０１に格納したままにする。
【００８１】
したがって、入力レートＲが契約レートＲｏを上回るフローの緊急要求メッセージによる優先キュー２００の輻輳が防止される。
【００８２】
また、図９（ｂ）には、Ｒ≦Ｒｏの場合にトークン蓄積量が第２閾値ｔｈ２を下回ったときのポリサの動作の一例が示されている。図９（ｂ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【００８３】
本例において、ミニバケツ３０のトークン蓄積量は、第２閾値ｔｈ２を下回っているとする。この場合、トークン要求部３２は、緊急要求メッセージを要求判定部２１に出力する。要求判定部２１は、該当するフローの入力レートＲが契約レートＲｏ以下であるため（「Ｒ≦Ｒｏ」参照）、要求メッセージを通常キュー２０１から優先キュー２００に移す。
【００８４】
したがって、入力レートＲが契約レートＲｏ以下であるフローの緊急要求メッセージに対しては、入力レートＲが契約レートＲｏを上回るフローより優先してトークン供給が行われる。このため、入力レートＲが契約レートＲｏ以下であるフローについて、契約帯域が保証される。
【００８５】
このように、優先度制御部２は、入力レートが契約レート以下であるフローの要求の優先度を、入力レートが契約レートを上回るフローの要求の優先度より高い値とする。このため、契約帯域内のフローのミニバケツ３０には、帯域超過フローより優先してトークンが供給される。
【００８６】
次に、入力レートの算出例を説明する。図１０（ａ）には通常要求メッセージの出力が示され、図１０（ｂ）には緊急要求メッセージの出力例が示されている。なお、図１０（ａ）及び図１０（ｂ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【００８７】
本例において、第１閾値ｔｈ１＝１０（KByte）及び第２閾値ｔｈ２＝５（Kbyte）とする。図１０（ａ）に示されるように、パケット長Ｌ１（Byte）のパケットが通過したとき、トークン蓄積量はパケット長Ｌ１（Byte）分だけ減算される。これにより、トークン蓄積量が第１閾値ｔｈ１を下回り、トークン要求部３２から通常要求メッセージが出力される。
【００８８】
また、図１０（ｂ）に示されるように、通常要求メッセージの出力から１０（msec）後、パケット長Ｌ２（Byte）のパケットが通過したとき、トークン蓄積量はパケット長Ｌ２（Byte）分だけ減算される。これにより、トークン蓄積量が第２閾値ｔｈ２を下回り、トークン要求部３２から緊急要求メッセージが出力される。
【００８９】
本例では、通常要求メッセージと緊急要求メッセージの出力の時間差Δｔ＝１０（msec）であるため、入力レートＲは、上記の式（１）から４（Mbps）（＝（１０Ｋ−５Ｋ）×８／０．０１）と算出される。
【００９０】
しかし、通常要求メッセージの出力時のトークン蓄積量は、パケット長Ｌ１によっては第１閾値ｔｈ１と同一にはならず、緊急要求メッセージの出力時のトークン蓄積量も、パケット長Ｌ２によっては第２閾値ｔｈ２と同一にはならない。このため、式（１）により算出される入力レートＲは、概算値である。
【００９１】
そこで、優先度制御部２は、第１閾値ｔｈ１を下回ったときと第２閾値ｔｈ２を下回ったときのトークン蓄積量の差分、及びトークン蓄積量が第１閾値ｔｈ１を下回ったときとトークン蓄積量が第２閾値を下回ったときの時間差Δｔから入力レートＲを算出してもよい。
【００９２】
Ｒ＝（Ａ１−Ａ２）／Δｔ     ・・・（２）
【００９３】
入力レートＲは、例えば上記の式（２）により算出される。式（２）において、Ａ１は、トークン蓄積量が第１閾値ｔｈ１を下回ったときのトークン蓄積量であり、Ａ２は、トークン蓄積量が第２閾値ｔｈ２を下回ったときのトークン蓄積量である。このため、式（２）によると、入力レートＲが式（１）より高精度に算出される。
【００９４】
本例の場合、トークン蓄積量Ａ１＝９．８（KByte）とし（図１０（ａ）参照）、トークン蓄積量Ａ２＝４．６（KByte）とすると（図１０（ｂ）参照）、入力レートＲは、４．１６（Mbps）（＝（９．８Ｋ−４．６Ｋ）×８／０．０１）と算出される。
【００９５】
図１１は、要求判定部２１の動作の一例を示すフローチャートである。本動作は、例えば、トークン要求部３２から要求メッセージが入力されたことを契機として行われる。
【００９６】
要求判定部２１は、要求メッセージが緊急要求メッセージであるか否かを判定する（ステップＳｔ２１）。要求判定部２１は、要求メッセージが通常要求メッセージである場合（ステップＳｔ２１のＮｏ）、その要求時刻ｔ１を検出してレート監視テーブル２２に記録する（ステップＳｔ２８）。次に、要求判定部２１は、通常要求メッセージを通常キュー２０１に入力して（ステップＳｔ２９）、動作を終了する。
【００９７】
また、要求判定部２１は、要求メッセージが緊急要求メッセージである場合（ステップＳｔ２１のＹｅｓ）、その要求時刻ｔ２を検出する（ステップＳｔ２２）。なお、要求時刻ｔ１，ｔ２は、例えばカウンタ値に基づき検出される。次に、要求判定部２１は、上記の式（１）により入力レートＲを算出する（ステップＳｔ２３）。
【００９８】
なお、要求判定部２１は、上記の式（１）に代えて、上記の式（２）により入力レートＲを算出してもよい。この場合、要求判定部２１は、上記のステップＳｔ２８において、トークン要求部３２からトークン蓄積量Ａ１を取得し、要求時刻ｔ２とともにレート監視テーブル２２に記録しておく。また、要求判定部２１は、上記のステップＳｔ２２において、トークン要求部３２からトークン蓄積量Ａ２を取得する。取得されたトークン蓄積量Ａ１，Ａ２は、入力レートＲの算出に用いられる。
【００９９】
次に、要求判定部２１は、レート監視テーブル２２からフローに応じた契約レートＲｏを取得する（ステップＳｔ２４）。次に、要求判定部２１は、算出した入力レートＲと契約レートＲｏを比較する（ステップＳｔ２５）。
【０１００】
要求判定部２１は、比較の結果、Ｒ≦Ｒｏの場合（ステップＳｔ２５のＹｅｓ）、緊急要求メッセージを優先キュー２００に入力する（ステップＳｔ２６）。次に、要求判定部２１は、通常キュー２０１に格納された通常要求メッセージを削除し（ステップＳｔ２７）、動作を終了する。なお、要求判定部２１は、ステップＳｔ２７の処理を省略し、通常要求メッセージを通常キュー２０１に格納したままにしてもよい。
【０１０１】
また、要求判定部２１は、比較の結果、Ｒ＞Ｒｏの場合（ステップＳｔ２５のＮｏ）、緊急要求メッセージを優先キュー２００に格納することなく、動作を終了する。これにより、契約帯域内のフロー（Ｒ≦Ｒｏ）のトークンの要求の優先度が、帯域超過フロー（Ｒ＞Ｒｏ）より高くなる。このようにして、要求判定部２１は動作する。
【０１０２】
上述した例において、要求判定部２１は、入力レートＲの１回分の算出値に基づき、要求の優先度を制御するが、これに限定されない。要求判定部２１は、複数回算出した入力レートＲ１〜Ｒ４の平均値Ｒａｖを算出し、平均値Ｒａｖと契約レートＲｏを比較し、その比較結果に応じて要求の優先度を制御してもよい。これにより、瞬間的な入力レートＲの変動に起因する優先度の誤判定が防止されるため、要求の優先度を高精度に制御することが可能となる。
【０１０３】
図１２（ａ）及び図１２（ｂ）には、この場合のレート監視テーブル２２の一例が示されている。図１２（ａ）及び図１２（ｂ）において、図７（ｂ）と共通する項目については、その説明を省略する。
【０１０４】
レート監視テーブル２２には、異なる期間に算出された複数の入力レートＲ１〜Ｒ４が記録される。入力レートＲ１〜Ｒ４のうち、入力レートＲ１（＝６（Mbps））が最も新しい値であり、入力レートＲ４は最も古い値である。なお、本例では、４つの期間分の入力レートＲ１〜Ｒ４がレート監視テーブル２２に記録されているが、記録する入力レートＲ１〜Ｒ４の数に限定はない。
【０１０５】
Ｒａｖ＝（Ｒ＋Ｒ１＋Ｒ２＋Ｒ３＋Ｒ４）／５   ・・・式（３）
【０１０６】
要求判定部２１は、上記の式（３）により、入力レートＲ１〜Ｒ４と新たに算出した入力レートＲの移動平均値Ｒａｖを算出する。図１２（ａ）の例の場合、新たに算出した入力レートＲ＝４（Mbps）とすると、入力レートＲ１〜Ｒ４は、それぞれ、６（Mbps）、２０（Mbps）、１５（Mbps）、１０（Mbps）であるため、移動平均値Ｒａｖ＝１１（Mbps）（＝（４＋６＋２０＋１５＋１０）／５）と算出される。
【０１０７】
要求判定部２１は、新たに算出した入力レートＲ＝４（Mbps）と契約レートＲｏ＝１０（Mbps）を比較した場合、Ｒ＜Ｒｏ（契約帯域内）と判定するが、移動平均値Ｒａｖ＝１１（Mbps）と契約レートＲｏ＝１０（Mbps）を比較した場合、Ｒ≧Ｒｏ（帯域超過）と判定する。このように、要求判定部２１は、移動平均値Ｒａｖを優先度の判定に用いることにより、平滑化された入力レートにより正確な判定が可能となる。なお、移動平均値Ｒａｖは、平均値の一例であり、これに代えて例えば加重移動平均値などが用いられてもよい。
【０１０８】
また、複数の入力レートＲ１〜Ｒ４は、新たに入力レートＲが算出されるたびに更新される。図１２（ａ）は更新前のレート監視テーブル２２を示し、図１２（ｂ）は更新後のレート監視テーブル２２を示す。新たに入力レートＲが算出されると、その新たに算出された入力レートＲ（＝４（Mbps））は、入力レートＲ１として新たに記録される。また、更新前の入力レートＲ１〜Ｒ３は、入力レートＲ２〜Ｒ４として新たに記録される。これにより、更新前の入力レートＲ４は、レート監視テーブル２２から消去される。
【０１０９】
図１３は、本例の要求判定部２１の動作を示すフローチャートである。なお、図１３において、図１１と共通する処理については同一の符号を付し、その説明を省略する。
【０１１０】
要求判定部２１は、入力レートＲを算出した後（ステップＳｔ２３）、入力レートＲと、レート監視テーブル２２に記録された４つの入力レートＲ１〜Ｒ４とから上記の式（３）を用いて移動平均値Ｒａｖを算出する（ステップＳｔ２３ａ）。次に、要求判定部２１は、レート監視テーブル２２から契約レートＲｏを取得し（ステップＳｔ２４）、算出した移動平均値Ｒａｖと比較する（ステップＳｔ２５ａ）。
【０１１１】
要求判定部２１は、Ｒａｖ≦Ｒｏの場合（ステップＳｔ２５ａのＹｅｓ）、図１１と同様の処理（ステップＳｔ２６，Ｓｔ２７）を行い、図１２（ａ）及び図１２（ｂ）を参照して述べたレート監視テーブル２２の更新処理が行われる（ステップＳｔ２７ａ）。また、要求判定部２１は、Ｒａｖ＞Ｒｏの場合（ステップＳｔ２５ａのＮｏ）、ステップＳｔ２６及びＳｔ２７の処理を行わずに、レート監視テーブル２２の更新処理を行う（ステップＳｔ２７ａ）。このようにして、要求判定部２１は動作する。
【０１１２】
また、優先度制御部２は、通過制御部３におけるトークンの要求から供給までの期間ごとにフローごとのパケットの廃棄の有無を検出し、複数の期間における廃棄の判定回数とフローごとの所定回数を比較し、その比較結果に応じてトークン管理部１に対するトークンの要求の優先度をフローごとに制御してもよい。上述したように、帯域超過フローの場合、契約レートＲｏを超える分のパケットは廃棄されるため、パケットの廃棄が行われた期間の数に基づき帯域超過フローを判別することができる。このため、入力レートＲの算出処理を行うことなく、低負荷の処理で要求の優先度を制御することが可能となる。
【０１１３】
図１４（ａ）には、上記の実施例の場合のレート監視テーブル２２が示されている。レート監視テーブル２２は、フローＩＤ、廃棄上限回数Ｎｕ、期間＃１〜＃４ごとのパケット（ＰＫＴ）廃棄の有無、及び廃棄回数ｎが記録されている。廃棄上限回数Ｎｕは、フローごとに、その契約レートに応じて設定される。
【０１１４】
期間＃１〜＃４は、それぞれ、通過制御部３におけるトークンの要求から供給までの期間である。例えば、期間＃１〜＃４は、通過制御部３が緊急要求メッセージを出力してからトークンが供給されるまでの期間であり、一例として優先度制御部２内のカウンタを用いて管理される。なお、本例では４つの期間＃１〜＃４が挙げるが、レート監視テーブル２２に記録される期間の数に限定はない。
【０１１５】
優先度制御部２は、期間＃１〜＃４内の廃棄の有無を通過判定部３１の通知から検出し、期間＃１〜＃４のうち、廃棄が「有」の回数を廃棄回数ｎに記録する。なお、期間＃１〜＃４のうち、期間＃１が最も新しく、期間＃４が最も古く、期間＃１〜＃４の「ＰＫＴ廃棄有無」は、新たに廃棄有無を検出するたびに更新される。つまり、新たな廃棄有無の検出結果は、期間＃１の「ＰＫＴ廃棄有無」として新たに記録される。また、更新前の期間＃１〜＃３の「ＰＫＴ廃棄有無」は、期間＃２〜＃４の「ＰＫＴ廃棄有無」として新たに記録される。これにより、更新前の期間＃４の「ＰＫＴ廃棄有無」は、レート監視テーブル２２から消去される。
【０１１６】
図１４（ｂ）には、ｎ≦Ｎｕの場合（点線の枠内参照）にトークン蓄積量が第２閾値ｔｈ２を下回ったときのポリサの動作の一例が示されている。図１４（ｂ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【０１１７】
要求判定部２１は、ｎ≦Ｎｕの場合、要求メッセージＲＱを通常キュー２０１から優先キュー２００に移す。より具体的には、要求判定部２１は、緊急要求メッセージを優先キュー２００に入力し（実線のＲＱ参照）、通常キュー２０１に格納済みの通常要求メッセージを削除する（点線のＲＱ参照）。これにより、ｎ≦Ｎｕのフロー、つまり契約レート内のフローの要求が優先的にトークン管理部１に出力される。
【０１１８】
一方、図１４（ｃ）には、ｎ＞Ｎｕの場合（点線の枠内参照）にトークン蓄積量が第２閾値ｔｈ２を下回ったときのポリサの動作の一例が示されている。図１４（ｃ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【０１１９】
要求判定部２１は、要求メッセージを、優先キュー２００には入力せず（×印参照）、通常キュー２０１に格納したままにする。つまり、要求判定部２１は、緊急要求メッセージを廃棄して、優先的な処理を行わない。これにより、ｎ＞Ｎｕのフロー、つまり帯域超過フローの要求が優先的にトークン管理部１に出力されることが防止される。
【０１２０】
図１５は、レート監視テーブル２２の更新処理の一例を示すフローチャートである。本処理は、例えば一定の周期で行われる。
【０１２１】
要求判定部２１は、トークンの供給の有無を判定する（ステップＳｔ４１）。要求判定部２１は、例えば、通常キュー２０１または優先キュー２００から要求メッセージが出力されたとき、トークンの供給が行われたと判定する。
【０１２２】
要求判定部２１は、トークンの供給がない場合（ステップＳｔ４１のＮｏ）、処理を終了し、トークンの供給が行われた場合（ステップＳｔ４１のＹｅｓ）、レート監視テーブル２２の期間＃２〜＃４の「ＰＫＴ廃棄有無」を更新する（ステップＳｔ４２）。より具体的には、要求判定部２１は、更新前の期間＃１〜＃３の「ＰＫＴ廃棄有無」を、それぞれ期間＃２〜＃４の「ＰＫＴ廃棄有無」として新たに記録する。
【０１２３】
次に、要求判定部２１は、通過判定部３１からの通知に基づき、最新の期間内のパケットの廃棄の有無を検出する（ステップＳｔ４３）。要求判定部２１は、廃棄が有った場合（ステップＳｔ４３のＹｅｓ）、期間＃１の「ＰＫＴ廃棄有無」を「有」とし（ステップＳｔ４４）、廃棄がない場合（ステップＳｔ４３のＮｏ）、期間＃１の「ＰＫＴ廃棄有無」を「無」として（ステップＳｔ４５）、処理を終了する。このようにして、レート監視テーブル２２の更新処理は行われる。
【０１２４】
また、図１６は、本例の要求判定部２１の動作を示すフローチャートである。本処理は、例えば、トークン要求部３２から要求メッセージが入力されたことを契機として行われる。
【０１２５】
まず、要求判定部２１は、要求メッセージが緊急要求メッセージであるか否かを判定する（ステップＳｔ５１）。要求判定部２１は、要求メッセージが通常要求メッセージである場合（ステップＳｔ５１のＮｏ）、通常要求メッセージを通常キュー２０１に入力し（ステップＳｔ５７）、動作を終了する。
【０１２６】
また、要求判定部２１は、要求メッセージが緊急要求メッセージである場合（ステップＳｔ５１のＹｅｓ）、レート監視テーブル２２の期間＃１〜＃４の「ＰＫＴ廃棄有無」からパケットの廃棄回数ｎを算出する（ステップＳｔ５２）。なお、算出されたパケットの廃棄回数ｎは、レート監視テーブル２２に記録される。次に、要求判定部２１は、レート監視テーブル２２から上限回数Ｎｕを取得する（ステップＳｔ５３）。
【０１２７】
次に、要求判定部２１は、パケットの廃棄回数ｎ及び廃棄上限回数Ｎｕを比較する（ステップＳｔ５４）。要求判定部２１は、ｎ≦Ｎｕの場合（ステップＳｔ５４のＹｅｓ）、緊急要求メッセージを優先キュー２００に入力する（ステップＳｔ５５）。次に、要求判定部２１は、通常キュー２０１から緊急要求メッセージと同一のフローの通常要求メッセージを削除して（ステップＳｔ５６）、動作を終了する。なお、ステップＳｔ５６の処理は省略されてもよい。
【０１２８】
また、要求判定部２１は、ｎ＜Ｎｕの場合（ステップＳｔ５４のＮｏ）、緊急要求メッセージを優先キュー２００に格納することなく、動作を終了する。これにより、契約帯域内のフロー（Ｒ≦Ｒｏ）のトークンの要求の優先度が、帯域超過フロー（Ｒ＞Ｒｏ）より高くなる。このようにして、要求判定部２１は動作する。
【０１２９】
これまで述べた実施例において、待機処理部２０には２つのキュー２００，２０１だけが設けられているが、これに限定されない。例えば図１７（ａ）〜図１７（ｃ）に示されるように、待機処理部２０ａには、通常キュー２０１及び優先キュー２００に加えて、帯域超過フローの緊急要求メッセージが入力される準優先キュー２０２が設けられてもよい。
【０１３０】
より具体的には、図１７（ａ）には、通常要求メッセージが入力された場合の優先度制御部２の動作が示されている。なお、図１７（ａ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【０１３１】
待機処理部２０ａには、通常キュー２０１、優先キュー２００、及び準優先キュー２０２が設けられている。通常キュー２０１、優先キュー２００、及び準優先キュー２０２のうち、優先キュー２００の優先度が最も高く、次に準優先キュー２０２の優先度が高く、通常キュー２０１の優先度は最も低い。待機処理部２０ａは、この優先度に従った順番で要求メッセージをトークン管理部１に出力する。
【０１３２】
要求判定部２１ａは、通常要求メッセージが入力された場合、入力レートＲに関わらず、通常キュー２０１に入力する（ＲＱ参照）。
【０１３３】
また、図１７（ｂ）には、Ｒ≦Ｒｏのフローの緊急要求メッセージが入力された場合の優先度制御部２の動作が示されている。なお、図１７（ｂ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【０１３４】
要求判定部２１ａは、緊急要求メッセージが入力されたとき、レート監視テーブル２２から、フローの入力レートＲが契約レートＲｏ以下であると判定すると（「Ｒ≦Ｒｏ」参照）、要求メッセージを通常キュー２０１から優先キュー２００に移す。より具体的には、要求判定部２１ａは、緊急要求メッセージを優先キュー２００に入力し（実線のＲＱ参照）、通常キュー２０１に格納済みの通常要求メッセージを削除する（点線のＲＱ参照）。
【０１３５】
また、図１７（ｃ）には、Ｒ＞Ｒｏのフローの緊急要求メッセージが入力された場合の優先度制御部２の動作が示されている。なお、図１７（ｃ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【０１３６】
要求判定部２１ａは、緊急要求メッセージが入力されたとき、レート監視テーブル２２から、フローの入力レートＲが契約レートＲｏより大きいと判定すると（「Ｒ＞Ｒｏ」参照）、要求メッセージを通常キュー２０１から準優先キュー２０２に移す。より具体的には、要求判定部２１ａは、緊急要求メッセージを準優先キュー２０２に入力し（実線のＲＱ参照）、通常キュー２０１に格納済みの通常要求メッセージを削除する（点線のＲＱ参照）。
【０１３７】
このように、優先度制御部２は、緊急要求メッセージを優先キュー２００または準優先キュー２０２に入力することにより、トークン蓄積量が第２閾値ｔｈ２を下回ったフローの要求の優先度を、トークン蓄積量が第１閾値ｔｈ１を下回ったフローの要求の優先度より高い値とする。このため、トークンが枯渇しそうなミニバケツ３０には、十分なトークンが蓄積されたミニバケツ３０より優先的にトークンが供給される。
【０１３８】
また、優先度制御部２は、契約レートＲｏ内のフローの緊急要求メッセージを優先キュー２００に入力し、帯域超過フローの緊急要求メッセージを準優先キュー２０２に入力する。これにより、優先度制御部２は、トークン蓄積量が第２閾値ｔｈ２を下回ったフローのうち、入力レートＲが契約レートＲｏ以下であるフローの要求の優先度を、入力レートＲが契約レートＲｏを上回るフローの要求の優先度より高い値とする。このため、帯域超過フローのミニバケツ３０でも、緊急要求メッセージが出力された場合、通常要求メッセージが出力されたものより優先的にトークンが供給される。
【０１３９】
図１８は、本例の要求判定部２１ａの動作を示すフローチャートである。なお、図１８において、図１１と共通する処理については同一の符号を付し、その説明を省略する。
【０１４０】
要求判定部２１ａは、入力レートＲと契約レートＲｏを比較し（ステップＳｔ２５）、Ｒ≦Ｒｏの場合（ステップＳｔ２５のＹｅｓ）、緊急要求メッセージを優先キュー２００に入力する（ステップＳｔ２６）。また、要求判定部２１ａは、Ｒ＞Ｒｏの場合（ステップＳｔ２５のＮｏ）、緊急要求メッセージを準優先キュー２０２に入力する（ステップＳｔ２６ｂ）。このため、緊急要求メッセージは、入力レートＲと契約レートＲｏの比較結果によらずに、通常要求メッセージより優先的にトークン管理部１に出力される。
【０１４１】
次に、要求判定部２１ａは、通常キュー２０１から、緊急要求メッセージと同じフローの通常要求メッセージを削除して（ステップＳｔ２７）、動作を終了する。なお、ステップＳｔ２７の処理は省略されてもよい。このようにして、要求判定部２１ａは動作する。
【０１４２】
また、優先度制御部２は、要求の優先度を、入力レートＲと契約レートＲｏの差分に応じた複数の段階に分けてもよい。例えば図１９（ａ）〜図１９（ｃ）、図２０（ａ）、及び図２０（ｂ）に示されるように、待機処理部２０ｂには、通常キュー２０１に加えて、入力レートＲと契約レートＲｏの差分に応じた第１〜第４キュー２０３〜２０６が設けられてもよい。
【０１４３】
図１９（ａ）には、通常要求メッセージが入力された場合の優先度制御部２の動作が示されている。なお、図１９（ａ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【０１４４】
待機処理部２０ｂには、通常キュー２０１及び第１〜第４キュー２０３〜２０６が設けられている。通常キュー２０１には通常要求メッセージが入力され、第１〜第４キュー２０３〜２０６には緊急要求メッセージが入力される。第１〜第４キュー２０３〜２０６は、入力レートＲと契約レートＲｏの差分に応じて使い分けられる。
【０１４５】
以下に述べるように、Ｒ≦Ｒｏ／２のフローの場合、緊急要求メッセージは第１キュー２０３に入力され、Ｒｏ／２＜Ｒ≦Ｒｏのフローの場合、緊急要求メッセージは第２キュー２０４に入力される。また、Ｒｏ＜Ｒ≦２×Ｒｏのフローの場合、緊急要求メッセージは第３キュー２０５に入力され、２×Ｒｏ＜Ｒのフローの場合、緊急要求メッセージは第４キュー２０６に入力される。
【０１４６】
第１〜第４キュー２０３〜２０６の優先度は、第１キュー２０３が最も高く、第２キュー２０４、第３キュー２０５、第４キュー２０６の順に低くなる。また、通常キュー２０１の優先度は第４キュー２０６より低い。待機処理部２０ｂは、この優先度に従った順番で要求メッセージをトークン管理部１に出力する。
【０１４７】
要求判定部２１ｂは、通常要求メッセージが入力された場合、入力レートＲに関わらず、通常キュー２０１に入力する（ＲＱ参照）。
【０１４８】
図１９（ｂ）には、Ｒ≦Ｒｏ／２のフローの緊急要求メッセージが入力された場合の優先度制御部２の動作が示されている。なお、図１９（ｂ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【０１４９】
要求判定部２１ｂは、緊急要求メッセージが入力されたとき、レート監視テーブル２２から、フローの入力レートＲが契約レートＲｏの１／２以下であると判定すると（「Ｒ≦Ｒｏ／２」参照）、要求メッセージを通常キュー２０１から第１キュー２０３に移す。より具体的には、要求判定部２１ｂは、緊急要求メッセージを第１キュー２０３に入力し（実線のＲＱ参照）、通常キュー２０１に格納済みの通常要求メッセージを削除する（点線のＲＱ参照）。
【０１５０】
図１９（ｃ）には、Ｒｏ／２＜Ｒ≦Ｒｏのフローの緊急要求メッセージが入力された場合の優先度制御部２の動作が示されている。なお、図１９（ｃ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【０１５１】
要求判定部２１ｂは、緊急要求メッセージが入力されたとき、レート監視テーブル２２から、フローの入力レートＲが契約レートＲｏの１／２より大きく契約レートＲｏ以下であると判定すると（「Ｒｏ／２＜Ｒ≦Ｒｏ」参照）、要求メッセージを通常キュー２０１から第２キュー２０４に移す。より具体的には、要求判定部２１ｂは、緊急要求メッセージを第２キュー２０４に入力し（実線のＲＱ参照）、通常キュー２０１に格納済みの通常要求メッセージを削除する（点線のＲＱ参照）。
【０１５２】
図２０（ａ）には、Ｒｏ＜Ｒ≦２×Ｒｏのフローの緊急要求メッセージが入力された場合の優先度制御部２の動作が示されている。なお、図２０（ａ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【０１５３】
要求判定部２１ｂは、緊急要求メッセージが入力されたとき、レート監視テーブル２２から、フローの入力レートＲが契約レートＲｏより大きく契約レートＲｏの２倍以下であると判定すると（「Ｒｏ＜Ｒ≦２×Ｒｏ」参照）、要求メッセージを通常キュー２０１から第３キュー２０５に移す。より具体的には、要求判定部２１ｂは、緊急要求メッセージを第３キュー２０５に入力し（実線のＲＱ参照）、通常キュー２０１に格納済みの通常要求メッセージを削除する（点線のＲＱ参照）。
【０１５４】
図２０（ｂ）には、２×Ｒｏ＜Ｒのフローの緊急要求メッセージが入力された場合の優先度制御部２の動作が示されている。なお、図２０（ｂ）において、図５と共通する構成については同一の符号を付し、その説明を省略する。
【０１５５】
要求判定部２１ｂは、緊急要求メッセージが入力されたとき、レート監視テーブル２２から、フローの入力レートＲが契約レートＲｏの２倍より大きいと判定すると（「２×Ｒｏ＜Ｒ」参照）、要求メッセージを通常キュー２０１から第４キュー２０６に移す。より具体的には、要求判定部２１ｂは、緊急要求メッセージを第４キュー２０６に入力し（実線のＲＱ参照）、通常キュー２０１に格納済みの通常要求メッセージを削除する（点線のＲＱ参照）。
【０１５６】
このように、要求判定部２１ｂは、緊急要求メッセージの優先度を、入力レートＲと契約レートＲｏの差分に応じた４段階に制御するため、高精度な優先制御が可能となる。
【０１５７】
図２１は、本例の要求判定部２１ｂの動作を示すフローチャートである。なお、図２１において、図１１と共通する処理については同一の符号を付し、その説明を省略する。
【０１５８】
要求判定部２１ｂは、契約レートＲｏの取得後（ステップＳｔ２４）、算出した入力レートＲと契約レートＲｏを比較する（ステップＳｔ２５０）。要求判定部２１ｂは、Ｒ≦Ｒｏ／２の場合、緊急要求メッセージを第１キュー２０３に入力し（ステップＳｔ２６１）、Ｒｏ／２＜Ｒ≦Ｒｏの場合、緊急要求メッセージを第２キュー２０４に入力する（ステップＳｔ２６２）。
【０１５９】
また、要求判定部２１ｂは、Ｒｏ＜Ｒ≦２×Ｒｏの場合、緊急要求メッセージを第３キュー２０５に入力し（ステップＳｔ２６３）、２×Ｒｏ＜Ｒの場合、緊急要求メッセージを第４キュー２０６に入力する（ステップＳｔ２６４）。このため、要求判定部２１ｂは、緊急要求メッセージの優先度を、入力レートＲと契約レートＲｏの差分に応じて４段階に分けて制御することができる。
【０１６０】
次に、要求判定部２１ｂは、通常キュー２０１から、緊急要求メッセージと同じフローの通常要求メッセージを削除して（ステップＳｔ２７）、動作を終了する。なお、ステップＳｔ２７の処理は省略されてもよい。このようにして、要求判定部２１ｂは動作する。
【０１６１】
図２２には実施例のポリサの効果が示されている。図２２には、図４の比較例と対比できるように図５の構成を単純化して示されている。本例のポリサには、図４の比較例と同様に、帯域超過のフロー＃１〜＃３（１００（Mbps））、及び入力レートＲがフロー＃１〜＃３より高い契約レートＲｏ内のフロー＃４（１（Gbps））が混在する。
【０１６２】
フロー＃１〜＃３のミニバケツ３０は帯域超過により枯渇するため、緊急要求メッセージが出力される。しかし、フロー＃１〜＃３の入力レートＲは契約レートＲｏより大きいため、フロー＃１〜＃３の緊急要求メッセージは、優先キュー２００に入力されない。したがって、優先キュー２００は輻輳しない。
【０１６３】
そして、フロー＃４のミニバケツ３０のトークン蓄積量が第２閾値ｔｈ２を下回ったとき、フロー＃４の緊急要求メッセージが出力される。フロー＃４の入力レートＲは契約レートＲｏ以下であるため、フロー＃４の緊急要求メッセージは、通常キュー２０１ではなく、優先キュー２００に入力される（点線参照）。
【０１６４】
このとき、優先キュー２００は輻輳していないため、フロー＃４の緊急要求メッセージに応じて、直ちにメインバケツ１１のトークンがフロー＃４のミニバケツ３０に供給される。したがって、フロー＃４にミニバケツ３０には、パケットの通過に間に合うようにトークンが供給され、パケットの廃棄は生じない。これにより、フロー＃４の出力レートが入力レートＲと同じ１（Gbps）に維持されるため、フロー＃４の契約帯域が保証される。
【０１６５】
これまで述べたように、実施例に係る帯域制御であるポリサは、トークン管理部１と、通過制御部３と、優先度制御部２とを有する。トークン管理部１は、要求に応じパケットのトークンを供給する。通過制御部３は、パケットのフローごとにトークン管理部１にトークンを要求し、その要求に応じ供給されたトークンに基づき、フローごとにパケットの通過を制御する。
【０１６６】
優先度制御部２は、フローごとのパケットの入力レートＲとフローごとに設定された契約レートＲｏを比較し、その比較結果に応じてトークン管理部１に対する要求の優先度をフローごとに制御する。
【０１６７】
上記の構成によると、優先度制御部２は、入力レートＲが契約レートＲｏ以下であるフローの要求の優先度を、入力レートＲが契約レートＲｏより大きいフローの要求より高い値とすることができる。これにより、入力レートＲが契約レートＲｏ以下であるフローにトークンが優先的に供給されるため、そのフローの契約帯域が保証される。
【０１６８】
また、実施例に係る帯域制御方法は、以下のステップを含む。
ステップ（１）：要求に応じパケットのトークンを供給するトークン管理部１にパケットのフローごとにトークンを要求する。
ステップ（２）：要求に応じ供給されたトークンに基づき、フローごとにパケットの通過を制御する。
ステップ（３）：フローごとのパケットの入力レートＲとフローごとに設定された契約レートＲｏを比較する。
ステップ（４）：その比較結果に応じてトークン管理部１に対する要求の優先度をフローごとに制御する。
【０１６９】
実施例に係る帯域制御方法は、実施例に係る帯域制御装置と同様の構成を含むので、上述した内容と同様の作用効果を奏する。
【０１７０】
上述した実施形態は本発明の好適な実施の例である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施可能である。
【０１７１】
なお、以上の説明に関して更に以下の付記を開示する。
（付記１）  要求に応じパケットのトークンを供給する供給部と、
パケットのフローごとに前記供給部に前記トークンを要求し、該要求に応じ供給された前記トークンに基づき、前記フローごとにパケットの通過を制御する通過制御部と、
前記フローごとのパケットの入力レートと前記フローごとに設定された設定値を比較し、該比較結果に応じて前記供給部に対する前記要求の優先度を前記フローごとに制御する優先度制御部とを有することを特徴とする帯域制御装置。
（付記２）  前記優先度制御部は、前記入力レートが前記設定値以下である前記フローの前記要求の優先度を、前記入力レートが前記設定値を上回る前記フローの前記要求の優先度より高い値とすることを特徴とする付記１に記載の帯域制御装置。
（付記３）  前記優先度制御部は、前記要求の優先度を、前記入力レートと前記設定値の差分に応じた複数の段階に分けることを特徴とする付記１または２に記載の帯域制御装置。
（付記４）  前記通過制御部は、パケットを通過させるたびに前記フローごとに前記トークンを減算し、前記トークンが所定の第１閾値を下回ったとき及び前記所定の第１閾値より小さい所定の第２閾値を下回ったとき、前記トークンを要求することを特徴とする付記１乃至３の何れかに記載の帯域制御装置。
（付記５）  前記優先度制御部は、
前記トークンが前記所定の第２閾値を下回った前記フローの前記要求の優先度を、前記トークンが前記所定の第１閾値を下回った前記フローの前記要求の優先度より高い値とし、
前記トークンが前記所定の第２閾値を下回った前記フローのうち、前記入力レートが前記設定値以下である前記フローの前記要求の優先度を、前記入力レートが前記設定値を上回る前記フローの前記要求の優先度より高い値とすることを特徴とする付記４に記載の帯域制御装置。
（付記６）  前記優先度制御部は、前記所定の第１閾値と前記所定の第２閾値の差分、及び前記トークンが前記所定の第１閾値を下回ったときと前記トークンが前記所定の第２閾値を下回ったときの時間差から前記入力レートを算出することを特徴とする付記４または５に記載の帯域制御装置。
（付記７）  前記優先度制御部は、前記所定の第１閾値を下回ったときと前記所定の第２閾値を下回ったときの前記トークンの差分、及び前記トークンが前記所定の第１閾値を下回ったときと前記トークンが前記所定の第２閾値を下回ったときの時間差から前記入力レートを算出することを特徴とする付記４または５に記載の帯域制御装置。
（付記８）  前記優先度制御部は、複数回算出した前記入力レートの平均値を算出し、前記平均値と前記設定値を比較し、該比較結果に応じて前記要求の優先度を制御することを特徴とする付記１乃至７の何れかに記載の帯域制御装置。
（付記９）  前記通過制御部は、前記トークンに基づきパケットを廃棄し、
前記優先度制御部は、前記通過制御部における前記トークンの要求から供給までの期間ごとに前記フローごとのパケットの廃棄の有無を検出し、複数の期間における該廃棄の判定回数と前記フローごとの所定回数を比較し、該比較結果に応じて前記供給部に対する前記トークンの要求の優先度を前記フローごとに制御することを特徴とする付記１乃至８の何れかに記載の帯域制御装置。
（付記１０）  要求に応じパケットのトークンを供給する供給部に、パケットのフローごとに前記トークンを要求し、
該要求に応じ供給された前記トークンに基づき、前記フローごとにパケットの通過を制御し、
前記フローごとのパケットの入力レートと前記フローごとに設定された設定値を比較し、
該比較結果に応じて前記供給部に対する前記要求の優先度を前記フローごとに制御することを特徴とする帯域制御方法。
（付記１１）  前記入力レートが前記設定値以下である前記フローの前記要求の優先度を、前記入力レートが前記設定値を上回る前記フローの前記要求の優先度より高い値とすることを特徴とする付記１０に記載の帯域制御方法。
（付記１２）  前記要求の優先度を、前記入力レートと前記設定値の差分に応じた複数の段階に分けることを特徴とする付記１０または１１に記載の帯域制御方法。
（付記１３）  パケットを通過させるたびに前記フローごとに前記トークンを減算し、前記トークンが所定の第１閾値を下回ったとき及び前記所定の第１閾値より小さい所定の第２閾値を下回ったとき、前記トークンを要求することを特徴とする付記１０乃至１２の何れかに記載の帯域制御方法。
（付記１４）  前記トークンが前記所定の第２閾値を下回った前記フローの前記要求の優先度を、前記トークンが前記所定の第１閾値を下回った前記フローの前記要求の優先度より高い値とし、
前記トークンが前記所定の第２閾値を下回った前記フローのうち、前記入力レートが前記設定値以下である前記フローの前記要求の優先度を、前記入力レートが前記設定値を上回る前記フローの前記要求の優先度より高い値とすることを特徴とする付記１３に記載の帯域制御方法。
（付記１５）  前記所定の第１閾値と前記所定の第２閾値の差分、及び前記トークンが前記所定の第１閾値を下回ったときと前記トークンが前記所定の第２閾値を下回ったときの時間差から前記入力レートを算出することを特徴とする付記１３または１４に記載の帯域制御方法。
（付記１６）  前記所定の第１閾値を下回ったときと前記所定の第２閾値を下回ったときの前記トークンの差分、及び前記トークンが前記所定の第１閾値を下回ったときと前記トークンが前記所定の第２閾値を下回ったときの時間差から前記入力レートを算出することを特徴とする付記１３または１４に記載の帯域制御方法。
（付記１７）  複数回算出した前記入力レートの平均値を算出し、前記平均値と前記設定値を比較し、該比較結果に応じて前記要求の優先度を制御することを特徴とする付記１０乃至１６の何れかに記載の帯域制御方法。
（付記１８）  前記トークンに基づきパケットを廃棄し、
前記トークンの要求から供給までの期間ごとに前記フローごとのパケットの廃棄の有無を検出し、
複数の期間における該廃棄の判定回数と前記フローごとの所定回数を比較し、
該比較結果に応じて前記供給部に対する前記トークンの要求の優先度を前記フローごとに制御することを特徴とする付記１０乃至１７の何れかに記載の帯域制御方法。
【符号の説明】
【０１７２】
１       トークン管理部
２       優先度制御部
３       通過制御部
１１       メインバケツ
２１       要求判定部
２２       レート監視テーブル
３０       ミニバケツ
３１       通過判定部
３２       トークン要求部
２００      優先キュー
２０１      通常キュー
２０２      準優先キュー
２０３〜２０６     第１〜第４キュー
【図１】
2017041807.tif 000003
【図２】
2017041807.tif 000004
【図３】
2017041807.tif 000005
【図４】
2017041807.tif 000006
【図５】
2017041807.tif 000007
【図６】
2017041807.tif 000008
【図７】
2017041807.tif 000009
【図８】
2017041807.tif 000010
【図９】
2017041807.tif 000011
【図１０】
2017041807.tif 000012
【図１１】
2017041807.tif 000013
【図１２】
2017041807.tif 000014
【図１３】
2017041807.tif 000015
【図１４】
2017041807.tif 000016
【図１５】
2017041807.tif 000017
【図１６】
2017041807.tif 000018
【図１７】
2017041807.tif 000019
【図１８】
2017041807.tif 000020
【図１９】
2017041807.tif 000021
【図２０】
2017041807.tif 000022
【図２１】
2017041807.tif 000023
【図２２】
2017041807.tif 000024