基于分布式哈希表的对等系统 关键技术研究 博士生:邹福泰 指导教师:马范援 答辩日期:2005年1月25日
1 基于分布式哈希表的对等系统 关键技术研究 博士生：邹福泰 指导教师：马范援 答辩日期：2005年1月25日
大纲 研究背景 路由问题及解决方案 拓扑问题及解决方案 查询问题及解决方案 进一步的研究方向
2 大纲 ◼ 研究背景 ◼ 路由问题及解决方案 ◼ 拓扑问题及解决方案 ◼ 查询问题及解决方案 ◼ 进一步的研究方向
研究背景 对等( peer-to-peer,简称P2P)系统在如下领域已得到广 泛应 (1)文件共享 eDonkey、 BitTorrent(超级下载速度) (2)即时通讯 Jabber(更强能力) (3)信息搜索 Peer search(实时搜索) (4)内容分发Cora(网页按需就近获得) (5)协同工作 groove( isual office) (6)广域存储 Ocean store(无尽存储) (7)网络计算SETI@Home(超级计算力) (8)组通信 Scribe(应用级组播) 新兴应用领域仍不断增长中
3 研究背景 ◼ 对等(peer-to-peer，简称P2P)系统在如下领域已得到广 泛应用： (1)文件共享 eDonkey、 BitTorrent(超级下载速度) (2)即时通讯 Jabber(更强能力) (3)信息搜索 PeerSearch(实时搜索) (4)内容分发 Coral(网页按需就近获得) (5)协同工作 Groove(visual office) (6)广域存储 OceanStore(无尽存储) (7)网络计算 SETI@Home(超级计算力) (8)组通信 Scribe(应用级组播) 新兴应用领域仍不断增长中
P2P系统构造及发展 ■P2P系统将分布于 Internet的众多计算机构造 个自组织的利益群体,其中每个计算机的功能 都是对等的。 ■构造过程是一个由简单到复杂的发展史 n1999 Napster(集中式, central index server) 2000 gnutella(分散不收敛, flooding) 2001 Chord/ CAN/ Pastry/ Tapestry(分散且收 敛DHT)
4 P2P系统构造及发展 ◼ P2P系统将分布于Internet的众多计算机构造一 个自组织的利益群体，其中每个计算机的功能 都是对等的。 ◼ 构造过程是一个由简单到复杂的发展史 ◼ 1999 Napster(集中式,central index server) ◼ 2000 Gnutella(分散不收敛,flooding) ◼ 2001 Chord/CAN/Pastry/Tapestry(分散且收 敛,DHT)
1999 Napster A EP2 CENTRAL B INDEX PEERS IP3 CENTRAL PlG SERVER RESOURCES ↓5
5 1999 Napster
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系统能够高的可扩展性、自组织性及 确定性等优良特性，非常适合广域分布计算，受到高度重视