命に学ぶ情報ネットワークの 組織化設計・制御

将来ネットワークに関する⼤阪⼤学における取り組み
⽣命に学ぶ情報ネットワークの
⾃⼰組織化設計・制御
村⽥正幸
⼤阪⼤学⼤学院情報科学研究科
[email protected] www.anarg.jp
September 5 th , 2014
第１回 将来ネットワーク科学リサーチシンポジウム
内容
 ⾃⼰組織化制御
「⼼地よさ」
全体構
造
ユーザ要求
の変化
環境変
動
 進化適応する情報ネット
ワークのための設計・制
御
 ⽣物における縮退機構
→SDN/NFVへの応⽤
 ⽣物における階層とモジュ
ール化→トポロジー設計・
制御、仮想化制御への応⽤
M. Murata
最適解への移⾏
E
A
F
B
D
C
2
⽣物の⾃⼰組織化
管理型⾃⼰組織化制御
新世代ネットワークの展開
 仮想化
 SDN (Software-Defined Network)／OpenFlow、
NFV (Network Functions Virtualization)
 サービスの多様な発展の促進、HWのコモディティ化、SW
制御によるHWの多様な技術発展の吸収
 IoT (Internet of Things)、M2M (Machineto-Machine Communication)
 実社会と仮想社会の融合
 CCN (Content Centric Networking)/ICN
(Information Centric Networking)
M. Murata
3
 アドレス指定（ホスト指定＋DNS）ではなく、コンテンツ
名によるルーティングと発⾒
実現できていないこと
⼤規模複雑システムを対象とした
 時間ダイナミクスへの対応
 短期：（急激な）トラヒック変動、故障、情
報粒度
 ⻑期：トラヒック増⼤（⻑期的増⼤）、新し
いサービスの登場に対する変動
 空間ダイナミクスへの対応
 短期：モビリティ
 ⻑期：情報数／端末数／ノード数／インター
ネット全体の構成に関する規模的成⻑
 インターネット
Hyper Giantsの登場によるトポ
ロジー、トラヒック流の⾮構造化
 IoT/M2M
制御フィードバックによる時間変
動の取り扱い？
 CCN/SDN/NFV
「時空間ダイナミクスに対する適
応を可能にする」ツール
→その解決策は今後
M. Murata
Sasitharan Balasubramaniam, Kenji Leibnitz, Pietro Lio, Dmitri Botvich, Masayuki
Murata, “Biological Principles for Future Internet Architecture Design,” IEEE
Communication Magazine, vol. 49, Issue 7, pp. 44-52, July 2011.
4
SRC: ATLAS Internet Observatory 2009 Annual Report, C. Labovitz, S. Iekel-Johnson, D. McPherson
設計原理としての⾃⼰組織化⼿法

⾃⼰組織化原理の⽬標
 各コンポーネントは、隣接するコンポーネント、あるいは、環境との
インタラクションによって、全体の構造や機能を発現する
 ボトムアップ的システム設計⼿法
 トップダウン的設計⼿法（要素還元論）の限界
 ダイナミクス（環境変動）への適応能⼒
 ⼤規模化、複雑化への適応能⼒
 具体的な実現⼿法
A large number of redundant components
A certain degree of randomness
No central coordinator
A combination of positive and negative feedback
Emergent behavior from numerous local
interactions
S. Camazine, J. Deneubourg, N. R. Franks, J. Sneyd, G. Theraulaz, & E.
Bonabeau, Self-Organization in Biological Systems, 2001.
⾃⼰組織型情報ネットワーク制御
ランダム性の導⼊による新しい安定解の発⾒
正のフィードバック+負のフィードバックによる安定化
エンティティ間の局所的通信による全体制御の実現
時間的・空間的変動（外的変動；トラヒック変動や新サ
ービス創出、内的変動；故障）のあるシステムに対する
ロバスト性の確保
M. Murata
6

