JP4637154B2 - トラヒックコントロール方法及び装置 - Google Patents

Description

本発明は、ＷＦＱ（Weight Fair Queuing）回路を用いたトラヒックコントロール装置に関する。

データ通信以外に音声電話やＴＶ電話など、多様な通信サービスがインターネットを介して提供されている。このような多様化に伴い、柔軟性と高速性を両立するために、各キュー、スケジューラ、そしてシェーパを、セレクタを用いて接続し、送信要求と要求受理信号のハンドシェークを用いたＱｏＳ（Quality of Service）方式が提案されてきた（例えば、特許文献１、特許文献２参照）。さらに、このＱｏＳ方式に用いるスケジューリングモジュールが提案されている（例えば、特許文献３参照）。この方式では、各入力に指定された重みをクロックサイクル毎に時分割、あるいは、加算値を変更して各入力の要求フレーム長との比較を行うカウンタに加算し、値が正かつ送信要求がある入力をラウンドロビンで選択して後段への送信要求信号として用いている。
特開２００５−３１１４０９号公報 特開２００５−３２３２３０号公報 特開２００７−１１０５１５号公報

しかしながら、上述した従来技術では、送信要求を受けていない場合かつ入力カウンタが正でありかつ、送信受理信号を受け取ったあるいは、delayが０になった場合そのカウンタに蓄積されていた値を総カウンタに戻さなければならないといったように処理が複雑であり、加えて、各入力は最大フレームサイズの負数分のレジスタを持たなければならず、さらには、それらがすべて総カウンタに戻った場合のレジスタを持たなければならない。そのため、回路規模は大きくなってしまう。また、重みの範囲が大きくなった場合（たとえば、１：１５→１：２５５）、方式的に正確なカウンタヘの加算ができなくなる。これは、Ethernet（登録商標）フレームの最小フレーム長は、６４Byte（バイト）であり、一度の加算によって、ある入力には１しか加算しないのに、ある入力には２５５が一度に加算されるために、２５５が加算された入力からバースト的に３フレーム（２５５／６４＝３．９８）送出される可能性があることによる。

そこで、本発明は、このような事情を考慮してなされたものであり、その目的は、算術演算を行うことで、各動作ステップ数の削減および、固定化を行い、高速かつ小型のＱｏＳ回路、特にキュー制御を行う重み付け公平制御（ＷＦＱ：Weight Fair Queuing）回路を提供することにある。

前記課題を解決するために、本発明は、複数の入力ポートからの入力を後段に出力するトラヒックコントロール装置におけるトラヒックコントロール方法であって、前記トラヒックコントロール装置は、複数の入力ポートそれぞれに対応した商カウンタの値及び余りカウンタの値を記憶する記憶手段を備えており、前記商カウンタのうち最小値である商カウンタを選択し、選択された商カウンタに対応した入力ポートからの送信要求を後段回路に送信する出力過程と、選択された商カウンタ以外の前記商カウンタの値を、前記選択された商カウンタの値を減算した値に更新する更新過程と、前記選択された商カウンタに対応した入力ポートからの入力のフレーム長と、当該入力ポートに対応した余りカウンタの値とを加算した値を、当該入力ポートに対応した所定の重みの値で除算し、除算した結果の商により前記選択された商カウンタの値を更新し、除算した結果の余りにより当該入力ポートに対応した余りカウンタの値を更新する演算過程とを有することを特徴とする。

また、本発明は、上述するトラヒックコントロール方法であって、前記演算過程において、前記選択された商カウンタに対応した入力ポートからの入力のフレーム長と、当該入力ポートに対応した余りカウンタの値とを加算する代わりに、当該入力ポートの入力のフレーム長を、所定分、あるいは、重みのとりうる最大値分だけ左ビットシフトし、当該入力ポートに対応した余りカウンタの値と連結する、ことを特徴とする。
また、本発明は、上述するトラヒックコントロール方法であって、前記記憶手段は、各入力ポートに対応し、送信要求が送信された順序に応じて値が変更されるラウンドロビンカウンタをさらに記憶し、前記出力過程において、最小値を有する前記商カウンタが複数ある場合、前記ラウンドロビンカウンタの値により、送信要求を送信する入力ポートを選択する、ことを特徴とする。

また、本発明は、複数の入力ポートからの入力を後段に出力するトラヒックコントロール装置であって、複数の入力ポートそれぞれに対応した商カウンタの値及び余りカウンタの値を記憶する記憶手段と、前記商カウンタのうち最小値である商カウンタを選択し、選択された商カウンタに対応した入力ポートからの送信要求を後段回路に送信する制御手段と、選択された商カウンタ以外の前記商カウンタの値を、前記選択された商カウンタの値を減算した値に更新するとともに、当該選択された商カウンタに対応した入力ポートからの入力のフレーム長と、当該入力ポートに対応した余りカウンタの値とを加算した値を、当該入力ポートに対応した所定の重みの値で除算し、除算した結果の商により前記選択された商カウンタの値を更新し、除算した結果の余りにより当該入力ポートに対応した余りカウンタの値を更新する演算手段と、を備えることを特徴とする。

