JP4806716B2 - 通信品質制御装置、及び通信品質制御方法 - Google Patents

Description

本発明は、通信品質制御装置、及び通信品質制御方法に関する。

データ通信以外に音声電話やＴＶ電話など、多様な通信サービスがインターネットを介して提供されている。このような多様化に伴い、柔軟性と高速性を両立するために、各キュー（Queue、待ち行列）、スケジューラ、そしてシェーパ(Shaper)をセレクタにより接続し、送信要求と要求受理信号のハンドシェークを用いたＱｏＳ（Quality of Service）方式が提案されてきた（例えば、特許文献１、２参照）。なお、ＱｏＳとは、ネットワーク上で、通信のための帯域を予約した際に、一定の通信品質を保証する技術である。

さらに、このＱｏＳ方式に用いるスケジューリング方法が提案されている（例えば、特許文献３、４参照）。この方式は、各入力に指定された重みをクロックサイクル毎に時分割、あるいは、加算値の変更により各入力に設置されるカウンタへ各入力の重みに比例した値を加算し、カウンタの値が０または正であり、送信要求を受けている入力をラウンドロビン（Round Robin）により選択し、後段に送信要求を送信（伝達）する。上記ラウンドロビンとは、リソースを順番に割り振ることにより選択される入力の偏りをなくすことを行う方式である。

従来の通信品質制御装置は、送信時、選択された入力カウンタから要求パケットの長さ分を減じ、送出機会を他の入力より下げる。もし、加算値が小さい場合には、次の送出機会までの時間が長くなることにより、出力レートは低下する。一方、もし、加算値が大きい場合には、次の送出機会までの時間が短くなることにより、出力レートは増加する。これにより、重み付け公平制御が行われている。

送信要求したパケットが出力されると、送信要求が通過したパスを経由し、送信受理信号が戻ってくる。この送信受理信号を受けた場合、先に選択された送信要求入力に対して受理信号を送出する。

特開２００５−３１１４０９号公報 特開２００５−３２３２３０号公報 特開２００７−１１０４８３号公報 特開２００７−１１０５１５号公報

しかしながら、従来の通信品質制御装置は、受理信号を送出後すぐに次に送出するパケットを選択すると誤った入力を選択してしまうので、ある一定期間、選択を行わず（ＷａｉｔＣｎｔと言う変数をカウントダウンすることにより計測）、一定期間経過後（ＷａｉｔＣｎｔと言う変数が０となった場合）に入力選択を開始する。精度や、動作速度に影響が発生するため、従来の通信品質制御装置は、この一定期間中にも、先に記述した重みに比例する値を加算しなければならない。但し、送信要求を受けておらず、入力カウンタが正であり、送信受理信号を受け取った、あるいはＷａｉｔＣｎｔが０になった場合、従来の通信品質制御装置は、そのカウンタに蓄積されていた値を総カウンタに戻さなければならない。このため、従来の通信品質制御装置は、処理が複雑で、かつ各入力は最大フレームサイズの負数分のレジスタを持たなければならず、かつそれらがすべて総カウンタに戻った場合のレジスタを持たなければならないので、回路規模が大きくなる。

また、重みの範囲が大きくなった場合（例えば、１：１５→１：２５５）、従来の通信品質制御装置は、正確なカウンタへの加算ができなくなる。これは、加算時にある入力カウンタに対しては１が加算され、他のある入力には、２５５が一度に加算されることになり、パケットがバーストして送信される可能性があるからである。例えば、２５５が加算された入力に蓄積されているパケット長が６４Ｂｙｔｅである場合、３パケット（２５５／６４＝３．９８）が一度に送出される可能性がある。

また、従来技術で提案されているスケジューリング方法は、優先制御、あるいは重み付け公平制御を同時に実行することはできず、排他的な動作を余儀なくされる。そのため、優先制御の後に重み付け公平制御を行う、あるいは重み付け公平制御を行った後で優先制御を行うために、従来の通信品質制御装置は、スケジューラ等の接続関係を変更するためのセレクタを必要とする。そのため、回路規模がさらに増大するという問題がある。

また、従来技術では、各入力への重みの加算速度は、そのスケジューラが取り扱う最大性能に合わせなければならない。このため、従来の通信品質制御装置は、加算回路の並列化／動作周波数の上昇／加算単位の増加のいずれか、あるいは併せた対策を行う必要があり、回路規模の増大、消費電力の増大、設計の複雑さの増大、スケジューリング精度の低下といった問題を生じる。

本発明は、このような事情を考慮してなされたものであり、その目的は、回路規模の縮小・スケジューリング精度の向上を図ることができる通信品質制御装置、及び通信品質制御方法を提供することにある。

上述した課題を解決するために、本発明は、スケジューリング回路の入力ポート毎に設定された重み値に基づいて出力優先順位を決定し、該出力優先順に従って前記入力ポート毎に割り振られた送信パケットを出力する通信品質制御装置において、前記スケジューリング回路は、前記入力ポート毎に保持されている複数の参照値である、送信パケットの送信要求、優先度、商、及びラウンドロビン値のうち少なくとも優先度と商を結合して、入力選択用比較値を生成する入力選択比較値生成手段と、前記入力選択用比較値を比較し、最も値が小さい入力ポートを選択する選択手段と、前記最も値が小さい入力ポートに対する送信パケットのフレーム長を、当該入力ポートに対して設定されている重み値で除算する算出手段と、前記算出手段による除算結果である商及び余りを、次回の入力ポート選択時に、前記入力選択比較値生成手段により前記入力選択用比較値を生成する際の前記複数の参照値の１つとして当該入力ポートに対して保持する保持手段と、入力ポートに付されたグループ番号が前記最も値が小さい入力ポートに付されたグループ番号と一致している場合には、前記最も値が小さい入力ポートに付されたグループ番号と同一のグループ番号が付される入力ポートに対する商及び余りを、前記最も値が小さい入力ポートに対する商及び余りにより上書きし、入力ポートに付されたグループ番号が前記最も値が小さい入力ポートに付されたグループ番号と一致していない場合には、グループ番号が一致していない他の入力ポートに対する商を前記最も値が小さい入力ポートに対する商で減じる制御手段と、を備えることを特徴とする通信品質制御装置である。

