（计算机应用技术专业论文）数据驱动的p2p流媒体直播系统数据调度研究.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者：囊丕摩 日期：矽年 h e a d p a c k 中，是数据对象则进行数据包的拆分。当一个新的普通节点加入 系统，首先要获得报头对象，再根据当前播放位置，请求相应的数据对象。 报头对象数据对象 h e a d h e a d d a t a h e a d d a t a p a c k e t 图2 7a s f 流媒体文件格式 数据对象( 数据包) 包括数据头对象和数据部分，如果进行如图2 8 所示 的拆分，将整个数据包按照s i z e 大小进行均分，会造成接收数据过分依赖第一 个数据分片，如果第一个分片丢失，则整个数据包就无法恢复。针对这样的问 题，我们设计了新的分包方案，如图2 9 所示，将数据包中的数据头对象进行 封装，大小为1 2 字节，将数据包的数据部分按照( s i z e - 1 2 ) 大小进行均分，获 得数据分片，然后为每一个分片加上数据头对象，这样每个数据分片都包含数 2 1 p 2 p 流媒体相关技术 据包的头对象，地位是相等的，消除了对第一个数据分片的依赖，其中个别数 据分片丢失，不影响数据包的重组。因为这个头对象很小，只有1 2 字节，所以 不会增加很多的传输数据量，是可行的。 数据包 数据分片 图2 8 数据对象拆分 t 数据包 数据分片 1 图2 9 数据对象拆分改进 ， ( 2 ) 数据分片的传输 系统中各个节点间的交互控制信息是通过r t c p t c p 协议进行传输的，保证 控制信息的准确接收。其中控制信息包括节点的加入、退出、邻居节点的更新、 k e e p a l i v e 等信息。流媒体数据采用r t p 协议传输，数据包在发送端经过r t p 2 2 p 2 p 流媒体相关技术 封装，加入时间戳( t i m es t a m p ) 和序列号( s e q u e n c en u m b e r ) 等信息，然后 交给u d p 层进行传输，在接收端以相反的顺序处理。系统中利用开源的j r t p l i b 库实现流媒体数据的传输，具体使用过程包括： ( 1 ) 。j r t p l i b 库的编译 j r t p l i b 是一个开源的r t p 库，j t h r e a d 是歼源的线程类，如果没有j t h r e a d ， j r t p l i b 也可编译通过( 需更改r t p c o n f i g _ w i n h 文件中r t p s u p p o i 玎j h r e a d 参数) ，j r t p l i b 中需要程序周期调用相关的函数来获取数据。j r t p l i b 的编译步骤 如下： 1 ) 释放j r t p l i b - 3 6 0 ，j t h r e a d - 1 2 1 z i p ，将j t h r e a d 1 2 1 释放在j r t p l i b - 3 6 0 下； 2 ) 将j t h r e a d h 和j m u t e x h 这两个文件加入到j r t p l i b - 3 6 o s r c 中； 3 ) 将j r t p l i b 中文件中所有包含j t h r e a d h 和j m u t e x h 的程序，都改为# i n c l u d e j t h r e a d j m u t e x h ，： 4 ) 对j t h r e a d 和j 却l i b 工程，在p r o j c c t - s c t t i n g s - c c + + - c o d eg e n e r a t i o n ：u s e r u n - t i m el i b r a r y 中，对于d e b u g ，选择：d e b u gm u l t i t h m a d e dd l l ： 5 ) 编译j t h r e a d 一1 2 1 和j 却l i b - 3 6 0 ，生成j t h r e a d 1 i b 和j r t p l i b - 3 6 0 1 i b 。 对系统中的编译和执行的步骤： ， 1 ) 新建工程，将l s t r e a m 系统文件和j r t p l i b d s w 工程中的所有头文件都加入 工程中； ； 2 ) 将编译生成的j r t p l i b 1 i b 和j t h r e a d 1 i b 拷贝到v c 库文件目录中； 3 ) 告诉编译器使用指定的库，在文件前面增加语句： 4 ) 编译，执行。 ” ( 2 ) 发送 ， 发送流媒体数据的主要流程是：获得接收端的m 地址和端口号，创建r t p 会 话，指定r t p 数据接收端，设置r t p 会话默认参数，发送流媒体数据。 系统定义r t p s e n d h 类，包括函数：r t p s e n d l n i t o 、r t p a d d d e s t 0 ，负责r t p 数 据的发送。数据发送过程如下： p 2 p 流媒体相关技术 首先生成r t p s e s s i o n 类的实例，调用c r e a t e ( ) 方法来对其进行初始化操作。 设置恰当的时间戳单元( 调用r t p s e s s i o n 类的s c t t i m e s t a m p u n i t 方法) ，并且 设置好数据发送的目标地址，r t p 协议允许同一会话存在多个目标地址， r t p a d d d e s t 函数通过调用r t p s e s s i o n 类的a d d d e s t i n a t i o n 0 、d e l e t e d e s t i n a t i o n ( ) 和c l e a r d e s t i n a t i o n s 0 方法来完成地址的添加、删除和清除。目标地址全部指定 之后，调用r t p s e s s i o n 类的s e n d p a c k e t 0 方法，向所有的目标地址发送流媒体数 据。 ( 3 ) 接收 流媒体数据r t p 接收的主要流程是：获得用户指定的端口号，创建r t p 会 话，设置接收模式，接受r t p 数据，检索r t p 数据源，获取r t p 数据，删除 r t p 数据。 r t p 数据报有三种接收模式( r e c e i v e m o d ea l l 、r e c i 邑i v e m o d e i g n o r e s o m e 、r e c e e m o d ea c c e p t s o m e ) ，每种接收模式具体规定了 哪些到达的r t p 数据报会被接收。通过调用r t p s e s s i o n 类的s e t r e c e i v e m o d e 0 方法可以设置接收模式，本系统采用r e c e i v e m o d ea l l 缺省的接收模式， 所有到达的r t p 数据报都将被接收。 系统定义了类r t p r e v c v h ，包括函数r t p r e v l n i t o 、r t p a d d s o u r 0 ，负责r t p 数 据的接收。数据接收过程如下： p 2 p 流媒体相关技术 2 5 数据调度相关模块分析 ( 1 ) 基于b u f f e rm a p p i n g 的多级缓存 p 2 p 流媒体直播系统中p e e r _ 1 2 的缓存机制和替换策略对系统的整体性能会产 生很大影响，通过节点的缓存机制，可以使节点保持较平衡的整体网络负载， 提高网络实时传输效果，保持数据接收的稳定性。l s t r e a m 系统采用二级三缓存 方案，如图2 1 0 所示，设计三缓存，一级缓存由接收缓冲区构成，从其它结点 获得数据分片、对分片进行排序；二级缓存由转发缓冲区和播放缓冲区构成， 负责向其它结点转发数据分片、本地流媒体播放。 图2 1 0 缓冲区设计图 系统中，源节点通过编码器获得视频数据，然后将数据分割成大小相同的分 片，转发给请求节点。请求节点将分片重组成视频数据，用于播放视频，所以 节点用于转发和播放的数据包是不一样的，将其分开设计是很必要的。这样设 计还带来一个好处：转发的替换策略不受播放位置的影响，也就是说转发缓冲 区可以将没有播放的数据给替换掉，因为播放缓冲区里已经有对应的数据。系 统中用t r e e - p u s h 和m e s h p u l l 相结合的传输策略，在t r e e p u s h 这种策略下， 为了使接收端接收到的数据尽可能的减少乱序，发送端采用有序发送。视频数 据进入播放器必须是有序的，否则就无法还原原来的画面，所以需要一个接收 缓冲区完成对数据的排序，实现稳定、流畅的播放，缓存采用f i f o 方式，数据 播放完直接丢弃。 接收数据首先到达接收缓存进行排序，然后将排序后的数据分别放进播放缓 存和转发缓存中。当接收缓存已满而有新的数据分片到达时，须进行缓存替换， 采用基于最小序号的缓存替换算法，即每次都先将最小序号的数据分片放入转 发缓冲区，同时放入播放缓冲区中。在数据分片由接收缓冲区放入播放缓冲区 p 2 p 流媒体相关技术 之前，首先完成数据分片的重组，这是分包过程的逆过程，即将分片还原成从 编码器中出来的数据包，由数据分片重组成流媒体数据包，然后放入播放缓冲 区。为了实现稳定、流畅的播放，缓存采用采用环形队列来实现，数据播放完 直接丢弃。l s t r e a m 采用混合流媒体调度算法，即p u s h p u l l 相结合的调度算 法，为了保证高效率的转发数据，转发缓冲区采用f i f o 缓存替换策略，并且给 转发缓冲区增加缓存映射b m ，来表示节点缓存数据情况。 n p 节点的伙伴及伙伴之间数据的传输方向并不固定，伙伴之间根据各自缓 存的数据情况进行数据交换，所以节点和伙伴需要相互知道所缓存的数据的内 容。b m 的表示及交互过程如图2 1 1 所示，b m 信息是用来表明本节点缓存有哪 些数据分片，需要哪些数据分片。b m 是不断更新的，节点之间通过周期性地向 邻居节点发送b m 信息，知道邻居节点缓存的数据内容，进而可以向拥有这个 分片的节点，请求自己需要的数据。 霸 3l 缺失数据片 l 一 断p 雹：三医亚 图2 1 1 酬交互设计图 我们对n p 节点的转发缓存区进行缓存映射，b u f f e rm a p 由一个二维映射表 表示，如果转发缓冲区里，这个原始数据包对应的所有分片都 在，就置为1 ，有缺失小包的话，就置为0 。使用1 6 b i t 描述转发缓冲区的最小 序号的数据包，然后用6 4 b i t 标识缓冲区内从最小序号开始的长度为6 4 的流媒 体包序列中，哪些片段有数据( 1 表示拥有该数据片断，0 表示没有) 。 在p u l l 策略中，节点b 从节点a 处获取一个数据包p 需要经过下面3 个步 骤： 蛔f 圃蛔f 圃砸i 匦 心 p 2 p 流媒体相关技术 ( 1 ) a 发送b m 给b ，声明数据包p 存在自己的缓存中； ( 2 ) 如果b 需要数据包p ，则发送b m 请求给a ，请求a 给自己发送数据包p ； ( 3 ) a 接收到请求后，将p 发送给b 所以数据传输过程是繁琐的，为了提高效率，减少网络流量中控制信息的 比重，每次b m 请求一个大包序列。假如每次请求长度是2 ，现在想请求序号为 1 、2 的大包，在邻居节点中查找，既有1 ，又有2 的邻居节点，就选这个邻居 节点请求数据，下次请求序号加2 如果没有符合这个条件的邻居节点，我们就 选只有1 的邻居节点请求数据。在p u l l 策略中，每次b m 请求一个原始数据 包序列，邻居节点将多个原始数据包的信息合并起来发送给请求节点。 ( 2 ) p u s h p u l l 相结合的的数据传输 一 数据预处理 信号度件i l ”1 1 缓存附一封装包阡_ 一拆分包 图2 1 2 传输模型图 数据 传输 ( 韵 系统传输模型如图2 1 2 所示，频道源节点( c s p s ) 首先获得视频源，视频源可 以是摄像机、摄像头、麦克风等设备采集的音频、视频信息，电视信号、电视 机顶盒采集的卫星信号，或者各种媒体文件如a s f 、a v i 、w a v 、m p g 、m p 3 、 w m v 、w m a 等。源节点编码器将视频源进行数据编码后，生成流媒体数据包， 2 7 p 2 p 流媒体相关技术 由于数据包的大小超过了m t u ，所以在视频源节点的应用程序中对数据包进行 了拆分，拆分为大小相同的小包，然后把拆分后的小包进行封装，加上一些头 部信息进行标识，组成数据分片，放入源节点的缓存中。当有客户端请求时， 源节点把缓存中的数据分片封装为r t p 包传送到目的节点，目的节点通过r t p 协议接收来自源节点的信息。系统中节点类型有两种：超级节点和普通节点， 其中超级节点位于数据传输的第二层，可以从视频源节点直接获得数据，以频 道源为树根形成一棵逻辑转发树，通过p u s h 的机制进行数据传输。超级节点 负载大于普通节点，一方面将获得的数据分片进行缓存，用于数据播放，另一 方面还要向簇内普通节点提供服务，包括向簇内部分n p 节点p u s h 流媒体数据 和管理簇内节点。普通节点位于系统的第三层，遵循地域相近原则形成簇，簇 内节点之间是网状结构，图中节点a 和节点b 是位于一个簇的两个n p 节点，a 与b 之间形成邻居节点关系，通过实时地交换b m 信息，了解相互缓存数据内 容，采用p u l l 的数据传输策略，通过数据调度算法选择自己要请求的数据包 和对应的邻居节点进行数据包的请求，然后接收邻居节点发来的数据包，最后 调用m c d i ap l a y e r ，进行本地播放。 在混合结构模型的第三层，数据传输需要解决两个关键的问题，覆盖网的构 造和数据调度策略的选择。普通节点加入系统时，采取就近原则加入到簇内， 簇内节点组成网状逻辑拓扑，首先每个节点独立地选择一些邻居节点构成一个 无结构的网络，称为覆盖网的构造，然后是通过p u l l 机制进行数据传输，其 中要解决的关键问题是如何进行数据调度，将在第四章展开介绍。 下层覆盖网的构造过程主要包括节点的加入和邻居关系的确立，具体过程 为：一个节点a 申请加入系统，首先它要先向t s 发送注册报文s e n d t s ，t s 收 到该报文后，保存a 的相关信息并且根据节点调度算法返回给a 一个s p 节点 和若干个n p 节点( 这些节点播放的频道与节点请求的频道是相同的) 。然后a 发送报文s e u d s p ，与该s p 节点连接，并加入以该s p 节点为簇首的簇内，同时从 返回的n p 节点中选择一些性能比较优的节点作为自己的邻居节点通过发送报 文s e n d p n 建立邻居关系，这些邻居节点为其提供数据源。 涉及到n p 与t s 建立连接的报文、与簇首建立连接的报文和与一些n p 节点 建立伙伴关系的报文，报文的格式如下： s t r u c ts e n d t s 、 p 2 p 流媒体相关技术 c h a rm e s s a g e m s g _ s i z e ； t y p es t a t u s ；用于标识节点是s p 节点还是n p 节点 i n tc h a n n e l i d ；表示频道号 ) ； s t r u c ts e n d s p r ) ，所以可以确定下一个时间间隔a t ( 滑动窗口的滑动步长) 内 允许请求调度的数据包的范围为滑动窗口内t p + t 时刻后的数据，将此区域叫做 交换窗口( e x c h a n g i n gw i p d o w ) ，只向邻居请求交换窗口中缺少的数据包。根据 交换窗口中数据对时间的敏感程度，将其分为紧急区域和非紧急区域，即将播 放的部分就是紧急区域，如交换窗口的前1 5 。数据调度最理想的状态是紧急区 域中的数据全部都已经到达，每次只需要请求调度非紧急区域的数据。缓冲区 中数据的结构如图3 1 所示。 图3 1 数据缓冲区结构 3 2 2 数据分片的优先级定义 数据驱动的流媒体系统中，分片的数量不是成比例的，经常会出现某些分片 的副本过少，导致分片有很少的潜在提供者。为了方面描述，简称副本数量过 少的分片为稀缺分片，因为有很少的邻居拥有这些分片，所以必须优先请求， 3 2 数据调度算法l r f a 的设计 这样可以快速地增加稀缺分片的副本，促进节点负载平衡，提高整体的下载速 率。p 2 p 文件系统b t 就是采用稀缺分片优先调度( r a r e s tf i r s t ) 的算法。其 次因为是流媒体直播系统，所以要考虑数据的实时性即紧急程度，一个快到播 放生存期( p l a y b a c kd e a d l i n e ) 的数据应该比刚进入交换窗口的数据有更高的优 先级。根据分片的稀缺性和实时性，为它定义不同的优先级，优先级越高，就 说明该分片越重要，需要优先调度。 把数据分片的稀缺性和实时性作为决定数据分片优先级的两个因素，表3 1 是下面定义所用到的参数的描述，定义数据分片的优先级的计算公式为： ，、 彳= 叱l 磁l + ( 1 - a ) p a s ) ( 3 1 ) 其中s = ( s r e q s m i n ) s i z e ， 0 a 1 一k 瓷5 踯，= 一。嘉1 表3 1 参数描述1 只， 节点i 请求分片j 的优先级 硭 节点k 存有分片j n b r ( i )节点i 的邻居集合 s 数据在调度窗口里的位置 s r e q 数据分片的序号 s m i n调度窗口里数据分片的最小序号 s i z e 系统调度窗口的大小 最( 叼 数据分片的稀缺性 尼( ) 数据分片的实时性 fb _ ， 节点i 的邻居节点中持有数据分片j 的邻居节点的 -，暑l 七加r ( f ) 个数 ( 3 2 ) ( 3 3 ) 数据调度算法l r f a 的设计 假设系统中每个节点的邻居节点数为n ，系统中分片数为m ，那么计算数据 分片优先级的时间复杂度为o ( n 幸m ) 。 3 2 3 节点能力的评估 。 系统中，每隔一个调度周期，节点就向邻居节点发送一次数据请求。为了 能快速、完整地获得数据，应该优先请求节点能力强的邻居节点。邻居节点可 能要同时给多个请求节点传输数据，所以它的节点能力会被分配到各个请求节 点。每个请求节点只需知道邻居节点分给自己支配的能力的大小，这个能力受 到邻居节点的可用上传带宽、请求节点的可用下载带宽、网络链路质量、请求 节点个数等多方面因素的影响，是一个动态变化的值。如果用传统的方法实时 测量是非常消耗资源的，所以采用基于节点历史传输数据实时估算节点能力的 方法。 一 且 计算节点能力要用到的参数如表3 2 所示，初始化c a p a 二为常量 g = m i n ( 仇觑耐j | 7 刀姗，i n b a n d b ，l i n k a 一口) ，在每个调度周期，节点b 向一些邻居节点 请求数据，然后对这些邻居节点的能力进行一次估算，因为系统中数据分片的 大小基本相等，所以用数据分片的个数作为计量单位。 表3 2 参数描述2 c a p a a 邻居节点a 的能力 o u t b a n d 邻居节点a 的上传带宽 i n b a n d b节点b 的下载带宽 工加以一矗节点a 到节点占的链路状况 c a p a ： 邻居节点彳分配给节点口的能力 b u m 邻居节点a 接收到的请求传输数据的节点个数 计算节点能力的函数为 c a l c u l a t e c a p a c i t y ( ) d a t a r e q u e s t n u m ；上次请求的数据包的数目，一定小于上次计算的能力 d a t a r e c e i v e n u m ；上次请求发出后，接收到的数据包的数目 3 4 数据调度算法l r f a 的设计 i f ( d a t a r e q u e s t n u m 一0 ) 第一次向该邻居请求数据 鳓：m i n ( o u t b a n d 彳恤卅，i n b a n d 8 ，l i n k 枷) ； r e t u r n ： i f ( d a t a r e q u e s t n u m = ：鲰：) 疗 c a p a j = d a t a r e c e i v e n u m ： “ 该算法主要考虑请求的数据包的数量与邻居节点当前能力的关系，如果相 等，就把邻居节点的能力调整为此次接收到的数据包的数量；如果小于，则邻 居节点的能力保持不变。 3 3 最小最少优先的数据调度算法设计 3 3 1 分片调度 系统中有些数据分片有很少的潜在提供者，主要是因为：这些分片序号较 小，位于缓冲区的紧急区域，并且它在一些邻居中已经滑出了缓冲区滑动窗口， 或者这些分片是非常新的数据，位于非紧急缓冲区，还没有被广泛传播，因此 只有数据源节点和与数据源相连的伙伴拥有。前者分片位于紧急缓冲区，实时 性要求也很强，所以式3 1 中a 取1 2 ，即稀缺性和实时性并重。后者分片实时 性要求不强，所以式3 1 中a 取l ，即只考虑稀缺性。在带宽有限的情况下， 应该首先请求紧急区域中有较少潜在提供者的数据，否则可能会导致紧急区域 的数据在播放时间以前不能到达。而非常新的数据分片，随着播放时间的向后 p u s h 移，会在邻居节点之间广泛传播。 分片调度算法为：首先请求紧急区域中未到达的分片，用公式3 1 计算分 片的优先级其中a = 1 2 ，按照其优先级从大到小排序，放到请求集合；然后再 请求非紧急区域中未到达的分片，用公式3 1 其中a = l 计算分片的优先级，计 算结果按照从大到小的顺序，放进请求集合r e q u e s t c o l l e c t i o n 中。 3 3 2 节点调度 为了实现负载平衡，为每个节点定义一个接受请求数a c c _ n u m ，当有邻居节 数据调度算法l r f a 的设计 点从它请求一个数据包时，a c c h u m 加1 ；当它成功发送出一个数据包时，a c c n u m 减l 。确定请求的分片后，从含有该分片的邻居节点中选择a c e n u m 最小的节点， 进行数据请求。这样做既可以使邻居节点上传数据的负载平衡，充分利用节点 资源，又可以缩短请求节点等待数据的时间，最快地得到请求数据。 若拥有该分片的邻居节点的a c e n u m 相等，调用c a l c u l a t e c a p a c i t y ( ) 函数 计算节点能力，选择能力最大的邻居节点进行请求。p e e r 节点的服务能力有很 大的差异性，这样就可以充分利用p e e r 节点的带宽、处理能力等资源，为用户 提供高质量的流媒体服务。 3 3 3l r f a 调度算法 用分片调度算法确定要请求的数据分片，然后采用节点调度算法来确定该 向哪些节点请求数据，l r f a 调度算法包含上面两部分的内容： ( 1 ) 计算紧急区域中还没有到的数据包的优先级，因为两个要素并重，所以 取口= 1 2 。按照其优先级从小到大排序，放到请求集合r e q u e s t c o l l e c t i o n 中。- ( 2 ) 计算非紧急区域中还没有到的数据包的优先级，取口= l 。按照其p 酊耐t ) ， 从小到大排序，放到请求集合r e q u e s t c o l l e c t i o n 中。若请求集合 r e q u e s t c o l l e c t i o n 中的数据包的个数大于设定的一次请求的数据包的个数，则 结束第2 步。 ( 3 ) 计算每个邻居节点的服务能力，调用每个邻居的c a l e u l a t e c a p a c i t y ( ) 函数。 ( 4 ) 从请求队列中取出一个数据包，寻找含有该数据包且a c cn u m 最小的邻 居，若拥有该分片的邻居的a c ci l u m 相等，选择其中节点能力最大的邻居节点。 将该数据包的编号放入该邻居的请求队列r e q u e s tp a c k e t ( 5 ) 继续第( 4 ) 步，直到请求集合r e q u e s t c o l l e e t i o n 中的数据都处理完毕， 清空数据请求集合r e q u e s t c o l l e c t i o n 。 ( 6 ) 将邻居的请求r e q u e s t p a c k e t - q u e u e 转化成消息发送给邻居，记录每个邻 居的d a t a r e q u e s t n u m 。 l r f a 算法伪码描述如下： l r f a ( ) f o rv j e ld o e l 表示紧急区域未到达的分片集合 c a l c u l a t e ( 尸，) e n df o r 数据调度算法l r f a 的设计 d e s c e n d s o r t ( pj ) r e q u e s t c 0 1 l e c t i o n ( ) f o rv i en ld o n l 表示非紧急区域朱到达的分片集合 c a l c u l a t e ( 尸) e n df o r d e s c e n d s o r t ( pj ) f o rc s e t r e q u e s t c 0 1 1 e c t i o n ( ) e n df o r f o rv f n bd o n b 表示邻居节点集合 c a c u l a t e a c c e p t n u m ( d e n df o r i f ( u n i q u e m i n ( a c c _ n u m ) ) a c c _ n u m 最小的邻居节点唯一 c h o o s e n o d e0 e l s ec a l c u l a t e c a p a c i t y ( ) c h o o s e m a x c a p a ( ) s e n d m e s s a g e ( ) r e g is t e r ( d a t a r e q u e s t n u m ) 3 4l r f a 与l r f 对比 图3 2 和图3 3 给出了两个数据调度的例子，将本系统提出的l r f a 算法和 u 心算法进行了对比。线条旁边的数字代表这个链路上允许传输数据块的最大 数目，节点附近的数据块代表节点此刻持有的数据块。图3 2 节点4 向节点l ， 2 和3 请求数据块，l p - 汗 调度算法首先请求潜在提供者较少的数据块，如果一个 数据块有多个潜在提供者，那么将选中具有最多剩余带宽的伙伴进行请求，如 图l r fs c h e d u l i n g ( 1 ) 所示，数据块2 只有一个提供者，所以向节点2 请求，之 后节点2 的剩余带宽变成了3 ，因为大于节点1 的带宽，所以向节点2 请求数据 块4 ，之后节点2 的剩余带宽为2 ，因为大于节点3 的带宽，所以向节点2 请求 数据块3 。与此不同，使用l r f a 算法如图l r f as c h e d u l i n g ( 1 ) 所示，可以取得 更好的负载平衡，提高数据传输效率，较少时延。图3 3 中节点3 和4 都向l 请 3 7 数据调度算法l r f a 的设计 求数据，l r f 算法如图l r fs c h e d u l i n g ( 2 ) 所示，节点l 链路上出现拥塞，但节 点4 却未充分利用节点2 的资源。l r f a 算法如图l r f as c h e d u l i n g ( 2 ) 所示，节 点4 向节点2 请求数据块2 和5 ，避免节点l 链路上的拥塞。 口口 l r fscheduling(1)lrfa s c h e d u l i n g ( 1 ) 图3 2 数据调度结果对比( 1 ) l r fs c h e d u l i n g ( 2 ) l r f a s c h e d u l i n g ( 2 ) 图3 3 数据调度结果对比( 2 ) 3 5 算法时间复杂度分析 假设系统中节点个数为k 每个节点的邻居节点数为n ，系统中分片数为m ， 那么计算数据分片优先级的时间复杂度为o ( n 宰m ) 。计算节点的能力，需记录节 点在一个调度周期里请求数据分片的个数和接收的数据分片的个数，通过对比 这两个值的大小，对节点能力进行调整，计算节点能力的时间复杂度为o c k ) 。 l r f a 调度算法由上面两部分组成，时间复杂度是两者的和o ( n l i l + k ) 。 数据调度算法l r f a 的设计 3 6 本章小结 本章首先给出了p 2 p 视频直播系统中的数据分片的优先级和节点能力的定 义和计算方法，然后结合现有的稀缺优先策略，提出了最少最小优先算法 ( l r f a ) 。算法中考虑了流媒体数据的稀缺性和实时性，也考虑了如何既能实现 节点的负载平衡，又能充分利用节点资源。通过两个实例将本文提出的算法和 稀缺优先调度算法对比，并对算法的时间复杂度进行了度量。得出结论，最少 最小优先算法既克服了传统策略的缺点，又能根据分片的重要性，节点的异构 性和动态性自动调整调度策略，可以有效缩短数据的传输时延，较好地实现节 点负载平衡，提高视频的播放质量。 。 实验及结果分析 4 实验及结果分析 本章首先给出了数据调度算法的实验目标，然后重点介绍了算法的性能指 标，详细描述了实验环境的配置搭建以及实验的运行过程，分别比较随机算法、 循环鲁棒算法、稀缺优先算法和最少最小优先算法在同等条件下的性能差异。 4 1 实验目标 一个合理高效的数据调度算法，应满足系统在稳定性、节点负载平衡、数 据传输时延以及带宽利用等方面的性能要求，但现有的数据调度算法并不能很 好的解决以上问题。随机调度算法实现简单，但不能很好的适应网络的异构性， 且稳定性差；循环鲁棒算法可以较好地实现负载平衡，稀缺优先算法数据延迟 较小，但二者均依赖于带宽的计算。对此，本文在以上数据调度算法的基础上， 结合各个算法的优点，提出了一种最少最小优先的数据调度算法l r f a 。本章的 主要目的是通过仿真实验来验证l r f a 算法稳定性较好，不依赖于带宽的计算， 并且能够适应节点的异构性，有效缩短数据的传输时延，较好地实现节点负载 平衡，从而能够提高p 2 p 流媒体直播系统的播放质量。 4 2 实验环境 本文采用了模拟仿真的方法对数据调度算法进行了模拟实验。设置交换窗 口大小为1 0 秒数据量，缓存大小为1 分钟数据量，数据调度周期为1 秒，通过 改变系统的运行时间、系统的规模或者节点播放速率来测试l r f a 算法的性能。 用网络模拟器n s 2 作为模拟工具，n s 2 是一个离散事件模拟器，源于r e a l n e t w o r ks i m u l a t o r 的一个变种，受到d a r p a 的v i n t 项目的支持，由美国加州 b e r k e l e y 大学l b l 。x e r o xp a r c ，u c b 和u s c i s i 共同开发的网络仿真集成环 境，具有开放性好、扩展性强、适用于w i n d o w s 和l i n u x 系统平台的特点，是 一个出色的研究网络拓扑结构、分析网络传输的仿真工具。同时，n s 2 是免费 的，开放源代码的，具有开放的体系结构。这使得利用n s 2 进行网络模拟的研 究者可以很方便的扩展n s 2 的功能，也可以很方便地共享和交流彼此的研究成 实验及结果分析 果。n s 2 吸纳了这些开发者贡献的各方面的模块，从而使它的构件库不断地丰 富，这正是一个好的网络模拟器的生命力之所在。利用n s 2 进行网络模拟的整 个过程如图4 1 所示。 图4 1n s 一2 网络模拟过程 4 3 性能指标 仿真实验中我们主要考虑了四个关键的参数，作为评估算法优劣的依据， 下面是参数的定义： 定义l ：传输率( d e l i v e r yr a t i o ) 为播放生存期内到达的数据包的数量与节 点接收到的数据包的数量的比值。用d r 来表示传输率，五表示在播放生存期内 到达的数据包的数量，刀表示节点接收到的数据包的数量，如果第i 数据包在播 放生存期内到达，使磊= l ，否则4 f f i o 。传输率计算公式如下： 一 d r ：y 点n ( 4 1 ) 笥 定义2 ：数据时延( p a c k e tl a t e n c y ) 为节点接收数据的等待时间，即从节点 发出数据请求，到接收到该数据的时间。用p l 表示数据时延，t s 为节点发出数 据请求的时间，t r 为节点接收到该数据的时间。数据时延的计算公式： p i ( 4 2 ) 定义3 ：播放停顿频率( p l a y b a c kf r e e z ef r e q u e n c y ) 单位时间内节点在接收 流媒体数据进行播放的过程中所停顿的次数。p f f 表示节点的播放停顿频率，在 节点生命周期中，回放停顿的总次数，除以节点生存时间l i ，乘3 6 0 0 秒( 即 l 小时) ，计算公式如下： 4 1 实验及结果分析 p f f = 兰x 3 6 0 0( 4 3 ) 厅 定义4 ：协议通信开销( p r o t o c o lc o m m u n i c a t es p e n d i n g ) 节点与邻居节点 之间交换的缓存状念信息，以及数据请求报文信息，占系统中所有信息的比重。 用p c s 表示协议通信开销，用c d 代表缓存状态信息和数据请求报文信息，d i 表 示节点之间交换的数据信息，协议通信丌销计算公式为： p c s ：1 0 0 ( 4 4 ) 4 4 实验结果及分析 本章通过三个实验来对比系统采用随机策略、循环鲁棒策略、稀缺优先策 略与本文提出的最少最小优先策略取得的平均传输率。系统的平均传输率( 设为 a v g为所有节点传输率的平均值，通过下面公式计算 ， _ d r ) 一 d r = y d r n a v g ( 4 5 ) _ d r = 乞d r n ：( 4 - 5 ) f 暑i 在实验l 中，系统的规模是固定不变的，共有5 0 0 个节点，运行一个小时， 获得系统中每个节点的传输率，然后求平均，得到系统的平均传输率，实验结 果如图4 2 所示，相对于其他算法，l r f a 算法更优，其平均传输率在9 5 左右。 实验2 是在系统规模和运行时间一定的情况下，通过改变节点的播放速率，得 到的系统平均传输率变化情况，如图4 3 所示，实验结果表明，当播放速率比较 低时，四种算法的平均传输率都很高，但是随着播放速率不断提高，其余三种 算法的平均传输率都很快下降，只有l r f a 算法比较稳定，保持在9 8 左右。 实验3 是在系统运行时间和节点播放速率固定的情况下，改变系统规模，测得 不同算法的平均传输率。如图4 4 所示，实验结果表明，四条曲线都很平缓，说 明随着系统规模的扩大，四种算法都有很好的可扩展性，但是本文提出的l r f a 算法的平均传输率优于其余三种算法1 0 0 o - 3 0 。 实验及结果分析 图4 2 系统的平均传输率随运行时间的变化 图4 3 系统的平均传输率随播放速率的变化 4 3 实验及结果分析 缓锄锄：孙砌嬲# 绱觏善磊：嬲锄。嚣g r o u ps 移磁蕊蕊蹴；镭勃磊藐矧么 图4 4 系统的平均传输率随系统规模的变化 实验4 和实验5 对比了采用不同算法系统的平均数据时延情况，平均数据 时延( 设为a v g为系统中所有节点的数据时延的平均值。计算公式为pl) y p l n a v g ， ( 4 6 ) _ p l = 乞p l n ( 4 6 ) f = l 实验4 是在系统规模一定的情况下，对比不同算法的平均数据时延，结果 如图4 5 所示，l r f a 算法的平均数据时延最小，并且相对于其他三种算法，l r f a 在网络质量较差、扰动性较大的情况下，仍能保证较小的传输时延波动。实验5 改变系统规模，对比不同算法的平均数据时延，图4 6 的实验结果显示，随着系 统节点数的增加，由于p 2 p 技术的引入，使得各种数据调度算法的平均数据时 延都会相对减小。在现有的三种数据调度算法中，稀缺优先算法的平均数据时 延最小，l r f a 算法对稀缺优先算法进行了改进，获得更小的平均数据时延。 图4 5 系统的平均数据时延随运行时间变化图 一 ： _ 一 i 7 一 一 1 - - - - - - r a n d o m 一r o u n d - r o b i n - l r f 斗- l r f a 醇黧裟篙篓慧淼瓣篡糕焉黧瓣乎 晋耋翌譬黧磊翼篆羔鋈? 茎墓宰磊芸蓑蕃蓑篡篓霎妻亲誓主嚣：i ! i ：筹了，内 燃然妻譬篇篇篇篇篡蒸裟邕茹 要黧凳鬃焉燃喾篇篇茹徽淼嚣； 纂絮鲻嚣焉装糕戮：! 晶鬟戮嚣蔷 黧越行意愿蒜篱怒嚣2蓄=蔷麦嘉lrfa l r f 以看出， 算法的播放停顿频率最小， 算法次乙，囚朊w 甘匕秽啾旧 实验及结果分析 图4 7 播放停顿频率比较 为了减少网络流量中控制信息的比重，从而进一步提高系统的整体性能， 本文对n p 节点的数据请求过程进行了改进。传统的基于拉的数据传输策略下， 每次请求一个数据包，而本算法中，每次请求多个数据包，测得系统的控制开 销，如图4 8 所示，较改进前减少了4 0 。 图4 8 协议控制开销比较 4 5 本章小结 本章首先介绍了实验目标，仿真环境和性能评测指标，通过改变运行时间、 系统规模和播放速率，分别测得系统的平均传输率、平均数据时延、播放停顿 实验及结果分析 频率，将l r f a 算法和r a n d o m 、r o u n d r o b i n 、l r f 三种算法进行了对比实验， 实验表明l r f a 算法在传输率、数据时延、播放停顿频率三个衡量调度算法的指 标方面比其余三种算法表现出了更好的性能，具有较高的实用价值。系统中对 n p 节点数据请求过程进行了改进，减少了系统中的协议通信开销。 4 7 总结与展望 5 总结与展望 5 1 本文工作总结+ 随着p 2 p 技术的发展，其应用也越来越广泛，尤其是视频直播方面的应用 尤为突出。在采用p 2 p 技术的直播系统中，组成员间的树形结构能提高系统吞 吐量，但维护多个独立的组播树需要较大的协议计算能力和通信开销；而全网 状结构虽然能较好适应节点的动态和抖动性，但一定程度上容易导致视频传输 延迟、增大系统控制开销。所以在本文中，介绍了分层混合的非结构化的流媒 体直播系统模型l s t r e a m ，按照分层分簇的方式构建拓扑结构，将稳定性差的普 通节点聚集成簇，各个簇组成了下层的覆盖网，提高了系统的可扩展性和抗扰 动性。 本文主要完成的工作： ( 1 ) 以l s t r e a m 系统为背景，介绍了数据传输过程，及系统中的核心模块 缓存模块、数据传输模块的设计与实现。缓存模块和数据传输模块与数据调度 紧密相关，系统中采用了二级三缓存的独特设计，为转发缓存区增加了b m 信 息，节点之间通过交互b m 信息，得知对方缓存数据内容；数据传输模块主要 介绍了节点加入系统后，与簇首和邻居节点之间建立连接，接收和发送数据的 过程。 ( 2 ) l s t r e a m 中同一个簇的n p 节点组成一个覆盖网，簇内n p 节点之间采 用p u s h p u l l 相结合的数据传输模型，需要考虑数据调度问题。本文重点研究 了簇内n p 节点采用的数据调度算法，分析了现有的p 2 p 流媒体直播系统的数据 调度算法的局限性，依据p 2 p 流媒体直播系统数据分片的稀缺性和紧急性，以 及对邻居节点能力的实时评估，提出了最少最小优先的数据调度算法解决了如 何用最高的效率请求获得最重要的数据分片，提高了系统性能，进一步改善节 点的视频播放质量。 ( 3 ) 将本文的最小最少优先的数据调度算法l r f a 和目前常用的 r a n d o m ( 随机调度策略) 和r o u n d - r o b i n ( 循环鲁棒策略) 和l 0 c a lr a r e s t - f i r s t ( 稀缺 优先策略) 进行了对比实验，仿真结果及分析表明，较上述三种算法，本文算法 应用在p 2 p 流媒体直播系统的网状拓扑层，性能更好。 4 8 总结与展望 5 2 本文的贡献及展望 本文分析了现存的数据传输模型，在此基础上介绍了一种分层混合的直播 系统l s t r e a m ，并重点研究了分层混合直播系统中簇内的数据调度算法，提出了 一种最小最少优先的数据调度算法l r f a 。该算法既克服了传统策略的缺点，又 能根据分片的重要性，节点的异构性和动态性自动调整调度策略，可以有效缩 短数据的传输时延，较好地实现节点负载平衡，提高视频的播放质量。该算法 不仅适用于l s t r e a m 系统的簇内节点，还可以用于任何基于数据驱动网络的多媒 体直播系统。 下一步可以在以下两方面开展进一步的研究： ( 1 ) 数据调度问题应该考虑多方面的因素，本文的数据调度算法主要考虑 了分片的重要程度，充分利用节点的网络资源，实现节点的负载平衡等因素， 还有继续改进的空间，譬如将最大化流媒体系统的数据吞吐量作为考虑因素， 对l r f a 做进一步的改进。 ( 2 ) 在现有的流媒体系统中，缺乏对节点进行有效的管理和监测，下一步、 可以将节点的管理与数据调度相结合，将节点的可靠性和安全性加入节点能力 的评估参数中。 ( 3