非構造化オーバーレイネットワーク構築におけるメトロポリス法を用いたアルゴリズムの評価

高村, 達史; 土屋, 達弘; 菊野, 亨

電子情報通信学会技術研究報告. DC, ディペンダブルコンピューティング, 2009, 109(12), 13-17

Number of Access:347（2025-06-06 06:12 Counts）

Identifier to cite or link to this item: https://hdl.handle.net/11094/27241

Link to primary information 

File Format Terms of use Size Views Date.Available Description information
itr109_12_13 pdf None 610 KB 75 2014.04.03  

Item Information

Output File Export EndNote Basic Export Mendeley

Title
非構造化オーバーレイネットワーク構築におけるメトロポリス法を用いたアルゴリズムの評価
Evaluation of a Metropolis Algorithm for Constructing Unstructured Overlay Networks
ヒコウゾウカ　オーバーレイ　ネットワーク　コウチク　ニ　オケル　メトロポリスホウ　ヲ　モチイタ　アルゴリズム　ノ　ヒョウカ
Creator
CreatorName
高村, 達史 ; タカムラ, タツシ ; Takamura, Tatsushi
NRID
1000030283740 1000030283740
ORCID
0000-0002-3329-9235 0000-0002-3329-9235
researchmap permalink
tatsuhirotsuchiya72 tatsuhirotsuchiya72
Scopus Author ID
7403030658 7403030658
CreatorName
土屋, 達弘 ; ツチヤ, タツヒロ ; Tsuchiya, Tatsuhiro
NRID
1000050093745 1000050093745
CreatorName
菊野, 亨 ; キクノ, トオル ; Kikuno, Tohru
Subject
非構造化オーバーレイネットワーク
peer-to-peer
耐故障性
メトロポリス法
Unstructured overlay network
fault tolerance
metropolis algorithm
Abstract
P2Pシステムの通信はオーバーレイネットワークと呼ばれる仮想的なネットワーク上で行われる.オーバーレイネットワーク上で通信コストと故障耐性を最適化する手法の一つに,モンテカルロシミュレーションで用いられるメトロポリス法を適用するアルゴリズムがある.これらのアルゴリズムは,乱数に基づき局所的な接続関係を変化させることを繰り返すことによってネットワークを最適化する.メトロポリス法の最大の利点は局所解に収束することを防ぐことにあるが,そうすることが実際に有効であるかは定量的に議論されていなかった.本研究ではメトロポリス法であるLocaliserを対象に,メトロポリス法を用いることがオーバーレイネットワークのパフォーマンスと故障耐性の実現に有効であるかどうかについて検討する.
Peer-to-peer (P2P) systems use a virtual network called an overlay network to route messages to distinations. Some algorithms adopt the Metropolis scheme, which is a common Monte Carlo method, to optimize the communication cost and fault tolerance of an overlay network. These algorithms iteratively perform local topological changes in a randomized fashion, eventually resulting in an optimized network. The intended advantage of using the Metropolis scheme is the avoidance of getting trapped in local optima; however there has been no convincing evidence for it. In this paper we consider Localiser, which is one of these Metropolis scheme-based algorithms, and study the effects of using the Metropolis scheme on the performance and resiliency of an overlay.
Publisher
電子情報通信学会
The Institute of Electronics, Information and Communication Engineers
デンシ　ジョウホウ　ツウシン　ガッカイ
Source Title
電子情報通信学会技術研究報告. DC, ディペンダブルコンピューティング
Volume (Issue)
109(12)
Page
13-17
Date of Issued
2009-04-14
Language
Japanese
Handle URL
https://hdl.handle.net/11094/27241
PISSN
09135685
NCID
AA11645397
Access Rights
open access
CopyRight
Copyright © 2011 by IEICE
本文データはCiNiiから複製したものである
oaire:version
Version of Record
Category
学術雑誌論文 Journal Article