2000 Gnutella FIRST-LEVEL NEIGHBORS SECOND-LEVEL NEIGHBORS REQUESTING PEER TRANSFER□
6 2000 Gnutella
2001 DHTS DHTs展现了良好的结构性, greeding routing Chord[stoi 2001] CaN[RATN 2001 Pastry[RoWs 2001] Tapestry [zhAo 2001
7 2001 DHTs ◼ DHTs展现了良好的结构性,greeding routing ◼ Chord[STOI 2001] ◼ CAN[RATN 2001] ◼ Pastry[ROWS 2001] ◼ Tapestry [ZHAO 2001]
Chord h.earce h(key) Succ Table Items I ikey E(n, successor(n)/ return successor(n) id+2 succ 011 2 for i=m down to 1 2|40 3 iffingerlG]E(n, key) then finger/i /. search(key) 0 Succ. Table Items d+2 succ query(7) 266 Succ. Table 6 2 id+2 succ 070 00 Succ. Table 2|22 i id+succ 03 666
8 n.search(key) 1 if key (n,successor(n)] return successor(n) 2 for i=m down to 1 3 if finger[i] (n,key) then finger[i].search(key) Chord 0 1 2 3 4 5 6 7 i id+2i succ 0 2 2 1 3 6 2 5 6 Succ. Table i id+2i succ 0 3 6 1 4 6 2 6 6 Succ. Table i id+2i succ 0 1 1 1 2 2 2 4 0 Succ. Table 7 Items 1 Items i id+2i succ 0 7 0 1 0 0 2 2 2 Succ. Table query(7)
CAN nl query f4 7 6 f4 0 01234567
9 ◼ n1 query f4 CAN 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 0 n1 n2 n3 n4 n5 f1 f2 f3 f4
DHT技术在P2P系统中的作用 提供分散且收敛特性 提供动态加入与离开时的容错特性 因而,基于DHT技术的P2P系统能够高的可扩展性、自组织性及 确定性等优良特性,非常适合广域分布计算,受到高度重视。 哈希表 分布式哈希表。 hash( data) Key=hash(data) Put(key, value )+ Lookup(key)->node IP. Get(key)->value Route(node iP,put, key, value ) Route(node_IP, get, key)->value
10 DHT技术在P2P系统中的作用 ◼ 提供分散且收敛特性 ◼ 提供动态加入与离开时的容错特性 ◼ 因而，基于DHT技术的P2P系统能够高的可扩展性、自组织性及 确定性等优良特性，非常适合广域分布计算，受到高度重视