1-hopで全てのノードを検索可能な"OneHop"

Full-Information Lookups for Peer-to-Peer Overlaysという論文を読んだのでまとめ．

Abstract

多くのP2Pにおいて，ピアはルックアップのための情報を少ししか持たない．
これはノード同士の情報交換を少なくするためである．
しかし，それが原因となってマルチホップでしかルックアップできなくしている．

そこで，全てのピアへのルーティング情報を持ち，one-hopでルックアップ可能なシステムを提案する．
メンバシップの情報を保持するために，ピアの変化の情報をどのように広めるかを説明する．
ノードの頻繁な離脱時に，このシステムにどれくらい帯域が必要かも説明する．
99%が正しいノードに到達することが分かった？？

疑問と回答

1. スケーラビリティは？

おそらく10万〜100万程度のノード数を想定．

2. 帯域圧迫はどうなんだろう？

階層構造で必要最小限のピアに通知していくもよう．

少数のスーパーピア
↓
ほかのスーパーピア
↓
その他のピア

また，パラメータの調節により，適切な帯域消費を実現するとのこと．

範囲検索が可能なSkip Graph

P2Pの検索技術ならRFC4981で宣言したように、Skip Graphについての論文を適当に読んだのでまとめ。

既存のDHTの問題点

Chord・Pastry・CANといったDHTは、keyをハッシュしてスケーラビリティと負荷分散を実現
　↓
ハッシュのせいでkeyの順序が崩れ、範囲検索が困難

Skip Graphなら範囲検索が可能

Keyをハッシュしないため、範囲検索が可能になるとのこと。

論文内の図などは、大阪大学工学部電子情報エネルギー工学科の小西さんが書かれたスライドを見るとよいと思う。

keyの探索アルゴリズムは以下のように行われる。

Algorithm 1: search for node n

upon receiving (searchOp, startNode,level):
if n.key = searchKey then
  send (search0p, n) to startNode

if n.key < searchKey then
  while level > 0 do
    if (nRlevel ).key < searehKey then
      send (search0p, startNode,level) to nRlevel
      break
    else level <- level-1

else
  while level > 0 do
    if (nLlevel).key > searchKey then
      send (search0p, startNode,level) to nLlevel
      break
    else level <- level-1

if level < 0 then
  send (search0p, n) to startNode

このアルゴリズムではkeyに一致したときと探索に失敗したときにstartNodeへsendするが、
範囲検索の場合はkeyが範囲内に一致したときにstartNodeへsendするようにアルゴリズムを変更すれば範囲検索ができる(?)

出典

"Skip Graphs" James Aspnes, Gauri ShahSODA, Jan. 2003, pp.384-393

P2Pの検索技術ならRFC4981

P2Pの検索について学ぶなら, まずはRFC4981.
ということで, RFC4981を読んでいこうと思う.

Abstract

The pace of research on peer-to-peer (P2P) networking in the last five years warrants a critical survey. P2P has the makings of a disruptive technology -- it can aggregate enormous storage and processing resources while minimizing entry and scaling costs.

Failures are common amongst massive numbers of distributed peers, though the impact of individual failures may be less than in conventional architectures. Thus, the key to realizing P2P's potential in applications other than casual file sharing is robustness.

P2P search methods are first couched within an overall P2P taxonomy. P2P indexes for simple key lookup are assessed, including those based on Plaxton trees, rings, tori, butterflies, de Bruijn graphs, and skip graphs. Similarly, P2P indexes for keyword lookup, information retrieval and data management are explored. Finally, early efforts to optimize range, multi-attribute, join, and aggregation queries over P2P indexes are reviewed. Insofar as they are available in the primary literature, robustness mechanisms and metrics are highlighted throughout. However, the low-level mechanisms that most affect robustness are not well isolated in the literature. Recommendations are given for future research.

skip graphって言葉よく聞くけど、ちゃんと調べたことがない。
"Skip Graphs" James Aspnes, Gauri ShahSODA, Jan. 2003, pp.384-393
明日少しだけ読んでみようと思う。