(57)【要約】【課題】  所望のトラヒックやバッファ量の条件に対して、各キューの長さにおける存在確率分布を、プログラミングを簡単に行い、且つ、短時間で演算可能とする。【解決手段】  本発明は、存在確率メモリＡに初期の存在確率分布が設定され、それの値と、入力トラヒックの特性を表す遷移確率を用いて演算を行い、その結果を「演算後存在確率分布」とし、他方の存在確率メモリＢに記録する。メモリＡから読み出された値による一連の演算が終了すると、今度は、メモリＢの値を「演算前存在確率分布」とし、演算を行い、その結果を「演算後存在確率分布」として、存在確率メモリＡに記録する。さらに、メモリＡの値を「演算前存在確率分布」として演算を行い、その結果を「演算後存在確率分布」として、メモリＢに記録する。これらの演算を、演算の終了条件（例えば所定の回数）を満たすまで繰り返す。【選択図】  図１
2011078079.tif 000002
【特許請求の範囲】
【請求項１】
バッファにトラヒックが入力する待ち行列において、各キューの長さにおける存在確率分布を求めるキュー長分布演算方法であって、
各キューの長さにおける存在確率分布を、入力トラヒックの特性を表している各トラヒックの生起確率を遷移確率として用いて演算する演算手段と、
遷移確率に従って演算する前及び演算した後の各キューの長さにおけるそれぞれの一連の存在確率を記憶する少なくとも２つのメモリ（以下、それぞれを「演算前存在確率メモリ」、「演算後存在確率メモリ」と記す）を有する装置において、
前記演算手段が、
単位時間内にキュー長をｘ（ｘは０以上の整数）だけ増加させる入力トラヒック長の生起確率をｐ（ｘ）、待ち行列のバッファから出力されることによる単位時間内に減少するキューの長さの最大値をａ、演算する前のキュー長をｍ、演算前存在確率メモリをｑ１（ｍ）（ｍ＝０，１，２，…，Ａ（但し、Ａはメモリの最大キュー長））、演算後存在確率メモリをｑ２（ｍ）（ｍ＝０，１，２，…，Ａ）とした場合に、
キュー長ｍについて、ｙ＝（ｍ＋ｘ−ａ）を求め、その値が負の場合はｙ＝０（ゼロ）とし、演算後のキュー長ｙの存在確率ｑ２（ｙ）の値にｐ（ｘ）×ｑ１（ｍ）を加算する計算を、ｘの値を０（ゼロ）から順に１ずつ加算してｙ＝Ａになるまで行う演算ステップを実行すること特徴とするキュー長分布演算方法。
【請求項２】
前記演算ステップは、
演算前のキュー長ｍと単位時間に増加するキュー長ｘを変化させる順番を逆にして演算する、すなわち、ある値ｘについて、ｍを順次１ずつ増加または減少させてｙ＝（ｍ＋ｘ−ａ）を求め、演算後のキュー長ｙの存在確率ｑ２（ｙ）の値にｐ（ｘ）×ｑ１（ｍ）を加算する計算を行い、この計算を、ｘを順次１ずつ増加または減少させる演算を行う
請求項１記載のキュー長分布演算方法。
【請求項３】
待ち行列における各キューの長さにおける存在確率分布を求めるキュー長分布演算方法であって、
各キューの長さにおける存在確率分布を、入力トラヒックの特性を表している遷移確率を用いて演算する演算手段と、
遷移確率に従って演算する前及び後の各キューの長さにおける一連の存在確率を記憶する少なくとも２つのメモリを有する装置において、
演算手段が、
演算後存在確率メモリのキュー長ｎについて、ｚ＝ｎ−ｘ＋ａを求め、演算後のキュー長ｎの存在確率ｑ2（ｎ）の値にｐ（ｘ）×ｑ１（ｚ）を加算する計算を、ｘの値を０（ゼロ）から順に１ずつ加算して、ｚが−１になるまで行う（但し、ｚがＡより大きい場合はｑ2（ｎ）に加算する演算を行わない。これらの計算を、ｎの値を０（ゼロ）から順に１ずつ加算してｎ＝Ａまで繰り返す）演算ステップを行う
ことを特徴とするキュー長分布演算方法。
【請求項４】
有限バッファ長でキューが溢れる場合には、各キューの長さにおける存在確率分布が一定の値に漸近するまで前記演算ステップを行い、
一定の値に漸近した各キューの長さにおける存在確率分布を演算前の値とする
請求項１乃至３のいずれか１項に記載のキュー長分布演算方法。
【請求項５】
前記演算ステップは、
演算後のキュー長ｎと単位時間に増加するキュー長ｘを変化させる順番を逆にして演算する、すなわち、ある値ｘについて、ｎを順次１ずつ増加または減少させて演算後存在確率メモリのキュー長ｎについて、ｚ＝ｎ−ｘ＋ａを求め、演算後のキュー長ｎの存在確率ｑ2（ｎ）の値にｐ（ｘ）×ｑ１（ｚ）を加算する計算を行い、この計算を、ｘを順次１ずつ増加または減少させる演算を行う
請求項３記載のキュー長分布演算方法。
【請求項６】
前記演算ステップを繰り返し行い、
あるキュー長における存在確率の演算前と演算後の値の差がある閾値以下、または、ある閾値以上、または、差の絶対値がある閾値以下になったときに存在確率演算を停止し、演算後の各キューの長さにおける存在確率分布を出力する
請求項１乃至５のいずれか１項に記載のキュー長分布演算方法。
【請求項７】
前記各キューの長さにおける演算前存在確率と演算後存在確率との差の絶対値を求め、該絶対値の総和がある閾値以下、または、１と総和との差がある閾値以上になった場合に、繰り返し演算を停止し、演算後の各キューの長さにおける存在確率分布を出力する
請求項１乃至５のいずれか１項に記載のキュー長分布演算方法。
【請求項８】
各キューの長さにおける存在確率分布の初期値として、キュー長＝０の存在確率を１とし、それ以外のキュー長の存在確率を０（ゼロ）とする
請求項１乃至７のいずれか１項に記載のキュー長分布演算方法。
【請求項９】
前記演算ステップにおける各キューの長さにおける存在確率の演算後に、存在確率の値の総和を求め、その総和がある閾値以下、または、１と総和の差がある閾値以上になったときに繰り返し演算を停止する
請求項１乃至８のいずれか１項に記載のキュー長分布演算方法。
【請求項１０】
前記演算ステップにおける各キューの長さにおける存在確率の演算後に、存在確率の値の総和を求め、その総和がある閾値を超えたとき、または、総和と１との差がある閾値以上になったときに繰り返し演算を停止する
請求項１乃至８のいずれか１項に記載のキュー長分布演算方法。
【請求項１１】
前記存在確率メモリおよび演算用レジスタの各サイズ（仮数部や指数部のビット数）を拡張する
請求項９また１０記載のキュー長分布演算方法。
【請求項１２】
バッファにトラヒックが入力する待ち行列において、各キューの長さにおける存在確率分布を求めるキュー長分布演算装置であって、
各キューの長さにおける存在確率分布を、入力トラヒックの特性を表している各トラヒックの生起確率を遷移確率として用いて演算する演算手段と、
遷移確率に従って演算する前及び演算した後の各キューの長さにおけるそれぞれの一連の存在確率を記憶する少なくとも２つのメモリ（以下、それぞれを「演算前存在確率メモリ」、「演算後存在確率メモリ」と記す）を有し、
前記演算手段は、
単位時間内にキュー長をｘ（ｘは０以上の整数）だけ増加させる入力トラヒック長の生起確率をｐ（ｘ）、待ち行列のバッファから出力されることによる単位時間内に減少するキューの長さの最大値をａ、演算する前のキュー長をｍ、演算前存在確率メモリをｑ１（ｍ）（ｍ＝０，１，２，…，Ａ（但し、Ａはメモリの最大キュー長））、演算後存在確率メモリをｑ２（ｍ）（ｍ＝０，１，２，…，Ａ）とした場合に、
キュー長ｍについて、ｙ＝（ｍ＋ｘ−ａ）を求め、その値が負の場合はｙ＝０（ゼロ）とし、演算後のキュー長ｙの存在確率ｑ２（ｙ）の値にｐ（ｘ）×ｑ１（ｍ）を加算する計算を、ｘの値を０（ゼロ）から順に１ずつ加算してｙ＝Ａになるまで行う手段を有することを特徴とするキュー長分布演算装置。
【請求項１３】
請求項１乃至１０のいずれか１項に記載のキュー長分布演算方法の各処理をコンピュータに実行させるためのキュー長分布演算プログラム。
【請求項１４】
請求項１３に記載のキュー長分布演算プログラムを格納したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰ(Internet Protocol)やＡＴＭ(Asynchronous Transfer Mode)等のトラヒック（ＩＰパケット、イーサネットフレーム、ＡＴＭセル等）が、ネットワーク内のスイッチ（ルータ、Ｌ２ＳＷ)等のバッファに入力後出力される場合の、バッファのキュー長分布演算方法及び装置及びプログラムに係り、特に、待ち行列における各キューの長さにおける存在確率分布及び損失確率（または、廃棄確率。以下「損失確率」と記す）の演算を行うためのキュー長分布演算方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
従来の各キューの長さにおける存在確率分布を求める方法として、モンテカルロシミュレーション法とインポータンスサンプリングシミュレーション法が知られている（例えば、非特許文献１参照）。さらに、得られた存在確率分布からサバイバ関数を求め、キューの長さに対応する損失確率を得ることも行われている。
【０００３】
Ｍ／Ｄ／１モデルやＭＭＰＰ／Ｄ／１モデルなどのトラヒック解析に用いられるモンテカルロシミュレーション法は、コンピュータ内で、擬似ランダム関数を使って固定長のトラヒックを多数発生させ、その統計情報を各キューの長さにおける存在確率分布とするものである。
【０００４】
図１４は、従来のモンテカルロシミュレーション法の例を示したものである。バッファに入力するトラヒックの特性が事前にある生起確率分布で設定されており、それに対して擬似ランダム関数を使って一つ一つのトラヒックを発生させてバッファに入力させ、その時々のキュー長を計数し、これを統計的に有効な数になるまで繰り返し、最終的に各キューの長さにおける存在確率分布を求める。
【０００５】
よって、プログラミングも比較的簡単で、それを繰り返し演算すればよく、近年のＣＰＵの急速な発達により、同一内容のシミュレーション結果であれば、以前より短い時間で、所望の存在確率分布を求めることができる。しかし、統計情報が有効になるような多数の発生回数が必要であり、また、最近はメモリ価格の低廉化によりキュー長が長くなる傾向があるため、所望の存在確率分布を求めるためにはこれまで以上の回数のシミュレーションを行う必要があり、短時間で正確な結果を得ることは困難である。また、多くの回数のシミュレーションに用いる擬似乱数に限界があるという問題があることが、非特許文献１に述べられている。
【０００６】
一方、インポータンスサンプリングシミュレーション法では、簡単に言えば、ある関数による変換を行うことにより、所望のキュー長で損失確率を効率よく得ることができる方法である。従って、モンテカルロシミュレーション法に比べて短時間で結果を得ることができる。しかし、インポータンスサンプリングシミュレーション法は、モンテカルロシミュレーション法に比べて複雑なため、プログラミングに時間が掛かるという特徴がある。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】中川健治、"モンテカルロシミュレーション基礎"、電子情報通信学会、通信ソサイエティマガジン、２００８年秋号、No.6, pp.11-20.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上述のように、従来の方法は、プログラミングは簡単で短時間で済むが、演算時間がかかるか、または、演算時間は短いがそのプログラミングが複雑で時間がかかるというものであり、プログラミングが簡単で短時間で済み、且つ、演算時間が短い方法がないという問題があった。
【０００９】
本発明は、上記の点に鑑みなされたもので、所望のトラヒックやバッファ量の条件に対して、各キューの長さにおける存在確率分布を、従来に比べて、プログラミングを簡単に行え、且つ、短時間で演算できるキュー長分布演算方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明（請求項１）は、バッファにトラヒックが入力する待ち行列において、各キューの長さにおける存在確率分布を求めるキュー長分布演算方法であって、
各キューの長さにおける存在確率分布を、入力トラヒックの特性を表している各トラヒックの生起確率を遷移確率として用いて演算する演算手段と、
遷移確率に従って演算する前及び演算した後の各キューの長さにおけるそれぞれの一連の存在確率を記憶する少なくとも２つのメモリ（以下、それぞれを「演算前存在確率メモリ」、「演算後存在確率メモリ」と記す）を有する装置において、
演算手段が、
単位時間内にキュー長をｘ（ｘは０以上の整数）だけ増加させる入力トラヒック長の生起確率をｐ（ｘ）、待ち行列のバッファから出力されることによる単位時間内に減少するキューの長さの最大値をａ、演算する前のキュー長をｍ、演算前存在確率メモリをｑ１（ｍ）（ｍ＝０，１，２，…，Ａ（但し、Ａはメモリの最大キュー長））、演算後存在確率メモリをｑ２（ｍ）（ｍ＝０，１，２，…，Ａ）とした場合に、
キュー長ｍについて、ｙ＝（ｍ＋ｘ−ａ）を求め、その値が負の場合はｙ＝０（ゼロ）とし、演算後のキュー長ｙの存在確率ｑ２（ｙ）の値にｐ（ｘ）×ｑ１（ｍ）を加算する計算を、ｘの値を０（ゼロ）から順に１ずつ加算してｙ＝Ａになるまで行う演算ステップを実行する。
【００１１】
さらに、これらの計算を、ｍの値を０（ゼロ）から順に１ずつ加算してｍ＝Ａまで繰り返す。この一連の処理を、以下、１回の存在確率演算と呼ぶことにする。
【００１２】
尚、上記存在確率演算において、ｘの値を、（Ａ−ｍ＋ａ）から順に１ずつ減算してｘ＝０（ゼロ）になるまで行ってもよいし、また、ｍの値を、Ａから順に１ずつ減算してｍ＝０（ゼロ）まで繰り返してもよい。
【００１３】
また、本発明（請求項２）は、請求項１記載のキュー長分布演算方法において、
演算ステップは、
演算前のキュー長ｍと単位時間に増加するキュー長ｘを変化させる順番を逆にして演算する、すなわち、ある値ｘについて、ｍを順次１ずつ増加または減少させてｙ＝（ｍ＋ｘ−ａ）を求め、演算後のキュー長ｙの存在確率ｑ２（ｙ）の値にｐ（ｘ）×ｑ１（ｍ）を加算する計算を行い、この計算を、ｘを順次１ずつ増加または減少させる演算を行う。
【００１４】
本発明（請求項３）は、待ち行列における各キューの長さにおける存在確率分布を求めるキュー長分布演算方法であって、
各キューの長さにおける存在確率分布を、入力トラヒックの特性を表している遷移確率を用いて演算する演算手段と、
遷移確率に従って演算する前及び後の各キューの長さにおける一連の存在確率を記憶する少なくとも２つのメモリを有する装置において、
演算手段が、
演算後存在確率メモリのキュー長ｎについて、ｚ＝ｎ−ｘ＋ａを求め、演算後のキュー長ｎの存在確率ｑ2（ｎ）の値にｐ（ｘ）×ｑ１（ｚ）を加算する計算を、ｘの値を０（ゼロ）から順に１ずつ加算して、ｚが−１になるまで行う。但し、ｚがＡより大きい場合はｑ2（ｎ）に加算する演算を行わない。これらの計算を、ｎの値を０（ゼロ）から順に１ずつ加算してｎ＝Ａまで繰り返す演算ステップを行う。
【００１５】
当該請求項３に係る発明は、請求項１のキュー長分布演算方法において、後述する図７に示すように、演算前存在確率メモリのあるキュー長の存在確率を、遷移確率ｐ（ｘ）に従って、演算後のメモリの各キュー長の存在確率に分配するのに対し、図８に示すように、演算後存在確率メモリのあるキュー長に遷移する全ての演算前存在確率メモリの各キュー長の存在確率を、遷移確率ｐ（ｘ）に従って集約する方法である。
【００１６】
また、前記請求項１で述べたのと同様なオルタナティブがある。
【００１７】
また、本発明（請求項４）は、請求項１乃至３のいずれか１項に記載のキュー長分布演算方法において、
有限バッファ長でキューが溢れる場合には、各キューの長さにおける存在確率分布が一定の値に漸近するまで上記の演算ステップを行い、
一定の値に漸近した各キューの長さにおける存在確率分布を演算前の値とする。
【００１８】
また、本発明（請求項５）は、請求項３記載のキュー長分布演算方法において、
演算ステップは、
演算後のキュー長ｎと単位時間に増加するキュー長ｘを変化させる順番を逆にして演算する、すなわち、ある値ｘについて、ｎを順次１ずつ増加または減少させて演算後存在確率メモリのキュー長ｎについて、ｚ＝ｎ−ｘ＋ａを求め、演算後のキュー長ｎの存在確率ｑ2（ｎ）の値にｐ（ｘ）×ｑ１（ｚ）を加算する計算を行い、この計算を、ｘを順次１ずつ増加または減少させる演算を行う。
【００１９】
また、本発明（請求項６）は、請求項１乃至５のいずれか１項に記載のキュー長分布演算方法において、演算ステップを繰り返し行い、
あるキュー長における存在確率の演算前と演算後の値の差がある閾値以下、または、ある閾値以上、または、差の絶対値がある閾値以下になったときに存在確率演算を停止し、演算後の各キューの長さにおける存在確率分布を出力する。
【００２０】
また、本発明（請求項７）は、請求項１乃至５のいずれか１項に記載のキュー長分布演算方法において、
各キューの長さにおける演算前存在確率と演算後存在確率との差の絶対値を求め、該絶対値の総和がある閾値以下、または、１と総和との差がある閾値以上になった場合に、繰り返し演算を停止し、演算後の各キューの長さにおける存在確率分布を出力する。
【００２１】
また、本発明（請求項８）は、請求項１乃至７のいずれか１項に記載のキュー長分布演算方法において、
各キューの長さにおける存在確率分布の初期値として、キュー長＝０の存在確率を１とし、それ以外のキュー長の存在確率を０（ゼロ）とする。
【００２２】
また、本発明（請求項９）は、請求項１乃至８のいずれか１項に記載のキュー長分布演算方法において、
演算ステップにおける各キューの長さにおける存在確率の演算後に、存在確率の値の総和を求め、その総和がある閾値以下、または、１と総和の差がある閾値以上になったときに繰り返し演算を停止する。
【００２３】
また、本発明（請求項１０）は、請求項１乃至９のいずれか１項に記載のキュー長分布演算方法において、
演算ステップにおける各キューの長さにおける存在確率の演算後に、存在確率の値の総和を求め、その総和がある閾値を超えたとき、または、総和と１との差がある閾値以上になったときに繰り返し演算を停止する。
【００２４】
また、本発明（請求項１１）は、請求項９または１０記載のキュー長分布演算方法において、
存在確率メモリおよび演算用レジスタの各サイズ（仮数部や指数部のビット数）を拡張する。
【００２５】
本発明（請求項１２）は、バッファにトラヒックが入力する待ち行列において、各キューの長さにおける存在確率分布を求めるキュー長分布演算装置であって、
各キューの長さにおける存在確率分布を、入力トラヒックの特性を表している各トラヒックの生起確率を遷移確率として用いて演算する演算手段と、
遷移確率に従って演算する前及び演算した後の各キューの長さにおけるそれぞれの一連の存在確率を記憶する少なくとも２つのメモリ（以下、それぞれを「演算前存在確率メモリ」、「演算後存在確率メモリ」と記す）を有し、
演算手段は、
単位時間内にキュー長をｘ（ｘは０以上の整数）だけ増加させる入力トラヒック長の生起確率をｐ（ｘ）、待ち行列のバッファから出力されることによる単位時間内に減少するキューの長さの最大値をａ、演算する前のキュー長をｍ、演算前存在確率メモリをｑ１（ｍ）（ｍ＝０，１，２，…，Ａ（但し、Ａはメモリの最大キュー長））、演算後存在確率メモリをｑ２（ｍ）（ｍ＝０，１，２，…，Ａ）とした場合に、
キュー長ｍについて、ｙ＝（ｍ＋ｘ−ａ）を求め、その値が負の場合はｙ＝０（ゼロ）とし、演算後のキュー長ｙの存在確率ｑ２（ｙ）の値にｐ（ｘ）×ｑ１（ｍ）を加算する計算を、ｘの値を０（ゼロ）から順に１ずつ加算してｙ＝Ａになるまで行う手段を有する。
【００２６】
本発明（請求項１３）は、請求項１乃至１０のいずれか１項に記載のキュー長分布演算方法の各処理をコンピュータに実行させるためのキュー長分布演算プログラムである。
【００２７】
本発明（請求項１４）は、請求項１３に記載のキュー長分布演算プログラムを格納したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００２８】
上記のように本発明の各キューの長さにおける存在確率分布を求める方法は、従来のモンテカルロシミュレーション法における、擬似ランダム関数を使ったある生起確率分布に従った個々のトラヒック入力を、ひとまとめにして確率として演算する方法である。このため、モンテカルロシミュレーション法で時間が掛かる主要因である、擬似ランダム関数を使ったある生起確率分布に従った個々のトラヒック入力を行わないため、モンテカルロシミュレーション法に比べて、短時間に行うことが可能である。また、非特許文献１に述べられている、擬似乱数の限界の問題もない。
【００２９】
また、本発明の方法は、モンテカルロシミュレーション法をベースとしており、関数の変換等を行わないため、インポータンスサンプリングシミュレーション法に比べて簡単であり、プログラミングに掛かる時間が短いという特徴がある。
【００３０】
以上の特徴から、従って、所望のトラヒックやバッファ量の条件に対して、各キューの長さにおける存在確率分布を、従来に比べて、プログラミングを簡単に短時間に行い、且つ、短時間で演算できるという効果がある。また、これにより得られた存在確率分布を使って、サバイバ関数を短時間で得ることができる。
【図面の簡単な説明】
【００３１】
【図１】本発明のＭ／Ｄ／１の場合（ＡＴＭ通信Ｄ＝１）の場合の概要を示す図である。
【図２】本発明のＭ／Ｇ／１の場合（ＩＰパケット通信）の場合の概要を示す図である。
【図３】本発明のキュー長分布演算装置の構成図である。
【図４】本発明の第２の実施の形態における演算部の演算方法である。
【図５】本発明の１回の存在確率演算を行う第１の実施の形態のフローチャートである。
【図６】本発明の演算用メモリが二つの場合のパラメータで指定された回数で演算を終了する場合の演算処理のフローチャートである。
【図７】本発明の１回の存在確率演算を行う第３の実施の形態のフローチャートである。
【図８】本発明の第３の実施の形態における演算部の演算方法である。
【図９】本発明の第５の実施の形態における演算処理のフローチャートである。
【図１０】本発明の第６の実施の形態における演算処理のフローチャートである。
【図１１】本発明の第７の実施の形態における演算処理のフローチャートである。
【図１２】本発明の第８の実施の形態における演算処理のフローチャートである。
【図１３】本発明の第１０の実施の形態における２状態ＭＭＰＰ／Ｄ／１モデルの例である。
【図１４】従来のモンテカルロシミュレーション法の例である。
【発明を実施するための形態】
【００３２】
以下、図面と共に本発明の実施の形態を説明する。
【００３３】
上述の課題を解決するために、本発明の各キューの長さにおける存在確率分布を求める方法は、モンテカルロシミュレーション法をベースとして、従来のモンテカルロシミュレーションにおける、擬似ランダム関数を使ってある生起確率分布に従って発生させた一つ一つのトラヒック（セルやパケット等）のバッファへの入力を、ひとまとめにして確率で演算する。これにより、モンテカルロシミュレーション法で時間がかかる主要因である「擬似ランダム関数を使ってある生起確率分布に従って発生させた一つ一つのトラヒックのバッファへの入力」を行わずに済み、その結果としてモンテカルロシミュレーション法に比べて、短時間に結果を得ることが可能である。
【００３４】
図１は、バッファの入力トラヒックがＭ／Ｄ／１またはＭＭＰＰ／Ｄ／１の場合の本発明の概要を説明したものである（ＡＴＭ通信の場合、Ｄ＝１）。また、図２は、同様に、Ｍ／Ｇ／１またはＭＭＰＰ／Ｇ／１の場合の本発明の概要を説明したものである（ＩＰパケット通信等の場合）。
【００３５】
なお、本発明では、バッファの長さ（以下、バッファ長）は理論的には無限長であるが、実際の演算では有限長にせざるを得ないため、演算結果に影響を及ぼさない十分長いバッファ長で本発明の演算を行う。
【００３６】
図１４のモンテカルロシミュレーション法と比較して、事前に設定されたある生起確率分布から擬似ランダム関数を使って一つ一つのトラヒックを発生させるのではなく、設定されたある生起確率分布そのものを使って、各キューの長さにおける存在確率分布を求める。これにより、一つ一つのトラヒックの発生を統計的に有効になるまで繰り返す必要がなく、モンテカルロシミュレーション法より極めて短時間に行うことができる。
図１および図２に示すように、演算を繰り返すことにより初期値の影響がなくなり、定常的に安定な各キューの長さにおける存在確率分布を得ることができる。
【００３７】
［第１の実施の形態］
図３は、本発明の第１の実施の形態におけるキュー長分布演算装置の構成を示す。
【００３８】
同図に示すキュー長分布演算装置１は、入出力部２、演算部３と記憶部４から構成される。
【００３９】
記憶部４は、演算前と演算後のそれぞれの一連の存在確率分布を記録する少なくとも二つの存在確率メモリ（図３では、存在確率メモリＡ５と存在確率メモリＢ６）を内包しており、前記存在確率メモリｑ１（ｍ）およびｑ２（ｍ）（但し、ｍ＝０，１，２，...，Ａ）の内容が記録される。すなわち、存在確率メモリｑ１（ｍ），存在確率メモリｑ２（ｍ）は、キュー長＝０（ゼロ）から最大キュー長Ａまでの存在確率を記録できる。
【００４０】
また、記憶部４は、単位時間にキュー長をｘだけ増加させる入力トラヒックの発生確率ｐ（ｘ）を記録するトラヒック確率メモリ７を内包する。トラヒックが発生し（トラヒック入力＝０（ゼロ）、すなわち、トラヒックが発生しないことも含む）、単位時間にキュー長をｘ（ｘは整数）だけ増加させるトラヒックが入力すると、ｑ１（ｍ）はｑ２（ｍ＋ｘ−a）に遷移確率ｐ（ｘ）で遷移する。
【００４１】
さらに、記憶部４は、演算のための各種パラメータを格納する。
【００４２】
例えば、待ち行列のバッファから出力されることによる、単位時間に減少するキューの長さａを格納する。ａの値は、ＡＴＭ通信場合には、単位時間に１セルがキューから出力されるので、ａ＝１となる。また、ＩＰパケット通信では、ａは事前に決められた単位時間に出力するバイト量になる。
【００４３】
また、繰り返し演算の終了を判定するための所定の閾値を格納する。
【００４４】
演算部３は、存在確率メモリｑ１（ｍ）に初期の存在確率分布が設定され、それを「演算前存在確率分布」として、そこから読み出された値とトラヒック確率メモリ７から読み出された値を用いて演算を行い、その結果を「演算後存在確率分布」として、他方の存在確率メモリｑ２（ｍ）に記録する。存在確率メモリｑ１（ｍ）から読み出された値による一連の演算が終了すると、今度は、存在確率メモリｑ２（ｍ）の値を「演算前存在確率分布」として、そこから取得した値とトラヒック確率メモリ７から読み出された値を用いて演算を行い、その結果を「演算後存在確率分布」として、存在確率メモリｑ１（ｍ）に記録する。さらに、演算部３は、存在確率メモリｑ１（ｍ）の値を「演算前存在確率分布」として演算を行い、その結果を「演算後存在確率分布」として、存在確率メモリｑ２（ｍ）に記録する。これらの演算を、演算の終了条件（例えば所定の回数）を満たすまで繰り返す。
【００４５】
また、演算部３は、最後に、演算結果を入出力部２に渡す。この際、演算結果以外に、サバイバ関数を求めて渡すことも可能である。さらに、パラメータとして最大キュー長が入力された場合には、キューから溢れる確率（損失率またはロス率）を渡すことも可能である。
【００４６】
サバイバ関数Ｖ（ｋ）は、演算終了後の各キュー長ｉの存在確率をメモリｑ（ｉ）とするとき、
【００４７】
【数１】
2011078079.tif 000003
で求められる値であり、あるキュー長ｋが示されたとき、それより大きいキュー長の存在確率の和をキューから溢れる確率（損失率またはロス率）と見做すものである。
【００４８】
入出力部２は、演算に必要なパラメータを入力し、演算結果として、各キューの長さにおける存在確率分布、または、サバイバ関数、または、キューから溢れる確率（損失率またはロス率）を出力する。
【００４９】
次に、上記の構成における一連の処理を説明する。
【００５０】
まず、入出力部２から外部パラメータとして、
・ Ａ：最大キュー長；
・ ａ：「単位時間に減少するキュー長」の最大値；
・ ｐ（ｘ）：キュー長をｘ増加させるトラヒック入力の発生確率；
・  演算前存在確率メモリの初期値
などが入力される。
【００５１】
演算前存在確率メモリの初期値は、例えば、ｑ１（０）＝１、ｑ１（ｍ）＝０（ｍ＝１，２，３，…，Ａ））であり、これはバッファが空の状態を表している。尚、初期値は、
【００５２】
【数２】
2011078079.tif 000004
の条件を満たせば、どのようなｑ（ｍ）の組合せでも構わない。
【００５３】
演算部３は、演算後存在確率メモリｑ２（ｎ）の初期値を
ｑ２（ｎ）＝０（ｎ＝０，１，２，３，…，Ａ）
に設定する。
【００５４】
演算部３は、以下の処理を行う。
【００５５】
単位時間内にキュー長をｘ（ｘは０以上の整数）だけ増加させるトラヒックの入力確率をｐ（ｘ）、待ち行列のバッファから出力されることによる単位時間内に減少するキューの長さの最大値をａ、演算する前のキュー長をｍ、演算前存在確率メモリをｑ１（ｍ）（ｍ＝０，１，２，…，Ａ（但し、Ａはメモリの最大キュー長））、演算後存在確率メモリをｑ２（ｍ）（ｍ＝０，１，２，…，Ａ）とした場合に、キュー長ｍについて、ｙ＝（ｍ＋ｘ−ａ）を求め、その値が負の場合はｙ＝０（ゼロ）とし、演算後のキュー長ｙの存在確率ｑ２（ｙ）の値にｐ（ｘ）×ｑ１（ｍ）を加算する計算を、ｘの値を０（ゼロ）から順に１ずつ加算してｙ＝Ａになるまで行う。この例を図４に示す。さらに、これらの計算を、ｍの値を０（ゼロ）から順に１ずつ加算してｍ＝Ａまで繰り返す。この一連の処理が１回の存在確率演算であり、図５に示す通りである。
【００５６】
尚、上記存在確率演算において、ｘの値を、（Ａ−ｍ＋a）から順に１ずつ減算してx＝０（ゼロ）になるまで行ってもよいし、また、ｍの値を、Ａから順に１ずつ減算してｍ＝０（ゼロ）まで繰り返してもよい。
【００５７】
以下に具体例を記す。
【００５８】
例えば、ｍ＝５、ｘ＝２，ａ＝１の場合、すなわち、演算する前の存在確率メモリｑ１（ｍ）のキュー長ｙが５で、単位時間に、存在確率ｐ（２）でキュー長を２増加させるトラヒックが発生し、同時に、待ち行列のバッファから出力されることによって、キュー長が１減少する場合、単位時間経過後の存在確率メモリｑ２（ｍ）のキュー長ｙは、
ｙ＝ｍ＋ｘ−ａ＝５＋２−１＝６
になる。従って、演算前存在確率メモリｑ１（５）から、確率ｐ（２）で、演算後存在確率メモリｑ２（６）に遷移する。
【００５９】
この場合における演算後のキュー長ｙ＝（ｍ＋ｘ−ａ）の存在確率の演算は、演算後存在確率メモリｑ２（６）の値に、演算前存在確率メモリｑ１（５）に確率ｐ（２）を掛けた値を加算する。即ち、
ｑ２（６）＝ｑ２（６）＋ｑ１（５）×ｐ（２）
となる。
【００６０】
なお、ｙの値が負（ｙ＜０）の場合には、そのようなことは実際には起こらないので、ｙ＝０（ゼロ）として扱い、演算後のキュー長ｙ＝０の存在確率の値に、ｑ１（ｍ）×ｐ（ｘ）を加算する。即ち、
ｑ２（０）＝ｑ２（０）＋ｑ１（ｍ）×ｐ（ｘ）
となる。
【００６１】
次に、演算用メモリが２つの場合は、図６に示すように、演算後存在確率メモリだったｑ２（ｍ）を演算前存在確率メモリとし、演算前存在確率メモリだったｑ１（ｍ）を演算後存在確率メモリとして、上記と同様の存在確率演算を１回行う。すなわち、ｘ＝０からｘを順次１ずつ増加させて、計算ステップを行い、ｍ＝０からｍ＝Ａになるまで繰り返す。つまり、奇数回の演算終了後は、ｑ１（ｍ）を演算後存在確率メモリとし、ｑ２（ｍ）を演算前存在確率メモリとする。また、偶数回の演算終了後はｑ２（ｍ）を演算後存在確率メモリとし、ｑ１（ｍ）を演算前存在確率メモリとする。
【００６２】
尚、ｑ１（ｍ）とｑ２（ｍ）を演算前存在確率メモリと演算後存在確率メモリとして交互に使わずに、常時、ｑ１（ｍ）を演算前存在確率メモリ、ｑ２（ｍ）を演算後存在確率メモリとし、存在確率演算後のｑ２（ｍ）の内容を
ｑ１（ｍ）＝ｑ２（ｍ）（ｍ＝０，１，２，…，ｍ）
として複写して次の存在確率演算を行う方法もある。
【００６３】
これらの処理の終了方法としては、図６の外部パラメータに示すように、存在確率演算の回数を予め入力パラメータとして設定する方法がある。
【００６４】
演算用メモリが３つの場合には、１回目の存在確率演算後、ｑ２（ｍ）を演算前存在確率メモリとし、ｑ３（ｍ）を演算後存在確率メモリとして２回目の存在確率演算を行う。３回目の計算はｑ３（ｍ）を演算前存在確率メモリ、ｑ１（ｍ）を演算後存在確率メモリとして、以下同様の処理を行う。演算用メモリが４つ以上の場合も同様である。
【００６５】
［第２の実施の形態］
本実施の形態におけるキュー長分布演算装置の構成は図３と同様である。
【００６６】
本実施の形態では、第１の実施の形態における演算部３の演算において、演算前のキュー長ｍと単位時間に増加するキュー長ｘを変化させる順番を逆にして演算する、すなわち、ある値ｘについて、ｍを順次１ずつ増加または減少させてｙ＝（ｍ＋ｘ−ａ）を求め、演算後のキュー長ｙの存在確率ｑ２（ｙ）の値にｐ（ｘ）×ｑ１（ｍ）を加算する計算を行い、この計算を、ｘを順次１ずつ増加または減少させる演算を行う。
【００６７】
［第３の実施の形態］
本実施の形態におけるキュー長分布演算装置の構成は図３と同様である。
【００６８】
本実施の形態では、第１の実施の形態における演算部３の演算において、演算後存在確率メモリのキュー長ｎについて、ｚ＝ｎ−ｘ＋ａを求め、演算後のキュー長ｎの存在確率ｑ2（ｎ）の値にｐ（ｘ）×ｑ１（ｚ）を加算する計算を、ｘの値を０（ゼロ）から順に１ずつ加算して、ｚが−１になるまで行う。但し、ｚがＡより大きい場合はｑ2（ｎ）に加算する演算を行わない。これらの計算を、ｎの値を０（ゼロ）から順に１ずつ加算してｎ＝Ａまで繰り返す。この一連の処理を図７に示す。
【００６９】
図４に示すように、演算前存在確率メモリのあるキュー長の存在確率を、遷移確率ｐ（ｘ）に従って、演算後のメモリの各キュー長の存在確率に分配するのに対し、図８に示すように、演算後存在確率メモリのあるキュー長に遷移する全ての演算前存在確率メモリの各キュー長の存在確率を、遷移確率ｐ（ｘ）に従って集約する方法である。
【００７０】
また、前述の第１の実施の形態で述べたのと同様なオルタナティブがある。
【００７１】
［第４の実施の形態］
本実施の形態におけるキュー長分布演算装置の構成は図３と同様である。
【００７２】
本実施の形態では、演算部３において、演算後のキュー長ｎと単位時間に増加するキュー長ｘを変化させる順番を逆にして演算する。
【００７３】
すなわち、ある値ｘについて、ｎを順次１ずつ増加または減少させて演算後存在確率メモリのキュー長ｎについて、ｚ＝ｎ−ｘ＋ａを求め、演算後のキュー長ｎの存在確率ｑ2（ｎ）の値にｐ（ｘ）×ｑ１（ｚ）を加算する計算を行い、この計算を、ｘを順次１ずつ増加または減少させる演算を行う。
【００７４】
［第５の実施の形態］
本実施の形態では、繰り返し演算の回数に依らない自動終了方法（１）について説明する。
【００７５】
本実施の形態におけるキュー長分布演算装置の構成は図３と同様である。
【００７６】
本実施の形態では、あるキュー長ｍと閾値が事前にパラメータとして入力され、演算部３において、キュー長ｍにおける存在確率の演算前と演算後の値の差が閾値以下、または、ある閾値以上、または、差の絶対値がある閾値（ＴＨ１）以下になったときに存在確率演算を停止し、演算後の各キューの長さにおける存在確率分布を出力する。
【００７７】
すなわち、演算部３は、上述の第１から第４のいずれかの実施の形態における存在確率演算を繰り返し行い、メモリｑ１（ｍ）とメモリｑ２（ｍ）のあるキュー長における存在確率の演算前と演算後の値の差を求め、トラヒック確率メモリ７に格納しておき、当該差がトラヒック確率メモリ７に格納されている閾値以下、または、閾値以上、または、│ｑ２（Ｍ）−ｑ１（Ｍ）│≧（ＴＨ１）になったとき繰り返し演算を停止し、演算後の各キューの長さにおける存在確率分布をメモリｑ２（ｍ）出力することにより、各キューの長さにおける存在確率分布を求めることができる。
【００７８】
本実施の形態において、差の絶対値がある閾値（ＴＨ１）以下になったときに存在確率演算を停止する場合の一連の処理を図９に示す。
【００７９】
［第６の実施の形態］
本実施の形態では、繰り返し演算の回数に依らない自動終了方法（２）について説明する。
【００８０】
本実施の形態におけるキュー長分布演算装置の構成は図３と同様である。
【００８１】
本実施の形態では、閾値が事前にパラメータとして入力され、演算部３において、上述の第１から第４のいずれかの実施の形態における各キューの長さにおける演算前存在確率と演算後存在確率との差の絶対値を求め、該絶対値の総和がトラヒック確率メモリ７に格納されている閾値以下、または、１と総和の差が閾値（ＴＨ２）以上になった場合に繰り返し演算を停止し、演算後の各キューの長さにおける存在確率分布をメモリｑ２（ｍ）に出力することにより、各キューの長さにおける存在確率分布を求めることができる。
【００８２】
各キュー長における差の絶対値の総和が閾値（ＴＨ２）以下になったときに存在確率演算を停止する場合の一連の処理を図１０に示す。
【００８３】
［第７の実施の形態］
本実施の形態では、演算精度不足の検出方法（１）について説明する。
【００８４】
本実施の形態におけるキュー長分布演算装置の構成は図３と同様である。
【００８５】
演算精度不足の検出方法（１）として、閾値が事前にパラメータとして入力され、演算部３は、１回の存在確率演算終了毎に、存在確率の値の総和を求め、該総和がトラヒック確率メモリ７に予め格納されている閾値以下、または、１と該総和の差が閾値（ＴＨ３）以上になったときに繰り返し演算を停止することにより演算精度不足を検出することができる。本実施の形態における上記の一連処理を図１１に示す。
【００８６】
［第８の実施の形態］
本実施の形態では、演算精度不足の検出方法（２）について説明する。
【００８７】
本実施の形態におけるキュー長分布演算装置の構成は図３と同様である。
【００８８】
演算精度不足の検出方法（２）として、閾値が事前にパラメータとして入力され、演算部３は、１回の存在確率演算終了毎に、存在確率の値の総和を求め、該総和がトラヒック確率メモリ７に予め格納されている閾値を超えたとき、または、該総和と１との差が閾値（ＴＨ４）以上になったときに繰り返し演算を停止することにより、演算精度不足を検出することができる。本実施の形態における上記の一連処理を図１２に示す。
【００８９】
メモリの桁数不足による演算エラーの検出と対策として、演算前と演算後の存在確率分布を記録する存在確率メモリｑ１（ｍ）、存在確率メモリｑ２（ｍ）、または、演算用レジスタの各サイズ（仮数部や指数部のビット数）を拡張し、演算精度不足が検出されない場合に、各キューの長さにおける存在確率分布を求めることができる。
【００９０】
最後に、上記のようにして求められた演算結果（または、サバイバ関数を）入出力部２に渡す。
【００９１】
［第９の実施の形態］
本実施の形態におけるキュー長分布演算装置の構成は図３と同様である。
【００９２】
前述の実施の形態では、バッファが無限長の場合について説明したが、本実施の形態では、有限バッファにおけるキュー長分布演算及び損失確率を求める方法を示す。第１の実施の形態では、無限バッファを想定し、キューの長さは理論的には無限長であるが、実際の演算では有限長にせざるを得ないため、演算結果に影響を及ぼさない十分長いキュー長で演算を行う。しかし、本実施の形態では、理論的にもバッファからの廃棄を伴う有限バッファを対象としており、このため、演算結果は、無限バッファを想定した「各キューの長さにおける存在確率分布」や「サバイバ関数から求めた廃棄率」の値とは異なる。
【００９３】
本実施の形態は、以下の２つのステップで行う。
【００９４】
（１）有限のキュー長で、第１の実施の形態と同様な繰り返し演算を行う。このとき、ある確率でバッファ溢れによる損失が発生するが、最大キュー長を越える位置への遷移は実際には起こらないため、損失になる遷移は全て最大キュー長への遷移にする。この演算を「各キューの長さにおける存在確率分布」の値が一定の値に漸近するまで繰り返す。
【００９５】
（２）一定の値に漸近した「各キューの長さにおける存在確率分布」を演算前の値ｑ1（ｍ）とし、１回だけ演算を行う。但し、最大キュー長を超える位置への遷移は全てトラヒックの損失となり、最大キュー長Ａを超えた各キュー長に遷移する場合の遷移前の各キュー長の生起確率ｑ1（ｍ）と遷移確率ｐ(x)とその遷移によって損失となるトラヒックのデータグラム（パケット、イーサネットフレーム、セル等）の数ｄの積の総和が損失確率Ｌになる。即ち、
【００９６】
【数３】
2011078079.tif 000005
となる。
【００９７】
［第１０の実施の形態］
本実施の形態におけるキュー長分布演算装置の構成は図３と同様である。
【００９８】
ここでは、これまで述べてきた実施の形態を使ってＭ／Ｄ／１の損失確率を得た後、ＭＭＰＰ／Ｄ／１の場合の損失確率を計算する方法について説明する。
【００９９】
ＭＭＰＰ／Ｄ／１モデルは、複数の異なる密度の固定長トラヒック入力（Ｍ／Ｄ／１）がランダムに切り替わるモデルと捉えることができ、その損失確率を各トラヒック入力の損失確率に重み付けした和として算出する。
【０１００】
図１３は、本発明の第１０の実施の形態における２状態ＭＭＰＰ／Ｄ／１モデルの例である。これまでの実施の形態で説明した方法を用いて求めた状態０の損失確率をＬ０、状態１の損失確率をＬ１、状態０から状態１への遷移確率をｒ０１、状態１から状態０への遷移確率をｒ１０とするとき、この場合の損失確率Ｌａを、
【０１０１】
【数４】
2011078079.tif 000006
で算出する。
【０１０２】
本発明の各キューの長さにおける存在確率分布を求める方法は、従来のモンテカルロシミュレーションにおける、擬似ランダム関数を使ったある生起確率分布に従った個々のトラヒック入力を、ひとまとめにして確率として演算する。これにより、モンテカルロシミュレーション法で時間がかかる主要因である擬似ランダム関数を使ったある生起確率分布に従った個々のトラヒック入力を行わずに済み、その結果としてモンテカルロシミュレーション法に比べて、短時間に結果を得ることが可能である。
【０１０３】
また、本発明は、モンテカルロシミュレーション法をベースとしており、関数の変換等を行わないため、インポータンスサンプリングシミュレーション法に比べて簡単であり、プログラミングに係る時間が短い、という特徴がある。
【０１０４】
また、本発明では、予め閾値を定めることにより、必要な精度になったときに計算を停止することができる。
【０１０５】
なお、上記の演算部３の動作をプログラムとして構築し、キュー長分布演算装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１０６】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【０１０７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１０８】
本発明は、待ち行列における各キューの長さにおける存在確率分布を求める技術に適用可能である。
【符号の説明】
【０１０９】
１  キュー長分布演算装置
２  入出力部
３  演算部
４  記憶部
５  存在確率メモリＡ
６  存在確率メモリＢ
７  トラヒック確率メモリ
【図１】
2011078079.tif 000007
【図２】
2011078079.tif 000008
【図３】
2011078079.tif 000009
【図４】
2011078079.tif 000010
【図５】
2011078079.tif 000011
【図６】
2011078079.tif 000012
【図７】
2011078079.tif 000013
【図８】
2011078079.tif 000014
【図９】
2011078079.tif 000015
【図１０】
2011078079.tif 000016
【図１１】
2011078079.tif 000017
【図１２】
2011078079.tif 000018
【図１３】
2011078079.tif 000019
【図１４】
2011078079.tif 000020