論 文
FIFO キューのパケット廃棄確率に対する IS 法を用いたオンライン

推定小林 信裕†

中川 健治†† a)

On-line Estimation by Importance Sampling for the Packet Loss Probability of
FIFO Queue
Nobuhiro KOBAYASHI† and Kenji NAKAGAWA††a)

あらまし 本論文では，FIFO キューのパケット廃棄確率を NS-2 を用いた IS シミュレーションによって推定する新たな方法を提案する．従来の IS 法のようにパケットの到着レートを上げるのではなく，処理レートを下げてキュー長を伸ばし廃棄事象を多く発生させる．それによって，各ノード内で IS 法を実行できるため，オンラインでの廃棄確率の推定が可能になる．MC 法と従来 IS 法及び提案 IS 法によるシミュレーション結果を比較し考察する．
キーワード

FIFO キュー，パケット廃棄確率，IS シミュレーション，オンライン推定

1. ま え が き

ン法を適用する．IS 法は実際の確率分布と異なる確率

インターネットにおいて最も多く利用されている得られた値を補正して目標とする確率を得る方法でFIFO (First In First Out) キューにおけるパケット

ある [1], [5]．筆者らはこれまでに，NS-2 による DRR

廃棄確率をネットワークシミュレータ NS-2 を用いて(Deﬁcit Round Robin) スケジューラのパケット廃棄推定する．

確率推定に対して IS 法を適用し，その特性を評価し分布を使用して小さい確率の事象をより多く発生させ，NS-2 を用いてパケット廃棄確率シミュレーションをた [4]．

行う場合，モンテカルロ (Monte Carlo, MC) シミュ

通常，IS 法では，パケット廃棄事象が MC 法より

レーション法によるのが一般的である．NS-2 に MCも多く発生するように到着レートを上げてシミュレー法を適用すると，シミュレーションモデルの確率的構

ションを行い，得られた値を補正して真の廃棄確率に造を直接利用することができ，簡単にプログラムを作

対する不偏推定値を得る．到着レートを適切な値に設成することができる．しかし，ITU-T Rec. Y.1541 [3]定することによって，推定値の分散がもとの MC 法にで規定されている最も厳しいクラスのパケット廃棄確よる推定値の分散よりも小さくなる．分散は発生する率である 10−5 以下の小さい廃棄確率の場合，注目す

標本数に反比例するので，分散を同程度にすれば IS

るパケット廃棄事象がなかなか発生せず，シミュレー法は MC 法よりも標本数が少なくて済む．すなわち，ションに時間がかかり，また推定値の信頼性も低い．

シミュレーションが高速化される [1], [4]．

そこで，NS-2 によるシミュレーションの高速化と以上が IS 法の一般的な説明であるが，その IS 法

推定値の推定精度の向上のためにインポータンスサンの問題点について考えてみよう．上記のような IS 法

プリング (Importance Sampling, IS) シミュレーショ

では，到着レートを上げて廃棄事象が頻繁に発生するようにしているのであるが，より現実的なシミュレー†（株）イートラスト，長岡市
eTRUST, Nagaoka-shi, 940–0871 Japan††

ト廃棄確率の評価において，到着レートを上げること

長岡技術科学大学，長岡市
Nagaoka University of Technology, Nagaoka-shi, 940–2188
Japana) E-mail: nakagawa@nagaokaut.ac.jp

電子情報通信学会論文誌

ション，あるいは実際のネットワークにおけるパケッが可能だろうか．ネットワーク全体をモデル化してシミュレーションをオフラインで考えれば可能である．

c 一般社団法人電子情報通信学会 2012
B Vol. J95–B No. 5 pp. 627–635 

627電子情報通信学会論文誌 2012/5 Vol. J95–B No. 5

しかし，ユーザが送信するトラヒックをそのまま利用発生させて，重み関数によって補正して P (Q > q) のしてオンラインで推定を行う場合には到着レートを上推定値を得る [1]．P  を用いてシミュレーションを行

げてユーザトラヒックを実際と異なるものにすることうので，P  をシミュレーション分布という．

はできない．
ユーザトラヒックを変形しないでそのまま観測して高速なシミュレーションはできないだろうか．もし，待ち行列における IS 法では裾確率 P (Q > q) の推定をサイクル単位で考える [2]．サイクルとはキュー長が正である一つの時間区間のことである．

それができればパケット廃棄確率を高速に推定して，

2. 1 キュー長の裾確率に対する IS 推定値