群知能に基づく情報伝搬機構
 各ノードは近接ノードと制御情報を交換して、トポロジー構築、経路
制御を⾃⼰組織的に実現
 任意のノードによる情報拡散・収集を⾃⼰組織的に構成
 情報拡散：ノードから周縁に向かって情報伝達
 情報収集：ノードへ周縁から情報伝達
 パルス結合振動⼦における進⾏波現象を利⽤
蛍の発光同期・進
⾏波現象
情報波の伝達
パルス結合振動⼦モデル
振動⼦集合
振動⼦のタイマ位相
タイマ位相が1に達すると振動⼦は発⽕
結合された振動⼦は刺激を受け位相が進⾏
センサネットワーク上で
さまざまな進⾏波を形成
M. Murata
Naoki Wakamiya and Masayuki Murata, “Scalable and robust scheme
for data fusion in sensor networks,” in Proceedings of the First
International Workshop on Biologically Inspired Approaches to
Advanced Information Technology, (Lausanne), pp. 305-314,
January 2004.
7
刺激を受けた結果，振動⼦が発⽕→同期
固定の位相差で発⽕→進⾏波
⽣物に学ぶ⾃⼰組織型ネットワーク制御
対象システムの特性
・⼤規模かつ複雑
・環境が変動する
1. 他ユーザの利⽤状況
2. ⾃⾝の利⽤状況
3. 資源⾃⾝の変動
4. 統計情報の変動
→集中型制御による最適化
→状態空間の爆発
・発⾒的解法
GA (Genetic Algorithm)法、NN法
SA (Simulated Annealing)法
→局所最適解からの脱出に確率を⽤いる
→環境変動に対しては？
⽣物に学ぶ
⾃⼰組織型制御
環境変動への
適応性
最適性
効率
ロバスト性
 「⾼速⼤容量」ネットワーク
M. Murata
・情報を収集し、個別最適解を準備
→
信頼のできるネットワーク
8
量
よ
り
質
！
従来の⼿法
⾃⼰組織化制御に対して指摘される問題
M. Murata
11
1. 「創発＝「結果がわからない」のでは使えない」
 ミクロ→マクロ：要素還元論にとらわれすぎ
 サブシステムの積み上げによる全体システムの設計の限界が、今抱
えている問題
2. 「管理できないネットワークは使えない」
 「管理する」の意味
 現状の状態を把握している？／資源を操作する？
 時間粒度の異なる話をしていないか
3. 「保証できないネットワークはビジネスに使えない」
 現状、すべてを保証できるしかけはない
 問題がなければ、何をやっても（やらなくても）うまくいく
4. 「評価⼿法がない」
 現状シミュレーション
管理型⾃⼰組織化制御
⾃律分散システム
システムが予め想定した動作条件に対して⾃律的
に適応
創発
⾃⼰組織化システム
⾃⼰組織化システム
集中制御なしに、ダイナミックに変化する環境に
おいて動作する。想定困難な状況に対しても、創
発的に対応する
管理型⾃⼰組織化システム
⾃⼰組織化原理を維持しつつ、外部操作によって
動作する範囲を設定する
⾃⼰組織化エレメント
集中／分散コントローラ
観測
制御動作
⾃⼰組織化エレメント
M. Murata
機能発現：ボトムアップ
全体適応：トップダウン
12
⾃⼰組織化システム
ポテンシャル場による⾃⼰組織型経路制御
 近接作⽤に基づくポテンシャル場の構築
 ノード間の局所情報の交換により⾃⼰組織的にポテンシャル場を構
築
Φ : ポテンシャル
t
D
n
nb
 熱拡散⽅程式を離散化した式を利⽤
:
:
:
:
時間
拡散定数
ノード
隣接ノード集合
 境界条件として、シンクノードに最⼩ポテンシャルを設定
 グラディエントを利⽤した経路決定
 次ホップとして望ましいノードほど低いポテンシャルを所持
 ポテンシャルがより低い隣接ノードを次ホップに選択
