一种基于混合动态优先队列的P2P流媒体系统数据请求调度方法

摘要

本发明公开了一种基于混合动态优先队列的P2P流媒体系统数据请求调度方法，在数据发送结点分别建立调度时限优先队列和调度稀缺度优先队列；由数据接收结点发出的数据请求中，包含有播放时限信息和稀缺度信息；在每个数据请求到达数据发送结点时，根据调度时限和稀缺度将数据请求分别插入调度时限优先队列和调度稀缺度优先队列的相应位置；数据调度时，优先调度调度时限将在下一个调度周期中过期的请求，其次按稀缺度优先调度，在每一数据调度完成时，从两个队列中删除已调度数据请求，并调整调度时限优先队列中各数据请求的调度时限。本发明的方法可以得到更高的平均数据块按时到达率和结点上传带宽利用率，从而具有更好的媒体回放质量。

说明书

技术领域

本发明涉及一种基于P2P技术的内容分发服务，特别是P2P流媒体服务，尤其涉及一种P2P流媒体系统的数据请求调度方法。

背景技术

流媒体是指在数据网络上按时间先后次序传输和播放的连续音、视频数据流。流媒体数据流具有3个特点：连续性、实时性、时序性，即其数据流具有严格的前后时序关系。由于流媒体的这些特点，它已经成为在互联网上实时传输音、视频的主要方式。把P2P技术引入到流媒体传输中就形成了P2P流媒体技术。

根据结点的组织方式，P2P流媒体系统可分为两大类：树状结构与网状结构。在网状结构的P2P流媒体系统采用数据驱动的方式。为了让媒体文件的各个部分可以并行下载，需要将文件分割成多个小块，文件块用顺序的序号表示，编号通常从0开始，直至最后一块。由于网状结构P2P流媒体系统的结点间不存在确定的上下游关系，一般采用缓存图(Buffer Map)来表示当前缓存中媒体数据块的存储状态并在结点之间进行交换。在缓存图中，内容的存储状态用二元值来记录，1表示存在，0表示不存在。缓存图表示了当前结点缓存中数据的可用性情况，它是内容交换时数据块选择的参考依据。

P2P流媒体系统的性能取决于两个方面：对等网络构建和结点数据调度方法。对等网络构建决定了各个结点可能使用的网络资源，而数据调度决定了结点如何使用这些可用资源。在P2P流媒体系统中，结点接收其邻居结点周期性地发来的数据块存储状态信息，并决定从哪个结点获取所希望得到的数据块，这个过程即是数据调度。CoolStreaming系统中采用本地稀缺优先的数据块选择和基于最大可用带宽的结点选择策略，是一种比较有代表性的数据调度方式。数据调度决定了P2P系统的资源使用方式，对系统性能具有关键影响。在P2P流媒体应用中，需要设计智能化的调度算法才能更好地满足媒体内容的实时播放要求。特别地，调度算法需要满足每个数据块的回放时限和邻居结点的带宽约束。

由于系统中结点数量很多，且各个结点根据本地信息独立做出结点选择策略，因此可能出现在某个结点出现大量的数据请求的情况。为了避免请求丢失，需要对请求进行排队。同样地，结点周期性地响应数据请求，发送相应的数据块。由于每个数据请求需要一定的时间(与数据块大小与服务结点上行带宽有关)，当数据请求到达速率超出请求处理时间时，则请求将会出现排队。长时间的请求等待将产生多方面的问题：其一，对于流媒体应用，有可能出现当请求可以被服务时已经超出其播放时限，从而传送了无用数据；其二，请求等待降低了数据传送的速率；其三，在请求排队期间，该连接将一直保持，由于连接数量有限，长时间占用连接而不进行数据传送降低了系统资源利用率。

目前，数据发送结点对收到的数据请求通常采用先到先服务的方式(将请求保存在先进先出队列中)。由于先到先服务调度方式没有考虑数据播放的时限，因此，当播放时限邻近的数据请求排在队列的后面时，调度该请求时可能已经超出了其播放时限，即便前面调度的数据块到接收端以后还需等待播放时限到来。因此，传统的先进先出(FIFO)队列管理机制在队列长度较长时可能成为系统的性能瓶颈，有必要设计智能的数据请求调度方法。