得られた値を用いてリアルタイムに，例えば，パケッ

元の分布 P によって生成されたパケットの処理終

ト送信のレート制御に使用することができる．

了時点を t(1), t(2), · · · , t(j), · · · とする．シミュレー

IS 法の重要な点はパケット廃棄事象を多く発生さ

ション分布 P  によって生成されたパケットによる時せることである．パケットの到着レートを増加させる

刻 t(j) でのキュー長を Q (t(j)) とすると，P (Q > q)のではなく，処理レートを低下させることによってもに対する IS 推定値 P̂IS は以下のように与えられる [2]．

キュー長を伸ばして廃棄事象を多くすることができる．この方法の特徴はユーザトラヒックを変化させず，P̂IS =

ネットワーク側だけの処理によって IS 法を実現できることである．具体的には，ネットワーク側では実際のパケット処理と並行して仮想的に遅いパケット処理を行ってキュー長を伸ばす．IS 法では，統計量としてMC 法よりも長くなったキュー長が得られればよいのだから，これを NS-2 への付加的なカウンタとして実現する．

M
1 1 
1q (Q (t(j)))W (j)·D M m=1 j=1

1 
W (j)
M̃ m=1 j=1
P Q (t(1)), · · · , Q (t(j))

W (j) =  
P Q (t(1)), · · · , Q (t(j))

(1)

M̃

D=

(2)

(3)

こ こ で ，M 及 び M̃ は サ イ ク ル 数 を 表 す．ま た ，

遅いパケット処理をするのに新たに別のタイマー

1q (Q (t(j))) は 条 件 Q (t(j)) > q が 成 り 立 つ と きを設けてパケット処理の時間を長くする方法はとら

1，そうでないとき 0 となる関数，すなわち，事象ない．NS-2 が event driven なシミュレータであるこ{Q > q} の指示関数を表す．W (j) は重み関数であり，との特徴を生かして，FIFO キューへのパケット到着

D は平均サイクル長の IS 推定値である．(1) において

(enqueue) イベントとキューからの送出 (dequeue) イ

P̂IS の 1/D を除く部分は 1 サイクル中でキュー長が q

ベントのみを観測時点としてキュー長を変化させ，最を超えている時間の長さの IS 推定値である [2]．また，適な IS シミュレーションを行う．

(1) の j に関する和は以下のようにする．待ち行列に

そこで，本研究の目的を下記の 3 点とする．

対する IS 法において P  によるトラヒック密度が 1 よ(I) FIFO キューのパケット廃棄確率を NS-2 を用いり大きい場合は IS のキュー長 Q が時間とともに発散

た IS シミュレーションによって推定する．

してしまう．そこで，(1) において j = 1, 2, · · · とし(II) 到着レートを上げるのではなく処理レートを下ていき，1q (Q (t(j))) = 1，すなわち Q (t(j)) > q とげてキュー長を MC 法よりも伸ばし廃棄事象を多く発なる番号 j を適当な回数観測したら観測を打ち切って生させる．それによってオンライン推定を可能にする．

サイクルを終了させる．ここで，適当な回数とは，統(III) MC 法と IS 法によるシミュレーション結果を比較し，考察する．

2. 待ち行列に対する IS シミュレーション

計量




j=1 1q (Q (t(j)))W (j) が十分に収束したと考えられる回数である．経験的にこの回数は約 20 程度である．このように途中でサイクルを打ち切る方法を
ダイナミック IS という [2], [4]．

IS 法を待ち行列に適用する一般的な方法について考時点 t(j) は元の分布 P によって生成したパケット

える．定常状態におけるキュー長を Q とし，Q があるの処理終了時点であるが，P  の選び方によっては t(j)値 q を超える確率 P (Q > q) に対する IS 法を考える．

は Q にとって特に意味のない時点となるかもしれな

P (Q > q) をキュー長の裾確率という．q が大きいと

い．しかし，{t(j)}j=1,2,··· が十分に密な時点列であれ

事象 {Q > q} はなかなか発生しないので，元の分布ば，式 (3) の重み関数 W (j)，すなわちゆう度比の計

P と異なる別の分布 P  を用いて事象 {Q > q} を多く
628

算は十分に精度が高いといえる．

論文／FIFO キューのパケット廃棄確率に対する IS 法を用いたオンライン推定

2. 2 最適シミュレーション分布は μ∗ = λ となり，到着率と処理率を入れ替えたもの