ＷＦＱ回路等のトラヒックコントロール装置においては、カウンタから重み値を繰り返し減算する処理、後段回路に送信要求をした入力についてはそのフレーム長をカウンタに加算する処理など、各種の演算処理が必要となるが、本発明によれば、重み値の繰り返し減算を不要にするとともに、フレーム長をカウンタに加算する処理には固定小数点を用いてその演算処理を簡易化すること等、により、ＷＦＱ回路に必要な各種の演算処理を高速化し、また、回路規模を小さくすることが可能となる。

以下、図面を用いて本発明の一実施形態を説明する。
まず始めに、本発明の一実施形態によるトラヒックコントロール装置としてのＷＦＱ（Weight Fair Queuing）回路の基本動作を、図１に示す概要動作フローに基づいて説明する。
同図において、ＷＦＱ回路は、対応して設置されている入力カウンタが０以下かつ前段回路から送信要求を受信している入力ポートを選択し（ステップＳ１１）、後段回路に、この選択した送信要求を出力する（ステップＳ１２）。続いてＷＦＱ回路は、後段回路に送信要求を出力した入カポートに対応して設置されている入力カウンタに、後段回路に送信要求を出力したフレームのフレーム長を加算する（ステップＳ１３）。ＷＦＱ回路は、各入力カウンタから、入力ポート毎に予め設定された重み値を所定の周期（例えば、システムクロック毎）で減算する（ステップＳ１４）。

ＷＦＱ回路が後段回路から受理信号を受信すると（ステップＳ１５）、前段回路に受理信号を出力する（ステップＳ１６）。ＷＦＱ回路は、待ち制御を行うカウンタであるＷａｉｔＣｎｔに、待ちの上限値であるＪｕｄｇｅＷａｉｔの値を設定する（ステップＳ１７）。ＷａｉｔＣｎｔの設定後、ＷＦＱ回路は、ＷａｉｔＣｎｔの値が０になるまで、ＷａｉｔＣｎｔの値を所定の周期（例えば、システムクロック毎）で１ずつ減算する（ステップＳ１８、Ｓ１９）。そして、ＷａｉｔＣｎｔの値が０になったときに、次に後段回路へ送信すべき要求を決定するために、ステップＳ１１に戻り、選択された入力ポートからの送信要求を待つことになる。入力カウンタは後段回路に送信要求を出力した時点で、ステップＳ１３においてフレーム長が加算されている。また、このようにすることで、重み値を制御することにより、後段回路への送信要求の送出タイミングを適切に制御することが可能となる。

以上のＷＦＱ回路の動作を数式で表現し、それに基づき、本発明の基本原理を説明する。
各入力ポートｉ（ｉは入カポートの番号）の入力カウンタをｃｎｔ［ｉ］、重み値をｗｅｉｇｈｔ［ｉ］、送信要求を出力すべきであると選択された入力ポートにおける入力のフレーム長をｆｌｅｎとすると、各入力カウンタｃｎｔ［ｉ］の値は、所定の周期で重み値により減算されることから以下の（式１）のようになる。なお、以下の式において、「＝」は、右辺演算後の結果を左辺に格納することを意味する。

ｃｎｔ［ｉ］＝ｃｎｔ［ｉ］−ｗｅｉｇｈｔ［ｉ］ ただし、ＣＮＴ［ｉ］＞０ …（式１）

上記の（式１）の両辺をｗｅｉｇｈｔ［ｉ］で除算すると、以下の（式２）のようになる。

ｃｎｔ［ｉ］／ｗｅｉｇｈｔ［ｉ］＝ｃｎｔ［ｉ］／ｗｅｉｇｈｔ［ｉ］−１ …（式２）

ここで、ｃｎｔ［ｉ］／ｗｅｉｇｈｔ［ｉ］をＣＮＴ［ｉ］とおくと、（式２）は、以下の（式３）のようになる。

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

この場合、最も最初にｃｎｔ［ｉ］が０以下となるのは、明らかに、|ＣＮＴ［ｉ］|（ＣＮＴ［ｉ］の絶対値）が最も小さい入力である。このことから、（式１）のように、ｗｅｉｇｈｔ［ｉ］を減算し続け、値が０以下になる入力ポートを選択する場合に比べ、送信要求が入力されている入力ポートｉのＣＮＴ［ｉ］の大きさを比較するだけで、送信要求の送出を行う入カポートの選択が可能となり、演算処理の高速化を図ることができる。

