我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 正交树 >

基于P2P对等网络流媒体服务系统技术的研究pdf

归档日期:07-02       文本归类:正交树      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  燕山大学 硕士学位论文 基于P2P对等网络流媒体服务系统技术的研究 姓名:王丽芬 申请学位级别:硕士 专业:计算机软件与理论 指导教师:李阳明 20060101 摘要 摘要 对等网络流媒体技术可以合理地利用客户端的计算机能力和带宽资 源,使用户实现下载的同时播放流媒体节目,也可以利用自身的计算机空 闲资源为其它用户提供服务。因此,P2P流媒体系统成为P2P技术领域内重 要应用之一,也是当前分布式系统领域的一个研究热点。本文着重从以下 几个方面进行了深入研究和探讨。 首先,在分析对等网络技术研究现状的基础上,设计适合广域网中的 底层网络平台G-N及其算法。G.N平台采用了两阶段搜索策略、基于多点延 迟的MPR技术和随机走步算法,将在一定程度上改善系统搜索效率和时问 延迟,为研究更实用的P2P流媒体系统提供构建网络平台的关键技术。 其次,在充分研究P2P流媒体系统的传输和分配的特点后,设计了媒体 控制层,并将聚类思想应用到该层当中,使请求节点尽可能的选择与自己 同属于一个聚类的节点为其提供资源。 再次,提出数据分配策略及数据控制协议。根据每个节点意愿提供的 不同带宽,将节点划分为不同的等级。在数据发送节点间,根据对方服务 能力等因素来分配每个数据发送节点所发送的数据数量,从而可以减少数 据接收的时间延迟。 然后,为了保证媒体文件的连续播放,同时使系统具有快速扩充系统 的能力,提出数据缓存模块。系统可以根据请求节点的请求,数据缓存模 块缓存一些媒体文件片段,以备节点间的传输中断。节点也可以选择需要 的文件进行存储。 最后,使用网络仿线对系统的底层网络平台和系统性能进 行验证。 关键词P2P对等网络;流媒体技术:P2P流媒体;G-N系统;多播;带宽 燕山大学工学硕士学位论文 Abstract Peer-to—Peermedia callBse and technologiescomputingcapacity streaming can other ofclientend makethe clients bandwidth effectively.Furthermore,it afilewhile media isnot one play downloaded.So,P2Pstreamingsystemonly ofthe ofP2P alsooncofhotresearchesinfieldof technology,bm applications distribution the ofissuesofP2Pmedia system-Inpaper,some streaming willbestndied. research thebasisof actualitiesonP2P Firstly,on analyzing technologies.the fit network its thatare forⅥqdeAreaNetwork platform(G-N)andalgorithms are theG-N search designed.Onplatform,twophases strmegy,multipoint and walk fire random can relay(MPR)technologiesalgorithmadopted.which ofP2Pmedia and ina relay improvesearchingefficiency system way.These main that to bottom usedbuild for platform providetechnologies researching more P2Pmedia applied system. streaming onsufficientresearchesoncharacteristicsoftransmission Secondly,based anddata thatP2Pmedia controlis allotting streamingsystemhas,medialayer anduse idea the Can the ofclusteron make designed layer.Thjs requestingpeers Useresourceofthe that tothesa_rrle supplyinspeersbelong cluster嬲the requestingpeers’. anddatacontrol are strategy Thirdly,data嬲s远Ilillg protocolproposed, whichCanmake contributetheirdifferentbandwidthintermoftheirdesire. peers Canbe intodifferent data Furthermore,thesepeers separated classes.During call the that should every transmitting.systemassignmagnitude supplyingpeer transmit their a1.ThisCanmakedata accordingservingcapacities,et receive reduce. delay orderto thatmediaale Fourthly,inguaranfee files and continuouslyplayed that Canbe of must system expanded systemfast,data capacity cachin4;module cachesomemedia inthe ofthe of in segmentslight requestsrequestingpeers Ⅱ Abstract ordertoavoid Peerscallselectfond intermittingduringtransportation segment tostore,too. simulation that Simulation Finally,theexperimentNS一2(NetworkVersion 2) isintroducedis deployed. P2P media Keywordsnetwork;Mediastreaming;P2P streaming;G-Nsystem Multicast;Bandwidth m 燕山大学硕士学位论文原创性声明 本人郑重声明:此处所提交的硕士学位论文《基于P2P对等网络流媒 体服务系统技术的研究》,是本人在导师指导下,在燕山大学攻读硕士学位 期间独立进行研究工作所取得的成果。据本人所知,论文中除已注明部分 外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡 献的个人和集体,均已在文中以明确方式注明。本声明的法律结果将完全 由本人承担。 作者签字王聊棼 日期:伽;年:弓月∥目 燕山大学硕士学位论文使用授权书 《基于P2P对等网络流媒体服务系统技术的研究》系本人在燕山大学 攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果 归燕山大学所有,本人如需发表将署名燕山大学为第一完成单位及相关人 员。本人完全了解燕山大学关于保存、使用学位论文的规定,同意学校保 留并向有关部门送交论文的复印件和电子版本,允许论文被查阅和借阅。 本人授权燕山大学,可以采用影印、缩印或其他复制手段保存论文,可以 公布论文的全部或部分内容。 保密口,在 年解密后适用本授权书。 本学位论文属于 不保密留。 (请在以上相应方框内打…4 ) 作者签名:盖翻棼 日期:训辟弓月/细 导师签名 南n 日期.《年5月尹 h7{ 第1章绪论 第1章绪论 P2P11.-4]即是Peerto Peer的缩写,称为对等连接或对等网络。它不仅能用 服务器的资源,同时能够合理地使用用户计算机的空闲资源。用户在享受 流媒体节目的同时,也在利用自身计算机所空闲的资源为其它用户提供服 务。而且整个流媒体服务系统的资源不仅仅是服务器资源,同时还包括用 户的空闲计算机资源。用户数量增多,消耗的资源也随之增多,但是新增 加的用户又可以提供新的资源。所以,使用P2P技术提高质量和大容量的流 媒体服务系统成为可能,而且P2P模式的流媒体服务系统并不改变现有的流 媒体传输协议。 本文主要的研究动机为:结合流媒体技术与P2P传输技术的优点,来改 善网络的处理负载及网络带宽使用量,减少时间延迟,快速扩充系统能力。 并针对所使用的网络环境做最佳化的设定,改善以往主从式多媒体传播模 式的缺点。本论文所设计的P2P流媒体系统及其底层网络平台的性能,应用 在多媒体文件传播上可以达到的预期效果,将经过仿线研究背景 由于传统的影音数据被转化成为数字数据后,其数据量将极其庞大。 随着计算机硬件与网络技术的进步,有越来越多的实时影音资料可以利用 实时流媒体技术通过网页在网络‘51上取得,即使用户在很远的地方,仍然可 以根据需求实时接收影像与声音文件。 实时流媒体技术【6I从90年代开始逐渐流行,根据统计超过35万小时的运 动、音乐、新闻与娱乐的影音数据在因特网上不断被广播。虽然有许多流 式系统被发展,但主要分为两种形式,一种通过超文本传输协议WebJ]匣务器 提供下载功能,另一种则是使用主从式架构的流媒体服务器来达到目的。 但是超文本传输模式是针对文字与静态文件而设计,对于实时流式传输影 音文件并不是特别适合。所以针对实时多媒体影音数据的传输提出了 Control RealAudio的技术,通过使用网际协议TCP(Transport Protoc01)或者 燕山大学工学硕士学位论文 Protoc01)传送数据。 Datagrarn UDp[7](UsgT P2P对等网络技术已经被应用在文件共享系统[8-111上一段时间了,但是 对于P2P模式应用在多媒体实时传播上仍有很大的发展空间,而且多媒体影 音文件通过网际通讯协议[12,13】使用广播模式是不可行的,所以本研究将针 对多媒体数据的流式传输,使用P2P模式来寻求解决的方法。 P2P流媒体系统与文件共享系统最大的区别在于节点间数据共享的模 效的P2P实时流媒体系统来讲,需要解决以下问题。 (11不对称性由于节点上传带宽和下载带宽的不对称性,提供节点所 提供的上传带宽可能小于媒体数据的播放速率。解决这个问题的方法是, 是用多个数据发送节点为接收节点的每个实时流媒体会线)动态性在一个高度动态异构的网络中,如何为每个流媒体服务会 话选择和监控适当的数据发送节点,从而得到满足应用要求的流媒体服务 质量。这些动态性和异构性来自于节点能力和节点间的网络连接[14】主要表 现为以下情况:对等网络系统中的节点可以随时加入或退出系统或网络故 障随时断开,因此流媒体数据发送节点随时可能加入或停止流媒体服务会 话;节点的带宽可能随时改变,而且与多个数据发送节点间的连接具有不 同的端到端带宽、丢包率和失效率:就丢包率和失效率而言,底层网络拓 扑结构决定了数据接收节点和多个数据发送节点间的连接存在相关性。 1.2研究现状及领域 对等网络技术在文件共享方面已经取得巨大的成功。本节将从流媒体系统 中组播树构建、组管理以及网络检测和多播组调挨三个方面介绍目前在P2P 流媒体系统领域内的研究现状。 1.2.1组播树构建 组播树[15,16】的构建就是在覆盖网络上构造和维护一棵高效的和容错的 2 第1章绪论 生成树的问题。应用层组播或IP组播技术11”1】成为当前的一个研究热点, 提出了许多可扩展的组管理和可扩展的、可靠的消息传播【22】。为了超越单 棵树的简单结构,近来的对等网络技术方面的研究进一步利用树中兄弟之 间的“垂直链路”来克服构造树的难题。 1.21.1OvercastOvercastE23】是由一个中心的源节点、散布于网络的许多 Transfer Overcast内部节点以及许多具有标准HTTP(HypertextProtoc01)连接 的客户机组成。Overcast利用一个简单的树构建协议,把内部节点构建成以 源节点为根的散发树。Overcast的树构建算法的目标是使每个节点到根节点 的带宽最大化。这通过把一个新的节点放置在一个离根节点最远,但又不 牺牲到根节点带宽来获得。一个节点一旦初始化,它就开始了一个从根出 发的与其它节点一起的自我组织的过程。通过这个方法,这个新的节点可 以离根节点尽可能的远,同时保证可获得的带宽。因此,树构建算法倾向 于把一个新的节点挂在位于同一个网络内的父节点身上。Overcast组播树利 用了节点的转发能力,使得带宽利用率最大化。 虽然组播树路由算法在解决带宽合理利用方面很有效,但基于树的组 播协议存在一些固有的缺点,并且有时难以充分利用协作环境中的可用资 源。造成这个问题的原因是:在任何的组播树中,承担复制和转发组播数 据的节点只是组播树中的内部节点,这些内部节点只占所有参与节点的小 部分。大部分节点是叶子节点,没有贡献任何资源。这个结果和希望所有 节点都承担转发负载的初衷相违背。另外在树的结构中,从上到下,带宽 一般是单调递减的。尽管许多技术被提出来恢复丢失的数据,提高可取得 的带宽,但是,一个节点获得的带宽只由它的父亲节点所决定的。 为了克服树的天然缺陷,近来的研究提出使用“垂直链路”来增大带 上,这些技术具有一个共同点:应当利用覆盖网络中的每一个节点来增强 数据的传输,而不是仅仅利用单棵树中的内部节点。 1.2.1.2 个带对应一棵独立的多播树。节点根据它们愿意接收到的带的个数加入具 有同样多带数的组播树集合中,每个节点同时还给定一个它们愿意转发的 燕山大学工学硕士学位论文 带的上限。这确保转发负载散布到所有参与的节点上。 7】的组成员管理来辅助内部节 sDl“s仃eam利用Pastry的路由和Scribe[26,2 点正交树集合的构建。Pagtry通常把一个消息转发给节点标识和消息标识共 享最长前缀的节点。由于一棵Scribe树是由组成员到组标识的路由形成的, 因此所有的内部成员与组标识共享某些前缀。由此,只要组播树的组标识 最显著的位不同,就可以保证N棵Scribe树有正交的内部节点集。一个Stripe 组的组标识也称为这个带的带标识。为了限制节点的出度,还应用了Scribe 的内建的“push-down”方法。当一个已达到最大度的节点收到另外~个节 点要求接纳为前者的孩子节点的时候,前者把当前孩子节点的列表给后者; 后者接着寻求一个有最小延迟的孩子成为它的父亲节点。这个过程从上到 下递归进行,直到遇到一个可以接纳后者成为它的孩子的节点为止。为了 充分利用一些强节点的空闲带宽,这些强节点被组织成Scribe的一个独立的 组,称为能力空闲组。所有Splitstream的节点,只要它的孩子的数目少于它 转发的带的数目都属于这个组。当一个转发请求不能提供时,Splitstream:将 在能力空闲群中找一个能满足要求的节点。 1.2.1.3Bullet这个系统主要应用在面向高带宽的组播数据发送方面。它 可以不用把相同的数据流发送给所有的节点,Bulk提出在组播覆盖网络中 的节点协作传送正交的数据集。节点仍然从父节点那里接收到一组数据, 但它们还必须寻找能给它们提供它们缺少的数据的节点。Bullet采用了分布 式的算法使得数据可以均匀地散布在所有参与的节点当中。这个方法避免 定位最后一个数据块的问题,取得持续的高带宽的数据发送。 1.2.2多播组管理 除了组播树的构建之外,还需要管理参与的节点,特别是把节点根据 它们的特性组织成不同的组以及把消息发送给一些特定组中的所有成员。 组管理是覆盖网络的一个基本服务,也常常是许多组播程序的一个必要的 组成部分。Scribe提出一个面向大规模组的成员管理的分布式的应用层组播 结构。一个Scribe组包括唯一的组标识、节点标识和会合点(RendezvoUSl。 任何Scribe节点都可以创建一个组,其它节点可以加入这个组,或者把消息 4 第1覃绪论 广播给组中有恰当的证书的成员。因此,组管理机制对组的规模大小不同 的组来说都是高效的。pastry的随机的特性确保树是平衡的,并且转发的负 载均匀散布在所有的节点中。这种平衡使得Scribe可以支持许多有非常多成 员组。更进一步来说,加入请求以一种分布的方式就地被接受了。特别是, 会合点不用处理所有的加入请求。 CoopNetl2809l面向现场直播的流媒体的应用。这个应用把一个服务器的 内容发送给许多可能高度动态的接收节点。CoopNet使用客户端的组播来减 轻流媒体服务器的负载,并且帮助服务器克服瞬间冲击的问题。CoopNet 没有使用纯粹的P2P方式。因此,CoopNet受益于一个比分布方式更高效的 中心的管理。CoopN畦有一个指定的工作站负责管理节点的加入和离开。工 作站把组播树的整个结构存储在内存中。当一个节点开始接收现场直播的 流媒体时,这个节点与工作站接洽加入的操作。工作站从保存在内存的组 播树中找到一个合适的位置,把这个节点的父节点返回给这个节点。因此, 在实际应用中可以扩展到大规模系统中。 1.2.3网络检测与组调整 众所周知,互联网是一个高度动态的环境,很容易发生不可预测的分 割、拥塞、和突发冲击。除了组播的构建和管理外,一个覆盖网络应用程 序还必须不停地调整自身来适应多变的互联网环境。所以,底层网络应当 通过反复的检测感知底层的变化,相适应地调整自身的结构。目前有很多 基于检测的技术来检测网络。这些技术使用轻量的消息检测来估计节点间 的延迟与带宽。尽管检测消息和轻量的估计不能完全勾画出连接的特性, 但是它们在故障检测和路径选择方面非常有效。通常,覆盖网络把节点间 的连接看作“黑盒”,而黑盒测试对基于覆盖网络的组播系统已经足够了。 许多覆盖网络的设计采用了组播结构的局部调整:允许节点动态地选 择能够提供更好服务的节点。例如Overcast为了获得移动数据时观察到的近 似带宽,协议检测下载10KB花费的时间。这个方法给出的结果好于使用底 层带宽测量,例如Ping,得出的结果。除此,节点可以周期性地检测当前兄 弟节点、父亲节点、和祖父节点的带宽来估计自身的位置。节点直接测量 S 燕山大学工学硕士学位论文 祖父节点的带宽,作为对先前做出的当前父亲节点的孩子节点是否正确的 一个测试。如果必要,节点向上移动一层,成为它原来父亲节点的兄弟节 点。所以,Overcast可以内在地容纳除了根节点外的节点失效和网络阻塞。 在人们的不断研究和努力下,将P2P应用于流媒体技术的产品首先在实 经日趋成熟。目前,P2P模式的流媒体技术,已经走进市场,走进公众的娱 乐和信息服务的基础设施中。美国ChianCast网络公司提供的CCDP平台、美 用了P2P模式的流媒体服务技术。 1.3研究内容 本文研究如何基于P2P对等网络在动态多样的底层网络基础上构建可 以可扩展的、高效率的、高可用的流媒体服务,为P2P技术开辟更广阔的应 用领域。研究内容如下: 首先,研究支持流媒体应用的底层对等网络平台,及与之相关的数据 信息搜索算法。从基础平台来看,P2P分为结构化P2P和非结构化P2P,这两 种系统在数据存放、搜索条件、路由和一致性维护方面差别非常大,但具 有很强的互补性。P2P底层协议能够更好的支持上层流媒体应用,这个重要 的研究课题并没有得到研究界应有的重视。结合流媒体应用的特点和需求, 本文提出了一种P2P底层网络平台,非结构化P2P网络G.N平台,并讨论支 撑流媒体上层应用时的在节点成员维护,数据存放、路由策略和搜索算法 等核心算法和相应的性能评价。 其次,本文研究在动态的环境下,如何利用底层P2P网的拓扑结构和性 能信息来合理选择数据发送节点,并利用底层网络协议的相关功能调用监 控邻居节点及与邻居节点间网络连接的状态,并根据状态的变化来动态调 度并调整邻居节点的选择。从而合理利用底层网络协议的功能,在节点和 网络状况不可靠的环境中构造高可用性的流媒体服务。 再次,本文采用多个数据发送方提供流媒体数据,多个数据发送方无 法保证媒体数据按照播放时的顺序依次到达,因此,播放延迟成为影响P2P 6 第1章绪论 流媒体可用性的重要因素。为了解决这个问题,本文设计了一个优化的数 据分配算法,解决给定一个媒体数据接收节点和一组媒体上载带宽各异的 数据发送节点,如何适当地为每个数据发送节点分配媒体数据子集,从而 保证在多个数据发送节点之间合理地调度数据的发送,尽量减少媒体数据 的传输延迟。 最后,为了保证媒体文件播放的流畅性,应付网络传输过程中出现的 网络拥塞或连接突然中断等情况,通过对这个领域的潜心研究,本文设计 了一个数据缓存算法。根据请求节点的请求,系统为媒体文件的播放缓存 有效的多个副本,这样可以应付在系统传输期间出现的突发事件,如机器 故障、突然断电等,保证系统播放的连续性。 1.4论文结构 本文由五部分组成: 第1章是全文的绪论,叙述了本文的研究背景、研究内容、研究意义以 及研究现状及领域。 第2章是相关的关键技术研究,包括P2P对等网络技术概述和流媒体技 术概述。 第3章主要研究P2P流媒体系统底层网络系统及其算法,并在此基础上 设计了系统的底层网络平台G-N,并针对G-N系统的特点设计了相应算法。 第4章这章是全文的核心之~,是对P2P流媒体系统核心部分重点研究。 首先,将整个流媒体系统在逻辑上分成三个层次,提出每个层的主要负责 的功能;其次,对系统核心层(媒体控制层)作了具体研究,并将其功能模块 化;最后,针对各个模块的功能,提出相应的核心算法。 第5章采用实验平台一网络模拟器NS.2对系统的性能和底层网络平台 的性能进行了评价分析。 最后是本文的结论,总结了全文的工作,指出了系统需要继续完善的 地方,并给出了应用前景。 燕山大学工学硕士学位论文 第2章相关技术研究 P2P流媒体传输系统将P2P对等网络技术和流媒体技术完美的结合在一 起,改变了传统多媒体服务系统中客户端被动的局面,使得用户可以在观 看影音文件的同时,利用自身的空闲资源为系统中的其它用户服务。 2.1 P2P对等网络技术基础 P2P计算引导网络计算模式从集中式向分布式偏移,这使人们在Intemet 上的共享行为被提到了一个更高的层次,使人们以更主动深刻的方式参与 到网络中去,正如第二代互联网之父Doug.VanHouweling所说的:“下一代 互联网民们将真正参与到网络中来,每个人都能为网络的资源和功能扩展 做出自己的贡献”。随着P2P研究的进一步深入,P2P技术及应用将为信息社 会带来更多的机遇与挑战。 2.1.1 对等网络技术的主要应用 P2P技术引导网络应用的核心从中央服务器向网络边缘的终端设备扩 散,对等网络的应用【3¨2l主要体现在如下几个方面。 2.1.1.1对等计算对等计算是分布式计算的思想在广域网上的延伸,目的 是将网络上的CPU资源共享,把网络中众多的普通计算机中暂时不用的计 算能力累计起来,用以执行以往需要超级计算机来完成的任务。任何需要 大量数据处理的行业都可从对等计算中获利,如天气预报、动画制作、基 因组成的研究等,有了对等计算之后,就不再需要昂贵的超级计算机了。 就对等网络的本质而言,对等计算就是网络上CPU资源的共享。 2.1.1.2协同工作协同工作依托在网络之上。但以传统的Web方式实现, 往往给服务器带来极大的负担,并造成了昂贵的成本支出。而采用P2P技术, 可以在互联网上任意两个用户之间建立实时的联系和信息传输,避免了中 央服务器产生的网络和处理延迟及性能瓶颈,因而能够更方便、高效地实 现用户之间的协同。 2 第2章相关技术研究 Messaging)正是实 2.1.1.3在线交流最近几年兴起的即时通信IM0nstant 现了用户之间的直接交流,受到互联网用户的极大欢迎,可以说已经是无 处不在。目前很多公司正努力将这种方式应用到企业级的协同工作平台中 来,已经推出了一些产品。由于其具有成本低廉、平均事务处理能力较高、 可动态扩展等优良品性,并能够有效地提高信息交流和沟通效率,未来P2P 技术在企业级协同工作领域有着很好的应用前景。 2.1.1.4搜索引擎P2P技术使用户能够深度搜索文档,而且无需通过Web 服务器,也可以不受信息文档格式和宿主设备的限制,达到传统目录式搜 索引擎(只能搜索到20%.30%的网络资源)无可比拟的深度。 2.1.1.5文件交换可以说文件交换的需求直接引发了P2P技术热潮。传统 的Web方式中,要实现文件交换需要Web服务器的大力参与,要先通过文件 上传,然后才能下载。虽然,电子邮件方便了个人之间文件传递,却没有 办法解决大范围的交换,这也是WEB的重要缺陷。而P2P技术可以使用户利 用基于P2P网络协议的客户端软件脱离服务器,直接从含有所需文件的对等 节点机下载文件。 2.1.1.6网络游戏基于P2P方式的网络游戏是一个很有前景的应用。目前 已经有一些公司开始关注这方面的研发工作。 此外,还有诸如边缘服务、智能代理、实时通信技术和广域网络存储 labsAB等公司正 系统等其它几种应用方式。另外,美国cybiko及瑞典Pocit 试图将P2P技术应用到无线通信中,使得不必经过基站就可连接具有无线通 信功能的移动终端,实验性P2P产品…已经问世。 2.1.2P2P技术面临的典型问题 P2P对等网络技术所面临的典型问题【34J分别体现在网络体系结构、元数 据的组织与描述、资源搜索和安全问题等方面,下面将进行讨论。 2.1.2.1P2P网络体系结构拓扑结构是指分布式系统中各个计算单元之间 的物理或逻辑的互联关系,节点之间的拓扑结构一直是确定系统类型的重 要依据,目前互连网络中广泛使用集中式、层次式等拓扑结构,Intemet本 身是世界上最大的非集中式的互联网络。集中式拓扑结构系统目前面临着 9 燕山大学工学硕士学位论文 过量存储负载、Dos攻击等一些难以解决的问题。层次式拓扑结构是一种应 Name 用比较广泛的分布式拓扑结构,域名服务系统DNS(DomainService) 是其最典型的应用。P2P系统一般要构造一个非集中式的拓扑结构,在构造 过程中需要解决系统中所包含的大量节点如何命名、组织及确定节点的加 入、离开方式、出错恢复等问题。 2.1.2.2元数据的组织与描述P2P网络面向的是异构网络与操作系统,这 样就需要在这些系统之间交换数据资源,但是因为这些系统的数据表示并 不都是完全相同的,这样就需要一个能够在多个系统之间确定一个通用的 元数据表示方案。元数据的组织应该包括数据资源的表示、消息通信协议 等。很多系统都支持目前存在的协议,如何利用现有的协议和技术有效地 解决元数据的组织和描述是网络中研究的一个热点。 2.1.2.3资源搜索 在典型的P2P网络中数据资源分布在各个独立的节点 上,如何高效地索引、查找、定位以及访问这些数据信息资源是另一个需 要关注的重要问题,在分布式系统中这些问题同样也是正在研究的热点问 题。一般来说在P2P共享应用中所采用的检索方式是采用关键字来查询自己 所需的信息资源,同时人们也期望能够将数据资源的索引信息存放在系统 中的每一个节点上,在数据的访问过程中则期望能够采用流水、并行或选 择传输路径的方式来加快数据的访问速度。 2.1.2.4安全问题安全问题永远能跟上互联网的发展节奏,像美国在线的 “即时信使”和眼下的几种P2P软件对源代码的加密并不可靠,很容易就会 被反向汇编得出源代码,这些源代码最终像开放源代码软件一样在网上随 处可得。一方面会有利于人们针对不同的操作系统平台和功能需求重新编 译这些程序。另一方面,一些居心不良的黑客也能借机篡改软件源代码。 安全性确实是一个很大的问题,但是随着资源访问控制策略、多种授权、 利用数字签名进行身份认证、携带证明代码段、加密等安全技术的不断发 展,将会得到有效的解决。 2.2流媒体技术基础 P2P流媒体系统实质上是多媒体计算机与通讯网络技术相结合的产物。 t0 第2章相关技术聊f究 多媒体通讯与一般的数据通信不同:多媒体通讯要求能够综合地传输、交 换各种信息类型,而不同的信息呈现出不同的特征。P2P流媒体系统能够忍 受分组丢失造成的差错和反常,也可以忍受由于无重传或纠错机制而导致 的分组丢失,但是无法忍受显示不连续或显示混乱,即不能忍受任何的延 迟;而对于数据传输来说,则可以忍受延迟,但不能有错,因为即便是一 个字节的错误都会改变数据的意义。 2.2.1流媒体技术 流媒体口5l(StreamingMedia)是一种新兴的网络传输技术,在互联网上实 时顺序地传输和播放视/音频等多媒体内容的连续时基数据流,流媒体技术 包括流媒体数据采集、视,音频编解码、存储、传输、播放等领域。 一般来说,流包含两种含义,广义上的流是使音频和视频形成稳定和 连续的传输流和回放流的一系列技术、方法和协议的总称,习惯上称之为 流媒体系统;而狭义上的流是相对传统的下载回放(Download Playback)方式 而言的一种媒体格式,它能从Intemet上获取音频和视频等连续的多媒体流, 客户可以边接收边播放,使时延大大减少。 2.2.2流式传输方式 一般影音文件都较大,所以需要的存储容量也较大,同时由于网络带 宽的限制,下载常常要花数分钟甚至数小时,所以这种处理方法延迟也很 大。流式传输时,声音、影像或动画等各种媒体由音视频服务器向用户计 算机连续、实时传送,用户不必等到整个文件全部下载完毕,而只需要经 过几秒或十几秒的启动延时即可进行观看。当声音等各种媒体数据段在客 户机上播放时,文件的剩余部分将在后台从服务器继续下载,流式传输不 仅使启动延时成十倍或百倍地缩短,而且不需要太大的缓存容量。实现流 式传输【36】有两种方法:实时流式传输和顺序流式传输。 2.2.2.1顺序流式传输顺序流式传输是顺序下载,在下载文件的同时用户 可观看在线媒体,在给定时刻用户只能观看己下载的部分,而不能跳到还 未下载的部分。顺序流式传输不像实时流式传输在传输期间根据用户连接 11 燕山大学工学硕士学位论文 的速度做调整。由于标准的HTTP]]民务器可发送这种形式的文件,也不需要 其它特殊协议,它经常被称作HTTP流式传输。顺序流式传输比较适合高质 量的短片段,由于该文件在播放前观看的部分是无损下载的,这种方法保 证电影播放的最终质量。 Transfer 顺序流式文件时放在标准HTTP或FTP(FileProtoc01)J]艮务器上, 易于管理,基本上与防火墙无关。顺序流式传输不适合长片断和有随机访 问要求的视频,它也不支持现场广播,严格来说,它是一种点播技术。 2.2.2.2实时流式传输实时流式传输可以保证媒体信号带宽与网络连接 匹配,使媒体可被实时观看到。实时流与HTTP流式传输不同,实时流需要 专用的流媒体服务器与传输协议。 实时流式传输是实时传送,特别适合现场事件,也支持随机访问,用 户可快进或后退以观看前面或后面的内容。实时流式传输必须匹配连接带 宽,这意味着在以调制解调器连接时图像质量较差。而且,由于出错丢失 的信号被忽略掉,网络拥挤或出现问题时,视频质量很差。 2.2.3 流媒体播放方式 2.2.3.1 单播方式在客户端与媒体服务器之间需要建立一个单独的数据 通道,从一台服务器送出的每个数据包只能传送给一个客户机,这种传送方 式称为单播。在单播连接中,用户通过选择内容项目来初始化客户端连接。 用户可以开始、停止、后退、快进或暂停流。单播连接提供了对流的最大 控制,但是这种方式由于需要建立可靠连接,这样会迅速用完网络带宽。 所以这种方式的优缺点是:与用户的交互性强,但对网络带宽要求高,而 且响应需要很长时间,甚至有时会停止播放,管理人员也被迫购买硬件和 带宽来保证一定的服务质量。 2.2.3.2组播方式IP组播技术构建一种具有组播能力的网络,允许路由器 一次将数据包复制到多个通道上。采用组播方式,一台服务器能够对几十 万台客户机同时发送连续数据流而无延时。媒体服务器只需要发送一个信 息包,而不是多个;所有发出请求的客户端共享同一信息包。信息可以发 送到任意地址的客户机,减少网络上传输的信息包的总量。网络利用效率 12 第2章相关技术研究 大大提高,成本大为下降。 2.2.3.3点播和广播方式点播连接是客户端与服务器之间的主动的连接。 在点播连接中,用户通过选择内容项目来初始化客户端连接。用户可以开 始、停止、后退、快进或暂停流。点播连接提供对流的最大控制,但这种 方式由于每个客户端各自连接服务器,会迅速用完网络带宽。广播指的是 用户被动接收流。在广播过程中,客户端接收流数据,但不能控制流数据。 2.2.3.4几种方式的比较广播方式中数据包的单独一个拷贝将发送给网 络上的所有用户。使用单播发送时,需要将数据包复制多个拷贝,以多个 点对点的方式分别发送到需要它的那些用户,而使用广播方式发送,数据 包的单独一个拷贝发送给网络上的所有用户,而不管用户是否需要,上述 两种传输方式非常浪费网络带宽。组播吸收上述两种发送方式的长处,克 服了上述两种发送方式的弱点,将数据包的单独一个拷贝发送给需要的那 些客户。组播不会复制数据包的多个拷贝传输到网络上,也不会将数据包 发送给不需要它的那些客户,保证网络上多媒体应用占用网络的最小带宽。 2.2.4流媒体传输协议 流式传输的实现需要合适的传输协议。目前使用的流媒体传输协议【”1 Time 主要有:实时传输协议RTP(Real TransportProtoc01),实时传输控制协 Time Control 议RTCP(Real Time TransportProtocoO,实时流协议RTSP(Real Streaming Reserve ProtocoO和资源预留协议RSVP(ResourceProtoc01)。 2.2.4.1 实时传输协议实时传输协议提供具有实时特征的、端到端的数据 传送服务,可以用来传送声音和运动图像数据。它是专门用做支持多媒体 数据流传输的。RTP使用UDP装载数据在网上传输。它被用于以无确认方式 单向发送数据。每一个RTP数据报报头都包含使接收者可以恢复原始数据时 序的时间标记,描述了包的净载负荷的(Payload)性质,以及使接收方可以 处理丢失、重复或错误的数据报的顺序号。RTP既适合于向一个接收方f单 播),也适合于向多个接收方(多播)发送音频和视频流。 2.2.4.2实时传输控制协议实时传输控制协议RTCP是RTP的一个姊妹协 议,用来支持RTP协议功能。RTCP允许应用软件检测和调整网络中变化的 13 燕山大学工学硕士学位论文 Loads)。通过与Im结合,多媒体应用软件能够监视网络环 通讯量(Traffic 境参数并作恰当的调整。 一个RTCP消息有许多可堆积式分组(StackablePackets)构成,其中每个 分组均有自己的类型码和长度指示。RTCP消息格式与数据分组非常接近。 RTCP分组周期性地向接收地址发送报告。 2.2.4.3实时流协议实时流协议【3 的,该协议定义了一对多应用程序如何有效地通过Ip网络传输多媒体数据。 据。HTTP请求由客户端发出,服务器做出响应;使用RTSP时,客户端和服 务器端都可以发出请求,即RTsP是双向的。RTSP提供了一个可扩展的框架, 使实时数据的受控、点播成为可能,同时RTSP可以建立并控制一个或几个 时间同步的连续流媒体会话。 Control Messages Group Protoe01)和IGMP(IntemetManagementProtoc01)相 比,它是一个控制协议。RSVP的组成元素有发送者、接收者和主机或路由 器。发送者负责让接收者知道数据将要发送,以及需要什么样的QoS(Quality ofServe):接收者负责发送一个通知到主机或路由器,这样它们就可以准备 接收将要到来的数据;主机或路由器负责留出所有合适的资源。 2.2.5 目前流行的流媒体技术 网络上使用较多的流媒体技术主要有RealNetworks公司的RealMedia, Media Microsoft公司的Windows 是流媒体传输系统的主流技术。 2.2.5.1 RealMediaReal Media包括四类流媒体格式:RealAudio, RealVideo,RealPresentationa和RealFlash 4,分别用于传送不同的文件。Real Media采用SureStream技术,自动地并持续地调整数据流的流量以适应实际 应用中的各种不同网络带宽需求,轻松实现视音频和三维动画的回放。由 于Real 14 第2章相关技术研究 司和网上主要电台都使用RealSystemNt生界各地传送实时影音媒体信息以 及实时的音乐广播。 W‘mdowsMedia 2.2.5.2WindowsMedia 息流式播放方案,旨在Intemet和Imranet上实现包括音频、视频信息在内的 Stream 多媒体流信息的传输。其核心是ASF(AdvancedFormat)文件,ASF是 一种包含音频、视频、图像以及控制命令、脚本等多媒体信息的数据格式, 通过分成多个网络数据包在Intemet上传输,实现流式多媒体内容发布,因 此,人们把在网络上传输的内容就称为ASFS仃eam。ASF支持任意的压缩/ 解压缩编码方式,可使用任意一种底层网络传输协议,具有很大的灵活性。 2.2.5.3 Time Time是一个非常老牌的媒体技术, Quick Apple公司的Qick Time 它是一个开放式的架构,包含了各种各样或者非流式的媒体技术。Quik 在视频压缩上采用的是Sorenson Music Video技术,音频部分采用的QDesign Time电影文件格 QuickTime抽象层及QuickTime内置媒体服务系统。Quick 式定义了存储数字媒体内容的标准方案,使用这种文件格式不仅可以存储 Time媒体抽 单个的媒体内容,而且能保存对该媒体作品的完整描述。Quike 象层是一种综合性的媒体软件架构,它定义了软件工具和应用程序如何访 Time的关键 NQuickTime内置媒体服务系统,以及如何通过硬件提升Quick 性能。QuickTime内置媒体服务系统则可以作为软件开发工具的基础,帮助 Time的技术优势。 软件开发商和用户充分利用Quick 2.2.6流媒体缓存策略 流式传输的实现需要缓存。因为一个实时音频源或存储的音视频文件 在传输中被分解为许多数据包,而网络又是动态变化的,各个数据包选择 的路由可能不相同,故到达客户端的时延也就不同,甚至先发的数据包有 可能后到。为此,需要使用缓存系统来消除时延和抖动的影响,以保证数 据包顺序正确,从而使媒体数据能够连续输出。通常高速缓存所需要容量 并不大,因为通过丢失已经播放的内容可以重新利用空出的空间来缓存后 续尚未播放的内容。 15 燕山大学工学硕士学位论文 2.3本章小结 本章主要介绍作为P2P流式传输系统底层基础的P2P对等网络技术的应 用和现在主要面临的一些挑战,对认识P2P网络有一定的帮助;2.2节主要介 绍P2P流式传输系统中所涉及的另外一种核心技术—流媒体技术。在这一节 中,对流媒体技术、流式传输协议、流媒体技术当前的发展状况等作介绍。 16 第3章P2P流媒体系统底层网络及算法研究 第3章P2P流媒体系统底层网络及算法研究 P2P流媒体服务系统的底层基础是P2P对等网络,而底层P2P对等网络的 功能就是为系统提供流式传输的接口。深入研究这些对等网络中的算法对 P2P流媒体服务系统的设计有着很重要的作用,这些算法在特定的网络拓扑 结构中发挥它们的优点,同时也存在着它们的缺点,本章将会对这些对等 网络中的算法进行研究,并在研究的基础上提出自己的P2P流媒体服务系统 的底层网络拓扑结构,并提出相关的协议。 3.1 P2P网络基础设施 P2P基础设施是P2P节点得以相互协作的基础,一般指节点互联的拓扑 结构和节点在与相邻节点保持连接时的行为规范。P2P基础设施保证节点形 成连通的图结构,并在其上建立了特定的节点逻辑组织。所谓路由(搜索) 算法是指从一个节点出发,沿着节点之间的连接进行消息转发,最终到达 目标节点或实现路由目标(如搜索到所需数据)的过程。基础设施与路由算法 一般是一一对应的,特定的基础设施决定了它们之中所使用的路由特性和 搜索性能。 对于P2P流媒体系统而言,P2P基础设施决定了节点间互联的基本规则, 进而决定了搜索媒体数据和数据发送节点的方式和性能,因此,对于P2P流 媒体系统有着至关重要的作用。 3.2对等网络及其算法研究 3.2.1 节点搜索方式研究 资源搜索‘39】是P2P网络的基本问题,主要的解决技术方法有三种: (1)集中索引方式每一个节点将自身能够提供的共享内容注册到一个 或几个集中式的目录服务器中。查找资源时首先通过服务器定位,然后两 个节点之间直接通讯,例如Napster。这类网络实现简单,但往往需要大的 17 燕山大学工学硕士学位论文 目录服务器的支持,并且系统的健壮性不好。 没有任何索引信息,内容提交与内容查找都通过相 f2)RP时广播方式 邻节点直接广播传递,例如GnuteUa。一般情况下,采取这种方式的P2P网 络对参与节点的带宽要求比较高。 Hash (3)动态哈希表方式动态哈希表DHT一(DistributedTable)是很多 P2P网络所采取的资源定位方式。首先将网络中的每一个节点分配虚拟地址 VIDlⅣirtual Identity),同时用一个关键字(KEY)来表示其可提供的共享内容。 取一个哈希函数,这个函数可以将KEY转换成一个哈希值H(KEY)。网络中 节点相邻的定义是哈希值相邻。发布信息的时候就把(KEY,VID)Z元组发 布到具有和H(KEⅥ相近地址的节点上去,其中VID指出了文档的存储位置。 资源定位的时候,就可以快速根据H(KEY)到相近的节点上获取二元组 (KEY,Vm),从而获得文档的存储位置。 上述的节点搜索方式可以依据不同的P2P应用环境中进行选择,但是人 们普遍看好DHT方法。基于DHT的P2P网络在一定程度上可以直接实现内容 的定位。一个矛盾的问题是:如果一个节点提供共享的内容表示越复杂, 则哈希函数越不好选择,相应的,网络的拓扑结构就越复杂。 3.2.2集中方式的搜索算法性能分析 Napster系统【4l】是使用这种搜索算法的典型代表,是包含有中心索引服 务器最早的P2P文件共享系统。Napster采用了Web搜索引擎的集中方式的搜 索,而不是真正的分布式搜索,目PNapster是一个带有中央服务器的混合式 P2P网络。客户端下载文件或对外提供文件共享,而服务器端的主要目的是 为了建立当前所有在线的节点所存文件的目录索引,而不是存储文件本身。 节点每次连接到N印ster网络后将自己当前的IP地址、端口号、拥有的 文件及存放路径等信息发送到服务器,加入服务器的目录索引,这些信息 以后将用于和其它节点直接建立连接,对外提供文件共享。Napster的搜索 过程如下: Stepl:请求节点打开Napster应用程序,登陆中央服务器,并向其发送 文件搜索请求; 1It 第3章P2P流媒体系统底层网络及算法研究 SteD2:服务器端通过查找目录索引,看是否有与请求节点请求搜索相 匹配的文件信息; Step3:服务器向请求节点发送拥有该文件的所有节点的IP地址、端IS/ 号和存放路径等信息来响应请求节点的请求; ste甜:请求节点根据服务器所提供的信息,Ping每一台拥有所请求的 文件的提供节点,计算返回时间,与距离最短的提供节点直接建立连接, 开始下载文件。如果提供节点位于防火墙后,则请求节点通过服务器向提 供节点发送自己的IP地址和端口号,请求提供节点主动与请求节点建立网 络连,否则直接建立连接下载文件: Step5:下载文件完成后双方中止连接。 这种集中式搜索算法可以对请求的数据进行快速查找并能够返回最合 适的目的节点。实际的文件传输将在请求节点和提供节点之间通过TCP连接 of 直接进行。但是集中式搜索面临着信息量过载、拒绝服务攻击(Denial Service)等一些难题。 3.2.3纯分布式搜索算法性能分析 纯分布式搜索算法按索引结构的不同可以分为两类:严格结构索引和 自由结构索引…“。 3.2,3.1 自由结构索引算法性能分析这种算法只根据搜索历史对索引记 录进行适应性调整,应用前景广泛。使用该类方法的系统有GnutellaH2,431和 KazaAl44】等,其基本搜索原理分别为宽度优先搜索和深度优先搜索。这两 种算法鲁棒性虽强,但运行效率很低。扩散式的宽度优先搜索导致消息数 量呈指数增加,回溯式的深度优先搜索耗时过长。 构的P2P文件共享系统。Gnutella中每个节点维护了一个邻居表,记录了与 之相关联的节点的IP地址。Onutella主要支持三类操作:拓扑维护、文件搜 索和文件下载。 拓扑维护目的是通过在相邻节点之间彼此交换邻居节点信息来保持拓 扑图的连通性,并替换因节点离线而失效的连接。节点定期向邻居节点发 19 燕山大学工学硕士学位论文 送P堍消息,收到Ping消息的节点则回应一个Pong消息并附带当前所拥有的 邻居信息。收到邻居列表后节点按照一定规则进行邻居替换,保证自身具 有一定数量的有效邻居。当新的节点加入系统时(它起码需要知道系统中另 一个节点的IP地址1,它向系统已有的节点发送Ping消息而获得足够的邻居 节点,从而加入系统。 Gnutella中,每个节点共享一些文件,并提供基于文件名的本地查询操 作。它使用消息洪泛(Flooding)的方式搜索其它节点上的文件。发起搜索操 作的节点向所有邻居节点发送Query消息,而接至1]Query消息的节点进行本 地查询,并把查询进一步转发给自己的所有邻居。这一消息广播的过程重 复进行,直到满足一定的结束条件。为避免无穷递归,每个搜索消息都有 再被转发。另外节点对近期接收到的消息进行缓存,以避免重复处理同样 的消息。搜索操作结束后,发起搜索的节点会收到一些查询结果,记录了 满足条件的文件及其存放的节点IP。请求节点可从中选择一些合适的节点 来下载所需文件。 由于路由的不收敛性,Gnutella式的搜索又被称作盲目搜索仍lind Search)。这种搜索一方面无法保证在所需文件 se盯ch)或随机搜索(Random 存在时必然搜索到,另一方面则产生了大量无价值的转发消息,造成了严 重的网络负担。如何解决随机搜索的低效率和高带宽开销的问题一直是P2P 对等网络研究工作的热点。 使用集中式的服务器来提供文件监控和定位服务。但与Gnutella不同, KaZaA把加入系统的节点按照其能力分为两类,强节点(SuperNode)和普通 Node)。每个普通节点都隶属于一个强节点。当一个普通节点 节点(Ordhlary 启动KazaA程序时,它首先与某一强节点建立TCP连接,然后向这个强节点 传送它所共享文件的元数据。这样就允许强节点维护了一个关于所有隶属 于它的普通节点文件的数据库,包括了其从属的普通节点的文件标识和对 应的IP地址。于是,每个强节点就成为了一个局部的类似TNapster中心文 件目录服务期的中心节点。这样,KaZaA较好地利用了大规模P2P系统中的 第3章P2P流媒体系统底层网络及算法研究 节点异构性,按照一个两级的分层结构,让连接能力(带宽)强、计算能力 fcPul强和在线时间长的节点处于较高的层次,在系统维护和文件搜索中承 担更多的任务。每个强节点也是通过TCP连接一定数量的其它强节点。存在 连接的两个节点间周期性的交换强节点列表。KaZaA的典型设置中,每个 普通节点维护一个包括200个强节点的列表,而每个强节点维护包括上千个 强节点的列表。在这个列表中,每个节点对应的表项都包括一个时间戳, 当节点收到新的节点列表时,会把时间戳较为靠前的节点替换掉。 普通节点向其归属的强节点汇报的文件元数据包括:文件名,文件大 小,内容哈希值(HashValue),以及其它附属信息(这些附属信息可以用于关 键字查询)。文件内容哈希值是一个文件的唯一标识,如果对于某个文件的 下载任务失败,KaZaA客户端会根据内容哈希值自动搜索相同的文件。 3.2.3.2严格结构索引算法性能研究与分析在这类系统中每个节点都具 有虚拟的逻辑地址,并根据地址使所有节点构成一个相对稳定而紧致的拓 扑结构。在此拓扑上构造一个存储文件的分布式哈希表DHT,文件根据自 身的索引存储到哈希表中。每次检索也是根据文件的索引在DHT中搜索相 应的文件。生成文件索引的方法有三种:根据文件的信息生成的哈希值 (HASH)索引;根据文件包含的关键字生成关键字索引;还有根据文件的内 容向量索引,如PSearch。它们通过严格控制网络拓扑和文件存放位置,能 有效地检索到结果,同时保证搜索步数在O(109N)范围内(N为节点总数),实 现了可扩展性搜索,但搜索算法对节点的限制条件过多,需要严格控制网 络拓扑和文件存储位置,所以,它们更适合运行于企业内网。 (1)Chord它是美国麻省理工学院设计的一种分布式的可扩展的查找 和路由协议。在Chord[45埘l中,节点并不需要知道所有其它节点的信息。每 个Chord节点只需要知道关于其它节点的少量的“路由”信息。在由N个节点 组成的网络中,每个节点只需要维护其它O(109N)个节点的信息,同样,每 次查找只需要O(bgN)条消息。当节点加入或者离开网络时,Chord需要更 新路Eh信息,所以每次加入或者离开需要传递O(109N)*O(109N)条消息。 如果m是关键字和节点标识符的位数(采用二进制表示),那么每个节点 只需要维护一张最多有m个表项的称为指针表(FingerTable)的路由表。节点 21 燕山大学工学硕士学位论文 进行mod2“,s称为节点n的第i个指针,用n.finger[i].node表示,指针表中的 其它项的含义如表3-1所示。 表3.1Finger表中的标识符 Table3-1Identifiersin table finger 符号 定义 Finger[i].stan (n+21’1)rood2“,1《=ism .interval 【丘nger[i].statrt,fmger[i+1].start] node 第一个大于等于IL丘“8盯【I]start的节点 标识符环中的下一个节点:lin留erll].node oredecessor 标识符环中的前一个节点 图3.1中的节点3就不知道关键字l的位置,因为l的后继节点信息并没有 包含在节点3的指针表中。 图3—1 Chord中的数据组织结构 Dam slluctureinChord Fig.3-1 organization 当节点n不知道关键字k的后继节点时的解决方法为:如果n能够找到一 个节点,这个节点的标识符更接近k,那么这个节点将会知道该关键字的更 多信息。根据这一特性,n将查找它的指针表,找到节点标识符大于k的第 22 第3章P2P流媒体系统底层网络及算法研究 一个节点j,并询问节点j,看j是否知道哪个节点更靠近k。通过重复这个过 程,n最终将会知道k的后继节点。 (2)PastryPastryl45081是微软研究院提出的可扩展的分布式对象定位和 路由协议,可用于构建大规模的P2P系统。在系统中的每个节点都有一个唯 一的节点号nodeld。当给定一条消息和一个关键字时,Pastry节点将会把这 条消息路由到在当前所有的Pastry节点中nodeld和关键字最接近的那个节 点。Pastry考虑了网络的位置信息,它的目标是使消息传递的距离最短。距 离采用类似于IP路由的hop数的标量距离度量。每个Pastry节点记录在节点 空间中和它直接相邻的邻居节点,当新节点加入、原有节点失效和恢复时 通知上层应用。由于节点号是随机分配的,那么在节点空间中相邻的节点 很可能在地理位置上是分散的,或者根本就属于不同的组织。 在Pastry中,节点所记录的路由表如图3.2所示,Pastry系统中节点的路 由表采用的是4进制。Leafset记录着在标识空间中与节点距离最近的若干节 Table的第一行,记录的是第一位与该节点nodeld不同的点,第 点,Routing 二行记录着nodeld第一位与该节点相同,而第二位不同的点,以此类推。空 格代表系统中不存在符合要求的节点。 NodeId10233102 Leafget【SMALLER}LARGER 22 I l l 10233001 010233232 Rouiinn乜bI£ .0.2212102 1 .2—2301203.3.1203203 0 1.1.3012331_2.2302031-3-021022 1o_1.32102 10.3-23302 10-0-31203 102-0-0230102-1-1302102-2-23023 1023.0.3221023.1.0001023.2-1213 10233.0-011 10233-2.32 0 02331.2.0 2 l set Neighborhoo 10200230I }13021022l l I 02212102 l 3l 33213321 I 图3—2 Pastry节点数据组织结构 Data structureofnodesin Fig.3-2 organization Pastry 当系统规模为n时,只要不出现标识空间中连续的L/2(L是一个系统配置 参数,通常取16或32)个节点同时失效,那么,系统一定可以在O(109n)步之 23 燕山大学工学硕士学位论文 内,把消息路至1]nodeld与目标标识最近的节点。为了进行路由,nodeld和 目标标识被想象为以2b进制的数字串。每一次路由,节点都是在路由表中 找至1.1nodeld距离目标标识最近的点。具体做法是,如果本节点与目标标识前 串匹配长度为b位,那么系统将在该节点路由表中找至lJnodeld至少与目标匹 配b+l位的节点,如果没有找到这样的点,那么就去寻找同样匹配b位,而 且距离目标比本节点近(nodeld更接近)的节点,如果仍未找到,则本节点就 是目标终点。 Pastry系统中的每个节点都被分配一个128位的节点号。节点号用于在 节点空间中标识节点的位置。节点号是在节点加入系统时随机分配的。分 配策略是在节点空间中均匀分布。节点号可以通过计

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

本文链接:http://destinosmice.com/zhengjiaoshu/65.html