離散時刻 t(j) におけるもとの分布 P によるキュー長となる．元のトラヒック密度は ρ = λ/μ < 1 なので，を Q(t(j)), j = 1, 2, · · · とする．Q(t(j)) が Markov

最適シミュレーション分布では ρ∗ = μ/λ > 1 となる．

連鎖をなすとし，Q(t(j − 1)) > 0 のとき i.i.d.（独立つまり，不安定なキューになりキュー長 Q∗ は時間と同分布）確率変数 X によってともに発散してしまう．そこで，事象 {Q∗ > q} を十Q(t(j)) = Q(t(j − 1)) + X, j = 1, 2, · · ·(4)と表されているとする．つまり，キュー長の確率は X
によって決まる．このとき，P̂IS の分散 V [P̂IS ] を最小にする X ∗ は次のように与えられる [1]．

3. FIFO キューのモデル化
本章では，FIFO キューへのパケット到着と Byte

X の モ ー メ ン ト 母 関 数 を ϕX (θ) ≡ E(e ) = θx
x e P (X = x) とし，P (X = x) に対する指数
θX

単位でのパケット処理をモデル化する．

3. 1 パケット到着のモデル化
キューに到着するトラヒックには K 種類のパケッ

的測度変換をP (X  = x) =分に多く観測したら 2. 1 で述べたダイナミック IS に
よってサイクルを強制的に打ち切る．

eθx P (X = x), θ∈R
ϕX (θ)ト長 lk [Byte]，k = 1, · · · , K のパケットが含まれて(5)いるとする．パケット長 lk のパケットの到着レートをΛk [Byte/s] とする．フロー数は特に考慮せず，すべてと定義する．次の定理が成り立つ [1]．

[定理 A] V [P̂IS ] を最小にする確率変数 X  = X ∗ は指∗数的測度変換 P (X ∗ = x) = eθ x P (X = x) によって与えられる．ここで，θ∗ は方程式 ϕX (θ∗ ) = 1, θ∗ > 0の解である．

のフローを多重化した結果のトラヒックにおけるパケット長 lk のパケットの到着レートを Λk と考えればよい．
パケット長 lk のパケットは到着率 Λk /lk [packet/s] のポアソン過程に従うとする．

3. 2 パケット処理のモデル化

以下では，分散 V [P̂IS ] を最小にするシミュレーショ

到着したパケットはサイズ ∞ のバッファに格納さン分布を「最適」シミュレーション分布という [6], [7]．

れ，到着順に処理される．処理レートを μ [Byte/s] と2. 2. 1 M/M/1 の最適シミュレーション分布する．本論文では，有限のバッファサイズ q をもつ

定理 A を，例えば，M/M/1 待ち行列に応用してFIFO キューにおけるパケット廃棄確率を，バッファ最適シミュレーション分布を計算すると次のようにな

サイズ無限大の FIFO キューにおけるキュー長の裾確る [1]．

率 P (Q > q) で近似する．そこで，本論文では便宜上，到着率を λ とし，処理率を μ とする．M/M/1 のキュー長変化を連続時間マルコフ連鎖として表現した

P (Q > q) をパケット廃棄確率と呼ぶことにする．
以上の定義に基づいて，FIFO キューはパラメータ

ものを一様化 [5] によって離散時間マルコフ連鎖とす
ると，式 (4) の X は次のような確率変数となる．


X=

+1,

at prob. λ̄−1,at prob. μ̄

S = (Λk , μ)k=1,··· ,K(8)によって規定されると考える．

(6)

3. 3 FIFO キューにおけるキュー長変化の確率的構造

ここで，λ̄ = λ/(λ + μ)，μ̄ = μ/(λ + μ) である．Xのモーメント母関数は ϕX (θ) = λ̄eθ + μ̄e−θ となるので，ϕX (θ∗ ) = 1，θ∗ > 0 を解いて θ∗ = log(μ̄/λ̄) と∗∗

時刻 t においてキュー内にあるパケット長 lk の全パ
ケットの合計バイト数を Qk (t) [Byte]，k = 1, · · · , Kとし，Q(t) =K

k=1 Qk (t) [Byte] とおく．パケットなる．したがって，最適な X は定理 A の P (X =の処理終了時刻を td (1), td (2), · · · , td (j), · · · とする．

x) = eθ x P (X = x) より
+1, at prob. μ̄X∗ =−1, at prob. λ̄

ここで，添字の d はキューからの送出 (dequeue) を表∗

す．時刻 td (1) に処理が終了するパケットの処理開始(7)

