講演抄録/キーワード |
講演名 |
2014-03-06 11:40
構造化オーバレイにおけるクエリの流量のみに基づく経路表構築手法 ○安藤泰弘・長尾洋也・宮尾武裕・首藤一幸(東工大) NS2013-207 |
抄録 |
(和) |
構造化オーバレイでは,各ノードが自身が持つ経路表を参照し,クエリを担当ノードまで転送する.
ノードにはノードIDという数値や数値の組が割り振られ,各ノードは,ノードID間の距離やノード間に存在するノード数に基づいて経路表に載せるノードを選ぶ.それによって,効率的な担当ノード探索,すなわち少ないホップ数でのクエリの担当ノードへの到達を達成する.従来,効率的な担当ノード探索には,ノードID間の距離やノード間に存在するノード数を指標として用いることが必要だと考えられてきた.しかし実はそれらを指標として用いずとも効率的な探索が可能であることを我々は発見した.その例として,クエリ流量に基づく経路表構築手法Flow-based Flexible Routing Tables (FFRT) を示す.FFRTでは,各ノードは,経路表に載っている各ノードについてクエリ流量,つまり転送したクエリの数を求め,経路表に載っている各ノードのクエリ流量を均一にすることを目指して経路表を構築する.本手法には,ノードIDの分布やアクセス先IDの分布に偏りがあっても既存手法と同等以上の効率を達成するという応用上の利点がある. |
(英) |
In structured overlays, nodes transfer a query hop by hop to the node that is responsible to the query's target ID by referring their routing tables.Each node is assigned node ID and selects nodes to be on its routing table on the basis of ID distance or the number of nodes between a pair of nodes.Those criteria, ID distance or the number of nodes between a pair of nodes enables efficient lookup, that is a small number of hop counts to the responsible node.So far those criteria were considered to be necessary to efficient lookup.We found that efficient lookup does not require those criteria.As an example, this paper shows Flow-based Flexible Routing Tables (FFRT), a routing table construction method solely based on a flow of queries.
In FFRT, a node calculates the flow of queries, that is the amount of queries transferred to each node on its routing table, and maintains its routing table to aim at uniform flow of queries for nodes on its routing table.FFRT provides such practical merit as it performs efficient lookups though node IDs and query's target IDs are distributed ununiformly. |
キーワード |
(和) |
peer-to-peer / オーバレイネットワーク / 分散ハッシュテーブル / / / / / |
(英) |
peer-to-peer / overlay network / distributed hash table / / / / / |
文献情報 |
信学技報, vol. 113, no. 472, NS2013-207, pp. 179-184, 2014年3月. |
資料番号 |
NS2013-207 |
発行日 |
2014-02-27 (NS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
NS2013-207 |