講演抄録/キーワード |
講演名 |
2017-03-04 13:25
Ballistic Skip Graph: Skip Graph型定数次数構造化オーバレイ ○青木優介・大西真晶・首藤一幸(東工大) SITE2016-82 IA2016-112 |
抄録 |
(和) |
ノード群による自律分散的なネットワーク構築や,データの保存、検索を実現する構造化オーバレイ技術の一つに,Skip Graphがある.Skip Graphに参加するノードは複数本のショートカットリンクを持ち,次数は全ノード数$N$に対して$O(log{} N)$となる.本研究では,Skip Graphの特長を残しつつ,ノードの次数が$O(log{} N)$ではなく$O(1)$となる新たな構造化オーバレイBallistic Skip Graphを提案する.提案手法は各ノードの持つショートカットリンクのレベルをランダムに1つに限定することで定数次数を実現しており,ノード群のグループ化や全ノード数の推定などが不要なため,参加ノード数の増加,減少に伴うネットワークの広範囲に及ぶ再構築が不要という特長を備えている.評価実験により平均経路表サイズが小さな定数に抑えられていることを確認した. |
(英) |
Structured overlays enable a number of nodes to construct an application-level network autonomously and to search data. Skip Graph, one of structured overlays, supports range queries. Each node in Skip Graph has multilevel shortcut links. The degree of each node is $O(log{} N)$ on a network with the $N$ nodes. In this paper, we propose Ballistic Skip Graph, a structured overlay that reduces the degree of each node to $O(1)$ by limiting the number of shortcut links to a single level at random while supporting range queries. The proposed method does not require extensive reconfiguration of the network when nodes join or leave because it does not group nodes. The evaluation experiment confirmed that the average routing table size is suppressed to a small constant. |
キーワード |
(和) |
Peer-to-Peer / 構造化オーバレイ / Skip Graph / 定数次数オーバレイ / / / / |
(英) |
Peer-to-Peer / structured overlay / Skip Graph / constant-degree overlay / / / / |
文献情報 |
信学技報, vol. 116, no. 491, IA2016-112, pp. 197-202, 2017年3月. |
資料番号 |
IA2016-112 |
発行日 |
2017-02-24 (SITE, IA) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
SITE2016-82 IA2016-112 |