また本発明は、上記の発明において、前記入力選択比較値生成手段は、重み付け公平制御、優先制御、重み付け公平制御と優先制御、または優先制御と重み付け公平制御のいずれを実行するかに応じて、前記入力選択用比較値を生成するための参照値の組み合わせを変えて、前記入力選択用比較値を生成する、ことを特徴とする。

また、上述した課題を解決するために、本発明は、スケジューリング回路の入力ポート毎に設定された重み値に基づいて出力優先順位を決定し、該出力優先順に従って前記入力ポート毎に割り振られた送信パケットを出力する通信品質制御方法において、前記スケジューリング回路の入力ポート毎に保持されている複数の参照値である、送信パケットの送信要求、優先度、商、及びラウンドロビン値のうち少なくとも優先度と商を結合して、入力選択用比較値を生成するステップと、前記入力選択用比較値を比較し、最も値が小さい入力ポートを選択するステップと、前記最も値が小さい入力ポートに対する送信パケットのフレーム長を、当該入力ポートに対して設定されている重み値で除算するステップと、前記除算結果である商及び余りを、次回の入力ポート選択時に、前記入力選択用比較値を生成する際の前記複数の参照値として当該入力ポートに対して保持するステップと、入力ポートに付されたグループ番号が前記最も値が小さい入力ポートに付されたグループ番号と一致している場合には、前記最も値が小さい入力ポートに付されたグループ番号と同一のグループ番号が付される入力ポートに対する商及び余りを、前記最も値が小さい入力ポートに対する商及び余りにより上書きし、入力ポートに付されたグループ番号が前記最も値が小さい入力ポートに付されたグループ番号と一致していない場合には、グループ番号が一致していない他の入力ポートに対する商を前記最も値が小さい入力ポートに対する商で減じるステップと、を含むことを特徴とする通信品質制御方法である。

また本発明は、上記の発明において、前記入力選択比較値は、重み付け公平制御、優先制御、重み付け公平制御と優先制御、または優先制御と重み付け公平制御のいずれを実行するかに応じて、前記複数の参照値の組み合わせを変えて生成される、ことを特徴とする。

この発明によれば、通信品質制御装置は、加減算処理への要求性能を大幅に削減することができ、回路規模の縮小・スケジューリング精度の向上を図ることができるという利点が得られる。

また、この発明によれば、優先制御のみ／重み付け公平制御のみ／前段優先制御・後段重み付け公平制御／前段重み付け公平制御・後段優先制御を実現することが可能となり、通信品質制御装置は、従来手法で必要であったセレクタを廃することが可能となり、更なる回路規模を削減することができるという利点が得られる。

本発明の第１実施形態によるＱｏＳ回路の構成を示すブロック図である。 フレーム長に対して浮動小数点演算、余りを計算に入れ込んだ固定小数点演算、あるいは余りを計算に入れない固定小数点演算を行う場合での累積値を示す概念図である。 入力数３のＷＦＱ（Weighted Fair Queuing：重み付け公平制御）において、各レジスタ値がどのように変化するかの一例を示す概念図である。 本第１実施形態によるスケジューリング回路１０の構成を示すブロック図である。 本第１実施形態において、ＷＦＱあるいは、前段ＰＱ（Priority queuing：優先制御）後段ＷＦＱ制御時の動作を説明するためのフローチャートである。 本第１実施形態において、ＰＱあるいは、前段ＷＦＱ後段ＰＱ制御時の動作を説明するためのフローチャートである。 ＷＦＱあるいは、前段ＰＱ後段ＷＦＱ制御時の入力選択用比較値を示す概念図である。 ＰＱあるいは、前段ＷＦＱ後段ＰＱ制御時の入力選択用比較値を示す概念図である。 入力の重みで除される数値（被除数）を示す概念図である。 ＷＦＱモードでの動作概要を示す概念図である。 前段ＰＱで後段ＷＦＱモードでの動作概要を示す概念図である。 ＰＱモードでの動作概要を示す概念図である。 前段ＷＦＱで後段ＰＱモードでの動作概要を示す概念図である。 本発明の第２実施形態による、ＱｏＳ回路の構成を示すブロック図である。

以下、本発明の一実施形態を、図面を参照して説明する。

Ａ．第１実施形態
まず、本発明の第１実施形態について説明する。
図１は、本発明の第１実施形態によるＱｏＳ回路の構成を示すブロック図である。図において、ＱｏＳ回路に入力されたパケットは、受信部１において受信処理が行われ、識別部２、ＦＩＦＯ（First-In First-Out）３に供給される。識別部２では、例えば、ＴＯＳ（Type Of Service）値や、ＩＰアドレス、ポート番号によって品質クラス分けされ、結果を識別結果生成部４に供給する。なお、ＴＯＳ値は、ＩＰパケットのヘッダに含まれ、ＱｏＳを制御する目的で処理の優先度を指定するために用いられる。