目前，P2P流媒体系统的数据调度研究主要集中数据请求发送端，即探讨结点如何根据自己的数据需求选择数据块和目标结点请求数据。这些研究隐含一个假设，即数据发送端可以及时响应数据请求。根据上面的分析，在数据发送结点可能出现请求排队的现象，然而如何在数据发送端进行合理的调度数据请求还没有引起广泛的重视。

在P2P文件共享系统中，数据发送结点相当于数据传送服务的服务器方，它们的性能对P2P系统的整体性能具有重要影响。最短剩余处理时间(Shortest Remaining Processing Time，SRPT)是一种经典的优化任务调度方法，可以证明，SRPT可以最小化请求所需的平均响应时间。为了缩短P2P文件共享系统中数据请求的平均服务时间，Qiao等人提出在数据发送端采用SRPT方式调度收到的数据请求。该方法的目标应用是P2P文件共享系统，请求调度依据是剩余处理时间，因而没有考虑数据块的播放时限。此外，该方法也没有考虑系统中数据块多样性要求。

因此，需要根据流媒体的特殊要求，构建专门的数据请求调度方法。

发明内容

本发明的目的是提供一种用于P2P流媒体系统的数据请求调度方法，能够适应流媒体实时性、时序性的要求，提高系统的调度利用性能。

为达到上述目的，本发明采用的技术方案是：一种基于混合动态优先队列的P2P流媒体系统数据请求调度方法，在数据发送结点分别建立调度时限优先队列和调度稀缺度优先队列；由数据接收结点发出的数据请求中，包含有播放时限信息和稀缺度信息；在每个数据请求到达数据发送结点时，根据播放时限信息计算在数据发送结点的调度时限，根据稀缺度信息计算稀缺度，并根据调度时限和稀缺度将数据请求分别插入调度时限优先队列和调度稀缺度优先队列的相应位置；在数据发送结点设定调度周期，在每个调度周期开始时，进行数据调度；所述数据调度为，首先检查调度时限优先队列，如果有请求的调度时限将在下一个调度周期中过期，则调度该数据请求，否则，检查调度稀缺度优先队列，如果存在数据请求，则调度排列在前的数据请求，在每一数据调度完成时，从两个队列中删除已调度数据请求，并调整调度时限优先队列中各数据请求的调度时限，如果两个队列均为空队列，则停止数据调度，等待下一个调度周期的开始。

上述技术方案中，数据发送结点在响应数据请求时同时考虑数据块的播放时限和稀缺程度。根据结点的播放时限和数据的处理与传送时间计算请求的调度时限，为满足数据块的播放时限，数据请求应在调度时限之前进行调度。在调度周期内优先调度播放时限即将到达数据块，若无数据块到达其调度时限，优先调度稀缺度低的数据请求。调度时限优先队列和调度稀缺度优先队列的数据结构，可以分别设置两个队列结构，将数据请求分别复制到两个队列中；也可以设置一个队列，另一个采用数据索引结构，例如设置调度时限优先队列，再设定稀缺度的数据索引；还可以根据数据请求的到达时限设置队列，同时分别设置调度时限和稀缺度的索引。这些队列结构的设置方式均能实现上述技术方案的两个优先队列要求，因而均属于本发明的保护范围。

上述技术方案中，数据请求的调度时限的计算方法为，

记数据块大小为CS，媒体播放速率为R，则单个数据块播放时间：t＝CS/R；

记请求数据块序号为SN_r，当前正在播放数据块序号SN_p，则播放时限t_d＝(SN_r-SN_p)*t；

请求发送结点请求发送时间戳为ts_s，请求接收时间戳为ts_r，请求发送时间t_rs＝ts_r-ts_s；

请求响应结点数据块发送时间td_s＝max(CS/BW_s，CS/BW_r)+d_ul，其中BW_s表示发送结点带宽，BW_r表示接收结点带宽，d_ul是上行链路时延(网络中间结点排队时间)；

