研究速報
ヒックの確率法則を必要としない IS 法の適用が望ま待ち行列からの退去過程に対する Blind IS 法による特性評価
森口健一†（正員）中川 健治††a)（正員）

棄却することによりシミュレーション系列を生成する．

Simulation

一般的に待ち行列からの退去過程は複雑な統計的性

Ken-ichi MORIGUCHI†††† a)質をもち，通常の IS 法の適用が困難である．そこで, Regular Members

本研究では，1 段目の待ち行列を M/D/1 待ち行列あ株式会社富士通プライムソフトテクノロジ，名古屋市

Fujitsu

Primesoftware

Technologies

Ltd,

Aoi

1–16–38,Higashi-ku, Nagoya-shi, 461–0004 Japan††

トラヒックの確率法則の知識を必要としない IS 法
は Blind IS 法と呼ばれ [1]，観測系列を受入れまたはPerformance Evaluation for a Tandem Queue by Blind IS

and Kenji NAKAGAWAれる．

るいは 2 状態 MMPP/D/1 待ち行列とし，1 段目の待ち行列からの退去過程を入力とするサービス時間一定

長岡技術科学大学電気系，長岡市

Department of Electrical Engineering, Nagaoka University ofの 2 段目の待ち行列に Blind IS 法を適用してそのセTechnology, Nagaoka-shi, 980–2188 Japan

ル廃棄率特性の評価を行う．

a) E-mail: nakagawa@nagaokaut.ac.jp

あらまし
−10

される 10ATM によるマルチメディア通信で要求以下のセル廃棄率を，通常のモンテカルロシミュレーション法（MC 法）で求めるのは困難である．また，インポータンスサンプリングシミュレーション法（IS 法）も，対象となるトラヒックの確率法則が未知の場合には適用することができない．一方，

Blind IS 法 [1] はトラヒックの確率法則を知らなくても実行できる IS 法であり，未知のトラヒックに対して適用できる．本研究では，待ち行列に対する BlindIS 法において，到着数に対する新たな受入棄却関数を提案し，前段の待ち行列からの退去過程を入力とする

2. 従来法によるシミュレーション
2. 1 IS シミュレーション
IS 法は所望の事象が起こりやすいようなシミュレーション分布を用いて事象を発生させ，得られた標本値を重み関数で補正して所望の確率を求める [2]．もとの分布の確率密度を p(x)，シミュレーション分布の確率密度を q(x) とすると，シミュレーション分布ともとの分布の変化分を重み関数 p(x)/q(x) によって補正す
る．重み関数に p(x) が用いられており，もとの分布の知識なしでは推定値を得ることができない．

2. 2 Blind IS シミュレーション
Blind IS 法 [1] では，観測系列 {Xi } を受入れまた待ち行列の 10−10 以下のセル廃棄率の推定値を得るは棄却して，所望の事象が起こる割合が大きくなるよことを目的とする．

は 0 ≤ h(x) ≤ 1 を満足する関数 h(x) を用いる．こキーワード Blind IS，待ち行列からの退去過程，セル廃棄率，大偏差理論1. ま え が きATM（Asynchronous Transfer Mode）ネットワー
クにおいてマルチメディア通信を実現するには 10−10以下のセル廃棄率が要求される．しかし一般的なモンテ
カルロ（MC：Monte Carlo）法によるシミュレーショ
ンでは計算時間と乱数の精度の問題により 10−10 以下のセル廃棄率を求めるのは困難である [2]．そこでインうなシミュレーション系列を生成する．受入れ/棄却にの h(x) を受入れ棄却関数と呼ぶ．{Ui } を区間 [0, 1]上の一様乱数系列として Ui ≤ h(Xi ) ならば Xi を受け入れ，Ui > h(Xi ) ならば棄却する．受け入れられたものだけの系列をシミュレーション系列として用いる．もとの系列の確率密度を p(x) とおくと，シミュレーション系列の確率密度 q(x) はq(x) =p(x)h(x)a(1)

ポータンスサンプリング（IS：Importance Sampling）となる．ここで，a は {Xi } の受入れ確率である．こ法の適用を考える．IS 法はもとのトラヒックの分布をのとき Blind IS 法における重み関数は−10変化させたシミュレーション分布を用いて 10以下のセル廃棄率を推定することができる．IS 法を適用するためには，シミュレーション分布の決定のためにトラヒックの確率法則を知っている必要があるが，実際のシステムではその複雑さゆえにトラヒックの確率法則を見出すことは現実的ではない．そのため，トラ
電子情報通信学会論文誌 B Vol. J85–B