時刻を td (0) とおく．
時間区間 td (j−1) < t ≤ td (j) に処理されるパケットとなる．つまり，元の到着率 λ と処理率 μ に対して，のパケット長を L(j) [Byte] とする．そして，その時間

最適シミュレーション分布の到着率は λ∗ = μ，処理率

区間 td (j − 1) < t ≤ td (j) に到着するパケット長 lk の629

電子情報通信学会論文誌 2012/5 Vol. J95–B No. 5

パケットの個数を nk (j) 個とし，A(j) =K

k=1 nk (j)lk

とおく．A(j) は時間区間 td (j − 1) < t ≤ td (j) に到

3. 4 FIFO キューの最適シミュレーション分布
FIFO キューのパケット廃棄確率に対する IS 推定値

着する全バイト数を表す．このとき，次の漸化式が成P̂IS の分散を最小にするシミュレーション分布，すな

り立つ；

わち最適シミュレーション分布を決定する．それは文献 [4] と同様にしてQ(td (j)) = Q(td (j −1))+A(j)−L(j), j = 1, 2, · · ·(9)P (X ∗ =x)=

L = L(j) として，X = A − L とおく．また，最大パケット長を lmax = max(l1 , · · · , lK ) とする．X の確
率 P (X = x), x ≥ −lmax ，及び X のモーメント母関
数 ϕ(θ) を求める．

πk



K


R(nk ; λ∗kk ), (16)k=1 n·l=x+lk k =1

ここで，キュー長差 Q(td (j)) − Q(td (j − 1)) = A(j) −L(j) について考える．変数 j を省略して，A = A(j)，Kx ≥ −lmax ,∗λ∗kk = elk θ λkk , k, k  = 1, · · · , K(17)となることが分かる．

4. オンライン IS 推定

バッファサイズ = ∞ としているので，到着したパ

さて，ここで，(17) について考える．元の FIFO

ケットは廃棄されず必ずサーバで処理される．した

キューのキュー長変化規則 X に関するシステムパラ

がって，処理されるパケットの割合はパケット到着率

メータを S = (Λk , μ)k=1,··· ,K とし，IS 法の最適なΛk /lk に比例する．そこで，πk = P (L = lk ) とお
くと，S ∗ = (Λ∗k , μ∗k )k=1,··· ,KΛk /lkπk = K, k = 1, · · · , Kk =1 Λk /lk(10)

を 得 る ．長 さ lk の パ ケット に 対 す る 処 理 時 間 を

τk = lk /μ [s] とおく．長さ τk の時間区間におけるパケット長 lk のパケットの到着率 λkk は(11)となる．更に，K(12)

とおく．また，記号の簡単化のために，ポアソン確率K

k=1 nk lkと書く．

P (X=x)=

K


πk



k=1 n·l=x+lk

K


(19)

∗ Λk
Λ∗k
= elk θ, k = 1, · · · , K
μ∗k
μ

(20)

理レート μ∗k [Byte/s] が (20) の関係を満たしていれよるパラメータ Λ∗k ，μ∗k の決定には任意性がある．特∗に，Λ∗k = elk θ Λk ，μ∗k = μ としたのが，文献 [4] でさせてキュー長を伸ばす方法である．本論文では，∗

R(nk ; λkk ), (13)

k =1

K




πk exp f (θ)lk(21)の特徴は，Λ∗k = Λk ，すなわちユーザトラヒックを変∗(14)化させないということである．そして，μ∗k = e−lk θ μとして処理レートを元の μ より小さくしてキュー長をk=1伸ばすのである．

を得る．そして，ϕX (θ∗ ) = 1, θ∗ > 0Λ∗k = Λk , μ∗k = e−lk θ μ, k = 1, · · · , K

として IS 法を実行する．(21) によるパラメータ設定

x ≥ −lmax ,(15)を満たす θ = θ∗ が唯一つ存在することが分かる [4]．
630

lk Λ∗kμ∗k lk

ある．[4] は，多くの IS 法と同様に到着レートを増加

以上の記号の下で，文献 [4] と同様にして，

ϕX (θ) =λ∗kk =

ば，(18) の S ∗ は最適なパラメータである．(20) に

k=1/n! と略記し，n · l =とする．(11) と同様にを得る．IS 法において，到着レート Λ∗k [Byte/s] と処

1  Λk lk θf (θ) = −θ +(e − 1)μlk

を R(n; λ) = λ e(18)となるので，(11)，(17)，(19) より，Λ lk Λk
λkk = τk k =lk 
μ lk 