则调度时限为t_s＝t_d-t_rs-td_s。

因此，通常地，所述播放时限信息包括播放时限和请求发送时间戳。当然，所述播放时限信息也可以包括当前正在播放数据块序号和请求发送时间戳，此时，由于请求数据块序号已知，单个数据块播放时间已知，因此可以由数据发送结点计算播放时限，进而计算调度时限，但相应地增加了数据发送结点的负荷。

所述稀缺度信息为，在数据接收结点记录的请求数据块的副本数量。

稀缺度＝请求数据块的副本数量÷数据块总数，在调度稀缺度优先队列中，数据请求按照稀缺度从小到大的顺序排列。

对应的数据请求中，可以包含副本数量，也可以包含经过归一化处理的称缺度值。

由于结点难以获得系统中其它全部结点的数据块块信息，数据块副本数量的统计只具有局部意义。

由于上述技术方案运用，本发明与现有技术相比具有下列优点：

1.本发明的方法在用于P2P流媒体系统时，在数据发送结点对来自系统中其它结点中的数据请求进行了合理的调度，能够满足被请求数据块的播放时限，因此可以减少数据块错过播放时限的机会，从而提高媒体回放的质量；同时兼顾了数据在系统中的多样性要求，在时间约束得到满足的前提下，优先调度稀缺度较低的数据块请求，可以提高系统中数据块的多样性，从而有助于让更多的结点下载到想要的数据，进而提高系统的利用率。

2.仿真实验表明，采用本发明的方法，相比于现有技术的方法可以得到更高的平均数据块按时到达率和结点上传带宽利用率，从而具有更好的媒体回放质量。

附图说明

图1为本发明实施例一基于混合动态优先队列的P2P流媒体系统数据请求调度流程图；

图2为实施例一中平均数据块按时到达率随时间变化情况示意图；

图3为实施例一中结点上传带宽利用率随时间变化情况示意图；

图4为实施例一中不同系统规模条件下平均数据块按时到达率比较示意图；

图5为实施例一中不同系统规模条件下结点上传带宽利用率比较示意图。

具体实施方式

下面结合附图及实施例对本发明作进一步描述：

实施例一：参见附图1所示，一种基于混合动态优先队列的P2P流媒体系统数据请求调度方法，在数据发送结点分别建立调度时限优先队列和调度稀缺度优先队列；由数据接收结点发出的数据请求中，包含有播放时限信息和稀缺度信息；在每个数据请求到达数据发送结点时，根据播放时限信息计算在数据发送结点的调度时限，根据稀缺度信息计算稀缺度，并根据调度时限和稀缺度将数据请求分别插入调度时限优先队列和调度稀缺度优先队列的相应位置；在数据发送结点设定调度周期，在每个调度周期开始时，进行数据调度；所述数据调度为，首先检查调度时限优先队列，如果有请求的调度时限将在下一个调度周期中过期，则调度该数据请求，否则，检查调度稀缺度优先队列，如果存在数据请求，则调度排列在前的数据请求，在每一数据调度完成时，从两个队列中删除已调度数据请求，并调整调度时限优先队列中各数据请求的调度时限，如果两个队列均为空队列，则停止数据调度，等待下一个调度周期的开始。

其中，数据接收结点也就是请求发送结点，数据请求除了包括请求的数据块序号，请求的源结点，还需要携带在数据发送结点进行请求调度所需的相关信息，包括播放时限，请求发送时间，数据块副本数量(或稀缺度)。可用C++语言结构体表示如下：

struct ChunkReq{

    unsigned int seq_num；

    unsigned iht src_id；

    double playback_deadline；

    time_t req_sending_time；

    double  rarity_degree；

}；

数据发送结点进行数据调度：

分别建立两个优先队列，分别用于保存数据块的调度时限和稀缺度，在数据发送结点，数据块请求可以表示为：

struct ChunkReq_Recv{

    unsigned int seq_num；

    unsigned int src_id；

    double sched_deadline；

    double rarity_degree；

}；