p(x)
ap(x)
==q(x)
p(x)h(x)/ah(x)(2)となり p(x) に依存しない．したがって，もとの系列の確率法則が未知の場合にも適用することが可能である．すなわち，一般的に複雑なトラヒックとなり通常の IS 法の適用が困難な待ち行列からの退去過程に対No. 6 pp. 1005–1009 2002 年 6 月1005

電子情報通信学会論文誌 2002/6 Vol. J85–B No. 6を観測し，一様乱数 u を発生させる．u ≤ h(x) ならば x 個の到着をすべて受け入れ，u > h(x) ならば x個の到着をすべて棄却する．受け入れられた系列を入力として IS 法を適用する．
図1

Poisson または MMPP を入力とする直列待ち行列

Fig. 1

Tandem queues with Poisson or MMPP input.

例えば，式 (3) で t = 2 とすると，x = 0, 1 のときには確率的に受け入れられ，x ≥ 2 のときには確実に受け入れられる．その結果，到着率が大きくなって待しても適用することができる．ここで，受入れ確率 aち行列長が長くなり，廃棄事象が発生する頻度が高くは推定する必要があるが，情報量としてはそれほど多なって小さい廃棄確率を推定することが可能となる．

くない．

受入れ棄却関数として式 (3) の形の関数を用いる（ 1 ） Blind IS 法の待ち行列への適用

理由は，文献 [1] で独立同分布（i.i.d：independent待ち行列長が 0 のときから次に 0 になるときまで

and identically distributed）確率関数に対する Blind
IS 法において効率的であることが示されている関数
hB (x)（文献 [1]，p.2882）を参考にしたためである．
3. 2 タイムスロット幅 w と h(x) のしきい値 tをサイクルという．待ち行列に対する従来の Blind IS法 [1] においてはサイクル単位での受入れ/棄却が提案されている．サイクル単位での受入れ/棄却というのは，サイクルのなかで待ち行列長がある値を超えたらル全体を棄却するという方法である．しかし到着率の2 段目の待ち行列への到着数は 1 段目の待ち行列のサービス時間当り 0 または 1 である．すなわち，2 以上の到着がないため式 (3) を用いた受入れ/棄却では低い待ち行列では待ち行列長がある程度以上は長くな待ち行列長が長くならない．そこで，シミュレーショそのサイクル全体を受け入れ，そうでなければサイクらないので，サイクル単位での受入れ/棄却ではほとンの単位時間であるタイムスロット幅を 1 段目の待ちんど受入れが行われず，シミュレーション系列を生成行列のサービス時間よりも長くする．タイムスロットすることができない．

幅を 1 段目の待ち行列のサービス時間の w 倍とする

（ 2 ） 退去過程への適用と，単位時間当りの到着数は 0〜w となり，式 (3) を

1 段目の待ち行列からの退去過程を入力とする 2段目の待ち行列に Blind IS 法を適用することを考える．1 段目の待ち行列への入力は Poisson 過程またはMMPP（Markov Modulated Poisson Process）とし，サービスはサービス率 µ1 の一定サービスとする．ま用いた受入れ/棄却が有効となる．
しかし，w を大きくしすぎると逆に待ち行列長が長くならない．w を大きくすることにより，到着数が増えて受入れ確率が大きくなり棄却されなくなる．棄却が行われなければ到着率はサービス率よりも小さいまた，2 段目の待ち行列のサービスはサービス率 µ2 の一まとなり，待ち行列長が長くならない．そこで，式 (3)定サービスとする．λ < µ2 < µ1 とする（図 1 参照）．

におけるしきい値 t を変化させて受入れ確率をおさえる．t を大きくすれば確実に受け入れられる到着が減

3. 提案する Blind IS 法
3. 1 受入棄却関数

り，受入れ確率が小さくなる．

待ち行列に対する従来の Blind IS 法 [1] ではサイク

タイムスロット幅 w としきい値 t を適切に決める

ル単位の受入れ/棄却が行われる．しかし到着率が小ことにより良い推定値を得ることができる．適切なタさい場合にはサイクル単位の受入れ/棄却では待ち行イムスロット幅としきい値の組はトラヒックパラメー列長が長くならないという問題がある．そこで，到着タにより変化するが，良い推定値が得られる場合が多数単位での受入れ/棄却を行う [3]．

