电子科技大学：《网络计算模式 Network Computing Paradigm》课程教学资源（课件讲稿）07 P2P网络（二）Distributed Hash Table

Distributed Hash Table Introduction >DHT原理 >代表性DHT算法 >基于DHT的结构化P2P比较 >基于DHT的P2P应用 1

1  Introduction  DHT原理  代表性DHT算法  基于DHT的结构化P2P比较  基于DHT的P2P应用 Distributed Hash Table

1 Introduction ■Chord 基于分布式Hash表 ■Pastry (DHT:Distributed Hash Table ■CAN 结构化P2P: 直接根据查询内容的关键字定位其索引的存放节点 2

2 1 Introduction  Chord  Pastry  CAN 基于分布式Hash表 (DHT： Distributed Hash Table ) 结构化P2P: 直接根据查询内容的关键字定位其索引的存放节点

2.1Hash函数概述 Hash函数可以根据给定的一段任意长的消息计算出一个 固定长度的比特串，通常称为消息摘要(MD:Message Digest)，一般用于消息的完整性检验。 ■ Hash函数有以下特性： ■ 给定P,易于计算出MD(P) ■只给出MD(P),几乎无法找出P ■无法找到两条具有同样消息摘要的不同消息 ■ Hash函数 ■MD5:消息摘要长度固定为128比特 ■SHA-1:消息摘要长度固定为160比特 3

3 2.1 Hash函数概述  Hash函数可以根据给定的一段任意长的消息计算出一个 固定长度的比特串，通常称为消息摘要（MD：Message Digest），一般用于消息的完整性检验。  Hash函数有以下特性：  给定 P，易于计算出 MD（P）  只给出 MD（P），几乎无法找出 P  无法找到两条具有同样消息摘要的不同消息  Hash函数  MD5：消息摘要长度固定为128比特  SHA-1：消息摘要长度固定为160比特

2.2Hash函数应用于P2P的特性 ■惟一性：不同的输入明文，对应着不同的 输出摘要 ■将节点P地址的摘要作为节点D,保证 了节点D在P2P环境下的惟一性 SHA-1(“202.38.64.1) =24b92cb1d2b81a47472a93d06af3d85a42e463ea SHA-1(“202.38.64.2”) =eld9b25dee874b0c51db4c4ba7c9ae2b766fbf27 4

4 2.2 Hash函数应用于P2P的特性  惟一性：不同的输入明文，对应着不同的 输出摘要  将节点IP地址的摘要作为节点ID，保证 了节点ID在P2P环境下的惟一性 SHA-1(“202.38.64.1”) =24b92cb1d2b81a47472a93d06af3d85a42e463ea SHA-1(“202.38.64.2”) =e1d9b25dee874b0c51db4c4ba7c9ae2b766fbf27

2.3DHT算法 将内容索引抽象为对 ■K是内容关键字的Hash摘要：K=Hash(key) ■V是存放内容的实际位置，例如节点P地址等 ■ 所有的对组成一张大的Hash表，该表存储了所有 内容的信息 ■每个节点都随机生成一个标识(D),把Hash表分割成许 多小块，按特定规则（即K和节点D之间的映射关系） 分布到网络中去，节点按这个规则在应用层上形成一个 结构化的重叠网络 给定查询内容的K值，可以根据K和节点D之间的映射关 系在重叠（Overlay)网络上找到相应的V值，从而获得 存储文件的节点P地址 5

5 2.3 DHT算法  将内容索引抽象为对  K是内容关键字的Hash摘要：K = Hash(key)  V是存放内容的实际位置，例如节点IP地址等  所有的对组成一张大的Hash表，该表存储了所有 内容的信息  每个节点都随机生成一个标识(ID)，把Hash表分割成许 多小块，按特定规则（即K和节点ID之间的映射关系） 分布到网络中去，节点按这个规则在应用层上形成一个 结构化的重叠网络  给定查询内容的K值，可以根据K和节点ID之间的映射关 系在重叠（Overlay）网络上找到相应的V值，从而获得 存储文件的节点IP地址

2.3DHT算法 kv 内容索引 提取 K=Hash(key） 内容 内容关键字key 内容存储位置等信息 value 内容索引 Hash表 电影、夜宴 电影 K=hash(电影，夜宴) 夜宴 V=http://video.com.cn/ http://video.com.cn/ yeyan.avi yeyan.avi 6

6 2.3 DHT算法 内容 内容关键字key 内容存储位置等信息 value 内容索引 提取 K=Hash(key) k v Hash表 电影 夜宴 电影、夜宴 http://video.com.cn/ yeyan.avi 内容索引 K=hash(电影, 夜宴) V = http://video.com.cn/ yeyan.avi

2.3DHT算法 规则？ N32 Chord、CAN、 Tapestry、Pastry N8 N48 N16 a.Hash表 b.分布式Hash表 在许多情况下，节点ID为节点IP地址的Hash摘要

7 2.3 DHT算法 k v a. Hash表 b. 分布式Hash表 规则? K V N1 N48 N16 N32 N8 K V K V K V K V Chord、CAN、 Tapestry、Pastry 在许多情况下，节点ID为节点IP地址的Hash摘要

2.3DHT算法 索引发布和内容定位 (K1.V1) K V K=Hash(xyz.mp3) V1=128.1.2.3 插入 .Vi) 查询(K K V A K V 128.1.2.3 xyz.mp3 田 B 8

8 2.3 DHT算法 插入 (K1 ,V1 ) K V K V K V K V K V K V K V K V K V K V K V (K1 ,V1 ) 查询(K1 ) A 128.1.2.3 B K1=Hash(xyz.mp3) V1=128.1.2.3 C  索引发布和内容定位

2.3DHT算法 ■ 定位(Locating) ■节点D和其存放的对中的K存在着映 射关系，因此可以由K获得存放该对 的节点D ■路由(Routing) ■在覆盖网上根据节点D进行路由，将查询消 息最终发送到目的节点。每个节点需要到其 邻近节点的路由信息，包括节点D、P等 9

9 2.3 DHT算法  定位(Locating)  节点ID和其存放的对中的K存在着映 射关系，因此可以由K获得存放该对 的节点ID  路由(Routing)  在覆盖网上根据节点ID进行路由，将查询消 息最终发送到目的节点。每个节点需要到其 邻近节点的路由信息，包括节点ID、IP等

2.3DHT算法 网络拓扑 ■拓扑结构由节点D和其存放的对中的 K之间的映射关系决定 ■拓扑动态变化，需要处理节点加入/退出/失效 的情况 在重叠网上节点始终由节点ID标识，并且根据ID进行路由 10

10 2.3 DHT算法  网络拓扑  拓扑结构由节点ID和其存放的对中的 K之间的映射关系决定  拓扑动态变化，需要处理节点加入/退出/失效 的情况 在重叠网上节点始终由节点ID标识，并且根据ID进行路由