JP4118757B2

JP4118757B2 - Weighted priority control method

Info

Publication number: JP4118757B2
Application number: JP2003194998A
Authority: JP
Inventors: 信司古谷
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 2003-07-10
Filing date: 2003-07-10
Publication date: 2008-07-16
Anticipated expiration: 2023-07-10
Also published as: JP2005033408A

Description

【０００１】
【発明の属する技術分野】
本発明は、通信装置の帯域制御方法に関するものであり、特に、回線にデータを出力する際に、回線交換処理と同時に帯域制御を行う重み付け優先制御方法に関するものである。
【０００２】
【従来の技術】
データを出力する１つの出力先、たとえば、回線の直前に設置された複数の待ち行列（キュー）それぞれに設定された重み付けの値にしたがって、各キューのデータに対して回線の帯域のうちの一定の割合の帯域を保証するためのアルゴリズムとして、重み付けラウンドロビン（ＷＲＲ：Weighted Round Robin）方式や重み付けフェアキューイング（ＷＦＱ：Weighted Fair Queuing）方式がある。
【０００３】
ＷＲＲ方式は、データを読み出すキューの順番を予め決めておき、その順番にしたがって、各キューから順次データを読み出していくラウンドロビン（回転優先制御）を行う際に、各キューに重み付けの値を設定しておき、データを読み出すごとに重み付けの値をデクリメントしていく。そして、重み付けの値が「０」になったキューからはデータを読み出さずに、つぎのキューのデータを読み出すことで、各キューから出力するデータの出力頻度を制御して、一定の割合の帯域を保証するものである。したがって、特にＡＴＭ（Asynchronous Transfer Mode）のセルなど固定長のデータを扱う場合、デクリメントと重み付けの値が設定可能なカウンタで実現可能であり、ハードウエアで構成するにあたっても、非常に簡単かつ小規模な回路で実現することができる。
【０００４】
このような理由から、ＷＲＲ方式を用いた装置の実装や機能に様々な拡張や工夫をこらした技術が考えられている。第１の従来技術では、優先インデックスを用いたアルゴリズムを基本とし、優先インデックステーブルを用いた構成に対して、優先ソートリストを設けて、実際のパケット転送シーケンス（ラウンド）ごとに、全フローあるいは所定フローを優先インデックスの大きい順（降順）に格納し、この優先ソートリスト内の先頭の各フローから順にパケットを転送し、その後、優先ソートリスト外の各フローからパケットを転送するようにして、ＷＲＲ方式の問題である遅延ジッタ性能を向上するようにしている（たとえば、特許文献１参照）。
【０００５】
また、第２の従来技術では、セルバッファ回路にセルがないときには有意のセル有無フラグを送出するセル有無フラグ出力回路と、カウントメモリの対応するカウント値が減算され「０」になったときに有意のウエイト有無フラグを送出するウエイト有無フラグ送出回路と、セル有無フラグまたはウエイト有無フラグの何れか一方または両方が有意である時に一斉に有意のカウント初期化フラグを送出するカウント初期化フラグ送出回路とをセルバッファ毎に備え、各セルバッファ回路の中の１つのセルバッファ回路を選択してセルを出力する時に、対応するカウント初期化フラグが有意の場合、対応するカウンタ値のみを初期化するようにして、カウンタ値の初期化する時間の制約をなくすことで、セルバッファ回路の数に関係なくメモリを使用してカウンタを構成することができるようにしている。（たとえば、特許文献２参照）。
【０００６】
【特許文献１】
特開平１１−２９８５２３号公報
【特許文献２】
特開２０００−２７８２７２号公報
【０００７】
【発明が解決しようとする課題】
上記第１の従来技術では優先インデックスを用いたアルゴリズムを、上記第２の技術ではＷＲＲ方式のアルゴリズムを用いている。すなわち、上記従来技術は両者とも、それ自体が１つのアルゴリズムの体を成しており、つぎに読み出すべきキューを選択するのは、そのアルゴリズムが唯一であるという環境のみに適合する。そのため、上記２つの従来技術では、つぎに読み出すべきキューを選択するアルゴリズムが２つである場合、不都合が生じることがある。
【０００８】
たとえば、一般的に、ネットワーク上に流れるデータは、帯域制御の要求の通りに流れるわけではない。ネットワーク上に流れるデータをミクロな時間単位で見ると、あるところにデータが集中して帯域制御の要求する通りにデータを読み出していたのでは、キューからデータがあふれてしまい、あふれたデータは破棄される。
【０００９】
このような場合、ＲＥＤ（Random Early Detection）により破棄が１つのデータ系列に集中しないようにするのが一般的であるが、データを破棄しないに越したことはない。そこで、「キューからデータがあふれる前にデータが集中しているキューを検知して、検知したキューのデータを優先的に回線に出力する」というアルゴリズムを上記２つの従来技術に追加したとする。すなわち、ＷＲＲ方式などの帯域制御を維持するアルゴリズムと、それとは別につぎに読み出すべきキューを選択する（この場合は、データが集中しているキューを選択する）アルゴリズムとがあるとする。これら２つのアルゴリズムがそれぞれに選択したキューが異なり、帯域制御を維持するアルゴリズムとは異なるアルゴリズムが選択したキューからデータを読み出した場合、上記２つの従来技術では、帯域制御の効果そのものを失わないための手順は検討されていない。
【００１０】
そのため、上記２つの従来技術では、キューの状況に応じて帯域制御を維持するアルゴリズムと、それとは別のアルゴリズムとを使い分ける必要がある場合、帯域制御の精度を維持することはできないという問題があった。
【００１１】
この発明は上記に鑑みてなされたもので、帯域制御を維持するアルゴリズムと、それとは異なるアルゴリズムとを有し、帯域制御を維持するアルゴリズムとは異なるアルゴリズムにより選択されたキューからデータを読み出した場合でも、帯域制御を維持するアルゴリズムの帯域の精度を維持することができる重み付け優先制御方法を得ることを目的としている。
【００１２】
【課題を解決するための手段】
上記目的を達成するために、この発明にかかる重み付け優先制御方法は、複数のキュー・バッファに蓄積されているデータを前記複数のキュー・バッファ毎に割り付けられている重み付けの値の割合で各キュー・バッファから読み出して前記データの帯域を保証する重み付け優先制御方法であって、前記重み付けの値を初期値とし、各キュー・バッファからのデータ読み出しの度に算出される優先度に基づき前記複数のキュー・バッファの優先順位を決定し、決定した優先順位に従ってデータを読み出すキュー・バッファを選択することにより、前記データの帯域を保証する第１のアルゴリズムと、この第１のアルゴリズムとは異なる処理によってデータを読み出すキュー・バッファを選択する第２のアルゴリズムとを有し、前記第１および第２のアルゴリズムによって選択されたキュー・バッファが異なる場合には、所定の条件が成立する以外の場合前記第２のアルゴリズムによって選択されたキュー・バッファを優先するとともに、前記優先するキュー・バッファ以外のすべてのキュー・バッファの第１のアルゴリズムにおける優先度を上げる処理を行う事を特徴とする。
【００１３】
この発明によれば、各キュー・バッファごとに割り付けられた重み付けの値を初期値とし、各キュー・バッファからのデータ読み出しの度に算出される優先度に基づき複数のキュー・バッファの優先順位を決定し、決定した優先順位に従ってデータを読み出すキュー・バッファを選択することによりデータの帯域を保証する第１のアルゴリズムによって選択されたキュー・バッファと、第１のアルゴリズムとは異なる処理によってデータを読み出すキュー・バッファを選択する第２のアルゴリズムによって選択されたキュー・バッファとが異なる場合には、所定の条件が成立する場合を除いて、第２のアルゴリズムによって選択されたキュー・バッファを優先するとともに、優先するキュー・バッファ以外のすべてのキュー・バッファの優先度を上げるようにしている。ただし、第２のアルゴリズムによって選択されたキュー・バッファを優先して、優先するキュー・バッファ以外の全てのキュー・バッファの優先度を上げる場合、実装上は優先度を上げる限度がある。この場合、キュー・バッファの優先度が限度を超えた場合を所定の条件として、優先度が限度値を超えた場合には第１のアルゴリズムによって選択されたキュー・バッファを優先することにより、実装上の問題を解決するとともに、第２のアルゴリズムによって選択されたキュー・バッファを選択し続けて帯域保証が維持できなくなるという現象を防ぐことができる。
【００１４】
【発明の実施の形態】
以下に添付図面を参照して、この発明にかかる重み付け優先制御方法の好適な実施の形態を詳細に説明する。
【００１５】
実施の形態１．
図１〜図５を用いて本発明の実施の形態１を説明する。図１は、この発明における実施の形態１の重み付け優先制御方法に基づいて動作する重み付け優先制御装置の構成を示すブロック図である。図１に示した重み付け優先制御装置は、一定量のデータ（パケット）を蓄積する複数（この場合は３つ）のキュー・バッファ１１〜１３と、予め定められた２つの異なるアルゴリズムのうちの一方のアルゴリズムに基づいてキュー・バッファ１１〜１３の１つを選択するキュー制御部３０と、キュー制御部３０が選択したキュー・バッファのパケットを読み出し、回線に出力する多重化部２０とを備えている。
【００１６】
キュー制御部３０は、重み付けによる帯域制御を行い回線の帯域の一定量の割合を保証する第１のアルゴリズムと、帯域制御とは異なるアルゴリズムによりパケットを読み出すべきキュー・バッファを決定する第２のアルゴリズムとを有し、キュー・バッファ１１〜１３を監視して、キュー・バッファ１１〜１３の状態に基づいて、第１のアルゴリズムで選択したキュー・バッファと第２のアルゴリズムで選択したキュー・バッファのどちらを優先するかを選択する。そして、選択したキュー・バッファを多重化部２０に通知する。
【００１７】
第１のアルゴリズムは、複数のキュー・バッファそれぞれに設定された重み付けの値を初期値とし、各キュー・バッファからのデータ読み出しの度に算出される優先度に基づき複数のキュー・バッファの優先順位を決定し、決定した優先順位に従ってデータを読み出すキュー・バッファを選択することにより、データの帯域を保証するアルゴリズムであり、ここではＷＲＲ方式とする。
【００１８】
第２のアルゴリズムは、キュー・バッファからパケットがあふれる前にデータが集中しているキュー・バッファを検知して、検知したキュー・バッファのパケットを優先的に回線に出力するアルゴリズムである。
【００１９】
キュー制御部３０は、キュー・バッファ１１〜１３に対応した重み付けの値をカウントするカウンタ３１〜３３と、キュー・バッファ１１〜１３がそれぞれ保持するパケットの合計パケット長を監視するキュー監視部３４と、つぎにパケットを読み出すべきキュー・バッファを選択するキュー選択部３５と、キュー・バッファ１１〜１３の重み付けの値に基づいてそれぞれの優先度を算出する重み付け演算部３６とを備えている。
【００２０】
キュー監視部３４は、キュー・バッファ１１〜１３がそれぞれに蓄積するパケットの合計パケット長が予め定められた閾値を超えていないかを監視する。そして、蓄積したパケットの合計パケット長が閾値を超えているキュー・バッファを検出した場合、検出したキュー・バッファを識別するための情報を含む超過情報をキュー選択部３５に出力する。
【００２１】
キュー選択部３５は、第１のアルゴリズムまたは第２のアルゴリズムに基づいてつぎにパケットを読み出すべきキュー・バッファを選択して、選択したキュー・バッファのパケットを読み出すように多重化部２０に通知する。キュー選択部３５は、キュー監視部３４から超過情報の通知を受けた場合、第２のアルゴリズムに基づいて選択したキュー・バッファを第１のアルゴリズムに基づいて選択したキュー・バッファよりも優先して多重化部２０に通知する。そして、第２のアルゴリズムに基づいてキュー・バッファを選択した際に、選択したキュー・バッファに対応するカウンタのカウント値（優先度）がマイナスの値になると、重み付け演算部３６に重み付けの値を算出するように通知する。
【００２２】
第１のアルゴリズムの場合、キュー選択部３５は、パケットが蓄積されているキュー・バッファに対応するカウンタのカウント値が「０」でないものをラウンドロビンによって検索し、最初に検出したカウンタに対応するキュー・バッファをパケット読み出し対象のキュー・バッファとして選択する。この場合は、カウンタ３１、カウンタ３２、カウンタ３３、カウンタ３１の順（ラウンドロビン方向）にカウント値を確認する。キュー選択部３５は、最後に選択したキュー・バッファを記憶しておき、つぎにパケットを読み出すべきキュー・バッファを選択する際には、記憶しているキュー・バッファに対応するカウンタのカウント値を確認する。そして、カウント値が「０」の場合は、順次ラウンドロビン方向のカウンタの値を確認し、カウント値が「０」でないカウンタに対応するキュー・バッファを選択する。
【００２３】
第２のアルゴリズムの場合、キュー選択部３５は、キュー監視部３４から通知された超過情報内のキュー・バッファを選択する。ただし、同一のキュー・バッファを選択する超過情報が連続してきた場合には、予め定められた一定の回数を限度に超過情報により通知されたキュー・バッファを連続して選択する。
【００２４】
カウンタ３１〜３３は、各カウンタに対応したキュー・バッファが選択されてパケットが回線に出力された場合、カウント値をデクリメントする。ここでは、カウンタ３１がキュー・バッファ１１に、カウンタ３２がキュー・バッファ１２に、カウンタ３３がキュー・バッファ１３にそれぞれ対応する。
【００２５】
重み付け演算部３６は、カウンタ３１〜３３のカウント値がすべて「０」になると、予め定められたキュー・バッファ１１〜１３の重み付けの値を各カウンタに設定する。また、第２のアルゴリズムにより選択したキュー・バッファに対応するカウンタのカウント値がマイナスになると、各カウンタのカウント値に予め定められた重み付けの値を加算した値を各カウンタに設定する。すなわち、マイナスになったカウンタのカウント値をプラスにするために、各カウンタのカウント値にそれぞれの重み付けの値を加算して、第１のアルゴリズムによる帯域制御の重み付けの比率を維持するようにする。
【００２６】
図２〜図５は、キュー・バッファ１１〜１３に蓄積されているパケットと、カウンタ３１〜３３の値と、キュー選択部３５が選択したキュー・バッファのパケットを多重化部２０が読み出して、読み出したパケットを回線４０に出力した様子を示す図である。図２〜図５を参照して、この発明における実施の形態１の重み付け優先制御方法に基づいて動作する重み付け優先制御装置の動作を説明する。ここでは、キュー・バッファ１１の重み付けの値を「１」、キュー・バッファ１２の重み付けの値を「３」、キュー・バッファ１３の重み付けの値を「２」とし、キュー・バッファ１１〜１３に蓄積されるパケットの長さは全て同一（固定長）であるものとする。
【００２７】
まず、図２および図３を参照して、第１のアルゴリズムに基づいてパケットを出力する動作を説明する。図２（ａ）において、キュー・バッファ１１はパケットＡ１〜Ａ４を、キュー・バッファ１２はパケットＢ１〜Ｂ５を、キュー・バッファ１３はパケットＣ１〜Ｃ４をそれぞれ蓄積しており、カウンタ３１には「１」が、カウンタ３２には「３」が、カウンタ３３には「２」が設定されている。すなわち、カウンタ３１〜３３には、重み付けの値が優先度の初期値として重み付け演算部３６により設定されている。また、キュー監視部３４に予め定められている閾値は、点線で示したようにここではパケット６個分のパケット長とする。
【００２８】
キュー・バッファ１１〜１３に蓄積されているパケットの合計パケット長が各キュー・バッファとも閾値を超えていないので、キュー選択部３５は第１のアルゴリズムに基づいてキュー・バッファを選択する。キュー選択部３５は、キュー・バッファ１１の優先度を示すカウンタ３１のカウント値を確認する。カウンタ３１のカウント値は「１」であるので、キュー選択部３５はキュー・バッファ１１を選択して、キュー・バッファ１１のパケットを読み出すように多重化部２０に通知する。
【００２９】
図２（ｂ）に示すように、多重化部２０は、キュー・バッファ１１のパケットＡ１を読み出して、読み出したパケットＡ１を回線４０に出力する。キュー選択部３５がキュー・バッファ１１を選択したので、カウンタ３１はカウント値をデクリメントして、カウント値を「０」にする。
【００３０】
キュー・バッファ１１を選択したので、キュー選択部３５は、キュー・バッファ１２に対応するカウンタ３２のカウント値を確認する。カウンタ３２のカウント値は「３」であるので、キュー選択部３５はキュー・バッファ１２を選択して、キュー・バッファ１２のパケットを読み出すように多重化部２０に通知する。
【００３１】
図２（ｃ）に示すように、多重化部２０は、キュー・バッファ１２のパケットＢ１を読み出して、読み出したパケットＢ１を回線４０に出力する。キュー選択部３５がキュー・バッファ１２を選択したので、カウンタ３２はカウント値をデクリメントして、カウント値を「２」にする。
【００３２】
キュー・バッファ１２を選択したので、キュー選択部３５は、キュー・バッファ１３に対応するカウンタ３３のカウント値を確認する。カウンタ３３のカウント値は「２」であるので、キュー選択部３５はキュー・バッファ１３を選択して、キュー・バッファ１３のパケットを読み出すように多重化部２０に通知する。
【００３３】
図２（ｄ）に示すように、多重化部２０は、キュー・バッファ１３のパケットＣ１を読み出して、読み出したパケットＣ１を回線４０に出力する。キュー選択部３５がキュー・バッファ１３を選択したので、カウンタ３３はカウント値をデクリメントして、カウント値を「１」にする。
【００３４】
キュー・バッファ１３を選択したので、キュー選択部３５は、カウンタ３１のカウント値を確認する。カウンタ３１のカウント値は「０」である。そのため、キュー選択部３５は、ラウンドロビン方向でカウンタ３１のつぎのカウンタ３２のカウント値を確認する。カウンタ３２のカウント値は「２」であるので、キュー選択部３５は、キュー・バッファ１２を選択して、キュー・バッファ１２のパケットを読み出すように多重化部２０に通知する。
【００３５】
図２（ｅ）に示すように、多重化部２０は、キュー・バッファ１２のパケットＢ２を読み出して、読み出したパケットＢ２を回線４０に出力する。キュー選択部３５がキュー・バッファ１２を選択したので、カウンタ３２はカウント値をデクリメントして、カウント値を「１」にする。
【００３６】
キュー・バッファ１２を選択したので、キュー選択部３５は、キュー・バッファ１３に対応するカウンタ３３のカウント値を確認する。カウンタ３３のカウント値は「１」であるので、キュー選択部３５はキュー・バッファ１３を選択して、キュー・バッファ１３のパケットを読み出すように多重化部２０に通知する。
【００３７】
図３（ｆ）に示すように、多重化部２０は、キュー・バッファ１３のパケットＣ２を読み出して、読み出したパケットＣ２を回線４０に出力する。キュー選択部３５がキュー・バッファ１３を選択したので、カウンタ３３はカウント値をデクリメントして、カウント値を「０」にする。
【００３８】
キュー・バッファ１３を選択したので、キュー選択部３５は、キュー・バッファ１１に対応するカウンタ３１のカウント値を確認する。カウンタ３１のカウント値は「０」であるので、キュー選択部３５は、ラウンドロビン方向でカウンタ３１のつぎのカウンタ３２のカウント値を確認する。カウンタ３２のカウント値は「１」であるので、キュー選択部３５はキュー・バッファ１２を選択して、キュー・バッファ１２のパケットを読み出すように多重化部２０に通知する。
【００３９】
図３（ｇ）に示すように、多重化部２０は、キュー・バッファ１２のパケットＢ３を読み出して、読み出したパケットＢ３を回線４０に出力する。キュー選択部３５がキュー・バッファ１２を選択したので、カウンタ３２はカウント値をデクリメントして、カウント値を「０」にする。
【００４０】
ここで、カウンタ３１〜３３のそれぞれのカウント値が全て「０」となる。キュー選択部３５は、カウンタ３３、カウンタ３１、カウンタ３２の順に各カウンタのカウント値を確認して、各カウンタのカウント値が「０」であることを確認すると、重み付け演算部３６に初期値を設定するように通知する。
【００４１】
通知を受けると重み付け演算部３６は、予め定められたキュー・バッファ１１〜１３の重み付けの値をカウンタ３１〜３３に設定する。キュー・バッファ１１の重み付けが「１」、キュー・バッファ１２の重み付けが「３」、キュー・バッファ１３の重み付けが「２」であるので、重み付け演算部３６は、図３（ｈ）に示すように、カウンタ３１に「１」を、カウンタ３２に「３」を、カウンタ３３に「２」を設定する。
【００４２】
重み付け演算部３６がカウンタ３１〜３３に新たにカウント値を設定した後、キュー選択部３５は、ラウンドロビン方向に順にカウンタ３１〜３３のカウント値を確認して、カウント値が「０」でない場合には、そのカウンタに対応するキュー・バッファを選択し、カウント値が「０」の場合には、つぎのカウンタのカウント値を確認する。多重化部２０は、キュー選択部３５が選択したキュー・バッファのパケットを読み出して回線４０に出力する動作を繰り返す。図３（ｊ）、図３（ｋ）および図３（ｍ）はその様子を示している。
【００４３】
つぎに、図４および図５を参照して、キュー・バッファ１１に蓄積されたパケットが予め定められた閾値を超えた場合を例にあげて、重み付け優先制御装置が第２のアルゴリズムに基づいてパケットを出力する動作を説明する。ここでは、第２のアルゴリズムにより同一のキュー・バッファを連続して選択する限度を４回とする。
【００４４】
図４（ａ）において、キュー・バッファ１１は、パケットＡ１〜Ａ５を、キュー・バッファ１２はパケットＢ１〜Ｂ５を、キュー・バッファ１３はパケットＣ１〜Ｃ５をそれぞれ蓄積しており、カウンタ３１には「１」が、カウンタ３２には「３」が、カウンタ３３には「２」が設定されている。すなわち、カウンタ３１〜３３には、キュー・バッファ１１〜１３の重み付けの値が初期値として重み付け演算部３６により設定されている。また、キュー監視部３４に予め定められている閾値は、点線で示したようにここではパケット６個分のパケット長とする。
【００４５】
キュー・バッファ１３〜３３に蓄積されているパケットの量は、それぞれ５つで閾値を超えていないので、キュー選択部３５は第１のアルゴリズムに基づいてキュー・バッファを選択する。キュー選択部３５は、カウンタ３２のカウント値が「３」であることを確認して、キュー・バッファ１２を選択する。図４（ｂ）に示すように、多重化部２０は、キュー・バッファ１２のパケットＢ１を読み出して、読み出したパケットＢ１を回線４０に出力する。キュー選択部３５がキュー・バッファ１２を選択したので、カウンタ３２はカウント値をデクリメントして、カウント値を「２」にする。また、パケットＢ１を回線４０に出力している間に、キュー・バッファ１１にパケットＡ６〜Ａ９が、キュー・バッファ１２にパケットＢ６が新たに蓄積され、キュー・バッファ１１に蓄積されたパケットの合計パケット長が閾値を超えたとする。キュー監視部３４は、キュー・バッファ１１に蓄積されたパケットの量が閾値を超えたことを検知して、キュー・バッファ１１が閾値を超えたことを通知するための超過情報をキュー選択部３５に出力する。
【００４６】
キュー・バッファ１２を選択したので、本来、キュー選択部３５は、カウンタ３３のカウント値が「２」であることを確認してキュー・バッファ１３を選択する。しかし、キュー監視部３４から超過情報が通知されたため、通知された超過情報に含まれるキュー・バッファ１１を選択する。すなわち、第１のアルゴリズムに基づいて選択したキュー・バッファ１２ではなく、第２のアルゴリズムに基づいて選択したキュー・バッファ１１を優先して、キュー・バッファ１１のパケットを読み出すように多重化部２０に通知する。
【００４７】
図４（ｃ）に示すように、多重化部２０は、キュー・バッファ１１のパケットＡ１を読み出して、読み出したパケットＡ１を回線４０に出力する。キュー選択部３５がキュー・バッファ１１を選択したので、カウンタ３１はカウント値をデクリメントして、カウント値を「０」にする。
【００４８】
キュー・バッファ１１に蓄積されているパケットの合計パケット長は「８」となるが、まだ閾値を超えている。キュー監視部３４は、キュー・バッファ１１が閾値を超えていることを超過情報によりキュー選択部３５に通知する。キュー選択部３５は、通知された超過情報に含まれるキュー・バッファ１１を選択して、キュー・バッファ１１のパケットを読み出すように多重化部２０に通知する。
【００４９】
図４（ｄ）に示すように、多重化部２０は、キュー・バッファ１１のパケットＡ２を読み出して、読み出したパケットＡ２を回線４０に出力する。キュー選択部３５がキュー・バッファ１１を選択したので、カウンタ３１はカウント値をデクリメントして、カウント値を「−１」にする。
【００５０】
カウンタ３１のカウント値が「−１」になると、重み付け演算部３６は、各カウンタのカウント値に予め定められた重み付けの値を加算した値を各カウンタに設定する。キュー・バッファ１１の重み付けの値は「１」、キュー・バッファ１２の重み付けの値は「３」、キュー・バッファ１３の重み付けの値は「２」であり、カウンタ３１のカウント値は「−１」、カウンタ３２のカウント値は「２」、カウンタ３３のカウント値は「２」である。重み付け演算部３６は、図４（ｅ）に示すように、カウンタ３１のカウント値「−１」とキュー・バッファ１１の重み付けの値「１」を加算した値「０」をカウンタ３１に、カウンタ３２のカウント値「２」とキュー・バッファ１２の重み付けの値「３」を加算した値「５」をカウンタ３１に、カウンタ３３のカウント値「２」とキュー・バッファ１３の重み付けの値「２」を加算した値「４」をカウンタ３３に、それぞれ設定する。
【００５１】
キュー・バッファ１１に蓄積されているパケットの合計パケット長は「７」となるが、まだ閾値を超えている。キュー監視部３４は、キュー・バッファ１１が閾値を超えていることを超過情報によりキュー選択部３５に通知する。キュー選択部３５は、通知された超過情報に含まれるキュー・バッファ１１を選択して、キュー・バッファ１１のパケットを読み出すように多重化部２０に通知する。
【００５２】
図４（ｆ）に示すように、多重化部２０は、キュー・バッファ１１のパケットＡ３を読み出して、読み出したパケットＡ３を回線４０に出力する。キュー選択部３５がキュー・バッファ１１を選択したので、カウンタ３１はカウント値をデクリメントして、カウント値を「−１」にする。
【００５３】
カウンタ３１のカウント値が「−１」になると、重み付け演算部３６は、各カウンタのカウント値に予め定められた重み付けの値を加算した値を各カウンタに設定する。キュー・バッファ１１の重み付けの値は「１」、キュー・バッファ１２の重み付けの値は「３」、キュー・バッファ１３の重み付けの値は「２」であり、カウンタ３１のカウント値は「−１」、カウンタ３２のカウント値は「５」、カウンタ３３のカウント値は「４」である。重み付け演算部３６は、図５（ｇ）に示すように、カウンタ３１のカウント値「−１」とキュー・バッファ１１の重み付けの値「１」を加算した値「０」をカウンタ３１に、カウンタ３２のカウント値「５」とキュー・バッファ１２の重み付けの値「３」を加算した値「８」をカウンタ３１に、カウンタ３３のカウント値「４」とキュー・バッファ１３の重み付けの値「２」を加算した値「６」をカウンタ３３に、それぞれ設定する。キュー・バッファ１１に蓄積されているパケットの合計パケット長は「６」になり、閾値以下となる。キュー・バッファ１１に蓄積されているパケットの量が閾値以下になったので、キュー選択部３５は、第１のアルゴリズムに基づいてキュー・バッファを選択する。キュー・バッファ１１を選択していたので、キュー選択部３５は、カウンタ３２のカウント値を確認する。カウンタ３２の値は「８」であるので、キュー選択部３５は、キュー・バッファ１２を選択して、キュー・バッファ１２のパケットを読み出すように多重化部２０に通知する。
【００５４】
図５（ｈ）に示すように、多重化部２０は、キュー・バッファ１２のパケットＢ２を読み出して、読み出したパケットＢ２を回線４０に出力する。キュー選択部３５がキュー・バッファ１２を選択したので、カウンタ３２はカウント値をデクリメントして、カウント値を「７」にする。
【００５５】
その後、新たにキュー・バッファ１１〜１３にパケットが蓄積されても、キュー・バッファ１１〜１３のそれぞれに蓄積されたパケットの合計パケット長が閾値を超えなければ、キュー選択部３５は第１のアルゴリズムに基づいてキュー・バッファを選択する。第１のアルゴリズムでの動作については図２および図３を参照して説明したものと同様となるのでここでは詳細な動作の説明は省略する。
【００５６】
キュー選択部３５は、ラウンドロビン方向にカウンタ３１〜３３のカウント値が「０」でないものを検索し、最初に検出したカウンタに対応するキュー・バッファをパケット読み出し対象のキュー・バッファとして選択し、多重化部２０は、キュー選択部３５が選択したキュー・バッファのパケットを読み出して、読み出したパケットを回線４０に出力する。そして、キュー選択部３５が選択したキュー・バッファに対応するカウンタは、カウント値をデクリメントする。このような動作を、カウンタ３１〜３３のカウント値が全て「０」になるまで繰り返す。図５（ｈ）では、カウンタ３１のカウント値は「０」である。したがって、キュー・バッファ１２とキュー・バッファ１３に蓄積されているパケットが、それぞれのカウンタ３２、３３のカウント値が「０」になるまで、交互に回線４０に出力される。その様子を、図５（ｊ）、図５（ｋ）および図５（ｍ）に示す。そして、キュー・バッファ１１〜１３に蓄積されたパケットがなくなることなく、かつ、キュー・バッファ１１〜１３に蓄積されたパケットが閾値を超えることなくパケットが蓄積されたとすると、最終的には図５（ｎ）に示すように、カウンタ３１〜３３のカウント値全てが「０」となる。
【００５７】
カウンタ３１〜３３のカウント値が全て「０」になると、重み付け演算部３６は、予め定められたキュー・バッファ１１〜１３の重み付けの値をカウンタ３１〜３３に設定する。そして、キュー選択部３５は重み付けの値が設定されたカウンタ３１〜３３の値を用いてキュー・バッファを選択する。
【００５８】
ここで、実際に、カウンタ３１〜３３に重み付けの値が設定されてから、全てのカウンタのカウント値が「０」になるまでの期間に出力されたパケットが、キュー・バッファ１１〜１３に予め定められた重み付けの値である「１：３：２」の割合となっているかを確認する。図５（ｎ）に示すように、キュー・バッファ１１から出力されたパケットはＡ１〜Ａ３の３つであり、キュー・バッファ１２から出力されたパケットはＢ１〜Ｂ９の９つであり、キュー・バッファ１３から出力されたパケットはＣ１〜Ｃ６の６つである。したがって、各キュー・バッファから出力されたパケットの割合は、「３：９：６＝１：３：２」であり、重み付けの値である「１：３：２」が維持されていることがわかる。
【００５９】
このようにこの実施の形態１では、複数のキュー・バッファに蓄積されているデータに対して一定の割合の帯域を保証するために、予め定められた重み付けの値による優先度に基づいて複数のキュー・バッファの優先順位を決定してデータを読み出すキュー・バッファを選択する第１のアルゴリズムと、第１のアルゴリズムとは異なる第２のアルゴリズムによりデータを読み出すキュー・バッファを選択する第２のアルゴリズムがあり、これら２つのアルゴリズムにより選択したキュー・バッファが異なる場合には、第２のアルゴリズムにより選択したキュー・バッファを優先してデータを出力する。その際に、優先したキュー・バッファ以外の全てのキュー・バッファ優先度を上げるようにしているため、第２のアルゴリズムにより選択したキュー・バッファを優先した場合でも、第１のアルゴリズムの帯域保証の精度を維持することができる。
【００６０】
なお、説明を簡単にするために、第２のアルゴリズムによってキュー・バッファ１を選択する条件を閾値として説明したが、第２のアルゴリズムによってキュー・バッファ１を選択する条件にヒステリシスを用いてもよい。
【００６１】
また、この実施の形態１では、第２のアルゴリズムにより同一のキュー・バッファを連続して選択する限度を４回とした。したがって、たとえば、キュー・バッファ１１に蓄積されているパケットが閾値を超えた場合、キュー・バッファ１１から第２のアルゴリズムによって４回連続でパケットを読み出した後、さらにキュー・バッファ１１に蓄積されているパケットが閾値を超えていても、第１のアルゴリズムを優先することになる。しかし、第１のアルゴリズムを優先する条件はこれに限るものではなく、つぎのような条件も考えられる。
【００６２】
第２のアルゴリズムを優先したことにより、第２のアルゴリズムで選択されたキュー・バッファ以外のカウンタのカウント値は増加する。本発明では、このカウント値の増加の限度値を設定しておき、カウント値が限度値を超えた場合には、キュー監視部３４の要求に拘わらず、限度値を超えたカウンタに対応するキュー・バッファからパケットの読み出しを優先するか、全てのカウンタのカウント値が限度値以下になるまで第１のアルゴリズムによって選択されたキュー・バッファからパケットを読み出すようにしてもよい。カウンタ値の限度値は、各キュー・バッファの重み付けの値、システムに要求される性能、リソースとして実装されるキュー・バッファの深さにより決定すればよい。すなわち、第１のアルゴリズムおよび第２のアルゴリズムの達成度の折り合いは、そのシステムによって決定すればよい。このように、各カウンタのカウント値（優先度）が限度値までは第２のアルゴリズムを優先するが、優先度が限度値を超えた場合には帯域を保証する第１のアルゴリズムを優先することにより、実装時のカウンタのビット値を決定することができ、実装上の問題を解決することができるとともに、第２のアルゴリズムを守り続けて帯域保証が維持できなくなるという現象を防ぐことができる。
【００６３】
また、この実施の形態１では、第２のアルゴリズムを「キュー・バッファからパケットがあふれる前にデータが集中しているキュー・バッファを検知して、検知したキュー・バッファのパケットを優先的に回線に出力する」とした。しかし、第２のアルゴリズムはこれに限定されるものではなく、帯域を保証する帯域制御のアルゴリズムとは異なるものであればよい。たとえば、帯域制御のアルゴリズムと優先度が競合するものとして、入力バッファ型スイッチに帯域制御のアルゴリズムを追加した場合がある。この場合、入力バッファ型スイッチのスイッチ交換アルゴリズムと、帯域制御のアルゴリズムとが競合することがある。入力バッファ型スイッチは、Ｎ（Ｎは自然数）×Ｎポートの交換を行う際に、交換するデータの入力と出力のポートを常に「１：１」に接続しなければデータを流すことができない。つまり、複数の入力ポートから１つの出力ポートへ１回の交換でデータを転送することは不可能であり、交換アルゴリズムがスイッチのスループット性能に与える影響は大きい。そのため交換アルゴリズム性能を維持するのと、帯域制御を維持するのとでは、どちらを優先すべきかはシステム設計で決定すればよい。
【００６４】
実施の形態２．
図６〜図８を用いて本発明の実施の形態２を説明する。実施の形態１では、帯域制御のアルゴリズムとそれとは異なるアルゴリズムとをキュー・バッファの常態に応じて選択して固定長のパケットを回線に出力する際に、帯域制御の制度を維持するようにした。しかしながら、実際のシステムにおいて、パケットは固定長とは限らない。この実施の形態２では、キュー・バッファの状態に応じて帯域制御のアルゴリズムとそれとは異なるアルゴリズムとを選択して、可変長のパケットを回線に出力した際にも、帯域制御の精度を維持するものである。
【００６５】
図６は、この発明における実施の形態２の重み付け優先制御方法に基づいて動作する重み付け優先制御装置の構成を示すブロック図である。図６に示した重み付け優先制御装置は、図１に示した実施の形態１の重み付け優先制御装置のキュー制御部３０の変わりにキュー制御部３０ａを備えている。実施の形態１と同じ機能を持つ構成部分には同一符号を付し、重複する説明は省略する。
【００６６】
キュー制御部３０ａは、重み付けによる帯域制御を行い回線の帯域の一定量の割合を保証する第１のアルゴリズムと、帯域制御とは異なるアルゴリズムによりパケットを読み出すべきキュー・バッファを決定する第２のアルゴリズムとを有し、キュー・バッファ１１〜１３を監視して、キュー・バッファ１１〜１３の状態に基づいて、第１のアルゴリズムで選択したキュー・バッファと第２のアルゴリズムで選択したキュー・バッファのどちらを優先するかを選択する。そして、選択したキュー・バッファを多重化部２０に通知する。
【００６７】
第１のアルゴリズムは、複数のキュー・バッファそれぞれに設定された重み付けの値を初期値とし、各キュー・バッファからのデータ読み出しの度に算出される優先度に基づき複数のキュー・バッファの優先順位を決定し、決定した優先順位に従ってデータを読み出すキュー・バッファを選択することにより、データの帯域を保証するアルゴリズムである。
【００６８】
この発明における実施の形態２の重み付け優先制御装置と、実施の形態１の重み付け優先制御装置との違いは、扱うパケットが可変長であるのか固定長であるのかの違いである。そのため、実施の形態２では、重み付け処理が実施の形態１のＷＲＲ方式とは異なるアルゴリズムを採用する。
【００６９】
まず、可変長のパケットの制御に適用される重み付け処理について説明する。ここで、キュー・バッファ１１の重み付けの値を「４」、キュー・バッファ１２の重み付けの値を「３」、キュー・バッファ１３の重み付けの値を「６」とする。これら重み付けの値は、キュー・バッファ１１から読み出された総パケット長をｘ１、キュー・バッファ１２から読み出された総パケット長をｘ２、キュー・バッファ１３から読み出された総パケット長をｘ３とすると、回線４０にパケットを出力する時の帯域が、「ｘ１：ｘ２：ｘ３＝４：６：３」の比で維持されるようにすることを意味する。この実施の形態２の第１のアルゴリズムにおいては、これら重み付けの値の逆数を帯域制御に利用する。ここで、制御値をｙとすると、制御値ｙは、
ｙ＝（１／重み付けの値）×１００・・・（式１）
で表される。ただし、ｙは小数点以下を四捨五入した整数とする。（式１）では、１００をかけるようにしているが、これに限定されるものではなく、ハードウエアで実現する場合にはそのハードウエアに応じて、また、システムの要求する精度に応じて適切な値を決定すればよい。
【００７０】
（式１）を用いた場合、キュー・バッファ１１の制御値ｙ１は、
ｙ１＝（１／４）×１００＝２５
となり、キュー・バッファ１２の制御値ｙ２は、
ｙ２＝（１／６）×１００＝３３
となり、キュー・バッファ１３の制御値ｙ３は、
ｙ３＝（１／３）×１００＝１７
となる。この実施の形態２の重み付け優先制御装置は、これらの制御値ｙ１〜ｙ３に基づいて帯域制御を行う。
【００７１】
第１のアルゴリズムは、キュー・バッファ１１〜１３の先頭のパケット長とキュー・バッファ１１〜１３に対応した制御値ｙ１〜ｙ３との積をカウント値（優先度）とし、これらのカウント値を比較して、一番小さい値のカウント値のキュー・バッファを選択する。すなわち、常に各キュー・バッファの一番先頭のパケットだけが考慮の対象として重み付けの帯域制御を行う。なお、カウント値が等しい場合には、ラウンドロビン等を付加的に実施して常に１つを選択する。
【００７２】
第２のアルゴリズムは、実施の形態１と同様に、キュー・バッファからパケットがあふれる前にパケットが集中しているキュー・バッファを検知して、検知したキューのデータを優先的に回線に出力するためのアルゴリズムである。
【００７３】
キュー制御部３０ａは、キュー・バッファ１１〜１３に対応した重み付けの値を記憶するカウント値レジスタ３７〜３９と、キュー・バッファ１１〜１３がそれぞれ蓄積しているパケットの合計パケット長を監視するキュー監視部３４と、つぎにパケットを読み出すべきキュー・バッファを決定するキュー選択部３５ａと、キュー・バッファ１１〜１３の重み付けの値を算出する重み付け演算部３６ａとを備えている。
【００７４】
キュー選択部３５ａは、第１のアルゴリズムまたは第２のアルゴリズムに基づいてつぎにパケットを読み出すべきキュー・バッファを選択して、選択したキュー・バッファのパケットを読み出すように多重化部２０に通知するとともに、選択したキュー・バッファを重み付け演算部３６ａに通知する。
【００７５】
第１のアルゴリズムの場合、キュー選択部３５ａは、カウント値レジスタ３７〜３９に保持されているカウント値を比較して、一番小さい値のカウント値を検索し、検索したカウント値を保持するカウント値レジスタに対応するキュー・バッファを選択する。カウント値が等しい場合には、ラウンドロビン等を付加的に実施して常に１つを選択する。第２のアルゴリズムの場合、キュー選択部３５ａは、キュー監視部３４から通知された超過情報内のキュー・バッファを選択する。
【００７６】
キュー選択部３５ａが選択したキュー・バッファに対応するカウント値レジスタのカウント値が「０」以上の場合、重み付け演算部３６ａは、キュー選択部３５ａが選択したキュー・バッファに対応するカウント値レジスタのカウント値を各カウント値レジスタのカウント値から減算する。そして、減算したカウント値をカウント値レジスタに設定する。また、キュー選択部３５ａが選択したキュー・バッファに対応するカウント値レジスタには、選択したキュー・バッファの先頭のパケット長と（式１）に基づいて算出した制御値の積を設定する。
【００７７】
キュー選択部３５ａが選択したキュー・バッファに対応するカウント値レジスタのカウント値が「０」より小さい場合、重み付け演算部３６ａは、キュー選択部３５ａが選択したキュー・バッファに対応するカウント値レジスタのカウント値に、選択したキュー・バッファの先頭のパケット長と（式１）に基づいて算出した制御値の積を加算する。そして、加算した値をキュー選択部３５ａが選択したキュー・バッファに対応するカウント値レジスタに設定する。
【００７８】
カウント値レジスタ３７〜３９は、各カウンタに対応したキュー・バッファの先頭パケットのパケット長と（式１）に基づいて算出された制御値との積を保持する。カウント値レジスタ３７がキュー・バッファ１１に、カウント値レジスタ３８がキュー・バッファ１２に、カウント値レジスタ３９がキュー・バッファ１３にそれぞれ対応する。
【００７９】
図７および図８は、キュー・バッファ１１〜１３に蓄積されているパケットと、カウント値レジスタ３７〜３９の値と、キュー選択部３５ａが選択したキュー・バッファのパケットを多重化部２０が読み出して、読み出したパケットを回線４０に出力した様子を示す図である。図７および図８を参照して、この発明における実施の形態２の重み付け優先制御装置の動作を説明する。
【００８０】
まず、図７を参照して、第１のアルゴリズムに基づいてパケットを出力する動作を説明する。図７（ａ）において、キュー・バッファ１１はパケットＡ１〜Ａ３を、キュー・バッファ１２はパケットＢ１〜Ｂ４を、キュー・バッファ１３はパケットＣ１〜Ｃ３をそれぞれ蓄積している。予め定められている基準パケット長を「１」とすると、パケットＡ１のパケット長は「３」、パケットＡ２のパケット長は「２」、パケットＡ３のパケット長は「２」、パケットＢ１のパケット長は「１」、パケットＢ２のパケット長は「２」、パケットＢ３のパケット長は「３」、パケットＢ４のパケット長は「１」、パケットＣ１のパケット長は「２」、パケットＣ２のパケット長は「１」、パケットＣ３のパケット長は「４」である。
【００８１】
カウント値レジスタ３７には（式１）を用いて算出した制御値ｙ１である「２５」とキュー・バッファ１１の先頭のパケットＡ１のパケット長「３」を乗算した値「７５」が、カウント値レジスタ３８には（式１）を用いて算出した制御値ｙ２である「３３」とキュー・バッファ１２の先頭のパケットＢ１のパケット長「１」を乗算した値「３３」が、カウント値レジスタ３９には（式１）を用いて算出した制御値ｙ３である「１７」とキュー・バッファ１３の先頭のパケットＣ１のパケット長「２」を乗算した値「３４」が設定されている。
【００８２】
ここでは、キュー監視部３４に予め定められている閾値は、点線で示したように基準パケット長７個分のパケット長とする。キュー・バッファ１１に蓄積されているパケットＡ１〜Ａ３の合計パケット長、キュー・バッファ１２に蓄積されているパケットＢ１〜Ｂ４の合計パケット長、キュー・バッファ１３に蓄積されているパケットＣ１〜Ｃ３の合計パケット長は、それぞれ「７」であり、閾値を超えていない。
【００８３】
キュー選択部３５ａは、カウント値レジスタ３７〜３９に設定されているカウント値を比較して一番小さいカウント値を検索し、検索したカウント値レジスタに対応するキュー・バッファを選択する。そして、選択したキュー・バッファのパケットを読み出すように多重化部２０に通知するとともに、選択したキュー・バッファを重み付け演算部３６ａに通知する。ここでは、カウント値レジスタ３８に保持されているカウント値「３３」が一番小さいので、キュー選択部３５ａはキュー・バッファ１２を選択する。
【００８４】
図７（ｂ）に示すように、多重化部２０は、キュー・バッファ１２のパケットＢ１を読み出して、読み出したパケットＢ１を回線４０に出力する。カウント値レジスタ３８のカウント値が「０」以上であるので、重み付け演算部３６ａは、カウント値レジスタ３７〜３９のそれぞれのカウント値からカウント値レジスタ３８のカウント値を減算し、減算した値を新たなカウント値としてカウント値レジスタ３７〜３９に設定する。
【００８５】
ここでは、図７（ａ）に示したように、カウント値レジスタ３７のカウント値が「７５」、カウント値レジスタ３８のカウント値が「３３」、カウント値レジスタ３９のカウント値が「３４」である。したがって、カウント値レジスタ３７のカウント値は「４２」、カウント値レジスタ３８のカウント値は「０」、カウント値レジスタ３９のカウント値は「１」となる。
【００８６】
キュー・バッファ１２のパケットＢ１を読み出したので、重み付け演算部３６ａは、キュー・バッファ１２の先頭のパケットＢ２のパケット長「２」と（式１）に基づいて算出したキュー・バッファ１２の制御値ｙ２である「３３」との積「６６」をカウント値レジスタ３８に設定する。したがって、図７（ｂ）に示すように、カウント値レジスタ３７のカウント値は「４２」、カウント値レジスタ３８のカウント値は「６６」、カウント値レジスタ３９のカウント値は「１」となる。
【００８７】
このように第１のアルゴリズムでは、キュー選択部３５ａは、カウント値レジスタ３７〜３９のカウント値を比較して、一番小さいカウント値を検索して、検索したカウント値レジスタに対応するキュー・バッファを選択し、多重化部２０は、選択されたキュー・バッファに蓄積されている先頭のパケットを回線４０に出力する。重み付け演算部３６ａは、選択されたキュー・バッファに対応するカウント値レジスタのカウント値を、各カウント値レジスタの値から減算して、新たなカウント値を各カウント値レジスタに設定する。そして、選択されたキュー・バッファに対応するカウント値レジスタには、キュー・バッファの先頭のパケットのパケット長と（式１）を用いて算出した制御値との積をカウント値として設定する動作を繰り返す。その時のキュー・バッファ１１〜１３に蓄積されているパケットと、カウント値レジスタ３７〜３９の値と、キュー選択部３５ａが選択したキュー・バッファのパケットを多重化部２０が読み出して、読み出したパケットを回線４０に出力した様子を図７（ｃ）〜図７（ｆ）に示す。
【００８８】
ここで、第１のアルゴリズムがＷＲＲ方式やＷＲＱ方式と同様に、キュー・バッファに蓄積されるパケットが輻輳してきた時点においても、各キュー・バッファ毎に出力先の帯域の一定割合以上の帯域を保証することが可能であることを簡単に説明する。
【００８９】
ある時間ｔ内に出力先に読み出されたパケットについて、キュー・バッファＳ（ここでは、キュー・バッファ１１〜１３であり、Ｓ＝１１，１２，１３とする）から読み出されたパケット数をＮｓ（ここでは、キュー・バッファＳごとに、１、２、…、Ｎｓ）、キュー・バッファＳから読み出されたパケットそれぞれのパケット長をｓＰｎ、各キュー・バッファ毎の重み付けをＢｓとすると、キュー・バッファＳ帯域が重み付けの値で維持されるためには、
【数１】