a)当数据发送结点收到某个数据请求时，

根据播放时限和请求接收时间计算出调度时限，如果调度时限小于当前时间，则向请求发送结点发送NACK拒绝请求。否则，根据所算出的数据块调度时限和稀缺程度按照从小到大的顺序分别插入到相应的优先队列中。

b)当调度周期开始时间到达时，

按如下规则从两个优先队列中选择本次调度周期需要响应的请求：

S1：检查调度时限优先队列，如有请求的调度时限将在下一调度周期中过期(T_i＜＝t_s＜T_i+1)，则调度该数据请求(可能不止一个)，否则调度稀缺度优先队列中队首请求(稀缺度最小)，并通过上行链路发送数据。

S2：从两个队列中删除已调度请求

S3：请求调度完成后需调整调度时限优先队列中的调度时限(减去一个数据块发送时间)，如数据块的调度时限小于当前时间，则向其发送结点发送NACK消息。

如在一个调度周期内可同时调度多个请求，则重复上述过程。

其中，数据请求的调度时限的计算方法为，

记数据块大小为CS，媒体播放速率为R，则单个数据块播放时间：t＝CS/R；

记请求数据块序号为SN_r，当前正在播放数据块序号SN_p，则播放时限t_d＝(SN_r-SN_p)*t；

请求发送结点请求发送时间戳为ts_s，请求接收时间戳为ts_r，请求发送时间t_rs＝ts_r-ts_s；

请求响应结点数据块发送时间td_s＝max(CS/BW_s，CS/BW_r)+d_ul，其中BW_s表示发送结点带宽，BW_r表示接收结点带宽，d_ul是上行链路时延(网络中间结点排队时间)；

则调度时限为t_s＝t_d-t_rs-td_s。

根据本实施例的方法，通过仿真实验将该方法与先到先服务和最近时限优先调度方法进行了对比，重点比较三种方法的两个关键性能指标：平均数据块按时到达率和平均结点上传带宽利用率。显然，请求发送端的数据调度方法对上述性能同样有影响，在对比实验时保持请求发送端的数据调度方法不变。

图2所示为系统中在数据发送结点采用不同请求调度方法系统的平均数据块按时到达率随采样时间的变化情况。FIFO表示先到先服务调度方式(采用FIFO队列)，EDF表示最近时限调度，HPS表示本发明公开的混合优先调度方法。从图中可见，采用本发明方法相比于其它方法可以得到更高的平均数据块按时到达率，从而具有更好的媒体回放质量。目前常用的先到先服务方式性能相对最差。

图3所示为系统中在数据发送结点采用不同请求调度方法系统的结点上传带宽利用率随采样时间的变化情况。图中图例同图2(下同)。结点上传带宽利用率越高意味着系统具有的实际容量。图中表明，采用本发明公开方法系统中结点上传带宽利用率略高于其它两种方法。

图4所示为系统在不同规模条件下三种方法的平均数据块按时到达率比较。从图中可见，随着系统规模(结点数量)增加，系统中平均数据块按时到达率呈下降趋势，但在结点数量相同时，本发明公开方法的在三种方法中具有最高的平均数据块按时到达率。类似于图2结果，目前常用的先到先服务方式性能相对最差。

图5所示为系统在不同规模条件下三种方法的系统中结点上传带宽利用率比较。该图清晰地显示出在该实验条件下本发明公开方法可以获得明显较高的结点带宽上传利用率，特别是在系统规模较大时，本发明的性能优势更加明显。这是因为稀缺度优先调度增加了系统中数据块的多样性，从而可以提高各结点获取所需数据的机会。在三种方法中，最近时限优先调度方法条件下结点上传带宽利用率最低，因为在这种条件下，数据块序号分布相对集中，不利于提高结点上传带宽利用率。

从上述实验结果可见，本发明公开的基于混合优先队列数据请求调度方法相比于当前常用的先到先服务请求调度方法和简单的优先调度方法可以有效地提高P2P流媒体系统的平均数据块按时到达率和结点上传带宽利用率，从而提高系统的媒体回放质量。