多重パスメッセージ転送ネットワークの数理モデルと論理 沼澤政信* 栗原正仁** *小樽商科大学商学部社会情報学科 **北海道大学大学院工学研究科システム情報工学専攻

モバイルエージェントとは？ 位置透過性とは？ エージェント技術 ネットワークのような動的なシステムに対して， 信頼性やロバスト性を提供する有効な技術 モバイルエージェント(mobile agent) インターネット上のノード間を移動するエージェント 位置透過性(location transparency)をもつシステムでは，他のエージェントの位置情報を知ることなしにエージェント同士が互いに通信できる． 2003.9.16 第4回WINGS

位置透過性を実現する 3つの基本モデル 探索モデル(searching model) 　通信相手のエージェントが存在し得る位置についての事前知識をもち，メッセージを送る前にそれらの位置すべてに検索メッセージをブロードキャストすることにより相手の現在位置を見つける 登録モデル(registering model) 　エージェントは特定のディレクトリサーバ上の自らの位置情報を自ら更新する 転送モデル(forwarding model) 　エージェントが現在のノードから移動する前にそのノード内に移動先ノードへのポインタを記憶させ，ポインタの列（パス）を作成する． これに沿って，将来受信したメッセージが 目標のエージェントへと転送される． 2003.9.16 第4回WINGS

転送モデルの問題点 －ロバスト性の欠如－ ポインタの列（パス）に沿って，将来受信したメッセージが 転送モデルの問題点 －ロバスト性の欠如－ ポインタの列（パス）に沿って，将来受信したメッセージが 目標のエージェント（以後，ターゲットと呼ぶ）へと転送される モバイルエージェント (ターゲット) 2003.9.16 第4回WINGS

転送モデルの問題点 －ロバスト性の欠如－ ◆パス上の一つのノードが故障すると… 次のノード位置を示すポインタも失われるため， 転送モデルの問題点 －ロバスト性の欠如－ ◆パス上の一つのノードが故障すると… 次のノード位置を示すポインタも失われるため， メッセージを目標のエージェントまで転送できない 故障 モバイルエージェント (ターゲット) 2003.9.16 第4回WINGS

多重パスメッセージ転送ネットワーク （MMFN：multi-path message forwarding networks） ノードとターゲットの間の多重パスにより， ロバスト性なメッセージ送信が可能 n 次のMMFNにおいては，故障ノード数が高々 n 個であるならば，すべてのノードについて，ターゲットまでのパスの存在を保証する ※ MMFN は整数 n で表される次数（degree）により分類 2003.9.16 第4回WINGS

本発表の内容 【投稿論文-目次】 序論 多重パスメッセージ転送ネットワーク MMFN の動的メカニズムの数理モデル 関連研究 結論 準備 論理システム Ln 健全性 計算論的解釈 関連研究 結論 2003.9.16 第4回WINGS

次に説明する内容は… 【投稿論文-目次】 序論 多重パスメッセージ転送ネットワーク MMFNの定義 MMFN の動的メカニズムの数理モデル 準備 MMFNの定義 MMFNのロバスト性 MMFN の動的メカニズムの数理モデル 論理システム Ln 健全性 計算論的解釈 関連研究 結論 2003.9.16 第4回WINGS

MMFNの定義 定義1 ：次数 n （ n は非負整数）のMMFNは 以下の条件を満たす有限で単純な無閉路グラフ G = (V, E) である． すべてのノード v ∈ V は od(v) ≤ n + 1 を満たす，かつ 任意の整数 i （0 ≤ i ≤ n）について， od(v) = i であるノード v ∈ V がただ一つ存在する． ※ v からの外向きリンクの数を v の出次数（outdegree） と呼び，od(v) と記述する a od(a) = 2 2003.9.16 第4回WINGS

MMFNの定義 ◆ 次数 i の特殊ノード（special node） si od(si) = i （0 ≤ i ≤ n）を満たす唯一のノード ◆ ターゲット（target） s0 次数 0 の特殊ノード ◆ 残余ノード（residual nodes） r od(r) = n + 1 を満たす残りのノード 定義1 ：次数 n （ n は非負整数）のMMFNは 以下の条件を満たす有限で単純な無閉路グラフ G = (V, E) である． すべてのノード v ∈ V は od(v) ≤ n + 1 を満たす，かつ 任意の整数 i （0 ≤ i ≤ n）について， od(v) = i であるノード v ∈ V がただ一つ存在する． ※ v からの外向きリンクの数を v の出次数（outdegree） と呼び，od(v) と記述する a od(a) = 2 2003.9.16 第4回WINGS

