(57)【要約】【課題】  パケットの遅延を低減する通信装置及びパケットスケジューリング方法を提供する。【解決手段】  通信装置は、パケットを蓄積する複数のキューと、前記複数のキューに、キューごとの優先度に基づく順序に従って、読出許容量をそれぞれ与えるスケジューラ部と、前記読出許容量を消費して前記複数のキューから前記パケットを読み出す読出処理部と、前記複数のキューに蓄積された前記パケットの蓄積量を、キューごとに計数する蓄積量計数部とを有し、前記蓄積量計数部は、前記スケジューラ部に前記蓄積量の変化を通知し、前記スケジューラ部は、前記蓄積量計数部の当該通知に応じて、前記複数のキューのうち、前記蓄積量が変化したキューの前記優先度を調整する。【選択図】図８
2014187421.tif 000002
【特許請求の範囲】
【請求項１】
パケットを蓄積する複数のキューと、
前記複数のキューに、キューごとの優先度に基づく順序に従って、読出許容量をそれぞれ与えるスケジューラ部と、
前記読出許容量を消費して前記複数のキューから前記パケットを読み出す読出処理部と、
前記複数のキューに蓄積された前記パケットの蓄積量を、キューごとに計数する蓄積量計数部とを有し、
前記蓄積量計数部は、前記スケジューラ部に前記蓄積量の変化を通知し、
前記スケジューラ部は、前記蓄積量計数部の当該通知に応じて、前記複数のキューのうち、前記蓄積量が変化したキューの前記優先度を調整することを特徴とする通信装置。
【請求項２】
前記蓄積量計数部は、前記スケジューラ部に、前記蓄積量が０になったことを通知し、
前記スケジューラ部は、前記蓄積量計数部の当該通知に応じて、前記複数のキューのうち、前記蓄積量が０になったキューの前記優先度を低下させることを特徴とする請求項１に記載の通信装置。
【請求項３】
前記複数のキューのうち、前記優先度を低下させたキューに前記パケットが蓄積されたことを、前記スケジューラ部に通知する通知部を、さらに有し、
前記スケジューラ部は、前記通知部の当該通知に応じて、前記複数のキューのうち、前記優先度を低下させたキューの前記優先度を低下前の値に戻すことを特徴とする請求項２に記載の通信装置。
【請求項４】
前記スケジューラ部は、重み付けラウンドロビン方式に従い、前記複数のキューに前記読出許容量を与え、前記複数のキューのうち、前記優先度を低下させたキューに対する前記読出許容量の付与を、他のキューの後回しにすることを特徴とする請求項２または３の何れかに記載の通信装置。
【請求項５】
前記蓄積量計数部は、前記スケジューラ部に変化後の前記蓄積量を通知し、
前記スケジューラ部は、前記蓄積量計数部から通知された変化後の前記蓄積量に応じて、前記複数のキューのうち、前記蓄積量が変化したキューの前記優先度を調整することを特徴とする請求項１に記載の通信装置。
【請求項６】
前記複数のキューに与えられた前記読出許容量を、キューごとに計数する読出許容量計数部を、さらに有し、
前記読出許容量計数部は、前記スケジューラ部に前記読出許容量の変化を通知し、
前記スケジューラ部は、前記読出許容量計数部の当該通知に応じて、前記複数のキューのうち、前記読出許容量が変化したキューの前記優先度を調整することを特徴とする請求項１乃至５の何れかに記載の通信装置。
【請求項７】
前記読出許容量計数部は、前記スケジューラ部に前記読出許容量が０より大きくなったことを通知し、
前記スケジューラ部は、前記読出許容量計数部の当該通知に応じて、前記複数のキューのうち、前記読出許容量が０より大きくなったキューの前記優先度を低下させることを特徴とする請求項６に記載の通信装置。
【請求項８】
前記読出許容量計数部は、前記スケジューラ部に変化後の前記読出許容量を通知し、
前記スケジューラ部は、前記読出許容量計数部から通知された変化後の前記読出許容量に応じて、前記複数のキューのうち、前記読出許容量が変化したキューの前記優先度を調整することを特徴とする請求項６に記載の通信装置。
【請求項９】
前記複数のキューを一組として、複数の組から読み出された前記パケットをそれぞれ蓄積する複数の上位キューを、さらに有し、
前記スケジューラ部は、
前記複数の上位キューから、上位キューごとの上位側優先度に基づく順序に従って、１つの上位キューを選択し、選択した上位キューに対応する前記複数のキューの１つに前記読出許容量を与え、
前記複数の組の何れかに含まれる前記複数のキューの全ての前記蓄積量が０となった場合、前記複数の上位キューのうち、当該組に対応する上位キューの前記上位側優先度を低下させることを特徴とする請求項２または３に記載の通信装置。
【請求項１０】
パケットを蓄積する複数のキューに、キューごとの優先度に基づく順序に従って、読出許容量をそれぞれ与え、
前記読出許容量を消費して前記複数のキューから前記パケットを読み出し、
前記複数のキューに蓄積された前記パケットの蓄積量の変化に応じて、前記複数のキューのうち、前記蓄積量が変化したキューの前記優先度を調整することを特徴とするパケットスケジューリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、通信装置及びパケットスケジューリング方法に関する。
【背景技術】
【０００２】
通信需要の増加に伴い、レイヤ２スイッチやルータなどのスイッチ機器、すなわちパケットを交換するパケット交換装置のスループットの向上が求められている。スループットを向上するために、キューからのパケットの読み出し制御によりトラフィックを管理するスケジューリング機能の改善が提案されている。
【０００３】
例えば、特許文献１には、ＤＲＲ（Deficit
Round Robin）法において統計的観測情報に基づいて粒度を設定する点が開示されている。特許文献２には、帯域制御を維持するアルゴリズムの帯域の精度を、他の異なるアルゴリズムにより選択されたキューからデータを読み出した場合において維持する点が開示されている。
【０００４】
特許文献３には、パケットを格納するキューごとに、固定のセグメント長を単位としてスケジューリングを行うことにより、外部メモリに対するアクセス処理時間を低減する点が開示されている。特許文献４には、入力制御部及び出力帯域制御部がファブリックを介して接続された構成において、入力制御部が、要求により出力帯域制御部から取得したクレジットに基づいて、出力帯域制御部にファブリックを介してパケットを出力する点が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００１−２２３７４０号公報
【特許文献２】特開２００５−３３４０８号公報
【特許文献３】特開２００５−２８６３８３号公報
【特許文献４】米国特許第７，９９０，８５８号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
キューから１つのパケットが読み出されるたびに、スケジューリングにより次の読み出し対象のキューを選択する場合、スケジューリングに許容される処理時間は、パケットの読み出し処理の時間に制約される。このため、スケジューリングに許容される処理時間は、パケットの長さが、例えばイーサネット（登録商標、以下同様）フレームのように可変であるとき、読み出されるパケットの長さ（つまり、データ量）に依存する。
【０００７】
例えば、通信速度を１００（Ｇｂｐｓ）とすると、スケジューリングに許容される処理時間は、１５００（Ｂｙｔｅ）の長さのパケットの場合、約１２１（ｎｓ）であるのに対し、６４（Ｂｙｔｅ）の長さのパケットの場合、約６．７（ｎｓ）となる。つまり、短いパケット（ショートパケット）が連続で読み出されるとき、スケジューリングに許容される時間は、比較的に短い時間に制限されるため、スケジューリングに高い処理性能が求められる。
【０００８】
例えば、ショートパケットだけを読み出す場合、スケジューリングに約１４８．８（Ｍｂｐｓ）の処理速度が求められる。この場合、パケット処理の動作周波数を３００（ＭＨｚ）とすると、１つのショートパケットを２クロック（３００（ＭＨｚ）／２＝１５０（Ｍｂｐｓ）≒１４８．８（Ｍｂｐｓ））で処理することになる。要求される処理速度は、キューの個数が多い場合や、スケジューリングに複雑なアルゴリズムを用いた場合、さらに高くなる。
【０００９】
これに対して、複数のパケットを、連続して読み出せるようにバースト的なトラフィックとして扱い、スケジューリング処理を、１パケット単位ではなく、所定のデータ量を単位として行えば、スケジューリングに許容される時間の制限が緩和される。例えば、２５００（Ｂｙｔｅ）単位でスケジューリング処理を行う場合、動作周波数を３００（ＭＨｚ）とすれば、６０クロックの処理時間（２００（ｎｓ））で１００（Ｇｂｐｓ）（＝２５００（Ｂｙｔｅ）／２００（ｎｓ））のスループットが実現される。つまり、このバーストデータ単位のスケジューリング方式によれば、スケジューリングに許容される時間の制限を緩和することが可能となる。
【００１０】
本方式の場合、各キューから所定のデータ量が一度に読み出されるように、当該データ量が、読み出し可能なパケットのデータ量を示す読出許容量として、キューごとに与えられる。キューに蓄積されたパケットは、キューが保有する読出許容量が０より大きい場合、該読出許容量を消費して読み出される。
【００１１】
この読出許容量による制御を行う場合、読出許容量を与えるキューを選択するためのスケジューリング処理が、パケットの読出対象のキューを選択するためのスケジューリング処理とは別に行われる。このとき、各キューに適切な優先順位で読出許容量を付与しなければ、パケットの読み出しに遅延が生ずる可能性がある。
【００１２】
例えば、パケットが蓄積されたキューに優先して、パケットが蓄積されていないキューに読出許容量を与えると、該蓄積されたパケットは、読出許容量が付与されるまで待機しなければならないため、遅延する。なお、このような問題は、イーサネットフレームに限られず、ＩＰ（Internet Protocol）パケットなどの他のパケットについても同様に存在する。さらに、このような問題は、パケット交換装置に限られず、波長多重伝送装置などの他の通信装置についても同様に存在する。
【００１３】
そこで本件は上記の課題に鑑みてなされたものであり、パケットの遅延を低減する通信装置及びパケットスケジューリング方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本明細書に記載の通信装置は、パケットを蓄積する複数のキューと、前記複数のキューに、キューごとの優先度に基づく順序に従って、読出許容量をそれぞれ与えるスケジューラ部と、前記読出許容量を消費して前記複数のキューから前記パケットを読み出す読出処理部と、前記複数のキューに蓄積された前記パケットの蓄積量を、キューごとに計数する蓄積量計数部とを有し、前記蓄積量計数部は、前記スケジューラ部に前記蓄積量の変化を通知し、前記スケジューラ部は、前記蓄積量計数部の当該通知に応じて、前記複数のキューのうち、前記蓄積量が変化したキューの前記優先度を調整する。
【００１５】
本明細書に記載のパケットスケジューリング方法は、パケットを蓄積する複数のキューに、キューごとの優先度に基づく順序に従って、読出許容量をそれぞれ与え、前記読出許容量を消費して前記複数のキューから前記パケットを読み出し、前記複数のキューに蓄積された前記パケットの蓄積量の変化に応じて、前記複数のキューのうち、前記蓄積量が変化したキューの前記優先度を調整する方法である。
【発明の効果】
【００１６】
本明細書に記載の通信装置及びパケットスケジューリング方法は、パケットの遅延を低減するという効果を奏する。
【図面の簡単な説明】
【００１７】
【図１】実施例に係る通信装置の機能構成を示す構成図である。
【図２】ネットワークインターフェースカードの機能構成を示す構成図である。
【図３】通信装置内のパケットの経路を示す図である。
【図４】比較例の出力処理部の機能構成を示す構成図である。
【図５】１００００（Ｂｙｔｅ）のパケットが到着した場合の出力処理部の動作例を示す図である。
【図６】１０００１（Ｂｙｔｅ）のパケットが到着した場合の出力処理部の動作例を示す図である。
【図７】比較例におけるパケットの入出力タイミング及びクレジットの付与順序の例を示す図である。
【図８】第１実施例の出力処理部の機能構成を示す構成図である。
【図９】蓄積量フラグＱ＿ｅｍｐｔｙに応じた優先度の調整動作の一例を示す図である。
【図１０】クレジットの付与の順序を示す表である。
【図１１】比較例におけるクレジットの付与の順序を示す表である。
【図１２】パケットを読み出すときのキュー管理部の動作を示すフローチャートである。
【図１３】キュー管理部から通知を受信したときのスケジューラ部の動作を示すフローチャートである。
【図１４】スケジューリング処理を行うときのスケジューラ部の動作を示すフローチャートである。
【図１５】パケットの到着通知を受信したときのスケジューラ部の動作を示すフローチャートである。
【図１６】第１実施例の動作の一例を示す図である。
【図１７】実施例におけるパケットの入出力タイミング及びクレジットの付与順序の例を示す図である。
【図１８】比較例における重み付けラウンドロビン方式の動作の一例を示す図である。
【図１９】蓄積量フラグＱ＿ｅｍｐｔｙを用いた重み付けラウンドロビン方式の動作の一例を示す図である。
【図２０】スケジューリング処理を行うときのスケジューラ部の動作を示すフローチャートである。
【図２１】第２実施例の動作の一例を示す図である。
【図２２】パケットが読み出されたときのキュー管理部の動作を示すフローチャートである。
【図２３】キュー管理部から通知を受信したときのスケジューラ部の動作を示すフローチャートである。
【図２４】スケジューリング処理を行うときのスケジューラ部の動作を示すフローチャートである。
【図２５】第３実施例の出力処理部の機能構成を示す構成図である。
【図２６Ａ】第３実施例の動作の一例を示す図（その１）である。
【図２６Ｂ】第３実施例の動作の一例を示す図（その２）である。
【図２７】パケットを読み出すときのキュー管理部の動作を示すフローチャートである。
【図２８】キュー管理部から通知を受信したときのスケジューラ部の動作を示すフローチャートである。
【図２９】スケジューリング処理を行うときのスケジューラ部の動作を示すフローチャートである。
【図３０Ａ】第４実施例の動作の一例を示す図（その１）である。
【図３０Ｂ】第４実施例の動作の一例を示す図（その２）である。
【図３１】パケットを読み出すときのキュー管理部の動作を示すフローチャートである。
【図３２】キュー管理部から通知を受信したときのスケジューラ部の動作を示すフローチャートである。
【図３３】スケジューリング処理を行うときのスケジューラ部の動作を示すフローチャートである。
【図３４】第５実施例の動作の一例を示す図である。
【図３５】パケットを読み出すときのキュー管理部の動作を示すフローチャートである。
【図３６】キュー管理部から通知を受信したときのスケジューラ部の動作を示すフローチャートである。
【図３７】第６実施例の出力処理部の機能構成を示す構成図である。
【図３８】第６実施例の動作の一例を示す図である。
【図３９】第６実施例の動作の一例を示す図である。
【図４０】第６実施例の動作の一例を示す図である。
【図４１】第６実施例の動作の一例を示す図である。
【図４２】スケジューリング処理を行うときのスケジューラ部の動作を示すフローチャートである。
【発明を実施するための形態】
【００１８】
図１は、実施例に係る通信装置の機能構成を示す構成図である。通信装置は、複数のネットワークインターフェースカード９１と、２枚のスイッチカード９２と、コントロールカード９３とを有する。各カード９１〜９３は、筐体に設けられた個別のスロットに収容され、互いに電気的に接続される。なお、本明細書において、通信装置として、レイヤ２スイッチやルータなどのパケット交換装置を例に挙げるが、これに限定されない。
【００１９】
通信装置は、外部装置から受信したパケットを、その宛先に従って他の外部装置に中継する。なお、本明細書において、パケットとは、伝送されるデータ（情報）の伝送単位であり、例としてイーサネットフレームを挙げるが、これに限られず、ＩＰパケットなどの他のフレームであってもよい。
【００２０】
複数のネットワークインターフェースカード９１は、それぞれ、外部装置との間において、パケットを送受信する。外部装置としては、例えば、パーソナルコンピュータなどの端末装置、サーバ装置、及びルータが挙げられる。複数のネットワークインターフェースカード９１は、複数のポートにより光ファイバと接続され、例えば１０００ＢＡＳＥ−ＳＸの規格に基づく通信を行う。
【００２１】
２枚のスイッチカード９２は、それぞれ、複数のネットワークインターフェースカード９１の間において、パケットを交換する。より具体的には、スイッチカード９２は、ネットワークインターフェースカード９１からパケットが入力され、パケットを、その宛先に応じたネットワークインターフェースカード９１に出力する。２枚のスイッチカード９２は、例えば、ハードウェア故障などの障害に備えて、運用系及び予備系として使用される。
【００２２】
コントロールカード９３は、複数のネットワークインターフェースカード９１及び２枚のスイッチカード９２を制御する。コントロールカード９３は、ネットワーク制御装置などと接続され、ユーザーインターフェースに関する処理、各カード９１，９２に対する設定処理、及び各カード９１，９２からの情報収集処理などを行う。コントロールカード９３は、これらの処理を実行するＣＰＵ（Central Processing Unit）などのプロセッサ９３０及びメモリ９３１を有する。
【００２３】
図２は、ネットワークインターフェースカード９１の機能構成を示す構成図である。ネットワークインターフェースカード９１は、複数の光送受信器９１０と、ＰＨＹ／ＭＡＣ部９１１と、入力処理部９１２と、出力処理部９１３と、制御部９１４とを有する。
【００２４】
複数の光送受信器９１０は、それぞれ、外部装置から光ファイバを介して受信した光信号を電気信号に変換してＰＨＹ／ＭＡＣ部９１１に出力し、また、ＰＨＹ／ＭＡＣ部９１１から入力された電気信号を光信号に変換し、光ファイバを介して外部装置に送信する。つまり、複数の光送受信器９１０は、外部装置との間でパケットを送受信するためのポートとして機能する。
【００２５】
ＰＨＹ／ＭＡＣ部９１１は、外部装置とのリンクの確立処理や複数の光送受信器１０に対するパケットの分配処理などを行う。ＰＨＹ／ＭＡＣ部９１１は、複数の光送受信器９１０から入力されたパケットを入力処理部９１２に出力し、出力処理部９１３から入力されたパケットを複数の光送受信器９１０に出力する。
【００２６】
入力処理部９１２及び出力処理部９１３は、イングレス（ＩＮＧＲＥＳＳ）及びイーグレス（ＥＧＲＥＳＳ）のパケット処理をそれぞれ行う。入力処理部９１２は、パケットの帯域制御処理などを行って、スイッチカード９２にパケットを出力する。出力処理部９１３は、スイッチカード９２から入力されたパケットの帯域制御処理などを行って、ＰＨＹ／ＭＡＣ部９１１にパケットを出力する。
【００２７】
制御部９１４は、コントロールカード９３と通信を行い、入力処理部９１２及び出力処理部９１３の制御を行う。制御部９１４は、ＣＰＵなどのプロセッサ及びメモリ（図示せず）を備える。
【００２８】
図３には、通信装置内のパケットの経路が示されている。なお、図３は、入力処理部９１２の構成も示す。
【００２９】
まず、パケットは、ネットワークインターフェースカード９１の入力処理部９１２に入力される。入力処理部９１２は、クラス判定部８０と、ポリサー８１と、分配部８２と、複数の入力キュー８３と、出力部８４とを有する。
【００３０】
クラス判定部８０は、パケットごとの通信品質（ＱｏＳ：Quality of Service）のクラスを判定し、クラスに応じたフローＩＤを、例えば装置内ヘッダに含めてパケットに付与する。クラス判定部８０は、例えば、パケットのヘッダに含まれる宛先（ＤＡ：Destination
Address）、またはＶＬＡＮ（Virtual Local Area Network）  ＩＤに基づいてクラスを判定する。
【００３１】
ポリサー８１は、入力されるパケットのトラフィック量が所定の帯域を超えないように、所定帯域を超える分のパケットを廃棄する。分配部８２は、パケットを、宛先となるネットワークインターフェースカード９１に応じて、複数の入力キュー８３に分配する。つまり、入力キュー８３は、ネットワークインターフェースカード９１ごとに設けられている。複数の入力キュー８３は、パケットを、出力部８４により読み出されるまで蓄積する。出力部８４は、複数の入力キュー８３から１つを選択して、選択した入力キュー８３からパケットを読み出して、スイッチカード９２のスイッチ部９２０に出力する。スイッチ部９２０は、入力されたパケットを宛先に応じたネットワークインターフェースカード９１の出力処理部９１３に出力する。
【００３２】
図４は、比較例の出力処理部９１３の機能構成を示す構成図である。出力処理部９１３は、キュー管理部（QMG: Queue ManaGer）１及びスケジューラ部（SCH: SCHeduler）２を有する。
【００３３】
キュー管理部１は、分配部１０と、複数のキュー１１と、読出処理部１２と、蓄積量計数部１３０と、クレジット計数部１３１とを有する。キュー管理部１は、複数のキュー１１の各々に蓄積されたパケットの蓄積量を管理し、スケジューラ部からキュー１１ごとに付与されたクレジット、つまり、読み出し可能なパケットのデータ量を示す読出許容量に基づいて、パケットの読み出しを制御する。
【００３４】
分配部１０は、スイッチカード９２から到着したパケット（図４中の「ＰＫＴ」参照）を、フローＩＤごとに複数のキュー１１にそれぞれ分配する。図４に示された例では、フロー＃０のパケットが分配部１０に到着し、フロー＃０用のキュー１１に入力される。また、分配部１０は、パケットが到着するたびに、到着したパケットのパケット長、つまりデータ量をスケジューラ部２に通知する。
【００３５】
複数のキュー１１は、それぞれ、分配部１０から入力されたパケットを蓄積する。キュー１１は、フロー＃０〜＃Ｎ（Ｎ：自然数）ごとに設けられており、個数Ｎに限定はない。
【００３６】
読出処理部１２は、クレジット（読出許容量）を消費して複数のキュー１１からパケットを読み出す。読出処理部１２は、複数のキュー１１のうち、０（Ｂｙｔｅ）より多いクレジットを保有するキュー１１から、パケットを読み出す対象となるキュー１１を選択する。図４に示された例では、５１２（Ｂｙｔｅ）のパケットが蓄積されたフロー＃Ｎ用のキュー１１から、６４（Ｂｙｔｅ）のパケットが読み出されている。
【００３７】
蓄積量計数部１３０は、複数のキュー１１に蓄積されたパケットの蓄積量を、キュー１１ごと（つまり、フロー＃０〜＃Ｎごと）に計数する。蓄積量計数部１３０は、パケットがキュー１１に入力されたとき、及び、読出処理部１１がキュー１１からパケットを読み出したとき、該当するキュー１１の蓄積量を更新する。
【００３８】
図４に示された例において、フロー＃０用のキュー１１に、既に１００（Ｂｙｔｅ）のパケットが蓄積されており、分配部１０に１０００（Ｂｙｔｅ）のパケットが到着することによって、フロー＃０の蓄積量は、１１００（Ｂｙｔｅ）となる。また、フロー＃２の蓄積量は、１００００（Ｂｙｔｅ）である。フロー＃Ｎの蓄積量は、５１２（Ｂｙｔｅ）のパケットが蓄積されたフロー＃Ｎ用のキュー１１から、６４（Ｂｙｔｅ）のパケットが読み出されることにより、４４８（Ｂｙｔｅ）（＝５１２−６４）となる。
【００３９】
クレジット計数部１３１は、複数のキュー１１に与えられたクレジットを、キュー１１ごと（つまり、フロー＃０〜＃Ｎごと）に計数する。クレジットは、スケジューラ部２から各フロー＃０〜＃Ｎのキュー１１に対して、一度に、一定量（本例では２５００（Ｂｙｔｅ））だけ与えられる。
【００４０】
クレジット計数部１３１は、スケジューラ部２からクレジットの付与があったとき、該当するキュー１１のクレジットを更新する。図４の例では、スケジューラ部２から、フロー＃Ｎのキュー１１に２５００（Ｂｙｔｅ）のクレジットが与えられている。このため、フロー＃Ｎのクレジットは、既存の５１２（Ｂｙｔｅ）に、２５００（Ｂｙｔｅ）が加算されて、３０１２（Ｂｙｔｅ）となる。
【００４１】
読出処理部１２は、パケットを読み出す対象となるキュー１１の選択処理を、パケット単位ではなく、一度のクレジットの付与単位である２５００（Ｂｙｔｅ）単位に行い、１以上のパケットをバースト的なトラフィック（データの塊）として読み出す。したがって、読出処理部１２におけるスケジューリング処理、つまりキュー１１の選択処理の時間的制限が、パケット単位のスケジューリングの場合よりも緩和される。
【００４２】
また、クレジット計数部１３１は、読出処理部１２によりクレジットが消費されたとき、該当するキュー１１のクレジットを更新する。つまり、クレジット計数部１３１は、クレジットが消費されたとき、該当するキュー１１のクレジットから、消費分、つまり読み出されたパケットのパケット長分を減算する。
【００４３】
読出処理部１２は、１つのパケットを複数の部分に分割して読み出さないため、パケットの一部のデータは、余剰分として、クレジット分を超えて読み出されることになる。つまり、読出処理部１２は、キュー１１が有するクレジットが０（Ｂｙｔｅ）より大きければ、クレジットが読み出すパケットのパケット長より少ない場合であっても、当該パケットを読み出す。この場合、クレジットは、負の値となる。
【００４４】
例えば、フロー＃０のキュー１１が、２５００（Ｂｙｔｅ）のクレジットを有している場合に、当該キュー１１から２６００（Ｂｙｔｅ）のパケット長のパケットが読み出されると、フロー＃０のクレジットは、図４に示されるように、−１００（Ｂｙｔｅ）となる。このように、クレジットが、読み出し対象となるパケットのパケット長に満たない場合に、該パケットが読み出されると、クレジット計数部１３１は、足りない分のデータ量をマイナス分として計上する。
【００４５】
一方、スケジューラ部２は、仮想蓄積量計数部２１０及びクレジット付与部２０を有する。仮想蓄積量計数部２１０は、キュー１１ごと（つまり、フロー＃０〜＃Ｎごと）に仮想蓄積量を計数する。仮想蓄積量は、蓄積量計数部１３０により計数される蓄積量とは異なり、キュー１１に与えられたクレジットを、読み出されたパケットのパケット長と仮定した場合に、仮想的に算出される蓄積量である。
【００４６】
仮想蓄積量計数部２１０は、キュー１１に入力されたパケットのパケット長を、分配部１０から通知され、また、キュー１１にクレジットが与えられたことを、クレジット付与部２０から通知される。仮想蓄積量計数部２１０は、パケットがキュー１１に入力されたとき、該パケットのパケット長を、該当するキュー１１の仮想蓄積量に加算する。また、仮想蓄積量計数部２１０は、キュー１１にクレジットが与えられたとき、該当するキュー１１の仮想蓄積量から、与えられたクレジット分を減算する。つまり、仮想蓄積量は、キュー１１の蓄積量から、当該キュー１１に与えたクレジット分を減算して得られる値である。これに対して、蓄積量計数部１３０は、パケットの読み出し時に、既存の蓄積量からパケット長を減算するので、蓄積量及び仮想蓄積量は、一定期間、ずれを生ずる。
【００４７】
図４の例において、フロー＃０の仮想蓄積量は、１０００（Ｂｙｔｅ）のパケットが、フロー＃０のキュー１１に入力されるから、既存の−１００（Ｂｙｔｅ）に、１０００（Ｂｙｔｅ）が加算され、９００（Ｂｙｔｅ）となる。また、フロー＃Ｎの仮想蓄積量は、フロー＃Ｎのキュー１１に２５００（Ｂｙｔｅ）のクレジットが与えられているので、既存の５１２（Ｂｙｔｅ）から２５００（Ｂｙｔｅ）が減算され、−１９８８（Ｂｙｔｅ）となる。
【００４８】
クレジット付与部２０は、複数のキュー１１に、キュー１１ごとの仮想蓄積量に従って、一定のクレジット（２５００（Ｂｙｔｅ））をそれぞれ与える。クレジット付与部２０は、例えば、クラス判定部８０で判定されたクラス優先度に従い、複数のキュー１１のうち、クレジットを与える対象となるキュー１１を選択する。なお、クレジット付与部２０は、仮想蓄積量を０とするように、クレジットの付与対象となるキュー１１を選択する。
【００４９】
また、クレジット付与部２０は、シェーパによりクレジットを与える間隔を調整する。シェーパは、フロー＃０〜＃Ｎごとに設けられ、例えば、送信権として扱われるトークンを貯めるトークンバケットを有し、トークンの残量に応じてクレジットの付与を制限する。このため、クレジットを与える間隔は、トークンの供給レートにより調整される。
【００５０】
このように、出力処理部９１３は、パケットを、読み出し処理においてバースト的なトラフィックとして扱うため、キュー管理部１及びスケジューラ部２に機能が分離されている。このため、スケジューラ部２は、キュー１１ごとの蓄積量に代えて、仮想蓄積量を管理する。仮想蓄積量は、既に述べたとおり、蓄積量と必ずしも一致せず、異なる値をとり得るので、クレジット付与部２０がクレジットを付与する順序も、蓄積量に従うとは限らず、結果的にパケットの読み出しに遅延を生じ得るという問題がある。以下に、その理由を具体的に述べる。
【００５１】
図５には、１００００（Ｂｙｔｅ）のパケットが到着した場合の出力処理部９１３の動作例が示されている。図５は、図４に示された構成において、蓄積量計数部１３０の蓄積量、クレジット計数部１３１のクレジット、及び、仮想蓄積量計数部２１０の仮想蓄積量を、時系列（時刻ｔ０〜ｔ５）に示している。なお、以降の説明において、クレジット計数部１３１が計数したクレジットの値を、「クレジットカウント値」と表記する。
【００５２】
時刻ｔ０において、キュー管理部１に１００００（Ｂｙｔｅ）のパケットが到着することにより、蓄積量及び仮想蓄積量は、１００００（Ｂｙｔｅ）となる。また、クレジットカウント値は、０（Ｂｙｔｅ）とする。なお、フローＩＤは、＃０〜＃Ｎのうち、何れであってもよい。
【００５３】
次に、時刻ｔ１において、スケジューラ部２（クレジット付与部２０）からキュー管理部１に２５００（Ｂｙｔｅ）のクレジットが与えられる。これにより、クレジットカウント値は、２５００（Ｂｙｔｅ）となり、仮想蓄積量は、７５００（Ｂｙｔｅ）となる。
【００５４】
次に、時刻ｔ２において、１００００（Ｂｙｔｅ）のパケットが、キュー管理部１から読み出される。これにより、クレジットカウント値は、−７５００（Ｂｙｔｅ）となり、蓄積量は、０（Ｂｙｔｅ）となり、仮想蓄積量は、７５００（Ｂｙｔｅ）となる。
【００５５】
次に、時刻ｔ３において、スケジューラ部２からキュー管理部１に２５００（Ｂｙｔｅ）のクレジットが与えられる（２回目のクレジットの付与）。これにより、クレジットカウント値は、−５０００（Ｂｙｔｅ）となり、仮想蓄積量は、５０００（Ｂｙｔｅ）となる。
【００５６】
次に、時刻ｔ４において、スケジューラ部２からキュー管理部１に２５００（Ｂｙｔｅ）のクレジットが与えられる（３回目のクレジットの付与）。これにより、クレジットカウント値は、−２５００（Ｂｙｔｅ）となり、仮想蓄積量は、２５００（Ｂｙｔｅ）となる。
【００５７】
次に、時刻ｔ５において、スケジューラ部２からキュー管理部１に２５００（Ｂｙｔｅ）のクレジットが与えられる（４回目のクレジットの付与）。これにより、クレジットカウント値は、０（Ｂｙｔｅ）となり、仮想蓄積量は、０（Ｂｙｔｅ）となる。
【００５８】
このように、蓄積量は、時刻ｔ２におけるパケットの読み出しにより０（Ｂｙｔｅ）になるが、その後の時刻ｔ３〜ｔ５において、スケジューラ部２は、仮想蓄積量が０（Ｂｙｔｅ）になるようにクレジットを与える。本動作例では、到着したパケットのパケット長が、付与される２５００（Ｂｙｔｅ）のクレジットの整数倍（２５００（Ｂｙｔｅ）×４＝１００００（Ｂｙｔｅ））であるので、クレジットカウント値が、時刻ｔ５において０（Ｂｙｔｅ）となる。
【００５９】
しかし、到着したパケットのパケット長が、付与するクレジットの整数倍ではなく、端数を含む場合、以下に述べるように、蓄積量が０（Ｂｙｔｅ）であるにも関わらず、余分にクレジットを与えることになる。
【００６０】
図６には、１０００１（Ｂｙｔｅ）のパケットが到着した場合の出力処理部９１３の動作例が示されている。図６は、図４に示された構成において、蓄積量計数部１３０の蓄積量、クレジット計数部１３１のクレジット、及び、仮想蓄積量計数部２１０の仮想蓄積量を、時系列（時刻ｔ０〜ｔ６）に示している。
【００６１】
時刻ｔ０において、キュー管理部１に１０００１（Ｂｙｔｅ）のパケットが到着することにより、蓄積量及び仮想蓄積量は、１０００１（Ｂｙｔｅ）となる。また、クレジットカウント値は、０（Ｂｙｔｅ）とする。なお、フローＩＤは、＃０〜＃Ｎのうち、何れであってもよい。
【００６２】
次に、時刻ｔ１において、スケジューラ部２（クレジット付与部２０）からキュー管理部１に２５００（Ｂｙｔｅ）のクレジットが与えられる。これにより、クレジットカウント値は、２５００（Ｂｙｔｅ）となり、仮想蓄積量は、７５０１（Ｂｙｔｅ）となる。
【００６３】
次に、時刻ｔ２において、１０００１（Ｂｙｔｅ）のパケットが、キュー管理部１から読み出される。これにより、クレジットカウント値は、−７５０１（Ｂｙｔｅ）となり、蓄積量は、０（Ｂｙｔｅ）となる。
【００６４】
次に、時刻ｔ３において、スケジューラ部２からキュー管理部１に２５００（Ｂｙｔｅ）のクレジットが与えられる（２回目のクレジットの付与）。これにより、クレジットカウント値は、−５００１（Ｂｙｔｅ）となり、仮想蓄積量は、５００１（Ｂｙｔｅ）となる。
【００６５】
次に、時刻ｔ４において、スケジューラ部２からキュー管理部１に２５００（Ｂｙｔｅ）のクレジットが与えられる（３回目のクレジットの付与）。これにより、クレジットカウント値は、−２５０１（Ｂｙｔｅ）となり、仮想蓄積量は、２５０１（Ｂｙｔｅ）となる。
【００６６】
次に、時刻ｔ５において、スケジューラ部２からキュー管理部１に２５００（Ｂｙｔｅ）のクレジットが与えられる（４回目のクレジットの付与）。これにより、クレジットカウント値は、−１（Ｂｙｔｅ）となり、仮想蓄積量は、１（Ｂｙｔｅ）となる。
【００６７】
次に、時刻ｔ６において、スケジューラ部２からキュー管理部１に２５００（Ｂｙｔｅ）のクレジットが与えられる（５回目のクレジットの付与）。これにより、クレジットカウント値は、２４９９（Ｂｙｔｅ）となり、仮想蓄積量は、−２４９９（Ｂｙｔｅ）となる。
【００６８】
このように、本動作例では、仮想蓄積量を０（Ｂｙｔｅ）とするようにクレジットが付与された結果、パケット長が、２５００（Ｂｙｔｅ）のクレジットに対し端数を有するため、時刻ｔ６において、クレジットカウント値が２４９９（Ｂｙｔｅ）となる。上述したように、読出処理部１２は、クレジットカウント値が０より大きいとき、該当するキュー１１からパケットを読み出すが、時刻ｔ６において既に蓄積量は０（Ｂｙｔｅ）であるため、読み出し対象となるパケットが存在しない。
【００６９】
つまり、本動作例では、時刻ｔ６において、パケットの到着に先立って、余分にクレジットが与えられている。このようなクレジットの付与は、結果的にパケットの読み出しに遅延を生ずる。
【００７０】
図７には、比較例におけるパケットの入出力タイミング及びクレジットの払い出し順序の例が示されている。図７において、符号Ｐ１は、キュー管理部１に到着したフローＡ〜Ｚ（Ａ〜Ｚ：フローＩＤ）のパケットのタイミングを示し、符号Ｐ２は、キュー管理部１からポートに出力されたパケットのタイミングを示す。
【００７１】
フローＡ〜Ｍのパケットは、パケット長が１０００１（Ｂｙｔｅ）であるロングパケットであり、合計５（Ｇｂｐｓ）（例えば５（Ｍｂｐｓ）×１０００フロー）のレートでキュー管理部１に入力されている。一方、フローＮ〜Ｚのパケットは、パケット長が１００（Ｂｙｔｅ）であるショートパケットであり、合計５（Ｇｂｐｓ）（例えば５（Ｍｂｐｓ）×１０００フロー）のレートでキュー管理部１に入力されている。
【００７２】
キュー管理部１の出力側、つまりポートのレートを１０（Ｇｂｐｓ）とすると、キュー管理部１の入力側の合計レート及び出力側の合計レートが一致するため、理論上、パケットに遅延は生じない。しかし、実際は、ロングパケットのパケット長が１０００１（Ｂｙｔｅ）である場合、１００００（Ｂｙｔｅ）の場合と異なり、上述した余分なクレジットの付与のため、ショートパケットの出力タイミングに遅延ｔｄが生ずる。
【００７３】
符号Ｐ３は、ロングパケットのパケット長が１０００１（Ｂｙｔｅ）である場合のクレジットの付与順序を示す。また、符号Ｐ４は、ロングパケットのパケット長が１００００（Ｂｙｔｅ）の場合のクレジットの付与順序を示す。付与順序は、フローの種別（Ａ〜Ｚ）及び付与の回数により示されている。なお、付与順序は、図７の紙面右側が早く、紙面左側が遅い。
【００７４】
既に述べたように、１０００１（Ｂｙｔｅ）の場合、１００００（Ｂｙｔｅ）の場合と異なり、スケジューラ部２は、ロングパケットのフローＡ〜Ｍについて５回目のクレジットの付与を行う（矢印参照）。ここで、クレジットの付与間隔は、クレジット付与部２０のシェーパにおけるトークンの供給レートにより従うので、一定の単位時間内に付与されるクレジットは、フロー全体において所定量に制限される。
【００７５】
したがって、ロングパケットのフローＡ〜Ｍのキュー１１に、パケットの到着に先立って余分な付与（つまり５回目のクレジットの付与）が行われると、その後で入力されたショートパケットのフローＮ〜Ｚのキュー１１に対するクレジットの付与が遅延する。つまり、ロングパケットのパケット長が１０００１（Ｂｙｔｅ）の場合、ショートパケットに関するクレジットの付与順序が、１００００（Ｂｙｔｅ）の場合より遅れる（符号ｔｐ参照）。なお、長い目で見れば、各フローのキュー１１に付与されるクレジットの総量は、同じである。
【００７６】
そこで、実施例に係る通信装置では、キュー管理部１が、スケジューラ部２にキュー１１の蓄積量の変化を通知することにより、蓄積量の変化に応じてクレジットの付与順序を調整する。
【００７７】
（第１実施例）
図８は、第１実施例の出力処理部９１３の機能構成を示す構成図である。図８において、図４と共通する構成については、同一の符号を付し、その説明を省略する。
【００７８】
出力処理部９１３は、キュー管理部１及びスケジューラ部２を有する。キュー管理部１は、分配部（通知部）１０と、複数のキュー１１と、読出処理部１２と、蓄積量計数部１３０ａと、クレジット計数部１３１とを有する。一方、スケジューラ部２は、仮想蓄積量計数部２１０、蓄積量フラグ管理部２１１、及びクレジット付与部２０ａを有する。
【００７９】
蓄積量計数部１３０ａは、比較例における蓄積量計数部１３０と同様の機能を有するだけでなく、スケジューラ部２に蓄積量の変化を通知する機能を有する。より具体的には、蓄積量計数部１３０ａは、読出処理部１２からのパケットの読み出しにより、何れかのキュー１１が空、つまり蓄積量が０になったことを契機として、その旨を、蓄積量フラグＱ＿ｅｍｐｔｙにより蓄積量フラグ管理部２１１に通知する。
【００８０】
蓄積量フラグ管理部２１１は、フロー＃０〜＃Ｎごと、つまりキュー１１ごとに設けられた蓄積量フラグＱ＿ｅｍｐｔｙを管理する。蓄積量フラグＱ＿ｅｍｐｔｙは、キュー１１の蓄積量が０（空）である場合、「ｔｒｕｅ」（真）を示し、そうでない場合、「ｆａｌｓｅ」（偽）を示す。蓄積量フラグ管理部２１１は、蓄積量計数部１３０ａの上記の通知に応じて、該当するキュー１１の蓄積量フラグＱ＿ｅｍｐｔｙを更新する。蓄積量フラグＱ＿ｅｍｐｔｙを更新は、パケットの読み出し時の蓄積量計数部１３０ａの通知、及び、パケットの到着時の分配部１０の通知に応じて行われる。後者の通知があると、蓄積量フラグ管理部２１１は、蓄積量フラグＱ＿ｅｍｐｔｙを「ｆａｌｓｅ」に更新する。
【００８１】
クレジット付与部２０ａは、比較例におけるクレジット付与部２０と同様に、キュー１１ごとの仮想蓄積量に従ってクレジットを与えるだけでなく、さらに、キュー１１ごとの優先度に基づく順序に従って、クレジットをそれぞれ与える。クレジット付与部２０ａは、蓄積量フラグＱ＿ｅｍｐｔｙに応じて、クレジット付与の優先度を調整する。以下に、動作例を挙げて説明する。
【００８２】
図９には、蓄積量フラグＱ＿ｅｍｐｔｙに応じた優先度の調整動作の一例が示されている。図９の紙面左側には、優先度の調整前の状態（状態（ａ））が示され、図９の紙面右側には、優先度の調整後の状態（状態（ｂ））が示されている。なお、図９は、図８に示された構成のうち、蓄積量計数部１３０ａ、クレジット計数部１３１、仮想蓄積量計数部２１０、蓄積量フラグ管理部２１１、及びクレジット付与部２０ａを示す。
【００８３】
クレジット付与部２０ａは、フロー＃０〜＃Ｎごと、つまりキュー１１ごとにクレジット付与の優先度を管理するための高優先リスト２０１及び低優先リスト２０２を有する。クレジット付与部２０ａは、蓄積量フラグＱ＿ｅｍｐｔｙに応じて、各フロー＃０〜＃Ｎを高優先リスト２０１及び低優先リスト２０２の一方に登録する。クレジット付与部２０ａは、優先度が同一であるフロー＃０〜＃Ｎのキュー１１を、例えばラウンドロビン方式に従って公平に選択する。
【００８４】
状態（ａ）において、フロー＃０，＃１，＃２，＃Ｎの仮想蓄積量は、それぞれ、１０００１（Ｂｙｔｅ）、８０００（Ｂｙｔｅ）、−１００（Ｂｙｔｅ）、２００（Ｂｙｔｅ）とする。フロー＃０，＃１，＃Ｎは、通常の優先度である高優先リスト２０１に登録され、クレジット付与対象の選択において公平に扱われる。フロー＃２は、仮想蓄積量が負の値であるため、何れのリスト２０１，２０２にも登録されない。なお、登録状態は、丸印（「○」）により示されている。
【００８５】
また、フロー＃０の蓄積量は、１０００１（Ｂｙｔｅ）であり、クレジット付与部２０ａは、例えば、フロー＃０のキュー１１に、２５００（Ｂｙｔｅ）のクレジットを付与する。これにより、フロー＃０のクレジットカウンタ値は、２５００（Ｂｙｔｅ）となり、フロー＃０の仮想蓄積量は、１０００１（Ｂｙｔｅ）から７５０１（Ｂｙｔｅ）になる。
【００８６】
一方、状態（ｂ）において、フロー＃０のキュー１１から、１０００１（Ｂｙｔｅ）のパケット長のパケットが読み出されることにより、フロー＃０の蓄積量が、０（Ｂｙｔｅ）となり、フロー＃０のクレジットカウンタ値は、−７５００（Ｂｙｔｅ）となる。これにより、蓄積量計数部１３０ａは、フロー＃０のキュー１１が空であることを、蓄積量フラグ管理部２１１に通知する。通知は、例えば、１（Ｂｉｔ）のデータの形式（フロー＃０の蓄積量フラグＱ＿ｅｍｐｔｙ［０］＝ｔｒｕｅ）で行われる。
【００８７】
蓄積量フラグ管理部２１１は、蓄積量計数部１３０ａの通知に応じて、フロー＃０の蓄積量フラグＱ＿ｅｍｐｔｙ［０］を、「ｆａｌｓｅ」から「ｔｒｕｅ」に更新する。これに従い、クレジット付与部２０ａは、フロー＃０を低優先リスト２０２に登録し、フロー＃０の仮想蓄積量が７５０１（Ｂｙｔｅ）であるにも関わらず、クレジット付与を、他のフローの後回しにする。
【００８８】
図１０には、本例におけるクレジットの付与の順序が示されている。図１０は、順序ごとのフローＩＤに加えて、クレジットの付与による仮想蓄積量の変化も示す。なお、フロー＃１のキュー１１は、仮想蓄積量が負の値になるまで空にならないと仮定する。
【００８９】
フロー＃０のキュー１１は、順序「１」におけるクレジットの付与により、パケットが読み出されて空になるため、その後、フロー＃０のキュー１１へのクレジット付与は、空でないフロー＃１のキュー１１の後回しにされる。なお、フロー＃Ｎのキュー１１は、順序「３」におけるクレジットの付与により仮想蓄積量が負の値になるため、その後、クレジットを与えられない。
【００９０】
一方、図１１には、比較例におけるクレジットの付与の順序が示されている。フロー＃０のキュー１１は、順序「１」におけるクレジットの付与により、パケットが読み出されて空になる。しかし、スケジューラ部２は、フロー＃０のキュー１１が空になったことを知らないので、フロー＃０のキュー１１及びフロー＃１のキュー１１は、交互にクレジットが与えられる。
【００９１】
このように、スケジューラ部２は、蓄積量計数部１３０ａの通知に応じて、複数のキュー１１のうち、蓄積量が０になったキュー１１の優先度を低下させる。したがって、蓄積量が０になったキュー１１へのクレジットの付与は、他のキュー１１の後回しにされる。
【００９２】
次に、本実施例におけるキュー管理部１及びスケジューラ部２の動作を説明する。図１２は、パケットが読み出されたときのキュー管理部１の動作を示すフローチャートである。
【００９３】
読出処理部１２がフロー＃ｉ（ｉ：自然数）のキュー１１からパケットを読み出すと（ステップＳｔ１）、蓄積量計数部１３０ａは、フロー＃ｉの蓄積量から、読み出されたパケットのパケット長（ＰＫＴ長）を減算する（ステップＳｔ２）。次に、クレジット計数部１３１は、フロー＃ｉのクレジットカウンタ値から、読み出されたパケットのパケット長（ＰＫＴ長）を減算する（ステップＳｔ３）。なお、ステップＳｔ３の処理順序は、ステップＳｔ２の前であってもよい。
【００９４】
次に、蓄積量計数部１３０ａは、フロー＃ｉの蓄積量が０であるか否かを判定し（ステップＳｔ４）、フロー＃ｉの蓄積量が０である場合（ステップＳｔ４のＹｅｓ）、蓄積量フラグＱ＿ｅｍｐｔｙ［ｉ］が「ｔｒｕｅ」であることを、スケジューラ部２に通知する。一方、フロー＃ｉの蓄積量が０でない場合（ステップＳｔ４のＮｏ）、処理を終了する。このようにして、キュー管理部１は、パケットが読み出されたときの動作を行う。
【００９５】
また、図１３は、キュー管理部１から通知を受信したときのスケジューラ部２の動作を示すフローチャートである。蓄積量フラグ管理部２１１は、蓄積量計数部１３０ａから蓄積量フラグＱ＿ｅｍｐｔｙ［ｉ］の通知を受信すると（ステップＳｔ１１）、フロー＃ｉの蓄積量フラグＱ＿ｅｍｐｔｙ［ｉ］を更新する（ステップＳｔ１２）。このようにして、スケジューラ部２は、キュー管理部１から通知を受信したときの動作を行う。
【００９６】
また、図１４は、スケジューリング処理を行うときのスケジューラ部２の動作を示すフローチャートである。クレジット付与部２０ａは、フロー＃ｉのスケジューリング契機が到来すると、フロー＃ｉの蓄積量フラグＱ＿ｅｍｐｔｙ［ｉ］が「ｔｒｕｅ」（真）であるか否かを判定する（ステップＳｔ２１）。
【００９７】
フロー＃ｉの蓄積量フラグＱ＿ｅｍｐｔｙ［ｉ］が「ｔｒｕｅ」である場合（ステップＳｔ２１のＹｅｓ）、フロー＃ｉを低優先リスト２０２に登録する（ステップＳｔ２３）。一方、フロー＃ｉの蓄積量フラグＱ＿ｅｍｐｔｙ［ｉ］が「ｆａｌｓｅ」である場合（ステップＳｔ２１のＮｏ）、フロー＃ｉを高優先リスト２０１に登録する（ステップＳｔ２２）。このようにして、スケジューラ部２は、スケジューリング処理を行うときの動作を行う。
【００９８】
また、図１５は、パケットの到着通知を受信したときのスケジューラ部２の動作を示すフローチャートである。キュー管理部１にフロー＃ｉのパケットが到着すると、分配部１０から蓄積量フラグ管理部２１１に、当該パケットのパケット長が通知される（ステップＳｔ３１）。
【００９９】
次に、蓄積量フラグ管理部２１１は、フロー＃ｉの蓄積量フラグＱ＿ｅｍｐｔｙ［ｉ］を「ｆａｌｓｅ」に更新する（ステップＳｔ３２）。このようにして、スケジューラ部２は、パケットの到着通知を受信したときの動作を行う。
【０１００】
また、図１６は、第１実施例の動作の一例が示されている。図１６は、図８に示された構成において、蓄積量計数部１３０ａの蓄積量、クレジット計数部１３１のクレジット、仮想蓄積量計数部２１０の仮想蓄積量、及び蓄積量フラグ管理部２１１の蓄積量フラグＱ＿ｅｍｐｔｙを、時系列（時刻ｔ０〜ｔ５）に示している。
【０１０１】
時刻ｔ０において、クレジット付与部２０ａは、フロー＃０のキュー１１にクレジットを与えることにより、フロー＃０のクレジットカウンタ値は、２５００（Ｂｙｔｅ）となり、フロー＃０の仮想蓄積量は、７５０１（Ｂｙｔｅ）となる。このとき、フロー＃０の蓄積量は、１０００１（Ｂｙｔｅ）であり、フロー＃１の蓄積量は、５０００（Ｂｙｔｅ）である。また、スロー＃１のクレジットカウンタ値は、−５０００（Ｂｙｔｅ）である。なお、フロー＃０の蓄積量フラグＱ＿ｅｍｐｔｙ［０］及びフロー＃１の蓄積量フラグＱ＿ｅｍｐｔｙ［１］は、「ｆａｌｓｅ」を示す。
【０１０２】
次に、時刻ｔ１において、１０００１（Ｂｙｔｅ）のパケットが、フロー＃０のキュー１１から読み出される。これにより、フロー＃０の蓄積量は、０（Ｂｙｔｅ）になり、フロー＃０のクレジットカウント値は、−７５０１（Ｂｙｔｅ）となる。
【０１０３】
次に、時刻ｔ２において、蓄積量計数部１３０ａは、蓄積量フラグ管理部２１１に、フロー＃０の蓄積量フラグＱ＿ｅｍｐｔｙ［０］が「ｔｒｕｅ」であることを通知する。これにより、蓄積量フラグ管理部２１１において、蓄積量フラグＱ＿ｅｍｐｔｙ［０］が「ｔｒｕｅ」に更新される。このため、クレジット付与部２０ａは、フロー＃０を低優先リスト２０２に登録し、フロー＃０のキュー１１へのクレジット付与を、フロー＃１のキュー１１の後回しにする。
【０１０４】
次に、時刻ｔ３において、クレジット付与部２０ａは、フロー＃１のキュー１１にクレジットを与えることにより、フロー＃１のクレジットカウンタ値は、−２５００（Ｂｙｔｅ）となり、フロー＃１の仮想蓄積量は、２５００（Ｂｙｔｅ）となる。なお、フロー＃１のクレジットカウンタ値が負であるため、フロー＃１のキュー１１に蓄積されたパケットは読み出されない。
【０１０５】
次に、時刻ｔ４において、クレジット付与部２０ａは、フロー＃１のキュー１１にクレジットを与えることにより、フロー＃１のクレジットカウンタ値は、０（Ｂｙｔｅ）となり、フロー＃１の仮想蓄積量は、０（Ｂｙｔｅ）となる。
【０１０６】
次に、時刻ｔ５において、１０００１（Ｂｙｔｅ）のフロー＃０のパケットが到着すると、分配部１０は、仮想蓄積量計数部２１０及び蓄積量フラグ管理部２１１に、到着したパケットのフローＩＤ及びパケット長を通知する。これにより、フロー＃０の仮想蓄積量は、１７５０２（Ｂｙｔｅ）となり、フロー＃０の蓄積量フラグＱ＿ｅｍｐｔｙ［０］は、「ｆａｌｓｅ」に更新される。
【０１０７】
クレジット付与部２０ａは、フロー＃０の蓄積量フラグＱ＿ｅｍｐｔｙ［０］が「ｆａｌｓｅ」となったことにより、フロー＃０を高優先リスト２０１に再登録し、フロー＃０のキュー１１へのクレジット付与を、フロー＃１のキュー１１と公平に行う。このように、スケジューラ部２は、分配部１０の通知に応じて、複数のキュー１１のうち、優先度を低下させたキュー１１の優先度を低下前の値に戻す。したがって、キュー１１の優先度は、即時かつ自律的に調整前の値に戻される。
【０１０８】
図１７には、実施例におけるパケットの入出力タイミング及びクレジットの付与順序の例を示されている。図１７において、符号Ｐ５は、キュー管理部１に到着したフローＡ〜Ｚ（Ａ〜Ｚ：フローＩＤ）のパケットのタイミングを示し、符号Ｐ６は、キュー管理部１からポートに出力されたパケットのタイミングを示す。なお、各フローＡ〜Ｚは、図７を参照して述べたとおりである。
【０１０９】
符号Ｐ７は、本実施例におけるクレジットの付与順序を示す。また、符号Ｐ８は、比較例におけるクレジットの付与順序を示し、図７の符号Ｐ３により示され付与順序と同一である。付与順序の表記については、図７を参照して述べたとおりである。
【０１１０】
実施例の付与順序Ｐ７において、順序に付記された「（空）」は、該当フローのキュー１１が空、つまり蓄積量が０であることを示す。実施例の付与順序Ｐ７において、フローＡ及びフローＢの２〜５回目のクレジットの付与（図６参照）は、上述した蓄積量フラグＱ＿ｅｍｐｔｙの通知により、比較例の付与順序Ｐ８より遅れている（矢印Ｒ１参照）。つまり、フローＡ及びフローＢの２〜５回目のクレジットの付与は、後回しにされている。このため、フローＺのキュー１１へのクレジットの付与の遅延が解消され（矢印Ｒ２参照）、フローＺのショートパケットの遅延も解消される（符号Ｐ６参照）。
【０１１１】
なお、パケットの到着に先立つ余分なクレジットの付与、つまり５回目の付与だけではなく、２〜４回目の付与も後回しにされている。しかし、クレジットは、パケットが到着するまでにキュー１１に与えられればよく、また、上述したように、パケットの到着時、分配部１０の通知によって、該当するフロー１１の優先度は調整前の値に戻されるので、問題を生ずることはない。
【０１１２】
このように、本実施例において、蓄積量計数部１３０ａは、スケジューラ部２に、蓄積量が０になったことを通知する。スケジューラ部２は、蓄積量計数部の当該通知に応じて、複数のキュー１１のうち、蓄積量が０になったキューの優先度を低下させる。
【０１１３】
したがって、本実施例によると、スケジューラ部２は、蓄積量が０になったことを、自ら読み出すことなく、イベントドリブンにより通知される。このため、スケジューラ部２は、通知に応じて、速やかに当該キュー１１へのクレジット付与を、他のキュー１１の後回しにすることができる。よって、蓄積量が０（Ｂｙｔｅ）ではないキュー１１に優先的にクレジットが与えられ、読出処理部１５により読み出されるまでの該キュー１１のパケットの待機時間が低減されるので、読み出しの遅延が低減される。
【０１１４】
また、スケジューラ部２は、キュー１１ごとの優先度に応じて順序を調整しつつ、重み付けラウンドロビン方式に従って、各フロー＃０〜＃Ｎの重み値の比に基づいて各キュー１１にクレジットを与えてもよい。
【０１１５】
図１８には、比較例における重み付けラウンドロビン方式の動作の一例が示されている。本比較例では、図４に示される構成に加え、フロー＃０〜＃Ｎごとの重み値を管理する重み値管理部２１２が設けられている。重み値管理部２１２は、ネットワーク管理装置などにより重み値が設定される。図１８は、時系列（時刻ｔ０〜ｔ５）に従って、仮想蓄積量計数部２１０の仮想蓄積量及び重み値管理部２１２の重み値を、フロー＃０〜＃２ごとに示す。
【０１１６】
初期状態において、フロー＃０，＃１，＃２の仮想蓄積量を、それぞれ、１００００（Ｂｙｔｅ），８０００（Ｂｙｔｅ），３０００（Ｂｙｔｅ）とする。また、フロー＃０，＃１，＃２の重み値を、それぞれ、３，２，１とする。
【０１１７】
時刻ｔ０において、クレジット付与部２０は、フロー＃０のキュー１１にクレジットを与える。これにより、仮想蓄積量計数部２１０は、フロー＃０の仮想蓄積量を、１００００（Ｂｙｔｅ）から７５００（Ｂｙｔｅ）に更新する。また、重み値管理部２１２は、フロー＃０の重み値を、３から２に更新する。
【０１１８】
時刻ｔ１，ｔ２においても、クレジット付与部２０は、フロー＃０のキュー１１にクレジットを与える。これにより、仮想蓄積量計数部２１０は、フロー＃０の仮想蓄積量を、７５００（Ｂｙｔｅ）から２５００（Ｂｙｔｅ）に更新する。また、重み値管理部２１２は、フロー＃０の重み値を、２から０に更新する。
【０１１９】
ここで、クレジット付与部２０は、フロー＃０の重み値の初期値と同じ回数（３回）だけ、フロー＃０のキュー１１にクレジットを与えたので、フロー＃０の仮想蓄積量が０（Ｂｙｔｅ）より大きいが、クレジットの付与対象をフロー＃１のキュー１１に変更する。
【０１２０】
次に、時刻ｔ３，ｔ４において、クレジット付与部２０は、フロー＃１のキュー１１にクレジットを与える。これにより、仮想蓄積量計数部２１０は、フロー＃１の仮想蓄積量を、８０００（Ｂｙｔｅ）から３０００（Ｂｙｔｅ）に更新する。また、重み値管理部２１２は、フロー＃１の重み値を、２から０に更新する。
【０１２１】
ここで、クレジット付与部２０は、フロー＃１の重み値の初期値と同じ回数（２回）だけ、フロー＃１のキュー１１にクレジットを与えたので、フロー＃１の仮想蓄積量＞０であるにも関わらず、クレジットの付与対象をフロー＃２のキュー１１に変更する。
【０１２２】
次に、時刻ｔ５において、クレジット付与部２０は、フロー＃２のキュー１１にクレジットを与える。これにより、仮想蓄積量計数部２１０は、フロー＃２の仮想蓄積量を、３０００（Ｂｙｔｅ）から５００（Ｂｙｔｅ）に更新する。また、重み値管理部２１２は、フロー＃２の重み値を、１から０に更新する。
【０１２３】
これにより、クレジット付与部２は、フロー＃２の重み値の初期値と同じ回数（１回）だけ、フロー＃２のキュー１１にクレジットを与えたので、フロー＃２の仮想蓄積量が０（Ｂｙｔｅ）より大きいが、スケジューリングの１周期分のクレジットの付与を終了する。
【０１２４】
一方、図１９には、蓄積量フラグＱ＿ｅｍｐｔｙを用いた重み付けラウンドロビン方式の動作の一例が示されている。本例では、図８に示される構成に加え、比較例と同様の重み値管理部２１２が設けられている。図１９は、時系列（時刻ｔ０〜ｔ５）に従って、仮想蓄積量計数部２１０の仮想蓄積量、重み値管理部２１２の重み値、及び蓄積量フラグ管理部２１１の蓄積量フラグＱ＿ｅｍｐｔｙを示す。
【０１２５】
初期状態におけるフロー＃０，＃１，＃２の仮想蓄積量及び重み値は、上述した比較例と同一とする。また、初期状態におけるフロー＃０，＃１，＃２の蓄積量フラグＱ＿ｅｍｐｔｙを、全て「ｆａｌｓｅ」とする。
【０１２６】
時刻ｔ０において、クレジット付与部２０ａは、フロー＃０のキュー１１にクレジットを与える。これにより、仮想蓄積量計数部２１０は、フロー＃０の仮想蓄積量を、１００００（Ｂｙｔｅ）から７５００（Ｂｙｔｅ）に更新する。また、重み値管理部２１２は、フロー＃０の重み値を、３から２に更新する。このとき、フロー＃０の蓄積量は、０（Ｂｙｔｅ）になったとする。
【０１２７】
次に、時刻ｔ１において、蓄積量フラグ管理部２１１は、蓄積量計数部１３０ａの通知に応じて、フロー＃０の蓄積量フラグＱ＿ｅｍｐｔｙ［０］を「ｔｒｕｅ」に更新する。これにより、クレジット付与部２０ａは、フロー＃０を低優先リスト２０２に登録する。
【０１２８】
クレジット付与部２０ａは、優先度を低下させたフロー＃０のキュー１１に対するクレジットの付与を、比較例と異なり、フロー＃０の重み値が２（≠０）であるにも関わらず、他のキュー＃１、＃２の後回しにする。したがって、クレジット付与部２０ａは、クレジットの付与対象をフロー＃１のキュー１１に変更する。
【０１２９】
次に、時刻ｔ１，ｔ２において、クレジット付与部２０ａは、フロー＃１のキュー１１にクレジットを与える。これにより、仮想蓄積量計数部２１０は、フロー＃１の仮想蓄積量を、８０００（Ｂｙｔｅ）から３０００（Ｂｙｔｅ）に更新する。また、重み値管理部２１２は、フロー＃１の重み値を、２から０に更新する。
【０１３０】
ここで、クレジット付与部２０ａは、フロー＃１の重み値の初期値と同じ回数（２回）だけ、フロー＃１のキュー１１にクレジットを与えたので、フロー＃１の仮想蓄積量が０（Ｂｙｔｅ）より大きいが、クレジットの付与対象をフロー＃２のキュー１１に変更する。
【０１３１】
次に、時刻ｔ３において、クレジット付与部２０ａは、フロー＃２のキュー１１にクレジットを与える。これにより、仮想蓄積量計数部２１０は、フロー＃２の仮想蓄積量を、３０００（Ｂｙｔｅ）から５００（Ｂｙｔｅ）に更新する。また、重み値管理部２１２は、フロー＃２の重み値を、１から０に更新する。
【０１３２】
ここで、クレジット付与部２０ａは、フロー＃２の重み値の初期値と同じ回数（１回）だけ、フロー＃２のキュー１１にクレジットを与えたので、フロー＃２の仮想蓄積量が０（Ｂｙｔｅ）より大きいが、クレジットの付与対象を再びフロー＃０のキュー１１に変更する。
【０１３３】
次に、時刻ｔ４，ｔ５において、クレジット付与部２０ａは、フロー＃０のキュー１１にクレジットを与える。これにより、仮想蓄積量計数部２１０は、フロー＃０の仮想蓄積量を、７５００（Ｂｙｔｅ）から２５００（Ｂｙｔｅ）に更新する。また、重み値管理部２１２は、フロー＃０の重み値を、２から０に更新する。つまり、フロー＃０のキュー１１は、蓄積量フラグＱ＿ｅｍｐｔｙ［０］が「ｔｒｕｅ」であるため、蓄積量フラグＱ＿ｅｍｐｔｙが「ｆａｌｓｅ」である他のフロー＃１，＃２の後回しとなる。
【０１３４】
また、図２０は、スケジューリング処理を行うときのスケジューラ部２の動作を示すフローチャートである。クレジット付与部２０ａは、スケジューリングの候補、つまり、クレジットの付与対象の候補として、フロー＃ｉを選択する（ステップＳｔ４１）。
【０１３５】
次に、クレジット付与部２０ａは、フロー＃ｉの重み値［ｉ］が０であるか否かを判定する（ステップＳｔ４２）。フロー＃ｉの重み値［ｉ］が０ではない場合（ステップＳｔ４２のＹｅｓ）、クレジット付与部２０ａは、フロー＃ｉの蓄積量フラグＱ＿ｅｍｐｔｙ［ｉ］が「ｔｒｕｅ」であるか否かを判定する（ステップＳｔ４３）。なお、ステップＳｔ４３の判定処理の順序は、ステップＳｔ４２の判定処理の前であってもよい。
【０１３６】
クレジット付与部２０ａは、フロー＃ｉの蓄積量フラグＱ＿ｅｍｐｔｙ［ｉ］が「ｆａｌｓｅ」である場合（ステップＳｔ４３のＮｏ）、フロー＃ｉのスケジューリングを決定する（ステップＳｔ４４）。つまり、クレジット付与部２０ａは、フロー＃ｉのキュー１１にクレジットを与える。
【０１３７】
一方、フロー＃ｉの重み値［ｉ］が０である場合（ステップＳｔ４２のＮｏ）、またはフロー＃ｉの蓄積量フラグＱ＿ｅｍｐｔｙ［０］が「ｔｒｕｅ」である場合（ステップＳｔ４３のＹｅｓ）、スケジューリングを決定したか否かを判定する（ステップＳｔ４５）。クレジット付与部２０ａは、スケジューリングが決定された場合（ステップＳｔ４５のＹｅｓ）、処理を終了する。また、クレジット付与部２０ａは、スケジューリングが決定されていない場合（ステップＳｔ４５のＮｏ）、フローＩＤであるｉを１つ増加させて、再びステップＳｔ４１から処理を行う。
【０１３８】
一方、クレジット付与部２０ａは、ステップＳｔ４４の処理後も、同様にステップＳｔ４５の判定処理を行う。このようにして、スケジューラ部２は、スケジューリング処理を行う。
【０１３９】
このように、本例において、クレジット付与部２０ａは、重み付けラウンドロビン方式に従い、複数のキュー１１にクレジットを与える。より具体的には、クレジット付与部２０ａは、スケジューリングの１周期において、各フローの重み値と同じ回数分だけ、クレジットを与える。
【０１４０】
また、クレジット付与部２０ａは、複数のキュー１１のうち、優先度を低下させたキュー１１に対するクレジットの付与を、該当するフロー（またはキュー１１）の重み値に関わらず、他のキュー１１の後回しにする。このため、本例によると、パケットの読み出しの遅延を低減するだけでなく、重み付けラウンドロビン方式に従い、各フローの重み値の比に基づいて各キュー１１にクレジットを付与することができる。
【０１４１】
（第２実施例）
第１実施例では、キュー１１が空になったことを契機として、該キュー１１の優先度を低下させたが、キュー１１の蓄積量が更新されたとき、更新後の蓄積量に基づいて該キュー１１の優先度を段階的に調整してもよい。
【０１４２】
図２１には、第２実施例の動作の一例が示されている。図２１に示されるように、本実施例において、スケジューラ部２は、蓄積量フラグ管理部２１１に代えて、蓄積レベル管理部２１３が設けられている。また、蓄積量計数部１３０ａは、キュー１１からパケットが読み出されることにより蓄積量が変化したとき、変化後の蓄積量Ｑ＿ｌｅｎｇｔｈを蓄積レベル管理部２１３に通知する。
【０１４３】
蓄積レベル管理部２１３は、蓄積量Ｑ＿ｌｅｎｇｔｈに応じ、蓄積量のレベルＱ＿ｌｅｎ＿ＬＶ（以下、「蓄積レベル」と表記）を、例えば、「Ｈｉｇｈ」、「Ｍｉｄｄｌｅ」、及び「Ｌｏｗ」の三段階に分けて管理する。蓄積レベル管理部２１３は、例えば、蓄積量Ｑ＿ｌｅｎｇｔｈが２５０１（Ｂｙｔｅ）以上である場合、「Ｈｉｇｈ」レベルと判定し、１〜２５００（Ｂｙｔｅ）以上である場合、「Ｍｉｄｄｌｅ」レベルと判定する。さらに、蓄積レベル管理部２１３は、蓄積量Ｑ＿ｌｅｎｇｔｈが０（Ｂｙｔｅ）である場合、「Ｌｏｗ」レベルと判定する。
【０１４４】
また、クレジット付与部２０ａは、「Ｈｉｇｈ」レベル、「Ｍｉｄｄｌｅ」レベル、及び「Ｌｏｗ」レベルにそれぞれ対応する高優先リスト、中優先リスト、及び低優先リストを有する。クレジット付与部２０ａは、各フロー＃０〜＃Ｎを、上記の３つのリストのうち、各蓄積レベルＱ＿ｌｅｎ＿ＬＶに応じたリストに登録する。
【０１４５】
図２１は、時系列（時刻ｔ０〜ｔ５）に従って、蓄積量計数部１３０ａの蓄積量、クレジット計数部１３１のクレジットカウンタ値、仮想蓄積量計数部２１０の仮想蓄積量、及び蓄積レベル管理部２１３の蓄積レベルＱ＿ｌｅｎ＿ＬＶを示す。
【０１４６】
時刻ｔ０において、クレジット付与部２０ａは、フロー＃０のキュー１１にクレジットを与える。これにより、フロー＃０のクレジットカウンタ値は、２５００（Ｂｙｔｅ）となる。
【０１４７】
また、フロー＃１のクレジットカウンタ値は、−５０００（Ｂｙｔｅ）であり、フロー＃０の蓄積量及びフロー＃１の蓄積量は、それぞれ、１０００１（Ｂｙｔｅ）及び５０００（Ｂｙｔｅ）である。フロー＃０の仮想蓄積量及びフロー＃１の仮想蓄積量は、それぞれ、７５０１（Ｂｙｔｅ）及び５０００（Ｂｙｔｅ）である。フロー＃０の蓄積レベル及びフロー＃１の蓄積レベルＱ＿ｌｅｎ＿ＬＶは、上述した基準に従い、ともに「Ｈｉｇｈ」レベルである。
【０１４８】
次に、時刻ｔ１において、フロー＃０のキュー１１から１０００１（Ｂｙｔｅ）のパケットが読み出される。これにより、フロー＃０のクレジットカウンタ値は、−７５０１（Ｂｙｔｅ）となり、フロー＃０の蓄積量は、０（Ｂｙｔｅ）となる。
【０１４９】
次に、時刻ｔ２において、蓄積量計数部１３０ａは、フロー＃０の変化後の蓄積量Ｑ＿ｌｅｎｇｔｈ［０］（＝０（Ｂｙｔｅ））を蓄積レベル管理部２１に通知する。これにより、蓄積レベル管理部２１３は、上述した基準に従い、フロー＃０の蓄積レベルＱ＿ｌｅｎ＿ＬＶを「Ｌｏｗ」に更新する。このため、フロー＃０は、低優先リストに登録され、クレジット付与が、フロー＃１のキューの後回しとされる。
【０１５０】
次に、時刻ｔ３において、クレジット付与部２０ａは、フロー＃１のキュー１１にクレジットを与える。これにより、フロー＃１のクレジットカウンタ値は、−２５００（Ｂｙｔｅ）となる。また、フロー＃１の仮想蓄積量は、２５００（Ｂｙｔｅ）となる。
【０１５１】
次に、時刻ｔ４において、クレジット付与部２０ａは、フロー＃１のキュー１１にクレジットを与える。これにより、フロー＃１のクレジットカウンタ値は、０（Ｂｙｔｅ）となる。また、フロー＃１の仮想蓄積量は、０（Ｂｙｔｅ）となる。
【０１５２】
次に、時刻ｔ５において、１０００１（Ｂｙｔｅ）のフロー＃０のパケットが、キュー管理部１に到着する。これにより、フロー＃０の蓄積量は、１０００１（Ｂｙｔｅ）となる。
【０１５３】
また、分配部１０は、蓄積レベル管理部２１３に、到着したパケットのパケット長（１０００１（Ｂｙｔｅ））を通知する。また、蓄積量計数部１３０ａは、フロー＃０の変化後の蓄積量Ｑ＿ｌｅｎｇｔｈ［０］（＝１０００１（Ｂｙｔｅ））を蓄積レベル管理部２１３に通知する。これにより、蓄積レベル管理部２１３は、上述した基準に従い、フロー＃０の蓄積レベルＱ＿ｌｅｎ＿ＬＶを「Ｈｉｇｈ」に更新する。クレジット付与部２０ａは、フロー＃０の蓄積レベルＱ＿ｌｅｎ＿ＬＶが「Ｈｉｇｈ」であるため、フロー＃０を高優先リストに登録する。
【０１５４】
次に、本実施例におけるキュー管理部１及びスケジューラ部２の動作を説明する。図２２は、パケットが読み出されたときのキュー管理部１の動作を示すフローチャートである。
【０１５５】
読出処理部１２がフロー＃ｉのキュー１１からパケットを読み出すと（ステップＳｔ５１）、蓄積量計数部１３０ａは、フロー＃ｉの蓄積量から、読み出されたパケットのパケット長（ＰＫＴ長）を減算する（ステップＳｔ５２）。次に、クレジット計数部１３１は、フロー＃ｉのクレジットカウンタ値から、読み出されたパケットのパケット長（ＰＫＴ長）を減算する（ステップＳｔ５３）。なお、ステップＳｔ５３の処理順序は、ステップＳｔ５２の前であってもよい。
【０１５６】
次に、蓄積量計数部１３０ａは、変化後のフロー＃ｉの蓄積量Ｑ＿ｌｅｎｇｔｈをスケジューラ部２に通知する（ステップＳｔ５４）。このようにして、キュー管理部１は、パケットが読み出されたときの動作を行う。
【０１５７】
また、図２３は、キュー管理部１から通知を受信したときのスケジューラ部２の動作を示すフローチャートである。蓄積量計数部１３０ａから変化後の蓄積量Ｑ＿ｌｅｎｇｔｈ［ｉ］を受信すると（ステップＳｔ７１）、蓄積レベル管理部２１３は、上述した基準に従い、フロー＃ｉの蓄積レベルＱ＿ｌｅｎ＿ＬＶ［ｉ］を更新する（ステップＳｔ７２）。なお、パケットが到着した場合、蓄積レベル管理部２１３は、分配部１０から、到着したフロー＃ｉのパケットのパケット長を受信し、蓄積量計数部１３０ａから、変化後の蓄積量Ｑ＿ｌｅｎｇｔｈ［ｉ］を受信する。このようにして、スケジューラ部２は、キュー管理部１から通知を受信したときの動作を行う。
【０１５８】
図２４は、スケジューリング処理を行うときのスケジューラ部２の動作を示すフローチャートである。クレジット付与部２０ａは、フロー＃ｉのスケジューリング契機が到来すると、フロー＃ｉの蓄積レベルＱ＿ｌｅｎ＿ＬＶ［ｉ］を判定する（ステップＳｔ６１）。
【０１５９】
クレジット付与部２０ａは、蓄積レベルＱ＿ｌｅｎ＿ＬＶ［ｉ］が「Ｈｉｇｈ」であるとき、フロー＃ｉを高優先リストに登録する（ステップＳｔ６２）。また、クレジット付与部２０ａは、蓄積レベルＱ＿ｌｅｎ＿ＬＶ［ｉ］が「Ｍｉｄｄｌｅ」であるとき、フロー＃ｉを中優先リストに登録する（ステップＳｔ６３）。また、クレジット付与部２０ａは、蓄積レベルＱ＿ｌｅｎ＿ＬＶ［ｉ］が「Ｌｏｗ」であるとき、フロー＃ｉを低優先リストに登録する（ステップＳｔ６４）。このようにして、スケジューラ部２は、スケジューリング処理を行うときの動作を行う。
【０１６０】
このように、本実施例において、蓄積量計数部１３０ａは、スケジューラ部２に変化後の蓄積量Ｑ＿ｌｅｎｇｔｈを通知する。スケジューラ部２は、蓄積量計数部１３０ａから通知された変化後の蓄積量Ｑ＿ｌｅｎｇｔｈに応じて、複数のキュー１１のうち、蓄積量Ｑ＿ｌｅｎｇｔｈが変化したキューの優先度を調整する。
【０１６１】
より具体的には、蓄積レベル管理部２１３は、蓄積量Ｑ＿ｌｅｎｇｔｈを所定の閾値と比較することにより、蓄積レベルＱ＿ｌｅｎ＿ＬＶを三段階（「Ｈｉｇｈ」、「Ｍｉｄｄｌｅ」、及び「Ｌｏｗ」）で判定する。そして、クレジット付与部２０ａは、蓄積レベルＱ＿ｌｅｎ＿ＬＶに基づいて、該当するフロー＃０〜＃Ｎの優先度を、３つの優先度リストを用いて段階的に調整する。
【０１６２】
したがって、本実施例によれば、キュー１１ごとの蓄積量に応じて、クレジット付与の順序を柔軟に制御することが可能となる。なお、本実施例では、蓄積レベルＱ＿ｌｅｎ＿ＬＶ及び優先度リストを三段階に分けた例を示したが、これに限定されず、四段階以上であってもよい。
【０１６３】
（第３実施例）
上述した実施例において、クレジット付与の優先度は、蓄積量の変化に応じて調整されるが、蓄積量だけでなく、クレジットカウンタ値の変化に応じて調整されてもよい。上述したように、読出処理部１５は、クレジットカウンタ値が０より大きいことを条件として、パケットを読み出す。このため、クレジットカウンタ値が０より大きいキュー１１へのクレジット付与を、そうでないキュー１１の後回しにすることにより、フロー間、つまりキュー１１間の公平性を向上することができる。
【０１６４】
図２５は、第３実施例の出力処理部９１３の機能構成を示す構成図である。図２５において、図８と共通する構成については、同一の符号を付し、その説明を省略する。
【０１６５】
出力処理部９１３は、キュー管理部１及びスケジューラ部２を有する。キュー管理部１は、分配部１０と、複数のキュー１１と、読出処理部１２と、蓄積量計数部１３０ａと、クレジット計数部（読出許容量計数部）１３１ａとを有する。一方、スケジューラ部２は、仮想蓄積量計数部２１０、蓄積量フラグ管理部２１１、クレジットフラグ管理部２１４、及びクレジット付与部２０ｂを有する。
【０１６６】
クレジット計数部１３１ａは、比較例におけるクレジット計数部１３１と同様の機能を有するだけでなく、スケジューラ部２にクレジットの変化を通知する機能を有する。より具体的には、クレジット計数部１３１ａは、読出処理部１２からパケットが読み出されたとき、該当するフロー＃０〜＃Ｎのクレジットカウンタ値から該パケット長を減算し、クレジットフラグＣｒｅｄｉｔ＿ｅｘｔをクレジットフラグ管理部２１４に通知する。
【０１６７】
クレジットフラグ管理部２１４は、フロー＃０〜＃Ｎごと、つまりキュー１１ごとに設けられたクレジットフラグＣｒｅｄｉｔ＿ｅｘｔを管理する。クレジットフラグＣｒｅｄｉｔ＿ｅｘｔは、クレジットカウンタ値が０より大きい場合、「ｔｒｕｅ」（真）を示し、そうでない場合、「ｆａｌｓｅ」（偽）を示す。クレジットフラグ管理部２１４は、クレジット計数部１３１ａの上記の通知に応じて、該当するキュー１１のクレジットフラグＣｒｅｄｉｔ＿ｅｘｔを更新する。
【０１６８】
クレジット付与部２０ｂは、上記のクレジット付与部２０ａと同様に、キュー１１ごとの優先度に基づく順序に従って、クレジットをそれぞれ与える。クレジット付与部２０ｂは、蓄積量フラグＱ＿ｅｍｐｔｙに加え、クレジットフラグＣｒｅｄｉｔ＿ｅｘｔに応じて、クレジット付与の優先度を調整する。以下に、動作例を挙げて説明する。
【０１６９】
図２６Ａ及び図２６Ｂには、第３実施例の動作の一例が示されている。図２６Ａ及び図２６Ｂは、図２５に示された構成において、蓄積量計数部１３０ａの蓄積量、クレジット計数部１３１ａのクレジット、仮想蓄積量計数部２１０の仮想蓄積量、クレジットフラグ管理部２１４のクレジットフラグＣｒｅｄｉｔ＿ｅｘｔを、時系列（時刻ｔ０〜ｔ７）に示している。
【０１７０】
時刻ｔ０において、フロー＃０及びフロー＃１の各蓄積量は、２１００（Ｂｙｔｅ）及び５０００（Ｂｙｔｅ）であり、フロー＃０及びフロー＃１の各クレジットは、−１０００（Ｂｙｔｅ）及び−５１００（Ｂｙｔｅ）である。また、フロー＃０及びフロー＃１の各仮想蓄積量は、それぞれ、５０００（Ｂｙｔｅ）及び５１００（Ｂｙｔｅ）である。フロー＃０及びフロー＃１の各クレジットフラグＣｒｅｄｉｔ＿ｅｘｔは、ともにクレジットカウンタ値が負の値であるために、「ｆａｌｓｅ」である。
【０１７１】
次に、時刻ｔ１において、クレジット付与部２０ｂは、フロー＃０のキュー１１にクレジットを与えることにより、フロー＃０のクレジットカウンタ値は、１５００（Ｂｙｔｅ）となり、フロー＃０の仮想蓄積量は、２５００（Ｂｙｔｅ）となる。
【０１７２】
次に、時刻ｔ２において、１００（Ｂｙｔｅ）のパケットが、フロー＃０のキュー１１から読み出される。これにより、フロー＃０の蓄積量は、２０００（Ｂｙｔｅ）になり、フロー＃０のクレジットカウント値は、１４００（Ｂｙｔｅ）となる。
【０１７３】
次に、時刻ｔ３において、クレジット計数部１３１ａは、クレジットフラグ管理部２１４に、フロー＃０のクレジットフラグＣｒｅｄｉｔ＿ｅｘｔ［０］が「ｔｒｕｅ」であることを通知する。これにより、クレジットフラグ管理部２１４は、クレジットフラグＣｒｅｄｉｔ＿ｅｘｔ［０］を「ｔｒｕｅ」に更新する。このため、クレジット付与部２０ｂは、フロー＃０の優先度を低下させ、フロー＃０を低優先リストに登録する。したがって、フロー＃０のキュー１１へのクレジットの付与は、フロー＃１のキュー１１の後回しとなる。
【０１７４】
次に、時刻ｔ４において、クレジット付与部２０ｂは、フロー＃１のキュー１１にクレジットを与えることにより、フロー＃１のクレジットカウンタ値は、−２６００（Ｂｙｔｅ）となり、フロー＃１の仮想蓄積量は、２６００（Ｂｙｔｅ）となる。
【０１７５】
次に、時刻ｔ５において、クレジット付与部２０ｂは、フロー＃１のキュー１１にクレジットを与えることにより、フロー＃１のクレジットカウンタ値は、−１００（Ｂｙｔｅ）となり、フロー＃１の仮想蓄積量は、１００（Ｂｙｔｅ）となる。
【０１７６】
次に、時刻ｔ６において、１５００（Ｂｙｔｅ）のパケットが、フロー＃０のキュー１１から読み出される。これにより、フロー＃０の蓄積量は、５００（Ｂｙｔｅ）になり、フロー＃０のクレジットカウント値は、−１００（Ｂｙｔｅ）となる。
【０１７７】
次に、時刻ｔ７において、クレジット計数部１３１ａは、クレジットフラグ管理部２１４に、フロー＃０のクレジットフラグＣｒｅｄｉｔ＿ｅｘｔ［０］が「ｆａｌｓｅ」であることを通知する。これにより、クレジットフラグ管理部２１４は、クレジットフラグＣｒｅｄｉｔ＿ｅｘｔ［０］を「ｆａｌｓｅ」に更新する。
【０１７８】
次に、本実施例におけるキュー管理部１及びスケジューラ部２の動作を説明する。図２７は、パケットが読み出されたときのキュー管理部１の動作を示すフローチャートである。
【０１７９】
読出処理部１２がフロー＃ｉのキュー１１からパケットを読み出すと（ステップＳｔ８１）、蓄積量計数部１３０ａは、フロー＃ｉの蓄積量から、読み出されたパケットのパケット長（ＰＫＴ長）を減算する（ステップＳｔ８２）。次に、クレジット計数部１３１ａは、フロー＃ｉのクレジットカウンタ値から、読み出されたパケットのパケット長（ＰＫＴ長）を減算する（ステップＳｔ８３）。なお、ステップＳｔ８３の処理順序は、ステップＳｔ８３の前であってもよい。
【０１８０】
次に、クレジット計数部１３１ａは、フロー＃ｉのクレジットカウンタ値が０より大きいか否かを判定する（ステップＳｔ８４）。クレジット計数部１３１ａは、クレジットカウンタ値が０より大きい場合（ステップＳｔ８４のＹｅｓ）、フロー＃ｉのクレジットフラグＣｒｅｄｉｔ＿ｅｘｔ［ｉ］が「ｔｒｕｅ」であることを、クレジットフラグ管理部２１４に通知する。
【０１８１】
一方、クレジットカウンタ値が０以下である場合（ステップＳｔ８４のＮｏ）、クレジット計数部１３１ａは、フロー＃ｉのクレジットフラグＣｒｅｄｉｔ＿ｅｘｔ［ｉ］が「ｆａｌｓｅ」であることを、クレジットフラグ管理部２１４に通知する。このようにして、キュー管理部１は、パケットが読み出されたときの動作を行う。
【０１８２】
このように、クレジット計数部１３１ａは、パケットの読み出しを契機とし、クレジットフラグＣｒｅｄｉｔ＿ｅｘｔを通知するため、クレジットフラグ管理部２１４は、クレジット付与のタイミングと無関係に、クレジットフラグＣｒｅｄｉｔ＿ｅｘｔを更新できる。もっとも、クレジットフラグＣｒｅｄｉｔ＿ｅｘｔの通知は、パケットの読み出しだけでなく、クレジット付与を契機として行われてもよい。
【０１８３】
また、図２８は、キュー管理部１から通知を受信したときのスケジューラ部２の動作を示すフローチャートである。クレジットフラグ管理部２１４は、クレジット計数部１３１ａからクレジットフラグＣｒｅｄｉｔ＿ｅｘｔ［ｉ］の通知を受信すると（ステップＳｔ９１）、クレジットフラグＣｒｅｄｉｔ＿ｅｘｔ［ｉ］を更新する（ステップＳｔ９２）。このようにして、スケジューラ部２は、キュー管理部１から通知を受信したときの動作を行う。
【０１８４】
また、図２９は、スケジューリング処理を行うときのスケジューラ部２の動作を示すフローチャートである。クレジット付与部２０ｂは、フロー＃ｉのスケジューリング契機が到来すると、フロー＃ｉのクレジットフラグＣｒｅｄｉｔ＿ｅｘｔ［ｉ］が「ｔｒｕｅ」（真）であるか否かを判定する（ステップＳｔ１０１）。
【０１８５】
フロー＃ｉのクレジットフラグＣｒｅｄｉｔ＿ｅｘｔ［ｉ］が「ｔｒｕｅ」である場合（ステップＳｔ１０１のＹｅｓ）、フロー＃ｉを低優先リスト２０２に登録する（ステップＳｔ１０３）。一方、フロー＃ｉのクレジットフラグＣｒｅｄｉｔ＿ｅｘｔ［ｉ］が「ｆａｌｓｅ」である場合（ステップＳｔ１０１のＮｏ）、フロー＃ｉを高優先リスト２０１に登録する（ステップＳｔ１０２）。このようにして、スケジューラ部２は、スケジューリング処理を行うときの動作を行う。
【０１８６】
このように、本実施例において、クレジット計数部１３１ａは、スケジューラ部２にクレジットが０より大きくなったことを通知する。スケジューラ部２は、クレジット計数部１３１ａの当該通知に応じて、複数のキュー１１のうち、クレジットが０より大きいキュー１１（フロー）の優先度を低下させる。
【０１８７】
したがって、本実施例によれば、クレジットが０より大きいキュー１１へのクレジット付与を、クレジットが０以下のキュー１１の後回しにできる。このため、クレジットが０以下のキュー１１に優先的にクレジットが与えられ、読出処理部１５により読み出されるまでの該キュー１１のパケットの待機時間が低減されるので、読み出しの遅延が低減される。
【０１８８】
（第４実施例）
上述した実施例では、パケットの読み出しを契機として、更新後のクレジットカウンタ値が０より大きい場合に該キュー１１の優先度を低下させたが、更新後のクレジットカウンタ値に基づいて該キュー１１の優先度を段階的に調整してもよい。
【０１８９】
図３０Ａ及び図３０Ｂには、第４実施例の動作の一例が示されている。図３０Ａ及び図３０Ｂに示されるように、本実施例において、スケジューラ部２は、クレジットフラグ管理部２１４に代えて、クレジットレベル管理部２１５が設けられている。また、クレジット計数部１３１ａは、キュー１１からパケットが読み出されることによりクレジットカウンタ値が変化したとき、変化後のクレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎをクレジットレベル管理部２１５に通知する。
【０１９０】
クレジットレベル管理部２１５は、クレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎに応じ、クレジットカウンタ値のレベルＣｒｅｄｉｔ＿ＬＶ（以下、「クレジットレベル」と表記）を、例えば、「Ｈｉｇｈ」、「Ｍｉｄｄｌｅ」、及び「Ｌｏｗ」の三段階に分けて管理する。クレジットレベル管理部２１５は、例えば、クレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎが２５０１（Ｂｙｔｅ）以上である場合、「Ｌｏｗ」レベルと判定し、１〜２５００（Ｂｙｔｅ）以上である場合、「Ｍｉｄｄｌｅ」レベルと判定する。さらに、クレジットレベル管理部２１５は、クレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎが０（Ｂｙｔｅ）以下である場合、「Ｈｉｇｈ」レベルと判定する。
【０１９１】
また、クレジット付与部２０ｂは、「Ｈｉｇｈ」レベル、「Ｍｉｄｄｌｅ」レベル、及び「Ｌｏｗ」レベルにそれぞれ対応する高優先リスト、中優先リスト、及び低優先リストを有する。クレジット付与部２０ｂは、各フロー＃０〜＃Ｎを、上記の３つのリストのうち、各クレジットレベルＣｒｅｄｉｔ＿ＬＶに応じたリストに登録する。
【０１９２】
図３０Ａ及び図３０Ｂは、時系列（時刻ｔ０〜ｔ７）に従って、蓄積量計数部１３０ａの蓄積量、クレジット計数部１３１ａのクレジットカウンタ値、仮想蓄積量計数部２１０の仮想蓄積量、及びクレジットレベル管理部２１５のクレジットレベルＣｒｅｄｉｔ＿ＬＶを示す。
【０１９３】
時刻ｔ０において、フロー＃０及びフロー＃１の各蓄積量は、２１００（Ｂｙｔｅ）及び５０００（Ｂｙｔｅ）であり、フロー＃０及びフロー＃１の各クレジットは、−１０００（Ｂｙｔｅ）及び−５１００（Ｂｙｔｅ）である。また、フロー＃０及びフロー＃１の各仮想蓄積量は、それぞれ、５０００（Ｂｙｔｅ）及び５１００（Ｂｙｔｅ）である。フロー＃０及びフロー＃１の各クレジットレベルＣｒｅｄｉｔ＿ＬＶは、上記の基準に従い、ともに「Ｈｉｇｈ」である。
【０１９４】
次に、時刻ｔ１において、クレジット付与部２０ｂは、フロー＃０のキュー１１にクレジットを与えることにより、フロー＃０のクレジットカウンタ値は、１５００（Ｂｙｔｅ）となり、フロー＃０の仮想蓄積量は、２５００（Ｂｙｔｅ）となる。
【０１９５】
次に、時刻ｔ２において、１００（Ｂｙｔｅ）のパケットが、フロー＃０のキュー１１から読み出される。これにより、フロー＃０の蓄積量は、２０００（Ｂｙｔｅ）になり、フロー＃０のクレジットカウント値は、１４００（Ｂｙｔｅ）となる。
【０１９６】
次に、時刻ｔ３において、クレジット計数部１３１ａは、クレジットフラグ管理部２１４に、フロー＃０のクレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎ［０］が１４００（Ｂｙｔｅ）であることを通知する。これにより、クレジットレベル管理部２１５は、上記の基準に従い、フロー＃０のクレジットレベルＣｒｅｄｉｔ＿ＬＶを「Ｍｉｄｄｌｅ」に更新する。このため、クレジット付与部２０ｂは、フロー＃０の優先度を低下させ、フロー＃０を中優先リストに登録する。したがって、フロー＃０のキュー１１へのクレジットの付与は、フロー＃１のキュー１１の後回しとなる。
【０１９７】
次に、時刻ｔ４において、クレジット付与部２０ｂは、フロー＃１のキュー１１にクレジットを与えることにより、フロー＃１のクレジットカウンタ値は、−２６００（Ｂｙｔｅ）となり、フロー＃１の仮想蓄積量は、２６００（Ｂｙｔｅ）となる。
【０１９８】
次に、時刻ｔ５において、クレジット付与部２０ｂは、フロー＃１のキュー１１にクレジットを与えることにより、フロー＃１のクレジットカウンタ値は、−１００（Ｂｙｔｅ）となり、フロー＃１の仮想蓄積量は、１００（Ｂｙｔｅ）となる。
【０１９９】
次に、時刻ｔ６において、１５００（Ｂｙｔｅ）のパケットが、フロー＃０のキュー１１から読み出される。これにより、フロー＃０の蓄積量は、５００（Ｂｙｔｅ）になり、フロー＃０のクレジットカウント値は、−１００（Ｂｙｔｅ）となる。
【０２００】
次に、時刻ｔ７において、クレジット計数部１３１ａは、クレジットレベル管理部２１５に、フロー＃０のクレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎ［０］が−１００（Ｂｙｔｅ）であることを通知する。これにより、クレジットレベル管理部２１５は、上記の基準に従い、フロー＃０のクレジットレベルＣｒｅｄｉｔ＿ＬＶを「Ｈｉｇｈ」に更新する。
【０２０１】
次に、本実施例におけるキュー管理部１及びスケジューラ部２の動作を説明する。図３１は、パケットが読み出されたときのキュー管理部１の動作を示すフローチャートである。
【０２０２】
読出処理部１２がフロー＃ｉのキュー１１からパケットを読み出すと（ステップＳｔ１１１）、蓄積量計数部１３０ａは、フロー＃ｉの蓄積量から、読み出されたパケットのパケット長（ＰＫＴ長）を減算する（ステップＳｔ１１１）。次に、クレジット計数部１３１ａは、フロー＃ｉのクレジットカウンタ値から、読み出されたパケットのパケット長（ＰＫＴ長）を減算する（ステップＳｔ１１３）。なお、ステップＳｔ１１３の処理順序は、ステップＳｔ１１２の前であってもよい。
【０２０３】
次に、クレジット計数部１３１ａは、変化後のフロー＃ｉのクレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎ［ｉ］をスケジューラ部２に通知する（ステップＳｔ１１４）。このようにして、キュー管理部１は、パケットが読み出されたときの動作を行う。
【０２０４】
また、図３２は、キュー管理部１から通知を受信したときのスケジューラ部２の動作を示すフローチャートである。クレジット計数部１３１ａから変化後のクレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎ［ｉ］を受信すると（ステップＳｔ１２１）、クレジットレベル管理部２１５は、上述した基準に従い、フロー＃ｉのクレジットレベルＣｒｅｄｉｔ＿ＬＶ［ｉ］を更新する（ステップＳｔ１２２）。このようにして、スケジューラ部２は、キュー管理部１から通知を受信したときの動作を行う。
【０２０５】
図３３は、スケジューリング処理を行うときのスケジューラ部２の動作を示すフローチャートである。クレジット付与部２０ｂは、フロー＃ｉのスケジューリング契機が到来すると、フロー＃ｉのクレジットレベルＣｒｅｄｉｔ＿ＬＶ［ｉ］を判定する（ステップＳｔ１３１）。
【０２０６】
クレジット付与部２０ｂは、クレジットレベルＣｒｅｄｉｔ＿ＬＶ［ｉ］が「Ｈｉｇｈ」であるとき、フロー＃ｉを高優先リストに登録する（ステップＳｔ１３２）。また、クレジット付与部２０ｂは、クレジットレベルＣｒｅｄｉｔ＿ＬＶ［ｉ］が「Ｍｉｄｄｌｅ」であるとき、フロー＃ｉを中優先リストに登録する（ステップＳｔ１３３）。また、クレジット付与部２０ｂは、クレジットレベルＣｒｅｄｉｔ＿ＬＶ［ｉ］が「Ｌｏｗ」であるとき、フロー＃ｉを低優先リストに登録する（ステップＳｔ１３４）。このようにして、スケジューラ部２は、スケジューリング処理を行うときの動作を行う。
【０２０７】
このように、本実施例において、クレジット計数部１３１ａは、スケジューラ部２に変化後のクレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎを通知する。スケジューラ部２は、クレジット計数部１３１ａから通知された変化後のクレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎに応じて、複数のキュー１１のうち、クレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎが変化したキュー１１の優先度を調整する。
【０２０８】
より具体的には、クレジットレベル管理部２１５は、クレジットカウンタ値Ｃｒｅｄｉｔ＿ｌｅｎを所定の閾値と比較することにより、クレジットレベルＣｒｅｄｉｔ＿ＬＶを三段階（「Ｈｉｇｈ」、「Ｍｉｄｄｌｅ」、及び「Ｌｏｗ」）で判定する。そして、クレジット付与部２０ｂは、クレジットレベルＣｒｅｄｉｔ＿ＬＶに基づいて、該当するフロー＃０〜＃Ｎの優先度を、３つの優先度リストを用いて段階的に調整する。
【０２０９】
したがって、本実施例によれば、キュー１１ごとの蓄積量に応じて、クレジット付与の順序を柔軟に制御することが可能となる。なお、本実施例では、クレジットレベルＣｒｅｄｉｔ＿ＬＶ及び優先度リストを三段階に分けた例を示したが、これに限定されず、四段階以上であってもよい。
【０２１０】
（第５実施例）
既に述べたように、読出処理部１５は、クレジットカウンタ値が０より大きいキュー１１からパケットを読み出す。このとき、読み出されたパケットのパケット長（データ量）がクレジットカウンタ値より大きい場合、パケット長分の減算によりクレジットカウンタ値は０より小さくなる（つまり、負の値になる）。そして、図５及び図６を参照して述べたように、比較例のスケジューラ部２は、クレジットカウンタ値が負の値であっても、仮想蓄積量が０より大きければ、仮想蓄積量が０となるように、複数回にわたって、当該キュー１１にクレジットを与える。
【０２１１】
そこで、蓄積量が０（Ｂｙｔｅ）になったとき、クレジットカウンタ値を強制的に０（Ｂｙｔｅ）とするとともに、仮想蓄積量からクレジットカウンタ値の絶対値を減算して相殺することにより、クレジット付与の回数を低減してもよい。
【０２１２】
図３４には、第５実施例の動作の一例が示されている。クレジット計数部１３１ｂは、上記のクレジット計数部１３１と同様の機能を有するだけでなく、蓄積量が０（Ｂｙｔｅ）である場合に、仮想蓄積量計数部２１０ａに超過消費量を通知する機能を有する。超過消費量は、クレジットカウンタ値が０より小さい場合、つまり負の値である場合におけるクレジットカウンタ値の絶対値である。仮想蓄積量計数部２１０ａは、超過消費量を通知すると、当該クレジットカウンタ値を０（Ｂｙｔｅ）にする。
【０２１３】
また、仮想蓄積量計数部２１０ａは、上記の仮想蓄積量計数部２１０と同様の機能を有するだけでなく、クレジット計数部１３１ｂの通知を受けたとき、該当するフロー＃０〜＃Ｎの仮想蓄積量から超過消費量を減算する機能を有する。これにより、仮想蓄積量は、相殺されて０（Ｂｙｔｅ）となる。
【０２１４】
図３４は、時系列（時刻ｔ０〜ｔ３）に従って、蓄積量計数部１３０ａの蓄積量、クレジット計数部１３１ｂのクレジットカウンタ値、及び仮想蓄積量計数部２１０ａの仮想蓄積量を示す。
【０２１５】
時刻ｔ０において、キュー管理部１に１０００１（Ｂｙｔｅ）のパケットが到着することにより、蓄積量及び仮想蓄積量は、１０００１（Ｂｙｔｅ）となる。また、クレジットカウント値は、０（Ｂｙｔｅ）とする。なお、フローＩＤは、＃０〜＃Ｎのうち、何れであってもよい。
【０２１６】
次に、時刻ｔ１において、スケジューラ部２からキュー管理部１に２５００（Ｂｙｔｅ）のクレジットが与えられる。これにより、クレジットカウント値は、２５００（Ｂｙｔｅ）となり、仮想蓄積量は、７５０１（Ｂｙｔｅ）となる。
【０２１７】
次に、時刻ｔ２において、１０００１（Ｂｙｔｅ）のパケットが、キュー管理部１から読み出される。これにより、クレジットカウント値は、−７５０１（Ｂｙｔｅ）となり、蓄積量は、０（Ｂｙｔｅ）となる。
【０２１８】
また、クレジット計数部１３１ｂは、蓄積量が０（Ｂｙｔｅ）であり、クレジットカウント値が負の値であるため、超過消費量が７５０１（Ｂｙｔｅ）であることを、スケジューラ部２に通知する。
【０２１９】
次に、時刻ｔ３において、クレジット計数部１３１ｂは、クレジットカウンタ値を０（Ｂｙｔｅ）とする。また、仮想蓄積量計数部２１０ａは、クレジット計数部１３１ｂの通知に応じて、仮想蓄積量から超過消費量を減算することにより、仮想蓄積量を０とする。このため、本実施例では、図５及び図６と比べると理解されるように、２〜５回目のクレジット付与が省かれる。
【０２２０】
次に、本実施例におけるキュー管理部１及びスケジューラ部２の動作を説明する。図３５は、パケットを読み出すときのキュー管理部１の動作を示すフローチャートである。
【０２２１】
読出処理部１２がフロー＃ｉのキュー１１からパケットを読み出すと（ステップＳｔ１５１）、蓄積量計数部１３０ａは、フロー＃ｉの蓄積量から、読み出されたパケットのパケット長（ＰＫＴ長）を減算する（ステップＳｔ１５２）。次に、クレジット計数部１３１ｂは、フロー＃ｉのクレジットカウンタ値から、読み出されたパケットのパケット長（ＰＫＴ長）を減算する（ステップＳｔ１５３）。なお、ステップＳｔ１５３の処理順序は、ステップＳｔ１５２の前であってもよい。
【０２２２】
次に、クレジット計数部１３１ｂは、フロー＃ｉの蓄積量が０であるか否かを判定し（ステップＳｔ１５４）、蓄積量が０ではない場合（ステップＳｔ１５４のＮｏ）、処理を終了する。一方、蓄積量が０である場合（ステップＳｔ１５４のＹｅｓ）、クレジット計数部１３１ｂは、フロー＃ｉのクレジットカウンタ値が０より小さいか否か（負の値であるか否か）を判定する（ステップＳｔ１５５）。
【０２２３】
クレジット計数部１３１ｂは、クレジットカウンタ値が０以上である場合（ステップＳｔ１５５のＮｏ）、処理を終了する。一方、クレジットカウンタ値が０より小さい場合（ステップＳｔ１５５のＹｅｓ）、クレジット計数部１３１ｂは、クレジットカウンタ値の絶対値を、超過消費量として、仮想蓄積量計数部２１０ａに通知する（ステップＳｔ１５６）。なお、ステップＳｔ１５４の処理順序は、ステップＳｔ１５５の前であってもよい。
【０２２４】
次に、クレジット計数部１３１ｂは、フロー＃ｉのクレジットカウンタ値に、超過消費量を加算することにより、フロー＃ｉのクレジットカウンタ値を０（Ｂｙｔｅ）とする（ステップＳｔ１５７）。このようにして、キュー管理部１は、パケットが読み出されたときの動作を行う。
【０２２５】
また、図３６は、キュー管理部１から通知を受信したときのスケジューラ部２の動作を示すフローチャートである。クレジット計数部１３１ｂから超過消費量を受信すると（ステップＳｔ１６１）、仮想蓄積量計数部２１０ａは、仮想蓄積量から超過消費量を減算する（ステップＳｔ１６２）。このようにして、スケジューラ部２は、キュー管理部１から通知を受信したときの動作を行う。
【０２２６】
このように、本実施例において、クレジット計数部１３１ｂは、キュー１１の蓄積量が０になり、同キュー１１のクレジットカウンタ値が０より小さくなったとき、仮想蓄積量計数部２１０ａに、当該キューのクレジットカウンタ値を、超過消費量として通知する。さらに、クレジット計数部１３１ｂは、当該キューのクレジットカウンタ値を０とする。また、仮想蓄積量計数部２１０ａは、クレジット計数部１３１ｂからクレジットカウンタ値が通知されたとき、仮想蓄積量から超過消費量を減算する。
【０２２７】
したがって、クレジット計数部１３１ｂは、クレジット付与部２０ａから複数回にわたってクレジットを与える手間をかけることなく、一度にクレジットカウンタ値を０とすることができる。また、クレジット計数部１３１ｂは、仮想蓄積量計数部２１０ａに、クレジットカウンタ値の絶対値である超過消費量を通知し、仮想蓄積量計数部２１０ａは、仮想蓄積量から超過消費量を減算するので、該当するキュー１１へのクレジット付与が省かれる。
【０２２８】
（第６実施例）
これまで述べた内容は、複数の下位キューが複数の組に分かれ、各組に対応する上位キューが設けられた階層的なキュー構成にも適用できる。図３７は、第６実施例の出力処理部９１３の機能構成を示す構成図である。図３７において、図８と共通する構成については、同一の符号を付し、その説明を省略する。
【０２２９】
出力処理部９１３は、キュー管理部１及びスケジューラ部２を有する。キュー管理部１は、分配部１０と、複数の下位キュー１１ａ，１１ｂと、複数の上位キュー１４ａ，１４ｂと、読出処理部１２ａと、蓄積量計数部１３０ａと、クレジット計数部１３１とを有する。
【０２３０】
複数の下位キュー１１ａ，１１ｂは、第１の組Ｕ１及び第２の組Ｕ２に分けられている。第１の組Ｕ１は、フロー＃０〜＃２の下位キュー１１ａを含み、第２の組Ｕ２は、フロー＃３〜＃５の下位キュー１１ｂを含む。
【０２３１】
読出処理部１２ａは、クレジットを消費して、複数の下位キュー１１ａ，１１ｂからパケットを読み出す。そして、読出処理部１２ａは、読み出したパケットを、複数の上位キュー１４ａ，１４ｂのうち、パケットを読み出した下位キュー１１ａ，１１ｂに対応する上位キューに出力する。なお、読出処理部１２ａの他の機能は、先の実施例の読出処理部１２と共通する。
【０２３２】
上位キュー１４ａ，１４ｂは、互いに異なるポート＃０，＃１にそれぞれ対応して設けられている。ポート＃０の上位キュー１４ａは、第１の組Ｕ１の下位キュー１１ａから読み出されたパケットが蓄積され、ポート＃１の上位キュー１４ｂは、第２の組Ｕ２の下位キュー１１ｂから読み出されたパケットが蓄積される。なお、ポート＃０，＃１は、図２に示された光送受信器９１０である。
【０２３３】
一方、スケジューラ部２は、仮想蓄積量計数部２１０、蓄積量フラグ管理部２１１、及びクレジット付与部２３を有する。クレジット付与部２３は、クレジットを複数の下位キュー１１ａ，１１ｂに与えるとき、まず、上位キュー１４ａ，１４ｂごとの優先度（上位側優先度）に基づく順序に従って、１つの上位キューを選択する。さらに、クレジット付与部２３は、選択した上位キュー１４ａ，１４ｂに対応する組Ｕ１，Ｕ２の複数の下位キュー１１ａ，１１ｂに、下位キューごとの優先度に基づく順序に従って、クレジットをそれぞれ与える。
【０２３４】
クレジット付与部２３は、第１の組Ｕ１からクレジット付与対象となる下位キュー１１ａを選択する第１処理部２３１と、第２の組Ｕ２からクレジット付与対象となる下位キュー１１ｂを選択する第２処理部２３２とを有する。第１処理部２３１及び第２処理部２３２は、それぞれ、高優先リスト２３１ａ，２３２ａ及び低優先リスト２３１ｂ，２３２ｂを有する。
【０２３５】
第１処理部２３１及び第２処理部２３２は、第１実施例のクレジット付与部２０ａと同様に、下位キュー１１ａ，１１ｂごとの蓄積量フラグＱ＿ｅｍｐｔｙに応じて、各フロー＃０〜＃５を高優先リスト２３１ａ，２３２ａ及び低優先リスト２３１ｂ，２３２ｂの一方に登録する。フロー＃０〜＃２は高優先リスト２３１ａ及び低優先リスト２３１ｂの一方に登録され、フロー＃３〜＃５は、高優先リスト２３２ａ及び低優先リスト２３２ｂの一方に登録される。なお、登録状態は、丸印（「○」）により示されている。
【０２３６】
また、クレジット付与部２３は、第１の組Ｕ１及び第２の組Ｕ２から、クレジット付与対象となる組を選択する第３処理部２３３を、さらに有する。つまり、第３処理部２３３は、ポート＃０の上位キュー１４ａ及びポート＃１の上位キュー１４ｂから１つを選択する。
【０２３７】
第３処理部２３３は、上位キュー１４ａ，１４ｂごとの優先度に基づく順序に従って、１つの上位キューを選択する。第３処理部２３３は、優先度を区別するために高優先リスト２３３ａ及び低優先リスト２３３ｂを有する。各上位キュー１４ａ，１４ｂのポート＃０、＃１は、高優先リスト２３３ａ及び低優先リスト２３３ｂの一方に登録される。なお、登録状態は、丸印（「○」）により示されている。
【０２３８】
第３処理部２３３は、第１の組Ｕ１及び第２の組Ｕ２の何れかに含まれる下位キュー１１ａ，１１ｂの全ての蓄積量が０（Ｂｙｔｅ）となった場合、上位キュー１４ａ，１４ｂのうち、その組に対応する上位キューの優先度を低下させる。より具体的には、第３処理部２３３は、第１の組Ｕ１及び第２の組Ｕ２の何れかに含まれる全下位キュー１１ａ，１１ｂの蓄積量フラグＱ＿ｅｍｐｔｙが「ｔｒｕｅ」となった場合、その組に対応する上位キューの優先度を低下させる。
【０２３９】
図３７の例では、第１の組Ｕ１の全下位キュー１１ａの蓄積量が０（Ｂｙｔｅ）であるため、全ての蓄積量フラグＱ＿ｅｍｐｔｙが「ｔｒｕｅ」である。このため、第１処理部２３１は、フロー＃０〜＃２を低優先リスト２３１ｂに登録し、第３処理部２３３は、ポート＃０を低優先リスト２３３ｂに登録する。
【０２４０】
一方、第２の組Ｕ２では、フロー＃４の下位キュー１１ｂの蓄積量だけが０（Ｂｙｔｅ）であるため、フロー＃４の蓄積量フラグＱ＿ｅｍｐｔｙが「ｔｒｕｅ」であり、他のフロー＃３，＃５の蓄積量フラグＱ＿ｅｍｐｔｙは、「ｆａｌｓｅ」である。このため、第２処理部２３２は、フロー＃４のみを低優先リスト２３１ｂに登録し、第３処理部２３３は、ポート＃１を高優先リスト２３３ａに登録する。つまり、第３処理部２３３は、各組Ｕ１，Ｕ２において、少なくとも１つの蓄積量フラグＱ＿ｅｍｐｔｙが「ｆａｌｓｅ」であれば、その組に対応するポート＃０，＃１を高優先リスト２３３ａに登録する。
【０２４１】
したがって、図３７の例におけるクレジット付与の順序は、例えば、フロー＃３（ポート＃１）、フロー＃５（ポート＃１）、フロー＃４（ポート＃１）、フロー＃０（ポート＃０）、フロー＃１（ポート＃１）、フロー＃２（ポート＃０）の順となる。このうち、最後の４つ（フロー＃４，＃０，＃１，＃２）は、蓄積量フラグＱ＿ｅｍｐｔｙが「ｔｒｕｅ」である。つまり、本実施例では、下位キュー１１ａ，１１ｂの蓄積量フラグＱ＿ｅｍｐｔｙによる影響を、上位キュー１４ａ，１４ｂに与えることができる。
【０２４２】
一方、第３処理部２３３が、蓄積量フラグＱ＿ｅｍｐｔｙによらず、単純に、２つの上位キュー１４ａ，１４ｂ（ポート＃０、＃１）を交互に選択すると仮定する。この場合、クレジット付与の順序は、例えば、フロー＃０（ポート＃０）、フロー＃３（ポート＃１）、フロー＃１（ポート＃０）、フロー＃５（ポート＃１）、フロー＃２（ポート＃０）、フロー＃４（ポート＃１）の順となる。このうち、１番目、３番目、５番目、及び６番目のフロー＃０，＃１，＃２，＃４は、蓄積量フラグＱ＿ｅｍｐｔｙが「ｔｒｕｅ」である。つまり、この例では、蓄積量が０であるフロー＃０の下位キュー１１ａに、蓄積量が０より大きい他のフロー＃３，＃５の下位キュー１１ｂより早い順序でクレジットを与えてしまう。
【０２４３】
図３８〜図４１には、第６実施例の動作の一例が時系列に示されている。図３８に示されるように、フロー＃０〜＃５の仮想蓄積量を、それぞれ、７０００（Ｂｙｔｅ）、２０００（Ｂｙｔｅ）、１０００（Ｂｙｔｅ）、４０００（Ｂｙｔｅ）、５０００（Ｂｙｔｅ）、６０００（Ｂｙｔｅ）とする。また、フロー＃１，＃２の積量フラグＱ＿ｅｍｐｔｙは、「ｔｒｕｅ」であり、フロー＃０，＃３〜＃５の蓄積量フラグＱ＿ｅｍｐｔｙは、「ｆａｌｓｅ」である。
【０２４４】
このとき、各組Ｕ１，Ｕ２において、少なくとも１つの蓄積量フラグＱ＿ｅｍｐｔｙが「ｆａｌｓｅ」であるので、ポート＃０，＃１は、ともに高優先リスト２３３ａに登録されている。また、フロー＃０は、高優先リスト２３１ａに登録され、フロー＃１，＃２は、低優先リスト２３１ｂに登録されている。フロー＃３〜＃５は、高優先リスト２３２ａに登録されている。
【０２４５】
クレジットが、フロー＃０の下位キュー１１ａに与えられ、パケットが読み出されて、フロー＃０の下位キュー１１ａの蓄積量が０（Ｂｙｔｅ）になると、図３９に示されるように、フロー＃０の蓄積量フラグＱ＿ｅｍｐｔｙは、「ｔｒｕｅ」となる。このため、第１処理部２３１は、フロー＃０を低優先リスト２３１ｂに登録する。なお、フロー＃０の仮想蓄積量は、４５００（Ｂｙｔｅ）になる。
【０２４６】
次に、図４０に示されるように、第１の組Ｕ１において、全ての蓄積量フラグＱ＿ｅｍｐｔｙが「ｔｒｕｅ」になったので、第３処理部２３３は、第１の組Ｕ１に対応するポート＃０を、低優先リスト２３３ｂに登録する。このため、第３処理部２３３は、ポート＃０の上位キュー１４ａの選択を、ポート＃１の上位キュー１４ｂの後回しにする。
【０２４７】
次に、１５００（Ｂｙｔｅ）のパケットが到着して、フロー＃１の下位キュー１１ａに入力されると、図４１に示されるように、フロー＃１の仮想蓄積量は、３５００（Ｂｙｔｅ）となり、フロー＃１の蓄積量フラグＱ＿ｅｍｐｔｙは、「ｆａｌｓｅ」になる。このため、第１処理部２３１は、フロー＃１を高優先リスト２３１ａに登録する。
【０２４８】
また、第３処理部２３３は、第１の組Ｕ１において、少なくとも１つの蓄積量フラグＱ＿ｅｍｐｔｙが「ｆａｌｓｅ」になったので、第１の組Ｕ１に対応するポート＃０を、高優先リスト２３３ａに登録する。これにより、第３処理部２３３は、ポート＃０，＃１の上位キュー１４ａ，１４ｂの選択を、公平に行う。
【０２４９】
また、図４２は、スケジューリング処理を行うときのスケジューラ部２の動作を示すフローチャートである。より具体的には、図４２は、第３処理部２３３の動作を示す。
【０２５０】
第３処理部２３３は、下位側の高優先リスト２３１ａ，２３２ａまたは低優先リスト２３１ｂ，２３２ｂに登録処理が行われたことを契機として、高優先リスト２３１ａ，２３２ａにフロー＃０〜＃５が登録されているか否かを判定する（ステップＳｔ１４１）。次に、第３処理部２３３は、下位側の高優先リスト２３１ａ，２３２ａの何れかに１つもフロー＃０〜＃５が登録されていない場合（ステップＳｔ１４１のＮｏ）、該高優先リストに対応するポート＃０，＃１を自己の低優先リスト２３３ｂに登録する（ステップＳｔ１４２）。
【０２５１】
一方、下位側の高優先リスト２３１ａ，２３２ａに少なくとも１つのフロー＃０〜＃５が登録されている場合（ステップＳｔ１４１のＹｅｓ）、第３処理部２３３は、該高優先リストに対応するポート＃０，＃１を自己の高優先リスト２３３ａに登録する（ステップＳｔ１４３）。このようにして、スケジューラ部２は、スケジューリング処理を行うときの動作を行う。
【０２５２】
このように、本実施例において、スケジューラ部２は、複数の上位キュー１４ａ，１４ｂから、上位キュー１４ａ，１４ｂごとの上位側優先度に基づく順序に従って、１つの上位キュー１４ａ，１４ｂを選択する。そして、スケジューラ部２は、選択した上位キュー１４ａ，１４ｂに対応する複数の下位キュー１１ａ，１１ｂの１つにクレジットを与える。また、スケジューラ部２は、複数の組Ｕ１，Ｕ２の何れかに含まれる複数の下位キュー１１ａ，１１ｂの全ての蓄積量が０となった場合、複数の上位キュー１４ａ，１４ｂのうち、当該組Ｕ１，Ｕ２に対応する上位キュー１４ａ，１４ｂの上位側優先度を低下させる。
【０２５３】
したがって、スケジューラ部２は、全ての下位キュー１１ａ，１１ｂの蓄積量が０となった組Ｕ１，Ｕ２に対応する上位キュー１４ａ，１４ｂの選択を後回しにできるので、当該下位キュー１１ａ，１１ｂへのクレジット付与を後回しにできる。
【０２５４】
これまで述べたように、実施例に係る通信装置は、パケットを蓄積する複数のキュー１１と、スケジューラ部２と、読出処理部１２と、蓄積量計数部１３０とを有する。スケジューラ部２は、複数のキュー１１に、キュー１１ごとの優先度に基づく順序に従って、クレジット（読出許容量）をそれぞれ与える。
【０２５５】
読出処理部１２は、クレジットを消費して複数のキュー１１からパケットを読み出す。蓄積量計数部１３０は、複数のキュー１１に蓄積されたパケットの蓄積量を、キュー１１ごとに計数する。
【０２５６】
蓄積量計数部１３０は、スケジューラ部２に蓄積量の変化を通知する。スケジューラ部２は、蓄積量計数部の当該通知に応じて、複数のキュー１１のうち、蓄積量が変化したキュー１１の優先度を調整する。
【０２５７】
このように、スケジューラ部２は、蓄積量計数部１３０から通知された蓄積量の変化を契機として、蓄積量が変化したキュー１１の優先度を調整するので、当該キュー１１へのクレジット付与の順序が、蓄積量の変化に応じて調整される。読出処理部１２は、クレジットを消費して複数のキュー１１からパケットを読み出すため、クレジット付与の順序の調整に伴い、当該キュー１１からパケットが読み出されるまでの待機時間も調整される。したがって、実施例に係る通信装置によると、パケットの遅延が低減される。
【０２５８】
また、実施例に係るパケットスケジューリング方法は、以下の（１）〜（３）の工程を含む。
（１）パケットを蓄積する複数のキュー１１に、キュー１１ごとの優先度に基づく順序に従って、クレジット（読出許容量）をそれぞれ与える。
（２）クレジットを消費して複数のキュー１１からパケットを読み出す。
（３）複数のキュー１１に蓄積されたパケットの蓄積量の変化に応じて、複数のキュー１１のうち、蓄積量が変化したキュー１１の優先度を調整する。
【０２５９】
したがって、実施例に係るパケットスケジューリング方法によると、実施例に係る通信装置と同様の作用効果が得られる。
【０２６０】
以上、好ましい実施例を参照して本発明の内容を具体的に説明したが、本発明の基本的技術思想及び教示に基づいて、当業者であれば、種々の変形態様を採り得ることは自明である。
【０２６１】
なお、以上の説明に関して更に以下の付記を開示する。
（付記１）  パケットを蓄積する複数のキューと、
前記複数のキューに、キューごとの優先度に基づく順序に従って、読出許容量をそれぞれ与えるスケジューラ部と、
前記読出許容量を消費して前記複数のキューから前記パケットを読み出す読出処理部と、
前記複数のキューに蓄積された前記パケットの蓄積量を、キューごとに計数する蓄積量計数部とを有し、
前記蓄積量計数部は、前記スケジューラ部に前記蓄積量の変化を通知し、
前記スケジューラ部は、前記蓄積量計数部の当該通知に応じて、前記複数のキューのうち、前記蓄積量が変化したキューの前記優先度を調整することを特徴とする通信装置。
（付記２）  前記蓄積量計数部は、前記スケジューラ部に、前記蓄積量が０になったことを通知し、
前記スケジューラ部は、前記蓄積量計数部の当該通知に応じて、前記複数のキューのうち、前記蓄積量が０になったキューの前記優先度を低下させることを特徴とする付記１に記載の通信装置。
（付記３）  前記複数のキューのうち、前記優先度を低下させたキューに前記パケットが蓄積されたことを、前記スケジューラ部に通知する通知部を、さらに有し、
前記スケジューラ部は、前記通知部の当該通知に応じて、前記複数のキューのうち、前記優先度を低下させたキューの前記優先度を低下前の値に戻すことを特徴とする付記２に記載の通信装置。
（付記４）  前記スケジューラ部は、重み付けラウンドロビン方式に従い、前記複数のキューに前記読出許容量を与え、前記複数のキューのうち、前記優先度を低下させたキューに対する前記読出許容量の付与を、他のキューの後回しにすることを特徴とする付記２または３の何れかに記載の通信装置。
（付記５）  前記蓄積量計数部は、前記スケジューラ部に変化後の前記蓄積量を通知し、
前記スケジューラ部は、前記蓄積量計数部から通知された変化後の前記蓄積量に応じて、前記複数のキューのうち、前記蓄積量が変化したキューの前記優先度を調整することを特徴とする付記１に記載の通信装置。
（付記６）  前記複数のキューに与えられた前記読出許容量を、キューごとに計数する読出許容量計数部を、さらに有し、
前記読出許容量計数部は、前記スケジューラ部に前記読出許容量の変化を通知し、
前記スケジューラ部は、前記読出許容量計数部の当該通知に応じて、前記複数のキューのうち、前記読出許容量が変化したキューの前記優先度を調整することを特徴とする付記１乃至５の何れかに記載の通信装置。
（付記７）  前記読出許容量計数部は、前記スケジューラ部に前記読出許容量が０より大きくなったことを通知し、
前記スケジューラ部は、前記読出許容量計数部の当該通知に応じて、前記複数のキューのうち、前記読出許容量が０より大きくなったキューの前記優先度を低下させることを特徴とする付記６に記載の通信装置。
（付記８）  前記読出許容量計数部は、前記スケジューラ部に変化後の前記読出許容量を通知し、
前記スケジューラ部は、前記読出許容量計数部から通知された変化後の前記読出許容量に応じて、前記複数のキューのうち、前記読出許容量が変化したキューの前記優先度を調整することを特徴とする付記６に記載の通信装置。
（付記９）  前記複数のキューを一組として、複数の組から読み出された前記パケットをそれぞれ蓄積する複数の上位キューを、さらに有し、
前記スケジューラ部は、
前記複数の上位キューから、上位キューごとの上位側優先度に基づく順序に従って、１つの上位キューを選択し、選択した上位キューに対応する前記複数のキューの１つに前記読出許容量を与え、
前記複数の組の何れかに含まれる前記複数のキューの全ての前記蓄積量が０となった場合、前記複数の上位キューのうち、当該組に対応する上位キューの前記上位側優先度を低下させることを特徴とする付記２または３に記載の通信装置。
（付記１０）  前記複数のキューに与えられた前記読出許容量を、キューごとに計数する読出許容量計数部を、さらに有し、
前記読出処理部は、前記複数のキューのうち、前記読出許容量が０より大きいキューからパケットを読み出し、
前記読出許容量計数部は、
前記複数のキューから前記パケットが読み出されたとき、当該キューの前記読出許容量から前記パケットのデータ量を減算し、
当該キューの前記蓄積量が０になり、当該キューの前記読出許容量が０より小さくなったとき、前記スケジューラ部に、当該キューの前記読出許容量を通知するとともに、当該キューの前記読出許容量を０とし、
前記スケジューラ部は、
前記蓄積量から、前記複数のキューに与えた前記読出許容量を減算して得られるキューごとの仮想蓄積量が０になるように、前記複数のキューの各々に前記読出許容量を与え、
前記読出許容量計数部から前記読出許容量が通知されたとき、前記仮想蓄積量から前記読出許容量の絶対値を減算することを特徴とする付記１に記載の通信装置。
（付記１１）  パケットを蓄積する複数のキューに、キューごとの優先度に基づく順序に従って、読出許容量をそれぞれ与え、
前記読出許容量を消費して前記複数のキューから前記パケットを読み出し、
前記複数のキューに蓄積された前記パケットの蓄積量の変化に応じて、前記複数のキューのうち、前記蓄積量が変化したキューの前記優先度を調整することを特徴とするパケットスケジューリング方法。
（付記１２）  前記複数のキューに蓄積された前記パケットの蓄積量が０になったとき、前記複数のキューのうち、当該キューの前記優先度を低下させることを特徴とする付記１１に記載のパケットスケジューリング方法。
（付記１３）  前記複数のキューのうち、前記優先度を低下させたキューに前記パケットが蓄積されたとき、前記複数のキューのうち、当該キューの前記優先度を低下前の値に戻すことを特徴とする付記１２に記載のパケットスケジューリング方法。
（付記１４）  重み付けラウンドロビン方式に従い、前記複数のキューに前記読出許容量を与え、前記複数のキューのうち、前記優先度を低下させたキューに対する前記読出許容量の付与を、他のキューの後回しにすることを特徴とする付記１２または１３の何れかに記載のパケットスケジューリング方法。
（付記１５）  前記複数のキューの変化後の前記蓄積量に応じて、前記複数のキューのうち、当該キューの前記優先度を調整することを特徴とする付記１０に記載のパケットスケジューリング方法。
（付記１６）  前記複数のキューの前記読出許容量の変化に応じて、前記複数のキューのうち、当該キューの前記優先度を調整することを特徴とする付記１１乃至１５の何れかに記載のパケットスケジューリング方法。
（付記１７）  前記複数のキューのうち、前記読出許容量が０より大きくなったキューの前記優先度を低下させることを特徴とする付記１６に記載のパケットスケジューリング方法。
（付記１８）  前記複数のキューの変化後の前記読出許容量に応じて、前記複数のキューのうち、当該キューの前記優先度を調整することを特徴とする付記１６に記載のパケットスケジューリング方法。
（付記１９）  前記複数のキューを一組として、複数の組から読み出された前記パケットをそれぞれ蓄積する複数の上位キューから、上位キューごとの上位側優先度に基づく順序に従って、１つの上位キューを選択し、該選択した上位キューに対応する前記複数のキューの１つに前記読出許容量を与え、
前記複数のキューの全ての前記蓄積量が０となった場合、前記複数の上位キューのうち、当該上位キューの前記上位側優先度を低下させることを特徴とする付記１２または１３に記載のパケットスケジューリング方法。
【符号の説明】
【０２６２】
１                                キュー管理部
２                                スケジューラ部
１０                              分配部（通知部）
１１                              キュー
１１ａ，１１ｂ                    下位キュー
１２                              読出処理部
１４ａ，１４ｂ                    上位キュー
２０，２０ａ，２０ｂ，２３        クレジット付与部
１３０，１３０ａ                  蓄積量計数部
１３１，１３１ａ，１３１ｂ        クレジット計数部（読出許容量計数部）
２１０，２１０ａ                  仮想蓄積量計数部
２１１                            蓄積量フラグ管理部
２１２                            重み値管理部
２１３                            蓄積レベル管理部
２１４                            クレジットフラグ管理部
２１５                            クレジットレベル管理部
Ｕ１，Ｕ２                        組
【図１】
2014187421.tif 000003
【図２】
2014187421.tif 000004
【図３】
2014187421.tif 000005
【図４】
2014187421.tif 000006
【図５】
2014187421.tif 000007
【図６】
2014187421.tif 000008
【図７】
2014187421.tif 000009
【図８】
2014187421.tif 000010
【図９】
2014187421.tif 000011
【図１０】
2014187421.tif 000012
【図１１】
2014187421.tif 000013
【図１２】
2014187421.tif 000014
【図１３】
2014187421.tif 000015
【図１４】
2014187421.tif 000016
【図１５】
2014187421.tif 000017
【図１６】
2014187421.tif 000018
【図１７】
2014187421.tif 000019
【図１８】
2014187421.tif 000020
【図１９】
2014187421.tif 000021
【図２０】
2014187421.tif 000022
【図２１】
2014187421.tif 000023
【図２２】
2014187421.tif 000024
【図２３】
2014187421.tif 000025
【図２４】
2014187421.tif 000026
【図２５】
2014187421.tif 000027
【図２６Ａ】
2014187421.tif 000028
【図２６Ｂ】
2014187421.tif 000029
【図２７】
2014187421.tif 000030
【図２８】
2014187421.tif 000031
【図２９】
2014187421.tif 000032
【図３０Ａ】
2014187421.tif 000033
【図３０Ｂ】
2014187421.tif 000034
【図３１】
2014187421.tif 000035
【図３２】
2014187421.tif 000036
【図３３】
2014187421.tif 000037
【図３４】
2014187421.tif 000038
【図３５】
2014187421.tif 000039
【図３６】
2014187421.tif 000040
【図３７】
2014187421.tif 000041
【図３８】
2014187421.tif 000042
【図３９】
2014187421.tif 000043
【図４０】
2014187421.tif 000044
【図４１】
2014187421.tif 000045
【図４２】
2014187421.tif 000046