(57)【要約】入力部１９１は、パケットを振り分けて複数の収容部１９３に収容させる。複数の収容部１９３は、パケットの書き込みと読み出しとが可能である複数のキュー１９３１に前記パケットを収容する。読出制御部１９４は、前記パケットが書き込まれている前記キューを示す書込キュー情報を前記収容部ごとに生成する書込キュー情報生成部１９４１と、前記パケットを読み出す優先順位を前記キューごとに決定する優先順位決定部１９４０と、前記書込キュー情報と前記優先順位とに応じて前記パケットを読み出すべき前記キューを前記収容部ごとに決定する読出キュー決定部１９４２と、を有する。
2003103234.tif 000002
【特許請求の範囲】
【請求項１】
それぞれ対応する出力ポートに接続されパケットの書き込みと読み出しとが可能である複数のキューに前記パケットを収容する複数の収容手段と、入力ポートに入力される前記パケットを振り分けて前記収容手段に収容させる入力手段と、前記パケットを読み出すべき前記キューを前記収容手段ごとに決定し当該決定したキューから前記パケットを読み出して前記出力ポートへ出力させる読出制御手段とを備え、前記読出制御手段は、前記パケットが書き込まれている前記キューを示す書込キュー情報を前記収容手段ごとに生成する書込キュー情報生成手段と、前記パケットを読み出す優先順位を前記キューごとに決定する優先順位決定手段と、前記書込キュー情報と前記優先順位とに応じて前記パケットを読み出すべき前記キューを前記収容手段ごとに決定する読出キュー決定手段と、を有するパケット転送回路。
【請求項２】
前記優先順位決定手段は、前記収容手段ごとに前記キューの優先順位を判別可能に記憶する優先順位記憶手段と、前記優先順位記憶手段に前記キューの各々の前記優先順位を前記収容手段ごとに書き込んで記憶させる優先順位書込手段と、前記書込キュー情報と前記優先順位記憶手段に記憶した前記優先順位とに応じて前記パケットが書き込まれている前記キューのうち最も高い前記優先順位の前記キューを前記収容手段ごとに検知して前記読出キュー決定手段に通知する最優先順位検知手段と、を有し、前記読出キュー決定手段は、前記最優先順位検知手段からの前記通知と前記書込キュー情報とに応じて前記パケットを読み出すべき前記キューを前記収容手段ごとに決定することを請求項１に記載のパケット転送回路。
【請求項３】
前記読出キュー決定手段は、前記書込キュー情報が示す前記キューのうちで最も前記優先順位が高い前記キューを前記優先順位決定手段が決定した前記優先順位に応じて前記収容手段ごとに検出するキュー検出手段と、前記キュー検出手段が前記収容手段ごとに検出した前記キューを前記パケットの取り出しを行うべき前記キューとして前記収容手段ごとに選択的に採用するキュー選択手段と、を有する請求項２に記載のパケット転送回路。
【請求項４】
前記キュー選択手段は、前記キュー検出手段により検出される前記キューを前記パケットの取り出しを行うべき前記キューとして選択的に採用して当該採用したキューを指す選択キュー情報を前記収容手段ごとに生成する選択キュー情報生成手段と、前記選択キュー情報生成手段が前記収容手段ごとに生成した前記選択キュー情報を格納する選択キュー格納手段と、を有し、前記選択キュー情報生成手段は、前記選択キュー格納手段が今回格納した前記選択キュー情報が指す前記キュー以外の前記キューを前記キュー検出手段が検出した場合に当該検出したキューを指す前記選択キュー情報を次回に生成する請求項３に記載のパケット転送回路。
【請求項５】
前記選択キュー情報格納手段は、前記選択キュー情報生成手段が前記収容手段ごとに生成した前記選択キュー情報を保持する選択キュー保持手段を前記収容手段ごとに備え、前記選択キュー情報生成手段は、前記選択キュー保持手段が今回保持した前記選択キュー情報が指す前記キュー以外の前記キューを前記キュー検出手段が検出した場合に当該検出したキューを指す前記選択キュー情報を次回に生成して前記選択キュー保持手段に保持させる請求項４に記載のパケット転送回路。
【請求項６】
前記キューは、前記選択キュー情報生成手段が前記収容手段ごとに前記選択キュー情報を生成するために序列づけられており、前記選択キュー情報生成手段は、前記選択キュー保持手段が今回保持した前記選択キュー情報が指す前記キューを前記序列の最下位とし、前記キュー検出手段が検出した前記キューのうち前記序列が最も高い前記キューを指す前記選択キュー情報を前記収容手段ごとに次回に生成する請求項に５記載のパケット転送回路。
【請求項７】
前記優先順位書込手段は、前記キューから読み出されたデータ量を前記収容手段ごとに検知する読出データ量検知手段と、前記読出データ量検知手段が検知した前記データ量が前記キューごとに定めた閾値になった場合に当該キューの前記優先順位が所定の順位まで下がるように修正して前記優先順位記憶手段に書き込む優先順位修正手段と、を有する請求項６に記載のパケット転送回路。
【請求項８】
前記優先順位修正手段は、前記キューごとに定めた閾値を記憶する閾値記憶手段と、前記読出データ量検知手段により検知された前記データ量と前記閾値記憶手段に記憶された前記パケットを出力した前記キューの前記閾値とに応じて当該キューの前記優先順位を前記キューごとに算出して前記優先順位記憶手段に書き込む優先順位算出手段とを備える請求項７に記載のパケット転送回路。
【請求項９】
前記優先順位算出手段は、前記読出データ量検知手段により検知された前記データ量が前記閾値記憶手段に記憶した前記データ量を出力した前記キューに定めた前記閾値となる時に、対応する前記キューの前記優先順位を所定の順位になるように前記出力データ量に応じて前記優先順位を下げて算出する請求項８に記載のパケット転送回路。
【請求項１０】
前記閾値記憶手段は、前記キューの最低保証帯域に対応する閾値を記憶する第１の個別閾値回路と、前記第１の個別閾値回路が記憶した前記閾値以上の値の閾値を記憶する第２の個別閾値回路とを備え、前記優先順位修正手段は、前記読出データ量検知手段により検知された前記データ量が前記第１の個別閾値回路が記憶した前記閾値となった場合に前記優先順位を最低保証帯域以上の前記データ量を出力した前記キューのために定めた第１の優先順位まで下げて前記優先順位記憶手段に書き込み、かつ、前記読出データ量検知手段により検知された前記データ量が前記第２の個別閾値回路が記憶した前記閾値となった場合に前記第１の優先順位より低い第２の優先順位まで下げて前記優先順位記憶手段に書き込む請求項９に記載のパケット転送回路。
【請求項１１】
前記最優先順位検知手段は、前記優先順位記憶手段が記憶した前記優先順位と前記書込キュー情報に応じて前記パケットを記憶した前記キューの前記優先順位のうち最も高い前記優先順位を前記収容手段ごとに検知する優先キュー検知手段と、前記優先キュー検知手段が検知した前記優先順位を保持可能な優先順位保持手段と、を有する請求項１０に記載のパケット転送回路。
【請求項１２】
前記優先順位保持手段は、前記優先キュー検知手段が検知した前記優先順位を前記収容手段ごとに保持するための優先度保持回路を備える請求項１１に記載のパケット転送回路。
【請求項１３】
前記書込キュー情報生成手段は、前記収容手段ごとに前記書込キュー情報を記憶した書込キュー情報記憶手段と、前記キューのパケット書き込み状況に応じて前記書込キュー情報記憶手段に記憶した前記書込キュー情報を更新する書込キュー情報更新手段と、を有する請求項１２に記載のパケット転送回路。
【請求項１４】
前記書込キュー情報更新手段は、前記パケットの出力を完了する前記キューを前記収容手段ごとに検知する完了キュー検知手段を備え、前記完了キュー検知手段の検知に応じ前記書込キュー情報を更新する請求項１３に記載のパケット転送回路。
【請求項１５】
前記優先順位決定手段は、前記完了キュー検知手段の検知に応じて前記パケットを出力した前記キューの前記優先順位を新たに決定する請求項１４に記載のパケット転送回路。
【請求項１６】
前記優先順位書込手段は、前記完了キュー検知手段の検知に応じ前記優先順位を前記優先順位記憶手段に書き込んで記憶させる請求項１５に記載のパケット転送回路。
【請求項１７】
前記最優先順位検知手段は、前記完了キュー検知手段の検知に応じて前記パケットが書き込まれている前記キューの前記優先順位のうち最も高い前記優先順位を新たに検知して前記読出キュー決定手段に新たな前記優先順位を通知する１６に記載のパケット転送回路。
【請求項１８】
前記読出キュー決定手段は、前記最優先順位検知手段が新たに通知した前記優先順位に応じて前記パケットを読み出すべきキューを新たに決定する請求項１７に記載のパケット転送回路。
【請求項１９】
前記閾値記憶手段に前記閾値を書き込む閾値書込手段をさらに備え、前記閾値記憶手段は、前記閾値を変更可能に記憶するものであって、前記閾値書込手段から前記キューごとの前記閾値が書き込まれる請求項１７に記載のパケット転送回路。
【請求項２０】
前記優先順位が前記第２の優先順位以下となった場合に前記パケットが出力できる前記キューを決定して前記読出キュー決定手段に指示する決定指示手段をさらに備え、前記読出キュー決定手段は、前記第２の優先順位より高い前記キューが無い場合に前記決定指示手段が指示する前記キューのうち前記パケットを記憶している前記キューを読み出すべき前記キューとして決定する請求項１９に記載のパケット転送回路。
【請求項２１】
それぞれ対応する出力ポートに接続されパケットの書き込みと読み出しとが可能である複数のキューに前記パケットを収容する複数の収容手段と、入力ポートに入力される前記パケットを振り分けて前記収容手段に収容させる入力手段と、前記パケットを読み出すべき前記キューを前記収容手段ごとに決定し当該決定したキューから前記パケットを読み出して前記出力ポートへ出力させる読出制御手段とを備え、前記読出制御手段は、前記パケットが書き込まれている前記キューを示す書込キュー情報を前記収容手段ごとに生成する書込キュー情報生成手段と、前記キューから前記パケットを出力する優先順位を決定するパケット出力選択手段と、前記書込キュー情報と前記優先順位とに応じて前記パケットを読み出すべき前記キューを前記収容手段ごとに決定する読出キュー決定手段と、を有し、前記パケット出力選択手段は、前記パケットが記憶されている前記キューを検知する記憶検知手段と、前記パケットを出力する前記優先順位を前記キューごとに決定する優先順位決定手段と、前記優先順位決定手段により決定された前記優先順位に応じて前記記憶検知手段により検知された前記キューの中から前記パケットを出力させるべき前記キューを決定する選択決定手段と、前記キューから出力される前記パケットの出力データ量を計測する出力量計測手段と、前記出力量計測手段によって計測された前記出力データ量に基づいて１又は複数の前記キューを有する複数のグループ収容手段の各々の前記出力データ量を累積して保持する複数の累積保持部と、を有し、前記累積保持手段によって保持された前記キューの前記出力データ量の累積値が所定の閾値以上となった場合に当該前記累積保持手段に対応する前記キューの前記優先順位を所定の順位まで前記優先順位決定手段が下げるパケット転送回路。
【請求項２２】
前記優先順位選択手段は、複数の前記キューのそれぞれの前記優先順位を記憶することが可能な優先順位記憶手段と、前記優先順位記憶手段に前記キューのそれぞれの前記優先順位を書き込む優先順位書込手段と、を有し、前記優先順位書込手段は、前記累積保持手段ごとに定められた前記所定の閾値を記憶する累積閾値記憶手段と、前記累積保持手段によって保持されている前記キューの前記出力データ量の前記累積値が前記累積閾値記憶手段に記憶されている前記所定の閾値以上となった場合に前記優先順位決定手段により前記所定の順位まで下げられた前記キューの前記優先順位を前記優先順位記憶手段に書き込む累積書込手段と、を有し、前記選択決定手段は、前記優先順位記憶手段に記憶されている前記優先順位の中で最も高い前記優先順位に対応する前記キューを前記パケットの出力が行われるべき前記キューとして選択する請求項２１に記載のパケット転送回路。
【請求項２３】
前記パケットを出力する前記キューに対応し前記出力量計測手段によって計測された前記出力データ量のうちの対応する前記キューの前記出力データ量を保持する複数の個別保持手段とを有し、前記個別保持手段によって保持された前記キューの前記出力データ量が閾値以上となった場合に前記優先順位決定手段が前記キューの前記優先順位を所定の順位まで下げる請求項２２に記載のパケット転送回路。
【請求項２４】
前記個別保持手段ごとに定められた前記所定の閾値を記憶する個別閾値記憶手段と、前記個別保持手段によって保持されている前記キューの前記出力データ量が前記個別閾値記憶手段に記憶されている前記所定の閾値以上となった場合に前記優先順位決定手段によって前記所定の順位まで下げられた前記キューの前記優先順位を前記優先順位記憶手段に書き込む個別書込手段と、を有する請求項２３に記載のパケット転送回路。
【請求項２５】
前記個別保持手段によって保持されている前記キューの前記出力データ量が前記所定の閾値以上となった場合に前記キューの前記優先順位を前記所定の順位まで下げるよう計算を行う優先順位計算手段を有し、前記優先順位決定手段は前記優先順位計算手段による計算結果に応じて前記優先順位を決定する請求項２４に記載のパケット転送回路。
【請求項２６】
前記個別閾値記憶手段に前記所定の閾値として前記キューの最低保証帯域に対応する第１の閾値と前記第１の閾値より大きい第２の閾値とが記憶され、前記個別保持手段によって保持されている前記キューの前記出力データ量が前記第１の閾値以上となった場合に前記優先順位決定手段が前記キューの前記優先順位を所定の第１の順位まで下げ、かつ、前記個別保持手段によって保持されている前記キューの前記出力データ量が前記第２の閾値以上となった場合に前記優先順位決定手段が前記キューの前記優先順位を前記所定の第１の順位より低い第２の所定の順位まで下げる請求項２５に記載のパケット転送回路。
【請求項２７】
前記選択決定手段は、前記記憶検知手段によって検知された前記キューのうちで最も前記優先順位が高い前記キューを検出する優先キュー検出手段と、前記優先キュー検出手段によって検出された前記キューの中から当該選択決定手段が選択すべき前記キューを決定するキュー決定手段と、を有する請求項２６に記載のパケット転送回路。
【請求項２８】
前記キュー決定手段は、前記優先キュー検出手段によって検出された前記キューを示す決定キュー情報を生成する決定キュー情報生成手段と、前記決定キュー情報生成手段によって生成された前記決定キュー情報を保持することが可能な決定キュー情報保持手段と、を有し、前記優先キュー検出手段によって前記決定キュー情報保持手段に保持されている前記決定キュー情報が示す前記キュー以外の前記キューが検出された場合に前記決定キュー情報生成手段が検出された前記キューを示す前記決定キュー情報を生成する請求項２７に記載のパケット転送回路。
【請求項２９】
複数の前記キューはそれぞれの前記優先順位により序列付けられており、前記決定キュー情報生成手段は、前記決定キュー情報保持手段に保持されている前記決定情報が示す前記キューを前記序列の最下位とする前記決定キュー情報を生成し、前記検出された前記キューを前記序列の最上位とする前記決定キュー情報を生成する請求項２８に記載のパケット転送回路。
【請求項３０】
前記累積保持手段のそれぞれと前記キューとの対応関係を示すキュー判別情報が記憶されるキュー判別記憶手段を有し、前記累積保持手段によって保持されている前記キューの前記出力データ量の前記累積値が前記累積閾値記憶手段に記憶されている前記所定の閾値以上となった場合に前記累積書込手段が前記キュー判別情報を参照して前記累積保持手段との対応関係を有する前記キューの前記優先順位を前記優先順位記憶手段に書き込む請求項２９に記載のパケット転送回路。
【請求項３１】
それぞれ対応する出力ポートに接続されパケットの書き込みと読み出しとが可能である複数のキューを有する複数の収容手段の前記複数のキューに前記パケットを収容する時に入力される前記パケットを振り分けて前記収容手段に収容させる入力ステップと、前記パケットを読み出すべき前記キューを前記収容手段ごとに決定し当該決定したキューから前記パケットを読み出して前記出力ポートへ出力させる読出制御ステップと、を備え、前記読出制御ステップは、前記パケットが書き込まれている前記キューを示す書込キュー情報を前記収容手段ごとに生成する書込キュー情報生成ステップと、前記パケットを読み出す優先順位を前記キューごとに決定する優先順位決定ステップと、前記書込キュー情報と前記優先順位とに応じて前記パケットを読み出すべき前記キューを前記収容手段ごとに決定する読出キュー決定ステップと、を有するパケット転送方法。
【請求項３２】
それぞれ対応する出力ポートに接続されパケットの書き込みと読み出しとが可能である複数のキューを有する複数の収容手段の前記複数のキューに前記パケットを収容する時に入力される前記パケットを振り分けて前記収容手段に収容させる入力ステップと、前記パケットを読み出すべき前記キューを前記収容手段ごとに決定し当該決定したキューから前記パケットを読み出して前記出力ポートへ出力させる読出制御ステップと、を備え、前記読出制御ステップは、前記パケットが書き込まれている前記キューを示す書込キュー情報を前記収容手段ごとに生成する書込キュー情報生成ステップと、前記パケットを読み出す優先順位を前記キューごとに決定する優先順位決定ステップと、前記書込キュー情報と前記優先順位とに応じて前記パケットを読み出すべき前記キューを前記収容手段ごとに決定する読出キュー決定ステップと、を具備するパケット転送方法をコンピュータに実行させるパケット転送プログラム。
【発明の詳細な説明】
技術分野
本発明は、複数のキューに記憶したパケットを出力するパケット転送回路及びパケット転送方法に関するものである。
背景技術
近年、パケット転送装置のスループット向上を目指し、ＶＯＱ（Ｖｉｒｔｕａｌ  Ｏｕｔｐｕｔ  Ｑｕｅｕｉｎｇ）法を採用したパケット転送装置が用いられている。
ＶＯＱ法によるパケット転送装置は、パケットを受信する複数の受信部とパケットを送信する複数の送信部とを具備し、受信部に備えたＶＯＱへ受信したパケットをキューイングする構成となっている。
また、この種の従来の装置として、特開２００１−７８２２号公報に記載のパケット転送装置が使用されている。このパケット転送装置は、図１に示すように、受信部１に各送信部２に対応するＶＯＱを持つＶＯＱＭ（ＶＯＱ  Ｍｏｄｕｌｅ）３が備えられている。
ＶＯＱＭ３は、ＶＯＱがパケットをキューイングすると、図２に示すように、各送信部に対応するＳＭ（Ｓｃｈｅｄｕｌｅｒ  Ｍｏｄｕｌｅ）へパケットをキューイングしていることを伝える。各ＳＭは、パケットをキューイングしているいずれかのＶＯＱＭ３に、パケットを送信部２と受信部１との間に設けられたクロスバスイッチ４に出力するよう通知する。当該ＳＭに対応する送信部２とパケットをクロスバスイッチ４に出力するよう通知したＶＯＱＭ３を備える受信部１とが接続されるようにクロスバコントロール５が制御する。
クロスバスイッチ４の切り替えの機会は、一定の周期のタイムスロットごとに訪れるようになっている。各々のＳＭは、図３に示すように、複数のタイムスロットからなるフレームごとに次のフレームの各タイムスロットでパケットを出力するＶＯＱを決定する。図３は、４つの送信部２と４つの受信部１とを具備するパケット転送装置のスケジューラの動作を示している。図３には、１フレームは、４タイムスロットからなり、４個のＳＭ（ＳＭ１〜ＳＭ４）が次のフレームの各タイムスロットでパケットを出力するＶＯＱを決定する様子が示されている。フレームＦ１のタイムスロットＴ１では、ＳＭ１はフレームＦ２のタイムスロットＴ５にて出力するＶＯＱを決定している。
上述の通り、ＳＭ１は、タイムスロットＴ１でフレームＦ２のタイムスロットＴ５でパケットを出力するＶＯＱを決定すると、ＳＭ２に決定したＶＯＱを伝える。また、ＳＭ１には、タイムスロットＴ８でどのＶＯＱのパケットを出力するようにＳＭ４が決定したかが伝えられる。
ＳＭ１は、タイムスロットＴ２でフレームＦ２のタイムスロットＴ８でパケットを出力するＶＯＱを、ＳＭ４が伝えたＶＯＱ以外のＶＯＱのうちからの決定し、ＳＭ４から伝えられたＶＯＱとＳＭ１がタイムスロットＴ２にて決定したＶＯＱをＳＭ２に伝える。
このように、各ＳＭは、各フレームの各タイムスロットで、次のフレームの各タイムスロットにおいてパケットを出力するＶＯＱを決定し、下のＳＭに伝えるようになっている。この時に、先に上のＳＭが決定したＶＯＱも伝えられるように、ＳＭ同士を循環するパイプライン状に接続した構成になっている。同一のタイムスロットに同一の受信部１に備えられた複数のＶＯＱがクロスバスイッチ４へパケットを出力しないように、各タイムロットにおいて既にパケットを出力するよう決定したＶＯＱを伝えあう。
各ＳＭの決定はＶＯＱＭに伝えられる。各ＶＯＱＭは、どのタイムスロットでパケットを出力するよう決定されたかをレジスタに記憶する。そして、各ＶＯＱＭは、当該レジスタを参照しパケットを出力すべきタイムスロットでＶＯＱからクロスバスイッチへパケットを出力するようになっている。
図２、３の例は、４つの送信部２と４つの受信部１とを具備するパケット転送装置の例である。図３に示すように、ＳＭ１は、タイムスロットＴ１ではタイムスロットＴ５でＳＭ１に対応する送信部と接続する受信部を決定している。この時に、ＳＭ２〜ＳＭ３は、各ＳＭに対応する送信部とタイムスロットＴ５で接続する受信部の決定を行っていないので、ＳＭ１は、タイムスロットＴ５での決定を最優先に行うことができる。
タイムスロットＴ１では、ＳＭ２〜ＳＭ４も同様に各々に対応する送信部と接続する受信部の決定を最優先で行うタイムスロットがある。ＳＭ２はタイムスロットＴ６での優先権を持ち、ＳＭ３はタイムスロットＴ７での優先権を持ち、ＳＭ４はタイムスロットＴ８での優先権を持つ。タイムスロットＴ２では各々のＳＭは第２位の優先権をもつタイムスロットで各々に対応する送信部と接続する受信部の決定を行って、タイムスロットＴ４まで順次優先権を低下させながら各タイムスロットで各々に対応する送信部と接続する受信部の決定を行うようになっている。
上述のとおり、送信部と受信部の接続の決定をＳＭと同数のタイムスロットからなるフレーム単位で、各々のＳＭは最高の優先権から最低の優先権をもつタイムスロットにおける決定を行うので、フレーム単位で各々のＳＭは均等に対応する送信部と接続する受信部の決定を行うことができる。
また、パケット出力すべきキューの決定を行う従来の技術として、例えば、特開２００１−１６８８６９号公報に記載されているパケット転送装置が知られている。特開２００１−１６８８６９号公報には、最低帯域保証、各ユーザ間における空き帯域の共用及び公平性の確保などを実現する帯域共用制御方法及びパケット転送装置が開示されている。
図４は、特開２００１−１６８８６９号公報に記載されている従来のパケット転送装置の構成を示すブロックである。図５は、従来のパケット転送装置における制御アルゴリズムを説明するための図である。
図４に示すように、複数の入力路１１のそれぞれからのセルは、多重化された後に、ＶＰＩ／ＶＣＩ変換テーブル１４で、多重化状態のセル２２のそれぞれから出力情報としてのＶＰＩ（Ｖｉｒｔｕａｌ  Ｐａｔｈ  Ｉｄｅｎｔｉｆｉｅｒ）及びＶＣＩ（Ｖｉｒｔｕａｌ  Ｃｈａｎｎｅｌ  Ｉｄｅｎｔｉｆｉｅｒ）が抽出された上で、入力共用グループ／コネクション情報２３に変換された状態として書き込み制御部１５に与えられる。この入力共用グループ／コネクション情報２３に基づき、書き込み制御部１５でセルバッファ１３への書き込みアドレスが作成されることによって、多重化状態のセル２２のそれぞれは、セルバッファ１３に入力共用グループごと、かつ、コネクションごとに一時蓄積される。
また、書き込み制御部１５からの書き込みアドレスによって、キュー先読みフラグテーブル１６上には、入力共用グループごと、かつ、コネクションごとに各セル２２がセルバッファ１３上に一時蓄積されているか否かを示す情報が、キュー先読み情報１７として記憶される。
以上のようにして、セルバッファ１３上には各セル２２が一時蓄積された後に、各セル２２が、読み出し制御部１７からの読み出しアドレスによりそのセルバッファ１３から読み出された上で、所望の出力路１２に出力されるべく分離される。
読み出し制御部１７では、出力共用グループ情報２５とコネクション情報２６からセルバッファ１３への読み出しアドレスが生成される。出力共用グループ情報２５は、一定周期で巡回しているＷＲＲスケジューラ１９からの読み出しアドレス２４によって、ＷＲＲ（重み付けラウンドロビン：Ｗｅｉｇｈｔｅｄ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）１テーブル２０から読み出し制御部１７に供給される。また、その出力共用グループ情報２５を読み出しアドレスとして、ＷＲＲ２テーブル２１からは、その出力共用グループ内コネクションセル出力許容情報２８が読み出される。
また、出力共用グループ情報２５を読み出しアドレスとして、キュー先読みフラグテーブル１６からは、その出力共用グループ内のコネクションごとにセルが一時蓄積されているか否かの情報が、キュー先読み情報２７として読み出される。次に、このキュー先読み情報２７と出力共用グループ内のコネクションセル出力許容情報２８からキュー検索部１８で出力コネクション情報２６が作成される。そのキュー検索部１８には、プライオリティエンコーダを用いた出力コネクション決定部１８ａと、プライオリティエンコード結果を検索履歴として記憶しておくための検索履歴記憶部１８ｂとが備えられている。
なお、図５に示すように、従来の技術における制御アルゴリズムのスケジューリング方式は、ＷＲＲスケジューラ１９、ＷＲＲ１テーブル２０、ＷＲＲ２テーブル２１及びキュー先読みフラグテーブル１６を含む。
すなわち、特開２００１−１６８８６９号公報に開示されているパケット転送装置においては、一定周期で巡回しているＷＲＲスケジューラ１９がＷＲＲ１テーブル２０から出力共用グループ情報２５を読み出す。そして、このパケット転送装置においては、その情報に基づき、ＷＲＲ２テーブル２１から出力共用グループ内のコネクションセル出力許容情報２８が読み出されて、キュー検索部１８の出力コネクション決定部１８ａが出力すべきキューを決定する。
しかしながら、特開２００１−７８２２号公報に記載のパケット転送装置においては、１フレームを構成するタイムスロットの数がＳＭの数に等しいため、受信部及び送信部が増加すると１フレームを構成するタイムスロットの数も増加するという問題がある。すなわち、特開２００１−７８２２号公報に記載のパケット転送装置においては、受信部及び送信部の増加に伴い１フレームの時間も延びるため、各ＳＭがパケットを出力するＶＯＱを決定する時間もまた延びるから、その間パケットがＶＯＱから出力されないので遅延時間が増大するという問題がある。
また、特開２００１−１６８８６９号公報に記載のパケット転送装置においては、２種類のテーブルから順番に情報を読み出すことによって初めて出力すべきキューの検索を開始可能とする構成であるため、キュー検索部７８が２種類のテーブルの読み出しが完了するまで検索を待つ必要があるから、キューの決定までに時間がかかってしまうという問題がある。また、特開２００１−１６８８６９号公報に記載のパケット転送装置においては、キューからパケットを出力させる前に予めＷＲＲスケジューラ１９の動作を開始させる部を設けなければならないという問題がある。
発明の開示
本発明の目的は、以上のような実情に鑑みて成されたものであり、各送信部と各受信部との接続を均等に決定して受信部及び送信部の数にかかわらず遅延時間が短い高速なパケット転送回路及びパケット転送方法を提供することである。
また、本発明の他の目的は、複数のキューをグループ分けして管理する時に２種類のテーブルから順番に情報を読み出すことなく簡単な構成によってパケットを出力すべきキューを高速で選択できるパケット転送回路及びパケット転送方法を提供することである。
本発明の一形態によれば、パケット転送回路は、それぞれ対応する出力ポートに接続されパケットの書き込みと読み出しとが可能である複数のキューに前記パケットを収容する複数の収容手段と、入力ポートに入力される前記パケットを振り分けて前記収容手段に収容させる入力手段と、前記パケットを読み出すべき前記キューを前記収容手段ごとに決定し当該決定したキューから前記パケットを読み出して前記出力ポートへ出力させる読出制御手段とを備え、前記読出制御手段は、前記パケットが書き込まれている前記キューを示す書込キュー情報を前記収容手段ごとに生成する書込キュー情報生成手段と、前記パケットを読み出す優先順位を前記キューごとに決定する優先順位決定手段と、前記書込キュー情報と前記優先順位とに応じて前記パケットを読み出すべき前記キューを前記収容手段ごとに決定する読出キュー決定手段と、を有する。
本発明のさらに他の形態によれば、パケット転送方法は、それぞれ対応する出力ポートに接続されパケットの書き込みと読み出しとが可能である複数のキューを有する複数の収容手段の前記複数のキューに前記パケットを収容する時に入力される前記パケットを振り分けて前記収容手段に収容させる入力ステップと、前記パケットを読み出すべき前記キューを前記収容手段ごとに決定し当該決定したキューから前記パケットを読み出して前記出力ポートへ出力させる読出制御ステップと、を備え、前記読出制御ステップは、前記パケットが書き込まれている前記キューを示す書込キュー情報を前記収容手段ごとに生成する書込キュー情報生成ステップと、前記パケットを読み出す優先順位を前記キューごとに決定する優先順位決定ステップと、前記書込キュー情報と前記優先順位とに応じて前記パケットを読み出すべき前記キューを前記収容手段ごとに決定する読出キュー決定ステップと、を有する。
本発明のさらに他の形態によれば、パケット転送プログラムは、それぞれ対応する出力ポートに接続されパケットの書き込みと読み出しとが可能である複数のキューを有する複数の収容手段の前記複数のキューに前記パケットを収容する時に入力される前記パケットを振り分けて前記収容手段に収容させる入力ステップと、前記パケットを読み出すべき前記キューを前記収容手段ごとに決定し当該決定したキューから前記パケットを読み出して前記出力ポートへ出力させる読出制御ステップと、を備え、前記読出制御ステップは、前記パケットが書き込まれている前記キューを示す書込キュー情報を前記収容手段ごとに生成する書込キュー情報生成ステップと、前記パケットを読み出す優先順位を前記キューごとに決定する優先順位決定ステップと、前記書込キュー情報と前記優先順位とに応じて前記パケットを読み出すべき前記キューを前記収容手段ごとに決定する読出キュー決定ステップと、を具備するパケット転送方法をコンピュータに実行させる。
発明を実施するための最良の形態
以下、本発明の実施の形態について、添付図面を参照して詳細に説明する。
（実施の形態１）
以下、本発明のパケット転送回路及びパケット転送方法に関する実施の形態１について、図面を参照して具体的に説明する。
図６は、本実施の形態１に係るパケット転送回路の構成を示すブロック図である。図６に示すように、本実施の形態１に係るパケット転送回路１０９における入力部１９１は、パケット転送回路１０９が具備する各々の出力ポートに収容部１９３を介し接続されている。入力部１９１は、受信したパケットを該パケットの宛先に対応する出力ポートに接続された収容部１９３に渡し、収容部１９３が該パケットを送信できるように構成されている。
上述の構成により、パケット転送回路１０９は、入力部１９１が互いに影響を与え合うことなく受信したパケットを送信すべき出力ポートに接続された複数の収容部１９３へ渡すことができ、かつ、複数の収容部１９３の各々が互いに影響を与え合うことなく送信すべきパケットを送信可能な構成であるから、高いスループットを実現可能となっている。
パケットの宛先は、パケット転送回路１０９が具備する複数の出力ポートのいずれかに対応している。入力部１９１に備えた受信パケット振り分け部１９１１は、受信したパケットの宛先に対応する出力ポートに接続された収容部１９３へ受信したパケットを渡す。
収容部１９３は、入力部１９１が渡すパケットを記憶する複数のキュー１９３１を備えている。各々のキュー１９３１には、出力ポートへパケットを渡す優先順位が定められている。収容部１９３は、パケットを書込んだキューを示す書込キュー通知情報１９５を読出制御部１９４へ通知する。読出制御部１９４は書込キュー通知情報１９５に基づいて収容部１９３ごとにパケットを読み出すべきキュー１９３１を決定し、決定したキュー１９３１を示す読出キュー指示情報１９８を収容部１９３ごとに指示する。収容部１９３は、指示された読出キュー指示情報１９８が示すキュー１９３１から出力ポートへパケットを送信する。そして、収容部１９３は、パケットの送信が完了すると、読み出したデータ量を読出量情報１９７として読出制御部１９４へ通知する。
また、閾値書込部１１０及び決定指示部１１１は、パケット転送回路１０９に対する外部からの設定を読出制御部１９４に通知する。パケット転送回路１０９は、各々のキュー１９３１に対する閾値１１０１を設定し、また、キュー１９３１からの読出しデータ量が第２の閾値を超えた場合にパケットの読出しを停止するか否かの決定指示１１１１を設定することができる。
図７〜図１１に、パケット転送回路１０９の具体的な構成を示す。ここで、図７〜図１１に示す各種の機能ブロックは、ハードウエア及びソフトウエアのいずれで構築しても良い。本例では、図７〜図１１に示す各種の機能ブロックは、メモリ装置で構成される各種記憶部を除いて、ソフトウエアで構築しているものとして説明する。すなわち、後述する各機能ブロックと同じ動作をコンピュータに実行させるプログラムがシステム上の所定の場所に格納されていて、コンピュータがプログラムを読み出して適宜実行するものとする。また、全ての機能ブロックをソフトウエアで構築するのではなく、高速処理が要求される機能などのハードウエア回路で構成した方がシステムパフォーマンスの面で優れているのであればシステム設計に応じてソフトウエアとハードウエアを適宜組み合わせてシステム設計することも可能である。
図７は、読出制御部１９４の構成を示すブロック図である。図７に示すように、読出制御部１９４は、書込キュー情報生成部１９４１、優先順位決定部１９４０及び読出キュー決定部１９４２を有している。書込キュー情報生成部１９４１は、パケットが書込まれているキュー１９３１を示す書込キュー情報１９４１２を収容部１９３ごとに生成する。優先順位決定部１９４０は、パケットを読み出す優先順位をキュー１９３１ごとに決定する。読出キュー決定部１９４２は、書込キュー情報１９４１２と優先順位とに応じパケットを読み出すべきキューを収容部１９３ごとに決定する。
書込キュー情報生成部１９４１は、書込キュー情報記憶部１９４１４及び書込キュー情報更新部１９４１１を有している。書込キュー情報記憶部１９４１４は、収容部１９３ごとに書込キュー情報１９４１２を記憶する。書込キュー情報更新部１９４１１は、キュー１９３１のパケット書き込み状況に応じて書込キュー情報記憶部１９４１４に記憶した書込キュー情報１９４１２を更新する。書込キュー情報更新部１９４１１は、パケットの出力を完了するキュー１９３１を収容部１９３ごとに検知する完了キュー検知部１９４１３を備えている。
書込キュー情報更新部１９４１１は、収容部１９３から書き込みを行ったキューを示す書込キュー通知情報１９５を通知されると、書込キュー情報記憶部１９４１４から該当する収容部１９３の書込キュー情報１９４１２を取得する。そして、書込キュー情報更新部１９４１１は、書込キュー通知情報１９５が示すキュー１９３１のパケット格納状況のみを更新して書込キュー情報記憶部１９４１４に対して更新した書込キュー情報１９４１２を通知する。
完了キュー検知部１９４１３は、パケットを出力していたキュー１９３１を収容する収容部１９３からパケットの読出し完了と読出し完了後にそのキュー１９３１にパケットが残っているかどうかを示す読出完了通知情報１９６を通知される。完了キュー検知部１９４１３は、読出完了通知情報１９６を通知されると、読出キュー決定部１９４２から収容部１９３ごとに通知される決定キュー情報１９４７からパケットの出力を完了するキュー１９３１を収容部１９３ごとに検知する。そして、完了キュー検知部１９４１３は、そのキュー１９３１と収容部１９３及び読出完了通知情報１９６に応じたキュー１９３１の書き込み状況を書込キュー情報更新部１９４１１に対して通知する。また、完了キュー検知部１９４１３は、パケットを出力していたキュー１９３１からの読出しが完了することを完了キュー検知情報１９９として収容部１９３ごとに書込キュー情報更新部１９４１１及び優先順位決定部１９４０に対し通知する。
書込キュー情報更新部１９４１１は、完了キュー検知情報１９９を通知されると、書込キュー情報記憶部１９４１４から該当する収容部の書込キュー情報１９４１２を取得する。そして、書込キュー情報更新部１９４１１は、完了キュー検知部１９４１３の検知に応じパケットの出力を完了したキュー１９３１のパケット格納状況のみを更新して書込キュー情報記憶部１９４１４に対して更新した書込キュー情報１９４１２を通知する。
書込キュー情報記憶部１９４１４は、書込キュー情報更新部１９４１１から更新された書込キュー情報１９４１２を通知されると、収容部１９３ごとに更新された書込キュー情報１９４１２を記憶する。そして、書込キュー情報記憶部１９４１４は、記憶した書込キュー情報１９４１２を収容部１９３ごとに読出キュー決定部１９４２及び優先順位決定部１９４０へ通知する。
優先順位決定部１９４０は、優先順位記憶部１９４６、優先順位書込部１９４４及び最優先順位検知部１９４５を備えている。優先順位記憶部１９４６は、収容部１９３ごとに各キュー１９３１の優先順位を判別可能に記憶する。優先順位書込部１９４４は、先順位記憶部１９４６にキュー１９３１の各々の優先順位を収容部１９３ごとに書込んで記憶させる。最優先順位検知部１９４５は、書込キュー情報１９４１２と優先順位記憶部１９４６に記憶した優先順位とに応じパケットが書込まれているキュー１９３１の優先順位のうち最も高い優先順位を収容部１９３ごとに検知して読出キュー決定部１９４２に通知する。
図８は、優先順位書込部１９４４の構成を示したブロック図である。同８に示すように、優先順位書込部１９４４は、読出データ量検知部１９４４２及び優先順位修正部１９４４３を備えている。読出データ量検知部１９４４２は、各キュー１９３１から読み出されたデータ量を収容部１９３ごとに検知する。優先順位修正部１９４４３は、読出データ量検知部１９４４２により検知されたデータ量がキュー１９３１ごとに定めた閾値になった場合に、そのキュー１９３１の優先順位が所定の順位まで下がるように修正して優先順位記憶部１９４６に書込む。
読出データ量検知部１９４４２は、完了キュー検知情報１９９から決定キュー情報１９４７の示すキュー１９３１の読出データ量を検知する。そして、読出データ量検知部１９４４２は、その読出データ量と、パケットを出力していたキュー１９３１を収容する収容部１９３から通知される読出量情報１９７とを加算したデータ量を優先順位修正部１９４４３に通知する。
優先順位修正部１９４４３は、読出データ量検知部１９４４２により検知されたデータ量が各キュー１９３１ごとに定めた閾値になった場合に、そのキュー１９３１の優先順位が所定の順位まで下がるように修正して前記優先順位記憶部１９４６に書き込む。図８の閾値記憶部１９４４６は、キュー１９３１ごとに定めた閾値を記憶する。同じように、図８の優先順位算出部１９４４５は、読出データ量検知部１９４４２により検知されたデータ量と閾値記憶部１９４４６に記憶されたパケットを出力したキュー１９３１に応じてそのキューの優先順位を算出して優先順位記憶部１９４６に書き込む。
優先順位算出部１９４４５は、読出データ量検知部１９４４２により検知された図１１のグラフの横軸に示すデータ量が閾値記憶部１９４４６に記憶したデータ量が出力したキュー１９３１に定めた閾値（Ｔｈ１）になる時に、対応する前記キュー１９３１の優先順位を所定の順位（図１１のＢ）になるようにその出力データ量に応じて優先順位を下げて算出する。図示する例では、キュー１９３１が出力したデータ量が０のとき優先順位はＡに示す値となっている。
図８に示す各々の閾値記憶部１９４４６は、第１の個別閾値回路１９４４６ａ及び第２の個別閾値回路１９４４６ｂを有している。第１の個別閾値回路１９４４６ａは、キュー１９３１の最低保証帯域に対応する閾値を記憶する。キュー１９３１ごとの第２の個別閾値回路１９４４６ｂは、第１の個別閾値回路１９４４６ａが記憶した閾値以上の値の閾値を記憶する。優先順位修正部１９４４３は、読出データ量検知部１９４４２により検知されたデータ量が第１の個別閾値回路１９４４６ａにより記憶された閾値（図１１のＴｈ１）となった場合に、最低保証帯域以上のデータを出力した前記キュー１９３１のために定めた第１の優先順位（図１１のＢ）まで優先順位を下げて優先順位記憶部１９４６に書き込む。また、優先順位修正部１９４４３は、読出データ量検知部１９４４２により検知されたデータ量が第２の個別閾値回路１９４４６ｂにより記憶された閾値（図１１のＴｈ２）となった場合に、第１の優先順位より低い第２の優先順位（図１１のＣ）まで優先順位を下げて前記優先順位記憶部１９４６に書き込む。
優先順位修正部１９４４３は、パケット収容装置１０９に対する決定指示１１１の設定により、第２の個別閾値回路１９４４６ｂが記憶した閾値となったキュー１９３１の出力を停止する場合には、図１１のＤ１に示すように優先順位を出力停止用の優先順位まで下げる。第２の個別閾値回路１９４４６ｂが記憶した閾値を超えてもパケットを出力許可する場合には、優先順位修正部１９４４３は、図１１のＤ３のように優先順位を変化させてもよいが、好ましくは図１１のＤ２のように出力データ量に応じて優先順位を下げるようにすると、各キュー１９３１は均等にパケットを出力できる。
また、閾値記憶部１９４４６は、閾値を変更可能に記憶するものであり、パケット転送回路１０９は、閾値記憶部１９４４６に閾値を書き込む閾値書込部１１０をさらに備えた構成になっている。
前述の最優先順位検知部１９４５は、図９に示すように、書込キュー情報１９４１２と優先順位記憶部１９４６に記憶した優先順位とに応じパケットが書き込まれているキュー１９３１の優先順位のうち最も高い優先順位を収容部１９３ごとに検知して読出キュー決定部１９４２に通知するものである。
優先キュー検知部１９４５１は、優先順位記憶部１９４６が記憶した優先順位と書込キュー情報１９４１２に応じてパケットを記憶したキュー１９３１の優先順位のうち最も高い優先順位を収容部１９３ごとに検知する。また、最優先順位保持部１９４５５は、優先キュー検知部１９４５１が検知した優先順位を保持可能である。
最優先順位保持部１９４５５は、優先キュー検知部１９４５１が検知した優先順位を収容部１９３ごとに保持するための優先度保持回路１９４５６１を備えているので、読出しキュー決定部１９４２は、収容部１９３ごとに読み出すべきキュー１９３１を決定することができる。また、最優先順位検知部１９４５は、前述の完了キュー検知部１９４１３の検知に応じてパケットが書き込まれているキュー１９３１の優先順位のうち最も高い優先順位を新たに検知して読出キュー決定部１９４２に新たな優先順位を通知する。
前述の読み出しキュー決定部１９４２は、図１０に示すように、最優先順位検知部１９４５の通知と書込キュー情報１９４１２とに応じてパケットを読み出すべきキュー１９３１を収容部１９３ごとに決定する。
キュー検出部１９４２１は、優先順位決定部１９４０が決定した優先順位に応じて最優先順位検知部１９４５により収容部１９３ごとに通知される最優先順位情報１９４９に基づき、書込キュー情報１９４１２が示すキュー１９３１のうちで最も優先順位が高いキュー１９３１を収容部１９３ごとに検出する。
最優先順位検知部１９４５は、完了キュー検知部１９４１３の検知に応じパケットが書き込まれているキュー１９３１の優先順位のうち最も高い優先順位を新たに検知して読出キュー決定部１９４２に新たな優先順位を通知するので、パケットの出力が完了したときに読出キュー決定部１９４２は新たにパケットを読み出すキュー１９３１を決定する。
また、キュー選択部１９４２２は、キュー検出部９４２１が収容部９３ごとに検出したキュー１９３１のうち選択すべきキュー１９３１を収容部１９３ごとに選択して、その選択に応じた読出キュー指示情報１９８と決定キュー情報１９４７とを出力してキュー１９３１からパケットを出力させる。
キュー選択部１９４２２は、選択キュー情報生成部１９４２２１及び選択キュー格納部１９４２２２を有している。選択キュー情報生成部１９４２２１は、キュー検出部１９４２１が検出しキュー１９３１のいずれかを指す選択キュー情報を収容部１９３ごとに生成する。選択キュー格納部１９４２２２は、選択キュー情報生成部１９４２２１が収容部１９３ごとに生成した選択キュー情報を格納する。読み出すキュー１９３１の選択を特定のキュー１９３１に偏ることなく均等にするために、選択キュー情報生成部１９４２２１は、選択キュー格納部１９４２２２が今回格納した選択キュー情報が指すキュー１９３１以外のキュー１９３１をキュー検出部１９４２１が検出した場合に、そのキュー１９３１を指す選択キュー情報を次回に生成する。
また、選択キュー情報格納部１９４２２２は、選択キュー情報生成部１９４２２１が収容部１９３ごとに生成した選択キュー情報を保持するための選択キュー保持部１９４２２４を収容部１９３ごとに備えている。
選択キュー情報生成部１９４２２１は、選択キュー保持部１９４２２４が今回保持した選択キュー情報が指すキュー１９３１以外のキュー１９３１をキュー検出部１９４２１が検出した場合、そのキュー１９３１を指す選択キュー情報を次回に生成して選択キュー保持部１９４２２４に保持させる。選択キュー情報生成部１９４２２１は、選択キュー保持部１９４２２４が保持している選択キュー情報を決定キュー情報１９４７として収容部１９３ごとに通知する。
各々のキュー１９３１は、選択キュー情報生成部１９４２２１が収容部１９３ごとに選択キュー情報を生成するために序列づけられている。選択キュー情報生成部１９４２２１は、選択キュー保持部１９４２２２が今回保持した選択キュー情報が指すキュー１９３１を序列の最下位とし、キュー検出部１９４２１が検出したキュー１９３１のうち序列が最も高いキュー１９３１を指す選択キュー情報を収容部１９３ごとに次回に生成する。
また、読出キュー決定部１９４２は、決定指示部１１１からの決定指示に応じて、第２の優先順位より高いキュー１９３１が無い場合、決定指示部１１１が指示するキュー１９３１のうちパケットを記憶しているキュー１９３１を読み出すべきキュー１９３１として決定する。
このように、本発明の実施の形態１においては、受信したパケットを入力部１９１が収容部１９３ごとに振り分けて収容し、読出制御部１９４の書込キュー情報生成部１９４１が収容部１９３ごとにパケットが書込まれているキュー１９３１を示す書込キュー情報を生成し、同様に読出制御部１９４の優先順位決定部１９４０がパケットを読み出す優先順位を決定する。このため、本発明の実施の形態１においては、読出キュー決定部１９４２は書込キュー情報と優先順位に応じてパケットを読み出すべきキュー１９３１を収容部１９３ごとに決定することができる。したがって、、本実施の形態１においては、送受信部が増加した場合でも収容部１９３の数が増加するだけで読み出すべきキュー１９３１を決定する時間は変わらず遅延時間の短い高速なパケット転送回路を得ることができる。
また、本発明の実施の形態１においては、選択キュー情報生成部１９４２２１がキュー検出部１９４２１において検出されたキュー１９３１のいずれかを指す選択キュー情報を生成し、選択キュー情報格納部１９４２２２は選択キュー情報生成部１９４２２１が生成した選択キュー情報を次回の選択機会まで格納するため、次回の選択機会において選択キュー情報生成部１９４２２１は、キュー検出部１９４２１が検出したキュー１９３１の中に選択キュー情報格納部１９４２２２で格納している前回の選択キュー情報と異なるキュー１９３１が存在する場合に該キュー１９３１を指す選択キュー情報を生成することができるから、読み出すキュー１９３１の選択が特定のキュー１９３１に偏ることなく均等にすることができる。
したがって、本発明の実施の形態１によれば、複数の収容部１９３ごとに複数のキュー１９３１の優先順位を決定するため、複数の収容部１９３ごとにパケットを並行に転送するから、各送信部と各受信部との接続を均等に決定してパケットを並行に転送するので、受信部及び送信部の数にかかわらず遅延時間が短い高速なパケット転送回路を提供することができる。
（実施の形態２）
次に、本発明の実施の形態２について、図面を参照して詳細に説明する。
図１２は、本発明の実施の形態２に係るパケット転送回路の構成を示すブロック図である。
図１２に示すように、本発明の実施の形態２に係るパケット転送回路２００は、本発明の実施の形態１に係るパケット転送回路１０９において、複数の収容部１９３の各々における複数のキュー１９３１の出力を読出制御部１９４の代わりに出力選択部２０２により制御するものである。
出力選択部２０２は、複数のキュー１９３１のいずれか１つを選択し、選択されたキュー１９３１に記憶されているパケットを外部に出力する構成となっている。
また、出力選択部２０２は、記憶検知部２２１、優先順位決定部２２２、選択決定部２２３、複数の個別保持部２２４、複数の積重保持部（累積保持部）２２５及び出力量計測部２２６を有している。
記憶検知部２２１は、パケットを記憶しているキュー１９３１を検知する機能を有している。優先順位決定部２２２は、キュー１９３１ごとにパケットを出力する優先順位を決定する機能を有している。そして、選択決定部２２３は、記憶検知部２２１によって検知されたキュー１９３１の中からパケットを出力すべきキュー１９３１を優先順位決定部２２２によって決定された優先順位に応じて決定し、そのキュー１９３１に対してパケットの出力指示を行う。
また、出力量計測部２２６は、各キュー１９３１が出力するパケットのデータ量を計測する。複数の個別保持部２２４は、各々のキュー１９３１に対応して設置されている。複数の個別保持部２２４は、対応する各キュー１９３１から出力されるパケットの出力データ量（出力量計測部２２６によって計測された出力データ量）を保持する。そして、各個別保持部２２４に保持される各キュー１９３１からの出力データ量が各キュー１９３１に対して定められた閾値となった場合には、優先順位決定部２２２が、その個別保持部２２４に対応するキュー１９３１の優先順位を所定の順位、又は、出力データ量に応じた順位まで下げる設定を行う。これにより、出力データ量が閾値に達していないキュー１９３１の相対順位が上がり、閾値に達していないキュー１９３１に記憶されているパケットが優先的に出力されるようになるので、キュー１９３１ごとの帯域制御が可能となる。
また、複数の積重保持部２２５は、各々が１又は複数のキュー１９３１（１又は複数のキュー１９３１によって構成されるグループ収容装置）に対応しており設置されている。複数の積重保持部２２５は、対応する前記グループ収容装置から出力されるパケットの出力データ量（出力量計測部２２６によって計測された出力データ量）を累積して保持する。そして、各積重保持部２２５と対応関係を有する前記グループ収容装置からの出力データ量の累計値が、グループ収容装置ごとに対して（すなわち、積重保持部２２５ごとに対して）定められた閾値となった場合には、優先順位決定部２２２が、その積重保持部２２５に対応する前記グループ収容装置の優先順位を所定の順位、又は、出力データ量の累積値に応じた順位まで下げる設定を行う。
これにより、出力データ量の累積値が閾値に達していない前記グループ収容装置に属するキュー１９３１の相対順位が上がり、閾値に達していない前記グループ収容装置に属するキュー１９３１に記憶されているパケットが優先的に出力されるようになるので、前記グループ収容装置ごとの帯域制御及びキュー１９３１ごとの帯域制御が可能となっている。
なお、所定の積重保持部２２５に保持される出力データ量の累積値とは、所定の積重保持部２２５に対応付けられた前記グループ収容装置の出力データ量の合計値である。所定の積重保持部２２５に対してキュー１９３１が１つのみ対応付けられている場合には、そのキュー１９３１に係る個別保持部２２４と積重保持部２２５とは、同一の値を保持することになる。
上記のように、複数のキュー１９３１をグループ分けしてグループ収容装置とすることにより、例えば、複数のユーザ装置と通信する単一のユーザ装置に対して帯域制御を行う場合にそのユーザ装置と通信する複数のユーザ装置のそれぞれに関して１又は複数のキュー１９３１を設定し、１又は複数のキュー１９３１を１つのグループ収容装置として管理して帯域制御を行うことが可能となる。
また、さらに、出力選択部２０２は、判別書込部２０３、閾値書込部２０４及び検出指示部２０５を有している。判別書込部２０３は、キュー１９３１とグループとの対応を矛盾なく設定する。判別書込部２０３は、出力量計測部２２６の積重判別記憶部２２６１（後述）と優先順位決定部２２２のキュー判別記憶部２２２６１（後述）とに、積重保持部２２５ごとに対応するキュー１９３１を示すキュー判別情報と、キュー１９３１ごとに対応する積重保持部２２５を示す積重判別情報（累計判別情報）とを供給して記憶させる。
また、検出指示部２０５は、割り当てられた帯域を使い終えたキュー１９３１を出力禁止のキュー１９３１とするか、又は、ベストエフォートのキュー１９３１（サービスが保証されないキュー１９３１）とするかを選択する。検出指示部２０５は、選択決定部２２３の優先キュー検出部２２３１（後述）に対して、優先順位が最も低くなったキュー１９３１に関してそのキュー１９３１からのパケットの出力を禁止すべき指示を行う。また、閾値書込部２０４は、優先順位決定部２２２の積重閾値記憶部２２２７（後述）と個別閾値記憶部２２２２（後述）とに、各積重保持部２２５に設定された閾値とキュー１９３１ごとの閾値とを書き込む。
また、図１３は、本発明の実施の形態２に係るパケット転送回路の優先順位決定部の構成を示すブロック図である。図１３に示すように、優先順位決定部２２２は、優先順位記憶部２２２１及び優先順位書込部２２２３を有している。そして、優先順位書込部２２２３は、各キュー１９３１及び前記グループ収容装置の優先順位を優先順位記憶部２２２１に書き込む。
また、優先順位書込部２２２３は、複数の個別閾値記憶部２２２２、個別書込部２２２５、積重書込部（累積書込部）２２２６及び複数の積重閾値記憶部（累積閾値記憶部）２２２７を有している。
複数の個別閾値記憶部２２２２は、各個別保持部２２４に対応して設置されている。複数の個別閾値記憶部２２２２は、各個別保持部２２４における出力データ量（すなわち、各キュー１９３１における出力データ量）の閾値を記憶している。なお、各個別閾値記憶部２２２２において、異なる閾値（すなわち、個別保持部２２４ごとに異なる閾値）を設定することが可能である。また、閾値書込部２０４によって、各個別閾値記憶部２２２２に記憶された閾値を変更することも可能である。
個別書込部２２２５は、各個別保持部２２４に保持された出力データ量及び各個別閾値記憶部２２２２に記憶されている閾値を受けて、個別保持部２２４から供給された出力データ量とその個別保持部２２４に対応する個別閾値記憶部２２２２から供給された閾値とを比較する。そして、個別書込部２２２５は、出力データ量が閾値を超えた場合にそのキュー１９３１の優先順位を所定の順位まで下げてその所定の順位を優先順位記憶部２２２１に書き込む。
一方、複数の積重閾値記憶部２２２７は、各積重保持部２２５に対応して設置されている。複数の積重閾値記憶部２２２７は、各積重保持部２２５における出力データ量の累積値（すなわち、前記グループ収容装置ごとにおける出力データ量の累積値）の閾値を記憶している。なお、各積重閾値記憶部２２２７において、異なる閾値（すなわち、積重保持部２２５ごとに異なる閾値）を設定することが可能である。また、閾値書込部２０４によって、各積重閾値記憶部２２２７に記憶された閾値を変更することも可能である。
また、積重書込部２２２６は、各積重保持部２２５に保持された出力データ量の累積値及び各積重閾値記憶部２２２７に記憶されている閾値を受けて、積重保持部２２５から供給された出力データ量の累積値とその積重保持部２２５に対応する積重閾値記憶部２２２７から供給された閾値とを比較する。そして、積重書込部２２２６は、出力データ量の累積値が閾値を超えた場合に、そのキュー１９３１及び前記グループ収容装置の優先順位を所定の順位まで下げてその所定の順位を優先順位記憶部２２２１に書き込む。
なお、個別保持部２２４及び積重保持部２２５は、所定の時間ごとにリセットされることによって、所定の時間当たりの出力データ量及びその累積値を保持できるようにすることが好ましい。また、同様に、優先順位記憶部２２２１に記憶されるキュー１９３１又は前記グループ収容装置ごとの優先順位も、所定の時間ごとにリセットされ、予め各キュー１９３１又は前記グループ収容装置に定められた優先順位に戻るようにすることが好ましい。また、前記閾値は、各キュー１９３１及び前記グループ収容装置の各々に対して設定し、個別閾値記憶部２２２２又は積重閾値記憶部２２２７に記憶し、各々に割り当てられた帯域と上述の所定の時間とを参照して決定することが好ましい。
また、特に、閾値書込部２０４を用いることによって、各キュー１９３１及び前記グループ収容装置の各々に対応する個別閾値記憶部２２２２又は積重閾値記憶部２２２７に閾値の書き込み及び変更が可能なので、前記グループ収容装置の各々に割り当てる帯域、所定の前記グループ収容装置に属する各キュー１９３１に割り当てる帯域などを確実に設定することが可能である。また、任意のタイミングで各キュー１９３１及び前記グループ収容装置に割り当てる帯域を柔軟に変更することも可能である。
また、図１４は、本発明の実施の形態２に係るパケット転送回路における個別閾値記憶部及び個別書込部の構成を示すブロック図である。図１４に示すように、個別閾値記憶部２２２２は、第１の個別閾値回路２２２２１及び第２の個別閾値回路２２２２２を有している。個別書込部２２２５は、優先順位計算部２２２８及び計算結果書込部２２２９を有している。
図１４に示す個別書込部２２２５の優先順位計算部２２２８は、個別保持部２２４から供給された出力データ量が、対応する個別閾値記憶部２２２２に記憶された閾値を超えた場合に、対応するキュー１９３１の優先順位が所定の順位になるよう優先順位を計算する。また、この計算結果は、計算結果書込部２２２９によって、優先順位記憶部２２２１に書き込まれる。
図１８は、本発明の実施の形態２に係るパケット転送回路における優先順位計算部によって計算される優先順位と出力データ量との関係の第１の例を説明するための図である。図１８において、縦軸は優先順位を示し、横軸はキュー１９３１の出力データ量を示している。優先順位計算部２２２８は、出力データ量と個別閾値記憶部２２２２に記憶された閾値とに応じて優先順位を計算する。そして、図１８に示すように、キュー１９３１がパケットを出力していない場合には、キュー１９３１の優先順位を図１８の優先順位Ｆとし、キュー１９３１の出力データ量が増すごとにキュー１９３１の優先順位を下げて、出力データ量がキュー１９３１に定められた閾値（図１８のＴｈ１）に達した場合には、所定の順位（図１８の優先順位Ｇ）となるよう設定する。
このように、優先順位計算部２２２８で優先順位を決定することにより、閾値の近傍までの量のデータを出力したキュー１９３１の優先順位よりも、まだ閾値の近傍までの量のデータを出力していないキュー１９３１の優先順位を高く設定することが可能となるので、各キュー１９３１における出力データ量が閾値に達するまでの平均時間を均等にすることが可能となる。
また、図１４に示すように、個別閾値記憶部２２２２は、第１の個別閾値回路２２２２１及び第２の個別閾値回路２２２２２を有している。第１の個別閾値回路２２２２１は、キュー１９３１の最低保証帯域に対応する閾値（最低保証帯域閾値）を記憶している。第２の個別閾値回路２２２２２は、第１の個別閾値回路２２２２１に記憶された最低保証帯域閾値よりも大きな値である最大帯域の閾値（最大帯域閾値）を記憶している。個別閾値記憶部２２２２は、パケットを記憶している（キューイングしている）全てのキュー１９３１が第１の個別閾値回路２２２２１に記憶された最低保証帯域閾値までデータを出力した場合でも、それらのキュー１９３１が第２の個別閾値回路２２２２２に記憶された閾値までデータを出力することが可能な余剰帯域を有効に利用できるようになっている。
個別保持部２２４に保持された出力データ量が第１の個別閾値回路２２２２１に記憶された閾値となった場合には、個別書込部２２２５は、そのキュー１９３１の優先順位を、最低保証帯域閾値以上のデータ量を出力したキュー１９３１に対して定められた第１の優先順位まで下げて優先順位記憶部２２２１に書き込む。また、個別保持部２２４に保持された出力データ量が第２の個別閾値回路２２２２２に記憶された閾値となった場合には、個別書込部２２２５は、そのキュー１９３１の優先順位を、第１の優先順位より低い第２の優先順位まで下げて優先順位記憶部２２２１に書き込む。
図１９は、本発明の実施の形態２に係るパケット転送回路における優先順位計算部によって計算される優先順位と出力データ量との関係の第２の例を説明するための図である。図１９において、縦軸は優先順位を示し、横軸はキュー１９３１の出力データ量を示している。
優先順位計算部２２２８は、図１９に示すように、キュー１９３１がパケットを出力していない場合には、キュー１９３１の優先順位を図１９の優先順位Ａとし、キュー１９３１の出力データ量が増すごとにキュー１９３１の優先順位を下げて、出力データ量が第１の個別閾値回路２２２２１に記憶された閾値（図１９のＴｈ１）に達した場合には、所定の順位（図１９の優先順位Ｂ）となるように設定する。
これにより、パケットをキューイングしている全てのキュー１９３１が最低保証帯域閾値までデータを出力した場合には、キュー１９３１は、出力データ量が第２の個別閾値回路２２２２２に記憶された閾値（図１９のＴｈ２）に達するまで、パケットを出力することが可能である。キュー１９３１の出力データ量が閾値Ｔｈ２に達したとき、そのキュー１９３１の優先順位は図１９に示すベストエフォートの優先順位Ｃとなる。
このように、閾値書込部２０４は、いずれかのキュー１９３１に対応する個別閾値記憶部２２２２に備えられた第２の個別閾値回路２２２２２に対して、第１の個別閾値回路２２２２１に記憶された閾値より低い閾値を書き込んで記憶させることが可能であり、キュー１９３１に対して最低保証帯域と最大帯域とを設定することが可能となる。
また、検出指示部２０５によってベストエフォートとされたキュー１９３１に関しては、その後に、そのキュー１９３１からのパケットの出力データ量によらず、図１９の優先順位Ｄ３に示されるように、優先順位を変化させないようにすることも可能である。また、図１９の優先順位Ｄ２に示すように、監視期間内に常にパケットを出力し続けて、その出力データ量が物理的に出力可能な上限値に達したキュー１９３１に関しては、検出指示部２０５によって出力禁止のキュー１９３１とみなされるようにすることも可能である。これによって、出力したデータ量が多いキュー１９３１ほど優先順位が下がるので、各キュー１９３１が均等にパケットを出力することが可能となる。
また、図１５は、本発明の実施の形態２に係るパケット転送回路の積重閾値記憶部及び積重書込部の構成を示すブロック図である。図１５に示すように、積重閾値記憶部２２２７は、第１の積重閾値回路（第１の累積閾値回路）２２２７１及び第２の積重閾値回路（第２の累積閾値回路）２２２７２を有している。積重書込部２２２６は、キュー判別記憶部２２２６１及び対応書込部２２６２を有している。
図１５に示す積重書込部２２２６の複数のキュー判別記憶部２２２６１は、各積重保持部２２５に対応して設置されている。複数のキュー判別記憶部２２２６１は、対応する各キュー１９３１及び前記グループ収容装置の各々を示す判別情報が記憶されている。そして、積重保持部２２５に保持される出力データ量が所定の閾値を超えた場合には、対応書込部２２２６２は、各積重保持部２２５に対応するキュー判別記憶部２２２６１に記憶されている判別情報を参照して、優先順位を変更すべきキュー１９３１を検知し、変更後の優先順位を優先順位記憶部２２２１に書き込む。
また、積重閾値記憶部２２２７の第１の積重閾値回路２２２７１には、積重保持部２２５に対応するキュー１９３１の最低保証帯域（対応するキュー１９３１が複数存在する場合には、それらの閾値の合計）の累積の閾値である最低保証帯域累積閾値が記憶される。第２の積重閾値回路２２２７２には、第１の積重閾値回路２２２７１に記憶された最低保証帯域累積閾値よりも大きな値である最大帯域の累積の閾値（最大帯域累積閾値）が記憶されている。
そして、積重保持部２２５に保持された出力データ量が第１の積重閾値回路２２２７１により記憶された閾値となった場合には、積重書込部２２２６は、そのキュー１９３１の優先順位を、最低保証帯域累積閾値以上のデータを出力したキュー１９３１に対して定められた第１の優先順位まで下げて優先順位記憶部２２２１に書き込む。また、積重書込部２２２６は、積重保持部２２５に保持された出力データ量が第２の積重閾値回路２２２７２により記憶された閾値となった場合には、そのキュー１９３１の優先順位を、第１の優先順位より低い第２の優先順位まで下げて優先順位記憶部２２２１に書き込む。
これにより、パケットをキューイングしている全てのキュー１９３１及び全ての前記グループ収容装置が最低保証帯域累積閾値までデータを出力した場合でも、キュー１９３１は出力データ量が最大帯域累積閾値に達するまで、パケットを出力することが可能であるため、余剰帯域を有効に利用することが可能である。
また、図１７は、本発明の実施の形態２に係るパケット転送回路における選択決定部の構成を示すブロック図である。図１７に示すように、選択決定部２２３は、優先キュー検出部２２３１及びキュー決定部２２３２を有している。優先キュー検出部２２３１は、優先順位決定部２２２により決定された優先順位に応じて、記憶検知部２２１によって検知された最も優先順位が高いキュー１９３１を検出する。キュー決定部２２３２は、優先キュー検出部２２３１によって検出されたキュー１９３１の中から選択すべきキュー１９３１を決定することが可能である。
また、キュー決定部２２３２は、決定キュー情報生成部２２３２１及び決定キュー情報保持部２２３２２を有している。決定キュー情報生成部２２３２１は、優先キュー検出部２２３１により検出されたキュー１９３１のいずれかを示す決定キュー情報を生成する。決定キュー情報保持部２２３２２は、決定キュー情報生成部２２３２１からの決定キュー情報を保持する。これにより、決定キュー情報生成部２２３２１は、決定キュー情報保持部２２３２２によって現在保持されている決定キュー情報が示すキュー１９３１を検知することが可能である。
また、決定キュー情報保持部２２３２２によって現在保持されているキュー１９３１以外のキュー１９３１が、優先キュー検出部２２３１によって検出された場合には、決定キュー情報生成部２２３２１は、そのキュー１９３１を示す決定キュー情報を次の回に生成する。さらに、決定キュー情報生成部２２３２１は、決定キュー情報保持部２２３２２によって現在保持されている決定キュー情報が示すキュー１９３１を序列の最下位（優先順位を最も下げた状態）とし、優先キュー検出部２２３１によって検出されたキュー１９３１のうち序列が最も高いキュー１９３１（優先順位が最も高いキュー１９３１）を示す決定キュー情報を次の回に生成するから、選択ごとに序列が変更されるようになっているので、複数のキュー１９３１を均等に選択できる。
また、図１６は、本発明の実施の形態２に係るパケット転送回路における出力量計測部の構成を示すブロック図である。図１６に示すように、出力量計測部２２６は、積重判別記憶部（累積判別記憶部）２２６１、データ量計数回路２２６２、個別選択回路２２６３、積重選択回路２２６４及び完了検知部２２６５を有している。
複数の積重判別記憶部２２６１は、積重保持部２２５ごとに設定されている。複数の積重判別記憶部２２６１は、積重保持部２２５とキュー１９３１及び前記グループ収容装置との対応関係を示す積重判別情報を記憶することが可能である。これにより、積重保持部２２５とキュー１９３１及び前記グループ収容装置との対応が確実に判別可能となるから、パケットを出力するキュー１９３１の出力データ量は、その積重判別情報によって特定される積重保持部２２５に確実に累積される。
また、データ量計数回路２２６２は、キュー１９３１の出力データ量を計数する。データ量計数回路２２６２によって計数された出力データ量は、個別選択回路２２６３及び積重選択回路２２６４に供給される。個別選択回路２２６３は、キュー１９３１ごとの出力データ量を保持することが可能な個別保持部２２４を選択する。積重選択回路２２６４は、キュー１９３１及び前記グループ収容装置ごとの出力データ量を累積して保持することが可能な積重保持部２２５を選択する。
個別選択回路２２６３は、選択決定部２２３によって選択されたキュー１９３１に対応する個別保持部２２４に対して出力データ量を供給する。また、積重選択回路２２６４は、選択決定部２２３によって選択された前記グループ収容装置に対応する積重判別記憶部２２６１内の積重判別情報が示す積重保持部２２５に対して出力データ量を供給する。
さらに、判別書込部２０３は、積重保持部２２５ごとに設定されたキュー判別記憶部２２２６１にキュー判別情報を書き込んで記憶させて、そのキュー判別情報が示すキュー１９３１に対応する積重判別記憶部２２６１にその積重保持部２２５を示す積重判別情報を書き込んで記憶させることによって、キュー１９３１と前記グループ収容装置との対応を矛盾なく設定することが可能である。また、判別書込部２０３は、キュー判別記憶部２２２６１及び積重判別記憶部２２６１に記憶された情報を変更可能とすることによって、ユーザは、キュー１９３１と前記グループ収容装置との対応を変更することが可能となる。
また、完了検知部２２６５は、キュー１９３１によるパケット出力の完了を検知する。完了検知部２２６５は、優先順位決定部２２２、選択決定部２２３、データ量計数回路２２６２、個別選択回路２２６３及び積重選択回路２２６４などにパケット出力の完了を通知することによって、処理のタイミング（同期の確保）を通知し、また、処理時以外（待機状態時）に消費される電力量を抑えることを可能とする。すなわち、パケット出力の完了のタイミングに基づいて、データ量計数回路２２６２は、計数を行って個別保持部２２４及び積重保持部２２５に出力データ量を供給することが可能となる。また、同様に、優先順位決定部２２２も、パケット出力の完了のタイミングに応じて、パケットが出力されたキュー１９３１の優先順位を新たに決定することが可能である。さらに、選択決定部２２２も、同様に、パケット出力の完了のタイミングに応じて、選択すべきキュー１９３１を新たに決定すること可能である。
上記のように、完了検知部２２６５によりパケット出力の完了を検知することによって、パケットの出力中のキュー１９３１が存在する場合、選択決定部２２３が、そのキュー１９３１からのパケット出力が完了するまで、他のキュー１９３１の選択が行えないから、ＡＴＭセルのような固定長のパケットのみならず、ＩＰパケットのような可変長のパケットも、確実に制御して出力させることが可能となる。
また、上述の優先順位は、一定の監視期間（所定の期間）ごとに、初期設定時の優先順位に戻るようになっている。図１８に示すように、閾値書込部２０４が、個別閾値記憶部２２２２の第１の個別閾値回路２２２２１及び第２の個別閾値回路２２２２２に等しい閾値（図１８のＴｈ１＝Ｔｈ２）を書き込んで記憶させ、個別書込部２２２５が、優先順位記憶部２２２１にパケットを出力していないキュー１９３１の優先順位を最も高い順位（図１８の優先順位Ｆ）として書き込むことにより、格別の装置を必要とせずに、専用線サービスのように遅延が少ないキュー１９３１をパケット転送回路２００の内部に設けることが可能となる。
図１８に示すように、閾値Ｔｈ１に達するまでの出力データ量に相当するパケットを出力したキュー１９３１は、図１８の優先順位Ｇまでその優先順位が下げられ、また、検出指示部２０５がそのキューの出力を禁止した場合にはさらに図１８の優先順位Ｄ１までその優先順位が下げられて、そのキュー１９３１からパケットが出力されなくなる。また、検出指示部２０５がベストエフォートのキュー１９３１とした場合には、そのキュー１９３１は、図１８の優先順位Ｃに示すベストエフォート用の優先順位までその優先順位が下げられる。その後、そのキュー１９３１がパケットを出力した場合には、図１８の優先順位Ｄ３に示すように優先順位を変化させないようにすることも可能だが、前述の図１８の優先順位Ｄ２に示すように、上限値に達したキュー１９３１は、出力禁止のキュー１９３１となるようにすることが好ましい。
また、図２０は、本発明の実施の形態２に係るパケット転送回路における優先順位計算部によって計算される優先順位と出力データ量との関係の第３の例を説明するための図である。図２０に示すように、個別閾値記憶部２２２２の第１の個別閾値回路２２２２１及び第２の個別閾値回路２２２２２に等しい閾値（図２０のＴｈ１＝Ｔｈ２）を書き込んで記憶させ、個別書込部２２２５が、キュー１９３１の出力データ量によらず最も低い優先順位Ｅを優先順位記憶部２２２１に書き込むことによって、ベストエフォートのキュー１９３１をパケット転送回路２００の内部に設けることが可能となる。この場合にも、上述と同様に、その後、そのキュー１９３１がパケットを出力した場合には、図１８の優先順位Ｄ３に示すように優先順位を変化させないようにすることも可能であるが、前述の図１８の優先順位Ｄ２に示すように、上限値に達したキュー１９３１は、出力禁止のキュー１９３１となるようにすることが好ましい。
なお、本発明の実施の形態２では、本発明のパケット転送回路２００が、各機能を有するユニットによって構成されている態様について説明したが、同様の動作を行うことを可能とするプログラムをコンピュータによって実行することによって、本発明を実現することも可能である。
このように、本発明の実施の形態２によれば、本発明の実施の形態１の効果に加えて、複数のキュー１９３１のグループ分けを行って複数のグループ収容装置とし、前記複数のグループ収容装置の各々に属するキュー１９３１の出力データ量の累積値（合計値）に基づく帯域制御が可能となりため、２種類のテーブルから順番に情報を読み出すことなく、簡単な構成によってパケットを出力すべきキュー１９３１を高速で選択可能となる。
なお、本発明の実施の形態２は、１つの収容部１９３の複数のキュー１９３１の出力を制御する場合にも適用することができる。
本明細書は、２００２年５月３０日出願の特願２００２−１５７３３３及び２００２年５月３１日出願の特願２００２−１６０５７９に基づく。この内容は、すべてここに含めておく。
産業上の利用可能性
本発明は、パケットを受信して複数の出力ポートから出力する装置に適用することができる。
【図面の簡単な説明】
図１は、従来のパケット転送装置の構成を示すブロック図、
図２は、図１の従来のパケット転送装置におけるスケジューラの構成を示すブロック図、
図３は、図２のスケジューラの動作を説明するためのタイミング図、
図４は、他の従来のパケット転送装置の構成を示すブロック図、
図５は、他の従来のパケット転送装置における制御アルゴリズムを説明するための図、
図６は、本発明の実施の形態１に係るパケット転送回路の構成を示すブロック図、
図７は、本発明の実施の形態１に係るパケット転送回路の読出制御部の具体的な構成を示すブロック図、
図８は、本発明の実施の形態１に係るパケット転送回路の優先順位書込部の具体的な構成を示すブロック図、
図９は、図８の優先順位書込部における最優先順位検知部の具体的な構成を示すブロック図、
図１０は、図８の優先順位書込部における読出キュー決定部の具体的な構成を示すブロック図、
図１１は、本発明の実施の形態１に係るパケット転送回路における読出データ量と優先順位の関係を説明するための図、
図１２は、本発明の実施の形態２に係るパケット転送回路の構成を示すブロック図、
図１３は、図１２のパケット転送回路における優先順位決定部の構成を示すブロック図、
図１４は、図１２のパケット転送回路における個別閾値記憶部及び個別書込部の構成を示すブロック図、
図１５は、図１２のパケット転送回路における積重閾値記憶部及び積重書込部の構成を示すブロック図、
図１６は、図１２のパケット転送回路における出力量計測部の構成を示すブロック図、
図１７は、図１２のパケット転送回路における選択決定部の構成を示すブロック図、
図１８は、図１２のパケット転送回路における優先順位計算部によって計算される優先順位と出力データ量との関係の第１の例を説明するための図、
図１９は、図１２のパケット転送回路における優先順位計算部によって計算される優先順位と出力データ量との関係の第２の例を説明するための図、
図２０は、図１２のパケット転送回路における優先順位計算部によって計算される優先順位と出力データ量との関係の第３の例を説明するための図である。
【図１】
2003103234.tif 000003
【図２】
2003103234.tif 000004
【図３】
2003103234.tif 000005
【図４】
2003103234.tif 000006
【図５】
2003103234.tif 000007
【図６】
2003103234.tif 000008
【図７】
2003103234.tif 000009
【図８】
2003103234.tif 000010
【図９】
2003103234.tif 000011
【図１０】
2003103234.tif 000012
【図１１】
2003103234.tif 000013
【図１２】
2003103234.tif 000014
【図１３】
2003103234.tif 000015
【図１４】
2003103234.tif 000016
【図１５】
2003103234.tif 000017
【図１６】
2003103234.tif 000018
【図１７】
2003103234.tif 000019
【図１８】
2003103234.tif 000020
【図１９】
2003103234.tif 000021
【図２０】
2003103234.tif 000022
【国際調査報告】
2003103234.tif 000023
2003103234.tif 000024
2003103234.tif 000025
2003103234.tif 000026