なお、各入力ポートｉのｃｎｔ［ｉ］は、ある入力ポートｉのｃｎｔ［ｉ］が０以下となるまで、ｃｎｔ［ｉ］からｗｅｉｇｈｔ［ｉ］を減算し続け、ｃｎｔ［ｉ］の値が更新される。
そこで、すべての入力ポートｉのＣＮＴ［ｉ］の中の最小値をＣＮＴｍｉｎとすると、このＣＮＴｍｉｎを各入力ポートに対応するＣＮＴ［ｉ］から減ずることで、ある入力ポートのｃｎｔ［ｉ］が０以下となるまで、各入力ポートのｃｎｔ［ｉ］からｗｅｉｇｈｔ［ｉ］を減算し続けるのと同じになる。
すなわち、以下の（式４）の演算を行うことにより、各入力ポートｉに対応するＣＮＴ［ｉ］を更新することができ、ｃｎｔ［ｉ］が０以下となるまでｗｅｉｇｈｔ［ｉ］を減算し続ける場合に比べ、処理が簡単化され、演算処理の高速化を図ることができる。

ＣＮＴ［ｉ］＝ＣＮＴ［ｉ］−ＣＮＴｍｉｎ …（式４）

また、後段回路に送信要求送出する時、ｃｎｔ［ｉ］にフレーム長ｆｌｅｎを加算する必要がある。すなわち、以下の（式５）のようになる。

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

（式５）において、ｆｌｅｎ／ｗｅｉｇｈｔ［ｉ］の演算を、浮動小数点で行うと、浮動小数点の除算は計算コストが高くなる。従って、固定小数点で行ったほうがハードウェア化、処理の高速化の面から好ましい。しかしながら、固定小数点のため割り切れない場合が存在し、ｆｌｅｎ／ｗｅｉｇｈｔ［ｉ］の余りＲ［ｉ］が累積的な誤差を生む。そこで、余りを次の計算時、フレーム長ｆｌｅｎに加算するようにすることで、累積誤差を０にできる。具体的には、除算を行う前のＣＮＴ［ｉ］の値をＣＮＴ’［ｉ］とし、除算を行ったことによる商をＱ［ｉ］、余りをＲ［ｉ］とすると、ｆｌｅｎ＝Ｑ［ｉ］×ｗｅｉｇｈｔ［ｉ］＋Ｒ［ｉ］であることから、以下の（式６）のようになる。

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

そして、その次に除算機会を得たときには、同様に以下のようになる。

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

ここで、ＣＮＴ”［ｉ］は除算２回前のＣＮＴ［ｉ］の値、Ｑ’、Ｒ’はそれぞれ前回除算を行ったときの商と余りである。Ｒは、０≦Ｒ＜ｗｅｉｇｈｔ［ｉ］を満たすので、累積誤差はｗｅｉｇｈｔ［ｉ］に収まる。図５は、除算累積誤差を説明するための図であり、たとえば同図に示すようなフレーム長のフレームが１行目のものから順に入力され、当該フレーム長に対して演算を行う場合、本方式を使用すると、余りを計算に入れ込んだ固定小数点演算累積値の欄に示すように、浮動小数点演算の累積結果との差は小数点以下のみとなるが、余りの足しこみを行わない場合、余りを計算に入れ込まない固定小数点演算累積値の欄に示すように誤差は次々と累積されていく。

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

つまり、上記（式５）と、Ｑ［ｉ］＝（ｆｌｅｎ−Ｒ［ｉ］）／ｗｅｉｇｈｔ［ｉ］であることから、以下の（式８）のようになる。

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

しかし、実際には、Ｒ［ｉ］／ｗｅｉｇｈｔ［ｉ］は小数点以下の値となるため、（式８）は以下の（式９）のようになる。

ＣＮＴ［ｉ］＝ＣＮＴ’［ｉ］+Ｑ［ｉ］ …（式９）

また、（式８）の両辺を２^ｍ倍（「＾」は、べき乗を表す）すると、以下の（式１０）のようになる。なお、「<<ｍ」は、ｍビットだけ左シフトすることを示す。

ＣＮＴ［ｉ］<<ｍ
＝ＣＮＴ’［ｉ］<<ｍ＋（ｆｌｅｎ<<ｍ）／ｗｅｉｇｈｔ［ｉ］ …（式１０）

（式８）を用いて、（式１０）を変形すると、以下の（式１１）のようになる。なお、Ｒ’［ｉ］は前回の入力フレームｉが送信要求として選択されたときに行われた除算の余りである。

