saga's blog

突出重点,系统全面,不留死角

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 2 Stories :: 185 Comments :: 0 Trackbacks

公告

QQ:34O859O5

常用链接

留言簿(15)

搜索

  •  

积分与排名

  • 积分 - 207704
  • 排名 - 118

最新评论

阅读排行榜

评论排行榜

Kad是Kademlia的简称,eMule的官方网站在2004年2月27日正式发布的 eMule v0.42b中,Kad开始正式内嵌成为eMule的一个功能模块,可以说从这个版本开始eMule便开始支持Kad网络了。

Kad的出现,结束了之前edonkey时代,在ed圈里只存在着ED2K一种网络的模式,它通过新的协议开创并形成了自己的kad网络,使之和ED2K网络并驾齐驱,而且它还完全支持两种网络,可以在两种网络之间通用。Kad同样也属于开源的自由软件。它的程序和源代码可以在官方网站[url]http://www.emule-project.net[/url]上下载。

Kad网络拓扑的最大特点在于它完全不需要服务器,我们都知道传统的ed2k网络需要服务器支持作为中转和存储hash列表信息,kad可以不通过服务器同样完成ed2k网络的一切功能,你唯一要做的就是连线上网,然后打开kad。Kad需要UDP端口的支持,之后Emule会自动按照客户端的要求,来判断它能否自由连线,然后同样也会分配给你一个id,这个过程和我们ed2k的高id和低id检查很像,不过这个id所代表的意义不同于ed2k网络,它代表一个是否“freely”的状态。

Kad和ed2k网络有着完全不同的观念但是相同的目的: 都是搜索和寻找文件的源。 Kad网络的主要的目标是做到不需要服务器和改善可量测性。相对于传统的ed2k服务器只能处理一定数量的使用者(我们在服务器列表也都看到了,每个服务器都有最大人数限制),而且如果服务器比较大连接人数过多,还会严重的的拖垮网络。而Kad能够自我组织,并且自我调节最佳的使用者数量以及他们的连接效果。因此, 它更能使网络的损失达到最小。由于具备了以上所叙述的功能,Kad也被称之为Serverless network(无服务器网络)。虽然目前一直处于开发阶段(alpha stage) 。但毫无疑问,它无可比拟的优势,将会使它成为p2p的明天。


通俗的来讲就是在kad网络中,我们每个emule用户端只负责处理一小部分搜索和查找源的工作。分配这些工作的时候,通过我们每个用户端的唯一的ID和搜索文件的hash值之间的匹配来决定。比如像我猜我猜我猜猜.rm这个文件由用户小王来负责(通过该文件的hash值来决定),那么任何其他用户在下载这个文件的时候都会告诉其他用户,小王有这个文件,其他用户去下载这个文件的时候也会询问小王,小王也会告诉他们谁正在共享这个文件,这样kad找源的工作就完成了。搜索时候的方法也差不多,只不过是每个人负责一个关键字。

整个过程有点像在照线索循序问路而找到正确方向,而不是路上随便到处抓人在问路。而每个地方里的网络相关信息,则会随着电脑及文件的加入而持续更新。好处在于让你可以搜索整个网络,而不只是在某一地区。目前来讲,这个机制和算法是绝对领先而且非常优秀的。

如何找到用户小王则是通过将用户id异或的方式,两个id的二进位异或值决定他们之间的逻辑距离,如1100距离1101要比距离1001近。那么当一个用户加入kad后,首先通过一个已知的用户找到一批用户的id和ip地址和端口。当该用户要寻找一个特定用户A的时候,该用户先询问几个已知的逻辑距离较A较近的用户,如B用户,C用户,D用户,B,C,D会告诉该用户他们知道的更加近的用户的id和ip地址和端口,同理类推,这个用户最终就能找到A。所以寻找的次数会在logN数量级,这里N代表询问的人数。

其实也就是一种分散式杂凑的方法,基本上是对网络上某一特定时刻的文件进行快照(snapshot),然后将这些信息分散到整个网络里。 为了找到特定的文件,搜索的要求先到达网络上的任何一台电脑上,然后这台电脑就会再将它转到另一台有更多文件信息的电脑。第三台电脑可能就拥有文件本身——或者也可能再继续转到其他有正确信息的电脑。采用这种方法,通常只需要跳转两到三次,便可以轻松查找到所需文件。
posted on 2006-06-01 23:15 saga.constantine 阅读(1616) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理