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））。

来源：维库开发网