n −λキュー長変化規則 X ∗ に関するシステムパラメータをIS 法におけるキュー長を IS キュー長 (IS queue
length) という．特に最適なパラメータ (21) による IS
キュー長を最適な IS キュー長といい，Q∗ と表す．Q∗

論文／FIFO キューのパケット廃棄確率に対する IS 法を用いたオンライン推定を計算するためのカウンタを以下のように提案する．

4. 1 オンラインでの IS キュー長の計算

5

let k =PktInd(te (i)):

6Q∗ = Q∗ + lk

前節でも述べたように，本論文での IS シミュレー

7

ションの特徴は，到着レートを変えずに処理レートを8

at dequeue time td (j)let k =PktInd(td (j)):

小さくしてキュー長を伸ばし廃棄事象を多く発生させ9

Ck = Ck + 1

ることである．ユーザトラヒックを変えずに処理を変

10

If Ck ≥ exp (lk θ∗ )えるということは，IS 法を全てネットワーク側の処理

11

then Q∗ = Q∗ − lk :の変更だけで実現できるということである．したがっ12

Ck = Ck − exp (lk θ∗ )て，従来の IS 法と異なり，IS 法をオンラインで実行できる．

上記の動作アルゴリズムについて説明する．まず，処理レートを小さくするためにすぐに考えられる方

基本的なこととして，この動作は IS キュー長 Q∗ に関

法は，処理時間を管理する新たなタイマーを設けてパするサイクル単位で実行されている．つまり，Q∗ = 0

ケットをゆっくり処理することだが，新たなタイマーのときを時間原点として，Q∗ > 0 である期間，すなを NS-2 に実装するとシステムが複雑になる．そこで，

わちサイクルを単位として推定値が得られる．

本研究では，NS-2 が event driven で動作するシミュ

第 1〜3 行において，時刻 0 で IS キュー長 Q∗ とカウレータであるという特徴を利用して，最適な IS キュー

ンタ Ck が初期化される．第 4〜6 行で，FIFO キュー

長 Q∗ を簡単に計算するカウンタを提案する．

いて，到着したパケットのパケット長 lk が IS キュー

最適な IS キュー長を計算するために以下のカウン

長 Q∗ に加算される．このパケット到着時の動作は，タを用意する．

FIFO キューのキュー長に対する動作と同じである．
次に，FIFO キューからパケットが送出される時刻

Q∗ [Byte]

最適な IS キュー長を表す
カウンタ(dequeue time) td (j) において，送出されたパケット

Ck , k = 1 · · · , K

パケット処理を遅くするためのカウンタ

して，カウンタ値 Ck が exp (lk θ∗ ) 以上となったときこれらのカウンタの組 {Q∗ , Ck , k = 1, · · · , K} を総称して ISQL カウンタ (IS Queue Length counter) という．

ISQL カウンタについて説明する．FIFO キューへパケットが到着する時刻を te (1), te (2), · · · , te (i), · · ·とし，パケットが処理されて FIFO キューから送出される時刻を td (1), td (2), · · · , td (j), · · · とする．添字のe，d は，それぞれ enqueue, dequeue の頭文字である．
また，時刻 t に到着する，あるいは送出されるパケッ
トの index を返す関数を PktInd(t) とする．ここで，パケットの index とは，パケットの長さが lk のときの添字 k のことである．

ISQL カウンタの動作アルゴリズムの擬似コードと図を下記に示す．

ISQL カウンタの動作アルゴリズム
1にパケットが到着する時刻 (enqueue time) te (i) にお

4. 2 ISQL カウンタとそのアルゴリズムに対応するカウンタ Ck が 1 加算される（第 9 行）．そ（第 10 行）に IS キュー長 Q∗ から対応する 1 パケッ
ト分の Byte 数 lk が減算され（第 11 行），Ck から

exp (lk θ∗ ) が減算される（第 12 行）．第 9〜12 行の動
作は，カウンタ Ck が 1 ずつ増加してゆき，exp (lk θ∗ )以上になったときに Q∗ からパケット長 lk が送出されるので，長さ lk のパケットに対する処理時間が約

exp (lk θ∗ ) 倍になること，言い換えると処理レートが約 exp (−lk θ∗ ) 倍になることを意味する．この効果に
よって IS キュー長 Q∗ が伸びるのである．exp (lk θ∗ )が整数でないときには第 12 行の減算で端数が生じる
が，その端数は次回に繰り越されるので，長時間で考えれば長さ lk のパケットはほぼ μ∗ = μ exp (−lk θ∗ )のレートで処理されることになる．ここで注意すべき
ことは，IS キュー長 Q∗ からのパケット長 lk の送出は必ずしも到着順には行われていないことである．すなわち，Q∗ の中ではパケットの個性は失われ，全パ

