(57)【要約】【課題】複数の通信ポート間においてパケットを交換するパケット伝送装置に設けられた出力パケットバッファの記憶領域の使用効率を向上する。【解決手段】パケット伝送装置１は、複数の通信ポートＰ＃０〜Ｐ＃ｎと、パケットを交換するスイッチ３と、複数の通信ポートＰ＃０〜Ｐ＃ｎから出力するパケットをそれぞれ保持する複数のキューが記憶される記憶部２０と、停止信号生成部２６とを備える。停止信号生成部２６は、いずれかの通信ポートＰ＃０のキューに保持されるパケット量が所定の第１閾値Ｔｄｉ０以上であり、かつ複数のキューに保持されるパケット量の合計が所定の第２閾値Ｔａｉ以上であるとき、通信ポートＰ＃０宛のパケットをスイッチ２０へ入力するのを停止させる停止信号を生成する。【選択図】図２
2010226208.tif 000002
【特許請求の範囲】
【請求項１】
複数の通信ポートと、
前記複数の通信ポート間でパケットを交換するスイッチと、
前記複数の通信ポートから出力するパケットをそれぞれ保持する複数のキューが記憶される記憶部と、
いずれかの前記通信ポートの前記キューに保持されるパケット量が所定の第１閾値以上であり、かつ前記複数のキューに保持されるパケット量の合計が所定の第２閾値以上であるとき、前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを停止させる停止信号を生成する停止信号生成部と、
を備えるパケット伝送装置。
【請求項２】
前記スイッチへのパケットの入力を制御するパケット入力制御部を備え、
前記停止信号は、前記パケット入力制御部が前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを停止させる請求項１に記載のパケット伝送装置。
【請求項３】
前記いずれかの通信ポートの前記キューに保持されるパケット量が所定の第３閾値よりも小さくなり、又は前記複数のキューに保持されるパケット量の合計が所定の第４閾値よりも小さくなったとき、前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを許可する許可信号を生成する許可信号生成部を備える請求項１又は２に記載のパケット伝送装置。
【請求項４】
複数の回線間におけるパケット交換を行うスイッチを有するパケット伝送装置に設けられ、前記回線と前記スイッチとの間において前記パケットのインタフェース制御を行う回線インタフェースユニットであって、
前記複数の回線に接続される複数の前記通信ポートと、
前記複数の通信ポートから出力するパケットをそれぞれ保持する複数のキューが記憶される記憶部と、
いずれかの前記通信ポートの前記キューに保持されるパケット量が所定の第１閾値以上であり、かつ前記複数のキューに保持されるパケット量の合計が所定の第２閾値以上であるとき、前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを停止させる停止信号を生成する停止信号生成部と、
を備える回線インタフェースユニット。
【請求項５】
前記パケット伝送装置は、複数の前記回線インタフェースユニットを備え、
各前記回線インタフェースユニットは、前記スイッチを経由して他の前記回線インタフェースユニットへ伝送される停止信号パケットを、前記停止信号に従って生成する停止信号パケット生成部を備え、
前記停止信号パケットは、前記スイッチへの前記いずれかの通信ポート宛のパケットの入力の停止を要求するパケットである、請求項４に記載の回線インタフェースユニット。
【請求項６】
複数の通信ポートと、前記複数の通信ポート間でパケットを交換するスイッチと、前記複数の通信ポートから出力するパケットをそれぞれ保持する複数のキューが記憶される記憶部と、を備えるパケット伝送装置の制御方法であって、
いずれかの前記通信ポートの前記キューに保持されるパケット量と所定の第１閾値との間の比較、及び前記複数のキューに保持されるパケット量の合計と所定の第２閾値との間の比較をそれぞれ行い、
いずれかの前記通信ポートの前記キューに保持されるパケット量が所定の第１閾値以上であり、かつ前記複数のキューに保持されるパケット量の合計が所定の第２閾値以上であるとき、前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを停止する、パケット伝送装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の通信ポート間においてパケットを交換するパケット伝送装置及びパケット伝送方法に関する。
【背景技術】
【０００２】
従来、パケットを伝送するパケット通信網においては、複数の通信ポートを備えこれら複数の通信ポート間でパケットを交換するパケット伝送装置が設けられる。このようなパケット伝送装置には、例えばレイヤ２スイッチ装置がある。パケット伝送装置においては、通信ポートから入力されたパケットの宛先アドレスに応じて、このパケットを転送する宛先の通信ポートが決定される。入力されたパケットは、決定された宛先の通信ポートへ転送され、この通信ポートから出力される。以下の説明においてパケットが出力される通信ポートを単に「出力ポート」と記載することがある。
【０００３】
各パケットは、出力ポートから出力される前に、一時的に出力パケットバッファに蓄積される。パケット伝送装置のスケジューラは、各パケットの優先度クラスや各出力ポートの伝送レートに応じて送信制御が行う。この結果、各通信ポート宛に転送されたパケットが出力パケットバッファから読み出され、それぞれの通信ポートから出力される。
【０００４】
なお、所定のバッファ管理方式の使用によって個々のフローに対するレート保証を与えるレ―ト保証方法が提案されている。この方法では、他のフローからの過剰なトラフィックがある場合でも、パケット送信決定におけるフロー数への依存をなくすと同時に全体的な複雑さをさらに少なくすることを目的とする。
【０００５】
この方法は、各ストリームｎが１からＮまでの範囲のインデックスを付けられ、パケット交換ネットワーク内の共通の出力リンクｊで送信するために多重化され、このリンクがパケットを格納するバイト数で表された合計バッファ空間を有するバッファから成る、複数のパケット・ストリームｎの各パケット・ストリームについて明示的なレート保証Ｒnを提供する方法である。
【０００６】
この方法は、次のステップを含む。ａ）各現在の受信パケットについて、現在の受信パケットに関連づけられたパケット・ストリームｎを識別するステップ。ｂ）現在の受信パケットを合計バッファ空間の専有部分に加えて第１の和を求めるステップ。ｃ）第１の和が第１のしきい値を超えるか否かを判断し、それに応答して第１の変数を設定するステップ。ｄ）現在の受信パケットをストリームｎに割り振られたバッファ空間に加えて第２の和を求めるステップ。ｅ）第２の和が第２のしきい値を超えるか否かを判断し、それに応答して第２の変数を設定するステップ。ｆ）第１及び第２の変数に基づいてパケットを受け入れるかまたは拒否し、それによってストリームの前記レート保証Ｒnを保証するステップ。
【０００７】
また、非同期転送モードで転送されるＡＴＭセルを入力ポートと出力ポートとの間でスイッチングするＡＴＭ交換機のスイッチ制御回路が提案されている。このスイッチ制御回路は、入力ポート及び出力ポート各々に対応して設けられかつ入力ポートと出力ポートとの間でＡＴＭセル交換を行うための入力ポートバッファ及び出力ポートバッファと、出力ポートバッファでのセル廃棄を防止するために出力ポートバッファの占有量に応じて送出再開信号と送出停止信号と送出制御信号とのうちいずれかを出力するバックプレッシャ機能と、セル送出制御手段を有する。
【０００８】
このセル送出制御手段は、ＡＴＭセルを送出する出力ポートに対応してバックプレッシャ機能から送出再開信号が入力された時に当該出力ポートに対して予め設定された第１のレートでＡＴＭセルを送出するよう制御し、かつＡＴＭセルを送出する出力ポートに対応してバックプレッシャ機能から送出制御信号が入力された時に当該出力ポートに対して予め設定された第２のレートでＡＴＭセルを送出するよう制御する。
【０００９】
さらに、受信パケットをパケットバッファに書き込むとき、そのアドレスを、物理ポートに対応する宛先毎に読出アドレスとして第１の記憶部に記憶すると共に、受信パケットの受信パケット情報を記憶する第１手段と、スケジューリング制御に従って受信パケットをパケットバッファから読み出すとき、受信パケット情報で指定された宛先の読出アドレスを第１の記憶部から読み出して第２の記憶部に保持する第２手段と、調停制御に従って、第２の記憶部に保持されている読出アドレスを取り出し、これに対応する受信パケッをパケットバッファから読み出す第３手段と、を備えるパケット伝送装置が提案されている。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２０００−４９８５３号公報
【特許文献２】特開平１０−１４５３８２号公報
【特許文献３】特開２００９−２１８７２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上述のパケット伝送装置の出力パケットバッファには、各通信ポートから出力されるパケットのキューが格納される。また各通信ポートのキューには、各通信ポートについてバックプレッシャを行うことを要求するバックプレッシャ発行閾値と、バックプレッシャの解除を要求するバックプレッシャ解除閾値がそれぞれ設定されている。以下の説明では、簡単のため、バックプレッシャを「ＢＰ」と省略して記載することがある。
【００１２】
ある通信ポートのキューに蓄積したパケット量がＢＰ発行閾値を超えると、その通信ポートについてのＢＰ発行要求信号が出力される。ＢＰ発行要求信号を受信した他の通信ポートでは、ＢＰ発行要求信号が出力された通信ポートへ転送すべきパケットを受信しても、このパケットの転送を停止し、又はＢＰ発行要求信号が出力された通信ポートへのパケット転送レートを調整する。
【００１３】
ＢＰ発行要求信号によって、パケット蓄積量がＢＰ発行閾値を超えた通信ポートへ転送されるパケットの量が低下する。その後、この通信ポートのキューに蓄積されるパケット量がＢＰ解除閾値を下回ると、その通信ポートについてのＢＰ解除要求信号が出力される。ＢＰ解除要求信号を受信した他の通信ポートでは、上述したパケットの転送の停止や、パケット転送レートの調整を解除する。上記の処理によって、パケット伝送装置は出力パケットバッファの容量オーバに起因するパケット廃棄を防止している。
【００１４】
この処理によれば、各通信ポートにおけるパケット蓄積量が、通信ポート毎に個別に許された許容蓄積量であるＢＰ発行閾値以上となるか否かによって、ＢＰ発行要求信号の出力可否が決定される。したがって、ある通信ポートにおけるパケット蓄積量がＢＰ発行閾値を超えれば、たとえ他の通信ポートから出力されるパケットの蓄積量が少なく出力パケットバッファ全体の記憶容量に余裕があったとしても、ＢＰ発行要求信号が出力される。このため、上記処理では、出力パケットバッファの記憶領域を有効に活用していない。
【００１５】
開示の装置及び方法は、出力パケットバッファの記憶領域の使用効率を向上することを目的とする。
【課題を解決するための手段】
【００１６】
実施例の一形態によれば、複数の通信ポートと、複数の通信ポート間でパケットを交換するスイッチと、複数の通信ポートから出力するパケットをそれぞれ保持する複数のキューが記憶される記憶部と、停止信号生成部とを備えるパケット伝送装置が与えられる。この停止信号生成部は、いずれかの通信ポートのキューに保持されるパケット量が所定の第１閾値以上であり、かつ複数のキューに保持されるパケット量の合計が所定の第２閾値以上であるとき、上記いずれかの通信ポート宛のパケットをスイッチへ入力するのを停止させる停止信号を生成する。
【００１７】
実施例の他の形態によれば、複数の回線間におけるパケット交換を行うスイッチを有するパケット伝送装置に設けられ、これらの回線とスイッチとの間においてパケットのインタフェース制御を行う回線インタフェースユニットが与えられる。この回線インタフェースユニットは、複数の回線に接続される複数の前記通信ポートと、複数の通信ポートから出力するパケットをそれぞれ保持する複数のキューが記憶される記憶部と、停止信号生成部とを備える。この停止信号生成部は、いずれかの通信ポートのキューに保持されるパケット量が所定の第１閾値以上であり、かつ複数のキューに保持されるパケット量の合計が所定の第２閾値以上であるとき、上記いずれかの通信ポート宛のパケットをスイッチへ入力するのを停止させる停止信号を生成する。
【発明の効果】
【００１８】
上記実施例によれば、出力パケットバッファの記憶領域の使用効率が向上する。
【図面の簡単な説明】
【００１９】
【図１】開示のパケット伝送装置の概略構成の説明図である。
【図２】ＬＩＵカードの概略構成の説明図である。
【図３】ＢＰ発行要求信号を出力する条件の説明図である。
【図４】ＢＰ解除要求信号を出力する条件の説明図である。
【図５】閾値テーブルの構成例の説明図である。
【図６】キュー長管理部の概略構成の説明図である。
【図７】パケット蓄積量テーブルの構成例の説明図である。
【図８】ＢＰ発行要求信号を出力する際の動作の説明図である。
【図９】ＢＰ解除要求信号を出力する際の動作の説明図である。
【図１０】各閾値の設定例の説明図である。
【図１１】（Ａ）及び（Ｂ）は出力パケットバッファの状態の説明図（その１）である。
【図１２】（Ａ）及び（Ｂ）は出力パケットバッファの状態の説明図（その２）である。
【図１３】（Ａ）及び（Ｂ）は出力パケットバッファの状態の説明図（その３）である。
【図１４】（Ａ）及び（Ｂ）は出力パケットバッファの状態の説明図（その４）である。
【図１５】（Ａ）及び（Ｂ）は出力パケットバッファの状態の説明図（その５）である。
【図１６】（Ａ）及び（Ｂ）は出力パケットバッファの状態の説明図（その６）である。
【図１７】出力パケットバッファの構成例の説明図である。
【図１８】アドレス管理部の概略構成の説明図である。
【図１９】チェーン管理テーブルの構成例の説明図である。
【図２０】先頭アドレス管理テーブルの構成例の説明図である。
【図２１】末尾アドレス管理テーブルの構成例の説明図である。
【図２２】読出アドレス格納部の概略構成の説明図である。
【図２３】各アドレスＦＩＦＯの構成例の説明図である。
【図２４】パケット受信時におけるＬＩＵカードの動作の説明図（その１）である。
【図２５】パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その１）である。
【図２６】パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その２）である。
【図２７】パケット受信時におけるＬＩＵカードの動作の説明図（その２）である。
【図２８】パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その３）である。
【図２９】パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その４）である。
【図３０】パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その５）である。
【図３１】パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その６）である。
【図３２】パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その７）である。
【図３３】パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その８）である。
【図３４】パケット送信時におけるＬＩＵカードの動作の説明図である。
【図３５】パケット送信時の出力パケットバッファ及び各テーブルの状態の説明図（その１）である。
【図３６】パケット送信時の出力パケットバッファ及び各テーブルの状態の説明図（その２）である。
【発明を実施するための形態】
【００２０】
以下、添付する図面を参照して実施例を説明する。図１は、開示のパケット伝送装置の概略構成の説明図である。参照符号１はパケット伝送装置を示し、参照符号２…２は回線インタフェースユニット（LIU: Line Interface Unit）カードを示し、参照符号３はスイッチカードを示し、参照符号ＮＷ１及びＮＷ２はネットワーク網を示す。パケット伝送装置１は、例えばレイヤ２スイッチであってよいが、本実施例の適用範囲はレイヤ２スイッチに限定されるものではなく、出力パケットバッファにおけるパケット蓄積量を調整するバックプレッシャ機能を有する他の種類のパケット伝送装置にも、広く適用可能である。
【００２１】
パケット伝送装置１は、ＬＩＵカード＃１〜＃４を含む複数のＬＩＵカード２…２とスイッチカードを備える。各ＬＩＵカード２…２は、ネットワーク網ＮＷ１及び／又はＮＷ２から到来するパケットを受信し、又はネットワーク網ＮＷ１及び／又はＮＷ２へパケットを送信するための複数の物理ポートＰ＃０〜Ｐ＃ｎを備える。複数のＬＩＵカード２…２を、「ＬＩＵカード２」と総称することがある。また、複数の物理ポートＰ＃０〜Ｐ＃ｎを「物理ポートＰ」と総称することがある。特許請求の範囲に記載の通信ポートは、例えば、物理ポートＰによって実現されてよい。
【００２２】
パケット伝送装置１は、ネットワーク網ＮＷ１及び／又はＮＷ２から受信したパケットをスイッチカード３へ入力する前に一時的に格納する入力パケットバッファ４を備える。またパケット伝送装置１は、スイッチカード３から受信したパケットをネットワーク網ＮＷ１及び／又はＮＷ２へ送信する前に一時的に格納する出力パケットバッファ５を備える。
【００２３】
例えば、ネットワークＮＷ１及び／又はＮＷ２から到来したパケットは、図１の点線で表した経路に沿ってスイッチカード３へ入力される。まずパケットは、物理ポートＰにおいて受信される。パケットは、入力パケットバッファ４に一時的に格納された後、スイッチカード３へ入力される。
【００２４】
スイッチカード３では、各パケットの宛先となる物理ポート、すなわち各パケットを出力すべき物理ポートをそれぞれ識別し、識別した物理ポートが存在するＬＩＵカード２へパケットを出力する。この出力経路を一点鎖線にて表す。
【００２５】
スイッチカード３からパケットを受信したＬＩＵカード２は、スケジューリング制御及び出力制御を行って、各物理ポートＰからネットワーク網ＮＷ１及び／又はＮＷ２へ、パケットを送信する。
【００２６】
このようにネットワーク網ＮＷ１及び／又はＮＷ２へパケットが送信される物理ポートは、パケット伝送装置１によるパケット交換処理の、転送先又は宛先となる物理ポートである。以下の説明において、パケット伝送装置１によるパケット交換処理の転送先となる物理ポートを、このパケットの「宛先ポート」と記載することがある。また、以下の説明において、パケット伝送装置１によるパケット交換処理によりある物理ポートへ転送されるパケットのことを、この物理ポート「を宛先とするパケット」若しくはこの物理ポート「宛のパケット」と記載することがある。
【００２７】
図２は、図１に記されたＬＩＵカード２の概略構成の説明図である。参照符号１１はマルチプレクサ（Ｍｕｘ）を示し、参照符号１２は入力パケットバッファメモリを示し、参照符号１３は書込制御部を示し、参照符号１４は読出制御部を示し、参照符号１５はセレクタを示す。
【００２８】
参照符号２０は出力パケットバッファメモリを示し、参照符号２１は書込制御部を示し、参照符号２２は読出制御部を示し、参照符号２３はデマルチプレクサ（Ｄｍｕｘ）を示し、参照符号２４はキュー長管理部を示す。
【００２９】
参照符号２５は閾値管理部を示し、参照符号２６はＢＰ信号生成部を示し、参照符号２７はＢＰパケット生成部を示し、参照符号２８はＢＰパケット検出部を示す。参照符号３０はスケジューラを示し、参照符号３１はアドレス管理部を示し、参照符号３２は読出アドレス格納部を示す。
【００３０】
ＬＩＵカード２は、マルチプレクサ（Ｍｕｘ）１１、入力パケットバッファメモリ１２、書込制御部１３、読出制御部１４、セレクタ１５、出力パケットバッファメモリ２０、書込制御部２１、読出制御部２２、及びデマルチプレクサ（Ｄｍｕｘ）２３を備える。
【００３１】
また、ＬＩＵカード２は、キュー長管理部２４、閾値管理部２５、ＢＰ信号生成部２６、ＢＰパケット生成部２７、ＢＰパケット検出部２８、スケジューラ３０、アドレス管理部３１、及び読出アドレス格納部３２を備える。
【００３２】
マルチプレクサ（Ｍｕｘ）１１は、ネットワーク網ＮＷ１及び／又はＮＷ２から各物理ポートＰにおいて受信されたパケットを多重化する。入力パケットバッファメモリ１２は、図１に示した入力パケットバッファ４用の記憶領域を用意するために用いられ、ネットワーク網ＮＷ１及び／又はＮＷ２から入力されたパケットを蓄積する。
【００３３】
書込制御部１３は、マルチプレクサ１１から受信したパケットを入力パケットバッファメモリ１２へ書き込む。書込制御部１３は、パケット伝送装置１に設けられた各物理ポートＰについて生成されたＢＰ発行要求信号を受信する。ＢＰ発行要求信号は、対象の物理ポートＰについてバックプレッシャを行うことを要求する信号であり、後述のＢＰ信号生成部２６及びＢＰパケット検出部２８によって生成される。
【００３４】
ある物理ポートＰ＃ｘについて生成されたＢＰ発行要求信号を受信したとき、書込制御部１３は、物理ポートＰ＃ｘを宛先とするパケットの書き込みを抑制する。書込制御部１３は、入力パケットバッファメモリ１２の容量に応じて物理ポートＰ＃ｘを宛先とするパケットを廃棄することによって、パケットの書き込みを抑制する。
【００３５】
書込制御部１３は、パケット伝送装置１に設けられた各物理ポートＰについて生成されたＢＰ解除要求信号を受信する。ＢＰ解除要求信号は、対象の物理ポートＰについて行われているバックプレッシャを解除することを要求する信号であり、後述のＢＰ信号生成部２６及びＢＰパケット検出部２８によって生成される。ある物理ポートＰ＃ｘについて生成されたＢＰ解除要求信号を受信したとき、書込制御部１３は、物理ポートＰ＃ｘを宛先とするパケットの書き込みの抑制を解除する。
【００３６】
読出制御部１４は、入力パケットバッファメモリ１２からパケットを読み出し、読み出されたパケットをスイッチカード３へ入力する。読出制御部１４は、パケット伝送装置１に設けられた各物理ポートＰについて生成されたＢＰ発行要求信号を受信する。ある物理ポートＰ＃ｘについて生成されたＢＰ発行要求信号を受信したとき、読出制御部１４は、物理ポートＰ＃ｘを宛先とするパケットの入力パケットバッファメモリ１２から読み出しを抑制する。
【００３７】
読出制御部１４は、パケット伝送装置１に設けられた各物理ポートＰについて生成されたＢＰ解除要求信号を受信する。ある物理ポートＰ＃ｘについて生成されたＢＰ解除要求信号を受信したとき、読出制御部１４は、物理ポートＰ＃ｘを宛先とするパケットの読み出しの抑制を解除する。このようにして、書込制御部１３及び読出制御部１４は、ネットワーク網ＮＷ１及び／又はＮＷ２から各物理ポートＰにおいて受信されたパケットの、スイッチカード３への入力を制御する。特許請求の範囲に記載されたパケット入力制御部は、例えば書込制御部１３及び読出制御部１４によって実現されてよい。
【００３８】
セレクタ１５は、読出制御部１４及びＢＰパケット生成部２７のどちらからパケットが出力されるのかに応じて、スイッチカード３へのパケットの入力元を、読出制御部１４とＢＰパケット生成部２７との間で切り替える。
【００３９】
出力パケットバッファメモリ２０は、図１に示した出力パケットバッファ５用の記憶領域を用意するために用いられ、ネットワーク網ＮＷ１及び／又はＮＷ２へ出力するパケットを蓄積する。ＬＩＵカード２に設けられた各物理ポートＰに対してそれぞれ個別のキューが用意され、各物理ポートＰを宛先とするパケットは、それぞれの物理ポートＰに対して用意されたキューに保持される。出力パケットバッファメモリ２０には、ＬＩＵカード２に設けられた複数の物理ポートＰについて用意された上記の複数のキューが記憶される。
【００４０】
書込制御部２１は、スイッチカード３から受信したパケットを出力パケットバッファメモリ２０へ書き込む。また書込制御部２１は、受信したパケットをキュー長管理部２４へ送信する。
【００４１】
後述するように、書込制御部２１は、出力パケットバッファメモリ２０へ書き込むパケットのパケット情報をアドレス管理部３１へ送信する。パケット情報は、対象のパケットの宛先ポートの識別情報及びパケットサイズを含む。書込制御部２１は、パケットを出力パケットバッファメモリ２０へ書き込むとき、パケットを書き込む書込アドレス値をアドレス管理部３１から受信する。
【００４２】
読出制御部２２は、スケジューラ３０の制御にしたがって、各物理ポートＰから出力するパケットを出力パケットバッファメモリ２０から読み出し、デマルチプレクサ（Ｄｍｕｘ）２３へ出力する。読出制御部２２は、読み出したパケットをキュー長管理部２４へ送信する。
【００４３】
デマルチプレクサ（Ｄｍｕｘ）２３は、出力パケットバッファメモリ２０から読み出された多重化されたパケットを、各物理ポートＰ宛のパケットに分離する。またデマルチプレクサ（Ｄｍｕｘ）２３は、各物理ポートＰから出力されるパケットを整調する。
【００４４】
キュー長管理部２４は、各物理ポートＰに対してそれぞれ用意されたキュー毎に、各キューに保持されたパケット量を監視する。またキュー長管理部２４は、これら複数のキューに保持されるパケット量の総合計値を監視する。
【００４５】
閾値管理部２５は、各物理ポートＰ＃０、Ｐ＃１〜Ｐ＃ｎに対してそれぞれ用意されたキュー毎に設定されたＢＰ発行閾値Ｔｄｉ０、Ｔｄｉ１〜Ｔｄｉｎ、及びＢＰ解除閾値Ｔｄｒ０、Ｔｄｒ１〜Ｔｄｒｎを記憶する。閾値管理部２５は、これら複数のキューに保持されるパケット量の総合計値に対して設けられたＢＰ発行閾値Ｔａｉ及びＢＰ解除閾値Ｔａｒを記憶する。
【００４６】
以下の説明において、ＢＰ発行閾値Ｔｄｉ０〜Ｔｄｉｎ及びＢＰ解除閾値Ｔｄｒ０〜Ｔｄｒｎを、それぞれ「個別ＢＰ発行閾値」及び「個別ＢＰ解除閾値」と呼ぶことがある。また、以下の説明においてＢＰ発行閾値Ｔａｉ及びＢＰ解除閾値Ｔａｒを、それぞれ「全体ＢＰ発行閾値」及び「全体ＢＰ解除閾値」と呼ぶことがある。
【００４７】
特許請求の範囲に記載された第１閾値は、例えば、個別ＢＰ発行閾値Ｔｄｉ０〜Ｔｄｉｎであってよい。特許請求の範囲に記載された第２閾値は、例えば、全体ＢＰ発行閾値Ｔａｉであってよい。特許請求の範囲に記載された第３閾値は、例えば、個別ＢＰ解除閾値Ｔｄｒ０〜Ｔｄｒｎであってよい。特許請求の範囲に記載された第４閾値は、例えば、全体ＢＰ解除閾値Ｔａｒであってよい。
【００４８】
ＢＰ信号生成部２６は、ＢＰ発行要求信号及びＢＰ解除要求信号を生成する。ＢＰ信号生成部２６は、ある物理ポートＰ＃ｘのキューに保持されるパケット量が個別ＢＰ発行閾値Ｔｄｉｘ以上であり、かつ複数の物理ポートＰ＃０〜Ｐ＃ｎに対してそれぞれ用意された複数のキューに保持されるパケット量の総合計値が全体ＢＰ発行閾値Ｔａｉ以上になったとき、この物理ポートＰ＃ｘについてＢＰ発行要求信号を生成する。
【００４９】
なお、簡単のため以下の説明において、複数の物理ポートＰ＃０〜Ｐ＃ｎに対してそれぞれ用意された複数のキューに保持されるパケット量の総合計値のことを、単に「総パケット量」と記載することがある。
【００５０】
ＢＰ信号生成部２６は、ある物理ポートＰ＃ｘについてＢＰ発行要求信号を生成した後に、物理ポートＰ＃ｘのキューに保持されるパケット量が個別ＢＰ解除閾値Ｔｄｒｘよりも小さくなると、物理ポートＰ＃ｘについてＢＰ解除要求信号を生成する。また、ＢＰ信号生成部２６は、ある物理ポートＰ＃ｘについてＢＰ発行要求信号を生成した後に、総パケット量が全体ＢＰ解除閾値Ｔａｒよりも小さくなった場合も、物理ポートＰ＃ｘについてＢＰ解除要求信号を生成する。
【００５１】
特許請求の範囲に記載された停止信号及び許可信号は、例えば、それぞれＢＰ発行要求信号及びＢＰ解除要求信号であってよい。ＢＰ信号生成部２６は、ＢＰ発行要求信号及びＢＰ解除要求信号を、書込制御部１３及び読出制御部１４へ出力する。ＢＰ信号生成部２６は、ＢＰ発行要求信号及びＢＰ解除要求信号が生成されたことに知らせるために、これらの信号をＢＰパケット生成部２７へ出力してもよい。
【００５２】
ＢＰ信号生成部２６がＢＰ発行要求信号を生成したとき、ＢＰパケット生成部２７は、対象の物理ポートＰ＃ｘについてバックプレッシャを行うことを要求するＢＰ発行要求パケットを生成する。特許請求の範囲に記載された停止信号パケットは、例えば、ＢＰ発行要求パケットであってよい。ＢＰ信号生成部２６がＢＰ解除要求信号を生成したとき、ＢＰパケット生成部２７は、対象の物理ポートＰ＃ｘについて行われているバックプレッシャを解除することを要求するＢＰ解除要求パケットを生成する。
【００５３】
ＢＰパケット生成部２７は、生成されたＢＰ発行要求パケット及びＢＰ解除要求パケットを、セレクタ１５を介してスイッチカード３へ入力する。ＢＰ発行要求パケット及びＢＰ解除要求パケットは、スイッチカード３を経由して、パケット伝送装置１に設けられた各ＬＩＵカード２へ転送される。
【００５４】
ＢＰパケット検出部２８は、スイッチカード３を経由して入力された、他のＬＩＵカード２にて生成されたＢＰ発行要求パケット及びＢＰ解除要求パケットを検出する。ＢＰ発行要求パケットを受信したとき、ＢＰパケット検出部２８は、対象の物理ポートＰ＃ｘについてのＢＰ発行要求信号を、書込制御部１３及び読出制御部１４へ出力する。ＢＰ解除要求パケットを検出したとき、ＢＰパケット検出部２８は、対象の物理ポートＰ＃ｘについてのＢＰ解除要求信号を、書込制御部１３及び読出制御部１４へ出力する。
【００５５】
スケジューラ３０は、各物理ポートＰに接続された回線を使用する顧客の契約帯域を監視して帯域制御を行いながら、出力パケットバッファメモリ２０からパケットを読み出すべき宛先ポートを選択するスケジューリング制御を行う。スケジューラ３０は、例えばラウンドロビン方式によって宛先ポートを選択してもよい。
【００５６】
アドレス管理部３１は、書込制御部２１が出力パケットバッファメモリ２０へパケットを書き込む書込アドレス値を発行する。アドレス管理部３１は、書込アドレス値を書込制御部２１へ出力する。アドレス管理部３１は、スケジューラ３０によるスケジューリング制御に従って、読出制御部２２が出力パケットバッファメモリ２０からパケット読み出す読出アドレス値を発行する。アドレス管理部３１は、読出アドレス値を読出アドレス格納部３２へ出力する。
【００５７】
読出アドレス格納部３２は、アドレス管理部３１から受信した読出アドレス値を一時的に格納する。読出アドレス格納部３２は、各物理ポートＰのそれぞれの実レートに応じてパケットを出力すべき物理ポートを順次決定する。読出アドレス格納部３２は、格納された読出アドレス値のうち、決定された物理ポート宛のパケットを読み出すアドレス値を読出制御部２２へ出力する。読出制御部２２は、各物理ポートＰから出力するパケットを、読出アドレス格納部３２から受信したアドレスから読み出す。
【００５８】
次に、ＢＰ信号生成部２６によりＢＰ発行要求信号及び／又はＢＰ解除要求信号が出力される条件を説明する。図３の（Ａ）及び図３の（Ｂ）は、ＢＰ発行要求信号を出力する条件の説明図であり、図４の（Ａ）及び図４の（Ｂ）は、ＢＰ解除要求信号を出力する条件の説明図である。ここでは、説明の簡単のため、複数の物理ポートＰ＃０〜Ｐ＃ｎが３個の物理ポートＰ＃０、Ｐ＃１及びＰ＃２である場合を想定する。
【００５９】
参照符号１００、１０１及び１０２は、それぞれ物理ポートＰ＃０、Ｐ＃１及びＰ＃２に対して、これらのポートから出力されるパケットを保持するために用意されたキュー＃０、＃１及び＃２を示す。参照符号１０３は、キュー＃０〜＃２に格納されるパケットを記憶するために使用されている全記憶容領域を示す。図１０の（Ａ）、図１０の（Ｂ）、図１１の（Ａ）、図１１の（Ｂ）、図１２の（Ａ）、図１２の（Ｂ）、図１３の（Ａ）、図１３の（Ｂ）、図１４の（Ａ）、図１４の（Ｂ）、図１５の（Ａ）、図１５の（Ｂ）、図１６の（Ａ）、図１６の（Ｂ）においても同様である。
【００６０】
本例において、キュー＃０〜＃２をそれぞれ使用する各物理ポートＰ＃０〜Ｐ＃２は、ＬＩＵカード２に設けられた各物理ポートＰのうちの一部又は全部であってよい。キュー＃０〜＃２により利用可能な記憶領域は、出力パケットバッファメモリ２０において、各物理ポートＰから出力されるパケットを保持するキューのために確保された全記憶領域であってよい。またはキュー＃０〜＃２により利用可能な記憶領域は、出力パケットバッファメモリ２０において、各物理ポートＰから出力されるパケットを保持するキューのために確保された一部の記憶領域であってよい。
【００６１】
図３の（Ａ）及び図３の（Ｂ）において、キュー＃０〜＃２及び全記憶領域１０３の全記憶容量に対して、キュー＃０〜＃２及び全記憶領域１０３にそれぞれ蓄積されるパケット量が占める記憶容量が、ハッチングされた領域の高さで表される。キュー＃０〜＃２においてハッチングされた各領域のパケット量は、全記憶領域１０３において同じパターンでハッチングされた各領域のパケット量に対応する。また、キュー＃０〜＃２に蓄積されるパケット量に対する、各キュー＃０〜＃２にそれぞれ設定された個別ＢＰ発行閾値Ｔｄｉ０〜Ｔｄｉ２及び個別ＢＰ解除閾値Ｔｄｒ０〜Ｔｄｒ２の位置が、点線１０４及び１０５にて表されている。全記憶領域１０３に蓄積されるパケット量に対する、全体ＢＰ発行閾値Ｔａｉ及び全体ＢＰ解除閾値Ｔａｒの位置が、点線１０６及び１０７にてそれぞれ表されている。図４の（Ａ）、図４の（Ｂ）、図１０の（Ａ）、図１０の（Ｂ）、図１１の（Ａ）、図１１の（Ｂ）、図１２の（Ａ）、図１２の（Ｂ）、図１３の（Ａ）、図１３の（Ｂ）、図１４の（Ａ）、図１４の（Ｂ）、図１５の（Ａ）、図１５の（Ｂ）、図１６の（Ａ）、図１６の（Ｂ）においても同様である。
【００６２】
図３の（Ａ）の場合には、キュー＃０において、パケット蓄積量が個別ＢＰ発行閾値Ｔｄｉ０を超えている。しかし、パケット蓄積量が個別ＢＰ発行閾値Ｔｄｉ０以上であることのみを条件としてキュー＃０についてバックプレッシャを行うと、全記憶領域１０３にまだ余裕があるのにも関わらず、これ以上、物理ポートＰ＃０宛のパケットが蓄積できない。
【００６３】
本実施例では、ＢＰ信号生成部２６は、キュー＃０のパケット蓄積量が個別ＢＰ発行閾値Ｔｄｉ０以上であっても、総パケット量、すなわちキュー＃０〜＃２の蓄積パケットの総合計値が全体ＢＰ発行閾値Ｔａｉ以上になるまで、キュー＃０についてのＢＰ発行要求信号を生成しない。すなわち、図３の（Ｂ）に示すように、キュー＃０のパケット蓄積量が個別ＢＰ発行閾値Ｔｄｉ０以上となり、総パケット量が全体ＢＰ発行閾値Ｔａｉ以上となったとき、ＢＰ信号生成部２６は、キュー＃０についてのＢＰ発行要求信号を生成する。
【００６４】
キュー＃０についてＢＰ発行要求信号が生成されると、キュー＃０へのパケットの蓄積が止まるので、キュー＃０のパケット蓄積量が減少を始める。本実施例では、ＢＰ信号生成部２６は、総パケット量が全体ＢＰ解除閾値Ｔａｒよりも小さくなったとき、キュー＃０についてのＢＰ発行解除信号を生成する。この状態を図４の（Ａ）に示す。または、ＢＰ信号生成部２６は、キュー＃０のパケット蓄積量が個別ＢＰ解除閾値Ｔｄｒ０よりも小さくなったとき、キュー＃０についてのＢＰ発行解除信号を生成する。この状態を図４の（Ｂ）に示す。
【００６５】
このように、総パケット量が全体ＢＰ発行閾値になるまで、バックプレッシャを行わないことにより、個別ＢＰ発行閾値以上のパケットを蓄積したキューへ入力されるパケットを、他のキューのために用意した記憶領域に格納することができるので、全記憶領域１０３の利用効率が向上する。
【００６６】
個別ＢＰ発行閾値Ｔｄｉ０〜Ｔｄｉｎ及び個別ＢＰ解除閾値Ｔｄｒ０〜Ｔｄｒｎ、並びに全体ＢＰ発行閾値Ｔａｉ及び全体ＢＰ解除閾値Ｔａｒは、図２の閾値記憶部２５に記憶される閾値テーブル１１０に格納される。図５は、閾値テーブル１１０の構成例の説明図である。
【００６７】
閾値テーブル１１０は、各物理ポートＰ＃０〜Ｐ＃ｎにそれぞれ対応するアドレス「０」〜「ｎ」に、それぞれの各物理ポートＰ＃０〜Ｐ＃ｎのキューに設定された個別ＢＰ発行閾値Ｔｄｉ０〜Ｔｄｉｎ及び個別ＢＰ解除閾値Ｔｄｒ０〜Ｔｄｒｎを格納する。また、閾値テーブル１１０は、アドレス「ｎ＋１」に全体ＢＰ発行閾値Ｔａｉ及び全体ＢＰ解除閾値Ｔａｒを格納する。
【００６８】
なお、ＢＰ発行要求信号が出力されても、書込制御部１３及び読出制御部１４がスイッチカード３へのパケットの入力を停止するまでにはタイムラグがあり、このタイムラグの間はキューにパケットが送信されてくる。このため、個別ＢＰ発行閾値Ｔｄｉ０〜Ｔｄｉｎ及び全体ＢＰ発行閾値Ｔａｉの値を、実際の使用可能記憶容量よりも少なく設定して、タイムラグの間に受信されるパケットを格納できるようにしてもよい。
【００６９】
また、ＢＰ解除要求信号が出力されても、書込制御部１３及び読出制御部１４がパケットの送信を再開されるまでのタイムラグがある。この間にキューが空になってしまうと出力レート割れやバーストを生じさせてしまう。このため、個別ＢＰ解除閾値Ｔｄｒ０〜Ｔｄｒｎ及び全体ＢＰ解除閾値Ｔａｒの値は、キューの蓄積量が０にならないように設定してよい。
【００７０】
上述のパケット蓄積量と各閾値との比較処理は、図２のキュー長管理部２４によって行われる。図６は、図２に記されたキュー長管理部２４の概略構成の説明図である。参照符号４０は受信パケットサイズ算出部を示し、参照符号４１は送信パケットサイズ算出部を示し、参照符号４２はパケット蓄積量メモリを示し、参照符号４３は蓄積量演算部を示し、参照符号４４は比較部を示す。
【００７１】
キュー長管理部２４は、受信パケットサイズ算出部４０、送信パケットサイズ算出部４１、パケット蓄積量メモリ４２、蓄積量演算部４３、及び比較部４４を備える。
【００７２】
受信パケットサイズ算出部４０は、出力パケットバッファメモリ２０へ書き込むパケットを書込制御部２１から受信する。受信パケットサイズ算出部４０は、このパケットのパケットサイズを算出する。
【００７３】
送信パケットサイズ算出部４１は、出力パケットバッファメモリ２０から読み出されたパケットを読出制御部２２から受信する。送信パケットサイズ算出部４１は、このパケットのパケットサイズを算出する。
【００７４】
パケット蓄積量メモリ４２は、各物理ポートＰ＃０〜Ｐ＃ｎのキューに保持されているパケットのそれぞれのパケット蓄積量と、総パケット量と、を格納するパケット蓄積量テーブル１１１を記憶する。図７は、パケット蓄積量テーブル１１１の構成例の説明図である。
【００７５】
パケット蓄積量テーブル１１１は、各物理ポートＰ＃０〜Ｐ＃ｎにそれぞれ対応するアドレス「０」〜「ｎ」に、それぞれの各物理ポートＰ＃０〜Ｐ＃ｎのキューに保持されるパケットの蓄積量を格納する。また、パケット蓄積量テーブル１１１は、アドレス「ｎ＋１」に総パケット量を格納する。
【００７６】
図６を参照する。蓄積量演算部４３は、パケット蓄積量テーブル１１１に記憶されている、書込制御部２１から受信したパケットの宛先ポートのキューのパケット蓄積量に、受信パケットサイズ算出部４０が算出したサイズを加える。また、蓄積量演算部４３は、パケット蓄積量テーブル１１１に記憶されている総パケット量に、受信パケットサイズ算出部４０が算出したサイズを加える。
【００７７】
また蓄積量演算部４３は、パケット蓄積量テーブル１１１に記憶されている、読出制御部２２から受信したパケットの宛先ポートのキューのパケット蓄積量から、送信パケットサイズ算出部４１が算出したサイズを減算する。また、蓄積量演算部４３は、パケット蓄積量テーブル１１１に記憶されている総パケット量から、送信パケットサイズ算出部４１が算出したサイズを減算する。
【００７８】
比較部４４は、閾値記憶部２５の閾値テーブル１１０から、個別ＢＰ発行閾値Ｔｄｉ０〜Ｔｄｉｎ及び個別ＢＰ解除閾値Ｔｄｒ０〜Ｔｄｒｎ、並びに全体ＢＰ発行閾値Ｔａｉ及び全体ＢＰ解除閾値Ｔａｒを読み出す。
【００７９】
比較部４４は、各キューのパケット蓄積量と、各キューにそれぞれ設定された個別ＢＰ発行閾値Ｔｄｉ０〜Ｔｄｉｎとを比較する。比較部４４は、各キューのパケット蓄積量と、各キューにそれぞれ設定された個別ＢＰ解除閾値Ｔｄｒ０〜Ｔｄｒｎとを比較する。比較部４４は、総パケット量と全体ＢＰ発行閾値Ｔａｉとを比較する。比較部４４は、総パケット量と全体ＢＰ解除閾値Ｔａｒとを比較する。比較部４４は、これらの比較結果をＢＰ信号生成部２６に出力する。ＢＰ信号生成部２６は、これらの比較結果に基づいて、ＢＰ発行要求信号及びＢＰ解除要求信号を生成すべきか否かを判定する。
【００８０】
続いて、ＢＰ発行要求信号を出力する際の動作を説明する。図８は、ＢＰ発行要求信号を出力する際の動作の説明図である。なお、別な実施の態様においては、下記のオペレーションＡＡ〜オペレーションＡＫの各オペレーションはステップであってもよい。
【００８１】
オペレーションＡＡにおいて受信パケットサイズ算出部４０は、出力パケットバッファメモリ２０へ書き込むパケットを書込制御部２１から受信する。オペレーションＡＢにおいて受信パケットサイズ算出部４０は、受信したパケットのパケットサイズを算出する。
【００８２】
オペレーションＡＣにおいて蓄積量演算部４３は、書込制御部２１から受信したパケットの宛先ポートのキューである、対象のキューのパケット蓄積量をパケット蓄積量テーブル１１１から読み出す。この対象のキューを、図８の説明において「キュー＃ｘ」と記し、キュー＃ｘが設けられた物理ポートを「物理ポートＰ＃ｘ」と記す。また図８の説明において、キュー＃ｘについて設定された個別ＢＰ発行閾値を、「個別ＢＰ発行閾値Ｔｄｉｘ」と記す。
【００８３】
オペレーションＡＤにおいて蓄積量演算部４３は、読み出したパケット蓄積量に受信パケットサイズ算出部４０が算出したサイズを加えることにより、対象のキュー＃ｘのパケット蓄積量の記憶値を更新する。蓄積量演算部４３は、更新したパケット蓄積量をパケット蓄積量テーブル１１１へ保存する。
【００８４】
オペレーションＡＥにおいて蓄積量演算部４３は、総パケット量をパケット蓄積量テーブル１１１から読み出す。オペレーションＡＦにおいて蓄積量演算部４３は、読み出した総パケット量に受信パケットサイズ算出部４０が算出したサイズを加えることにより、総パケット量の記憶値を更新する。蓄積量演算部４３は、更新した総パケット量をパケット蓄積量テーブル１１１へ保存する。
【００８５】
オペレーションＡＧにおいて比較部４４は、閾値記憶部２５の閾値テーブル１１０から、個別ＢＰ発行閾値Ｔｄｉｘを読み出す。オペレーションＡＨにおいて比較部４４は、更新された対象のキュー＃ｘのパケット蓄積量と、個別ＢＰ発行閾値Ｔｄｉｘとを比較する。
【００８６】
対象のキュー＃ｘのパケット蓄積量が個別ＢＰ発行閾値Ｔｄｉｘ以上であるとき（オペレーションＡＨ：Ｙ）、処理はオペレーションＡＩへ移行する。対象のキュー＃ｘのパケット蓄積量が個別ＢＰ発行閾値Ｔｄｉｘより小さいとき（オペレーションＡＨ：Ｎ）、ＢＰ信号生成部２６によるＢＰ発行要求信号の生成が行われずに、処理が終了する。
【００８７】
オペレーションＡＩにおいて比較部４４は、閾値記憶部２５の閾値テーブル１１０から、全体ＢＰ発行閾値Ｔａｉを読み出す。オペレーションＡＪにおいて比較部４４は、更新された総パケット量と全体ＢＰ発行閾値Ｔａｉとを比較する。
【００８８】
総パケット量が全体ＢＰ発行閾値Ｔａｉ以上であるとき（オペレーションＡＪ：Ｙ）、処理はオペレーションＡＫへ移行する。総パケット量が全体ＢＰ発行閾値Ｔａｉより小さいとき（オペレーションＡＪ：Ｎ）、ＢＰ信号生成部２６によるＢＰ発行要求信号の生成が行われずに、処理が終了する。
【００８９】
オペレーションＡＫにおいてＢＰ信号生成部２６は、キュー＃ｘが設けられた物理ポートＰ＃ｘについてＢＰ発行要求信号を出力する。その後処理が終了する。以上、図８を参照して説明した上記動作によって、ＢＰ信号生成部２６は、ある物理ポートＰ＃ｘのキューに保持されるパケット量が個別ＢＰ発行閾値Ｔｄｉｘ以上であり、かつ総パケット量が全体ＢＰ発行閾値Ｔａｉ以上になったとき、この物理ポートＰ＃ｘについてＢＰ発行要求信号を生成する。
【００９０】
図９は、ＢＰ解除要求信号を出力する際の動作の説明図である。なお、別な実施の態様においては、下記のオペレーションＢＡ〜オペレーションＢＫの各オペレーションはステップであってもよい。
【００９１】
オペレーションＢＡにおいて送信パケットサイズ算出部４１は、出力パケットバッファメモリ２０から読み出されたパケットを読出制御部２２から受信する。オペレーションＢＢにおいて送信パケットサイズ算出部４１は、受信したパケットのパケットサイズを算出する。
【００９２】
オペレーションＢＣにおいて蓄積量演算部４３は、読出制御部２２から受信したパケットの宛先ポートのキューである、対象のキューのパケット蓄積量をパケット蓄積量テーブル１１１から読み出す。この対象のキューを、図９の説明において「キュー＃ｘ」と記し、キュー＃ｘが設けられた物理ポートを「物理ポートＰ＃ｘ」と記す。また図９の説明において、キュー＃ｘについて設定された個別ＢＰ解除閾値を、「個別ＢＰ解除閾値Ｔｄｒｘ」と記す。
【００９３】
オペレーションＢＤにおいて蓄積量演算部４３は、送信パケットサイズ算出部４１が算出したサイズを読み出したパケット蓄積量から減算することにより、対象のキュー＃ｘのパケット蓄積量の記憶値を更新する。蓄積量演算部４３は、更新したパケット蓄積量をパケット蓄積量テーブル１１１へ保存する。
【００９４】
オペレーションＢＥにおいて蓄積量演算部４３は、総パケット量をパケット蓄積量テーブル１１１から読み出す。オペレーションＢＦにおいて蓄積量演算部４３は、送信パケットサイズ算出部４１が算出したサイズを読み出した総パケット量から減算することにより、総パケット量の記憶値を更新する。蓄積量演算部４３は、更新した総パケット量をパケット蓄積量テーブル１１１へ保存する。
【００９５】
オペレーションＢＧにおいて比較部４４は、閾値記憶部２５の閾値テーブル１１０から、個別ＢＰ解除閾値Ｔｄｒｘを読み出す。オペレーションＢＨにおいて比較部４４は、更新された対象のキュー＃ｘのパケット蓄積量と、個別ＢＰ解除閾値Ｔｄｒｘとを比較する。
【００９６】
対象のキュー＃ｘのパケット蓄積量が個別ＢＰ解除閾値Ｔｄｒｘより小さいとき（オペレーションＢＨ：Ｙ）、処理はオペレーションＢＫへ移行する。対象のキュー＃ｘのパケット蓄積量が個別ＢＰ解除閾値Ｔｄｒｘ以上のとき（オペレーションＢＨ：Ｎ）、処理はオペレーションＢＩへ移行する。
【００９７】
オペレーションＢＩにおいて比較部４４は、閾値記憶部２５の閾値テーブル１１０から、全体ＢＰ解除閾値Ｔａｒを読み出す。オペレーションＢＪにおいて比較部４４は、更新された総パケット量と全体ＢＰ解除閾値Ｔａｒとを比較する。
【００９８】
総パケット量が全体ＢＰ解除閾値Ｔａｒより小さいとき（オペレーションＢＪ：Ｙ）、処理はオペレーションＢＫへ移行する。総パケット量が全体ＢＰ解除閾値Ｔａｒ以上のとき（オペレーションＢＪ：Ｎ）、ＢＰ信号生成部２６によるＢＰ解除要求信号の生成が行われずに、処理が終了する。
【００９９】
オペレーションＢＫにおいてＢＰ信号生成部２６は、キュー＃ｘが設けられた物理ポートＰ＃ｘについてＢＰ解除要求信号を出力する。その後処理が終了する。以上、図９を参照して説明した上記動作によって、ＢＰ信号生成部２６は、ある物理ポートＰ＃ｘのキューに保持されるパケット量が個別ＢＰ解除閾値Ｔｄｒｘより小さくなったときか、若しくは総パケット量が全体ＢＰ解除閾値Ｔａｒよりも小さくなったとき、この物理ポートＰ＃ｘについてＢＰ解除要求信号を生成する。
【０１００】
以下、添付する図１０の（Ａ）、図１０の（Ｂ）、図１１の（Ａ）、図１１の（Ｂ）、図１２の（Ａ）、図１２の（Ｂ）、図１３の（Ａ）、図１３の（Ｂ）、図１４の（Ａ）、図１４の（Ｂ）、図１５の（Ａ）、図１５の（Ｂ）、図１６の（Ａ）及び図１６の（Ｂ）を参照しながら、本実施例によるＢＰ発生要求信号及びＢＰ解除要求信号の生成処理の動作を説明する。
【０１０１】
説明の簡単のため、複数の物理ポートＰ＃０〜Ｐ＃ｎの数が３個である場合、すなわち複数の物理ポートＰ＃０〜Ｐ＃ｎが、３個の物理ポートＰ＃０、Ｐ＃１及びＰ＃２である場合を想定する。これら物理ポートＰ＃０、Ｐ＃１及びＰ＃２に対して、出力パケットを保持するためにキュー＃０、＃１及び＃２が用意される。
【０１０２】
また、複数のキュー＃０〜＃２のために確保された全記憶領域１０３に保持可能なパケットの記憶容量を３００とする。したがって、この記憶容量を、複数のキュー＃０〜＃２に均等に割り当てた場合の各キューの記憶可能容量は１００となる。なお、パケットのデータ量及び記憶容量を表すために本説明で使用される数の単位は、データのビット数を示す単位であれば何でもよく、特に特定しない。
【０１０３】
図１０に示すように、個別ＢＰ発行閾値Ｔｄｉ０〜Ｔｄｉ２の値が「８０」に、個別ＢＰ解除閾値Ｔｄｒ０〜Ｔｄｒ２の値が「４０」に、全体ＢＰ発行閾値Ｔａｉの値が「２００」に、全体ＢＰ解除閾値Ｔａｒの値が「１００」に設定された場合を想定する。
【０１０４】
図１１の（Ａ）及び図１１の（Ｂ）は出力パケットバッファの状態の説明図（その１）である。なお、図１１の（Ａ）に表される「パケット＃０」はキュー＃０に保持されるパケットにより占められた記憶容量を表す。「パケット＃１」はキュー＃１に保持されるパケットにより占められた記憶容量を表す。「パケット＃２」はキュー＃２に保持されるパケットにより占められた記憶容量を表す。図１２の（Ａ）、図１３の（Ａ）、図１４の（Ａ）、図１５の（Ａ）及び図１６の（Ａ）についても同様である。
【０１０５】
パケットがキュー＃０〜＃２に蓄積されることにより、キュー＃０のパケット蓄積量が「９０」に、キュー＃１のパケット蓄積量が「２０」に、キュー＃２のパケット蓄積量が「２０」になる。この状態ではキュー＃０のパケット蓄積量「９０」が個別ＢＰ発行閾値Ｔｄｉ０（＝８０）以上となっている。しかし、総パケット量（９０＋２０＋２０＝１３０）が、全体ＢＰ発行閾値Ｔａｉ（＝２００）より小さい。このため、ＢＰ信号生成部２６は、キュー＃０についてＢＰ発行要求信号を生成しない。
【０１０６】
図１２の（Ａ）及び図１２の（Ｂ）は出力パケットバッファの状態の説明図（その２）である。この場合、キュー＃０のパケット蓄積量が「１３０」に、キュー＃１のパケット蓄積量が「５０」に、キュー＃２のパケット蓄積量が「３０」になっている。この状態ではキュー＃０のパケット蓄積量「１３０」が個別ＢＰ発行閾値Ｔｄｉ０（＝８０）以上となり、かつ総パケット量（１３０＋５０＋３０＝２１０）が、全体ＢＰ発行閾値Ｔａｉ（＝２００）以上となっている。このため、ＢＰ信号生成部２６は、キュー＃０についてＢＰ発行要求信号を生成する。
【０１０７】
この場合、キュー＃０は、全記憶領域１０３をキュー＃０〜＃２に均等に割り当てた場合の各キューの記憶容量「１００」よりも多いパケットを保持しているので、キュー＃０は、他のキュー＃１及び＃２のために用意された記憶領域を利用している、と言うことができる。
【０１０８】
ＢＰ信号生成部２６によるＢＰ発行要求信号の生成によって、物理ポートＰ＃０に対してバックプレッシャが行われると、キュー＃０のパケット蓄積量が減少する。図１３の（Ａ）及び図１３の（Ｂ）は出力パケットバッファの状態の説明図（その３）である。この場合、キュー＃０のパケット蓄積量が「６０」に、キュー＃１のパケット蓄積量が「７０」に、キュー＃２のパケット蓄積量が「５０」になっている。
【０１０９】
この状態ではキュー＃０のパケット蓄積量「６０」が個別ＢＰ解除閾値Ｔｄｒ０（＝４０）以上であり、総パケット量（６０＋７０＋５０＝１８０）が、全体ＢＰ解除閾値Ｔａｒ（＝１００）以上である。このため、ＢＰ信号生成部２６は、キュー＃０についてのＢＰ解除要求信号を生成しない。このため、物理ポートＰ＃０に対してバックプレッシャは解除されない。
【０１１０】
物理ポートＰ＃０に対するバックプレッシャにより、キュー＃０のパケット蓄積量がさらに減少する。また、他のキュー＃１および＃２には更にパケットが蓄積される。図１４の（Ａ）及び図１４の（Ｂ）は出力パケットバッファの状態の説明図（その４）である。この場合、キュー＃０のパケット蓄積量が「３０」に、キュー＃１のパケット蓄積量が「９０」に、キュー＃２のパケット蓄積量が「６０」になっている。
【０１１１】
この状態では、総パケット量（３０＋９０＋６０＝１８０）が、全体ＢＰ解除閾値Ｔａｒ（＝１００）以上であるが、キュー＃０のパケット蓄積量「３０」が個別ＢＰ解除閾値Ｔｄｒ０（＝４０）よりも小さくなる。このため、ＢＰ信号生成部２６は、キュー＃０についてのＢＰ解除要求信号を生成する。これによって物理ポートＰ＃０に対するバックプレッシャが解除される。
【０１１２】
一方で、キュー＃１のパケット蓄積量「９０」が個別ＢＰ発行閾値Ｔｄｉ１（＝８０）以上となっている。しかし、総パケット量「１８０」が、全体ＢＰ発行閾値Ｔａｉ（＝２００）より小さい。このため、ＢＰ信号生成部２６は、キュー＃１についてＢＰ発行要求信号を生成しない。
【０１１３】
図１５の（Ａ）及び図１５の（Ｂ）は出力パケットバッファの状態の説明図（その５）である。この場合、キュー＃０のパケット蓄積量が「５０」に、キュー＃１のパケット蓄積量が「１１０」に、キュー＃２のパケット蓄積量が「７０」になっている。この状態ではキュー＃１のパケット蓄積量「１１０」が個別ＢＰ発行閾値Ｔｄｉ１（＝８０）以上となり、かつ総パケット量（５０＋１１０＋７０＝２３０）が、全体ＢＰ発行閾値Ｔａｉ（＝２００）以上となっている。このため、ＢＰ信号生成部２６は、キュー＃１についてＢＰ発行要求信号を生成する。
【０１１４】
この場合、キュー＃１は、全記憶領域１０３をキュー＃０〜＃２に均等に割り当てた場合の各キューの記憶容量「１００」よりも多いパケットを保持しているので、キュー＃１は、他のキュー＃０及び＃２のために用意された記憶領域を利用している、と言うことができる。
【０１１５】
図１６の（Ａ）及び図１６の（Ｂ）は出力パケットバッファの状態の説明図（その６）である。この場合、キュー＃０のパケット蓄積量が「２０」に、キュー＃１のパケット蓄積量が「６０」に、キュー＃２のパケット蓄積量が「１０」になっている。この状態では、キュー＃１のパケット蓄積量「６０」が個別ＢＰ解除閾値Ｔｄｒ１（＝４０）以上であるが、総パケット量（２０＋６０＋１０＝９０）が、全体ＢＰ解除閾値Ｔａｒ（＝１００）よりも小さくなる。このため、ＢＰ信号生成部２６は、キュー＃１についてのＢＰ解除要求信号を生成する。これによって物理ポートＰ＃１に対するバックプレッシャが解除される。
【０１１６】
本実施例よれば、複数のキューのうちの特定のキューにパケットが集中して蓄積されても、他のキューのパケット蓄積量が少ない場合には、複数のキューが記憶される記憶領域の空き領域に、上記特定キューに蓄積するパケットを格納することができる。このため、キューを記憶する記憶領域に利用効率が向上する。
【０１１７】
以下、出力パケットバッファメモリ２０へのパケットを書き込みの際のアドレス制御について説明する。出力パケットバッファメモリ２０が、各物理ポートＰに対してそれぞれ用意されるキューに対して割り当てる記憶領域の大きさは固定長ではない。出力パケットバッファメモリ２０は、各キューに対して割り当てる記憶領域の大きさを変更することができる。
【０１１８】
このようなバッファメモリの制御方法は、特許文献３にて開示されている。以下の説明では、出力パケットバッファメモリ２０のアドレス制御方法として、特許文献３に開示される方法と同様のアドレス制御方法を説明する。しかし、出力パケットバッファメモリ２０は、各キューに対して割り当てる記憶領域の大きさを変更することができればよく、出力パケットバッファメモリ２０を制御する方法は、以下の実施形態に限定されるものではない。
【０１１９】
図１７は、出力パケットバッファメモリ２０に記憶される出力パケットバッファ５の構成例の説明図である。出力パケットバッファ５は、アドレス空間「０」〜「ｍ」の各アドレスに、パケットを格納する。
【０１２０】
図１８は、図２に記されたアドレス管理部３１の概略構成の説明図である。参照符号５０はアドレス制御部を示し、参照符号５１はチェーン管理メモリを示し、参照符号５２は先頭アドレス管理メモリを示し、参照符号５３は末尾アドレス管理メモリを示す。アドレス管理部３１は、アドレス制御部５０と、チェーン管理メモリ５１と、先頭アドレス管理メモリ５２と、末尾アドレス管理メモリ５３を備える。
【０１２１】
チェーン管理メモリ５１には、チェーン管理テーブル１２０が記憶される。図１９は、チェーン管理テーブル１２０の構成例の説明図である。チェーン管理テーブル１２０は、出力パケットバッファ５に格納されたパケットの順序のつながりを、各パケットが格納された出力パケットバッファ５のアドレス値のチェーンを用いて管理する。またチェーン管理テーブル１２０は、出力パケットバッファ５内の空きアドレスを管理する。
【０１２２】
チェーン管理テーブル１２０は、パケットバッファのアドレス毎に、各アドレスに格納されたパケットの次のパケットが格納されたアドレス値を記憶する。チェーン管理テーブル１２０に記憶される、次のパケットの格納アドレスの値のことを、以下の説明において「次アドレス値」と記載することがある。
【０１２３】
またチェーン管理テーブル１２０は、パケットが格納されていない出力パケットバッファ５の空のアドレスについては、各空のアドレスの次にパケットを格納すべき他の空のアドレス値を格納する。チェーン管理テーブル１２０に記憶される、次にパケットを格納すべき他の空のアドレス値のことを、以下の説明において「空き次アドレス値」と記載することがある。
【０１２４】
チェーン管理テーブル１２０は、出力パケットバッファ５の各アドレス「１」〜「ｍ」にそれぞれ対応するアドレス「１」〜「ｍ」に、次アドレス値又は空き次アドレス値を格納する。
【０１２５】
先頭アドレス管理メモリ５２には、先頭アドレス管理テーブル１２１が記憶される。図２０は、先頭アドレス管理テーブル１２１の構成例の説明図である。先頭アドレス管理テーブル１２１は、各物理ポートＰ毎に、それぞれの物理ポートＰへ出力される先頭パケットが格納されている出力パケットバッファ５のアドレス値を格納する。先頭アドレス管理テーブル１２１に記憶される、先頭パケットが格納されている出力パケットバッファ５のアドレス値のことを、以下の説明において「先頭アドレス値」と記載することがある。
【０１２６】
また、先頭アドレス管理テーブル１２１は、出力パケットバッファ５に次にパケットを書き込む空き領域のアドレス値を格納する。先頭アドレス管理テーブル１２１に記憶される、出力パケットバッファ５に次にパケットを書き込む空き領域のアドレス値のことを、以下の説明において「空き領域の先頭アドレス値」と記載することがある。
【０１２７】
先頭アドレス管理テーブル１２１は、各物理ポートＰ＃０〜Ｐ＃ｎにそれぞれ対応するアドレス「０」〜「ｎ」に、それぞれの各物理ポートＰ＃０〜Ｐ＃ｎのへ出力される先頭パケットが格納されている出力パケットバッファ５のアドレス値を格納する。先頭アドレス管理テーブル１２１は、アドレス「ｎ＋１」に空き領域の先頭アドレス値を格納する。
【０１２８】
末尾アドレス管理メモリ５３には、末尾アドレス管理テーブル１２２が記憶される。図２１は、末尾アドレス管理テーブル１２２の構成例の説明図である。末尾アドレス管理テーブル１２２は、各物理ポートＰ毎に、それぞれの物理ポートＰへ出力される末尾パケットが格納されている出力パケットバッファ５のアドレス値を格納する。末尾アドレス管理テーブル１２２に記憶される、末尾パケットが格納されている出力パケットバッファ５のアドレス値のことを、以下の説明において「末尾アドレス値」と記載することがある。
【０１２９】
また、末尾アドレス管理テーブル１２２は、出力パケットバッファ５の空きアドレスのうち、パケットを書き込む順番が最後のアドレス値を格納する。末尾アドレス管理テーブル１２２に記憶される、パケットを書き込む順番が最後のアドレス値のことを、以下の説明において「空き領域の末尾アドレス値」と記載することがある。
【０１３０】
末尾アドレス管理テーブル１２２は、各物理ポートＰ＃０〜Ｐ＃ｎにそれぞれ対応するアドレス「０」〜「ｎ」に、それぞれの各物理ポートＰ＃０〜Ｐ＃ｎのへ出力される末尾パケットが格納されている出力パケットバッファ５のアドレス値を格納する。末尾アドレス管理テーブル１２２は、アドレス「ｎ＋１」に空き領域の先頭アドレス値を格納する。
【０１３１】
アドレス制御部５０の機能及び動作については、後述のＬＩＵカード２の動作の説明において併せて説明する。
【０１３２】
図２２は、図２に記された読出アドレス格納部３２の概略構成の説明図である。参照符号６１は宛先識別部を示し、参照符号６２は各物理ポートＰ＃０〜Ｐ＃ｎ毎に設けられた複数のアドレスＦＩＦＯを示す、参照符号６３は調停部を示す。読出アドレス格納部３２は、宛先識別部６１と、複数のアドレスＦＩＦＯ６２と、調停部６３を備える。
【０１３３】
宛先識別部６１は、アドレス管理部３１から読出アドレス値を受信する。宛先識別部６１は、スケジューラ３０により決定された宛先ポートを識別する。識別した宛先ポートは、受信した読出アドレス値に格納されたパケットの宛先ポートである。宛先識別部６１は、物理ポートＰ＃０〜Ｐ＃ｎ毎に用意された複数のアドレスＦＩＦＯ６２のうちいずれのアドレスＦＩＦＯに、受信した読出アドレス値を格納するかを選択し、選択したアドレスＦＩＦＯに読出アドレスを格納する。
【０１３４】
アドレスＦＩＦＯ６２は、物理ポートＰ＃０〜Ｐ＃ｎ毎に、出力するパケットを読み出す読出アドレス値を格納する。図２３は、１つのアドレスＦＩＦＯ６２の構成例の説明図である。アドレスＦＩＦＯ６２は、アドレス空間「０」〜「ｘ」の各アドレスに、読出パケット値を格納する。
【０１３５】
図２２を参照する。調停部６３は、読出アドレス値を取り出すアドレスＦＩＦＯ６２を選択し、選択したアドレスＦＩＦＯ６２から取り出した読出アドレス値を読出制御部２２へ出力する。また、後述するようにバックプレッシャ信号Ｓｂｐにより物理ポートＰ毎にパケットの読出を停止する。
【０１３６】
ＬＩＵカード２がスイッチカード３からパケットを受信したときの動作を、図２４〜図３３を参照して説明する。図２４は、パケット受信時におけるＬＩＵカード２の動作の説明図（その１）である。まず、ある宛先ポートのキューにパケットが受信されていない状態においてパケットを最初に受信した時の動作を説明する。なお、以下の動作（１）〜（５）に関連する信号の各フローは、それぞれ図２４において点線（１）〜（５）により表されている。
【０１３７】
動作（１）において、スイッチカード３からパケットを受信したとき、書込制御部２１はパケット情報をアドレス制御部５０へ送信する。パケット情報は、受信したパケットの宛先ポートの識別情報及びパケットサイズを含む。アドレス制御部５０は、先頭アドレス管理テーブル１２１から、空き領域の先頭アドレス値を取得する。
【０１３８】
動作（２）において、アドレス制御部５０は、動作（１）で取得した空き領域の先頭アドレス値が示すアドレスの記憶内容を、チェーン管理テーブル１２０から読み出すことによって空き次アドレス値を取得する。アドレス制御部５０は、取得した空き次アドレス値を、先頭アドレス管理テーブル１２１のアドレス「ｎ＋１」に書き込むことによって、空き領域の先頭アドレス値を更新する。
【０１３９】
動作（３）において、アドレス制御部５０は、先頭アドレス管理テーブル１２１の宛先ポートに対応するアドレスに、動作（１）で取得した空き領域の先頭アドレス値を書き込む。これによって先頭アドレス管理テーブル１２１に記憶されている宛先ポートの先頭アドレス値が更新される。またアドレス制御部５０は、末尾アドレス管理テーブル１２２の宛先ポートに対応するアドレスにも、動作（１）で取得した空き領域の先頭アドレス値を書き込む。これによって末尾アドレス管理テーブル１２２に記憶されている宛先ポートの末尾アドレス値が更新される。
【０１４０】
動作（４）において、アドレス制御部５０は、スケジューラ３０へパケット情報を通知する。パケット情報は、スケジューラ３０の読出制御のために使用される。
【０１４１】
動作（５）において、アドレス制御部５０は、動作（１）で取得した空き領域の先頭アドレス値を書込制御部２１へ出力する。書込制御部２１は、その空き領域の先頭アドレス値が示す出力パケットバッファ５のアドレスに受信パケットを格納する。
【０１４２】
図２５は、パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その１）である。図２５に示す状態では、また出力パケットバッファ５にパケットが格納されていない。このため、出力パケットバッファ５は全て空である。また、チェーン管理テーブル１２０は、空き次アドレスのみによって満たされている。
【０１４３】
チェーン管理テーブル１２０は各アドレスのアドレス値は、１つのアドレス（本例ではアドレス「０」）を除いて、他のいずれかの１つのアドレスに格納された空き次アドレス値によって指定される。このような各アドレスに格納された空き次アドレス値によって、チェーン管理テーブル１２０は各アドレスが連鎖的に繋がれている。チェーン管理テーブル１２０の各アドレスは、出力パケットバッファ５の各アドレスに一対一に対応している。したがって、チェーン管理テーブル１２０は、空き次アドレス値による各アドレスの連鎖によって、出力パケットバッファ５の空きアドレスのチェーンを記憶することができる。
【０１４４】
先頭アドレス管理テーブル１２１には、まだ先頭アドレス値が格納されておらず、空き領域の先頭アドレス値は「０」である。末尾アドレス管理テーブル１２２にも、まだ末尾アドレス値が格納されておらず、空き領域の末尾アドレス値は「ｎ」である。
【０１４５】
図２６は、パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その２）である。受信されたバッファＡ１、Ｂ１及びＣ１は、それぞれ物理ポートＰ＃０〜Ｐ＃２を宛先ポートとするパケットである。パケットＡ１、Ｂ１及びＣ１の順でこれらパケットを受信することによって、出力パケットバッファ５のアドレス「０」、「１」及び「２」にそれぞれパケットＡ１、Ｂ１及びＣ１が格納される。
【０１４６】
出力パケットバッファ５のアドレス「０」、「１」及び「２」に格納されたパケットの次のパケットはまだ格納されていないので、チェーン管理テーブル１２０のアドレス「０」、「１」及び「２」に格納される次アドレス値は意味を持たない。
【０１４７】
先頭アドレス管理テーブル１２１のアドレス「０」、「１」及び「２」には、パケットＡ１〜Ｃ１がそれぞれ格納された出力パケットバッファ５のアドレス「０」、「１」及び「２」が格納される。出力パケットバッファ５のアドレス「０」、「１」及び「２」にパケットが書き込まれることにより、空き領域の先頭アドレス値は「３」になる。
【０１４８】
末尾アドレス管理テーブル１２２のアドレス「０」、「１」及び「２」には、パケットＡ１〜Ｃ１がそれぞれ格納された出力パケットバッファ５のアドレス「０」、「１」及び「２」が格納される。空き領域の末尾アドレス値は「ｎ」のままである。
【０１４９】
図２７は、パケット受信時におけるＬＩＵカード２の動作の説明図（その２）である。まず、既にパケットを受信しているキューにおいて、さらにパケットが受信される時の動作を説明する。なお、以下の動作（１）〜（６）に関連する信号の各フローは、それぞれ図２７において点線（１）〜（６）により表されている。
【０１５０】
動作（１）において、スイッチカード３からパケットを受信したとき、書込制御部２１はパケット情報をアドレス制御部５０へ送信する。アドレス制御部５０は、先頭アドレス管理テーブル１２１から、空き領域の先頭アドレス値を取得する。
【０１５１】
動作（２）において、アドレス制御部５０は、動作（１）で取得した空き領域の先頭アドレス値が示すアドレスの記憶内容を、チェーン管理テーブル１２０から読み出すことによって空き次アドレス値を取得する。アドレス制御部５０は、取得した空き次アドレス値を、先頭アドレス管理テーブル１２１のアドレス「ｎ＋１」に書き込むことによって、空き領域の先頭アドレス値を更新する。
【０１５２】
動作（３）において、アドレス制御部５０は、末尾アドレス管理テーブル１２２の宛先ポートに対応するアドレスに、動作（１）で取得した空き領域の先頭アドレス値を書き込む。これによって末尾アドレス管理テーブル１２２に記憶されている宛先ポートの末尾アドレス値が更新される。
【０１５３】
動作（４）において、アドレス制御部５０は、宛先ポートに対応するアドレスの記憶内容を先頭アドレス管理テーブル１２１から読み出し、宛先ポートの先頭アドレス値を取得する。アドレス制御部５０は、チェーン管理テーブル１２０の、宛先ポートの先頭アドレス値が示すアドレスに、動作（１）で取得した空き領域の先頭アドレス値を書き込む。これによって、チェーン管理テーブル１２０に記憶されている、宛先ポート宛のパケットが格納されている出力パケットバッファ５のアドレス値のチェーンが更新される。
【０１５４】
動作（５）において、アドレス制御部５０は、スケジューラ３０へパケット情報を通知する。
【０１５５】
動作（６）において、アドレス制御部５０は、動作（１）で取得した空き領域の先頭アドレス値を書込制御部２１へ出力する。書込制御部２１は、その空き領域の先頭アドレス値が示す出力パケットバッファ５のアドレスに受信パケットを格納する。
【０１５６】
なお、１つのパケットのデータが複数アドレスの記憶領域を使用する場合も、上記動作と同様に、空きアドレスの取得とアドレス値のチェーンの更新を１パケット内で複数回行い、パケット内をチェーンで繋いで行けばよい。
【０１５７】
図２８は、パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その３）である。受信されたバッファＡ２は、物理ポートＰ＃０を宛先ポートとするパケットである。図２６の（Ｃ）の状態の先頭アドレス管理テーブル１２１に格納された空き領域の先頭アドレス値は「３」であるため、パケットＡ２は、出力パケットバッファ５のアドレス「３」に格納される。
【０１５８】
チェーン管理テーブル１２０のアドレス「０」には、次アドレス値「３」が格納される。この次アドレス値によって、出力パケットバッファ５のアドレス「０」に格納されたパケットＡ１の次パケットＡ２は、アドレス「３」に格納されることが記憶される。このように、チェーン管理テーブル１２０のあるアドレス値Ａｄ１のアドレスに格納されるアドレス値Ａｄ２のアドレスには、出力パケットバッファ５のアドレス値Ａｄ１のアドレスに格納されるパケットの次のパケットが格納される。
【０１５９】
チェーン管理テーブル１２０の各アドレスは、出力パケットバッファ５の各アドレスに一対一に対応している。このため、チェーン管理テーブル１２０の各アドレスは、それぞれに格納された次アドレス値によって連鎖的に繋がれる。チェーン管理テーブル１２０は、次アドレス値による各アドレスの連鎖によって、各宛先ポート宛のパケットが格納されたアドレスのチェーンを記憶する。
【０１６０】
また、チェーン管理テーブル１２０のアドレス「３」に格納されたパケットＡ２の次のパケットはまだ格納されていないので、チェーン管理テーブル１２０のアドレス「３」に格納される次アドレス値は意味を持たない。
【０１６１】
出力パケットバッファ５のアドレス「３」にパケットＡ２が書き込まれることにより、先頭アドレス管理テーブル１２１に格納される空き領域の先頭アドレス値は「４」になる。出力パケットバッファ５のアドレス「３」に物理ポートＰ＃０宛のパケットＡ２が書き込まれることにより、末尾アドレス管理テーブル１２２の宛先ポートＰ＃０に対応するアドレス「０」に記憶される宛先ポートＰ＃０の末尾アドレス値が「３」に更新される。
【０１６２】
図２９は、パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その４）である。受信されたバッファＣ２は、物理ポートＰ＃２を宛先ポートとするパケットである。図２８の（Ｃ）の状態の先頭アドレス管理テーブル１２１に格納された空き領域の先頭アドレス値は「４」であるため、パケットＣ２は、出力パケットバッファ５のアドレス「４」に格納される。
【０１６３】
チェーン管理テーブル１２０のアドレス「２」には、次アドレス値「４」が格納される。この次アドレス値によって、出力パケットバッファ５のアドレス「２」に格納されたパケットＣ１の次パケットＣ２は、アドレス「４」に格納されることが記憶される。また、チェーン管理テーブル１２０のアドレス「４」に格納されたパケットＣ２の次のパケットはまだ格納されていないので、チェーン管理テーブル１２０のアドレス「４」に格納される次アドレス値は意味を持たない。
【０１６４】
出力パケットバッファ５のアドレス「４」にパケットＣ２が書き込まれることにより、先頭アドレス管理テーブル１２１に格納される空き領域の先頭アドレス値は「５」になる。出力パケットバッファ５のアドレス「４」に物理ポートＰ＃２宛のパケットＣ２が書き込まれることにより、末尾アドレス管理テーブル１２２の宛先ポートＰ＃２に対応するアドレス「２」に記憶される宛先ポートＰ＃０の末尾アドレス値が「４」に更新される。
【０１６５】
図３０は、パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その５）である。受信されたバッファＡ３は、物理ポートＰ＃０を宛先ポートとするパケットである。図２９の（Ｃ）の状態の先頭アドレス管理テーブル１２１に格納された空き領域の先頭アドレス値は「５」であるため、パケットＡ３は、出力パケットバッファ５のアドレス「５」に格納される。
【０１６６】
チェーン管理テーブル１２０のアドレス「３」には、次アドレス値「５」が格納される。この次アドレス値によって、出力パケットバッファ５のアドレス「３」に格納されたパケットＡ２の次パケットＡ３は、アドレス「５」に格納されることが記憶される。また、チェーン管理テーブル１２０のアドレス「５」に格納されたパケットＡ３の次のパケットはまだ格納されていないので、チェーン管理テーブル１２０のアドレス「５」に格納される次アドレス値は意味を持たない。
【０１６７】
出力パケットバッファ５のアドレス「５」にパケットＡ３が書き込まれることにより、先頭アドレス管理テーブル１２１に格納される空き領域の先頭アドレス値は「６」になる。出力パケットバッファ５のアドレス「５」に物理ポートＰ＃０宛のパケットＡ３が書き込まれることにより、末尾アドレス管理テーブル１２２の宛先ポートＰ＃０に対応するアドレス「０」に記憶される宛先ポートＰ＃０の末尾アドレス値が「５」に更新される。
【０１６８】
図３１は、パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その６）である。受信されたバッファＢ２は、物理ポートＰ＃１を宛先ポートとするパケットである。図３０の（Ｃ）の状態の先頭アドレス管理テーブル１２１に格納された空き領域の先頭アドレス値は「６」であるため、パケットＢ２は、出力パケットバッファ５のアドレス「６」に格納される。
【０１６９】
チェーン管理テーブル１２０のアドレス「１」には、次アドレス値「６」が格納される。この次アドレス値によって、出力パケットバッファ５のアドレス「１」に格納されたパケットＢ１の次パケットＢ２は、アドレス「６」に格納されることが記憶される。また、チェーン管理テーブル１２０のアドレス「６」に格納されたパケットＢ２の次のパケットはまだ格納されていないので、チェーン管理テーブル１２０のアドレス「６」に格納される次アドレス値は意味を持たない。
【０１７０】
出力パケットバッファ５のアドレス「６」にパケットＢ２が書き込まれることにより、先頭アドレス管理テーブル１２１に格納される空き領域の先頭アドレス値は「７」になる。出力パケットバッファ５のアドレス「６」に物理ポートＰ＃１宛のパケットＢ２が書き込まれることにより、末尾アドレス管理テーブル１２２の宛先ポートＰ＃１に対応するアドレス「１」に記憶される宛先ポートＰ＃１の末尾アドレス値が「６」に更新される。
【０１７１】
図３２は、パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その７）である。受信されたバッファＣ３は、物理ポートＰ＃２を宛先ポートとするパケットである。図３１の（Ｃ）の状態の先頭アドレス管理テーブル１２１に格納された空き領域の先頭アドレス値は「７」であるため、パケットＣ３は、出力パケットバッファ５のアドレス「７」に格納される。
【０１７２】
チェーン管理テーブル１２０のアドレス「４」には、次アドレス値「７」が格納される。この次アドレス値によって、出力パケットバッファ５のアドレス「４」に格納されたパケットＣ２の次パケットＣ３は、アドレス「７」に格納されることが記憶される。また、チェーン管理テーブル１２０のアドレス「７」に格納されたパケットＣ３の次のパケットはまだ格納されていないので、チェーン管理テーブル１２０のアドレス「７」に格納される次アドレス値は意味を持たない。
【０１７３】
出力パケットバッファ５のアドレス「７」にパケットＣ３が書き込まれることにより、先頭アドレス管理テーブル１２１に格納される空き領域の先頭アドレス値は「８」になる。出力パケットバッファ５のアドレス「７」に物理ポートＰ＃２宛のパケットＣ３が書き込まれることにより、末尾アドレス管理テーブル１２２の宛先ポートＰ＃２に対応するアドレス「２」に記憶される宛先ポートＰ＃２の末尾アドレス値が「７」に更新される。
【０１７４】
図３３は、パケット受信時の出力パケットバッファ及び各テーブルの状態の説明図（その８）である。受信されたバッファＢ３は、物理ポートＰ＃１を宛先ポートとするパケットである。図３２の（Ｃ）の状態の先頭アドレス管理テーブル１２１に格納された空き領域の先頭アドレス値は「８」であるため、パケットＢ３は、出力パケットバッファ５のアドレス「８」に格納される。
【０１７５】
チェーン管理テーブル１２０のアドレス「６」には、次アドレス値「８」が格納される。この次アドレス値によって、出力パケットバッファ５のアドレス「６」に格納されたパケットＢ２の次パケットＢ３は、アドレス「８」に格納されることが記憶される。また、チェーン管理テーブル１２０のアドレス「８」に格納されたパケットＢ３の次のパケットはまだ格納されていないので、チェーン管理テーブル１２０のアドレス「８」に格納される次アドレス値は意味を持たない。
【０１７６】
出力パケットバッファ５のアドレス「８」にパケットＢ３が書き込まれることにより、先頭アドレス管理テーブル１２１に格納される空き領域の先頭アドレス値は「９」になる。出力パケットバッファ５のアドレス「８」に物理ポートＰ＃１宛のパケットＢ３が書き込まれることにより、末尾アドレス管理テーブル１２２の宛先ポートＰ＃１に対応するアドレス「１」に記憶される宛先ポートＰ＃１の末尾アドレス値が「８」に更新される。
【０１７７】
図３４は、パケット送信時におけるＬＩＵカード２の動作の説明図である。なお、以下の動作（１）〜（７）に関連する信号の各フローは、それぞれ図３４において点線（１）〜（７）により表されている。
【０１７８】
動作（１）において、スケジューラ３０は、スケジューリング処理によってパケットを出力する物理ポートＰを決定する。簡単のため、図３４に関する以下の説明において、スケジューラ３０により決定されたこの物理ポートを「物理ポートＰ＃ｘ」と記載する。スケジューラ３０は、物理ポートＰ＃ｘをアドレス制御部５０に通知する。アドレス制御部５０は、物理ポートＰ＃ｘに対応するアドレスの記憶内容を先頭アドレス管理テーブル１２１から読み出すことにより、物理ポートＰ＃ｘの先頭アドレス値を読み出す。
【０１７９】
動作（２）において、アドレス制御部５０は、動作（１）で取得した物理ポートＰ＃ｘの先頭アドレス値が示すアドレスの記憶内容をチェーン管理テーブル１２０から読み出すことによって、次アドレス値を取得する。アドレス制御部５０は、取得した次アドレス値を、先頭アドレス管理テーブル１２１の物理ポートＰ＃ｘに対応するアドレスへ書き込む。これによって、先頭アドレス管理テーブル１２１に記憶された物理ポートＰ＃ｘの先頭アドレス値が更新される。
【０１８０】
動作（３）において、アドレス制御部５０は、動作（１）で取得した先頭アドレス値を読出アドレス値として読出アドレス格納部３２へ出力する。読出アドレス格納部３２の宛先識別部６１は、物理ポートＰ＃ｘに対して用意されたアドレスＦＩＦＯ６２に、先頭アドレス値を格納する。
【０１８１】
動作（４）において、アドレスＦＩＦＯ６２に蓄積された読出アドレス値は、調停部６３からの読出要求により、アドレスＦＩＦＯ６２から読み出される。調停部６３は、例えばラウンドロビン動作によって、読出アドレス値を取り出すアドレスＦＩＦＯ６２を決定してよい。調停部６３は、取り出した読出アドレス値を読出制御部２２へ出力する。読出制御部２２は、調停部６３から出力された読み出しアドレス値が示すアドレスの記憶内容を出力パケットバッファ５から読み出すことにより、パケットを取得する。パケットは、デマルチプレクサ２３を介して物理ポートＰ＃ｘから出力される。
【０１８２】
なお、デマルチプレクサ２３は各物理ポートＰの実レートに応じて、パケットの出力制御を行っている。デマルチプレクサ２３は、バースト等により実レートを越える状態が起きた場合は、パケットの出力を停止し、またバックプレッシャ信号Ｓｂｐを調停部６３に送出する。このとき、調停部６３は該当ポートからの読出を停止する。
【０１８３】
動作（５）において、アドレス制御部５０は、末尾アドレス管理テーブル１２２から空き領域の末尾アドレス値を読み出す。アドレス制御部５０は、チェーン管理テーブル１２０の、空き領域の末尾アドレス値が示すアドレスに、動作（１）で取得した物理ポートＰ＃ｘの先頭アドレス値を書き込む。これによって、動作（４）でパケットの読み出しが終了したアドレス値を、新しい空き領域の末尾アドレス値として現在の空き領域の末尾アドレス値の後に繋げるチェーンが、チェーン管理テーブル１２０に記憶される。
【０１８４】
動作（６）において、アドレス制御部５０は、チェーン管理テーブル１２０の、動作（１）で取得した物理ポートＰ＃ｘの先頭アドレス値が示すアドレスに「空き次アドレス＝なし」を書き込む。
【０１８５】
動作（７）において、アドレス制御部５０は、末尾アドレス管理テーブル１２２のアドレス「ｎ＋１」に上記（１）で取得した物理ポートＰ＃ｘの先頭アドレス値を書き込むことによって、空き領域の末尾アドレス値を更新する。
【０１８６】
以下、図３５〜４０を参照して、パケット送信時の出力パケットバッファ及び各テーブルの状態の遷移を説明する。図３５は、パケット送信時の出力パケットバッファ及び各テーブルの状態の説明図（その１）である。図３３に示した状態からパケットＡ１が送信される場合を想定する。
【０１８７】
スケジューラ３０の指示により、宛先ポートＰ＃０のパケットＡ１を送信するとき、アドレス制御部５０は、図３３の（Ｃ）の先頭アドレス管理テーブル１２１に記憶された宛先ポートＰ＃０の先頭アドレス値「０」を、読出アドレス格納部３２のアドレスＦＩＦＯ６２に格納しておく。
【０１８８】
調停部６３が、その調停動作により、読出制御部３３へ宛先ポートＰ＃０の先頭アドレス値「０」を与えることにより、宛先ポートＰ＃０の先頭アドレス値「０」における受信パケットＡ１が、出力パケットバッファ５から読み出される。
【０１８９】
パケットが読み出された出力パケットバッファ５のアドレス「０」は空き状態となる。チェーン管理テーブル１２０の、現在の空き領域の末尾アドレス値「ｎ」のアドレスの記憶内容が、新たな空き領域の末尾アドレス値「０」へ更新される。また、チェーン管理テーブル１２０のアドレス「０」の記憶内容の値は、「空き次アドレス＝なし」に更新される。
【０１９０】
図３３の（Ｂ）の状態のチェーン管理テーブル１２０では、出力パケットバッファ５のアドレス「０」に格納されたパケットＡ１の次のパケットＡ２の格納先として、アドレス「３」が指定されている。このため、先頭アドレス管理テーブル１２１に記憶される、宛先ポートＰ＃０の先頭アドレス値が「３」へ更新される。
末尾アドレス管理テーブル１２２に記憶される空き領域の末尾アドレス値が、新たな空き領域の末尾アドレス値「０」へ更新される。
【０１９１】
図３６は、パケット送信時の出力パケットバッファ及び各テーブルの状態の説明図（その２）である。図３５に示した状態からパケットＡ２が送信される場合を想定する。パケットＡ２の格納先は、出力パケットバッファ５のアドレス「３」である。このため、パケットが読み出された出力パケットバッファ５のアドレス「３」は空き状態となる。
【０１９２】
チェーン管理テーブル１２０の、現在の空き領域の末尾アドレス値「０」のアドレスの記憶内容が、新たな空き領域の末尾アドレス値「３」へ更新される。また、チェーン管理テーブル１２０のアドレス「３」の記憶内容の値は、「空き次アドレス＝なし」に更新される。
【０１９３】
図３５の（Ｂ）の状態のチェーン管理テーブル１２０では、出力パケットバッファ５のアドレス「３」に格納されたパケットＡ２の次のパケットＡ３の格納先として、アドレス「５」が指定されている。このため、先頭アドレス管理テーブル１２１に記憶される、宛先ポートＰ＃０の先頭アドレス値が「５」へ更新される。
末尾アドレス管理テーブル１２２に記憶される空き領域の末尾アドレス値が、新たな空き領域の末尾アドレス値「３」へ更新される。
【０１９４】
以上の実施例を含む実施形態に関し、更に以下の付記を開示する。
【０１９５】
（付記１）
複数の通信ポートと、
前記複数の通信ポート間でパケットを交換するスイッチと、
前記複数の通信ポートから出力するパケットをそれぞれ保持する複数のキューが記憶される記憶部と、
いずれかの前記通信ポートの前記キューに保持されるパケット量が所定の第１閾値以上であり、かつ前記複数のキューに保持されるパケット量の合計が所定の第２閾値以上であるとき、前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを停止させる停止信号を生成する停止信号生成部と、
を備えるパケット伝送装置。
【０１９６】
（付記２）
前記スイッチへのパケットの入力を制御するパケット入力制御部を備え、
前記停止信号は、前記パケット入力制御部が前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを停止させる付記１に記載のパケット伝送装置。
【０１９７】
（付記３）
前記いずれかの通信ポートの前記キューに保持されるパケット量が所定の第３閾値よりも小さくなり、又は前記複数のキューに保持されるパケット量の合計が所定の第４閾値よりも小さくなったとき、前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを許可する許可信号を生成する許可信号生成部を備える付記１又は２に記載のパケット伝送装置。
【０１９８】
（付記４）
前記スイッチへのパケットの入力を制御するパケット入力制御部を備え、
前記許可信号は、前記パケット入力制御部が前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを許可する付記３に記載のパケット伝送装置。
【０１９９】
（付記５）
複数の回線間におけるパケット交換を行うスイッチを有するパケット伝送装置に設けられ、前記回線と前記スイッチとの間において前記パケットのインタフェース制御を行う回線インタフェースユニットであって、
前記複数の回線に接続される複数の前記通信ポートと、
前記複数の通信ポートから出力するパケットをそれぞれ保持する複数のキューが記憶される記憶部と、
いずれかの前記通信ポートの前記キューに保持されるパケット量が所定の第１閾値以上であり、かつ前記複数のキューに保持されるパケット量の合計が所定の第２閾値以上であるとき、前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを停止させる停止信号を生成する停止信号生成部と、
を備える回線インタフェースユニット。
【０２００】
（付記６）
前記パケット伝送装置は、複数の前記回線インタフェースユニットを備え、
各前記回線インタフェースユニットは、前記スイッチを経由して他の前記回線インタフェースユニットへ伝送される停止信号パケットを、前記停止信号に従って生成する停止信号パケット生成部を備え、
前記停止信号パケットは、前記スイッチへの前記いずれかの通信ポート宛のパケットの入力の停止を要求するパケットである、付記５に記載の回線インタフェースユニット。
【０２０１】
（付記７）
複数の通信ポートと、前記複数の通信ポート間でパケットを交換するスイッチと、前記複数の通信ポートから出力するパケットをそれぞれ保持する複数のキューが記憶される記憶部と、を備えるパケット伝送装置の制御方法であって、
いずれかの前記通信ポートの前記キューに保持されるパケット量と所定の第１閾値との間の比較、及び前記複数のキューに保持されるパケット量の合計と所定の第２閾値との間の比較をそれぞれ行い、
いずれかの前記通信ポートの前記キューに保持されるパケット量が所定の第１閾値以上であり、かつ前記複数のキューに保持されるパケット量の合計が所定の第２閾値以上であるとき、前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを停止する、パケット伝送装置の制御方法。
【０２０２】
（付記８）
前記いずれかの通信ポートの前記キューに保持されるパケット量が所定の第３閾値よりも小さくなり、又は前記複数のキューに保持されるパケット量の合計が所定の第４閾値よりも小さくなったとき、前記いずれかの通信ポート宛のパケットを前記スイッチへ入力するのを許可する付記７に記載のパケット伝送装置の制御方法。
【符号の説明】
【０２０３】
１    パケット伝送装置
２    ＬＩＵカード
２０    出力パケットバッファメモリ
２４    キュー長管理部
２６    ＢＰ信号生成部
２７    ＢＰパケット生成部
Ｐ＃０〜Ｐ＃ｎ    物理ポート
【図１】
2010226208.tif 000003
【図２】
2010226208.tif 000004
【図３】
2010226208.tif 000005
【図４】
2010226208.tif 000006
【図５】
2010226208.tif 000007
【図６】
2010226208.tif 000008
【図７】
2010226208.tif 000009
【図８】
2010226208.tif 000010
【図９】
2010226208.tif 000011
【図１０】
2010226208.tif 000012
【図１１】
2010226208.tif 000013
【図１２】
2010226208.tif 000014
【図１３】
2010226208.tif 000015
【図１４】
2010226208.tif 000016
【図１５】
2010226208.tif 000017
【図１６】
2010226208.tif 000018
【図１７】
2010226208.tif 000019
【図１８】
2010226208.tif 000020
【図１９】
2010226208.tif 000021
【図２０】
2010226208.tif 000022
【図２１】
2010226208.tif 000023
【図２２】
2010226208.tif 000024
【図２３】
2010226208.tif 000025
【図２４】
2010226208.tif 000026
【図２５】
2010226208.tif 000027
【図２６】
2010226208.tif 000028
【図２７】
2010226208.tif 000029
【図２８】
2010226208.tif 000030
【図２９】
2010226208.tif 000031
【図３０】
2010226208.tif 000032
【図３１】
2010226208.tif 000033
【図３２】
2010226208.tif 000034
【図３３】
2010226208.tif 000035
【図３４】
2010226208.tif 000036
【図３５】
2010226208.tif 000037
【図３６】
2010226208.tif 000038