ポテンシャル場
M. Murata
Data
Sensor node
Sink node
13
Data
管理ノードによる負荷分散制御
 シンクノードを介したポテンシャル場の誘導的形成
 トラヒックの⼤域的負荷分散
例）複数のシンクノードに届くトラヒック量を均等化
複数のシンクノードの ”隣接局” の消費電⼒の均等化
Sensor node
Sink node

管理ノード
管理ノード
受信パケット個数
１パラメータ
１パラメータ
負荷の偏りを検出
シンクノードのポテンシャルを変更
適切なポテンシャルの値
負荷を分散
M. Murata
D. Kominami , M. Sugano, M. Murata, T. Hatauchi, “Controlled and Self-Organized Routing
for Large-Scale Wireless Sensor Networks,” ACM Transactions on Sensor Networks, 2014
14
 管理ノードの定期的な監視と管理によるフィードバック
 個々のノードは局所情報に基づき⾃⼰組織的に⾃⾝のポテンシャル
を決定するにもかかわらず管理者の望むポテンシャル場を実現
ゆらぎ⽅程式から情報ネットワークへ
d
x  f ( x)   
dt
アトラクタを持つ制御構造
ゆらぎを利⽤できる形で
受け⼊れる構造
f(x)=－dU(x)/dx
・各階層における制御・プ
ロトコルの動作
系の状態
状態が良いと
感じる度合い
スカラーとは限らない
ブラウン運動
歪み
センサー
熱ゆらぎ、⾃発ゆらぎ
ゆらぎの構造
システムの現在の状態
・システム遅延の逆数
・スループット
ノイズによるシステム駆動
・局所最適解からの脱出
・環境変動への適応
 階層化アーキテクチャをとる情報ネットワークにおいて、各階層プロトコルをアトラク
タを持つ制御構造によって実現し、新しい情報ネットワークアーキテクチャを実現する
M. Murata
18
 If-then-else型で扱われてきた制御システムを、ゆらぎ制御を⽤いてモデル化し、頑強
かつ環境変動に柔軟に適応可能な情報ネットワークシステムを実現
ゆらぎ原理による経路制御
常に変動している通信状況を環境情報とし
て取り込みながら，適応的で応答性のよい
経路制御を実現
九州
d
x  f (x)    
dt
経路選択確率
活性度
関東
最適解でない場合で
も、それに近い経路
をゆらぎ探索可能
ノイズ
d
s ( )
mi 
 d ( )mi  
