流媒体系统中基于请求迁移的任务调度算法

李 军，倪 宏，王玲芳，陈 君

(1.中国科学院声学研究所 国家网络新媒体工程技术研究中心，北京100190;2.中国科学院大学，北京100190)

0 引 言

流媒体服务将传统媒体内容网络化、数字化并以用户点播的方式向其提供服务。流媒体系统架构一般包括中央调度系统、多个媒体服务器等模块。调度模块负责整个流媒体系统的任务调度和管理、用户交互操作管理以及维护系统当前服务状态，包括用户请求参数、视频内容分布、点播统计信息、点播会话等。媒体服务器主要接收调度模块的命令，从本地存储或缓存中读取内容向用户提供服务。媒体服务器一般带有存储，由于多媒体内容体积较大，普通服务器存储容量有限，每个媒体服务器的服务能力有限。同时，经统计发现用户对流媒体内容的访问服从一定的规律，80%的用户访问20%的流媒体对象［1-2］，也就是说流媒体内容存在不同的流行度分布。对于热门内容可采取多副本放置的方法通过多台服务器同时向用户提供服务，以提高用户并发数量。由于各个媒体服务节点上内容分布不一致和影片流行度的倾斜性，导致节点之间的负载内容不均匀分布，节点之间的带宽资源和磁盘I/O 资源没有充分利用，系统的服务质量达不到最优化。同时，流媒体服务系统需要不间断地向用户提供服务，但服务器出现故障不可避免，因此，当某个媒体服务器出现故障时，其上正在服务中的请求需要快速迁移到其他服务器上，以保障用户媒体流不中断。

媒体服务器相互存储内容副本，通过请求到达时基于负载均衡的实时任务调度达到系统负载均衡。传统的迁移算法只在新到达的请求被阻塞时才进行请求迁移，这种策略称为最后一分钟请求迁移(Last-minute request migration)［3］。这种传统的迁移算法有两个问题:一是当迁移发生时系统负载已经严重不平衡，导致VoD 系统性能下降;二是由于较高的不均衡内容请求到达导致一些视频服务器已经达到其性能上限而出现不再接收其他媒体服务器迁移过来的客户请求的现象发生，这将产生更多的VoD 系统时延。第一种情况将出现请求被拒绝，从而导致VoD 系统的服务失败率上升;第二种情况会使得用户请求被阻塞而导致系统响应时延上升。这两种情况都会导致流媒体系统用户体验下降。

为了解决媒体服务器节点之间负载不均匀分布以及服务不间断冗余容灾带来的问题，人们在流媒体服务基于迁移的任务调度方面进行了大量研究。Wolf 等提出一种DASD 跳跃算法［4-5］，通过媒体服务器间的请求迁移来维护硬盘负载均衡。Guo 等［6］提出了一种组合负载均衡算法(Combinational load balance)，通过视频副本放置来减少用户请求的阻塞率。Zhao 等［7］研究了同构分布式VoD 系统的负载迁移和动态文件副本更新问题，提出了随机早期迁移(Random early migration，REM)算法，较好地解决了服务失败率和时延问题。

上述方法主要关注的是请求到达时的任务分配问题，根据当前流媒体服务系统的负载状态均衡各媒体服务器的负载，以达到系统整体负载均衡的目的。同时，在考虑请求均衡分配时，系统整体负载较重的情况下，如果需要通过多步迁移以接收一个新到达的请求，将不可避免地造成对正在服务中的请求以及新到达的请求引入服务的短暂中断和服务时延增加。流媒体系统在组建完成后，任何两个节点间是否可迁移已经确定，故可预先计算任意一个节点到其他所有节点的所有可能迁移路径，避免迁移决策实时计算开销。另外，上述研究均没有考虑到当正在服务中的设备出现故障时的服务迁移问题。

本文提出了基于请求迁移的任务调度算法，包括:①对于新到达的点播请求，如果包含该请求媒体内容的所有媒体服务器均处于满负载状态，在保障当前正在服务中请求不间断的情况下通过有限步的请求迁移满足新到达请求被服务;如果需要迁移的请求数量超过预设阈值，则拒绝新到达请求以保障正在服务中的会话质量;②如果某个正在服务中的媒体服务器出现故障不能服务时，调度模块检测到后立即将该服务器负责的请求快速迁移到其他存储有相应媒体内容的服务器上继续为用户提供服务，保障用户服务不中断。

1 VoD 系统性能描述

