兰州商学院毕业论文-P2P文件传输的实现

兰兰 州州 商商 学学 院院 本科生毕业论文 设计 本科生毕业论文 设计 论文 设计 题目 论文 设计 题目 P2PP2P 文件传输的实现文件传输的实现 学学 院 院 系 系 信息工程学院信息工程学院 计算机科学与技术系计算机科学与技术系 专专 业业 方方 向向 电子信息工程电子信息工程 年年 级 级 班 班 2007 级级 学学 生生 姓姓 名 名 白晨艳白晨艳 指指 导导 教教 师 师 曹晓军曹晓军 2011 年 5 月 30 日 声 明 本人郑重声明 所呈交的毕业论文 设计 是本人在导师的指导下取得的成果 对本论文 设计 的研究做出重要贡献的个人和集体 均已在文中以明确方式标明 因本毕业论文 设计 引起的法律结果完全由本人承担 本毕业论文 设计 成果归兰州商学院所有 特此声明 毕业论文 设计 作者签名 年 月 日 I P2P 文件传输的实现文件传输的实现 摘摘 要要 网络技术的快速发展方便了我们的日常生活 加快了工作效率 增进 了交流 网络的出现确实给我们带来了很多的便利 但是人们对文件传输 的效率仍有所期待 打破传统的 Client Server 模式 在对等网络中 每个 结点的地位都是相同的 具备客户端和服务器双重特性 可以同时作为服 务使用者和服务提供者 加快了传输效率 所以开发 P2P 文件传输系统是 一个很有实践性意义的课题 本设计资源搜索使用了超节点间的洪泛和聚簇内的基于 Chord 的分布 式哈希表相结合的算法 工具选择 C 实现从外网到内网进行的文件传 输 用到 NAT 穿透技术 关键词关键词 P2P Nat 文件传输文件传输 II ABSTRACT The rapid development of network technology to facilitate our daily life to speed up the work efficiency and enhanced communication The advent of the Internet really gives us a lot of convenience but the file transfer efficiency is expected to improved Break the traditional Client Server mode the status of each node are the same in the peer to peer network have the dual characteristics of the client and server can also service users and service providers to speed up the transmission efficiency So development the system of P2P file transfer is a great of practical sgnificance subject The design resources search using the flooding between supernode and the Chord based distributed hash algorithms combined appearances tools select C to achieve files transfer from outside the network to inside the network use NAT Hole Punching technology Key Words P2P Nat File transfer III 目目 录录 一 引言 1 二 P2P 分布式文件传输系统发展综述 1 一 什么是 P2P 1 二 P2P 的分类 2 三 P2P 的技术特点 4 四 P2P 的应用领域 5 1 对等计算 5 2 协同工作 6 3 搜索引擎 6 4 文件交换 7 三 P2P 传输系统中算法的研究与分析 7 一 资源的定位与搜索算法的分析 7 1 Chord 算法 7 2 CAN 算法 9 3 Tapestry 算法 11 4 Pastry 算法 12 二 几种算法的比较 12 三 基于超节点改进的 Chord 方法 13 四 洪泛与 Chord 的结合 14 四 基于 P2P 的传输系统的设计与实现 16 一 P2P 传输系统的框架设计 16 二 P2P 传输系统的界面设计 17 1 搜索模块 17 2 文件下载控制模块 19 3 文件下载显示模块 20 三 P2P 传输系统的网络结构设计 21 1 超节点的选取 21 2 节点的管理 22 五 P2P 传输系统中关键技术的研究与实现 23 一 超节点的选择 23 二 节点间通信连接的建立 25 三 节点间文件传输的实现 28 1 断点续传 28 2 多线程下载 29 六 总结 29 参考文献 31 致谢 32 1 P2P 文件传输的实现文件传输的实现 一 引言一 引言 P2P 打破了 C S 的僵局 将 PC 机的潜力充分挖掘出来了 给出了一 种更灵活 更接近互联网本质的信息组织 共享方案 P2P 技术是充满活 力的 P2P 技术创造了一种全新的商业模式 它打破了传统的 C S 模式 对等网络中每个节点的地位都是平等的 每个节点既充当服务器 为其他 节点提供服务 同时也享用其他节点提供的服务 传统的 C S 模式控制了信息流动 使服务器端充斥了过时信息 阻 碍了真正的交流 P2P 技术把控制权重新归还到用户手中去 人们通过 P2P 可以共享硬盘上的文件 目录甚至整个硬盘 所有人都共享了他们认 为最有价值的最新的东西 这将使互联网上信息的价值得到极大的提升 二 二 P2PP2P 分布式文件传输系统发展综述分布式文件传输系统发展综述 一 一 什么是什么是 P2P P2P 1 是 peer to peer 的缩写 peer 在英语里有 地位 能力等 同等 者 同事 和 伙伴 等意义 这样一来 P2P 也就可以理解为 伙伴对伙 伴 的意思 或称为对等联网 目前人们认为其在加强网络上人的交流 文件交换 分布计算等方面大有前途 简单的说 P2P 直接将人们联系起来 让人们通过互联网直接交互 如图 1 所示 6 P2P 使得网络上的沟通变得容易 更直接共享和交互 真 正地消除中间商 P2P 就是人可以直接连接到其他用户的计算机 交换文 件 而不是像过去那样连接到服务器去浏览与下载 P2P 另一个重要特点 2 是改变互联网现在的以大网站为中心的状态 重返 非中心化 并把权力 交还给用户 Peer Peer Peer Peer 图 P2P 模型 二 二 P2P 的分类的分类 P2P 模式的变化经历了集中式 分布式和混合式 3 个阶段 P2P 技术 起源于文件交换技术 在发展过程中 文件交换技术的演变最具代表性 下面介绍 P2P 模式的几种形式 1 集中式对等网络 1 如图 2 所示 集中式 P2P 模式由一个中心 服务器来负责记录共享信息以及反馈对这些信息的查询 每一个对等实体 要对它所需共享的信息以及进行的通信负责 根据需要下载它所需要的其 他对等实体上的信息 这种形式具有中心化的特点 但是它不同于传统意 义上的 Client Server 模式 因为传统意义上的 Client Server 模式采用的是 一种垄断的手段 所有资料都存放在服务器上 客户机只能被动的从服务 器上读取信息 并且客户机之间不具有交互能力 而集中式 P2P 模式则是 所有网上提供的资料都存放在提供资料的客户机上 服务器上只保留索引 信息 此外服务器与对等实体以及对等实体之间都具有交互能力 3 图 集中式对等网模型 2 分布式对等网络 1 如图 3 所示 在分布式 P2P 中 对等机通 过与相邻对等机之间的连接 遍历整个网络体系 每个对等机在功能上都 是相似的 并没有专门的服务器 而对等机必须依靠它们所在的分布网络 来查找文件和定位其他对等机 这种无中心 纯分布式系统不再是简单的 点到点通信 而是更高效 更复杂的网络通信 Servent Servent Servent Servent 图 3 分布式对等网模型 4 3 混合 P2P 网络 1 集中式 P2P 有利于网络资源的快速检索 并 且只要服务器能力足够强大就可以无限扩展 但是其中心化的模式易遭到 直接的攻击 分布式解决了抗攻击的问题 但是又缺乏快速搜索和可扩展 性 混合式 P2P 结合了集中式和分布式 P2P 优点 在设计思想和处理能力 上都进一步的优化 它在分布式模式的基础上 将用户节点能力进行分类 使某些节点担任特殊任务 三 三 P2P 的技术特点的技术特点 非中心化 Decentralization 网络中的资源和服务分散在所有结点上 信息的传输和服务的实现都直接在结点之间进行 可以无需中间环节和服 务器的介入 避免了可能的瓶颈 可扩展性 在 P2P 网络中 随着用户的加入 不仅服务的需求增加了 系统整体的资源和服务能力也在同步地扩充 始终能较容易地满足用户的 需要 整个体系是全分布的 不存在瓶颈 理论上其可扩展性几乎可以认 为是无限的 健壮性 P2P 架构天生具有耐攻击 高容错的优点 由于服务是分散 在各个结点之间进行的 部分结点或网络遭到破坏对其它部分的影响很小 P2P 网络一般在部分结点失效时能够自动调整整体拓扑 保持其它结点的 连通性 P2P 网络通常都是以自组织的方式建立起来的 并允许结点自由 地加入和离开 P2P 网络还能够根据网络带宽 结点数 负载等变化不断 地做自适应式的调整 高性价比 性能优势是 P2P 被广泛关注的一个重要原因 随着硬件技 术的发展 个人计算机的计算和存储能力及网络带宽等性能依照摩尔定理 5 高速增长 采用 P2P 架构可以有效地利用互联网中散布的大量普通结点 将计算任务或存储资料分布到所有结点上 利用其中闲置的计算能力或存 储空间 达到高性能计算和海量存储的目的 通过利用网络中的大量空闲 资源 可以用更低的成本提供更高的计算和存储能力 隐私保护 在 P2P 网络中 由于信息的传输分散在各节点之间进行 而无需经过某个集中环节 用户的隐私信息被窃听和泄漏的可能性大大缩 小 四 四 P2P 的应用领域的应用领域 P2P 引导网络计算模式从集中式向分布式偏移 也就是说网络应用的 核心从中央服务器向网络边缘的终端设备扩散 服务器到服务器 服务器 到 PC 机 PC 机到 PC 机 PC 机到 WAP 手机 所有网络节点上的设备都可 以建立 P2P 对话 这使人们在 Internet 上的共享行为被提到了一个更高的 层次 使人们以更主动深刻的方式参与到网络中去 P2P 给互联网的分布 共享精神带来了无限的遐想 从目前的应用来看 P2P 的威力还主要体现 在大范围的共享 搜索的优势上 主要有四大类型的应用 对等计算 协 同工作 搜索引擎 文件交换 1 对等计算 对等计算 采用 P2P 技术的对等计算 正是把网络中的众多计算机暂时不用的计 算能力连结起来 使用积累的能力执行超级计算机的任务 任何需要大量 数据处理的行业都可从对等计算中获利 如天气预报 动画制作 基因组 的研究等 有了对等计算之后 就不再需要昂贵的超级计算机了 Intel 也 6 剥用对等计算技术来设计其 CPU 并为其节省极大的费用 同时对等计算 的发展是以 PC 机资源的有效利用为根本出发点的 自然也极力受到 Intel 的极力推崇 从本质而言 对等计算就是网络上 CPU 资源的共享 2 协同工作 协同工作 公司机构的日益分散 给员工和客户提供轻松 方便的消息和协作的 工具 变得日益重要 网络的出现 使协同工作成为可能 但传统的 WEB 方式实现 给服务器带来了极大的负担 造成了昂贵的成本支出 P2P 技术的出现 使得互联网上任意两台 PC 机都可建立实时的联系 建 立了这样一个安全 共享的虚拟空间 人们可以进行各种各样的活动 这 些活动可以是同时进行 也可以交互进行 P2P 技术可以帮助企业和关键 客户 以及合作伙伴之间建立起一种安全的网上工作联系方式 3 搜索引擎 搜索引擎 P2P 技术的另一个优势是开发出强大的搜索工具 P2P 技术使用户能 够深度搜索文档 而且这种搜索无需通过 Web 服务器 也可以不受信息文 档格式和宿主设备的限制 可达到传统目录式搜索引擎 只能搜索到 20 30 的网络资源 无可比拟的深度 理论上将包括网络上的所有开放的信息 资源 以 P2P 技术发展的另一先锋 Gnutella 进行的搜索为例 一台 Pc 上 的 Gnutella 软件可将用户的搜索请求同时发给网络上另外 10 台 PC 如果搜 索请求未得到满足 这 lO 台 PC 中的每一台都会把该搜索请求转发给另外 10 台 PC 这样 搜索范围将在几秒钟内以几何级数增长 几分钟内就可 7 搜遍几百万台 PC 上的信息资源 可以说 P2P 为互联网的信息搜索提供 了全新的解决之道 4 文件交换 文件交换 可以说文件交换的需求直接引发了 P2P 技术热潮 在传统的 WEB 方 式中 要实现文件交换需要服务器的大力参与 通过将文件上传到某个特 定的网站 用户再到某个网站搜索需要的文件 然后下载 这种方式的不 便之处不言而喻 电子邮件是方便了个人间文件传递问题 却没法解决大 范围的交换 这也是 WEB 的重要缺陷 Napster 就是在这种情况下横空出 世 抓住人们对 MP3 喜欢的需求 Napster 的 MP3 交换直接引发了网络的 P2P 技术革命 三 三 P2PP2P 传输系统中算法的研究与分析传输系统中算法的研究与分析 一 一 资源的定位与搜索算法的分析资源的定位与搜索算法的分析 1 Chord 算法算法 Chord 7 16 是一个环形结构化 P2P 模型 给定一个关键字 Chord 可以 有效地把该关键字映射到网络中某个节点上 关键字和节点都分别拥有一 个 n 比特的标识符 K 和 N Chord 方法使用了一致性散列函数 SHA 1 通过哈希关键字和节点 IP 地址分别得到 K 和 N 这样 网络中的节点和 数据就被映射到一个空间为 2n 的圆环上 该环被称为 Chord 环 关键字 为 K 的文件连同拥有它的节点 IP 构成了结构 存储在节点标识等 于 K 的节点上 若等于 K 的节点不存在 则在 Chord 环的顺时针方向上 选择紧跟着 K 的节点存放 该节点称为 K 的后继节点 记为 successer K 8 如图 4 所示 图 4 Chord 环映射机制 在图中 n 4 因为 11 要 4 位二进制来表示 K 为 1 的关键字存储在 标识 N 为 l 的节点中 K 3 的关键字 因为标识为 3 的节点不存在 所以 放在节点 4上 记为 successor 3 4 同理 K 10 的关键字放在标识为 11 的节点上 当有新的节点进入或退出时 仍遵循上面的策略 比如 当节点标识 为 3 的节点加入时 存放在节点 4 上的关键字 K 3 就会转移到节点 3 中 当节点 4 退出时 存放在节点 4 上的关键字 K 3 就会转移到节点 6 中 在路由过程中 Chord 环上的每个节点只需要维护它在环上的后继节点的标 识和 IP 地址就可以完成简单的查询过程 但这种查询方式在网络规模很大 时会很慢 比如网络中有 n 个节点 查询的复杂度就为 o n 数量级 为了 提高查询效率 可以增加每个节点的路由表信息 将环中的所有节点以路 9 由表的形式存放在每个节点中 当收到查询命令时首先根据关键字标识符 判断大致在哪个节点上 然后将查询命令转发到这个节点上 这样以较小 的存储消耗为代价 提高了查询的效率 另外 双向路由策略也能提高查 询的效率 2 CAN 算法算法 CAN 是一种用于结构化对等网络 P2P 的分布式哈希 9 查找系统 可以 在 Internet 规模的大型对等网络上提供类似哈希表的功能 具有可扩展 容错和完全自组织等特点 和 Chord 一样 CAN 可以将整个系统看成一张 保存 K V 对的大哈希表 其中 K 为文件名通过哈希函数 SHA 1 计算 后所得到的关键字 V 为该文件所存在节点的 IP 地址 CAN 将整个大的 哈希表划分后存放到各个节点中 每个节点都保存邻居节点的信息 具有 较好的容错性 当某个邻居节点发生连接错误时 路由信息可以绕过此节 点 CAN 是基于虚拟的 d 维笛卡儿坐标空间实现其数据的组织和查找功能 的 它将整个坐标空间动态地分配给系统中的所有节点 每个节点都拥有 独立的互不相交的一块区域 如图 5 所示 在一个二维笛卡儿坐标空间上 存在 9 个节点 分别存放在不同的区域 CAN 中这样定义邻居节点 在 d 维坐标空间中 如果两个节点的坐标在 d 1 维上重叠而在另一维上相邻接 则称这两个节点是邻居关系 在图中可以看到节点 A 和 B 在 Y 维上重叠 但在 x 维上相邻 因此 A 和 B 是邻居节点 A 和 E 在 X 和 Y 维上都相邻 但没有在某一维上重叠 所以它们不是邻居节点 不难看出 对于 d 维的 坐标空间 每个节点有 2d 个邻居节点 如节点 E 有 B D F H 四个邻居 10 节点 图 5 二维 CAN 结构图 在 CAN 方法中通过哈希函数将文件名映射为文件名关键字 在笛卡 儿坐标空间中找到存放这个关键字的节点 找出对应的 IP 值的坐标空间 路由到该点中就能查到文件 从图中可以看到 CAN 中的路由实际上就是 穿过笛卡儿空间从源坐标到目的坐标的一条直线段路径 在 CAN 中 每 个节点都维护一张路由表 此表用来存放该节点所有邻居的 IP 地址和坐标 空间 在路由时节点将消息转发给坐标路由表中距目的坐标最近的节点 直到目的坐标 对于划分成 n 个同等大小的 d 维坐标空问 平均路由长度 为 d 4 n1 d 跳 从 CAN 的结构可以看到 因为坐标空间中两个节点 之间有多条不同路径 如果某个邻居失效 节点可以其它路径路由 若某 个节点的 2d 个邻居都失效 它可以通过扩展搜索来找到下一个消息转发 点 当有新节点加入时 系统必须为它分配相应的坐标空间 一般是将某 11 个现有节点的坐标空间分为两部分 将其中一部分分配给新的节点 当新 节点获得坐标空间后 从被分割的节点那里获取邻居信息 略加调整 包括 某个邻居的退出和被分割节点的加入 被分割的节点作出同样调整 同时 两个节点都需通知它们的邻居修改邻居表 同时 系统会定时作周期性更 新 以使每个节点都保有最新信息 当某个节点离开时 它需要将自己的坐标空间和文件名关键字存储信 息转交给某个邻居节点 如果该邻居节点的坐标空间可以合并该区并产生 单个有效的空间 如离开节点的空间是该节点分割的 那么任务就完成了 如果不行 就将该空间移交给空间最小的邻居节点 3 Tapestry 算法算法 Tapestry 算法 7 和上面提到的两种算法在资源定位上都一样 都是通 过哈希函数将文件名哈希为关键字标识符 将节点的 IP 哈希后得到节点标 识符 关键字标识符找到和自己匹配或最近的节点标识符后将文件名和拥 有该文件的节点 IP 保存在此节点中 但 Tapestry 在结构上和上述两种方法不同 它在运行时构造一棵分布 式的 n 元搜索树 网络中的每个节点代表搜索树的一个叶子节点 因为 Tapestry 的前缀路由方法使得 n 元搜索树的构造和节点的标识符密切相关 Tapestry 在路由时 当一条查找消息到达传递过程中的第 n 个节点时 该 节点和目的节点的共同前缀长度至少大于 n 为了进行转发 该节点将查 找邻居表的第 n l 级中和目的标识符下一数位相匹配的邻居节点 转发过 程将在每个节点中依次进行直到到达目的节点 这种方法可以保证路由至 12 多经过 logbN 个节点就可以到达目的节点 这里 N 是节点标识符名字空间 的大小 而 b 是标识符使用的基数 一般为 16 同样 由于每个节点的邻 居映射表的每个级别只需要保存 b 个表项 因此 邻居映射表的空间为 logbN 当新节点加入时 首先从网络系统中选取一个节点 获取它的路由表 将标识符与路由表中记录的节点标识符做字尾比对 在此路由表中找到与 其节点标识符最相近的节点 再利用这个节点的路由表信息做进一步字尾 对比 如此下去 直到找到与标识符最近的节点 并从中获取关键字离自 己更近一些的文件索引信息 4 PastryPastry 算法算法 Pastry 7 是微软研究院提出的可扩展的分布式对象定位和路由协议 它 同样是利用哈希函数将文件索引信息分散存放到系统中的各个节点中 在 结构上 它同 Chord 算法一样 是环形结构 它与 Chord 不同的地方在于 它的路由表更复杂 除了存储一些节点的标识符和 IP 地址以外 为了达到 快速搜寻的目的 Pastry 中每个节点都会包含三个部分 路由表 叶子节 点集和邻居节点集 其中路由表记录与本节点标识符前几个数字相同的节 点 这和 Tapestry 算法的路由表类似 叶子节点集记录与本节点标识符相邻 的节点 邻居节点集记录与本节点网络距离相近的节点 Pastry 在搜索资源时 当某一节点收到一条查询消息时 首先检查该 消息的关键字是否落在叶子节点集范围内 如果是 则直接把消息转发给 对应的节点 也就是叶子节点集中 NodeID 和关键字最接近的节点 如果 关键字没有落在叶子节点集范围内 节点就会把消息转发给路由表中的一 13 个节点 该节点的标识符和关键字的相同前缀至少要比当前节点的标识符 和关键字的相同前缀多一位 依次搜索下去 直到找到符合要求的目的节 点 二 几种算法的比较 二 几种算法的比较 前面列出了几种最常见的 DHT 算法 9 这四种方法系统开销小 路由 效率高 易于维护 拥有较好的扩展性 他们之间也存在着异同点 从资 源定位上来讲 几种算法都是一样 通过哈希函数算出文件的关键字和节 点的标识符 若关键字和某节点的标识符匹配或相近 则将文件名关键和 存放文件的节点 IP 存放在该节点中 系统所有文件的索引都分散存放在各 个节点中 几种算法的不同主要体现在路由策略上 Chord 的路由表记录环上的 节点指针 鉴于已经有一些对它改进的方法 在路由选择上有较强的灵活 CAN 将一个 d 维空间分块 每个节点占据其中一块 Tapestry 和 Pastry 都 是基于树状结构的 Pastry 的路由表中第 n 行记录的节点标识符和本节点 标识符的前 n 1 位相同 Tapestry 与之相反 是做字尾的比对 Tapestry 和 Pastry 的性能要优于前两者 从算法原理上来讲 Pastry 又略优于 Tapestry 但是从结构实现上来讲 Chord 是最简单的 它也不需要像 Tapestry 和 Pastry 花费那么多代价去建立路由表 维护路由表 正因为它 的简单 使得它使用起来也是最灵活的 可以根据需要优化路由策略 本 系统就以 Chord 方法为基础实现资源的定位和搜索 14 三 基于超节点改进的 三 基于超节点改进的 Chord 方法方法 10 前面提到将文件关键字和节点 m 地址以分布式哈希表的方法分散在各 个节点上 这样做确实提高了资源的搜索效率 但在实际的共享网络中 由于节点众多 所有节点都位于同一个 Chord 环中是不现实的 在此提出 了基于超节点的改进的 chord 方法 它有以下几方面的好处 1 超节点的引进大大降低了 Chord 环的复杂度 网络中的所有节 点不必再位于同一个 Chord 环中 可以根据区域将 Chord 环划分 每个区 域中选出超节点 管理着这个区域节点构成的 Chord 环 2 降低了节点内路由表的大小 在 Chord 结构中每个节点都维护 一部分路由表 共有 log2N 个项 N 为命名空间的大小 其中第 i 项存放着 距离该节点长度为 2i l 的节点的后继信息 当超节点引进划分了 Chord 环 后 实际上 N 变小了 每个节点维护的路由信息数也随之减少 在原 Chord 环结构中为了维护每个节点内的路由表信息 每个节点 如 A 周期性向它的后续节点 如 B 发送消息 后续节点也向它的前驱节点 发送回送消息 如果此时一个新的节点 C 加入到它们之间 节点 C 会通知 节点 B 它现在加入网络中 但节点 A 还不知道节点 C 的存在 下次节点 A 发送消息给节点 B 时 节点 B 将返回它的前驱节点 C 的信息 节点 A 存储节点 C 的信息 并把节点 C 做为自己后续节点 同时通知节点 C 自 己是节点 C 的前驱节点 如果节点退出 Chord 环 它必须分别向它的前后 续节点发送通知 以便更新路由表 但由于某种原因 节点还没有来及向 前后续节点通告就退出 Chord 环 是环发生断链 例如 结点 C 在节点 A 和节点 B 之间 节点 A 下次发送询问消息时 没有收到节点 C 的回复 15 节点可能尝试几次 如果到一定的时间还是没有收到节点 C 的回复 节点 A 就判断节点 C 退出 chord 环 但节点 A 不知道节点 B 是它的后续节点 从而产生断链 需要一个稳定的机制来处理这种事情的发生 超节点能很好的解决这一问题 在正常情况一下 每个节点都会定时 的向超结点发送信息确认是否仍保持连接 当某个节点断开连接后 超节 点先得到此消息 向聚簇内的普通节点广播此信息 普通节点收到信息后 修改路由表即可 四 洪泛与 四 洪泛与 Chord 的结合的结合 在搜索过程中 搜索的资源可能是另一个区域的节点所拥有的 这个 时候就需要超节点转发查询请求 聚簇内的节点分布是结构化的 可是超 节点的分布是非结构化的 在每个超结点中都维护着一张路由表 让载着 邻居超节点的网络地址信息 例如 超节点 A 中记载着 B 的地址信息 B 中记载着 A 和 C 的地址信息 C 中记载着 B 的地址信息 这种信息可以 通过超节点入网时广播获得 超节点在转发查询请求时查询自己的路由表 将信息转发到邻居超节点中 因为文件的查询可能获得多个查询结果 用 户也希望获得多个查询结果 这样可以从中任选一个信誉度高的 所以查 询信息的转发可以无休止的进行下去直到所有的超节点都收到为止 这种 方法被称为洪泛法 但是这样做存在两个问题 第一 如果加入的节点很多 这种查询信 息的无休止转发势必影响文件搜索的效率 第二 当一个超节点收到查询 请求并转发时 它可能还会将此信息转发给发送信息给它的那个节点 这 样造成了大量的冗余 占用网络带宽 导致网络风暴 16 针对第一个问题 可以对传统的洪泛做一些改进 加入 TTL 限制消 息存活的生命期 达到一定的值时该消息不再转发下去 这样做虽然有可 能导致文件信息检索的不完整 但提高了检索的效率 在系统中可以根据 查询结果自行修改 TTL 值 若用户在系统默认的 TTL 值情况下未能检索 到满意的文件下载信息 可以增加此值 但 TTL 值不能超过 255 针对第二个问题 可以在超节点加一个标识 当超节点 A 第一次接收 到查询请求时设该标识为 l 将请求转发给超节点 B 后 B 会将此消息再 次返还给 A A 是 B 的邻居节点 这时 A 对此请求的标识已设为 1 自动将 数据包丢弃不再转发下去 综上所述 本文中所提到的资源搜索算法使用了超节点间的洪泛和聚 簇内的基于 Chord 的分布式哈希表算法相结合的方法 大大提高了资源定 位的效率 四 基于四 基于 P2PP2P 的传输系统的设计与实现的传输系统的设计与实现 一 一 P2P 传输系统的框架设计传输系统的框架设计 2 P2P 文件共享系统从宏观上来讲 可以大致分为 4 个层次 应用层 通知层 网络传输层和物理层 如图 6 所示 17 P2P 文件传输系统 应用层 通知层 网络传输层 物理层 图 6 P2P 文件系统框架 应用层主要提供用户与系统交互的界面 通过应用层提供的文件服务 接口 用户享有一个虚拟的文件共享空间 用户可以输入想要搜索的文件 名称 设置上传和下载的相关选项 用户可以输入想要搜索的文件名称 设置上传和下载的相关选项 应用层屏蔽了下层路由 传输等技术细节 用户可以像使用本地存储系统一样 访问分布式存储空间 通知层实现了节点的管理和目录管理等功能 在选项 应用层屏蔽了 下层路由 传输等技术细节 用户可以像使用本地存储系统一样这层中实 现了整个 P2P 网络传输系统的结构 首先是超节点的选取 其次 当普通 节点登录时 会将个人信息 如 IP 地址等 注册到超节点上 超节点利用 IP 地址哈希后构成基于 Chord 环的簇内网内结构 节点共享的文件会通过哈 希函数计算出关键字后将索引信息存入相关节点 网络传输层是整个文件共享系统的核心 在这一层里主要完成节点对 资源的搜索定位以及文件的上传与下载功能 另外 为了提高系统的效率 和安全性 可将负载平衡 服务质量和网络安全模型等相关因素加入这一 层 18 物理层由分布各处的具有存储空间和计算能力的计算机 系统节点 及连接它们之间的底层网络部件构成 各个用户节点通过贡献自己的存储 空间和计算资源构成 P2P 存储系统的基本元素 是文件存储的底层实体 物理层是整个系统的物理基础 二 二 P2P 传输系统的界面设计传输系统的界面设计 应用层主要涉及到整个 P2P 系统的界面设计 它只是 P2P 技术应用的 一个实例 提供方便的人机交互 真正一系列功能的实现在后面的通知层 和网络传输层实现 本系统旨在掌握 P2P 技术的应用 为今后的网络教学 平台提供技术支持 重点放在网络传输层 应用层只涉及到对 P2P 传输过 程中的一些设置和下载的显示 按功能 可将应用层分为下面几个模块 1 1 搜索模块 搜索模块 任务搜索模块主要是为用户提供搜索内容的输入 将搜索的内容提交 给网络传输层 该模块有两种搜索模式 文件名搜索和用户名搜索 1 文件名搜索 在本 P2P 系统中 文件共有三种属性 文件名 扩展名和文件大小 搜索时 用户输入文件名关键字 然后通过网络层在簇内检索并将查询信 息交给超节点转发 搜索后将文件信息回传给该节点 2 用户名搜索 每个系统中的节点入网时都会提供自己的用户名 为了提高系统的网 络安全性 为每个节点设置一个信誉度 信誉度随着上传文件数目的增加 而提升 19 在系统使用过程中 也许某个节点 A 对另外一个节点 B 提供的资源感 兴趣 下次还想查看 B 节点提供的文件下载列表 这时就可以在界面中输 入 B 节点的用户名 搜索到该用户后两者建立连接由 B 将文件列表反馈给 节点 A 节点 A 也可以将节点 B 添加为好友 这一功能通过本地数据库中 的一个表来记录 但由于没有中心服务器 并不提供显示好友是否在线功 能 只有当搜索好友的文件列表时才会将好友是否在线的信息反馈给搜索 节点 搜索不到文件列表表示不在线 即使在线但没共享文件也视为不在线 另外 同一聚簇内节点间的传输平均速率是大于聚簇间节点的传输速 率的 所以为了提高效率 本系统还提供了 我的网上邻居 这一功能 点击网上邻居搜索按钮后 超节点会将在线节点的信息 包括用户名和信誉 等级 下发给搜索节点 搜索节点可以通过点击某一节点查看它的共享文件 列表 在搜索模块中 只是提供了文件名和用户搜索 并没有提供基于内 容的搜索 2 文件下载控制模块 文件下载控制模块 17 如大多数 P2P 应用软件一样 本系统提供了文件下载控制模块 主要 包括以下几种功能 1 连接控制 在下载过程中 由于种种原因 如网络上传节点网络中断 下载可能终 止 系统提供自动重连机制 从两方面进行设置 重试时间和重试次数 重试时间是设置连接超时值 重试次数是在未连上之前重新连接的次数 若经过设定的重连次数仍没有连上 该文件下载任务自动转为停止 放到 20 文件下载队列的队尾 需要手动才能重新回到下载文件的队列 2 存储和共享目录设置 一般情况下系统都会提供默认的存储和共享目录 用户将下载的文件 和想要共享的文件分别放入这两个目录中 也可根据情况自己修改 3 缓存设置 早期有的 P2P 下载工具 如 BT 没有提供缓冲存储机制 这对硬盘具有 很大损耗 本系统中提供缓冲存储功能 先将下载的内容放入自行设定的 缓存中 然后再写到硬盘上 4 下载任务队列控制 该控制功能主要完成两方面的任务 首先是设置可同时下载的任务数 其他任务处于等待状态 其次 是设置下载任务的优先权 可将等待队列 中的某个任务置为优先下载或优先等待两种模式 优先下载时 将正在下 载中的最后一个任务置为等待状态 优先下载的任务立即执行 优先等待 时 当正在下载的某一任务下载完成时该任务立即执行 5 下载进度控制 下载进度控制模块主要是通过界面上按钮的单击事件触发响应函数对 某个选中的下载任务进行操作 主要包括 开始 暂停 停止 三个功能 当选中某个任务点击 开始 时 若正在下载的任务数已经达 到预先设定的最大值 则该任务进入任务等待队列 若未达到 就立即连 接源节点下载 暂停 只是停止本节点与数据源节点之间的数据传输 但彼此之间的连接并未断开 当重新开始下载时仍使用原来的路由路线恢 复数据的传输 停止 是彻底将下载节点和源节点的连接断开 文件下 21 载任务从下载队列中撤除 3 文件下载显示模块 文件下载显示模块 该模块主要起到下载文件信息的显示作用 包括两个部分 已下载和 下载文件显示 它们在显示时使用相同的方式 包括文件下载状态 文件 名及其扩展名 文件大小 已下载百分比和已用时等 但两者在本质上却 有很大的不同 在后台的数据库这两部分使用不同的表进行信息的记录 1 已下载任务显示 已下载任务的表结构相对简单 主要包括文件名和扩展名 文件大小 文件下载完成时间 文件下载用时和文件保存路径这几个字段 在系统运 行过程中程序从表中读取数据 按项分别显示在界面上 已下载百分比直 接填入 100 下载状态皆为完成 2 下载任务显示 下载任务包括正在下载的 暂停的 停止的和等待状态的任务 它有 两种显示模式 概要显示和详细信息显示 概要显示和已下载任务的显示 模式相同 在主界面的列表控件里显示文件的状态信息 文件名及其扩展 名 文件大小 文件下载的百分比和已用时等 除此之外 通过双击某个 下载任务还能看到更为详细的下载信息 这些信息包括文件的分块情况以 及各个块已经下载的百分比 在文件显示模块中还提供了 删除 操作 无论是已下载的文件还是 正在下载中的文件通过点击 删除 都能将其从显示列表中剔除 同时也 在数据库中删除相应的表项 此外 用户可根据需要选择是否删除已经下 载了的文件 22 三 三 P2P 传输系统的网络结构设计传输系统的网络结构设计 14 通知层实现了节点和目录管理等功能 该层主要完成两个功能 超节 点选取和普通节点的管理 1 超节点的选取 超节点的选取 17 前面已经提到过本节点是基于超节点的分布式结构化 P2P 网络结构 因此 超节点的选取也不是一件随随便便的事 超节点具有带宽大 内存 大 处理能力强的特点 本系统中 超级节点的选取大体上是按区域来划分的 有两种超级节 点的选择方法 第一是系统设定 比如让小型局域网内的服务器作为这个 局域网的超级节点 这种超级节点具有处理能力强 功能稳定的特点 它 们是静态的 第二种是动态产生 在软件中根据特定的算法 对节点的负载情况做 出评估 计算出节点的资源消耗因子 让负载轻的节点担任本区域内的超 级节点 2 节点的管理 节点的管理 节点的管理实际上是节点之间互通信息的过程 主要包括下面几个步 骤 1 节点的登录 当一个节点连入 P2P 系统时它需要登录到超级节点上 这里所说的登 录就是与超级节点建立起连接 将自己的 IP 地址和用户名等网络信息注册 到超级节点上便于以后的服务和管理 当然 也有可能此节点自己动态的 23 变成超级节点接受其他普通节点的连接 超级节点本地维护着一张表 这 张表记录着所有和它连接过的节点的信息 这些信息包括节点的端口地址 用户名 连接状态 节点的信誉度和节点的资源消耗因子等 2 簇内文件共享结构的建立 一旦节点连入系统 它将立即使用哈希函数计算出共享目录下的文件 的关键字 通过 Chord 方法将文件索引信息存放到匹配的节点上 因为这 些信息是动态的 节点随时可能修改共享的内容 再加上这些信息有多有 少 所以在节点中索引信息并不存储在数据库中 而是开辟一块内存空间 以表的格式记录存放的关键字信息 这种方法减少了因读写数据库所消耗 的时间 又从内存中搜索 提高了搜索效率 在实现上这里使用容器类 3 节点下载时连接的建立 节点登录注册以后 就可以系统提供的下载功能 用户输入想要查询 的文件名或想要查询的用户名 若是文件名 则计算出关键字 在簇内利 用节点的路由表进行查询 同时提交给超级节点 超级节点转发查询请求 到别的超级节点上 若是用户名 则直接将用户名发送给超级节点 超级 节点根据查询内容首先搜索本地数据库 看是否有匹配的 若没有匹配的 则通过相应的路由算法将查询请求包发送到系统中的其他超级节点上 无 论是文件搜索还是用户名搜索 最终都会向查询节点返回拥有该资源的源 节点地址或者超时信息通知查询节点搜索无效 4 节点的退出 节点的退出分超级节点的退出和普通节点的退出 超级节点退出时 会查询数据库表中的资源消耗因子字段 看聚簇内 24 的哪个节点拥有顶替它成为超级节点的能力 将内存数据库中的信息和其 他超级节点的路由信息通过网络发送给该节点并通知其它节点它的退出和 超级节点的变更 普通节点的退出时 它首先将存储的关键字信息表传送 给邻居节点 同时向超级节点发送一个消息 与超级节点断开连接 超级 节点将内存数据表中与该节点相关的项删除 并将该节点退出的消息发送 到其他节点上以更新其他节点的路由表 以上是节点正常退出下的情况 但是由于网络本身的不稳定性 再加 上硬件故障 软件异常等情况 不管是超级节点还是普通节点都有可能异 常退出 五 五 P2PP2P 传输系统中关键技术的研究与实现传输系统中关键技术的研究与实现 一 超节点的选择 一 超节点的选择 15 17 超节点的选择有两种情况 一种是直接指定可作为超级节点的计算机 这种是静态的 具有较高的稳定性和安全性 但由于缺乏灵活性 在大型 文件共享系统中用的不多 另外一种是节点加入网络后根据其信誉度和负 载率两个指标动态地选择超级节点 在这里将要讨论的是第二种 超节点的选择有一个原则 内网内使用服务器作为代理上网的计算机 不能作为超级节点 即使这样的计算机有较高的信誉度和极低的负载率 因为在网络传输过程中通过代理连接是件相对比较麻烦的事 能作为超级 节点的计算机必须是能直接与因特网相连的 超节点的选择流程如图 7 所 示 25 广播登录消息 超节点回应 选择超节点 注册信息 有 成为普通节点 成为备份超节点 否 首先当一个节点启动P2P应用程序接入文件系统时会广播一个消息 告诉一定范围内的节点自己登录了 因为物理位置相近的节点之间在信息 检索时时延会相对短一些 传输数据的平均速率也会高一些 为了提高网 络传输效率 尽可能的要将众多节点按逻辑区域划分 使得在一定范围内 的节点聚集在一个簇中 这就要求节点登录时的广播不是无限制的广播 在这个广播消息上要加上一个限制 TTL 生存时间 每通过一个路由器 TTL的值就减1 当它的值为0时 该包就丢弃 广播的范围也到此为止 节点是否能成 为超节点 成为超节点 无 是 图 7 超节点的选择流程 26 通过这种机制可以较为有效地将节点划分 接下来 当某个超节点收到了这个广播 它会沿原路径逆向发送自己 的地址 信誉度 负载率以及消息到达那里所经过的跳数 TTL 减少的值 该节点收到了此信息 说明在预定的区域内存在超节点 如果没有收到 则担当起该区域内超节点的角色 为其他节点服务 一个节点发出广播以后可能收到多个超节点的回应 它需要根据返回 的超节点的信息 包括信誉度 负载率 时延 选择一个合适的超节点 与 该超节点连接后即上传自己的节点信息 超节点接收到节点的信息后会将 该节点的信誉度和负载率与备份超节点比较 若优于备份超节点 则该节 点取代原备份超节点 否则成为普通节点 二 节点间通信连接的建立 二 节点间通信连接的建立 在 P2P 应用系统中 节点间的连接分两种情况 直接连接与间接连接 直接连接是指有公网地址的节点能直接与对方连接 在系统中 当超节点 将下载源地址返回给查询节点时 若二者都拥有公网地址就能直接建立起 连接 间接连接则要复杂一些 随着接入 Internet 的计算机数量的不断猛增 IP 地址资源也就愈加匮 乏 很多计算机并不具有外部公网地址 它被分配到的往往是局域网内部 网络中使用的内部地址 它需要与外部进行直接的连接就要使用一种技术 NAPT Network Address Port Translation 18 NAPT 的作用就是在 NAT 网关处 将内部地址替换成公用地址 从而在外部公网上正常使用 根据 NAPT 设备对传入数据分组进行地址端口映射方式的不同 一般被分 成两类 对称型 NAPT 和锥型 NAPT 27 对称型 NAPT 对于一个给定的本地 UDP 端口 如果与其连接的目的 端口 IP 地址相同 端口不同 NAPT 使用同一个会话 如果目的 IP 地址不同 无论任何端口 NAPT 使用不同的会话 也就是说由目的 IP 地址是否相同 来决定 NAPT 是否用同一个会话 锥型 NAPT 对于一个给定的本地 UDP 端口 如果与其连接的目的端 口 IP 地址相同 端口不同 NAPT 使用同一个会话 如果目的 IP 地址不同 无论任何端口 NAPT 也使用相同的会话 也就是说只要本地绑定的 UDP 端口相同 而不管发出的目的地址是否相同 都使用同一个会话 这种类 型 NAPT 也是目前大多数所使用的 本系统也是针对这种类型的 NAPT 设 计出网络连接的方法 在锥型NAPT模式下 节点间的连接又分多种情况 对等方分别处于 外网和内网 对等方处在同一NAT后 通信的对等方位于不同内网 前两 种情况相对简单 这里对第三种情况展开描述 如图8所示 图 8 位于不同内网的节点 SuperNode S 202 116 178 166 NAPT A 外网 IP 219 214 35 24 内网 IP 192 168 0 1 NAPT B 外网 IP 202 114 175 85 内网 IP 192 168 0 1 Node A 192 168 0 2 4000 Node B 192 168 0 3 5000 首先 节点 A 登录 P2P 网络 它的内网地址是 192 168 0 2 使 28 用端口 4000 与 NAPT A 建立会话 NAPT 的外网 IP 地址是 219 144 35 24 当节点 A 想与超节点 S 进行通信时 NAPTA 为它们 的会话分配端口 40000 那么超节点 S 收到的节点 A 的地址是 219 144 35 24 40000 这个地址就是节点 A 的外网地址 相同的 节点 B 通过 NAPT B 与超节点 S 连接 它的外网地址是