識別結果生成部４では、当該ＱｏＳ回路において使われる制御情報（パケット長、仮想品質クラス、出力ポート等）を生成し、送信パケット生成部５に供給する。送信パケット生成部５では、識別結果生成部４から制御情報を受けることで、ＦＩＦＯ３からデータを読み出し、ＴＴＬ（Time To Live）減算や、ＮＡＴ（Network Address Translation）処理に伴うパケットの書き換えを行い、識別結果生成部４から受けたデータと共にパケット書き込み部６に供給する。

なお、上記ＴＴＬ減算とは、パケット転送処理を行う際にパケットの生存時間（ＴＴＬ）を減算し、データの行き先が見つからずに無限ループに陥ることを防ぐための処理である。また、ＮＡＴ処理とは、ネットワークで用いられる、ローカルアドレスとグローバルアドレスとを相互変換する処理である。

パケット書き込み部６では、受け取ったパケットや、識別結果をパケットバッファ７に格納する。また、パケット書き込み部６では、書き込んだパケットに関するパケット情報を識別結果等から生成し、キュー部８に渡す。キュー部８は、例えばメモリであって、複数のインタフェース毎にパケット情報を保持するキューを有する。キュー判定部９では、受け取ったパケット情報を、複数のインタフェースのうち、どのインタフェースのどのキューにキューイングするのかを判定するための制御情報である、仮想品質クラスおよび出力ポート等から判定してキューイングする。もし、キューが空であれば、キュー判定部９は、キュー部８のキュー毎に、送信要求、フレーム長、キュー番号をスケジューリング回路１０に送出させる。スケジューリング回路１０は、受信した情報の送出先の空き状況や、内部状態に応じて、優先制御や、重み付けラウンドロビン、シェーピング(Shaping)などによりスケジューリングし、パケット読み出し部１１に送出する。

なお、上記重み付けラウンドロビンとは、重み付けに従ってリソースを順番に割り振ることを意味する。また、シェーピングとは、ネットワーク上のトラフィックを制御し、パケットを遅延させることで通信性能を保証する方式である。

送出要求を受け取ったパケット読み出し部１１は、受け取った要求に対するキュー番号からパケット情報をキュー部８から取得し、送出要求されたパケットがパケットバッファ７のどの位置にあるのかなどの情報を読み出す。また、パケット読み出し部１１は、送信部１２に対してパケットの送出が可能か調べ、可能であれば、先に取得した位置に従って、パケットバッファ７からパケットを読み出し、送信部１２に対してパケットを送出する。さらにパケット読み出し部１１は、併せてスケジューリング回路１０に対して送信要求受理信号を送出する。

送信部１２では、出力状態を監視しており、パケットを送出可能状態にあるかどうかをパケット読み出し部１１に通知するとともに、パケット読み出し部１１から受け取ったパケットを、その出力形式に合わせて送出する。また、受理信号を受けたキュー部８は、当該キューにキューイングされている先頭キューを削除し、結果、次のキューが残っている場合、そのキューに対する送信要求をスケジューリング回路１０に対して送出する。

次に、スケジューリング回路１０について詳しく実施形態を説明するが、その前に、既出の重み付け公平制御回路の基本動作を説明する。上記において、既出の重み付け公平制御回路は重みに比例した値を加算すると説明したが、以下では、これを減算に置き換えて説明する。同様に、パケット送出時、そのパケット長により入力カウンタを減算すると説明したが、加算に置き換えて説明する。

（Ｓ１）既出の重み付け公平制御回路は、キュー部８から送信要求を受信する。

（Ｓ２）パケット読み出し部１１に出力選択された入力からのパケット情報と送信要求とを出力する。

（Ｓ３）出力選択された入力ポートのカウンタに、送信要求したパケットのパケット長を加算する。

（Ｓ４）各入力ポートのカウンタから、入力ポート毎に予め設定された重み値を所定の周期（例えば、システムクロック毎）で減算する。この減算は、当該入力に対する送信要求がなくなったとき（ＷａｉｔＣｎｔが０で送信要求が検出されないとき）、停止すると共に、負数分をトータルカウンタへ戻す。

（Ｓ５）パケット読み出し部１１から受理信号を受信した場合、キュー部８に受理信号を出力する。

（Ｓ６）待ち制御を行うカウンタであるＷａｉｔＣｎｔに、待ちの上限値であるＪｕｄｇｅＷａｉｔの値を設定する。

（Ｓ７）ＷａｉｔＣｎｔの値が０になるまでＷａｉｔＣｎｔの値を所定の周期（例えば、システムクロック毎）で１ずつ減算する。

（Ｓ８）ＷａｉｔＣｎｔの値が０になったときに、入力カウンタの値が０以下になっている入力ポートを選択する。

すなわち、既出の重み付け公平制御回路は、上記ステップＳ４において所定の周期で重み値により減算してゆき、０以下になった入力ポートからの要求を、パケット読み出し部１１への送信要求とする。また、既出の重み付け公平制御回路は、複数が０以下になっている場合には、ラウンドロビンで入力を選択する（上記ステップＳ２へ）。入力カウンタは、パケット読み出し部１１に送信要求を出力した時点で、上記ステップＳ３によりフレーム長が加算される。入力ポートへの送信要求がなくなった場合、ステップＳ１を行い、次の送信要求が受信されるのを待つ。

このように、既出の重み付け公平制御回路は、カウンタを制御することで、パケット読み出し部１１への送信要求の送出タイミングを適切に制御することが可能となる。

上述したＷＦＱ（Weighted Fair Queuing：重み付け公平制御）回路の動作を数式で表現し、それに基づき、以下では、本実施形態のＷＦＱ制御についての基本原理を説明する。