表1 为符号说明。针对VoD 系统的性能质量，近期一些研究者关注服务器系统、客户端以及它们之间的网络。Mundur 等［8］研究了接纳控制和网络传输机制以满足数据比特率、端到端VoD服务时延约束的QoS 要求。他们的系统中仍然采用简单的最后一分钟迁移策略，迁移只有在请求被阻塞时才会发生。杨戈等［9］分析了基于CDN(Content distribution network)和基于迁移只有在请求被阻塞时才会发生的情况。还分析了基于CDN(Content distribution network)和基于P2P(Peer-to-peer)，采用批处理、补丁等算法的流媒体系统。Barnett 等［10］在中央控制的视频系统和分布式视频系统上根据存储和流化成本两方面比较了“setup”的开销。Kao 等［11］研究融合了基于CDN 的用户交互操作来分析不同VoD 系统中通信和存储开销之间的平衡。

表1 符号说明Table 1 Key variables

对VoD 点播系统而言，系统稳定性体现在是否能够持续不断地为用户提供服务。而VoD 系统的稳定性又主要体现在请求成功率和服务时延上。其中，请求成功率μ 定义为:

请求服务时延Ti定义为从系统接收到请求到媒体服务器开始为其提供服务之间的时间间隔。假设所有媒体服务器对请求的处理时间τ 都相同。如果新请求能够一次被某个媒体服务器服务，则服务时延为τ;如果该请求经过有限步骤迁移后被某媒体服务器服务，则服务时延为迁移路径上服务器的数量乘以τ;如果调度器在决策时发现经过限定的迁移步骤仍然无法为该请求提供服务，则拒绝请求。

本文采用请求成功率和服务时延两个性能指标来衡量VoD 系统的性能。

2 基于请求迁移的任务调度算法

2.1 有限步请求迁移描述

如图1(a)所示的VoD 系统中有3 台媒体服务器，每个服务器能够存储2 个视频内容，同时共享一个大的存储空间。每个服务器可以同时服务5 个用户。假设一个内容A 的新请求或迁移请求在某时刻到达。由于只有媒体服务器1 上存储有视频A，而此时服务器1 已经达到其服务能力上限。为了能够为新请求提供服务，需要从服务器1 上迁出一个视频B 正在服务中的请求到服务器2 上。迁移的请求不能立即被服务器2 接收，因为它也已经满负载运行。此时，服务器2 将一个视频C 的请求迁移到媒体服务器3，由于服务器3这个时候还没有满负载，能够接收该迁入的请求。至此，经过2 步迁移后，新请求被媒体服务器1 接收和服务。在迁移完成之后，除了最后一台服务器负载增加了1，迁移路径上其他服务器负载都保持不变，图1(b)展示了迁移过程和迁移后的系统状态。如图1(c)所示，如果共享存储中有视频A，则该请求可以直接被分配到媒体服务器3，由其接收并提供服务。

图1 系统请求迁移示意图Fig.1 Demonstration of migration in VoD

2.2 新任务到达时请求迁移

新任务到达时请求迁移分为两种:一种是存在多个媒体服务器存储有被请求的内容时，根据当前各服务器的负载状态对请求任务进行分配，以保证各服务器负载平衡;另外一种是在一个VoD 系统中，当某个热门视频的请求到达时，所有缓存有该视频的服务器都达到负载容量上限，这时该请求将会被阻塞。但这里仍然可以通过迁移一个正在服务中的请求到其他服务器上来服务该新请求。被迁移的请求可能被其他服务器立即接收，也可能在其迁移成功前引起一系列的迁移操作。这种迁移是由调度器在决定迁移之后发起，本文称之为新任务到达时请求迁移。

2.3 故障时请求迁移

故障时请求迁移主要目的是在出现单机故障时保障用户服务不间断。当集群中的某个媒体服务器因为硬件或软件原因出现故障无法为用户提供服务时，调度服务器监测到后，及时将该服务器正在服务的用户请求迁移到其他存储有相应视频内容的服务器上，继续为用户提供服务。如果在迁移过程中发现某个用户请求的视频内容在其他服务器及共享存储上均不存在时，则调度服务器记录任务故障信息并向用户发送消息以中止服务。图2 为故障时迁移前、后VoD 系统媒体流状态。这种迁移由调度服务器在发现故障后发起，本文称之为被动请求迁移，也叫故障时请求迁移。

图2 故障时请求迁移Fig.2 Migration in server failure

2.4 RMTS 算法

