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