本実施形態のＷＦＱ制御において、入力カウンタをｃｎｔ［ｉ］（ｉは入力ポートの番号）、重み値をｗｅｉｇｈｔ［ｉ］（ｉは、入力ポートの番号）、フレーム長をｆｌｅｎとすると、各入力カウンタｃｎｔ［ｉ］の値は、所定の周期で重み値により減算されることから、次式（１）のようになる。

ｃｎｔ［ｉ］＝ｃｎｔ［ｉ］−ｗｅｉｇｈｔ［ｉ］ ……（１）
但し、ｃｎｔ［ｉ］＞０

上記数式（１）の両辺をｗｅｉｇｈｔ［ｉ］で除算すると、
ｃｎｔ［ｉ］／ｗｅｉｇｈｔ［ｉ］＝ｃｎｔ［ｉ］／ｗｅｉｇｈｔ［ｉ］−１
となる。

ここで、ＣＮＴ［ｉ］＝ｃｎｔ［ｉ］／ｗｅｉｇｈｔ［ｉ］とすると、次式（２）で表される。

ＣＮＴ［ｉ］＝ＣＮＴ［ｉ］−１ ……（２）

この場合、最初にｃｎｔ［ｉ］が０以下となるのは、明らかに、｜ＣＮＴ［ｉ］｜が最も小さい入力の場合である。このことから、スケジューリング回路１０は、数式（１）のように、ｗｅｉｇｈｔ［ｉ］を減算し続け、値が０以下になる入力ポートを選択する。あるいは、スケジューリング回路１０は、０以下になるのを待つのではなく、ＣＮＴ［ｉ］の大きさを比較することにより、送信要求の送出を行う入力ポートの選択が可能となり、演算処理の高速化が図れる。

各入力ポートのｃｎｔ［ｉ］は、ある入力ポートのｃｎｔ［ｉ］が０以下となるまで、ｃｎｔ［ｉ］からｗｅｉｇｈｔ［ｉ］を減算し続けることで更新される。そこで、すべての入力のＣＮＴ［ｉ］の最小値をＣＮＴｍｉｎとすると、ＣＮＴｍｉｎで各入力ポートに対応するＣＮＴ［ｉ］を減ずることで、ある入力ポートのｃｎｔ［ｉ］が０以下となるまで、各入力ポートのｃｎｔ［ｉ］からｗｅｉｇｈｔ［ｉ］を減算し続けるのと同じになる。

すなわち、スケジューリング回路１０は、ＣＮＴ［ｉ］＝ＣＮＴ［ｉ］−ＣＮＴｍｉｎの演算を行うことにより、各入力ポートに対応するＣＮＴ［ｉ］を更新することができる。このため、スケジューリング回路１０は、ｃｎｔ［ｉ］が０以下となるまで、ｗｅｉｇｈｔ［ｉ］を減算し続ける場合に比べ、処理が簡単化され、演算処理の高速化が図れる。この部分が従来と大きく異なるところである。

また、パケット読み出し部１１に送信要求送出するとき、ｃｎｔ［ｉ］にフレーム長ｆｌｅｎを加算する必要がある。すなわち、ＣＮＴ［ｉ］は、次式（３）で表すことができる。

ＣＮＴ［ｉ］＝（ｃｎｔ［ｉ］＋ｆｌｅｎ）／ｗｅｉｇｈｔ［ｉ］＝ＣＮＴ［ｉ］＋ｆｌｅｎ／ｗｅｉｇｈｔ［ｉ］ ……（３）

上記数式（３）において、ｆｌｅｎ／ｗｅｉｇｈｔ［ｉ］の演算を、浮動小数点で行うことが考えられるが、浮動小数点の除算は一般に計算コスト（回路規模等）が高くなる。従って、浮動小数点で除算する以外に、固定小数点で除算することも考えられる。固定小数点で行ったほうがハードウェア化、処理の高速化の面から好ましい。

しかしながら、固定小数点のため、割り切れない場合が存在し、その余りＲ［ｉ］が累積的な誤差を生む。そこで、次式（４）のように、余りを次の計算時、フレーム長ｆｌｅｎに加算することで、スケジューリング回路１０は、累積誤差を０にでき、固定小数点除算を行う場合の課題が解決される。除算を行う前のＣＮＴ［ｉ］の値をＣＮＴ’［ｉ］とし、除算を行ったことによる商をＱ［ｉ］、余りをＲ［ｉ］とすると、次式（４）で表すことができる。

ＣＮＴ［ｉ］＝ＣＮＴ’［ｉ］＋ｆｌｅｎ／ｗｅｉｇｈｔ［ｉ］＝ＣＮＴ’［ｉ］＋（ｆｌｅｎ−Ｒ［ｉ］）／ｗｅｉｇｈｔ［ｉ］＋Ｒ［ｉ］／ｗｅｉｇｈｔ［ｉ］
＝ＣＮＴ’［ｉ］＋Ｑ［ｉ］＋Ｒ［ｉ］／ｗｅｉｇｈｔ［ｉ］ ……（４）

となる。そして、その次に除算機会を得たときは、同様に、次式（５）で表される。

ＣＮＴ［ｉ］＝ＣＮＴ’［ｉ］＋ｆｌｅｎ／ｗｅｉｇｈｔ［ｉ］
＝ＣＮＴ’’［ｉ］＋Ｑ’［ｉ］＋Ｒ’［ｉ］／ｗｅｉｇｈｔ［ｉ］＋ｆｌｅｎ／ｗｅｉｇｈｔ［ｉ］
＝ＣＮＴ’’［ｉ］＋Ｑ’［ｉ］＋（ｆｌｅｎ＋Ｒ’［ｉ］−Ｒ［ｉ］）／ｗｅｉｇｈｔ［ｉ］＋Ｒ［ｉ］／ｗｅｉｇｈｔ［ｉ］
＝ＣＮＴ’’［ｉ］＋Ｑ’［ｉ］＋Ｑ［ｉ］＋Ｒ［ｉ］／ｗｅｉｇｈｔ［ｉ］
……（５）

