SLOP 系统中数据块请求调度算法的研究

摘要：本文在研究分析现有P2P 视频直播系统的基础上，提出了SLOP 系统中最少优先的动态数据量请求调度算法，并进行了仿真分析，得到相应结论。

1 前言

SLOP 是Streaming Live media Over Peer-to-peer 的简称，它是一个基于P2P 技术的视频直播传输系统，其在视频直播系统中的位置见图1。它将观看同一节目的所有用户组成一个覆盖网，覆盖网内结点通过相互协作完成数据的传输。现有的P2P 视频直播系统在覆盖网技术和数据交换技术两方面都存在着值得改进的地方，本文重点研究视频直播传输系统中的数据交换问题。

P2P 视频直播系统中面对的是实时流动的数据，结点的缓冲区大小有限，只有保证结点之间的数据窗口有相互重叠的数据它们才能进行相互交换数据。P2P 视频直播系统中采用滑动窗口的机制，结点只能缓存当前播放点前后的一小段数据，需要提供一种机制保证所有结点窗口内的数据有重叠部分才能够相互协作交换数据。另外P2P 视频直播系统中不建立数据传输的树结构，因而需要实时交换窗口内的数据状态信息，这种数据状态信息是一个种额外的开销，应该越小越好，所以，提供更好更及时的数据状态交换算法也是研究的要点。

P2P 视频直播系统中的数据要求实时性，而结点又采用乱序的方式获取数据，因而结点之间数据的差异性，和选择什么数据块由什么结点来传输是一个关键性问题。选择恰当的结点传输恰当的数据块是发挥系统中所有结点能力的关键，也是提升系统扩展能力的关键。如果都选择最新的数据块传输，就不能发挥结点之间协同的能力而降低系统的扩展性。因而现在一般都采用数据块的提供者最少的先下载，选择什么结点什么时间传输该块决定了缓冲窗口内的数据能否使得结点正常进行播放，也影响着其它的结点获取数据。因而提供一种让结点之间负载均衡又能满足播放要求的数据块请求算法是非常必要的。

2 基本思想

SLOP 系统中结点之间相互协作并利用彼此的上传带宽来及时的获得数据。那么数据块的请求调度需要考虑两个方面，数据块的分布和结点的上传带宽。数据块的分布必须均匀，分布均匀是指邻居结点之间享有不同的数据块。首先分布均匀使得结点之间有不同的数据。这是它们能相互交换数据的前提条件。其次分布均匀不会使得某个结点成为新的中心结点而出现瓶颈。结点的上传带宽是高度动态变化的，系统必须适应这种带宽动态变化的网络环境。首先，宽带网的飞速发展虽然提高了结点与服务器之间的带宽，但是结点与结点之间的带宽因跨越跳数较多仍然较低。其次，结点是异构的，它们接入网络的方式不同导致其上传带宽也不一样。最后，结点处在一个高度动态变化的环境之中，它的上传带宽受网络流量的影响而不停变化。块请求调度算法在为每个邻居分配上传任务时必须考虑这种情况。因此，数据块分布不均匀将会导致无法有效利用结点的上传带宽，不考虑结点的上传带宽的动态性而分配数据块请求量会导致不能及时获得数据。

本文提出在 SLOP 中采用最少优先的动态数据量请求调度算法来应对上述两个因素。所谓最少优先即结点首先请求邻居数最少的块，同时也隐含着对邻居数相同的块随机请求。最少优先使得数据能够快速的蔓延到结点之中，并且使之分布均匀。这样结点之间就拥有彼此不同的数据而能相互请求。所谓动态数据量即每次邻居连接管理器依据邻居连接上次数据的获取情况重新计算下次应该分配的请求数据量。动态数据量请求实时的适应了网络带宽的动态变化，能让强能力的邻居提供更多的数据，而弱能力的邻居也能提供数据。

3 最少优先的动态数据量请求调度算法

该算法包含四个内容点，划分块、交换数据块状态信息、分配数据量和选择数据块。划分块是交换数据状态信息的基础，数据块状态信息以块为单位进行描述。数据状态信息又是选择数据块的基础，结点只能向有该数据块的邻居发起对该块的请求。分配数据量依据邻居结点上次提供的数据量进行动态调整。这四个内容点彼此相连构成该算法。