ＣＮＴ［ｉ］<<ｍ
＝ＣＮＴ’［ｉ］<<ｍ＋（ｆｌｅｎ<<ｍ）／ｗｅｉｇｈｔ［ｉ］
＝（ＣＮＴ”［ｉ］<<ｍ＋Ｑ’［ｉ］＋Ｒ’［ｉ］／ｗｅｉｇｈｔ［ｉ］）＋（ｆｌｅｎ<<ｍ）／ｗｅｉｇｈｔ［ｉ］
＝ＣＮＴ”［ｉ］<<ｍ＋Ｑ’［ｉ］＋（ｆｌｅｎ<<ｍ＋Ｒ’［ｉ］）／ｗｅｉｇｈｔ［ｉ］ …（式１１）

（式１１）に、（式９）を代入すると、以下の（式１２）になる。

ＣＮＴ［ｉ］<<ｍ＝ＣＮＴ’［ｉ］＋（ｆｌｅｎ<<ｍ＋Ｒ’［ｉ］）／ｗｅｉｇｈｔ［ｉ］ …（式１２）

１≦ｗｅｉｇｈｔ［ｉ］≦２＾ｍならば、０≦Ｒ’［ｉ］＜２＾ｍである。また、ｆｌｅｎ≧１であるので、ｆｌｅｎ<<ｍ≧２＾ｍである。そのため、ｆｌｅｎ<<ｍ＋Ｒ’［ｉ］は、ｆｌｅｎとＲ’［ｉ］のビット結合となる。

以上のように、入力カウンタｃｎｔ［ｉ］の値を用いるのではなく、ｃｎｔ［ｉ］をｗｅｉｇｈｔ［ｉ］で除したＣＮＴ［ｉ］及びその最小値ＣＮＴｍｉｎを用いることで、送信要求の送出を行う入力の選択や、重み値による減算による更新処理を簡単に行うことが可能となり、演算時間の高速化を図ることができる。また、後段回路にフレームを送出したときのフレーム長を加算してＣＮＴ［ｉ］の値を更新する演算においても、上述したように、固定小数点を用いた場合の余りによる誤差の累積を適切に処理することで、簡単な処理によりＣＮＴ［ｉ］の値を更新することができ、演算処理を高速化することができる。
なお、上記においては、重みのとりうる最大値分ビットシフトを行っているが、適当な、予め決められた所定分、ビットシフトを行うことでもよい。

図２は、上述の基本原理に基づいて構成した、本発明の一実施形態によるＷＦＱ回路１００の構成例である。また、図３は、図２のＷＦＱ回路１００の動作フローを示した図である。以下、図２、図３に基づいて、本発明の実施の形態について詳細に説明する。

まず、図２を用いて、本発明の一実施の形態によるＷＦＱ回路１００の構成について説明する。図２の構成例では、入力ポートの数が４（ｉ＝０〜３）である場合について示しているが、４以上あるいは４以下の場合であってもよい。

入力ｉフレーム長記憶手段１０１−ｉ（ｉ＝０〜３）は、前段回路から入力ポートｉに入力されたフレームのフレーム長であるｆｌｅｎ［ｉ］を格納する手段である。入力ｉ重み記憶手段−ｉ（ｉ＝０〜３）は、入力ポートｉの入力に対する重み値であるｗｅｉｇｈｔ［ｉ］を格納する手段である。入力ｉ商記憶手段１０３−ｉ（ｉ＝０〜３）は、商カウンタ、すなわち、入力ポートｉの入力に対する、上述したＣＮＴ［ｉ］の商を格納する手段、入力ｉ余り記憶手段１０４−ｉ（ｉ＝０〜３）は、余りカウンタ、すなわち、ＣＮＴ［ｉ］の余りを格納する手段である。入力ｉラウンドロビンカウンタ記憶手段１０５−ｉ（ｉ＝０〜３）は、入カポートｉの入力に対応するラウンドロビンカウンタを格納する手段であり、演算回路１０６（演算手段）は、上述した各種の演算を実行する演算回路、制御回路１０７（制御手段）は、ＷＦＱ回路１００の全体を制御する制御回路である。図２に示す制御回路１０７内の記憶手段に格納されているＷａｉｔＣｎｔは、待ち制御を行うためのカウンタであり、制御回路１０７内の記憶手段に格納されているＪｕｄｇｅＷａｉｔは、ＷａｉｔＣｎｔの上限値として設定される値である。
なお、以下、入力ｉフレーム長記憶手段１０１−０〜３を総称して入力ｉフレーム長記憶手段１０１、入力ｉ重み記憶手段−０〜３を総称して入力ｉ重み記憶手段、入力ｉ商記憶手段１０３−０〜３を総称して入力ｉ商記憶手段１０３、入力ｉ余り記憶手段１０４−０〜３を総称して入力ｉ余り記憶手段１０４、入力ｉラウンドロビンカウンタ記憶手段１０５−０〜３を総称して入力ｉラウンドロビンカウンタ記憶手段１０５と記載する。入力ｉフレーム長記憶手段１０１、入力ｉ重み記憶手段、入力ｉ商記憶手段１０３、入力ｉ余り記憶手段１０４、入力ｉラウンドロビンカウンタ記憶手段１０５は、例えばレジスタである。