が成り立つ必要がある。
【００９０】
【数２】

は、キュー・バッファＳから出力された実際の帯域をあらわすので、それぞれの比がＢｓに対応していればよい。厳密には、（式２）の各項が等しく（「＝」で結ばれる）ならなければならないが、有限の時間ｔにおいて、パケット長が可変であるため等しくはならない。（式２）を比の形式で表すと、
【数３】

となる。ここでは、時間ｔは共通であるので削除している。そして、各項のΣ内の項、₁₁Ｐ₁／Ｂ₁₁，₁₁Ｐ₂／Ｂ₁₁，₁₁Ｐ₃／Ｂ₁₁，…，₁₁Ｐ_n／Ｂ₁₁は、まさに重み付け演算部３６ａが算出する「キュー・バッファ１１の先頭のパケット長×重み付けの値の逆数」に他ならない。したがって、上述したような動作を行うことは、ある時間ｔにおける（式３）の各項の差を、常に極力小さく（最小ではない）維持していくことになる。厳密には、最小でなければならないが、ハードウエアで実現する場合、他の要件も含めて考えると帯域制御の方式の１つとして十分である。
【００９１】
つぎに、図８を参照して、この発明における実施の形態２の重み付け優先制御装置が、第２のアルゴリズムに基づいてパケットを出力する動作を説明する。
【００９２】
図８（ａ）において、キュー・バッファ１１はパケットＡ１〜Ａ３を、キュー・バッファ１２はパケットＢ１〜Ｂ４を、キュー・バッファ１３はパケットＣ１〜Ｃ４をそれぞれ蓄積している。予め定められている基準パケット長を「１」とすると、パケットＡ１のパケット長は「３」、パケットＡ２のパケット長は「２」、パケットＡ３のパケット長は「２」、パケットＢ１のパケット長は「１」、パケットＢ２のパケット長は「２」、パケットＢ３のパケット長は「３」、パケットＢ４のパケット長は「１」、パケットＣ１のパケット長は「２」、パケットＣ２のパケット長は「１」、パケットＣ３のパケット長は「４」である。
【００９３】
カウント値レジスタ３７には（式１）を用いて算出した制御値ｙ１である「２５」とキュー・バッファ１１の先頭のパケットＡ１のパケット長「３」を乗算した値「７５」が、カウント値レジスタ３８には（式１）を用いて算出した制御値ｙ２である「３３」とキュー・バッファ１２の先頭のパケットＢ１のパケット長「１」を乗算した値「３３」が、カウント値レジスタ３９には（式１）を用いて算出した制御値ｙ３である「１７」とキュー・バッファ１３の先頭のパケットＣ１のパケット長「２」を乗算した値「３４」が設定されている。
【００９４】
ここでは、キュー監視部３４に予め定められている閾値は、点線で示したように基準パケット長７個分のパケット長とする。キュー・バッファ１１に蓄積されているパケットＡ１〜Ａ３の合計パケット長、キュー・バッファ１２に蓄積されているパケットＢ１〜Ｂ４の合計パケット長、キュー・バッファ１３に蓄積されているパケットＣ１〜Ｃ３の合計パケット長は、それぞれ「７」であり、閾値を超えていない。しがたって、キュー制御部３０ａは、上述した第１のアルゴリズムに基づいてキュー・バッファ選択して、多重化部２０は、キュー制御部３０ａが選択したパケットを読み出して、読み出したパケットを回線４０に出力する動作を繰り返し、パケットＢ１、パケットＣ１、パケットＣ２、パケットＡ１の順に回線４０にパケットを出力する（図７（ｂ）〜図７（ｅ）参照）。
【００９５】
ここで、図８（ｂ）に示すように、キュー・バッファ１３にパケット長「１」のパケットＣ４とパケット長「３」のパケットＣ５が蓄積されたとする。キュー・バッファ１３に蓄積されているパケットＣ３〜Ｃ５の合計パケット長は「８」となり、閾値「７」を超える。キュー監視部３４は、キュー・バッファ１３に蓄積されているパケットＣ３〜Ｃ５の合計パケット長が閾値を超えたことを検知して、キュー・バッファ１３が閾値を超えたことを通知するための超過情報をキュー選択部３５ａに出力する。
【００９６】
キュー監視部３４から超過情報が通知されたため、キュー選択部３５ａは、通知された超過情報に含まれるキュー・バッファ１３を選択する。すなわち、第１のアルゴリズムに基づいてカウント値の一番小さいキュー・バッファ１２ではなく、第２のアルゴリズムに基づいて選択したキュー・バッファ１３を優先し、キュー・バッファ１３のパケットを読み出すように多重化部２０に通知する。
【００９７】
多重化部２０は、キュー・バッファ１３のパケットＣ３を読み出して、読み出したパケットＣ３を回線４０に出力する。重み付け演算部３６ａは、カウント値レジスタ３７〜３９のそれぞれのカウント値からカウント値レジスタ３９のカウント値を減算し、減算した値を新たなカウント値としてカウント値レジスタ３７〜３９に設定する。
【００９８】
図８（ｂ）に示したように、カウント値レジスタ３７のカウント値が「５０」、カウント値レジスタ３８のカウント値が「２４」、カウント値レジスタ３９のカウント値が「４４」である。したがって、カウント値レジスタ３７のカウント値は「６」、カウント値レジスタ３８のカウント値は「−２０」、カウント値レジスタ３９のカウント値は「０」となる。
【００９９】
キュー・バッファ１３のパケットＣ３を読み出したので、重み付け演算部３６ａは、キュー・バッファ１３の先頭のパケットＣ４のパケット長「１」と（式１）に基づいて算出したキュー・バッファ１３の制御値ｙ３である「１７」を乗算した値「１７」をカウント値レジスタ３７に設定する。したがって、図８（ｃ）に示すように、カウント値レジスタ３７のカウント値は「６」、カウント値レジスタ３８のカウント値は「−２０」、カウント値レジスタ３９のカウント値は「１７」となる。
【０１００】
ここで、キュー・バッファ１１にパケット長「２」のパケットＡ４とパケット長「３」のパケットＡ５が蓄積されたとする（図８（ｃ）参照）。キュー・バッファ１１に蓄積されているパケットＡ２〜Ａ５の合計パケット長が「８」となり、閾値「７」を超える。キュー監視部３４は、キュー・バッファ１１に蓄積されているパケットＡ２〜Ａ５の合計パケット長が閾値を超えたことを検知して、キュー・バッファ１１が閾値を超えたことを通知するための超過情報をキュー選択部３５ａに出力する。
【０１０１】
キュー監視部３４から超過情報が通知されたため、キュー選択部３５ａは、通知された超過情報に含まれるキュー・バッファ１１を選択して、キュー・バッファ１１のパケットを読み出すように多重化部２０に通知する。
【０１０２】
多重化部２０は、キュー・バッファ１１のパケットＡ２を読み出して、読み出したパケットＡ２を回線４０に出力する。重み付け演算部３６ａは、カウント値レジスタ３７〜３９のそれぞれのカウント値からカウント値レジスタ３７のカウント値を減算し、減算した値を新たなカウント値としてカウント値レジスタ３７〜３９に設定する。
【０１０３】
図８（ｃ）に示したように、カウント値レジスタ３７のカウント値が「６」、カウント値レジスタ３８のカウント値が「−２０」、カウント値レジスタ３９のカウント値が「１７」である。したがって、カウント値レジスタ３７のカウント値は「０」、カウント値レジスタ３８のカウント値は「−２６」、カウント値レジスタ３９のカウント値は「１１」となる。
【０１０４】
キュー・バッファ１１のパケットＡ２を読み出したので、重み付け演算部３６ａは、キュー・バッファ１１の先頭のパケットＡ３のパケット長「２」と（式１）に基づいて算出したキュー・バッファ１１の制御値ｙ１である「２５」との積「５０」をカウント値レジスタ３７に設定する。したがって、図８（ｄ）に示すように、カウント値レジスタ３７のカウント値は「５０」、カウント値レジスタ３８のカウント値は「−２６」、カウント値レジスタ３９のカウント値は「１１」となる。
【０１０５】
図８（ｄ）に示したように、キュー・バッファ１１のパケットＡ２を出力し、キュー・バッファ１１〜１３に新たに蓄積されたパケットもないので、キュー・バッファ１１〜１３に蓄積されているパケットの各合計パケット長は、どれも閾値を超えていない。したがって、キュー選択部３５ａは、第１のアルゴリズムに基づいてキュー・バッファを選択する。すなわち、カウント値レジスタ３７〜３８のそれぞれのカウント値の一番小さいカウント値レジスタに対応するキュー・バッファを選択する。図８（ｄ）においては、キュー選択部３５ａは、カウント値が「−２６」のキュー・バッファ１２を選択し、多重化部２０は、キュー・バッファ１２のパケットＢ２を回線４０に出力する。
【０１０６】
重み付け演算部３６ａは、キュー・バッファ１２の先頭のパケットＢ３のパケット長「３」と（式１）に基づいて算出したキュー・バッファ１２の制御値ｙ２である「３３」を乗算した値「９９」を、カウント値レジスタ３８のカウント値「−２６」に加算する。そして、加算した値「７３」をカウント値レジスタ３８に設定する。重み付け演算部３６ａは、キュー・バッファ１１とキュー・バッファ１３に対応するカウント値レジスタ３７とカウント値レジスタ３９のカウント値については変更しない。すなわち、パケットを読み出したキュー・バッファに対応するカウント値レジスタのカウント値が「０」より小さい場合（カウント値が負数の場合）、重み付け演算部３６ａは、他のカウント値レジスタのカウント値を新たに設定せず、パケットを読み出したキュー・バッファに対応するカウント値レジスタのカウント値にパケット長と制御値との積を加算する。そして、加算した値をパケットを読み出したキュー・バッファに対応するカウント値レジスタに設定する。したがって、図８（ｅ）に示すように、カウント値レジスタ３７のカウント値は「５０」、カウント値レジスタ３８のカウント値は「７３」、カウント値レジスタ３９のカウント値は「１１」となり、カウント値レジスタ３７〜３９のカウント値は、全て「０」以上となる。
【０１０７】
その後、キュー選択部３５ａは、カウント値レジスタ３７〜３９のカウント値を比較して、一番小さいカウント値のカウント値レジスタに対応するキュー・バッファ１３を選択し、多重化部２０は、キュー・バッファ１３のパケットＣ４を回線４０に出力する。そして、重み付け演算部３６ａは、カウント値レジスタ３９のカウント値をカウント値レジスタ３７〜３９のカウント値から減算するとともに、キュー・バッファ１３の先頭パケットＣ５のパケット長と（式１）に基づいて算出した制御値ｙ３を乗算して、カウント値レジスタ３７〜３９のカウント値を算出して、それぞれのカウント値レジスタに設定する。その様子を図８（ｆ）に示す。
【０１０８】
このようにこの実施の形態２では、複数のキュー・バッファに蓄積されているデータに対して一定の割合の帯域を保証するために、予め定められた重み付けの値による優先度に基づいて複数のキュー・バッファの優先順位を決定してデータを読み出すキュー・バッファを選択する第１のアルゴリズムと、第１のアルゴリズムとは異なる第２のアルゴリズムによりデータを読み出すキュー・バッファを選択する第２のアルゴリズムがあり、これら２つのアルゴリズムにより選択したキュー・バッファが異なる場合には、第２のアルゴリズムにより選択したキュー・バッファを優先してデータを出力する。その際に、優先したキュー・バッファの優先度を下げるようにしているため、第２のアルゴリズムにより選択したキュー・バッファを優先した場合でも、第１のアルゴリズムの帯域保証の精度を維持することができる。
【０１０９】
なお、カウント値レジスタの値が負数になったときの取り扱いとして、負数値をいくつまで許可するかという制限が、実現性に大きく影響する。この制限は、重みの逆数を整数に変換するために乗算する値(この場合は１００)と、パケット長として規格化された値(この場合は１から、最大４まで)によって決まる。システムに要求される性能にもよるが、最大長のパケット、数個から数十個分程度、借入ができるようにするのが妥当である。もちろんリソースとして実装されるキュー・バッファの深さもこの値を決定する要因である。そしてこのときの処理は、あるキュー・バッファのカウント値レジスタが負数の限度値に達した場合には、今度はキュー監視部３４の要求に拘わらず、負数の限度に達したカウント値レジスタに対応するキュー・バッファからのパケットの読み出しを最優先するというように、互いのアルゴリズムの達成度に折り合いをつけるようにすればよい。
【０１１０】
また、実施の形態１および２では、帯域制御を第１のアルゴリズムとし、キュー・バッファに保持するデータ長による制御を第２のアルゴリズムとして説明したが、これに限定されるものではなく、つぎにデータを読み出すべき優先制御処理が複数あって、それらの優先制御処理が共謀する可能性がある環境において適用可能である。
【０１１１】
【発明の効果】
以上説明したように、各キュー・バッファ１ごとに割り付けられた重み付けの値を初期値とし、各キュー・バッファからのデータ読み出しの度に算出される優先度に基づき複数のキュー・バッファの優先順位を決定し、決定した優先順位に従ってデータを読み出すキュー・バッファ１を選択することによりデータの帯域を保証する第１のアルゴリズムによって選択されたキュー・バッファと、第１のアルゴリズムとは異なる処理によってデータを読み出すキュー・バッファを選択する第２のアルゴリズムによって選択されたキュー・バッファとが異なる場合には、所定の条件が成立する場合を除いて、第２のアルゴリズムによって選択されたキュー・バッファを優先するとともに、優先するキュー・バッファ以外のすべてのキュー・バッファの優先度を上げるようにしているため、第２のアルゴリズムにより選択したキュー・バッファを優先した場合でも、第１のアルゴリズムの帯域の保証の精度を維持することができる。
【図面の簡単な説明】
【図１】この発明における実施の形態１の重み付け優先制御方法に基づいて動作する重み付け優先制御装置の構成を示すブロック図である。
【図２】図１に示した重み付け優先制御装置の動作を説明するための図である。
【図３】図１に示した重み付け優先制御装置の動作を説明するための図である。
【図４】図１に示した重み付け優先制御装置の動作を説明するための図である。
【図５】図１に示した重み付け優先制御装置の動作を説明するための図である。
【図６】この発明における実施の形態２の重み付け優先制御方法に基づいて動作する重み付け優先制御装置の構成を示すブロック図である。
【図７】図６に示した重み付け優先制御装置の動作を説明するための図である。
【図８】図６に示した重み付け優先制御装置の動作を説明するための図である。
【符号の説明】
１１，１２，１３キュー・バッファ、２０多重化部、３０キュー制御部、３１，３２，３３カウンタ、３４キュー監視部、３５，３５ａキュー選択部、３６，３６ａ重み付け演算部、３７，３８，３９カウント値レジスタ、４０回線。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a bandwidth control method for a communication apparatus, and more particularly to a weighted priority control method for performing bandwidth control simultaneously with circuit switching processing when data is output to a circuit.
[0002]
[Prior art]
According to the weighting value set for each output destination that outputs data, for example, a plurality of queues (queues) installed immediately before the line, a constant of the bandwidth of the line for the data of each queue There are a weighted round robin (WRR) method and a weighted fair queuing (WFQ) method as an algorithm for assuring a bandwidth of the above rate.
[0003]
In the WRR method, the order of queues for reading data is determined in advance, and a weighting value is set for each queue when performing round robin (rotation priority control) for sequentially reading data from each queue according to the order. A weight value is decremented every time data is read out. Then, by reading the data of the next queue without reading the data from the queue whose weighting value is “0”, the output frequency of the data output from each queue is controlled, and a certain percentage of bandwidth Is guaranteed. Therefore, especially when handling fixed-length data such as ATM (Asynchronous Transfer Mode) cells, it can be realized with a counter capable of setting decrement and weight values. It can be realized with a simple circuit.
[0004]
For these reasons, a technique is conceived in which various expansions and ingenuities are applied to the implementation and functions of the apparatus using the WRR method. In the first prior art, an algorithm using a priority index is basically used, and a priority sort list is provided for a configuration using a priority index table, so that all flows or a predetermined number is determined for each actual packet transfer sequence (round). The flows are stored in order of descending priority index (descending order), packets are transferred in order from the first flow in the priority sort list, and then packets are transferred from each flow outside the priority sort list. The delay jitter performance which is a problem of the system is improved (for example, see Patent Document 1).
[0005]
Further, in the second prior art, when there is no cell in the cell buffer circuit, a cell presence / absence flag output circuit for sending a significant cell presence / absence flag and a corresponding count value of the count memory are subtracted to “0”. A wait presence / absence flag sending circuit for sending a significant wait presence / absence flag, and a count initialization flag sending circuit for simultaneously sending a significant count initialization flag when either or both of the cell presence / absence flag and the wait presence / absence flag are significant For each cell buffer, when one cell buffer circuit in each cell buffer circuit is selected and a cell is output, if the corresponding count initialization flag is significant, only the corresponding counter value is initialized. In this way, by eliminating the time limit for initializing the counter value, the memory can be used regardless of the number of cell buffer circuits. So that it is possible to construct a counter is used. (For example, refer to Patent Document 2).
[0006]
[Patent Document 1]
JP-A-11-298523
[Patent Document 2]
JP 2000-278272 A
[0007]
[Problems to be solved by the invention]
The first prior art uses an algorithm using a priority index, and the second technique uses a WRR algorithm. That is, both of the above prior arts form the body of one algorithm, and the queue to be read out next is selected only in an environment where the algorithm is unique. For this reason, the above two conventional techniques may cause inconveniences when there are two algorithms for selecting a queue to be read next.
[0008]
For example, in general, data flowing on a network does not flow as required by bandwidth control. Looking at the data flowing on the network in micro time units, if data is concentrated at a certain place and data is read as requested by bandwidth control, the data overflows from the queue, and the overflowed data is discarded. Is done.
[0009]
In such a case, it is general that the discards are not concentrated on one data series by RED (Random Early Detection), but it is not unreasonable to discard the data. Therefore, it is assumed that an algorithm “detects a queue in which data is concentrated before data overflows from the queue and outputs the detected queue data preferentially to the line” is added to the above two conventional techniques. That is, it is assumed that there are an algorithm for maintaining bandwidth control such as the WRR method and an algorithm for selecting a queue to be read next (in this case, selecting a queue in which data is concentrated). When the queues selected by these two algorithms are different and data is read from a queue selected by an algorithm different from the algorithm that maintains the bandwidth control, the above two conventional techniques do not lose the bandwidth control effect itself. This procedure has not been studied.
[0010]
Therefore, the above two conventional techniques have a problem that the accuracy of the bandwidth control cannot be maintained when it is necessary to properly use an algorithm for maintaining the bandwidth control according to the queue status and a different algorithm. It was.
[0011]
The present invention has been made in view of the above, and has an algorithm for maintaining bandwidth control and a different algorithm, and when data is read from a queue selected by an algorithm different from the algorithm for maintaining bandwidth control. However, an object of the present invention is to obtain a weighted priority control method that can maintain the accuracy of the bandwidth of the algorithm that maintains the bandwidth control.
[0012]
[Means for Solving the Problems]
In order to achieve the above object, according to the weighted priority control method of the present invention, the data stored in a plurality of queue buffers is assigned to each queue at a ratio of a weight value assigned to each of the plurality of queue buffers. A weighted priority control method for guaranteeing the bandwidth of the data read from the buffer, wherein the weighting value is an initial value, and the plurality of the plurality of weights are controlled based on the priority calculated each time data is read from each queue buffer. By determining the priority of the queue buffer and selecting the queue buffer from which data is read according to the determined priority, the first algorithm for guaranteeing the bandwidth of the data is different from the first algorithm. A second algorithm for selecting a queue buffer from which data is read, the first and If the queue buffers selected by the algorithm of 2 are different, the queue buffer selected by the second algorithm is prioritized unless a predetermined condition is satisfied, and the queue buffers other than the priority queue buffer are selected. A process for increasing the priority in the first algorithm of all queue buffers is performed.
[0013]
According to this invention, the weighting value assigned to each queue buffer is used as an initial value, and the priority order of a plurality of queue buffers is determined based on the priority calculated each time data is read from each queue buffer. The queue buffer selected by the first algorithm that guarantees the bandwidth of the data by selecting and selecting the queue buffer that reads the data according to the determined priority, and reads the data by a process different from the first algorithm If the queue buffer selected by the second algorithm for selecting the queue buffer is different from the queue buffer selected by the second algorithm, the queue buffer selected by the second algorithm is prioritized unless a predetermined condition is satisfied. Priority for all queue buffers except the preferred queue buffer It is to raise the. However, when priority is given to the queue buffer selected by the second algorithm and the priority of all queue buffers other than the priority queue buffer is increased, there is a limit to increase the priority in terms of implementation. In this case, when the priority of the queue buffer exceeds the limit, the queue buffer selected by the first algorithm is prioritized when the priority exceeds the limit value. In addition to solving the above problem, it is possible to prevent the phenomenon that the bandwidth guarantee cannot be maintained by continuously selecting the queue buffer selected by the second algorithm.
[0014]
DETAILED DESCRIPTION OF THE INVENTION
Exemplary embodiments of a weighting priority control method according to the present invention will be explained below in detail with reference to the accompanying drawings.
[0015]
Embodiment 1 FIG.
A first embodiment of the present invention will be described with reference to FIGS. FIG. 1 is a block diagram showing a configuration of a weighting priority control apparatus that operates based on the weighting priority control method according to the first embodiment of the present invention. The weighted priority control apparatus shown in FIG. 1 includes a plurality of (three in this case) queue buffers 11 to 13 that store a fixed amount of data (packets), and one of two predetermined different algorithms. A queue control unit 30 that selects one of the queue buffers 11 to 13 based on the above algorithm, and a multiplexing unit 20 that reads the packet of the queue buffer selected by the queue control unit 30 and outputs the packet to the line. Yes.
[0016]
The queue control unit 30 performs a bandwidth control by weighting to guarantee a certain ratio of the bandwidth of the line, and a second algorithm to determine a queue buffer from which a packet is to be read by an algorithm different from the bandwidth control. The queue buffers 11 to 13 are monitored, and the queue buffer selected by the first algorithm and the queue buffer selected by the second algorithm are selected based on the state of the queue buffers 11 to 13. Select which one has priority. Then, the selected queue buffer is notified to the multiplexing unit 20.
[0017]
The first algorithm uses a weighting value set for each of the plurality of queue buffers as an initial value, and the priority order of the plurality of queue buffers based on the priority calculated each time data is read from each queue buffer. And a queue buffer for reading out data according to the determined priority order, thereby guaranteeing the data bandwidth. Here, the WRR method is used.
[0018]
The second algorithm is an algorithm that detects a queue buffer in which data is concentrated before a packet overflows from the queue buffer, and outputs the detected queue buffer packet preferentially to the line.
[0019]
The queue control unit 30 includes counters 31 to 33 that count weighting values corresponding to the queue buffers 11 to 13, and a queue monitoring unit 34 that monitors the total packet length of the packets held by the queue buffers 11 to 13, respectively. Next, a queue selection unit 35 that selects a queue buffer from which a packet is to be read out, and a weighting calculation unit 36 that calculates each priority based on the weighting values of the queue buffers 11 to 13 are provided.
[0020]
The queue monitoring unit 34 monitors whether the total packet length of the packets stored in the queue buffers 11 to 13 exceeds a predetermined threshold. When a queue buffer in which the total packet length of the accumulated packets exceeds the threshold value is detected, excess information including information for identifying the detected queue buffer is output to the queue selection unit 35.
[0021]
The queue selection unit 35 selects a queue buffer from which a packet is next to be read based on the first algorithm or the second algorithm, and notifies the multiplexing unit 20 to read the packet in the selected queue buffer. . When the queue selection unit 35 receives notification of excess information from the queue monitoring unit 34, the queue selection unit 35 prioritizes the queue buffer selected based on the second algorithm over the queue buffer selected based on the first algorithm. The information is notified to the multiplexing unit 20. When the queue buffer is selected based on the second algorithm and the count value (priority) of the counter corresponding to the selected queue buffer becomes a negative value, the weighting unit 36 is assigned a weighting value. Notify you to calculate.
[0022]
In the case of the first algorithm, the queue selection unit 35 searches for a counter whose counter value corresponding to the queue buffer in which the packet is accumulated is not “0” by round robin, and corresponds to the first detected counter. Select the queue buffer as the queue buffer from which packets are read. In this case, the count values are checked in the order of the counter 31, counter 32, counter 33, and counter 31 (round robin direction). The queue selection unit 35 stores the queue buffer selected last, and when selecting the queue buffer from which a packet is to be read next, the queue selection unit 35 sets the count value of the counter corresponding to the stored queue buffer. Check. When the count value is “0”, the counter value in the round robin direction is sequentially confirmed, and the queue buffer corresponding to the counter whose count value is not “0” is selected.
[0023]
In the case of the second algorithm, the queue selection unit 35 selects a queue buffer in the excess information notified from the queue monitoring unit 34. However, when the excess information for selecting the same queue buffer continues, the queue buffer notified by the excess information is continuously selected up to a predetermined fixed number of times.
[0024]
The counters 31 to 33 decrement the count value when a queue buffer corresponding to each counter is selected and a packet is output to the line. Here, the counter 31 corresponds to the queue buffer 11, the counter 32 corresponds to the queue buffer 12, and the counter 33 corresponds to the queue buffer 13.
[0025]
When all the count values of the counters 31 to 33 become “0”, the weighting calculation unit 36 sets the predetermined weighting values of the queue buffers 11 to 13 to each counter. When the count value of the counter corresponding to the queue buffer selected by the second algorithm becomes negative, a value obtained by adding a predetermined weight value to the count value of each counter is set in each counter. That is, in order to make the count value of the counter that has become negative, the weight value of each counter is added to the count value of each counter so as to maintain the weight ratio of the bandwidth control by the first algorithm. .
[0026]
2 to 5, the multiplexing unit 20 reads out the packets accumulated in the queue buffers 11 to 13, the values of the counters 31 to 33, and the queue buffer packets selected by the queue selection unit 35. 4 is a diagram illustrating a state in which a read packet is output to a line 40. FIG. With reference to FIGS. 2 to 5, the operation of the weighting priority control apparatus that operates based on the weighting priority control method according to the first embodiment of the present invention will be described. Here, the weight value of the queue buffer 11 is set to “1”, the weight value of the queue buffer 12 is set to “3”, the weight value of the queue buffer 13 is set to “2”, and the queue buffers 11 to 13 are assigned. Assume that the lengths of the accumulated packets are all the same (fixed length).
[0027]
First, an operation for outputting a packet based on the first algorithm will be described with reference to FIGS. 2 and 3. In FIG. 2A, the queue buffer 11 stores packets A1 to A4, the queue buffer 12 stores packets B1 to B5, and the queue buffer 13 stores packets C1 to C4. “1”, “3” is set in the counter 32, and “2” is set in the counter 33. That is, in the counters 31 to 33, a weighting value is set by the weighting calculation unit 36 as an initial value of priority. Further, the threshold value predetermined for the queue monitoring unit 34 is a packet length of six packets here, as indicated by a dotted line.
[0028]
Since the total packet length of the packets stored in the queue buffers 11 to 13 does not exceed the threshold value for each queue buffer, the queue selection unit 35 selects the queue buffer based on the first algorithm. The queue selection unit 35 checks the count value of the counter 31 indicating the priority of the queue buffer 11. Since the count value of the counter 31 is “1”, the queue selection unit 35 selects the queue buffer 11 and notifies the multiplexing unit 20 to read the packet of the queue buffer 11.
[0029]
As shown in FIG. 2B, the multiplexing unit 20 reads the packet A1 from the queue buffer 11 and outputs the read packet A1 to the line 40. Since the queue selection unit 35 has selected the queue buffer 11, the counter 31 decrements the count value to set the count value to “0”.
[0030]
Since the queue buffer 11 has been selected, the queue selection unit 35 checks the count value of the counter 32 corresponding to the queue buffer 12. Since the count value of the counter 32 is “3”, the queue selection unit 35 selects the queue buffer 12 and notifies the multiplexing unit 20 to read the packet of the queue buffer 12.
[0031]
As shown in FIG. 2C, the multiplexing unit 20 reads the packet B1 from the queue buffer 12 and outputs the read packet B1 to the line 40. Since the queue selection unit 35 has selected the queue buffer 12, the counter 32 decrements the count value to set the count value to “2”.
[0032]
Since the queue buffer 12 has been selected, the queue selection unit 35 checks the count value of the counter 33 corresponding to the queue buffer 13. Since the count value of the counter 33 is “2”, the queue selection unit 35 selects the queue buffer 13 and notifies the multiplexing unit 20 to read the packet in the queue buffer 13.
[0033]
As illustrated in FIG. 2D, the multiplexing unit 20 reads the packet C1 from the queue buffer 13 and outputs the read packet C1 to the line 40. Since the queue selection unit 35 has selected the queue buffer 13, the counter 33 decrements the count value to set the count value to “1”.
[0034]
Since the queue buffer 13 has been selected, the queue selection unit 35 checks the count value of the counter 31. The count value of the counter 31 is “0”. Therefore, the queue selection unit 35 checks the count value of the counter 32 next to the counter 31 in the round robin direction. Since the count value of the counter 32 is “2”, the queue selection unit 35 selects the queue buffer 12 and notifies the multiplexing unit 20 to read the packet of the queue buffer 12.
[0035]
As shown in FIG. 2E, the multiplexing unit 20 reads the packet B2 from the queue buffer 12 and outputs the read packet B2 to the line 40. Since the queue selection unit 35 has selected the queue buffer 12, the counter 32 decrements the count value to set the count value to “1”.
[0036]
Since the queue buffer 12 has been selected, the queue selection unit 35 checks the count value of the counter 33 corresponding to the queue buffer 13. Since the count value of the counter 33 is “1”, the queue selection unit 35 selects the queue buffer 13 and notifies the multiplexing unit 20 to read the packet in the queue buffer 13.
[0037]
As shown in FIG. 3F, the multiplexing unit 20 reads the packet C2 from the queue buffer 13 and outputs the read packet C2 to the line 40. Since the queue selection unit 35 has selected the queue buffer 13, the counter 33 decrements the count value to set the count value to “0”.
[0038]
Since the queue buffer 13 has been selected, the queue selection unit 35 checks the count value of the counter 31 corresponding to the queue buffer 11. Since the count value of the counter 31 is “0”, the queue selection unit 35 checks the count value of the counter 32 next to the counter 31 in the round robin direction. Since the count value of the counter 32 is “1”, the queue selection unit 35 selects the queue buffer 12 and notifies the multiplexing unit 20 to read the packet in the queue buffer 12.
[0039]
As shown in FIG. 3G, the multiplexing unit 20 reads the packet B3 from the queue buffer 12 and outputs the read packet B3 to the line 40. Since the queue selection unit 35 has selected the queue buffer 12, the counter 32 decrements the count value to set the count value to “0”.
[0040]
Here, the count values of the counters 31 to 33 are all “0”. The queue selection unit 35 checks the count value of each counter in the order of the counter 33, the counter 31, and the counter 32, and if the count value of each counter is “0”, sets the initial value to the weighting calculation unit 36. Notify to set.
[0041]
Upon receiving the notification, the weight calculation unit 36 sets the predetermined weight values of the queue buffers 11 to 13 in the counters 31 to 33. Since the weighting of the queue buffer 11 is “1”, the weighting of the queue buffer 12 is “3”, and the weighting of the queue buffer 13 is “2”, the weighting calculation unit 36 is as shown in FIG. In addition, “1” is set in the counter 31, “3” is set in the counter 32, and “2” is set in the counter 33.
[0042]
After the weighting calculation unit 36 newly sets a count value in the counters 31 to 33, the queue selection unit 35 sequentially checks the count values of the counters 31 to 33 in the round robin direction, and the count value is not “0”. The queue buffer corresponding to the counter is selected, and when the count value is “0”, the count value of the next counter is confirmed. The multiplexing unit 20 repeats the operation of reading the queue buffer packet selected by the queue selection unit 35 and outputting it to the line 40. FIG. 3 (j), FIG. 3 (k), and FIG.
[0043]
Next, referring to FIG. 4 and FIG. 5, the weight priority control apparatus is based on the second algorithm, taking as an example a case where the packet accumulated in the queue buffer 11 exceeds a predetermined threshold. An operation for outputting a packet will be described. Here, the limit for continuously selecting the same queue buffer by the second algorithm is four times.
[0044]
In FIG. 4A, the queue buffer 11 stores packets A1 to A5, the queue buffer 12 stores packets B1 to B5, and the queue buffer 13 stores packets C1 to C5. “1” is set, “3” is set in the counter 32, and “2” is set in the counter 33. That is, in the counters 31 to 33, the weighting values of the queue buffers 11 to 13 are set by the weighting calculation unit 36 as initial values. Further, the threshold value predetermined for the queue monitoring unit 34 is a packet length of six packets here, as indicated by a dotted line.
[0045]
Since the amount of packets stored in the queue buffers 13 to 33 is 5 and does not exceed the threshold value, the queue selection unit 35 selects a queue buffer based on the first algorithm. The queue selection unit 35 selects the queue buffer 12 after confirming that the count value of the counter 32 is “3”. As shown in FIG. 4B, the multiplexing unit 20 reads the packet B1 from the queue buffer 12 and outputs the read packet B1 to the line 40. Since the queue selection unit 35 has selected the queue buffer 12, the counter 32 decrements the count value to set the count value to “2”. While the packet B1 is being output to the line 40, the packets A6 to A9 are newly accumulated in the queue buffer 11, the packet B6 is newly accumulated in the queue buffer 12, and the total number of packets accumulated in the queue buffer 11 Assume that the packet length exceeds the threshold. The queue monitoring unit 34 detects that the amount of packets accumulated in the queue buffer 11 has exceeded the threshold, and sends excess information for notifying that the queue buffer 11 has exceeded the threshold to the queue selection unit 35. Output to.
[0046]
Since the queue buffer 12 is selected, the queue selection unit 35 originally selects the queue buffer 13 after confirming that the count value of the counter 33 is “2”. However, since excess information is notified from the queue monitoring unit 34, the queue buffer 11 included in the notified excess information is selected. That is, the multiplexing unit 20 reads the packets in the queue buffer 11 with priority given to the queue buffer 11 selected based on the second algorithm, not the queue buffer 12 selected based on the first algorithm. Notify
[0047]
As shown in FIG. 4C, the multiplexing unit 20 reads the packet A1 from the queue buffer 11 and outputs the read packet A1 to the line 40. Since the queue selection unit 35 has selected the queue buffer 11, the counter 31 decrements the count value to set the count value to “0”.
[0048]
The total packet length of the packets stored in the queue buffer 11 is “8”, but still exceeds the threshold. The queue monitoring unit 34 notifies the queue selection unit 35 that the queue buffer 11 exceeds the threshold value using excess information. The queue selection unit 35 selects the queue buffer 11 included in the notified excess information and notifies the multiplexing unit 20 to read the packet in the queue buffer 11.
[0049]
As shown in FIG. 4D, the multiplexing unit 20 reads the packet A2 from the queue buffer 11 and outputs the read packet A2 to the line 40. Since the queue selection unit 35 has selected the queue buffer 11, the counter 31 decrements the count value to set the count value to “−1”.
[0050]
When the count value of the counter 31 becomes “−1”, the weight calculation unit 36 sets a value obtained by adding a predetermined weight value to the count value of each counter in each counter. The weight value of the queue buffer 11 is “1”, the weight value of the queue buffer 12 is “3”, the weight value of the queue buffer 13 is “2”, and the count value of the counter 31 is “−1”. The count value of the counter 32 is “2”, and the count value of the counter 33 is “2”. As shown in FIG. 4E, the weighting calculation unit 36 adds a value “0” obtained by adding the count value “−1” of the counter 31 and the weighting value “1” of the queue buffer 11 to the counter 31. A value “5” obtained by adding the count value “2” of 32 and the weight value “3” of the queue buffer 12 to the counter 31, the count value “2” of the counter 33 and the weight value “2” of the queue buffer 13 "4" is set in the counter 33.
[0051]
The total packet length of the packets stored in the queue buffer 11 is “7”, but still exceeds the threshold. The queue monitoring unit 34 notifies the queue selection unit 35 that the queue buffer 11 exceeds the threshold value using excess information. The queue selection unit 35 selects the queue buffer 11 included in the notified excess information and notifies the multiplexing unit 20 to read the packet in the queue buffer 11.
[0052]
As shown in FIG. 4 (f), the multiplexing unit 20 reads the packet A 3 from the queue buffer 11 and outputs the read packet A 3 to the line 40. Since the queue selection unit 35 has selected the queue buffer 11, the counter 31 decrements the count value to set the count value to “−1”.
[0053]
When the count value of the counter 31 becomes “−1”, the weight calculation unit 36 sets a value obtained by adding a predetermined weight value to the count value of each counter in each counter. The weight value of the queue buffer 11 is “1”, the weight value of the queue buffer 12 is “3”, the weight value of the queue buffer 13 is “2”, and the count value of the counter 31 is “−1”. The count value of the counter 32 is “5”, and the count value of the counter 33 is “4”. As shown in FIG. 5G, the weighting calculation unit 36 adds a value “0” obtained by adding the count value “−1” of the counter 31 and the weighting value “1” of the queue buffer 11 to the counter 31. A value “8” obtained by adding the count value “5” of 32 and the weight value “3” of the queue buffer 12 to the counter 31, the count value “4” of the counter 33 and the weight value “2” of the queue buffer 13 "6" is set in the counter 33. The total packet length of the packets stored in the queue buffer 11 is “6”, which is below the threshold value. Since the amount of packets stored in the queue buffer 11 has become equal to or less than the threshold value, the queue selection unit 35 selects a queue buffer based on the first algorithm. Since the queue buffer 11 has been selected, the queue selection unit 35 confirms the count value of the counter 32. Since the value of the counter 32 is “8”, the queue selection unit 35 selects the queue buffer 12 and notifies the multiplexing unit 20 to read the packet of the queue buffer 12.
[0054]
As shown in FIG. 5H, the multiplexing unit 20 reads the packet B2 from the queue buffer 12, and outputs the read packet B2 to the line 40. Since the queue selection unit 35 has selected the queue buffer 12, the counter 32 decrements the count value to set the count value to “7”.
[0055]
After that, even if packets are newly accumulated in the queue buffers 11 to 13, if the total packet length of the packets accumulated in the queue buffers 11 to 13 does not exceed the threshold value, the queue selection unit 35 selects the first Select a queue buffer based on the algorithm. Since the operation of the first algorithm is the same as that described with reference to FIGS. 2 and 3, detailed description of the operation is omitted here.
[0056]
The queue selection unit 35 searches for a counter whose counter value is not “0” in the round robin direction, selects a queue buffer corresponding to the first detected counter as a queue buffer to be read from a packet, Multiplexer 20 reads the queue buffer packet selected by queue selector 35 and outputs the read packet to line 40. Then, the counter corresponding to the queue buffer selected by the queue selection unit 35 decrements the count value. Such an operation is repeated until the count values of the counters 31 to 33 are all “0”. In FIG. 5H, the count value of the counter 31 is “0”. Therefore, the packets stored in the queue buffer 12 and the queue buffer 13 are alternately output to the line 40 until the count values of the

