擬似ネットワークトポロジーを用いたODトラヒック行列推定の精度向上
概要
情報化社会の進展により,通信インフラは人々の社会・経済活動の基盤としての重要性がますます高まっている.これに伴い,通信インフラにおけるネットワーク障害が与える影響,発生頻度が増大している.ネットワーク障害を未然に防ぐことや迅速に復旧させることを実現させるためには,ネットワークの利用状態を継続的に把握することが必要である.一方で,情報化社会の進展は,通信インフラの複雑化およびトラヒックの増大をもたらしている.このため,ネットワークの利用状態を直接把握することは容易ではなく,観測可能な情報から間接的に推定する技術が求められる.これを実現する技術がネットワークトモグラフィ技術である。
ネットワークトモグラフィ技術には,ネットワーク内の異常を検知するものや,ネットワークの伝送遅延を推定するものがある [1, 2, 3, 4].また,使用されるモデルや数学的手法も様々である.例えば,文献 [1] では,対象のトポロジーにおいてリンクの相関関係を考慮し,各リンクにおいて輻輳が発生している確率を推定する手法が提案されている.また,連続時間二変量マルコフ連鎖モデルに基づき,エンドツーエンドでの測定からそのネットワーク内におけるリンクの遅延分布を推定する手法も存在する [4].
本論文では,多岐にわたるネットワークトモグラフィ技術の中でもOD (Origin-Destination)トラヒック行列推定と呼ばれる問題に取り組む.直接的な観測が困難であるネットワーク上の大域的な対地間トラヒックフローの流量 (対地間フロー流量) を,それらが通過するルータで容易に計測可能な集約されたフロー流量 (集約フロー流量) から推定する問題である.このような問題の解法として,自由度の高い離散分布モデルを用いた逆関数法 [5] が提案されている.逆関数法は対地間フロー流量の分布が互いに独立であり,かつ,それぞれの対地間フロー流量が 0 となる確率が正であるという仮定の下で実行可能な手法である.この仮定が成り立つとき,逆関数法により集約フロー流量の確率分布から対地間フロー流量の確率分布が一意に定まる.
逆関数法 [5] には 2 つの問題があった.1 つは,逆関数法が非常に強い仮定を置いていることである.特に,対地間フロー流量が 0 となる確率が正である,すなわち,少なくとも 1 度は通過パケット数が 0 になる場合があるという仮定は一般には成り立つとは限らない.先行研究 [6] では,対地間フロー流量が 0 でなくとも実行可能となるように,一般化逆関数法を提案した.一般化逆関数法では,対地間フロー流量の最小値が既知の下で実行可能である.2 つ目の問題は,推定に用いる集約フロー流量の観測データに影響されやすいことである.これは,逆関数法の離散分布モデルの自由度が高すぎること,および逆関数法の計算手法が再帰的であることに起因する.文献 [7] では,この問題に対して,観測データのリサンプリングとそれにより得られる複数の推定結果の選別を行った.推定された対地間フロー流量分布から再計算される集約フロー流量の期待値と観測データから得られる集約フロー流量の期待値を比較することで,推定結果の妥当性を評価した.そして,その評価結果に基づいて推定精度が低いと考えられる推定結果を除外し,従来手法 [5] よりも高い精度を実現した.このように,逆関数法は適用可能な環境の拡大や誤差の抑制を目指した研究が進められている.しかしながら,これらの先行研究 [6],[7] は対地間フロー流量の期待値の推定に重きを置いており,分布の推定精度向上に対する改良が不十分である.
既存手法 [6],[7] はいずれも推定対象のネットワークトポロジーを前提としたモデルに適用していた.本論文では,推定対象のトポロジーに対して数学的に等価な擬似トポロジーに着目する.この擬似トポロジーでは,逆関数法の実行が可能である.元の推定対象トポロジーと擬似トポロジーにおける推定結果を適切に組み合わせることで,対地間フロー流量分布の推定精度向上を図る.
本論文の構成は以下の通りである.第1 節では,本論文の概要を述べる.第2 節では,本論文の先行研究である逆関数法 [5],およびその発展手法について説明する.第3 節では,提案手法について述べる.第4 節では,提案手法の評価実験を行ない,その結果を考察する.第5 節では,関連研究について述べる.第 6 節では,本論文の結論を述べ,残された課題を示す.