次に、図３を用いて、図２に示すＷＦＱ回路の動作について説明する。
制御回路１０７は、自身の備える記憶手段に記憶するＪｕｄｇｅＷａｉｔに、所定の値を設定する（ステップＳ２０１）。さらに制御回路１０７は、各入力ｉ重み記憶手段１０２に、各入力ポートｉの所定の重み値ｗｅｉｇｈｔ［ｉ］を設定し（ステップＳ２０２）、各入力ｉ商記憶手段１０３、各入力ｉ余り記憶手段１０４を０クリアする（ステップＳ２０３）。

続いて、制御回路１０７は、いずれかの入力ポートｉに前段回路から送信要求があるかを判断する（ステップＳ２０４）。どの入力ポートｉにも前段回路から送信要求がない場合には（ステップＳ２０４：ＮＯ）、ステップＳ２０４からの処理を再度実行する。
一方、いずれかの入力ポートｉに前段回路から送信要求がある場合（ステップＳ２０４：ＹＥＳ）、制御回路１０７は、上述の基本原理で説明した各入力ポートｉのＣＮＴ［ｉ］を比較し、ＣＮＴ［ｉ］が最も小さい入力を選択するとともに、その選択したＣＮＴ［ｉ］から最小値であるＣＮＴｍｉｎを求める。具体的には、ＣＮＴ［ｉ］の値は、入力ｉ商記憶手段１０３に格納されているため、各入力ｉ商記憶手段１０３内の設定内容を用いて、ＣＮＴ［ｉ］の値が最小の入力を選択する。ＣＮＴ［ｉ］の値が最小の入力ポートｉを入力ポートｊとし、入力ポートｊからの入力を入力ｊとすると、最小値であるＣＮＴｍｉｎは、入力ｊ商記憶手段１０３−ｊに格納されている値となる（ステップＳ２０５）。ただし、最小値比較時に、比較対象の入力に送信要求が来ていない入力に対しては、比較を行わない。

制御回路１０７が、後段回路に、入力ｊに対する送信要求を送出すると（ステップＳ２０６）、以下のステップＳ２０８〜Ｓ２１０の処理を入力数の分だけ繰り返す（ステップＳ２０７）。
すなわち、演算回路１０６は、上述の基本原理の（式４）で説明したＣＮＴ［ｉ］＝ＣＮＴ［ｉ］−ＣＮＴｍｉｎを演算する。具体的には、ＣＮＴｍｉｎは、上述したように、入力ｊ商記憶手段１０３−ｊに格納されており、各入力ｉのＣＮＴ［ｉ］は、入力ｉ商記憶手段１０３−ｉ（ｉはｊ以外）に格納されているため、これらを用いて、上記の（式４）の減算処理を行う（ステップＳ２０８）。
そして、ステップＳ２０７による演算結果が負の場合、負になった入力ｋに対応した商を格納する入力ｋ商記憶手段１０３−ｋと、当該入力ｋに対応した余りを格納する入力ｋ余り記憶手段１０４−ｋとに、値として「０」を設定する（ステップＳ２０９、Ｓ２１０）。このようにすることにより、ＣＮＴ［ｉ］が負になることがなくなり、以後の処理を簡単にすることができる。

次に、上述の基本原理で説明したように、（式５）に基づき、送信要求を行った入力ｊに対するフレーム長の加算に伴うＣＮＴ［ｉ］の更新を行う（ステップＳ２１１）。すなわち、演算処理の高速化のため、固定小数点を用いた場合は以下のようになる。
演算回路１０６は、入力ｊフレーム長記憶手段１０１−ｊに格納されている入力ｊのフレーム長の値（ｆｌｅｎ）に、入力ｊ余り記憶手段１０４−ｊ内に格納されている入力ｊの余りの値を加算し、その加算結果を入力ｊ重み記憶手段−ｊに格納されている値であるｗｅｉｇｈｔ［ｊ］で除算する。演算回路１０６は、除算結果の商を入力ｊ商記憶手段１０３−ｊに、余りを入力ｊ余り記憶手段１０４−ｊに格納することにより、送信要求を行った入力ｊのＣＮＴ［ｊ］の値を更新する。あるいは、上述した基本原理の（式１３）に基づき、フレーム長を左シフトして、入力ｊの余りとビット結合し、ｗｅｉｇｈｔ［ｊ］で除算するようにしてもよい。