ここで、ＣＮＴ’’［ｉ］は、除算２回前のＣＮＴ［ｉ］の値、Ｑ’、Ｒ’は、それぞれ前回除算を行ったときの商と余りである。Ｒは、０≦Ｒ＜ｗｅｉｇｈｔ［ｉ］を満たすので、累積誤差は、ｗｅｉｇｈｔ［ｉ］に収まる。

例えば、図２は、フレーム長に対して浮動小数点演算、余りを計算に入れ込んだ固定小数点演算、あるいは余りを計算に入れない固定小数点演算を行う場合での累積値を示す概念図である。上述した本実施形態による余りを計算に入れ込んだ固定小数点演算を用いると、浮動小数点演算の累積結果との差は、小数点以下のみとなる。しかし、余りの足しこみを行わない固定小数点演算の場合には、誤差は、次々と累積されていくことが示されている。

また、除算時除数の最大値ｍ（ｗｅｉｇｈｔ［ｉ］の取り得る最大値）分、ＣＮＴ［ｉ］、ｆｌｅｎをｍビット左シフトして除算を行うことで、加算の必要はなくなり、ビット結合だけで処理することが可能となり、演算時間をさらに短縮できる。具体的には、次式（６）で表される。

ＣＮＴ［ｉ］＜＜ｍ−Ｒ［ｉ］＝ＣＮＴ［ｉ］＜＜ｍ−（ｆｌｅｎ＜＜ｍ＋Ｒ’［ｉ］）／ｗｅｉｇｈｔ［ｉ］ ……（６）

ここで、Ｒ’［ｉ］は、前回入力ｉが送信要求として選択されたときに行われた除算の余りである。以上のように、スケジューリング回路１０は、入力カウンタｃｎｔ［ｉ］の値を用いるのではなく、ｃｎｔ［ｉ］をｗｅｉｇｈｔ［ｉ］で除したＣＮＴ［ｉ］及びその最小値ＣＮＴｍｉｎを用いることで、送信要求の送出を行う入力の選択や重み値による減算による更新処理を簡単に行うことが可能となり、演算時間の高速化が図れる。

また、パケット読み出し部１１にパケットを送出したときのパケット長を加算し、ＣＮＴ［ｉ］の値を更新する演算においても、上述したように、スケジューリング回路１０は、固定小数点を用いた場合の余りによる誤差の累積を適切に処理することで、簡単な処理でＣＮＴ［ｉ］の値を更新することができ、演算処理を高速化できる。

図３は、入力数３のＷＦＱにおいて、各レジスタ値がどのように変化するかの一例を示す概念図である。初期状態（０）において、入力がない時刻ｔ１で、入力０と入力１に送信要求が受信される。このとき、ｃｎｔ［ｉ］が最も小さいのは、入力０なので、入力０が選択され、（１０００＜＜５＋２）／３＝１０６６７…１となる。また、他の入力からは、ｃｎｔ［０］の値であった１０００が引かれる。入力２は、減算後、負になるので、ｃｎｔ［２］は、０となる。また、ラウンドロビン値は、最近選択されたものが最も大きな値になるので、ｒｏｕｎｄ［０］が３から３となり、他の各入力のｒｏｕｎｄ［ｉ］で３以上の値を持つものをデクリメントする必要があるが、送信したものが最も大きな値である３であったためデクリメントは行わない。

状態（１）の時刻ｔ２において、入力２にも送信要求が受信される。ｃｎｔ［２］が最も小さいので、ｃｎｔ［２］が選択され、各入力から０が減じられる。ｃｎｔ［２］は、（１００＜＜５＋０）／１から３２００となる。ラウンドロビン値ｒｏｕｎｄ［２］は、２から３に変化し、他の入力のｒｏｕｎｄ［ｉ］で２以上のものは、デクリメントされ、入力０のｒｏｕｎｄ［０］は、３から２に変化する。これを繰り返すことにより、スケジューリング回路１０は、ＷＦＱ処理を行う。

ところで、入力ポートを選択する段階で以下のことを考える。通常のＷＦＱ（重み付け公平制御）は、最小のカウンタ値ＣＮＴ［ｉ］を持つ入力を選択するが、優先度値をこのＣＮＴ［ｉ］のＭＳＢ側、ＬＳＢ側に結合することにより、以下の様な選択規則になる。

（優先度値をＭＳＢ側に結合した場合）
優先度値が小さいものがその後のＣＮＴ［ｉ］に優先する。優先度値が同じ場合、ＣＮＴ［ｉ］の小さい入力が選択される。

（優先度値をＬＳＢ側に結合した場合）
ＣＮＴ［ｉ］が優先し、優先度値は、ＣＮＴ［ｉ］値が同じでない限り無視される。ＣＮＴ［ｉ］が同じ場合、優先度値の小さい入力が選択される。

この規則を利用して、スケジューリング回路１０は、従来、ＰＱ（優先制御）／ＷＦＱ（重み付け公平制御）スケジューラの接続変更を行うのに必要であったセレクタを廃すことが可能となる。

