博 士 （ 情 報 科 学 ） 松 村 有 祐
学 位 論 文 題 名
Studies on Methodology of Structural Design for Dynamic Communication Networks
（動 的通 信ネ ット ワークの構造設計手法に関する研究）
学 位 論 文 内 容 の 要 旨
近年ユーザーが急増し ているSkypeは，世界中の1千万人を超えるユーザーに対して高品質を通 話サーピスを提供しており，その技術が注目されている．この技術の根幹に，トラフイック遅延を短 縮するネットワーク構造を維持するアルゴリズムの存在がある．実社会のネットワークにおいて，あ る機能要求を満たす構造を設計する問題は，クラスNPに属する組合せ問題であり，更に，ノード数 やトラフイック量が時系列的に変化する動的性質を有しており，解くことが極めて困難である，そこ でSkypeでは，ユーザーのログインに伴うノード数の増加時に，ネットワーク全体の遅延を改善す るりンクの生成規則を設計し，構造を制御している．
しかしながら，この生成規則はSkypeに固有を特性に依存し，また高度を専門知識を有するエン ジニアの試行錯誤によって設計されたものである．従って，他のネットワークに対して適用すること は困難である，今後も様々を形態のネットワークアプリケーションの開発が期待されており，動的条 件 下 で 機 能 要 求 を 満 た す 汎 用 的 な 構 造 生 成 規 則 の 設 計 手 法 の 確 立 が 求 め ら れ て い る ， 本学位論文では，動的誼通信ネットワークにおいて，理論的に最適性を考慮し，機能要求を満たす 構造を生成する構造生成規則の設計手法を構築することを目的としている，このために最適化法に 基づき下記の手順で生成規則を設計する手法を提案し，設計した生成規則で生成される構造を数値 実験により評価し，提案手法が有効であることを確かめている，
(1)時系列的に変化するノード数 トラフィック条件を想定し，その各ステップにおける最適を 構造を最適化の手法で求める．具体的には，通信ネットワークを待ち行列ネットワークとしてモデル 化 し， トラ フィ ッ ク遅 延を 最小 と する 構造 最適 化問 題 を定 式化 し， その 解 法を 提案 する ． (2)各ステップ間での最適構造の遷移を理論的に分析し，その結果をもとに生成規則を設計する．
具体的には，まず，各ステップで新たにりンクを獲得するノードに関する特徴量，すをわち，次数・平 均パス長・サーピス率等を分析し，これらの特徴量とりンクの獲得回数との相関を計算する．そし て ， こ れ ら の 特 微 量 の 大 小 に 依 存 し て ノ ー ド が り ン クを 獲得 する 生成 規 則を 設計 する ， 各章の内容を以下に要約する．
‑ 155−
第1章 では，通信ネットワークの設計に関する従来研究および近年の複雑ネットワーク研究を俯 瞰し，研究背景および研究意義について述べている．
第2章では，提案手法の着想および概要について述べている．
第3章 では，動的を通信ネットワークを待ち行列ネットワークとしてモデル化し，トラフイック 遅延の最小化を目的関数とした構造最適化問題を提案している，ある時刻から次の時刻に遷移する 際，トラフイック条件等が変化することを想定し，次のように制約条件・目的関数を設計した．まず，
制約条件として各ステップ間での構造遷移を制限する条件を与えた．これは，2条件で独立に構造最 適化を実施するとっ得られる構造が大きく異をり，ノードの追加時のりンク生成による全体構造の改 善がそもそも不可能に誼るためである．目的関数は，あるステップのある条件下でのみで待ち時間が 最小であれぱよいので誼いことから，各ステップにおける待ち時間を平均的に小とするものとして 与えた，そして，種々の動的条件下で数値実験を行い，その実験結果を分析し，生成規則の設計法を 検討した．
第4章 では．前章の数値実験で得られた解をもとに生成規則を設計し，その有効性を検証してい る．具体的には，まず，最適化で得られた解を分析し，各ステップで新たにりンクを獲得するノード に関する特徴量，す社わち，次数・平均パス長・サーピス率等を分析し，これらの特徴量とりンクの 獲得回数との相関を計算した，そして，相関のある特徴量の大小に依存してノードがりンクを獲得す る生成規則を設計した，ここでは，複雑ネットワーク研究で知られる適応度モデルを基礎として生成 規則を得る方法を提案した．得られた生成規則の有効性は数値実験によって検証され，本学位論文で 提案した構造生成規則設計手法の有効性が示された，
第5章では，本学位論文の結論について述べている．
―156 ‑
学位 論文審査の要旨
学 位 論 文 題 名
Studies on Methodology of Structural Design for Dynamic Communication Networks
（ 動 的 通 信 ネ ッ ト ワ ー ク の 構 造 設 計 手 法 に 関 す る 研 究 ）
実 社 会 のネ ッ ト ワ ー ク にお い て ， あ る機 能 要 求 を 満た す 構 造 を 設計 す る 問 題 は ，ク ラ スNPに 屈 す る組 合 せ 問 題 であ り ， 更 に ，ノ ー ド 数 や トラ フ ィ ッ ク 丗 が時 系 列 的 に 変化 す る 動 的 性質 を 有 し て お り，解 くこと が極め て困難 であ る．
近 年 ユ ー ザ ー が 急 増 し てい るSkypeで は ， トラ フ ィ ッ ク 遅延 を 短 縮 す る 要求 に 対 し ， ネッ ト ワ ー ク構 造 を 生 成 する 構 造 生 成 規則 を 開 発 し ，1千 万 人 を 超え る ユ ー ザ ー に対 し て 高品質 を通話 サー ビス を提供 してい る．
し か し を が ら ， こ の 構 造生 成 規 則 はSkypeに固 有 を 特 性 に依 存 し て お り ，他 の ネ ッ ト ワー ク に 対 して 適 用 す る こと は 困 雛 で ある ． 今 後 も 様々 を 形 態 の ネ ット ワ ー ク ア プリ ケ ー シ ョ ンの 開 発 が 期 待 されて おり， 汎用的 を設計 手法 の確立 が求め られて いる ．
本 学 位 論文 で は ， 動 的 を通 信 ネ ッ ト ワー ク に お い て， 機能 要求を 満たす 構造の 生成規 則の 汎用的 を 設計手 法を柵 築する ことを 目的 として いる，
ま ず ， 動的 を 通 信 ネ ッ トワ ー ク を 待 ち行 列 ネ ッ ト ワー クと してモ デル化 し，ト ラフィ ック 遅延を 最 小と す る 構 造 を得 る 最 適 化 問題 を 定 式 化 し， そ の 解 法 を提案 してい る． 次に， 最適榊 造にお いて 。新 たにり ンクを 獲得す るノー ドに 関する 特徴｜ ｜t すをわち，次数・平均パス長・サービス率等を分析し，
これら の特徴 ！｜よ とりン クの 獲得回 数との 間に相 関が あるこ とが明 らかにしている．そして，これらの 特徴 皿 の 大 小 に依 存 し て ノ ード が り ン ク を獲 得 す る 生 成規則 を設計 して いる． さらに ，生成 規則 を用 いて 生 成 し た ネッ ト ワ ー ク を数 値 実 験 に より 評 価 し ， 提 案手 法 が 有 効 であ る こ と を 確か め て い る ． こ れ を 要す る に ， 申 請 者は ， 動 的 を 通信 ネ ッ ト ワ ーク の構 造設計 手法に ついて 新知見 を得 たもの で あり ， 複 雑 系 工学 を ら ぴ に 調和 系 工 学 に 貢献 す る と こ ろ大を るもの があ る．よ って申 請者は ，北 海道 大学博 士（情 報科学 ）の学 位を 授与さ れる資 格ある もの と認め る，
− 157―