一方、上述したステップＳ２０６の実行後、制御回路１０７は、後段回路から受理信号の受信を待つ。後段からの受理信号を受信すると（ステップＳ２１３）、制御回路１０７は、ＷａｉｔＣｎｔに、ステップＳ２０１において設定したＪｕｄｇｅＷａｉｔの値を設定する（ステップＳ２１４）。制御回路１０７は、選択された入力ｊに接続される前段回路へ受理信号を送信する（ステップＳ２１５）。

ＷａｉｔＣｎｔは、制御回路１０７により、所定の周期（例えばシステムクロック毎）で減算される（ステップＳ２１６）。
上述したステップＳ２１６の実行後、制御回路１０７は、ＷａｉｔＣｎｔの値が０かを判定し、０になるまで繰り返し減算を行う（ステップＳ２１６、Ｓ２１７）。このように、ＷａｉｔＣｎｔの現在を行って０になった場合（ステップＳ２１７：ＹＥＳ）、ＷａｉｔＣｎｔの減算を停止する（ステップＳ２１８）。

上述したステップＳ２１１の後に、ＷａｉｔＣｎｔの値が０になった場合（ステップＳ２１２：ＹＥＳ）、ステップＳ２０４に戻り、ＣＮＴ［ｉ］が最小の入力の選択を行う。

なお、ステップＳ２０４において、ＣＮＴ［ｉ］の最小値を求める際に、同じ値が存在したり、同時に０以下になる入力が存在する場合は、ＷＦＱの基本動作として、該当する入力をラウンドして選択する必要がある。すなわち順繰りに、ｔｍｐ＝入力０ラウンドロビンカウンタ、入力０ラウンドロビンカウンタ＝入力１ラウンドロビンカウンタ、入力１ラウンドロビンカウンタ＝入力２ラウンドロビンカウンタ、入力２ラウンドロビンカウンタ＝入力３ラウンドロビンカウンタ、入力３ラウンドロビンカウンタ＝ｔｍｐ（入力０ラウンドロビンカウンタの元の値）とし、各入力ポートに対応するラウンドロビンカウンタを１つずつずらす。あるいは、いままでの送信履歴から、最も送信を行っていない入力を選択するようにしてもよい。その際の選択処理は、以下に述べるように、各入力ｉに対応して設けられている入力ｉラウンドロビンカウンタ記憶手段１０５−ｉ内に記憶されている入力ｉラウンドロビンカウンタを用いて行うのが効果的である。

すなわち、例えば入力ポート数を４とし、入力２が送信要求ポートとして選択された場合、入力２ラウンドロビンカウンタより大きい値をもつ各入力ｉラウンドロビンカウンタは１デクリメント（減算）を行い、入力２ラウンドロビンカウンタ＝３とする。このようにすることで、最近送信した順に入力ｉラウンドロビンカウンタは、３，２，１，０という値を持つことになる。
上記においては、ＣＮＴ［ｉ］を比較して最も小さい入力を選択しているが、入力ｉラウンドロビンカウンタをさらに用いて比較を行うこともできる。つまり、入力選択時の比較に用いる値をｃｍｐ［ｉ］とするならば、ＣＮＴ［ｉ］の値に同じものがある場合であっても、以下のように容易に選択可能となる。なお、入力数が４の場合を想定しており、よって、入力ｉラウンドロビンカウンタの２ｂｉｔ（０〜３の値）を用いている。また、「｜」はビット結合を表す。

ｃｍｐ［ｉ］（１８ｂｉｔ）
＝ＣＮＴ［ｉ］（１６ｂｉｔ）｜入力ｉラウンドロビンカウンタ（２ｂｉｔ） …（式１３）

さらに入力要求がある場合、ｒｅｑｕｅｓｔ［ｉ］＝０、入力要求がない場合、ｒｅｑｕｅｓｔ［ｉ］＝１とし、以下の式で算出される値（ｃｍｐ［ｉ］）を用いて入力選択時の最小値選択を行う。

ｃｍｐ［ｉ］（１９ｂｉｔ）
＝ｒｅｑｕｅｓｔ［ｉ］（１ｂｉｔ）｜ＣＮＴ［ｉ］（１６ｂｉｔ）｜入力ｉラウンドロビンカウンタ（２ｂｉｔ） …（式１４）