respective counters

32 and 33 become “0”. This is shown in FIGS. 5 (j), 5 (k), and 5 (m). Then, assuming that the packets stored in the queue buffers 11 to 13 do not disappear and the packets stored in the queue buffers 11 to 13 do not exceed the threshold value, the packets are finally stored in FIG. As shown in (n), all the count values of the counters 31 to 33 are “0”.
[0057]
When the count values of the counters 31 to 33 all become “0”, the weighting calculation unit 36 sets the predetermined weighting values of the queue buffers 11 to 13 in the counters 31 to 33. Then, the queue selection unit 35 selects a queue buffer using the values of the counters 31 to 33 in which the weighting values are set.
[0058]
Here, the packets output in the period from when the weight values are actually set to the counters 31 to 33 until the count values of all the counters become “0” are stored in the queue buffers 11 to 13 in advance. It is confirmed whether the ratio is “1: 3: 2”, which is a predetermined weighting value. As shown in FIG. 5 (n), three packets A1 to A3 are output from the queue buffer 11, and nine packets B1 to B9 are output from the queue buffer 12. There are six packets C1 to C6 output from the buffer 13. Accordingly, the ratio of packets output from each queue buffer is “3: 9: 6 = 1: 3: 2”, and the weighting value “1: 3: 2” is maintained. Recognize.
[0059]
As described above, in the first embodiment, in order to guarantee a certain percentage of bandwidth for data stored in a plurality of queue buffers, a plurality of weights are determined based on priorities based on predetermined weight values. A first algorithm for selecting a queue buffer for reading data by determining priority of the queue buffer, and a second algorithm for selecting a queue buffer for reading data by a second algorithm different from the first algorithm If the queue buffers selected by these two algorithms are different, data is output with priority given to the queue buffer selected by the second algorithm. At that time, since the priority of all queue buffers other than the priority queue buffer is raised, even when priority is given to the queue buffer selected by the second algorithm, the bandwidth guarantee of the first algorithm is guaranteed. Accuracy can be maintained.
[0060]
In order to simplify the description, the condition for selecting the queue buffer 1 by the second algorithm has been described as a threshold value. However, hysteresis may be used for the condition for selecting the queue buffer 1 by the second algorithm. .
[0061]
In the first embodiment, the limit for continuously selecting the same queue buffer by the second algorithm is set to four times. Therefore, for example, when the packet accumulated in the queue buffer 11 exceeds the threshold, the packet is continuously read out four times from the queue buffer 11 by the second algorithm, and further accumulated in the queue buffer 11. Even if the number of packets exceeds the threshold, the first algorithm is prioritized. However, the condition that gives priority to the first algorithm is not limited to this, and the following condition is also conceivable.
[0062]
By giving priority to the second algorithm, the count values of the counters other than the queue buffer selected by the second algorithm are increased. In the present invention, a limit value for increasing the count value is set, and when the count value exceeds the limit value, the queue corresponding to the counter exceeding the limit value regardless of the request of the queue monitoring unit 34 is set. A priority may be given to reading packets from the buffer, or packets may be read from the queue buffer selected by the first algorithm until the count values of all counters are equal to or less than the limit value. The limit value of the counter value may be determined by the weight value of each queue buffer, the performance required for the system, and the depth of the queue buffer implemented as a resource. That is, a compromise between achievement levels of the first algorithm and the second algorithm may be determined by the system. In this way, the second algorithm is prioritized until the count value (priority) of each counter reaches the limit value, but when the priority exceeds the limit value, the first algorithm that guarantees the bandwidth is prioritized. Thus, it is possible to determine the bit value of the counter at the time of mounting, solve the mounting problem, and prevent the phenomenon that the bandwidth guarantee cannot be maintained by continuing to observe the second algorithm.
[0063]
In the first embodiment, the second algorithm is “detecting a queue buffer in which data is concentrated before packets overflow from the queue buffer, and preferentially connecting the detected queue buffer packet to the line. Output to ". However, the second algorithm is not limited to this and may be different from the bandwidth control algorithm that guarantees the bandwidth. For example, there is a case where a bandwidth control algorithm is added to the input buffer type switch as a priority conflict with the bandwidth control algorithm. In this case, the switch exchange algorithm of the input buffer type switch may compete with the bandwidth control algorithm. When the N (N is a natural number) × N ports are exchanged, the input buffer type switch cannot flow data unless the input and output ports of the exchanged data are always connected to “1: 1”. That is, it is impossible to transfer data from a plurality of input ports to one output port by one exchange, and the exchange algorithm has a great influence on the throughput performance of the switch. Therefore, the system design should determine which of the switching algorithm performance and the bandwidth control should be prioritized.
[0064]
Embodiment 2. FIG.
A second embodiment of the present invention will be described with reference to FIGS. In the first embodiment, the bandwidth control system is maintained when a bandwidth control algorithm and a different algorithm are selected according to the normal state of the queue buffer and a fixed-length packet is output to the line. . However, in an actual system, a packet is not always a fixed length. In the second embodiment, a bandwidth control algorithm and a different algorithm are selected according to the state of the queue buffer, and the accuracy of bandwidth control is maintained even when a variable-length packet is output to the line. Is.
[0065]
FIG. 6 is a block diagram showing a configuration of a weighting priority control apparatus that operates based on the weighting priority control method according to the second embodiment of the present invention. The weighting priority control device shown in FIG. 6 includes a queue control unit 30a instead of the queue control unit 30 of the weighting priority control device of the first embodiment shown in FIG. Components having the same functions as those in the first embodiment are denoted by the same reference numerals, and redundant description is omitted.
[0066]
The queue control unit 30a includes a first algorithm that performs bandwidth control by weighting to guarantee a certain proportion of the bandwidth of the line, and a second algorithm that determines a queue buffer from which packets are to be read by an algorithm different from the bandwidth control. The queue buffers 11 to 13 are monitored, and the queue buffer selected by the first algorithm and the queue buffer selected by the second algorithm are selected based on the state of the queue buffers 11 to 13. Select which one has priority. Then, the selected queue buffer is notified to the multiplexing unit 20.
[0067]
The first algorithm uses a weighting value set for each of the plurality of queue buffers as an initial value, and priorities of the plurality of queue buffers based on a priority calculated each time data is read from each queue buffer. And a queue buffer that reads data according to the determined priority order is selected to guarantee the data bandwidth.
[0068]
The difference between the weighted priority control apparatus according to the second embodiment and the weighted priority control apparatus according to the first embodiment of the present invention is a difference in whether a packet to be handled has a variable length or a fixed length. For this reason, in the second embodiment, an algorithm different in weighting processing from the WRR method in the first embodiment is adopted.
[0069]
First, the weighting process applied to control of variable length packets will be described. Here, the weight value of the queue buffer 11 is “4”, the weight value of the queue buffer 12 is “3”, and the weight value of the queue buffer 13 is “6”. These weighting values are such that the total packet length read from the queue buffer 11 is x1, the total packet length read from the queue buffer 12 is x2, and the total packet length read from the queue buffer 13 is x3. Then, it means that the bandwidth when outputting a packet to the line 40 is maintained at a ratio of “x1: x2: x3 = 4: 6: 3”. In the first algorithm of the second embodiment, the reciprocal of these weight values is used for bandwidth control. Here, if the control value is y, the control value y is
y = (1 / weighting value) × 100 (Expression 1)
It is represented by However, y is an integer rounded to the nearest decimal point. In (Equation 1), 100 is multiplied, but the present invention is not limited to this, and when implemented by hardware, it is appropriate according to the hardware and according to the accuracy required by the system. It is sufficient to determine a correct value.
[0070]
When (Equation 1) is used, the control value y1 of the queue buffer 11 is
y1 = (1/4) × 100 = 25
The control value y2 of the queue buffer 12 is
y2 = (1/6) × 100 = 33
The control value y3 of the queue buffer 13 is
y3 = (1/3) × 100 = 17
It becomes. The weighted priority control apparatus according to the second embodiment performs band control based on these control values y1 to y3.
[0071]
The first algorithm uses the product of the head packet length of the queue buffers 11 to 13 and the control values y1 to y3 corresponding to the queue buffers 11 to 13 as a count value (priority), and compares these count values. Then, the queue buffer having the smallest count value is selected. That is, weight control is always performed with only the first packet of each queue buffer being considered. When the count values are equal, round robin or the like is additionally performed to always select one.
[0072]
Similar to the first embodiment, the second algorithm detects a queue buffer in which packets are concentrated before packets overflow from the queue buffer, and outputs the detected queue data to the line with priority. Is an algorithm for
[0073]
The queue control unit 30a includes count value registers 37 to 39 for storing weighting values corresponding to the queue buffers 11 to 13, and a queue for monitoring the total packet length of the packets stored in the queue buffers 11 to 13, respectively. The monitoring unit 34 includes a queue selection unit 35 a that determines a queue buffer from which a packet is to be read next, and a weighting calculation unit 36 a that calculates weight values of the queue buffers 11 to 13.
[0074]
The queue selection unit 35a selects the queue buffer from which the packet is to be read next based on the first algorithm or the second algorithm, and notifies the multiplexing unit 20 to read the packet in the selected queue buffer. At the same time, the selected queue buffer is notified to the weighting calculator 36a.
[0075]
In the case of the first algorithm, the queue selection unit 35a compares the count values held in the count value registers 37 to 39, searches for the smallest count value, and holds the searched count value. Select the queue buffer that corresponds to the value register. When the count values are equal, round robin or the like is additionally performed to always select one. In the case of the second algorithm, the queue selection unit 35 a selects a queue buffer in the excess information notified from the queue monitoring unit 34.
[0076]
When the count value of the count value register corresponding to the queue buffer selected by the queue selection unit 35a is “0” or more, the weighting calculation unit 36a stores the count value register corresponding to the queue buffer selected by the queue selection unit 35a. The count value is subtracted from the count value of each count value register. Then, the subtracted count value is set in the count value register. The count value register corresponding to the queue buffer selected by the queue selection unit 35a is set to the product of the leading packet length of the selected queue buffer and the control value calculated based on (Equation 1).
[0077]
When the count value of the count value register corresponding to the queue buffer selected by the queue selection unit 35a is smaller than “0”, the weighting calculation unit 36a selects the count value register corresponding to the queue buffer selected by the queue selection unit 35a. The product of the head packet length of the selected queue buffer and the control value calculated based on (Equation 1) is added to the count value. Then, the added value is set in the count value register corresponding to the queue buffer selected by the queue selection unit 35a.
[0078]
The count value registers 37 to 39 hold the product of the packet length of the first packet of the queue buffer corresponding to each counter and the control value calculated based on (Equation 1). The count value register 37 corresponds to the queue buffer 11, the count value register 38 corresponds to the queue buffer 12, and the count value register 39 corresponds to the queue buffer 13.
[0079]
7 and 8, the multiplexing unit 20 reads the packets stored in the queue buffers 11 to 13, the values of the count value registers 37 to 39, and the packets of the queue buffer selected by the queue selection unit 35a. FIG. 6 is a diagram illustrating a state in which a read packet is output to the line 40. With reference to FIGS. 7 and 8, the operation of the weighted priority control apparatus according to the second embodiment of the present invention will be described.
[0080]
First, an operation for outputting a packet based on the first algorithm will be described with reference to FIG. In FIG. 7A, the queue buffer 11 stores packets A1 to A3, the queue buffer 12 stores packets B1 to B4, and the queue buffer 13 stores packets C1 to C3. When the predetermined reference packet length is “1”, the packet length of the packet A1 is “3”, the packet length of the packet A2 is “2”, the packet length of the packet A3 is “2”, and the packet length of the packet B1 Is “1”, the packet length of the packet B2 is “2”, the packet length of the packet B3 is “3”, the packet length of the packet B4 is “1”, the packet length of the packet C1 is “2”, and the packet length of the packet C2 Is “1”, and the packet length of the packet C3 is “4”.
[0081]
In the count value register 37, a value “75” obtained by multiplying “25”, which is the control value y1 calculated by using (Equation 1), and the packet length “3” of the first packet A1 of the queue buffer 11, is the count value. A value “33” obtained by multiplying “33”, which is the control value y2 calculated using (Equation 1), by the packet length “1” of the first packet B1 of the queue buffer 12, is stored in the register 38 as a count value register 39. Is set to a value “34” obtained by multiplying the control value y3 “17” calculated by using (Equation 1) by the packet length “2” of the first packet C1 of the queue buffer 13.
[0082]
Here, the threshold value predetermined for the queue monitoring unit 34 is set to a packet length of seven reference packet lengths as indicated by a dotted line. The total packet length of the packets A1 to A3 stored in the queue buffer 11, the total packet length of the packets B1 to B4 stored in the queue buffer 12, and the packets C1 to C3 stored in the queue buffer 13 The total packet length is “7”, and does not exceed the threshold.
[0083]
The queue selection unit 35a compares the count values set in the count value registers 37 to 39 to search for the smallest count value, and selects a queue buffer corresponding to the searched count value register. Then, the multiplexing unit 20 is notified to read the packet of the selected queue buffer, and the selected queue buffer is notified to the weighting calculation unit 36a. Here, since the count value “33” held in the count value register 38 is the smallest, the queue selection unit 35 a selects the queue buffer 12.
[0084]
As shown in FIG. 7B, the multiplexing unit 20 reads the packet B1 from the queue buffer 12 and outputs the read packet B1 to the line 40. Since the count value of the count value register 38 is equal to or greater than “0”, the weighting calculation unit 36a subtracts the count value of the count value register 38 from each count value of the count value registers 37 to 39, and newly calculates the subtracted value. Is set in the count value registers 37 to 39 as a count value.
[0085]
Here, as shown in FIG. 7A, the count value of the count value register 37 is “75”, the count value of the count value register 38 is “33”, and the count value of the count value register 39 is “34”. is there. Therefore, the count value of the count value register 37 is “42”, the count value of the count value register 38 is “0”, and the count value of the count value register 39 is “1”.
[0086]
Since the packet B1 of the queue buffer 12 is read, the weighting calculation unit 36a calculates the control value of the queue buffer 12 calculated based on the packet length “2” of the first packet B2 of the queue buffer 12 and (Equation 1). The product “66” with “33” which is y 2 is set in the count value register 38. Accordingly, as shown in FIG. 7B, the count value of the count value register 37 is “42”, the count value of the count value register 38 is “66”, and the count value of the count value register 39 is “1”.
[0087]
As described above, in the first algorithm, the queue selection unit 35a compares the count values of the count value registers 37 to 39 to search for the smallest count value, and the queue buffer corresponding to the searched count value register. The multiplexing unit 20 outputs the first packet stored in the selected queue buffer to the line 40. The weighting calculation unit 36a subtracts the count value of the count value register corresponding to the selected queue buffer from the value of each count value register, and sets a new count value in each count value register. In the count value register corresponding to the selected queue buffer, an operation for setting the product of the packet length of the first packet of the queue buffer and the control value calculated using (Equation 1) as the count value is performed. repeat. The multiplexing unit 20 reads out the packets stored in the queue buffers 11 to 13 at that time, the values in the count value registers 37 to 39, and the packets in the queue buffer selected by the queue selection unit 35a. FIG. 7 (c) to FIG. 7 (f) show a state in which is output to the line 40. FIG.
[0088]
Here, as in the case of the WRR method and the WRQ method, when the packets accumulated in the queue buffer are congested, the first algorithm sets a bandwidth equal to or greater than a certain ratio of the output destination bandwidth for each queue buffer. Briefly explain that it can be guaranteed.
[0089]
For packets read to the output destination within a certain time t, the number of packets read from the queue buffer S (here, the queue buffers 11 to 13 and S = 11, 12, and 13) Ns (here, 1, 2,..., Ns for each queue buffer S), the packet length of each packet read from the queue buffer S is sPn, and the weight for each queue buffer is Bs. In order for the queue buffer S bandwidth to be maintained at a weighted value,
[Expression 1]