図４は、上述した本発明の基本原理に基づく、本第１実施形態によるスケジューリング回路１０の構成を示すブロック図である。スケジューリング回路１０は、制御回路１０１、制御テーブル１０２、演算回路１０３からなる。制御テーブル１０２は、各入力ポートに対して、入力ポートに送信要求が受信されているかを示す送信要求（０でなし、１であり）、当該入力ポートに要求された送信要求パケットのフレーム長、当該入力ポートの制御を司るグループ番号、ＷＦＱの重み、ＰＱの優先度、ラウンドロビン制御を行うために使用するラウンドロビン値、入力に対する上述したＣＮＴ［ｉ］を示す商、ＣＮＴ［ｉ］の余りを記憶する。制御回路１０１は、上述したＪｕｄｇｅＷａｉｔ、ＷａｉｔＣｎｔを保持するとともに、設定された動作モードを格納する。制御回路１０１は、制御テーブル１０２に格納されている各種値に従って、後述する図５、図６に示す処理を実行する。演算回路１０３は、制御回路１０１による処理に伴う加減算、除算などを行う。

次に、ＷＦＱあるいは、前段ＰＱ後段ＷＦＱ制御時のスケジューリング回路１０の動作について説明する。
図５は、本第１実施形態において、ＷＦＱあるいは、前段ＰＱ後段ＷＦＱ制御時の動作を説明するためのフローチャートである。制御回路１０１は、各入力ポートのいずれかに送信要求が受信されているか否かを判定し（ステップＳａ１）、送信要求が受信されていない場合（ステップＳａ１のＮＯ）、送信要求が受信されるまで当該判定を行う。

一方、各入力ポートのいずれかに送信要求が受信された場合（ステップＳａ１のＹＥＳ）、制御回路１０１は、図７に示すように、比較するための情報として、入力ｎ（０〜Ｎ）の送信要求、商、ラウンドロビンカウンタ、優先度の値を連結し、入力選択用比較値を作成する（ステップＳａ２）。連結は、比較を簡便に行うための１つの方法であり、比較優先順は左から行うため、要素毎に比較を行っても良いが、ハードウェア等を用いて検索ビット長を長くできる場合、一度に比較した方が処理時間は短くなる。

ここで、図１０は、ＷＦＱモードでの動作概要を示す概念図であり、図１１は、前段ＰＱで後段ＷＦＱモードでの動作概要を示す概念図である。ＷＦＱモードの場合には、例えば、図１０に示すように、スケジューリング回路１０において、入力ポート０〜３には、各々、グループ０〜３、優先度７、重み２４、８９、８、２５４が設定されている。この場合、帯域分割は、入力ポート０：入力ポート１：入力ポート２：入力ポート３＝２４：８９：８：２５４の割合で出力される。

また、前段ＰＱで後段ＷＦＱモードの場合には、例えば、図１１に示すように、スケジューリング回路１０において、入力ポート０〜３には、各々、グループ０、０、１、３、優先度０、１、１、０、重み２４、２４、２５４、２５４が設定されている。この場合、出力優先順位は、前段ＰＱ（グループ０）が入力ポート０：高優先、入力ポート１：低優先、前段ＰＱ（グループ１）が入力ポート２：低優先、入力ポート３：高優先となり、帯域分割は、ＰＱ（グループ０）出力：ＰＱ（グループ１）出力＝２４：２５４となる。

次に、制御回路１０１は、各入力ｎ（０〜Ｎ）の入力選択用比較値を比較し、入力選択用比較値が最も小さい入力Ｎｍｉｎを求める（ステップＳａ３）。この比較には、入力要求のビット反転がＭＳＢに設定されており、送信要求が存在する場合には、入力要求のビットは１であり、存在しない場合には、入力要求のビットは０となる。当然、０（送信要求有）が最小値として選択されるので、大小比較により、送信要求があるかどうかの判断が可能となる。また、最小値を検索した結果、ＭＳＢが１である場合、送信要求している入力が存在しないことを表しており、容易にいずれかの入力に送信要求があるのかないのか判断することが可能となる。

次に、制御回路１０１は、各入力に対して最小の入力選択用比較値を持つ入力Ｎｍｉｎのフレーム長及び送信要求をパケット読み出し部１１に送信する（ステップＳａ４）。ところで、入力選択用比較値には、ラウンドロビンカウンタも連結されている。これは、最小値を求める際に、同じ値が存在したり、同時に０以下になる入力が存在したりする場合には、ＷＦＱ処理を行うときに該当する入力をラウンドして選択する必要がある。この処理は、順繰りにｔｍｐ＝入力０ラウンドロビンカウンタ、入力０ラウンドロビンカウンタ＝入力１ラウンドロビンカウンタ、入力１ラウンドロビンカウンタ＝入力２ラウンドロビンカウンタ、入力２ラウンドロビンカウンタ＝入力３ラウンドロビンカウンタ、入力３ラウンドロビンカウンタ＝ｔｍｐとすることで実現する。

あるいは、このラウンドロビン値を用いず、別の記憶手段を用い、今までの送信履歴から最も送信していない入力を選択するようにすることで、ラウンドロビンを実現する方法も考えられる。これは、例えば、入力ポート数を４とすると、入力２が送信要求ポートとして選択された場合、入力２ラウンドロビンカウンタより大きい値を持つ各入力ｉラウンドロビン値は、１デクリメントされ、入力２ラウンドロビン値＝３とする。このようにすることで、最近送信した順に３、２、１、０という値を持つことになり、最小値比較においてパラメータ値がまったく同じ場合、過去最も送信していない入力が選択されるようになる。

次に、演算回路１０３は、送信要求されたパケットのフレーム長に最小値を持つ入力の余りを結合（加算）して作られる被除数を入力Ｎｍｉｎの重みで除し、制御テーブル１０２の商及び余りを更新する（ステップＳａ５）。この結合（加算）は、数式（６）及び図９で示されるように、連結処理で実現可能であり、演算処理量を削減することができる。上記、商、余りは、制御テーブル１０２の当該入力ポートに対応する、商、余りに設定される。

