信息网络与协议ch08.pptVIP

DHT原理—过程kva.Hash表b.分布式Hash表规则?KVN1N48N16N32N8KVKVKVKVChord、CAN、Tapestry、Pastry在许多情况下,节点ID为节点IP地址的Hash摘要DHT原理—索引发布和内容定位插入

(K1,V1)KVKVKVKVKVKVKVKVKVKVKV(K1,V1)查询(K1)ABK1=Hash(xyz.mp3)V1=xyz.mp3CDHT原理—过程总结网络拓扑拓扑结构由节点ID和其存放的K,V对中的K之间的映射关系决定拓扑动态变化，需要处理节点加入/退出/失效的情况定位(Locating)节点ID和其存放的K,V对中的K存在着映射关系，因此可以由K获得存放该K,V对的节点ID路由(Routing)在重叠网上根据节点ID进行路由，将查询消息最终发送到目的节点。每个节点需要到其邻近节点的路由信息，包括节点ID、IP等在重叠网上节点始终由节点ID标识，并且根据ID进行路由Chord—Hash表分布规则Hash算法SHA-1Hash节点IP地址－m位节点ID(表示为NID)Hash内容关键字－m位K(表示为KID)节点按ID从小到大顺序排列在一个逻辑环上K,V存储在后继节点上Successor(K)：从K开始顺时针方向距离K最近的节点ID=hash(IP)=14N56K=hash(key)=54N1N8N14N21N32N38N42N48N51m=6Chord—简单查询过程每个节点仅维护其后继节点ID、IP地址等信息查询消息通过后继节点指针在圆环上传递直到查询消息中包含的K落在某节点ID和它的后继节点ID之间速度太慢O(N)，N为网络中节点数N56K54Lookup(K54)N56N1N8N14N21N32N38N42N48N51m=6Chord—扩展查询过程指针表N56指针表N8+1N8+2N8+4N8+8N8+16N8+32N14N14N14N21N32N42节点S的第i个指针successor[n+2(i-1)],1≤i≤mChord—扩展查询过程指针表中有O(logN)个节点查询经过O(logN)跳N56K54指针表N8+1N8+2N8+4N8+8N8+16N8+32N14N14N14N21N32N42Lookup(K54)指针表N42+1N42+2N42+4N42+8N42+16N42+32N48N48N48N51N1N14Chord—网络波动网络波动：Churn由节点的加入、退出或者失效所引起每个节点都周期性地运行探测协议来检测新加入节点或退出/失效节点，从而更新自己的指针表和指向后继节点的指针Chord—网络波动节点加入新节点N事先知道某个或者某些节点，并且通过这些节点初始化自己的指针表其它节点运行探测协议，新节点N被反映到相关节点的指针表和后继节点指针新节点N的第一个后继节点将其维护的小于N节点ID的所有K交给该节点维护ID=hash(IP)=14N56K=hash(key)=54N1N8N14N21N32N38N42N48N51m=6N26Chord—网络波动节点退出/失效如指针表中包含失效节点，将相应指针指向大于该节点ID的第一个有效节点即该节点的后继节点维护包括r个最近后继节点的后继列表，用后继列表中第一个正常节点替换失效节点ID=hash(IP)=14N56K=hash(key)=54N1N8N14N21N32N38N42N48N51m=6N26Chord—拓扑失配O(logN)逻辑跳数，但是每一逻辑跳可能跨越多个自治域，甚至是多个国家的网络重叠网络与物理网络脱节，实际的寻路时延较大至2012年1月，BitTorrent公司宣称有1.51亿活跃用户使用BT协议第八章对等网络主要内容概述非结构化对等网络结构化对等网络主要内容概述非结构化对等网络结构化对等网络引入背景对等网络，也称为P2P网络（Peer-toPeer），主要有两个原因导致P2P网络的引入传统客户/服务器模式的不足网络边缘闲置资源利用的需求瓶颈问题：服务器的带宽、存储、计算等资源受限，易成为瓶颈单点失效问题：服务器是整个网络的中心，失效将会导致服务无法访问Internet边缘的设备(用户终