子分片流水作业.ppt

P2P网络体系 大纲 第一代P2P网络：混合式P2P体系（＊） 第二代P2P网络：无结构P2P体系（＊） 第三代P2P网络：结构化P2P体系 本讲需要大家关注的是： （1）P2P思想是如何应用到文件共享领域？ （2）无结构的网络如何在节点随意加入和退出的情况下实现自组织？ （3）多源下载技术的实现思想以及技术方法 （4）Freenet的匿名技术?? 第一代P2P网络：混合式P2P体系 Napster BitTorrent Napster:P2P网络的先驱 世界上第一个应用性P2P网络，混合式P2P体系最杰出的代表 1999年波士顿东北大学的Shawn Fanning开发Napster，用于MP3文件交流，与传统的提供音乐下载的网站不同，Napster服务器里无歌曲，仅有其它用户硬盘上的文件的索引 Napster使用的软件技术都是当时已有的，只是改变了软件的应用体系，打破了客户/服务器模式的瓶颈 Napster半年吸引了5000万注册用户，最高时超过6100万用户 Napster网络的工作原理 服务器： 维护所有Napster用户的共享文件索引 监控系统中每个用户的状态(连接带宽、连接时间、在线状态) Napster性能分析 节点异构 Bandwidth, online time Free Riding 20-40%用户几乎从来不提供文件共享而只是下载；大约1%的结点支撑Napster文件共享 Napster的缺陷 C/S的残余：文件交换使用P2P，但文件查询、系统维护靠server，带来系统瓶颈、服务器单点失效、可扩展性低等问题 组织管理过于松散，仅赋予用户平等的功能，无义务要求、能力区分 版权问题：导致Napster发布后当年即被起诉，两年后关闭服务，是P2P文件共享系统迄今为止最大的困境 BitTorrent-分片优化的新一代混合式P2P网络 Napster进一步发展，BitTorrent： 相同架构，但文件分片，使用散列函数映射 用户有上传义务 网络及用户信息更新、BT种子维护由server中的Tracker完成，下载同一文件的用户围绕Tracker形成独立子网，不同文件的Tracker在不同server上，将server分散化，成为P2P在国内最成功的应用 BitTorrent体系原理 Overview – system components Overview – system components Overview – system components Overview – system components Overview – system components Overview – system components Overview – system components BitTorrent分片机制 BT将文件分为固定大小的分片(典型大小256KB)，每个用户必须通知其他下载者自己拥有的分片，分片的完整性由散列函数保证 分片流水作业：构架在TCP之上的应用层协议，同时发送多个请求，以避免在两个分片发送之间的延迟，进一步，分片可以划分为子分片(典型16KB)，BT一直保持几个请求（通常是5个）被流水式地同时发送。流水作业选择同时发送的请求数目的依据，是使大多数连接变得饱和以充分利用带宽 BitTorrent分片选择策略 严格的优先级（一个分片的下载） 一旦请求了某个分片的子分片，那么该分片的所有子分片具有更高优先级，以尽可能快地获得一个完整的分片 最少者优先（中间阶段/平稳期） 尽量选择所知用户拥有数最少的分片作为下一个下载分片，以使网络中最稀少的分片尽快拥有多个复制 下载者从Tracker了解哪些分片较少 随机的第一个片段（文件下载最初阶段） 当最少的分片只有一个用户拥有时，为避免并发冲突，第一个分片先随机选择，完成下载后再切换到“最少者优先”策略 最后阶段模式（文件下载最后阶段） 为加速最后阶段下载，下载者向他所连接的所有用户都发送某分片的子分片请求，一旦某个子分片到了，下载者就会向其他用户发送cancel消息，以避免浪费带宽 BitTorrent阻塞算法 BT并不是由Tracker服务器集中分配资源，每个用户自己有责任尽可能地提高自己的下载速率 下载者根据连接用户提供的下载速率给予同等的上传回报(tit-for-tat)；对合作者提供上传服务，对不合作者进行临时阻塞 一个好的阻塞算法应该利用所有可用的资源，为所有下载者提供一致、可靠的下载速率，并适当惩罚只下载而不上传的用户 阻塞算法的经济学背景——帕累托有效 当一个系统中资源配置已达到这样一种境地：任何重新改变资源配置的方式，都不可能使一部分人在没有其他人受损的情况下受益，这一资源配置的状态称为“帕累托最优”状态，或称为“