6。阻塞（choking）算法
BT并不集中分配资源。每个peer自己有责任来尽可能的提高它的下载速率。Peers从它可以连接的peers处下载文件，并根据对方提供的下载速率给予同等的上传回报（你敬我一尺，我敬你一丈）。对于合作者，提供上传服务，对于不合作的，就阻塞对方。所以说，阻塞是一种临时的拒绝上传策略，虽然上传停止了，但是下载仍然继续。在阻塞停止的时候，连接并不需要重新建立。阻塞算法并不属于BT对等协议（指peers 之间交互的协议）的技术部分，但是对提高性能是必要的。一个好的阻塞算法应该利用所有可用的资源，为所有下载者提供一致可靠的下载速率，并适当惩罚那些只下载而不上传的peers。
BT帕累托有效是指资源配置已达到这样一种境地，即任何重新改变资源配置的方式，都不可能使一部分人在没有其他人受损的情况下受益。这一资源配置的状态，被称为“帕累托最优”（Pareto optimum）状态，或称为“帕累托有效”（Pareto efficient）
在计算机领域，寻求帕累托有效是一种本地优化算法BitTorrent的阻塞算法，用一种针锋相对的方式来试图达到帕累托最优。
但是算法存在以下问题:
最后一个片断的问题被夸大了但是随机的第一个片断问题则被低估了.BitTorrentr的最少优先策略在允许一个拥有了大部文件片断的节点快速找到缺少的片断的效率并不好。
eMule协议和片选择及搜索算法
为了最大化整个网络的吞吐量和共享，eMule仔细挑选选择块的下载顺序。基本的选择策略和分片信息是这样的：每个文件被分成9.28M的块，每部分分成 180KB的片。块下载的顺序是由发送请求文件块消息（6.4.4节）的下载客户端决定。下载客户端可以在任何给定时刻从各个源中下载一个单独的文件块，所有从相同源中请求的片都在同一个块中。下面的原理（以这个顺序）应用于下载块等级：
1.（可获得的）大片的频率，尽可能快的下载非常稀少的大片来形成一个新的源。
2.用来预览的块（最初+最后的大片），预览或检查文件（比如，电影、mp3）
3.请求状态（过程中下载），尝试向每个源询问其它的大片。在所有源之间扩散请求。
4.完成（未到某种程度的完成），在开始下载另一个时应该完成获得部分的大片
频率标准定义了三个区域：非常稀少、稀少和一般。在每个区域里，标准有特定的权重，用来计算块等级。较低等级的块先下载。下面的列表根据上面的原理指定文件等级范围：
l 0-9999 - 不请求和请求非常稀少的块
l 10000-19999 - 不请求稀少和预览块
l 20000-29999 - 不请求大部分完成的一般的块
l 30000-39999 - 请求的稀少和预览的块
l 40000-49999 - 请求的没有完成的一般的块
这个算法通常选择第一个最稀少的块。然而，部分完成的块，接近完成的，也可能被选中。对于一般的块，在不同的源之间扩散下载。
eMule和BT中DHT算法
DHT的全称是Distributed Hash Table，即分布式哈希表技术，是一种分布式存储方法。这种网络不需要中心节点服务器，而是每个客户端负责一个小范围的路由，并负责存储一小部分数据，从而实现整个DHT网络的寻址和存储。和中心节点服务器不同，DHT网络中的各节点并不需要维护整个网络的信息，而是只在节点中存储其临近的后继节点信息，大幅减少了带宽的占用和资源的消耗。DHT网络还在与关键字最接近的节点上复制备份冗余信息，避免了单一节点失效问题。形象地，我们可以把整个DHT 网络想象成一个大城市，那么每个客户端，就好比城市里各个角落的地图，上面绘制了附近区域的地形情况，把这些地图一汇总，城市的全貌就出来了。
而DHT所采用的算法中最出名的是Kademlia，eMule最早开始使用，Bitcomet、Azureus和BitTorrent只是步其后尘，同样使用Kademlia算法的DHT。不过它们各自的实现协议不尽相同，因此不能相互兼容（BitComet与BitTorrent兼容，Azureus 更像eMule，但与其它都不兼容）。 在2005年5月著名的BiTtorrent在4.1.0版实现基于Kademlia协议的DHT技术后，很快国内的BitComet和 BitSpirit也实现了和BitTorrent兼容的DHT技术，实现trackerless下载方式。emule实现的基于Kademlia类似的技术（BT中叫DHT，emule中叫Kad），和BT软件使用的Kd技术的区别在于key、value和node ID的计算方法不同.
对于BT协议，目前国内用户使用最多的BT客户端就是Bitcomet，默认情况下，无须做任何设置BitComet即可自动连接并使用DHT网络。启动软件，它会使用和TCP端口号相同的UDP端口进行DHT网络连接。任何P2P技术的改进都与版权的博奕脱不了干系，DHT网络能够引起如此注目亦是如此。确实，BT采用DHT网络后，反盗版将变得更加困难。因为在此之前，用户进行BT下载时，必需首先连接上Tracker服务器，根据所获得的正在进行下载和上传的用户列表，才能够进行正常的文件交换。这样的话，只需封禁掉提供Tracker服务的网站，便可以截断盗版传播的途径。DHT网络则不同，由于此时互联网中任何一个运行BT客户端的用户都可以作为DHT网络中的节点，因此即使封禁掉那些提供Tracker服务的网站，用户还是能够通过全球范围的逻辑DHT网络分享文件，反盗版就无从谈起。除非让世界上的人都不上网，或宣布使用BT软件为重罪。但是“技术从来都是一把双刃剑”。在批判BT助长盗版气焰的同时，我们也应该看到，BT也正在日渐成为合法作品传播的途径。由于无法承受大流量的访问，一些免费和共享软件（如Foobar2000等）开始采用 BT方式分发，大型的合法软件——Linux系统，更是将BT作为主要的分发渠道。
在eMule中也有使用，常把它叫做KAD，只不过具体实现的协议有所不同。Kad网络的主要的目标是做到不需要服务器和改善可量测性。相对于传统的 ed2k服务器只能处理一定数量的使用者(我们在服务器列表也都看到了,每个服务器都有最大人数限制)，而且如果服务器比较大连接人数过多,还会严重的的拖垮网络。传统的ed2k网络需要服务器支持作为中转和存储hash列表信息，kad可以不通过服务器同样完成ed2k网络的一切功能。Kad需要UDP 端口的支持，之后Emule会自动按照客户端的要求，来判断它能否自由连线，然后同样也会分配一个id，这个过程和ed2k的高id和低id检查很像，不过这个id所代表的意义不同于ed2k网络，它代表一个是否“freely”的状态。
Kad能够自我组织,并且自我调节最佳的使用者数量以及他们的连接效果。因此, 它更能使网络的损失达到最小。由于具备了以上所叙述的功能，Kad也被称之为Serverless network（无服务器网络）。虽然目前一直处于开发阶段(alpha stage) 。通过进行 Kad关键字搜寻，任何人可以在文件分享网络中寻找资料。没有任何中央服务器储存文件索引，这项工作是平均由所有客户端担当：拥有要分享的文件的枝节点，会先处理文件的内容，并从内容计算出一组杂凑Hash值，这组值将会在分享网络中辨识这个文件。kad网络首先给每个客户分配一个唯一的ID值,然后对不同的ID值进行异或来得到两个客户之间的"距离",kad会维护一个桶,"距离"越近的用户桶里的数量会越多,kad定期对桶里的用户进行清理,以保持其有效性. 对于文件和用户emule会有两个这样的结构,可以通过kad来查找文件和文件相关的用户信息;同样为了考虑冗余的问题, kad会将其自身的信息复制一份给"距离"它最近的一定数量的用户,这样就算在它下线后,这些信息也不会丢失.Kad本身有一个nodes.dat文件，也叫做节点文件，这里面存放了我们在Kad网络中的邻居节点，我们都是通过这些节点来进入Kad网络的，相当于Bt下载中通过router来加入DHT网络。
注：在eMule具体的实现过程中，采用的ID是128bit。例如：找到用户小王则是通过将用户id异或的方式，两个id的二进位异或值决定他们之间的逻辑距离，如1100距离1101要比距离1001近。那么当一个用户加入kad后，首先通过一个已知的用户找到一批用户的id和ip地址和端口。当该用户要寻找一个特定用户A的时候，该用户先询问几个已知的逻辑距离较A较近的用户，如B用户,C用户,D用户，B，C，D会告诉该用户他们知道的更加近的用户的id和ip地址和端口，同理类推，这个用户最终就能找到A。所以寻找的次数会在logN数量级，这里N代表询问的人数。
最令人遗憾的是BT和eMule中的DHT算法无法互通和兼容！
注：在Kad网络中，系统存储的数据以<key,value>对形式存放。在BT的DHT实现中，其key值为torrent文件的info_hash串，其value值则和torrent文件有密切关系。
DHT技术的缺点和发展存在的问题
1。节点频繁加入和离开引起网络的抖动；网络波动的程度严重影响发现算法的效率。网络波动（Churn、fluctuation of network）包括结点的加入、退出、失败、迁移、并发加入过程、网络分割等。DHT的发现算法如Chord、CAN、Koorde等都是考虑网络波动的最差情况下的设计与实现。由于每个结点的度数尽量保持最小，这样需要响应的成员关系变化的维护可以比较小，从而可以快速恢复网络波动造成的影响。但是每个结点仅有少量路由状态的代价是发现算法的高延时，因为每一次查找需要联系多个结点。
2。DHT算法由于采用分布式散列函数，只适合于准确的查找，如果要支持目前Web搜索引擎具有的多关键字查找的功能，还要引入新的方法。原因在于DHT工作方式: 基于DHT的P2P系统采用相容散列函数根据精确关键词进行对象的定位与发现。散列函数总是试图保证生成的散列值均匀随机分布，结果两个内容相似度很高但不完全相同的对象被生成了完全不同的散列值，存放到了完全随机的两个节点上。因此，DHT可以提供精确匹配查询，但是支持语义是非常困难的。目前在DHT 基础上开展带有语义的资源管理技术的研究还非常少。由于DHT的精确关键词映射的特性决定了无法和信息检索等领域的研究成果，阻碍了基于DHT的P2P系统的大规模应用。作为一种资源组织与发现技术必然要支持复杂的查询，如关键词、内容查询等。尽管信息检索和数据挖掘领域提供了大量成熟的语义查询技术，由于DHT精确关键词映射的特性阻碍了DHT在复杂查询方面的应用。
3。DHT的安全性：比如节点之间通迅和查找分工没有适当安全认证机制，存在很多安全隐患
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
