（信息与通信工程专业论文）基于bittorrent的文件分发策略关键技术研究.pdf

i ) ：ji 。，i ， 1 峄 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 曲墓墨 日期： 如解歹月】1 日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：2 0 1 p 年岁月2 1 日 ， ， j 摘要 摘要 目前p 2 p 技术在多个领域中取得了广泛的应用，b i t t o r r c n t 是典型的基于p 2 p 技术的文件分发系统，拥有广泛的用户群。本文以改善b i t t o r r e n t 的分发性能，提 高系统文件下载时间，加快文件分发时间为研究目的，其主要创新如下： ( 1 ) 提出了基于t r a c k e r 算法优化的节点选择策略。该策略中，t r a c k e r 服务器 在统计在线节点时，对在线节点的上传速率、下载速率、节点状态作了分类并排 序，当有节点请求邻居节点时，t r a c k e r 根据节点在网络中所处的下载时期这个特 征，从排序的上传速率、下载速率链表里选取部分节点作为请求节点的邻居节点。 ( 2 ) 提出了基于空闲带宽的内容分发策略。本文在分析新入网节点、即将下载 完成的节点的工作原理的基础上，指出新入网节点下载前期存在着空闲的下载带 宽，而处于下载后期阶段的节点存在着空闲的上传带宽。针对这个问题，基于空 闲带宽的内容分发策略对其做了优化：当检测到节点处于这两种状态时，分别通 过自适应增加其下载带宽、上传带宽，来有效整合其闲置资源，以提高系统资源 利用率，并在整体性能上节省了文件分发时间。 ( 3 ) 提出了基于稀有分片的内容分发策略。在阐述文件分片均匀分布重要性 时，本文提出了通过种子节点来调节文件分片分布。基于稀有分片的内容分发策 略在此思想的基础上，对种子节点的工作机制做了优化：种子节点统计周围邻居 节点各自拥有的文件分片，计算出稀有分片，优先把网络中稀有分片分发给新入 网节点，以平衡稀有分片的数目。该策略与基于t r a c k e r 算法优化的节点选择策略 相辅相成。 此三种策略的相互协作，极大地加快了b i t t o r r e n t 分发文件的效率，使得在相 同规模的网络环境下，b i t t o r r c n t 能更快的分发相同大小的文件。这种文件分发效 率的提高，具有很强的现实背景和应用价值。之后，本文介绍了基于分布式对等 网络仿真平台的策略仿真设计，并经仿真测试证实了优化策略的预期效果。 关键字：b i t t o r r e n t ，节点选择，空闲带宽，稀有分片 1 1 j p a b s t r a c t a b s t r a c t p e e r - t o - p e e r ( p 2 p ) t e c h n o l o g yh a sa c h i e v e daw i d er a n g eo fa p p l i c a t i o n s a so n e o ft h ep 2 pf i l ed i s t r i b u t i o ns y s t e m ，b i t t o r r e n th a sb e c o m et h eh o t s p o to fp 2 p s t u d v t h i s t h e s i sa i m e da t d e c r e a s i n g f i l ed o w n l o a dt i m ei n o r d e rt oi m p r o v eb i t t o r r e n t d i s t r i b u t i o np e r f o r m a n c e t h em a i nr e s e a r c ho ft h j st h e s i si sa sf o l l o w s ： f i r s t l y , a no p t i m i z e dn o d es e l e c t i o ns t r a t e g yw a sp r o p o s e dt oo v e r c o m et h e d r a w b a c k so fr a n d o mn o d es e l e c t i o ni nb i t t o r r e n ts y s t e m s ：t r a c k e rs e r v e rc l a s s i f i e d o n l i n en o d e su s e f u li n f o r m a t i o n ，w h i c hi n c l u d e dt h eu p l o a d ，d o w n l o a d ，a n dn o d es t a t e w h e nt h e r ew a sn o d er e q u e s t i n gn e i g h b o rl i s t ，t r a c k e rs e l e c t e dt h en e i g h b o rn o d e sb v t h er e q u e s tn o d e sp e r i o dp a r t i a l l yf r o mt h es t a t i s t i c a lr e s u l t s ，p a r t i a l l yf r o mt h er a n d o m r e s u l t s i tw a sw o r t hn o t i n gt h es e e dn o d e s ，w h i c hw i l lw o r ko nt h eo p t i m i z e ds t r a t e g v i n t r o d u c e dl a t e r , i fi tw a sc o n t a i n e di nt h er e t u r n e dn e i g h b o rn o d e s s e c o n d l y , t h i st h e s i sp o i n t e do u tt h a tt h e r ee x i s t e du n o c c u p i e db a n d w i d t h ，w h i c h w a sd o w n l o a db a n d w i d t ha tt h en o d e si n i t i a ls t a g e ，w h i l eu p l o a db a n d w i d t ha tt h el a s t s t a g eo fn o d e , s i nr e s p o n s et ot h i s ，a no p t i m i z e dc o n t e n td i s t r i b u t i o ns t r a t e g yw a s p r o p o s e d ：x g v h e nn o d ew a sa tt h ei n i t i a lo rl a s ts t a g e ，i tw i l la d a p t i v e l yi n c r e a s ei t s u n o c c u p i e db a n d w i d t hi no r d e rt oe f f e c t i v e l yi n t e g r a t et h ei d l er e s o u r c e sa n di m p r o v e t h es y s t e mp e r f o r m a n c e t h i r d l y , a c c o r d i n gt os e e dc h a r a c t e r , t h i st h e s i sp r o p o s e dt h a tt h es e e dn o d ec a n r e g u l a t et h ep i e c ed i s t r i b u t i o n t oa v o i dt h en e g a t i v ee f f e c t so fr a r ep i e c e ，t h es e e d n o d e 。o p e r a t i n gm e c h a n i s mw a so p t i m i z e d ：s e e dn o d ew i l ls t a t p i e c e sa m o u n tw h i c h w e r eo w n e db yn e i g h b o rn o d e s ，t h e nc a l c u l a t et h er a r ep i e c e s ，s oi tc a nb a l a n c et h e a m o u n to fr a r ep i e c e sb yg i v i n gp r i o r i t yt ot h en o d e sw h i c h r e q u e s t st h er a r ep i e c e s b a s e do nd i s t r i b u t e ds i m u l a t i o np l a t f o r m ，t h i st h e s i sd e s i g n e da n di m p l e m e n t e d t h e s e o p t i m i z e ds t r a t e g i e s s i m u l a t i o nr e s u l t sd e m o n s t r a t e dt h a to p t i m a l s t r a t e g i e s a c h i e v e db e t t e rd i s t r i b u t e de f f i c i e n c yw h i l er e t a i n i n gt h ea m h i t e c t u r eo fb i t t o r r e n t k e y w o r d s ：b i t t o r r e n t ，n o d es e l e c t i o n ，u n o c c u p i e db a n d w i d t h ，r a r ep i e c e i i 1一 t t 目录 目录 第一章 引言1 1 1 研究背景1 1 1 1 p 2 p 技术1 1 1 2 p 2 p 文件分发系统。2 1 2 研究目的与意义3 1 - 3 论文主要贡献4 1 4 论文组织结构。5 第二章b i t t o r r e n t 文件分发系统。6 2 1 b i t t o r r e n t 系统简介6 2 1 1b it t o r r e n t 分片机制7 2 1 2 b i t t o r r e n t 阻塞算法8 2 1 3 t r a c k e r 算法9 2 2b i t t o r r e n t 扩展协议9 2 2 1m u l t i t r a c k e r 9 2 2 2m e r k l e h a s ht r e e 。lo 2 2 3u d pt r a c k e re x t e n s i o n 1 0 2 2 4s u p e rs e e d i n g 。l o 2 2 5f a s ta ll o w e d 11 2 2 6d i s t r i b u t e dh a s ht a b l e 1 2 2 3 小结。13 第三章基于t r a c k e r 算法优化的节点选择策略研究1 4 3 1 引言14 3 2 问题定义1 4 3 2 1 t r a c k e r 算法问题描述1 4 3 2 2 阻塞算法问题描述15 3 3 算法思想1 6 3 3 1 在线节点统计策略1 6 3 3 2 邻居节点选择策略l7 i i i 目录 3 4 算法设计2 2 3 4 1 统计在线节点2 2 3 4 2选择邻居节点2 3 3 5 算法优缺点分析j 2 6 3 6 小结2 6 第四章基于节点状态的内容分发策略研究2 7 4 1 引言。2 7 4 2 基于空闲带宽的内容分发策略研究2 7 4 2 1问题定义2 7 4 2 1 1文件下载初期问题描述2 7 4 2 1 2 下载最后阶段问题描述2 8 4 2 2 算法思想2 9 4 2 2 1 基于空闲下载带宽的策略2 9 4 2 2 2 基于空闲上传带宽的策略3 0 4 2 3 算法设计3 3 4 2 3 1基于空闲下载带宽的算法设计3 3 4 2 3 2 基于空闲上传带宽的算法设计3 4 4 3 基于稀有分片的内容分发策略研究3 5 4 3 1问题描述3 5 4 3 1 1文件分片的均匀性分布3 5 4 3 1 2 种子节点3 6 4 3 1 3问题的引入3 7 4 3 2 算法思想3 8 4 3 2 1 基于稀有分片的策略3 8 4 3 2 2 基于新入网节点的策略3 9 4 3 3 算法设计4 2 4 4 算法优缺点分析4 2 4 5 刀、结4 3 第五章策略仿真与测试4 4 5 1 仿真平台4 4 5 2 仿真数据结构4 7 5 3 仿真设计5 3 v i 1 k 、 目录 5 3 1 请求邻居列表5 3 5 3 2 请求文件分片5 4 5 3 3 响应下载请求5 5 5 3 4 接收文件分片5 6 5 3 5 关闭节点处理5 7 5 3 6 接收消息处理5 8 5 4 仿真效果图6 0 5 5 仿真测试6 1 5 5 1测试环境6 1 5 5 2 测试参数设置6 2 5 5 3 测试结果与分析6 3 5 5 3 1 不同时刻，下载完成的节点数6 3 5 5 3 2 下载第一、最后一片的平均时间6 4 5 5 3 3 正常运行时，文件分片分布6 4 5 6 小结。6 5 第六章结论6 7 6 1 本文工作总结6 7 6 2 下一步研究方向6 8 j 2 | 谢7 0 参考文献。7 1 攻硕期间取得的研究成果7 4 科研工作7 4 科研成果7 4 v 1 v k u 第一章引言 1 1 研究背景 1 1 1p 2 p 技术 第一章引言帚一早ji 舀 近年来，对等网络( p e e r - t o p e e r ，简称p 2 p ) 计算迅速成为i t 界关注的焦点， 并被看作影响i n t e r n e t 未来的重要科技之一。目前p 2 p 技术在文件分发、流媒体传 输、实时通讯、协同工作、分布式计算、分布式数据存取等多个领域中取得了广 泛的应用。下面将重点介绍几种相当比较成熟的应用技术。 ( 1 ) 文件分发 文件分发是p 2 p 应用的重点和主流，可以说文件分发的需求直接引发了p 2 p 技术的产生。传统的c s 模式下，两个网络用户要实现文件交换需要服务器的参 与，典型应用如f t p 。当网络节点数目大量增多时，服务器的负载也随之增加， 使得文件传送缓慢甚至无法传送。在p 2 p 文件分发系统中，由于具体的文件传输 仅存在于交互的两两客户端节点间，有效地解决了服务器的瓶颈问题，并且具有 较高的扩展性和良好的容错性。常见的p 2 p 文件分发系统有b i t t o r r e n t 、e m u l e l l 】 等。 ( 2 ) 流媒体传输 流媒体文件传输的特点是传输量大且传输速率稳定。p 2 p 技术适应了适应了流 媒体传输对网络带宽的需求，因为所需要的大量带宽被所有共享多媒体文件的用 户分担，用户间提供数据流量。目前的p 2 p 流媒体应用相当广泛，如p e e r c a s t 2 1 、 a n y s e e 【3 1 、p p l i v e 4 蝽。 ( 3 ) 分布式数据存取 p 2 p 的分布式数据存取系统本身包含文件共享的功能，但其目的与文件共享不 同，更多的是研究海量的数据存储，以数据的可用性、持久性、安全性为目标， 为确保数据的可用性和持久性，往往采用分片、复制、缓存等方法。典型的p 2 p 分布式数据存取系统如o c e a n s t o r e 5 1 、q a n 州6 1 、p a s t 7 等。 ( 4 ) 分布式计算 p 2 p 的分布式计算将巨大的计算任务分解，交给许多台计算机分别执行，然后 电子科技大学硕士学位论文 再将它们计算的结果进行归纳和整合，从而开发每个网络节点的潜力。这种技术 利用众多计算机的空闲c p u 计算能力，使用积累的能力执行超级计算机任务。它 同样适用于任何需要大量数据处理的行业，如天气预报、动画制作、基因组研究 世 1 丁o p 2 p 技术不仅在产业界( m i c r o s o f t 、i b m 、i n t e l 、s u n 、h p 等) 发展迅速，而 且在学术界也同样受到高度关注。近几年，在i p t p s ，i e e ep 2 p , s i g c o m m ，i n f o c o m 和i p d p s 等并行结构和分布式计算方向的国际顶级学术会 议上出现了众多关于p 2 p 技术的重要研究成果。并目学术界举办了针对p 2 p 技术 的学术会议i p t p s ，这是p 2 p 领域最高级的专业国际会议。i p t p s 上发表的许多论 文，都成为p 2 p 领域的指导性文章，引领着p 2 p 领域的研究方向。 1 1 2p 2 p 文件分发系统 文件分发是p 2 p 技术最广泛的一个应用。p 2 p 文件分发系统的特点是充分利 用网络带宽，开发每个网络节点的潜力，使得节点在下载文件的同时也提供上传 文件服务，较好地提高了网络工作效率，具有较高的扩展性和良好的容错性。下 面将从其发展过程来详细分析各分发系统的特点。 n a p s t e r 系统是最早出现的文件分发系统，整个系统由目录服务器和各个客户 端构成。目录服务器由一个或一组高性能的服务器承担，主要负责所有活动客户 端共享资源的管理，并提供资源查询服务。客户端安装在个人计算机上，可以动 态地加入和离开网络。这种中心化的拓扑不可避免地两个问题就是可扩展性和单 点失效。 c m u t e l l a 8 】是无结构的p 2 p 网络。在g n u t e l l a 网络中，每个节点既是服务器又 是客户端。当一个节点需要查询消息时，会采用泛洪式的查询方式，即先把查询 消息发送到自己的直接邻居节点。邻居节点首先查找自己的数据列表，如果发现 要查询的数据，就回送一条确认信息，否则就把这条信息转发给自己的直接邻居。 在转发过程中，节点会检查并修改消息头的t r l 字段和h o p s 字段，如果发现消 息的t t l 为o ，直接丢弃该消息。这种查询方式带来的最大问题就是网络流量的 几何式增长，而且查询的命中率也不高。 b i t t o r r e 目a t 是以分散化的服务器为核心提供文件分发的p 2 p 网络，它提供文件 分片、多源下载，同时限制用户在下载的同时必须上传。而网络和用户信息的更 新，尤其是b i t t o r r e n t 种子的维护，是依靠服务器中的t r a c k e r 来完成的，下载同 2 第一章引言 一文件的用户围绕t r a c k e r 形成一个独立的子网。b i t t o l t c n t 的协议也是公开的， 任何人都可以开发服务器和客户端。国内比较流行的一个客户端是b i t c o m c t 。 c d o n k e y 将网络节点组织成两层：服务器层和客户层。e d o n k c y 将文件分块， 分块又分成片段，片段进一步分成小块，从而提供多源下载机制和更细粒度的数 据完整性检查。o v c m c t 是c d o n k c y 所使用的分布式搜索网络，它本身是一个独立 的应用，但e d o n k c y 将它整合到自己的体系中。 c m u l c 是e d o n k e y 的改良版，而且是开源软件。e m u l c 采用了和c d o n k c y 相同 的网络协议，能直接登陆e d o n k c y 服务器，加入e d o n k c y 网络。但它也提供了 c d o n k c y 不具备的功能，比如自动搜索网络中的服务器、缓存搜索结果、和其他节 点交换服务器地址、首先下载文件头尾供用户预览、利用k a d e m l i a 算法来实现节 点间的发现和消息路由等。由于服务器分布在整个网络，c m u l e 是半中心化拓扑， 从一定程度减少了单点失效的概率。 m a z e 9 是北京大学网络实验室开发的一个混合式p 2 p 个人信息中心文件系统。 从结构上看，m a z e 具有和n a p s t c r 类似的结构，每个用户都把自己的共享数据交 到目录服务器上，但m a z e 充分利用了这种集中控制的优点，把整个系统的运营信 息收集起来，可以供其他方面的研究，如社会学、网络资源分布等。目前基于m a z e 开展了很多研究，如网格计算、网络观测平台及数据挖掘等。 1 2 研究目的与意义 b i t t o r r c n t 是实际部署最成功的大规模p 2 p 文件分发系统之一，已经发展成为 一种主要的p 2 p 应用，并逐渐改变着互联网的使用。就共享文件下载而言， b i t t o r r e n t 可以消除服务器瓶颈，同样的网络资源可以支持更多用户的文件下载业 务。近年来，b i t t o r r c n t 文件分发系统已经成为学术界研究的焦点，不断有新的研 究成果出现，然而对于b i t t o r r c n t 系统的研究还需进一步的完善。在此背景下，本 文选择b i t t o n e n t 文件分发系统作为研究方向。 现在的b i t t o r r c t l t 系统过于注重节点间协作的公平性，公平性是双方通信的原 则，对方给自己上传的数据多，那么自己也相应的优先给对方上传；若对方很少 甚至从不给自己上传数据，那么自己也采取措施减少甚或停止给对方提供上传。 该策略虽然兼顾到双方利益，实现了公平通信，但是忽略了快速性、高效性对文 件分发系统的重要性。 基于上述原因，本文以改善b i t t o r r c n t 的分发性能，提高系统文件下载时间， 3 电子科技大学硕士学位论文 加快文件分发时间为研究目的，使得在相同规模的网络环境下，系统能更快的分 发相同大小的文件。这种文件分发效率的提高，具有很强的现实背景和应用价值。 这种结合了p 2 p 技术和快速分发性能的b i t t o r r e n t 系统可以加快游戏软件及游 戏补丁的快速下载及分发。随着网络游戏的发展，游戏目录越做越大，更新也越 来越频繁，再加上游戏更新时的集中性，在短时间内要把更新文件推到用户的机 器上以确保用户能正常玩。运营商要确保更新文件能够及时的更新到用户机器中 就要加大对带宽的投入，而高昂的c d n 费用，增加了网络游戏发布和更新的成本。 由于游戏更新时的集中性大部分用户会同时访问服务器获取数据，使得当某些服 务器出故障时，很大数量的用户的下载或者更新无法进行。而结合了p 2 p 技术和 快速分发性能的b i t t o r r e n t 系统无疑给此问题提供了更好的解决方案。 1 3 论文主要贡献 本文通过对现有p 2 p 技术及b i t t o r r e n t 文件分发系统相关研究工作的深入研究 和比较分析，开展了一系列理论研究和应用开发工作，主要包括： ( 1 ) 提出了基于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 会返回部分不同速率的种子节点，而此时，种子节点的工作机制是采取以 下所述的基于稀有分片的内容分发策略。 ( 2 ) 提出了基于空闲带宽的内容分发策略。针对新入网节点、即将下载完成的 节点各自分别存在着空闲的下载带宽、上传带宽这个问题，基于空闲带宽的内容 分发策略对其做了优化：当检测到节点处于这两种状态时，分别通过自适应增加 其下载带宽、上传带宽，来有效整合其闲置资源，以提高系统资源利用率，并在 整体性能上节省了文件分发时间。 ( 3 ) 提出了基于稀有分片的内容分发策略。基于稀有分片的内容分发策略主要 通过种子节点来调节文件分片分布：种子节点统计周围邻居节点各自拥有的文件 分片，计算出稀有分片，优先把网络中稀有分片分发给新入网节点，以平衡稀有 分片的数目。该策略与基于t r a c k e r 算法优化的节点选择策略相辅相成。 4 第一章引言 ( 4 ) 最后，本文介绍了基于分布式对等网络仿真平台的策略仿真设计，并给出 了策略仿真所涉及的主要数据结构和部分关键技术。仿真中，仿真测试主要考察 三个方面的性能指标：不同时刻，下载完成的节点数；第一片、最后一片下载完 成的平均时间；在正常运行时，网络中的文件分片分布状况。测试结果证实了优 化策略的预期效果。 1 4 论文组织结构 论文一共分为六章。 第一章，引言。在介绍p 2 p 技术的基础上，对p 2 p 文件分发系统作了分类和 概括，选取多项具有代表性的现有研究成果作了原理剖析，分析并总结了其各自 的优缺点。 第二章，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 文件分发系统的基本理论和关键算法，并对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 算法优化的节点选择策略的 详细工作流程图。 第四章，基于节点状态的内容分发策略研究。按照节点在下载过程中所处的 不同时期，将节点状态分为新加入网络的节点、处于下载后期的节点、下载完成 的种子节点、下载与上传二者并存的正常节点。由于正常节点的工作机制已相对 成熟和完善，本章主要是研究前三种节点状态的内容分发策略。针对前两种状态 的节点，提出了基于空闲带宽的内容分发策略。针对种子节点的特殊性，提出了 基于稀有分片的内容分发策略。 第五章，策略仿真与测试。本章介绍了基于分布式对等网络仿真平台的策略 仿真设计，并给出了策略仿真所涉及的主要数据结构和部分关键技术。在仿真测 试部分，主要考察三个方面的性能指标：不同时刻，下载完成的节点数；第一片、 最后一片下载完成的平均时间；正常运行时，网络中的文件分片分布状况。 第六章，结论。对本文的工作进行总结，并对下一步研究进行展望。 5 电子科技大学硕士学位论文 第二章b it t o rr e n t 文件分发系统 b i t t o r r e n t 是典型的基于p 2 p 技术的文件分发系统，拥有广泛的用户群。据研 究显示【l o 】【l l 】，b i t t o r r e n t 占p 2 p 流量的5 3 ，增加了i s 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 细节。 2 11 3 i t t o r r e n t 系统简介 b i t t o r r e n t 系统【1 2 】【1 3 】由四个部分组成：b i t t o r r e n 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 用户。 b i t t o r r e n t 网站是一系列提供t o r r e n t 文件搜索的服务器，从一个b i t t o r r e n 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 网站进行搜索。 t o r r e n t 文件服务器保存t o r r e n 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 网络中，一个文件的共享开始于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 网络和用户信息的维护者，其职责是帮助用户相互发现 对方，下载同一文件的所有用户围绕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 r a c k e r 和用户间 基于h 1 r r r p 的协议进行交互。用户告诉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 用户可以同时下载多个文件。对于每一个文件而言，用户通常 按照下述步骤下载： 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 网站将该搜索请 求重定向到它的某个网站镜像，检索它所知的所有t o r r e n t 文件服务器，返回给用 6 第二章b i t t o r r e n t 文件分发系统 户关于该文件的t o r r e n t 文件。用户根据t o r r e n t 文件信息连接到相应的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 r a c k e r 获得新的用户信息建立新的连接。 2 1 1b i t t o r r e n t 分片机制 b i t t o r r e n t 将文件分割为固定大小的分片，典型的大小是2 5 6 k b ，每个用户必 须通知其他下载者自己拥有的分片数。为了验证数据完整性，对每个分片都通过 s h a 1 散列函数计算出它的散列值保存在t o r r e n t 文件中，用户只有在检查了分片 的完整性后，才通知其他用户它拥有这个分片。 b i t t o r r e n t 协议【1 4 】将每个片段又进一步分为子片段，每个子片段的大小一般是 1 6 k 。同时，它一直保持几个请求被同时发送，使得大多数连接变得饱和以充分利 用带宽。 选择一个好的顺序来下载分片对提高性能非常重要【l s 】【1 6 】。差的分片选择算法 不仅低效，而且使用户间相互等待以致浪费了彼此的带宽资源。在不同的阶段， b i t t o r r e n t 的分片选择策略有所不同： ( 1 ) 严格的优先级 严格的优先级，发生在下载一个分片时期。一旦请求了某个分片的子分片， 那么该分片剩下的所有子分片优先于其他分片的子分片被请求，这样可以尽可能 的获得一个完整的分片。 ( 2 ) 最少优先 该策略发生在文件下载中间阶段的平稳期。对一个下载者来说，在选择下一 个要下载的分片时，通常选择的是它所知用户拥有数最少的那个分片，这种策略 确保了每个下载者都拥有与它连接的用户们最希望得到的那些分片，同时也确保 了普通的分片放在最后下载。 ( 3 ) 随机的第一个片段 该策略发生在文件下载的最初阶段。最少优先策略的一个例外是节点在下载 起初的时候，此时下载者没有任何分片可供上传，所以需要尽快获取一个完整的 分片。但此时最少的分片通常只被某特定用户拥有，所以，下载此分片要比其他 分片慢得多。因此，第一个分片应是随机选择的，直到第一个分片下载完成，才 7 电子科技大学硕士学位论文 切换到最少优先策略。 h ) 最后阶段模式 该策略发生在文件下载的最后阶段。有时候，可能会从一个速率很慢的用户 那里请求一个分片，在下载的中间阶段这没有多大问题，但是在下载的最后阶段 它却可能潜在的延迟下载的完成。为了避免这种情况，在最后阶段，下载者向它 所连接的所有用户都发送某分片的子分片请求，一旦某个子分片到了，下载者就 会向其它用户发送c a n c e l 消息，取消对那些子分片的请求，以避免带宽浪费。 2 1 2bit t o rr e n t 阻塞算法 阻塞算法对提高b i t t o r r e n t 性能是非常必要的，一个好的阻塞算法应该利用所 有可用的资源，为所有下载者提供一致、可靠的下载速率，并适当惩罚那些只下 载而不上传的自私用户。 ( 1 ) c h o k i n ga l g o r i t h m 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 0 秒做一次轮询，每隔1 0 秒计算一次哪 个用户要被阻塞，然后将阻塞状态保持到下一个1 0 秒。时间间隔取1 0 秒是因为 这已经足够t c p 来进行调整以使传输率达到最大。 ( 2 ) o p t i m i s t i cu n c h o k i n g 如果只是简单地为那些向自己提供最高的下载速率的用户提供上传，那么就 没有办法来发现那些空闲的连接是否比当前正使用的连接更好。为了解决这个问 题，在任何时候，每个用户都拥有一个称为o p t i m i s t i cu n c h o k i n g 的连接，不管它 的下载速率怎样。每隔3 0 秒，用户重新计算一次哪个连接应该是o p t i m i s t i c u n c h o k i n g 。3 0 秒足以让上传能力达到最大，下载能力也相应达到最大。 ( 3 ) a n t i s n u b b i n g 某些情况下，一个下载者可能被它所连接的所有用户都阻塞了，此时它将保 8 第二章b it t o r r e n t 文件分发系统 持较低的下载速率，直到通过o p t i m i s t i cu n c h o k i n g 找到更好的用户来连接。为了 缓解这个问题，如果一段时间后，从某个用户那里一个分片也没有得到，那么下 载者不再为对方提供上传。 一旦某个用户完成了下载，它就不可能再通过下载速率来决定为哪些用户提 供上传。此时，它会优先选择那些能从它这里得到更高上传速率的用户，或者选 择那些此刻刚好被阻塞的用户，以尽可能地利用上传带宽。 2 1 3t r a c k e r 算法 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 算法返回邻居节点信息，请求节点与邻居节点建立通信联系后， 然后节点间按照b i t