图3 展示了传统迁移算法、REM 算法以及本文提出的调度算法中迁移概率pi和当前服务负载li的关系。图3(a)表示传统的迁移算法只有在新到达的请求被阻塞时才进行请求迁移，这种策略称为最后一分钟请求迁移。图3(b)中，REM算法中给出两个阈值Max_th 和Min_th，当负载大于Max_th 时，表示服务器负载很重，任何新请求都将导致迁移事件发生。当负载介于Min_th 和Max_th 之间时，请求迁移发生的概率随着负载的上升线性增加。由于过早迁移浪费服务能力，同时还会使得服务时延增加，而过晚迁移会导致系统负载不均衡。本文的调度算法在新请求到达时，根据各媒体服务器的全局负载状态，决定是否直接将请求分配到某个服务器上还是经过λ(λ＜Γ)步迁移后为其提供服务。迁移概率的计算公式为:

式中:B 和n 为参数，本文在第3 节讨论赋值问题。

图3 迁移概率与媒体服务器负载状态的关系Fig.3 Relationship between migration possibility and server load

当负载li小于阈值时，说明该媒体服务器负载较轻，可继续提供服务。当负载li大于阈值时，表示当前媒体服务器正在为一定数量的用户提供服务，但仍然有能力接收新的请求。为了使系统的整体负载趋于均衡，可以在多个媒体服务器间进行请求迁移。由于请求迁移一方面会影响正在服务的用户，同时会使得新到达的请求服务时延增加。因此，在媒体服务器负载达到设定的阈值Lth后，本文在S 型曲线基础之上进行改进，计算迁移概率pi。从图3(c)中可以看到:改进后的S型曲线在负载接近Lth时计算得到的迁移概率pi较小;当负载接近上限L 时计算得到的迁移概率pi较大，也就是说在服务可用的前提下，只有在负载较高时才进行请求迁移，以减少迁移引入的服务时延。当pi大于系统计算的随机值时，进行负载均衡迁移。由于服务时延将随着迁移路径长度的增长而增加。因此本文对迁移路径长度进行限制以保障用户服务质量。当根据媒体内容分布H和媒体服务器物理连接拓扑Λ 计算得到的迁移路径长度大于系统容忍的最大迁移路径长度Γ时，将拒绝为接收该请求而进行正在服务中的请求迁移。

改进的S 型曲线，当参数n 越大时曲线越快趋近于1。本文中n 是为了接收新请求而进行的迁移路径长度λ 的函数，且随迁移路径长度的增加而快速减小。因此，本文采用负指数函数形式表示，如式(2)所示:

结合式(1)和式(2)，可以得到如下属性:

属性1 调度器接收到新请求R(j)，如果所有存储有媒体内容j 的服务器负载均大于阈值Lth时，为了系统负载均衡需要计算迁移概率;当计算得到的迁移路径长度λ 越大时，n 值越小，迁移概率越小。

由于请求迁移长度直接影响正在服务的用户请求，上述性质避免产生过长迁移路径的迁移行为，保障用户的服务质量。

对于迁移路径的获取，在已知VoD 系统媒体内容分布H 和媒体服务器物理连接拓扑Λ 时，将每个媒体服务器作为一个节点，部署有相同内容的节点之间通过直线相连形成图。本文假设系统中内容保持稳定，没有更新，即图中各节点的连接关系保持不变。当系统部署完成后，可根据改进的Dijkstra 算法［12-13］求得图中任意节点为起始点到其他所有可到达节点的最短路径集合。任务迁移发生时迁移路径为该集合中的成员而无需再重新计算所有的迁移路径。

本文在VoD 系统的调度服务器上展示基于请求迁移的调度算法。调度器收到一个视频j 的请求R(j)时，将执行以下算法:

Step1 对于R(j)，调度服务器根据当前媒体分布状态H、系统各媒体服务器的负载li决定是否需要迁移:①如果服务器Si存储有内容j 且li＜Lth，则将R(j)分配给Si，更新Si负载状态，转到Step 6。②如果所有存储内容j 的服务器Si，均有li＞Lth:如果ω(i)集合中至少有一条路径中紧随Si的节点负载小于L，则计算各路径的长度，再根据式(1)和(2)计算迁移概率pi;否则，转到Step 5;

Step2 调度器生成随机数p，0 ≤p ≤1。如果pi≥p 则转到Step 3;否则转到Step 4。

Step3 调度器向路径上的服务器发送迁移消息。请求迁移在路径上进行，R(j)被保持在调度器节点。

Step4 Si开始服务新到达的请求。调度器更新VoD 系统各节点的负载状态，转到Step 6。

Step5 拒绝请求R(j)。

Step6 调度器等待下一个请求。

