基于P2P的流媒体播放器的设计与实现

基于P2P的流媒体播放器的与实现 中国科学技术大学 硕士学位论文 基于P2P的流媒体播放器的设计与实现 姓名:梁荣龙 申请学位级别:硕士 专业:模式识别与智能系统 指导教师:朱明 20068>0501摘要 摘要 随着网络技术的迅猛发展和宽带的普及,越来越多的用户开始;络收看 秆矾、影等视频内容,流媒体服务已成为互联网运用中一个重要的部分。但 是 山于受到当训硎络和媒体服务器服务能力的限制,使得流媒体胀务只能在一 个小 ‘区域内摊“?』?的服务,如何扩展流媒体服务的服务能力利应用范刚已 成为肖 氚媒休服务? 个重要的彻究谍题。近几年来,随着基于层纠播的技术和 壤』处事服务 披术迅速发展.使得在流媒体服务中引入这些技术成为可 能。 本文提出了完整的仃点管理算法,结合网络拓扑信息,使节点尽量选择地理 位背州邻点提供数掘,使连续捅放所需要的网络带宽容易满足,并且减少大 量通过悄铡勺网络流量。 采川从名个节点获耿数据的方法来保证网络可用带宽达到获取数据的速率, 并减小节点失效的影响。提了完整的节点选择算法,数据分配算法,速率控制 算法使多个节羔工作,引入了节点错误处理算法和数据丢失处理算法,使系 统一有较好外错’:能。 枞枷宝【】 :支术荆 技术的优点,采用组播和相结合的混合模型, :投 减少了大’融’门例络流量。组橘叫以极大的减轻服务器及网络的负担, 杠 ?为?。分旧列用网络和主机资源,以减轻服务器力,提高服务能力: 火键:实卜流媒体,对等网络,组挢,拓扑发现,町用带宽测量 \ 】 。 . ’ ,.. \\. . . , , , 。、 .., . , 。。, . 、, 、 . ’. ? \‘’ ’ . / “ . ’ .‘ ,, , \, \, . : ,?, ,‘,导险 导论 .背景介绍 随着网的飞速发展,人们已经不再单纯的满足于页面,图像和声 音等平而媒体,而刊音视频等多媒体服务的需求越来越多。流媒体服务作为 互联 网卜一个重要的应用逐渐成为人们研究的一个重要课题。人们希望通过网络 也能 收名到直播节乩或者能将自己的节目共享,同别人一起观看。但是由于受到 当 训网络和媒川报务州&务能力的限制,使得流媒体服务只能在一个小的区域内提 腆仃限脓务,:、腋流媒体服务的服务能力和应用范围已成为当前流媒体服 务的个甄婴的删究课题 传统一蜒丁客户川务器模式的架构使得服务器的性能和刚络带宽成为瓶 颈,在扩展性方丽存在很大问题。而架构能解决系统的词、展性问题,每 个节点’在接收数据的同时能向其它节点提供数据,从而降低了服务器的负担。因 此在实时流媒体中采用架构使得火规模的应用成为可能。 .本文的工作 本文根抓 播技术羽 技术能点,采用绸播和相结合的混合 模型,征一个局域嗍内如果有多个节点在收看同一个节目,只需其中一个节点从 其’?予网获取数扼,然后将数据通过组播的方式发送子网内的其它节点,充分利 川丁川捕优冉,盱亡甘甑雨从其它子网获取数据,同时这些书点同样 咀】?【’? 例。提‖数据,因::.少了大量的网络流量。 提出完整的节点管理算法,节点管理算法考虑网络拓:、信启、,使节点尽量 能得到引刊地理位锚’相邻的节点作为邻居节点,这样使节点在选择提供数据的 节点州能选择到与地理位置相邻的节点,选择地理位置相邻的节点提供数据 可以 减少通过骨二硎的网络流量,同时从地理位置相邻的节点获取数据时,由于地理 位茸棚邻很近,节点之削的网络可用带宽一般较大,可以满足连续摇放数据需要 四带啦。 搜水能允分利』每个节点的资源,节点在获取数据的同州能向其它占点 提供数副,为保?获取的数据能供播放器连续播放,采用从多个节点获取数据的 力法柬保刖矧络可用带宽达到获取数掘的速率,并减小了节点失效对节点获取数 据的影?,为从多个节点获取数据,提出了完整的节点选择算法,数据分配算法, 坐率铃川钾池他多个节.川工作,钊对节点失效入了节点错误处理算法,针 州数‘“上火,入’数掘失处理:法,使系统有较好的容错性能。导论 .本文的组织 本文:节绷织为:第一章为背景介绍和本文:作;第二章为相关研究现状: 笫三章介绍网络可用带宽测量算法和网络拓扑发现算法:第四章详细介绍节点管 瑚算法;第章介绍节氧选择算法,数据分配算法,速率控制算法,节点错误处 理算法和数据丢失算法以及穿透网络地址转换技术;第六章为实验结果,验证容 错机制,数据分配算法,速率控制算法等的有效性;箢七章为对本文的工作 以及刊下~步丁作的展望。相关研究现状 相关研究现状 .流媒体技术综述 传统的流媒体服务大都是采用/模式,/模式中服务器的服务和处理能 力,以及靠近服务器的地方的网络带宽便成为制约流媒体服务能力和服务质量的 一个瓶颈,在网络中存在重复信息的传播。 和是针对/模式,为分散单个服务器的处理负担,并减 少网络中重复信息的传播,足/模式的一种扩展,适用于大文件的媒体服务,但 代价昂贵。 的思想是在原来申播路由转发的网络架构是础 上,在服务器或主机之间构造一个应用层的网络来实现某种应用。应用层组播的 指出了网络研究 一些算法属于 算法的范围。 的一个方向,即保持目前单播的、不可靠的报文转发机制,而通过在主 机和服务器之问构造应用层网络来支持新的功能。 组播模型是对基本的“币播、尽力发送”模型的一个重要扩充, 它把组播的主要功能都放在路由器上实现。组播算法的基本出发点足:在存 在多 个接收者的时,通过合并重复信息的传输来达到减少带宽浪费和降低服务器处理 负担的目的,在性能上可以大提高。在组播方面已经进行了大量的研究,但 由于组播在传输技术利管理上存在严重的问题,目前组播没有在 中得到普遍采用。 近年来基于的网络共享技术迅速发展,与传统的/模式的网络服务 相比,模式侧重利用客户端的资源,利用客户端的处理器资源和网络资源, 通过增加主机之间的自组织,提高应用的灵活性,降低服务器的负担,解决主机 一服务器模型中的单点故障问题,在刚络中每个节点都既作为客户端又作 为服务器为其他节点提供服务,在这种模式下可以充分利用资源,极大地减轻了 服务器的压力。 随着和 等技术的提出,出现了应用层组播 这样一个研究方向。它的主要思想是:保持原有的单播、 尽力发送模型,尽量不改变原来网络的体系结构,而主要通过增加端系统的功能 来实现组播的功能。由于对网络本身的改变很少,应用层组播具有很好的灵活性。 但是在带宽利用效率方面也无法和组播相比。应用层组播算法的设计中引入 了??的思想,但应用层组播的研究并不是?.研究的一个子 集。.. 组播技术 、视频会议、数据和资料分发、网络音频应用、网络视频应用、多媒 体远程教育等宽带应用都对网络的承载能力提出了挑战。采用单播技术构建的传 统网络已经无法满足新兴宽带网络应用在带宽和网络服务质量方面的要求,单播 传输是在发送者和每一接收者之间需要单独的数据信道。如果有大量主机希望获 得数据包的同一份拷贝时,每个数据都要复制多份并向每个接收点都发送一份, 这样既消耗了不必要的系统资源,又占用了网络带宽,带来延迟长、网络拥塞, 数据丢失等等问题。为保证一定的服务质量需增加硬件和带宽。 组播是利用一种将数据包从源传送到多个目的地,将信息的拷贝 发送到一组地址,到达所有想要接收它的接收者处。组播是将数据包尽最 大努力传输到一个构成组播群组的主机集合,群组的各个成员可以分布于各个独 立的物理网络上。 同单播相比,组播效率非常高,因为任何给定的链路至多用一次,可以节省 网络带宽和资源。在一个鲴播环境里,成百上千的组播应用用户和一个组播 应用 用户消耗的骨干网带宽是一样的,从而最大限度的解决目前宽带应用对带宽和网 络服务质量的要求。 组播能够有效地节省劂络带宽和资源,管理网络的增容和控青一销,大 大减轻发送服务器的负荷,从而高性能地发送信息。另外,组播传送的信息能同 时到达用户端,时延小,并且网络中的服务器不需要知道每个客户机的地址。所 有的接收者使用一个网络组播地址,可实现匿名服务,并且组播具有可升级 性,与新的和业务能相兼容。 在组播网中,每个组播组有惟一的组播地址,组播地址的范围是:,.. 剑...,但是地址...是保留的,它不能赋给任何群组。其它 的组播地址作为暂时地址被用户使用;组播数据包可以送到标识目的主机的组地 址,发送者不必知道有哪些组成员,它自己不必是组成员,对组成员中主机的数 目和位置也没有限制。主机不需要和组成员以及发送者商量,可以任意加入和离 开组播组;使用组地址,不必知道主机指定的位置,可以找到具有此组播地址的 任何资源和服务器,在动态变化的信息提供者中搜寻到需要的信息,或者发 布信 息到任意大小的可选用户群。 组播协议分为主机一路由器之间的组成员关系协、议和路由器一路由器之间的 组播路由协议。组成员关系协议包括可连网组管理协议。组播路由协议 分为域内组播路由协议和域间组播路由协议。域内组播路由协议包括?、 、等协议,域间组播路由咖议包括、等协议。同 时为了有效抑制组播数据在链路层的扩散,引入了 、等二 层组播协议。 在~个组播路由器建立路由,传送其组播群组成员关系信息之前,它必须确 定在本地网络上有一个或多个主机是否加入了某个组播群组。为此,组播路由器相关:究现状 和实现组播的主机必须使用互连网组管理协议来进行群组成员关系信息的通信。 消息被置于报文中传送。中定义了两种消息类型:主机成员询 问和主机成员报告。当某主机想要介绍某个组播流量时,它向本地的组播路由器 发送”主机成员报告”消息,告知欲接收的组播地址。组播路由器收到”主机成员 报告”消息后把该主机加入指定的主机组,并在设定的周期内向组播地址 . .发送”主机成员询问”消息。主机如果还想继续接收组播流量,必须发送 ”主机成员报告”消息。 建立并上上维护路由器直联网段的组成员关系信息。域内组播路由协议 根据维护的这些组播组成员关系信息,运用一定的组播路由算法构造组播 分发树避行组播数据包转发。域间组播路由协议在自治域之问发布具有组播 能力 的路由信息以及组播源信息,以使组播数据在域间进行转发。 虽然组播技术效率很高,但它在实际运用中却难以大规模运用,主要是 由于要求所有参加组播的端系统之间的路由器都必须支持组播功能,这给组 播的推广使用带来很大的困难。 .. 技术 是一种分布式网络,网络的参与者其享他们所拥有的一部分资源,包括 处理器资源、存储资源、网络带宽,参与者在获得服务的同时业可以直接外 提 供一部分服务。打破了传统的客户服务器模式,在网络中的每个结点的地位 都是平等的。 是非中心化的,网络中的资源和服务分散在所有结点上,信息的传输和 服务的实现都直接在结点之间进行,可以无需中间环节利服务器的介入,避 免了 可能的瓶颈。的非中心化特点,对系统可扩展性、健壮性都有益处。 在网络中,随着用户的加入,系统整体的资源和服务能力也在同步地 于、充,整个体系是全分布的,不存在瓶颈,所以可扩展性强。由于服务是分散在 各个结点之司进行的,部分结点或网络遭到破坏剥其它部分的影响很小。网 络一般在部分结点失效时能够自动调整拓扑,保持其它结点的连通性。网络 通常都是以自组织的方式建立起来的,并允许结点自由地加入和离开。 可以有效地利用互联网中散布的大量普通结点,将计算任务或存储资料 分布到所有结点上。利用其中闲置的计算能力或存储空间,达到高性能计算和海 量存储的目的。通过利用网络中的大量空闲资源,可以用更低的成本提供更高的 计算和存储能力。减少了对服务器计算能力、存储能力,网络带宽的要求,同时 因为资源分布在多个节点,实现了整个网络的负载均衡。 按拓扑结构有以下几种形式:中心化拓: ;全分 布式非结构化拓 ;全分布式结构化拓扑 ,也称作网络怫半分布式拓 。相关研究现状 是一种中心化拓扑的系统,它将文件查向与文件传输的分离, 有效地节省了中央服务器的带宽消耗,减少了系统的文件传输延时。中央服务器 保存着网络中所有活动对等计算机共享资源的目录信息。对等节点发出文件查询 请求,中央服务器返回符合查询要求的对等机地址信息列表。查询发起对等机接 收到应答后,对等节点直接从返回的对等节点获得数据。中心化拓扑维护简单, 发现效率高,能够实现复杂查询。但问题是与传统客户机/服务器结构相同,随 着网络规模的扩大,中央服务器会成为瓶颈,容易造成单点故障。 是一种全分布非结构化拓扑的系统,它没有索引服务器,采用 基于完全随机图的泛洪发现和随机转发机制。通过。值来实现控制搜索消息 的传输距离。能够较快发现目的结点,支持复杂查询,如带有规则表达式的多关 键浏查询,模糊查询。每一个节点既是客户机同时又是服务器,完全是对等的。 非结构化网络将重叠网络认为是一个完全随机图,一般不提供性能保证,但容错 性好,并受结点频繁加入和退出系统的影,但是查询的结果可能不完全,查 向速度较慢。但是随着鞋网节点的不断增多,网络规模的扩大,泛洪方式定位对 等节点的方法将造成网络流量急剧增加,浪费大量网络资源。由于没有确定拓扑 结构的支持,非结构化网络无法保证资源发现的效率,由于采用、泛洪、随 机或选择转发算法,搜索南径不可控,可扩展性较差。因此全分布非结构化拓扑 的系统面临发现的准确性和可扩展性两个问题。 完全分布式结构化拓扑网络采用分布式散列表,针对非结构化系统中 的随机搜索造成的不可扩展性,构造一个高度结构化的系统,使其如何能够有效 地查找信息。通过分布式散列函数,将输入的关键字惟一映射到某个节点上,然 后通过某些路由算法同该结点建立连接。不需要中心节点服务器,每个节点负责 一个小范围的路由,并负责存储一小部分数据,从而实现整个网络的寻址 和存储。网络中的各节点并不需要维护整个网络的信息,而是只在节点中 存储其临近的后继节点信息,减少了带宽的占用和资源的消耗。 列络还在 与关键字最接近的节点上复制备份冗余信息,避免了单一节点失效问题。 分布式散列表是一个出广域范围大量节点共同维护的巨大散列表。散列表被 分割成不连续的块,每个节点被分配给一个属于自己勺散列块,并成为这个散列 块的管理者。通过加密救列函数,一个对象的名字或关键词被映射为位或 位的散列值。 在技术中,络节点按照一定的方式分配一个唯一节点标识符,资源 对象通过散列运算产生一个唯一的资源标识符,且该资源将存储在节点标识 符与 资源标识符相等或者相近的结点上。需要查找该资源时,采用同样的方法可定位 到存储该资源的结点。】,都是分布式结构化对象定位和路由协 议。 是一种可扩展的分布式对象定位和路由协议,可用于构建大规模的 系统。每个结点分配一个位的结点标识符号,所有的结点标识符形成了 一个环形的结点标识符号空问,范围从到”.,结点加入系统时通过散列相关究现状 结点地址在位结点标识符号空间中分配结点标识符号。每个节点维护包 括有叶结点,路由表,邻居节点组成的表,消息通过路由表转发,每次转发到比 当前节点与目标节点的结点标识符号前缀相同位数更多的节点。 类结构能够自适应结点的动态加入/退出,有着良好的可扩展性、鲁棒 性、结点分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构, 可以提供精确的发现。只要目的结点存在于网络中总能发现它,发现 的准确性得到了保证。 类结构问题是的维护机制较为复杂,尤其是结点频繁加入退出造 成的网络波动会增加的维护代价。另外一个问题是仅支持精确关键 词匹配查询,无法支持内容/语义等复杂查淘。类结构与真实网络拓扑完全 脱离,使其在性能上并没有达到最好,造成资源利用不合理。 半分布式结构吸取了中心化结构和全分布式非结构化拓扑的优点,选择性能 较高的结点作为超级节点,在各个超级节点上存储了系统中其他部分结点的信 息,发现算法仅在超级节点之间转发,超级节点再将查询请求转发给适当的叶子 节点。半分布式结构也是一个层次式结构,超级节点之间构成一个高速转发层, 超级节点和所负责的普通节点构成若干层次。应用层组播技术 技术的基础上发展而来。其 应用层组播技术是在技术 基本思想是屏敝底层物理网络的拓扑绌节,将组成员节点直接白组织成一个逻辑 覆盖网络,并在应用层提供组播路由协议来构建和维护该网络,为数据传输提供 高效、可靠服务。它将转发树构建在应用层卜,两个主机实际的链路是底层的单 播路径。组播源查询组播路由表,获得子节点的单播地址,再分别打包、 转发,数据包通过相应的单播路径传输给予节点,子节点接收数据包后查询路由 表,再分别打包、转发,直到所有节点都收到数据包。查询、打包、接收和转发 工作都在网络终端主机的应用层上完成。通过在主机上安装相应的应用层组播软 件就可以实现广域网范围内的组播服务。和组播增加网络机制的方法不同, 应用层组播的基本思想是保持原有的简单、不可靠、单播的转发模型, 由端系统来实现组播转发的功能。 应用层组播算法假设网络中的带宽和转发资源是相对丰富的,而服务器的能 力是~个主要瓶颈。使用应用层组播会比组播消耗更多的带宽,但是和单播 方案相比,它还是可以有效的降低服务器的负载和减少带宽的使用。大多数参与 组播的端系统可以贡献出~部分资源用于组播的转发。上层应用对性能的要求并 不很苛刻,可以容忍报文的丢失和较大的延迟。 应用层组播的主要优势在于应用层组播便于实现和推广,它只需要改变端系 统,而不需要对路由器进行任何修改。其次,应用层组播便于针对特定应用进行 优化,可以针对不同的应用使用不同的实现方案,而不必像组播那样必须统一相关研,现状 到一个模型中。 应用层组播一般会比组播使用更多的网络资源,由于参与转发的端系统 可能不稳定,导致组播转发的可靠性受到影响,由于参与转发的端系统的性能无 法保证,可能导致延迟、转发速率等性能的下降。基于这些特点,前应用层组 播的研究主要集中于视频会议系统、媒体流的分发系统和订阅/分发系统等。应 用层组播的主要应用是实时的多媒体传输。一方面这利用了多媒体信息的性质, 即在传输链路质量下降的情况下,用户仍然可以利用收到的低速率的或者不完整 的信息,这适用于同一组播组中的多个用户可能接收能力不同的情况。而文件传 输等可靠传输则没有这样的性质。另 方面也发挥了组播上集中、空问上分 布的特点。 组播节点的组织方法主要方式有树,网和特定的逻辑结构。树的优点是实现 简单,维护的开销小,扩展性好。它的缺点是可靠性比较差,这主要由于树结构 时节点接收数据通路足唯一的,是单一故障点。而网和树的优缺点恰好相反,节 点一般有多个接收数据通路,可靠性比较高;但维护开销比较大,扩展性比较差。 在大组播组的应用巾一般使用树,而在一些中小组播组的应用中使用网。特定的 逻辑结构一般扩展性好,且不需要路由算法,但网络节点映射后所建立的逻辑结 构一般不能很好的利用网络的性能。 【用参与的端系统通过自组织形式和完全分布式的方 式构建一个覆盖嘲,再在这个网上以每个数据源为根各构造一个生成树。可 以对 每个数据源使用单独的生成树为针对每个数据源进行性能优化。 能通过适应网络的动态变化和应用层性能来优化覆盖网的性能。使用阀 可以提高组播组的可靠性,在其基础上可以进行多个生成树的构造,为提高系统 的可靠性,组播组的每个成员都维护一个所有组成员的列表,但也大大增加了系 统的开销,降低了系统的可扩展性,使这个方案只能使用在小规模多源组播组的 情况下。相对组播而言, 带来双倍的数据量和很大的时延。 是在一个数据源的情况,将接收者组织成为一层一层的簇,然 后在分层的基础上构建组播树,每一个簇中有一个头节点和附加头节点,头节点 负责监视簇中的成员节点,附加头节点负责向成员节点发送数据,大部分组成员 位于分层结构的底层,只和少量固定数目的节点存在联系,这样就大大降低了大 部分组播成员的处理开销。头节点的错误不会影响其他成员节点的服务连续性, 附加头节点离开时,头节点可以迅速选取另一个作为附加头节点。无论节点数如 何增加,组播树的节点度数是常数级,组播树的高度为“、,错误恢复只需 在一小部分节点中处理,不会影响源节点,节点加入过程迅速,维持簇结构的开 销很小,与节点数独立,由可以构建大规模的单源组播树,扩展性很好。 主要针对由于动态的加入和退出组播组,或者由于主机自身的 稳定性不能得到保证,在组成员之问同时维护多个组播树,利用算法把媒 体编码成个媒体流,同时沿多个组播树传播。组成员只要收到个媒体流中 的任何个,都可以完成解码。算法把原始的视频序列压缩成多位流,每相关研究现状 个流对应一种描述,都可以提供可接受的视觉质量。多个描述结合起来提供更好 的质量。该方法的优点是实现了对数据丢失的健壮性和增强的质量。其缺点是相 比单拙述编码,它在压缩的效率上受到影响,对网络带宽的浪费比较大。而且由 于在多描述之间必须加入一定的相关性信息,这进一步降低了压缩的效率,同时 维护多个组播树的开销比较大;在多路同时传送机制下,数据的同步可能是一个 问题。 .实时流媒体研究现状 /使用协议在用户之间传播控制信令,使用 类似于多点对多点的数据传播协议在用户之问传送媒体数据包。协议 的高度可扩展性、多点对多点的数据传输协议的高度稳定性。它的核心操作很简 单,每个节点周期性的同一部分节点交换数据可用信息,从一个或多个节点得到 可用的数据,同时向其它节点提供可用数据。这种方式简单,易于实现,不用构 建和维护全局的数据结构,『司时有效性很高,数据转发不是被限制在固定的方向, 而是根据数据的可用性动态决定的。节点之间的关系是自适应的,每个节点在多 个数据提供者问快速切换,所以系统鲁棒性很强。 是一种以接收端为驱动的实时流媒体系统,它保证每 个节点的负荷不会很大,节点之问保持松散的连接,一些节点被选择来缓存部分 数据。节点从多个节点获取数据,保证负载均衡,能适应节点的加入和退出。 是一种非结构化的实时流媒体系统,每个节点随机的选 取邻居节点获取数据,数据交换采用推和拉结合的方式,通过拉的方式获得数据, 呵以在抖动率很高的情况下也能:广作的很好,但是这种方式的延时很大,而通过 推的方法获得数据则可减小延时。 也是基于实时流媒体系统,通过推断底层网络的拓扑结 构,根据网络信息情况选取节点,监视节点之问的网络连接状况,包括节点错误 和节点之间的网络带宽降低等情况。能动态的实现节点切换,保证接收者的数据 的到达。但节点管理采用结构化的网络节点管理协议,使选择的邻居节点 未必是地理位置相邻的节点。删络测量与打扑发现 网络测量与拓扑发现 网络带宽是网络的很重要的参数,网络运营商需要了解网络带宽情况来指导 网络规划、瓶颈故障检测、拥塞控制、接纳控制以及异构无线网络的切换、性能 优化等。在系统中,需要根据网络状况即网络可用带宽来选择服务节点,并 在网络带宽变化的情况下及时调整服务节点。 在很多情况下都需要了解网络拓扑信息,在仿真方面,必须先获取网络的真 实拓扑情况后才‘能升始仿真;在网络管理方面,在获得网络拓扑信息的情况后才 能够发现是否应该添加新的路由器,是否当前的硬件配置的合理,还可以让网络 管理者了解网络中的错误和瓶颈;在选址方而,网络拓扑信息可以让用户知道在 哪里布置服务器,才‘能使网络延迟最小,网络可用带宽最大;在算法方面,拓扑 信息能使一些协议或算法在性能匕提高,例如对拓扑敏感的路由,组通讯 中对拓扑很敏感的组选择算法等。 本章介绍了两种测量网络可用带宽的典型算法和当前网络拓扑发现的各种 算法。 .网络可用带宽测量 端到端的网络容量的定义,假设发送端到接送端的报文通过同一条路,这条 通路的跳数为,每段链路的传输率或链路容量为.,则端到端的网络容量为 , , 冈此端剑端的网络容量定义为当网络中没有其它网络流量时所能提供的最 大传 输率。 假如在一段时问间隔,。,。内链路传输了“,,比特数据, /。,,表示链路在时问问隔。,,。的利用率,其中“,。,。, 链路的在时间间隔乇,内的可用带宽,被定义为链路的容量在时间 间隔,。,内末用的比例, 群 一“, 将这个概念扩展,端到端在问间隔的?丁用带宽被定义为链路中所有段的 最小可用带宽 一“,%, 网络测量与拓扑发现 因此端到端的可用网络带宽定义为在不减少链路中其它流量的传输速率的 情况 下链路能提供的最大传输速率。最小传输速率的链路决定了端到端的网络容 量, 最小为使用的链路容量决定了端到端的网络可用带宽。 目前测量网络可用带宽的算法可以分为两类,一种是基丁二的算法,另 一种是基于的算法。 ..基于的算法 是一种基于的算法网络用带宽的工具,假如发送端周期 性的发送报文流到接收端,报文流包括个报文,每个报文的长度为位,报 文的传输周期为,则流的传输率为/位侮秒。发送端在发送报文之前将发 送时间附在报文中,在接收端收到报文的时间为“,,接收端计算报文的相 对单程延迟为 ,一, 口是在发送端到接收端的绝对单程延迟加上或减去一个偏移量,为发送端和 接收端时钟偏差。绝对单程延迟为 四 肚喜告争善苦啪 其中表示在报文到达时链路的队列大小,不包括报文,彰等表示报 文在链路的延迟,和报文的绝刘延迟差为 ?:,一:兰譬:兰?露 其中‘,,。 在接收端,根据每个报文的相对单程延迟来判断数据传输速率是否大于删络 可用带宽。当数掘传输速率大于网络可用带宽时,‘,数据包将在网络可用 带宽最小的链路发生短时间的过载,如图所示:网络测量与拓扑发现 翔 图传输速率大于网络可用带宽 在过载的这段时间内,网络可用带宽最小的链路接收到的报文将不能够全部 及日 的转发出去,因此如果报文在网络可用带宽最小的链路延迟队列中,则它的 队 列延迟将比报文的队列延迟火。因此当传输速率大于网络可用带宽时,包 序列的相对延迟序列.,,??,将出现增长的趋势。 另一方面,如果传输速率小于端到端的可用带宽,,流将不会在网络 可用带宽最小的链路引起过载,随着报文的增加不会造成积压,因此当传输 速率 小于可用带宽时,包序列的相对延迟序列日.,??,将不会出现增长的趋 势。如图?所示: 图传输速率小于网络可用带宽 因此可以采用迭代的方法测量端到端的网络可用带宽,发送端按照速率 发送流到接收端,接收端单程延迟的变化,根据决定是否火于网络 可用带宽,如果大于网络可用带宽,发送端调整流的发送速率,使 小于,否则使大于,具体的 ,?烈;络测量与拓扑发现 ,““; ”“??/; 一,?是在发送流后网络可用带宽的上下界,初始状况下,??, ?“为大于网络可用带宽的一个值。算法在?、一””时中止,国为用户指 定的测量精度,如果在测量时间内网络可用带宽不变,发送“。”’次流后网络 用带宽将汇聚在『?,一。但是在真实的网络情况下,网络可用带宽在测 量时问间隔内可能是变化的。 在中,发送报文的周期和报文的大小是两个重要的参数,流 的传输速率为 / 、 先确定后,再选择和,的大小不能小于一定的值,电不能人于链路的最 大传输单元以防止被分段,太小可能在链路层被填充修改,引起传输率的改变, 冈此一般的大小选择从字节到最大传输单元,并且为的倍数以防止填 充。另一方面,传输时间周期应尽可能小,如果传输时间周期增加,每个流的 持续时间也会增加,理想情况下每个流的传输持续时间应该在端系统存被下文 切换之前结束。传输时间周期小,整个测试过程的时间也会减小,最小传输时问 周期取决于端系统的硬件和操作系统,一般取为。流中报文个数的选择 存在一个平衡问题,如果报文个数太多,报文在发送速率大于网络可用带宽 的情况下可能会引起带宽最小链路处队列充满,从而造成网络拥塞和报文丢失, 但如果报文太少,则提供给接收端的信息过少,接收端没有足够的采样,很难判 断单程延迟是否有增长的趋势。一般取,在这种情况下流的长度很少引起 报文丢失,同时也提供了足够的信息去判断单程延迟是否有增长的趋势。 在如何判断单程延迟的增长趋势时,在一路具体的流中,将报文分成【 个组,计算每个组的单程延迟中值。,再分析集合‘,,?.,,这 样使得鲁棒性更好。然后通过两个指标来衡量增长趋势,第一个指标是单程 延迟 对的增, 。。?‘“/一 如果‘“,则。“】,否则。”。计算连续的单程 延迟对的增长比例,因此。,。如果单程延迟是独立的,则。。的期望值 为.,如果呈现很强的增长趋势,。。将达到。当。,时,认为出现了 网络测量与拓扑发现 增氏趋势,当昌?.时,认为未出现增长趋势,其余情况则处丁二未确定状态。 第二个指标叫成对差别探测 /?』‖“ 量化开始部分和结束部分的变化相对于整个流的变化情况,.。。,如 果单程延迟是独立的,。的期望值为,如果呈现很强的增长趋势,。,,将 达到。当。.时,认为出现了增长趋势,当。.时,认为未出现增 长趋势,其余处于未确定状态。如果两个指标都表明出现了增长趋势,则认为 发 送速率大于网络可用带宽,如果两个指标都没有表明出现增氏趋势,则可判 定发 送速率小于可用带宽,如果两个指标呈现不同状态,则去掉这路流的数据。 不是跟据单独的一路流来判断发送速率是否大于网络可用带宽,而 是通过发送路流来判断发送速率是否大于网络可用带宽。所有的流发送速率 都为,在前一路流被通知后才‘能够发送一卜一路流,所以两路流之间有时问 问隔 ?,这个时间间隔?至少大于链路的往还时间,总的发送持续时间为 ??,当和?确定时,决定整个持续时间,默认取。 如果有%的流都呈现增长趋势,或者都末呈现出增长趋势,则可判定发送速率 是否大于网络可用带宽,否则为灰色区域,不能判定是否呈现出增长趋势。 速率调整算法,?表示在一定阶段后网络可用带宽的下界限的最大值, ?“表示在一定阶段后网络可用带宽的上界限的最小值,即月一,?“是在发送 流后网络可用带宽的上下界;?“表示不确定区域中的最小速率,“表示不 确定区域巾的最大速率。因此??,?。】表示不确定区域包含的最大范罔。当 月?“、一只”“唧时,或?一?且一一?时,用月?,胪“估计网络 可用带宽。算法描述如下: / / :?“?“。“““/ ”洲月删”/????????????????????篁塑里兰堑盐垄型 ”” ““/ ?、月””/:一?、刚 ?孙; 。月一/; ?“ “?;“?/; ?趴一洲”一??.“,月?“; ?一兰,,刚,如网络可用带宽为时 测量时间大概需要。 ..基于的算法 是一种基于算法的测量网络可用带宽的工具。基于包对的测量 网络。‘用带宽的方法是通过发送一系列连续的报文,测量通过网络后的报/: ,报文通过网络时,网络中的其它流量会插在报文中,造成问隙的增加。 在接收端的间隙值将和网络流量有一定函数关系,可以用来计算网络流量。 但是 间隙值和网络流量的关系很复杂,如图所示: ???? 一 口圆圆亩圃 盎蕊卜忡 嘎?皿??卿??,?““一““““ 图 竞争报文利探测报文交叠 。表示报文和报文离开路由器的间隙,表示报文到达路由器时路由 器输出队列的大小,表示和报文到达之间的网络流量,譬表示和 报文到达路由器的问隙,。为瓶颈、口隙,是报文在输出队列的传输延迟,也 是相邻报文在瓶颈链路的间隙,,表示链路容量。网络测量与拓扑发现 如果和报文到达路由器的时间处于同一个排队周期,区域被称为, 如果和报文到达路由器的时问处于不同排队周期,区域被称为,如 图所示。在区域中,报文将遇到空队列,此时输出间隙。?/皖, 在报文到达时,需要处理队列/处理。,处理两个报文之间到 达的网络流量芝,/,,所以/,矾眈/,璺时报文刁‘会遇到空队 列,即图中的三角形区域。其它情况下,和报文将处于同一排队队列『, 这时输出间隙由两部分组成,处理报文。,处理两个报文之间到达的网络 流量 ,/,所以。‰皖,/皖,在这个区域中,输出间隙足网络流量的 图单跳模型 函数,可以用这利方法得到网络流量,进而求得网络可用带宽,但如果包对操 作 落在区域,输出间隙将和网络流量没有关系。 通过发送包序列的方式来测量网络流量,假如个报文间隙是增加的,间 隙值为那,.,, 个报文间隙未变,问隙值为?.,, 艮隙值减小,间隙值为一。.,,则在报文探测期间网络流 州州 量为吃?一孙,??矿?『为探测时间,所以报文探测期问网络 仁 』 流量所占用的网络带宽为 ,?矿一踟/??百?酊 这个公式称为公式,必须保证是在区域,需要控制三个重要的参 数,报文的大小,网络流量和报文初始间隙。小报文易受干扰,取报文大为小网络测量与拓扑发现 。由于网络流量是突发式的,短时问的测量结果不足以得出平均网络流量, 需要发送大量的报文,但如果报文太多,将造成队列充满,报文丢失,增加网络 负载,取报文数为。报文初始间隙是一个重要参数,增加间隙将很容易掉进 区域,使得输出间隙和网络流量独立,两者之间没有关系。需要较小的输 入间隙,但如果孙,虽然不在区域,瓶颈链路将被堵塞,引起数据包 丢失。通过采取逐步增加输入问隙的方法,开始会造成堵塞,不能得到网络可用 带宽的信息,当输入间隙达到。,除非网络空闲,在瓶颈链路仍然有网络堵塞, 输出间隙将大于输入间隙,继续增加输入涮隙,到达某一点,探测报文发送速率 将和网络的可川带宽相等,输出间隙将和输.隙相等。 所以当输入间隙和输出问隙相等时,可以估计网络可用带宽。算法描述如下: : 产 / ; ; 口; 月;口; ??一; ??;. ?, ?; ? 。; ,, ; ?; / 严 ?~?; / ~? ? ; ~逻缸; ?为网络可用带宽,为网络容量,?为竞争带宽, 计算输出间隙的总和,‘计算瓶颈间隙,??计 算比瓶颈间隙。大的输出间隙的总和,?判断输出间隙利输入间隙 是否相等,当 』塑:竺里:.:坐:里 ?, 时返回,否则返回。网络测量与拓扑发现 .网络拓扑发现 ..拓扑发现的基本工具 目前网络拓扑发现的基本工具有/ ,和。 报文时,需要回应一 / 是当每个主机当收到 个 报文到探测主机,如果探测主机收到响应报文,则所探测 的主机在线。能精确的发现目标主机是否在网络中,并且这种发现方式的 网络负荷很小,如果主机在线,仅需一个往还时间,一般情况下为十几毫秒就可 以收到响应报文,但如果主机不在线,则至少需要二十毫秒的超时时问,因此探 测不在线的主机不销很大。还可以刘一个子网内的所有主机进行探测,将地 址的主机部分设为全或全,子网内的所有在线的主机在收到广播探测报文时 都会回应一个响应报文,但在有的网络中只有路由器会发送一个响应报文,甚至 有的网络中所有的主机都不会发送响应报文,主要防止恶意的用户伪装别人发送 大量的广播报文,造成其它主机被大量的广播响应报文淹没。用来发现网 络拓扑是一种不可靠的方法,有的路由器或者防火墙禁止报文通过,有的 主机在收到 报文时也不会发送响应报文,造成这种方法的失效。 可用来发现源主机到目标主机之间的路由器。主机每次将值 增大,在每经过一个路由器时将被减,如果路由器发现已为,则路 消息,否则将报文转发下一跳路由器。 由器会向源主机发送? 这样使得源主机到目标主机之间的路由器都将源主机向发送? 消息,从而获得所有的路由器。因为几乎所有的路由器设计时都实现了发送 ? 消息的功能,所以大多数情况下的结果是准确可信 的。由于采用逐渐增大值的方法,探测一个目标主机需要依次发送不同 值的多个探测报文,因此用获取结果比要慢的多,并且给网络 带来的负荷也比大。可以设计一种并发式的命令,一次发送不 同值的多个包,从而加速路由器的发现速度,但是有的网络提供商将路由 器对进行隐藏,使得这种方法失效。 服务器将自己所在域内的主机的名字和主机的地址绑定,使得主机 的名字和主机的地址可以相互查渤。许多服务器提供了区域传输命令, 服务器收到区域传输命令时将返回域内的一系列主机的地址。区域传输命令 对于 查找域内的所有主机和路由器非常有用,这个命令给网络带来的负荷很小, 并且 迅速,但可能没有返回域内所有的主机。服务器提供的信息可能与实际情 况不一致,甚至有些服务器没有提供区域传输命令。网络测量与拓扑发现 ..网络掩码长度猜测算法 当给定地址,需要猜测地址的网络掩码睦度,思想是发送网络掩码长 度为的广播报文,当收到一个响应报文时,则此时的就 是地址的网络掩码长度,如果没有收;应报文,则减小的值,继 续发送发送网络掩码长度为的广播报文。算法描述如下: 一 . . 以和结尾的两个广播报文都需要发送的原凼是为了防止出现以下错 误,当猜测地址为...的网络掩码长度时,真实的网络掩码长度为 位,如果只发送以结尾的广播报文,则当为时,发送 的广播报文为...,发送后会收到响应报文,这时将误认为网 络掩码长度为。但如果同时发送以结尾的广播报文,将不会收到响应 报文,可以得出网络掩码长度不是,将避免得出错误结论。这个启发式呵以 用在支持广播的子网,虽然它是精确的,但它发送一系列的广播包,使得 发现过程较慢,给网络带来的负载较大。 ..子网的网络号猜测算法 通过一群地址来猜测子网的网络号,假定知道子网内地址为,, 的主机,和子网相连的路由器与子网相连的接口地址为,启发式的目标是确 定 主机所在子网的网络号。由于,,和在一个子网内,此有相同的 网络前缀,将,,和进行位与,所得到的结果作为网络号的近似值。 假如路由器的地址为...,主机的地址为..., ...,...,前三个字节完全一样,只处理最后一个字节, 将所有地址进行位与运算,所得到的结果为,然后将所有地址进行位 或运算,所得到的结果为叭,因此地址的最后五位必定为主机字节部分, 所以子网号有可能为,,,四种情况。如果只有这几个地址,将没办法 作进一步的判定,但如果又发现一个地址为.. .的主机,则位与的结果 为,排除了,,三种情况。这个启发式能够用于任何域内,它 带来的负荷小,如果地址分布均匀,得出的结果将很精确,但当所有的地 址分布在高端时,这种启发式将得不到精确的结果。网络测量与拓扑发现 ..网络拓扑发现算法 目前网络拓扑发现主要有以几种算法: . 这个算法很简单,它假定在任何地方都可用,先将与发现主机所在予 网相连的路由器地址加入到临时集合中,然后对临时集合中的每一个路由器, 通 过找出其相邻的路由器,主机可以从路由器的表中得到。算法 拙述如下: . ....? .?. 这个算法快速,有效,完全,准确,但它必须在所有的路由器都支持的情 况下才‘能使用。 .区域传输命令和广播 这个算法假定区域传输命令和广播都可用,首先用区域传输命令获取 到一系列域内的主机,然后验证返回的主机是否有效,最后确定域中的所有 子网。 通过的方法验证主机的有效性,用广播启发式算法确定网络中的所有 子网,最后为发现区域传输命令中没有返回的主机,向每个发现的子网发送 广播 ,然后将收到的向应主机加入临时集合巾,算法描述如下: . ? . .? . .? ? . .? ?? ?? ‘ 这个算法既不有效,也不快速,因为广播启发式算法速度很慢,且引入了 较大的负荷,更重要的是算法依赖区域传输命令和广播时可用,由于安 全原因很少的情况下两者能够同时可用。网络测量与拓扑发现 .区域传输命令和 这个算法假定区域传输命令可用,将返回一系列域内的主机和路由器,还假 定区域传输命令返回路由器所有接口的地址,而不是随机的返回其中一个地 址。 基本的思想是区域传输命令返回一系列域内的主机和路由器,在启发式中需 要 知道路由器的地址,主机通过,很容易发现路由器与子网相连的接口的 地址,但有的路由器不是返回与子网相连的接口的地址,这时需要先通过一个反 向的名字查询,得到的路由器的所有地址。用路由器的所有地址与其它主机进行 异或,结果中拥有最小位的接口就是与子网相连的接口的地址。对每个接口维持 两个哈希表,一个保存与所有主机地址的位与结果,另一个保存与所有主机地址 的位或结果。随着越来越多的主机地址被处理,位与的结果将越来越接近网络号, 由网络号和位或表能快速的决定子网掩码,算法描述如下: . . . ? .?.?.? . ?、?? . . ?. ? . . ..’.这个算法比前面一个算法快,负载更小,因为在子网猜测算法上效率更高,因此 比前面算法应用场合更广,这个算法的问题是当所有主机的地址都分布在高端 时,将得不到正确的子网号,同时还假定查询会返回路由器的所有地址, 在有的域不是路由器的所有地址都在中。 .骨干网络拓扑发现 骨干网络的拓扑发现与在一个域内的拓扑发现完全同,在一个域内,能用 区域传输命令和广播发现大量的主机,在骨干网中,最有可能的电是最好网络测量与拓扑发现 的方法便是通过来发现路由器和链路。最初的方法是在地址空间中产 生分布均匀的地址,对每个地址进行,保存返回的结果.最 后用结果分析拓扑情况,这种方法的问题是依赖于探测的地址选择,并且代价昂 贵,并目.只能发现‘部分骨干网络。解决的办法是减少探测的主机,在表中 保存了一个域内与骨干网相连的大量的主机地址,通过随机选择一个域内的主机 发送探测报文,能发现大量的路由器和链路。算法描述如下: ?.. . , .... , ...,. . ..这样减少了探测主机的个数,但它只能发现从探测源到各个域的路由器和链路, 对各个域之间的路由器和链路信息则不能获得,解决的办法是从多个源司时进行 探测。虽然这个算法不能找到所有的路由器和链路,除非在每个域内都有一个探 测源,但是如果探测源分布的很好的情况下,将得到’胃‘干网络拓扑很好的近似。节点管理算法 节点管理算法 节点管理算法是网络中的‘个重要问题,本章详细阐述了节点管理算 法,包括服务器节点的节点管理,头节点的节点管理和普通节点的节点管理,节 点管理算法以每个节点都能找到与自己地理位置相邻的节点为设计目标。节点分 为服务器节点和~般节点,一般节点又分为头节点和普通节点。三种节点的节点 管理算法不同,普通节点通过头节点获得邻居节点,而头节点则先从服务器节点 获得一部分邻居节.,再从这些邻居节点那里获取更多的邻居节点,是一种基 于 协议的节点管理算法。 .服务器节点的节点管理 一般节点通过以下格式和服务器节点进行节点信息的交互,其中表示 ?? .. ; ? ../; ; 交互的类型,当等于??时表示一般节点到服务器 节点的请求报文,通知服务器节点返回请求节点的邻居节点;当等于;表示一个子网内头节点退出,所在子网内的一个普通 节点成为头节点;当等于.一时表示一个节点发现邻居节 点已经失效或者子冽内的头节点在退出前主动向服务节报告将要退出系统;当 等丁:?表示节点将直接从服务器节点获得数据;当 等于??时表示普通节点要从一个处:防火墙内部或者 通过网络地址转换连入网络的节点获得数据时,这时不能直接和这种节点建立连 接,需先向服务器节点发出请求,由服务器节通知节点同时向请求节点建立连 接,这样两端才能开始通讯;当等于 时表示服务器节 点通知某个节点有其它节点想和它建立连接。 表示报文中节点地址的个数,即中的前几个地址有效,如假如 等于,则,为有效的节点地址。 表示节点的地址,当等于 时,地 址为普通节点的本地地址;当等于一时,地址为 子刚内的头节点的地址;当等于??时,地址为将要退出 的节点地址;当等于?时,地址为将直接从服务器 节点获得数据的节点的地址;当等于?时,地址为需节点管理算法 时,地址为请求连接的 要连接的节点的地址;当等于 节点的地址。 服务器节点维护一个链表,链表记录了当前在线的所有子网内的头节点的信 息。链表元素的结构如下: ; ? ; ? ; ; ; ; 受 ; 其中,指针指向链表的下一个元素。 ?是节点的全局地址,为解决全局地址紧缺的蒯题,出现了 技术,是十把内部私有网络地址转换成全局地址的技术,在局域网 中的主机使用内部地址,当主机要与外部网络进行通讯时,在网关处将内部 地址 替换成全局地址,从而在外部网络中正常使用,其它主机看剑主机的地址是