Need to hold.
[0090]
[Expression 2]

Represents the actual bandwidth output from the queue buffer S, and it is sufficient that each ratio corresponds to Bs. Strictly speaking, the terms in (Equation 2) must be equal (connected by “=”), but they are not equal at a finite time t because the packet length is variable. Expressing (Equation 2) in the form of a ratio,
[Equation 3]

It becomes. Here, since the time t is common, it is deleted. And the terms in Σ of each term, ₁₁ P ₁ / B ₁₁ , ₁₁ P ₂ / B ₁₁ , ₁₁ P _Three / B ₁₁ , ..., ₁₁ P _n / B ₁₁ Is exactly “the first packet length of the queue buffer 11 × the reciprocal of the weighting value” calculated by the weighting calculation unit 36a. Therefore, performing the operation as described above always maintains the difference between the terms of (Expression 3) at a certain time t as small as possible (not minimum). Strictly speaking, it must be the minimum, but when implemented in hardware, it is sufficient as one of the bandwidth control methods considering other requirements.
[0091]
Next, with reference to FIG. 8, the operation in which the weighting priority control apparatus according to the second embodiment of the present invention outputs a packet based on the second algorithm will be described.
[0092]
In FIG. 8A, the queue buffer 11 stores packets A1 to A3, the queue buffer 12 stores packets B1 to B4, and the queue buffer 13 stores packets C1 to C4. When the predetermined reference packet length is “1”, the packet length of the packet A1 is “3”, the packet length of the packet A2 is “2”, the packet length of the packet A3 is “2”, and the packet length of the packet B1 Is "1", the packet length of the packet B2 is "2", the packet length of the packet B3 is "3", the packet length of the packet B4 is "1", the packet length of the packet C1 is "2", the packet length of the packet C2 Is “1”, and the packet length of the packet C3 is “4”.
[0093]
In the count value register 37, a value “75” obtained by multiplying “25”, which is the control value y1 calculated by using (Equation 1), and the packet length “3” of the first packet A1 of the queue buffer 11, is the count value. A value “33” obtained by multiplying “33”, which is the control value y2 calculated using (Equation 1), by the packet length “1” of the first packet B1 of the queue buffer 12, is stored in the register 38 as a count value register 39. Is set to a value “34” obtained by multiplying the control value y3 “17” calculated by using (Equation 1) by the packet length “2” of the first packet C1 of the queue buffer 13.
[0094]
Here, the threshold value predetermined for the queue monitoring unit 34 is set to a packet length corresponding to seven reference packet lengths as indicated by a dotted line. The total packet length of the packets A1 to A3 stored in the queue buffer 11, the total packet length of the packets B1 to B4 stored in the queue buffer 12, and the packets C1 to C3 stored in the queue buffer 13 The total packet length is “7”, and does not exceed the threshold. Therefore, the queue control unit 30a selects the queue buffer based on the first algorithm described above, and the multiplexing unit 20 reads the packet selected by the queue control unit 30a and sends the read packet to the line 40. The packet is output to the line 40 in the order of the packet B1, the packet C1, the packet C2, and the packet A1 (see FIGS. 7B to 7E).
[0095]
Here, as shown in FIG. 8B, it is assumed that a packet C4 having a packet length “1” and a packet C5 having a packet length “3” are stored in the queue buffer 13. The total packet length of the packets C3 to C5 stored in the queue buffer 13 is “8”, which exceeds the threshold “7”. The queue monitoring unit 34 detects that the total packet length of the packets C3 to C5 accumulated in the queue buffer 13 exceeds the threshold, and notifies the queue buffer 13 that the threshold has been exceeded. Information is output to the queue selector 35a.
[0096]
Since the excess information is notified from the queue monitoring unit 34, the queue selection unit 35a selects the queue buffer 13 included in the notified excess information. That is, the queue buffer 13 selected based on the second algorithm is prioritized rather than the queue buffer 12 having the smallest count value based on the first algorithm, and is multiplexed so that packets in the queue buffer 13 are read out. To the control unit 20.
[0097]
The multiplexing unit 20 reads the packet C3 from the queue buffer 13 and outputs the read packet C3 to the line 40. The weighting calculation unit 36a subtracts the count value of the count value register 39 from the count values of the count value registers 37 to 39, and sets the subtracted value in the count value registers 37 to 39 as a new count value.
[0098]
As shown in FIG. 8B, the count value of the count value register 37 is “50”, the count value of the count value register 38 is “24”, and the count value of the count value register 39 is “44”. Therefore, the count value of the count value register 37 is “6”, the count value of the count value register 38 is “−20”, and the count value of the count value register 39 is “0”.
[0099]
Since the packet C3 of the queue buffer 13 has been read, the weighting calculation unit 36a calculates the control value of the queue buffer 13 calculated based on the packet length “1” of the leading packet C4 of the queue buffer 13 and (Equation 1). A value “17” obtained by multiplying “17”, which is y3, is set in the count value register 37. Therefore, as shown in FIG. 8C, the count value of the count value register 37 is “6”, the count value of the count value register 38 is “−20”, and the count value of the count value register 39 is “17”. .
[0100]
Here, it is assumed that a packet A4 having a packet length “2” and a packet A5 having a packet length “3” are accumulated in the queue buffer 11 (see FIG. 8C). The total packet length of the packets A2 to A5 stored in the queue buffer 11 is “8”, which exceeds the threshold “7”. The queue monitoring unit 34 detects that the total packet length of the packets A2 to A5 accumulated in the queue buffer 11 has exceeded the threshold value, and exceeds the queue buffer 11 for notifying that the queue buffer 11 has exceeded the threshold value. Information is output to the queue selector 35a.
[0101]
Since the excess information is notified from the queue monitoring unit 34, the queue selection unit 35 a selects the queue buffer 11 included in the notified excess information and reads the packet from the queue buffer 11 to the multiplexing unit 20. Notice.
[0102]
The multiplexing unit 20 reads the packet A2 from the queue buffer 11 and outputs the read packet A2 to the line 40. The weighting calculation unit 36a subtracts the count value of the count value register 37 from the count values of the count value registers 37 to 39, and sets the subtracted value in the count value registers 37 to 39 as a new count value.
[0103]
As shown in FIG. 8C, the count value of the count value register 37 is “6”, the count value of the count value register 38 is “−20”, and the count value of the count value register 39 is “17”. Therefore, the count value of the count value register 37 is “0”, the count value of the count value register 38 is “−26”, and the count value of the count value register 39 is “11”.
[0104]
Since the packet A2 of the queue buffer 11 is read, the weighting calculation unit 36a calculates the control value of the queue buffer 11 calculated based on the packet length “2” of the first packet A3 of the queue buffer 11 and (Equation 1). The product “50” with “25” which is y 1 is set in the count value register 37. Therefore, as shown in FIG. 8D, the count value of the count value register 37 is “50”, the count value of the count value register 38 is “−26”, and the count value of the count value register 39 is “11”. .
[0105]
As shown in FIG. 8 (d), the packet A2 of the queue buffer 11 is output, and there is no packet newly accumulated in the queue buffers 11-13, so that the packets are accumulated in the queue buffers 11-13. None of the total packet lengths of the packets exceeds the threshold. Therefore, the queue selection unit 35a selects a queue buffer based on the first algorithm. That is, the queue buffer corresponding to the count value register having the smallest count value in each of the count value registers 37 to 38 is selected. In FIG. 8D, the queue selection unit 35a selects the queue buffer 12 with the count value “−26”, and the multiplexing unit 20 outputs the packet B2 of the queue buffer 12 to the line 40.
[0106]
The weighting calculation unit 36a multiplies the packet length “3” of the leading packet B3 of the queue buffer 12 by “33”, which is the control value y2 of the queue buffer 12 calculated based on (Equation 1). Is added to the count value “−26” of the count value register 38. Then, the added value “73” is set in the count value register 38. The weighting calculation unit 36a does not change the count values of the count value register 37 and the count value register 39 corresponding to the queue buffer 11 and the queue buffer 13. That is, when the count value of the count value register corresponding to the queue buffer from which the packet is read is smaller than “0” (when the count value is a negative number), the weighting calculation unit 36a newly sets the count value of the other count value register. The product of the packet length and the control value is added to the count value of the count value register corresponding to the queue buffer from which the packet has been read. Then, the added value is set in the count value register corresponding to the queue buffer from which the packet has been read. Therefore, as shown in FIG. 8E, the count value of the count value register 37 is “50”, the count value of the count value register 38 is “73”, and the count value of the count value register 39 is “11”. The count values of the value registers 37 to 39 are all “0” or more.
[0107]
Thereafter, the queue selection unit 35a compares the count values of the count value registers 37 to 39, selects the queue buffer 13 corresponding to the count value register with the smallest count value, and the multiplexing unit 20 The packet C4 in the buffer 13 is output to the line 40. Then, the weighting calculation unit 36a subtracts the count value of the count value register 39 from the count value of the count value registers 37 to 39 and calculates based on the packet length of the first packet C5 of the queue buffer 13 and (Equation 1). By multiplying the control value y3, the count values of the count value registers 37 to 39 are calculated and set in the respective count value registers. This is shown in FIG.
[0108]
As described above, in the second embodiment, in order to guarantee a certain percentage of bandwidth for data stored in a plurality of queue buffers, a plurality of weights are determined based on priorities based on predetermined weight values. A first algorithm for selecting a queue buffer for reading data by determining priority of the queue buffer, and a second algorithm for selecting a queue buffer for reading data by a second algorithm different from the first algorithm If the queue buffers selected by these two algorithms are different, data is output with priority given to the queue buffer selected by the second algorithm. At this time, since the priority of the priority queue buffer is lowered, even when priority is given to the queue buffer selected by the second algorithm, the accuracy of the bandwidth guarantee of the first algorithm can be maintained. it can.
[0109]
Note that the limit on how many negative values are allowed as handling when the value of the count value register becomes a negative number greatly affects the feasibility. This limit is determined by a value (in this case, 100) multiplied to convert the reciprocal of the weight to an integer and a value normalized as the packet length (in this case, from 1 to a maximum of 4). Although it depends on the performance required for the system, it is reasonable to be able to borrow the maximum length of packets, from several to tens of packets. Of course, the depth of the queue buffer implemented as a resource is also a factor that determines this value. In this case, when the count value register of a certain queue buffer reaches a negative limit value, this time, it corresponds to the count value register that has reached the negative limit regardless of the request of the queue monitoring unit 34. It is only necessary to balance the achievement of each other's algorithm such that the highest priority is given to reading packets from the queue buffer.
[0110]
In the first and second embodiments, the bandwidth control is described as the first algorithm and the control based on the data length held in the queue buffer is described as the second algorithm. However, the present invention is not limited to this. The present invention can be applied in an environment where there are a plurality of priority control processes from which data is to be read and these priority control processes may collide.
[0111]
【The invention's effect】
As described above, the priority value of a plurality of queue buffers is set based on the priority calculated each time data is read from each queue buffer, with the weighting value assigned to each queue buffer 1 as an initial value. And the queue buffer selected by the first algorithm that guarantees the bandwidth of the data by selecting the queue buffer 1 for reading the data according to the determined priority, and the data by a process different from the first algorithm If the queue buffer selected by the second algorithm for selecting the queue buffer to read is different from the queue buffer selected by the second algorithm, the queue buffer selected by the second algorithm is given priority unless a predetermined condition is satisfied. All queue buffers except the preferred queue buffer Because it has to increase the priority, even when the priority of the queue buffer that is selected by the second algorithm, it is possible to maintain the accuracy of band guarantee first algorithm.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of a weighting priority control apparatus that operates based on a weighting priority control method according to Embodiment 1 of the present invention.
FIG. 2 is a diagram for explaining the operation of the weighting priority control apparatus shown in FIG. 1;
FIG. 3 is a diagram for explaining the operation of the weighted priority control apparatus shown in FIG. 1;
FIG. 4 is a diagram for explaining the operation of the weighted priority control apparatus shown in FIG. 1;
FIG. 5 is a diagram for explaining the operation of the weighting priority control apparatus shown in FIG. 1;
FIG. 6 is a block diagram showing a configuration of a weighting priority control apparatus that operates based on the weighting priority control method according to the second embodiment of the present invention.
7 is a diagram for explaining the operation of the weighted priority control apparatus shown in FIG. 6;
FIG. 8 is a diagram for explaining the operation of the weighted priority control apparatus shown in FIG. 6;
[Explanation of symbols]
11, 12, 13 Queue buffer, 20 Multiplexing unit, 30 Queue control unit, 31, 32, 33 Counter, 34 Queue monitoring unit, 35, 35a Queue selection unit, 36, 36a Weighting operation unit, 37, 38, 39 Count value register, 40 lines.