かったタイムスロット幅 w = 3，しきい値 t = 3 を用ある長さの時間区間をタイムスロットと定義し，1タイムスロット中の 2 段目の待ち行列への到着数を xとして受入棄却関数 h(x) を次のように定義する．

h(x) ≡ min[eθ(x−t) , 1](3)いる．

3. 3  の 決 定式 (3) において θ が推定値及び分散に大きな影響を与える．そのため適切な θ を選ぶことが重要である．既知のトラヒックに対しては large deviation theory よここで，θ は正の実数，t は正の整数であり，これらり待ち行列長の変化量のモーメント母関数 M (θ) = 1の値は後で決定する．1 タイムスロット中の到着数 xを満たす θ が最適な θ となる [2]．最適な θ とは推定1006

レター

値の分散が最小となる θ である．
いま，待ち行列からの退去過程を入力とする 2 段目の待ち行列を考えている．幅 w のタイムスロットにおける 2 段目の待ち行列への到着数を x とし，x のタイムスロットごとの分布を p(x) とする．待ち行列長が十分長いとき，1 タイムスロット当りの待ち行列長の変化は x − wµ2 となるので，そのモーメント母関数はM (θ) =w


p(x)eθ(x−wµ2 )(4)x=0となる．そして方程式 M (θ) = 1 を満たす θ を用いる．

θ の決定のために 1 タイムスロットの到着数分布p(x) を推定してそれを利用しているが，退去過程の確

図 2 M/D/1 からの退去過程のセル廃棄率に対する推定値の比較
Fig. 2 Estimation for the cell loss probability of thedeparture process from M/D/1.

率過程としての統計的性質のすべてを推定しているわ
けではない．つまり，トラヒックに関する一部の情報だけで θ を決定しているのである．そこで，p(x) がトラヒックに関するすべての統計的性質でないことを示すために，1 タイムスロットの到着数分布が p(x) となる（相関を考慮しない）Bernoulli モデルの MC 法によるセル廃棄率の推定値と比較する．

4. シミュレーションと考察
1 段目の M/D/1 の到着率 λ, サービス率 µ1 及び 2段目の待ち行列のサービス率 µ2 ，タイムスロット幅w，受入れ棄却関数 h(x) のしきい値 t を表 1 に示す．
また 1 段目が 2 状態 MMPP/D/1 の場合の各状態の到着率 λi , 状態遷移確率 rij ，i, j = 0, 1 と µ1 ，µ2 ，w，t を表 2 に示す．

図 3 MMPP/D/1 からの退去過程のセル廃棄率に対する推定値の比較
Fig. 3 Estimation for the cell loss probability of thedeparture process from MMPP/D/1.

表 1，表 2 のそれぞれの場合における Blind IS 法による 2 段目の待ち行列のセル廃棄率の推定結果を，
図 2〜図 4 に示す．また 1 段目の待ち行列からの退去Table 1

表 1 シミュレーションパラメータ（1）Parameters of tandem queues and blind IS (1).
case 1case 2

Table 2

λ0.48
0.30

µ1
1.0
1.0µ20.60.6w
33t33

表 2 シミュレーションパラメータ（2）Parameters of tandem queues and blind IS (2).

case 3case 4case 5case 6λ00.6
0.3
0.90.9

λ1
0.4
0.1
0.1
0.1

r01
0.9
0.9
0.1
0.1

r10
0.1
0.1
0.1
0.1

µ1
1.0
1.0
1.0
1.0

µ2
0.6
0.6
0.60.6w
33315t33315

図 4 パラメータ w と t の変更による推定精度の改良
Fig. 4 Improvement of the estimation by altering theparameters w and t.

1007

電子情報通信学会論文誌 2002/6 Vol. J85–B No. 6

過程を，θ の決定に用いた p(x) に従う Bernoulli モデルと考えた場合のセル廃棄率も示す．
図 2，図 3 において 1 段目の M/D/1 からの退去過程を Bernoulli モデルとした場合には良い推定ができていないが，提案法による推定値は精度の良い推定値が得られている．提案法では，M/D/1 からの退去過程を入力とする場合にはほとんどすべての場合において精度の良い推定ができていることを確認した．また，

MMPP/D/1 からの退去を入力とする場合にはバース
ト性の低い場合に良い推定値が得られた．退去過程では相関が生じるが Bernoulli モデルでは相関を考慮し
図5

