论文部分内容阅读
文件分发是一类将文件发送到大量的终端用户的应用的总称,包括了文件共享、流媒体在线观看等一系列最为常见用的互联网应用。随着网络的发展,用户的规模越来越大,对文件发布的性能要求也越来越高。P2P技术利用了普通用户的计算资源和上传带宽资源,可以提高文件分发的性能。网络编码(Network Coding)是近几年通信科学一个新兴的研究领域。使用网络编码后,通信的中间节点不再是直接转发数据包,而是将收到的一些包编码成一个新的包后进行转发,目的节点进行解码得到原始数据。网络编码和P2P技术结合,可以显著提高文件分发的分发速度、鲁棒性、可扩展性等多方面的性能。本文的主要研究内容和贡献有:1)本文提出了稀疏线性编码算法,并由Cooper的关于稀疏矩阵的研究成果推导出关于稀疏线性编码的编码成功率的定理。使用稀疏线性编码,可以降低网络编码的编码复杂度,与原有的完全编码相比较,编码复杂度由O(n)下降到了O(log n),其中n是原始数据信息的数量。在对较大的文件进行分发时,稀疏编码可以在保持高编码成功率的情况下,达到比完全编码算法高得多的编码速度。实验中,以主流配置(Intel Pentium D 3.2GHz,1GB RAM)的个人计算机对128MB文件进行编码,在分块大小为256KB时,平均编码速度达到了7MB/s,可以不拖累网络传输。2)网络编码可以通过优化数据块调度的方式提高P2P文件系统的性能。我们将稀疏线性编码引入了P2P文件分发系统,实现了一个使用稀疏线性编码的系统(Ecode)。基于相同框架,同时也实现了一个不使用编码的P2P文件分发系统(LRF),其中使用了局部稀缺优先算法进行数据块调度。我们在局域网平台上进行了文件分发的对比实验。实验结果表明,在平均下载时间,总发布时间,整体吞吐量几个方面,Ecode比LRF性能更好。平均来说,使用稀疏编码减少了约10-15%的下载时间。3)我们提出了预先检测机制,以避免无效(线性相关)的数据块被发送。基于同样框架,我们实现了一个使用预先检测机制和稀疏线性编码的P2P文件分发系统(SmartCode),以及用于对照的无编码系统(LRF)和未使用预先检测的编码系统(Ecode)。SmartCode是第一个使用稀疏编码的广域网文件分发系统。在PlanetLab上,我们进行了三种系统的广域网实验。实验结果表明,在平均下载时间和鲁棒性方面,SmartCode的表现优于其余两个系统。相比于Ecode系统和LRF系统,SmartCode分别减少了平均7%和11%的下载时间。在鲁棒性方面,SmartCode的优势更大。在一些极端的情况下,LRF没有节点能够完成下载,Ecode只有几个节点可以完成,而SmartCode超过75%的节点都能完成下载。