次に、制御回路１０１は、入力ｎ（０〜Ｎ）のグループ番号が入力Ｎｍｉｎのグループ番号と一致しているか判定し（ステップＳａ６）、一致している場合には、制御テーブル１０２に対して、最小値を持つ入力Ｎｍｉｎと同じグループに属する入力ポートに対する商・余りを、その最小値を持つ入力Ｎｍｉｎの商・余りにより上書きする（ステップＳａ７）。一方、一致しない他の入力の商に対しては、最小値を持つ入力Ｎｍｉｎの商を、他の入力ｎの商から減ずる（ステップＳａ８）。但し、商を減じて負になる場合、その商を０とする。また、場合により余りも０にする。

これにより、動作モードがＷＦＱ（図１０）あるいは、前段ＰＱ後段ＷＦＱ（図１１）モードの場合、同一グループ内では、常に同じ商・余りを持ち、グループ間では、上述したＷＦＱの動作説明に従った商・余りを持つことになる。最小値比較に使う値は、図７に示す形なので、あるグループ内の優先付けは、ＬＳＢ側に付く優先度により決定するので、ＷＦＱあるいは前段ＰＱ後段ＷＦＱ動作となる。

最後に、ＷａｉｔＣｎｔが満了するまで待ち（ステップＳａ９）、次の送信要求受理開始までの時間を調整する。すなわち、図１に示す要求／受理信号の送受で制御されるＱｏＳ回路は、送信受理後の要求受付時間の調整を行う必要がある。このＷａｉｔＣｎｔは、パケット読み出し部１１からの受理信号を受けたときに、制御回路１０１のＷａｉｔＣｎｔに予め設定されているＪｕｄｇｅＷａｉｔの値を書き込む。そして、選択された入力に接続されるキュー部８へ受理信号を送信する。ＷａｉｔＣｎｔは、所定の周期（例えば、システムクロック毎）で減算される。ＷａｉｔＣｎｔの値が０になるまで繰り返し減算し、０になった場合、ＷａｉｔＣｎｔの減算を停止する。そして、ＷａｉｔＣｎｔの値が０になった場合、最小値選択に戻り、最小の入力の選択を行う。

次に、ＰＱあるいは、前段ＷＦＱ後段ＰＱ制御時の動作について説明する。
図６は、本第１実施形態において、ＰＱあるいは、前段ＷＦＱ後段ＰＱ制御時の動作を説明するためのフローチャートである。なお、図６に示すフローチャートにおいて、図５と異なる点は、ステップＳｂ２と、ステップＳｂ６以降の処理であるので、図５と同じステップＳｂ１、ステップＳｂ３〜Ｓｂ５については説明を省略する。

また、図１２は、ＰＱモードでの動作概要を示す概念図であり、図１３は、前段ＷＦＱで後段ＰＱモードでの動作概要を示す概念図である。ＰＱモードの場合には、例えば、図１２に示すように、スケジューリング回路１０において、入力ポート０〜３には、各々、優先度０〜３、重み２５５が設定されている。出力優先順位は、入力ポート０：高優先であり、順次、優先順位が下がり、入力ポート３：低優先となる。

また、前段ＷＦＱで後段ＰＱモードの場合には、例えば、図１３に示すように、スケジューリング回路１０において、入力ポート０〜３には、各々、優先度０、０、１、１、重み２４、８９、８、２５４が設定されている。この場合、帯域分割は、前段ＷＦＱ（０）で、入力ポート０：入力ポート１＝２４：８９となり、前段ＷＦＱ（１）で、入力ポート２：入力ポート３＝８：２５４となる。また、出力優先順位は、ＷＦＱ（０）：高優先で、ＷＦＱ（１）：低優先となる。

動作モードがＰＱ、前段ＷＦＱで後段ＰＱモードの場合には、図８に示すように、制御回路１０１は、比較するための情報として、入力ｎ（０〜Ｎ）の送信要求、優先度、商、ラウンドロビンカウンタの値を連結し、入力選択用比較値を作成する（ステップＳｂ２）。なお、この場合も、要素毎に比較を行ってもかまわない。

また、動作モードがＰＱ、あるいは、前段ＷＦＱ後段ＰＱモードの場合、制御回路１０１は、入力ｎ（０〜Ｎ）の優先度が入力Ｎｍｉｎの優先度と一致しているか判定し（ステップＳｂ６）、一致している場合には、最小値を持つ入力Ｎｍｉｎと同じ優先度を持つ入力ｎに対する商から、最小値を持つ入力Ｎｍｉｎの商を減じる。但し、商を減じて負になる場合、その商を０とする。また、場合により余りも０にする。

この場合、先に示したＷＦＱの動作の影響は、同一優先度（言い換えると、グループ）内にしか波及しない。これにより、同一優先度内は、ＷＦＱ動作となるが、最小値比較においては、優先度比較の方がＭＳＢ側に存在するので、先に優先度（グループ）により選択されることにより、ＰＱあるいは、前段ＷＦＱ後段ＰＱの動作となる。

Ｂ．第２実施形態
本発明の第２実施形態について説明する。
図１４は、本発明の第２実施形態による、ＱｏＳ回路の構成を示すブロック図である。なお、図１に対応する部分には同一の符号を付けて説明を省略する。図１に示す構成との違いは、パケット送出後に、ＴＴＬ減算や、ＩＰアドレス書き換えなどのパケット書き換えを行う送信パケット生成部５を、パケット読み出し部１１と送信部１２との間に配置している点にある。