at time 0

ケットの合計 Byte 数のみが Q∗ によって管理されて∗

2

Q = 0:

いる．このことを図 1 の Q∗ においてパケット間の点

3

Ck = 0, k = 1, · · · , K

線で示している．我々の目的は事象 {Q > q} の確率

4at enqueue time te (i)を得ることなので，パケットの処理順は結果に影響を631

電子情報通信学会論文誌 2012/5 Vol. J95–B No. 5
表 1 パケット長に関するパラメータ
Table 1 Parameters on packet length.
異なるパケット長の種類

K=1

パケット長 [Byte]l = 128

表 2 FIFO キュー及び従来 IS 法のパラメータ
Table 2 Parameters on FIFO queue and conventionalIS.

図1Fig. 1ISQL カウンタによる処理レートの低減と IS
キュー長
Reduction of service rate and IS queue length
by ISQL counter.

case 1case 2case 3case 4

到着レート Λ[kByte/s]

12.5

50.0

75.0

100

処理レート μ[kByte/s]

125

125

125

125

トラヒック密度 Λ/μ最適な到着率 Λ∗[kByte/s]

0.1

0.4

0.6

0.8

464.4

252.5

193.5

154.0

表 3 ISQL カウンタのパラメータ
Table 3 Parameters on ISQL counter.

与えない．

4. 3 ISQL カウンタによる IS 推定値
式 (1)，(2)，(3) のキュー長 Q として ISQL カウンθ∗case 1case 2case 3case 4

2.82
×10−2

1.26
×10−2

7.40
×10−2

3.37
×10−2

タで得られた最適な IS キュー長 Q∗ を用いて，パケッ

最適処理レート μ∗ =∗μe−lθ [kByte/s]

3.36

24.76

48.47

81.24

ト廃棄確率 P (Q > q) に対する IS 推定値 P̂IS は [4] と処理レートの比 μ/μ∗

37.15

5.05

2.58

1.54

同様にして以下のように与えられる．

トラヒック密度 Λ/μ∗

3.72

2.02

1.55

1.23

P̂IS =

M
1 1 
1q (Q∗ (td (j)))W (j) (22)·D M m=1 j=1

1 
W (j)
M̃ m=1 j=1(23)

W (j) = exp (−θ∗ Q∗ (td (j)))

(24)

M̃

D=

であって，従来 IS 法よりもこれらの特性において優れているということを主張するものではない．本論文で提案するオンライン IS 法の特徴は，実際に稼働しているネットワークのトラヒックをそのまま利用してパケット廃棄確率の高速な推定ができることであるが，特徴である「オンライン」ということを数値的に主張(22)，(23) の j に関する和は 2. 1 の最後の部分に述することは難しい．本章では，したがって，提案 IS 法

べたようにシミュレーションの途中でサイクルを打ちの IS 法としての基本的性能を評価するものである．

切るダイナミック IS 法によって行う．

5. シミュレーションによる比較評価

5. 1 シミュレーション 1
表 1，表 2 に示す条件でシミュレーションを行う．
すべてのパケット長が等しく 128 [Byte] である．到着

幾つかの条件のもとで，FIFO キューのパケット廃レートを 4 種類変えて調べる．表 3 に ISQL カウン

棄確率に対する推定値の精度，得られる推定値の限界，

タのパラメータを示す．表 3 において処理レートのシミュレーション時間について考察する．比較するシ比 μ/μ∗ が，例えば case1 では 37.15 となっているが，ミュレーション法は，MC 法，到着レートを大きくす

これは図 1 において，元の処理速度の 1/37.15 のゆっる従来 IS 法 (conventional IS) 及び処理レートを小さくりした速度でパケットを処理するのが最適であるこくする本論文での提案 IS 法 (proposed IS) である．ことを表している．また，case1 では元のトラヒック密こで，従来 IS 法とは，文献 [4] で作成した DRR に対

度 Λ/μ が表 2 より 0.1 であり，最適なトラヒック密する IS 法を FIFO キューに対応するように修正した

度 Λ/μ∗ が表 3 より 3.72 である．つまり Λ/μ∗ > 1

ものである．

なので Q∗ は不安定である．