次数 n のMMFN の例 2003.9.16 第4回WINGS

次に説明する内容は… 【投稿論文-目次】 序論 多重パスメッセージ転送ネットワーク MMFNのロバスト性 準備 MMFNの定義 MMFNのロバスト性 MMFN の動的メカニズムの数理モデル 論理システム Ln 健全性 計算論的解釈 関連研究 結論 2003.9.16 第4回WINGS

MMFNのロバスト性（1） 定理1 G = (V, E) はターゲットを t とする次数 n のMMFN であるとする．このとき，任意のノード v ∈ V と任意の集合 A ⊆ V − {v, t} について，もし |A| ≤ n ならば，A のいずれのノードも通過しない v から t へのパスが存在する． 高々 n 個のノードが故障状態になろうともメッセージ はターゲットへ転送可能である ⇒ ロバスト性（robustness）がある 2003.9.16 第4回WINGS

MMFNのロバスト性（2） 上記の次数 2 のMMFNにおいては，2つのノードが故障した場合でも，ノード v で受信したメッセージはターゲット t へ転送可能である． 2003.9.16 第4回WINGS

次に説明する内容は… 【投稿論文-目次】 序論 多重パスメッセージ転送ネットワーク MMFN の動的メカニズムの数理モデル 準備 MMFNの定義 MMFNのロバスト性 MMFN の動的メカニズムの数理モデル 論理システム Ln 健全性 計算論的解釈 関連研究 結論 2003.9.16 第4回WINGS

配置（configuration）：論理式 グラフ G = (R + S, E) が特殊ノード S と残余ノード R をもつ 次数 n の MMFN であるときに限り真となる論理命題 次数 残余ノードの集合 特殊ノードの列 リンク の集合 S は，要素を i について降順に並べた順序集合（ordered set）とみなし，ドット「.」により要素を分けて列 sn.sn−1. ・ ・ ・ .s0 として記述する． たとえば，s.S は最初（最左）の要素 s の後に列 S が続く列を表す. 2003.9.16 第4回WINGS

論理システム Ln Ln この動的メカニズムを6つの推論規則からなる 論理システム Ln により形式的に表現する． スタート a 配置は，エージェントがノードからノードへ移動した後も，MMFN がもつべき性質を保持するように再構成されなければならない． この動的メカニズムを6つの推論規則からなる 論理システム Ln により形式的に表現する． スタート a ノード u による拡張 Ln 新しいノード u への移動 特殊ノード s への移動 残余ノード r への移動 ノード v をバイパス 2003.9.16 第4回WINGS

スタート a 初期状態 次数0 残余ノードなし リンクなし ターゲット 2003.9.16 第4回WINGS

ノード u による拡張 残余ノードなし 次数が 増える 特殊ノード 適用前 S t 2003.9.16 第4回WINGS

ノード u による拡張 S t u 残余ノードなし 次数が 増える 適用後 適用前 特殊ノード 特殊ノード 2003.9.16 第4回WINGS

新しいノード u への移動 次数変化なし 適用前 残余ノード 特殊ノード R S t s 2003.9.16 第4回WINGS

新しいノード u への移動 R S t u s 次数変化なし 適用前 適用後 残余ノード 残余ノード 特殊ノード 特殊ノード 2003.9.16 第4回WINGS

例 a スタート a ノード b による拡張 新しいノード c への移動 新しいノード d への移動 b c d n=0 n=1 n=1 2003.9.16 第4回WINGS

特殊ノード s への移動 適用前 特殊ノード 残余ノード R S S t s 2003.9.16 第4回WINGS

特殊ノード s への移動 適用後 適用前 特殊ノード 残余ノード R S S t s 2003.9.16 第4回WINGS

残余ノード r への移動 適用前 残余ノード 特殊ノード R S t r s 2003.9.16 第4回WINGS

残余ノード r への移動 R S t r s 適用後 適用前 残余ノード 残余ノード 特殊ノード 特殊ノード (ターゲット) 2003.9.16 第4回WINGS

例 特殊ノード c への移動 新しいノード d への移動 a b c d 残余ノード a への移動 n=1 n=1 n=1 2003.9.16 第4回WINGS

