(57)【特許請求の範囲】
【請求項１】
送信待ちのパケットデータをそれぞれ出力保証帯域の設定が可能な複数のキューにより管理し該キュー毎のパケットデータの送信量を該出力保証帯域の設定に基づいてスケジューリングするパケット・スケジューラであって、
該パケットデータに関する情報に基づいて、空き状態のキューについての出力保証帯域を余剰帯域としてアクティブ状態の他のキューに公平に配分するための計算を行なう前計算手段と、
少なくとも、上記の各キューから最初に出力されるべき第１パケットデータの理想出力時刻計算に必要な該前計算手段での第１計算結果を含む第１中間データと、該第１パケットデータの次に出力されるべき第２パケットデータについての理想出力時刻計算に必要な該前計算手段での第２計算結果を含む第２中間データとを記憶する中間計算結果記憶手段と、
該中間計算結果記憶手段に記憶されている該第１中間データに基づいて上記の各キューにおける第１パケットデータについての理想送信時刻情報を計算する後計算手段と、
該後計算手段によって計算された各理想出力時刻情報に基づいて最優先に送信すべきキューの第１パケットデータを決定する送信パケットデータ決定手段と、
該送信パケットデータ決定手段で最優先に送信すべきと決定された第１パケットデータと同じキューに属する第２パケットデータについての第２中間データを、当該キューの新たな第１パケットデータについての第１中間データとして他のキューに属する第１パケットデータの第１中間データとともに該中間計算結果記憶手段から読み出して該後計算手段へ出力する中間計算結果読み出し制御手段とをそなえて構成されたことを特徴とする、パケット・スケジューラ。
【請求項２】
該中間計算結果読み出し制御手段が、
該中間計算結果記憶手段に記憶されている、該送信パケットデータ決定手段で最優先に送信すべきと決定された第１パケットデータについての第１中間データを無効にするように構成されたことを特徴とする、請求項１記載のパケット・スケジューラ。
【請求項３】
該中間計算結果記憶手段が、
該第２パケットデータの次に出力されるべき第３パケットデータの理想出力時刻計算に必要な該前計算手段での第３計算結果を含む第３中間データを、新たな第２パケットについての第２中間データとして記憶するように構成されたことを特徴とする、請求項１又は請求項２に記載のパケット・スケジューラ。
【請求項４】
該送信パケットデータ決定手段が、
該後計算手段によって計算された理想出力時刻情報を比較して最優先に送信すべき第１パケットデータの理想出力時刻情報を選択する理想出力時刻情報選択手段と、
該理想出力時刻情報選択手段からの理想出力時刻情報と該後計算手段からバイパス入力される理想出力時刻情報とを比較して最優先に送信すべき第１パケットデータを決定する合流制御手段と、
該後計算手段において計算された該第２パケットデータの理想出力時刻情報を該バイパス入力として該合流制御手段へ出力するとともに、それ以外の第１パケットデータの理想出力時刻情報を該理想出力時刻情報選択手段へ出力するバイパス制御手段とをそなえて構成されていることを特徴とする、請求項１〜３のいずれか１項に記載のパケット・スケジューラ。
【請求項５】
該バイパス制御手段が、
該キュー毎のバイパス制御回路をそなえるとともに、
該バイパス制御回路が、それぞれ、
該後計算手段によって計算された該第１パケットデータの理想出力時刻情報を記憶するメモリ部と、
該メモリ部に記憶された該理想出力時刻情報を該バイパス入力もしくは該理想出力時刻情報選択手段への入力として選択的に出力するバイパス選択部と、
該合流制御手段で最優先に送信すべきと決定された第１パケットデータの属するキュー番号が自担当のキュー番号と一致すると該メモリ部の該理想出力時刻情報が該バイパス入力として選択され、該キュー番号が自担当のキュー番号と異なると該メモリ部の該理想出力時刻情報が該理想出力時刻情報選択手段への入力として選択されるよう該バイパス選択部を制御する状態制御部とをそなえて構成されたことを特徴とする、請求項４記載のパケット・スケジューラ。
【請求項６】
該バイパス制御手段が、
該合流制御手段で最優先に送信すべきと決定した第１パケットデータについての理想出力時刻情報を無効にするように構成されたことを特徴とする、請求項４記載のパケット・スケジューラ。
【請求項７】
複数のパケットインタフェースについての送信待ちのパケットデータをそれぞれ出力保証帯域の設定が可能な複数のキューにより該パケットインタフェース毎に管理し該キュー毎のパケットデータの送信量を該出力保証帯域の設定に基づいてスケジューリングするパケット・スケジューラであって、
非アクティブ状態となっているキューについての出力保証帯域を余剰帯域としてアクティブ状態の他のキューに公平に配分するための計算を行なう前計算手段と、
少なくとも、上記の各キューから最初に出力されるべき第１パケットデータの理想出力時刻計算に必要な該前計算手段での第１計算結果を含む第１中間データと、該第１パケットデータの次に出力されるべき第２パケットデータの理想出力時刻計算に必要な該前計算手段での第２計算結果を含む第２中間データとを記憶する中間計算結果記憶手段と、
該中間計算結果記憶手段に記憶されている該第１中間データに基づいて上記の各キューにおける第１パケットデータの理想出力時刻情報を計算する後計算手段と、
該後計算手段によって計算された各理想出力時刻情報に基づいて最優先に送信すべきキューの第１パケットデータを決定する送信パケットデータ決定手段と、該送信パケットデータ決定手段で最優先に送信すべきと決定された第１パケットデータと同じキューに属する第２パケットデータについての第２中間データを、当該キューの新たな第１パケットデータについての第１中間データとして他のキューに属する第１パケットデータについての第１中間データとともに該中間計算結果記憶手段から読み出して該後計算手段へ出力する中間計算結果読み出し制御手段とをそなえるとともに、
上記の各手段を複数のパイプライン処理ステージに分割し、該パイプライン処理ステージが、それぞれ、一定時間毎に異なるパケットインタフェースについての処理を行なうように構成されたことを特徴とする、パケット・スケジューラ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケット・スケジューラに関し、特に、いわゆるルータなどのパケット転送装置においてＷＦＱ(Weighted Fair Queuing)を用いたパケット・スケジューリングを行なうのに好適な、パケット・スケジューラに関する。
【０００２】
【従来の技術】
ネットワークにおけるパケットデータ（以下、単に「パケット」という）のフロー、あるいは、フローのアグリゲート(集合；以下、これらを総称してストリームという)のサービス品質（ＱｏＳ：Quality of Service）を保証するために、ＩＰ（Internet Protocol）ルータやＡＴＭ（Asynchronous Transfer Mode）ルータなどのネットワーク中継装置（パケット転送装置）では、それぞれのストリームに対して帯域を予約し、その予約帯域を保証するようにパケットの送信、即ち、各ストリーム毎のキューに保持されたパケットの読み出し制御（パケット・スケジューリング）を行なう必要がある。なお、上記の各キューは、通常、先入れ先出し（ＦＩＦＯ：First-In First-Out）方式のメモリ（バッファ）で構成される。
【０００３】
一方、出力リンク（回線）の帯域を最大限に利用するため、各キューのアクティブ状況によって一時的に生じる剰余帯域をストリーム間で公平に配分する機能、即ち、非アクティブ状態のキュー（ストリーム）に対して設定されている予約帯域をアクティブ状態のキュー（ストリーム）に公平に分配する機能も必要となる。
【０００４】
なお、キューの「アクティブ状態」とは送信待ちのパケットがキューに存在している（保持されている）状態を意味し、「非アクティブ状態」とは、送信待ちのパケットがキューに存在しない（保持されていない、つまり空き）状態を意味する。
以上のような機能をもつパケット・スケジューリング手法としては、ＷＦＱがよく知られているが、従来のＷＦＱによる処理機能の実現では計算量が多いため、高速リンクに対応する実現が困難となっている。以下、ＷＦＱの計算原理について説明する。
【０００５】
パケット転送装置において、各ストリームのパケットはそれぞれ対応するキューに保持され、各キューに保持されたパケットはＦＩＦＯ方式で出力される（先頭パケットが出力されると、次のパケットが先頭パケットとなる）ので、ＷＦＱでは、非アクティブ状態のキューの余剰帯域を公平に配分することも考慮した場合、各キューの先頭パケット（最初に出力されるべきパケット）の理想出力時刻Ｆi,1を次式（１−１）により計算し、得られた各キューの先頭パケットの理想出力時刻Ｆi,1に基づいて、最優先で出力すべき先頭パケットを次式（１−２）により選択して出力することが行なわれる。
【０００６】
【数１】
0004199414.tif 000002
【０００７】
【数２】
0004199414.tif 000003
【０００８】
ここで、上記の式（１−１），（１−２）で使用した各記号の意味を説明する。
まず、式（１−１）の第１項において、Ｆはパケットの理想出力時刻、Ｔはパケットの到着時刻の情報をそれぞれ表わし、これらのＦやＴの添字部分(i,j)は、ｉ番目のキュー（以下、キュー＃ｉと表記する）の先頭からｊ番目のパケットを指す。即ち、Ｆi,jはキュー＃ｉの先頭からｊ番目のパケットについての理想出力時刻（情報）を表わし、Ｔi,jはキュー＃ｉの先頭からｊ番目のパケットの到着時刻（情報）を表わすことになる。
【０００９】
なお、１つのパケット・スケジューラ（以下、単に「スケジューラ」という）は１〜ｎ番目までのキューの処理を可能とするので、ｉ＝１〜ｎである。また、ｊ＝１は、スケジューラで計算を行なっている時に、キュー＃ｉの先頭に位置するパケットを表わし、ｊ＝０は直前に出力したパケットの出力時刻を表わす。
つまり、式（１−１）の第１項ｍａｘ｛Ｆi,0，Ｔi,1｝は、直前に出力したキュー＃ｉの先頭パケットの理想出力時刻と、その先頭パケットに続く同じキュー＃ｉのパケットの到着時刻とのうち値の大きい（遅い）方をとることを表わす。これは、先頭パケットの理想出力時刻Ｆi,1の計算基準となる時刻情報を、直前に出力したキュー＃ｉの先頭パケットの出力時刻Ｆi,0と、その先頭パケットに続く同じキュー＃ｉのパケットの到着時刻Ｔi,1とのいずれかに揃えることを意味する。
【００１０】
例えば、パケット出力後に次のパケットが到着する状況（次のパケット到着までにスケジューラによる計算が完了している状況）では、パケットの到着時刻Ｔi,1の方が直前に出力したパケットの出力時刻Ｆi,0よりも遅いので、次のパケットの到着時刻Ｔi,1が理想出力時刻Ｆi,1の計算基準となり、逆に、パケット出力前に次のパケットが到着する状況（スケジューラによる計算途中で次のパケットが到着する状況）では、直前に出力したパケットの出力時刻Ｆi,0の方が次のパケットの到着時刻Ｔi,1よりも遅いので、直前に出力したパケットの出力時刻Ｆi,1が理想出力時刻Ｆi,1の計算基準となる。
【００１１】
一方、式（１−１）の第２項において、Ｌi,jはキュー＃ｉの先頭からｊ番目のパケットの長さ、Φｉはキュー＃ｉに設定された予約帯域、Φｂはアクティブ状態のキュー（以下、単に「アクティブキュー」ともいう）＃ｉについての予約帯域Φｉの合計、Ｒは全キュー＃１〜＃ｎの予約帯域Φｉの合計をそれぞれ表わす。つまり、式（１−１）の第２項は、空き状態のキュー＃ｉの予約帯域を他のキューへ公平に配分するためのパラメータを表わしていることになる。
【００１２】
そして、式（１−２）は、アクティブ状態のキューの中で最も理想出力時刻Ｆi,1の値が小さいものを選択することを意味する。つまり、理想出力時刻Ｆi,1が大きい先頭パケットほど、優先して出力すべき先頭パケットとしては選択されにくくなることが分かる。
例えば、或るキュー＃ｉから１回の出力で大きなパケット長Ｌのパケットを出力した場合には、次のパケット（新たな先頭パケット）についての理想出力時刻Ｆi,1の値が大きくなるので、そのパケットは出力パケットとして選択されにくくなり、連続出力は行なわれにくくなる。
【００１３】
また、同じキュー＃ｉから連続してパケットが出力された場合にも、式（１−１）の第２項の累積により、理想出力時刻Ｆi,1が増加してゆくので、或る程度連続してパケット出力が行なわれた時点で、そのキュー＃ｉの先頭パケットは出力パケットとしては選択されにくくなる。
逆に、例えば、予約帯域Φｉに大きな値が設定されているキュー＃ｉは、他のキュー＃ｉに比べて理想出力時刻Ｆi,1が小さくなるので、そのキュー＃ｉのパケットが出力パケットとして選択されやすくなる。
【００１４】
なお、以下の説明において、便宜上、上記の式（１−１）は次式（１−３）に示すように変形する。
Ｆi,1＝αi,1＋βi,1×γ  …（１−３）
ただし、αi,1＝ｍａｘ｛Ｆi,0，Ｔi,1｝、βi,1＝Ｌi,1／Φｉ、γ＝Φｂ／Ｒである。また、上記のαi,1は「α」、βi,1は「β」もしくは「βｉ」とそれぞれ略記する場合がある。同様に、前記のＦi,jを「Ｆ」もしくは「Ｆｉ」、Ｔi,jを「Ｔ」もしくは「Ｔｉ」とそれぞれ略記する場合もある。以上の記号は、後述する本発明の実施形態においても同様の意味で使用するものとする。
【００１５】
さて、ここで、上述したような計算を実際にハードウェア（パケット・スケジューラ）として実現するには、例えば、図２１に示すような構成が考えられる。即ち、この図２１に示すように、ＷＦＱを用いたパケット・スケジューラ１００は、キュー管理部１０１，計算部１０２及び最小値選択部１０３をそなえて構成され、さらに、キュー管理部１０１は、エンキュー処理部１１１，キュー記憶部１１２及びデキュー処理部１１３をそなえ、計算部１０２は、γ計算部１２１，β計算部１２２，各キュー＃ｉ毎の記憶部１２３−１〜１２３−ｎ及び各キュー毎のＦ計算部１２４−１〜１２４−ｎをそなえて構成されている。
【００１６】
ここで、キュー管理部１０１において、キュー記憶部１１２は、図示しないパケットメモリに格納された到着パケットに関する情報〔パケット長Ｌ，到着時刻Ｔ(TimeStamp)，上記パケットメモリでの格納位置（メモリアドレス；TopPointer）〕を、その到着パケットが属するストリーム対応のキュー＃１〜＃ｎ毎にＦＩＦＯ形式で記憶してキュー管理テーブルとして管理するためのものである。
【００１７】
また、エンキュー処理部１１１は、上記のパケットメモリから通知されるエンキュー番号（EnQueueNo）に基づいて、上記の到着パケットの情報を、キュー記憶部１１２（キュー管理テーブル）の対応するキュー＃ｉに格納（エンキュー）するものであり、デキュー処理部１１３は、最小値選択部１０３にて最優先に出力すべきと決定した先頭パケットの属するキュー番号ｉ（デキュー指示；DeQueueNo=i）を受けることにより、そのキュー番号ｉに対応するキュー＃ｉの先頭パケットの情報（メモリアドレス）をパケットメモリに通知して該当パケットを出力リンク（回線）に送出させるとともに、そのパケットの情報〔パケット長Ｌ，到着時刻Ｔ(TimeStamp)，メモリアドレス（TopPointer）〕を削除するものである。
【００１８】
なお、本キュー管理部１０１では、各キュー＃ｉ毎に設定される予約帯域Φｉやアクティブキュー＃ｉの合計予約帯域Φｂ，最小値選択部１０３で選択された先頭パケットの出力時刻Ｆi,0なども管理されている。
次に、計算部１０２において、γ計算部１２１は、キュー管理部１０１で管理されているアクティブキュー＃ｉの合計予約帯域Φｂを基に前記のγ（＝Φｂ／Ｒ）を計算するためのものであり、β計算部１２２は、キュー管理部１０１で管理されている情報のうち、パケット長Ｌと予約帯域Φｉとにより上記のβ（＝Ｌ／Φｉ）を計算するためのもので、その計算結果βは、キュー番号ｉに対応する記憶部１２３−ｉに記憶されるようになっている。なお、キュー管理部１０１で管理されている到着時刻Ｔ及び出力時刻Ｆi,0は、β計算部１２２は経由せずにそのまま対応するキュー番号ｉの記憶部１２３−ｉにて上記の計算結果βと組で記憶される。
【００１９】
また、各Ｆ計算部１２４−ｉは、それぞれ、上記の記憶部１２３に記憶されている情報（β，Ｔ，Ｆi,0）に基づいて、前記の式（１−３）による計算を行なうことにより、対応するキュー＃ｉの先頭パケットについての理想出力時刻Ｆを計算するＦi,1を計算するためのもので、このために、図２１中に示すように、それぞれ、β×γ計算部１２５，α計算部１２６及びこれらの各計算部１２５，１２６の計算結果を加算することにより理想出力時刻Ｆi,1を求める加算部１２７を有して構成されている。
【００２０】
そして、上記の最小値選択部１０３は、上記の各Ｆ計算部１２４−ｉによって求められた各キュー＃ｉ毎の先頭パケットの理想出力時刻Ｆi,1を、例えば、トーナメント方式などで比較することにより、最小の理想出力時刻Ｆi,1をもつ先頭パケットの属するキュー＃ｉを選択（決定）するためのもので、そのキュー番号ｉがデキュー指示としてデキュー処理部１１３に通知（フィードバック）されることによって、該当するキュー＃ｉの先頭パケットがパケットメモリから読み出されて出力リンクへ転送されるようになっている。なお、このとき選択された理想出力時刻Ｆi,1も、キュー管理部１０１に通知され、キュー管理部１０１にて、次の計算で使用する出力時刻Ｆi,0として管理されることになる。
【００２１】
上述のごとく構成されたパケット・スケジューラ１００では、或るストリームからのパケット到着毎に、エンキュー処理部１１１によって、その到着パケットが属するストリームに対応するキュー＃ｉの状態が更新されてゆく。そして、キュー＃ｉの先頭にパケットが存在する場合、その先頭パケットに関する情報(パケット長Ｌi,1，到着時刻Ｔi,1)，直前に出力された先頭パケットに関する情報（出力時刻Ｆi,0）及びキュー＃ｉ対応の設定情報（１／Φｉ）がそれぞれキュー管理部１０１から計算部１２４に送られる。
【００２２】
計算部１２４−ｉでは、まず、上述のごとくキュー管理部１０１から送られてきた情報により、γ計算部１２１にてγの値が計算されるとともに、β計算部１２２にてβの値が計算され、βは対応するキュー番号ｉの記憶部１２３−ｉに保持される。なお、βの計算に用いられなかった情報（到着時刻Ｔi,1，出力時刻Ｆi,0）は、それぞれ、β計算部１２２によって得られたβとともに記憶部１２３−ｉに保持される。
【００２３】
そして、γ計算部１２１によって求められたγと、記憶部１２３−ｉに保持されたβ，Ｔi,1及びＦi,0とは、それぞれ、同じタイミングで対応するキュー番号ｉのＦ計算部１２４−ｉに入力され、そのＦ計算部１２４−ｉでは、このようにして送られてきた情報（γ，β，Ｔi,1及びＦi,0）を基に、β×γ計算部１２５にてβ×γの値が計算されるとともに、α計算部１２６にてαの値が計算され、それらの計算結果が加算部１２７にて加算されることにより、キュー番号ｉの先頭パケットについての理想出力時刻Ｆi,1が求められる。
【００２４】
このようにして各Ｆ計算部１２４−ｉにて求められた各理想出力時刻Ｆi,1は、それぞれ、同一タイミングで最小値選択部１０３に入力され、最小値選択部１０３は、トーナメント方式などによって各理想出力時刻Ｆi,1を比較して、最もの値の小さい理想出力時刻Ｆi,1を選択し、そのキュー番号ｉをデキュー指示としてキュー管理部１０１のデキュー処理部１１３に通知する。
【００２５】
これにより、デキュー処理部１１３によって、デキュー番号ｉのキュー＃ｉの先頭パケットが読み出されて、出力リンクに送出される。以降、同様にして、各キュー＃ｉ毎に先頭パケットの理想出力時刻Ｆi,1が計算されて、最も小さい理想出力時刻Ｆi,1をもつキュー＃ｉの先頭パケットが最優先に出力すべきパケットとして選択されて、出力リンクへ送出されてゆく。
【００２６】
ただし、本パケット・スケジューラ１００は、図２１中に示すように、キュー管理部１０１，記憶部１２３−ｉ（γ計算部１２１），Ｆ計算部１２４−ｉ及び最小値選択部１０３が、それぞれ、時間とともに同時に動作し一定時間（一定クロック数）ｐτ毎に情報を後段へ出力する４段のパイプライン構成になっており、計算部１０２では、次のデキュー指示が発生するまで、同じ情報に基づいた計算が繰り返し行なわれ、次のデキュー指示が発生すると、パイプライン処理によるそれまでの途中計算結果を破棄する（無効にする）ことで、デキュー指示発生後の新たな情報に基づく計算が開始されるようになっている。
【００２７】
また、上述した計算過程において、パケットの入出力によってキュー＃ｉのアクティブ状態に変化があると、合計予約帯域Φｂの値が変化する（つまり、アクティブキュー＃ｉに割り当て可能な余剰帯域の値が変化する）ため、式（１−３）の再計算が必要となる。
即ち、空き状態のキュー＃ｉにパケットが新たに格納されてアクティブキュー＃ｉの数が増えたり、１つしかパケットが保持されていないキュー＃ｉからそのパケットが出力されて空き状態のキュー＃ｉが増えたりすると、合計予約帯域Φｂの値が変化するため、γ計算部１２１において、γ（＝Φｂ／Ｒ）の再計算が必要になるのである。
【００２８】
このため、上記のγ計算部１２１は、空き状態からアクティブ状態に遷移したキュー＃ｉが生じると上記の合計予約帯域ΦｂとしてΦｂ＝Φｂ＋Φｉを用いてγの再計算を行ない、逆に、アクティブ状態から空き状態に遷移したキュー＃ｉが生じると上記の合計予約帯域ΦｂとしてΦｂ＝Φｂ−Φｉを用いてγの再計算を行なう。
【００２９】
以上のようにして、パケット・スケジューラ１００は、各キュー＃ｉのアクティブ状況によって一時的に生じる剰余帯域をストリーム間で公平に配分しながら、設定された予約帯域Φｉを保証するようにパケットの送信（パケット・スケジューリング）を行なうことが可能である。
【００３０】
【発明が解決しようとする課題】
しかしながら、このような従来のパケット・スケジューラ１００では、デキュー指示の発生からの一連のパイプライン処理の合計遅延時間が、そのスループットを決定してしまう。例えば、パイプライン段数をｍ段（図２１ではｍ＝４段）とすると、１パイプライン当たりの処理時間（遅延時間）は上記のようにｐτなので、上記の合計遅延時間はｍ×ｐτと表わせる。
【００３１】
ここで、最小パケット長（Ｌmin）のパケットが連続して入出力するときのスループット（Ｓ）は、Ｓ＝Ｌmin／（ｍ×ｐτ）によって求められる。つまり、パケット・スケジューラ１００のスループット（Ｓ）は、パイプライン処理の総段数（ｍ）によって制限されてしまうのである。
そこで、例えば、ｍ＝Ｌmin／（Ｓ×ｐτ）の時間間隔で各キュー＃ｉの先頭パケットに関する情報をパイプライン処理に入力することで、スループット（Ｓ）の向上を図ることも考えられるが、パイプライン処理では、上述したように、同じパケットについてのデキュー指示が重複して発生しないよう、必ず、デキュー指示によってパイプライン処理中のキュー＃ｉの先頭パケットに関する情報を無効にしなければならないので、実際には、同じキュー＃ｉからは連続的に（つまり、ｐτ間隔で）パケットを出力（デキュー）することができない。
【００３２】
即ち、或るキュー＃ｉの先頭パケットに対するデキュー指示が発生した場合、他のキュー＃ｉの先頭パケット（最小値選択部１０３で選択されなかったキュー＃ｉの先頭パケット）のパイプライン処理による計算途中の情報については有効であるが、デキュー済み先頭パケットについてのパイプライン処理による計算途中の情報については無効にしなければならない。
【００３３】
このため、次に同じキュー＃ｉからパケットがデキューされるのは、キュー管理部１０１から次の先頭パケットについての情報が計算部１０２に新たに送られて、新たに理想出力時刻Ｆi,1が求められ、その値が最小値選択部１０３にて比較・選択されるまでなく、結果として、同じキュー＃ｉからは（ｍ−１）×ｐτ間隔でしかパケットをデキューすることができず、パケット出力のスループットが低下してしまうのである。
【００３４】
本発明は、このような課題に鑑み創案されたもので、パイプライン処理の段数に起因して生じるスループットの低下を回避して、パケット・スケジューリングの大幅な高速化を図れるようにした、パケット・スケジューラを提供することを目的とする。
【００３５】
【課題を解決するための手段】
上記の目的を達成するために、本発明のパケット・スケジューラ（請求項１）は、送信待ちのパケットデータをそれぞれ出力保証帯域の設定が可能な複数のキューにより管理し各キュー毎のパケットデータの送信量をそれぞれの出力保証帯域の設定に基づいてスケジューリングするものであって、次の各手段をそなえて構成されていることを特徴としている。
【００３６】
（１）上記のパケットデータに関する情報に基づいて、空き状態のキューについての出力保証帯域を余剰帯域としてアクティブ状態の他のキューに公平に配分するための計算を行なう前計算手段
（２）少なくとも、上記の各キューから最初に出力されるべき第１パケットデータの理想出力時刻計算に必要な上記前計算手段での第１計算結果を含む第１中間データと、上記第１パケットデータの次に出力されるべき第２パケットデータについての理想出力時刻計算に必要な上記前計算手段での第２計算結果を含む第２中間データとを記憶する中間計算結果記憶手段
（３）この中間計算結果記憶手段に記憶されている第１中間データに基づいて上記の各キューにおける第１パケットデータについての理想送信時刻情報を計算する後計算手段
（４）この後計算手段によって計算された各理想出力時刻情報に基づいて最優先に送信すべきキューの第１パケットデータを決定する送信パケットデータ決定手段
（５）この送信パケットデータ決定手段で最優先に送信すべきと決定された第１パケットデータと同じキューに属する第２パケットデータについての第２中間データを、そのキューの新たな第１パケットデータについての第１中間データとして他のキューに属する第１パケットデータの第１中間データとともに上記の中間計算結果記憶手段から読み出して後計算手段へ出力する中間計算結果読み出し制御手段
ここで、上記の中間計算結果読み出し制御手段は、上記の中間計算結果記憶手段に記憶されている、上記送信パケットデータ決定手段で最優先に送信すべきと決定された第１パケットデータについての第１計算結果を無効にするように構成されるのが好ましい（請求項２）。
【００３７】
また、上記の中間計算結果記憶手段は、上記の第２パケットデータの次に出力されるべき第３パケットデータの理想出力時刻計算に必要な上記前計算手段での第３計算結果を含む第３中間データを、新たな第２パケットについての第２中間データとして記憶するように構成されていていもよい（請求項３）。
さらに、上記の送信パケットデータ決定手段は、次の各手段をそなえて構成されていてもよい（請求項４）。
【００３８】
（１）上記の後計算手段によって計算された理想出力時刻情報を比較して最優先に送信すべき第１パケットデータの理想出力時刻情報を選択する理想出力時刻情報選択手段
（２）この理想出力時刻情報選択手段からの理想出力時刻情報と上記の後計算手段からバイパス入力される理想出力時刻情報とを比較して最優先に送信すべき第１パケットデータを決定する合流制御手段
（３）上記の後計算手段において計算された第２パケットデータの理想出力時刻情報を上記のバイパス入力として上記の合流制御手段へ出力するとともに、それ以外の第１パケットデータの理想出力時刻情報を上記の理想出力時刻情報選択手段へ出力するバイパス制御手段
なお、上記のバイパス制御手段は、上記キュー毎のバイパス制御回路をそなえるとともに、これらの各バイパス制御回路が、それぞれ、次の各部をそなえていてもよい（請求項５）。
【００３９】
（１）上記の後計算手段によって計算された第１パケットデータの理想出力時刻情報を記憶するメモリ部
（２）このメモリ部に記憶された理想出力時刻情報を上記バイパス入力もしくは上記理想出力時刻情報選択手段への入力として選択的に出力するバイパス選択部
（３）上記の合流制御手段で最優先に送信すべきと決定された第１パケットデータの属するキュー番号が自担当のキュー番号と一致すると上記メモリ部の理想出力時刻情報が該バイパス入力として選択され、上記キュー番号が自担当のキュー番号と異なると上記メモリ部の理想出力時刻情報が上記理想出力時刻情報選択手段への入力として選択されるよう上記バイパス選択部を制御する状態制御部
また、上記のバイパス制御手段は、上記の合流制御手段で最優先に送信すべきと決定した第１パケットデータについての理想出力時刻情報を無効にするように構成されるのが好ましい（請求項６）。
【００４０】
さらに、本発明のパケット・スケジューラは、複数のパケットインタフェースについての送信待ちのパケットデータをそれぞれ出力保証帯域の設定が可能な複数のキューにより上記の各パケットインタフェース毎に管理し該キュー毎のパケットデータの送信量を上記出力保証帯域の設定に基づいてスケジューリングするパケット・スケジューラであって、次の各手段をそなえるとともに、これらの各手段が複数のパイプライン処理ステージに分割され、且つ、これらのパイプライン処理ステージが、それぞれ、一定時間毎に異なる上記パケットインタフェースについての処理を行なうように構成されたことを特徴としている（請求項７）。
【００４１】
（１）非アクティブ状態となっているキューについての出力保証帯域を余剰帯域としてアクティブ状態の他のキューに公平に配分するための計算を行なう前計算手段
（２）少なくとも、上記の各キューから最初に出力されるべき第１パケットデータの理想出力時刻計算に必要な該前計算手段での第１計算結果を含む第１中間データと、上記第１パケットデータの次に出力されるべき第２パケットデータの理想出力時刻計算に必要な該前計算手段での第２計算結果を含む第２中間データとを記憶する中間計算結果記憶手段
（３）この中間計算結果記憶手段に記憶されている上記第１中間データに基づいて上記の各キューにおける第１パケットデータの理想出力時刻情報を計算する後計算手段
（４）この後計算手段によって計算された各理想出力時刻情報に基づいて最優先に送信すべきキューの第１パケットデータを決定する送信パケットデータ決定手段
（５）この送信パケットデータ決定手段で最優先に送信すべきと決定された第１パケットデータと同じキューに属する第２パケットデータについての第２中間データを、当該キューの新たな第１パケットデータについての第１中間データとして他のキューに属する第１パケットデータについての第１中間データとともに上記の中間計算結果記憶手段から読み出して後計算手段へ出力する中間計算結果読み出し制御手段
【００４２】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
（Ａ）一実施形態の説明
図１は本発明の一実施形態としてのパケット・スケジューラの構成を示すブロック図で、この図１に示すパケット・スケジューラ１は、キュー管理部２，前計算部３，中間結果記憶部４，後計算部５及び最小値決定処理部１０（バイパス制御部６，最小値選択部７及び合流制御部８）をそなえて構成されている。なお、本パケット・スケジューラ１は、この図１中に示すように、それぞれｐτ間隔で後段の処理へ情報を出力する４段のパイプライン構成になっているものとする。
【００４３】
ここで、キュー管理部２は、図２１により前述したものと同様に、送信待ちのパケットデータ（以下、単に「パケット」という）をそれぞれ予約帯域（出力保証帯域）Φｉの設定が可能な複数のキュー＃１〜＃ｎにより管理するためのもので、このために、本実施形態では、図１及び図２に示すように、エンキュー処理部２１，キュー記憶部２２，デキュー処理部２３及びエンキュー・デキュー調停部２４をそなえて構成されている。なお、図１では、エンキュー・デキュー調停部２４の図示は省略している。
【００４４】
そして、上記のキュー記憶部２２は、本実施形態においても、到着パケットに関する情報〔関連パラメータ；パケット長Ｌ，到着時刻Ｔ(TimeStamp)，図２に示すパケットメモリ９での格納位置（メモリアドレス；TopPointer）〕を、その到着パケットが属するストリーム対応のキュー＃１〜＃ｎ毎にＦＩＦＯ形式で記憶してキュー管理テーブル２２１（図２参照）として管理するためのものである。
【００４５】
また、エンキュー処理部２１は、パケットメモリ９から通知されるエンキュー番号（EnQueueNo）に基づいて、上記の到着パケットの情報（関連パラメータ）を、キュー管理テーブル２２１の対応するキュー＃ｉに格納（エンキュー）することにより、パケット到着（パケットメモリ９への書き込み）毎にその状態を更新するものである。
【００４６】
ただし、本エンキュー処理部２１は、最初の計算では各キュー＃ｉの先頭から１番目のパケットと２番目のパケットの情報をキュー管理テーブル２２１から読み出してそれぞれ時系列に後段の前計算部３に出力するようになっている。また、上記のパケット情報のうち到着時刻Ｔ(TimeStamp)については、図２では、エンキュー処理部２１がキュー管理テーブル２２１に対してエンキューを行なったときのタイマ２５でのタイマ値として得られる構成になっている。
【００４７】
一方、デキュー処理部２３は、後述するデキュー指示（デキュー番号ｉ）を受けることにより、そのデキュー番号ｉに対応する先頭パケットの情報（メモリアドレス；TopPointer）をキュー管理テーブル２２１から読み出してパケットメモリ９に通知するもので、これにより、そのメモリアドレスに格納されているパケットがパケットメモリ９から読み出されて出力リンク（回線）に送出されることになる。
【００４８】
ただし、本実施形態のデキュー処理部２３は、上記のデキュー指示を受けると、デキュー番号ｉに対応するキュー管理テーブル２２１に格納されているデキュー済みのパケット情報を削除するとともに、同じキュー＃ｉの３番目のパケット情報をキュー管理テーブル２２１から読み出して前計算部３に出力する機能も有している。
【００４９】
また、エンキュー・デキュー調停部２４は、少なくとも、キュー管理テーブル２２１の同じキュー＃ｉに同一タイミングで上記のエンキュー処理部２１及びデキュー処理部２３がアクセスしてパケットの情報が消失してしまうようなことを防止するために、エンキュー処理部２１及びデキュー処理部２３のキュー管理テーブル２２１に対するアクセスタイミングをそれぞれ調停するためのものである。
【００５０】
次に、前計算部３は、上記のキュー管理部１０１から出力されてくるパケットの情報に基づいて、ＷＦＱの計算、即ち、空き状態のキュー＃ｉについての予約帯域Φｉを余剰帯域としてアクティブキュー＃ｉに公平に配分するための計算を行なうためのもので、このために、図１に示すように、γ計算部３１及びβ計算部３２をそなえて構成されている。
【００５１】
ここで、γ計算部３１は、余剰帯域の配分変数〔γ＝Φｂ×（１／Ｒ）〕を計算するためのものである。ただし、パケットの入出力でキュー＃ｉのアクティブ状況が変化した場合には、γ計算部３１は、γの再計算を行なう。例えば、Φbがアクティブキューの予約帯域Φｉを合計した値で、初期値（全てのキュー＃ｉにパケット情報が存在しないとき）が０であるとすると、空き状態からアクティブ状態に遷移したキュー＃ｉが生じると、Φｂ=Φｂ＋Φｉを計算しそのΦｂでγを計算し直す。一方、アクティブ状態から空き状態に遷移したキュー＃ｉが生じると、Φｂ=Φｂ−Φｉを計算しそのΦｂでγを計算し直す。
【００５２】
なお、本γ計算部３１は、例えば図２に示すように、上記のΦｉの代わりに、（Φｉ／Ｒ）を予めＲＡＭ３１１に設定しておけば、その値（Φｉ／Ｒ）をアクティブキュー＃ｊ（ｊ∈active）の数だけγ演算器（加算器）３１２にて累積加算してゆくだけで、Φｂ×（１／Ｒ）を求めることができ、乗算の計算を省略することができる。
【００５３】
一方、上記のβ計算部３２は、パケット長（Ｌ）×予約帯域（1／Φｉ)の計算により前記のβを求めるもので、例えば図２では、エンキュー処理部２１から通知されるキュー番号（QueueNo=i）により、予めＲＡＭ３２１に設定された（１／Φｉ)を読み出して、その値（１／Φｉ)と、同じくエンキュー処理部２１から通知されるパケット長Ｌ（PacketLen）とを乗算器３２２にて乗算することにより、βを求める構成になっている。
【００５４】
次に、中間結果記憶部４は、各キュー＃ｉの先頭と２番目のパケットの情報に対しての中間計算データ(βi,1，Ｔi,1)，(βi,2，Ｔi,2)と、合流制御部８の出力からフィードバックされてくる、直前に出力した先頭パケットの出力時刻(Ｆi,0)とをキュー＃ｉ毎に保持して後段の後計算部５へ出力するためのものである。なお、以下では、これらの中間計算データ(βi,1，Ｔi,1)，(βi,2，Ｔi,2)と、直前に出力した先頭パケットの理想出力時刻(Ｆi,0)とを総称して「中間データ」という場合がある。
【００５５】
つまり、上記の中間結果記憶部４は、少なくとも、上記の各キュー＃ｉの先頭パケット（第１パケットデータ）の理想出力時刻計算Ｆに必要な前計算部３１での第１計算結果として上記のβi,1を含む（第１）中間データと、上記先頭パケットの次に出力されるべき２番目のパケット（第２パケットデータ）についての理想出力時刻計算に必要な第２計算結果として上記のβi,2を含む（第２）中間データとを記憶するようになっているのである。
【００５６】
このため、本中間結果記憶部４は、図１及び図２に示すように、それぞれ、上記の中間データを記憶するためのキュー毎＃ｉの中間データ記憶部４１−１〜４１−ｎと、デキュー指示により上記中間データの読み出し制御を行なう中間データ読み出し制御部４２とをそなえて構成されている。なお、図２では、中間データ読み出し制御部４２の図示は省略している。
【００５７】
具体的に、この中間データ読み出し制御部４２は、デキュー指示（DeQueueNo=i）を受けることにより、そのデキュー番号ｉと対応する中間データ記憶部４１−ｉの２番目のパケット情報(βi,2,Ｔi,2)と出力時刻（Ｆi,0)とを読み出して後計算部５へ出力するとともに、中間データ記憶部４１−ｉにおいて、その２番目パケットの情報を先頭パケットの情報として更新し、且つ、合流制御部８の出力からデキュー指示（DeQueueNo=i）とともにフィードバックされてくる出力時刻（Ｆi,0)を記憶する一方、デキュー指示（DeQueueNo=i）以外のキュー＃ｋ（ｋ≠ｉ）については、先頭のパケット情報(βk,1,,Ｔk,1)を対応する中間データ記憶部４１−ｋから読み出して後計算部５に出力するようになっている。
【００５８】
つまり、本中間データ読み出し制御部４２は、後述する合流制御部８で最優先に送信（デキュー）すべきと決定された先頭パケットと同じキュー＃ｉに属する２番目のパケットについての中間データを、そのキュー＃ｉの新たな先頭パケットについての中間データとして他のキュー＃ｋに属する先頭パケットの中間データとともに中間計算結果記憶部４から読み出して後計算部５へ出力するようになっているのである。これにより、一定の遅延時間で後段処理のためのデータ出力が可能となり、デキューから次のパケットの計算開始までの遅延時間を短縮することが可能である。
【００５９】
なお、上述のごとく２番目パケットの情報を新たな先頭パケットの情報として更新したキュー＃ｉについては、キュー管理部２から送出された３番目のパケットの情報に基づいて前計算部３で計算されたパケット情報(βi,2,Ｔi,2)と、デキュー指示（DeQueueNo=i）とともに送られてくる直前に出力した先頭パケットについての出力時刻（Ｆi,0)とが新たな２番目のパケットについての中間データとして中間データ記憶部４１−ｉに記憶される。
【００６０】
つまり、本パケット・スケジューラ１は、一定時間間隔ｐτ毎に、２番目パケットの情報を新たな先頭パケットの情報として更新したことで空きのできた中間データ記憶部４１−ｉに、その次（３番目）のパケットについての中間データを、順次、補填してゆくことで、常に、先頭パケットと２番目のパケットとの２つ分のパケットについての中間データを中間データ記憶部４１−ｉに保持しておくように動作するのである。
【００６１】
次に、後計算部５は、パイプライン前段の上記の中間結果記憶部４から入力された、全アクティブキュー＃ｉの中間データに基づいて、各アクティブキュー＃ｉ毎に、前記の式（１−３）による演算を行なって、各アクティブキュー＃ｉの先頭パケットの理想出力時刻Ｆi,1を求めるためのもので、このために、図１及び図２に示すように、キュー＃ｉ毎のＦ計算部５１−１〜５１−ｎを有しており、これらの各Ｆ計算部５１−ｉに、それぞれ、β×γを計算するβ×γ計算部（乗算器）５２と、αi,1＝ｍａｘ｛Ｆi,0,Ti,1｝を計算するα計算部５３と、これらの各計算部５２，５３の計算結果を加算することにより理想出力時刻Ｆi,1を求める加算部５４とがそなえられている。
【００６２】
また、最小値決定処理部（送信パケットデータ決定手段）１０は、上記の後計算部５によって計算された各理想出力時刻Ｆi,1に基づいて最優先に送信すべきキュー＃ｉの先頭パケットを決定（選択）するためのもので、このために、本実施形態では、それぞれ、次のような機能を有する前記バイパス制御部６，最小値選択部７及び合流制御部８がそなえられている。
【００６３】
即ち、バイパス制御部６は、各キュー＃ｉと対応して、後計算部５からの計算結果（キュー＃ｉ毎の理想出力時刻Ｆi,1）を最小値選択部７を経由せずに合流制御部８へバイパスするかどうかを示す状態変数Ｓｉを有し、この状態変数Ｓｉに応じて理想出力時刻Ｆi,1を最小値選択部７及び合流制御部８のいずれかに選択的に出力するためのもので、例えば、Ｓｉ＝ＯＮ状態の場合には、次に後計算部５から入力されてくる理想出力時刻Ｆi,1を合流制御部８へバイパスし、Ｓｉ＝ＯＦＦ状態の場合には、バイパスせずに最小値選択部７へ出力するようになっている。
【００６４】
このため、本バイパス制御部６には、図２に示すように、各キュー＃ｉ毎のバイパス制御回路６１−１〜６１−ｎがそなえられており、さらに、これらの各バイパス制御回路６１−ｉには、それぞれ、例えば図３に示すように、一時記憶部６２，選択部６３及び状態制御部６４が設けられている。
ここで、上記の一時記憶部（メモリ部）６２は、後計算部５の対応するＦ計算部５１−ｉから入力される理想出力時刻Ｆi,1を一時的に記憶しておくためのものであり、選択部（バイパス選択手段）６３は、この一時記憶部６２に記憶された理想出力時刻Ｆi,1を合流制御部８へのバイパス入力もしくは最小値選択部７への入力として選択的に出力するためのものである。
【００６５】
そして、状態制御部６４は、例えば図４に示す状態遷移図に従って状態変数Ｓｉを制御することで、選択部６３での選択状態を制御するためのものである。即ち、初期状態において状態変数ＳｉはＯＦＦ状態（非バイパス状態；状態遷移６５−１）であり、ＯＦＦ状態で、自担当のキュー番号ｉと一致するデキュー番号ｉを受けると、状態変数ＳｉはＯＮ状態（バイパス状態）に遷移して（状態遷移６５−２）、状態制御部６４は、一時記憶部６２への上書きを許容することで出力待機中の先頭パケットについての理想出力時刻Ｆi,1を破棄する（無効にする）とともに、次に後計算部５から到着する先頭パケット（元々は２番目のパケット）についての理想出力時刻Ｆi,1がバイパスされる状態に選択部６３を制御する。
【００６６】
一方、状態変数Ｓｉ＝ＯＦＦ状態のときに受けたデキュー番号ｉが自担当のキュー番号ｉと一致しない場合は、状態変数ＳｉはＯＦＦ状態のまま（状態遷移６５−３）で、状態制御部６４は、一時記憶部６２において待機中の先頭パケットについての理想出力時刻Ｆi,1が最小値選択部７へ出力されるよう選択部６３を制御する。なお、状態変数Ｓｉ＝ＯＦＦ状態で、理想出力時刻Ｆi,1が単に入力されてきた場合も、状態変数Ｓｉは変化せず（ＯＦＦ状態のまま）、入力されてきた理想出力時刻Ｆi,1が一時記憶部６２に記憶される（状態遷移６５−４）。
【００６７】
また、状態変数Ｓｉ＝ＯＮ状態のときに受けたデキュー番号ｉが自担当のキュー番号ｉと一致した場合は、状態変数Ｓｉは変化せず（ＯＮ状態のまま）、状態制御部６４は、一時記憶部６２において待機中の先頭パケットについての理想出力時刻Ｆi,1がバイパスされるよう選択部６３を制御する（状態遷移６５−５）。
【００６８】
一方、状態変数Ｓｉ＝ＯＮ状態のときに受けたデキュー番号ｉが自担当のキュー番号ｉと一致しない場合は、状態変数ＳｉはＯＦＦ状態に遷移し、状態制御部６４は、一時記憶部６２において待機中の先頭パケットについての理想出力時刻Ｆi,1が最小値選択部７へ出力されるよう選択部６３を制御する（状態遷移６５−６）。
【００６９】
また、状態変数Ｓｉ＝ＯＮ状態のときに、理想出力時刻Ｆi,1が入力されてきた場合は、状態変数Ｓｉは変化せず（ＯＦＦ状態のまま）、その理想出力時刻Ｆi,1がそのまま一時記憶部６２に記憶されるとともに、状態制御部６４が、その理想出力時刻Ｆi,1を合流制御部８へバイパスするよう選択部６３を制御する（状態遷移６５−７）。
【００７０】
なお、キュー＃ｉが空き状態となり、処理すべきデータ（理想出力時刻Ｆi,1）が存在しなくなった場合は、状態変数Ｓｉ（以下、単に「Ｓ」と略記する場合もある）は、元の状態（ＯＮ／ＯＦＦ状態）に関わらず、ＯＦＦ状態となり、状態制御部６４は、最小値選択部７への出力が選択されるよう選択部６３を制御する（状態遷移６５−８，６５−９）。
【００７１】
このようにして、本状態制御部６４は、自担当のキュー番号ｉと一致するデキュー番号ｉのデキュー指示を受けると、次に後計算部５（Ｆ計算部５１−ｉ）から到着する理想出力時刻Ｆi,1を合流制御部８へバイパスするよう選択部６３を制御し、デキュー番号ｉが自担当のキュー番号ｉと一致しなければ、次に後計算部５（Ｆ計算部５１−ｉ）から到着する理想出力時刻Ｆi,1をバイパスせずに最小値選択部７へ出力するよう選択部８を制御することが実現されている。
【００７２】
従って、バイパス制御部６全体でみると、バイパス制御部６は、デキュー番号ｉと対応するキュー＃ｉの理想出力時刻Ｆi,1を廃棄するとともに、それ以外のキュー＃ｋ（ｋ≠ｉ）の理想出力時刻Ｆk,1を最小値選択部７に出力し、且つ、デキュー番号ｉ対応のバイパス状態（Ｓｉ）をＯＮ状態に設定し、デキュー番号ｉ以外のキュー＃ｋに対応するバイパス状態（Ｓｋ）をＯＦＦ状態に設定していることになる。
【００７３】
次に、最小値選択部７は、上記のバイパス制御部６（バイパス制御回路６１−ｉ）から入力されてくる理想出力時刻Ｆｉ（ただし、合流制御部８へバイパスされたものは除く）の中から、最も値の小さい理想出力時刻Ｆｉのキュー番号ｉとその値Ｆｉを出力するもので、例えば図２に示すように、それぞれ値の小さい方を選択出力する（ｎ−１）個の比較器７１により、トーナメント方式で各理想出力時刻Ｆｉを比較することで、最も値の小さい理想出力時刻Ｆｉを出力するようになっている。
【００７４】
そして、合流制御部８は、上記のバイパス制御部６によってバイパスされてくる理想出力時刻Ｆｉと、上記の最小値選択部７で選択された理想出力時刻Ｆｉとを大小比較することにより、値の小さい方の理想出力時刻Ｆｉを選択するもので、選択された理想出力時刻Ｆｉのキュー番号ｉがデキュー指示としてキュー管理部２（デキュー処理部２３），中間結果記憶部４，バイパス制御部６にフィードバックされるとともに、その値Ｆｉが直前に出力した先頭パケットの出力時刻Ｆi,0（次の計算のための入力値）として中間結果記憶部４１（中間データ記憶部４１−ｉ）にフィードバックされて記憶されるようになっている。
【００７５】
つまり、本実施形態のパケット・スケジューラ１は、或るキュー＃ｉの先頭パケットがデキューされると、パイプライン処理により、それまでに中間結果記憶部４から後計算部５に既に読み出されて後計算部５で計算済みの２番目のパケットについての理想出力時刻Ｆｉをバイパス制御部６によって合流制御部８へバイパスすることで、その理想出力時刻Ｆｉと、デキューされなかった他のキュー＃ｋの先頭パケットについての理想出力時刻Ｆｋとが同じタイミングで合流制御部８に入力されて大小比較されるようにしているのである。
【００７６】
これにより、合流制御部８では、同じキュー＃ｉから連続して先頭パケットがデキューされる場合にも、デキューされなかったキュー＃ｋの先頭パケットとデキューされたキュー＃ｉの先頭パケットの次のパケットとの理想出力時刻比較を必ずパイプライン段数１段分の処理時間（ｐτ）毎に行なうことができる。即ち、同じキュー＃ｉからｐτ間隔で連続して先頭パケットをデキューすることが可能となるのである。
【００７７】
以下、上述のごとく構成された本実施形態のパケット・スケジューラ１の動作について詳述する。ただし、以下の説明では、説明の簡単化のために、例えば図５に示すように、キュー＃ｉの数（ｎ）が“２”の場合を例にする。なお、この図５において、“Ｑ１”はキュー＃１、“Ｑ２”はキュー＃２、“Ｐ１”は先頭パケットの情報（中間データ）を表わす。即ち、“Ｑ１，Ｐ１”はキュー＃１の先頭パケットの情報を意味し、“Ｑ２，Ｐ１”はキュー＃２の先頭パケットの情報を意味する。これらの記号の意味は、以降で使用する図６〜図１６においても同様である。
【００７８】
（１）初期状態〔パケット出力（デキュー指示）が無い状態〕からデキュー指示（パケット出力）が発生するまでの動作説明（図６〜図８）
まず、図６に示すように、初期状態では、パケットの出力がないので、デキュー指示も発生していない。このとき、バイパス制御部６での各キュー＃１，＃２に対応するバイパス制御回路６１−１，６１−２のバイパス状態（状態変数Ｓ）は全てＯＦＦ状態にリセットされている。
【００７９】
かかる状態で、キュー管理部２の各キュー＃１，＃２にそれぞれ送信待ちのパケットが存在しているとすると、システムクロック〔一定の時間間隔(pτ)〕に従って、キュー管理部２のエンキュー処理部２１から各キュー＃１，＃２の先頭パケットと２番目のパケットの情報が前計算部３に出力され、前計算部３にて、各キュー＃１，＃２のそれぞれについて、先頭パケットと２番目のパケットに対するβの値が計算されるとともに、先頭パケットについてのγの値が計算される。
【００８０】
そして、得られた２パケット分のβの値は、それぞれ、キュー＃１，＃２毎に、中間結果記憶部４の対応する中間データ記憶部４１−１，４１−２に、先頭パケット（Ｐ１）及び２番目のパケット（Ｐ２）についての中間データの一部として一旦保持される。中間結果記憶部４は、各中間データ記憶部４１−１，４１−２に保持されている２パケット分の中間データのうち先頭パケットについての中間データの組をそれぞれ後段の後計算部５へ送る（符号Ｓ１参照）。なお、パケットの無い空き状態のキュー＃ｉについては、パケットが存在しない識別情報を送って、以降の段では処理しない。
【００８１】
その後、後計算部５（Ｆ計算部５１−１，５１−２）での計算を経て、各キュー＃１，＃２の先頭パケットについて求められた理想出力時刻Ｆ1，Ｆ2の組がバイパス制御部６に到着したとする。ここで、この場合、バイパス制御部６（バイパス制御回路６１−１，６１−２）における状態変数ＳｉはそれぞれＯＦＦ状態であるので、バイパス制御部６は、いずれも、到着した理想出力時刻Ｆ1，Ｆ2をバイパスしないように制御する（図４に示す状態遷移６５−４参照）。
【００８２】
即ち、図７に示すように、一定の時間間隔（pτ）をトリガとして、バイパス制御部６は、状態変数Ｓｉ＝ＯＦＦ状態のキュー＃１，＃２に対して、到着した理想出力時刻Ｆ1，Ｆ2をそれぞれ最小値選択部７に出力する（符号Ｓ２参照）。一方、このとき、中間結果記憶部４では、デキュー指示が発生していないので、前回送ったものと同じ先頭パケットについての中間データの組をそれぞれ後計算部５へ送る（符号Ｓ３参照）。
【００８３】
そして、最小値選択部７では、入力してきた理想出力時刻Ｆ1，Ｆ2のうち、値の小さい方の理想出力時刻Ｆ1，Ｆ2（仮に、Ｆ1とする）を選択して、合流制御部８へ出力する。この処理と平行して、後計算部５からは、図８に示すように、次の中間データの組が出力されて、バイパス制御部６に入力される。このとき、何れのバイパス制御回路６１−１，６１−２の状態変数ＳもＯＦＦ状態であるので、到着した中間データの組は、それぞれ、対応する一時記憶部６２に記憶される（符号Ｓ４，図４に示す状態遷移６５−４参照）。
【００８４】
一方、このとき、合流制御部８では、最小値選択部７の出力とバイパス制御部６の出力とを合流して値の小さい方を選択するが、この場合は、バイパス制御部６からバイパスされてくるデータが無いので、最小値選択部７から入力された理想出力時刻Ｆ1をそのまま選択する（符号Ｓ５参照）。そして、デキュー指示（DeQueueNo=1）を前段(キュー管理部２，中間結果記憶部３，バイパス制御部６)にフィードバックするとともに、選択した理想出力時刻Ｆ1を次の計算のために中間結果記憶部４へフィードバックする。
【００８５】
（２）同じキュー＃ｉから連続してパケットが出力される場合の動作説明
次に、以下では、同じキュー＃ｉに対して連続してデキュー指示が発生して、同じキュー＃ｉから２つのパケットが連続して出力される場合の動作について説明する。
まず、図９に示すように、図８により上述したごとく、合流制御部８においてキュー＃１の先頭パケットについての理想出力時刻Ｆ1が選択されて、デキュー指示（DeQueueNo=1）が、キュー管理部２，中間結果記憶部４及びバイパス制御部６にフィードバックされたとする（キュー＃１の先頭パケットが出力リンクに出力されたとする）。
【００８６】
すると、図１０に示すように、キュー管理部２では、キュー＃１から次(３番目)のパケット（Ｐ３）の情報をキュー管理テーブル２２１から読み出して前計算部３に出力する（符号Ｓ６参照）。また、中間結果記憶部４では、キュー＃１の２番目のパケットについての中間データ（Ｑ１，Ｐ２）を新たな先頭パケットについての中間データ（Ｑ１，Ｐ１）として読み出して、デキュー指示（DeQueueNo=1）を受けたキュー＃１以外のキュー＃２の先頭パケットについての中間データ（Ｑ２，Ｐ１）と組で、後計算部５に出力する（符号Ｓ７参照）。このとき、キュー＃１の２番目のパケットについての中間データ（Ｑ１，Ｐ２）は、先頭パケットについての中間データ（Ｑ１，Ｐ１）として一時記憶部６２に記憶される（符号Ｓ７′参照）。
【００８７】
さらに、バイパス制御部６では、上記のデキュー指示（DeQueueNo=1）により、キュー＃１と対応する一時記憶部６２に記憶されている理想出力時刻Ｆ1を破棄して（無効にして；図９参照）、キュー＃１対応の状態変数ＳをＯＮ状態に設定する（図４に示す状態遷移６５−２参照）とともに、キュー＃１以外の理想出力時刻Ｆ2を最小値選択部７に出力する（符号Ｓ８参照）。このとき、キュー＃１以外の状態変数ＳはＯＦＦ状態のままである（図４に示す状態遷移６５−３参照）。
【００８８】
その後、図１１に示すように、上記の符号Ｓ８で示すキュー＃２の先頭パケットについての理想出力時刻Ｆ2は、最小値選択部７に入力され、最小値選択が行なわれる（符号Ｓ９参照）。一方、このとき、後計算部５での処理遅延時間を経て、図１０において中間結果記憶部４から読み出された中間データ（符号Ｓ７参照）に基づいて求められた理想出力時刻Ｆ1，Ｆ2がバイパス制御部６の入力に到着する（符号Ｓ１０参照）。
【００８９】
そして、図１２に示すように、バイパス制御部６では、キュー＃１対応の状態変数Ｓ＝ＯＮ状態であるため、到着した理想出力時刻Ｆ1を一時記憶部６２に記憶する（符号Ｓ１１参照）とともに、合流制御部８へバイパスする（符号Ｓ１２，図４に示す状態遷移６５−７参照）。なお、このとき、状態変数Ｓ＝ＯＦＦ状態のキュー＃２の先頭パケットについての理想出力時刻Ｆ2は、バイパスせずに一時記憶部６２に記憶する（符号Ｓ１３，図４に示す状態遷移６５−４参照）。
【００９０】
合流制御部８では、最小値選択部７から送られてきたキュー＃１以外のキュー＃２に対応する理想出力時刻Ｆ2と、バイパス制御部６からバイパスされてくるキュー＃１の先頭パケット（元々は２番目のパケット）についての理想出力時刻Ｆ1の中から最小のものを選んで出力する。仮に、キュー＃１の先頭パケットについての理想出力時刻Ｆ1が選ばれたら、つまり、同じキュー＃１に対するデキュー指示（DeQueueNo=1）が連続して発生した場合、そのデキュー指示（DeQueueNo=1）により、以下の処理が行なわれる。
【００９１】
即ち、図１３に示すように、まず、キュー管理部２では、キュー管理テーブル２２１からキュー＃１の次(３番目)のパケットの情報を読み出して、前計算部３に出力する（符号Ｓ１５参照）。
一方、中間結果記憶部４では、上記のデキュー指示（DeQueueNo=1）により、中間データ記憶部４１−１からキュー＃１の２番目のパケットに関する中間データ（Ｑ１，Ｐ２）を新たな先頭パケットについての中間データ（Ｑ１，Ｐ１）として、他のキュー＃２の先頭パケットに関する中間データ（Ｑ２，Ｐ１）との組で後計算部５に出力する（符号Ｓ１６参照）とともに、上記の中間データ（Ｑ１，Ｐ２）を新たな先頭パケットについての中間データ（Ｑ１，Ｐ１）として記憶する（符号Ｓ１７参照）。
【００９２】
また、バイパス制御部６では、上記のデキュー指示（DeQueueNo=1）により、キュー＃１に対応する一時記憶部６２の（理想出力時刻Ｆ1）を無効にする（符号Ｓ１８参照）。なお、このとき、キュー＃１対応の状態変数ＳはＯＮ状態のままである（図４に示す状態遷移６５−５参照）。一方、他のキュー＃２の理想出力時刻Ｆ2は最小値選択部７に出力される（符号Ｓ１９参照）。このとき、キュー＃２対応の状態変数Ｓは、デキュー番号が一致しないので、ＯＦＦ状態のままである（図４に示す状態遷移６５−３参照）。
【００９３】
以降は、合流制御部８にて他のキュー＃２の先頭パケットについての理想出力時刻Ｆ2が選択されてデキュー指示（DeQueueNo=2）が発生するまで、図１１〜図１３により上述したパイプライン処理が繰り返し実施されて、同じキュー＃１から連続してパケットがデキューされる。
（３）前回と異なるキュー＃ｉに対するデキュー指示が発生した場合の動作説明
さて、以下では、図１２に示す状態において、合流制御部８にて、キュー＃１の先頭パケットについての理想出力時刻Ｆ1よりもキュー＃２の先頭パケットについての理想出力時刻Ｆ2の方が小さく、キュー＃２に対するデキュー指示（DeQueueNo=2）が発生した場合（符号Ｓ１４参照）の動作を説明する。
【００９４】
即ち、図１４に示すように、合流制御部８にて、キュー＃２の先頭パケットについての理想出力時刻Ｆ2が選ばれて出力されたとする（符号Ｓ１９′参照）と、キュー＃２に対するデキュー指示（DeQueueNo=2）が、キュー管理部２，中間結果記憶部４，バイパス制御部６にそれぞれフィードバックされる。
すると、図１５に示すように、キュー管理部２では、上記のデキュー指示（DeQueueNo=2）により、キュー＃２から次(３番目)のパケットの情報を読み出して前計算部３に出力する（符号Ｓ２０参照）。一方、中間結果記憶部４では、キュー＃２の２番目のパケットについての中間データをキュー＃２の新たな先頭パケットについての中間データとして読み出して、他のキュー＃１の先頭パケットについての中間データと組で、後計算部５に出力する（符号Ｓ２１参照）とともに、キュー＃２の先頭パケットについての中間データを先頭パケットについての中間データとして記憶する（符号Ｓ２２参照）。
【００９５】
また、このとき、バイパス制御部６では、上記のデキュー指示（DeQueueNo=2）により、キュー＃２に対応するバイパス制御回路６１−２の一時記憶部６２に保持されているデータ（理想出力時刻Ｆ2）を破棄するとともに、キュー＃２に対応する状態変数ＳをＯＮ状態に設定する（図４に示す状態遷移６５−２参照）。なお、他のキュー＃１に対応するバイパス制御回路６１−１では、デキュー指示（DeQueueNo=2）によるデキュー番号が一致しないので、状態変数ＳはＯＦＦ状態のままで、一時記憶部６２に保持中のデータ（理想出力時刻Ｆ1）を最小値選択部７に出力する（符号Ｓ２３及び図４に示す状態遷移６５−５参照）。
【００９６】
最小値選択部７では、この場合、バイパス制御部６からの入力が無いので、図１６に示すように、キュー＃１に対応する理想出力時刻Ｆ1を合流制御部８へ出力する（符号Ｓ２４参照）。一方、このとき、後計算部５での処理遅延時間を経て、中間結果記憶部５から出力されたキュー＃１，＃２の次のパケットについての理想出力時刻Ｆ1，Ｆ2の組が、バイパス制御部６の入力に到着する。
【００９７】
バイパス制御部６では、キュー＃２の状態変数Ｓ＝ＯＮ状態であるため、到着した理想出力時刻Ｆ2を合流制御部８へバイパスさせる（符号Ｓ２５参照）。ただし、このときバイパスした理想出力時刻Ｆ2は一時記憶部６２に保持しておく（図４に示す状態遷移６５−７参照）。また、キュー＃２以外の状態変数Ｓ＝ＯＦＦ状態のキュー＃１に対応する理想出力時刻Ｆ1は、バイパスされずに対応する一時記憶部６２に保持される（図４に示す状態遷移６５−４参照）。
【００９８】
そして、合流制御部８では、最小値選択部６からのデータ（理想出力時刻Ｆ1）とバイパス制御部６からバイパスされてきたデータ（理想出力時刻Ｆ2）の中から最小のものを選んで出力する。なお、仮に、キュー＃１に対応する理想出力時刻Ｆ1が選ばれたら、次は、図９からの処理が行なわれ、キュー＃２に対応する理想出力時刻Ｆ2が再度選ばれたら、図１４からの処理が行なわれる。
【００９９】
ここで、最初にキュー＃１に対するデキュー指示（DeQueueNo=2）が発生した後、次に、キュー＃２に対するデキュー指示（DeQueueNo=1）が発生する場合の動作をタイムチャートにして表わすと図１７のようになる。なお、この図１７において、Ｐ１はキュー＃ｉの先頭パケットを表わし、（Ｑi,n）は連続的にみたときのキュー＃ｉのｎ番目のパケットについてのデータを表わす。
【０１００】
即ち、最小値選択部７での比較の結果、キュー＃１に対応する理想出力時刻Ｆ1が選ばれて、デキュー指示（DeQueueNo=1）が発生したとする（矢印ｔ１，ｔ２参照）。なお、このとき、バイパス制御部６には、後計算部５での処理遅延時間を経て、次の先頭パケットについての中間データの組が既に保持されている（矢印ｔ３参照）。
【０１０１】
上記のデキュー指示（DeQueueNo=1）は、バイパス制御部６（バイパス制御回路６１−１，６１−２），中間結果記憶部４（中間データ記憶部４１−１，４１−２），キュー管理部２のそれぞれにフィードバックされ（矢印ｔ４参照）、まず、バイパス制御部６では、キュー＃１に対応する理想出力時刻Ｆ1を無効にする（出力しないことで次に到着するデータで上書きさせる）一方、キュー＃１以外の理想出力時刻Ｆ2を最小値選択部７へ出力する（矢印ｔ５参照）。
【０１０２】
また、中間結果記憶部４では、上記のデキュー指示（DeQueueNo=1）により、キュー＃１については２番目のパケット（Ｐ２）の中間データを新たな先頭パケットについての中間データとして後計算部５（Ｆ計算部５１−１）に出力する（矢印ｔ６参照）一方、その他のキュー＃２については再度同じ先頭パケット（Ｐ１）についての中間データを後計算部５（Ｆ計算部５１−２）に出力する（矢印ｔ７参照）。
【０１０３】
さらに、キュー管理部２では、上記のデキュー指示（DeQueueNo=1）により、キュー＃１の３番目のパケット（Ｑ１，Ｐ３）の情報がキュー管理テーブル２２１から読み出されて前計算部３へ出力している（矢印ｔ８参照）。
その後、合流制御部８には、最小値選択部７からのデキュー指示（DeQueueNo=1）の無かったキュー＃２に対応する理想出力時刻Ｆ2が到着する（矢印ｔ９参照）とともに、後計算部５（Ｆ計算部５１−１）で求められたキュー＃１の２番目のパケットについての理想出力時刻Ｆ1が新たな先頭パケットについての理想出力時刻Ｆ1としてバイパス制御部６でバイパスされて到着する（矢印ｔ１０，ｔ１１参照）。
【０１０４】
このとき、中間結果記憶部４（中間データ記憶部４１−１）には、キュー＃１の３番目のパケットについての前計算部３による計算結果が到着している（矢印ｔ８′参照）。また、バイパスされなかったキュー＃２の先頭パケットの理想出力時刻Ｆ2はバイパス制御部６で一時的に保持される（矢印ｔ１０′参照）。
そして、合流制御部８は、到着した各理想出力時刻Ｆ1，Ｆ2の中で最小のものを選んで出力する。仮に、今度は理想出力時刻Ｆ2の方が小さかったとすると、デキュー指示（DeQueueNo=2）が発生し（矢印ｔ１２参照）、これが再び、バイパス制御部６（バイパス制御回路６１−１，６１−２），中間結果記憶部４（中間データ記憶部４１−１，４１−２），キュー管理部２のそれぞれにフィードバックされる（矢印ｔ１３参照）。
【０１０５】
すると、まず、バイパス制御部６では、今度は、キュー＃２に対応する理想出力時刻Ｆ2を無効にする（出力しないことで次に到着するデータで上書きさせる）一方、キュー＃２以外の理想出力時刻Ｆ1を最小値選択部７へ出力する（矢印ｔ１４参照）。
一方、中間結果記憶部４では、上記のデキュー指示（DeQueueNo=2）により、今度は、キュー＃２については２番目のパケット（Ｐ２）の中間データを新たな先頭パケットについての中間データとして後計算部５（Ｆ計算部５１−２）に出力する（矢印ｔ１５参照）一方、その他のキュー＃１については再度同じ先頭パケット（Ｐ１）についての中間データを後計算部５（Ｆ計算部５１−１）に出力する（矢印ｔ１６参照）。
【０１０６】
また、キュー管理部２では、上記のデキュー指示（DeQueueNo=2）により、キュー＃２の３番目のパケット（Ｑ２，Ｐ３）の情報がキュー管理テーブル２２１から読み出されて前計算部３へ出力している（矢印ｔ１７参照）。
その後、合流制御部８には、最小値選択部７からのデキュー指示（DeQueueNo=2）の無かったキュー＃１に対応する理想出力時刻Ｆ1が到着する（矢印ｔ１８参照）とともに、後計算部５（Ｆ計算部５１−２）で求められたキュー＃２の２番目のパケットについての理想出力時刻Ｆ2が新たな先頭パケットについての理想出力時刻Ｆ2としてバイパス制御部６でバイパスされて到着する（矢印ｔ１９，ｔ２０参照）。
【０１０７】
このとき、中間結果記憶部４（中間データ記憶部４１−２）には、キュー＃２の３番目のパケットについての前計算部３による計算結果が到着しており（矢印ｔ１７′参照）、バイパス制御部６では、バイパスされなかったキュー＃２の先頭パケットの理想出力時刻Ｆ2が一時的に保持される（矢印ｔ１９′参照）。
そして、合流制御部８は、到着した各理想出力時刻Ｆ1，Ｆ2の中で最小のものを選んでデキュー指示（DeQueueNo=i）を出力し（矢印ｔ２１参照）、以降は、そのデキュー番号に応じて、上記と同様の処理が繰り返されてゆく。
【０１０８】
以上のように、本実施形態のパケット・スケジューラ１によれば、中間結果記憶部４において常に先頭パケットと２番目のパケットの２つ分のパケットについての中間データが記憶されるようにしておき、デキュー指示の発生したキュー＃ｉの２番目のパケットについての中間データを先頭パケットについての中間データとして後計算部５へ出力するので、デキューされなかったキュー＃ｋの先頭パケットの情報とデキューされたキュー＃ｉの２番目のパケットの情報とを同時に、後段の処理に入力でき、キュー管理部２手段と前計算部３の処理遅延を隠蔽できる。
【０１０９】
また、デキューされたキュー＃ｉの２番目のパケットについての中間データに基づいて後計算部５で求められたデータ（理想出力時刻Ｆｉ）をバイパス制御部６により合流制御部８へバイパスすることにより、常に、各キュー＃ｉの理想出力時刻Ｆｉの比較に有効なデータをパイプライン段数１段分の処理時間ｐτ間隔で合流制御部８に入力することができるので、最小値選択部７での処理遅延時間を隠蔽できる。
【０１１０】
従って、異なるキュー＃ｉに対するデキュー指示（DeQueueNo=i）が連続して発生する場合、同じキュー＃ｉに対するデキュー指示（DeQueueNo=i）が連続して発生する場合のいずれの場合においても、合流制御部８では、デキュー指示の無かったキュー＃ｋの先頭パケットと、デキュー指示のあったキュー＃ｉの次のパケットとについて理想出力時刻比較を必ずｐτ毎に行なうことができ、常に、約ｐτ毎にパケットのデキューを実施することができる。
【０１１１】
この結果、デキュー指示（DeQueueNo=i）により、次の出力パケット算出（決定）までの時間を、従来の約３×ｐτから約ｐτの１／３に短縮でき、約３倍のスループットの向上を実現することが可能である。
また、デキュー指示（DeQueueNo=i）が発生したときには、中間結果記憶部４のキュー＃ｉに対応する先頭パケットについての中間データと、バイパス制御部６で保持されているキュー＃ｉに対応する理想出力時刻Ｆｉとをそれぞれ無効にするので、デキュー済みのパケットに対して重複してデキュー指示（DeQueueNo=i）が発生してしまうことを確実に回避することができ、本パケット・スケジューラの信頼性の向上にも大いに寄与する。
【０１１２】
（Ｂ）その他
なお、上述したパケット・スケジューラ１は、図１８に示すように、搭載先のネットワーク中継装置（パケット転送装置）１１に、複数の異なる転送レートのインタフェース（パケットインタフェース）１１−１〜１１−６（ＩＦ１〜ＩＦ６；２．５Ｇｂｐｓ×４，１０Ｇｂｐｓ×２）が装備されている場合、図１９に示すように上述した各部２〜８を１τで処理可能な複数のパイプライン処理ステージ（Ａ１〜Ａ４，Ｂ１〜Ｂ４，Ｃ１〜Ｃ４）に分割し、図２０に示すように、１τ毎のタイムスロットで、ＩＦ５→ＩＦ１→ＩＦ６→ＩＦ２→ＩＦ５→ＩＦ３→ＩＦ６→ＩＦ４という具合に、共有メモリ９′（図１８参照）に保持された異なるインタフェースのパケットについてのパイプライン処理を実施するようにしてもよい。ただし、この場合、各パイプライン処理ステージ間にフリップフロップ（ＦＦ）回路などを設けてパイプライン処理の同期制御を行なう必要がある。
【０１１３】
このようにすれば、１つのパケット・スケジューラ１で、複数の異なる転送レートのインタフェース１１−１〜１１−６について、上述した実施形態と同様の処理を実現することができるので、ネットワーク中継装置１１の大幅な小型化及び性能向上に大きく寄与する。
また、上述した実施形態では、中間結果記憶部４とバイパス制御部６の双方を設けているが、バイパス制御部６を省略した構成にしたとしても、従来（図２１参照）に比して約２倍程度の処理速度（スループット）の向上を望める。さらに、上述した実施形態では、中間結果記憶部４に記憶しておくパケット数を“２”としているが、勿論、３以上にしてもよい。
【０１１４】
そして、本発明は、上述した実施形態に限定されるものではなく、上記以外にも本発明の趣旨を逸脱しない範囲で種々変形して実施することができる。
【０１１５】
【発明の効果】
以上詳述したように、本発明のパケット・スケジューラによれば、少なくとも、各キューから最初に出力されるべき第１パケットデータの理想出力時刻計算に必要な第１中間データと、その次に出力されるべき第２パケットデータについての理想出力時刻計算に必要な第２中間データとを記憶しておき、最優先に送信すべきと決定された第１パケットデータと同じキューに属する第２パケットデータについての第２中間データを、そのキューの新たな第１パケットデータについての第１中間データとして他のキューに属する第１パケットデータの第１中間データとともに後計算手段へ出力するので、後計算手段での理想出力時刻計算までの処理遅延を隠蔽できて、その処理速度（スループット）を大幅に向上することができる（請求項１）。
【０１１６】
ここで、上述のごとく最優先に送信すべきと決定された第１パケットデータについての第１中間データは無効にするのが好ましく、このようにすれば、同じ第１パケットデータが重複して最優先に送信すべきパケットデータとして決定されてしまうことを確実に回避することができるので、本パケット・スケジューラの信頼性の向上に大きく寄与する（請求項２）。
【０１１７】
また、上述のごとく第２パケットデータについての第２中間データを新たな第１パケットデータについての第１中間データとして後計算手段へ出力した場合、上記の第２パケットデータの次に出力されるべき第３パケットデータの理想出力時刻計算に必要な第３中間データを、新たな第２パケットについての第２中間データとして記憶するようにしておけば、次回の理想出力時刻の計算までに必要なデータを確保しておくことができるので、理想出力時刻計算までの処理遅延をさらに効果的に隠蔽できる（請求項３）。
【０１１８】
さらに、後計算手段において計算された第２パケットデータの理想出力時刻情報をバイパスするバイパス制御手段をそなえることにより、それ以外の第１パケットデータの理想出力時刻情報と同時に上記の第２パケットデータの理想出力時刻情報を合流制御手段へ入力できるようにすることで、異なるキューのパケットデータが最優先に送信されるべきデータとあると連続して決定される場合、同じキューのパケットデータが最優先に送信されるべきデータであると連続して発生する場合のいずれにおいても、理想出力時刻情報の選択を一定時間間隔で行なうことができ、さらに、本パケット・スケジューラの処理速度（スループット）を大幅に向上することができる（請求項４，５）。
【０１１９】
ここで、上記のバイパス制御手段は、最優先に送信すべきと決定した第１パケットデータについての理想出力時刻情報を無効にするように構成するのが好ましく、このようにすれば、やはり、同じ第１パケットデータが重複して最優先に送信すべきパケットデータとして決定されてしまうことを確実に回避することができるので、本パケット・スケジューラの信頼性の向上に大きく寄与する（請求項６）。
【０１２０】
ところで、本パケット・スケジューラは、複数のパケットインタフェースについての送信待ちのパケットデータをそれぞれ出力保証帯域の設定が可能な複数のキューにより各パケットインタフェース毎に管理する場合、上記の各手段を複数のパイプライン処理ステージに分割し、これらのパイプライン処理ステージが、それぞれ、一定時間毎に異なるパケットインタフェースについての処理を行なうように構成してもよい。このようにすれば、１つのパケット・スケジューラで、上記と同様の処理を実現することができるので、搭載先装置の大幅な小型化及び性能向上に大きく寄与する（請求項７）。
【図面の簡単な説明】
【図１】本発明の一実施形態としてのパケット・スケジューラの構成を示すブロック図である。
【図２】図１に示すパケット・スケジューラの詳細構成例を示すブロック図である。
【図３】図２に示すバイパス制御回路の構成例を示すブロック図である。
【図４】図３に示す状態制御部の動作を説明するための状態遷移図である。
【図５】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理）を説明するためのブロック図である。
【図６】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；初期状態からデキュー指示が発生するまで）を説明するためのブロック図である。
【図７】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；初期状態からデキュー指示が発生するまで）を説明するためのブロック図である。
【図８】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；初期状態からデキュー指示が発生するまで）を説明するためのブロック図である。
【図９】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；同じキューに対し連続してデキュー指示が発生する場合）を説明するためのブロック図である。
【図１０】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；同じキューに対し連続してデキュー指示が発生する場合）を説明するためのブロック図である。
【図１１】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；同じキューに対し連続してデキュー指示が発生する場合）を説明するためのブロック図である。
【図１２】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；同じキューに対し連続してデキュー指示が発生する場合）を説明するためのブロック図である。
【図１３】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；同じキューに対し連続してデキュー指示が発生する場合）を説明するためのブロック図である。
【図１４】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；異なるキューに対しデキュー指示が発生する場合）を説明するためのブロック図である。
【図１５】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；異なるキューに対しデキュー指示が発生する場合）を説明するためのブロック図である。
【図１６】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；異なるキューに対しデキュー指示が発生する場合）を説明するためのブロック図である。
【図１７】図１及び図２に示すパケット・スケジューラの動作（パイプライン処理；異なるキューに対しデキュー指示が発生する場合）を説明するためのタイムチャートである。
【図１８】本実施形態に係るパケット・スケジューラが適用されるネットワーク中継装置の一例を示すブロック図である。
【図１９】図１８に示すパケット・スケジューラのパイプライン構成例を示すブロック図である。
【図２０】図１９に示すパケット・スケジューラの動作を説明するためのタイムスロット割り当て例を示す図である。
【図２１】ＷＦＱを用いたパケット・スケジューラの一例を示すブロック図である。
【符号の説明】
１  パケット・スケジューラ
２  キュー管理部
３  前計算部
４  中間結果記憶部
５  後計算部
６  バイパス制御部
７  最小値選択部
８  合流制御部
９  パケットメモリ
９′  共有メモリ
１０  最小値決定処理部（送信パケットデータ決定手段）
１１  ネットワーク中継装置（パケット転送装置）
１１−１〜１１−６  パケットインタフェース
２１  エンキュー処理部
２２  キュー記憶部
２３  デキュー処理部
２４  エンキュー・デキュー調停部
２５  タイマ
３１  γ計算部
３２  β計算部
４１−１〜４１−ｎ  中間データ記憶部
４２  中間データ読み出し制御部
５１−１〜５１−ｎ  Ｆ計算部
５２  β×γ計算部
５３  α計算部
５４  加算部
６１−１〜６１−ｎ  バイパス制御回路
６２  一時記憶部（メモリ部）
６３  選択部（バイパス選択手段）
６４  状態制御部
７１  比較器
２２１  キュー管理テーブル
３１１，３２１  ＲＡＭ
３１２  γ演算器（加算器）
３２２  乗算器
【図１】
0004199414.tif 000004
【図２】
0004199414.tif 000005
【図３】
0004199414.tif 000006
【図４】
0004199414.tif 000007
【図５】
0004199414.tif 000008
【図６】
0004199414.tif 000009
【図７】
0004199414.tif 000010
【図８】
0004199414.tif 000011
【図９】
0004199414.tif 000012
【図１０】
0004199414.tif 000013
【図１１】
0004199414.tif 000014
【図１２】
0004199414.tif 000015
【図１３】
0004199414.tif 000016
【図１４】
0004199414.tif 000017
【図１５】
0004199414.tif 000018
【図１６】
0004199414.tif 000019
【図１７】
0004199414.tif 000020
【図１８】
0004199414.tif 000021
【図１９】
0004199414.tif 000022
【図２０】
0004199414.tif 000023
【図２１】
0004199414.tif 000024