JP3872716B2 - パケット出力制御装置 - Google Patents
パケット出力制御装置 Download PDFInfo
- Publication number
- JP3872716B2 JP3872716B2 JP2002129149A JP2002129149A JP3872716B2 JP 3872716 B2 JP3872716 B2 JP 3872716B2 JP 2002129149 A JP2002129149 A JP 2002129149A JP 2002129149 A JP2002129149 A JP 2002129149A JP 3872716 B2 JP3872716 B2 JP 3872716B2
- Authority
- JP
- Japan
- Prior art keywords
- packet
- output
- queue
- output line
- dequeue
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/50—Overload detection or protection within a single switching element
- H04L49/505—Corrective measures
- H04L49/508—Head of Line Blocking Avoidance
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/22—Traffic shaping
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/24—Traffic characterised by specific attributes, e.g. priority or QoS
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/50—Queue scheduling
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/50—Queue scheduling
- H04L47/56—Queue scheduling implementing delay-aware scheduling
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/50—Overload detection or protection within a single switching element
- H04L49/505—Corrective measures
- H04L49/506—Backpressure
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、パケットを格納する複数のキューをそなえたパケット出力制御装置に関し、特に、各キューに格納された先頭パケットの中から最も早く転送を完了することのできるパケットを効率良く選出して出力するパケット出力制御装置に関する。
【０００２】
【従来の技術】
近年のADSL，CATV，FTTH等の急速な普及により、専用線をもたない一般家庭や企業まで高速なインターネット環境が提供されるようになり、従来の電子メールやファイル転送だけでなく、映画やニュース等の大容量の情報量をもったコンテンツの配信もインターネット上で広く行なわれるようになってきた。
【０００３】
今後も、更に様々なアプリケーションが、ＩＰ（Internet Protocol）ネットワーク上に統合され、サービスが提供されていくものと思われる。このようなＬＡＮやインターネットを背景に、ＩＰネットワークの中核を成すルータ装置（Ｌ３スイッチ）の市場規模は、今後さらに拡大していくと思われ、情報量の大容量化とともにその処理能力の向上も求められている。
【０００４】
また、電子メール，ＦＴＰ（File Transfer Protocol）によるファイル転送や動画・音声配信など、要求されるトラフィック特性（許容廃棄率や遅延等）の異なる種々のサービスをＩＰネットワークでストレスなく提供するためには、それぞれの品質を劣化させないように、ルータ機器等にてトラフィクフロー（ユーザが転送要求する複数の連続したパケット）に応じた優先制御や帯域制御を行なうＱｏＳ（Quality of Service）制御が必要である。
【０００５】
例えば、ＦＴＰデータやＷＷＷ（World Wide Web）データのようなトラフィックデータに対しては、各フローのデータを最大限のリソース（主に、帯域幅）を利用し、高速且つ公平に転送することが重要視され、ルータ装置には、これらのフロー（あるいはフローの集合）毎に予約された帯域幅を、各フローに割り当てて保証するとともに、出力回線（出力リンク）において余ったリソースを、これらの各フロー間で公平に再配分する制御を、高速出力リンクに応じて高速処理することが要求される。
【０００６】
これに対し、ＶｏＩＰ（Voice over IP）のような音声トラフィックデータに対しては、リンクの帯域幅を最大限且つ公平に利用するよりも、固定の転送レートを保証し、遅延ジッタを最小にすることが重要である。
ここで、ＱｏＳ制御の仕組みを図４５に示す。即ち、この図４５に示すように、既存のＱｏＳ制御では、下記に示す各処理（１）〜（４）（図４５中では、丸付き数字で示す）が実行される。
【０００７】
（１）入力したＩＰパケットのＩＰアドレスやＭＡＣ（Media Access Control）アドレス及びＴｏＳ（Type of Service）フィールドを参照して、入力パケットをアプリケーション毎のフローに分類（識別）する。
（２）識別したフロー番号に従って、入力パケットをキューに振り分ける（キューイング）。
【０００８】
（３）各キューに設定された優先度や帯域に従って、キュー先頭のパケットの長さやキューイング時刻などを基に各キューの先頭パケットをデキューする順序やタイミングを計算（スケジューリング）する。
（４）スケジューリング結果に従って、各キューの先頭パケットをキューから読み出す（デキュー）。
【０００９】
以上の処理により、キューに振り分けたフロー毎のＱｏＳ制御が可能となる。
さて、パケットスケジューリングに関しては様々なアルゴリズムがあるが、ＷＦＱ(Weighted Fair Queuing)やＷＲＲ(Weighted Round Robin)等が代表的であり、これらのうちＷＦＱは可変長パケットに対して公平な帯域分配を行なう手法としては最適と考えられている。以下、このＷＦＱのアルゴリズムについて説明する。
【００１０】
或る固定帯域が予約されたキューの帯域制御の概念を図４６に示す。ここで、キューの設定（予約）帯域をφ、スケジューリング対象となるキューの先頭パケットのパケット長をＬとすると、そのパケットの送出完了に必要な時間はＬ／φで求められる。帯域制御は、このＬ／φによりパケットの出力完了予定時刻（スケジューリング評価値）Fを求め、タイマが示す現時刻Trが出力完了予定時刻Ｆを超えた時に、次のパケットの出力を許可するというものである。なお、送信完了予定時刻Fは以下の式（１）によって求められる。
【００１１】
【数１】
【００１２】
ここで、この式（１）において、Tiはフロー番号ｋのｉ番目のパケット到着時刻、Liはフロー番号ｋのｉ番目のパケット長を示し、max[Fi-1, Ti]は、前パケット送信完了予定時刻Ｆi-1とパケット到着時刻Tiとを比較し、大きい方を選択する処理を示す。
したがって、式（１）は、パケット到着時刻Ti＜前パケット送信完了予定時刻Fi-1の場合は、図４６中に丸付き数字１で示すように、パケット送信完了予定時刻FiがFi-1を基準に計算され、逆に、パケット到着時刻Ti ≧ 前パケット送信完了予定時刻Fi-1の場合は、図４６中に丸付き数字２で示すように、パケット送信完了予定時刻Fiがパケット到着時刻Tiを基準に計算されることを意味する。
【００１３】
そして、ＷＦＱでは、パケット到着時に、キューの先頭に存在する全てのフロー番号kのｉ番目のパケットに対して、以下の式（２）を計算し、スケジューリング評価値Fを算出する。
【００１４】
【数２】
【００１５】
ここで、この式（２）において、φkはフローkの予約帯域、φbはアクティブ状態のＷＦＱのφkの合計（Σφk）、ＲはＷＦＱの合計帯域をそれぞれ示す。なお、説明を簡単にするために、上記の式（２）を以下の式（３）に置き換える。
【００１６】
【数３】
【００１７】
そして、この式（３）におけるアクティブ状態キューの先頭パケットのα値を、常時、現タイマ値Trと比較し、Tr≧αとなるパケットの集合から最も小さなスケジューリング評価値（以下、単に「評価値」ともいう）Fをもつパケットを選択し出力する。したがって、直前パケットの転送に長時間を要したキューや、転送に長時間を要する先頭パケットのキューに対しては、パケット出力（デキュー）の優先順位が下がることになる。
【００１８】
このようにして、ＷＦＱでは、パケット送信完了予定時刻Fiによるパケット出力順序の重み付け制御を行なって、キュー間の公平なパケット出力を実現するとともに、非アクティブキューに割り当てられている余剰帯域をアクティブキューに公平に割り当てて、リソースの有効利用を図り、アクティブキューのパケットをより高速に転送してサービスの向上を図っている。
【００１９】
なお、上記のアクティブ状態とは、キューに少なくとも１つパケットが存在している状態を意味し、このように少なくとも１つパケットが存在するキューをアクティブキューと呼ぶ。そして、上記の式（３）におけるγ値はかかるアクティブ状態の変化によって、逐次、変化することになる。このため、評価値Fは、アクティブ状態が変化する度に、全てのキューについて評価値Fの再計算を行なう必要がある。
【００２０】
例えば、図４７に示すように、５本のキューに対してそれぞれ１００Ｍｂｐｓの帯域が予約され、それら５本中３本のキューにパケットが存在している場合（３本のキューのみがアクティブ状態の場合）、残り２本の空きキューに予約されている余剰帯域２００Ｍｂｐｓ分は３本のアクティブキューへ公平に分配され、それぞれ約１６７Ｍｂｐｓとなり、その帯域に従った再スケジューリングが行なわれて出力回線へパケットが出力（デキュー）されることになる。
【００２１】
【発明が解決しようとする課題】
従来、上述したＷＦＱにおけるスケジューリング評価値の演算は、プロセッサを用いたソフトウェアによる処理が主流であった。しかし、ソフトウェアによる処理では、シーケンシャルな処理しか行なえず、特に、リアルタイムに変化するγ値を反映させる再計算に非常に時間がかかり、同一出力回線や同一キューの連続パケットを処理する能力（スループット）が出ないという課題があった。
【００２２】
一方、スループット向上のために、ハードウェアによりスケジューリング評価値の演算を実現しようとすると、前記の式（２）に除算と乗算の演算が含まれるために、乗算器，除算器を用いる必要があり、回路規模が増大し、ＬＳＩやＦＰＧＡ（Field Programmable Gate Array）への実装が困難であった。そのため、ハードウェアによりＷＦＱを実現する場合でも、実装可能なキューの数が出力回線当たり数本程度に制限されてきた。
【００２３】
また、出力回線が複数存在する場合には、それらの出力回線毎に専用のスケジューラを設け、出力回線毎に使用するスケジューラを選択して動作させるという構成を採ることが考えられるが、これをハードウェアにより実現しようとすると、さらに回路規模が増大し、ＬＳＩやＦＰＧＡへの実装は略不可能となってしまう。そこで、従来は、上記γ値による再計算を行なわないバーチャルクロック等のＷＦＱの派生アルゴリズムを用いることで、前記γ値の再計算の演算量を削減する手法も考えられている。
【００２４】
しかしながら、かかるバーチャルクロック等の派生アルゴリズムを導入すると、例えば特開2000-101637号公報にも記載されているとおり、パケット送信完了予定時刻Fの時間軸が実時間とは異なる独自のものとなってしまうので、パケットの出力順序制御を行なうスケジューラを、サービス（ＱｏＳ）に応じて複数設けた場合、各スケジューラ間での最優先出力パケットの選択処理等、スケジューラ間の連携が困難になる。
【００２５】
上記の特開2000-101637号公報により提案されている技術は、かかるバーチャルクロック等の派生アルゴリズムを導入することなく、前記γの再計算の演算量を削減できるようにしたものであるが、本公知技術を用いたとしても、複数の出力回線をもつ装置におけるＷＦＱ（スケジューラ）を、装置規模を増大させることなく、ＬＳＩやＦＰＧＡへの実装が可能なものとして実現するのは困難であった。
【００２６】
即ち、上記公知技術では、前記β値に大きな差の無いパケット同士の送信完了予定時刻Fは前記γ値が変動したとしてもそれらの大小関係が入れ替わる確率が低く、仮に入れ替わってもその時刻差は微小であることに鑑み、前記β値に大きな差の無い評価値Fの集合をクラスタとしてクラスタリングし、γ値の変動についてはクラスタの先頭ポインタが示す評価値Fに対してのみ反映させることで、γ値の変動による評価値Fの再計算をクラスタ数（Ｍ）分だけに抑えて演算量を削減することが行なわれる。
【００２７】
しかし、かかるクラスタリングによるＷＦＱは、β値の格差が比較的小さく、クラスタ数Ｍ<<キュー個数Ｎであるときに演算量を削減するには有効であるが、サービス別に数十kbps〜数百kbps又は数Gbpsとφの値が変化する場合には、β値の変動幅の自由度が制限される、もしくは、そのβ値の変動幅に対応させてクラスタ数を変更する必要がある。
【００２８】
しかも、クラスタ内のγ値の変動は無視されるため、サービス品質に対してその誤差を許容できるクラスタ数の考察も必要になる。また、クラスタ内のポインタ管理のレイテンシがパケット長最小の連続パケット入力時におけるスケジューリングのボトルネックとなる。さらに、上記クラスタリングにより演算量を或る程度削減できたとしても、出力回線数が増えると、この場合も、スケジューラ数を増やす必要があるので、結局、ＬＳＩやＦＰＧＡへの実装は困難である。
【００２９】
本発明は、以上のような課題に鑑み創案されたもので、多様化，大容量化するインターネットサービス等に対して、多くのサービス毎にクラス分けして制御可能であるキューの本数と高精度の帯域制御、及びスループットの飛躍的な向上が可能であり、且つ、ハードウェアによる実装が可能である、小型で処理能力に優れたパケット出力制御装置を提供することを目的とする。
【００３０】
【課題を解決するための手段】
上記の目的を達成するために、本発明のパケット出力制御装置は、複数の出力回線毎に設けられた複数のキューと、入力されたパケットを当該パケットのフローに応じて該キューのいずれかにエンキューするエンキュー手段と、エンキュー手段により上記の各キューにエンキューされた各パケットについてのデキュー指示をスケジュールするパケットスケジューラと、パケットスケジューラからのデキュー指示によって指示されたキューからパケットをデキューするデキュー手段とをそなえるとともに、上記パケットスケジューラが、下記の各手段をそなえたことを特徴としている。
【００３１】
(1)同一出力回線に属する各キューにエンキューされた先頭パケットに関する少なくとも到着時刻情報及びパケットサイズ情報を含む所定のパラメータに基づいて当該先頭パケットの送信完了予定時刻を示す評価値をそれぞれ所定の評価値演算式により並列演算する並列演算手段
(2)並列演算手段での演算対象とする出力回線を選択的（時分割）に指定して同一出力回線に属する各キューの先頭パケットについてのパラメータを該並列演算手段に入力させる演算制御手段
(3)並列演算手段で求められた同一出力回線に属する各キューの先頭パケットの評価値に基づいて優先出力すべき先頭パケットの評価値を選出する同一出力回線内キュー間調停手段
(4)同一出力回線内キュー間調停手段で選出された評価値を該出力回線毎に保持し、該出力回線毎の評価値と該出力回線の設定帯域とに基づいて優先出力すべき先頭パケットを決定する出力回線間調停手段
(5)出力回線間調停手段で決定した先頭パケットについてのデキュー指示を該デキュー手段に与えるデキュー制御手段
ここで、上記の演算制御手段は、上記の各出力回線の設定帯域に応じた割合で時分割に該並列演算手段での演算対象とする出力回線を指定する時分割演算回線指定部をそなえて構成されていてもよい。
【００３２】
また、上記のパケットスケジューラは、入力パケットのパラメータに基づいて上記評価値演算式中で繰り返し演算が不要な項を予め全キューで共通化された前処理として演算し、当該演算結果を該並列演算手段での演算に用いられる中間変数として該並列演算手段に入力する前処理部をそなえていてもよい。
【００３３】
さらに、上記のパケットスケジューラは、同一出力回線に属する各キューうちパケットの存在しないキューに割り当てられている帯域を、パケットの存在する同一出力回線に属する他のキューに配分する帯域配分率を算出する帯域配分率算出手段をさらにそなえ、上記の並列演算手段が、上記の帯域配分率算出手段で算出された同じ帯域配分率に基づいて、上記の各評価値を再計算するように構成されていてもよい。
【００３４】
また、上記のパケットスケジューラは、上記複数の出力回線のうち同一パケットを配信すべき複数の出力回線を指定する配信先情報を保持する配信先情報保持手段と、この配信先情報保持手段に保持された配信先情報によって指定されている出力回線が上記演算制御手段によって指定される毎に、上記の並列演算手段で求められる同一キューについての評価値が、上記出力回線間調停手段での選定候補として当該出力回線間調停手段に入力されるように出力制御する配信制御手段とをそなえていてもよい。
【００３５】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
（Ａ）本発明の一実施形態の説明
図１は本発明の一実施形態としてのパケット出力制御装置の全体構成を示すブロック図で、この図１に示すパケット出力制御装置１は、フレームメモリ２，変換テーブル３，キュー管理部４，パケットスケジューラ５，メモリ制御部６及びタイムスタンプ部７をそなえて構成されている。
【００３６】
ここで、フレームメモリ２（以下、単に「メモリ２」と略記することがある）は、キューを構成する物理メモリで、キューイングするパケットデータの本体が本メモリ２に格納されるようになっている。また、変換テーブル３は、入力パケットの宛先ＩＰアドレス等のヘッダ情報を基にフロー識別を行ない、その識別結果に応じて入力パケットを適切なキューへ振り分けるためのもので、一般的に、ＣＡＭ（Content Addressable Memory）等を用いて構成される。
【００３７】
さらに、キュー管理部４は、キュー毎にパケット情報を論理的にリンクし、パケットデータのフレームメモリ２内でのポインタを決定・管理するとともに、エンキューポインタ及びデキューポインタをメモリ制御部６に与えて、入力パケットのエンキュー及びデキューを制御するものである。
パケットスケジューラ（以下、単に「スケジューラ」ともいう）５は、キューの先頭パケットのスケジュールパラメータ（後述）に基づいて、デキューすべきパケットの順番及びタイミングを計算（スケジュール）するもので、そのスケジュール結果に従って次にデキューすべき先頭パケットのキュー番号がキュー管理部４に通知されるようになっている。
【００３８】
メモリ制御部６は、キュー管理部４からエンキュー又はデキューするパケットのポインタ（アドレス）を受信し、そのポインタが示すフレームメモリ２のアドレスに対するパケットの書き込み／読み出し制御を行なうためのものである。
つまり、このメモリ制御部６と上記のキュー管理部４とで、入力パケットをそのパケットのフローに応じて複数のキューのいずれかにエンキューするエンキュー手段と、パケットスケジューラ５からのデキュー指示によって指示されたキューからパケットをデキューするデキュー手段としての機能が実現されていることになる。
【００３９】
タイムスタンプ部７は、キューにエンキューするパケット毎に、その到着時刻を付加するためのものである。
上述のごとく構成されたパケット出力制御装置１での処理の流れは、次のようになる。
(1)入力パケットに、タイムスタンプ部７が到着時刻を付加する。
【００４０】
(2)入力パケットのヘッダ情報，パケットサイズ，到着時刻を変換テーブル３に入力してフロー識別を行ない、適切なキュー番号を得る。
(3)キュー管理部４にてパケット情報を指定キューにリンクし、エンキューパケット本体のフレームメモリ２への格納（エンキュー）ポインタをメモリ制御部６に出力して書き込み指示を与える。
【００４１】
(4)メモリ制御部６は、キュー管理部４から受信したエンキューポインタが示すフレームメモリ２のアドレスに入力パケットデータ本体を書き込む。
(5)キュー管理部４は、エンキューしたパケットがキューの先頭であった場合、そのパケットのスケジュールパラメータをスケジューラ５へ入力する。
(6)スケジューラ５は、各キューの先頭パケットのスケジュールパラメータを基に、スケジューリング処理（スケジューリング評価値Fの演算）を行ない、デキューすべきパケットの順序およびタイミングを決定して、デキューすべきキュー番号をキュー管理部４に出力する。
【００４２】
(7)キュー管理部４は、スケジューラ５から受信したキュー番号の先頭パケットが存在するポインタ（デキューポインタ）をメモリ制御部６に出力してパケットの読み出し指示を与える。
(8)この際、キュー管理部４は、パケット情報のリンク構造の操作（更新）を行ない、当該キューにおいてデキューされるパケットに続いてパケットが存在する場合は、そのパケットを新たな先頭パケットとみなして、そのパケットのスケジュールパラメータをスケジューラ５へ送出する。
【００４３】
(9)メモリ制御部６は、キュー管理部４から受信したデキューポインタが示すメモリ２のアドレスに書き込まれているパケットデータを読み出す。
以上のようにして、パケット出力制御装置１においても、スケジューラ５にて、各キューの先頭パケットについてそれぞれスケジューリング評価値Fの演算を行ない、その評価値Fを基にデキューすべきパケットの順序及びタイミングがスケジュールされるわけであるが、１０００本を超えるような膨大な数のキューに対応した全並列化は実質不可能なので、本実施形態のスケジューラ５では、評価値演算対象の出力回線を時分割に切り替えることで、同一出力回線に属する各キューの先頭パケットについての評価値Fの並列演算を、全出力回線間で共通に行なえるようになっている。
【００４４】
（Ａ１）パケットスケジューラの詳細説明
以下、本実施形態の要部であるスケジューラ５の詳細について説明する。
図２及び図３はいずれも上記のパケットスケジューラ５の構成を示すブロック図であるが、これらの図２及び図３に示すように、本実施形態のスケジューラ５は、前処理部５１，演算制御部５２，先頭パケットメモリ５３，γ演算部５４，並列演算部５５，選択部５６，シェーピング部５７，ポート間調停部５８，デキュー制御部５９及びタイマ６０等をそなえて構成されている。
【００４５】
また、先頭パケットメモリ５３には、複数の出力回線（ポート）＃１〜＃Ｍ毎にそれぞれ複数のフロー（ここでは、ｎ）に対応して設けられたキュー＃ｊ−１〜＃ｊ−ｎ（ただし、ｊは１〜Ｍ）が設けられ、並列演算部５５には、各キュー＃ｊ−１〜＃ｊ−ｎに対応して複数のスケジューリング評価値演算器５５−１〜５５−ｎが設けられ、シェーピング部５７には、出力回線＃１〜＃Ｍに対応して複数の出力回線シェーピング回路５７−１〜５７−Ｍが設けられている。
【００４６】
そして、この図２及び図３に示すスケジューラ５では、概略して、次のような処理が実行される。
即ち、まず、前処理部５１において、スケジュール演算の中間変数βが求められ、これがキュー＃ｊ−ｋ（ｋ＝１〜ｎ）毎に先頭パケットメモリ５３に他のスケジュールパラメータ（到着時刻Ti等）と共に格納される。そして、演算制御部５２において所定のタイムスロット毎にスケジューリングを行なう演算対象の出力回線＃ｊが決定され、それに従って先頭パケットメモリ５３から同一出力回線＃ｊに属する各キューの先頭パケットについてのスケジュールパラメータの組が同時（並列）に読み出されて、並列演算部５５の各スケジューリング評価値演算器（以下、単に「演算器」という）５５−１〜５５−ｎへ入力される。
【００４７】
各演算器５５−１〜５５−ｎでは、スケジューリング評価値F1〜Fnがパイプライン制御で求められ、後述する評価値有効フラグと共に選択部５６へ出力される。選択部５６は、有効な演算器５５−ｋの出力の中からスケジューリング評価値の最小値（当該出力回線＃ｊへ優先出力すべきパケット）を選出して、シェーピング部５７の出力回線シェーピング回路５７−ｊに出力回線＃ｊ別に格納する。
【００４８】
そして、シェーピング部５７は、出力回線シェーピング回路５７−ｊでの後述するシェーピング処理により、出力回線＃ｊの設定帯域に応じた処理オーバーフロー及びパケットバースト出力制御のための評価値の補正を行なった上で、補正後の評価値をポート間調停部５８へ出力し、ポート間調停部５８では、出力回線＃ｊ間での評価値の最小値選択を行なってデキュー制御部５９に出力する。
【００４９】
これにより、デキュー制御部５９は、ポート間調停部５８で選出された評価値に対応するキュー＃ｊ−ｋに対するデキュー指示を発生してキュー管理部４へ出力するとともに、そのキュー番号をキュー識別信号として前処理部５１，演算制御部５２，並列演算部５５，シェーピング部５７，ポート間調停部５８及びデキュー制御部５９へそれぞれフィードバックする。なお、このフィードバック信号は、後述するようにパイプライン処理上の同一評価値更新に用いられる。
【００５０】
以下、上述した各部の機能についてより詳細に説明する。
まず、先頭パケットメモリ５３は、図３に示すように、キュー管理部４から受信される、入力パケットのパケットサイズ情報や到着時刻情報等のスケジュールパラメータを上述のごとく出力回線（ポート）＃１〜＃Ｍ毎にそれぞれ複数のフローに対応して設けられたキュー＃ｊ−１〜＃ｊ−ｎにより保持・管理するものである。
【００５１】
そして、この先頭パケットメモリ５３は、本実施形態では、図８により後述するように、各演算器５５−１〜５５−ｎ用の先頭パケットメモリ５３−１〜５３−ｎをそなえて構成され、これらの先頭パケットメモリ５３−１〜５３−ｎに、出力回線＃１〜＃Ｍ別に各キュー＃ｊ−ｋのスケジュールデータが格納されるようになっている。
【００５２】
なお、これらの先頭パケットメモリ５３−１〜５３−ｎには、後述するように、先頭パケットを含む連続する複数パケットについてのスケジュールパラメータが格納される。また、本先頭パケットメモリ５３（５３−１〜５３−ｎ）は、例えば、ＲＡＭ等を用いて構成される。
また、並列演算部５５は、各キュー＃ｊ−１〜＃ｊ−ｎと１対１に対応付けられたｎ個の演算器５５−１〜５５−ｎにより、同一出力回線＃ｊ内の全キュー＃ｊ−１〜＃ｊ−ｎのスケジューリング評価値F1〜Fnを、それぞれ、下記に示すＷＦＱ演算式（４）により、所定の１タイムスロット内で同時に（並列に）演算するようになっている。
【００５３】
【数４】
【００５４】
つまり、本実施形態のスケジューラ５は、所定のタイムスロットによって演算対象とする出力回線＃ｊを切り替える、つまり、先頭パケットメモリ５３から読み出す各キュー＃ｊ−１〜＃ｊ−ｎの先頭パケットのスケジュールパラメータの組を切り替えることで、各出力回線＃１〜＃Ｍ間で各演算器５５−１〜５５−ｎを共有する構成になっているのである。
【００５５】
そして、上記のタイムスロットの割り当て、即ち、スケジュールパラメータ読み出し対象の出力回線＃ｊの時分割指定（以下、「時分割演算回線指定」ともいう）を制御するのが、上記の演算制御部（時分割演算回線指定部）５２であり、本実施形態では、例えば、図５に示すような演算出力回線テーブル５２１に基づいて上記時分割演算回線指定が行なわれるようになっている。
【００５６】
即ち、回線組み合わせ毎の１６ステップ〔タイムスロット（ＴＳ）〕を１サイクル（所定周期）とした場合、演算制御部５２は、例えば、図５中に丸付き数字１で示す1Gbps x16本(回線＃１〜＃１６：図５では単に回線１〜１６と表記している)の出力回線設定であれば全出力回線に対する割り当ての機会は同じであるので、デキュー制御部５９からのフィードバック情報（デキュー識別信号：デキュー指示が発生したキューを識別するための情報）を受信する毎に、１タイムスロット（ＴＳ）＝１回線の割合で演算ポートを決定することになる。
【００５７】
これに対し、図５中に丸付き数字２で示す1Gbps×8本(回線＃１〜回線＃８)，10Gbps×１本（回線＃９）の組み合わせでは、8Gbps:10Gbps=4:5であるが、簡略化して、回線＃１:回線＃２:回線＃３:回線＃４:回線＃５:回線＃６:回線＃７:回線＃８:回線＃９=1:1:1:1:1:1:1:1:8の割合で演算ポートが演算制御部５２によって決定されることになる。同様に、図５中に丸付き数字３〜５で示す設定の場合も、出力回線＃ｊの設定帯域が大きいものほど、その設定帯域に応じて１サイクル内でのタイムスロット割り当ての機会が多くなるように、演算ポートが演算制御部５２によって決定される。
【００５８】
なお、この演算ポートの割り当てにおいて、演算制御部５２は、例えば図６に示すように、出力回線＃ｊ毎に、先頭パケットメモリ５３からのパケット有無判定フラグ（図４参照）によってアクティブ回線／ノンアクティブ回線の判定を行ない、次ステップの回線＃ｊ＋１がノンアクティブである場合にはアクティブな回線＃ｊまで遷移して、演算ポートを指定する処理を行なう。
【００５９】
以上のような出力回線＃ｊ毎の設定帯域に応じた演算ポート切り替えを行なうことで、設定帯域の大きな出力回線＃ｊに属するキュー＃ｊ−ｋ（ｋ＝１〜ｎ）に対するデキュー指示を出力できる間隔を、設定帯域の小さな他の出力回線＃ｐ（ただし、ｐ＝１〜Ｍで、ｐ≠ｊ）に属するキュー＃ｐ−ｋに対するデキュー指示の間隔よりも狭くすることができ、設定帯域の大きな出力回線＃ｊほど、スループットを向上することができる。
【００６０】
例えば図７に示すように、（１）（図７中では、（１）〜（７）を丸付き数字で示す）回線Ａ，Ｂ，Ｃの出力帯域比をＡ：Ｂ：Ｃ＝２：１：１として演算ポート切り替えを行なったとすると、（２）先頭パケットメモリ５３からのスケジュールパラメータ読出，演算器５５−ｋでの（３）α値選択及びβ×γ演算処理，（４）評価値F（α＋β×γ）の有効判定処理，（５）選択部５６での最小評価値Fの選出処理及び（６）シェーピング部５７でのシェーピング処理から成るパイプライン処理上に存在するパケット情報の割合が、出力回線帯域が大きいほど多くなり、その結果、（７）ポート間調停部５８でのデキューバスシェーピング処理では、回線Ａに属するキューに対するデキュー指示の発生間隔が、回線Ｃに属するキューに対するデキュー指示の発生間隔よりも短くなり、回線Ａのスループットが向上するのである。
【００６１】
ところで、上記の各演算器５５−ｋの構成であるが、前記の評価値演算式（４）による演算機能を実現するために、例えば図４に示すような構成を有している。即ち、各演算器５５−ｋは、α選択回路５５１，出力判定回路５５２，セレクタ５５３，乗算器５５４及び加算器５５５をそなえて構成されている。なお、この図４において、６１は前回の評価値演算結果Fi-1を出力回線＃ｊ毎に保持する前評価値メモリを示すが、図２及び図３においてはその図示を省略している。
【００６２】
ここで、α選択回路５５１は、先頭パケットメモリ５３から読み出されたパケット到着時刻Tiと、前評価値メモリ６１に出力回線＃ｊ毎に保持された前回の評価値演算結果Fi-1とを比較して、値の大きい方を選出することにより、前記の評価値演算式（４）におけるmax{Fi-1, Ti}（フロー番号ｋを表す添え字は省略）を求めるものである。なお、前評価値メモリ６１からの前回の評価値演算結果Fi-1の読み出しは、演算制御部５２が演算ポート指定信号を読み出しアドレスとして指定することによって行なわれる。
【００６３】
また、出力判定回路５５２は、デキュー制御部５９によるデキュー指示の発生毎に、先頭パケットメモリ５３から上述した演算ポート切り替えに併せて出力回線＃ｊ毎の状態（パケットの有無）を表すパケット有無フラグと、タイマ６０からの現時刻情報Trとに基づいて、最終的に加算器５５５で求められる評価値Fiの有効／無効を判定して、その判定結果を出力するもので、ここでは、タイマ６０の現在時刻Tr>評価値Fiであれば「有効」を表すフラグが出力されるようになっている。なお、この評価値有効フラグが「無効」を示している評価値Fiは後段の選択部５６での調停対象外となる。
【００６４】
さらに、セレクタ５５３（帯域配分率選択手段）は、ＷＦＱ／固定切り替え設定に応じて、γ演算部５４で求められた前記の評価値演算式（４）におけるγ値（余剰帯域の帯域再配分率）と固定値〔固定帯域配分率（γ＝１）〕とを選択的に出力するもので、ＷＦＱによる帯域制御（余剰帯域の再配分）を行なう場合にはγ演算部５４の出力を選択し、余剰帯域の再配分を行なわない固定帯域制御を行なう場合には固定値γ＝１を選択して、乗算器５５４へ出力するようになっている。なお、上記の評価値演算式（４）においてγ＝１とすると、
【００６５】
【数５】
【００６６】
となる。また、上記の固定値γ＝１は、レジスタ等（固定帯域制御手段）に設定・保持される。
このように、演算器５５−ｋ毎に、ＷＦＱ／固定帯域キューの設定を行なうことにより、出力回線＃ｊ毎に、ＷＦＱによる帯域制御と固定帯域制御との構成比を任意に変更することが可能となり、出力回線＃ｊ毎に様々な帯域制御が可能となる。なお、かかるＷＦＱ／固定帯域キューの設定は、例えば図３５に示すように、各演算器５５−ｋに、出力回線＃ｊ毎にＷＦＱ／固定帯域キューの設定情報を保持する設定レジスタ５５６をもたせ、演算制御部５２からの出力回線指定に従って該当設定情報をＷＦＱ／固定帯域キュー切り替え信号としてセレクタ５５３に入力することで行なえる。
【００６７】
例えば、回線Ａ，Ｂ，Ｃ，Ｄの４回線について設定レジスタ５５６に「固定帯域制御」の設定情報を設定したとすると、図３６に示すように、回線Ａ，Ｂ，Ｃ，Ｄが演算対象として演算制御部５２により指定された場合は、γ＝１がセレクタ５５３により選択され、それ以外の回線についてはγ演算部５４で再計算されたγ値が選択されることになる。
【００６８】
次に、図４に示す乗算器５５４は、上記セレクタ５５３の出力と先頭パケットメモリ５３から読み出された中間変数βとを乗算することにより、前記の評価値演算式（４）におけるβ×γの項を求めるものであり、加算器５５５は、この乗算器５５４で求められたβ×γと、上述したα選択回路５５１で選択されたαとを加算することにより、前記の評価値演算式（４）で表される評価値Fi（＝α＋β×γ）を求めるものである。
【００６９】
なお、上記の中間変数β（＝Li／φi）は、パケット長Liとキュー＃ｊ−ｋの設定帯域φiによって求まり、設定帯域φiは時間による変化がないものと定義すると、デキュー指示発生毎の繰り返し演算は不要である。そこで、本実施形態においては、前処理部５１において、中間変数βを前処理として各キュー＃ｊ−ｋに共通で演算し、その結果を、同一出力回線＃ｊの各キュー＃ｊ−ｋの先頭パケットに関するスケジュールパラメータ（到着時刻Ti，パケット長Li）とともに同一タイムスロットで読み出されるように先頭パケットメモリ５３に保持させるようにする。
【００７０】
即ち、例えば図８に示すように、先頭パケットメモリ５３を、それぞれ出力回線＃ｊ別に各キュー＃ｊ−ｋの先頭パケットを保持する演算器５３−ｋ用の先頭パケットメモリ５３−１〜５３−ｎにより構成し、前処理部５１１において、キュー＃ｊ−ｋ毎に予め設定帯域φiが保持されたφ設定テーブル５１１から、キュー管理部４から通知されるキュー番号をアドレスとして該当キュー＃ｊ−ｋの設定帯域φiを読み出し、この設定帯域φiを除算器５１２にて同じくキュー管理部４から通知されるパケット長Liで除算することにより中間変数βを求め、これを、同一出力回線＃ｊに属する各キュー＃ｊ−ｋの先頭パケットについての中間変数として各演算器５３−ｋに保持させるようにするのである。このようにして、中間変数βの演算を前処理部５１で出力回線＃ｊ間で共通に行なうようにすることで、回路規模の削減を図ることが可能である。
【００７１】
さて次に、図２及び図４に示すγ演算部（帯域配分率算出手段）５４は、前記の評価値演算式（４）におけるγを求めるものであるが、本実施形態では、得られたγ値を各演算器５５−ｋでの同一出力回線＃ｊに属する各キュー＃ｊ−ｋについての評価値演算に同時に反映させるようになっている。そして、その構成は、例えば図９に示すように、γ演算制御部５４１，φ設定テーブル５４２，φ加減算器５４３，セレクタ５４４，Ｒ設定テーブル５４５，セレクタ５４６及び除算器５４７をそなえて構成されている。
【００７２】
ここで、上記のφ設定テーブル５４２は、キュー＃ｊ−ｋ毎の設定帯域φiを保持するものであり、φ加減算器５４３は、γ演算制御部１からの加減算指示信号に従って、このφ設定テーブル５４２から読み出されるφi値によりそれまでのφi値の累積値φb（アクティブキューの設定帯域の合計）についての加減算処理を出力回線（以下、単に「回線」ともいう）＃ｊ別に行なうもので、このために、図１０及び図１１に示すように、それぞれ加減算器５４３１とレジスタ５４３２とをそなえて成る回線＃ｊ毎のφb累積器５４３−１〜５４３−Ｍを有して構成されている。
【００７３】
また、セレクタ５４４は、演算制御部５２からの演算タイムスロット割り当てにより演算対象である回線＃ｊについて上記φ加減算器５４３（累積器５４３−ｊ）で求められた累積値φbを選択出力するものであり、Ｒ設定テーブル５４５は、出力回線＃ｊ毎の設定帯域Ｒ（＝同一出力回線＃ｊ内キュー＃ｊ−ｋの設定帯域φiの合計）を保持するものであり、セレクタ５４５は、セレクタ５４４と同様に、演算制御部５２からの演算タイムスロット割り当てにより演算対象である回線＃ｊについてのＲ値を選択出力するものである。
【００７４】
さらに、除算器５４７は、セレクタ５４４で選択されたφbを、セレクタ５４６で選択されたＲ値で除算することによりγ値を求めるもので、このようにして得られたγ値が回線＃ｊ毎の余剰帯域の再配分率として各演算器５５−ｋに入力されて、そのγ値（再配分率）による前記評価値演算式（４）の再計算が演算対象回線＃ｊの全キュー＃ｊ−ｋに対して同時に行なわれ、各キュー＃ｊ−ｋの先頭パケットについての評価値Fiに同時に反映される。
【００７５】
そして、γ演算制御部５４１は、エンキュー又はデキューのイベント発生毎に、該当キュー＃ｊ−ｋのパケット有無判定（つまり、アクティブキュー／ノンアクティブキューの判定）を行ない、φ加減算器５４３に対して、図１２に示すフローチャートに従った回線＃ｊ毎の加減算指示信号を出力することにより、エンキュー及びデキュー発生毎に、そのときのアクティブキュー数に応じた累積値φb（アクティブキューの合計予約帯域）の更新を行なうものである。
【００７６】
なお、各キュー＃ｊ−ｋのパケット有無判定は、本実施形態では、キュー管理部４がそなえるパケット数カウンタ（図示省略）ではなく、先頭パケットメモリ５３（５３−ｋ）におけるパケットの有無により判定を行なう。これは、図２５〜図３０により後述するようなキュー管理部４による連続パケットの管理により、常に、先頭パケットメモリ５３にパケットが存在するようになっているため、先頭パケットメモリ５３の状態を監視すれば、キュー＃ｊ−ｋ上のパケット有無判定が可能なためである。
【００７７】
さて、γ演算制御部５４１の動作であるが、γ演算制御部５４１は、スケジューラ５に入力があるか否かを監視するとともに（ステップＳ１）、デキュー制御部５９によりデキュー指示が発生したか否かを監視しており（ステップＳ６）、例えば、スケジューラ５にキュー番号の入力があると（ステップＳ１でＹＥＳと判定されると）、φ設定テーブル５４２に対してφiの読み出しアドレスを与えて、入力キュー番号に対応する演算対象のキュー＃ｊ−ｋについてのφiを読み出す（ステップＳ２）。
【００７８】
そして、γ演算制御部５４１は、該当キュー＃ｊ−ｋの先頭パケットメモリ５３（５３−ｋ）が空き状態であるか否かを確認し（ステップＳ３）、空き状態であれば（ステップＳ３でＹＥＳと判定されれば）、デキュー制御部５９による同一キュー＃ｊ−ｋへのデキュー指示が同時発生しているか否かをさらに確認し（ステップＳ４）、デキュー指示が同時発生していなければ（ステップＳ４でＮＯと判定されれば）、エンキュー指示の発生であるから、エンキュー指示の発生した回線＃ｊ−ｋの累積器５４３−ｊの加減算器５４３１に対して設定帯域φiの加算指示を与えて、レジスタ５４３２に保持されている累積値φbにφ設定テーブル５４２から読み出されたφi値を加算させる（ステップＳ５）。
【００７９】
なお、上記の処理において、スケジューラ５への入力が無い場合（ステップＳ１でＮＯの場合）や、該当キュー＃ｊ−ｋの先頭パケットメモリ５３（５３−ｋ）が空き状態でない場合（ステップＳ３でＮＯの場合）、γ演算制御部５４１は、引き続き、スケジューラ５への入力の有無，デキュー指示の発生の有無の監視を行なう。また、同一キュー＃ｊ−ｋに対するエンキュー指示とデキュー指示とが同時発生した場合（ステップＳ４でＹＥＳの場合）も、当該キュー＃ｊ−ｋのパケット数に変わりがないから、γ演算制御部５４１は、監視動作を継続する。
【００８０】
これに対して、デキュー制御部５９によるデキュー指示が発生した場合（ステップＳ６でＹＥＳの場合）、γ演算制御部５４１は、上記のステップＳ２と同様に、入力キュー番号に対応する演算対象のキュー＃ｊ−ｋについての設定帯域φiを読み出し（ステップＳ７）、そのキュー番号に対応する先頭パケットメモリ５３（５３−ｋ）に格納されているパケットが残り１パケットであるか否かを確認する（ステップＳ８）。
【００８１】
その結果、パケットが残り１パケットであると（ステップＳ８でＹＥＳと判定されると）、γ演算制御部５４１は、さらに、同一キュー＃ｊ−ｋに対するエンキュー指示が同時発生しているか否かを確認し（ステップＳ９）、エンキュー指示が発生していなければ（ステップＳ９でＮＯと判定されれば）、デキュー指示の発生した回線＃ｊ−ｋに対応する累積器５４３−ｊの加減算器５４３１に対して設定帯域φiの減算指示を与えて、レジスタ５４３２に保持されている累積値φbにφ設定テーブル５４２から読み出されたφi値を減算させる（ステップＳ１０）。
【００８２】
なお、この場合も、デキュー指示が発生していない場合（ステップＳ６でＮＯの場合）や、該当キュー＃ｊ−ｋの先頭パケットメモリ５３（５３−ｋ）に２以上のパケットが残っている場合（ステップＳ８でＮＯの場合）、γ演算制御部５４１は、監視動作を継続する。また、同一キュー＃ｊ−ｋに対するデキュー指示とエンキュー指示とが同時発生した場合（ステップＳ９でＹＥＳの場合）も、当該キュー＃ｊ−ｋのパケット数に変わりがないから、γ演算制御部５４１は、監視動作を継続する。
【００８３】
以上のようにして、γ演算部５４では、エンキュー及びデキューの発生毎に、そのエンキュー及びデキューのキュー番号情報を基に、該当キュー＃ｊ−ｋの設定帯域φiがφ設定テーブル５４２から読み出されて、その設定帯域φiによる累積値φbの更新が行なわれ、更新後の累積値φbに基づいてγ値が再計算される。そして、このγ値が各演算器５５−ｋにそれぞれ入力されることにより、同一出力回線＃ｊに属する各キュー＃ｊ−ｋの先頭パケットについての評価値Fiに同時に反映されるのである。
【００８４】
このように、γ値（再配分率）の計算を回線＃ｊ間で共通化することにより、回路規模の削減を図ることが可能である。
さて次に、図２及び図３に示す選択部（同一出力回線内キュー間調停手段）５６は、上述した各演算器５５−１〜５５−ｎで求められた各評価値F1〜Fnの中から最小の評価値（優先出力すべき評価値）を選出するものである。例えば図１３に示すように、キューａ，ｂ，ｃ，ｄの先頭パケットの到着時刻がそれぞれTai，Tbj，Tck，Tdm（Tai＜Tbj＜Tck＜Tdm）であり、キューａ，ｂ，ｃ，ｄの前回の先頭パケットについての評価値（送信完了予定時刻）がそれぞれ、Fai-1（＜Tai），Fbj-1（＜Tbj），Fck-1（＜Tck），Fdk-1（＞Tdk）であったとする。
【００８５】
すると、この場合、キューａ，ｂ，ｃについては、それぞれ、前回の送信完了予定時刻よりも到着時刻の方が遅い（Fai-1＜Tai，Fbj-1＜Tbj，Fck-1＜Tckの関係にある）ので、前記のα値はそれぞれ到着時刻Tai，Tbj，Tckが基準となり、キューｄについては、逆に、前回の送信完了予定時刻よりも到着時刻の方が早い（Fdk-1＞Tdkの関係にある）ので、前記のα値は前回の送信完了予定時刻Fdk-1が基準となって、それぞれについての今回の送信完了予定時刻Fai，Fbj，Fck，Fdm（Fai＜Fbj＜Fck＜Fdm）が演算器５５−ｋで求められることになる。
【００８６】
したがって、図１３の場合、キューａ≧キューｂ≧キューｃ≧キューｄの優先順位で選出が行なわれることになる。ただし、この図１３の場合、キューｄについてのα値がタイマ６０の計時値（Timer値）よりも大きい（α＜Timer値）ので、キューｄについての出力は許可されない。つまり、この場合は、キューa，ｂ，ｃ間でのみ出力調停が行なわれ、Fai＜Fbj＜Fckであるので、キューａ≧キューｂ≧キューｃの優先順位で選出が行なわれることになる。
【００８７】
なお、本選択部５６の調停アルゴリズムは、図２０（Ａ）及び図２０（Ｂ）により後述するポート間調停部５８の調停アルゴリズムと同様である。
次に、シェーピング部５７の出力回線シェーピング回路５７−ｊは、それぞれ、上述のごとく選択部５６により選出された評価値Fを出力回線シェーピング回路５７−１〜５７−Mにより出力回線＃ｊ別にバッファリングして、各出力回線＃ｊの設定帯域に応じたシェーピング処理を行なうもので、本実施形態では、例えば図１４に示すように、シェーピング制御部５７１とパケット情報レジスタ５７２とをそなえて構成され、シェーピング制御部５７１は、例えば図１５に示すように、さらに、出力判定値演算回路５７１−１，出力判定回路５７１−２及びバースト制御回路５７１−３をそなえて構成されている。
【００８８】
ここで、上記のシェーピング制御部５７１は、回線＃ｊ毎の設定帯域に応じた出力帯域のシェーピング制御を行なうものであり、パケット情報レジスタ５７２は、同一回線＃ｊに属する各キュー＃ｊ−ｋの先頭パケットについてのスケジューリング結果（評価値F）を保持するものである。
そして、シェーピング制御部５７１において、出力判定値演算回路５７１−１は、デキュー制御部５９による出力回線＃ｊのデキュー発生時に、下記式（６）によって、出力判定値Ci（評価値Fの補正値）の演算を行なうものである。
【００８９】
【数６】
【００９０】
なお、この式（６）において、Ci はパケット出力完了予定時刻、Ci-1は前パケット出力完了予定時刻、SEL｛Ci-1，Timer｝はCi-1とTimer値のいずれかの選択、Li はデキューパケット長、Ｒは出力回線設定帯域をそれぞれ表す。
このため、本出力判定値演算回路５７１−１は、例えば図１６に示すように、セレクタ５７１１，除算器５７１２，加算器５７１３及びレジスタ（Ｒ）５７１４をそなえて構成され、セレクタ５７１１により上記式（６）の第１項〔SEL｛Ci-1，Timer｝〕の機能が実現され、除算器５７１２により上記式（６）の第２項（Li／Ｒ）の演算が実現され、加算器５７１３により上記式（６）の第１項及び第２項の加算機能が実現されている。なお、レジスタ５７１４は、セレクタ５７１１の出力をラッチするためのものである。
【００９１】
そして、出力判定回路５７１−２は、上記の出力判定値Ci＜Timer値となった時に、次パケットについての出力判定（許可）信号をアサートする処理を行なうものである。この出力判定信号により出力許可されていない（ディゼーブルの）出力判定値Ciは、後段でのポート間調停部５８での最小値選択処理から除外されることになる。なお、上記出力判定信号は、出力パケットが無い場合と、後述するデキュー制御部５９からのフィードバック出力（マスク指示信号）によってもディセーブルされる。
【００９２】
図１７にシェーピング処理の概念を示す。或る先頭パケット（パケット番号“０”）についてデキューが発生した場合、まず、出力判定値演算回路５７１により、下記に示す式（７）により、出力判定値C0が演算される。
【００９３】
【数７】
【００９４】
ただし、ここでは、パケット番号“０”のパケットは前パケットが無効であるか、もしくは、後述するバースト制御回路５７１−３によるバースト制御により、デキュー時のTimer値（D0）がSEL｛Ci-1，Timer｝の項（セレクタ５７１１）において選択されているものとする。
そして、タイマ６０のTimer値（現在時刻）＜C0である時は、次パケットの出力が出力回線シェーピング回路５７−ｊ（パケット情報レジスタ５７２）にバッファリングされていてもそのデータ出力は許可されず（該当回線＃ｊの出力判定フラグが「無効」）、図１７に示すように、Timer値≧C0の条件で、次パケットについてのデータ出力が許可（該当回線＃ｊの出力判定フラグが「有効」）される。
【００９５】
このようにして、出力回線＃ｊ毎に、出力回線帯域設定に応じた出力判定フラグによる出力調停を行なうことにより、前出力完了時刻の早いパケットから優先的にデキューを発生させることができるので、同一出力回線＃ｊ内のキュー＃ｊ−ｋ単位の出力帯域の取り戻し制御を効果的に行なうことができる。また、調停回路の簡素化も可能である。
【００９６】
ところで、この場合、上記の出力判定値と実際のデキュー処理時刻との差（D‐C）が処理レイテンシ及びデキューバス上の輻輳等の影響により大きくなった場合、次パケット以降の出力がバースト的に行なわれ、デキューバス上の輻輳及びフレームメモリ２上での処理の破綻を招くおそれがある。
そこで、その保護のために、本実施形態では、図１５に示すバースト制御回路５７１−３により、上記の差の監視によるバースト出力制御を行なう。図１８にバースト制御の概念を示す。なお、この図１８において、Bはバースト出力を許可する制限値を表し、各出力回線シェーピング回路５７−ｊに設定される。
【００９７】
そして、図１８の（１）（図１８中では、（１），（２）を丸付き数字で示す）に示す場合は、デキュー発生時にTimer値‐C＜Bであるから、上記の式（７）のSEL｛Ci-1，Timer｝の項においてCi-1が選択され、次パケット出力のバースト出力が許可される。
これに対し、図１８の（２）に示す場合は、デキュー発生時にTimer値‐C≧Bであるから、上記の式（７）のSEL｛Ci-1，Timer｝の項においてTimer値が選択され、次パケットのバースト出力は許可されない。
【００９８】
このように、出力回線＃ｊ毎のバースト出力制御を行なうことにより、出力回線＃ｊ内のキュー＃ｊ−ｋ単位の帯域の取り戻しを許可しながら、出力回線＃ｊ毎のデキューによるオーバーフローを回避することが可能になる。
次に、図２及び図３に示すポート間調停部５８は、上述したシェーピング部５７から出力される出力判定フラグと出力判定値Ciとを基に、出力回線＃ｊ間のパケット出力の調停（有効な出力判定値Ciの中からの最小値選択）を行ない、これにより選択された出力回線＃ｊのキュー＃ｊ−ｋについての判定値をデキュー制御部５９へ出力するものである。
【００９９】
このポート間調停制御部５８による調停制御の概念を図１９に示す。この図１９に示す場合、現在時刻（Timer値）において、回線Ａ〜Ｄについてのシェーピング部５７での出力判定フラグの状態は、回線Ｄについては出力完了予定時刻C≧Timer値であるのでディゼーブル（「無効」）、他の回線Ａ，Ｂ，Ｃについては出力完了予定時刻C＜Timer値であるのでイネーブル（「有効」）となっている。
【０１００】
従って、ポート間調停部５８では、回線Ｄを除く回線Ａ，Ｂ，Ｃの中で、デキュー制御部５９への出力回線＃ｊを決定することになる。ここで、回線Ａ，Ｂ，Ｃについてのパケット出力完了予定時刻Cai，Cbj，Cckの関係は、Cbj＞Cai＞Cckとなっているが、回線Ｃについてはシェーピング部５７での上記バースト制御によってバースト制限値を超えているために出力完了予定時刻Cckは無効となり、その代わりにシェーピング部５７への入力時刻Sck+1が基準となる。
【０１０１】
これにより、ポート間調停部５８は、Cbj＞Sck+1＞Caiの関係から、回線Ａ≧回線Ｃ≧回線Ｂの優先順位でデキュー制御部５９へデータ出力することになる。つまり、上記のシェーピング部５７及びポート間調停部５８は、選択部５６で選出された評価値を出力回線＃ｊ毎に保持し、それらの評価値と出力回線＃ｊの設定帯域とに基づいて優先出力すべき先頭パケットを決定する出力回線間調停手段としての機能を果たしているのである。
【０１０２】
なお、以上の調停アルゴリズムをＣ言語のような記述で表現したものを図２０（Ｂ）に示す。なお、この図２０（Ｂ）に示す調停アルゴリズムは、図２０（Ａ）に示すように、４ポート分の出力判定値（Sa，Sb，Sc，Sd）と、それぞれの判定フラグ（Valid_Sa，Valid_Sb，Valid_Sc，Valid_Sd）とを入力した場合のアルゴリズムを示している。
【０１０３】
次に、図２に示すデキュー制御部５９は、ポート間調停部５８の出力をバッファリングし、デキューバスの設定帯域に応じたシェーピング処理を行なうもので、前述した出力回線シェーピング回路５７−ｊの構成（図１４及び図１５参照）と同様に構成され、例えば図２１に示すように、デキューバスの設定帯域に応じた出力帯域のシェーピング処理を制御するシェーピング制御部（デキューバスシェーピング制御部）５９１と、ポート間調停部５８による調停結果を保持するパケット情報レジスタ５９２とをそなえている。
【０１０４】
さらに、シェーピング制御部５９１には、図２２に示すように、出力判定値演算回路５９１−１，出力判定回路５９１−２及びバースト制御部（デキューバスバースト制御部）５９１−３がそなえられている。
そして、シェーピング制御部５９１の出力判定値演算回路５９１は、出力判定回路５９１−２のからのデキューイネーブルアサートタイミング毎に、下記の式（８）による出力判定値演算を行なうものである。
【０１０５】
【数８】
【０１０６】
なお、この式（８）において、Ciはパケット出力完了予定時刻、Ci-1は前パケット出力完了予定時刻、SEL｛Ci-1，Timer｝はCi-1とTimer値のいずれかの選択、Liはデキューパケット長、ＤＲはデキューバス設定帯域をそれぞれ表す。
また、出力判定回路５９１−２は、上記の出力判定値演算回路５９１による演算結果Ciがタイマ６０のTimer値よりも小さい（Timer値＞Ci）となった場合に、次パケットの出力許可信号（デキューイネーブル信号）のアサート処理（キュー管理部４へのデキュー指示）を行なうものである。
【０１０７】
これらの出力判定値演算回路５９１−１及び出力判定回路５９１−２によって、デキューバスの設定帯域（ＤＲ）に応じたシェーピング処理が可能となる。図２３にシェーピング処理の概念を示す。シェーピング処理自体は、前述した出力回線シェーピング回路５７−ｊにおける処理と同様であり、この場合も、或る先頭パケット（パケット番号“０”）のデキューが発生した場合、まず、出力判定値演算回路５９１−１にて、以下の式（９）が演算される。
【０１０８】
【数９】
【０１０９】
ただし、この場合も、パケット番号“０”のパケットは前パケットが無効であるか、もしくは、後述するバースト制御部５９１−３によるバースト制御によりデキュー発生時のTimer値（D0） が選択されているものと仮定する。
そして、上記の式（９）による演算結果C0がタイマ６０のTimer値よりも大きい（Timer値＜C0）場合は、出力判定回路５９１−２によりデキューイネーブル信号はディゼーブルされデキュー指示は発生しない。これに対し、Timer値≧C0の場合、出力判定回路５９１−２は、その時に有効なデータがパケット情報レジスタ５９２に格納されていれば、デキューイネーブル信号をアサートし、キュー管理部４へデキューパケット番号を通知する。
【０１１０】
なお、このデキューパケット番号は、パイプライン処理上の同一評価値更新（同一パケットの重複出力防止）のために、前処理部５１，演算制御部５２，並列演算部５５，シェーピング部５７，シェーピング制御部５９１内の出力判定回路５９１−１及びバースト制御部５９１−３にそれぞれフィードバックされる。
このようにして、デキュー制御部５９においても、デキューバスの設定帯域に応じたシェーピング処理を行なうことにより、前出力完了時刻の早いパケットから優先的にデキューを発生させることができるので、デキューバス内における出力回線単位の帯域の取り戻し制御を効果的に行なうことができる。また、調停回路の簡素化も可能である。
【０１１１】
ところで、この場合も、出力判定値演算回路５９１−１による演算結果と実際のデキュー時刻との差（D‐C）が処理レイテンシ及びデキューバス上の輻輳などにより大きくなった場合、次パケット以降の出力がバースト的に行なわれ、デキューバス上の輻輳及びフレームメモリ２上での処理の破綻を招くおそれがある。
そこで、その保護のために、本デキュー制御部５９においても、出力回線シェーピング回路５７−ｊと同様に、図２２に示すバースト制御回路５９１−３によって、上記差の監視によるバースト制御を行なう。図２４にバースト制御の概念を示す。なお、この図２４において、Bは、バースト出力を許可する制限値を表す。
【０１１２】
即ち、図２４の（１）（図２４中では、（１），（２）を丸付き数字で示す）で示す場合は、デキュー発生時にTimer値‐C＜Bであるから、上記の式（９）におけるSEL｛Ci-1，Timer｝の項においてCi-1が選択され、次パケットのバースト出力が許可されることになる。これに対し図２４の（２）で示す場合は、デキュー発生時にTimer値‐C≧Bであるから、上記SEL｛Ci-1，Timer｝の項においてTimer値が選択され、次パケットのバースト出力は許可されないことになる。
【０１１３】
かかるバースト制御により、デキューバスにおける出力回線＃ｊ単位の帯域の取り戻しを許可しながら、その帯域制御に伴うデキューバスのオーバーフローを有効に回避することが可能となる。
次に、以下では、上述したキュー管理部４でのキュー管理の詳細について説明する。
【０１１４】
図２５に示すように、本実施形態のキュー管理部４は、パラメータメモリ４１、次ポインタテーブルメモリ４２，第３（3th）パラメータメモリ４３，パケットカウンタメモリ４４及びポインタテーブルメモリ４５をそなえている。
ここで、パラメータメモリ４１は、図１に示すフレームメモリ２と同じワード数の記憶容量を有しており、ここに、図１に示す変換テーブル３から入力される各キュー＃ｊ−ｋの先頭パケットについてのスケジュールパラメータ〔パケット長，タイムスタンプ（到着時刻），ビットマップ情報等〕が順次格納されるようになっている。なお、上記の「ビットマップ情報」は後述する変形例においてパケットのマルチキャストを行なう際に指定される情報であり、マルチキャストを行なわない場合には不要な情報である。
【０１１５】
また、次ポインタテーブルメモリ４２も、このパラメータメモリ４１と同じワード数の記憶容量を有しているが、ここには、パラメータメモリ４１と同じポインタ上に、次パケットのポインタが格納されるようになっている。したがって、この次ポインタテーブルメモリ４２を検索することにより、パラメータメモリ４１からパラメータを連続的に取り出すことが可能になる。
【０１１６】
さらに、第３パラメータメモリ４３は、キュー＃ｊ−ｋの先頭から３番目のパケットについてのスケジュールパラメータ〔第３（3th）パラメータ〕をキュー＃ｊ−ｋ別に保持するものである。つまり、この場合、第３パラメータは、パラメータメモリ４１と第３パラメータメモリ４３の双方に格納されるようになっている。したがって、キュー番号のアドレスを基に先頭から３番目のパケットにつてのパラメータを、次ポインタテーブルメモリ４２を検索することなく即時出力することが可能となる。
【０１１７】
また、パケットカウンタメモリ４４は、キュー＃ｊ−ｋに格納されているパケット数をキュー＃ｊ−ｋ別に保持するものであり、ポインタテーブルメモリ４５は、先頭（Top）ポインタメモリ４５１，第４（4th）ポインタメモリ４５２及び最終（End）ポインタメモリ４５３により、キュー＃ｊ−ｋの先頭パケット，４番目のパケット及び最終パケットのパラメータメモリ４１上の格納位置を指すポインタを、キュー＃ｊ−ｋ別に保持するもので、これにより、キュー番号のアドレスを基に、キュー＃ｊ−ｋの先頭パケット，４番目のパケット及び最終パケットを検索することが可能である。
【０１１８】
具体的に、例えば、或るキュー＃ｊ−ｋに７個のパケットａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇがパケットａを先頭パケットとして連続して格納されている場合を考えると、上記のパラメータメモリ４１、次ポインタテーブルメモリ４２，第３（3th）パラメータメモリ４３，パケットカウンタメモリ４４及びポインタテーブルメモリ４５の上記ポインタによるデータリンク構造は図２６に示すようになる。
【０１１９】
即ち、図２６に示すように、或るキュー＃ｊ−ｋにエンキューされたパケットａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇのパラメータがそれぞれパラメータメモリ４１に格納された場合、次ポインタテーブルメモリ４２においては、パラメータメモリ４１と同じポインタ上にそれぞれ次パケットｂ，ｃ，ｄ，ｅ，ｆ，ｇのポインタが格納される。また、先頭から３番目のパケットｃについてのパラメータは、パラメータメモリ４１とは別に、第３パラメータメモリ４３にも格納される。
【０１２０】
そして、ポインタテーブルメモリ４５においては、各ポインタメモリ４５１，４５２，４５３の該当キュー番号が示すアドレスに、先頭パケットａについてのポインタ，４番目のパケットｄについてのポインタ，最終パケットｇについてのポインタがそれぞれ格納される。
以下、上述したリンク構造によりキュー管理を行なうキュー管理部４のエンキュー及びデキュー時の動作についてそれぞれ詳述する。
【０１２１】
（１）エンキュー時の動作
まず、キュー管理部４は、図２７に示すように、図１に示す変換テーブル３からのエンキュー指示の有無を監視しており（ステップＳ１１のＮＯルート）、エンキュー指示を受けると（ステップＳ１１でＹＥＳの場合）、エンキュー指示されたキュー番号のパケット数をパケットカウンタメモリ４４から読み出して現在のパケット数を識別し（ステップＳ１２）、そのパケット数に応じて、スケジューラ５へのパラメータ出力と、キュー管理部４内部のポインタ制御（ポインタリンク構造の更新）とを次のようにして実行する。
【０１２２】
即ち、識別したパケット数が０個で該当キュー＃ｊ−ｋの状態が空の場合（ステップＳ１３でＹＥＳの場合）、キュー管理部４は、図２８に示す処理（１）（図２８中では、（１）〜（５）を丸付き数字で示す）を実行して、入力パラメータをそのままスケジューラ５へ出力するとともに、ポインタリンク構造を更新し（ステップＳ１８）、パケットカウンタメモリ４４の該当キュー＃ｊ−ｋのパケット数をインクリメント（＋１）する（ステップＳ２４）。
【０１２３】
識別したパケット数が１個の場合（ステップＳ１３でＮＯ，ステップＳ１４でＹＥＳの場合）、キュー管理部４は、図２８に示す処理（２）を実行して、入力パラメータを先頭から２番目のパケットについてのパラメータとしてスケジューラ５へ送出するとともに、ポインタリンク構造を更新し（ステップＳ１９）、パケットカウンタメモリ４４の該当キュー＃ｊ−ｋのパケット数をインクリメント（＋１）する（ステップＳ２４）。
【０１２４】
識別したパケット数が２個の場合（ステップＳ１３及びＳ１４でＮＯ，ステップＳ１５でＹＥＳの場合）、キュー管理部４は、図２８に示す処理（３）を実行して、入力パラメータを先頭から３番目のパケットについてのパラメータとして第３パラメータメモリ４３に格納するとともに、ポインタリンク構造を更新し（ステップＳ２０）、パケットカウンタメモリ４４の該当キュー＃ｊ−ｋのパケット数をインクリメント（＋１）する（ステップＳ２４）。
【０１２５】
識別したパケット数が３個の場合（ステップＳ１３〜Ｓ１５でそれぞれＮＯ，ステップＳ１６でＹＥＳの場合）、キュー管理部４は、図２８に示す処理（４）を実行して、先頭から４番目のパケットについてのポインタが第４ポインタメモリ４５２に格納するとともに、ポインタリンク構造を更新し（ステップＳ２１）、パケットカウンタメモリ４４の該当キュー＃ｊ−ｋのパケット数をインクリメント（＋１）する（ステップＳ２４）。
【０１２６】
識別したパケット数が４個以上の場合（ステップＳ１３〜Ｓ１６でそれぞれＮＯ，ステップＳ１７でＹＥＳの場合）は、キュー管理部４は、図２８に示す処理（５）を実行して、最終ポインタの更新のみを行ない（ステップＳ２２）、パケットカウンタメモリ４４の該当キュー＃ｊ−ｋのパケット数をインクリメント（＋１）する（ステップＳ２４）。
【０１２７】
ただし、本実施形態においてパケットのカウンタ値の最大値は５としており、識別したパケット数が既に５以上である場合は、図２８に示す処理（５）の後、カウンタ値のインクリメントは行なわれない（パケットカウンタメモリ４４の該当カウンタ値には５が固定的に設定される）（ステップＳ２３）。
（２）デキュー時の動作
これに対し、デキュー時には、キュー管理部４は、図２９に示すフローチャート（ステップＳ３１〜Ｓ４５）に従って動作する。即ち、キュー管理部４は、スケジューラ５からのデキュー指示の受信を監視しており（ステップＳ３１のＮＯルート）、デキュー指示を受けると（ステップＳ３１でＹＥＳの場合）、キュー管理部４は、該当キュー＃ｊ−ｋのパケット数をパケットカウンタメモリ４４から読み出して、現在の該当キュー＃ｊ−ｋのパケット数を識別し（ステップＳ３２）、その識別結果に応じて、スケジューラ５へのパラメータ出力と、キュー管理部４内部のポインタ制御（ポインタリンク構造の更新）とを次のようにして実行する。
【０１２８】
まず、識別したパケット数が５個以上の場合（ステップＳ３３でＹＥＳの場合）、キュー管理部４は、図３０に示す処理（１）（図３０中では、（１）〜（５）を丸付き数字で示す）を実行して、該当キュー＃ｊ−ｋの先頭ポインタをデキューポインタとしてメモリ制御部６へ出力するとともに、３番目のパケットについてのパラメータをスケジューラ５に送出し、ポインタリンク構造を更新する（ステップＳ３８）。
【０１２９】
そして、キュー管理部４は、この更新により、第４ポインタが最終ポインタと等しくなったか否かを確認し（ステップＳ４４）、等しければパケットカウンタメモリ４４の該当カウンタ値を固定値（４）に設定し（ステップＳ４４のＹＥＳルートからステップＳ４５）、等しくなければ次のデキュー指示の監視動作に入る（ステップＳ４４のＮＯルート）。
【０１３０】
さて次に、識別したパケット数が４個の場合（ステップＳ３３でＮＯ，ステップＳ３４でＹＥＳの場合）、キュー管理部４は、図３０に示す処理（２）を実行して、該当キュー＃ｊ−ｋの先頭ポインタをデキューポインタとしてメモリ制御部６へ出力するとともに第３パラメータメモリ４３上の３番目のパケットについてのパラメータをスケジューラ５に送出し、ポインタリンク構造を更新したのち（ステップＳ３９）、パケットカウンタ値をデクリメント（−１）する（ステップＳ４３）。
【０１３１】
同様に、識別したパケット数が３個の場合（ステップＳ３３及びＳ３４でそれぞれＮＯ，ステップＳ３５でＹＥＳの場合）、キュー管理部４は、図３０に示す処理（３）を実行して、該当キュー＃ｊ−ｋの先頭ポインタをデキューポインタとしてメモリ制御部６へ出力するとともに第３パラメータメモリ４３上の３番目のパケットについてのパラメータをスケジューラ５に送出し、ポインタリンク構造を更新しのたち（ステップＳ４０）、パケットカウンタ値をデクリメント（−１）する（ステップＳ４３）。
【０１３２】
これに対して、識別したパケット数が２個の場合（ステップＳ３３〜Ｓ３５でそれぞれＮＯ，ステップＳ３６でＹＥＳの場合）、キュー管理部４は、図３０に示す処理（４）を実行して、該当キュー＃ｊ−ｋの先頭ポインタをデキューポインタとしてメモリ制御部６へ出力するとともに先頭ポインタの更新を行ない（スケジューラ５へパラメータは送出しない）（ステップＳ４１）、パケットカウンタ値をデクリメント（−１）する（ステップＳ４３）。
【０１３３】
識別したパケット数が１個の場合（ステップＳ３３〜Ｓ３６でそれぞれＮＯ，ステップＳ３７でＹＥＳの場合）、キュー管理部４は、図３０に示す処理（５）を実行することにより、メモリ制御部６への先頭ポインタ（デキューポインタ）の出力のみを行ない（ステップＳ４２）、パケットカウンタ値をデクリメント（−１）する（ステップＳ４３）。
【０１３４】
つまり、キュー管理部４は、キュー＃ｊ−ｋのパケット数が３個以上である場合には、第３パラメータメモリ４３上のパラメータ（３番目のパケットについてのパラメータ）をスケジューラ５へ出力し、ポインタリンク構造の更新を行ない、パケット数が２個以下である場合には、先頭ポインタのメモリ制御部６への出力を行ない、スケジューラ５へのパラメータ出力は行なわないのである。
【０１３５】
なお、上記のエンキュー及びデキュー処理は、図３１に示すように、互いに相反する位相で動作することにより、お互いが競合しないよう制御されている。
以上のようなキュー管理（ポインタリンク構造の更新）により、同一キュー＃ｊ−ｋにおける連続する２個分のパケットについてのパラメータがスケジューラ５へ送出されて、先頭パケットメモリ５３に２個分のパケットについてのパラメータ（ただし、本実施形態では前処理部５１による前処理後のパラメータ）が保持されることになる。
【０１３６】
ここで、図３２に示すように、スケジューラ５の入力から先頭パケットメモリ５３への格納までのレイテンシをＡサイクル、スケジューラ５出力のデキュー指示による先頭パケットメモリ５３のデータ更新から更新データのスケジューラ５出力までの処理レイテンシをＢサイクル、スケジューラ５の出力のデキュー指示から次パケット出力までのキュー管理部４の処理レイテンシをＣサイクルとする。
【０１３７】
仮に、スケジューラ５が先頭パケットについてのパラメータのみを処理するのであれば、同一キュー＃ｊ−ｋ上の最短デキュー間隔は図３２に示すループ（１）（図３２中では、（１），（２）を丸付き数字で示す）の処理に依存し、(Ａ＋Ｂ＋Ｃ)サイクルとなる。しかし、上述したように先頭パケットメモリ５３にキュー＃ｊ−ｋの先頭２個分のパラメータを格納することにより、同一キュー＃ｊ−ｋ上の最短デキュー間隔は、図３２に示すループ（２）の処理レイテンシ（Ｂサイクル）にできる。ただし、最短のデキュー間隔をＢサイクルで行なうためには、Ｂ≧（Ａ＋Ｃ）である必要がある。Ｂ＜（Ａ＋Ｃ）であれば、デキューの更新間隔は（Ａ＋Ｃ）サイクルに依存するようになる。
【０１３８】
したがって、例えば図３３に示すように、或るキュー＃ｊ−ｋに５つのパケット“１”〜“５”の入力があり、それらがいずれも最短デキュー間隔で出力可能なパケット長の短いものであり、且つ、Ｂ≧（Ａ＋Ｃ）を満足する場合、デキュー発生によりキュー管理部４及び先頭パケットメモリ５３への次パケットの出力要求が同時に発生することになり、パケット“１”〜“５”は最短保証間隔であるＢサイクルで連続してパケットをデキューすることが可能となる。
【０１３９】
その結果、連続パケット出力のボトルネックとなっていた処理レイテンシが大幅に削減され、5Gbpsや10Gbps等の高速帯域をもつ回線＃ｊやキュー＃ｊ−ｋに対する帯域制御の精度を高めて、設定帯域の保証を行なうことができる。
なお、上記のデキュー発生時には、キュー管理部４へのデキューイネーブル信号のアサートとともに、同一パケットの重複出力をマスクするために、スケジューラ５内部におけるパイプライン処理上の同一パケットについてのパラメータ対するマスク処理が行なわれる。
【０１４０】
即ち、図２中に示すように、デキュー発生時には、デキュー情報（デキュー識別信号：FB1，FB2，FB3，FB4）が、それぞれ、演算制御部５２，並列演算部５５の各演算器５５−ｋの出力判定回路５５２，シェーピング部５７における各出力回線シェーピング回路５７−ｊの出力判定回路５７１−２，デキュー制御部５９の出力判定回路５９１−２へそれぞれフィードバックされる。
【０１４１】
そして、演算制御部５２では、上記デキュー情報（FB1）の受信により、デキューパケットの出力回線＃ｊを次サイクルの演算出力回線として指定し、上記デキュー情報（FB2）により識別される演算器５５−ｋの出力判定回路５５２では、出力判定フラグをディセーブルにして、同一出力回線＃ｊの同一キュー＃ｊ−ｋについての演算結果出力をマスクする。
【０１４２】
また、上記デキュー情報（FB3）により識別される出力回線シェーピング回路５７−ｊの出力判定回路５７１−２においても、出力判定フラグをディセーブルにして、判定値出力をマスクし、デキュー制御部５９の出力判定回路５９１−２においても、上記デキュー情報（FB4）の受信により、判定値出力をマスクして次サイクルの全出力をマスクする。
【０１４３】
以上のマスク処理により、同一パケットの重複出力防止と、それに伴うキュー＃ｊ−ｋの帯域制御精度の低下を防止することができる。
ここで、例えば図３４に示すように、或る回線Ａのキュー（演算器）番号ｎのキューについてのデキューイベントがサイクルｔで発生した場合を考える。この場合、デキュー情報（FB4）により次サイクルの全出力がマスクされ、デキューバスの出力は停止する。また、デキュー情報（FB3）により回線Ａのシェーピング部５７の出力に対してｔ＋２サイクルまでマスク処理が働く。この処理によりｔ＋２サイクル目からは、回線Ａ以外の回線のデキュー処理が行なえることになる。
【０１４４】
さらに、デキュー情報（FB2）により、演算器５５−ｋの出力に対してｔ＋３サイクルまでマスク処理が働く。ただし、このポイントでは、回線Ａ以外の回線についてのデータをマスクしないように、当該ポイントのデータの回線識別処理を行ない、回線Ａについてのデータのみをマスクする。この処理により、ｔ＋３サイクル目からは、演算器番号ｎ以外の回線Ａについてのデキュー出力が行なえることになる。また、デキュー情報（FB1）により、先頭パケットメモリ５３から次パケットデータの更新を行なうため演算回線がＡに指定される。
【０１４５】
以上のようにして、全パイプライン処理上のデキューパケットによる更新処理が行われる。このように複数ポイントでデータのマスク処理を行なうことにより、他回線についてのパケットは最低２サイクル、同一回線内のパケットについては最低４サイクル間隔でのデキュー処理が可能になる。また、同一キューについても、本実施形態では、先頭パケットメモリ５３に先頭パケットについてのパラメータを常に２個をもたせているので、８サイクル間隔でのデキュー処理が可能になる。
【０１４６】
以上のように、上述した実施形態におけるパケット出力制御装置１によれば、ＷＦＱの評価値演算対象の回線＃ｊを時分割に指定し、指定された回線＃ｊに属する各キュー＃ｊ−ｋの先頭パケットについての評価値並列演算を各回線＃ｊに共通の演算器５５−ｋで実行するように構成したので、スケジューラ５の回路規模をキュー本数に対して大幅に削減することができる。
【０１４７】
したがって、従来困難であった多数キューについてのＷＦＱスケジューリング演算をハードウェア化することができて、その演算能力を大幅に向上することができ、精度の高いＷＦＱスケジューリングが実現可能である。
特に、上述した実施形態では、前処理部５１やγ演算部５４等の演算回路の共通化を図っているので、多数のキューをもつスケジューラについても、ＬＳＩやＦＰＧＡでの実装が可能になる。また、このような演算器共有構成を活かして、ＷＦＱをベースにした固定帯域キューや優先制御キューによるＱｏＳ制御を容易に実現することもできる。
【０１４８】
さらに、シェーピング部５７での出力回線＃ｊ毎のシェーピング処理により、キュー単位で発生する出力帯域の取り戻しの総和による出力回線＃ｊの輻輳を回避することができ、また、デキュー制御部５９でのデキューバスについてのシェーピング処理により、キュー＃ｊ−ｋ単位又は出力回線＃ｊ単位に発生する出力帯域の取り戻しの総和によるデキューバスの輻輳を回避することができる。
【０１４９】
また、演算回線の指定やパケットデキュー時の複数ポイントでのフィードバック処理（マスク処理）により、各キュー＃ｊ−ｋ及び各回線＃ｊにおける高いスループットも実現できる。
（Ａ２）第１変形例の説明
次に、以下では、パケットスケジューラ５の第１変形例について説明する。
【０１５０】
図３７は上述したパケットスケジューラ５の第１変形例を示すブロック図で、この図３７に示すパケットスケジューラ５は、図４に示す構成に比して、１タイムスロット当たりの演算対象であるｎ本のキュー＃ｊ−１〜＃ｊ−ｎに帯域制御の優先度を与えてキュー＃ｊ−１〜＃ｊ−ｎ間で帯域の優先制御を行なう場合に、それらのキュー（以下、優先制御キューという）＃ｊ−１〜＃ｊ−ｎに対応する各演算器５５−ｋについて、優先制御回路５５ａ−１〜５５ａ−ｎが設けられている点が異なる。なお、以下において、既述の符号と同一符号を付したものは、特に断らない限り、それぞれ既述のものと同一もしくは同様のものを示す。
【０１５１】
そして、これらの優先制御回路（優先制御手段）５５ａ−ｋは、例えば図３９に示すように、それぞれ、先頭パケットメモリ５３（５３−１〜５３−ｎ）のパケット有無状態を判定するパケット有無判定回路５５１ａをそなえており、その出力（自キュー＃ｊ−ｋのパケット有無状態）が優先度の高いものから順に、論理和（ＯＲ）回路５５１ｂを介して、優先度の低い優先制御回路にカスケードに接続されている。
【０１５２】
また、最も優先度の高い優先制御回路５５ａ−１を除く優先制御回路５５ａ−２〜５５ａ−ｎには、それぞれ、上位の優先制御回路におけるパケット有無判定回路５５１ａの反転出力と、自優先制御回路５５ａ−２〜５５ａ−ｎにおけるパケット有無判定回路５５１ａの出力との論理積（ＡＮＤ）をとる１入力反転型の論理積（ＡＮＤ）回路５５１ｃが設けられている。なお、各優先制御回路５５ａ−ｋの出力はデータ有効フラグとして対応する演算器５５−ｋの出力判定回路５５２に接続されている。
【０１５３】
つまり、本変形例のスケジューラ５は、優先制御回路５５ａ−１〜５５ａ−ｋによって、出力回線＃ｊ別に上位キューの状態と自キューのパケット有無状態を監視し、優先度の高いキューにパケットが存在していることがパケット有無判定回路５５１ａで検出されている場合には、それよりも優先度の低いキューにパケットが存在していたとしても、対応する演算器５５−ｋにデータ有効フラグを出力しない（ディゼーブルする）ことにより、そのキューについての演算器５５−ｋの演算結果（評価値）をマスクするのである。
【０１５４】
これにより、例えば図３８（Ａ）に示すように、パケットがａ→ｂ→ｃ→ｄ→ｅ→・・・・の順にエンキューされ、それらを２段階の優先度をもって出力制御を行なう場合、図３８（Ｂ）に示すように、各入力パケットを高優先制御キューと低優先制御キューとにそれぞれ振り分け〔この図３８（Ｂ）では、パケットａ，ｄ，ｅが高優先側、残りのパケットｃ，ｂが低優先側に振り分けられている〕、高優先側から低優先側にパケット有無状態を伝達し、高優先側のパケットの出力完了によって高優先側のパケットが無い状態の時にのみ、低優先側の出力が許可されることになる。その結果、上記の各入力パケットａ，ｂ，ｃ，ｄ，ｅは、図３８（Ａ）に示すように、パケットａ→ｄ→ｅ→ｂ→ｃの順に出力されることになる。
【０１５５】
したがって、例えば、画像や音声データ等のリアルタイム性の高いキューのデータを優先的に出力させるようにすることが可能となる。なお、この構成において、前評価値メモリ６１において複数優先制御キュー＃ｊ間で前評価値（パケット出力完了予定時刻）Fi-1 を共有することにより、複数優先制御キュー＃ｊを単一のキューとして帯域制御することができる。
【０１５６】
例えば図４０に示すように、２つのキューａ，ｂ間で帯域共有を行なう場合を考える。この場合、２つのキュー間には共通の設定帯域φが設定されており、優先度はキューａ＞キューｂと仮定する。これにより、下位のキューｂは、上位のキューａにパケットが存在する時には、上述したように出力がマスクされ、上位キューａのパケットの出力完了と上位キューａのパケット無しとの条件により出力が許可される。したがって、下位のキューｂにエンキューされたパケットは、上位のキューａについての空き帯域を使って出力されるようになる。
【０１５７】
なお、上述した優先制御キューは、勿論、全てのキューではなく一部のキューで構成してもよい。
（Ａ３）第２変形例の説明
上述したように、出力回線＃ｊ間で演算器５５−ｋを共用する構造により、複数回線＃ｊに対して同一処理経路をもつため、スケジューラ５は、複数出力回線＃ｊへの同一パケットのコピー処理（マルチキャスト配信）を容易に行なうことができる。
【０１５８】
図４１はこのようなマルチキャスト配信を実現するパケットスケジューラ５の構成（第２変形例）を示すブロック図で、この図４１に示すスケジューラ５は、図４に示す構成に比して、一部あるいは全ての演算器５５−ｋについて、ビットマップ制御部６２とマルチキャスト先頭パケットメモリ６３とがそなえられている点が異なる。なお、以下において、既述の符号と同一符号を付したものは、特に断らない限り、既述のものと同一もしくは同様のものを示す。
【０１５９】
ここで、ビットマップ制御回路６２は、演算制御部５２からの演算タイムスロット指定に応じて、マルチキャスト先頭パケットメモリ６３に格納されているマルチキャストパケットについてのスケジュールパラメータ出力の有効／無効を制御するもので、例えば図４１及び図４２に示すように、ビットマップ（Bitmap）レジスタ６２１，ビットマップ制御回路６２２，データ有効判定回路６２３及び最終パケット判定回路６２４をそなえて構成されている。
【０１６０】
ビットマップレジスタ（配信先情報保持手段）６２１は、どの出力回線＃ｊについてマルチキャスト配信を行なうかを指定する配信先回線ビットマップ情報〔例えば図４４（Ａ）に示すように、マルチキャスト配信を行なう場合は“１”、そうでない場合は“０”が設定される〕を保持するものである。なお、上記の配信先回線ビットマップ情報は、例えば図１に示す変換テーブル３からのスケジュールパラメータとともに受信される。
【０１６１】
ビットマップ制御回路（配信制御手段）６２２は、デキュー制御部５９からフィードバックされてくるデキュー情報に基づいて、上記ビットマップレジスタ６２１に格納された配信先回線ビットマップ情報（以下、単に「ビットマップ情報」という）の更新／クリアを制御するものであり、データ有効判定回路６２３は、演算制御部５２から演算ポート指定される毎に、マルチキャスト先頭パケットメモリ６３から読み出されるマルチキャスト配信用の先頭パケットについてのスケジュールパラメータが有効であることを示すフラグを演算器５５−ｋの出力判定回路５５２に出力するものである。
【０１６２】
最終パケット判定回路６２４は、現在のマルチキャスト配信対象の回線＃ｊが最終回線であるか否かを監視するもので、最終回線＃ｊであれば、ビットマップ制御回路６２２が、その旨（最終パケットフラグのイネーブル）を受けて、最終回線＃ｊに対するマルチキャストパケットのデキューによりビットマップレジスタ６２１の内容を次のマルチキャストパケットについてのビットマップ情報に更新するようになっている。
【０１６３】
以上の構成により、本第２変形例のスケジューラ５では、マルチキャストパケットについてのスケジュールパラメータがマルチキャスト先頭パケットメモリ６３に格納されるとともに、ビットマップ情報がビットマップ制御部６２のビットマップレジスタ６２１に格納される。
そして、前述した実施形態及び第１変形例のユニキャストキューにおいては、先頭パケットの有無判定により、演算器５５−ｋに入力されるパラメータの有効判定が行なわれるが、本第２変形例では、それに加えてビットマップ制御によるデータの有効判定がデータ有効判定回路６２３によって行なわれる。
【０１６４】
即ち、データ有効判定回路６２３は、ビットマップがアサート（“１”に設定）されている回線＃ｊに演算タイムスロットが演算制御部５２から指定された時に、演算器５５−ｋ出力の有効フラグをイネーブルにする〔例えば図４４（Ｂ）参照〕。
そして、図４３に示すように、マルチキャストパケットがデキューされた回線＃ｊ順に、ビットマップレジスタ６２１のビットマップ情報がビットマップ制御回路６２２によってクリアされてゆき、ビットマップ情報で指定された最後の回線＃ｊへのマルチキャストパケットがデキューされた時点で、最終パケット判定回路６２４からビットマップ制御回路６２２への最終パケットフラグ（イネーブル）が出力され、これにより、次のマルチキャストパケットについてのビットマップにビットマップレジスタ６２１の内容が更新される。
【０１６５】
このように、本第２変形例のスケジューラ５では、出力回線＃ｊ間で演算器５５−ｋが共用され、複数回線＃ｊに対して同一処理経路をもつことを利用して、複数出力回線の配信先情報をもったパケットをその配信先情報で指定された出力回線＃ｊの演算タイムスロット指定時に、そのパケットについての演算器５５−ｋによる演算結果を有効にするという簡単な制御で、指定された複数出力回線＃ｊへのパケット配信（マルチキャスト）を実現することができる。
【０１６６】
（Ｂ）付記
（付記１） 複数の出力回線毎に設けられた複数のキューと、
入力されたパケットを当該パケットのフローに応じて該キューのいずれかにエンキューするエンキュー手段と、
該エンキュー手段により上記の各キューにエンキューされた各パケットについてのデキュー指示をスケジュールするパケットスケジューラと、
該パケットスケジューラからのデキュー指示によって指示されたキューからパケットをデキューするデキュー手段とをそなえるとともに、
該パケットスケジューラが、
同一出力回線に属する各キューにエンキューされた先頭パケットに関する少なくとも到着時刻情報及びパケットサイズ情報を含む所定のパラメータに基づいて当該先頭パケットの送信完了予定時刻を示す評価値をそれぞれ所定の評価値演算式により並列演算する並列演算手段と、
該並列演算手段での演算対象とする出力回線を選択的に指定して同一出力回線に属する各キューの先頭パケットについてのパラメータを該並列演算手段に入力させる演算制御手段と、
該並列演算手段で求められた同一出力回線に属する各キューの先頭パケットの評価値に基づいて優先出力すべき先頭パケットの評価値を選出する同一出力回線内キュー間調停手段と、
該同一出力回線内キュー間調停手段で選出された評価値を該出力回線毎に保持し、該出力回線毎の評価値と該出力回線の設定帯域とに基づいて優先出力すべき先頭パケットを決定する出力回線間調停手段と、
該出力回線間調停手段で決定した先頭パケットについてのデキュー指示を該デキュー手段に与えるデキュー制御手段とをそなえたことを特徴とする、パケット出力制御装置。
【０１６７】
（付記２） 該演算制御手段が、上記の各出力回線の設定帯域に応じた割合で時分割に該並列演算手段での演算対象とする出力回線を指定する時分割演算回線指定部をそなえて構成されたことを特徴とする、付記１記載のパケット出力制御装置。
（付記３） 該パケットスケジューラが、
入力パケットの該パラメータに基づいて該評価値演算式中で繰り返し演算が不要な項を予め全キューで共通化された前処理として演算し、当該演算結果を該並列演算手段での演算に用いられる中間変数として該並列演算手段に入力する前処理部をそなえたことを特徴とする、付記１又は付記２に記載のパケット出力制御装置。
【０１６８】
（付記４） 該パケットスケジューラが、
同一出力回線に属する各キューうちパケットの存在しないキューに割り当てられている帯域を、パケットの存在する同一出力回線に属する他のキューに配分する帯域配分率を算出する帯域配分率算出手段をさらにそなえ、
該並列演算手段が、
該帯域配分率算出手段で算出された同じ帯域配分率に基づいて、上記の各評価値を再計算するように構成されたことを特徴とする、付記１〜３のいずれか１項に記載のパケット出力制御装置。
【０１６９】
（付記５） 該パケットスケジューラが、
該出力回線毎に、予め決められた固定帯域配分率を出力する固定帯域制御手段をさらにそなえ、
該並列演算手段が、
該固定帯域制御手段からの該固定帯域配分率に基づいて、上記の各評価値を計算するように構成されたことを特徴とする、付記１〜３のいずれか１項に記載のパケット出力制御装置。
【０１７０】
（付記６） 該パケットスケジューラが、
同一出力回線に属する各キューうちパケットの存在しないキューに割り当てられている帯域を、パケットの存在する同一出力回線に属する他のキューに配分する帯域配分率を算出する帯域配分率算出手段と、
該出力回線毎に、予め決められた固定帯域配分率を出力する固定帯域制御手段とをそなえるとともに、
該並列演算手段が、
同一出力回線に属するキュー毎に、該帯域配分率算出手段からの該帯域配分率と該固定帯域制御手段からの該固定帯域配分率のいずれか一方を選択する帯域配分率選択手段をそなえ、
該帯域配分率選択手段で選択された帯域配分率に基づいて該評価値を計算するように構成されたことを特徴とする、付記１〜３のいずれか１項に記載のパケット出力制御装置。
【０１７１】
（付記７） 該パケットスケジューラが、
同一出力回線に属する複数のキューに対して優先順位を与え、優先順位の高いキューにパケットが存在する場合に、当該キューよりも優先順位の低いキューについて該並列演算手段で求められる該評価値をマスク制御する優先制御手段をさらにそなえたことを特徴とする、付記１〜６のいずれか１項に記載のパケット出力制御装置。
【０１７２】
（付記８） 該パケットスケジューラが、
該優先順位の与えられた複数のキュー（以下、優先制御キューという）について該並列演算手段での前回の演算で求められた評価値を該優先制御キュー間で共通に保持する前評価値メモリをさらにそなえ、
該並列演算手段が、
該前評価値メモリに保持された評価値に基づいて新たな評価値の演算を行なうことにより、該複数の優先制御キューを単一のキューとみなして帯域制御を行なうように構成されたことを特徴とする、付記７記載のパケット出力制御装置。
【０１７３】
（付記９） 該パケットスケジューラが、
該複数の出力回線のうち同一パケットを配信すべき複数の出力回線を指定する配信先情報を保持する配信先情報保持手段と、
該配信先情報保持手段に保持された配信先情報によって指定されている出力回線が該演算制御手段によって指定される毎に、該並列演算手段で求められる同一キューについての該評価値を有効に制御する配信制御手段とをそなえたことを特徴とする、付記１記載のパケット出力制御装置。
【０１７４】
（付記１０） 該出力回線間調停手段が、
該出力回線毎に該同一出力回線内キュー間調停手段で選択された評価値を保持するレジスタと、
該評価値と該出力回線毎に予め設定された帯域情報とに基づいて、該出力回線の設定帯域を考慮した該評価値の出力制御を行なうことにより、該出力回線の帯域制御を行なう出力回線シェーピング制御部とをそなえたことを特徴とする、付記１記載のパケット出力制御装置。
【０１７５】
（付記１１） 該出力回線シェーピング制御部が、
該帯域制御において他の出力回線に属するキューの先頭パケットについての評価値との競合により出力が待たされた分の評価値出力を制御してパケットのバースト出力を制御する出力回線バースト制御部を有することを特徴とする、付記１０記載のパケット出力制御装置。
【０１７６】
（付記１２） 該パケットスケジューラが、
同一出力回線に属する各キューの先頭パケットを含む複数の連続するパケットについてのパラメータを保持する複数先頭パケットメモリをそなえ、
該演算制御手段が、
該先頭パケットについてのデキュー指示を契機に当該先頭パケットに続く次パケットについてのパラメータを該先頭パケットメモリから読み出して該並列演算手段に入力させるように構成されたことを特徴とする、付記１記載のパケット出力制御装置。
【０１７７】
（付記１３） 該時分割演算回線指定部が、
上記の各出力回線の設定帯域の比率に応じて所定周期内で時分割指定する同一出力回線の割合を設定するように構成されたことを特徴とする、付記２記載のパケット出力制御装置。
（付記１４） 該デキュー制御手段が、
該出力回線毎に該同一出力回線内キュー間調停手段で選択された評価値を保持するレジスタと、
該評価値とデキューバスに予め設定された帯域情報とに基づいて、該デキューバスの設定帯域に応じた該評価値の出力制御を行なうことにより、該出力回線の帯域制御を行なうデキューバスシェーピング制御部とをそなえたことを特徴とする、付記１又は付記１０に記載のパケット出力制御装置。
【０１７８】
（付記１５） 該デキューバスシェーピング制御部が、
該帯域制御において出力が待たされた分の評価値出力を制御してパケットのバースト出力を制御するデキューバスバースト制御部を有することを特徴とする、付記１４記載のパケット出力制御装置。
（付記１６） 該デキュー制御手段が、
該デキュー指示を契機に、上記の演算制御手段，並列演算手段及び出力回線間調停手段に対して、同一先頭パケットについての評価値をマスクするための制御信号を与えるマスク信号出力部をそなえたことを特徴とする、付記１記載のパケット出力制御装置。
【０１７９】
【発明の効果】
以上詳述したように、本発明のパケットスケジュール出力制御装置によれば、次のような効果ないし利点が得られる。
(1)評価値演算対象の出力回線を選択的に指定し、指定された出力回線に属する各キューの先頭パケットについての評価値を並列演算するので、パケットスケジューラの回路規模をキュー本数に対して大幅に削減することができる。したがって、従来困難であった多数キューについての評価値演算をハードウェア化することができて、その演算能力を大幅に向上することができ、精度の高いＷＦＱスケジューリングが実現可能である。
【０１８０】
(2)また、評価値演算式中の繰り返し演算が不要な項を前処理部により予め全キューで共通化された前処理として演算したり、キューのパケット有無の変化に伴って再計算される同じ帯域配分率に基づいて評価値の再計算を行なったりして、演算回路の共通化を図ることにより多数のキューをもつスケジューラについても、例えば、ＬＳＩやＦＰＧＡでの実装が可能になる。
【０１８１】
(3)さらに、このような並列演算構成を活かして、ＷＦＱをベースにした固定帯域キューや優先制御キューによるＱｏＳ制御，マルチキャスト配信等の制御を容易に実現することもできる。
(4)さらに、シェーピング部での出力回線毎のシェーピング処理（バースト制御）により、キュー単位で発生する出力帯域の取り戻しの総和による出力回線の輻輳を回避することができ、また、デキュー制御部でのデキューバスについてのシェーピング処理（バースト制御）により、キュー単位又は出力回線単位に発生する出力帯域の取り戻しの総和によるデキューバスの輻輳を回避することができる。
【０１８２】
(5)また、演算制御手段による演算回線の指定やパケットデキュー時の複数ポイントでのフィードバック処理（マスク処理）により、重複パケット出力を防止することができ、また、各キュー及び各出力回線の帯域制御精度の低下を防止して高いスループットも実現できる。
(6)演算制御手段が、各出力回線の設定帯域に応じた割合で時分割に上記並列演算対象とする出力回線を指定することにより、上述のごとく出力回線間で並列演算を共通化することによる演算精度の低下を防止することができる。
【０１８３】
(7)さらに、上記の評価値演算に際して、出力回線別に帯域再配分を行なうか否かを設定するようにすることもできるので、出力回線毎に固定帯域キューとＷＦＱによるキューとの構成比を任意に設定することができ、自由度の高いパケットスケジューラ５を提供することができる。
(8)また、同一出力回線に属する各キューの先頭パケットを含む複数の連続するパケットについてのパラメータを保持しておき、上記先頭パケットについてのデキュー指示を契機にその先頭パケットに続く次パケットについてのパラメータを先頭パケットメモリから読み出して並列演算手段に入力させることで、同一キューの連続パケットについてのパラメータ更新の処理レイテンシを短縮することができるので、高速出力回線に対する帯域制御の精度を向上して、設定帯域の保証を行なうことができる。
【０１８４】
(9)デキュー指示を契機に、同一先頭パケットについての評価値をマスクするので、同一パケットが重複出力されることを防止することができ、キューの帯域制御精度の低下を防止することができる
【図面の簡単な説明】
【図１】本発明の一実施形態としてのパケット出力制御装置の全体構成を示すブロック図である。
【図２】図１に示すパケットスケジューラの構成を示すブロック図である。
【図３】図１に示すパケットスケジューラの構成を示すブロック図である。
【図４】図２及び図３に示すスケジューリング評価値演算器の構成に着目したパケットスケジューラの要部構成を示すブロック図である。
【図５】図２及び図３に示す演算制御部で用いられる演算回線テーブルの一例を示す図である。
【図６】図２及び図３に示す演算制御部での演算回線決定動作を説明するための状態遷移図である。
【図７】図２及び図３に示すパケットスケジューラによる演算回線指定と回線スループットを説明するためのタイムチャートである。
【図８】図２及び図３に示す前処理部及び先頭パケットメモリの構成を示すブロック図である。
【図９】図２及び図３に示すγ演算部の構成を示すブロック図である。
【図１０】図９に示すφ加減算器の構成を示すブロック図である。
【図１１】図１０に示すφ累積器の構成を示すブロック図である。
【図１２】図９に示すγ演算部でのφ加減算処理を説明するためのフローチャートである。
【図１３】図２及び図３に示す選択部によるキュー間出力調停動作を説明するための図である。
【図１４】図２及び図３に示すシェーピング部における出力回線シェーピング回路の構成を示すブロック図である。
【図１５】図１４に示すシェーピング制御の構成を示すブロック図である。
【図１６】図１５に示す出力判定値演算回路の構成を示すブロック図である。
【図１７】図１４に示す出力回線シェーピング回路による回線シェーピング処理概念を説明するための図である。
【図１８】図１４に示す出力回線シェーピング回路による回線シェーピング処理及びバースト制御概念を説明するための図である。
【図１９】図２及び図３に示すポート間調停部による出力回線間調停動作を説明するための図である。
【図２０】（Ａ）及び（Ｂ）は図２及び図３に示すポート間調停部を実現するソフトウェアアルゴリズムの一例を示す図である。
【図２１】図２に示すデキュー制御部の構成を示すブロック図である。
【図２２】図２１に示すシェーピング制御部の構成を示すブロック図である。
【図２３】図２１及び図２２に示すデキュー制御部によるデキューバス・シェーピング処理概念を説明するための図である。
【図２４】図２１及び図２２に示すデキュー制御部によるデキューバス・バースト制御概念を説明するための図である。
【図２５】図１に示すキュー管理部のメモリ構成を示すブロック図である。
【図２６】図２５に示すキュー管理部のメモリ構成におけるポインタリンク構造例を示す図である。
【図２７】図１に示すキュー管理部のエンキュー処理時の動作を説明するためのフローチャートである。
【図２８】図２７に示す各処理の詳細を示す図である。
【図２９】図１に示すキュー管理部のデキュー処理時の動作を説明するためのフローチャートである。
【図３０】図２９に示す各処理の詳細を示す図である。
【図３１】図１に示すキュー管理部でのエンキュー／デキュー処理位相を説明するための図である。
【図３２】図１に示すキュー管理部及びパケットスケジューラ間での処理レイテンシを説明するための図である。
【図３３】図３２に示すキュー管理部及びパケットスケジューラによる処理レイテンシとデキュースループットを説明するための図である。
【図３４】図２及び図３に示すデキュー制御部によるデキュー情報のフィードバックによるマスク処理を説明するための図である。
【図３５】図４に示すスケジューリング評価値演算器におけるセレクタに対するＷＦＱ／固定帯域切り替え設定情報を保持するレジスタの構成を示すブロック図である。
【図３６】図２及び図３に示す演算制御部によるＷＦＱ／固定帯域切り替え制御を説明するためのタイムチャートである。
【図３７】図４に示すパケットスケジューラの第１変形例を示すブロック図である。
【図３８】（Ａ）及び（Ｂ）は優先制御キューによるパケット出力動作を説明するための図である。
【図３９】図３７に示す優先制御回路の構成を示すブロック図である。
【図４０】図３７及び図３９に示す優先制御回路による優先制御キューにおける評価値の共有を説明するための図である。
【図４１】図４に示すパケットスケジューラの第２変形例を示すブロック図である。
【図４２】図４１に示すビットマップ制御部の構成を示すブロック図である。
【図４３】 図４１及び図４２に示すビットマップ制御部によるマルチキャスト配信制御を説明するためのタイムチャートである。
【図４４】 （Ａ）及び（Ｂ）は図４１及び図４２に示すビットマップ制御部によるマルチキャスト配信制御を説明するための図である。
【図４５】ＱｏＳ制御の仕組みを説明するための図である。
【図４６】ＷＦＱによる帯域制御概念を説明するための図である。
【図４７】ＷＦＱによる帯域制御概念を説明するための図である。
【符号の説明】
１ パケット出力制御装置
２ フレームメモリ
３ 変換テーブル
４ キュー管理部
４１ パラメータメモリ
４２ 次ポインタメモリ
４３ 第３パラメータメモリ
４４ パケットカウンタメモリ
４５ ポインタテーブル
４５１ 先頭ポインタメモリ
４５２ 第４ポインタメモリ
４５３ 最終ポインタメモリ
５ パケットスケジューラ
６ メモリ制御部
７ タイムスタンプ部
５１ 前処理部
５２ 演算制御部（時分割演算回線指定部）
５２１ 演算出力回線テーブル
５３，５３−１〜５３−ｎ 先頭パケットメモリ
５４ γ演算部（帯域配分率算出手段）
５４１ γ演算制御部
５４２ φ設定テーブル
５４３ φ加減算器
５４３−１〜５４３〜Ｍ φ累積器
５４３１ 加減算器
５４３２ レジスタ
５４４，５４６ セレクタ
５４５ Ｒ設定テーブル
５４７ 除算器
５５ 並列演算部
５５−１〜５５−ｎ スケジューリング評価値演算器
５５１ α選択回路
５５２ 出力判定回路
５５３ セレクタ（帯域配分率選択手段）
５５４ 乗算器
５５５ 加算器
５５６ 設定レジスタ
５５ａ−１〜５５ａ−ｎ 優先制御回路
５５１ａ パケット有無判定回路
５５１ｂ 論理和（ＯＲ）回路
５５１ｃ １入力反転型の論積（ＡＮＤ）回路
５６ 選択部（同一出力回線内キュー間調停手段）
５７ シェーピング部
５７−１〜５７−Ｍ 出力回線シェーピング回路
５７１ シェーピング制御部（出力回線シェーピング制御部）
５７１−１ 出力判定値演算回路
５７１−２ 出力判定回路
５７１−３ バースト制御部（出力回線バースト制御部）
５７１１ セレクタ
５７１２ 除算器
５７１３ 加算器
５７１４ レジスタ（Ｒ）
５７２ パケット情報レジスタ
５７−１〜５７−Ｍ 出力回線シェーピング回路
５８ ポート間調停部（出力回線間調停手段）
５９ デキュー制御部
５９１ シェーピング制御部（デキューバスシェーピング制御部）
５９１−１ 出力判定値演算回路
５９１−２ 出力判定回路
５９１−３ バースト制御部（デキューバスバースト制御部）
５９２ パケット情報レジスタ
６０ タイマ
６１ 前評価値メモリ
６２ ビットマップ制御部
６２１ ビットマップレジスタ
６２２ ビットマップ制御回路
６２３ データ有効判定回路
６２４ 最終パケット判定回路
６３ マルチキャスト先頭パケットメモリ
【発明の属する技術分野】
本発明は、パケットを格納する複数のキューをそなえたパケット出力制御装置に関し、特に、各キューに格納された先頭パケットの中から最も早く転送を完了することのできるパケットを効率良く選出して出力するパケット出力制御装置に関する。
【０００２】
【従来の技術】
近年のADSL，CATV，FTTH等の急速な普及により、専用線をもたない一般家庭や企業まで高速なインターネット環境が提供されるようになり、従来の電子メールやファイル転送だけでなく、映画やニュース等の大容量の情報量をもったコンテンツの配信もインターネット上で広く行なわれるようになってきた。
【０００３】
今後も、更に様々なアプリケーションが、ＩＰ（Internet Protocol）ネットワーク上に統合され、サービスが提供されていくものと思われる。このようなＬＡＮやインターネットを背景に、ＩＰネットワークの中核を成すルータ装置（Ｌ３スイッチ）の市場規模は、今後さらに拡大していくと思われ、情報量の大容量化とともにその処理能力の向上も求められている。
【０００４】
また、電子メール，ＦＴＰ（File Transfer Protocol）によるファイル転送や動画・音声配信など、要求されるトラフィック特性（許容廃棄率や遅延等）の異なる種々のサービスをＩＰネットワークでストレスなく提供するためには、それぞれの品質を劣化させないように、ルータ機器等にてトラフィクフロー（ユーザが転送要求する複数の連続したパケット）に応じた優先制御や帯域制御を行なうＱｏＳ（Quality of Service）制御が必要である。
【０００５】
例えば、ＦＴＰデータやＷＷＷ（World Wide Web）データのようなトラフィックデータに対しては、各フローのデータを最大限のリソース（主に、帯域幅）を利用し、高速且つ公平に転送することが重要視され、ルータ装置には、これらのフロー（あるいはフローの集合）毎に予約された帯域幅を、各フローに割り当てて保証するとともに、出力回線（出力リンク）において余ったリソースを、これらの各フロー間で公平に再配分する制御を、高速出力リンクに応じて高速処理することが要求される。
【０００６】
これに対し、ＶｏＩＰ（Voice over IP）のような音声トラフィックデータに対しては、リンクの帯域幅を最大限且つ公平に利用するよりも、固定の転送レートを保証し、遅延ジッタを最小にすることが重要である。
ここで、ＱｏＳ制御の仕組みを図４５に示す。即ち、この図４５に示すように、既存のＱｏＳ制御では、下記に示す各処理（１）〜（４）（図４５中では、丸付き数字で示す）が実行される。
【０００７】
（１）入力したＩＰパケットのＩＰアドレスやＭＡＣ（Media Access Control）アドレス及びＴｏＳ（Type of Service）フィールドを参照して、入力パケットをアプリケーション毎のフローに分類（識別）する。
（２）識別したフロー番号に従って、入力パケットをキューに振り分ける（キューイング）。
【０００８】
（３）各キューに設定された優先度や帯域に従って、キュー先頭のパケットの長さやキューイング時刻などを基に各キューの先頭パケットをデキューする順序やタイミングを計算（スケジューリング）する。
（４）スケジューリング結果に従って、各キューの先頭パケットをキューから読み出す（デキュー）。
【０００９】
以上の処理により、キューに振り分けたフロー毎のＱｏＳ制御が可能となる。
さて、パケットスケジューリングに関しては様々なアルゴリズムがあるが、ＷＦＱ(Weighted Fair Queuing)やＷＲＲ(Weighted Round Robin)等が代表的であり、これらのうちＷＦＱは可変長パケットに対して公平な帯域分配を行なう手法としては最適と考えられている。以下、このＷＦＱのアルゴリズムについて説明する。
【００１０】
或る固定帯域が予約されたキューの帯域制御の概念を図４６に示す。ここで、キューの設定（予約）帯域をφ、スケジューリング対象となるキューの先頭パケットのパケット長をＬとすると、そのパケットの送出完了に必要な時間はＬ／φで求められる。帯域制御は、このＬ／φによりパケットの出力完了予定時刻（スケジューリング評価値）Fを求め、タイマが示す現時刻Trが出力完了予定時刻Ｆを超えた時に、次のパケットの出力を許可するというものである。なお、送信完了予定時刻Fは以下の式（１）によって求められる。
【００１１】
【数１】
ここで、この式（１）において、Tiはフロー番号ｋのｉ番目のパケット到着時刻、Liはフロー番号ｋのｉ番目のパケット長を示し、max[Fi-1, Ti]は、前パケット送信完了予定時刻Ｆi-1とパケット到着時刻Tiとを比較し、大きい方を選択する処理を示す。
したがって、式（１）は、パケット到着時刻Ti＜前パケット送信完了予定時刻Fi-1の場合は、図４６中に丸付き数字１で示すように、パケット送信完了予定時刻FiがFi-1を基準に計算され、逆に、パケット到着時刻Ti ≧ 前パケット送信完了予定時刻Fi-1の場合は、図４６中に丸付き数字２で示すように、パケット送信完了予定時刻Fiがパケット到着時刻Tiを基準に計算されることを意味する。
【００１３】
そして、ＷＦＱでは、パケット到着時に、キューの先頭に存在する全てのフロー番号kのｉ番目のパケットに対して、以下の式（２）を計算し、スケジューリング評価値Fを算出する。
【００１４】
【数２】
ここで、この式（２）において、φkはフローkの予約帯域、φbはアクティブ状態のＷＦＱのφkの合計（Σφk）、ＲはＷＦＱの合計帯域をそれぞれ示す。なお、説明を簡単にするために、上記の式（２）を以下の式（３）に置き換える。
【００１６】
【数３】
そして、この式（３）におけるアクティブ状態キューの先頭パケットのα値を、常時、現タイマ値Trと比較し、Tr≧αとなるパケットの集合から最も小さなスケジューリング評価値（以下、単に「評価値」ともいう）Fをもつパケットを選択し出力する。したがって、直前パケットの転送に長時間を要したキューや、転送に長時間を要する先頭パケットのキューに対しては、パケット出力（デキュー）の優先順位が下がることになる。
【００１８】
このようにして、ＷＦＱでは、パケット送信完了予定時刻Fiによるパケット出力順序の重み付け制御を行なって、キュー間の公平なパケット出力を実現するとともに、非アクティブキューに割り当てられている余剰帯域をアクティブキューに公平に割り当てて、リソースの有効利用を図り、アクティブキューのパケットをより高速に転送してサービスの向上を図っている。
【００１９】
なお、上記のアクティブ状態とは、キューに少なくとも１つパケットが存在している状態を意味し、このように少なくとも１つパケットが存在するキューをアクティブキューと呼ぶ。そして、上記の式（３）におけるγ値はかかるアクティブ状態の変化によって、逐次、変化することになる。このため、評価値Fは、アクティブ状態が変化する度に、全てのキューについて評価値Fの再計算を行なう必要がある。
【００２０】
例えば、図４７に示すように、５本のキューに対してそれぞれ１００Ｍｂｐｓの帯域が予約され、それら５本中３本のキューにパケットが存在している場合（３本のキューのみがアクティブ状態の場合）、残り２本の空きキューに予約されている余剰帯域２００Ｍｂｐｓ分は３本のアクティブキューへ公平に分配され、それぞれ約１６７Ｍｂｐｓとなり、その帯域に従った再スケジューリングが行なわれて出力回線へパケットが出力（デキュー）されることになる。
【００２１】
【発明が解決しようとする課題】
従来、上述したＷＦＱにおけるスケジューリング評価値の演算は、プロセッサを用いたソフトウェアによる処理が主流であった。しかし、ソフトウェアによる処理では、シーケンシャルな処理しか行なえず、特に、リアルタイムに変化するγ値を反映させる再計算に非常に時間がかかり、同一出力回線や同一キューの連続パケットを処理する能力（スループット）が出ないという課題があった。
【００２２】
一方、スループット向上のために、ハードウェアによりスケジューリング評価値の演算を実現しようとすると、前記の式（２）に除算と乗算の演算が含まれるために、乗算器，除算器を用いる必要があり、回路規模が増大し、ＬＳＩやＦＰＧＡ（Field Programmable Gate Array）への実装が困難であった。そのため、ハードウェアによりＷＦＱを実現する場合でも、実装可能なキューの数が出力回線当たり数本程度に制限されてきた。
【００２３】
また、出力回線が複数存在する場合には、それらの出力回線毎に専用のスケジューラを設け、出力回線毎に使用するスケジューラを選択して動作させるという構成を採ることが考えられるが、これをハードウェアにより実現しようとすると、さらに回路規模が増大し、ＬＳＩやＦＰＧＡへの実装は略不可能となってしまう。そこで、従来は、上記γ値による再計算を行なわないバーチャルクロック等のＷＦＱの派生アルゴリズムを用いることで、前記γ値の再計算の演算量を削減する手法も考えられている。
【００２４】
しかしながら、かかるバーチャルクロック等の派生アルゴリズムを導入すると、例えば特開2000-101637号公報にも記載されているとおり、パケット送信完了予定時刻Fの時間軸が実時間とは異なる独自のものとなってしまうので、パケットの出力順序制御を行なうスケジューラを、サービス（ＱｏＳ）に応じて複数設けた場合、各スケジューラ間での最優先出力パケットの選択処理等、スケジューラ間の連携が困難になる。
【００２５】
上記の特開2000-101637号公報により提案されている技術は、かかるバーチャルクロック等の派生アルゴリズムを導入することなく、前記γの再計算の演算量を削減できるようにしたものであるが、本公知技術を用いたとしても、複数の出力回線をもつ装置におけるＷＦＱ（スケジューラ）を、装置規模を増大させることなく、ＬＳＩやＦＰＧＡへの実装が可能なものとして実現するのは困難であった。
【００２６】
即ち、上記公知技術では、前記β値に大きな差の無いパケット同士の送信完了予定時刻Fは前記γ値が変動したとしてもそれらの大小関係が入れ替わる確率が低く、仮に入れ替わってもその時刻差は微小であることに鑑み、前記β値に大きな差の無い評価値Fの集合をクラスタとしてクラスタリングし、γ値の変動についてはクラスタの先頭ポインタが示す評価値Fに対してのみ反映させることで、γ値の変動による評価値Fの再計算をクラスタ数（Ｍ）分だけに抑えて演算量を削減することが行なわれる。
【００２７】
しかし、かかるクラスタリングによるＷＦＱは、β値の格差が比較的小さく、クラスタ数Ｍ<<キュー個数Ｎであるときに演算量を削減するには有効であるが、サービス別に数十kbps〜数百kbps又は数Gbpsとφの値が変化する場合には、β値の変動幅の自由度が制限される、もしくは、そのβ値の変動幅に対応させてクラスタ数を変更する必要がある。
【００２８】
しかも、クラスタ内のγ値の変動は無視されるため、サービス品質に対してその誤差を許容できるクラスタ数の考察も必要になる。また、クラスタ内のポインタ管理のレイテンシがパケット長最小の連続パケット入力時におけるスケジューリングのボトルネックとなる。さらに、上記クラスタリングにより演算量を或る程度削減できたとしても、出力回線数が増えると、この場合も、スケジューラ数を増やす必要があるので、結局、ＬＳＩやＦＰＧＡへの実装は困難である。
【００２９】
本発明は、以上のような課題に鑑み創案されたもので、多様化，大容量化するインターネットサービス等に対して、多くのサービス毎にクラス分けして制御可能であるキューの本数と高精度の帯域制御、及びスループットの飛躍的な向上が可能であり、且つ、ハードウェアによる実装が可能である、小型で処理能力に優れたパケット出力制御装置を提供することを目的とする。
【００３０】
【課題を解決するための手段】
上記の目的を達成するために、本発明のパケット出力制御装置は、複数の出力回線毎に設けられた複数のキューと、入力されたパケットを当該パケットのフローに応じて該キューのいずれかにエンキューするエンキュー手段と、エンキュー手段により上記の各キューにエンキューされた各パケットについてのデキュー指示をスケジュールするパケットスケジューラと、パケットスケジューラからのデキュー指示によって指示されたキューからパケットをデキューするデキュー手段とをそなえるとともに、上記パケットスケジューラが、下記の各手段をそなえたことを特徴としている。
【００３１】
(1)同一出力回線に属する各キューにエンキューされた先頭パケットに関する少なくとも到着時刻情報及びパケットサイズ情報を含む所定のパラメータに基づいて当該先頭パケットの送信完了予定時刻を示す評価値をそれぞれ所定の評価値演算式により並列演算する並列演算手段
(2)並列演算手段での演算対象とする出力回線を選択的（時分割）に指定して同一出力回線に属する各キューの先頭パケットについてのパラメータを該並列演算手段に入力させる演算制御手段
(3)並列演算手段で求められた同一出力回線に属する各キューの先頭パケットの評価値に基づいて優先出力すべき先頭パケットの評価値を選出する同一出力回線内キュー間調停手段
(4)同一出力回線内キュー間調停手段で選出された評価値を該出力回線毎に保持し、該出力回線毎の評価値と該出力回線の設定帯域とに基づいて優先出力すべき先頭パケットを決定する出力回線間調停手段
(5)出力回線間調停手段で決定した先頭パケットについてのデキュー指示を該デキュー手段に与えるデキュー制御手段
ここで、上記の演算制御手段は、上記の各出力回線の設定帯域に応じた割合で時分割に該並列演算手段での演算対象とする出力回線を指定する時分割演算回線指定部をそなえて構成されていてもよい。
【００３２】
また、上記のパケットスケジューラは、入力パケットのパラメータに基づいて上記評価値演算式中で繰り返し演算が不要な項を予め全キューで共通化された前処理として演算し、当該演算結果を該並列演算手段での演算に用いられる中間変数として該並列演算手段に入力する前処理部をそなえていてもよい。
【００３３】
さらに、上記のパケットスケジューラは、同一出力回線に属する各キューうちパケットの存在しないキューに割り当てられている帯域を、パケットの存在する同一出力回線に属する他のキューに配分する帯域配分率を算出する帯域配分率算出手段をさらにそなえ、上記の並列演算手段が、上記の帯域配分率算出手段で算出された同じ帯域配分率に基づいて、上記の各評価値を再計算するように構成されていてもよい。
【００３４】
また、上記のパケットスケジューラは、上記複数の出力回線のうち同一パケットを配信すべき複数の出力回線を指定する配信先情報を保持する配信先情報保持手段と、この配信先情報保持手段に保持された配信先情報によって指定されている出力回線が上記演算制御手段によって指定される毎に、上記の並列演算手段で求められる同一キューについての評価値が、上記出力回線間調停手段での選定候補として当該出力回線間調停手段に入力されるように出力制御する配信制御手段とをそなえていてもよい。
【００３５】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
（Ａ）本発明の一実施形態の説明
図１は本発明の一実施形態としてのパケット出力制御装置の全体構成を示すブロック図で、この図１に示すパケット出力制御装置１は、フレームメモリ２，変換テーブル３，キュー管理部４，パケットスケジューラ５，メモリ制御部６及びタイムスタンプ部７をそなえて構成されている。
【００３６】
ここで、フレームメモリ２（以下、単に「メモリ２」と略記することがある）は、キューを構成する物理メモリで、キューイングするパケットデータの本体が本メモリ２に格納されるようになっている。また、変換テーブル３は、入力パケットの宛先ＩＰアドレス等のヘッダ情報を基にフロー識別を行ない、その識別結果に応じて入力パケットを適切なキューへ振り分けるためのもので、一般的に、ＣＡＭ（Content Addressable Memory）等を用いて構成される。
【００３７】
さらに、キュー管理部４は、キュー毎にパケット情報を論理的にリンクし、パケットデータのフレームメモリ２内でのポインタを決定・管理するとともに、エンキューポインタ及びデキューポインタをメモリ制御部６に与えて、入力パケットのエンキュー及びデキューを制御するものである。
パケットスケジューラ（以下、単に「スケジューラ」ともいう）５は、キューの先頭パケットのスケジュールパラメータ（後述）に基づいて、デキューすべきパケットの順番及びタイミングを計算（スケジュール）するもので、そのスケジュール結果に従って次にデキューすべき先頭パケットのキュー番号がキュー管理部４に通知されるようになっている。
【００３８】
メモリ制御部６は、キュー管理部４からエンキュー又はデキューするパケットのポインタ（アドレス）を受信し、そのポインタが示すフレームメモリ２のアドレスに対するパケットの書き込み／読み出し制御を行なうためのものである。
つまり、このメモリ制御部６と上記のキュー管理部４とで、入力パケットをそのパケットのフローに応じて複数のキューのいずれかにエンキューするエンキュー手段と、パケットスケジューラ５からのデキュー指示によって指示されたキューからパケットをデキューするデキュー手段としての機能が実現されていることになる。
【００３９】
タイムスタンプ部７は、キューにエンキューするパケット毎に、その到着時刻を付加するためのものである。
上述のごとく構成されたパケット出力制御装置１での処理の流れは、次のようになる。
(1)入力パケットに、タイムスタンプ部７が到着時刻を付加する。
【００４０】
(2)入力パケットのヘッダ情報，パケットサイズ，到着時刻を変換テーブル３に入力してフロー識別を行ない、適切なキュー番号を得る。
(3)キュー管理部４にてパケット情報を指定キューにリンクし、エンキューパケット本体のフレームメモリ２への格納（エンキュー）ポインタをメモリ制御部６に出力して書き込み指示を与える。
【００４１】
(4)メモリ制御部６は、キュー管理部４から受信したエンキューポインタが示すフレームメモリ２のアドレスに入力パケットデータ本体を書き込む。
(5)キュー管理部４は、エンキューしたパケットがキューの先頭であった場合、そのパケットのスケジュールパラメータをスケジューラ５へ入力する。
(6)スケジューラ５は、各キューの先頭パケットのスケジュールパラメータを基に、スケジューリング処理（スケジューリング評価値Fの演算）を行ない、デキューすべきパケットの順序およびタイミングを決定して、デキューすべきキュー番号をキュー管理部４に出力する。
【００４２】
(7)キュー管理部４は、スケジューラ５から受信したキュー番号の先頭パケットが存在するポインタ（デキューポインタ）をメモリ制御部６に出力してパケットの読み出し指示を与える。
(8)この際、キュー管理部４は、パケット情報のリンク構造の操作（更新）を行ない、当該キューにおいてデキューされるパケットに続いてパケットが存在する場合は、そのパケットを新たな先頭パケットとみなして、そのパケットのスケジュールパラメータをスケジューラ５へ送出する。
【００４３】
(9)メモリ制御部６は、キュー管理部４から受信したデキューポインタが示すメモリ２のアドレスに書き込まれているパケットデータを読み出す。
以上のようにして、パケット出力制御装置１においても、スケジューラ５にて、各キューの先頭パケットについてそれぞれスケジューリング評価値Fの演算を行ない、その評価値Fを基にデキューすべきパケットの順序及びタイミングがスケジュールされるわけであるが、１０００本を超えるような膨大な数のキューに対応した全並列化は実質不可能なので、本実施形態のスケジューラ５では、評価値演算対象の出力回線を時分割に切り替えることで、同一出力回線に属する各キューの先頭パケットについての評価値Fの並列演算を、全出力回線間で共通に行なえるようになっている。
【００４４】
（Ａ１）パケットスケジューラの詳細説明
以下、本実施形態の要部であるスケジューラ５の詳細について説明する。
図２及び図３はいずれも上記のパケットスケジューラ５の構成を示すブロック図であるが、これらの図２及び図３に示すように、本実施形態のスケジューラ５は、前処理部５１，演算制御部５２，先頭パケットメモリ５３，γ演算部５４，並列演算部５５，選択部５６，シェーピング部５７，ポート間調停部５８，デキュー制御部５９及びタイマ６０等をそなえて構成されている。
【００４５】
また、先頭パケットメモリ５３には、複数の出力回線（ポート）＃１〜＃Ｍ毎にそれぞれ複数のフロー（ここでは、ｎ）に対応して設けられたキュー＃ｊ−１〜＃ｊ−ｎ（ただし、ｊは１〜Ｍ）が設けられ、並列演算部５５には、各キュー＃ｊ−１〜＃ｊ−ｎに対応して複数のスケジューリング評価値演算器５５−１〜５５−ｎが設けられ、シェーピング部５７には、出力回線＃１〜＃Ｍに対応して複数の出力回線シェーピング回路５７−１〜５７−Ｍが設けられている。
【００４６】
そして、この図２及び図３に示すスケジューラ５では、概略して、次のような処理が実行される。
即ち、まず、前処理部５１において、スケジュール演算の中間変数βが求められ、これがキュー＃ｊ−ｋ（ｋ＝１〜ｎ）毎に先頭パケットメモリ５３に他のスケジュールパラメータ（到着時刻Ti等）と共に格納される。そして、演算制御部５２において所定のタイムスロット毎にスケジューリングを行なう演算対象の出力回線＃ｊが決定され、それに従って先頭パケットメモリ５３から同一出力回線＃ｊに属する各キューの先頭パケットについてのスケジュールパラメータの組が同時（並列）に読み出されて、並列演算部５５の各スケジューリング評価値演算器（以下、単に「演算器」という）５５−１〜５５−ｎへ入力される。
【００４７】
各演算器５５−１〜５５−ｎでは、スケジューリング評価値F1〜Fnがパイプライン制御で求められ、後述する評価値有効フラグと共に選択部５６へ出力される。選択部５６は、有効な演算器５５−ｋの出力の中からスケジューリング評価値の最小値（当該出力回線＃ｊへ優先出力すべきパケット）を選出して、シェーピング部５７の出力回線シェーピング回路５７−ｊに出力回線＃ｊ別に格納する。
【００４８】
そして、シェーピング部５７は、出力回線シェーピング回路５７−ｊでの後述するシェーピング処理により、出力回線＃ｊの設定帯域に応じた処理オーバーフロー及びパケットバースト出力制御のための評価値の補正を行なった上で、補正後の評価値をポート間調停部５８へ出力し、ポート間調停部５８では、出力回線＃ｊ間での評価値の最小値選択を行なってデキュー制御部５９に出力する。
【００４９】
これにより、デキュー制御部５９は、ポート間調停部５８で選出された評価値に対応するキュー＃ｊ−ｋに対するデキュー指示を発生してキュー管理部４へ出力するとともに、そのキュー番号をキュー識別信号として前処理部５１，演算制御部５２，並列演算部５５，シェーピング部５７，ポート間調停部５８及びデキュー制御部５９へそれぞれフィードバックする。なお、このフィードバック信号は、後述するようにパイプライン処理上の同一評価値更新に用いられる。
【００５０】
以下、上述した各部の機能についてより詳細に説明する。
まず、先頭パケットメモリ５３は、図３に示すように、キュー管理部４から受信される、入力パケットのパケットサイズ情報や到着時刻情報等のスケジュールパラメータを上述のごとく出力回線（ポート）＃１〜＃Ｍ毎にそれぞれ複数のフローに対応して設けられたキュー＃ｊ−１〜＃ｊ−ｎにより保持・管理するものである。
【００５１】
そして、この先頭パケットメモリ５３は、本実施形態では、図８により後述するように、各演算器５５−１〜５５−ｎ用の先頭パケットメモリ５３−１〜５３−ｎをそなえて構成され、これらの先頭パケットメモリ５３−１〜５３−ｎに、出力回線＃１〜＃Ｍ別に各キュー＃ｊ−ｋのスケジュールデータが格納されるようになっている。
【００５２】
なお、これらの先頭パケットメモリ５３−１〜５３−ｎには、後述するように、先頭パケットを含む連続する複数パケットについてのスケジュールパラメータが格納される。また、本先頭パケットメモリ５３（５３−１〜５３−ｎ）は、例えば、ＲＡＭ等を用いて構成される。
また、並列演算部５５は、各キュー＃ｊ−１〜＃ｊ−ｎと１対１に対応付けられたｎ個の演算器５５−１〜５５−ｎにより、同一出力回線＃ｊ内の全キュー＃ｊ−１〜＃ｊ−ｎのスケジューリング評価値F1〜Fnを、それぞれ、下記に示すＷＦＱ演算式（４）により、所定の１タイムスロット内で同時に（並列に）演算するようになっている。
【００５３】
【数４】
つまり、本実施形態のスケジューラ５は、所定のタイムスロットによって演算対象とする出力回線＃ｊを切り替える、つまり、先頭パケットメモリ５３から読み出す各キュー＃ｊ−１〜＃ｊ−ｎの先頭パケットのスケジュールパラメータの組を切り替えることで、各出力回線＃１〜＃Ｍ間で各演算器５５−１〜５５−ｎを共有する構成になっているのである。
【００５５】
そして、上記のタイムスロットの割り当て、即ち、スケジュールパラメータ読み出し対象の出力回線＃ｊの時分割指定（以下、「時分割演算回線指定」ともいう）を制御するのが、上記の演算制御部（時分割演算回線指定部）５２であり、本実施形態では、例えば、図５に示すような演算出力回線テーブル５２１に基づいて上記時分割演算回線指定が行なわれるようになっている。
【００５６】
即ち、回線組み合わせ毎の１６ステップ〔タイムスロット（ＴＳ）〕を１サイクル（所定周期）とした場合、演算制御部５２は、例えば、図５中に丸付き数字１で示す1Gbps x16本(回線＃１〜＃１６：図５では単に回線１〜１６と表記している)の出力回線設定であれば全出力回線に対する割り当ての機会は同じであるので、デキュー制御部５９からのフィードバック情報（デキュー識別信号：デキュー指示が発生したキューを識別するための情報）を受信する毎に、１タイムスロット（ＴＳ）＝１回線の割合で演算ポートを決定することになる。
【００５７】
これに対し、図５中に丸付き数字２で示す1Gbps×8本(回線＃１〜回線＃８)，10Gbps×１本（回線＃９）の組み合わせでは、8Gbps:10Gbps=4:5であるが、簡略化して、回線＃１:回線＃２:回線＃３:回線＃４:回線＃５:回線＃６:回線＃７:回線＃８:回線＃９=1:1:1:1:1:1:1:1:8の割合で演算ポートが演算制御部５２によって決定されることになる。同様に、図５中に丸付き数字３〜５で示す設定の場合も、出力回線＃ｊの設定帯域が大きいものほど、その設定帯域に応じて１サイクル内でのタイムスロット割り当ての機会が多くなるように、演算ポートが演算制御部５２によって決定される。
【００５８】
なお、この演算ポートの割り当てにおいて、演算制御部５２は、例えば図６に示すように、出力回線＃ｊ毎に、先頭パケットメモリ５３からのパケット有無判定フラグ（図４参照）によってアクティブ回線／ノンアクティブ回線の判定を行ない、次ステップの回線＃ｊ＋１がノンアクティブである場合にはアクティブな回線＃ｊまで遷移して、演算ポートを指定する処理を行なう。
【００５９】
以上のような出力回線＃ｊ毎の設定帯域に応じた演算ポート切り替えを行なうことで、設定帯域の大きな出力回線＃ｊに属するキュー＃ｊ−ｋ（ｋ＝１〜ｎ）に対するデキュー指示を出力できる間隔を、設定帯域の小さな他の出力回線＃ｐ（ただし、ｐ＝１〜Ｍで、ｐ≠ｊ）に属するキュー＃ｐ−ｋに対するデキュー指示の間隔よりも狭くすることができ、設定帯域の大きな出力回線＃ｊほど、スループットを向上することができる。
【００６０】
例えば図７に示すように、（１）（図７中では、（１）〜（７）を丸付き数字で示す）回線Ａ，Ｂ，Ｃの出力帯域比をＡ：Ｂ：Ｃ＝２：１：１として演算ポート切り替えを行なったとすると、（２）先頭パケットメモリ５３からのスケジュールパラメータ読出，演算器５５−ｋでの（３）α値選択及びβ×γ演算処理，（４）評価値F（α＋β×γ）の有効判定処理，（５）選択部５６での最小評価値Fの選出処理及び（６）シェーピング部５７でのシェーピング処理から成るパイプライン処理上に存在するパケット情報の割合が、出力回線帯域が大きいほど多くなり、その結果、（７）ポート間調停部５８でのデキューバスシェーピング処理では、回線Ａに属するキューに対するデキュー指示の発生間隔が、回線Ｃに属するキューに対するデキュー指示の発生間隔よりも短くなり、回線Ａのスループットが向上するのである。
【００６１】
ところで、上記の各演算器５５−ｋの構成であるが、前記の評価値演算式（４）による演算機能を実現するために、例えば図４に示すような構成を有している。即ち、各演算器５５−ｋは、α選択回路５５１，出力判定回路５５２，セレクタ５５３，乗算器５５４及び加算器５５５をそなえて構成されている。なお、この図４において、６１は前回の評価値演算結果Fi-1を出力回線＃ｊ毎に保持する前評価値メモリを示すが、図２及び図３においてはその図示を省略している。
【００６２】
ここで、α選択回路５５１は、先頭パケットメモリ５３から読み出されたパケット到着時刻Tiと、前評価値メモリ６１に出力回線＃ｊ毎に保持された前回の評価値演算結果Fi-1とを比較して、値の大きい方を選出することにより、前記の評価値演算式（４）におけるmax{Fi-1, Ti}（フロー番号ｋを表す添え字は省略）を求めるものである。なお、前評価値メモリ６１からの前回の評価値演算結果Fi-1の読み出しは、演算制御部５２が演算ポート指定信号を読み出しアドレスとして指定することによって行なわれる。
【００６３】
また、出力判定回路５５２は、デキュー制御部５９によるデキュー指示の発生毎に、先頭パケットメモリ５３から上述した演算ポート切り替えに併せて出力回線＃ｊ毎の状態（パケットの有無）を表すパケット有無フラグと、タイマ６０からの現時刻情報Trとに基づいて、最終的に加算器５５５で求められる評価値Fiの有効／無効を判定して、その判定結果を出力するもので、ここでは、タイマ６０の現在時刻Tr>評価値Fiであれば「有効」を表すフラグが出力されるようになっている。なお、この評価値有効フラグが「無効」を示している評価値Fiは後段の選択部５６での調停対象外となる。
【００６４】
さらに、セレクタ５５３（帯域配分率選択手段）は、ＷＦＱ／固定切り替え設定に応じて、γ演算部５４で求められた前記の評価値演算式（４）におけるγ値（余剰帯域の帯域再配分率）と固定値〔固定帯域配分率（γ＝１）〕とを選択的に出力するもので、ＷＦＱによる帯域制御（余剰帯域の再配分）を行なう場合にはγ演算部５４の出力を選択し、余剰帯域の再配分を行なわない固定帯域制御を行なう場合には固定値γ＝１を選択して、乗算器５５４へ出力するようになっている。なお、上記の評価値演算式（４）においてγ＝１とすると、
【００６５】
【数５】
となる。また、上記の固定値γ＝１は、レジスタ等（固定帯域制御手段）に設定・保持される。
このように、演算器５５−ｋ毎に、ＷＦＱ／固定帯域キューの設定を行なうことにより、出力回線＃ｊ毎に、ＷＦＱによる帯域制御と固定帯域制御との構成比を任意に変更することが可能となり、出力回線＃ｊ毎に様々な帯域制御が可能となる。なお、かかるＷＦＱ／固定帯域キューの設定は、例えば図３５に示すように、各演算器５５−ｋに、出力回線＃ｊ毎にＷＦＱ／固定帯域キューの設定情報を保持する設定レジスタ５５６をもたせ、演算制御部５２からの出力回線指定に従って該当設定情報をＷＦＱ／固定帯域キュー切り替え信号としてセレクタ５５３に入力することで行なえる。
【００６７】
例えば、回線Ａ，Ｂ，Ｃ，Ｄの４回線について設定レジスタ５５６に「固定帯域制御」の設定情報を設定したとすると、図３６に示すように、回線Ａ，Ｂ，Ｃ，Ｄが演算対象として演算制御部５２により指定された場合は、γ＝１がセレクタ５５３により選択され、それ以外の回線についてはγ演算部５４で再計算されたγ値が選択されることになる。
【００６８】
次に、図４に示す乗算器５５４は、上記セレクタ５５３の出力と先頭パケットメモリ５３から読み出された中間変数βとを乗算することにより、前記の評価値演算式（４）におけるβ×γの項を求めるものであり、加算器５５５は、この乗算器５５４で求められたβ×γと、上述したα選択回路５５１で選択されたαとを加算することにより、前記の評価値演算式（４）で表される評価値Fi（＝α＋β×γ）を求めるものである。
【００６９】
なお、上記の中間変数β（＝Li／φi）は、パケット長Liとキュー＃ｊ−ｋの設定帯域φiによって求まり、設定帯域φiは時間による変化がないものと定義すると、デキュー指示発生毎の繰り返し演算は不要である。そこで、本実施形態においては、前処理部５１において、中間変数βを前処理として各キュー＃ｊ−ｋに共通で演算し、その結果を、同一出力回線＃ｊの各キュー＃ｊ−ｋの先頭パケットに関するスケジュールパラメータ（到着時刻Ti，パケット長Li）とともに同一タイムスロットで読み出されるように先頭パケットメモリ５３に保持させるようにする。
【００７０】
即ち、例えば図８に示すように、先頭パケットメモリ５３を、それぞれ出力回線＃ｊ別に各キュー＃ｊ−ｋの先頭パケットを保持する演算器５３−ｋ用の先頭パケットメモリ５３−１〜５３−ｎにより構成し、前処理部５１１において、キュー＃ｊ−ｋ毎に予め設定帯域φiが保持されたφ設定テーブル５１１から、キュー管理部４から通知されるキュー番号をアドレスとして該当キュー＃ｊ−ｋの設定帯域φiを読み出し、この設定帯域φiを除算器５１２にて同じくキュー管理部４から通知されるパケット長Liで除算することにより中間変数βを求め、これを、同一出力回線＃ｊに属する各キュー＃ｊ−ｋの先頭パケットについての中間変数として各演算器５３−ｋに保持させるようにするのである。このようにして、中間変数βの演算を前処理部５１で出力回線＃ｊ間で共通に行なうようにすることで、回路規模の削減を図ることが可能である。
【００７１】
さて次に、図２及び図４に示すγ演算部（帯域配分率算出手段）５４は、前記の評価値演算式（４）におけるγを求めるものであるが、本実施形態では、得られたγ値を各演算器５５−ｋでの同一出力回線＃ｊに属する各キュー＃ｊ−ｋについての評価値演算に同時に反映させるようになっている。そして、その構成は、例えば図９に示すように、γ演算制御部５４１，φ設定テーブル５４２，φ加減算器５４３，セレクタ５４４，Ｒ設定テーブル５４５，セレクタ５４６及び除算器５４７をそなえて構成されている。
【００７２】
ここで、上記のφ設定テーブル５４２は、キュー＃ｊ−ｋ毎の設定帯域φiを保持するものであり、φ加減算器５４３は、γ演算制御部１からの加減算指示信号に従って、このφ設定テーブル５４２から読み出されるφi値によりそれまでのφi値の累積値φb（アクティブキューの設定帯域の合計）についての加減算処理を出力回線（以下、単に「回線」ともいう）＃ｊ別に行なうもので、このために、図１０及び図１１に示すように、それぞれ加減算器５４３１とレジスタ５４３２とをそなえて成る回線＃ｊ毎のφb累積器５４３−１〜５４３−Ｍを有して構成されている。
【００７３】
また、セレクタ５４４は、演算制御部５２からの演算タイムスロット割り当てにより演算対象である回線＃ｊについて上記φ加減算器５４３（累積器５４３−ｊ）で求められた累積値φbを選択出力するものであり、Ｒ設定テーブル５４５は、出力回線＃ｊ毎の設定帯域Ｒ（＝同一出力回線＃ｊ内キュー＃ｊ−ｋの設定帯域φiの合計）を保持するものであり、セレクタ５４５は、セレクタ５４４と同様に、演算制御部５２からの演算タイムスロット割り当てにより演算対象である回線＃ｊについてのＲ値を選択出力するものである。
【００７４】
さらに、除算器５４７は、セレクタ５４４で選択されたφbを、セレクタ５４６で選択されたＲ値で除算することによりγ値を求めるもので、このようにして得られたγ値が回線＃ｊ毎の余剰帯域の再配分率として各演算器５５−ｋに入力されて、そのγ値（再配分率）による前記評価値演算式（４）の再計算が演算対象回線＃ｊの全キュー＃ｊ−ｋに対して同時に行なわれ、各キュー＃ｊ−ｋの先頭パケットについての評価値Fiに同時に反映される。
【００７５】
そして、γ演算制御部５４１は、エンキュー又はデキューのイベント発生毎に、該当キュー＃ｊ−ｋのパケット有無判定（つまり、アクティブキュー／ノンアクティブキューの判定）を行ない、φ加減算器５４３に対して、図１２に示すフローチャートに従った回線＃ｊ毎の加減算指示信号を出力することにより、エンキュー及びデキュー発生毎に、そのときのアクティブキュー数に応じた累積値φb（アクティブキューの合計予約帯域）の更新を行なうものである。
【００７６】
なお、各キュー＃ｊ−ｋのパケット有無判定は、本実施形態では、キュー管理部４がそなえるパケット数カウンタ（図示省略）ではなく、先頭パケットメモリ５３（５３−ｋ）におけるパケットの有無により判定を行なう。これは、図２５〜図３０により後述するようなキュー管理部４による連続パケットの管理により、常に、先頭パケットメモリ５３にパケットが存在するようになっているため、先頭パケットメモリ５３の状態を監視すれば、キュー＃ｊ−ｋ上のパケット有無判定が可能なためである。
【００７７】
さて、γ演算制御部５４１の動作であるが、γ演算制御部５４１は、スケジューラ５に入力があるか否かを監視するとともに（ステップＳ１）、デキュー制御部５９によりデキュー指示が発生したか否かを監視しており（ステップＳ６）、例えば、スケジューラ５にキュー番号の入力があると（ステップＳ１でＹＥＳと判定されると）、φ設定テーブル５４２に対してφiの読み出しアドレスを与えて、入力キュー番号に対応する演算対象のキュー＃ｊ−ｋについてのφiを読み出す（ステップＳ２）。
【００７８】
そして、γ演算制御部５４１は、該当キュー＃ｊ−ｋの先頭パケットメモリ５３（５３−ｋ）が空き状態であるか否かを確認し（ステップＳ３）、空き状態であれば（ステップＳ３でＹＥＳと判定されれば）、デキュー制御部５９による同一キュー＃ｊ−ｋへのデキュー指示が同時発生しているか否かをさらに確認し（ステップＳ４）、デキュー指示が同時発生していなければ（ステップＳ４でＮＯと判定されれば）、エンキュー指示の発生であるから、エンキュー指示の発生した回線＃ｊ−ｋの累積器５４３−ｊの加減算器５４３１に対して設定帯域φiの加算指示を与えて、レジスタ５４３２に保持されている累積値φbにφ設定テーブル５４２から読み出されたφi値を加算させる（ステップＳ５）。
【００７９】
なお、上記の処理において、スケジューラ５への入力が無い場合（ステップＳ１でＮＯの場合）や、該当キュー＃ｊ−ｋの先頭パケットメモリ５３（５３−ｋ）が空き状態でない場合（ステップＳ３でＮＯの場合）、γ演算制御部５４１は、引き続き、スケジューラ５への入力の有無，デキュー指示の発生の有無の監視を行なう。また、同一キュー＃ｊ−ｋに対するエンキュー指示とデキュー指示とが同時発生した場合（ステップＳ４でＹＥＳの場合）も、当該キュー＃ｊ−ｋのパケット数に変わりがないから、γ演算制御部５４１は、監視動作を継続する。
【００８０】
これに対して、デキュー制御部５９によるデキュー指示が発生した場合（ステップＳ６でＹＥＳの場合）、γ演算制御部５４１は、上記のステップＳ２と同様に、入力キュー番号に対応する演算対象のキュー＃ｊ−ｋについての設定帯域φiを読み出し（ステップＳ７）、そのキュー番号に対応する先頭パケットメモリ５３（５３−ｋ）に格納されているパケットが残り１パケットであるか否かを確認する（ステップＳ８）。
【００８１】
その結果、パケットが残り１パケットであると（ステップＳ８でＹＥＳと判定されると）、γ演算制御部５４１は、さらに、同一キュー＃ｊ−ｋに対するエンキュー指示が同時発生しているか否かを確認し（ステップＳ９）、エンキュー指示が発生していなければ（ステップＳ９でＮＯと判定されれば）、デキュー指示の発生した回線＃ｊ−ｋに対応する累積器５４３−ｊの加減算器５４３１に対して設定帯域φiの減算指示を与えて、レジスタ５４３２に保持されている累積値φbにφ設定テーブル５４２から読み出されたφi値を減算させる（ステップＳ１０）。
【００８２】
なお、この場合も、デキュー指示が発生していない場合（ステップＳ６でＮＯの場合）や、該当キュー＃ｊ−ｋの先頭パケットメモリ５３（５３−ｋ）に２以上のパケットが残っている場合（ステップＳ８でＮＯの場合）、γ演算制御部５４１は、監視動作を継続する。また、同一キュー＃ｊ−ｋに対するデキュー指示とエンキュー指示とが同時発生した場合（ステップＳ９でＹＥＳの場合）も、当該キュー＃ｊ−ｋのパケット数に変わりがないから、γ演算制御部５４１は、監視動作を継続する。
【００８３】
以上のようにして、γ演算部５４では、エンキュー及びデキューの発生毎に、そのエンキュー及びデキューのキュー番号情報を基に、該当キュー＃ｊ−ｋの設定帯域φiがφ設定テーブル５４２から読み出されて、その設定帯域φiによる累積値φbの更新が行なわれ、更新後の累積値φbに基づいてγ値が再計算される。そして、このγ値が各演算器５５−ｋにそれぞれ入力されることにより、同一出力回線＃ｊに属する各キュー＃ｊ−ｋの先頭パケットについての評価値Fiに同時に反映されるのである。
【００８４】
このように、γ値（再配分率）の計算を回線＃ｊ間で共通化することにより、回路規模の削減を図ることが可能である。
さて次に、図２及び図３に示す選択部（同一出力回線内キュー間調停手段）５６は、上述した各演算器５５−１〜５５−ｎで求められた各評価値F1〜Fnの中から最小の評価値（優先出力すべき評価値）を選出するものである。例えば図１３に示すように、キューａ，ｂ，ｃ，ｄの先頭パケットの到着時刻がそれぞれTai，Tbj，Tck，Tdm（Tai＜Tbj＜Tck＜Tdm）であり、キューａ，ｂ，ｃ，ｄの前回の先頭パケットについての評価値（送信完了予定時刻）がそれぞれ、Fai-1（＜Tai），Fbj-1（＜Tbj），Fck-1（＜Tck），Fdk-1（＞Tdk）であったとする。
【００８５】
すると、この場合、キューａ，ｂ，ｃについては、それぞれ、前回の送信完了予定時刻よりも到着時刻の方が遅い（Fai-1＜Tai，Fbj-1＜Tbj，Fck-1＜Tckの関係にある）ので、前記のα値はそれぞれ到着時刻Tai，Tbj，Tckが基準となり、キューｄについては、逆に、前回の送信完了予定時刻よりも到着時刻の方が早い（Fdk-1＞Tdkの関係にある）ので、前記のα値は前回の送信完了予定時刻Fdk-1が基準となって、それぞれについての今回の送信完了予定時刻Fai，Fbj，Fck，Fdm（Fai＜Fbj＜Fck＜Fdm）が演算器５５−ｋで求められることになる。
【００８６】
したがって、図１３の場合、キューａ≧キューｂ≧キューｃ≧キューｄの優先順位で選出が行なわれることになる。ただし、この図１３の場合、キューｄについてのα値がタイマ６０の計時値（Timer値）よりも大きい（α＜Timer値）ので、キューｄについての出力は許可されない。つまり、この場合は、キューa，ｂ，ｃ間でのみ出力調停が行なわれ、Fai＜Fbj＜Fckであるので、キューａ≧キューｂ≧キューｃの優先順位で選出が行なわれることになる。
【００８７】
なお、本選択部５６の調停アルゴリズムは、図２０（Ａ）及び図２０（Ｂ）により後述するポート間調停部５８の調停アルゴリズムと同様である。
次に、シェーピング部５７の出力回線シェーピング回路５７−ｊは、それぞれ、上述のごとく選択部５６により選出された評価値Fを出力回線シェーピング回路５７−１〜５７−Mにより出力回線＃ｊ別にバッファリングして、各出力回線＃ｊの設定帯域に応じたシェーピング処理を行なうもので、本実施形態では、例えば図１４に示すように、シェーピング制御部５７１とパケット情報レジスタ５７２とをそなえて構成され、シェーピング制御部５７１は、例えば図１５に示すように、さらに、出力判定値演算回路５７１−１，出力判定回路５７１−２及びバースト制御回路５７１−３をそなえて構成されている。
【００８８】
ここで、上記のシェーピング制御部５７１は、回線＃ｊ毎の設定帯域に応じた出力帯域のシェーピング制御を行なうものであり、パケット情報レジスタ５７２は、同一回線＃ｊに属する各キュー＃ｊ−ｋの先頭パケットについてのスケジューリング結果（評価値F）を保持するものである。
そして、シェーピング制御部５７１において、出力判定値演算回路５７１−１は、デキュー制御部５９による出力回線＃ｊのデキュー発生時に、下記式（６）によって、出力判定値Ci（評価値Fの補正値）の演算を行なうものである。
【００８９】
【数６】
なお、この式（６）において、Ci はパケット出力完了予定時刻、Ci-1は前パケット出力完了予定時刻、SEL｛Ci-1，Timer｝はCi-1とTimer値のいずれかの選択、Li はデキューパケット長、Ｒは出力回線設定帯域をそれぞれ表す。
このため、本出力判定値演算回路５７１−１は、例えば図１６に示すように、セレクタ５７１１，除算器５７１２，加算器５７１３及びレジスタ（Ｒ）５７１４をそなえて構成され、セレクタ５７１１により上記式（６）の第１項〔SEL｛Ci-1，Timer｝〕の機能が実現され、除算器５７１２により上記式（６）の第２項（Li／Ｒ）の演算が実現され、加算器５７１３により上記式（６）の第１項及び第２項の加算機能が実現されている。なお、レジスタ５７１４は、セレクタ５７１１の出力をラッチするためのものである。
【００９１】
そして、出力判定回路５７１−２は、上記の出力判定値Ci＜Timer値となった時に、次パケットについての出力判定（許可）信号をアサートする処理を行なうものである。この出力判定信号により出力許可されていない（ディゼーブルの）出力判定値Ciは、後段でのポート間調停部５８での最小値選択処理から除外されることになる。なお、上記出力判定信号は、出力パケットが無い場合と、後述するデキュー制御部５９からのフィードバック出力（マスク指示信号）によってもディセーブルされる。
【００９２】
図１７にシェーピング処理の概念を示す。或る先頭パケット（パケット番号“０”）についてデキューが発生した場合、まず、出力判定値演算回路５７１により、下記に示す式（７）により、出力判定値C0が演算される。
【００９３】
【数７】
ただし、ここでは、パケット番号“０”のパケットは前パケットが無効であるか、もしくは、後述するバースト制御回路５７１−３によるバースト制御により、デキュー時のTimer値（D0）がSEL｛Ci-1，Timer｝の項（セレクタ５７１１）において選択されているものとする。
そして、タイマ６０のTimer値（現在時刻）＜C0である時は、次パケットの出力が出力回線シェーピング回路５７−ｊ（パケット情報レジスタ５７２）にバッファリングされていてもそのデータ出力は許可されず（該当回線＃ｊの出力判定フラグが「無効」）、図１７に示すように、Timer値≧C0の条件で、次パケットについてのデータ出力が許可（該当回線＃ｊの出力判定フラグが「有効」）される。
【００９５】
このようにして、出力回線＃ｊ毎に、出力回線帯域設定に応じた出力判定フラグによる出力調停を行なうことにより、前出力完了時刻の早いパケットから優先的にデキューを発生させることができるので、同一出力回線＃ｊ内のキュー＃ｊ−ｋ単位の出力帯域の取り戻し制御を効果的に行なうことができる。また、調停回路の簡素化も可能である。
【００９６】
ところで、この場合、上記の出力判定値と実際のデキュー処理時刻との差（D‐C）が処理レイテンシ及びデキューバス上の輻輳等の影響により大きくなった場合、次パケット以降の出力がバースト的に行なわれ、デキューバス上の輻輳及びフレームメモリ２上での処理の破綻を招くおそれがある。
そこで、その保護のために、本実施形態では、図１５に示すバースト制御回路５７１−３により、上記の差の監視によるバースト出力制御を行なう。図１８にバースト制御の概念を示す。なお、この図１８において、Bはバースト出力を許可する制限値を表し、各出力回線シェーピング回路５７−ｊに設定される。
【００９７】
そして、図１８の（１）（図１８中では、（１），（２）を丸付き数字で示す）に示す場合は、デキュー発生時にTimer値‐C＜Bであるから、上記の式（７）のSEL｛Ci-1，Timer｝の項においてCi-1が選択され、次パケット出力のバースト出力が許可される。
これに対し、図１８の（２）に示す場合は、デキュー発生時にTimer値‐C≧Bであるから、上記の式（７）のSEL｛Ci-1，Timer｝の項においてTimer値が選択され、次パケットのバースト出力は許可されない。
【００９８】
このように、出力回線＃ｊ毎のバースト出力制御を行なうことにより、出力回線＃ｊ内のキュー＃ｊ−ｋ単位の帯域の取り戻しを許可しながら、出力回線＃ｊ毎のデキューによるオーバーフローを回避することが可能になる。
次に、図２及び図３に示すポート間調停部５８は、上述したシェーピング部５７から出力される出力判定フラグと出力判定値Ciとを基に、出力回線＃ｊ間のパケット出力の調停（有効な出力判定値Ciの中からの最小値選択）を行ない、これにより選択された出力回線＃ｊのキュー＃ｊ−ｋについての判定値をデキュー制御部５９へ出力するものである。
【００９９】
このポート間調停制御部５８による調停制御の概念を図１９に示す。この図１９に示す場合、現在時刻（Timer値）において、回線Ａ〜Ｄについてのシェーピング部５７での出力判定フラグの状態は、回線Ｄについては出力完了予定時刻C≧Timer値であるのでディゼーブル（「無効」）、他の回線Ａ，Ｂ，Ｃについては出力完了予定時刻C＜Timer値であるのでイネーブル（「有効」）となっている。
【０１００】
従って、ポート間調停部５８では、回線Ｄを除く回線Ａ，Ｂ，Ｃの中で、デキュー制御部５９への出力回線＃ｊを決定することになる。ここで、回線Ａ，Ｂ，Ｃについてのパケット出力完了予定時刻Cai，Cbj，Cckの関係は、Cbj＞Cai＞Cckとなっているが、回線Ｃについてはシェーピング部５７での上記バースト制御によってバースト制限値を超えているために出力完了予定時刻Cckは無効となり、その代わりにシェーピング部５７への入力時刻Sck+1が基準となる。
【０１０１】
これにより、ポート間調停部５８は、Cbj＞Sck+1＞Caiの関係から、回線Ａ≧回線Ｃ≧回線Ｂの優先順位でデキュー制御部５９へデータ出力することになる。つまり、上記のシェーピング部５７及びポート間調停部５８は、選択部５６で選出された評価値を出力回線＃ｊ毎に保持し、それらの評価値と出力回線＃ｊの設定帯域とに基づいて優先出力すべき先頭パケットを決定する出力回線間調停手段としての機能を果たしているのである。
【０１０２】
なお、以上の調停アルゴリズムをＣ言語のような記述で表現したものを図２０（Ｂ）に示す。なお、この図２０（Ｂ）に示す調停アルゴリズムは、図２０（Ａ）に示すように、４ポート分の出力判定値（Sa，Sb，Sc，Sd）と、それぞれの判定フラグ（Valid_Sa，Valid_Sb，Valid_Sc，Valid_Sd）とを入力した場合のアルゴリズムを示している。
【０１０３】
次に、図２に示すデキュー制御部５９は、ポート間調停部５８の出力をバッファリングし、デキューバスの設定帯域に応じたシェーピング処理を行なうもので、前述した出力回線シェーピング回路５７−ｊの構成（図１４及び図１５参照）と同様に構成され、例えば図２１に示すように、デキューバスの設定帯域に応じた出力帯域のシェーピング処理を制御するシェーピング制御部（デキューバスシェーピング制御部）５９１と、ポート間調停部５８による調停結果を保持するパケット情報レジスタ５９２とをそなえている。
【０１０４】
さらに、シェーピング制御部５９１には、図２２に示すように、出力判定値演算回路５９１−１，出力判定回路５９１−２及びバースト制御部（デキューバスバースト制御部）５９１−３がそなえられている。
そして、シェーピング制御部５９１の出力判定値演算回路５９１は、出力判定回路５９１−２のからのデキューイネーブルアサートタイミング毎に、下記の式（８）による出力判定値演算を行なうものである。
【０１０５】
【数８】
なお、この式（８）において、Ciはパケット出力完了予定時刻、Ci-1は前パケット出力完了予定時刻、SEL｛Ci-1，Timer｝はCi-1とTimer値のいずれかの選択、Liはデキューパケット長、ＤＲはデキューバス設定帯域をそれぞれ表す。
また、出力判定回路５９１−２は、上記の出力判定値演算回路５９１による演算結果Ciがタイマ６０のTimer値よりも小さい（Timer値＞Ci）となった場合に、次パケットの出力許可信号（デキューイネーブル信号）のアサート処理（キュー管理部４へのデキュー指示）を行なうものである。
【０１０７】
これらの出力判定値演算回路５９１−１及び出力判定回路５９１−２によって、デキューバスの設定帯域（ＤＲ）に応じたシェーピング処理が可能となる。図２３にシェーピング処理の概念を示す。シェーピング処理自体は、前述した出力回線シェーピング回路５７−ｊにおける処理と同様であり、この場合も、或る先頭パケット（パケット番号“０”）のデキューが発生した場合、まず、出力判定値演算回路５９１−１にて、以下の式（９）が演算される。
【０１０８】
【数９】
ただし、この場合も、パケット番号“０”のパケットは前パケットが無効であるか、もしくは、後述するバースト制御部５９１−３によるバースト制御によりデキュー発生時のTimer値（D0） が選択されているものと仮定する。
そして、上記の式（９）による演算結果C0がタイマ６０のTimer値よりも大きい（Timer値＜C0）場合は、出力判定回路５９１−２によりデキューイネーブル信号はディゼーブルされデキュー指示は発生しない。これに対し、Timer値≧C0の場合、出力判定回路５９１−２は、その時に有効なデータがパケット情報レジスタ５９２に格納されていれば、デキューイネーブル信号をアサートし、キュー管理部４へデキューパケット番号を通知する。
【０１１０】
なお、このデキューパケット番号は、パイプライン処理上の同一評価値更新（同一パケットの重複出力防止）のために、前処理部５１，演算制御部５２，並列演算部５５，シェーピング部５７，シェーピング制御部５９１内の出力判定回路５９１−１及びバースト制御部５９１−３にそれぞれフィードバックされる。
このようにして、デキュー制御部５９においても、デキューバスの設定帯域に応じたシェーピング処理を行なうことにより、前出力完了時刻の早いパケットから優先的にデキューを発生させることができるので、デキューバス内における出力回線単位の帯域の取り戻し制御を効果的に行なうことができる。また、調停回路の簡素化も可能である。
【０１１１】
ところで、この場合も、出力判定値演算回路５９１−１による演算結果と実際のデキュー時刻との差（D‐C）が処理レイテンシ及びデキューバス上の輻輳などにより大きくなった場合、次パケット以降の出力がバースト的に行なわれ、デキューバス上の輻輳及びフレームメモリ２上での処理の破綻を招くおそれがある。
そこで、その保護のために、本デキュー制御部５９においても、出力回線シェーピング回路５７−ｊと同様に、図２２に示すバースト制御回路５９１−３によって、上記差の監視によるバースト制御を行なう。図２４にバースト制御の概念を示す。なお、この図２４において、Bは、バースト出力を許可する制限値を表す。
【０１１２】
即ち、図２４の（１）（図２４中では、（１），（２）を丸付き数字で示す）で示す場合は、デキュー発生時にTimer値‐C＜Bであるから、上記の式（９）におけるSEL｛Ci-1，Timer｝の項においてCi-1が選択され、次パケットのバースト出力が許可されることになる。これに対し図２４の（２）で示す場合は、デキュー発生時にTimer値‐C≧Bであるから、上記SEL｛Ci-1，Timer｝の項においてTimer値が選択され、次パケットのバースト出力は許可されないことになる。
【０１１３】
かかるバースト制御により、デキューバスにおける出力回線＃ｊ単位の帯域の取り戻しを許可しながら、その帯域制御に伴うデキューバスのオーバーフローを有効に回避することが可能となる。
次に、以下では、上述したキュー管理部４でのキュー管理の詳細について説明する。
【０１１４】
図２５に示すように、本実施形態のキュー管理部４は、パラメータメモリ４１、次ポインタテーブルメモリ４２，第３（3th）パラメータメモリ４３，パケットカウンタメモリ４４及びポインタテーブルメモリ４５をそなえている。
ここで、パラメータメモリ４１は、図１に示すフレームメモリ２と同じワード数の記憶容量を有しており、ここに、図１に示す変換テーブル３から入力される各キュー＃ｊ−ｋの先頭パケットについてのスケジュールパラメータ〔パケット長，タイムスタンプ（到着時刻），ビットマップ情報等〕が順次格納されるようになっている。なお、上記の「ビットマップ情報」は後述する変形例においてパケットのマルチキャストを行なう際に指定される情報であり、マルチキャストを行なわない場合には不要な情報である。
【０１１５】
また、次ポインタテーブルメモリ４２も、このパラメータメモリ４１と同じワード数の記憶容量を有しているが、ここには、パラメータメモリ４１と同じポインタ上に、次パケットのポインタが格納されるようになっている。したがって、この次ポインタテーブルメモリ４２を検索することにより、パラメータメモリ４１からパラメータを連続的に取り出すことが可能になる。
【０１１６】
さらに、第３パラメータメモリ４３は、キュー＃ｊ−ｋの先頭から３番目のパケットについてのスケジュールパラメータ〔第３（3th）パラメータ〕をキュー＃ｊ−ｋ別に保持するものである。つまり、この場合、第３パラメータは、パラメータメモリ４１と第３パラメータメモリ４３の双方に格納されるようになっている。したがって、キュー番号のアドレスを基に先頭から３番目のパケットにつてのパラメータを、次ポインタテーブルメモリ４２を検索することなく即時出力することが可能となる。
【０１１７】
また、パケットカウンタメモリ４４は、キュー＃ｊ−ｋに格納されているパケット数をキュー＃ｊ−ｋ別に保持するものであり、ポインタテーブルメモリ４５は、先頭（Top）ポインタメモリ４５１，第４（4th）ポインタメモリ４５２及び最終（End）ポインタメモリ４５３により、キュー＃ｊ−ｋの先頭パケット，４番目のパケット及び最終パケットのパラメータメモリ４１上の格納位置を指すポインタを、キュー＃ｊ−ｋ別に保持するもので、これにより、キュー番号のアドレスを基に、キュー＃ｊ−ｋの先頭パケット，４番目のパケット及び最終パケットを検索することが可能である。
【０１１８】
具体的に、例えば、或るキュー＃ｊ−ｋに７個のパケットａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇがパケットａを先頭パケットとして連続して格納されている場合を考えると、上記のパラメータメモリ４１、次ポインタテーブルメモリ４２，第３（3th）パラメータメモリ４３，パケットカウンタメモリ４４及びポインタテーブルメモリ４５の上記ポインタによるデータリンク構造は図２６に示すようになる。
【０１１９】
即ち、図２６に示すように、或るキュー＃ｊ−ｋにエンキューされたパケットａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇのパラメータがそれぞれパラメータメモリ４１に格納された場合、次ポインタテーブルメモリ４２においては、パラメータメモリ４１と同じポインタ上にそれぞれ次パケットｂ，ｃ，ｄ，ｅ，ｆ，ｇのポインタが格納される。また、先頭から３番目のパケットｃについてのパラメータは、パラメータメモリ４１とは別に、第３パラメータメモリ４３にも格納される。
【０１２０】
そして、ポインタテーブルメモリ４５においては、各ポインタメモリ４５１，４５２，４５３の該当キュー番号が示すアドレスに、先頭パケットａについてのポインタ，４番目のパケットｄについてのポインタ，最終パケットｇについてのポインタがそれぞれ格納される。
以下、上述したリンク構造によりキュー管理を行なうキュー管理部４のエンキュー及びデキュー時の動作についてそれぞれ詳述する。
【０１２１】
（１）エンキュー時の動作
まず、キュー管理部４は、図２７に示すように、図１に示す変換テーブル３からのエンキュー指示の有無を監視しており（ステップＳ１１のＮＯルート）、エンキュー指示を受けると（ステップＳ１１でＹＥＳの場合）、エンキュー指示されたキュー番号のパケット数をパケットカウンタメモリ４４から読み出して現在のパケット数を識別し（ステップＳ１２）、そのパケット数に応じて、スケジューラ５へのパラメータ出力と、キュー管理部４内部のポインタ制御（ポインタリンク構造の更新）とを次のようにして実行する。
【０１２２】
即ち、識別したパケット数が０個で該当キュー＃ｊ−ｋの状態が空の場合（ステップＳ１３でＹＥＳの場合）、キュー管理部４は、図２８に示す処理（１）（図２８中では、（１）〜（５）を丸付き数字で示す）を実行して、入力パラメータをそのままスケジューラ５へ出力するとともに、ポインタリンク構造を更新し（ステップＳ１８）、パケットカウンタメモリ４４の該当キュー＃ｊ−ｋのパケット数をインクリメント（＋１）する（ステップＳ２４）。
【０１２３】
識別したパケット数が１個の場合（ステップＳ１３でＮＯ，ステップＳ１４でＹＥＳの場合）、キュー管理部４は、図２８に示す処理（２）を実行して、入力パラメータを先頭から２番目のパケットについてのパラメータとしてスケジューラ５へ送出するとともに、ポインタリンク構造を更新し（ステップＳ１９）、パケットカウンタメモリ４４の該当キュー＃ｊ−ｋのパケット数をインクリメント（＋１）する（ステップＳ２４）。
【０１２４】
識別したパケット数が２個の場合（ステップＳ１３及びＳ１４でＮＯ，ステップＳ１５でＹＥＳの場合）、キュー管理部４は、図２８に示す処理（３）を実行して、入力パラメータを先頭から３番目のパケットについてのパラメータとして第３パラメータメモリ４３に格納するとともに、ポインタリンク構造を更新し（ステップＳ２０）、パケットカウンタメモリ４４の該当キュー＃ｊ−ｋのパケット数をインクリメント（＋１）する（ステップＳ２４）。
【０１２５】
識別したパケット数が３個の場合（ステップＳ１３〜Ｓ１５でそれぞれＮＯ，ステップＳ１６でＹＥＳの場合）、キュー管理部４は、図２８に示す処理（４）を実行して、先頭から４番目のパケットについてのポインタが第４ポインタメモリ４５２に格納するとともに、ポインタリンク構造を更新し（ステップＳ２１）、パケットカウンタメモリ４４の該当キュー＃ｊ−ｋのパケット数をインクリメント（＋１）する（ステップＳ２４）。
【０１２６】
識別したパケット数が４個以上の場合（ステップＳ１３〜Ｓ１６でそれぞれＮＯ，ステップＳ１７でＹＥＳの場合）は、キュー管理部４は、図２８に示す処理（５）を実行して、最終ポインタの更新のみを行ない（ステップＳ２２）、パケットカウンタメモリ４４の該当キュー＃ｊ−ｋのパケット数をインクリメント（＋１）する（ステップＳ２４）。
【０１２７】
ただし、本実施形態においてパケットのカウンタ値の最大値は５としており、識別したパケット数が既に５以上である場合は、図２８に示す処理（５）の後、カウンタ値のインクリメントは行なわれない（パケットカウンタメモリ４４の該当カウンタ値には５が固定的に設定される）（ステップＳ２３）。
（２）デキュー時の動作
これに対し、デキュー時には、キュー管理部４は、図２９に示すフローチャート（ステップＳ３１〜Ｓ４５）に従って動作する。即ち、キュー管理部４は、スケジューラ５からのデキュー指示の受信を監視しており（ステップＳ３１のＮＯルート）、デキュー指示を受けると（ステップＳ３１でＹＥＳの場合）、キュー管理部４は、該当キュー＃ｊ−ｋのパケット数をパケットカウンタメモリ４４から読み出して、現在の該当キュー＃ｊ−ｋのパケット数を識別し（ステップＳ３２）、その識別結果に応じて、スケジューラ５へのパラメータ出力と、キュー管理部４内部のポインタ制御（ポインタリンク構造の更新）とを次のようにして実行する。
【０１２８】
まず、識別したパケット数が５個以上の場合（ステップＳ３３でＹＥＳの場合）、キュー管理部４は、図３０に示す処理（１）（図３０中では、（１）〜（５）を丸付き数字で示す）を実行して、該当キュー＃ｊ−ｋの先頭ポインタをデキューポインタとしてメモリ制御部６へ出力するとともに、３番目のパケットについてのパラメータをスケジューラ５に送出し、ポインタリンク構造を更新する（ステップＳ３８）。
【０１２９】
そして、キュー管理部４は、この更新により、第４ポインタが最終ポインタと等しくなったか否かを確認し（ステップＳ４４）、等しければパケットカウンタメモリ４４の該当カウンタ値を固定値（４）に設定し（ステップＳ４４のＹＥＳルートからステップＳ４５）、等しくなければ次のデキュー指示の監視動作に入る（ステップＳ４４のＮＯルート）。
【０１３０】
さて次に、識別したパケット数が４個の場合（ステップＳ３３でＮＯ，ステップＳ３４でＹＥＳの場合）、キュー管理部４は、図３０に示す処理（２）を実行して、該当キュー＃ｊ−ｋの先頭ポインタをデキューポインタとしてメモリ制御部６へ出力するとともに第３パラメータメモリ４３上の３番目のパケットについてのパラメータをスケジューラ５に送出し、ポインタリンク構造を更新したのち（ステップＳ３９）、パケットカウンタ値をデクリメント（−１）する（ステップＳ４３）。
【０１３１】
同様に、識別したパケット数が３個の場合（ステップＳ３３及びＳ３４でそれぞれＮＯ，ステップＳ３５でＹＥＳの場合）、キュー管理部４は、図３０に示す処理（３）を実行して、該当キュー＃ｊ−ｋの先頭ポインタをデキューポインタとしてメモリ制御部６へ出力するとともに第３パラメータメモリ４３上の３番目のパケットについてのパラメータをスケジューラ５に送出し、ポインタリンク構造を更新しのたち（ステップＳ４０）、パケットカウンタ値をデクリメント（−１）する（ステップＳ４３）。
【０１３２】
これに対して、識別したパケット数が２個の場合（ステップＳ３３〜Ｓ３５でそれぞれＮＯ，ステップＳ３６でＹＥＳの場合）、キュー管理部４は、図３０に示す処理（４）を実行して、該当キュー＃ｊ−ｋの先頭ポインタをデキューポインタとしてメモリ制御部６へ出力するとともに先頭ポインタの更新を行ない（スケジューラ５へパラメータは送出しない）（ステップＳ４１）、パケットカウンタ値をデクリメント（−１）する（ステップＳ４３）。
【０１３３】
識別したパケット数が１個の場合（ステップＳ３３〜Ｓ３６でそれぞれＮＯ，ステップＳ３７でＹＥＳの場合）、キュー管理部４は、図３０に示す処理（５）を実行することにより、メモリ制御部６への先頭ポインタ（デキューポインタ）の出力のみを行ない（ステップＳ４２）、パケットカウンタ値をデクリメント（−１）する（ステップＳ４３）。
【０１３４】
つまり、キュー管理部４は、キュー＃ｊ−ｋのパケット数が３個以上である場合には、第３パラメータメモリ４３上のパラメータ（３番目のパケットについてのパラメータ）をスケジューラ５へ出力し、ポインタリンク構造の更新を行ない、パケット数が２個以下である場合には、先頭ポインタのメモリ制御部６への出力を行ない、スケジューラ５へのパラメータ出力は行なわないのである。
【０１３５】
なお、上記のエンキュー及びデキュー処理は、図３１に示すように、互いに相反する位相で動作することにより、お互いが競合しないよう制御されている。
以上のようなキュー管理（ポインタリンク構造の更新）により、同一キュー＃ｊ−ｋにおける連続する２個分のパケットについてのパラメータがスケジューラ５へ送出されて、先頭パケットメモリ５３に２個分のパケットについてのパラメータ（ただし、本実施形態では前処理部５１による前処理後のパラメータ）が保持されることになる。
【０１３６】
ここで、図３２に示すように、スケジューラ５の入力から先頭パケットメモリ５３への格納までのレイテンシをＡサイクル、スケジューラ５出力のデキュー指示による先頭パケットメモリ５３のデータ更新から更新データのスケジューラ５出力までの処理レイテンシをＢサイクル、スケジューラ５の出力のデキュー指示から次パケット出力までのキュー管理部４の処理レイテンシをＣサイクルとする。
【０１３７】
仮に、スケジューラ５が先頭パケットについてのパラメータのみを処理するのであれば、同一キュー＃ｊ−ｋ上の最短デキュー間隔は図３２に示すループ（１）（図３２中では、（１），（２）を丸付き数字で示す）の処理に依存し、(Ａ＋Ｂ＋Ｃ)サイクルとなる。しかし、上述したように先頭パケットメモリ５３にキュー＃ｊ−ｋの先頭２個分のパラメータを格納することにより、同一キュー＃ｊ−ｋ上の最短デキュー間隔は、図３２に示すループ（２）の処理レイテンシ（Ｂサイクル）にできる。ただし、最短のデキュー間隔をＢサイクルで行なうためには、Ｂ≧（Ａ＋Ｃ）である必要がある。Ｂ＜（Ａ＋Ｃ）であれば、デキューの更新間隔は（Ａ＋Ｃ）サイクルに依存するようになる。
【０１３８】
したがって、例えば図３３に示すように、或るキュー＃ｊ−ｋに５つのパケット“１”〜“５”の入力があり、それらがいずれも最短デキュー間隔で出力可能なパケット長の短いものであり、且つ、Ｂ≧（Ａ＋Ｃ）を満足する場合、デキュー発生によりキュー管理部４及び先頭パケットメモリ５３への次パケットの出力要求が同時に発生することになり、パケット“１”〜“５”は最短保証間隔であるＢサイクルで連続してパケットをデキューすることが可能となる。
【０１３９】
その結果、連続パケット出力のボトルネックとなっていた処理レイテンシが大幅に削減され、5Gbpsや10Gbps等の高速帯域をもつ回線＃ｊやキュー＃ｊ−ｋに対する帯域制御の精度を高めて、設定帯域の保証を行なうことができる。
なお、上記のデキュー発生時には、キュー管理部４へのデキューイネーブル信号のアサートとともに、同一パケットの重複出力をマスクするために、スケジューラ５内部におけるパイプライン処理上の同一パケットについてのパラメータ対するマスク処理が行なわれる。
【０１４０】
即ち、図２中に示すように、デキュー発生時には、デキュー情報（デキュー識別信号：FB1，FB2，FB3，FB4）が、それぞれ、演算制御部５２，並列演算部５５の各演算器５５−ｋの出力判定回路５５２，シェーピング部５７における各出力回線シェーピング回路５７−ｊの出力判定回路５７１−２，デキュー制御部５９の出力判定回路５９１−２へそれぞれフィードバックされる。
【０１４１】
そして、演算制御部５２では、上記デキュー情報（FB1）の受信により、デキューパケットの出力回線＃ｊを次サイクルの演算出力回線として指定し、上記デキュー情報（FB2）により識別される演算器５５−ｋの出力判定回路５５２では、出力判定フラグをディセーブルにして、同一出力回線＃ｊの同一キュー＃ｊ−ｋについての演算結果出力をマスクする。
【０１４２】
また、上記デキュー情報（FB3）により識別される出力回線シェーピング回路５７−ｊの出力判定回路５７１−２においても、出力判定フラグをディセーブルにして、判定値出力をマスクし、デキュー制御部５９の出力判定回路５９１−２においても、上記デキュー情報（FB4）の受信により、判定値出力をマスクして次サイクルの全出力をマスクする。
【０１４３】
以上のマスク処理により、同一パケットの重複出力防止と、それに伴うキュー＃ｊ−ｋの帯域制御精度の低下を防止することができる。
ここで、例えば図３４に示すように、或る回線Ａのキュー（演算器）番号ｎのキューについてのデキューイベントがサイクルｔで発生した場合を考える。この場合、デキュー情報（FB4）により次サイクルの全出力がマスクされ、デキューバスの出力は停止する。また、デキュー情報（FB3）により回線Ａのシェーピング部５７の出力に対してｔ＋２サイクルまでマスク処理が働く。この処理によりｔ＋２サイクル目からは、回線Ａ以外の回線のデキュー処理が行なえることになる。
【０１４４】
さらに、デキュー情報（FB2）により、演算器５５−ｋの出力に対してｔ＋３サイクルまでマスク処理が働く。ただし、このポイントでは、回線Ａ以外の回線についてのデータをマスクしないように、当該ポイントのデータの回線識別処理を行ない、回線Ａについてのデータのみをマスクする。この処理により、ｔ＋３サイクル目からは、演算器番号ｎ以外の回線Ａについてのデキュー出力が行なえることになる。また、デキュー情報（FB1）により、先頭パケットメモリ５３から次パケットデータの更新を行なうため演算回線がＡに指定される。
【０１４５】
以上のようにして、全パイプライン処理上のデキューパケットによる更新処理が行われる。このように複数ポイントでデータのマスク処理を行なうことにより、他回線についてのパケットは最低２サイクル、同一回線内のパケットについては最低４サイクル間隔でのデキュー処理が可能になる。また、同一キューについても、本実施形態では、先頭パケットメモリ５３に先頭パケットについてのパラメータを常に２個をもたせているので、８サイクル間隔でのデキュー処理が可能になる。
【０１４６】
以上のように、上述した実施形態におけるパケット出力制御装置１によれば、ＷＦＱの評価値演算対象の回線＃ｊを時分割に指定し、指定された回線＃ｊに属する各キュー＃ｊ−ｋの先頭パケットについての評価値並列演算を各回線＃ｊに共通の演算器５５−ｋで実行するように構成したので、スケジューラ５の回路規模をキュー本数に対して大幅に削減することができる。
【０１４７】
したがって、従来困難であった多数キューについてのＷＦＱスケジューリング演算をハードウェア化することができて、その演算能力を大幅に向上することができ、精度の高いＷＦＱスケジューリングが実現可能である。
特に、上述した実施形態では、前処理部５１やγ演算部５４等の演算回路の共通化を図っているので、多数のキューをもつスケジューラについても、ＬＳＩやＦＰＧＡでの実装が可能になる。また、このような演算器共有構成を活かして、ＷＦＱをベースにした固定帯域キューや優先制御キューによるＱｏＳ制御を容易に実現することもできる。
【０１４８】
さらに、シェーピング部５７での出力回線＃ｊ毎のシェーピング処理により、キュー単位で発生する出力帯域の取り戻しの総和による出力回線＃ｊの輻輳を回避することができ、また、デキュー制御部５９でのデキューバスについてのシェーピング処理により、キュー＃ｊ−ｋ単位又は出力回線＃ｊ単位に発生する出力帯域の取り戻しの総和によるデキューバスの輻輳を回避することができる。
【０１４９】
また、演算回線の指定やパケットデキュー時の複数ポイントでのフィードバック処理（マスク処理）により、各キュー＃ｊ−ｋ及び各回線＃ｊにおける高いスループットも実現できる。
（Ａ２）第１変形例の説明
次に、以下では、パケットスケジューラ５の第１変形例について説明する。
【０１５０】
図３７は上述したパケットスケジューラ５の第１変形例を示すブロック図で、この図３７に示すパケットスケジューラ５は、図４に示す構成に比して、１タイムスロット当たりの演算対象であるｎ本のキュー＃ｊ−１〜＃ｊ−ｎに帯域制御の優先度を与えてキュー＃ｊ−１〜＃ｊ−ｎ間で帯域の優先制御を行なう場合に、それらのキュー（以下、優先制御キューという）＃ｊ−１〜＃ｊ−ｎに対応する各演算器５５−ｋについて、優先制御回路５５ａ−１〜５５ａ−ｎが設けられている点が異なる。なお、以下において、既述の符号と同一符号を付したものは、特に断らない限り、それぞれ既述のものと同一もしくは同様のものを示す。
【０１５１】
そして、これらの優先制御回路（優先制御手段）５５ａ−ｋは、例えば図３９に示すように、それぞれ、先頭パケットメモリ５３（５３−１〜５３−ｎ）のパケット有無状態を判定するパケット有無判定回路５５１ａをそなえており、その出力（自キュー＃ｊ−ｋのパケット有無状態）が優先度の高いものから順に、論理和（ＯＲ）回路５５１ｂを介して、優先度の低い優先制御回路にカスケードに接続されている。
【０１５２】
また、最も優先度の高い優先制御回路５５ａ−１を除く優先制御回路５５ａ−２〜５５ａ−ｎには、それぞれ、上位の優先制御回路におけるパケット有無判定回路５５１ａの反転出力と、自優先制御回路５５ａ−２〜５５ａ−ｎにおけるパケット有無判定回路５５１ａの出力との論理積（ＡＮＤ）をとる１入力反転型の論理積（ＡＮＤ）回路５５１ｃが設けられている。なお、各優先制御回路５５ａ−ｋの出力はデータ有効フラグとして対応する演算器５５−ｋの出力判定回路５５２に接続されている。
【０１５３】
つまり、本変形例のスケジューラ５は、優先制御回路５５ａ−１〜５５ａ−ｋによって、出力回線＃ｊ別に上位キューの状態と自キューのパケット有無状態を監視し、優先度の高いキューにパケットが存在していることがパケット有無判定回路５５１ａで検出されている場合には、それよりも優先度の低いキューにパケットが存在していたとしても、対応する演算器５５−ｋにデータ有効フラグを出力しない（ディゼーブルする）ことにより、そのキューについての演算器５５−ｋの演算結果（評価値）をマスクするのである。
【０１５４】
これにより、例えば図３８（Ａ）に示すように、パケットがａ→ｂ→ｃ→ｄ→ｅ→・・・・の順にエンキューされ、それらを２段階の優先度をもって出力制御を行なう場合、図３８（Ｂ）に示すように、各入力パケットを高優先制御キューと低優先制御キューとにそれぞれ振り分け〔この図３８（Ｂ）では、パケットａ，ｄ，ｅが高優先側、残りのパケットｃ，ｂが低優先側に振り分けられている〕、高優先側から低優先側にパケット有無状態を伝達し、高優先側のパケットの出力完了によって高優先側のパケットが無い状態の時にのみ、低優先側の出力が許可されることになる。その結果、上記の各入力パケットａ，ｂ，ｃ，ｄ，ｅは、図３８（Ａ）に示すように、パケットａ→ｄ→ｅ→ｂ→ｃの順に出力されることになる。
【０１５５】
したがって、例えば、画像や音声データ等のリアルタイム性の高いキューのデータを優先的に出力させるようにすることが可能となる。なお、この構成において、前評価値メモリ６１において複数優先制御キュー＃ｊ間で前評価値（パケット出力完了予定時刻）Fi-1 を共有することにより、複数優先制御キュー＃ｊを単一のキューとして帯域制御することができる。
【０１５６】
例えば図４０に示すように、２つのキューａ，ｂ間で帯域共有を行なう場合を考える。この場合、２つのキュー間には共通の設定帯域φが設定されており、優先度はキューａ＞キューｂと仮定する。これにより、下位のキューｂは、上位のキューａにパケットが存在する時には、上述したように出力がマスクされ、上位キューａのパケットの出力完了と上位キューａのパケット無しとの条件により出力が許可される。したがって、下位のキューｂにエンキューされたパケットは、上位のキューａについての空き帯域を使って出力されるようになる。
【０１５７】
なお、上述した優先制御キューは、勿論、全てのキューではなく一部のキューで構成してもよい。
（Ａ３）第２変形例の説明
上述したように、出力回線＃ｊ間で演算器５５−ｋを共用する構造により、複数回線＃ｊに対して同一処理経路をもつため、スケジューラ５は、複数出力回線＃ｊへの同一パケットのコピー処理（マルチキャスト配信）を容易に行なうことができる。
【０１５８】
図４１はこのようなマルチキャスト配信を実現するパケットスケジューラ５の構成（第２変形例）を示すブロック図で、この図４１に示すスケジューラ５は、図４に示す構成に比して、一部あるいは全ての演算器５５−ｋについて、ビットマップ制御部６２とマルチキャスト先頭パケットメモリ６３とがそなえられている点が異なる。なお、以下において、既述の符号と同一符号を付したものは、特に断らない限り、既述のものと同一もしくは同様のものを示す。
【０１５９】
ここで、ビットマップ制御回路６２は、演算制御部５２からの演算タイムスロット指定に応じて、マルチキャスト先頭パケットメモリ６３に格納されているマルチキャストパケットについてのスケジュールパラメータ出力の有効／無効を制御するもので、例えば図４１及び図４２に示すように、ビットマップ（Bitmap）レジスタ６２１，ビットマップ制御回路６２２，データ有効判定回路６２３及び最終パケット判定回路６２４をそなえて構成されている。
【０１６０】
ビットマップレジスタ（配信先情報保持手段）６２１は、どの出力回線＃ｊについてマルチキャスト配信を行なうかを指定する配信先回線ビットマップ情報〔例えば図４４（Ａ）に示すように、マルチキャスト配信を行なう場合は“１”、そうでない場合は“０”が設定される〕を保持するものである。なお、上記の配信先回線ビットマップ情報は、例えば図１に示す変換テーブル３からのスケジュールパラメータとともに受信される。
【０１６１】
ビットマップ制御回路（配信制御手段）６２２は、デキュー制御部５９からフィードバックされてくるデキュー情報に基づいて、上記ビットマップレジスタ６２１に格納された配信先回線ビットマップ情報（以下、単に「ビットマップ情報」という）の更新／クリアを制御するものであり、データ有効判定回路６２３は、演算制御部５２から演算ポート指定される毎に、マルチキャスト先頭パケットメモリ６３から読み出されるマルチキャスト配信用の先頭パケットについてのスケジュールパラメータが有効であることを示すフラグを演算器５５−ｋの出力判定回路５５２に出力するものである。
【０１６２】
最終パケット判定回路６２４は、現在のマルチキャスト配信対象の回線＃ｊが最終回線であるか否かを監視するもので、最終回線＃ｊであれば、ビットマップ制御回路６２２が、その旨（最終パケットフラグのイネーブル）を受けて、最終回線＃ｊに対するマルチキャストパケットのデキューによりビットマップレジスタ６２１の内容を次のマルチキャストパケットについてのビットマップ情報に更新するようになっている。
【０１６３】
以上の構成により、本第２変形例のスケジューラ５では、マルチキャストパケットについてのスケジュールパラメータがマルチキャスト先頭パケットメモリ６３に格納されるとともに、ビットマップ情報がビットマップ制御部６２のビットマップレジスタ６２１に格納される。
そして、前述した実施形態及び第１変形例のユニキャストキューにおいては、先頭パケットの有無判定により、演算器５５−ｋに入力されるパラメータの有効判定が行なわれるが、本第２変形例では、それに加えてビットマップ制御によるデータの有効判定がデータ有効判定回路６２３によって行なわれる。
【０１６４】
即ち、データ有効判定回路６２３は、ビットマップがアサート（“１”に設定）されている回線＃ｊに演算タイムスロットが演算制御部５２から指定された時に、演算器５５−ｋ出力の有効フラグをイネーブルにする〔例えば図４４（Ｂ）参照〕。
そして、図４３に示すように、マルチキャストパケットがデキューされた回線＃ｊ順に、ビットマップレジスタ６２１のビットマップ情報がビットマップ制御回路６２２によってクリアされてゆき、ビットマップ情報で指定された最後の回線＃ｊへのマルチキャストパケットがデキューされた時点で、最終パケット判定回路６２４からビットマップ制御回路６２２への最終パケットフラグ（イネーブル）が出力され、これにより、次のマルチキャストパケットについてのビットマップにビットマップレジスタ６２１の内容が更新される。
【０１６５】
このように、本第２変形例のスケジューラ５では、出力回線＃ｊ間で演算器５５−ｋが共用され、複数回線＃ｊに対して同一処理経路をもつことを利用して、複数出力回線の配信先情報をもったパケットをその配信先情報で指定された出力回線＃ｊの演算タイムスロット指定時に、そのパケットについての演算器５５−ｋによる演算結果を有効にするという簡単な制御で、指定された複数出力回線＃ｊへのパケット配信（マルチキャスト）を実現することができる。
【０１６６】
（Ｂ）付記
（付記１） 複数の出力回線毎に設けられた複数のキューと、
入力されたパケットを当該パケットのフローに応じて該キューのいずれかにエンキューするエンキュー手段と、
該エンキュー手段により上記の各キューにエンキューされた各パケットについてのデキュー指示をスケジュールするパケットスケジューラと、
該パケットスケジューラからのデキュー指示によって指示されたキューからパケットをデキューするデキュー手段とをそなえるとともに、
該パケットスケジューラが、
同一出力回線に属する各キューにエンキューされた先頭パケットに関する少なくとも到着時刻情報及びパケットサイズ情報を含む所定のパラメータに基づいて当該先頭パケットの送信完了予定時刻を示す評価値をそれぞれ所定の評価値演算式により並列演算する並列演算手段と、
該並列演算手段での演算対象とする出力回線を選択的に指定して同一出力回線に属する各キューの先頭パケットについてのパラメータを該並列演算手段に入力させる演算制御手段と、
該並列演算手段で求められた同一出力回線に属する各キューの先頭パケットの評価値に基づいて優先出力すべき先頭パケットの評価値を選出する同一出力回線内キュー間調停手段と、
該同一出力回線内キュー間調停手段で選出された評価値を該出力回線毎に保持し、該出力回線毎の評価値と該出力回線の設定帯域とに基づいて優先出力すべき先頭パケットを決定する出力回線間調停手段と、
該出力回線間調停手段で決定した先頭パケットについてのデキュー指示を該デキュー手段に与えるデキュー制御手段とをそなえたことを特徴とする、パケット出力制御装置。
【０１６７】
（付記２） 該演算制御手段が、上記の各出力回線の設定帯域に応じた割合で時分割に該並列演算手段での演算対象とする出力回線を指定する時分割演算回線指定部をそなえて構成されたことを特徴とする、付記１記載のパケット出力制御装置。
（付記３） 該パケットスケジューラが、
入力パケットの該パラメータに基づいて該評価値演算式中で繰り返し演算が不要な項を予め全キューで共通化された前処理として演算し、当該演算結果を該並列演算手段での演算に用いられる中間変数として該並列演算手段に入力する前処理部をそなえたことを特徴とする、付記１又は付記２に記載のパケット出力制御装置。
【０１６８】
（付記４） 該パケットスケジューラが、
同一出力回線に属する各キューうちパケットの存在しないキューに割り当てられている帯域を、パケットの存在する同一出力回線に属する他のキューに配分する帯域配分率を算出する帯域配分率算出手段をさらにそなえ、
該並列演算手段が、
該帯域配分率算出手段で算出された同じ帯域配分率に基づいて、上記の各評価値を再計算するように構成されたことを特徴とする、付記１〜３のいずれか１項に記載のパケット出力制御装置。
【０１６９】
（付記５） 該パケットスケジューラが、
該出力回線毎に、予め決められた固定帯域配分率を出力する固定帯域制御手段をさらにそなえ、
該並列演算手段が、
該固定帯域制御手段からの該固定帯域配分率に基づいて、上記の各評価値を計算するように構成されたことを特徴とする、付記１〜３のいずれか１項に記載のパケット出力制御装置。
【０１７０】
（付記６） 該パケットスケジューラが、
同一出力回線に属する各キューうちパケットの存在しないキューに割り当てられている帯域を、パケットの存在する同一出力回線に属する他のキューに配分する帯域配分率を算出する帯域配分率算出手段と、
該出力回線毎に、予め決められた固定帯域配分率を出力する固定帯域制御手段とをそなえるとともに、
該並列演算手段が、
同一出力回線に属するキュー毎に、該帯域配分率算出手段からの該帯域配分率と該固定帯域制御手段からの該固定帯域配分率のいずれか一方を選択する帯域配分率選択手段をそなえ、
該帯域配分率選択手段で選択された帯域配分率に基づいて該評価値を計算するように構成されたことを特徴とする、付記１〜３のいずれか１項に記載のパケット出力制御装置。
【０１７１】
（付記７） 該パケットスケジューラが、
同一出力回線に属する複数のキューに対して優先順位を与え、優先順位の高いキューにパケットが存在する場合に、当該キューよりも優先順位の低いキューについて該並列演算手段で求められる該評価値をマスク制御する優先制御手段をさらにそなえたことを特徴とする、付記１〜６のいずれか１項に記載のパケット出力制御装置。
【０１７２】
（付記８） 該パケットスケジューラが、
該優先順位の与えられた複数のキュー（以下、優先制御キューという）について該並列演算手段での前回の演算で求められた評価値を該優先制御キュー間で共通に保持する前評価値メモリをさらにそなえ、
該並列演算手段が、
該前評価値メモリに保持された評価値に基づいて新たな評価値の演算を行なうことにより、該複数の優先制御キューを単一のキューとみなして帯域制御を行なうように構成されたことを特徴とする、付記７記載のパケット出力制御装置。
【０１７３】
（付記９） 該パケットスケジューラが、
該複数の出力回線のうち同一パケットを配信すべき複数の出力回線を指定する配信先情報を保持する配信先情報保持手段と、
該配信先情報保持手段に保持された配信先情報によって指定されている出力回線が該演算制御手段によって指定される毎に、該並列演算手段で求められる同一キューについての該評価値を有効に制御する配信制御手段とをそなえたことを特徴とする、付記１記載のパケット出力制御装置。
【０１７４】
（付記１０） 該出力回線間調停手段が、
該出力回線毎に該同一出力回線内キュー間調停手段で選択された評価値を保持するレジスタと、
該評価値と該出力回線毎に予め設定された帯域情報とに基づいて、該出力回線の設定帯域を考慮した該評価値の出力制御を行なうことにより、該出力回線の帯域制御を行なう出力回線シェーピング制御部とをそなえたことを特徴とする、付記１記載のパケット出力制御装置。
【０１７５】
（付記１１） 該出力回線シェーピング制御部が、
該帯域制御において他の出力回線に属するキューの先頭パケットについての評価値との競合により出力が待たされた分の評価値出力を制御してパケットのバースト出力を制御する出力回線バースト制御部を有することを特徴とする、付記１０記載のパケット出力制御装置。
【０１７６】
（付記１２） 該パケットスケジューラが、
同一出力回線に属する各キューの先頭パケットを含む複数の連続するパケットについてのパラメータを保持する複数先頭パケットメモリをそなえ、
該演算制御手段が、
該先頭パケットについてのデキュー指示を契機に当該先頭パケットに続く次パケットについてのパラメータを該先頭パケットメモリから読み出して該並列演算手段に入力させるように構成されたことを特徴とする、付記１記載のパケット出力制御装置。
【０１７７】
（付記１３） 該時分割演算回線指定部が、
上記の各出力回線の設定帯域の比率に応じて所定周期内で時分割指定する同一出力回線の割合を設定するように構成されたことを特徴とする、付記２記載のパケット出力制御装置。
（付記１４） 該デキュー制御手段が、
該出力回線毎に該同一出力回線内キュー間調停手段で選択された評価値を保持するレジスタと、
該評価値とデキューバスに予め設定された帯域情報とに基づいて、該デキューバスの設定帯域に応じた該評価値の出力制御を行なうことにより、該出力回線の帯域制御を行なうデキューバスシェーピング制御部とをそなえたことを特徴とする、付記１又は付記１０に記載のパケット出力制御装置。
【０１７８】
（付記１５） 該デキューバスシェーピング制御部が、
該帯域制御において出力が待たされた分の評価値出力を制御してパケットのバースト出力を制御するデキューバスバースト制御部を有することを特徴とする、付記１４記載のパケット出力制御装置。
（付記１６） 該デキュー制御手段が、
該デキュー指示を契機に、上記の演算制御手段，並列演算手段及び出力回線間調停手段に対して、同一先頭パケットについての評価値をマスクするための制御信号を与えるマスク信号出力部をそなえたことを特徴とする、付記１記載のパケット出力制御装置。
【０１７９】
【発明の効果】
以上詳述したように、本発明のパケットスケジュール出力制御装置によれば、次のような効果ないし利点が得られる。
(1)評価値演算対象の出力回線を選択的に指定し、指定された出力回線に属する各キューの先頭パケットについての評価値を並列演算するので、パケットスケジューラの回路規模をキュー本数に対して大幅に削減することができる。したがって、従来困難であった多数キューについての評価値演算をハードウェア化することができて、その演算能力を大幅に向上することができ、精度の高いＷＦＱスケジューリングが実現可能である。
【０１８０】
(2)また、評価値演算式中の繰り返し演算が不要な項を前処理部により予め全キューで共通化された前処理として演算したり、キューのパケット有無の変化に伴って再計算される同じ帯域配分率に基づいて評価値の再計算を行なったりして、演算回路の共通化を図ることにより多数のキューをもつスケジューラについても、例えば、ＬＳＩやＦＰＧＡでの実装が可能になる。
【０１８１】
(3)さらに、このような並列演算構成を活かして、ＷＦＱをベースにした固定帯域キューや優先制御キューによるＱｏＳ制御，マルチキャスト配信等の制御を容易に実現することもできる。
(4)さらに、シェーピング部での出力回線毎のシェーピング処理（バースト制御）により、キュー単位で発生する出力帯域の取り戻しの総和による出力回線の輻輳を回避することができ、また、デキュー制御部でのデキューバスについてのシェーピング処理（バースト制御）により、キュー単位又は出力回線単位に発生する出力帯域の取り戻しの総和によるデキューバスの輻輳を回避することができる。
【０１８２】
(5)また、演算制御手段による演算回線の指定やパケットデキュー時の複数ポイントでのフィードバック処理（マスク処理）により、重複パケット出力を防止することができ、また、各キュー及び各出力回線の帯域制御精度の低下を防止して高いスループットも実現できる。
(6)演算制御手段が、各出力回線の設定帯域に応じた割合で時分割に上記並列演算対象とする出力回線を指定することにより、上述のごとく出力回線間で並列演算を共通化することによる演算精度の低下を防止することができる。
【０１８３】
(7)さらに、上記の評価値演算に際して、出力回線別に帯域再配分を行なうか否かを設定するようにすることもできるので、出力回線毎に固定帯域キューとＷＦＱによるキューとの構成比を任意に設定することができ、自由度の高いパケットスケジューラ５を提供することができる。
(8)また、同一出力回線に属する各キューの先頭パケットを含む複数の連続するパケットについてのパラメータを保持しておき、上記先頭パケットについてのデキュー指示を契機にその先頭パケットに続く次パケットについてのパラメータを先頭パケットメモリから読み出して並列演算手段に入力させることで、同一キューの連続パケットについてのパラメータ更新の処理レイテンシを短縮することができるので、高速出力回線に対する帯域制御の精度を向上して、設定帯域の保証を行なうことができる。
【０１８４】
(9)デキュー指示を契機に、同一先頭パケットについての評価値をマスクするので、同一パケットが重複出力されることを防止することができ、キューの帯域制御精度の低下を防止することができる
【図面の簡単な説明】
【図１】本発明の一実施形態としてのパケット出力制御装置の全体構成を示すブロック図である。
【図２】図１に示すパケットスケジューラの構成を示すブロック図である。
【図３】図１に示すパケットスケジューラの構成を示すブロック図である。
【図４】図２及び図３に示すスケジューリング評価値演算器の構成に着目したパケットスケジューラの要部構成を示すブロック図である。
【図５】図２及び図３に示す演算制御部で用いられる演算回線テーブルの一例を示す図である。
【図６】図２及び図３に示す演算制御部での演算回線決定動作を説明するための状態遷移図である。
【図７】図２及び図３に示すパケットスケジューラによる演算回線指定と回線スループットを説明するためのタイムチャートである。
【図８】図２及び図３に示す前処理部及び先頭パケットメモリの構成を示すブロック図である。
【図９】図２及び図３に示すγ演算部の構成を示すブロック図である。
【図１０】図９に示すφ加減算器の構成を示すブロック図である。
【図１１】図１０に示すφ累積器の構成を示すブロック図である。
【図１２】図９に示すγ演算部でのφ加減算処理を説明するためのフローチャートである。
【図１３】図２及び図３に示す選択部によるキュー間出力調停動作を説明するための図である。
【図１４】図２及び図３に示すシェーピング部における出力回線シェーピング回路の構成を示すブロック図である。
【図１５】図１４に示すシェーピング制御の構成を示すブロック図である。
【図１６】図１５に示す出力判定値演算回路の構成を示すブロック図である。
【図１７】図１４に示す出力回線シェーピング回路による回線シェーピング処理概念を説明するための図である。
【図１８】図１４に示す出力回線シェーピング回路による回線シェーピング処理及びバースト制御概念を説明するための図である。
【図１９】図２及び図３に示すポート間調停部による出力回線間調停動作を説明するための図である。
【図２０】（Ａ）及び（Ｂ）は図２及び図３に示すポート間調停部を実現するソフトウェアアルゴリズムの一例を示す図である。
【図２１】図２に示すデキュー制御部の構成を示すブロック図である。
【図２２】図２１に示すシェーピング制御部の構成を示すブロック図である。
【図２３】図２１及び図２２に示すデキュー制御部によるデキューバス・シェーピング処理概念を説明するための図である。
【図２４】図２１及び図２２に示すデキュー制御部によるデキューバス・バースト制御概念を説明するための図である。
【図２５】図１に示すキュー管理部のメモリ構成を示すブロック図である。
【図２６】図２５に示すキュー管理部のメモリ構成におけるポインタリンク構造例を示す図である。
【図２７】図１に示すキュー管理部のエンキュー処理時の動作を説明するためのフローチャートである。
【図２８】図２７に示す各処理の詳細を示す図である。
【図２９】図１に示すキュー管理部のデキュー処理時の動作を説明するためのフローチャートである。
【図３０】図２９に示す各処理の詳細を示す図である。
【図３１】図１に示すキュー管理部でのエンキュー／デキュー処理位相を説明するための図である。
【図３２】図１に示すキュー管理部及びパケットスケジューラ間での処理レイテンシを説明するための図である。
【図３３】図３２に示すキュー管理部及びパケットスケジューラによる処理レイテンシとデキュースループットを説明するための図である。
【図３４】図２及び図３に示すデキュー制御部によるデキュー情報のフィードバックによるマスク処理を説明するための図である。
【図３５】図４に示すスケジューリング評価値演算器におけるセレクタに対するＷＦＱ／固定帯域切り替え設定情報を保持するレジスタの構成を示すブロック図である。
【図３６】図２及び図３に示す演算制御部によるＷＦＱ／固定帯域切り替え制御を説明するためのタイムチャートである。
【図３７】図４に示すパケットスケジューラの第１変形例を示すブロック図である。
【図３８】（Ａ）及び（Ｂ）は優先制御キューによるパケット出力動作を説明するための図である。
【図３９】図３７に示す優先制御回路の構成を示すブロック図である。
【図４０】図３７及び図３９に示す優先制御回路による優先制御キューにおける評価値の共有を説明するための図である。
【図４１】図４に示すパケットスケジューラの第２変形例を示すブロック図である。
【図４２】図４１に示すビットマップ制御部の構成を示すブロック図である。
【図４３】 図４１及び図４２に示すビットマップ制御部によるマルチキャスト配信制御を説明するためのタイムチャートである。
【図４４】 （Ａ）及び（Ｂ）は図４１及び図４２に示すビットマップ制御部によるマルチキャスト配信制御を説明するための図である。
【図４５】ＱｏＳ制御の仕組みを説明するための図である。
【図４６】ＷＦＱによる帯域制御概念を説明するための図である。
【図４７】ＷＦＱによる帯域制御概念を説明するための図である。
【符号の説明】
１ パケット出力制御装置
２ フレームメモリ
３ 変換テーブル
４ キュー管理部
４１ パラメータメモリ
４２ 次ポインタメモリ
４３ 第３パラメータメモリ
４４ パケットカウンタメモリ
４５ ポインタテーブル
４５１ 先頭ポインタメモリ
４５２ 第４ポインタメモリ
４５３ 最終ポインタメモリ
５ パケットスケジューラ
６ メモリ制御部
７ タイムスタンプ部
５１ 前処理部
５２ 演算制御部（時分割演算回線指定部）
５２１ 演算出力回線テーブル
５３，５３−１〜５３−ｎ 先頭パケットメモリ
５４ γ演算部（帯域配分率算出手段）
５４１ γ演算制御部
５４２ φ設定テーブル
５４３ φ加減算器
５４３−１〜５４３〜Ｍ φ累積器
５４３１ 加減算器
５４３２ レジスタ
５４４，５４６ セレクタ
５４５ Ｒ設定テーブル
５４７ 除算器
５５ 並列演算部
５５−１〜５５−ｎ スケジューリング評価値演算器
５５１ α選択回路
５５２ 出力判定回路
５５３ セレクタ（帯域配分率選択手段）
５５４ 乗算器
５５５ 加算器
５５６ 設定レジスタ
５５ａ−１〜５５ａ−ｎ 優先制御回路
５５１ａ パケット有無判定回路
５５１ｂ 論理和（ＯＲ）回路
５５１ｃ １入力反転型の論積（ＡＮＤ）回路
５６ 選択部（同一出力回線内キュー間調停手段）
５７ シェーピング部
５７−１〜５７−Ｍ 出力回線シェーピング回路
５７１ シェーピング制御部（出力回線シェーピング制御部）
５７１−１ 出力判定値演算回路
５７１−２ 出力判定回路
５７１−３ バースト制御部（出力回線バースト制御部）
５７１１ セレクタ
５７１２ 除算器
５７１３ 加算器
５７１４ レジスタ（Ｒ）
５７２ パケット情報レジスタ
５７−１〜５７−Ｍ 出力回線シェーピング回路
５８ ポート間調停部（出力回線間調停手段）
５９ デキュー制御部
５９１ シェーピング制御部（デキューバスシェーピング制御部）
５９１−１ 出力判定値演算回路
５９１−２ 出力判定回路
５９１−３ バースト制御部（デキューバスバースト制御部）
５９２ パケット情報レジスタ
６０ タイマ
６１ 前評価値メモリ
６２ ビットマップ制御部
６２１ ビットマップレジスタ
６２２ ビットマップ制御回路
６２３ データ有効判定回路
６２４ 最終パケット判定回路
６３ マルチキャスト先頭パケットメモリ
Claims (6)
- 複数の出力回線毎に設けられた複数のキューと、
入力されたパケットを当該パケットのフローに応じて該キューのいずれかにエンキューするエンキュー手段と、
該エンキュー手段により上記の各キューにエンキューされた各パケットについてのデキュー指示をスケジュールするパケットスケジューラと、
該パケットスケジューラからのデキュー指示によって指示されたキューからパケットをデキューするデキュー手段とをそなえるとともに、
該パケットスケジューラが、
同一出力回線に属する各キューにエンキューされた先頭パケットに関する少なくとも到着時刻情報及びパケットサイズ情報を含む所定のパラメータに基づいて当該先頭パケットの送信完了予定時刻を示す評価値をそれぞれ所定の評価値演算式により並列演算する並列演算手段と、
該並列演算手段での演算対象とする出力回線を時分割に指定して同一出力回線に属する各キューの先頭パケットについてのパラメータを該並列演算手段に入力させる演算制御手段と、
該並列演算手段で求められた同一出力回線に属する各キューの先頭パケットの評価値に基づいて優先出力すべき先頭パケットの評価値を選出する同一出力回線内キュー間調停手段と、
該同一出力回線内キュー間調停手段で選出された評価値を該出力回線毎に保持し、該出力回線毎の評価値と該出力回線の設定帯域とに基づいて優先出力すべき先頭パケットを決定する出力回線間調停手段と、
該出力回線間調停手段で決定した先頭パケットについてのデキュー指示を該デキュー手段に与えるデキュー制御手段とをそなえたことを特徴とする、パケット出力制御装置。 - 該演算制御手段が、上記の各出力回線の設定帯域に応じた割合で時分割に該並列演算手段での演算対象とする出力回線を指定する時分割演算回線指定部をそなえて構成されたことを特徴とする、請求項１記載のパケット出力制御装置。
- 複数の出力回線毎に設けられた複数のキューと、
入力されたパケットを当該パケットのフローに応じて該キューのいずれかにエンキューするエンキュー手段と、
該エンキュー手段により上記の各キューにエンキューされた各パケットについてのデキュー指示をスケジュールするパケットスケジューラと、
該パケットスケジューラからのデキュー指示によって指示されたキューからパケットをデキューするデキュー手段とをそなえるとともに、
該パケットスケジューラが、
同一出力回線に属する各キューにエンキューされた先頭パケットに関する少なくとも到着時刻情報及びパケットサイズ情報を含む所定のパラメータに基づいて当該先頭パケットの送信完了予定時刻を示す評価値をそれぞれ所定の評価値演算式により並列演算する並列演算手段と、
該並列演算手段での演算対象とする出力回線を選択的に指定して同一出力回線に属する各キューの先頭パケットについてのパラメータを該並列演算手段に入力させる演算制御手段と、
該並列演算手段で求められた同一出力回線に属する各キューの先頭パケットの評価値に基づいて優先出力すべき先頭パケットの評価値を選出する同一出力回線内キュー間調停手段と、
該同一出力回線内キュー間調停手段で選出された評価値を該出力回線毎に保持し、該出力回線毎の評価値と該出力回線の設定帯域とに基づいて優先出力すべき先頭パケットを決定する出力回線間調停手段と、
該出力回線間調停手段で決定した先頭パケットについてのデキュー指示を該デキュー手段に与えるデキュー制御手段とをそなえ、
該演算制御手段が、
上記の各出力回線の設定帯域に応じた割合で時分割に該並列演算手段での演算対象とする出力回線を指定する時分割演算回線指定部をそなえて構成されたことを特徴とする、パケット出力制御装置。 - 該パケットスケジューラが、
入力パケットの該パラメータに基づいて該評価値演算式中で繰り返し演算が不要な項を予め全キューで共通化された前処理として演算し、当該演算結果を該並列演算手段での演算に用いられる中間変数として該並列演算手段に入力する前処理部をそなえたことを特徴とする、請求項１〜３のいずれか１項に記載のパケット出力制御装置。 - 該パケットスケジューラが、
同一出力回線に属する各キューうちパケットの存在しないキューに割り当てられている帯域を、パケットの存在する同一出力回線に属する他のキューに配分する帯域配分率を算出する帯域配分率算出手段をさらにそなえ、
該並列演算手段が、
該帯域配分率算出手段で算出された同じ帯域配分率に基づいて、上記の各評価値を再計算するように構成されたことを特徴とする、請求項１〜４のいずれか１項に記載のパケット出力制御装置。 - 該パケットスケジューラが、
該複数の出力回線のうち同一パケットを配信すべき複数の出力回線を指定する配信先情報を保持する配信先情報保持手段と、
該配信先情報保持手段に保持された配信先情報によって指定されている出力回線が該演算制御手段によって指定される毎に、該並列演算手段で求められる同一キューについての該評価値が、該出力回線間調停手段での選定候補として当該出力回線間調停手段に入力されるように出力制御する配信制御手段とをそなえたことを特徴とする、請求項１又は３に記載のパケット出力制御装置。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002129149A JP3872716B2 (ja) | 2002-04-30 | 2002-04-30 | パケット出力制御装置 |
| US10/281,366 US7190674B2 (en) | 2002-04-30 | 2002-10-25 | Apparatus for controlling packet output |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002129149A JP3872716B2 (ja) | 2002-04-30 | 2002-04-30 | パケット出力制御装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2003324471A JP2003324471A (ja) | 2003-11-14 |
| JP3872716B2 true JP3872716B2 (ja) | 2007-01-24 |
Family
ID=29243923
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2002129149A Expired - Fee Related JP3872716B2 (ja) | 2002-04-30 | 2002-04-30 | パケット出力制御装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US7190674B2 (ja) |
| JP (1) | JP3872716B2 (ja) |
Families Citing this family (40)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7181701B2 (en) * | 2003-01-03 | 2007-02-20 | Microsoft Corporation | Glanceable information system and method |
| US7792121B2 (en) * | 2003-01-03 | 2010-09-07 | Microsoft Corporation | Frame protocol and scheduling system |
| JPWO2004066570A1 (ja) * | 2003-01-17 | 2006-05-18 | 富士通株式会社 | ネットワークスイッチ装置およびネットワークスイッチ方法 |
| US7369491B1 (en) * | 2003-05-14 | 2008-05-06 | Nortel Networks Limited | Regulating data-burst transfer |
| US7751312B2 (en) * | 2003-06-13 | 2010-07-06 | International Business Machines Corporation | System and method for packet switch cards re-synchronization |
| US7391777B2 (en) * | 2003-11-03 | 2008-06-24 | Alcatel Lucent | Distance-sensitive scheduling of TDM-over-packet traffic in VPLS |
| US7876763B2 (en) * | 2004-08-05 | 2011-01-25 | Cisco Technology, Inc. | Pipeline scheduler including a hierarchy of schedulers and multiple scheduling lanes |
| US7593755B2 (en) | 2004-09-15 | 2009-09-22 | Microsoft Corporation | Display of wireless data |
| US7643493B1 (en) * | 2004-09-29 | 2010-01-05 | Altera Corporation | Method and apparatus for priority-provisioned arbitration scheduling for a switch fabric |
| US7545815B2 (en) * | 2004-10-18 | 2009-06-09 | At&T Intellectual Property Ii, L.P. | Queueing technique for multiple sources and multiple priorities |
| JP4483535B2 (ja) * | 2004-11-05 | 2010-06-16 | 株式会社日立製作所 | ネットワーク装置 |
| US8289972B2 (en) * | 2004-11-10 | 2012-10-16 | Alcatel Lucent | Gigabit passive optical network strict priority weighted round robin scheduling mechanism |
| US7606249B1 (en) * | 2004-12-21 | 2009-10-20 | Extreme Networks, Inc. | Methods and systems for caching packets to be written to or read from packet memory |
| US7489690B2 (en) * | 2005-08-12 | 2009-02-10 | Cellco Partnership | Integrated packet latency aware QoS scheduling algorithm using proportional fairness and weighted fair queuing for wireless integrated multimedia packet services |
| JP4833685B2 (ja) * | 2006-02-24 | 2011-12-07 | 富士通テレコムネットワークス株式会社 | Ｌａｎシステム及び帯域自動割当方法 |
| JP4878185B2 (ja) * | 2006-03-17 | 2012-02-15 | 株式会社リコー | データ通信回路および調停方法 |
| TW200816719A (en) * | 2006-08-23 | 2008-04-01 | Matsushita Electric Ind Co Ltd | Communication equipment |
| WO2008153193A1 (ja) * | 2007-06-15 | 2008-12-18 | Nec Corporation | アドレス変換装置及びアドレス変換方法 |
| US8141080B2 (en) * | 2007-08-30 | 2012-03-20 | International Business Machines Corporation | Asynchronous data structure pull application programming interface (API) for stream systems |
| US8165033B1 (en) | 2007-08-30 | 2012-04-24 | Altera Corporation | Method and apparatus for performing generalized processor sharing scheduling |
| US8861514B1 (en) * | 2007-09-27 | 2014-10-14 | Marvell International Ltd. | Method and apparatus for egress jitter pacer |
| JP5088145B2 (ja) * | 2008-01-10 | 2012-12-05 | 富士通株式会社 | パケット中継装置、制御方法およびパケット中継プログラム |
| US8345691B2 (en) | 2008-05-15 | 2013-01-01 | Cellco Partnership | Scheduling with quality of service support in wireless system |
| JP5237841B2 (ja) * | 2009-01-27 | 2013-07-17 | アラクサラネットワークス株式会社 | 帯域制御装置および通信制御半導体 |
| JP5263394B2 (ja) * | 2009-06-16 | 2013-08-14 | 富士通オプティカルコンポーネンツ株式会社 | 光通信装置及び光通信装置の節電制御方法 |
| US8631213B2 (en) | 2010-09-16 | 2014-01-14 | Apple Inc. | Dynamic QoS upgrading |
| US8510521B2 (en) | 2010-09-16 | 2013-08-13 | Apple Inc. | Reordering in the memory controller |
| US8314807B2 (en) | 2010-09-16 | 2012-11-20 | Apple Inc. | Memory controller with QoS-aware scheduling |
| US8909764B2 (en) * | 2011-07-28 | 2014-12-09 | Xyratex Technology Limited | Data communication method and apparatus |
| JP5907763B2 (ja) * | 2012-03-13 | 2016-04-26 | 三菱電機株式会社 | 集線装置および優先制御システム |
| US9258245B2 (en) * | 2012-09-12 | 2016-02-09 | Broadcom Corporation | Multiple cell dequeue for high speed queueing |
| US20140149715A1 (en) * | 2012-11-28 | 2014-05-29 | Los Alamos National Security, Llc | Scalable and programmable computer systems |
| US9053058B2 (en) | 2012-12-20 | 2015-06-09 | Apple Inc. | QoS inband upgrade |
| US9229896B2 (en) | 2012-12-21 | 2016-01-05 | Apple Inc. | Systems and methods for maintaining an order of read and write transactions in a computing system |
| JP6036310B2 (ja) * | 2013-01-09 | 2016-11-30 | 富士通株式会社 | パケット交換装置、伝送装置、及びパケットスケジューリング方法 |
| US11038819B2 (en) * | 2017-06-29 | 2021-06-15 | Intel Corporation | Technologies for extracting extrinsic entropy for workload distribution |
| JP6982250B2 (ja) * | 2018-07-31 | 2021-12-17 | 日本電信電話株式会社 | パケット転送装置、方法、及びプログラム |
| CN110830380A (zh) * | 2018-08-09 | 2020-02-21 | 华为技术有限公司 | 确定报文出队的速率的方法及装置 |
| US12224942B2 (en) * | 2020-03-05 | 2025-02-11 | Nippon Telegraph And Telephone Corporation | Network management systems, edge devices, network management devices, and programs |
| EP4282152A4 (en) * | 2021-01-19 | 2024-11-27 | Dejero Labs Inc. | SYSTEMS AND METHODS FOR PUSH DATA COMMUNICATIONS |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB9520807D0 (en) * | 1995-10-11 | 1995-12-13 | Newbridge Networks Corp | Fair queue servicing using dynamic weights |
| US5859835A (en) * | 1996-04-15 | 1999-01-12 | The Regents Of The University Of California | Traffic scheduling system and method for packet-switched networks |
| US6487212B1 (en) * | 1997-02-14 | 2002-11-26 | Advanced Micro Devices, Inc. | Queuing structure and method for prioritization of frames in a network switch |
| JP3306705B2 (ja) | 1998-09-22 | 2002-07-24 | 富士通株式会社 | パケット転送制御装置及びそのスケジューリング方法 |
| JP3438651B2 (ja) * | 1999-05-31 | 2003-08-18 | 日本電気株式会社 | パケット多重装置 |
| US6891834B1 (en) * | 1999-09-09 | 2005-05-10 | Avici Systems | Apparatus and method for packet scheduling |
| US7039013B2 (en) * | 2001-12-31 | 2006-05-02 | Nokia Corporation | Packet flow control method and device |
| US7110411B2 (en) * | 2002-03-25 | 2006-09-19 | Erlang Technology, Inc. | Method and apparatus for WFQ scheduling using a plurality of scheduling queues to provide fairness, high scalability, and low computation complexity |
-
2002
- 2002-04-30 JP JP2002129149A patent/JP3872716B2/ja not_active Expired - Fee Related
- 2002-10-25 US US10/281,366 patent/US7190674B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| US7190674B2 (en) | 2007-03-13 |
| US20030202517A1 (en) | 2003-10-30 |
| JP2003324471A (ja) | 2003-11-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3872716B2 (ja) | パケット出力制御装置 | |
| Stephens et al. | Implementing scheduling algorithms in high-speed networks | |
| US6477144B1 (en) | Time linked scheduling of cell-based traffic | |
| US7876763B2 (en) | Pipeline scheduler including a hierarchy of schedulers and multiple scheduling lanes | |
| US6134217A (en) | Traffic scheduling system and method for packet-switched networks with fairness and low latency | |
| CN111512602B (zh) | 一种发送报文的方法、设备和系统 | |
| US20040151197A1 (en) | Priority queue architecture for supporting per flow queuing and multiple ports | |
| EP1867112B1 (en) | Assigning resources to items such as processing contexts for processing packets | |
| US20100278190A1 (en) | Hierarchical pipelined distributed scheduling traffic manager | |
| US20130003755A1 (en) | Priority-aware hierarchical communication traffic scheduling | |
| US7529224B2 (en) | Scheduler, network processor, and methods for weighted best effort scheduling | |
| US7522609B2 (en) | Propagation of minimum guaranteed scheduling rates among scheduling layers in a hierarchical schedule | |
| JP2000295228A (ja) | スイッチ及びそのスケジューラ並びにスイッチスケジューリング方法 | |
| US10110515B2 (en) | Packet scheduling using hierarchical scheduling process | |
| US8879578B2 (en) | Reducing store and forward delay in distributed systems | |
| CN109729013A (zh) | 一种流量整形中添加令牌的方法、装置及计算机可读存储介质 | |
| US7116680B1 (en) | Processor architecture and a method of processing | |
| WO2016082603A1 (zh) | 一种调度器及调度器的动态复用方法 | |
| US7065091B2 (en) | Method and apparatus for scheduling and interleaving items using quantum and deficit values including but not limited to systems using multiple active sets of items or mini-quantum values | |
| KR20120055946A (ko) | 공평한 대역 할당 기반 패킷 스케줄링 방법 및 장치 | |
| WO2007047864A2 (en) | Traffic shaping and metering scheme for oversubscribed and/or cascaded communication devices | |
| US7599381B2 (en) | Scheduling eligible entries using an approximated finish delay identified for an entry based on an associated speed group | |
| JP3575688B2 (ja) | パケットスイッチ | |
| JPH10135957A (ja) | トラヒックシェイパー装置 | |
| US7474662B2 (en) | Systems and methods for rate-limited weighted best effort scheduling |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20041124 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20060620 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20060627 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20060825 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20061010 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20061020 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| LAPS | Cancellation because of no payment of annual fees |