Claims

A weighted priority control method for guaranteeing the bandwidth of the data by reading data stored in a plurality of queue buffers from each queue buffer at a ratio of a weight value assigned to each of the plurality of queue buffers. And
A queue that reads the data according to the determined priorities, determining the priorities of the plurality of queue buffers based on the priorities calculated each time data is read from each queue buffer, with the weighting value as an initial value. A first algorithm that guarantees a bandwidth of the data by selecting a buffer; and a second algorithm that selects a queue buffer that reads data by processing different from the first algorithm, and When the queue buffers selected by the first algorithm and the second algorithm are different, the queue buffer selected by the second algorithm is prioritized unless the predetermined condition is satisfied, and the priority queue buffer is selected. Priorities in the first algorithm for all queue buffers other than buffers Weighted priority control method comprising performing the process of increasing.

The predetermined condition is a case where the priority of the plurality of queue buffers is equal to or higher than a predetermined value. At this time, the queue buffer selected by the first algorithm is selected with priority. The weighting priority control method according to claim 1.

The predetermined condition is a case where the priority of the plurality of queue buffers is equal to or higher than a predetermined value. In this case, priority is given to selecting a queue buffer whose priority is equal to or higher than the predetermined value. 2. The weighted priority control method according to claim 1, wherein

The predetermined condition is when the priority queue buffer is the same queue buffer continuously for a predetermined number of times, and at this time, the queue buffer selected by the first algorithm is given priority. The weighting priority control method according to claim 1.