RMTS 算法中，每个请求迁移发生前都要找到最优路径。由于迁移过程中新到达的请求保持在调度器，需要找到最优的迁移路径以减少其服务时延和保障系统负载均衡。为了选择最优路径，定义负载均衡方差σ 为:

本文采用加权系数法来权衡迁移路径长度和负载均衡方差，如式(4)所示:

式中:λ 为各个可选路径的长度，λ ＜Γ。

当有多于一条最短路径时，根据属性1 在所有可选迁移路径中选择mp 值最小的路径作为最终迁移路径。

2.5 复杂度分析

通过上面给出的详细步骤可以看出:调度器具有整个系统的全局信息，迁移决策、迁移路径选择以及统计信息更新都由调度器完成。当到达一个新的请求时，调度器计算出迁移概率，如果需要迁移则选择最优的迁移路径。更新统计信息以保持系统信息一致。调度器可以调度下一个请求而不是等待所有媒体服务器中的迁移任务完成，调度器的决策和按步迁移可以并行进行。在这种情况下，RMTS 算法的复杂度取决于迁移决策的计算以及迁移路径的选择，这也是算法中最耗时的部分。由于在系统内容放置以及物理连接确定的情况下，可以预计算出所有可能的迁移路径Ω 以及以节点i 为起始点到其他任意节点的路径集合ω(i)，因此迁移路径选择是一个路径长度排序问题，选择mp 最小的路径即可。时间复杂度是O(logN)，此处N 为可选迁移路径的数量。RMTS算法可以很容易地扩展到由异构服务器组成的VoD 系统，每个服务器可以有不同的存储容量或服务能力。RMTS 算法对服务器的存储容量没有要求。对于存储更多视频副本的服务器，它们可能有更大的服务能力。

前文提到的REM 算法与RMTS 算法的区别主要为:REM 算法中视频服务器服务负载达到两个阈值中间时以一定的概率进行请求迁移，同时其根据最短路径的原则实时计算迁移路径。当系统内容放置以及物理连接确定后，任意两节点间是否可达即确定，故可以提前计算好所有节点到其他节点的迁移路径，避免在迁移决策时计算开销。RMTS 算法在选择迁移路径时使用负载均衡度和服务时延综合评价函数，在保证负载均衡的同时选择最短的迁移路径以减小服务时延。另外，本文限定迁移路径的长度。由于迁移会引入服务时延、影响被迁移的用户服务质量，因此当迁移路径超过阈值时将拒绝进行请求迁移。与REM 算法相比，RMTS 算法能够在更快得到迁移路径的同时保障更小的服务时延。最后，在系统重负载条件下RMTS 算法会优先保障正在服务中的用户服务不受影响。

参数Lth的选择，当服务器处于轻负载时，它有足够的空间来接收新请求，所以请求被阻塞或拒绝的概率很小。此外，每次请求迁移都涉及到控制消息传输成本、接纳控制以及任务调度。在本文的仿真实验中，设定Lth为满负载的70%，从而避免不必要的迁移。

3 试验及结果分析

3.1 试验环境

本文通过仿真试验比较了RMTS 算法与传统最后一分钟请求迁移算法、DASD 算法和REM 算法在请求成功率、服务时延两个方面的性能。试验条件为:模拟20 台媒体服务器和1 个中央调度器，200 个不同大小的媒体内容;每个媒体服务器能够存储1000 个内容，并且能够同时服务120 个用户。仿真VoD 系统中的所有媒体内容存储有不同数量的副本，200 个不同内容所有的存储数量为20 000。同时，假设用户点播请求服务到达率为ξ 个请求每分钟的泊松分布［14］，其中ξ 的取值范围为36 到44。内容点播模型采用θ=0.27的Zipf 分布［15-16］。假设所有内容时长为60 min，模拟VoD 系统初始化时负载为0，则在一个影片播放时间内该系统可以并发支持2400 个用户点播请求，也就是说平均请求到达率约为40 请求/min。分析式(1)(2)，在媒体服务器负载超过112 的情况下，B 值取2680 时，请求迁移概率快速接近于1，即当媒体服务器负载快接近服务能力上限时，发生请求迁移的概率接近于1。模拟系统中α 分别取0.3、0.5、0.7 进行比较。

3.2 结果分析

图4 和图5 分别给出了α=0.3、α=0.5、α=0.7 三种情况下系统请求成功率与系统负载、服务时延与系统负载之间的变化关系。从图中可以看到，随着用户到达率的增加，系统负载上升，请求成功率在下降，服务时延在增加。当系统负载较小时(ξ ＜41)，请求成功率和服务时延性能表现较好。当负载接近媒体服务器的能力上限时，请求成功率下降而服务时延上升。