3.1 划分块

我们用 K 代表块的大小。块越小描述块的信息就越多，导致结点间链路开销增大。数据量以块为单位分配，块越大就无法分配较小的数据量。我们用W 表示结点缓冲窗口能存放块的数目。W 太小使得结点之间没有彼此需要的数据而不能达到利用结点的上传带宽的目的。缓冲的块数目越多，后续结点与源节目播放的时间差就越长。当前，SLOP 中默认设定K=4KB，W＝4000。

3.2 交换数据块状态信息

我们利用三字节来描述一段序号连续的数目不大于 255 的块组，这样描述4000 个连续的块只需要48 字节。邻居连接对象记录对应邻居发送来的数据块状态信息和发送给对方的数据块状态信息。结点周期性的将缓冲窗口内数据块状态信息与已发送的和邻居发送的数据状态信息之间的差值发送给邻居结点，结点之间数据块状态信息的交换是必须的，因此我们采用这种增量的方法来减少这种开销。我们设Rkbps 为当前的频道的码率，G<V,E>为结点构成的覆盖网络，当所有结点都下载W 个数据块时，最坏情况即用3 字节表示一个块时产生的开销为|E|×W×3×8bit，下载的数据总量为W×|V|×K×1024×8bit，开销与数据的比值为(3×|E|)/(|V|×K×1024)，在每个结点平均连接30 个邻居且K=4KB 的负载1.1％。我们的实际运行中块大部分都是以大于15 个连续的块出现，因而实际中的负责肯定小于0.1％左右。

当结点收到邻居发送来的数据状态信息时，它首先将该信息加入到邻居连接对象的已接收数据块状态信息中，同时通知成员管理器增加缓冲窗口内数据状态信息中对应块邻居数目。

当与邻居结点的连接断开时，必须通知邻居管理器减少缓冲窗口内数据状态信息中对应块邻居数目，这样才使得邻居管理器记录的缓冲窗口内数据状态信息正确，以保证块选择算法的正确性。

3.3 分配数据块数目

数据量的分配依据邻居结点上次完成的情况周期性动态计算。设定 T 为每秒请求数据块的上限，设定为2×R/（K×8）＝R/4K。设定I 为每秒请求数据块的下限，设定为4。设定G 为上秒请求的块数目，F 为上秒完成块的数目，C 为本秒将请求的数据块数目。如果F 等于G，那么C 等于MIN（2×G，T）。如果F 小于G/2，那么C 等于0。如果F 大于等于G/2 小于L，那么C 等于MAX（I，F－（G－F））。

3.4 选择数据块

在计算出该秒该邻居应该提供多少数据块之后，邻居管理器利用邻居对象的数据块状态信息选取块。为了保证数据的及时性，我们把缓冲窗口分为两个部分，前1000 个块必须是立即获取的，而后3000 个块依据最少优先的选取策略，最少优先的选取策略为首先选择邻居数目最少的块，如果遇到多个块有相同的邻居数据就随机选择，同时把C 设定为实际选出的块数目，修改邻居管理器中数据块的状态为请求中，再向邻居发起请求。

结点与邻居断开时，若还有请求没有完成时结点通知邻居管理器恢复请求中的这些块为未请求状态，以便给其它的邻居提供。

结点收到邻居发来的数据后，将数据写入邻居管理器中的缓冲窗口中，同时更新该块数据的状态为已获得。这种信息将在交换数据块状态信息的处理中发送给其它的邻居结点。

图2 实验结构图

4 性能*价

我们从频道质量、交换状态信息开销量和源负载量三个方面来*价该算法。我们定义频道质量为结点播放频道时一段时间内丢失的数据量和全部数据量的比值，用Q 表示。交换状态信息开销量用状态信息交换的数据量和实际传输数据的量之间的比值来描述，用O 表示。源的负载量定义为源当前输出的带宽对频道码率的倍数，用L 表示。质量越好，用户的感观效果越好就更能满足应用的要求，当Q 为1 时表示没有任何数据的丢失或延迟到达。交换状态信息的数据量越小，O 也就越小。对于客户端/服务器模式系统该值随着用户数增加同比率增加，而对于SLOP 系统来说该值增长缓慢而且到达一定值后不再增大。

