Discovery Sagaサイレントキーワード俯瞰

OR / 確率モデル / 待ち行列 / ネットワーク / 応用確率論 / 点過程 / 通信ネットワーク / 性能評価 / 確率幾何モデル / 無線通信 / 定常点過程 / 漸近解析 / 複雑ネットワーク / 定常分布 / 極限定理 / ランダムグラフ / 次数分布

本研究では,点の間隔に相関のある1次元定常点過程に対する疑似再生方程式を導入し,それに対する極限定理を導きました.また,ネットワークの性能評価への応用のために,空間マーク付き点過程によって構成されるランダム・グラフの次数分布を漸近的に評価したり,セルラネットワークの空間点過程モデルを考え,被覆確率の漸近的な性質を調べたりしました.

確率モデル / 確率過程における相関性 / 漸近解析 / 待ち行列 / インターネット / Webキャッシュ / 通信品質 / DoS攻撃 / 確率過程の相関 / 確率順序 / 裾の重い分布 / 点過程 / 相関のある確率過程

本研究の目的は,入力に相関性を有する待ち行列モデル,また,さらに一般的な確率ネットワークに対して,定常性を仮定しない解析,あるいは動的なふるまいの解析を行ない,インターネット等に見られる様々な新しい特性の評価に応用することです.この目的の遂行のため,また関連する課題として,今年度に行なった研究は以下の通りです.
1.入力に相関を許す離散時間型の単一サーバ待ち行列モデルに対して,待合室の容量が異なるシステム間に成り立つ比例関係について解析しました.その結果は海外の学術論文誌への掲載が決定しています.ここではサンプルパス解析と呼ばれる手法を用いて,確率過程の定常性さえ要らない極めて一般的な仮定のもとで,待合室の容量が異なるシステムの系内人数分布の問に比例関係が成立することを示し,またその比例定数もサンプルパスを観測して得られる量から導けることを示しています.
2.昨年度からのテーマとして,インターネットにおけるWebキャッシュ等で用いられているLRU(Least-Recently-Used)キャッシュの解析を行ないました.ここでは,Webページへのアクセス頻度にZipfの法則と呼ばれる裾の重い分布の形が見られることから,このZipfの法則を仮定し,ページアクセス過程には任意の相関を許して,キャッシュの効率の良さの指標であるページフォールト率の漸近解析を行ないました.この成果も海外の学術論文誌への掲載が決定しています.
3.近年問題になっているインターネットにおけるDoS攻撃(サービス妨害攻撃)への対抗策である,確率的パケットマーキングによるIPトレースバック技術の性能評価法に関する研究も行いました.この問題は,組合せ確率論における古典的な問題であるクーポン収集問題の応用として表せることから,まずクーポン収集問題に対する漸近解析を行っています.
4.本研究の応用の面での成果である,インターネットにおける通信品質を測定するための新しい手法について,得られた結果を海外の学術論文誌に投稿中と昨年度の報告書に書きましたが,残念ながら投稿して一年以上経過しているにもかかわらず,まだ一度目の審査結果さえ返って来ていません.提案した手法は,測定のためにネットワークに送り込む試験パケットによる負荷を極力抑えながら,複数の利用者が受けるサービス品質を同時にかつ個別に測定できるというものであり,確率論における測度変換,サンプルパス解析,点過程および流体近似等の概念を用いています.

バランスの良い文字列 / m-バランス列 / ビリヤード列 / ネットワーク・スケジューリング / 情報ネットワーク / 待ち行列 / 確率モデル / 性能推定 / パターン・サーチ法 / スケジューリング / 定常特性

本研究の課題は,複数種類の文字を並べて無限に長い文字列を構成する際に,各文字に対して列の中で現れる割合(出現率)が与えられているときに,それを満足しながら如何にバランス良く(なるべく均等に)文字を並べるかという問題への取り組み,ならびにその情報ネットワーク等のスケジューリングや制御への応用についてです.この課題の遂行,およびこれに関連するテーマとして,今年度は以下の研究を行いました.
これまでに研究代表者の研究室では,上記の問題に対して「m-バランス列」という概念を提唱しています.これは,mに0以上の整数値を代入することによって,各文字が任意の出現率を持つ任意の(半)無限列に対してバランスの良さの指標を与える(mの値が小さい程バランスが良い)ものです.また,このm-バランス列を生成するアルゴリズムとして,ビリヤード列(billiard sequences)と呼ばれる文字列を生成するものを考え,N種の文字からなるビリヤード列は必ず(N-1)-バランス列になることを示しています.しかし,このアルゴリズムの問題点として,与えられた出現率の組によっては,よりバランスの良い列が存在するかもしれないにもかかわらず,それが実現されない場合がありました.これは,生成される文字列のバランスの良さが,アルゴリズムの初期値に大きく依存することに依ります.この問題に対して,文字の出現率が有理数であるときには,生成される文字列が周期列になることを利用し,確率的なアルゴリズムによって,ビリヤード列を生成するアルゴリズムに良い初期値を与えることに成功しました.尚,この研究成果は現在,海外の学術論文誌に投稿中です.
上記に加えて,応用に関する課題として,ネットワークのスケジューリングにおいて重要な待ち行列システムの並列推定に関する研究も行いました.また,インターネットにおける性能や通信品質の推定法に関する研究も行っています.