ノード v をバイパス 適用前 u v w 2003.9.16 第4回WINGS

ノード v をバイパス 適用後 適用前 u v w 2003.9.16 第4回WINGS

次に説明する内容は… 【投稿論文-目次】 序論 多重パスメッセージ転送ネットワーク MMFN の動的メカニズムの数理モデル 健全性 関連研究 準備 MMFNの定義 MMFNのロバスト性 MMFN の動的メカニズムの数理モデル 論理システム Ln 健全性 計算論的解釈 関連研究 結論 2003.9.16 第4回WINGS

論理システム Ln の健全性（soundness） 配置 G が論理システム Ln によって導出される G が定義1 のすべての条件を 満たしたMMFN である 定理2 もし G であるならば G である． Ln が生成する G はすべて MMFN である ⇒健全性（soundness）をもつ 2003.9.16 第4回WINGS

次に説明する内容は… 【投稿論文-目次】 序論 多重パスメッセージ転送ネットワーク MMFN の動的メカニズムの数理モデル 計算論的解釈 準備 MMFNの定義 MMFNのロバスト性 MMFN の動的メカニズムの数理モデル 論理システム Ln 健全性 計算論的解釈 関連研究 結論 2003.9.16 第4回WINGS

計算論的解釈（1） v w ノードは，プロセッサ，メモリ，通信ポートのような 計算資源をもつ計算ノードとみなすことができる （もしくは参照）として解釈 2003.9.16 第4回WINGS

計算論的解釈（2） s2 s1 t 論理システム Ln の各々の推論規則 ⇒ 遠隔操作（ remote procedure ） s2 s1 次数2 s2 s1 t 必要な情報を得るために ネットワーク全体の解析や探索をせずに， 各々の操作を実現することができる エージェントに現在の次数 k と， 全 k + 1 個の特殊ノード sk. … .s0 の現在位置の列 S を持たせる 2003.9.16 第4回WINGS

計算論的解釈（3） システムの計算量 定理3 Ln の時間計算量の上限は 2(n+1) ， V = R + S をネットワーク (R, S; E; n) のノード集合であるとする 定理3 Ln の時間計算量の上限は 2(n+1) ， Ln の領域計算量の上限は (n + 1)|V | である． 定数 n が与えられたとき， 時間計算量は（ |V | に独立な）定数であり， 領域計算量は |V | に比例する 2003.9.16 第4回WINGS

次に説明する内容は… 関連研究 【投稿論文-目次】 序論 多重パスメッセージ転送ネットワーク MMFN の動的メカニズムの数理モデル 結論 準備 MMFNの定義 MMFNのロバスト性 MMFN の動的メカニズムの数理モデル 論理システム Ln 健全性 計算論的解釈 関連研究 結論 2003.9.16 第4回WINGS

関連研究 本論文で提案したモデルは既存の高性能なモデルの いずれかを置き換えようとするものではなく，既存の モデルに取り入れて，ネットワークのロバスト性を任意 の次数にまで改善することを意図している． 探索モデル（Searching models） A.L.Murphy and G.P.Picco (1999) W.-S.E.Chen and C.-W.R.Leng(1997) 登録モデル（Registering models） T.Xianping, J.Lu, et al.(1997) M.van Steen, F.J.Hauck, et al.(1998) V.Roth and J.Peters (2001) 転送モデル（Forwarding models） S. Lazar, I.Weerakoon, el al. (1998) W.van Belle, K.Verelst, et al. (1999) M.Kurihara and M.Numazawa (2001) L. Moreau (1999) ハイブリッドモデル（Hybrid models） P.Wojciechowski and P.Sewell (1999) X.Feng, J.Cao, et al. (2001) 2003.9.16 第4回WINGS

まとめ 位置透過な通信のための多重パスメッセージ転送ネットワーク（MMFN） 今後の課題 グラフ理論によるMMFNの定義 論理システム Ln Ln の健全性 Ln の計算論的解釈 今後の課題 Ln の完全性 適切な次数 n を決定する方法 2003.9.16 第4回WINGS

多重パスメッセージ転送ネットワーク （MMFN：multi-path message forwarding networks） 配置（configuration）：論理式 論理システム Ln スタート a ノード u による拡張 新しいノード u への移動 特殊ノード s への移動 残余ノード r への移動 ノード v をバイパス 論理システム Ln の健全性 計算論的解釈 システムの計算量 関連研究 2003.9.16 第4回WINGS