特性の比較は，提案 IS 法がもつ IS 法としての基本

図 2 にパケット廃棄確率の推定値を示す．MC 法で的特性が従来 IS 法と同等であることを確認するもの

はサイクル数を 107 とし，従来 IS 法及び提案 IS 法で632

論文／FIFO キューのパケット廃棄確率に対する IS 法を用いたオンライン推定
表 6 ISQL カウンタのパラメータ
Table 6 Parameters on ISQL counter.
case 1case 2case 3case 4

1.04
×10−2

6.39
×10−3

3.74
×10−3

1.71
×10−3

最適処理レート μ∗1 =∗μe−l1 θ [kByte/s]

32.67

55.18

77.42

100.44

最適処理レート μ∗2 =∗μe−l2 θ [kByte/s]

8.54

24.35

47.95

80.71

θ∗

処理レートの比 μ/μ∗
1

3.83

2.27

1.61

1.24

処理レートの比 μ/μ∗
2

14.64

5.13

2.61

1.55

トラヒック密度

2.53

1.92

1.51

1.22

図 2 MC 法，従来 IS 法，提案 IS 法による推定値の比較
Fig. 2 Comparison of estimates by MC, conventional
IS and proposed IS.
表 4 パケット長に関するパラメータ
Table 4 Parameters on packet length.
異なるパケット長の種類

K=2

パケット長 [Byte]

l1 = 128, l2 = 256

表 5 FIFO キュー及び従来 IS 法のパラメータ
Table 5 Parameters on FIFO queue and conventionalIS.
case 1case 2case 3case 4

到着レート Λ1[kByte/s]

0.714

1.43

2.14

2.86

到着レート Λ2
[kByte/s]

24.3

48.6

72.9

97.1

処理レート μ[kByte/s]

125

125

125

125

トラヒック密度(Λ1 + Λ2 )/μ

0.2

0.4

0.6

0.8

最適な到着レート Λ∗
1[kByte/s]

2.73

3.25

3.45

3.55

最適な到着レート Λ∗
2[kByte/s]

355.8

249.3

190.3

150.5

図 3 MC 法，従来 IS 法，提案 IS 法による推定値の比較
Fig. 3Comparison of estimates by MC, conventional
IS and proposed IS.

case1 では最適な処理レートが μ∗1 = 32.67 [kByte/s]，μ∗2 = 8.54 [kByte/s] となり，短いパケット長と長いパケット長とで最適な処理レートが異なることに注意す
る．パケット廃棄確率に対する推定値を図 3 に示す．
図 3 からも提案 IS 法は従来 IS 法とほぼ同程度の特性をもつことが分かる．従来 IS 法と提案 IS 法の推定は 104 とした．この条件で MC 法と両方の IS 法の標値にわずかな誤差があるが，この誤差の理由について本分散が同程度となる．図 2 より MC 法では約 10−6

考える．提案 IS 法では処理レートを下げる方法としが推定値の限界であるが，従来 IS 法と提案 IS 法ともてタイマを設けるのではなく FIFO キューにおけるパに限界なく推定値が得られている．

ケット到着，送出のタイミングで IS キュー長 Q∗ を

5. 2 シミュレーション 2

計算している．タイマーなら完全に最適な処理レート

表 4，表 5 にシミュレーション条件を示す．このシを実現できるが，提案 IS 法では簡易的な方法なので，ミュレーションでは，K = 2，すなわち 2 種類の異なそれによる誤差と考えられる．

る長さのパケットが存在する場合である．ISQL カウン
タのパラメータを表 6 に示す．表 6 において，例えば，633

電子情報通信学会論文誌 2012/5 Vol. J95–B No. 5
表 7 MC 法と提案 IS 法のシミュレーション時間の比較
Table 7 Comparison of simulation time by MC andproposed IS.
MCproposed IS

108

サイクル数

103
−6

2.67 × 10−6−145.01 × 10−15

3.03 × 10

平均推定値

1.47 × 10

標本分散シミュレーション時間

379.8 [s]0.093 [s]6. む す び
本論文では，FIFO キューのパケット廃棄確率をオンラインで高速に推定する IS シミュレーション法を提案した．
従来の IS 法ではキューへの入力トラヒックをモデ
ル化し，モデルの到着レートを上げてパケット廃棄事
象を多く発生させる．しかし，その方法では実際の
図 4 MC 法と提案 IS 法による推定値のばらつきの比較
Fig. 4 Comparison of dispersion of estimates by MC
and proposed IS.