図１４に示す構成による長所は、受信後、すぐにパケットバッファ７にパケットを書き込むことができるため、パケット書き込みまでのＦＩＦＯ（図１のＦＩＦＯ３）をなくすことができる点である。但し、パケット読み出し後にパケット書き換えを行うための情報をキュー部８に蓄積しておく必要がある。そのため、キュー部８のサイズによっては、キュー部８の回路規模が増大する可能性があるが、ＦＩＦＯ３がなくなるため、装置としては、回路規模が削減される可能性もある。図１と図１４のどちらの構成を採用するかは、ＦＩＦＯ３のサイズとキュー部８のサイズとによる回路規模比較により選択すればよい。

上述した第１、第２実施形態によれば、スケジューリング回路１０は、各入力への減算処理がパケット送出要求時のみであり、加減算処理への要求性能を大幅に削減することができ、回路規模の縮小・スケジューリング精度の向上を図ることができる。

また、スケジューリング回路１０は、重み付け公平制御における送信パケット選択時に使用される各種カウンタの組み合わせの変更、及び多少の処理手法の変更により、優先制御のみ／重み付け公平制御のみ／前段優先制御・後段重み付け公平制御／前段重み付け公平制御・後段優先制御が実現可能となり、従来手法で必要であったセレクタを廃することが可能となり、更なる回路規模の削減が可能となる。

以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。

本発明は、パケットの送受信処理を行う通信品質制御装置、及び通信品質制御方法に好適である。

１…受信部、２…識別部、３…ＦＩＦＯ、４…識別結果生成部、５…送信パケット生成部、６…パケット書き込み部、７…パケットバッファ、８…キュー部、９…キー判定部、１０…スケジューリング回路、１１…パケット読み出し部、１２…送信部、１０１…制御回路、１０２…制御テーブル、１０３…演算回路

Claims (4)

1. スケジューリング回路の入力ポート毎に設定された重み値に基づいて出力優先順位を決定し、該出力優先順に従って前記入力ポート毎に割り振られた送信パケットを出力する通信品質制御装置において、
   前記スケジューリング回路は、
   前記入力ポート毎に保持されている複数の参照値である、送信パケットの送信要求、優先度、商、及びラウンドロビン値のうち少なくとも優先度と商を結合して、入力選択用比較値を生成する入力選択比較値生成手段と、
   前記入力選択用比較値を比較し、最も値が小さい入力ポートを選択する選択手段と、
   前記最も値が小さい入力ポートに対する送信パケットのフレーム長を、当該入力ポートに対して設定されている重み値で除算する算出手段と、
   前記算出手段による除算結果である商及び余りを、次回の入力ポート選択時に、前記入力選択比較値生成手段により前記入力選択用比較値を生成する際の前記複数の参照値の１つとして当該入力ポートに対して保持する保持手段と、
   入力ポートに付されたグループ番号が前記最も値が小さい入力ポートに付されたグループ番号と一致している場合には、前記最も値が小さい入力ポートに付されたグループ番号と同一のグループ番号が付される入力ポートに対する商及び余りを、前記最も値が小さい入力ポートに対する商及び余りにより上書きし、入力ポートに付されたグループ番号が前記最も値が小さい入力ポートに付されたグループ番号と一致していない場合には、グループ番号が一致していない他の入力ポートに対する商を前記最も値が小さい入力ポートに対する商で減じる制御手段と、
   を備えることを特徴とする通信品質制御装置。
2. 前記入力選択比較値生成手段は、
   重み付け公平制御、優先制御、重み付け公平制御と優先制御、または優先制御と重み付け公平制御のいずれを実行するかに応じて、前記入力選択用比較値を生成するための参照値の組み合わせを変えて、前記入力選択用比較値を生成する、
   ことを特徴とする請求項１に記載の通信品質制御装置。
3. スケジューリング回路の入力ポート毎に設定された重み値に基づいて出力優先順位を決定し、該出力優先順に従って前記入力ポート毎に割り振られた送信パケットを出力する通信品質制御方法において、
   前記スケジューリング回路の入力ポート毎に保持されている複数の参照値である、送信パケットの送信要求、優先度、商、及びラウンドロビン値のうち少なくとも優先度と商を結合して、入力選択用比較値を生成するステップと、
   前記入力選択用比較値を比較し、最も値が小さい入力ポートを選択するステップと、
   前記最も値が小さい入力ポートに対する送信パケットのフレーム長を、当該入力ポートに対して設定されている重み値で除算するステップと、
   前記除算結果である商及び余りを、次回の入力ポート選択時に、前記入力選択用比較値を生成する際の前記複数の参照値として当該入力ポートに対して保持するステップと、
   入力ポートに付されたグループ番号が前記最も値が小さい入力ポートに付されたグループ番号と一致している場合には、前記最も値が小さい入力ポートに付されたグループ番号と同一のグループ番号が付される入力ポートに対する商及び余りを、前記最も値が小さい入力ポートに対する商及び余りにより上書きし、入力ポートに付されたグループ番号が前記最も値が小さい入力ポートに付されたグループ番号と一致していない場合には、グループ番号が一致していない他の入力ポートに対する商を前記最も値が小さい入力ポートに対する商で減じるステップと、
   を含むことを特徴とする通信品質制御方法。
4. 前記入力選択比較値は、
   重み付け公平制御、優先制御、重み付け公平制御と優先制御、または優先制御と重み付け公平制御のいずれを実行するかに応じて、前記複数の参照値の組み合わせを変えて生成される、
   ことを特徴とする請求項３に記載の通信品質制御方法。

Images