上記のｃｍｐ［ｉ］を用いることにより、入力要求があるかどうかの判断を入力選択時に行わなくてもすむようになる。つまり、上式において算出されたｃｍｐ［ｉ］のうち最小値をもつｃｍｐ［ｉ］を選択し、その選択したｃｍｐ［ｉ］の最小値をＣＭＰ＿ＭＩＮとすると、ＣＭＰ＿ＭＩＮのＭＳＢ（Most Significant Bit：最上位ビット）が１である場合、ｒｅｑｕｅｓｔ［ｉ］が０であった入力がなかった、すなわち、どの入力にも送信要求はなかったということがわかる。また、送信要求が存在していれば、少なくともＣＭＰ＿ＭＩＮのＭＳＢは０になり、選択するポートｉを決定するために最小値のｃｍｐ［ｉ］を求める際には、ＭＳＢが０である、すなわち、入力要求があるポートからのみ選択が行われるため、比較のたびに送信要求があるかどうか判断する必要がなくなる。

図４は、上述したＷＦＱを用いて、各レジスタ値がどのように変化するかの一例を入力数３のＷＦＱを用いて説明する。なお、シフト量（ｗｅｉｇｈｔ［ｉ］の最大値）ｍ＝５であり、時刻０の初期状態において入力はないものとする。また、各入力ポートｉの重みは、ｗｅｉｇｈｔ［０］＝３、ｗｅｉｇｈｔ［１］＝２、ｗｅｉｇｈｔ［３］＝１であるとする。

時刻１において、制御回路１０７は、入力０の送信要求（フレーム長１０００）と、入力１の送信要求（フレーム長６４）を受信する。これにより、ｆｌｅｎ［０］＝１０００、ｆｌｅｎ［１］＝６４が格納される。そして、この時刻０において入力があった入力０と入力１のうち、ｃｎｔ［ｉ］がもっとも小さいのは入力０なので（ｃｎｔ［０］＝１０００、ｃｎｔ［１］＝２０００）、入力０が選択される。そして、（ｆｌｅｎ［０］<<ｍ＋Ｒ［０］）／ｗｅｉｇｈｔ［０］＝（１０００<<５＋２）／３＝１０６６７ 余り１となるため、ｃｎｔ［０］＝１０６６７、Ｒ［０］＝１のように更新される。
また、他の入力のｃｎｔ［ｉ］（ｉ＝１，２）からは、ｃｎｔ［０］の値であった１０００が減算されるが、入力２は減算により負になるので、ｃｎｔ［２］は０となる。また、ラウンドロビン値は、最も最近選択されたポートに対応したものが最も大きな値になるので、ｒｏｕｎｄ［０］が３から３となる。そして、他の各入力のｒｏｕｎｄ［ｉ］（ｉ＝１，２）のうち、３以上の値を持つものをデクリメントする必要があるが、送信したものが最も大きな値である３であったためデクリメントは行わない。

次に、時刻２において、入力２の送信要求（フレーム長１００）を受信する。現在入力があるｃｎｔ［ｉ］、すなわち、入力１と入力２のｃｎｔ［ｉ］を比較すると（ｃｎｔ［１］＝１０００、ｃｎｔ［２］＝０）、ｃｎｔ［２］が最も小さいので、ｃｎｔ［２］が選択され、入力２以外の各入力のｃｎｔ［ｉ］（ｉ＝０，１）から、ｃｎｔ［２］の値である０が減算される。（ｆｌｅｎ［２］<<ｍ＋Ｒ［２］）／ｗｅｉｇｈｔ［２］＝（１００<<５＋０）／１＝３２００ 余り０であるので、ｃｎｔ［２］＝３２００となり、Ｒ［２］には０が加算されるため０のままとなる。選択された入力２のラウンドロビン値ｒｏｕｎｄ［２］は、２から最も大きな値の３に変化し、他の入力のｒｏｕｎｄ［ｉ］で２以上のものは、デクリメントされるため、入力０のｒｏｕｎｄ［０］は３から２に変化する。

続いて、時刻３において、現在入力があるのは入力１のみであるので、入力１以外の各入力のｃｎｔ［ｉ］（ｉ＝０，２）から、ｃｎｔ［１］の値である１０２４が減算される。（ｆｌｅｎ［１］<<ｍ＋Ｒ［１］）／ｗｅｉｇｈｔ［１］＝（１００<<５＋０）／１＝１０２４ 余り０であるので、ｃｎｔ［１］＝１０２４となり、Ｒ［１］には０が加算されるため１のままとなる。選択された入力２のラウンドロビン値ｒｏｕｎｄ［２］は、１から最も大きな値の３に変化し、他の入力のｒｏｕｎｄ［ｉ］で１以上のものは、デクリメントされるため、入力０のｒｏｕｎｄ［０］は２から１に、入力２のｒｏｕｎｄ［２］は３から２に変化する。
時刻４以降も、同様の処理を繰り返すことによりＷＦＱ処理が行われる。

