モバイルエージェントネットワークの拡張とシミュレーション 大西 量 北海道工業大学
位置透過性を持つメッセージ通信 移動前のホストに移動先を通知 送信元はそのホストにメッセージを送信 ホストがメッセージを受け取って本来の通信相手が存在する移動先ホストに転送 Source Host 1 Host 2 Destination Message
問題点 どこか1箇所でも通信不能なホストがあるとメッセージは相手に届かない n次モバイルエージェントネットワーク によって解決 Source Host 1 Host 2 Destination Message n次モバイルエージェントネットワーク によって解決
n次モバイルエージェントネットワーク 有限で単純な無閉路有向グラフG=(V, E) Vに属する頂点: ホスト Eに属する有向辺: リンク 単純グラフ： 平行辺を持たない 無閉路グラフ： 回路を持たない n: 許容できる通信不能なホストの数
n次モバイルエージェントネットワーク(2) ターゲット: 外向きのリンクを持たないただ一つのホスト プロキシ: ターゲット以外のホスト k次プロキシ: 外向きのリンクの数がk個あるプロキシ 特殊プロキシ: k≦n であるk次プロキシ 正規プロキシ: 特殊プロキシでないプロキシ すべての特殊プロキシはターゲットを終点とするリンクを持つ
モバイルエージェントネットワークの例 (n=1) p s t 正規プロキシ 特殊プロキシ ターゲット
モバイルエージェントネットワークの信頼性 [定理] 互いに異なる任意のプロキシvとn個のプロキシw1・・・wnについて、どのw1・・・wnも通らないvからターゲットまでの経路が存在する t W3 W1 v W2
証明 vから以下のように適切な経路を辿る k本＞n 正規プロキシにいる間は終点がw1・・・wnのどれでもないリンクを辿る
証明(続き) いつかはターゲットか特殊プロキシにたどり着く 特殊プロキシに居るときはターゲットを終点とするリンクを辿る ターゲットに居るのならば終了 t s 特殊プロキシ ターゲット
モバイルエージェントネットワーク書き換え系 モバイルエージェントネットワーク の動的変化を表現 4つの規則 新しいホストへの移動 特殊プロキシへの移動 正規プロキシへの移動 バイパス 発展 修復
規則1. 新しいホストへの移動 (V, E) → (V + {u}, E + {(t, u)} 規則1. 新しいホストへの移動 (V, E) → (V + {u}, E + {(t, u)} + {(s1, u), (s2, u), …, (si, u)}) s2 s1 t u s2 s1 t (n=2)
規則2. 特殊プロキシへの移動 (V, E) → (V, E ＼ {{(sk, s1), (sk, s2), …, (sk, sk-1)} + {(sk, t)}} + {(s1, sk), (s2, sk), …, (sk-1, sk)} + {(t, sk)}) s2 s1 t s2 s1 t s2への移動(n=2)
規則3. 正規プロキシへの移動 (V, E) → (V, E ＼ {(u, x1), (u, x2), …, (u, xj)} + {(t, u)} + {(s1, u), (s2, u), …, (si, u)}) u s2 s1 t u s2 s1 t uへの移動(n=2)
規則4. バイパス v ≠ w のとき (V, E) → (V, E ＼ {(u, v)} + {(u, w)}) u v w u v w
モバイルエージェントネットワーク書き換え系 の健全性 [定理2] G0 → *G ならば、G はモバイルエージェントネットワークである。 t s 初期モバイルエージェントネットワークG0
証明 G0がモバイルエージェントネットワークであることは明白 Gがモバイルエージェントネットワーク かつ G→G’ならば G’はモバイルエージェントネットワーク グラフの有限性、単純性、非循環性
モバイルエージェントネットワークの シミュレーション n次モバイルエージェントネットワークを シミュレート 任意ホストに移動させ、メッセージを移動元から転送
モバイルエージェント ネットワークシミュレータ(1)
モバイルエージェント ネットワークシミュレータ(2)
おわりに モバイルエージェントネットワークの拡張 ネットワークの拡張による信頼性向上 ネットワーク書き換え系 書き換え系の健全性 シミュレート モバイルエージェントシステムに実装