5. 3 シミュレーション 3［高速性能評価］
次に，MC 法と提案 IS 法のシミュレーション時間を

キューとは別なシミュレーションになってしまう．
本研究では，ユーザからのパケットトラヒックをそのまま利用して，処理レートを下げることで廃棄事象を増やす新たな IS 法を提案した．それによって MC法と同様にオンラインでの推定ができ，更に MC 法
よりも高速に推定を実行できる．実際に，提案する IS比較する．前述のシミュレーション 2 における case2 で法のシミュレーションプログラムを NS-2 で作成した．

q = 2000 [Byte] のときのパケット廃棄確率を推定する

オンライン推定のために「ISQL カウンタ」を FIFOのにかかる時間を比較する．公平な比較を行うためにキューに置き，NS-2 の event driven なシミュレータ

次の手順による．まず，MC 法において 1 回のシミュとしての特徴を生かした方法でパケット処理レートをレーションでのサイクル数を 108 として P (Q > q) に小さくしてキュー長を伸ばすアルゴリズムを作成した．

対する 1 個の推定値を得る．同じことを繰返し行って，幾つかのシミュレーションを行い，得られた推定値の20 個の推定値を得て，それらの標本分散を計算する．

精度，推定限界，高速性について評価した．

次に提案 IS 法でサイクル数を 102 , 103 , 104 , 105 と今後は，提案した IS 法を用いて高速にリアルタイ

してそれぞれ 20 個の推定値を得て標本分散を計算す

ムのパケット廃棄確率を推定し，その値をすぐにレーる．最初に MC 法で得られた分散に最も近い分散を与ト制御のために使うことを検討していく．

えるサイクル数を選ぶ．この過程を示したのが図 4 である．図 4 より MC 法の 108 サイクルに対して提案

IS 法の 103 サイクルのときがほぼ同等の分散となる

文[1]sion, Simulation, and Estimation, Wiley, New York,
1990.

ことが分かる．このようにしてそれぞれのシミュレー
ションのサイクル数を決定して実行した結果を表 7

献J.A. Bucklew, Large Deviation Techniques in Deci-[2]

M. Devetsikiotis and J.K. Townsend, “Statisticaloptimization of dynamic importance sampling pa-に示す．推定値の平均と分散がほぼ等しいので同程度

rameters for eﬃcient simulation of communicationの推定精度といえる．このときのシミュレーション時

networks,” IEEE/ACM Trans. Netw., vol.1, no.3,
pp.293–305, June 1993.

間は，表 7 より MC 法では 379.8 秒であり，提案 IS
法では 0.093 秒となった．したがって，この場合，約4000 倍の高速化が得られている．

[3]

ITU-T Recommendation Y.1541,
http://www.itu.int/rec/T-REC-Y.1541-200602-I/en[4]

和泉光紀，中川健治，横谷哲也，“DRR スケジューラの
パケット廃棄確率算出における NS-2 へのインポータンス” 信学論
サンプリングシミュレーションの適用について，

634

論文／FIFO キューのパケット廃棄確率に対する IS 法を用いたオンライン推定[5]（B），vol.J94-B, no.5, pp.698–707, May 2011.
中川健治，“モンテカルロシミュレーション基礎—推定
精度評価の問題点とその克服，” 信学通誌，no.6, 秋号，pp.11–20, 2008.

[6]小川耕司，中川健治，“MMPP/D/1 キューイングにおける最適 IS シミュレーション分布，” 信学論（B-I），vol.J80B-I, no.2, pp.64–73, Feb. 1997.

[7]

J.S. Sadowsky, “Large deviations theory and eﬃcient simulation of excessive backlogs in a GI/GI/mqueue,” IEEE Trans. Autom. Control., vol.36, no.12,
pp.1383–1394, 1991.

（平成 23 年 9 月 8 日受付，12 月 27 日再受付）

小林信裕

平 21 長岡技科大・工・電気電子情報卒．
平 23 同大大学院修士課程了．同年（株）
イートラスト入社．

中川

健治 （正員）昭 55 東工大・理・数学卒．昭 60 同大大学院博士課程満期退学．昭 60 NTT 研究所入社．情報理論，ATM 容量設計等の研究に従事．平 4 長岡技科大工学部助教授，
平 19 同准教授，平 24 同教授．ネットワー
ク特性評価，待ち行列理論，大偏差理論等の研究に従事．理博．IEEE，日本 OR 学会，日本数学会，日本
工業教育協会各会員．

635