以上、本発明の実施の形態について説明したが、トラヒックコントロール装置の各手段は、専用のハードウェア（例えば、ワイヤードロジック等）により実現されるが、メモリおよびＣＰＵ（中央処理装置）により構成され、各部の機能を実現するためのプログラムをメモリからロードして実行することによりその機能を実現させるものであってもよい。また、メモリインタフェース回路の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、メモリインタフェース回路の各部に必要な処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。

また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。

本発明の一実施の形態によるＷＦＱ回路の基本動作フローを示す図である。 同実施形態によるＷＦＱ回路の構成例を示すブロック図である。 同実施形態によるＷＦＱ回路の動作フローを示す図である。 同実施形態によるＷＦＱ回路の動作を説明するための図である。 除算累積誤差を説明するための図である。

符号の説明

１００…ＷＦＱ回路
１０１−０…入力０フレーム長記憶手段
１０１−１…入力１フレーム長記憶手段
１０１−２…入力２フレーム長記憶手段
１０１−３…入力３フレーム長記憶手段
１０２−０…入力０重み記憶手段
１０２−１…入力１重み記憶手段
１０２−２…入力２重み記憶手段
１０２−３…入力３重み記憶手段
１０３−０…入力０商記憶手段
１０３−１…入力１商記憶手段
１０３−２…入力２商記憶手段
１０３−３…入力３商記憶手段
１０４−０…入力０余り記憶手段
１０４−１…入力１余り記憶手段
１０４−２…入力２余り記憶手段
１０４−３…入力３余り記憶手段
１０５−０…入力０ラウンドロビンカウンタ記憶手段
１０５−１…入力１ラウンドロビンカウンタ記憶手段
１０５−２…入力２ラウンドロビンカウンタ記憶手段
１０５−３…入力３ラウンドロビンカウンタ記憶手段
１０６…演算回路
１０７…制御回路

Claims (4)

1. 複数の入力ポートからの入力を後段に出力するトラヒックコントロール装置におけるトラヒックコントロール方法であって、
   前記トラヒックコントロール装置は、複数の入力ポートそれぞれに対応した商カウンタの値及び余りカウンタの値を記憶する記憶手段を備えており、
   前記商カウンタのうち最小値である商カウンタを選択し、選択された商カウンタに対応した入力ポートからの送信要求を後段回路に送信する出力過程と、
   選択された商カウンタ以外の前記商カウンタの値を、前記選択された商カウンタの値を減算した値に更新する更新過程と、
   前記選択された商カウンタに対応した入力ポートからの入力のフレーム長と、当該入力ポートに対応した余りカウンタの値とを加算した値を、当該入力ポートに対応した所定の重みの値で除算し、除算した結果の商により前記選択された商カウンタの値を更新し、除算した結果の余りにより当該入力ポートに対応した余りカウンタの値を更新する演算過程と
   を有することを特徴とするトラヒックコントロール方法。
2. 前記演算過程において、前記選択された商カウンタに対応した入力ポートからの入力のフレーム長と、当該入力ポートに対応した余りカウンタの値とを加算する代わりに、当該入力ポートの入力のフレーム長を、所定分、あるいは、重みのとりうる最大値分だけ左ビットシフトし、当該入力ポートに対応した余りカウンタの値と連結する、
   ことを特徴とする請求項１に記載のトラヒックコントロール方法。
3. 前記記憶手段は、各入力ポートに対応し、送信要求が送信された順序に応じて値が変更されるラウンドロビンカウンタをさらに記憶し、
   前記出力過程において、最小値を有する前記商カウンタが複数ある場合、前記ラウンドロビンカウンタの値により、送信要求を送信する入力ポートを選択する、
   ことを特徴とする請求項１または請求項２に記載のトラヒックコントロール方法。
4. 複数の入力ポートからの入力を後段に出力するトラヒックコントロール装置であって、
   複数の入力ポートそれぞれに対応した商カウンタの値及び余りカウンタの値を記憶する記憶手段と、
   前記商カウンタのうち最小値である商カウンタを選択し、選択された商カウンタに対応した入力ポートからの送信要求を後段回路に送信する制御手段と、
   選択された商カウンタ以外の前記商カウンタの値を、前記選択された商カウンタの値を減算した値に更新するとともに、当該選択された商カウンタに対応した入力ポートからの入力のフレーム長と、当該入力ポートに対応した余りカウンタの値とを加算した値を、当該入力ポートに対応した所定の重みの値で除算し、除算した結果の商により前記選択された商カウンタの値を更新し、除算した結果の余りにより当該入力ポートに対応した余りカウンタの値を更新する演算手段と、
   を備えることを特徴とするトラヒックコントロール装置。

Images