The second algorithm is:
When the total packet length of a plurality of data stored in the plurality of queue buffers exceeds a predetermined value, a queue buffer having the total packet length exceeding a predetermined value is selected. Item 5. The weighting priority control method according to any one of Items 1 to 4.

In the first algorithm, the order of reading the data of the plurality of queue buffers is determined, and each time the data is read, the priority of the queue buffer from which the data is read is decremented, and the priority is A weighted round-robin that selects a queue buffer from which data is read by resetting the priority to the weighting value when all the priorities become zero, and selecting a queue buffer from which zero queue buffers are excluded from selection. Even when data is read with priority given to the queue buffer selected by the above algorithm, the priority of the queue buffer from which the data was read is decremented. The weight according to any one of claims 1 to 5, wherein all the priorities are increased by adding the weighting value every time. Only priority control method.

A weighted priority control method for guaranteeing the bandwidth of the data by reading data stored in a plurality of queue buffers from each queue buffer at a ratio of a weight value assigned to each of the plurality of queue buffers. And
A queue buffer for determining the priority of the plurality of queue buffers based on the priority calculated based on the head data stored in each of the queue buffers and a weighting value, and reading the data according to the determined priority; A first algorithm that guarantees the bandwidth of the data by selecting, and a second algorithm that selects a queue buffer from which data is read by a process different from the first algorithm, and When the queue buffer selected by the second algorithm is different, the queue buffer selected by the second algorithm is prioritized unless a predetermined condition is satisfied, and the priority queue buffer is selected. Weighting priority control for performing processing for lowering priority in the first algorithm Law.

