早稲田大学大学院 基幹理工学研究科
博 士 論 文 概 要
論 文 題 目
非定常ポアソン過程を用いた
ネットワークトラヒック解析に関する研究 On the Network Traffic Analysis
with the Non-Stationary Poisson Process
申 請 者
小泉 大城
Daiki Koizumi
2010 年 5 月
情報化社会の急速な発展に伴い，インターネットを支えるネットワークに関する基盤技術開発の重要 性はますます高まっている．ネットワークトラヒックは，こうした目的に欠かせない研究対象のひとつ であり，主な指標として単位時間あたりのユーザの到着数，ユーザ毎のサービス利用時間，輻輳状態の 有無やその確率などがあり，これらを駆使して，トラヒックそのものの有する性質を解明したり，トラ ヒック解析の数理モデルを構築したりすることなどを研究目標としている．こうした研究成果を通じ，
ネットワーク管理や運用技術に新たな発展の機運がもたらされることが期待されている．
1990年代頃までのインターネット黎明期においては，ネットワーク環境の管理や運用現場は，関係す る技術者の経験や勘に多分に依存しており，基礎研究においても，電話網のトラヒック解析に使われた 待ち行列理論の研究成果が流用されることが多かった．ここでは，ユーザ到着やサービス利用時間に対 して，ポアソン分布，アーラン分布，あるいは指数分布などといった定常確率分布を仮定する場合がほ とんどであった．こうした流れと並行して，早くからネットワークトラヒックの実データを大規模に観 測し，それらの性質の解明を試みた研究も行われていた．1995年，インターネットのネットワークトラ ヒックの実データが必ずしも定常ポアソン分布に従わないという研究成果が発表されると，ネットワー クトラヒック研究にも非定常確率分布が導入されるようになった．
いま，ネットワークトラヒックの非定常確率分布によるモデル化の例として，ユーザ到着を取り上げ，
これが非定常ポアソン分布に従っているとする．このとき，離散時刻t= 0,1,2,· · ·におけるユーザ到着 数を離散確率変数Xtとすると，Xtは，以下の(1)–(4)による非定常ポアソン過程として定義すること ができる．
(1) X0 = 0.
(2) 過程は定常増分を持つ.
(3) P r{Xt+h−Xt= 1}=θth+o(t), h >0. (4) P r{Xt+h−Xt≥2}=o(t) .
以上の条件をすべて満たす確率過程Xtのことをパラメータθtの非定常ポアソン過程と呼び，このと き，P r{Xt=xt|θt}は，非定常ポアソン分布として以下のように定式化される．
P r{Xt=xt|θt} = (θt)xt
(xt)! exp (−θt).
本論文では，上式のパラメータθtが確率変数Θt=θtであると仮定し，Θtが非定常に変化するモデルと して以下を定義する．
Θt+1 = Ut
k Θt, 0< k≤1,
Θ1 ∼ Gamma(α1, β1), α1>0, β1 >0, Ut ∼ Beta[kαt,(1−k)αt].
ここで，第一式左辺のΘt+1は時刻(t+ 1)のパラメータ，第一式右辺のUtはΘtとは条件付独立な確 率変数で，超パラメータkは，0< k≤1なる実数である．また，第二式右辺のα1はガンマ分布の形状 パラメータ，β1は同じく尺度パラメータである．第三式は第二式と同様に，Utがベータ分布に従うこと を表している．
1
この非定常パラメータの変化モデルは，Θtが時間毎にΘt+1へと確率的に変化する，ランダムウォー ク型のモデルとなっている．Θt+1は，2つの確率変数Θt, Utの積によるメリン変換の一種として定義さ れている．また，超パラメータkは，0< k≤1なる値を取るが，k= 1のときは，Utの従うベータ分布 の尺度パラメータが0となり，Utの分散も0となる．したがって，Θt+1は時間によらずに定数となり，
Xtの確率分布は定常ポアソン分布に帰着する．一方，0< k <1のときは，Θtは確率的に変化し，Xtの 分布は非定常ポアソン分布となる．このように，上で定義したパラメータΘtの非定常変化モデルは，超 パラメータkを含み，k= 1における定常ポアソン分布を特殊形として一般化された定義となっている．
このとき，時刻tまでのユーザ到着数xt1=x1x2· · ·xtが観測されたもとで，以下の(5)または(6)を 行うことを考える．
(5) 時刻tにおけるパラメータΘˆtを推定する．
(6) 時刻(t+ 1)におけるユーザの到着数Xˆt+1を予測する．
本論文では，(5)のように時刻tにおける非定常パラメータΘˆtを推定することを特にパラメータ推定，
(6)のように時刻(t+ 1)におけるトラヒックXˆt+1を予測することを特にトラヒック予測と呼び，ここ までで述べた一連の問題のことを，非定常ポアソン過程によるネットワークトラヒック解析と称する．
このように本論文では，非定常ポアソン分布のパラメータを特に確率変数Θt=θtとしてモデル化す るアプローチを取るが，以降では簡単のため確率変数Θtとその実現値θtとを区別せず，単にθtなどと 書き，その確率分布もp(θt)と書くものとする．
ˆ
xt+1を求めるトラヒック予測については，多くの従来研究ではパラメータ推定値θˆtを既知の非定常確 率分布のクラスに代入した，p(xt|θˆt)の形式の確率分布を用いて予測されているが，本論文では時刻 (t+ 1)におけるユーザ到着の確率分布p(xt+1 |θt+1)をパラメータθtの事後分布p(θt+1 |xt1)で重み付 けを行った予測分布，
∫
p(xt+1|θt+1)p(θt+1|xt1)dθt+1,
を用いるベイズ的なアプローチを取る．類似のアプローチは，ある種の非定常正規分布について，超パ ラメータが既知の条件下で，パラメータ推定や予測の問題を解析的に解いたカルマンフィルタなどに見 ることができ，また，同様の条件下でポアソン分布や二項分布に拡張を図った研究も存在する．しかし，
非定常ポアソン分布によるアプローチをトラヒック解析に応用した例はない．
本論文では，以上で述べたような非定常ポアソン過程によるネットワークトラヒック解析を扱うが，特 にパラメータθtの非定常変化が，超パラメータkによって定義される，ランダムウォーク型のモデルを 考えている．非定常ポアソン過程によるモデル化は，必ずしもこの型のモデルのみに限らないが，ネッ トワークトラヒック解析への応用を考慮した場合，本論文による研究成果として，数学的な取り扱い易 さとネットワークトラヒックの実データとの整合性という，2点を挙げることができる．
前者の数学的な取り扱い易さについては，さらに2つに分けることができる．1つ目としては，超パ ラメータkが既知の条件下において，θˆtのパラメータ推定，およびxˆt+1のトラヒック予測が解析的な四 則演算にて導出可能であることを示した．さらにトラヒック予測値xˆt+1は，損失関数に二乗誤差を仮定 したもとでベイズ最適性を保持していることも示した．一般に，統計的決定理論を用いたベイズ最適な 予測値の計算においては，時刻tまでのユーザ到着数xt1を観測した下で，ベイズの定理によりパラメー
タの事後分布p(θt|xt1)を計算する必要が生じるが，この際の計算コストは定常なモデルにおいても莫 大になる場合がある．しかし，本論文で扱うランダムウォーク型の非定常ポアソン過程においては，パ ラメータの非定常性を仮定しながらも，超パラメータkが既知であれば，そのような問題が発生しない．
2つ目として，本論文の非定常ポアソン過程は，超パラメータkによりパラメータθtの非定常変化が 定義されているが，これがk= 1のときの定常ポアソン過程の自然な一般化になっている点を挙げるこ とができる．一般にはより多くの超パラメータを使った非定常ポアソン過程も数多く考えられるが，本 論文では1つの超パラメータのみで非定常パラメータθtのモデル化を行っている．ネットワークトラ ヒックの実データからのkの推定が，解析的には不可能なものの，数値計算によって比較的容易に近似 最尤推定が可能であることが示された．また，後述する実データを用いた情報量規準によるモデル選択 においても有効性の一因となることがわかった．
後者のネットワークトラヒックの実データとの整合性について，本論文では上に述べたように，超パ ラメータkを数値計算により近似最尤推定し，その下でパラメータ推定やトラヒック予測を行った．こ れらの結果を，kが既知の非定常ポアソン過程から人工的に発生させたデータを適用して，パラメータ推 定の精度を計算したり，ネットワークトラヒックの実データを適用して，トラヒック予測の精度を計算 したりすることで評価を行ったところ，定常ポアソン過程によるトラヒック解析モデルと比較して，本 論文で扱った非定常ポアソン過程によるトラヒック解析モデルは，良好なパラメータ推定精度および予 測精度を持つことが確認された．さらに，実データを用いて，情報量規準によりモデル選択を行ったと ころ，本論文で扱ったトラヒック解析モデルは，やはり定常ポアソンモデルと比較して実データに対す る相対的な当てはまりという点で優れていることを確認することができた．
以下に本論文の構成について述べる．第1章では，序論として研究背景，研究目的について述べる．
第2章では，準備として，本論文で非定常ポアソン過程を扱う際の基本となる，確率論，統計的決定 理論，確率過程についての定義を行い，最後の節で本論文による研究の位置づけについて説明する．
第3章では，時刻tにおけるネットワーク上のユーザ到着xtをランダムウォーク型の非定常ポアソン 過程p(xt|θt)で定式化し，統計的決定理論を用いることで，実トラヒックを観測したもとでのパラメー タ推定θˆtや損失関数に二乗誤差を仮定したもとでのベイズ最適なトラヒック予測xˆt+1が可能であるこ とを示す．また非定常なパラメータ変化を定義する超パラメータkが既知の条件下で，パラメータの確 率分布にガンマ分布の仮定をおくと，計算量が削減された形の予測アルゴリズムを導出可能なことを示 す．また，超パラメータkを数値計算で近似最尤推定する方法についても述べる．
第4章では，人工的に発生させたネットワークトラヒックデータやWorld Wide Web (WWW)トラ ヒックの実データを利用して，パラメータ推定θˆtの精度，トラヒック予測xˆt+1の精度，および超パラ メータkの近似最尤推定の精度等を計算し，本論文によるアプローチの評価や考察を行う．また，本論 文で扱うトラヒックモデルの出力結果を様々なネットワーク管理場面へ適用する場合の応用例について も検討を行う．
最後に第5章では，研究成果のまとめを行い，結論と今後の課題を整理する．
3
Ｎｏ.1
早稲田大学 博士（工学） 学位申請 研究業績書
氏 名 小泉 大城 印
（２０１０年 ４月 １日 現在）
種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者 含む）
1. ○論文
2. 論文
3. 論文
4. 講演
5. 講演
6. 講演
7. 講演
8. 講演
Bayesian Forecasting of WWW Traffic on the Time Varying Poisson Model, Proceeding of the 2009 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'09), pp.683-689, July, 2009, Daiki Koizumi, Toshiyasu Matsushima, and Shigeichi Hirasawa.
Reliability-Based Hybrid ARQ Scheme with Encoded Parity Bit Retransmissions and Message Passing Decoding, IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences, E90-A, vol.9, pp.1736-1744, Sep. 2007, Daiki Koizumi, Naoto Kobayashi, Toshiyasu Matsushima, and Shigeichi Hirasawa.
A Note on Error Correction Schemes with a Feedback Channel, IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences, E89-A, vol.10, pp. 2475-2480, Oct. 2006, Naoto Kobayashi, Daiki Koizumi, Toshiyasu Matsushima, and Shigeichi Hirasawa.
On the Hyperparameter Estimation of Time Varying Poisson Model for Bayesian WWW Traffic Forecasting, 2nd International Workshop of the European Research Consortium on Infomatics and Mathematics (ERCIM) Working Group on Computing & Statistics, Oct. 2009, Daiki Koizumi, Toshiyasu Matsushima, and Shigeichi Hirasawa.
On the Bayesian Forecasting Algorithm under the Non-Stationary Binomial Distribution with the Hyper Parameter Estimation, Ninth Valencia International Meeting on Bayesian Statistics (掲載決定), June 2010, Daiki Koizumi, Tota Suko, and Toshiyasu Matsushima.
サービスの開始と終了を考慮した Web トラヒックの非定常 Poisson 過程によるモ デル化について, 電子情報通信学会 情報ネットワーク研究会 技術研究報告 (IN2009-201), pp.343-347, 2010 年 3 月，小泉 大城，堀井 俊佑，松嶋 敏泰．
ベイズ符号化アルゴリズムを用いたテキストデータ圧縮, 情報処理学会 アルゴ リズム研究会 研究報告(2007-AL-110), pp.15-20, 2007 年 1 月, 中野 晶，小泉 大城，松嶋 敏泰．
記号の出現パターンを考慮した情報源に対するベイズ符号に関する研究, 電子 情報通信学会 情報理論研究会 技術研究報告（IT2006-29), pp.25-30, 2006 年 7 月, 南茂 龍之介, 小泉 大城, 松嶋 敏泰.
Ｎｏ.2
早稲田大学 博士（工学） 学位申請 研究業績書
種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者 含む）
9. 講演
10. 講演
11. 講演
12. 講演
13. 講演
14. 講演
15. 講演
16. 講演
The Reliability based Hybrid ARQ Scheme with both the Encoded Parity Bit Retransmissions and Message Passing Decoding, 2006 Hawaii, IEICE and SITA Joint Conference on Information Theory, May 2006, Daiki Koizumi, Naoto Kobayashi, Toshiyasu Matsushima, and Shigeichi Hirasawa.
A Note on HTTP Traffic Analysis of the Time Series Model with a Time Varying Density Parameter, 第 28 回情報理論とその応用学会 (SITA2005)予稿集 vol.2, pp.729-732, 2005 年 11 月 , Daiki Koizumi, Toshiyasu Matsushima, and Shigeichi Hirasawa.
単一ループをもつグラフィカルモデルにおける確率伝播型アルゴリズムに関す る一考察, 第 28 回情報理論とその応用学会 (SITA2005) 予稿集 vol.1, pp.1-4, 2005 年 11 月, 岡野 洋平, 小泉 大城, 松嶋 敏泰.
再帰的組織畳み込み符号を利用した Reliability Based Hybrid ARQ についての 研究, 電子情報通信学会 情報理論研究会 技術研究報告（IT2005-52), pp.7-11, 2005 年 9 月, 小林 直人, 小泉 大城, 松嶋 敏泰, 平澤 茂一.
A Study of Reliability Based Hybrid ARQ Scheme with Bitwise Posterior Probability Evaluation from Message Passing Algorithm, 2005 Hawaii, IEICE and SITA Joint Conference on Information Theory, May 2005, Daiki Koizumi, Naoto Kobayashi, Toshiyasu Matsushima, and Shigeichi Hirasawa.
Tailbiting 畳込み符号の復号アルゴリズムに関する一考察，電子情報通信学会 情報理論研究会 技術研究報告（IT2004-26), pp.47-52, 2004 年 7 月, 岡野 洋 平, 小泉 大城, 松嶋 敏泰．
The Generalization of Bayesian Network's Deductive Method, The 1999 Sigma Xi, The Scientific Research Society, Florida Tech Chapter, Apr. 1999, Daiki Koizumi, Yoshifumi Ukita, and Toshiyasu Matsushima.
The Generalization of Bayesian Network's Deductive Method, 電子情報通信 学会 情報理論研究会 技術研究報告（IT98-32), pp.25-30, 1998 年 7 月, Daiki Koizumi, Yoshifumi Ukita, and Toshiyasu Matsushima.
Ｎｏ.3
早稲田大学 博士（工学） 学位申請 研究業績書
種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者 含む）