在模拟实验中难以模拟结点之间的带宽变化情况，所以该算法的性能我们通过采集系统实际运行的数据所得。因实际运行中条件和环境的限制，目前系统的用户数最高仅在30 人左右。但是这些数据也可以真实的反映算法的性能。下面所得的数据在局域网内部完成即每个机器都能够被访问到且具有类似的带宽。如图2 所示，直播源放在一台单独的服务器上并使用NetMeter 软件测量从某时刻开始一段时间内的带宽值。SLOP 系统中使用突发的方式进行数据传输，因而我们测量10 分钟内的平均带宽值代表系统在这段稳定时间内服务器输出的带宽。Tracker 部署在另一台服务器上。每台PC 机上运行0-5 个客户端。当K=20KB 时，每个客户端需要80MB 左右的内存。我们的PC 机内存为512，为保证系统的正常运行因此每个PC 机最多运行5 个客户端。每个客户端负责记录一段时间内丢失的数据块和收到的数据块数，以及该客户端与所有邻居交换的数据量以及数据块状态信息量。在系统测试中，我们选择能达到VHS 半屏质量的320kbps 码率，块的大小分为4KB 和20KB 两种情况。

（1） 频道质量

在 SLOP 系统的测试中，无论K 为4KB 还是20KB，频道的质量都在100％。在Internet 环境中，频道会因为部分结点接入带宽低而导致质量下降，但目前都大于90％。

（2） 源负载量

对于客户端/服务器模式的视频直播系统而言，源负载量为系统当前的用户数，如图3 中三角形标记的直线。而对于P2P 系统来说，源负载量将远远小于系统中的用户数。从图3 中可以看到用户数为30 时，K 为4KB 的源负载仅为7.6，K 为20KB 的源负载仅为9.6。同时曲线随着用户数的增加其增长幅度越来越缓慢。我们也可以看出K 为20KB 和4KB 时它们在用户数大于15时出现差异，K=20KB 的曲线增长更快。这是因为K=20KB 时，块比较大导致结点随机交换数据时分布不均匀从而被迫从源获取更多的数据。在我们的实际中也发现，K=4KB 时更加适合Internet中的用户。从源负载的降低上，我们可以看出数据块在结点之间的分布是均匀的，结点相互利用了彼此的上传带宽。

（3） 交换状态信息开销

图 4 给出结点邻居数不同时交换状态信息的开销。结点与每个邻居都要进行状态信息的交换，因而邻居数的增加这种状态信息必然增多。上文中我们分析指出块越大交换状态信息开销就越少，从图4 中我们也可以看出。系统的测试中，结点的最大邻居数为23 时，K 为4KB 时开销为0.440‰，K 为20KB 时开销为0.394‰。SLOP 的实际运行中，结点的邻居数一般设定在30 左右，因此交换状态信息的开销不超过0.500‰。从图4 的曲线中我们可以看出曲线的增长随着邻居数的增加而变缓慢。一方面是因为结点邻居数增多它就能更快的获得数据块，使得数据块连续而降低其描述信息。另一方面是差值法的状态信息交换方法，使得结点与邻居之间同时发送相同信息的概率降低。

图4 邻居数与数据块信息开销

5 结束语

从上面的分析和实验结果来看，首先SLOP 视频直播传输系统能够正确完成传输视频流数据。其次，SLOP 系统极大的减轻了直播源的负载，而且有效的利用了邻居结点的上传带宽。最后，数据块状态信息的交换量不超过0.500‰，这个值远小于现有的任何系统。

本文作者创新点：作者在研究分析了现有基于P2P 视频直播系统的基础上，在SLOP 系统中提出了最少优先的动态数据量请求调度算法，不仅有效的降低了直播源的负载，提供了系统的扩展性，同时该算法产生的额外信息开销被降低到0.500‰。