(57)【特許請求の範囲】
【請求項１】
バッファを有するエレメントでパケットを受け取るステップと、
平均バッファフィルはバッファの平均充てん状態であって、パケットが記憶されるバッファの平均バッファフィルが、最小しきい値より大きく最大しきい値よりも小さいか否かを判断するステップと、
平均バッファフィルが、最小しきい値より大きく、最大しきい値よりも小さい場合に、パケットがエレメントから失われる確率を定める、パケットに関する廃棄確率を計算する計算ステップと、
廃棄確率を乱数と比較する比較ステップと、
廃棄確率が乱数より大きい場合にエレメントからパケットを廃棄する廃棄ステップとを含むアクセス制御の方法であって、
計算ステップは、
最後の廃棄からのカウント、パケットサイズ、平均バッファフィル、カラー及びキューを含む変数の値をプログラム可能なしきい値と比較して領域にマップすることで、新しい変数の値を得るマッピングステップと、
マッピングステップで得られた新しい変数の値を用いて、確率メモリにおける廃棄確率のアドレスを特定するステップと、
確率メモリには、新しい変数の値が取り得る組合せの全てに対して予め計算された廃棄確率が記憶されており、マッピングステップで得られた新しい変数の値について予め計算された廃棄確率を、特定されたアドレスを用いて確率メモリから取り出すステップとを含み、
廃棄確率は、以下のように定義され、
【数１】
0004050046.tif 000014
ここで、
【数２】
0004050046.tif 000015
であり、ｍａｘ＿ｐｍａｒｋｉｎｇ、  ｍａｘｔｈｍａｒｋｉｎｇ、ｍｉｎｔｈｍａｒｋｉｎｇ、ｍａｘＰａｃｋｅｔ、及びｑｕｅｕｅ＿ｗｅｉｇｈｔｑｕｅｕｅは定数である方法。
【請求項２】
マッピングステップは、変数の各々を少なくとも２つの領域の何れかにマップする請求項１に記載の方法。
【請求項３】
【数３】
0004050046.tif 000016
であり、k１及びk２は整数であり、これらの和＝Ｘである請求項１に記載の方法。
【請求項４】
Ｘ＝６４である請求項３に記載の方法。
【請求項５】
比較ステップは、乱数生成器を近似するリニアフィードバックシフトレジスタによって生成された乱数と、確率メモリから取り出された廃棄確率とを比較するステップを具える請求項１乃至４の何れかに記載の方法。
【請求項６】
廃棄ステップは、各２クロック周期でパケットを廃棄する工程を具える、請求項１乃至５の何れかに記載の方法。
【請求項７】
エレメントは、パケットをネットワークに送るリアセンブラを具える請求項１乃至６の何れかに記載の方法。
【請求項８】
パケットが記憶されるバッファを有するエレメントと、
バッファにつながっており、バッファの平均充てん状態である平均バッファフィルを決定する決定機構と、
平均バッファフィルが、最小しきい値より大きく、最大しきい値よりも小さい場合に、パケットがエレメントから失われる確率を定める、パケットに関する廃棄確率を計算する計算機構と、
乱数を生成する乱数生成機構と、
廃棄確率が乱数より大きい場合にエレメントからパケットを廃棄する廃棄機構とを具えており、
計算機構は、
予め計算された廃棄確率を有する確率メモリと、
最後の廃棄からのカウント、パケットサイズ、平均バッファフィル、カラー及びキューを含む変数の値をプログラム可能なしきい値と比較して領域にマップすることで、新しい変数の値を得るマッピング機構と、
マッピング機構で得られた新しい変数の値を用いて、確率メモリにおける廃棄確率のアドレスを特定する特定機構とを具えており、
確率メモリには、新しい変数の値が取り得る組合せの全てに対して予め計算された廃棄確率が記憶されており、
計算機構は、特定機構で特定されたアドレスを用いて、マッピング機構で得られた新しい変数の値について予め計算された廃棄確率を確率メモリから取り出し、
廃棄確率は、以下のように定義され、
【数４】
0004050046.tif 000017
ここで、
【数５】
0004050046.tif 000018
であり、ｍａｘ＿ｐｍａｒｋｉｎｇ、  ｍａｘｔｈｍａｒｋｉｎｇ、ｍｉｎｔｈｍａｒｋｉｎｇ、ｍａｘＰａｃｋｅｔ、及びｑｕｅｕｅ＿ｗｅｉｇｈｔｑｕｅｕｅは定数である装置。
【請求項９】
マッピング機構は、変数の各々を少なくとも２つの領域の何れかにマップする請求項８に記載の装置。
【請求項１０】
【数６】
0004050046.tif 000019
であり、k１及びk２は整数であり、これらの和＝Ｘである請求項８に記載の装置。
【請求項１１】
Ｘ＝６４である請求項１０に記載の装置。
【請求項１２】
乱数生成機構は、乱数生成器を近似するリニアフィードバックシフトレジスタを具える請求項８乃至１１の何れかに記載の装置。
【請求項１３】
廃棄機構は、各２クロック周期でパケットを廃棄する請求項８乃至１２の何れかに記載の装置。
【請求項１４】
エレメントは、パケットをネットワークに送るリアセンブラを具える請求項８乃至１３の何れかに記載の装置。
【請求項１５】
決定機構は、瞬間的キューフィルを決定する機構を具える請求項８乃至１４の何れかに記載の装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、アクティブキューマネジメント(active queue management)に関する。より詳細には、本発明は、アクティブキューマネジメントに関し、このキューマネジメントは、記憶されるためにバッファに受け取られるパケットの廃棄確率  (drop probability)を計算する。さらに、このキューマネジメントは、乱数と廃棄確率を比較して、バッファの平均バッファフィル(average buffer fill)が最小しきい値よりも大きく最大しきい値よりも小さい場合に、パケットが廃棄されるべきか否かを決定する。
【０００２】
【発明の背景】
ランダムアーリディテクション(Random Eariy Detection)、すなわちＲＥＤは、アクティブキューマネジメントを可能とすると言われるメカニクスの中の一つである。アクティブキューマネジメントは、高層のプロトコルダイナミクスと結び合った方法でバッファ占有率を制御することを試みる。この様なメカニクスの動機は、ＲＦＣ-２３０９”Recommendations on Queue Management and Congestion Avoidance in the Internet”において述べられている。
【０００３】
アクティブキューマネジメントをしなければ、オーバーフローするまで単にバッファが充てん(fill)される。これは、一般にテールドロップ(tail drop)として知られている。バーストの後ろの部分（ｔａｉｌ）は、ほとんど廃棄されるからである。実際のバッファオーバーフローの前に廃棄をトリガするアーリパケットディスカード(Early Packet Discard)（ＥＰＤ）は、ここに記載されたテールドロップ処理についてＡＴＭ独特の最適化をしたものである。
【０００４】
ＲＥＤとテールドロップの構成の最も著しい違いは、後者が、ほとんど充てんされたバッファを輻輳(congestion)下において保とうとする一方で、ＲＥＤは、バッファを比較的空に維持しようとすることである。これは、バッファを、到達速度(arrival rate)が出発速度(depature rate)よりも遅い期間内で出力リンクをビジーに保つビットの倉庫と見ることから、それらの主要な目的をバーストの吸収と見ることへの、原理的変換を示している。このことには、インターネットのトラヒック(traffic)の性質(多数のものが大量であり、集められた場合はさらにそうである)と、高層のインターネットプロトコル(特にＴＣＰ)がネットワーク容量を分かって対応する方法の理解とが反映されている。
【０００５】
ＲＥＤによってバッファ占有率をマネジメントする顕著な効果は、以下の事項を含む。
（１）遅延と遅延の変化は、キューイング遅延(queuing delay)の短縮を通じて短縮される。
（２）個々のソースが伝送する速度を制御する高層のプロトコルにおいて、状態同期(state synchronization)を回避することにより、リンクの利用は増加する。
（３）大量の通信量のソースに対する差別(discrimination)が排除される。
（４）長い距離にまたがるフロー(flow)に対する差別が減少する。
【０００６】
ＲＥＤは、最初に、ＦｌｏｙｄとＶａｎ  Ｊａｃｏｂｓｏｎによる論文「"Rabdom Early Detection Gateways For Congestion Avoidance", in IEEE/ACM Transactions on Networking, V.1 N.4, August 1993, p. 397-413」(http://www.aciri.org/floyd/papers/early.pdf で入手可)で提案された。この論文で示されたアルゴリズムは、最も効果的なサービスのみをサポートしていた。シスコシステムもＲＥＤを供給している。
【０００７】
ＲＥＤを拡張して、トラヒックの請負仕事(contract)にフローが従っているか否かに基づいた廃棄確率の区別(differentiation)をサポートすることは、ＣｌａｒｋとＦａｎｇの論文 "Explicit Allocation of Best Effort Delivery Service"(http://diffserv.lcs.mit.edu/Papers/exp-alloc-ddc-wf.ps で入手可)で説明されている。この論文は、一般に"ＲＥＤ ｗｉｔｈ Ｉｎ ａｎｄ Ｏｕｔ"(ＲＩＯ)として知られているものを与えている。ＮｉｃｈｏｌとＩｂａｎｅｚは、確実なサービスをサポートするためにＲＩＯの利用を検討している。
【０００８】
本発明によって、ＲＩＯは２つのマーキング（「カラー」）から３つのマーキングに拡張され、その３つのカラーのマーキングをＡＦ ＰＨＢの要求に適合できる。これは、重み付き(Weighted)ＲＥＤ（ＷＲＥＤ）と称される。パケットが各２クロック周期で到着するシステムでは、ＷＲＥＤアルゴリズムに要求される浮動小数点演算は、非常に長い時間を要するので、実行するのが非常に困難である。本発明は、厳密な整数演算と確率探索(probability lookup)を用いたＷＲＥＤの近似方法(approximation)を含む。
【０００９】
【発明の概要】
本発明は、パケットを記憶する装置に関する。その装置は、パケットを記憶するバッファを含む。その装置は、バッファの平均バッファフィルを決定する機構を含む。ここで、バッファの平均フィルは、バッファの平均充てん状態である。その決定機構は、バッファとつながっている。その装置は、パケットに関する廃棄確率を計算する機構を含み、パケットがバッファから失われる確率を定める。その装置は、乱数を発生する機構を含む。その装置は、廃棄確率が乱数よりも大きい場合にエレメントからのパケットを廃棄する機構を含む。
【００１０】
本発明は、アクセス制御の方法に関する。その方法は、バッファを有するエレメントでパケットを受け取るステップを含む。さらに、パケットが記憶されるバッファの平均バッファフィルが最小しきい値よりも大きく最大しきい値より小さいか否かを判断するステップがある。ここで、平均バッファフィルは、バッファの平均充てん状態である。次に、パケットに関する廃棄確率を計算するステップがあり、パケットがエレメントから失われる確率を定める。さらに、廃棄確率を乱数と比較するステップがある。次に、廃棄確率が乱数よりも大きい場合にエレメントからパケットを廃棄するステップがある。
【００１１】
【詳細な説明】
幾つかの図面を通じて、同じ符号は類似又は同一の部分を示している。特にその中の図１を参照すると、パケットを記憶する装置(10)が示されている。装置(10)はパケットが記憶されるバッファ(12)を具える。装置(10)は、バッファ(12)の平均バッファフィルを決定する機構(14)を具える。ここで、平均バッファフィルは、バッファ(12)の平均充てん状態である。決定機構(14)は、バッファ(12)につながれている。装置(10)は、パケットに関する廃棄確率を計算する機構(16)を具え、バッファ(12)からパケットが失われる確率を定める。装置(10)は、乱数を生成する機構(18)を具える。装置(10)は、廃棄確率が乱数より大きい場合にエレメント(29)からパケットを廃棄する機構(30)を具える。
【００１２】
計算機構(16)は、先に決定された(predetermined)廃棄確率を有する確率機構(20)を含み、該確率機構(20)から廃棄確率が得られるのが好ましい。確率機構(20)は、アドレスを有する確率メモリ(24)を具えるのが好ましく、計算機構(16)は、廃棄確率を有する確率メモリ(24)のアドレスを特定する(identifying)機構(22)を含む。計算機構(16)は、変数の値を領域(region)にマップ(map)するマッピング機構(26)を含むのが好ましい。
【００１３】
乱数生成機構は、乱数生成器を近似するリニアフィードバックシフトレジスタ(28)を含むのが好ましい。確率は、
【数７】
0004050046.tif 000002
として定義されるのが好ましく、ここで、
【数８】
0004050046.tif 000003
であり、max pｍａｒｋｉｎｇ、  maxthｍａｒｋｉｎｇ、  minthｍａｒｋｉｎｇ、
maxPacket、及びqueue weightｑｕｅｕｅは定数である。好ましくは、
【数９】
0004050046.tif 000004
であり、ここで、k１及びk２は整数であり、これらの和＝６４である。決定機構(14)は、瞬間的(instantaneous)キューフィルを決定する機構(32)を含むのが好ましい。
【００１４】
本発明は、アクセス制御の方法に関する。該方法は、バッファ(12)を有するエレメント(29)でパケットを受け取るステップを具える。そして、パケットが記憶されるバッファ(12)の平均バッファフィルが、最小しきい値よりも大きく最大しきい値よりも小さいか否かを判断するステップがある。ここで、平均バッファフィルは、バッファ(12)の平均充てん状態である。次に、パケットに関する廃棄確率を計算するステップがあり、エレメント(29)からパケットが失われる確率を定める。そして、廃棄確率を乱数と比較するステップがある。次に、廃棄確率が乱数より大きい場合にエレメント(29)からパケットを廃棄するステップがある。
【００１５】
計算ステップは、先に計算された(precomputed)廃棄確率を有する確率メモリ(24)から廃棄確率を取り出すステップを含む。計算ステップは、該取り出すステップの前に、廃棄確率の確率メモリ(24)におけるアドレスを特定するステップを含むのが好ましい。アドレスを決定するステップは、少なくとも２つの領域の何れかに各変数の値をマップするマッピングステップを含むのが好ましい。
【００１６】
アドレスを特定するステップは、そのマッピングステップの後に、変数からアドレスを決定するステップを含むのが好ましい。マッピングステップは、プログラム可能な(programable)しきい値と変数とを比較して、少なくとも２つの領域の何れかに各変数をマップするステップを含むのが好ましい。比較ステップは、乱数生成器を近似するリニアフィードバックシフトレジスタ(28)によって生成された乱数と廃棄確率とを比較するステップを含むのが好ましい。
【００１７】
変数は、最後の廃棄からのカウント、パケットサイズ、平均バッファフィル、カラー及びキューをそれぞれ含むのが好ましい。領域は、最後の廃棄からのカウント、パケットサイズ、平均バッファフィル、カラー、及びキューからなる変数からそれぞれ導かれた、ｃｏｕｎｔ＿ｒｅｇｉｏｎ、ｐｋｔｓｉｚｅ＿ｒｅｇｉｏｎ、ａｂｆ＿ｒｅｇｉｏｎ、ｃｏｌｏｒ、及びｑｕｅｕｅを含むのが好ましい。廃棄ステップは、各２クロック周期でパケットを廃棄するステップを含むのが好ましい。
【００１８】
エレメント(29)は、ネットワークにパケットを送るリアセンブラ(reassembler)を含むのが好ましい。確率は、
【数１０】
0004050046.tif 000005
として定義されるのが好ましく、ここで、
【数１１】
0004050046.tif 000006
であり、max pｍａｒｋｉｎｇ、maxthｍａｒｋｉｎｇ、minthｍａｒｋｉｎｇ、maxPacket、及びqueue weightｑｕｅｕｅは定数である。好ましくは、
【数１２】
0004050046.tif 000007
であり、ここで、ｋ１及びｋ２は整数であり、これらの和＝Xである。X＝６４であるのが好ましい。
【００１９】
発明の実施において、パケットを廃棄すると認められる場合を決定するために、２つのしきい値が用いられる。以下に示す式において、これらのしきい値は、最小しきい値及び最大しきい値のそれぞれについて、ｍｉｎｔｈ及びｍａｘｔｈと示される。これらのしきい値が平均バッファフィル（ａｂｆ）と比較されて、廃棄確率が決定される。ａｂｆがｍｉｎｔｈより小さいならば、問題のパケットは失われない（０．０の確率で失われる）。ａｂｆがｍａｘｔｈより大きいならば、問題のパケットは確実に失われる（１．０の確率で失われる）。ａｂｆがｍａｘｔｈとｍｉｎｔｈの間にある場合は、パケットについて廃棄確率が計算される。ａｂｆがｍｉｎｔｈを越えるほど、廃棄する確率は大きくなる。同じようにこの確率に影響を与える他の因子も存在する。これらには、最後の廃棄から受け取られたパケットの数、パケットのマーキング（ディフサーブカラー(DiffServ coler)）、及びパケットがどのキューに属するかということがある。図２は、基本的な重み付きＲＥＤの運用における確率関数を示している。図３は、パケットサイズ、最後の廃棄からのカウント、キュー、及びカラーからの影響が存在しない近似での確率関数を示している。
【００２０】
計算された確率は乱数と比較される。廃棄確率が大きい場合、パケットは廃棄される。そうでなければ、パケットは維持される。平均バッファフィルは、システム内への各パケットエントランス、又は周期的基準のとちらか一方に基づいて計算される。指数重み付けられた移動平均(exponentially weighted moving average)によって、システムは、廃棄なくトラヒックのバーストを処理できる。
【００２１】
ａｂｆｍａｒｋｉｎｇを、ｍａｒｋｉｎｇなるマーキングを伴うパケットに適用される、指数重み付き移動平均バッファ占有率とする。
ｉｑｆＱを、パケットが属するキューの瞬間的キューフィルとし、ｍｉｎＱを、このキューに保証された最小バッファ空間とする。
【００２２】
pktsizeは、バイトで示した到着するパケットのサイズとする。
max pｍａｒｋｉｎｇは、abfｍａｒｋｉｎｇがRｍａｒｋｉｎｇ，２に達する場合に構成される(configured)廃棄確率とする。
maxPacketは、構成される最大パケットサイズとする（MaxPacketは、パケットサイズに比例した廃棄確率を重み付ける働きをする）。
countは、最後にパケットが失われてからキューに入れられた(enqueued)パケットの数である。
【００２３】
平均バッファフィル関数は、
【数１３】
0004050046.tif 000008
である。
【００２４】
abfｍａｒｋｉｎｇの計算は浮動小数点演算であり、バッファ(12)の充てん状態の指数重み付き移動平均を計算する。weightは、０と１.０の間の値であり、０と１.０とを含む。weightパラメータは、その平均のスムーシング(smoothing)を制御する。iqfｍａｒｋｉｎｇは、瞬間的キューフィル、すなわちmarkingでクラス化された(classified)パケットが用いるバッファ(12)の瞬間的測定値である。weightが１.０に近づくほど、その平均はより緊密にその瞬間的測定値に従う。
【００２５】
確率関数について述べる。
これらの公式は、平均バッファフィルがminthとmaxthのしきい値の間にある場合のパケットの廃棄確率（pａ）を表す。
【数１４】
0004050046.tif 000009
【数１５】
0004050046.tif 000010
【００２６】
与えられたmarkingとqueueのパケットの廃棄確率は、幾つかの定数（max pｍａｒｋｉｎｇ、maxthｍａｒｋｉｎｇ、minthｍａｒｋｉｎｇ、maxPacket、及びqueue weightｑｕｅｕｅ）及び３つの変数（count、abfｍａｒｋｉｎｇ、及びpktsize）の関数である。得られる確率は、０と１.０の間の数であり、０と１．０を含む。queue weightｑｕｅｕｅもまた、０と１.０の間の数であり、０と１．０とを含む。abfｍａｒｋｉｎｇは、上記に示したように計算される浮動小数点数である。残りのパラメータは整数である。この実施例では、markingには３つの可能な値があり、queueには１６の可能な値がある。iqfＱ ＜ minＱ ならば、廃棄確率は必ず０.０である。
【００２７】
システムの要求は、各２クロック周期でパケットを処理できなければならないことである。それゆえ、各２クロック周期でＷＲＥＤ確率の決定を完了できなければならない。そのアルゴリズムは、深いパイプラインを伴って浮動小数点を用いて実施できるであろうが、ハードウェアでの浮動小数点演算は、時間と同様にゲートカウント(gate-count)においても不経済である。abfｍａｒｋｉｎｇの計算近似(computatioal approximation)及びpa(abfｍａｒｋｉｎｇ)の探索近似に基づく、abfｍａｒｋｉｎｇとpa(abfｍａｒｋｉｎｇ)の純整数近似が行われる。
【００２８】
abfｍａｒｋｉｎｇのコンピュータによる近似は、以下のようになされる。
【数１６】
0004050046.tif 000011
なお、ｋ１+ｋ２は必ず６４に等しい。
【００２９】
パラメータｋ１及びｋ２は整数であり、これらの和は６４に等しい必要がある。本実施例において、６４で割ることは単に５ビットのシフトである。掛け算は、単一周期で並行して行うことができる。次の足し算とシフトも単一周期で完了される。
【００３０】
近似の目的は、浮動小数点演算を排除することなので、確率探索近似の第１ステップは、０.０及び１.０を含む０.０から１.０までの確率範囲を、０及び２５５を含む０から２５５までの整数範囲に正規化する(normalize)ことである。確率は、８ビットの符号のない整数となる。さらに、その近似は、上記の確率計算に定数を含む利点があるので、これらの定数を伴う上記変数の組合せの確率変数をソフトウェアプログラムが先に計算できる。さらなる近似が要求されるが、それぞれの変数は数百の状態を取るので、先に計算された値を全て記憶することは禁止される。したがって、最後の近似は、可能な組合せの数を減らすために、プログラム可能なしきい値と変数の値とを比較して、変数の値を領域にマップすることである。
【００３１】
例えば、全ての変数（count、abfｍａｒｋｉｎｇ、及びpktsize）が範囲[０,１０２３]内の整数と仮定する。これらの変数の可能な組合せの全ては１０２４3、すなわち１，０７３，７４１，８２４のエントリーを要するであろう。それゆえ、解決法は、しきい値に基づいて、これらの値のそれぞれを４つの領域の１つにマップすることである。新しい変数は、count region、abf regionｍａｒｋｉｎｇ、及び pktsize regionとなる。その結果、変数の組合せの全てではなく、領域の組合せの全てにのみ記憶が必要とされる。つまり、４3、すなわち６４エントリーである。さらに２自由度（３つの値が可能なcoler、及び１６の値が可能なqueue）が考慮されると、全部で、３＊１６＊６４、すなわち８ビットの整数の３０７２エントリーが存在する。このコンセプトはより高精度に拡張できる。例えば、３つの変数を８つの領域のそれぞれにマップすることを望む場合、全部で３＊１６＊８3、すなわち２４，５７６エントリーとなる。
【００３２】
それぞれの変数（count region、abf regionｍａｒｋｉｎｇ、pktsize region、color、及び queue）は、５次元の確率配列(probability array)のインデックスになるので、探索近似を完全にすることができる。これらの変数の各組合せについて、ソフトウェアは、廃棄確率が取る値を先に計算する。
【００３３】
次に、ハードウェアの形態においては、１つの計算のみがなされる必要があり、これは、ｐｋｔｓｉｚｅ＿ｒｅｇｉｏｎである。ｃｏｕｎｔ＿ｒｅｇｉｏｎは、単に最後の廃棄からのカウントのカウンタの最上の２ビットであり、計算を必要としない。ａｂｆ＿ｒｅｇｉｏｎｍａｒｋｉｎｇは、バックグラウンドで周期的に計算され、パケットが到達した時にすでに使用可能である。ｃｏｌｏｒは、パケット自体から決定され、パケットが属するｑｕｅｕｅは、探索を通して(ＶＰＩ及びＶＣ或いはＩＰヘッダのような)パケットフロー識別子(identifier)から得られる。これらの５つのパラメータは、先計算(precomputed)確率メモリ(24)内にアドレスを作製するのに用いられ、パケットの確率が取り出される(retrieved)。最後に、この確率は、乱数生成器を近似するリニアフィードバックシフトレジスタ(28)の出力と比較されるので、パケットが失われるべきか否かを決定できる。この全ては、６クロック周期で完了し、各２サイクルで決定を完了するためにパイプライン化される。
【００３４】
上記のＷＲＥＤの実施で用いられるパラメータは、以下の表にまとめられている。これらは、非近似のＷＲＥＤのパラメータである。近似に直接適合するものには以下のタグが付されており
【外１】
0004050046.tif 000012
間接的に適合するものには注釈がある。
【００３５】
【表１】
0004050046.tif 000013
【００３６】
図４は、実施例のブロック図の概要である。
図５は、確率メモリアドレス作製(formation)構造のブロック図である。
図６は、ＷＲＥＤの実施例のフローチャートである。
【００３７】
例示目的で示した実施例において発明を詳細に説明したが、その詳細な説明は単にその目的のためであり、当該分野の専門家であれば、特許請求に規定された範囲以外のものについては、発明の精神及び範囲から逸脱することなく変形を成し得ることは理解されるべきである。
【図面の簡単な説明】
添付した図面において、発明の好ましい実施例と、発明を実施する好ましい方法は、以下のように示されている。
【図１】本発明の装置の概略図である。
【図２】ＲＥＤアルゴリズムの確率関数のグラフである。
【図３】ＷＲＥＤ階段状(stair-step)近似のグラフである。
【図４】本発明の装置の実施形態のブロック図の概略図である。
【図５】確率メモリアドレス作製構造のブロック図の概略図である。
【図６】本発明のアルゴリズムのフローチャートである。
【図１】
0004050046.tif 000020
【図２】
0004050046.tif 000021
【図３】
0004050046.tif 000022
【図４】
0004050046.tif 000023
【図５】
0004050046.tif 000024
【図６】
0004050046.tif 000025