(57)【特許請求の範囲】
【請求項１】
パケットデータをバッファに蓄積しながら転送するパケット転送装置において、
該バッファの蓄積量がゼロでないときの該バッファの時間平均蓄積量を計算する平均蓄積量計算部と、
該バッファの実際の蓄積量がゼロになったことをトリガにして該時間平均蓄積量を更新するための減衰値の計算を開始し、該バッファの蓄積量がゼロになってから最初のパケットデータの到着をトリガにして該減衰値の計算を終了するアイドル時間減衰値計算部とが設けられるとともに、
該アイドル時間減衰値計算部が、
該バッファの蓄積量がゼロになってから最初のパケットデータが到着するまでのアイドル時間を複数の時間間隔に分割したときの時間間隔に対応する部分減衰値を求める部分減衰値生成部と、
該部分減衰値生成部により求められた該時間間隔毎の部分減衰値を該アイドル時間の終了まで累積演算して更新することにより該減衰値を求める減衰値更新部とをそなえて構成されたことを特徴とする、パケット転送装置における平均バッファ蓄積量計算装置。
【請求項２】
該部分減衰値生成部が、
該時間間隔の経過を計測する時間計測部と、
該時間間隔毎の部分減衰値を予め記憶しておくとともに、該時間計測部で計測された該時間間隔の経過毎に対応する部分減衰値を該減衰値更新部へ出力する部分減衰値記憶部とをそなえて構成されたことを特徴とする、請求項１記載のパケット転送装置における平均バッファ蓄積量計算装置。
【請求項３】
該部分減衰値生成部が、
該時間間隔として、該部分減衰値が２のべき乗となる時間間隔で該部分減衰値を求めるように構成されたことを特徴とする、請求項１記載のパケット転送装置における平均バッファ蓄積量計算装置。
【請求項４】
該部分減衰値生成部が、
該アイドル時間を複数の一定時間間隔に分割したときの該一定時間間隔に満たない時間間隔に対応する部分減衰値を求める一定時間間隔未満部分減衰値計算部をそなえていることを特徴とする、請求項１記載のパケット転送装置における平均バッファ蓄積量計算装置。
【請求項５】
パケットデータをバッファに蓄積しながら転送するパケット転送装置において、
該バッファの実際の蓄積量がゼロでないときの該バッファの時間平均蓄積量を計算し、
該バッファの実際の蓄積量がゼロになったことをトリガにして該時間平均蓄積量を更新するための減衰値の計算を開始し、
該バッファの蓄積量がゼロになってから最初のパケットデータが到着するまでのアイドル時間を複数の時間間隔に分割したときの時間間隔に対応する部分減衰値を求め、
該時間間隔毎の部分減衰値を該アイドル時間の終了まで累積演算して更新することにより該減衰値を求め、
該バッファの蓄積量がゼロになってから最初のパケットデータの到着をトリガにして該減衰値の計算を終了することを特徴とする、パケット転送装置における平均バッファ蓄積量計算方法。
【請求項６】
該時間間隔の経過を計測し、
該時間間隔毎の部分減衰値を予め記憶部に記憶しておくとともに、該時間間隔の経過毎に対応する部分減衰値を出力することを特徴とする、請求項５記載のパケット転送装置における平均バッファ蓄積量計算方法。
【請求項７】
該時間間隔として、該部分減衰値が２のべき乗となる時間間隔で該部分減衰値を求めることを特徴とする、請求項５記載のパケット転送装置における平均バッファ蓄積量計算方法。
【請求項８】
該アイドル時間を複数の一定時間間隔に分割したときの該一定時間間隔に満たない時間間隔に対応する部分減衰値を求めることを特徴とする、請求項５記載のパケット転送装置における平均バッファ蓄積量計算方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケット転送装置における平均バッファ蓄積量計算装置及び方法に関し、例えば、ＩＰ（Internet Protocol）ルータやＡＴＭ（Asynchronous Transfer Mode）交換機等に用いて好適な平均バッファ蓄積量計算装置及び方法に関する。
【０００２】
【従来の技術】
近年、通信ネットワークにおけるトラヒック量の増加に伴って、輻輳によるネットワークの利用効率の低下が問題となっているが、従来は、この対策として、端局の送受信装置（端末）に輻輳回避メカニズムを実装することで、ネットワーク利用効率の低下に対してある程度の効果をもたらしている。
【０００３】
この送受信装置での輻輳回避メカニズムとしては、ＴＣＰ（Transmission Control Protocol）プロトコルに実装されているものがよく知られており、このメカニズムでは、例えば、送信装置がネットワーク内（ネットワーク中継装置）においてパケットが廃棄されていることを検出すると、自身の送信速度を下げることによって輻輳の回避を行ない、一方、パケットの廃棄が発生していなければ送信装置は帯域の有効利用のために送信速度を上げるようになっている。
【０００４】
ところが、この輻輳回避メカニズムが複数の送信側端末に実装されている場合、パケットの廃棄が発生すると、各送信側端末が一斉に送信速度を下げたり、逆に、パケットの廃棄が発生していないと、各送信側端末が、一斉に送信速度を上げたりする現象、即ち、複数の送信側端末の輻輳回避メカニズムが同期するグローバル同期（Global Synchronization）が発生する場合がある。
【０００５】
このグローバル同期が発生すると、送信速度を下げる制御が同期した場合には、ネットワークの利用効率が低下し、逆に、送信速度を上げる制御が同期した場合には、ネットワーク内に輻輳が生じて、パケットの廃棄が発生する可能性がある。
そのため、ネットワークにおける輻輳を十分に回避するためには、送受信装置に輻輳回避メカニズムを実装するだけでは十分でなく、ＩＰルータやＡＴＭ交換機などのネットワーク中継装置（パケット転送装置；以下、単に「中継装置」と言うこともある）においても輻輳回避の対策が必要とされるようになってきた。
【０００６】
即ち、ネットワーク中継装置に対し、輻輳回避メカニズムとして、ネットワーク中継装置内のキューがあふれる前に積極的にパケットを廃棄する「アクティブキュー管理」の実装の必要性が高まってきている。例えば、インターネット技術の標準化団体であるIETF（Internet Engineering Task Force）でも、文献１（ B.Braden,D.Clark, J.Crowcroft, "Recommendations on Queue Management and Congestion Avoidance in the Internet", RFC2309, IETF,April 1998）などに示されるように、「アクティブキュー管理」を中継装置へ実装することを強く推奨している。
【０００７】
この「アクティブキュー管理」を実現する方式としては、ＲＥＤ（Random Early Detection）がよく知られており、文献２（S.Floyd and V.Jacobson,“Random Early Detection Gateway for Congestion Avoidance in the Internet", IEEE/ACM Trans. on Networking, August 1993）等に記載されている。
このＲＥＤ（及びその変形）では、トラヒックのバースト性及び一時的な輻輳をある程度許容するために、実際のキュー長ｑで廃棄判定を行なうのではなく、パケットの到着毎に実際のキュー長ｑに基づいて平均キュー長ａｖｇの算出を行ない、この算出された平均キュー長ａｖｇに基づいてパケットの廃棄確率の算出が行なわれる。なお、キュー長ｑは中継装置内に蓄積されているパケットデータの長さ（量）について示したものであり、その単位は、ビット数やパケット数などの値で示される。
【０００８】
このＲＥＤに代表される「アクティブキュー管理」を中継装置に実装するためには、平均キュー長ａｖｇの計算機能が必要となる。
ここで、上記の平均キュー長ａｖｇの計算は、実際のキュー長ｑにもとづいて、パケット到着毎に指数重み付け平均移動法と呼ばれる方法によって行なわれることが定義されている。
【０００９】
すなわち、ＲＥＤでは、中継装置で許容するバーストの間隔と大きさによって決定する定数（重み係数）をＷ_ｑ（Ｗ_ｑ（０≦Ｗ_ｑ≦１）），ｑを実際のキュー長とすると、ｑ＞０の場合の平均キュー長ａｖｇは、次式（１）により求められることが知られている。
ａｖｇ←（１−Ｗ_ｑ）ａｖｇ＋Ｗ_ｑ・ｑ          …（１）
なお、この式（１）において、重み係数Ｗ_ｑを１に近く設定すれば、平均キュー長ａｖｇは、実際のキュー長ｑに近い値をとるようになり、バーストの影響についてあまり考慮しない値になり、逆に、重み係数Ｗ_ｑを０に近く設定すれば、平均キュー長ａｖｇは、バーストの影響を考慮した値になる。
【００１０】
また、実際のキュー長ｑが０である時間、すなわち、アイドル時間（idle_time）での平均キュー長ａｖｇは、そのアイドル時間中に中継装置で転送できたはずのパケットの数ｍを推定することで計算される。例えば、このアイドル時間中に転送できたはずのパケット数ｍは、アイドル時間をidle_time，最短パケット（最少単位のパケット）を転送するのに要する時間をｓとすると、次式（２）のように求められる。
【００１１】
ｍ＝idle_time／ｓ（個）                …（２）
この場合、アイドル時間終了直後の平均キュー長ａｖｇは、次式（３）のように表わされることが知られている。
ａｖｇ←（１−Ｗ_ｑ）mａｖｇ                  …（３）
なお、この計算〔減衰値（１−Ｗ_ｑ）mによる平均キュー長ａｖｇの更新〕を行なわないと、キュー長ｑがゼロ以上（ｑ＞０）の場合の平均キュー長ａｖｇで、次に到着したパケットについての廃棄確率が計算されるため、廃棄確率が高くなる場合がある。
【００１２】
以上のように、ＲＥＤによるアクティブキュー管理方法では、例えば、図１１に示すように、実際のキュー長ｑがゼロになってから次のパケットが到着するための間（アイドル時間；０〜idle_time）には、平均キュー長ａｖｇの計算に関する処理は行なわれず、アイドル時間が終了してから、減衰値（１−Ｗ_ｑ）mの計算が行なわれ（idle_time〜ｔ１）、得られた減衰値（１−Ｗ_ｑ）mを用いて平均キュー長ａｖｇの更新が行なわれる（ｔ１〜ｔ２）のである。そして、このようにして、計算された平均キュー長ａｖｇに基づいて、廃棄判定などの処理（ｔ２〜ｔ３）が行なわれてから、初めてパケット送信が行なわれる。
【００１３】
【発明が解決しようとする課題】
しかしながら、上述したような減衰値（１−Ｗ_ｑ）m（以下、（１−Ｗ_ｑ）＾ｍと表記する）を算出する際に必要なべき乗計算は、一般的には、例えば、文献３（野崎昭弘,“アルゴリズムと計算”；pp.10〜15,共立出版株式会社,１９８７年１０月）に記載されているように、加減乗除などの四則演算よりも、多くの計算時間、メモリ容量が必要となり、例えば、べき乗計算M＾ｅ（M,eのビット幅はそれぞれｘ,ｙ）に必要な計算時間及びメモリ容量は、eのビット幅ｘとの関係が深くビット幅ｙが大きいほど増加する。なお、この場合のべき乗計算は、少なくともｙ回以上の乗算処理が必要となることが知られており、べき乗計算時間はｙ回分の乗算処理時間以上となる。
【００１４】
つまり、減衰値計算では、ｍが大きくなる（アイドル時間が長くなる）と、減衰値（１−Ｗ_ｑ）＾ｍのべき乗計算に必要な時間（idle_time〜ｔ１）が大きくなる。このため、従来手法では、中継装置で転送するパケットの遅延時間が大きくなるので、通信品質の劣化を招いたり、また、高速回線に接続される中継装置への適用が困難であるなどの課題があった。
【００１５】
なお、上記Ｍを上記ｅよりも小さい値でべき乗した値を辞書としてテーブルに記憶し、このべき乗計算の一部をテーブル検索で処理することで、本来必要なべき乗計算の次数を低下させて、減衰値計算を高速化する手法もある。この場合、テーブルを記憶するメモリ容量を増やせば、より計算時間を短縮できることになるが、メモリ容量を増やすと装置（ハードウェア）規模の増大及びコストの増加につながる。
【００１６】
本発明は、このような課題に鑑み創案されたもので、平均キュー長を更新するための減衰値の計算をアイドル時間中に開始して、平均キュー長の計算が完了するまでの時間を短縮することで、回路規模及びコストが少なくて済み、且つ、パケット転送の高速処理が可能な、パケット転送装置における平均バッファ蓄積量計算装置及び方法を提供することを目的とする。
【００１７】
【課題を解決するための手段】
上記の目的を達成するために、本発明のパケット転送装置における平均バッファ蓄積量計算装置は、バッファの蓄積量がゼロでない場合には、前記バッファの時間平均蓄積量を計算する平均蓄積量計算部と、前記バッファの実際の蓄積量がゼロになったことをトリガにして前記時間平均蓄積量を更新するための減衰値の計算を開始し、前記バッファの蓄積量がゼロになってから、最初のパケットデータの到着をトリガにして減衰値の計算を終了するアイドル時間減衰値部とをそなえたことを特徴としている。
【００１８】
このような構成により、本発明のパケット転送装置における平均バッファ蓄積量計算装置（方法）では、アイドル時間内に平均蓄積量を更新するための減衰値の計算を開始するので、従来のようにアイドル時間が終了してから減衰値の計算を開始する場合に比して前記平均蓄積量を更新するまでの時間が短縮される。
【００２０】
また、前記アイドル時間減衰値計算部は、前記アイドル時間を複数の時間間隔に分割したときの時間間隔に対応する部分減衰値を求める部分減衰値生成部と、部分減衰値生成部により求められた該時間間隔毎の部分減衰値をこのアイドル時間の終了まで累積演算して更新することにより前記減衰値を求める減衰値更新部とをそなえていてもよく、このようにすれば、前記部分減衰値の計算に必要なべき乗次数を、アイドル時間を分割しない場合の減衰値の計算に必要なべき乗の次数よりも小さくできる。
【００２１】
そして、前記部分減衰値生成部に、時間間隔の経過を計測する時間計測部と、前記時間間隔毎の部分減衰値を予め記憶しておくとともに、この時間計測部で計測された前記時間間隔の経過毎に対応する部分減衰値を前記減衰値更新部へ出力する部分減衰値記憶部とをそなえて構成すれば、前記時間間隔毎の部分減衰値の計算が不要になる。
【００２２】
さらに、前記部分減衰値生成部が、前記時間間隔として、部分減衰値が２のべき乗となるように時間間隔を設定すれば、べき乗計算の代わりにシフト演算で減衰値の計算が可能になる。
また、前記部分減衰値生成部が、前記アイドル時間を複数の一定時間間隔に分割したときの一定時間間隔に満たない時間間隔に対応する部分減衰値を求める一定時間間隔未満部分減衰値計算部をそなえれば、前記一定間隔に満たない時間間隔に対応する部分減衰値を求めて、前記一定間隔毎の部分減衰値に反映することができる。
【００２３】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
（ａ）第１実施形態の説明
図１は、本発明の第１実施形態に係るパケット転送装置としてのネットワーク中継装置の構成を示すブロック図であって、この図１に示すネットワーク中継装置（ＩＰルータやＡＴＭ交換機など）５０は、平均キュー長計算装置（平均バッファ蓄積量計算装置）１，バッファ（パケットバッファ）２，書込制御部３，読出制御部４，キュー長計測部（カウンタ）５，パケット到着通知部６，廃棄判定部１３をそなえて構成されている。
【００２４】
ここで、バッファ２は、パケット転送装置５０に送信されてきたパケットデータ（ＩＰパケットやＡＴＭセルなど）を送信対象である装置に送信する前に一旦記憶しておくためのものであり、書込（エンキュー）制御部３は、到着したパケットデータをバッファ２に書き込むための制御（エンキュー制御）を行なうものであるが、本実施形態では、廃棄判定部１３での判定結果に基づいて、パケットデータの廃棄（「アクティブキュー管理」）も行なえるようになっており、読出（デキュー）制御部４はバッファ２に蓄積されたパケットのデータの読み出し制御（デキュー制御）を行なうためのものである。
【００２５】
また、キュー長計測部５は、バッファ２の蓄積状態を監視して実際のキュー長ｑを計測して、後述する平均キュー長計算装置１の減衰値計算制御部７に通知するためのもので、例えば、書込制御部３によるバッファ２への書き込みパケット数と読出制御部４によるバッファ２からの読み出しパケット数との差を監視することで、バッファ２のキュー長ｑを計測できるようになっている。
【００２６】
また、パケット到着通知部６は、パケットの到着（書込制御部３によるバッファ２のパケット書き込み）を後述する平均キュー長計算装置１の減衰値計算制御部７に通知するためのものである。
さらに、平均キュー長計算装置１は、バッファ２内の平均キュー長（平均バッファ蓄積量）ａｖｇの計算を行なうためのものであり、本実施形態では、図１中に示すように、減衰値（平均キュー長）計算制御部７，平均キュー長計算部（平均蓄積量計算部）８，減衰値計算部（アイドル時間減衰値計算部）１０，平均キュー長（蓄積量）更新部（乗算器）１１及びセレクタ１２をそなえて構成されている。
【００２７】
ここで、減衰値計算制御部７は、キュー長計測部５からのバッファ２の実際のキュー長ｑと、パケット到着を示す情報（パケット到着信号）に基づいて、平均キュー長ａｖｇの計算を制御するためのもので、ここでは、例えば、次のような機能を有している。
（１）キュー長ｑがゼロ以上（ｑ＞０）の場合には、パケットが到着する毎に平均キュー長計算部８にパケット到着を示す信号（パケット到着信号）を平均キュー長ａｖｇの計算を開始させるためのトリガとして出力する機能。
（２）キュー長ｑがゼロ（ｑ＝０）の場合には、減衰値計算制御部７は、減衰値計算部１０に、減衰値計算を開始させるためのトリガとして、ｑ＝０を示す信号を送信する機能。
（３）キュー長がゼロ（ｑ＝０）になった場合には、平均キュー長更新部１１にもこのｑ＝０を示す信号を、後述するように平均キュー長更新部１１に記憶された値を初期値にリセットするための信号として出力する機能。
（４）キュー長ｑがゼロ（ｑ＝０）の状態でパケットが到着した場合には、パケット到着を示す信号を減衰値計算部１０に減衰値計算を終了させるためのトリガとして出力する機能。
（５）セレクタ１２に、平均キュー長計算部８からの出力と、平均キュー長更新部１１からの出力のいずれかを有効にさせるため、ｑ＝０であるかどうかを判断させるための回線状態（実際のキュー長）を出力する機能。
【００２８】
また、平均キュー長計算部８は、実際のキュー長ｑがゼロより大きい（ｑ＞０）場合に、バッファ２の平均キュー長ａｖｇを計算するためのものであり、さらに、減衰値計算部１０は、バッファ２の実際のキュー長ｑがゼロになってから最初のパケットデータが到着するまでのアイドル時間（idle_time）内に、それまでの平均キュー長ａｖｇを更新するための前記減衰値（１−Ｗ_ｑ）＾ｍを計算するためのもので、ここでは、上記のｑ＝０となったとき減衰値計算制御部７から出力されるトリガを受けることにより、減衰値（１−Ｗ_ｑ）＾ｍの計算を開始し、また、上記のｑ＝０の状態でパケットが到着した時に減衰値計算制御部７から出力されるトリガを受けることで減衰値の計算を終了する。
【００２９】
さらに、平均キュー長更新部１１は、平均キュー長計算部８で得られた平均キュー長ａｖｇと、減衰値計算部１０で得られた減衰値（１−Ｗ_ｑ）＾ｍとを乗算することによって、平均キュー長ａｖｇを更新するためのものである。
そして、セレクタ１２は、平均キュー長計算部８で得られたｑ＞０の場合の出力と、減衰値計算部１０で得られた減衰値（１−Ｗ_ｑ）＾ｍによって、平均キュー長更新部１１において更新された平均キュー長ａｖｇとのいずれかを選択して、廃棄判定部１３に出力するためのものである。
【００３０】
すなわち、セレクタ１２は、バッファ２のキュー長ｑがゼロより大きい（ｑ＞０）場合には、平均キュー長計算部８の出力を平均キュー長ａｖｇとして廃棄判定部１３に出力する一方、キュー長ｑが０（ｑ＝０）の場合には、平均キュー長更新部１１の出力を平均キュー長ａｖｇとして出力するようになっているのである。
【００３１】
そして、廃棄判定部１３は、このセレクタ１２からの最新の平均キュー長ａｖｇに基づいて、バッファ２内のパケットの廃棄確率を算出してパケット廃棄処理を実行するかどうかの判定を行なうためのものであり、廃棄と判定した場合には書込制御部３に対してパケットの廃棄を指示し、廃棄をしないと判定した場合には、書込制御部３に書き込みを許可し、読出制御部４が通常通りパケットを読み出すことで、パケットの転送を実行させる。
【００３２】
次に、前述した平均キュー長計算部８は、上記の機能を実現すべく、例えば、図１中に示すように、平均キュー長記憶部（レジスタ）９，パラメータ記憶部（Ｗ_ｑレジスタ）２１，減算器２２，乗算器２３，加算器２４などをそなえて構成されている。
ここで、上記の平均キュー長記憶部９は、平均キュー長ａｖｇを記憶しておくためのもので、セレクタ１２から廃棄判定部１３に出力されるものと同じ出力を受信することで、常に、最新の平均キュー長ａｖｇを記憶しておくようになっている。
【００３３】
また、パラメータ記憶部２１は、このパケット転送装置５０内で許容するバーストの間隔と大きさによって決定される重み係数（時間定数）Ｗ_ｑ（０≦Ｗ_ｑ≦１）を保持しておくためのものであり、減算器２２は、キュー長計測部５からの実際のキュー長ｑと平均キュー長記憶部９からの平均キュー長ａｖｇとを減算するためのものであって、この減算器２２の出力は、次式（４）で表されることになる。
【００３４】
減算器２２の出力＝ａｖｇ−ｑ                  …（４）
また、乗算器２３は、この減算器２２の出力と、重み係数Ｗ_ｑとを乗算するためのものであり、その出力は次式（５）のように表されることになる。
乗算器２３の出力＝Ｗ_ｑ×（ｑ−ａｖｇ）＝Ｗ_ｑ・ｑ−Ｗ_ｑ・ａｖｇ…（５）
そして、加算器２４は、この乗算器２３の出力と平均キュー長記憶部９からの最新の平均キュー長ａｖｇとを加算して、平均キュー長計算部８の出力として、セレクタ１２に出力するためのものであり、この加算器２４の出力は、次式（６）のように表されることになる。
【００３５】
0003769176.tif 000002
この式（６）から、加算器２４からの出力は、前記の式（１）で表される平均キュー長ａｖｇと同一であることが分かる。そして、ｑ＞０の場合には、この加算器２４の出力がセレクタ１２で選択されて平均キュー長ａｖｇとして出力される。
【００３６】
一方、式（３）において前述したように、ｑ＝０の場合の平均キュー長ａｖｇを更新するための減衰値（１−Ｗ_ｑ）＾ｍは、本実施形態においても、アイドル時間中に転送できたはずのパケット数をｍ、アイドル時間をidle_time、最短パケットを転送するのに要する時間をｓとすると、次式（７）のように変形することができる。
【００３７】
0003769176.tif 000003
そして、重み係数Ｗ_ｑは、前述したように、パケット転送装置５０で許容するバーストの間隔と大きさによって決まる定数であり、また、ｓも回線の性質による固定的な値であるため、上記の式（７）における（１−Ｗ_ｑ）＾（１／ｓ）は定数と考えることができるので、これを次式（８）のようにＣとおくと、式（７）は式（９）のように変形できる。
【００３８】
（１−Ｗ_ｑ）＾（１／ｓ）＝Ｃ                …（８）
（１−Ｗ_ｑ）＾ｍ＝Ｃ＾idle_time             …（９）
つまり、平均キュー長ａｖｇを更新するための減衰値（１−W_ｑ）＾ｍは、idle_timeのべき乗関数として表すことができる。
【００３９】
ここで、上記のidle_timeを複数の時間間隔（Ｔ１，Ｔ２，……，Ｔｄ）に分割すると、idle_timeは次式（１０）のように表すことができる。
idle_time＝Ｔ１＋Ｔ２＋……＋Ｔｄ           …（１０）
したがって、式（９）において前述した減衰値は、次式（１１）のように変形できる。
【００４０】
Ｃ＾idle_time＝Ｃ＾Ｔ１×Ｃ＾Ｔ２×……×Ｃ＾Ｔｄ     …（１１）
つまり、平均キュー長ａｖｇの計算に用いる減衰値は、分割した各時間間隔Ｔ１，Ｔ２，……，Ｔｄが経過する毎に、その時間間隔Ｔ１，Ｔ２，……，Ｔｄに対応する部分減衰値を個々に計算し、各値を乗算することで求められるのである。
【００４１】
ここで、このidle_timeを分割する時間間隔を一定にした場合（図２参照）には、その一定時間間隔をＴ，アイドル時間中の一定時間間隔Ｔの数をｋ，アイドル時間中の一定時間間隔Ｔに満たない一定時間間隔Ｔ未満の時間間隔（以下、余り時間ともいう）をΔＴとすると、idle_timeは次式（１２）のように表すことができる。
【００４２】
0003769176.tif 000004
従って、この場合、式（９）は、次式（１３）のように表すことができる。
0003769176.tif 000005
つまり、アイドル時間を一定時間間隔Ｔで分割した場合には、一定時間間隔Ｔが経過する毎に部分減衰値Ｃ＾Ｔの計算をｋ回繰り返し、最後に、一定時間間隔Ｔに満たない時間間隔ΔＴに対応する部分減衰値Ｃ＾ΔＴを求めることで、アイドル時間中の減衰値の計算が可能になる。
【００４３】
また、この場合、式（１３）における一定時間間隔Ｔの値を、ΔＴが無視できる程十分小さく設定すれば、式（１３）は次式（１４）のように変形できる。
0003769176.tif 000006
つまり、一定時間間隔Ｔの値を、ΔＴが無視できる程十分小さく設定すれば、一定時間間隔Ｔの部分減衰値Ｃ＾Ｔの計算を繰り返し行なうだけで、減衰値の計算が可能になる。
【００４４】
ただし、本実施形態では、上記の余り時間ΔＴが無視できず、この余り時間ΔＴについての部分減衰値Ｃ＾ΔＴも算出する必要がある場合について説明する。
即ち、上記の式（１３）で表されるような減衰値演算を実現すべく、本実施形態の減衰値計算部１０は、例えば、図１及び図３に示すように、上記の時間間隔Ｔに対応する部分減衰値Ｃ＾Ｔを求める部分減衰値計算部（部分減衰値生成部）１５と、この部分減衰値計算部１５により求められたＣ＾Tをアイドル時間終了まで乗算（累積演算）することにより更新する減衰値更新部１４とをそなえて構成されており、このために、部分減衰値計算部１５は、さらに、時間計測部１９，パラメータ記憶部（レジスタ）１６及びべき乗計算部１７をそなえて構成されている。
【００４５】
ここで、部分減衰値計算部１５において、パラメータ記憶部１６は、式（８）の定数Ｃの値を記憶しておくためのものであり、べき乗計算部１７は、時間計測部１９からの一定時間間隔Ｔ毎に出力されるべき乗計算要求をトリガとして、式（８）の定数Ｃを用いて、時間計測部１９からの一定時間間隔Ｔに対応した部分減衰値Ｃ＾Ｔを計算するためのものである。
【００４６】
また、時間計測部１９は、べき乗計算部１７に対して、上記の一定時間間隔Ｔのべき乗計算要求を行なうためのもので、このために、計時（経過）時間監視部１９ａと、タイマー１９ｂと、タイミング発生部１９ｃとをそなえて構成されており、減衰値計算制御部７からのｑ＝０である旨を示す信号をトリガとして、タイマー１９ｂがカウント（計時）動作を開始し、このタイマー１９ｂでの、計時時間が一定時間間隔Ｔに達したら、計時時間監視部１９ａがべき乗計算部１７へ部分減衰値の計算を要求するとともに、タイマー１９ｂをリセットするという一連の動作を、ｑ＝０となった後の最初のパケットデータの到着により、計時時間監視部１９ａがタイミング発生部１９ｃからべき乗計算部停止要求を受けるまで繰り返すことによって、一定時間間隔Ｔ毎にべき乗計算部１７にべき乗計算要求を出力するようになっている。
【００４７】
そして、減衰値更新部１４は、べき乗計算部１７からの一定時間間隔Ｔに対応したべき乗計算結果（部分減衰値）Ｃ＾Ｔを上記のように累積演算するためのもので、このために、部分減衰値記憶レジスタ（tempレジスタ）１４ａと、乗算器１４ｂとをそなえており、次式（１５）に示すように、部分減衰値記憶レジスタ１４ａに記憶された値temp（初期値＝１）と、べき乗計算部１７で得られた一定時間間隔Ｔの部分減衰値Ｃ＾Ｔとを乗算して、部分減衰値記憶レジスタ１４ａのtempに再記憶させることを繰り返すことによって、アイドル時間中の部分減衰値Ｃ＾Ｔの累積演算を行なうようになっている。
【００４８】
temp← temp × Ｃ＾Ｔ                  …（１５）
そして、この減衰値計算部１０は、アイドル時間が終了すると、タイミング発生部１９ｃがパケット到着信号に基づいて、計時時間監視部１９ａが最後の一定時間間隔Ｔの後の余り時間ΔＴ（式（１２）参照）を計測し、べき乗計算部１７に、この余り時間ΔＴに対応したべき乗計算を要求して、べき乗計算部１７がこの余り時間ΔＴに対応する部分減衰値Ｃ＾ΔＴを計算する一定時間間隔未満部分減衰値計算部２５としての機能も有している。
【００４９】
即ち、減衰値計算部１０は、一定時間間隔Ｔに対応する部分減衰値Ｃ＾Ｔを計算し、この計算した部分減衰値Ｃ＾Ｔを累積演算する一連の動作をｋ回繰り返した後、アイドル時間が終了すると、余り時間ΔＴに対応する部分減衰値Ｃ＾ΔＴを計算して、ｋ回累積演算して得られた部分減衰値（Ｃ＾Ｔ）＾ｋに乗じる（反映させる）ことによって、余り時間ΔＴをも考慮した精度の良い減衰値を計算できるようになっているのである。
【００５０】
以下、上述のごとく構成されたパケット転送装置５０の動作を図４，図５（ａ）及び図５（ｂ）に示すフローチャートを参照しながら説明する。
なお、これらの図４，図５（ａ）及び図５（ｂ）に示すフローチャート中において、ｑは現在のキュー長、ａｖｇは平均キュー長、timeは時刻、Ｔは計測時間間隔、tempは減衰値又は部分減衰値（部分減衰値記憶レジスタ１４ａのtempの値）、countは最後にパケットを廃棄してから到着したパケット数（初期値は−１）、Ｒは［０，１］の一様乱数、W_ｑは重みパラメータ、min_thは平均キュー長の最小しきい値、max_thは平均キュー長の最大しきい値、max_pは平均キュー長がmax_thの時の廃棄確率の値、ｐ_ａ及びｐ_ｂは廃棄確率をそれぞれ表すものとし、前記timeの値は、常時インクリメントされているものとする。
【００５１】
まず、減衰値計算制御部７において、図４に示すように、パケット到着やデキュー，一定時間間隔Ｔの経過などの状態変化の発生が確認されると（ステップＡ１）、平均キュー長計算部８による平均キュー長ａｖｇの更新処理が開始される。
ここで、例えば、上記の状態変化が、パケットの到着であった場合（ステップＡ２でＹｅｓの場合）、減衰値計算制御部７は、図５（ａ）に示す「平均キュー長更新処理」を実行する（ステップＢ０）。
【００５２】
即ち、減衰値計算制御部７は、パケット到着により、まず、その時の実際のキュー長ｑ＝０で有るかどうかを判定し（ステップＢ１）、キュー長ｑ≠０であれば（ステップＢ１でＮｏであれば）、セレクタ１２を制御して、平均キュー長計算部８による平均キュー長ａｖｇの計算結果、つまり、前記の式（６）によって更新された（ステップＢ４）、平均キュー長ａｖｇを有効にする。
【００５３】
一方、パケット到着時にキュー長ｑ＝０であった場合には、減衰値計算制御部７は、セレクタ１２を制御して平均キュー長更新部１１の出力、即ち、パケット到着までに減衰値計算部１０によって求められている減衰値（temp←temp×Ｃ＾ΔＴ）によって更新された平均キュー長ａｖｇ（ａｖｇ←ａｖｇ×temp）を有効にする（ステップＢ１のＹｅｓルートからステップＢ２，Ｂ３）。
【００５４】
その後、パケットの到着毎に、このような平均キュー長ａｖｇの更新が実行され、その平均キュー長ａｖｇに基づいて、廃棄判定部１３による廃棄判定処理が実行される。
即ち、廃棄判定部１３は、図４に示すように、セレクタ１２から出力された平均キュー長ａｖｇの値が最小しきい値（min_th）よりも大きく、最大しきい値（max_th）よりも小さいという条件を満足しているかどうか（図６に示す領域▲２▼参照）を判定し（ステップＡ３）、満足していれば（ステップＡ３でＹｅｓであれば）、到着パケットにより、最後にパケットデータを廃棄してから到着したパケット数“count”（初期値は−１）の値を“＋１”する（ステップＡ４）。
【００５５】
そして、廃棄判定部１３は、平均キュー長計算装置１からの平均キュー長ａｖｇに基づいて、次式（１６）に示す廃棄確率ｐ_ｂの計算を行なった（ステップＡ５）後に、最後にパケットを廃棄してから到着したパケット数、換言すれば、廃棄されずに連続してエンキューされたパケット数を示している“count”の値を用いて、連続してパケットが廃棄され難くなるように、式（１６）の廃棄確率を、次式（１７）により補償する計算を行なう（ステップＡ６）。
【００５６】
ｐ_ｂ=max ｐ×（ａｖｇ− min_th）／（max_th − min_th）  …（１６）
ｐ_ａ＝ｐ_ｂ／（１−count×ｐ_ｂ）             …（１７）
その後、廃棄判定部１３は、乱数Ｒを発生し（ステップＡ７）、この乱数Ｒと上記の廃棄確率ｐ_ａとを比較し（ステップＡ８）、廃棄確率ｐ_ａが乱数Ｒ以上であれば（ステップＡ８でＹｅｓの場合）、書込制御部３にパケットデータの書き込みを行なわないように指示することで、廃棄処理が実行され（ステップＡ９）、“count”の値をゼロにリセットしたのち（ステップＡ１０）、処理を終了する。
【００５７】
一方、上記のステップＡ８において、廃棄確率ｐ_ａが乱数Ｒよりも小さい場合（ステップＡ８でＮｏの場合）には、廃棄判定部１３は、到着パケットのバッファ２への書き込みを指示することで、エンキュー処理を実行して（ステップＡ１５）、処理を終了する。
また、上記のステップＡ３において、上述した条件（平均キュー長ａｖｇの値が、最小しきい値min_thより大きく、最大しきいmax_th値よりも小さい）を満足していない場合（ステップＡ３でＮｏの場合）、廃棄判定部１３は、さらに平均キュー長ａｖｇが最大しきい値（図６に示す領域▲３▼参照）以上であるかどうかを判定し（ステップＡ１１）、最大しきい値max_th以上であれば、Ｙｅｓルートを通って、廃棄確率が“１”なので、このパケットの廃棄処理を行ない（ステップＡ１３）、“count”の値をゼロにしてから（ステップＡ１４）、処理を終了する。
【００５８】
一方、上記のステップＡ１１において、平均キュー長ａｖｇが最大しきい値max_thよりも小さい場合（図６に示す領域▲１▼参照）は、廃棄確率がゼロなので、パケットの廃棄処理を行なわずに、“count”を“−１”にセット（リセット）して（ステップＡ１１のＮｏルートからステップＡ１２）、エンキュー処理を行なう（ステップＡ１５）。
【００５９】
さて、ここで、図４に示すステップＡ１において確認された状態変化がパケット到着以外であった場合（ステップＡ２でＮｏの場合）、減衰値計算制御部７は、図５（ｂ）に示す「減衰値更新処理」を実行する（ステップＣ０）。
即ち、減衰値計算制御部７は、まず、発生した状態変化がデキューであるかどうかを判定し（ステップＣ１）、デキューであれば、そのデキューによってキュー長ｑ＝０となったかどうかを判定する（ステップＣ１のＹｅｓルートからステップＣ２）。その結果、キュー長ｑ＝０でなければ（ステップＣ２でＮｏの場合）、ｑ＞０なので減衰値の計算は行なわれずに処理が終了する。
【００６０】
一方、ステップＣ２において、ｑ＝０であれば、Ｙｅｓルートを通って、ステップＣ３へ進み、減衰値計算制御部７は、デキューによりキュー長ｑ＝０となった事を示す信号（トリガ）を減衰値更新部１４と、部分減衰値計算部１５の時間計測部１９のそれぞれに出力する。このとき、減衰値更新部１４（図３参照）の部分減衰値レジスタ１４ａに格納された値“temp”は、初期値“１”にセットされるとともに、タイマー１９ａのタイマー値“time”も“０”に初期化されて（ステップＣ３）、カウントが再開される。
【００６１】
そして、計時時間監視部１９ａにおいて、部分減衰値を計算する際の時間間隔の値Ｔがパラメータ“temp1”にセットされ（ステップＣ４）、この“temp１”の値がゼロになるまで（ステップＣ５でＹｅｓと判定されるまで）、その値を一定の時間値ｃで減じてゆく（ステップＣ５のＮｏルートからステップＣ６及びＣ４）。そして、“temp1”＝０になった時点で一定時間間隔Ｔが経過したことになり、減衰値更新処理は一旦終了する（ステップＣ５のＹｅｓルート）。
【００６２】
ただし、この時間間隔Ｔ経過により、新たな状態変化が発生するので、上記のステップＡ１からの処理が再開される。そして、この場合の状態変化は一定時間間隔Ｔの経過によって発生したので、図４に示すステップＡ２のＮｏルート及び図５（ｂ）に示すステップＣ１のＮｏルートを通って、ステップＣ７に進んで、アイドル時間中の減衰値の更新を行なう。
【００６３】
即ち、計時時間監視部１９ａが“temp1”＝０を確認すると、べき乗計算部１７に対して、一定時間間隔Ｔに対応したべき乗計算Ｃ＾Ｔの要求を出し、これにより、べき乗計算部１７において、一定時間間隔Ｔに相当する部分減衰値Ｃ＾Ｔの計算が行なわれる。そして、減衰値更新部１４において、減衰値記憶レジスタ１４ａに記憶された値“temp”と、べき乗計算部１７において得られた部分減衰値とが乗算されて部分減衰値Ｃ＾Ｔの更新が行なわれる（ステップＣ７）。
【００６４】
その後、タイマー１９ｂの時間“time”はリセットされ（time←０；ステップＣ８）、“temp１”内に一定時間間隔Ｔがセットされ（ステップＣ９）、この“temp１”の値がゼロになるまで（ステップＣ１０でＹｅｓと判定されるまで）、その値が一定の値ｃで減じられてゆく（ステップＣ１０のＮｏルートからステップＣ１１及びＣ９）。そして、“temp1”＝０になった時点で一定時間間隔Ｔが経過したことになり、減衰値更新処理は一旦終了する（ステップＣ１０のＹｅｓルート）。
【００６５】
そして、この後、新たにパケットが到着しない限り、一定時間間隔Ｔ毎の部分減衰値Ｃ＾Ｔの計算の処理（ステップＣ１〜ステップＣ１１）が繰り返され、時間間隔Ｔ毎に部分減衰値Ｃ＾Ｔが計算され、部分減衰値更新部１４において部分減衰値が随時更新されてゆく。
その後、ステップＡ１において、アイドル時間が終了、すなわち、新たなパケット到着による状態変化が発生すると、処理は図５（ａ）に示すステップＢ２に進み、減衰値計算制御部７が、タイミング発生部１９ｃに対し、パケットの到着を示す信号をトリガとして出力し、これにより、タイミング発生部１９ｃは、計時時間監視部１９ａに対して、タイマー１９ｂの停止を要求する信号を出力する。
【００６６】
ここで、前述したように、Ｃ＾ΔＴが無視できる程に一定時間間隔Ｔを小さな値に設定した場合には、一定時間間隔Ｔに対応する部分減衰値Ｃ＾Ｔのみを累積演算した値を減衰値として出力することができるが、ここでは、無視できないので、計時時間監視部１９ａにおいて、その時点でのタイマー１９ｂの値をカウントすることで、余り時間ΔＴが計測され、べき乗計算部１７において、余り時間ΔＴに対応する部分減衰値Ｃ＾ΔＴの計算が行なわれる。
【００６７】
そして、図５（ａ）にて前述したように、部分減衰値更新部１４において、部分減衰値記憶レジスタ１４ａ内の“temp”に格納された値、すなわち、最後の一定時間間隔Ｔに対応した部分減衰値Ｃ＾Ｔまでを累積演算した値（Ｃ＾Ｔ×Ｃ＾Ｔ×…×Ｃ＾Ｔ）と一定時間間隔未満部分減衰値Ｃ＾ΔＴとが乗じられることで、減衰値が計算されて（ステップＢ２）、平均キュー長更新部１１において、平均キュー長記憶部９の最新の平均キュー長ａｖｇと、この減衰値計算部１０で計算された減衰値とが乗じられて、平均キュー長ａｖｇが更新される（ステップＢ３）
以上のように、本第１実施形態によれば、図２に示すようにバッファ２の実際のキュー長ｑがゼロになったことをトリガにして、一定時間間隔Ｔ毎の部分減衰値Ｃ＾Ｔの計算を開始し、各部分減衰値Ｃ＾Ｔを最初のパケット到着まで順次累積演算することで、平均キュー長ａｖｇを更新するための減衰値を計算するので、従来（図１１参照）のようにアイドル時間が終了してから減衰値の計算を開始する場合に比して、平均キュー長ａｖｇの計算が完了するまでの時間を大幅に短縮できる。
【００６８】
その結果、パケット転送装置５０において、最終的なパケット転送までの時間が短縮されるので、高速処理化、通信品質を向上及びネットワークの利用率の向上が図れるとともに、高速回線を収容するパケット転送装置にも適応が可能となる。
また、アイドル時間を一定時間間隔Ｔに分割して、その時間間隔毎に減衰値を計算することによって、アイドル時間を分割しない場合と比して、べき乗計算の次数が小さくなり、べき乗計算が簡易化される。その結果、最終的なパケット転送までの時間がより短縮されるとともに、回路規模を縮小することができるので、装置（ハードウェア）の規模の縮小及びコストの低減を図ることができるようになる。
【００６９】
そして、べき乗計算の一部をテーブルに記憶して、テーブル検索を用いて減衰値の検索を行なう場合のように、テーブル検索用のメモリをそなえる必要もないので、さらなるハードウェア規模の縮小ならびコストの低減に大きく寄与する。
なお、本実施形態の時間計測部１９は、図８により後述するように、タイマー２０ａとレジスタ（時間記憶部）２０ｂとを用いて構成してもよい。
【００７０】
この場合、レジスタ２０ｂが減衰値計算制御部７からｑ＝０を示す信号をトリガとして、一定時間間隔Ｔの値をタイマーに出力し、タイマー２０ａはこの一定時間間隔Ｔを受信すると、この一定時間間隔Ｔのカウントダウンを開始する。
そして、この一定時間間隔Ｔのカウントダウンが終了すると、べき乗計算部１７にべき乗計算Ｃ＾Ｔを要求するとともに、レジスタに再びカウントすべき一定時間間隔Ｔを要求することを繰り返してゆくことで、一定時間間隔Ｔ毎のべき乗計算要求を繰り返す。
【００７１】
このようにしても、図３で上述した時間計測部１９と同様の動作を実現することが可能である。
（ａ１）本発明の第１実施形態の第１変形例の説明
図７は、上述した平均キュー長計算装置１に適応される減衰値計算部の第１変形例を示すブロック図で、この図７に示す部分減衰値生成部１０Ａは、部分減衰値計算（生成）部１５として、部分減衰値記憶部２７と時間計測部１９とをそなえて構成されている。なお、以下の説明において既述の符号と同一符号を付したものは、既述のものと同一もしくは同様の機能を有するものであるとする。
【００７２】
ここで、部分減衰値記憶部２７は、一定の時間間隔Ｔの部分減衰値Ｃ＾Ｔを予め記憶しておき、時間計測部１９からの一定時間間隔Ｔ毎の部分減衰値出力要求に応じて、部分減衰値Ｃ＾Ｔを減衰値更新部１４へ出力するためのものである。
このような構成により、時間計測部１９からの一定時間間隔Ｔ毎の部分減衰値の出力要求に応じて、部分減衰値記憶部２７に記憶された部分減衰値Ｃ＾Ｔを減衰値更新部１４へ出力し、この部分減衰値Ｃ＾Ｔと部分減衰値記憶レジスタ１４ａに記憶された値（temp）（前回の時間間隔Ｔに対応する部分減衰値Ｃ＾Ｔ；初期値＝１）とを乗算器１４ｂにて乗じて、部分減衰値記憶レジスタ１４ａに再記憶させることを繰り返すことで、図３で上述した減衰値計算部１０と同様の減衰値計算が行なわれる。
【００７３】
即ち、本変形例では、分割した時間間隔の数が少ない場合には、部分減衰値Ｃ＾Ｔの値を部分減衰値記憶部２７に予め記憶しておき、時間計測部１９からの一定時間間隔Ｔ毎の部分減衰値出力要求に応じて、記憶されている部分減衰値Ｃ＾Ｔを出力することで、べき乗計算を行なう場合と同様の減衰値計算をべき乗計算そのものを回避して実現しているのである。
【００７４】
従って、べき乗計算部１７が不要な分、さらに減衰値計算を高速に行なうことができる。
（ａ２）本発明の第１実施形態の第２変形例の説明
ところで、第１実施形態における減衰値計算部１０において、式（１５）で表されるような減衰値更新部１４での部分減衰値記憶レジスタ１４ａの値“temp”（初期値＝１）と、べき乗計算部１７からの部分減衰値Ｃ＾Ｔとの乗算処理は、一定時間間隔Ｔを次式（１９）のように部分減衰値が２のべき乗となるような値に設定すると、次式（２０）のように表すことができる。
【００７５】
0003769176.tif 000007
即ち、一定時間間隔Ｔの値を式（１９）を満足する値に設定した場合、時間間隔Ｔ毎に部分減衰値Ｃ＾Ｔの値を累積演算することは、式（２０）に示すように、減衰値記憶レジスタ１４ａに記憶された値“temp”を、シフト演算する処理と等価であることが分かる。
【００７６】
ここで、式（１９）のｔの値を、例えば“１”に設定すると、部分減衰値Ｃ＾Ｔは次式（２１）のように表すことができる。
Ｃ＾Ｔ＝２＾（−１）＝１／２              …（２１）
従って、ｔを“１”に設定した場合には、式（２０）は次式（２２）のようになる。
【００７７】
0003769176.tif 000008
即ち、この場合は、式（２１）を満足するような時間間隔Ｔ毎に、“temp”の値を半減させてゆくことと等価の処理となる。
【００７８】
このような処理を実現すべく、本第２変形例の減衰値計算部１０Ｂ（図８参照）は、（シフト演算部）シフタ２８と時間計測部２０とをそなえて構成されるとともに、シフト演算記憶部（レジスタ）２９がそなえられている。なお、本減衰値計算部１０Ｂも、図１に示す平均キュー長計算装置１の減衰値計算部１０として適用される。
【００７９】
ここで、時間計測部２０は、式（１９）を満足するような時間間隔Ｔ毎に、シフト演算部２８にシフト演算要求（除算要求）を行なうためのもので、このために、例えば、タイマー２０ａと、時間記憶部（レジスタ）２０ｂとをそなえて構成されている。そして、時間計測部２０ｂには、式（１９）を満足する時間間隔Ｔが記憶されており、この時間間隔Ｔが減衰値計算制御部７からの、実際のキュー長ｑがゼロになった事を示す信号をトリガとして、タイマー２０ａに供給されるようになっている。
【００８０】
即ち、この場合は、シフト演算部２８と時間計測部２０とが、アイドル時間を複数の時間間隔Ｔに分割したときの時間間隔Ｔに対応する部分減衰値Ｃ＾Ｔを求める部分減衰値生成部１５として機能し、シフト演算部２８とシフト演算記憶部２９とが、上記の式（２０）を満たすような時間間隔Ｔ毎に、シフト演算記憶部２９の“temp”の値について、シフト演算を繰り返すことによって、各時間間隔Ｔに対応する部分減衰値Ｃ＾Ｔをアイドル時間終了まで累積演算していくことで減衰値を求める（更新する）減衰値更新部１４として機能するのである。
【００８１】
以下、図９に示すシーケンス図を参照しながら、本第２変形例の平均バッファ計算装置１の動作を説明する。
なお、ｑ＞０の場合の動作（平均キュー計算部８（図１参照）における動作）は、従来例と同様であるので省略し、ここでは、アイドル時間中の減衰値を計算するための動作（減衰値計算部１０の動作）について説明することにする。
【００８２】
まず、バッファ２の実際のキュー長ｑがゼロになると、減衰値計算制御部７が、シフト演算記憶部２９と時間計測部２０に対して、キュー長ｑ＝０になった旨を通知し（ステップＤ１）、タイマー２０ａが、この信号をトリガとして、時間記憶部２０ｂからの時間Ｔについてカウントダウンを開始する（ステップＤ３）。
【００８３】
また、時間記憶部２０ｂは、ｑ＝０の旨を示す信号を受信すると、減衰値を初期値“１”に設定し（ステップＤ２）、タイマー２０ａにおいて、時間Ｔのカウントダウンが終了すれば（ステップＤ４）、シフト演算部２８に除算リクエストを出力する（ステップＤ５）。シフト演算部２８は、この要求を受信すると、シフト演算記憶部２９に記憶してある減衰値を、べき乗時間発生部２０の要求により、式（１９）のｔに応じた回数だけ半減処理する（ステップＤ６，Ｄ７）。
【００８４】
なお、ステップＤ４において、時間Ｔのカウントダウンが終了した際に、タイマー２０ａは、時間記憶部２０ｂに初期値を要求し（ステップＤ８）、時間記憶部２０ｂはこの要求に応じて時間Ｔを出力する（ステップＤ９）ことによって、タイマ−２０ａの値は再びＴにセットされ、タイマー２０ａの減算（ステップＤ１０，Ｄ１１）からシフト演算記憶部２９の値の半減までの一連の処理（ステップＤ１０〜ステップＤ１６）をアイドル時間中、すなわち、パケットが到着するまで繰り返す。
【００８５】
そして、減衰値計算制御部７（図１参照）において、パケットが到着したと判定されると、パケット到着信号を平均キュー長記憶部９とシフト演算記憶部２９に送信して（ステップＤ１７）、平均キュー長記憶部９は、このパケット到着信号を受信すると、最新の平均キュー長ａｖｇを平均キュー長更新部１１に送信し（ステップＤ１８）、また、減衰値計算部１０は、計算した減衰値を平均キュー長更新部１１に送信し（ステップＤ１９）、平均キュー長更新部１１は、これらの値を乗じることで平均キュー長ａｖｇを更新し、セレクタ１２及び平均キュー長記憶部９に出力する。
【００８６】
そして、この減衰値計算部１０からの平均キュー長ａｖｇは、セレクタ１２を経由して廃棄判定部１３に出力されて（ステップＤ２０，Ｄ２１）、この平均キュー長ａｖｇに基づく廃棄判定が廃棄判定部１３にて第１実施形態と同様に行なわれるようになっている。
以上のように、本第２変形例によれば、図１で上述した効果と同様の効果が得られるとともに、べき乗計算部１７の代わりにシフト演算部２８を用いることで、上述した第１実施形態やその第１変形例と同様の減衰値計算を実現しているので、より簡素な構成で安価に高速処理可能な平均キュー長計算装置１を実現することができる。
（ｃ）その他
ここで、図１で上述した平均キュー長計算装置１においては、例えば、キュー長ｑが０の場合で、そのアイドル時間が非常に短い場合には、減衰値更新部１０で得られる減衰値の精度が低下する可能性があるため、その減衰値によって更新される平均キュー長ａｖｇの値の精度も低下するおそれがある。
【００８７】
そのために、このような場合には、例えば、図１０に示すように、平均キュー長計算装置１におけるセレクタ１２の後段に、もう一つセレクタ３０を設けて、セレクタ１２からの出力と平均キュー長計算部８の出力のいずれかを選択出力するようにする。
この場合、セレクタ３０は、減衰値計算制御部７からのアイドル時間が短い事を示す信号を受信することにより、平均キュー計算部８からの平均キュー長ａｖｇを有効にして、従来と同様に（図１１参照）、パケット到着後に減衰値の更新処理を開始することで得られる減衰値によって、更新されるべき平均キュー長ａｖｇとして出力する。
【００８８】
一方、減衰値計算制御部７からアイドル時間が短いことを示す信号が受信されない場合には（キュー長ｑ＞０の場合やｑ＝０の場合でも、アイドル時間が所定時間よりも長い場合）には、セレクタ１２の出力を選択して、前述したようにアイドル時間中に求められた減衰値によって更新された平均キュー長ａｖｇを有効にし、この平均キュー長ａｖｇが、廃棄判定部１３での、廃棄判定処理に用いられる平均キュー長ａｖｇとして出力される。
【００８９】
このようにすれば、アイドル時間が非常に短い場合には、セレクタ３０が、平均キュー長計算部８からの平均キュー長ａｖｇを有効にし、廃棄判定部１３ではこのセレクタ３０からの出力に基づいて廃棄判定処理を行なうので、アイドル時間が非常に短い場合にも、精度の高い平均キュー長ａｖｇが得られ、その結果、精度の高い廃棄判定処理を行なうことが可能となる。
【００９０】
また、上述した各実施形態及び各変形例は、図３および図７で上述した時間計測部１９を、図８で上述した時間計測部２０のように、タイマー２０ａと時間記憶部２０ｂとで構成したり、また、図７で上述した部分減衰値計算部１０Ａおよび図８で上述した減衰値更新部１０Ｂに、図３で上述したような一定時間間隔未満部分減衰値計算部２５をそなえたり、種々組み合わせて構成してもよい。
【００９１】
そして、上述した各実施形態及びその各変形例では、減衰値計算制御部７からのｑ＝０を示す信号を減衰値計算開始のトリガ、パケット到着を示す信号を減衰値計算終了のトリガとしているが、これらのトリガは、必ずしもｑ＝０を示す信号及びパケット到着を示す信号で規定しなくてもよい。即ち、アイドル時間中であれば、どのタイミングで開始してもよい。ただし、上述した第１実施形態及びその変形例のようにトリガを設定した方が構成及び制御が簡単である。
【００９２】
そして、本発明は上述した各実施形態及び各変形例に限定されるものではなく、本発明の趣旨を逸脱しない範囲で種々変形して実施することができる。
【００９３】
【発明の効果】
以上詳述したように、本発明によれば、アイドル時間内にバッファの時間平均蓄積量を更新するための減衰値の計算を開始するので、従来のようにアイドル時間が終了してから減衰値の計算を開始する場合に比して、平均キュー長の計算が完了するまでの時間を大幅に短縮できる。従って、パケット転送装置におけるパケットの遅延時間を減少させることができるので、パケット転送装置の高速処理化、通信品質の向上及びネットワークの利用率の向上が図れるとともに、高速回線を収容するパケット転送装置への適用が可能となる。
【００９４】
ここで、前記バッファの蓄積量がゼロになったことをトリガにして前記減衰値の計算を開始し、前記最初のパケットデータの到着をトリガにして前記減衰値の計算を行なえば、減衰値の期間を特定するトリガを容易に規定できるので、簡便な構成・制御で上記の機能が実現できる。
【００９５】
また、前記アイドル時間を複数の時間間隔に分割したときの時間間隔に対応する部分減衰値を求め、求められた前記時間間隔毎の部分減衰値をこのアイドル時間の終了まで累積演算して更新することにより前記減衰値を求めてもよく、このようにすれば、前記部分減衰値の計算に必要なべき乗次数を、減衰値の計算に本来必要なべき乗計算の次数よりも小さくできるので、べき乗計算処理が削減され、更に高速処理が可能になるとともにその回路規模を縮小できる。
【００９６】
そして、時間間隔の経過を計測し、前記時間間隔毎の部分減衰値を予め記憶しておくとともに、計測された前記時間間隔の経過毎に対応する部分減衰値を出力すれば、前記時間間隔に対応する部分減衰値の計算が不要となるので、さらに、最終的なパケット転送までの時間を短縮することができる。
【００９７】
さらに、前記時間間隔として、部分減衰値が２のべき乗となるように時間間隔の設定を設定すれば、べき乗計算の替わりにシフト演算で減衰値の計算が行なえるので、回路規模の縮小が図れ、ひいては、コストの低減を図ることができるという利点がある。
また、前記アイドル時間を複数の一定時間間隔に分割したときの一定時間間隔に満たない時間間隔に対応する部分減衰値を求めれば、前記一定時間間隔に満たない時間間隔に対応する部分減衰値を求めて、この部分減衰値も前記一定間隔毎の部分減衰値と同様に減衰値に反映することができるので、より精度の高い平均キュー長を得ることができる。
【図面の簡単な説明】
【図１】本発明の第１実施形態に係るパケット転送装置としてのネットワーク中継装置の構成を示すブロック図である。
【図２】図１に示す平均キュー長計算装置の動作を説明するためのタイムチャートである。
【図３】図１に示す平均キュー長計算装置における減衰値計算部の構成を示すブロック図である。
【図４】図１に示すパケット転送装置の動作を説明するためのフローチャートである。
【図５】図１に示す平均平均キュー長計算装置の動作を説明するためのフローチャートであって、（ａ）は状態変化がパケット到着の場合の動作を説明するためのフローチャート、（ｂ）は状態変化がパケット到着以外の場合の動作を説明するためのフローチャートである。
【図６】図１に示す廃棄判定部による廃棄判定処理基準を説明するための図である。
【図７】図１及び図３に示す平均キュー長計算装置の第１変形例を示すブロック図である。
【図８】図１及び図３に示す平均キュー長計算装置の第２変形例を示すブロック図である。
【図９】図８に示す減衰値計算部を適用した場合の平均キュー長計算装置の動作を説明するためのシーケンス図である
【図１０】本発明の第１実施形態に係る平均キュー長計算装置の他の構成を示すブロック図である。
【図１１】従来のＲＥＤの方法によるアクティブキュー管理動作を説明するためのタイムチャートである。
【符号の説明】
１  平均キュー長計算装置（平均バッファ蓄積量計算装置）
２  バッファ（パケットバッファ）
３  書込（エンキュー）制御部
４  読出（デキュー）制御部
５  キュー長計測部
６  パケット到着通知部
７  減衰値計算制御部
８  平均キュー長計算部（平均蓄積量計算部）
９  平均キュー長記憶部（レジスタ）
１０  減衰値計算部（アイドル時間減衰値計算部）
１１  乗算器（平均キュー長更新部）
１２，３０  セレクタ
１３  廃棄判定部
１４  減衰値更新部
１４ａ  部分減衰値記憶レジスタ
１４ｂ，２３  乗算器
１５  部分減衰値計算部（部分減衰値生成部）
１６，２１  パラメータ記憶部
１７  べき乗計算部
１９，２０  時間計測部
１９ａ  計時時間監視部
１９ｂ，２０ａ  タイマー
１９ｃ  タイミング発生部
２０ｂ  時間記憶部
２２  減算器
２４  加算器
２５  一定時間間隔未満部分減衰値計算部
２７  部分減衰値記憶部
２８  シフト演算部
２９  シフト演算記憶部
５０  パケット転送装置
【図１】
0003769176.tif 000009
【図２】
0003769176.tif 000010
【図３】
0003769176.tif 000011
【図４】
0003769176.tif 000012
【図５】
0003769176.tif 000013
【図６】
0003769176.tif 000014
【図７】
0003769176.tif 000015
【図８】
0003769176.tif 000016
【図９】
0003769176.tif 000017
【図１０】
0003769176.tif 000018
【図１１】
0003769176.tif 000019