图4 请求成功率与系统负载之间的关系Fig.4 Relationship between request success rate and load

图5 服务时延与系统负载之间的关系Fig.5 Relationship between service delay and load

从图4 中可以看出，本文提出的RMTS 算法请求成功率在α=0.3、α=0.5、α=0.7 三种情况下均优于REM 算法、DASD 算法以及传统迁移算法。其中在α=0.5 时，RMTS 算法的请求成功率比REM 算法高出14%，而比传统迁移算法高出15%。同时，从图5 中可以看出，当α =0.5时，RMTS 算法的性能表现比α=0.3 和α=0.7时要好，这是因为α=0.5 时迁移路径长度与媒体服务器当前负载对迁移概率的影响具有同等比重，在一定程度上能够改善系统的请求成功率和服务时延。

图6 和图7 分别给出了α 取不同值时用户请求成功率和服务时延的变化，同样可以看出:当α取0.5 时系统的效率和服务时延最优。

图6 请求成功率与α 取值的关系Fig.6 Request success rate as a function of α

图7 服务时延与α 取值的关系Fig.7 Service delay as a function of α

4 结束语

通过对流媒体点播系统中任务调度的研究，提出了基于新任务到达时以及故障时请求迁移的任务调算法。试验结果表明:该算法能够在新任务到达VoD 系统以及系统中出现服务器故障时对任务进行调度，提高系统的请求成功率并降低服务时延。

［1］吴伟.流媒体服务器迁移技术研究［D］.北京:中国科学技术大学信息科学技术学院，2009.Wu Wei.The study of the request migration for streaming server［D］.Beijing:School of Information Science and Technology，University of Science and Technology of China，2009.

［2］Zhou Y，Fu T Z J，Chiu D M.On replication algorithm in P2P VoD［J］.Association for Computing Machinery，2013，21(1):233-243.

［3］Dhage S N，Meshram B B.Design and implementation of video servers for VoD system［J］.International Journal of Cloud Computing，2013，2(1):61-88.

［4］Wolf J L，Yu P S，Shachnai H.DASD Dancing:a disk load-balancing optimization scheme for on-demand video-on-demand computer systems［J］.Sigmetrics Performance Evaluation Review，1995，23(1):157-166.

［5］Dhage S，Meshram B B.Disk load balancing and video ranking algorithm for efficient access in video server［C］∥International Conference on Communication，Information＆ Computing Technology，Mumbai，India，2012:1-6.

［6］Guo J，Taylor P，Zukerman M，et al.On the efficient use of video-on-demand storage facility［C］∥2003 International Conference on Multimedia and Expo，2003:329-332.

［7］Zhao Y，Kuo C C J.Video server scheduling using random early request migration［J］.Multimedia Systems，2005，10(4):302-316.

［8］Mundur P，Simon R，Sood A K.End-to-end analysis of distributed video-on-demand systems［J］.IEEE Transactions on Multimedia，2004，6(1):129-141.

［9］杨戈，廖建新，朱晓民，等.流媒体分发系统关键技术综述［J］.电子学报，2009，37(1):137-145.Yang Ge，Liao Jian-xin，Zhu Xiao-min，et al.Survey of key technologies of the distribution system for streaming media［J］.Acta Electronica Sinica，2009，37(1):137-145.

［10］Barnett S A，Anido G J.A cost comparison of distributed and centralized approaches to video-on-demand［J］.IEEE Journal on Selected Areas in Communications，1996，14(6):1173-1183.

［11］Kao Y C，Lee C N，Wu P J，et al.A network coding equivalent content distribution scheme for efficient peerto-peer interactive VoD streaming［J］.IEEE Transactions on Parallel and Distributed Systems，2012，23(6):985-994.

［12］Chao Y，Hongxia W.Developed Dijkstra shortest path search algorithm and simulation［C］∥2010 International Conference on Computer Design and Applications(ICCDA)，Qinhuangdao，China，2010:116-119.

［13］Dijkstra E W.A note on two problems in connexion with graphs［J］.Numerische Mathematic，1959，1(1):269-271.

［14］Haight F A.Handbook of the Possion Distribution［M］.New York:Wiley，1967.

［15］Kali R.The city as a giant component:a random graph approach to Zipf＇s law［J］.Applied Economics Letters，2003，10(11):717-720.

［16］Kingsley Z G.Human Behavior and the Principle of Least Effort［M］.Boston:Addison-Wesley，1949.