2
2
dt
1  mmax  mi
activity: 経路の良さ(リンクスピード，遅延時間の逆数）
path 1
path 2
path 3
path 4
path 5
activity
0
2000
4000
Time
6000
8000
故障発⽣時に素早く回避
負荷変動などの環境変動に
対する素早い対応
19
M. Murata
経路選択確率
Kenji Leibnitz, Naoki Wakamiya and
Masayuki Murata, “Biologicallyinspired self-adaptive multi-path
routing in overlay networks,”
Communications of the ACM, Vol. 49,
No.3, pp. 62-67, March 2006.
•
•
ゆらぎ制御における解探索
１） α が固定（与条件）の場合、かつ、
η が０の場合
• ⾮線形連続時間発展⽅程式を明⽰的に
解くことが可能な場合もある。
• 過去の最適化に関するほとんどの研究
がこの場合「与条件固定、かつ、環境
の時間変動なし」を明⽰的・暗⽰的に
仮定
２） α が時間変動する場合、ただし、
η=０の場合
• 時々の α に依って最適解を導出する
ことは可能。ただし、局所最適解の場
合がある。また、計算を瞬時に⾏うこ
とが必須。
３）
α が時間変動し、かつ、η≠０とし
-dU(x)/dx = f(x)
た場合
• 局所最適解から脱出することが可能に
なる。
• ただし、最適解に到達した場合にも、
収束せずに近傍で振動する
• ゆらぎ制御のねらいは、環境変動が
あった場合にも、それをα を介して知
り、適応可能にしているところにある
M. Murata
Kenji Leibnitz, and Masayuki Murata, “Attractor selection and perturbation for
robust networks in fluctuating environments,” IEEE Network: The Magazine
of Global Internetworking, vol.24, no.3, pp.14-18, May/June 2010
20
• Activityの変化による最適解
の移動
• f(x)がactivityにより変化
• その上で、ランダム性を印
加
管理型⾃⼰組織化制御としてのゆらぎ制御
d
x  f(x)  α  η
dt
「⼼地よさ」
外的環境変動
全体構造
最適解への移⾏
内的環境変動
M. Murata
柳⽥敏雄, 四⽅哲也, ⽯⿊浩, 村⽥正幸, “⽣体ゆらぎに学ぶ知的⼈⼯
物と情報システム,” 応⽤物理学会誌, vol. 78, no. 7, August
2009.
21
個々のエンティティは環境に応じて⾃律的に動作
光通信基盤への適⽤
物理網（WDMベー
スの波⻑ルーティン
グネットワーク）上
に、論理トポロジー
（波⻑パスベースの
仮想ネットワーク；
VNT）を構築
IPネットワーク
ルータ
①ネットワーク品質を計測
②活性度計算
④仮想網設定投⼊
光通信ネットワーク基盤
M. Murata
Yuki Koizumi, Takashi Miyamura, Shinʼichi Arakawa, Eiji Oki, Kohei Shiomoto,
and Masayuki Murata “Adaptive virtual network topology control based on
attractor selection,” IEEE/OSA Journal of Lightwave Technology, vol. 28, pp.
1720–1731, June 2010.
24
③アトラクター選択
進化適応性の進化 (Evolution of Evolvability)
M. Murata
28
 「短期的な環境変動に対する適応性を失うこ
となく、⻑期にわたる予測困難な環境変動に
も適応して進化する能⼒」
 進化適応性を確保するためのしくみ
縮退特性（Degeneracy; networked
buffering）
表現型の可塑性（Plasticity）；エピジェネ
ティクス
階層化とモジュラリティ (Hierarchy and
modularity)
選択的淘汰⇒最適化≠多様性：パラドックス
 環境変化に対して選択によって適応す
る
新しい環境に適応するには多様性が必要
しかし、選択的淘汰の結果、多様性が失われ
る
• ⼤腸菌を対象にした実験結果では、
数⼗世代で新しい環境への適応性
が得られることがわかっている
• ⼀⽅、⼤腸菌は進化の袋⼩路に⼊
り込んでいる（すでに最適化され
ている）という⽣物学者もいる
 実際には、環境条件が変わると時間を
経ず進化できる（適応的進化）
Complexity
 中⽴変異
隠れた遺伝的変異（隠蔽変異、CGV: Cryptic
Genetic Variation）は、 通常の環境では表
現型の違いを⽣み出さない
遺伝的・環境的な撹乱を受けたときに表現型
多型として顕在化
Rを向上させ
るとCが増⼤
Degeneracy
DはRの源
Robustness
Dによって
Eが増⼤
RによってEが出現
Evolvability
The Diversity Paradox: How Nature Resolves an
Evolutionary Dilemma, James M. Whitacre, Sergei P.
Atamas, arXiv:1112.3115, 2011.
29
M. Murata
DはCと正の相関
CはEの必
須条件
新しい設計原理：環境適応性と進化適応性
 進化適応性 (Evolution of
Evolvability) のある持続的成⻑可能性
 ⻑期的には、進化しすぎて袋⼩路に⼊り
込む（最適化）ことなく、将来に渡る予
測困難な変化に対して適応できる進化適
応性
 短期的には、環境変動に対してロバスト
な環境適応性
M. Murata
31
 ネットワーク⽤語で⾔いかえると
 環境適応性：トラヒック変動、耐故障性
、近接の機能を選ぶ
 進化適応性：予測困難なシステム規模拡
⼤、利⽤形態の変化、機能要求の変化と
移動
進化適応可能なネットワークの
デザインアーキテクチャ
 短期的には仮想化技術を使って
局所的な⾃⼰組織化⼿法によっ
て対応。
 中⻑期の定期的なネットワーク
増強時には成⻑耐性を持つトポ
ロジー設計。
ネットワーク規模（新しいサービ
ス、新しいネットワーク）の拡⼤
によるトラヒック量増⼤
時間（⽇単位〜年単位）
M. Murata
新規設備投資
32
ネットワーク規模（総資源量）
古典的ネットワーク設計⼿法
ネットワーク全体のトラヒック量
計測に基づき、全体のコスト最適
化問題を解き、回線容量、ノード
増設を決定する
進化適応可能なネットワーク
 「中⻑期に渡って、短期的ロバスト性を失うことなく、予測
困難な環境に適応する能⼒を有する」ネットワーク
 進化適応性を確保するためのしくみ
縮退特性（Degeneracy; networked buffering）
情報理論的アプローチ
可塑性（Plasticity）
遺伝的多様性＝環境変動に対する遺伝発現の分散
階層化とモジュラリティ (Hierarchy and modularity)
 モジュラー構造→フラクタル特性
M. Murata
環境情報取
得
マイニン
グ＆予測
制御
性能計測
33
プランニ
ング
⽣物ネットワークの縮退特性
SRC: Striate cortical lesions affect deliberate decision
and control of saccade: Implication for blindsight, The
Journal of Neuroscience, Vol. 28, No. 42, pp. 10517–
10530 (2008).
 ネットワーク化バッファ
リング
 ネットワークの複数の構成要
素が、ある環境では互いに異
なる機能を実⾏する
 異なる環境においては他の構
成要素と同じ機能を実⾏する
例: 脳の補償活動
 そのためには、
 各構成要素が複数の機能を実
⾏可能で、かつ
 複数の構成要素の実⾏可能な
機能が部分的に重複している
E
A
F
B
D
C
M. Murata
34
発現パターンの変化による
タンパク質Dの発現数の不⾜の解消
WEBサービスへの適⽤
 複数のサービスコンポーネントの組み合わせ
 障害発⽣により特定のサービスコンポーネントの実⾏数が不⾜する場
合、各サーバの実⾏するサービスコンポーネントの変更により不⾜を
解消
M. Murata
⻑⾕川剛, 村⽥正幸, “⽣物ネットワークの縮退特性に基づくシステム冗⻑化⽅式に
おける⾃律的障害回復⼿法,” 電⼦情報通信学会技術研究報告, vol.113, no.4,
pp.31-36, NS2013-7, Apr. 2013.
35
 サーバがインストールするサービスコンポーネントの決定⽅法およびノー
ドへのサーバの収容⽅法
冗⻑化⼿法
 サーバがインストールするサービ
スコンポーネントの決定⽅法
 部分重複化⼿法
 各サーバがインストールするサー
ビスコンポーネントに部分的な重
複関係を発⽣
• パラメータ設定
•
•
•
•
サービスコンポーネント種類数: 200, ノード数: 100
各ノードに収容するサーバ数: 4
各サーバにインストールするサービスコンポーネント数: 2
各サーバが実⾏するサービスコンポーネント数: 1
 単純冗⻑化⼿法
M. Murata
36
 ランダム⼿法
様々なネットワークの相互情報量
R. Sole and S. Valverde, “Information theory of complex
networks: On evolution and architectural constraints,”
Complex Networks, vol. 650, pp. 189–207, Aug. 2004.
 残存次数の相互情報量を⽤いた
多様性評価

⼈⼯ネットワーク
:残存次数分布
⽣物ネットワーク
ソフトウェアネットワーク
代謝ネットワーク
電⼦回路
M. Murata
37
⽣成モデル
ルータレベルトポロジーの相互情報量
 ルーターレベルトポロジーは設計理念に基づいて設計されている（は
ず）
 規則性がある→多様性が低い
 実際、ルーターレベルトポロジーの多くは相互情報量が⼤きい
 最適化だけでなく、技術的・物理的な制約を考慮した設計にも起因？
 ただし、Verio 社の相互情報量は⼩さい
 ⼩規模な地域ISPの買収を繰り返して規模を拡⼤したことに起因(?)
Telstra Sprint AT&T Level3 Verio
ノード数
リンク数
H
Hc
I
M. Murata
329 467 523 623 839
615 1280 1304 5298 1885
4.24 4.74 4.46 6.04 4.65
3.11 3.84 3.58 5.42 4.32
1.13
0.9 0.88 0.61 0.33
確率的に⽣成され
たトポロジー
BA
523
1304
4.24
3.98
0.26
Random
523
1304
3.22
3.15
0.07
相互情報量 が⼩さい：
構造が多様
相互情報量 が⼤きい：
構造に規則性が出現
Lu Chen, Shinʼichi Arakawa, Hideyuki Koto, Nagao Ogino, Hidetoshi Yokota, and
Masayuki Murata, “Designing an Evolvable Network with Topological Diversity,” IEEE
International Workshop on Network Science for Communication Networks (in
conjunction with IEEE Infocom 2014), March 2014.
38
ISP のルータレベルトポロジー
階層化とモジュラリティ
 モジュールは階層構造の構成要素というだけでなく、ロバス
ト性、進化可能性の源泉
 モジュール内のダイナミクスはモジュールに閉じ込める
 モジュール構造によって進化を早める（全体の最適化を避ける）
 内部構造を設計し直さなくても、全体の機能を進化させることがで
きる
• Kashtan N, Noor E, Alon U (2007) Varying environments can speed up evolution. Proc Natl Acad
Sci, 104: 13711–13716.
• Kashtan N, Alon U (2005) Spontaneous evolution of modularity and network motifs. Proc Natl
Acad Sci, 102: 13773–13778.
AT＆T トポロジの構造
⽶国ASトポロジーの構造
M. Murata
Shin'ichi Arakawa, Tetsuya Takine, and Masayuki Murata, “Analyzing and
Modeling Router-level Internet Topology and Application to Routing
Control,” Computer Communications, Vol. 35, No. 8, pp. 980-992, May
2012.
39
http://sf0.org/thecunninglinguist/What-Is-The-Internet/
脳機能ネットワークのフラクタル特性分析
•
•
モジュールレベルトポロジー
Song, C., Havlin, S., and
Makse, H. A. Self-similarity
of complex networks. Nature
433, 392.
Song, C., Havlin, S., and
Makse, H. A. Origins of
fractality in the growth of
complex networks. Nat. Phys.
2, 275.
階層
• フラクタル性
• スケールフリー性
• 低い次数相関
モジュール内部トポロジー
• スケールフリー性
• ⾼い次数相関
モジュール間リンク
１．モジュール間の接続が多様である
２．故障がモジュール外部へ波及しない
３．下位階層での故障が上位階層へ波及しない
M. Murata
6.E-02
物理距離最⼩設計
（情報NW）
ISP (AT&T)
2.E-02
Scale-free
4.E-03
1.E-03
1
2
4
8
四條能伸, 荒川伸⼀, 村⽥正幸, “フラクタル性に着⽬した脳機能ネット
ワークの接続構造の分析とネットワークの⾼品質化への応⽤,” 電⼦情
報通信学会IN研究会発表予定
16
40
ネットワークの観点から
3.E-01
/
• ⼤きなモジュールは様々なモジュールと多
数のリンクを構築
• ⼩さなモジュールは⼤きなモジュールと優
先的にリンクを構築
• モジュール内部の平均次数となるノードが
多数のリンクを構築
1.E+00
融合研究で学んだこと
M. Murata
41
新しい発想の種は隣にある
異なる分野の研究者との対話こそ新しい
発想の源