The predetermined condition is a case where the priority of the plurality of queue buffers is equal to or lower than a predetermined value. At this time, priority is given to selecting a queue buffer whose priority is equal to or lower than the predetermined value. 8. The weighted priority control method according to claim 7, wherein

The second algorithm is:
When the total packet length of a plurality of data stored in the plurality of queue buffers exceeds a predetermined value, a queue buffer having the total packet length exceeding a predetermined value is selected. Item 9. The weighting priority control method according to Item 7 or 8.

The first algorithm includes a control value that is a product of a reciprocal of a weight value of the plurality of queue buffers and a predetermined value, and a packet of a leading packet stored in the plurality of queue buffers. The queue buffer having the lowest priority is selected with the product of the length as the initial value of the priority, and the priority of the queue buffer selected by the first algorithm is zero or positive. In the case of a number, the priority of the selected queue buffer is subtracted from the priorities of all the queue buffers, and the priority value of the selected queue buffer is set to the initial value using the data length next to the head. If the priority of the selected queue buffer is negative, the initial value is calculated based on the next data after the data read from the selected queue buffer. The value obtained by adding the calculated initial value and the current priority of the selected queue buffer is set as the priority to lower the priority of the selected queue buffer, and is selected by the second algorithm. If priority is given to the queue buffer, the priority of the selected queue buffer is subtracted from the priority of all queue buffers, and the priority of the selected queue buffer is the data length that is next to the head. The weighting priority control method according to claim 7, wherein an initial value is set using