（计算机应用技术专业论文）bittorrent对等节点覆盖网络技术研究.pdf

中山大学硕士学位论文 b i t t o r r e n t 对等节点覆盖别络技术研究 论文题目： 专业： 硕士生： 指导教师： b i t t o r r e n t 对等：宵点覆盖网络技术研究 计算机应用技术 李跃华 成良玉教授 摘要 最近几年来p 2 p 文件共享己成为i n t e r n e t 中最为流行的应用，出现了一系列 优秀的基于p 2 p 技术的文件共享应用软件，而b i t t o r r e n t 系统则是这一个领域的 典型应用。本文在查阅了大量关于p 2 p 和b i t t o r r e n t 方面的文献的基础上，着重 研究了b i t t o r r e n t 系统的原理、结构和运行机制，并重点研究了现有b i t t o 盯e n t 系统的节点覆盖网络的结构特点，发现现有b i t t o r r e n t 系统的节点覆盖网络所存 在的一些系统的负载均衡性、资源可达性以及系统公平性方面的问题。 k a z a a 系统结合了n a p s t e r 和g n u t e l l a 的优点，它使用了g n u t e l l a 的全分布 式的结构，这样可以使系统更容易扩展，同时它又使用了超级节点，用超级节点 来存储离它最近的叶子节点的文件信息，这些超级节点，再连接起来形成一个覆 盖网络。 k a z a a 系统的成功为b i t t o r r e n t 系统的覆盖网络改造提供了范例。k a z a a 系 统的利用超级节点实现分层拓扑结构的思想能够很好地解决系统均衡和资源可 达性以及系统公平性方面的问题，这一思想对于解决b i t t o r r e n t 系统存在的问题 恰到好处，不谋而合。因此，本人综合k a z a a 系统的超级节点分层拓扑思想以 及b i t t o r r e n t 系统的文件分片合作下载思想，提出一个带多个超级节点的双层 b r t o r r e n t 覆盖网拓扑结构的b i t t o r r e n t 系统k a z a ab t 。 文章在最后对新提出的b i t t o r r e n t 节点覆盖网络方案k a z a a b t 进行了网络 仿真实验和效果分析，证明k a z a ab t 是一种可行的b i t t o r r e n t 系统的节点覆盖 网络改进方案，并对k a z a ab t 进行了总结和展望。 关键词：p 2 p ，b i t t o r r e n t ，覆盖网络，k a z a a ，超级节点 中山大学硕士学位论文b i t t o r r e n t 对等节点覆盖网络技术研究 t i t i e ： m a j o r ： n a m e ： s u p e r v i s o r ： s t u d yo nb i t t o r r e n tp e e ro v e d a yn e t w o r kt e c h n o l o g y c o m p u t e ra p p l i c a t i o nt e c h n o l o g y l iy u e h u a p r o f e s s o rc h e n gl i a n g y u a bs t r a c t p 2 pf i l es h a r 吨a p p l i c a t i o n sh a sb e c o m et h em o s tp o p u l a ra p p l i c a t i o n si ni n t e r n e t i nr e c e n ty e a r s ，al o to fe x c e l l e n tf i l es h a r i n ga p p l i c a t i o n sb a s e do np 2 pt e c h n o l o g i e s e m e r g e di n c l u d i n gb i t t o r r e n ts y s t e m sw h i c hi s at y p i c a lo n ei nt h i sf i e l d t h i s d i s s e r t a t i o nf o c u s e dm u c he f f o r to nt h ep r i n c i p l e ，s t r u c t u r ea n do p e r a t i n gm e c h a n i s m o f b i t t o r r e n ts y s t e m sb a s e do nl o t so fl i t e r a t u r ei np 2 pa n db i t t o r r e n t ，a n ds t u d i e dt h e p e e ro v e r l a yn e t w o r ko fb i t t o r r e n ts y s t e m sa sa ne m p h a s i sw h i l ef o u n ds o m ee x i s t i n g p r o b l e m sl i k el o a db a l a n c e ，r e s o u r c e sa c c e s s a b i l i t ya n ds y s t e mf a i r n e s si nt h ep e e r o v e r l a yn e t w o r ki nb i t t o r r e n ts y s t e m k a z a as y s t e mc o m b i n e st h ea d v a n t a g e so fn a p s t e ra n dg n u t e l l a k a z a au s e s f u l ld i s t r i b u t e ds t r u c t u r ew h i c hm a k ei te a s yt oe x t e n d ，a n dt a k e sa d v a n t a g e so f s u p e r - n o d ei nw h i c hi ts t o r et h ef i l ei n f o r m a t i o no ft h en e a r e s tl e a fn o d e sa n df r o m w h i c hi tc o n s t r u c ta no v e r l a yn e t w o r k t h es u c c e s so fk a z a a s y s t e m ss e t sag o o de x a m p l ef o rt h et r a n s f o r m a t i o no f t h e p e e ro v e r l a yn e t w o r ko fb i t t o r r e n ts y s t e m s t h et h o u g h to fs u p e r - n o d ea n d h i e r a r c h i c a lt o p o l o g yi nk a z a as y s t e m sc a nr e p a i rt h el o a db a l a n c e ，r e s o u r c e s a c c e s s a b i l i t ya n ds y s t e mf a i r n e s sp r o b l e m sw h i c ho c c u r r e di nb i t t o r r e n ts y s t e m s s oi p r o p o s e dan e wk i n do fb i t t o r r e n ts y s t e m sn a m e dk a z a a _ b t , w h i c hc o m b i n e st h e t h et h o u g h to fs u p e r - n o d ea n dh i e r a r c h i c a lt o p o l o g yi nk a z a as y s t e m sa n dt h e t h o u g h to ff i l ep i e c i n ga n dc o d o w n l o a d i n g a tt h ee n do ft h i sd i s s e r t a t i o n , it e s t i f i e dt h ea v a i l a b i l i t yo ft h ek a z a a b tu s i n g n e t w o r ks i m u l a t i o ni nn s 2 ，a n dm a d eas u m m a r ya n de x p e c t a t i o n k e yw o r d s ：p 2 p , b i t t o r r e n t ，o v e r l a yn e t w o r k ，k a z a a , s u p e r - n o d e 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体己经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：细睥妒 使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：恋侈瞄争 r 期：冰r 月莎日 导师签名：舣良 日期：劲，脾f 月7 日 第1 章绪论 1 1p 2 p 与b i t t o r r e n t 技术简介 长期以来，传统的互联网计算模型c l i e n t s e r v e r ( c s ) 模型一直都是互联网领 域最主要的应用形式，如浏览网页和一些简单的局域网应用系统，p c 机首先向 服务器发出请求，然后从服务器上下载程序或数据。一些重要的协议像h t t p ， f t p 等都支持这种方式的服务，f t p 以其简单、稳定的文件传输方式而一直保持 着强大的生命力。h t t p 也成为了一种到目前为止w e b 应用领域事实上的标准。 由于c s 模型是向一台服务器请求服务，而服务器所提供的带宽和处理能力 是一定的。这样就容易出现一个问题：在这种中心化网络体系结构中，随着客户 不断的加入，用户的数量不断增多，整个网络不断扩大，对带宽和服务器的处理 能力的要求也随之持续增多，在这种情况下，服务器的瓶颈问题变的尤为突出， 服务器亦十分有可能崩溃，而服务器的崩溃就会造成整个系统的瘫痪。所以很多 的服务器都会有用户人数和下载速度的限制，这样就给用户造成了诸多的不便。 而在此同时，网络中大部分的客户机却处于空闲状态。 事实上，i n t e m e t 本身就是一个巨大的非集中式的网络。因特网本身的意义 也在于将巨大数量的分散的机器以各种不同的方式连接在一起。而这种连接的结 果就是一个包罗万象的分散的网络结构。如何能利用好因特网，就在于怎样才能 利用好这许多分散的非集中的资源。 如何合理利用好那些闲置的处理资源和未用的带宽，同时又能防止瓶颈问 题，p 2 p 计算模式提供了很好的解决办法。p 2 p 计算并非是一种全新的技术，早 在2 0 世纪7 0 年代就己出现，典型代表是u s e n e t 和f i d o n e t 这两个信息交换 系统，真正的p 2 p 技术的大规模应用起源于1 9 9 9 年的文件交换系统n a p s t e r 。 n a p s t e r 是最早出现的大规模p 2 p 应用系统，他由大量个人计算机用户参与， 每个用户都将共享出自己愿意共享的音乐文件，同时也可以下载其他用户的音乐 文件。n a p s t e r 在推出的初期取得了巨大的成功，一时间成为众多用户的选择， 但是之后他很快迫于版权问题的困扰，于2 0 0 1 年关闭。尽管如此，n a p s t e r 第一 次证实了p 2 p 思想在广域网范围内应用的可行性，在n a p s t e r 关闭之后，更多的 p 2 p 应用系统如雨后春笋般涌现，形成i n t e r n e t 领域的一股巨大发展浪潮。 p 2 p 可以简单的理解为一个节点既是客户端同时也是服务器。其节点拓扑结 构既有完全分布式的也有集中式的以及混合式的。完全分布式的结构被称为纯粹 的p 2 p 结构，象g n u t e l l a 就是一个很典型的纯粹的p 2 p 代表，而前面提到的 n a p s t e r 则是一个集中式的p 2 p 系统。与传统的分布式系统相比，p 2 p 技术在可 扩展性，健壮性，性价比，隐私保护和负载均衡等方面具有无可比拟的优势，因 此也具有了广阔的应用前景。根据具体应用不同，可以将p 2 p 分为以下类型i l 】： ( 1 ) 提供文件和其它内容共享的p 2 p 网络，例如n a p s t e r 、g n u t e l l a 、e d o n k e y 、 e m u l e 、b i t t o r r e n t 等； ( 2 ) 挖掘p 2 p 对等计算能力和存储共享能力，例如s e t i h o m e 、a v a k i 、 p o p u l a rp o w e r 等； ( 3 ) 基于p 2 p 方式的协同处理与服务共享平台，例如j x t a 、m a g i 、 g r o o v e 、n e tm ys e r v i c e 等； ( 4 ) 即时通讯交流，包括i c q 、o i c q 、y a h o om e s s e n g e r 等； ( 5 ) 安全的p 2 p 通讯与信息共享，例如s k y p e 、c r o w d s 、o n i o nr o u t i n g 等。 b i t t o r r e n t 是p 2 p 文件共享领域里的一项应用，也是当前最为流行的一个。 b i t t o r r e n t 吸引了大量的i n t e r n e t 用户，并成为i n t e m e t 中最主要的基于p 2 p 技术 的文件共享系统。曾经一段时间，b i t t o r r e n t 占据了整个i n t e m e t 流量的3 5 ，而 b i t t o r r e n t 流量也占所有p 2 p 文件共享系统总流量的5 3 | 2 1 。 b i t t o r r e n t ( 简称b t ) 系统简单地由一个中央服务器和一些接点组成，最初 的文件共享者通过发布一个包含有文件和中央服务器信息的种子文件来提供文 件共享，其他的文件下载者也通过这个种子文件和中央服务器来发现彼此并以很 高的效率来分发文件。 同传统的c s 模式以及纯粹的p 2 p 模式相比，b i t t o r r e n t 可以称的上是两者 的结合，同时也集中了两者的优点。b i t t o r r e n t 的种子是通过w e b 来发布的，其 发布者可以是众多的网络用户，信息覆盖广，更新快。同时b i t t o r r e n t 在获得c s 模式较高管理效率的情况下不需要发布种子的文件共享者象c s 模式那样提供 高额的投入就可以获得p 2 p 方式的极大的文件分发效率。 2 1 2 研究现状 b i t t o r r e n t 是目前因特网上最为流行的p 2 p 文件共享系统之一。b i t t o r r e n t 文 件共享系统在实际应用和学术研究中都吸引了人们大量的关注。b i t t o r r e n t 的成 功使得b i t t o r r e n t 得到了很大范围的推广应用。目前，互联网上出现了数十款 b i t t o r r e n t 下载工具。还有一些其他的软件，受b i t t o r r e m 文件分块分发思想的启 发，也做出了类似b i t t o r r e m 功能，像e d o n k e y 和e m u l e 。 b i t t o r r e n t 不但在实际应用中得到了人们的喜欢，在学术研究领域也得到了 众多研究者的青睐。自从2 0 0 3 年b c o h e n 首次在p 2 pe c o n o m i c sw o r k s h o p 上提 出b i t t o r r e n t 系纠3 1 以来，b i t t o r r e n t 就引起了很多人的关注。2 0 0 4 年，x y a n g 和gd ev e c i a n a 在i n f o c o m l 4 1 上以及d q i u 和r s r i k a n t 在s i g c o m m 5 】上发表 了对b i t t o r r e n t 的研究成果，对b i t t o r r e n t 系统的服务能力及性能做了模拟和分 析。2 0 0 5 年，j a p o u w e l s e 和eg a r b a c k i 在i p t p s 6 】上发表了对b i t t o r r e n t 系统 进行测量和分析研究的论文，a l e g o u t 和gu r v o y k e l l e r 等人通过实验的角度 来对b i t t o r r e n t 系统进行了理解和探讨【7 1 。2 0 0 6 年，r u c h i rb i n d a l ，p e ic a o 和 w i l l i a mc h a n 等人则提出了通过在t r a c k e r 服务器上对邻居接点进行有偏选择的 办法来得到的更近的邻居接点以提高下载速度的办法【8 】，c f r y 和m r e f e r 则提 出一种可以省略t r a c k e r 服务器的方法来构建b i t t o r r e n t 网络t 9 。2 0 0 7 年，p u r v i s h a h 和j e h a n - f r a n v o i sp a r i s 将b i t t o r r e n t 应用到了流媒体领域【1 0 】，l e ig u o 和 s o n g q m gc h e n 等人则对类b i t t o r r e n t 系统的性能进行了更为全面的研究和剖析 【1 1 】。近几年来，在一些国际顶级会议上，如i n f o c o m 、i p t p s 、i c d c s 和i w q o s 等，也不断出现了关于b i t t o r r e n t 方面的一些研究成果。很多学者做了在真实或 者是模拟环境下的b i t t o r r e n t 系统的性能的测量和评估，发现b i t t o r r e n t 系统有 着良好的性能，可以支持大规模的文件并发下载。很多的研究成果都从各个不同 的方面和角度对b i t t o r r e n t 系统进行了分析和研究。 目前，大部分的针对b i t t o r r e n t 系统的研究都集中于以下三个方面： ( 1 ) b i t t o r r e n t 系统的服务能力 ( 2 ) b i t t o r r e n t 系统的激励机制 ( 2 ) b i t t o r r e n t 系统覆盖网络的拓扑结构 3 1 3 本文的研究工作 本文主要做了以下工作： ( 1 ) 查阅了大量关于p 2 p 和b i t t o r r e n t 方面的文献，分析了b i t t o r r e n t 系统 的客户端和t r a c k e r 服务器端的功能和运行过程，着重研究了b i t t o r r e n t 系统的 协议、原理、结构和运行机制。 ( 2 ) 重点研究了现有b i t t o r r e n t 系统的节点覆盖网络的结构特点，分析了现 有b i t t o r r e n t 系统的节点覆盖网络的缺陷，并在比较各种现有p 2 p 覆盖网络拓扑 结构的基础上提出了一种新的b i t t o r r e n t 节点覆盖网络方案k a z a ab t 。 ( 3 ) 对本文提出的新的b i t t o r r e n t 节点覆盖网络方案k a z a ab t 进行了网 络仿真实验和效果分析，并将其与原有b i t t o r r e n t 系统的性能进行了对比。 1 4 论文的结构 第一章：绪论，概述了论文的研究背景、研究现状及本文的主要工作和组织 结构。 第二章：b i t t o r r e n t 系统描述与分析，介绍了b i t t o r r e n t 系统的框架、组成和 协议，简要分析了客户端和服务器端的主要功能和算法。 第三章：b i t t o r r e n t 对等节点覆盖网络技术研究及改进，探讨和分析了 b i t t o r r e n t 系统的覆盖网络形成机制和缺陷，并在研究现有p 2 p 覆盖网络拓扑结 构的基础上提出一种新的b i t t o r r e n t 对等节点覆盖网络改进方案k a z a a _ b t ，并 对其进行了描述和分析。 第四章：仿真实验与分析，介绍了实验环境、实验过程以及参数设置，分析 对比了实验结果。 第五章：总结与展望，对前文的工作进行了总结，并对以后的研究方向进行 了展望。 4 第2 章b it t o rr e n t 系统描述与分析 最近几年来p 2 p 文件共享己成为i n t e m e t 中最为流行的应用，出现了一系列 优秀的基于p 2 p 技术的文件共享应用软件，而b i t t o r r e n t 系统则是这一个领域的 典型应用。p 2 p 文件共享软件的成功来自于其高效的内容定位和文件传输机制。 尽管在最近几年里，内容定位吸引了大量的相关研究，而文件传输仅在最近才开 始成为人们主动研究的相关内容。一些人们非常熟悉的p 2 p 文件共享应用如 e d o n k e y , f a s t t r a c k ，g n u t e l l a , o v e m e t 都着重于内容定位，而b i t t o r r e n t 是应用 最广泛的着重于内容传输的p 2 p 文件共享应用系统。 b i t t o r r e n t 是一种高效文件内容分发协议。b i t t o r r e n t 最早于2 0 0 3 年由b r a m c o h e n 在一篇论文中提出，但是其最初的实现是他在2 0 0 2 年使用p y t h o n 语言编 写的，并以m i t 许可证发布来发布其开源的专利代码，因此当时b i t t o r r e n t 得到 了很快的发展。b i t t o r r e n t 采用高效的文件分片传输和点对点技术来共享大体积 文件，系统中每个下载用户即是客户端又是服务器端，不同的下载用户合作下载 同一个文件，并在拥有文件片段之后相互转发自己所拥有的文件部分，直到每个 用户的下载都全部完成。这种方法可以大大降低初始的文件共享者的传输任务， 而将负载同时均匀到每个下载者，这对于大体积文件的下载非常有利，可以快速 下载完整个文件，而无须占用大量带宽。 b i t t o r r e n t 以其优秀的文件分发表现，而得到了众多用户的喜爱，也因此吸 引了大量开发者对其软件系统的改进和同类新产品的开发的尝试。目前在市面上 出现了很多款b i t t o r r e n t 下载管理软件，其中流行的比较优秀的b i t t o r r e n t 软件 包括：b i t c o m e t 1 2 1 、u t 0 盯e n t 【1 3 】、a z u r e u s t l 4 1 、b i t s p i r i t t l5 1 、b i t t o r r e n t 等。b i t c o m e t 又叫做比特彗星，是一款非常流行的功能强大，界面友好的b t 下载管理软件。 b i t c o m e t 拥有多项领先的b t 下载技术，有边下载边播放的独有技术，也有方便 自然的使用界面。同时还将b t 技术应用到了普通的h t t p f t p 下载，可以通过 b t 技术加速普通下载。a z u r e u s 采用j a v a 编写，是一款跨平台的b t 客户机程序， 具备2 7 种语言供选择，用户可在单一的g u i 窗口同时管理多个下载、检视详细 的实时下载统计、设定进阶下载管理规则、设置和建立t o r r e n t 等，功能也很强 5 大，在英文用户中覆盖范围比较大。而b i t s p i r i t 又叫做比特精灵，以其高效稳定， 简单易用而著称。与前面的这些相比，用c 抖编写的u t o r r e n t 则相对轻量级很多， 但也因为它的小的特点以及稳定和对较旧硬件的支持而收到持续的好评。而所有 这些新近流行的软件的鼻祖b i t t o r r e n t 则相对使用用户少很多，但是由于其是开 放源代码的，是由他实现了b i t t o r r e n t 的思想，且其他的软件均是在其基础上加 以改进或模仿而得到的，因此也不失为一款很好的研究和使用的软件产品。 2 1b i t t o r r e n t 系统框架 一个b t 文件文件下载系统主要由下列部分组成： ( 1 ) 一个普通的w e b 服务器 ( 2 ) 一个t o r r e n t 种子文件( 也称为元信息文件) ( 3 ) 一个t r a c k e r 服务器 ( 4 ) 一个原始文件数据提供者 ( 5 ) 终端用户的w e b 浏览器 ( 6 ) b t 客户端 最初的文件共享者 图2 1b i t t o r r e n t 系统结构图 6 一个文件下载的流程如下： ( 1 ) 文件拥有者将文件通过b i t t o r r e n t 种子制作工具，将文件校验、大小、 t r a c k e r 服务器地址等信息制作成一个大小相对很小的t o r r e n t 种子文件。 ( 2 ) 文件拥有者将种子文件上传到种子发布站点，使浏览该站点的用户可 以知道有这个文件的存在并下载该种子文件来与其他下载这个文件的用户共同 下载。 ( 3 ) 文件拥有者通过下载工具来打开种子文件，连接到t r a c k e r 服务器进行 注册，开启文件的共享，提供上传服务。 ( 4 ) 文件下载者浏览种子发布站点，下载种子文件。 ( 5 ) 文件下载者打开种子文件，连接到t r a c k e r 服务器，注册，并从t r a c k e r 服务器处获得同一文件下载者的节点列表。 ( 6 ) 各个文件下载者通过不断的互相联系以及与t r a c k e r 之间的交流，来有 选择的下载和上传文件片段，直到所有节点都下载完毕为止。 要架构一个b i t t o r r e n t 系统，b t 下载客户端是自由的加入和退出的，最主要 的就是要搭配好t r a c k e r 服务器以及种子发布站点，以使系统能够提供稳定高效 的服务。流程如下： ( 1 ) 运行一个t r a c k e r 服务器 ( 2 ) 运行一个w e b 服务器，如a p a c h e 或者i i s 等。 ( 3 ) 在w r e b 服务器上运行种子发布系统( 通常是w e b 页面程序) 。 ( 4 ) 在w e b 服务器上，将文件扩展名t o r r e n t 和m 类型 a p p l i c a t i o n x b i t t o r r e n t 关联起来。 其中，t r a c k e r 服务器和w e b 服务器可以分别运行在不同的服务器上，但是 通常为了简单起见，都是运行在同一个服务器上。 至此，一个完整的b i t t o r r e n t 系统就可以运行了。在整个系统运行过程中， 在文件被其他节点发现前，t r a c k e r 服务器和w e b 服务器担任着很紧缺的资源的 角色，如果t r a c k e r 服务器或者w e b 服务器运行出错的话，就会影响到其他节点 发现共享文件的地址。在客户端获得种子文件并从t r a c k e r 服务器处获得节点列 表之后，最初的文件共享者就担任了这个过程的最重要的角色了。在最初的文件 共享者那里，一个共享文件被分成了很多小的文件块，下载者一块一块的从最初 7 的文件共享者那里得到原始下载数据。而最初的文件共享者的原始数据也会至少 持续比较长的一段时间才能被下载完，这个过程是不能被加速的。因为在下载开 始的时候，原始数据块只有最初的文件共享者才拥有，其他的下载节点都没有， 因此其他下载节点只能从最初的文件共享者处获得所有文件块的原始数据，一旦 一个数据块被下载下来以后，就可以通过在下载节点之间互相复制来加速整个下 载过程了。但是一旦最初的文件共享者在没有传完所有块的情况下就离开的话， 这一整个下载过程就不可能完成了。 整个系统各个部分之间的连接性如下： 种子发布站点负责提供一个静态的元信息文件( t o r r e n t 文件) ，而b t 客户 端则位于客户端机器上。t r a c k e r 服务器从所有下载者处接收信息，并返回给它 们一个随机的p e e r s 的列表。这种交互是通过h t t p 或h t t p s 协议来完成的。 下载者周期性的向t r a c k e r 服务器登记，使得t r a c k e r 服务器能了解它们的进度； 下载者之间通过直接连接进行数据的上传和下载。这种连接使用的是b i t t o r r e n t 对等协议，它是基于t c p 的。最初的文件共享者只负责上传，从不下载，因为 它已经拥有了完整的文件。最初的文件共享者是必须的。元文件和t r a c k e r 服务 器的响应都采用的是一种简单、有效、可扩展的格式，被称为b e n c o d i n g ，它可 以包含字符串和整数。由于对不需要的字典关键字可以忽略，所以这种格式具有 可扩展性，其它选项以后可以方便的加进来。 2 2b i t t o r r e n t 系统术语 到目前为止，在p 2 p 文件共享系统中，特别是在b i t t o r r e n t 系统中，还没有 形成标准统一的专门术语。在此，我为了更加清楚的描叙b i t t o r r e n t 系统，特地 将b i t t o r r e n t 系统中一些经常要用的到的名词抽出并加以解释。 文件块：在b i t t o r r e n t 系统中，一个文件通常在传输的时候被分成很多个 小块，然后以小块为计算单位来进行传输的，通常是2 5 6 k 一块。节点之间计算 传输了多少文件块时就是用这个单位来计算的，但是在实际的传输时，又通常将 这一块再分成很多小块来传输，比如1 6 k 每小块。 邻居结点集合：每个节点都会在运行的过程中保留和维护一些其他节点 的信息，以便于与这些节点进行数据的传输，这些节点就是这个节点的邻居，邻 8 居节点的集合就叫做邻居节点集合，邻居结点通常是通过跟t r a c k e r 服务器请求 后，从返回的节点列表中得到的，这个数量通常为5 0 。 连接结点集合：连接结点是邻居节点中的一部分，节点在每一个时刻只 能上载数据给其邻居节点中的部分节点，这一部分节点叫做这个节点的连接节 点，其集合叫做连接节点集合，这个数量通常是4 。 疏通与阻塞：通常用来表示两个节点间的关系，节点a 决定不给节点b 传送数据，则称为节点a 阻塞节点b ，相反，如果节点a 决定给节点b 传送数 据，则称节点a 疏通节点b 。 种子和下载结点：在b i t t o r r e n t 系统中，一共存在着两种类型的节点，一 种是存有完整的文件即已经下载完所有文件块的节点，因为他们只提供上传而不 再下载，所以叫做种子，还有另外一种节点，这种节点还没有下载完全部的文件 块，他们既可以提供上传的服务，又同时在下载自己所需要的文件块，叫做下载 节点。 t r a c k e r 服务器：为一中央目录服务器，他的功能被严格定义为帮助节点 之间互相发现对方。每个节点都需要到t r a c k e r 服务器去进行注册并保持与 t r a c k e r 服务器的联系以更新自己在t r a c k e r 服务器上的信息，同时从t r a c k e r 服 务器处得到其他下载节点的信息，以取得自己的邻居节点信息。 阻塞算法：阻塞算法是b i t t o r r e n t 系统中的节点选择算法。各个节点通过 阻塞算法来选择自己想要上传的节点，一般是使用t i t f o r - t a t 策略来进行选择的。 最少文件块：最少文件块是指在整个b i t t o r r e n t 系统中拥有的数量最少的 文件块。 最少文件块优先算法：是一个节点的文件块选择算法，节点会在选择下 载文件块的时候选择一个最少的文件块来进行下载。最少文件块优先算法又包括 全局最少文件块优先算法和局部最少文件块优先算法。全局最少文件块优先算法 是指选择在当前所有下载者中最少的文件块来进行下载，局部最少文件块优先算 法是指选择在所有邻居节点中存在最少的文件块来进行下载。由于b i t t o r r e n t 系 统系统的高度动态性，使得布局全局最少文件块优先算法的实现非常困难，因此 在实际的操作过程中，一般都是使用局部最少文件块优先算法。 b i t t o r r e n t 节点覆盖网络：在b i t t o r r e n t 系统中，所有的节点自发地形成 9 一个覆盖网，包括邻居节点覆盖网络和连接节点覆盖网络。由所有的节点通过他 们之间的邻居关系形成的覆盖网叫做邻居节点覆盖网络，由所有节点及其当前正 在进行数据交换的节点之间关系所形成的覆盖网络叫做连接节点覆盖网络。连接 节点覆盖网络是邻居节点覆盖网络的一个子集。 2 3b i t t o r r e n t 协议解释 b i t t o r r e m 是一种分发文件协议。它通过u r l 来识别内容，并且可以和w e b 进行无缝交互。它使用h t t p 协议，这样做的优势是：在多个下载者并发的下载 同一个文件时，每个下载者也同时为其它下载者上传服务，通过这种方式，文件 源可以支持大量的用户同时进行下载，而因为大量的负载被均衡到整个系统中， 所以提供源文件的机器的负载只有少量增长。 b i t t o r r e n t 协议主要包括以下几个方面的内容：b e n c o d i n g 编码，元信息文件 格式，t r a c k e r 查询格式，t r a c k e r 响应格式，b i t t o r r e n t 对等协议，对等消息类型 【1 6 1 。 2 3 1b e n c o d i n g 编码 t r a c k e r 的回应信息和元信息文件都以一种简单、高效并可扩展的格式来传 送，这种格式就是b e n c o d i n g 编码( 也称b 编码) 。b 编码过的信息是只包含字 符串和整型数据的字典和列表的嵌套。b e n c o d i n g 的格式如下： 对于字符串，其格式是字符串的长度加冒号再跟着实际的字符串，例如： 4 ：s p a r e ，就是字符串“s p a m 。 对于整数，编码规则如下，以i 开始，然后是1 0 进制的整数值，最后 以e 结尾。例如，i 3 e 表示3 ，i 3 e 表示3 。整数没有大小限制。i 0 e 是无效 的。除了i o e 表示0 外，所有以0 起始的整数都无效。 对于列表，编码规则如下，以l 开始，接下来是列表值的编码( 也采 用b 编码) ，最后以e 结束。例如：1 4 ：s p a m 4 ：e g g s e 表示【“s p a m , e g g s ”】。 对于字典，编码规则如下，以d 开始，接下来是可选的k e y s 和它对应 的值，最后以e 结束。例如：d 3 ：c o w 3 ：m 0 0 4 ：s p a m 4 ：e g g s e ，表示 c o w ：m o o ， s p a m ：e g g s ) ，而d 4 ：s p a m l l ：a l ：b e e 表示 s p a m ：【一a ，l b 】) 。 l o 2 3 2 元信息文件格式 元信息文件是采用b e n c o d i n g 编码的字典，他主要包含有以下关键值： 字段类型含义 a n n o u n c e字符串声明，t r a c k e r 服务器的u r l i n f o 字典共享文件的信息 表2 1 元信息文件主要键值 其中，对于单文件的元信息文件，i n f o 关键值对应一个字典包含如表2 2 所 描述的关键值： 字段类型含义 n a n l e字符串默认的下载文件或存放目录的名字 p i e c el e n g t h 整数 对应文件分割成的块的字节数 p l e c e s 字符串长为2 0 的倍数，分别为每个块的s h a l 校验码 l e n g t h 整数文件长度的字节数 表2 - 2 单文件情况下i n f o 字段的结构 在多文件情况下，元信息文件的i n f o 关键值与单文件情况下的最后一项不 同，将l e n g t h 字段变成了f i l e s 字段，具体如表2 3 所示： 字段 类型含义 n a m e 字符串默认的下载文件或存放目录的名字 p i e c el e n g t h 整数对应文件分割成的块的字节数 p i e c e s 字符串 长为2 0 的倍数，分别为每个块的s h a l 校验码 f i l e s 字典文件列表 表2 - 3 多文件情况下i n f o 字段的结构 在多文件情况下，多个文件被看作是把许多单文件按文件列表中的顺序连成 一个大文件下载，而关键值f i l e s 就对应文件列表，是一个字典的列表，其中每 一项又主要包含以下关键值： 字段类型含义 l e n g t h 整数长度，文件长度的字节数 p a t h 列表各个子目录名和文件名的列表 表2 4 多文件情况下f i l e s 字段的结构 2 3 3t r a c k e r 查询格式 t r a k c e r 通过h t t p 的g e t 命令的参数来接收信息，而响应给对方的是经过 b 编码的消息。尽管当前的t r a c k e r 的实现需要一个w e b 服务器，但是实际上可 以运行的更轻便一些，比如，作为a p a c h e 的一个模块。 发送给t r a c k e r 的g e t 请求，包含以下关键字： i i l 南h a s h ：元文件中i i l f o 部分的s h a l 验证码，2 0 字节长。 p e e ri d ：下载者的i d ，一个2 0 字节长的字符串。每个下载者在开始一次 新的下载之前，需要随机创建这个i d 。 i p ：一个可选的参数，给出了p e e r 的i p 地址( 或者d n s 主机名) 。通常用 在最初的文件共享者身上，假如它和t r a c k e r 在同一个机器上。 p o r t ：p e e r 所监听的端口。下载者通常在在6 8 8 1 端口上监听，假如该端 口被占用，那么会一直尝试到6 8 8 9 ，假如都被占用，那么就放弃监听。 u p l o a d e d ：已经上载的数据大小，十进制表示。 d o w n l o a d e d ：已经下载的数据大小，十进制表示。 l e f t ：该p e e r 还有多少数据没有下载完，十进制表示。 e v e n t ：这是个选择性的关键值，选项有s t a r t e d ，c o m p l e t e d 或m o p p e d ( 或 e m p t y ，等同于没有运行) 。如果没有运行，这个声明会定期间隔一段时间发出。 开始下载时发出s t a r t e d 值，完成下载时发出c o m p l e t e d 。如果一开始文件就是完 整的，则不会发出c o m p l e t e d ，下载者中止下载时发出s t o p p e d 。 2 3 4t r a c k e r 响应格式 t r a c k e r 的响应也是b 编码字典。如果t r a c k e r 响应中有关键值f a i l u r er e a s o n ， 就会对应一个人可以读懂的字符串信息解释质询失败的原因，不需要其它关键 值。否则，响应必须有两个关键值： i n t e r v a l 对应下载者定期发出请求的间隔秒数； p e e r s 对应着一个字典，包含了p e e r 自选i d 、i p 地址或d n s 主机名的字 符串和端口号。 尽管如此，p e e r s 不会完全按照计划的间隔发送请求，假如他们发生一个事 件或者想要更多的p e e r s ，那么下载者可能不定期的发送请求，下载者通过h t t p 的g e t 命令来向t r a c k e r 发送查询请求，t r a c k e r 响应一个p e e r s 的列表。 2 3 5b i t t o r r e n t 对等协议 b i t t o f r e n t 对等协议指的是p e e r 与p e e r 之间交换信息的协议，它是一种基于 1 2 t c p 的应用层对等协议。对等的两个连接是对称的，消息在两个方向上同样的传 递，数据也可以在任何一个方向上流动。 任何一个连接的任何一端都包含四比特的状态信息：是否阻塞对方 ( c h o k i n g ) 、是否对对方感兴趣( i n t e r e s t i n g ) 、是否被对方阻塞( c h o k e d ) 、是否 被对方感兴趣( i n t e r e s t e d ) 。任何一方只有当没有被对方阻塞( c