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进行路由