DetouringSkipGraph:迂回経路を活用する構造化オーバレイ

• Item type: SIG Technical Reports(1)
• 公開日: 2019-02-28
• タイトル: DetouringSkipGraph:迂回経路を活用する構造化オーバレイ
• タイトル / 言語: en
• タイトル: Detouring Skip Graph: A Structured Overlay Utilizing Detour Routes
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: グラフ/学習
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学
• 著者所属: 東京工業大学
• 著者所属: 東京工業大学
• 著者所属: 東京工業大学
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者名: 金子, 孟司; 坂野, 遼平; 青木, 優介; 首藤, 一幸
• 著者名(英): Takeshi, Kaneko; Ryohei, Banno; Yusuke, Aoki; Kazuyuki, Shudo
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ノード群による自律分散的なネットワークを構築し，効率的なルーティングを実現する構造化オーバレイ技術の一つに Skip Graph がある．Skip Graph は，各ノードに割り当てられる membership vector に基づいてネットワークトポロジを形成することで，ノード数 n に対してO (logn) の経路長を達成する．しかし，各ノードは大域的な情報をもたないため，大抵の場合は最短経路ではない．そこで我々は，迂回経路を活用することで経路長を短縮する Detouring Skip Graph を提案する．提案手法は追加リンクの構築等を必要としないため，Skip Graph の特長を維持した上での経路長の短縮に成功している．評価実験により，平均経路長がSkip Graph よりも 20% から 30% 程度短縮したことを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Skip Graph, one of the structured overlays, constructs its own structure based on membership vectors assigned to every node, and consequently it provides routing path lengths of O (logn) where n is the total number of nodes. However, there is a problem that most of routing paths are not the shortest paths because each node knows only its local information, rather than the global topology. We proposed Detouring Skip Graph, which shortens the path lengths by means of utilizing detour routes. It does not require construction of extra links and modification of its topology ; thereby, we succeeded in shortening them while maintaining the advantages of Skip Graph. Our evaluation experiments confirmed that the average path length was shortened by approximately 20% to 30% compared to Skip Graph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12326962
• 書誌情報: 研究報告インターネットと運用技術（IOT）; 巻 2019-IOT-44, 号 50, p. 1-8, 発行日 2019-02-28
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8787
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会