(57)【要約】統計情報を計数する複数の統計カウンタで構成された統計カウンタ装置１００に関し、統計カウンタのビット数を動的に制御することによりハード規模及び消費電力を削減するために、カウンタ管理部１３が、基礎カウンタ１０がフルカウント数又は該フルカウント数の一定範囲前になったとき予備カウンタ１１を基礎カウンタ１０の上位桁に動的にリンクして拡張カウンタ１２を構成し、拡張カウンタ１２がリセットされたとき、リンクを開放する。
2004112250.tif 000002
【特許請求の範囲】
【請求項１】
複数の基礎カウンタと、
複数の予備カウンタと、
各基礎カウンタが、フルカウント数又は該フルカウント数の一定範囲前になったとき該予備カウンタを各基礎カウンタの上位桁に動的にリンクして拡張カウンタを構成し、該拡張カウンタがリセットされたとき、該リンクを開放するカウンタ管理部と、
を備えたことを特徴とする統計カウンタ装置。
【請求項２】
請求の範囲１において、
該カウンタ管理部は、該拡張カウンタがフルカウント数又は該フルカウント数の一定範囲前になったとき、該予備カウンタを該拡張カウンタの上位桁にリンクした再拡張カウンタを構成することを特徴とした統計カウンタ装置。
【請求項３】
請求の範囲１又は２において、
全基礎カウンタと全予備カウンタとの合計ビット数が、所定の時間内に全基礎カウンタ及び拡張カウンタがカウントしたカウント数の合計を該基礎カウンタの数で割った値をカウントすることができるカウンタのビット数に該基礎カウンタ数を掛けた値以上で、該合計を１つのカウンタがカウントするに必要なビット数に該基礎カウンタの数を掛けた値より小さいことを特徴とした統計カウンタ装置。
【請求項４】
請求の範囲１において、
全基礎カウンタと全予備カウンタとの合計ビット数、及び基礎カウンタ及び予備カウンタの数が、ユーザパケットの帯域の分布状態に対応した値であることを特徴とした統計カウンタ装置。
【請求項５】
請求の範囲１において、
該カウンタ管理部が、該基礎カウンタ及び該予備カウンタのリンク状態を示すカウンタ管理メモリを備えたことを特徴とする統計カウンタ装置。
【請求項６】
請求の範囲５において、
該カウンタ管理部が、該カウンタ管理メモリで示されたリンク状態にある該基礎カウンタ及び該予備カウンタで構成された各拡張カウンタを示すカウンタ管理キャッシュメモリを備えたことを特徴とする統計カウンタ装置。
【請求項７】
請求の範囲１において、
該カウンタ管理部が、所定の周期で該基礎カウンタ及び該拡張カウンタをリセットすることを特徴とした統計カウンタ装置。
【請求項８】
請求の範囲７において、
該カウンタ管理部が、該リセット前に該基礎カウンタ及び該拡張カウンタの値を対応する外部カウンタに加算することを特徴とした統計カウンタ装置。
【請求項９】
請求の範囲１において、
全基礎カウンタと全予備カウンタとの合計ビット数、及び基礎カウンタ及び予備カウンタの数が、ユーザパケットの確率的な分布状態に対応した値であることを特徴とした統計カウンタ装置。
【請求項１０】
請求の範囲９において、
該カウンタ管理部が、リンクするための予備カウンタが不足したとき、該予備カウンタをリンクすることができなかった該基礎カウンタ又は該拡張カウンタをリセットすることを特徴とした統計カウンタ装置。
【請求項１１】
請求の範囲１０において、
該カウンタ管理部が、該リセット前に該基礎カウンタ又は該拡張カウンタの値を対応する外部カウンタに加算することを特徴とした統計カウンタ装置。
【発明の詳細な説明】
【技術分野】  本発明は統計カウンタ装置に関し、特に、統計情報を計数する複数の統計カウンタで構成された統計カウンタ装置に関するものである。
近年、通信技術の高速化及びその機器、例えば、携帯電話、及びインターネット等の普及に伴い、統計情報の種類と数、例えば、パケットの種類とその数はますます増大して来ている。このような統計情報に対応するためには、統計カウンタの数とそのビット数を大きくする必要がある。
【背景技術】  図１２は、ネットワーク４００に接続されたルータ（又はルータボード）２００ｚを示しており、このルータ２００ｚは、ルーティングチップ１１０ｚ、物理層インタフェース１５０＿１，１５０＿２、ＭＡＣ層インタフェース１４０＿１，１４０＿２、ＣＰＵ１３０、及びメモリ１２０を備えている。
ルーティングチップ１１０ｚは、３２ビットの統計カウンタ１０ｚ＿１〜１０ｚ＿６５５３６（以下、符号１０ｚで総称することがある。）を備え、メモリ１２０は、それぞれ、統計カウンタ１０ｚ＿１〜１０ｚ＿６５５３６に対応した、例えば４８ビットのパケットカウンタ１２１＿１〜１２１＿６５５３６（以下、符号１２１で総称することがある。）を備えている。
統計カウンタ１０ｚは、（１）送受信パケット計数用の統計カウンタ、（２）廃棄パケット計数用の統計カウンタ、又は（３）オクテットカウンタ用の統計カウンタである。
上記（１）の送受信パケット用の統計カウンタは、課金及び障害調査等に用いられ、（２）廃棄パケット用の統計カウンタは、障害調査等に用いられ、（３）オクテットカウンタは、帯域管理、課金及び障害調査等に用いられる。
上記（１）及び（２）のパケットをカウントする統計カウンタ１０ｚを例にして、統計カウンタ１０ｚに関連する動作を以下に説明する。ここで、統計カウンタ１０ｚのビット数は、一般的なデータ等のビット数と同様に３２ビットである。
ステップＴ５１：統計カウンタ装置１００ｚは、ネットワーク４００から、物理層インタフェース１５０＿１及びＭＡＣ層インタフェース１４０＿１を経由してパケットＰ１を受信する。統計カウンタ装置１００ｚにおいて、パケットＰ１に対応した統計カウンタ１０ｚ＿１は、対応するユーザからのパケットＰ１をカウントする。
この後、パケットＰ１は、ＭＡＣ層インタフェース１４０＿２及び物理層インタフェース１５０＿２を経由して、ネットワーク４００に送出される。
以後、同様に、ネットワーク４００の各ユーザからのパケットＰ２〜Ｐ６５５３６は、それぞれ対応する統計カウンタ１０ｚ＿２〜１０ｚ＿６５５３６でカウントされる。
ステップＴ５２，Ｔ５３：３２ビットの統計カウンタ１０ｚ＿１は、“２３２−１”（≒４，０００，０００，０００）個以上のパケットＰ１をカウントすることはできない。そこで、ＣＰＵ１３０は、例えば、統計カウンタ１０ｚ＿１の全ビット＝ａｌｌ“１”になる前に、統計カウンタ１０ｚ＿１の値を読み出し、メモリ１２０のパケットカウンタ１２１＿１に加算し、統計カウンタ１０ｚ＿１を“０”にリセットする。
同様に、ＣＰＵ１３０は、それぞれ、統計カウンタ１０ｚ＿２〜１０ｚ＿６５５３６の全ビット＝ａｌｌ“１”になる前に、統計カウンタ１０ｚ＿２〜１０ｚ＿６５５３６の値を読み出し、パケットカウンタ１２１＿２〜１２１＿６５５３６に加算し、統計カウンタ１０ｚ＿２〜１０ｚ＿６５５３６を“０”にリセットする。
これにより、例えば、パケットＰ１をカウントすることができる個数は、パケットカウンタ１２１＿１のビット数によるフルカウント値まで可能になる。例えばパケットカウンタ１２１＿１のビット数＝“４８”であれば、“２４８−１”までカウントできる。
例えば、インターネット・データ・センタ（Ｉｎｔｅｒｎｅｔ  Ｄａｔａ  Ｃｅｎｔｅｒ以下、ＩＤＣと称する。）のように多くの通信回線をルータ２００ｚが持っている場合、ユーザ毎のカウント処理が必要であり、カウンタ数が増大する。また、通信回線速度の高速化（１０Ｍｂｐｓ→１００Ｍｂｐｓ→１Ｇｂｐｓ→１０Ｇｂｐｓ）によって、単位時間当たりのパケット流量は増大し、これをカウントするカウンタのビット数も大きくする必要がある。
例えば、通信回線帯域が１０Ｇｂｐｓの場合、１秒当たりのパケット流量は約１５Ｍｐｐｓ（１パケット＝６４バイトのとき）となる。ここで、ＣＰＵ１３０のアクセス周期が４分程度必要であるとすれば、４分間の統計カウンタ１０ｚのカウント数＝１５Ｍｐｐｓ＊４＊６０≒３．６Ｇ＜２３２、したがって、各統計カウンタ１０ｚの必要ビット数＝３２ビットになる。
この結果、ハード規模及び消費電力の増大が重要な問題になっている。
統計カウンタ装置１００ｚを構成するチップの最大容量は、０．１１μｍプロセスの１４ｍｍ□チップで約１７ＭＢＣ（Ｂａｓｉｃ  Ｃｅｌｌ）である。カウンタ規模は、３２ビットカウンタで１．４ｋＢＣ、３６ビットカウンタで３．５ｋＢＣ程度である。
例えば、統計カウンタがユーザに対して１種類のパケットだけであっても１０００ユーザ分をカウントする場合、チップ全体に占める統計カウンタの割合は、３２ビットカウンタで８％（≒（１．４ｋ×１０００／１７Ｍ）×１００）程度になり、チップ全体における統計カウンタの規模が無視できない大きさになっている。また、チップ全体に占める統計カウンタの消費電力も、統計カウンタ規模と同程度の割合になる。
２つのカウンタ（例えば、Ｘ，Ｙ方向のアドレスをそれぞれ計数するＸ／Ｙアドレスカウンタ）の合計ビット数を小さくするカウンタ例として、第１計数手段（下位桁側）、ｎ（ｎは正の整数）個の第２計数手段、及び第３計数手段（上位桁側）を縦接続して１つのカウンタを構成するものがある（例えば、特許文献１）。
そして、このカウンタは、２つのカウンタに分断され、Ｘアドレスカウンタ及びＹアドレスカウンタとされる。すなわち、Ｘアドレスカウンタを、第１計数手段及び０〜ｉ（ｉ≦ｎ）個の下位桁側の第２計数手段で構成し、Ｙアドレスカウンタを残り上位桁側の第２計数手段及び第３計数手段で構成することで、Ｘアドレスカウンタ及びＹアドレスカウンタのビット数を可変にしてハード規模を小さくしている。
この方式では、第１の計数回路は、固定ビット長のカウンタを用いているため、このビット長より少ないビット長でよいユーザが使用する場合、ハードウェアに無駄が生じるという欠点があった。
この欠点を改良する計数回路（カウンタ）として、前段のカウンタのキャリー出力又は予め定めた電圧レベルとのいずれかの一方をキャリー入力として有効にするよう指定するスタートビット選択信号及びカウント動作許可・禁止を指定するカウントイネーブル信号の各々の供給に応答して計算動作を行い所定の計数結果を出力するとともにキャリー出力を後段に出力することにより縦続接続される所定数の単位カウンタと、前記スタートビット選択信号及びカウンタイネーブル信号を一時保持し前記単位カウンタの各々にそれぞれ前記スタートビット選択信号及び前記カウントイネーブル信号を出力する前記所定数のレジスタとを備えたことを特徴とする計数回路がある（例えば、特許文献２）。
この計数回路は、任意ビット長の独立した複数のカウンタに分割することができるので、ユーザ要求に柔軟に対応してハードウェア資源を効率的に利用できる。
しかしながら、上記の２方式では、各カウンタのビット数を予め指定する必要があり、カウント動作中に最適なビット数を自動的に指定することは出来ない。
【特許文献１】      特開平４−２２７５８２号
【特許文献２】      特開平８−２３７１１２号
従って本発明は、統計情報を計数する複数の統計カウンタで構成された統計カウンタ装置において、該統計カウンタのビット数を動的に制御することによりハード規模及び消費電力を削減することを課題とする。
【発明の開示】
上記の課題を解決するため、本発明の統計カウンタ装置は、複数の基礎カウンタと、複数の予備カウンタと、各基礎カウンタが、フルカウント数又は該フルカウント数の一定範囲前になったとき該予備カウンタを各基礎カウンタの上位桁に動的にリンクして拡張カウンタを構成し、該拡張カウンタがリセットされたとき、該リンクを開放するカウンタ管理部とを備えたことを特徴としている。
図１は、本発明の統計カウンタ装置の原理を示している。同図（１）は、従来のビット数固定の３２ビットの統計カウンタ１０ｚを示しており、この統計カウンタ１０ｚは、従来の統計カウンタ１０ｚ＿１〜１０ｚ＿１０２４で構成されており、１０２４（＝２１０）のユーザに対応している。統計カウンタ装置１００ｚ（図１２参照。）は、例えば統計カウンタ１０ｚ＿１に対応する同一ユーザ宛パケットが回線の全帯域（１０Ｇｂｐｓ）を占有している場合、他のカウンタ１０ｚ＿２〜１０ｚ＿１０２４は必要でなく無駄である。すなわち、統計カウンタ装置１００ｚが必要とするカウンタのビット数は、３２ビットのみでよい。
同図１（２）は、本発明の統計カウンタ装置１００（図４参照。）が、１０２４（＝２１０）のユーザ宛のパケットを、同時に同じ数だけ分散して受信した場合（すなわち、全帯域（１０Ｇｂｐｓ）を１０Ｇｂｐｓ／１０２４≒１０Ｍｂｐｓに分散して受信した場合）を示しており、各基礎カウンタ１０＿１〜１０＿１０２４がカウントするパケット数は、２２２（＝２３２／１０２４＝２３２−１０）である。すなわち、統計カウンタ装置１００が必要とするビット数は、カウンタ１０＿１ａ〜１０＿１０２４ａの部分の２２×１０２４ビットである。網掛け部分のカウンタ１０＿１ｂ〜１０＿１０２４ｂの部分は余っている。
例えば、カウンタ１０＿１が２２２個以上のパケットをカウントしなければならない場合、他の、例えばカウンタ１０＿２が、カウンタ１０＿１の２２ビット以上のパケット分だけ少なくカウントしている筈であるから、ビット数が余っている。そこで、この余ったビット数を、カウンタ１０＿１の上位桁に接続（リンク）すればよい。
図２は、図１において、ユーザ数（カウンタ数）が６５５３６（＝２１６）の場合を示しており、図２（１）は、図１（１）と同様である。図２（２）は、統計カウンタ装置１００が、６５５３６（＝２１６）のユーザ宛のパケットを、同じ数だけ受信した場合を示しており、各基礎カウンタ１０＿１〜１０＿６５５３６がカウントするパケット数は、２１６（＝２３２／２１６）である。すなわち、統計カウンタ装置１００が必要とするカウンタのビット数は、１６×６５５３６ビットである。
図１（２）と同様に、例えば、カウンタ１０＿１が２１６個以上のパケットをカウントしなければならない場合、他の例えばカウンタ１０＿２が、カウンタ１０＿１の１６ビット以上のパケット分だけ少なくカウントしている筈であるから、ビット数が余っている。そこで、この余ったビット数を、カウンタ１０＿１に上位桁にリンクすればよい。
本発明の統計カウンタ装置１００は、複数の基礎カウンタ１０と、複数の予備カウンタ１１と、カウンタ管理部１３とで構成する。
図３（１）及び（２）は、それぞれ、本発明の統計カウンタ装置１００における基礎カウンタ１０及び予備カウンタ１１を例示しており、それぞれ、８ビットの基礎カウンタ１０＿１〜１０＿６５５３６（以下、符号１０で総称することがある。）、及び４ビットの予備カウンタ１１＿１〜１１＿１３１０７２（以下、符号１１で総称することがある。）で構成されており、６５５３６のユーザに対応している。
予備カウンタ１１の各ビット数と予備カウンタ１１の数は、基礎カウンタ１０の上位桁にリンクして所定のビット数（カウント数）に拡張することが可能なように決定する。
同図（３）は、基礎カウンタ１０に予備カウンタ１１をリンクして拡張カウンタ１２を構成した例を示している。
各基礎カウンタ１０は、例えば、ユーザに対応したパケットをカウントしている。カウンタ管理部１３（図３には図示せず。）は、例えば、基礎カウンタ１０＿２がフルカウント数になったとき、すなわち、基礎カウンタ１０＿２の各ビット＝“ａｌｌ  １”になったとき、又はフルカウント数の一定範囲前に、使用されていない予備カウンタ１１＿４を基礎カウンタ１０＿２の上位桁にリンクした拡張カウンタ１２＿２を構成する。
また、カウンタ管理部１３は、拡張カウンタ１２＿２が、リセットされるとき、例えば、ＣＰＵ１３０によってメモリ１２０上の別のパケットカウンタ１２１＿２に読み込まれてリセットされたとき（図１２参照。）、予備カウンタ１１＿４を拡張カウンタ１２＿２から切り離し基礎カウンタ１０＿２のみとする。この切り離された予備カウンタ１１＿４は、他の基礎カウンタ１０のビット数を拡張するために待機する。
なお、以下、図３（３）に示した基礎カウンタ１０＿６５５３６のように、予備カウンタ１１がリンクされていない（０個付加された）場合においても、拡張カウンタ１２＿６５５３６と称する。
このように構成した拡張カウンタ１２によって次のような効果が発生する。すなわち、図１（２）及び図２（２）に示したように、必要とする全基礎カウンタ１０のビット数と全予備カウンタ１１のビット数との合計が、従来の全統計カウンタ１０ｚのビット数との合計より少なくすることが可能になり、ハード規模及び消費電力を削減することが可能になる。
また、上記の本発明において、該カウンタ管理部は、該拡張カウンタがフルカウント数又は該フルカウント数の一定範囲前になったとき、該予備カウンタを該拡張カウンタの上位桁にリンクした再拡張カウンタを構成することができる。
すなわち、図３（３）において、例えば、基礎カウンタ１０＿１と予備カウンタ１１＿１で構成された拡張カウンタ１２の上位桁に、さらに、予備カウンタ１１＿２をリンクした再拡張カウンタ１２を構成することができる。さらに、この再拡張カウンタ１２に予備カウンタ１１＿３をリンクして拡張カウンタ１２＿１とすることを繰り返すことが可能である。
これにより、拡張カウンタ１２のビット数を、必要なビット数にすることが可能になるとともに、予備カウンタ１１のビット数を小さくすれば、拡張カウンタ１２のビット数を細かく設定することが可能になる。
また、上記の本発明において、全基礎カウンタと全予備カウンタとの合計ビット数を、所定の時間内に全基礎カウンタ及び拡張カウンタがカウントしたカウント数の合計を該基礎カウンタの数で割った値をカウントすることができるカウンタのビット数に該基礎カウンタ数を掛けた値以上で、該合計を１つのカウンタがカウントするに必要なビット数に該基礎カウンタの数を掛けた値より小さくすることができる。
これにより、所定の時間内に全拡張カウンタが、同じカウント数になる場合、すなわち、全拡張カウンタのビット数の合計が最大になる最悪の場合に対応するだけのビット数のカウンタを確保することが可能になる。
なお、基礎カウンタ及び予備カウンタのビット数によって、必要なビット数は異なる。例えば、基礎カウンタ及び予備カウンタビット数が共に１である場合、拡張カウンタのビット数を細かく設定することが可能となり、全必要ビット数は最小になる。
また、上記の本発明において、全基礎カウンタと全予備カウンタとの合計ビット数、及び基礎カウンタ及び予備カウンタの数を、ユーザパケットの帯域の分布状態に対応した値とすることが可能である。
例えば、ユーザパケットの帯域が異なる場合、各ユーザに対応した必要な基礎／拡張カウンタのビット数は異なる。帯域の大きなユーザの拡張カウンタが重みの大きなビットを上位桁に使用するため、他の帯域の小さなユーザの拡張カウンタの必要ビット数は少なくなる。したがって、全基礎カウンタと全予備カウンタとの合計ビット数を、図１及び２で述べた最悪の場合より少なくすることが可能である。
また、上記の本発明において、該カウンタ管理部は、該基礎カウンタ及び該予備カウンタのリンク状態を示すカウンタ管理メモリを備えることができる。
これにより、該カウンタ管理部が、各ユーザに対応した基礎カウンタ又は拡張カウンタの構成を認識することが可能になる。
また、上記の本発明において、該カウンタ管理部は、該カウンタ管理メモリで示されたリンク状態にある該基礎カウンタ及び該予備カウンタで構成された各拡張カウンタを示すカウンタ管理キャッシュメモリを備えることができる。
すなわち、カウンタ管理キャッシュメモリは、各拡張カウンタを構成する基礎カウンタ及び予備カウンタを示す。
これにより、該カウンタ管理部は、カウンタ管理キャッシュメモリに基づき拡張カウンタのカウント動作を高速で行うことが可能になる。
また、上記の本発明において、該カウンタ管理部が、所定の周期で該基礎カウンタ及び該拡張カウンタをリセットしてもよい。
また、上記の本発明において、該カウンタ管理部は、該リセット前に該基礎カウンタ及び該拡張カウンタの値を対応する外部カウンタに加算することができる。
また、上記の本発明において、全基礎カウンタと全予備カウンタとの合計ビット数、及び基礎カウンタ及び予備カウンタの数を、ユーザパケットの確率的な分布状態に対応した値とすることが可能である。
すなわち、ユーザパケットのカウント数は、ユーザ数が多くなればなるほど、同時に同一数になる確率は小さい。従って、全基礎カウンタと全予備カウンタの合計ビット数は、上記の図１（２）及び図２（２）に場合と比較して、さらに小さくすることが可能である。
また、上記の本発明において、該カウンタ管理部は、リンクするための予備カウンタが不足したとき、該予備カウンタをリンクすることができなかった該基礎カウンタ又は該拡張カウンタをリセットしてもよい。
さらに、上記の本発明において、該カウンタ管理部は、該リセット前に該基礎カウンタ又は該拡張カウンタの値を対応する外部カウンタに加算してもよい。
例えば、一定周期で基礎カウンタ及び拡張カウンタのカウント値を外部カウンタに加算している場合、確率的な分布状態に対応した値で、全基礎カウンタ及び全予備カウンタのビット数等を決定した場合、予備カウンタが不足する可能性がある。予備カウンタが不足したとき、拡張できなかった基礎カウンタ又は拡張カウンタのカウント値を対応する外部カウンタに加算することで、カウント誤りを無くすことが可能である。
【図面の簡単な説明】  図１は、本発明に係る統計カウンタ装置の原理を示したブロック図（１）である。
図２は、本発明に係る統計カウンタ装置の原理を示したブロック図（２）である。
図３は、本発明に係る統計カウンタ装置の原理に基づく基礎カウンタ及び予備カウンタへのビット数の分配例を示したブロック図である。
図４は、本発明に係る統計カウンタ装置の実施例（１）を示したブロック図である。
図５は、本発明に係る統計カウンタ装置を備えたルータを用いたネットワーク例を示したブロック図である。
図６は、本発明に係る統計カウンタ装置におけるカウンタ管理キャッシュメモリ例及びカウンタ管理メモリ例を示した図である。
図７は、本発明に係る統計カウンタ装置の動作手順例（１）を示した図である。
図８は、本発明に係る統計カウンタ装置の動作手順例（１）におけるカウンタ管理キャッシュメモリ及びカウンタ管理メモリを示した図である。
図９は、本発明に係る統計カウンタ装置の動作手順例（２）を示した図である。
図１０は、本発明に係る統計カウンタ装置の動作手順例（２）におけるカウンタ管理キャッシュメモリ及びカウンタ管理メモリを示した図である。
図１１は、本発明に係る統計カウンタ装置の実施例（２）におけるカウンタ管理キャッシュメモリ例及びカウンタ管理メモリ例を示した図である。
図１２は、従来の統計カウンタ装置を用いたルータ例を示したブロック図である。
【符号の説明】
2004112250.tif 000003
2004112250.tif 000004
図中、同一符号は同一又は相当部分を示す。
【発明を実施するための最良の形態】  図４は、本発明に係る統計カウンタ装置１００の実施例（１）を示しており、この統計カウンタ装置１００は、カウンタ管理部１３、基礎カウンタ１０及び予備カウンタ１１で構成されている。統計カウンタ装置１００はＬＳＩで構成することができる。
カウンタ管理部１３は、カウンタ管理キャッシュメモリ１４とカウンタ管理メモリ１５を備えている。基礎カウンタ１０は、８ビットの基礎カウンタ１０＿１〜１０＿６５５３６（以下、符号１０で総称することがある。）で構成され、予備カウンタ１１は、４ビットの予備カウンタ１１＿１〜１１＿１９６６０８（６５５３６×３）（以下、符号１１で総称することがある。）で構成されている。
カウンタ管理部１３は、１つの８ビット基礎カウンタ１０に最大６つの４ビット予備カウンタ１１を接続して、最大３２ビットの拡張カウンタ１２を構成することができる。
なお、ユーザ数＝６５５３６の場合、統計カウンタ装置１００が必要とする全カウンタのビット数は、拡張カウンタ１２を１ビット毎に構成することが可能であれば、全基礎カウンタ１０及び全予備カウンタ１１の合計ビット数＝“１６×６５５３６”でよいが、予備カウンタ１１のリンク及びリンクの切断の回数は多くなる。
そこで、本実施例（１）では、８ビットの基礎カウンタ１０及び４ビットの予備カウンタ１１を用いてリンク及びその切断の回数を少なくし、その代わりの予備カウンタ１１の数を６５５３６個だけ増やして、全基礎カウンタ１０及び全予備カウンタ１１の合計ビット数＝“２０×６５５３６”としている。
図５は、本発明に係る統計カウンタ装置１００を備えたルータ２００を示している。ルータ２００は、サーバ２１０＿１〜２１０＿３、及びサーバ記憶部２２０＿１〜２２０＿３と共に、ＩＤＣ３００を構成している。また、ルータ２００は、ネットワーク４００に接続されており、このネットワーク４００からパケットＰ１，Ｐ２，…，Ｐ６５５３６を受信する。
図６は、図４に示したカウンタ管理キャッシュメモリ１４及びカウンタ管理メモリ１５をより詳細に示している。
図６（２）は、カウンタ管理メモリ１５の初期状態構成例を示しており、基礎カウンタ１０＿１〜１０＿６５５３６にそれぞれ対応する１９ビットのメモリフィールド１５＿１ａ〜１５＿６５５３６ａ（以下、符号１５＿ｉで総称することがある。）と、予備カウンタ１１＿１〜１１＿１９６６０８に対応する１９ビットのメモリフィールド１５＿１ｂ〜１５＿１ｄ，…，１５＿６５５３６ｂ〜１５＿６５５３６ｄ（同様に、以下、符号１５＿ｉで総称することがある。）で構成されている。
なお、図４で述べたように、この実施例（１）では、基礎カウンタ１０及び予備カウンタ１１のビット数をそれぞれ８ビット及び４ビットとしているため、拡張カウンタ１２のビット数を１ビット毎に設定することができない。従って、基礎カウンタ１０及び予備カウンタ１１の平均ビット数は、図２で示したワーストケースで必要なビット数＝１６ビットより大きいビット数＝“２０（＝８＋４×３）”を用いている。
メモリフィールド１５＿ｉは、１８ビットのポインタ１５＿ｉ＿ｐと１ビットのフラグ１５＿ｉ＿ｆとの合計“１９”ビットで構成されている。カウンタ管理メモリ１５のメモリフィールド１５＿１ａ〜１５＿１ｄの上には、メモリフィールド１５＿１ａ〜１５＿１ｄにそれぞれ対応するビット０〜１８，１９〜３７，３８〜５６，５７〜７５が示されている。
例えば、メモリフィールド１５＿１ａのフラグ１５＿１ａ＿ｆは、基礎カウンタ１０＿１の最上位桁に予備カウンタ１１＿１がリンクされているか否かを示している。この例では、フラグ１５＿１ａ＿ｆ＝“０”が、「リンクされている」ことを意味し、フラグ１５＿１ａ＿ｐ＝“１”が、「リンクされていない」ことを意味する。
例えば、ポインタ１５＿１ａ＿ｐは、基礎カウンタ１０＿１に接続（リンク）される予備カウンタ１１＿１に対応するメモリフィールド１５＿１ｂのアドレス＝“０ｘ１”を指し示している。
図では、ポインタとフラグとを合わせて“０ｘ１：０”として示している。
同様に、メモリフィールド１５＿ｉｂ〜１５＿ｉｄのフラグ１５＿ｉｂ＿ｆ〜１５＿ｉｄ＿ｆは、予備カウンタ１１の最上位桁にさらに予備カウンタ１１がリンクされている否かを示し、ポインタ１５＿ｉｂ＿ｐ〜１５＿ｉｄ＿ｐは、リンクされる次の予備カウンタ１１に対応するメモリフィールド１５＿ｉのアドレスを指し示している。予備カウンタ１１がリンクされていない場合は、ポインタ１５＿ｉｂ＿ｐ〜１５＿ｉｄ＿ｐには、「未使用」を示す所定のコードが設定される。
図６（１）は、カウンタ管理キャッシュメモリ１４の構成を示している。このメモリ１４は、各拡張カウンタ１２＿１〜１２＿６５５３６（＝１６４、以下、符号１２で総称することがある。）が、どこの基礎カウンタ１０と予備カウンタ１１とで構成されているかの初期状態を示している。
すなわち、メモリ１４は、拡張カウンタ１２＿１〜１２＿６５５３６の基礎カウンタ１０に対応する１８ビットのメモリフィールド１４＿１ａ〜１４＿６５５３６ａ（以下、符号１４＿ｉで総称することがある。）と、予備カウンタ１１に対応する１８ビットのメモリフィールド１４＿１ｂ〜１４＿１ｇ，…，１４＿６５５３６ｂ〜１４＿６５５３６ｇ（同様に以下、符号１４＿ｉで総称することがある。）とで構成されている。したがって、拡張カウンタ１２の最大ビット数＝“３２”（＝“８＋４×６”）である。
カウンタ管理キャッシュメモリ１４のメモリフィールド１４＿１ａ〜１４＿１ｇの上には、メモリフィールド１４＿１ａ〜１４＿１ｇにそれぞれ対応するビット０〜１７，１８〜３５，３６〜５３，５４〜７１，７２〜８９，９０〜１０７，１０８〜１２４が示されている。
例えば、拡張カウンタ１２＿１のメモリフィールド１４＿１ａ，１４＿１ｂには、それぞれ、同図（２）のカウンタ管理メモリ１５のアドレス＝“０ｘ０”，“０ｘ１”が設定され、基礎カウンタ１０＿１とこれにリンクされて拡張カウンタ１２＿１を構成する予備カウンタ１１＿１を示している。
予備カウンタ１１がリンクされていないメモリフィールド１４＿１ｃ〜１４＿１ｇには、“未使用”を示す所定のコードが設定される。
なお、予備カウンタ１１がリンクされていない基礎カウンタ１０のみの場合も、拡張カウンタ１２と称する。
カウンタ管理部１３は、カウンタ管理キャッシュメモリ１４に基づき基礎カウンタ１０、予備カウンタ１１、及び拡張カウンタ１２を管理する。
同図（３）は、同図（２）に示したリンク状態を示しており、全ての基礎カウンタ１０＿１〜１０＿６５５３６に１つ予備カウンタ１１がリンクされている場合を示している。例えば、拡張カウンタ１２＿１は、アドレス０ｘ０に対応する基礎カウンタ１０＿１と、アドレス０ｘ１に対応する予備カウンタ１１＿１で構成されていることを示している。
同図（４）は、カウンタ管理メモリ１５上に設定された空きメモリ空間を示しており、この空きメモリ空間には、基礎カウンタ１０＿１〜１０＿６５５３６及び拡張カウンタ１２＿１〜１２＿６５５３６（以下、拡張カウンタと総称することがある。）のいずれにもリンクされていない予備カウンタ１１がリンクされている。
空きメモリ空間のリンクの最下位端と最上位端のアドレスは、ポインタ（図示せず。）で示され、拡張カウンタ１２が予備カウンタ１１を必要とするときは、最上位端にある予備カウンタ１１を「未使用：１」として空きメモリ空間から切り離して使用し、拡張カウンタ１２が予備カウンタ１１を必要としなくなり切り離したときは、この切り離した予備カウンタ１１を空きメモリ空間の最下位端にリンクしておく。
これにより、拡張カウンタ１２に予備カウンタ１１を接続することや、切り離すことが容易になる。
なお、同図の実施例では、基礎カウンタ１０及び予備カウンタ１１のビット数を、それぞれ、８ビット及び４ビットとしたが、このビット数は、予め、必要とする統計カウンタ（拡張カウンタ）の特性に合わせた値とすることができる。これに伴って、基礎カウンタ１０に接続する予備カウンタ１１の数が決定される。
図７（１）及び（２）は、拡張カウンタ１２のビット数を制御する動作手順例（１）を示しており、この動作手順例（１）では、特に、拡張カウンタ１２に予備カウンタ１１を接続する手順を示している。この手順を以下に説明する。なお、この手順では、１つのユーザに対応するパケットＰ１のみに注目して説明する。複数のユーザに対応するパケットＰ１〜Ｐ６５５３６を処理する場合は、この手順の前にパケットを選択する処理ステップを挿入すればよい。
ステップＳ１０，Ｓ１１：同図（１）において、カウンタ管理部１３は、入力パケットＰ１を待ち、パケットＰ１を受信したとき、拡張カウンタ１２の値をチェックする。
ステップＳ１２：拡張カウンタ１２の全ビット＝ａｌｌ“１（フルカウント数）”である場合、ステップＳ１３に進み、全ビット＝ａｌｌ“１”でない場合、ステップＳ１４に進む。なお、このステップＳ１２における判定は、「全ビット＝ａｌｌ“１”である場合」の代わりに、拡張カウンタが「フルカウント数の一定範囲前になった場合」としてもよい。
ステップＳ１３，Ｓ１４：空きメモリ空間から切り離した予備カウンタ１１を拡張カウンタ１２にリンクした後、拡張カウンタ１２を１だけカウントアップする。
同図（２）は、カウンタ管理部１３が、カウンタ管理メモリ１５に基づき、拡張カウンタ１２に予備カウンタ１１を接続する手順を示している。
ステップＴ１１：カウンタ管理部１３は、拡張カウンタ１２の全ビット＝ａｌｌ“１”になった場合、拡張カウンタ１２に対応するメモリフィールド１５＿１ａのリンク状態を検索し、メモリフィールド１５＿１ａに対応する基礎カウンタ１０＿１とメモリフィールド１５＿１ｂに対応する予備カウンタ１１＿１とがリンクしていることを認識する。
ステップＴ１２，Ｔ１３：そこで、カウンタ管理部１３は、空きメモリ空間の最上位を示すポインタ（図示せず。）を参照して、空きメモリ空間（空き予備カウンタ１１、同図（３）参照。）の最上位にリンクされたアドレス＝“０ｘ２”のメモリフィールド１５＿１ｃをアドレス＝“０ｘ１”のメモリフィールド１５＿１ｂにリンクする。すなわち、カウンタ管理部１３は、ポインタ１５＿１ｂ＿ｐ＝“０ｘ２”、フラグ１５＿１ｂ＿ｆ＝“０”にし、ポインタ１５＿１ｃ＿ｐ＝“未使用”、フラグ１５＿１ｃ＿ｆ＝“１”にする。
ステップＳ１４：拡張カウンタ１２を“１”だけインクリメントする。
これにより、拡張カウンタ１２が、フルカウント状態である場合、拡張カウンタ１２の最上位桁に予備カウンタ１１をリンクすることが可能になり、拡張カウンタ１２がオーバフローしなくなる。
なお、ステップＳ１２における判定を、カウンタがフルカウント数（全ビット＝ａｌｌ“１”）になる場合の代わりに、フルカウント数の一定範囲前にしてもよい。
図８は、図７で示した動作手順例（１）によって変更されたカウンタ管理キャッシュメモリ１４及びカウンタ管理メモリ１５を示している。
図８（１）は、拡張カウンタ１２＿１に、さらに、アドレス０ｘ２に対応する予備カウンタ１１＿２をリンクした場合のカウンタ管理キャッシュメモリ１４を示している。メモリフィールド１４＿１ｃには、予備カウンタ１１＿２に対応するカウンタ管理メモリ１５のメモリフィールド１５＿１ｃのアドレス＝“０ｘ２”が設定されている。
図８（２）は、リンクされた基礎カウンタ１０＿１及び予備カウンタ１１＿１に、さらに、アドレス０ｘ２に対応する予備カウンタ１１＿２をリンクした場合のカウンタ管理メモリ１５を示している。メモリフィールド１５＿１ｂには、予備カウンタ１１＿２に対応するメモリフィールド１５＿１ｃのアドレス＝“０ｘ２”及びフラグ＝“０”が設定され（“０ｘ２”：“０”）、メモリフィールド１５＿１ｃには、“未使用”及びフラグ＝“１”が設定されている（“未使用”：“１”）。
このように、カウンタ管理キャッシュメモリ１４は、カウンタ管理メモリ１５で管理された結果を次のカウンタ管理メモリ１５の更新までの間キャッシュしておくメモリであり、拡張カウンタのカウント性能（高速動作）を確保するために必要である。
図９は、拡張カウンタ１２のビット数を制御する動作手順例（２）を示しており、この動作手順例（２）は、特に、拡張カウンタ１２から予備カウンタ１１を切り離す手順を示している。この手順例（２）を以下に説明する。なお、手順例（２）では、図７に示した動作手順例（１）と同様に、１つのユーザに対応するパケットＰ１のみに注目して説明する。
ステップＳ２１，Ｓ２２：同図（１）において、カウンタ管理部１３は、例えば、ＣＰＵ１３０（図１２参照。）からのカウンタ値の読み込みがあった場合、拡張カウンタ１２から全ての予備カウンタ１１を切り離して、基礎カウンタ１０のみとし、基礎カウンタ１０（拡張カウンタ１２）の値＝“０”にリセットする。
同図（２）は、カウンタ管理部１３が、カウンタ管理メモリ１５に基づき、拡張カウンタ１２＿１から予備カウンタ１１＿２を切り離す動作手順例を示している。
ステップＴ２１：カウンタ管理部１３は、基礎カウンタ１０＿１に対応するカウンタ管理メモリ１５上のリンク（メモリフィールド１５＿１ａを始点するリンク）を検索し、このリンクの最終端のメモリフィールド１５＿１ｃ（フラグ１５＿１ｃ＿ｆ＝“１”）を認識する。
ステップＴ２２：そして、カウンタ管理部１３は、メモリフィールド１５＿１ｃの１つ前にリンクされたメモリフィールド１５＿１ｂのポインタ１５＿１ｂ＿ｐ＝“未使用”及びフラグ１５＿１ｂ＿ｆ＝“１”に設定して、メモリフィールド１５＿１ｃをリンクから切り離すとともに、このメモリフィールド１５＿１ｃを空きメモリ空間リンクの最下位に戻す（同図（３）参照。）。すなわち、メモリフィールド１５＿６５５３６ｄのポインタ１５＿６５５３６ｄ＿ｐ＝“０ｘ２”、及び１５＿６５５３６ｄ＿ｆ＝“０”に設定する。
ステップＴ２３：カウンタ管理部１３は、メモリフィールド１５＿１ａ，１５＿１ｂに対応する基礎カウンタ１０＿１，予備カウンタ１１＿１の値＝“０”にリセットする。
なお、この例では、基礎カウンタ１０＿１及び予備カウンタ１１＿１で構成された拡張カウンタ１２＿１を最小ビット数の基礎カウンタ１０としている場合を示している。
これにより、ＣＰＵ１３０が、拡張カウンタ１２の値を読み出した場合、拡張カウンタ１２から予備カウンタ１１を分離して、基礎カウンタ１０のみとすることが可能になり、カウンタのビット数を少なくすることが可能になる。
図１０は、図９で示した動作手順例（２）によって、拡張カウンタ１２＿１からアドレス０ｘ２に対応する予備カウンタ１１＿２を切り離した場合のカウンタ管理キャッシュメモリ１４及びカウンタ管理メモリ１５を示している。
同図（１）は、カウンタ管理キャッシュメモリ１４を示しており、このメモリフィールド１４＿１ｃは、図８（１）に示したメモリフィールド１４＿１ｃ＝“０ｘ２”から“未使用”に変更されている。
同図（２）は、カウンタ管理メモリ１５を示しており、このメモリ１５のメモリフィールド１５＿１ｂのポインタ１５＿１ｂ＿ｐ及びフラグ１５＿１ｂ＿ｆは、図８（２）に示したポインタ１５＿１ｃ＿ｐ＝“０ｘ２”及びフラグ１５＿１ｃ＿ｆ＝“０”から、それぞれ“未使用”及び“１”に変更されている。
また、このメモリフィールド１５＿６５５３６ｄのポインタ１５＿６５５３６ｄ＿ｐ及びフラグ１５＿６５５３６ｄ＿ｆは、それぞれ、図８（２）に示したポインタ１５＿１ｃ＿ｐ＝“未使用”及びフラグ１５＿１ｃ＿ｆ＝“１”から、“０ｘ２”及び“０”に変更され、メモリフィールド１５＿１ｃをリンクしている。
また、メモリフィールド１５＿１ｃのポインタ１５＿１ｃ＿ｐ及びフラグ１５＿１ｃ＿ｆは、それぞれ“未使用”及び“１”のままで空き空間メモリにリンクされている。
図１１は、本発明の統計カウンタ装置１００の実施例（２）を示しており、この実施例（２）では、必要とする拡張カウンタ数が１０２４の場合を示している。統計カウンタ装置１００は、拡張カウンタ１２＿１〜１２＿１０２４（以下、符号１２で総称することがある。）に対応する１０２４個の８ビットの基礎カウンタ１０＿１〜１０＿１０２４と、１０２４個の８ビットの予備カウンタ１１及び２０４８個の６ビットの予備カウンタ１１を備えている。
同図（１）は、カウンタ管理キャッシュメモリ１４の構成例を示している。８ビットの基礎カウンタ１０と８ビットの予備カウンタ１１で１６ビットの拡張カウンタ１２を構成し、この拡張カウンタ１２に１つ以上の６ビットの予備カウンタ１１をリンクすることにより、２２ビット、２８ビット、３４ビットの拡張カウンタ１２を構成する。カウンタ管理キャッシュメモリ１４のメモリフィールド１４＿１ａ〜１４＿１ｅ，…，１４＿１０２４ａ〜１４＿１０２４ｅのビット数＝“１２”であり、上記の基礎カウンタ１０及び予備カウンタ１１の合計数４０９６（＝２１２）個に対応するアドレスを指定する。
図１１（２）は、カウンタ管理メモリ１５の構成例を示している。この例では、拡張カウンタ１２のリンク状態及び空きメモリ空間（６ビットの予備カウンタ）のリンク状態を示している。
カウンタ管理メモリ１５のメモリフィールド１５＿１ａ〜１５＿１ｄ，…，１５＿１０２４ａ〜１５＿１０２４ｄのビット数＝“１３”である。メモリフィールド１５＿１ａのポインタ１５＿１ａ＿ｐのビット数＝“１２”及びフラグ１５＿１ａ＿ｆのビット数＝“１”である。
このように、基礎カウンタ１０や予備カウンタ１１のビット数は、カウントする情報の特性に対応して変更することが可能である。
以上説明したように、本発明に係る統計カウンタ装置によれば、カウンタ管理部が、基礎カウンタがフルカウント数又は該フルカウント数の一定範囲前になったとき予備カウンタを基礎カウンタの上位桁に動的にリンクして拡張カウンタを構成し、拡張カウンタがリセットされたとき、リンクを開放するようにしたので、拡張カウンタのビット数を動的に制御しハード規模及び消費電力を削減することが可能になる。
必要な全カウンタのビット数を、本発明の統計カウンタ装置１００と従来の統計カウンタ装置１００ｚとで比較する。
図１において、ユーザ数が１０２４の場合、本発明の統計カウンタ装置１００が必要とするビット数＝２２ビット×１０２４、従来の本発明の統計カウンタ装置１００ｚが必要とするビット数＝３２ビット×１０２４である。従って、（２２ビット×１０２４）／（３２ビット×１０２４）≒０．６９であり、約３０％のハードウェア規模及び消費電力が削減することが可能になる。
図２において、ユーザ数が６５５３６の場合、本発明の統計カウンタ装置１００が必要とするビット数＝１６ビット×６５５３６、従来の統計カウンタ装置１００ｚが必要とするビット数＝３２ビット×６５５３６である。従って、（１６ビット×６５５３６）／（３２ビット×６５５３６）≒０．５０であり、約５０％のハードウェア規模及び消費電力が削減することが可能になる。
さらに、ユーザ数が１００００００＝２２０と仮定した場合、本発明の統計カウンタ装置１００が必要とするビット数＝１２ビット×１００００００、従来の統計カウンタ装置１００ｚが必要とするビット数＝３２ビット×１００００００である。従って、（１６ビット×１００００００）／（３２ビット×１００００００）≒０．３８であり、約６０％のハードウェア規模及び消費電力が削減することが可能になる。
【図１】
2004112250.tif 000005
【図２】
2004112250.tif 000006
【図３】
2004112250.tif 000007
【図４】
2004112250.tif 000008
【図５】
2004112250.tif 000009
【図６】
2004112250.tif 000010
【図７】
2004112250.tif 000011
【図８】
2004112250.tif 000012
【図９】
2004112250.tif 000013
【図１０】
2004112250.tif 000014
【図１１】
2004112250.tif 000015
【図１２】
2004112250.tif 000016
【国際調査報告】
2004112250.tif 000017
2004112250.tif 000018