M/D/1 からの退去過程のセル廃棄率に対する推定値の分散の比較
Fig. 5 Variance of estimates for the cell loss probabilityof the departure process from M/D/1.ていない．それに対して提案法では，退去過程の系列を用いてシミュレーションを行っているので，退去過程の相関を考慮した方法になっている．
図 4 では case 5 と case 6 の比較を示している．case5, case 6 とも同一の MMPP とサービス率を用いているが，タイムスロット幅 w と式 (3) のしきい値 t が異なる．MMPP のバースト性が高いので，case 5 においては良い推定値が得られていないが，case 6 のようにタイムスロット幅 w = 15，しきい値 t = 15 とすることによって精度の良い推定値が得られている．
また，いずれの場合にも提案法では MC 法で得られていない 10−10 以下のセル廃棄率を推定できている．
図 5 に図 2 の case 1 の推定値の分散を，図 6 に

図 6 MMPP/D/1 からの退去過程のセル廃棄率に対する推定値の分散の比較（case 4）
Fig. 6 Variance of estimates for the cell loss probability ofthe departure process from MMPP/D/1 (case 4).

図 3 の case 3 の推定値の分散を，図 7 に図 4 の case
6 の推定値の分散を示す．待ち行列長が短いときにはMC 法による分散が小さくなっているが，待ち行列長が長くなるにつれ提案法の分散のほうが小さくなっており，提案法が稀少確率の推定に有効であることがわ
かる．
以上の例においては MC 法との比較を示したため，10−10 以下の値で比較することができない．そこで，

表 3 M/M/1 からの退去過程に対する P (Q > q) の理論値と提案法による推定値の比較（λ = 0.5, µ1 =µ2 = 1）
Table 3 Comparison of the theoretical value ofP (Q > q) and the estimation by the proposed method for the departure processfrom M/M/1 (λ = 0.5, µ1 = µ2 = 1).

図 7 MMPP/D/1 からの退去過程のセル廃棄率に対する推定値の分散の比較（case 6）
Fig. 7 Variance of estimates for the cell loss probability ofthe departure process from MMPP/D/1 (case 6).

1008

q
0510
1520

P (Q > q) theoretical
5.0 × 10−1
1.2 × 10−3
2.3 × 10−6
4.3 × 10−9
6.9 × 10−12

P (Q > q) proposed
5.1 × 10−1
1.3 × 10−3
2.2 × 10−6
3.2 × 10−9
5.7 × 10−12 .

レター

1 段目のサービスをサービス率 µ1 の指数サービスとしたときの退去過程を，サービス率 µ2 の一定サービスをもつ 2 段目の待ち行列に入力したときのセル廃棄率を考える．その廃棄率の理論値と提案法による推定値との比較を表 3 に示す．

今後の課題としては，推定精度の良くなかった場合，すなわち 1 段目の待ち行列がバースト性の高いMMPP/D/1 の場合についての検討があげられる．また，θ の決定のために 1 タイムスロットの到着数分布p(x) を推定しているが，このような推定をなるべく行

1 段目からの退去過程は Poisson 過程になるので，2わない方法について検討する．更に，これまでに行っ段目の待ち行列における廃棄率の理論値は容易に得らた数値例では，到着率が低い場合に安全側となり，到れる．提案法の結果は，λ = 0.5, µ1 = µ2 = 1 とし，着率が高い場合に危険側となる傾向が見られた．この100 個の標本の平均値を示している．低い確率の値にことに関しても検討したい．
文

対してやや危険側になる場合があるが，ほぼ精度の良い推定値が得られていることが確認できる．
5. む す び
M/D/1 待ち行列及び MMPP/D/1 待ち行列からの−10退去過程を入力とする待ち行列に対して，10以下[1]generative Processes,” IEEE Trans. Information Theory, vol.44, no.7, pp.2877–2891, Nov. 1998.
[2]

よる推定値よりも分散が小さくなり，提案法が稀少確率の推定に有効であることがわかった．

小川耕司，中川健治，“MMPP/D/1 キューイングにおける最適 IS シミュレーション分布，” 信学論（B-I），vol.J80-のセル廃棄率の推定値を Blind IS 法によって得ることができた．また，待ち行列長が長い場合に MC 法に献

J. Bucklew, “The Blind Simulation Problem and Re-[3]B-I, no.2, pp.64–73, Feb. 1997.
小柳津真，中川健治，“待ち行列に対するブラインド IS シ” 長岡技科大課題研報，March 2000.
ミュレーション，（平成 13 年 9 月 19 日受付，14 年 1 月 7 日再受付）

1009