修士論文
コ ン テ ン ツ 指 向 ネ ッ トワ ー ク に お け る 移 動 端 末 を考 慮 した 蟻 コ ロ ニ ー 最 適 化 を
用 い た 経 路 制 御 法
14892526馬 目 慎 太 郎
指導教員 朝香 卓也
2016年1月
首都 大学 東 京 大学 院 シ ステ ムデ ザ イ ン研 究科 システ ムデザ イ ン専攻 経 営 システ ムデ ザ イ ン学 域
Copyright◎2016,ShintaroManome.
一i一
目次
第1章 1.1 1.2 1.3
第2章 2.1 2.2 2.3 2.4
第3章
‑←∩∠り0
00り09σ
第4章 4.1 4.2 4.3
第5章 5.1 5.2
序 論
研 究 背 景...
研 究 の 目 的 と 手 法 本 論 文 の 構 成 と要 旨
関 連 研 究
コ ン テ ン ツ 指 向 ネ ッ ト ワ ー ク...
蟻 コ ロ ニ ー 最 適 化 手 法...
コ ン テ ン ツ 指 向 ネ ッ ト ワ ー ク に お け る 蟻 コ ロ ニ ー 最 適 化 手 法 の 応 用...
コ ン テ ン ツ 指 向 ネ ッ ト ワ ー ク に お け る そ の 他 の 課 題 点 と 本 研 究 で 取 り 組 む 課
題 点...,...
コ ン テ ン ツ 指 向 ネ ッ ト ワ ー ク に お け る 移 動 端 末 を 考 慮 し た 蟻 コ ロ ニ ー 最 適 化
を 用 い た 経 路 制 御 法
提 案 方 式 の 概 要...,.
提 案 す る 経 路 制 御 方 法 の 手 順...
提 案 方 式 の 動 作 例 と 特 徴 ・ 利 点...
性 能 評 価
評 価 項 目 と シ ミ ュ レ ー シ ョ ン モ デ ル
評 価 結 果...
議 論...
6● ● ● ● ■ ● ● ● ● ●
● ● ● ●o● ● ● ■o■
結 論
本 論 文 の ま と め...
今 後 の 課 題 ・展 望.
付録Aコ ンテ ンツが2つ あ りそれ らが移動 する場合 の結果
‑⊥‑⊥り白り05FOO9白‑⊥1⊥
14
だ0ρ07‑‑⊥‑占‑⊥‑⊥n∠ (∠り白民UEO(∠9右り白90 Qり∩6∩6QUつ﹂900000
一ii一 目次
付 録Bフ ェ ロ モ ン を 方 向 性 を 考 慮 せ ず 付 加 し た 場 合 の 結 果...
謝辞 参考文献
..39
48
49
一iii一
図 目次
2.1 2.2 2.3 2.4 2.5 2.6
コ ン テ ン ツIDの 例...。..
CCN(Content‑CentricNetworks)に お け る コ ン テ ン ツ 発 見 の 概 要....
CCN(Content‑CentricNetworks)の ル ー タ の 構 成...,
蟻 の 採 餌 行 動 の 例...
SoCCeRの ル ー タ 構 成...
学 習 経 路 で の 失 敗 例...
ハ07‑0◎‑←90ピ01⊥‑⊥‑⊥
‑←り白004
QσりOQOり0
端 末 移 動 の 概 略...
提 案 方 式 の コ ン セ プ ト...
提 案 方 式 の ル ー タ 構 成...
提 案 方 式 の 動 作 手 順 概 要....。...。...
7‑80ソ∩U‑←‑←‑⊥り4
01り白004﹁0123456789111111444444444444444
到 達 率 の 平 均 前 推 移...,...
ホ ッ プ 数 の 平 均 前 推 移...,...9...。...
シ ミ ュ レ ー シ ョ ン モ デ ル1...
シ ミ ュ レ ー シ ョ ン モ デ ル2...,..
case.1‑a,N=10で の 到 達 率 推 移...
case.1‑a,N=5,TTL=15で の 到 達 率 推 移..。...
case.1‑a,N=1,TTL=15で の 到 達 率 推 移...
case.1‑b,N=10で の 到 達 率 推 移...。...
case.1‑b,N=5,TTLニ15で の 到 達 率 推 移...
case.1‑b,N=1,TTL=15で の 到 達 率 推 移...,..
case.1‑a,N=10,TTL=15で の ホ ッ プ 数 推 移...
case.1‑a,N=5,TTL=15で の ホ ッ プ 数 推 移...
case.1‑a,N=1,TTL=15で の ホ ッ プ 数 推 移...
case.1‑a,N=10,TTL=25で の ホ ッ プ 数 推 移...,...
case.1‑b,N=5,TTL=15で の ホ ッ プ 数 推 移...
334466778890011222222222223333
一iv一 図 目次
4.16 4.17 4.18 4.19 4.20 4.21 4.22 4.23 4.24 4.25
case.1‑b,N=1,TTL=15で の ホ ッ プ 数 推 移...
case.1‑b,N=10,TTL=15で の ホ ッ プ 数 推 移...。...
case.1‑b,N=10,TTL=25で の ホ ッ プ 数 推 移...
case.2,N=10で の 到 達 率 推 移...
case.2,N=5,TTL,=15で の 到 達 率 推 移...
case.2,N=1,TTL=15で の 到 達 率 推 移...
case.2,N=10,TTL=15で の ホ ッ プ 数 推 移...
case.2,Nニ5,TTLニ15で の ホ ッ プ 数 推 移...
case.2,N=1,TTL=15で の ホ ッ プ 数 推 移...
case.2,Nニ10,TTL=25で の ホ ッ プ 数 推 移...
22334456673333333333
01よ9白0δ4﹁0123456789111111
シ ミ ュ レ ー シ ョ ン モ デ ル3...
シ ミ ュ レ ー シ ョ ン モ デ ル4...
case.3,N=10,TTL=15で の 到 達 率 推 移.。...
case.3,N=5,TTL=15で の 到 達 率 推 移...
case.3,N=1,TTL=15で の 到 達 率 推 移...
case.4,N=1,TTL=15で の 到 達 率 推 移...
case.1‑a,N=10で の 到 達 率 推 移...
case.1‑b,N=10で の 到 達 率 推 移...
case.1‑a,N=10,TTL=15で の ホ ッ プ 数 推 移...
case.1‑a,N=10,TTL=25で の ホ ッ プ 数 推 移...
case.1‑b,Nニ10,TTL=15で の ホ ッ プ 数 推 移...
case.1‑b,Nニ10,TTL=25で の ホ ッ プ 数 推 移...
case.2,N=10で の 到 達 率 推 移...
case.2,N=10,TTL=15で の ホ ッ プ 数 推 移...
case.2,N=10,TTL=25で の ホ ッ プ 数 推 移...
900112334455677344444444444444
1
第1章
序論
1.1研 究 背 景
イ ン タ ー ネ ッ ト上 を 流 れ る トラ ピ ッ ク は,ユ ー ザ が 音 楽 や 動 画 の 視 聴,ネ ッ トシ ョ ッ ピ ン グ,SNSな ど様 々 な コ ン テ ン ツ を 取 得 す る 際 に 発 生 す る トラ ピ ッ ク が 多 く を 占 め て い る[1].
現 在 の イ ン タ ー ネ ッ トの ア ー キ テ ク チ ャ は 設 計 され た 当 初 の 名 残 が あ り,ロ ケ ー シ ョ ン 情 報 を 含 むIPア ド レ ス に よ っ て 通 信 を 行 っ て い る.つ ま り,ど の サ ー バ/ホ ス ト と通 信 を 行 う か に 重 点 を お い た ロ ケ ー シ ョ ン指 向 の 通 信 モ デ ル で あ る.基 本 的 な ク ラ イ ア ン トサ ー バ モ デ ル に お い て はURLを 基 に コ ン テ ン ツ を 保 持 す る サ ー バ を 特 定 し,コ ン テ ン ツ を 取 得 す る.し か し, イ ン タ ー ネ ッ ト使 用 人 口 が 増 大 し た こ と な ど に よ り,サ ー バ へ の ア ク セ ス が 多 くな り負 荷 が 集 中 し て し ま う こ とや,IPア ド レス の 枯 渇 な ど とい っ た 問 題 が 発 生 し て い る.そ れ ら を 回 避 す る た め に,ネ ッ トワ ー ク の 仕 組 み はContentDeliveryNetwork(CDN)[2]やPeer‑t(>Peer
(P2P)[3]な どへ と形 態 を 変 化 させ て きた.
CDNで は,同 一 コ ン テ ン ツ を 提 供 す る 複 数 の サ ー バ を用 意 し,地 理 的 に 分 散 して 配 置 す る.
そ して,DomainNalneSystem(DNS)に よ りURLか ら近 隣 も し くは 負 荷 の 小 さ い サ ー バ な ど 適 切 な サ ー バ を 選 択 し,そ の サ ー バ へ と誘 導 す る.つ ま り,CDNに お い て は ユ ー ザ が 指 定 した サ ー バ と は 異 な る 複 製 サ ー バ に 接 続 す る 可 能 性 が あ る.P2Pに お い て は,コ ン テ ン ツ 発 見 の プ ラ ッ トフ ォ ー ム と して ア プ リケ ー シ ョ ン層 で ユ ー ザ 間 を接 続 す る オ ー バ レ イ ネ ッ トワ ー ク を構城 す る.コ ン テ ン ツ 発 見 は オ ー バ レ イ ネ ッ トワ ー ク 上 で 行 わ れ,コ ン テ ン ツ 転 送 は コ ン テ ン ツ を 持 つ 他 の ユ ー ザ か ら行 わ れ る.さ ら に,BitTorrellt[8]な ど で は,コ ン テ ン ツ単 位 の 大 き な 単 位 で は な く,コ ンテ ン ツ を 分 割 し た よ り小 さ い チ ャ ン ク と呼 ば れ る単 位 で コ ン テ ン ツ 流 通 を 行 っ て い る.つ ま り,複 数 の コ ン テ ン ツ提 供 者 か ら コ ン テ ン ツ の 一 部 ず つ を 得 る こ と で コ ン テ ン ツ 全 体 の 取 得 を 行 っ て い る.ま た,ユ ー ザ が 情 報 を 探 す 際 にURLを 自 ら指 定 す る こ と は ほ と ん ど な く,キ ー ワ ー ドに 応 じ た 通 信 相 手 を サ ー チ エ ン ジ ン が 提 示 して くれ る よ う に な って い る.
2第1章 序 論
こ の よ う に,通 信 相 手 や 場 所 に こ だ わ ら ず,複 数 の ユ ー ザ か ら も コ ンテ ン ツ を取 得 す る と い う モ デ ル は,ロ ケ ー シ ョ ン指 向 な 通 信 モ デ ル と は 大 き く異 な っ て い る.つ ま り,「 ど こ か ら」
コ ン テ ン ツ を 得 る の か,「 誰 か ら」 コ ン テ ン ツ を 得 る の か と い う こ と に 関 心 が 無 い 通 信 モ デ ル と な っ て い る.し た が っ て,コ ン テ ン ツ 流 通 サ ー ビ ス の 観 点 か ら は,ユ ー ザ が 所 望 す る コ ン テ ン ツ さ え 得 られ れ ば 十 分 で,「 ど こ か ら 」 「誰 か ら」 得 た の か は 重 要 で は な い.こ の よ うな 変 化 が あ る に も 関 わ ら ず,現 状 の ネ ッ トワ ー ク ア ー キ テ ク チ ャ はIPア ド レ ス に よ る ロ ケ ー シ ョ ン 指 向 な 通 信 モ デ ル の ま ま で あ る.し た が っ て,上 下 層 で 通 信 モ デ ル の 乖 離 が 生 じ て い る.こ の こ と か ら,前 述 の 問 題 の 他 に も 無 駄 に 遠 回 り し て コ ン テ ン ツ を 取 得 し よ う と し て し ま っ た
り,キ ャ ッ シ ュ の 有 効 活 用 が で き て い な か っ た り し て い る.こ の モ デ ル の 乖 離 を 埋 め る べ く, ネ ッ トワ ー ク 自 体 を コ ン テ ン ツ の 名 称 な ど の 情 報 を含 ん だID(コ ンテ ン ツID)を ベ ー ス に し た ア ー キ テ ク チ ャ に す る様 々 な コ ン テ ン ツ 指 向 ネ ッ トワ ー ク が 提 案 ・研 究 され て い る.な お, 新 し い 研 究 分 野 で あ る た め,コ ン テ ン ツ 指 向 ネ ッ トワ ー ク と い う名 称 自体 も 普 遍 的 に 用 い ら れ る わ け で は な く,Content‑CentricNetwork(CCN)[9]やlnformation‑CentricNetwork
(ICN)[10][11]な ど の 既 存 の ア ー キ テ ク チ ャ の 名 称 も 用 い られ る.本 論 文 で は,こ れ ら を 統 一 的 に 表 す 用 語 と して,コ ン テ ン ツ 指 向 ネ ッ トワ ー ク を 用 い る.
コ ン テ ン ツ 指 向 ネ ッ ト ワ ー ク に お い て は,コ ン テ ン ツ 要 求 ク エ リ は 宛 先IPア ド レス に 代 わ り,要 求 コ ン テ ン ツ の 名 称 な ど の 情 報 を 含 ん だ コ ン テ ン ツIDに よ っ て ル ー チ ン グ が 行 わ れ る.
し た が っ て,コ ン テ ン ツIDを エ ン ト リ と した ル ー チ ン グ テ ー ブ ル が 各 ノ ー ドで 作 成 さ れ る.
また,ラ ッ プ ト ッ プ や ス マ ー トフ ォ ン,さ ら に は タ ブ レ ッ ト,ウ ェ ア ラ ブ ル 端 末,IoTな ど の 発 達 に よ り,モ バ イ ル 端 末 は コ ン テ ン ツ を取 得 す る側 だ け で な く,コ ン テ ン ツ を 配 信 す る側 に も な っ て い る.し か し,こ れ ら の モ バ イ ル 端 末 が 保 持 す る コ ン テ ン ツ を 有 効 活 用 す る 一 方 で, コ ン テ ン ツ 配 信 端 末 が 移 動 す る 場 合 の ル ー チ ン グ テ ー ブ ル の 書 き 換 え が 間 に 合 わ ず,コ ン テ ン ツ が 取 得 で き な い と い う課 題 が 存 在 す る.
1.2研 究 の 目 的 と 手 法
モ バ イ ル 端 末 や ウ ェ ア ラ ブ ル デ バ イ ス,IoTの 発 達 に よ り,コ ン テ ン ツ 指 向 ネ ッ ト ワ ー ク に お い て も そ れ ら を 無 視 す る こ と は で き な い だ け で な く,有 効 活 用 を して い く こ と が 必 要 で あ る.し か し,こ の ネ ッ トワ ー ク は も と も と移 動 へ の 対 応 が で きて お ら ず,近 年 そ の 解 決 を 目 指 し た 研 究 が な さ れ て き た.本 論 文 で の 移 動 と は,端 末 を 保 持 して い る ユ ー ザ が 徒 歩 や 自転 車, 車 な ど で 移 動 し,そ れ に伴 い 端 末 が 接 続 す る基 地 局 や ア ク セ ス ポ イ ン トが 変 わ っ て い く こ と を 指 す.コ ン テ ン ツ 指 向 ネ ッ トワ ー ク で は,各 コ ンテ ン ツ 保 持 端 末 が 自身 の 持 つ コ ン テ ン ツ 情 報
を フ ラ ッデ ィ ン グ す る こ と に よ っ て 全 て の ノ ー ドに コ ンテ ン ツ 情 報 を送 信 し,そ の 情 報 を 基 に 各 ノ ー ドは ル ー チ ン グ テ ー ブ ル を 作 成 す る.端 末 の 移 動 が 起 こ っ た 場 合,以 前 に 作 成 さ れ た ル ー チ ン グ テ ー ブ ル の 書 き換 え が 完 了 す る ま で 誤 っ た ル ー チ ン グ が 行 わ れ て し ま い,コ ン テ ン
1.3本 論 文 の 構 成 と要 旨3
ツ を取 得 す る こ と が で き な くな っ て し ま う.
従 来 研 究 で も こ の 課 題 を 解 決 す る た め に 様 々 な 方 式 が 提 案 さ れ て きて い る が,本 研 究 で は 蟻 コ ロ ニ ー 最 適 化 手 法(Antcolonyoptiinization,ACO)[4]を コ ン テ ン ツ 指 向 ネ ッ トワ ー ク に 応 用 させ,こ の 課 題 の 解 決 を 試 み る.ACOと は,蟻 の 採 餌 行 動 に ヒ ン トを 得 た 組 合 せ 最 適 化 問 題 に 対 す る メ タ ヒ ュ ー リ ス テ ィ ッ ク 手 法 の 一 つ で あ る.こ の 方 法 は,蟻 の 採 餌 行 動 を模 した 各 工 一 ジ ェ ン トが,探 索 路 に"フ ェ ロ モ ン"を 付 加 す る こ と で 他 の 蟻 と の 間 接 的 な 情 報 交 換 を 行 い,協 調 し あ っ て 組 合 せ 問 題 の 解 を 探 索 す る と い う郡 知 能 を用 い た 手 法 で あ る.フ ェ ロ モ ン は解 を 構 成 す る 各 路 に 付 加 さ れ,各 工 一 ジ ェ ン トは フ ェ ロ モ ン情 報 を 用 い て 次 回 の 解 探 索 を行 う.こ の 方 法 は,ル ー チ ング 問 題(巡 回 セ ー ル ス マ ン問 題 ヴ ィ ー グ ル ル ー チ ン グ ネ ッ トワ ー ク ル ー チ ン グ 問 題),な ど の 組 合 せ 最 適 化 問 題 に 適 用 さ れ そ の 有 効 性 が 確 認 さ れ て い る.そ の 高 い 汎 用 性 と性 能 か らACOはMobileAdHocNetwork(MANET)環 境 に お け る ル ー チ ン グ 問 題 の 解 く手 法 の 一 つ と して も 利 用 され て お り,動 的 環 境 で も そ の 有 効 性 を 発 揮 す る こ と が で き る.先 行 研 究 に お い て も コ ン テ ン ツ 指 向 ネ ッ トワ ー ク にACOを 適 応 した 研 究 が あ る が, 固 定 さ れ た コ ン テ ン ツ の み を 対 象 と し,ACOに よ り最 適 な コ ン テ ン ツ 取 得 先 を 決 定 す る こ と を 目 的 に して い る.移 動 を 考 慮 す る場 合,ACOで は フ ェ ロ モ ン を 残 し経 路 を 決 定 す る の で, 移 動 コ ン テ ン ツ ま で フ ェ ロ モ ン を残 して も,パ ケ ッ トを 送 信 す る 際 に は そ の 場 所 か ら移 動 し て い る可 能 性 が あ る.
そ こ で,本 論 文 で は コ ン テ ン ツ指 向 型 ネ ッ トワ ー ク に お い て,移 動 す る端 末 自身 が フ ェ ロ モ ン を移 動 し た 経 路 に 付 加 し,コ ン テ ン ツ保 持 端 末 と要 求 端 末 の 間 で 移 動 後 も 経 路 の 確 立 を 可 能 に す る,動 的 な 状 況 に 対 応 可 能 なACOを 用 い る こ とで 経 路 選 択 の ミス を減 らす 経 路 制 御 法 を 提 案 す る.シ ミ ュ レ ー シ ョ ン環 境 に お い て,提 案 方 式 と,端 末 自身 が フ ェ ロ モ ン を 付 加 し な い 方 式 を 比 較 評 価 す る.そ の 結 果,比 較 方 式 は コ ンテ ン ツ が 移 動 し た 後 到 達 率 が 下 が る に も 関 わ ら ず,提 案 方 式 は 到 達 率 が ほ と ん ど下 が る こ と無 く推 移 す る.こ れ に よ り提 案 方 式 が モ バ イ ル 端 末 が あ る状 況 で の コ ン テ ン ツ指 向 ネ ッ トワ ー ク に お い て 有 効 で あ る こ と を 示 す.
1.3本 論 文 の 構 成 と 要 旨
本 論 文 は5章 に よ り構 成 さ れ る.第2章 で は,本 稿 で 焦 点 と な る コ ン テ ン ツ 指 向 型 ネ ッ ト ワ ー ク技 術 が 発 展 す る に 至 っ た 経 緯 と,こ れ まで 提 案 さ れ て き た 代 表 的 な 技 術 の 紹 介 を す る.
ま た,課 題 を 解 決 す る た め に 用 い るACOの ア ル ゴ リズ ム や 代 表 的 な ル ー チ ン グ 手 法,そ れ ら を組 み 合 わ せ た 先 行 研 究 に つ い て 言 及 す る.第3章 で は,移 動 端 末 が 存 在 し,コ ン テ ン ツ を保 持 ・取 得 を移 動 端 末 が 行 う こ と を想 定 し た コ ン テ ン ツ 指 向 型 ネ ッ トワ ー ク 環 境 に お け る, ACOに よ る 移 動 端 末 自身 が 移 動 した 経 路 に フ ェ ロ モ ン を残 す こ とで コ ン テ ン ツ の 移 動 に 対 応 し た 経 路 制 御 法 に つ い て 記 述 し,そ の 特 徴 を述 べ る.そ して,第4章 で は,提 案 方 式 を 複 数 の シ ミ ュ レ ー シ ョ ン環 境 上 で コ ン テ ン ツ 発 見 率 と コ ン テ ン ツ 発 見 に か か る ホ ッ プ数 を 時 系 列 ご と
4第1章 序 論
に 比 較 ・分 析 し,そ の 特 性 と有 効 性 を確 認 す る.最 後 に 第5章 で は,第3章 お よ び 第4章 を 踏 ま え た う え で 本 論 文 を ま と め,課 題 点 や 今 後 の 展 望 に つ い て 述 べ る.
5
第2章
関連研 究
2.1コ ン テ ン ツ 指 向 ネ ッ トワ ー ク
現 在 の ネ ッ トワ ー ク 上 を 流 れ る トラ ヒ ッ ク は 年 々 増 加 し続 け て お り,さ ら に そ の 半 分 以 上 は コ ン テ ン ツ 流 通 に か か る ト ラ ヒ ッ ク が 占 め,今 後 も そ の 割 合 は 増 加 し て い く と見 込 ま れ て い る.こ れ は 昨 今Youtubeな どの 動 画 配 信 サ ー ビ ス が 非 常 に 多 く利 用 さ れ て い る こ と,さ ら に, 今 ま で テ レ ビ や 映 画 館 な どで 流 れ て い た ビ デ オ が イ ン タ ー ネ ッ ト上 に 流 れ て く る こ と を 考 え る と,こ の 傾 向 は 想 像 に 難 く な い.こ れ に 呼 応 す る よ う に,様 々 な コ ン テ ン ツ 配 信 技 術 が 開 発 さ れ 実 用 化 さ れ て い る.前 の 章 で 述 べ た 通 り,現 在 の イ ン タ ー ネ ッ トは ホ ス トーホ ス ト間 で 通 信 す る こ と を 前 提 と して お り,ロ ケ ー シ ョ ン情 報 を 含 むIPア ド レス を用 い て 通 信 対 象 を 指 定 し て い る ロ ケ ー シ ョ ン指 向 な 通 信 モ デ ル とな っ て い る.し か し そ の 一 方 で,ユ ー ザ は そ の こ と を 全 く意 識 す る こ と な く,コ ン テ ン ツ を探 す 際 に は所 望 の コ ン テ ン ツ の 名 前 で 検 索 を行 う.さ ら に,そ の コ ン テ ン ツ を 流 通 さ せ る サ ー ビ ス はCDNやP2Pと い っ た,コ ン テ ン ツ 指 向 な 通 信 モ デ ル と な っ て い る.こ れ に よ り,ア プ リケ ー シ ョ ン層 と下 位 層 で 指 向 す る 通 信 モ デ ル が 異 な っ て い る.し た が っ て,コ ンテ ン ツ 発 見 や 転 送 に か か る オ ー バ ヘ ッ ドが 増 大 して し ま っ て い る.こ れ らの 問 題 を 根 本 的 に 解 決 す る 手 段 と して,ネ ッ トワ ー ク を仕 組 み か ら変 え て い く こ と を 目 的 と し,コ ン テ ン ツ指 向 ネ ッ トワ ー ク が 提 案 され て い る.
ネ ッ トワ ー ク 自 体 が コ ン テ ン ツ 発 見 の 手 法 を 持 つ 提 案 と し て は,TRIAD【27],i3[281,
DONA[29]な ど が あ る.こ れ らの 提 案 は コ ン テ ン ツ 転 送 に つ い て は 現 状 の イ ン タ ー ネ ッ ト と 同 様 にIPを 用 い る こ とが ベ ー ス と な っ て い る.
次 に,コ ン テ ン ツ 発 見 と転 送 の 両 方 を コ ン テ ン ツ指 向 な ア プ ロ ー チ で 取 り組 ん だ ア ー キ テ ク チ ャ と して の 代 表 的 な 技 術 で あ るContent‑CentricNet,works(CCN)に つ い て 詳 し く説 明 す る.CCNは,ユ ー ザ が 送 出 し た コ ン テ ン ツ 要 求 を 出 し,コ ン テ ン ツ保 持 側 が そ れ を 受 け 取 る と コ ン テ ン ツ を 返 送 す る とい うPull型 の ア ー キ テ ク チ ャ を 採 用 して い る.コ ン テ ン ツIDの 例 を 図2.1に 示 す.標 準 化 さ れ て い な い た め 決 ま っ た ル ー ル は な い が,階 層 化 され て い な い ネ ー
6第2章 関連 研 究
ミ ン グ に 比 べ て,階 層 化 さ れ て い る ほ う が 名 前 の 衝 突 を 防 い だ り 情 報 の 集 約 が 可 能 で あ っ た り す る た め 多 く 使 わ れ て い る.例 で は,前 半 に ど ん な コ ン テ ン ツ か を 示 す 情 報 が,後 半 に バ ー
ジ ョ ン と セ グ メ ン ト の 情 報 が 記 述 さ れ て い る.コ ン テ ン ツ 要 求 は"lnteresV'と 呼 ば れ,そ れ に 対 す る レ ス ポ ン ス は"DataChunk"と 呼 ば れ る.コ ン テ ン ツ は 一 般 的 な サ イ ズ のDataChu.nk
に 分 割 さ れ,InterestはDataChunkを 単 位 と し て 送 出 さ れ る.コ ン テ ン ツ 発 見 の 概 要 を 図 2.2に,CCNの ル ー タ の 構 成 を 図2.3に 示 す.ネ ッ ト ワ ー ク 内 の ル ー タ に は,Interestの ル ー チ ン グ 情 報 と し てFIB(ForwardingInformationBase)が 保 持 さ れ る.FIBは コ ン テ ン ツ 名 を エ ン ト リ に 持 つ ル ー チ ン グ テ ー一ブ ル で あ る.111terestを 受 け 取 っ た ル ー タ は,FIB内 の 該 当 す る エ ン ト リ に 示 さ れ た イ ン タ フ ェ ー ス 方 向 へ とInterestを 転 送 す る.In七erestが ル ー チ ン グ
プ ロ ト コ ル に よ り要 求 コ ン テ ン ツ を 保 持 す る サ ー バ へ と 転 送 さ れ る の に 対 し,DataChunkは Interestの 辿 っ た 経 路 を ホ ッ プ バ イ ホ ッ プ で 転 送 さ れ る こ と で ユ ー ザ ホ ス ト に 届 け ら れ る.具 体 的 に は,各 ル ー タ でInterestが 到 着 し た イ ン タ フ ェ ー ス をPIT(PendingInterestTable)
と 呼 ば れ る テ ー ブ ル に 保 持 す る.DataChunkは,こ のPITの エ ン ト リ を 参 照 し て ホ ッ プ バ イ ホ ッ プ で 転 送 さ れ る.DataChunk転 送 後 はPIT内 の エ ン ト リ は 削 除 さ れ る.FIBは ル ー チ ン グ プ ロ ト コ ル の 更 新 に よ る 書 き 換 え 頻 度 が 低 く 比 較 的 長 期 間 保 持 さ れ る の に 対 し て,PIT はInterest到 着 に よ る エ ン ト リ 追 加,DataChu皿k転 送 に よ る エ ン ト リ削 除 が 行 わ れ る た め 頻 繁 に 書 き 換 え が 発 生 す る.FIBの ル ー チ ン グ テ ー ブ ル は,コ ン テ ン ツ を 保 持 す る サ ー バ か ら の 広 告 を 基 に,各 ル ー タ が 自 身 の カ バ ー す る コ ン テ ン ツ 名 の プ レ フ ィ ッ ク ス を 広 告 す る こ と で 作 成 さ れ る.IPで は ク エ リ の ル ー プ を 防 止 す る た め にFIBに お い て1エ ン ト リ に 対 し て 対 応 付 け ら れ る イ ン タ フ ェ ー ス は1つ に 制 限 さ れ る が,CCNで は,コ ン テ ン ツ を ど こ か ら 取 得 し て も 良 い と い う コ ン テ ン ツ 指 向 な 考 え や,PITの エ ン ト リ の 削 除 に よ っ て 本 質 的 に ル ー プ 発 生 が 防 止 さ れ て い る こ と か ら 同 一 コ ン テ ン ツ に 対 し て 複 数 の イ ン タ フ ェ ー ス が 対 応 付 け さ れ る こ と も 許 容 し て い る.ま た,In七erestが 送 出 さ れ た 後,対 応 す るD乱taChunkが い ま だ 届 い て い な い 状 態 で ル ー タ の 他 の イ ン タ フ ェ ー ス に 同 一 コ ン テ ン ツ のInterestが 到 着 す る と,単 純 に こ のInterestの 到 着 し た イ ン タ フ ェ ー一ス をPITに 追 加 す る だ け で 良 い.こ の 時,Interestは 先
User/Appsuppliedname Versioning&Segrnentation
「一 一 一 一 一L‑一 一 一 一T‑一̲
/syutodaLcom/V量deos/campusHino.mpg仁v2<'inies'amp>仁sl
L̲一 」L̲̲̲「 一̲」L̲̲一̲一
Giobally‑routableOrganizational
namename
Conventional/automatic
図2,1.コ ン テ ン ツIDの 例
2.1コ ン テ ン ツ 指 向 ネ ッ ト ワ ー ク 7
User圃 ー＼ b.Eachnodesets
routingtab且eon basisofcontentID
∈〕一 ＼
モ ⊃
:se翻 翻 諾iesi∈ 〕
τ 一
て三〕
d.Routingbased oncontentID
e.Detect content
User
團
∈ 〕/
ノ
﹄ 倫 闘
/
、 Contentsource
∈ 〕 ∈〕̲
∈〕 ⇔
1「、:〕
1'}
亀Br。adcastingc。ntent [informationbyflooding
Contentsource
図2.2.CCN(Content‑CentricNetworks)に お け る コ ン テ ン ツ 発 見 の 概 要
に 転 送 さ れ る こ と は な く破 棄 さ れ る.こ れ に よ り,マ ル チ キ ャ ス トが 明 示 的 な 信 号 を 用 い る こ と な く 実 現 で き,コ ン テ ン ツ 転 送 の 効 率 化 が 期 待 で き る.
CCNの ル ー タ に は,FIBとPIT以 外 にContentStoreと い う コ ン テ ン ツ キ ャ ッ シ ュ を 保 持 す る 機 能 が あ る.IPで は1度 バ ッ フ ァ か ら パ ケ ッ トが 転 送 さ れ る と パ ケ ッ ト は 削 除 さ れ る の に 対 し,CCNで は 同 一 コ ン テ ン ツ へ のInterestに 対 し再 利 用 が 可 能 で あ る こ と か ら 到 着 し たDataChunkは キ ャ ッ シ ュ に 保 存 さ れ る.CCNに お け る コ ン テ ン ツ ル ー タ で の 処 理 に つ い て,Interestが ル ー タ に 到 着 す る と,(1)キ ャ ッ シ ュ に 該 当Datachunkが 収 容 さ れ て い れ ば キ ャ ッ シ ュ か らDatachunkを 転 送 す る.(2)キ ャ ッ シ ュ に な い 場 合 に は,PITの エ ン ト リ に 既 に 同 一 のDatachunkエ ン ト リ が あ れ ば,Interestを 破 棄 し こ のInterestの 到 着 イ ン タ フ ェ ー ス をPITエ ン ト リ に 加 え る.そ う す る こ と で,こ れ 以 上Interestを 転 送 す る 必 要 は な く な る.(3)PITエ ン ト リ に も な け れ ば,新 た に こ の イ ン タ フ ェ ー ス をPITに 加 え た う え で, InterestをFIBの ル ー チ ン グ 情 報 の 示 す 方 向 へ 転 送 す る.こ の よ う に コ ン テ ン ツ を ど こ か ら 取 得 し て も 良 い と い う 概 念 を,コ ン テ ン ツ 要 求 の 誘 導,1対 多 型 へ 展 開 で き る コ ン テ ン ツ 転 送,
8第2章 関連 研 究
ContentStore
name data
/syutodai.com/Videos/αmlpusHino.mpg/v2/sl ●● ●
PendingInterestTable(PIτ)
prefix Requesth19飴ce(s)
/syutodai.com八7ideos/campusHino.mpg/v2/s3 0
FonwardingInformationBase(FIB)
prefbこ 血ce五st
/syutodai,com 0.1
図2.3.CCN(Content‑CentricNetworks)の ル ー タ の 構 成
キ ャ ッ シ ュ か ら の コ ン テ ン ツ 転 送 の 実 現 とい う形 で 可 能 と した ア ー キ テ ク チ ャ と してCCNは 位 置 づ け ら れ て い る.
コ ン テ ン ツ 指 向 ネ ッ トワ ー ク で 課 題 と して 取 り上 げ られ,多 くの 研 究 が な さ れ て い る キ ャ ッ シ ュ,移 動 へ の 対 応 の 既 存 研 究 に つ い て 詳 し く説 明 し,そ の 他 の ア プ ロ ー チ に も 言 及 す る.
[キャ ッ シ ユ1
キ ャ ッ シ ュ に つ い て は,Default‑path上 の キ ャ ッ シ ュ 活 用 を 目的 と した 提 案 とDefault‑path 以 外 の キ ャ ッ シ ュ 方 向 ヘ ク エ リ を 誘 導 す る 提 案 に つ い て 紹 介 す る.
WAVE[35]で は,木 構 造 の ネ ッ トワ ー ク トポ ロ ジ に お い て ル ー タ がData(inunkを 転 送 す る度 に,下 流 方 向 ル ー タ が キ ャ ッ シ ュ し て よ いchunkの 数 を徐 々 に 増 加 す る 方 法 を と っ て い る.ル ー タ 上 を フ ル コ ン テ ン ツ(全 て のchunkが そ ろ っ た コ ン テ ン ツ全 体)が1つ 転 送 され る た び に キ ャ ッ シ ュ す るchunkを 指 数 的 に 増 加 させ る.人 気 の あ る コ ン テ ン ツ は 頻 繁 に ル ー タ
2ユ コ ン テ ン ツ 指 向 ネ ッ トワ ー ク9
を 通 過 す る こ と か ら,こ の 方 法 に よ り 人 気 の あ る コ ン テ ン ツ に つ い て は 下 流 方 向 に キ ャ ッ シ ュ し て も よ いchunkの 数 が 多 く な る.す な わ ち,ユ ー ザ に 近 い ル ー タ に よ り人 気 の 高 い コ ン テ ン ツnキ ャ ッ シ ュ が 配 置 さ れ る こ と に な る.
Breadcrumbs[36]は,ロ ケ ー シ ョ ンIDに よ る ル ー チ ン グ が 動 作 す る 環 境 を ベ ー ス に,コ ン テ ン ツ 指 向 な 誘 導 を 行 う 提 案 で あ る.ユ ー ザ か ら の コ ン テ ン ツ 要 求 は,ロ ケ ー シ ョ ンIDに よ り コ ン テ ン ツ 提 供 サ ー バ へ と 転 送 さ れ る.コ ン テ ン ツ の ダ ウ ン ロ ー ド時 に 経 由 す る 各 ル ー タ に お い て コ ン テ ン ツ の 存 在 す る 方 向 を 示 す ポ イ ン タ で あ るBreadcrumbsを 残 す.そ の 後,他 の ユ ー ザ か ら の コ ン テ ン ツ 要 求 が 該 当 す るBreadcrumbsに 遭 遇 す る と,ホ ッ プ バ イ ホ ッ プ で
こ の ポ イ ン タ を 辿 り キ ャ ッ シ ュ さ れ た コ ン テ ン ツ へ と 誘 導 さ れ る.こ の 方 式 で は,キ ャ ッ シ ュ に た ど り つ け な か っ た 場 合 に は,ロ ケ ー シ ョ ンIDに よ りサ ー バ 方 向 へ と コ ン テ ン ツ 要 求 を 転 送 す る と い う 形 でF乱ll‑backmecganism,つ ま り安 全 策 が 講 じ ら れ て い る.さ ら に こ の 方 式 で ル ー プ に 陥 っ て し ま う と い う 問 題 を 解 決 し よ う と い うBreadcruエ ェlbs+[37]が 提 案 さ れ て い る.
こ の 方 式 はBreadcrumbs誘 導 情 報 エ ン ト リ の 拡 張 と 無 効 化 制 御 の 改 良 を 行 う こ と に よ っ て 問 題 を 解 決 し,さ ら に キ ャ ッ シ ュ を ル ー タ だ け で は な く ユ ー ザ に も 持 た せ る こ と で ル ー タ に か か
る キ ャ ッ シ ュ 機 能 の 負 荷 分 散 を 目 指 し て い る.
[移動 へ の 対 応 】
コ ン テ ン ツ 指 向 ネ ッ トワ ー ク で は 自 身 が 持 っ て い る コ ン テ ン ツ を 周 囲 に広 告 す る こ と に よ っ て 経 路 表 を作 る.し か し,モ バ イ ル 端 末 が コ ン テ ン ツ を 持 つ 場 合 そ の 場 所 が 変 化 す る 可 能 性 が あ り,そ の 場 合 経 路 表 が 書 き変 わ らず コ ン テ ン ツ の 発 見 失 敗 に つ な が る.そ れ を 防 ぐ た め に は 経 路 表 の 書 き 換 え を 頻 繁 に 行 う 必 要 が あ り,全 て を書 き換 え る に は 非 常 に 時 間 が か か っ て し ま う.結 果,モ バ イ ル 端 末 が 存 在 す れ ば す る ほ ど信 頼 性 が な い ネ ッ トワ ー ク に な っ て し ま う.そ の よ うな 問 題 を解 決 し よ う と い う手 法 が 提 案 さ れ て い る[18,19].前 者 で は,モ バ イ ル 端 末 が 移 動 を す る 前 に移 動 す る意 図 を伝 え る た め のPrefixregistrationと い う メ ッセ ー ジ を 周 囲 に送 信 す る.新 し い 場 所 に移 っ た ら,も と い た 場 所 の 周 辺 の ノ ー ドに新 し い 場 所 を 知 らせ るPReg
を 送 る.周 辺 の ノ ー ドは 一 時 的 な 経 路 を つ く る た め のPRegConfirmation(PRegConf)を
送 り返 す.そ の 後 徐 々 に 最 短 経 路 を 作 る よ うに 経 路 表 を 書 き 換 え て い く と い う手 法 で あ る.後 者 は,コ ン テ ン ツ送 信 元 が リア ル タ イ ム に 配 信 して い る コ ンテ ン ツ を ユ ー ザ が 取 得 して い る途 中,送 信 元 が 移 動 し た こ と に移 動 した と き の 一 時 的 な 経 路 を 保 存 す るMobilityelltryを 持 つ こ
と で 対 応 す る 手 法 で あ る.ク エ リ転 送 の 際 はMobilityentryの 優 先 度 を 高 く し,一 部 の 経 路 情 報 の み 更 新 し て 移 動 に対 応 して い る.ま た,こ の2つ と違 っ た ア プ ロ ー チ で の 研 究[20]で は, CCNの ル ー タ の な か に"scheduler"と い う リ ン ク の 状 態 と 名 前 解 決 を 行 う た め の コ ン テ ン ツ 配 信 者 の 名 前 を 保 持 す る ノー ドを 配 置 す る.コ ン テ ン ツ 要 求 ル ー タ はschedulerを 探 す た め の Interestを 送 り,schedulerは そ れ が 届 く と 自身 のIDを 返 送 す る.こ れ に よ り,schedulerは
コ ンテ ン ツ 配 信 者 と 要 求 者 間 の 最 良 の 経 路 を 算 出 す る.移 動 が 起 こ っ た 場 合 で もschedulerに
10第2章 関 連研 究
登 録 し 直 す こ とで 経 路 が 案 内 され る.し か し,こ れ ら は ロ ケ ー シ ョ ン情 報 を 使 わ な い と い う ポ リ シ ー に 反 し て い た り,余 計 な 処 理 や 情 報 を増 や した りす る こ と に な っ て し ま う.
これ らの 他 に も,コ ン テ ン ツ が 複 数 サ ー バ に存 在 す る場 合 に は 分 割 して 取 得,1つ の サ ー バ に し か な い 場 合 で も マ ル チ パ ス に よ り取 得 す る こ と で 負 荷 分 散 を 可 能 に し た 方 式[21],IoTな
ど に よ り膨 大 な コ ン テ ン ツ が あ り,コ ン テ ン ツ の 名 前 が 分 か らず 検 索 ・取 得 で き な い 場 合 で も,各 コ ン テ ン ツ に タ グ を付 与 して お く こ とで 探 索 が 可 能 に な り,さ ら に はFIBの サ イ ズ 縮 小 す る こ と が で き る 方 式[22]な ど が あ る.
2.2蟻 コ ロ ニ ー 最 適 化 手 法
蟻 コ ロ ニ ー 最 適 化 手 法(antcolonyoptimizatioil,ACO)[4]と は,実 際 の 蟻 の 採 餌 行 動 の 際 の 経 路 生 成 過 程 に ヒ ン トを得 た 組 合 せ 最 適 化 問 題 に 対 す る メ タ ヒ ュ ー リス テ ィ ッ ク手 法 の 一 つ で あ り,Dorigoら に よ って 研 究 ・提 案 され たAntSystem[7]と 呼 ば れ る ア ル ゴ リズ ム が 原 型 で あ る.こ の 方 法 は,蟻 の 採 餌 行 動 を 模 した 各 工 一 ジ ェ ン トが,探 索 路 に"フ ェ ロ モ ン"を 付 加 す る こ とで 他 の 蟻 との 間 接 的 な 情 報 交 換 を行 い,協 調 しあ っ て 組 合 せ 問 題 の 解 を探 索 す る
と い う郡 知 能 を用 い た 手 法 で あ る.フ ェ ロ モ ン は 解 を構 成 す る各 路 に付 加 され,各 工 一 ジ ェ ン トは フ ェ ロ モ ン情 報 を 用 い て 次 回 の 解 探 索 を 行 う.蟻 は 餌 場 か ら巣 ま で を 往 復 す る 際 に 自身 が 通 っ た 経 路 に 揮 発 性 の フ ェ ロ モ ン を 付 加 す る.短 い経 路 ほ ど蟻 が よ く通 りフ ェ ロ モ ン が 更 新 さ れ,遠 い 経 路 の フ ェ ロ モ ン は徐 々 に 消 え て し ま う.こ れ を繰 り返 す こ と に よ っ て 最 短 経 路 を 学 習 す る.そ の 過 程 の 詳 細 を 図2.4と 以 下 に 示 す.蟻 は 餌 場 か ら巣 ま で 複 数 の 経 路 を持 っ て い る
と考 え られ る が,こ こ で は 簡 単 に 説 明 す る た め 長 短2つ の経 路 を 持 っ て い た と仮 定 す る.
(a)蟻 は 最 初 ど ち らが 短 い 経 路 な の か 分 か ら な い た め2つ の 経 路 に 分 か れ て 進 み,短 い 経 路 の 蟻 は 長 い 経 路 の 蟻 に比 べ て 早 く餌 場 に た ど り着 く.
(b)短 い 経 路 の 蟻 は 化 学 物 質 で あ る フ ェ ロ モ ン を付 加 しな が ら長 い 経 路 を 選 ん だ 蟻 よ り早 く巣 に戻 っ て くる た め,次 に 出 発 す る 蟻 は フ ェ ロ モ ン の つ い た 短 い経 路 を 選 ぶ.以 降 の 蟻 も 同 様 に フ ェ ロ モ ン に 誘 引 され て 経 路 を 確 率 的 に 選 択 し,自 身 も フ ェ ロ モ ン を 付 加 す る.
(c)時 間 が 経 つ に つ れ て,短 い 経 路 の 方 が 通 る蟻 が 増 え て い き フ ェ ロ モ ン が 濃 く な っ て い く.
フ ェ ロ モ ン は 蒸 発 す る性 質 が あ る た め,長 い 経 路 を 通 る 蟻 は減 って い き フ ェ ロ モ ン は 徐 々 に 薄 くな って い く.
(d)最 終 的 に 長 い 経 路 の フ ェ ロ モ ン は無 くな り,全 て が 短 い 経 路 を 通 る こ と に な る.
こ の よ う に して 最 短 経 路 が 決 定 さ れ る.
こ の ア ル ゴ リ ズ ム を 基 に,ACOの 問 題 点 で あ る 局 所 解 に 陥 る こ と を 防 い だ り解 の 収 束 性 を 高 め た りす る 手 法 が 研 究 さ れ て い る.代 表 的 な も の の2つ がMaxMinAntSystem
(MMAS)[5]とcunningAntSystem(cAS)[6]で あ る.前 者 は フ ェ ロ モ ン軌 跡 濃 度 を最 小 濃
22蟻 コ ロ ニ ー 最 適 化 手 法11
(a)
(c)
'∋畜
∋ 畜,薗 日、
(b)
(d)
図2.4.蟻 の 採 餌 行 動 の 例
度 と最 大 濃 度 の 区 間 に 限 定 し,後 者 は 経 路 生 成 に フ ェ ロ モ ン濃 度 の 利 用 に 加 え て,他 工 一 ジ ェ ン トの 部 分 解 を借 用 す る こ と に よ り,探 索 過 程 で の 多 様 性 維 持 の 効 果 が 得 られ る.
ま た,ACOは,ル ー チ ン グ 問 題(巡 例 セ ー ル ス マ ン問 題,ヴ ィ ー グ ル ル ー チ ン グ ネ ッ トワー ク ル ー チ ン グ 問 題),な ど の 組 合 せ 最 適 化 問 題 に 適 用 さ れ そ の 有 効 性 が 確 認 さ れ て い る.そ の 高 い 汎 用 性 と性 能 か らACOはMobileAdHocNetwork〔MANET)や モ バ イ ル セ ンサ ネ ッ トワ ー ク に お け る ル ー チ ン グ 問 題 の 解 く手 法 の 一一つ と し て も 利 用 さ れ て い る[13][14].例 え
12第2章 関連 研 究
ば,ACOを 基 に し た 有 名 な ル ー チ ン グ 手 法 の うち の1つ にAntNet[12]が あ る.こ れ は蟻 パ ケ ッ トが 転 送 され る と 同 時 に ネ ッ トワ ー ク の 状 態 を記 録 し,そ の 情 報 を も と に各 ノ ー ドの ル ー チ ン グ テ ー ブ ル の 情 報 を書 き換 え,安 定 した 経 路 を確 立 す る.ゴ ー ル 地 点 が 始 め に 分 か っ て い な くて も解 の 探 索 が 可 能 で あ る こ とや,自 律 分 散 的 に 処 理 を行 う こ と が 可 能 な こ とか ら,モ バ イ ル 端 末 が 多 く存 在 す る 動 的 環 境 に お い て も 適 応 可 能 で あ り,今 回 想 定 す る コ ン テ ン ツ 指 向 ネ ッ トワ ー ク で も そ の 有 効 性 を発 揮 す る こ とが 期 待 で き る.
2.3コ ン テ ン ツ 指 向 ネ ッ トワ ー ク に お け る 蟻 コ ロ ニ ー 最 適 化 手 法 の 応 用
コ ン テ ン ツ 指 向 ネ ッ トワ ー ク に お い て 蟻 コ ロ ニ ー 最 適 化 手 法 を用 い た 研 究 が 数 多 くな され て い る.蟻 コ ロ ニ ー 最 適 化 手 法 の 特 徴 は 以 下 の 通 りで あ る.
● よ り良 い 解 を 評 価 し フ ェ ロ モ ンの 重 み 付 け を す る だ け で な く,悪 い 解 に な り そ う な 候 補 で は フ ェ ロ モ ン の 揮 発 に よ り評 価 値 が 減 る 方 向 に 向 か うた め,動 的 な 環 境 に も 高 い 適 応 力 を 持 つ.
・ ル ー チ ン グ テ ー ブ ル な どの 情 報 が 不 十 分 で も,自 律 分 散 的 に局 所 的 な 情 報 の み で 動 作 す る こ と が で き る.
● リ ン ク の 状 態 や 遅 延 な ど の 情 報 を フ ェ ロ モ ン に 反 映 させ る こ と が で き る.
● マ ル チ パ ス に も 対 応 可 能 で あ る.
コ ン テ ン ツ 指 向 ネ ッ トワ ー ク は コ ン テ ン ツ の 参 加 ・離 脱 ・移 動 が あ る動 的 な 環 境 で あ り,ル ー チ ン グ テ ー ブ ル も 完 全 な 情 報 を 持 っ て い る 訳 で は な い.ま た,同 一 コ ン テ ン ツ が 複 数 存 在 し経 路 が 単 純 に 一 意 に 決 ま ら な か っ た り,マ ル チ キ ャ ス トを 標 準 機 能 と し て 搭 載 し て い た りす る.
よ っ て 蟻 コ ロ ニ ー 最 適 化 手 法 は コ ンテ ン ツ 指 向 ネ ッ トワ ー ク に お い て そ の 有 効 性 を 発 揮 で き る の で あ る.
ACOを コ ン テ ン ツ 指 向 ネ ッ ト ワ ー ク に 応 用 し た 研 究 を い く つ か 紹 介 す る."SoCCeR:
ServiceoverContent‑Cenricrouting"[33]は 同 一 コ ン テ ン ツ が 複 数 個 存 在 す る コ ン テ ン ツ 指 向 ネ ッ トワ ー ク で,コ ン テ ン ツ を ど の 送 信 元 か ら取 得 す る か 考 え な くて は な ら な い 状 況 に お い て,最 適 な 取 得 先 をACOに よ っ て 蟻 が 持 ち 帰 る 情 報 に よ っ て 決 定 す る と い っ た 手 法 を 提 案 して い る.ア ー キ テ ク チ ャ はCCNを 基 に して お り,そ こ に 新 た にPheromonetableと い う FIBに 登 録 す る コ ン テ ン ツ の 取 得 先 を 決 定 す る た め のtableを 追 加 して い る(図2.5).複 数 の 同 一 コ ン テ ン ツ にInterestantを 送 出 し 目 的 の コ ン テ ン ツ に 達 す る と,ユ ー ザ か ら 目 的 の コ ン テ ン ツ ま で に 辿 り着 く遅 延 時 間 と コ ン テ ン ツ を保 持 す る サ ー バ へ の 負 荷 の 係 り具 合 を 目的 の コ ンテ ン ツ か ら ユ ー ザ に 返 送 さ れ るDataantが 持 ち 帰 っ て く る.そ れ を も と に負 荷 が 一 番 少 な
2.3コ ン テ ン ツ 指 向 ネ ッ トワ ー ク に お け る蟻 コ ロ ニ ー 最 適 化 手 法 の 応 用13
So(℃ ￠R
PIleromolletable
ServiceM
CCN(fas重 一Path)
FIB
face Plleromone probabihty na111e face
0 P)M POM C1 0.1.3
1 ρ1M PIM・ 一....亀 . C2 2.4
3 ρ3M P3M
一 、
● ■
・ ・o層 o
M 卜1
ServiceN N
」.'970
.!1レ3
‑9
0 ρON PON
7一甲 .膠,ρ.
"C3
0.↓5
3 ρ3N
9ρ膠,■, o .,「 匿 「.
P3N
(PLxl>Po.N!>P3M)and(P3N>PON)
図2.5.SoCCeRの ル ー タ 構 城
い 取 得 先 をFIBに 登 録 す る.こ れ に よ り,余 裕 が あ る取 得 先 か ら コ ン テ ン ツ を 取 得 す る こ と が で き,ラ ン ダ ム に 取 得 して き た 場 合 に 比 べ て 全 体 の 負 荷 が 下 が っ た.こ の 方 式 は 特 に サ ー ビ ス 指 向 ネ ッ トワ ー ク に 着 目 し た 研 究 で あ っ た.さ ら に こ れ を 拡 張 し た 方 式 も 提 案 さ れ て い る[17].Pheromonetableに 記 録 さ れ る蟻 の フ ェ ロ モ ン情 報 以 外 にGAresultsetと い う遺 伝 的 ア ル ゴ リズ ム を用 い た 情 報 を 加 え,解 の 収 束 を 速 め 遅 延 も 減 らす こ と を 可 能 に して い る.
GreedyAntColonyForwarding(GACF)[15]で は,ま ずISPの ドメ イ ン ご と に ネ ッ トワ ー ク を 分 割 し,コ ン テ ン ツ の 名 前 を効 率 よ く統 括 す る こ と に よ りル ー チ ン グ テ ー ブ ル の サ イ ズ を 大 幅 に 削 減 可 能 と して い る.ま た,機i能 を 分 け た2種 類 の 蟻 パ ケ ッ トを 用 意 す る.一 方(Hello Ant)が 全 て の 利 用 可 能 な 経 路 を探 索,そ の 内 で 最 適 な 経 路 を 決 定 し,も う一 方(NormalAnt) が デ ー タ を 取 得,そ れ と 同 時 に 最 適 化 を強 化 す る.こ の 方 式 も 上 記 と同 様FIBに コ ン テ ン ツ
ご と に 各 イ ン タ フ ェ ー ス の オ ー バ ヘ ッ ドや 最 小 帯 域 幅,RTT,ホ ッ プ数 な ど の 情 報 に 基 づ い た フ ェ ロ モ ン の 情 報 を 付 加 し て い る.こ の ア ル ゴ リ ズ ム を 拡 張 さ せ た 方 式[16】 で は,ISP内 と ISP問 で パ ケ ッ トの 転 送 方 法 を 変 え,CCNの ス ケ ー ラ ビ リテ ィ を 広 げ る こ と を 可 能 と して い る.し か し,こ れ ら は コ ンテ ン ツ が モ バ イ ル 端 末 に よ り保 持 さ れ,離 脱 ・参 加 を す る 場 合 を想 定 して い な い,ま た は 対 応 し き れ て い な い とい う問 題 点 が あ る.
14第2章 関 連研 究
2、4コ ンテ ン ツ指 向 ネ ッ トワー ク にお け るそ の他 の 課 題 点 と本 研 究 で 取 り組 む 課 題 点
コ ン テ ン ツ 指 向 ネ ッ トワ ー ク で は,2.1で 説 明 した こ と の 他 に も 改 良 さ れ る べ き,改 良 ・研 究 さ れ て い る課 題 点 が 数 多 くあ る.例 え ば,ル ー チ ン グ そ の も の を よ り様 々 な 状 況 に 対 応 で き る よ う に で き な い か,ル ー タ に 機 能 を追 加 す る こ と で よ り効 率 が 上 が ら な い か,コ ン テ ン ツ が モ バ イ ル 端 末 に よ り保 持 さ れ,離 脱 ・参 加 を す る 場 合 を 想 定 して い な い 点,実 装 ・運 用 に い た る まで の コ ス トや 実 現 性 は ど う な の か,な ど で あ る.こ の よ うな 多 くの 課 題 が あ る た めCCN はCDNやISPス ケ ー ル で は 適 応 が 可 能 で も ワ ー ル ドワ イ ドで は 不 可 能 で あ る との 報 告 も さ れ て い る[23].
蟻 コ ロ ニ ー 最 適 化 手 法 で は,最 短 経 路 を 見 つ け ら れ ず 局 所 解 に 陥 っ て し ま う場 合 が あ る,制 御 パ ケ ッ トが 多 く出 て し ま う,と い っ た 課 題 点 が あ る.そ れ を 回 避 し よ う と した 研 究 が 数 多 く
な さ れ て い る が 方 式 が 複 雑 に な っ て し ま っ た り,汎 用 性 が 無 く な っ て し ま っ た り して い る.
本 研 究 で 着 目 す る の は,コ ン テ ン ツ指 向 ネ ッ トワ ー ク に お い て,コ ン テ ン ツ が 移 動 端 末 に よ り保 持 さ れ,コ ン テ ン ツ 取 得 側 も 移 動 端 末 で あ り,そ れ ら の 参 加 ・離 脱 ・移 動 が あ る場 合 で あ る.昨 今,移 動 端 末 の 発 達 に よ り,ノ ー トパ ソ コ ン,ト ッ プ ス マ ー トフ ォ ン,タ ブ レ ッ ト端 末 な ど が 主 流 と な っ て き て い る.特 に ス マ ー ト フ ォ ン は,ほ ぼ1人 に つ き1台 持 っ て お り,ス マ ー ト フ ォ ン で 情 報 収 集,コ ミ ュ ニ ケ ー シ ョン,動 画 や 音 楽 な ど の コ ン テ ン ツ の 取 得 を行 っ て い る.ま た,ウ ェ ア ラ ブ ル デ バ イ ス やIoTの 潮 流 に よ り,1人 あ た りの 端 末 保 有 数 は 急 激 に 増 加 し て い く と考 え られ て い る.よ っ て,コ ンテ ン ツ 指 向 ネ ッ ト ワ ー ク に お い て も,移 動 端 末 へ の 対 応 は 必 要 不 可 欠 で あ る .図2.6に 示 す よ う に,ユ ー ザ と コ ン テ ン ツ 間 の 経 路 を確 立 で き て い た と して も,ユ ー ザ ま た は コ ン テ ン ツ が移 動 して し ま う と今 まで の 経 路 で は コ ン テ ン ツ 取 得 が 失 敗 と な っ て し ま う.こ の よ う な 問 題 に 対 処 す る べ く,本 論 文 で は コ ン テ ン ツ 指 向 ネ ッ トワ ー ク に お け る移 動 端 末 を 考 慮 し た 蟻 コ ロ ニ ー 最 適 化 を 用 い た 経 路 制 御 法 の 提 案 を 行 っ て い る.
2.4コ ン テ ン ツ 指 向 ネ ッ トワ ー ク に お け る そ の 他 の 課 題 点 と 本 研 究 で 取 り組 む 課 題 点 15
User User
ContentMovementofconte
(a)]Learnrouteto
COntentSOUrCe.
(b)̀̀lnterest,,issentalong
learnedroute,butcannotdiscover contentbecauseofmovement.
図2。6.学 習 経 路 で の 失 敗 例
