一种在线视频点播服务的动态请求路由方法

摘要

本发明是基于内容分发网络的视频点播系统中的请求路由问题提出的。首先，将终端用户视频请求按照平均比特率与期望观看时间进行分类；其次，将系统抽象为一个受控离散时间排队系统，包括一个分发器与多个数据中心；发明的目标是找到一个动态请求路由策略，使得系统所得利润最大；动态请求问题可建模为一个马尔科夫决策过程；然而，实际系统规模庞大，使得马尔可夫决策问题存在“状态空间爆炸”问题，经典算法无法应用；为了解决这一问题，本发明给出了两种近似求解方法，即贪心请求路由算法与有界马尔可夫决策请求路由算法，这两种近似算法的出发点不同：贪心策略忽略了未来终端用户请求到达的特征，而基于有界马尔可夫决策的策略则忽略了数据中心中的终端用户请求类型。

说明书

技术领域

本发明属于视频点播请求路由技术领域，特别涉及一种在线视频点播服务的动态请求路由方法。

背景技术

随着因特网技术的不断发展，核心网络和接入网络的容量明显提高。目前的应用程序已不再仅提供简单的文本网页，而且可以提供很多高级服务，其中最受欢迎的服务之一是视频点播服务。根据全球最最大的内容交付网络提供商Akamai报道，全世界网络平均传输速度在2010年增长了20％，部分原因是由于网络中高速传输的视频内容。当前互联网上类似于YouTube和Hulu的商业点播视频服务提供商主要是由内容分发网络支持。在RFC3466中，互联网工程任务组将内容分发网络定义为一种覆盖网络，是建立在通用IP网络之上的虚拟网络。内容分发网络包含许多分布在不同区域的数据中心，用户不需要访问源服务器，直接从分布于各地的数据中心的终端服务器取回视频流，避免了网络拥塞和源服务器过载。在基于内容分发网络的视频点播应用中，整个请求路由过程可以通过4个步骤进行描述，如图1所示：1)终端用户到达分发器；2)分发器采集所有数据中心的状态，并计算请求路由策略；3)分发器将目的数据中心的地址等信息返回给终端用户；4)终端用户请求被重定向到指定的数据中心。

可以将终端用户视频请求分类，找到一个动态请求路由策略，使得系统所得利润最大。动态请求问题可建模为一个马尔可夫决策过程。然而，实际系统规模庞大，使得马尔可夫决策问题存在“状态空间爆炸”问题，经典算法无法应用。

发明内容

为了克服上述现有技术的缺点，本发明的目的在于提供一种在线视频点播服务的动态请求路由方法，建立了视频点播服务请求路由问题的马尔可夫决策过程模型，提出了基于贪心策略、有界马尔可夫决策过程的请求路由算法，解决了视频点播中的请求路由问题，从而最大化视频服务提供商的利润。

为了实现上述目的，本发明采用的技术方案是：

一种在线视频点播服务的动态请求路由方法，建立由一个分发器与若干服务器即数据中心构成的视频点播服务系统模型，使用两个标准对用户进行分类：1)视频文件观看期望时间；2)视频文件平均比特率；然后建立数据中心模型，计算用户到达、离去概率，归结为一个标准的离散时间马尔可夫决策过程模型，找到一个动态请求路由策略，使得视频点播服务系统所得利润最大。

所述分发器为一个集中控制部件，收集所有视频点播请求并将其重定向到合适的数据中心中，在一个时间槽内，视频点播服务器将视频流媒体数据传送到其对应的终端用户，在时间槽末尾，一些终端用户会选择关闭流媒体连接并离开视频点播系统，而另一些终端用户则仍然继续观看视频节目，即这些用户驻留在系统中并将在下一个时间槽中持续接受服务器所发来的数据，每接受一个终端用户的视频点播视频请求，视频点播服务系统都会得到相应的经济利益。

在每个时间槽，到达分发器的第i类终端用户请求数λ_i是个随机变量，在视频点播服务中，认为λ_i服从某一稳态分布，即其为一个平稳随机过程，为了避免状态空间无界问题，假设λ_i为一个非负整数随机变量。

本发明用一个离散时间排队系统为每个数据中心进行建模：数据中心j所拥有的资源数为C_j，假设i类终端用户请求将消耗ω_i单位的资源，一个数据中心中的所有终端用户所消耗的资源总量不能超过该数据中心所拥有的资源总量；假设每个终端用户请求至少在系统中驻留一个时间槽，且所有请求离去都发生在时间槽的末尾；假设在每个时间槽内同属一个类型的请求的离去概率相同；假设第i类请求在系统中驻留的时间上界为即个时间槽，则

$>\frac{1}{p_i}-\frac{({\mathrm{Np}}_i+1)·{(1-p_i)}^N}{p_i}=\frac{T_i}{\Gamma }$>

其中，p_i为i类终端用户请求的离去概率，N为系统状态矩阵，其元素n_ij代表数据中心j中i类终端用户请求的个数，Γ为一个时间槽的长度；T_i为i类终端用户请求在系统中的期望驻留时间。由于在视频点播服务中，用户到达具有较强的“昼夜效应”，因此可以对一段时间内的用户到达情况进行统计分析，实地测量得到用户的到达概率。

所述马尔可夫决策过程模型中，在时间点t，分发器采集系统的状态，包括：

1)系统到达向量λ(t)＝{λ_i(t)},i∈I，描述了等待队列中i类终端用户请求的数量；

2)服务器负载矩阵N(t)＝{n_ij(t)},i∈I>

此后，分发器进行决策，决策行为是一个矩阵a(t)＝{a_ij(t)}，描述了重定向到数据中心j上i类终端用户请求的数量，决策完成后，系统时间演进到(t+1)^-，并收到回报R(N(t),a(t))，一些终端用户请求离开系统，这时，系统转换到下一状态。

所述马尔可夫决策过程模型总结如下：

状态：令系统的状态空间为S，其中一个元素即为(λ,N)，实际的系统状态看作一个关于时间的函数，即状态记为(λ(t),N(t))；

决策时间：决策时间为每个时间槽的开始，由于时间槽长度为Γ，因此决策时间为t∈{0,Γ,2Γ,...,nΓ,...}；

行为：在第t个时间槽的开始，分发器进行决策，采取行为a(t)，a(t)受以下条件约束：

$>\underset{j\in J}{\Sigma }{a}_{ij}\left(t\right)\le {\lambda }_i\left(t\right),\forall i\in I---\left(1\right)$>

$>\underset{i\in I}{\Sigma }{\omega }_i\left(a_{ij}\right(t)+n_{ij}(t\left)\right)\le C_j,\forall j\in J---\left(2\right)$>

其中，约束(3)是流守恒约束，含义为分发器重定向到各个数据中心的终端用户请求数量不能超过本时间槽内到达的终端用户请求数量，约束(4)是数据中心的资源即带宽限制；

状态转移概率：表达为：

$>\left(\begin{array}{c}\mathrm{Pr}\left(\right(N\left(t+1\right),\lambda \left(t+1\right)\left)\right|\left(N\left(t\right),\lambda \left(t\right)\right),a\left(t\right))\\ =\left(\begin{array}{cc}0,& if\forall j,n_{ij}(t+1)>n_{ij}\left(t\right)+a_{ij}\left(t\right)\\ \underset{i\in I}{\Pi }{f}_i\left({\lambda }_i\right(t+1\left)\right)·\underset{i\in J}{\Pi }\underset{i\in I}{\Pi }{g}_{ij}^t\left(n_{ij}\left(t\right)+a_{ij}\left(t\right)-n_{ij}\left(t+1\right)\right),& otherwise\end{array}\right)\end{array}\right)$>

回报：表达形式为r–c，其中r与c分别为每服务一个终端用户请求所得到的收入与成本，在第t个时间槽所得的收益为：

$>R\left(N\right(t),\lambda (t),a(t\left)\right)=\underset{i\in I}{\Sigma }\underset{j\in J}{\Sigma }\left(n_{ij}\right(t)+a_{ij}(t\left)\right)·(r_i-c_{ij})$>

其中n_ij(t)+a_ij(t)是在第t个时间槽内数据中心j中i类终端用户请求的数量，r_i-c_ij为数据中心j每服务一个i类终端用户请求所得的净利润。

优化目标：该问题的优化目标是最大化累积回报的期望，用一个无限时间折扣目标函数表示

马尔可夫决策模型来近似有限时间马尔可夫决策模型，其中0≤δ≤1为一个折扣因子。

所述通过贪心请求路由算法或者有界参数请求路由算法获取使得视频点播服务系统所得利润最大的动态请求路由策略。

所述贪心请求路由算法的优化目标是最大化当前时间槽内的回报，具体步骤如下：

该算法的思想是在当前时间槽内接受尽可能多的高回报率终端用户请求。事实上，该算法只需要跟踪每个数据中心的总负载，可以直接以在线(on-line)方式实施

所述有界参数请求路由算法具体步骤如下：

输入：请求路由BMDP问题

输出：区间值函数与策略π

其中IVI(Interval Value Iteration)为区间值迭代算法，IVI将请求路由BMDP问题作为输入。首先选定区间值函数的一个初始值，并反复调用区间迭代函数IVI(其算法如下所示)。算法结束时将会输出一个区间值函数与相应的B-策略π。

与现有技术相比，本发明给出了两种近似求解方法，即贪心请求路由算法与有界马尔可夫决策请求路由算法。这两种近似算法的出发点不同：贪心策略忽略了未来终端用户请求到达的特征，而基于有界马尔可夫决策的策略则忽略了数据中心中的终端用户请求类型。这两种算法都具有较低的计算复杂度，能有效提高英特网内容提供商的收益。

附图说明

图1是视频点播系统架构图。

图2是基于内容分发网络的视频点播服务系统模型。

图3是近似求解p_i示例(在该例中N＝10，Ti＝50s，Γ＝10s。驻留时间上界为100s。此时可近似得到p_i≈0.25。)。

具体实施方式

下面结合附图和实施例详细说明本发明的实施方式。

1.建立系统模型，包括以下几个部分：

表1本发明中所用到的符号及其描述

A.系统模型：使用离散时间受控排队模型对视频点播服务系统进行建模。模型如附图2所示，由一个分发器与若干服务器(数据中心)构成。分发器为一个集中控制部件，收集所有视频点播请求并将其重定向到合适的数据中心中。在一个时间槽内，视频点播服务器将视频流媒体数据传送到其对应的终端用户。在时间槽末尾，一些终端用户会选择关闭流媒体连接并离开视频点播系统，而另一些终端用户则仍然继续观看视频节目，即这些用户驻留在系统中并将在下一个时间槽中持续接受服务器所发来的数据。每接受一个终端用户的视频点播视频请求，云提供商都会得到一些经济利益。

B.符号说明：本发明模型中所用到的符号如表1所示。

2.建立终端用户模型，包括以下几个部分：

A.终端用户模型：在研究大型服务系统时，通常采用终端用户分类的方法。在本发明中，使用终端用户所请求的文件作为分类标准是不现实的，因为视频点播系统中可能会有成千上万种视频文件。此外，当终端用户种类数量变大时，请求路由马尔可夫决策过程问题的状态空间呈指数级增长，使得其难以求解。

B.本发明使用两个标准对用户进行分类：1)视频文件观看期望时间；2)视频文件平均比特率。

第一个标准保证了终端用户有近似相等的离去概率，第二个标准意味着所有用户消耗的资源量相同。λ_i设置：在每个时间槽，到达分发器的第i类终端用户请求数λ_i是个随机变量。在视频点播服务中，可以认为λ_i服从某一稳态分布，即其为一个平稳随机过程。为了避免状态空间无界问题，假设λ_i为一个非负整数随机变量。

3.建立数据中心模型：

每个数据中心都可以用一个离散时间排队系统进行建模：数据中心j所拥有的资源数(如网络带宽等)为C_j。假设i类终端用户请求将消耗ωⁱ单位的资源，一个数据中心中的所有终端用户所消耗的资源总量不能超过该数据中心所拥有的资源总量。与视频直播服务一样，在视频点播服务中，终端用户的请求也会“驻留”在服务器中。假设每个终端用户请求至少在系统中驻留一个时间槽，且所有请求离去都发生在时间槽的末尾。假设在每个时间槽内同属一个类型的请求的离去概率相同。这时有如下结论：假设第i类请求在系统中驻留的时间上界为即个时间槽，则

$>\frac{1}{p_i}-\frac{({\mathrm{Np}}_i+1)·{(1-p_i)}^N}{p_i}=\frac{T_i}{\Gamma }---\left(3\right)$>

其中，Γ为一个时间槽的长度；T_i为i类终端用户请求在系统中的期望驻留时间。

从公式(3)中较难得出p_i的解析解，可采用如下方法来求得p_i的数值解。当N较小时，可以以p_i为变量，绘制公式(3)等号左边的函数图像，并直接通过函数图像得到p_i的值，如附图3所示。当N较大时，公式(3)等号左边第二项趋近于0。此时，可以忽略该项，得到p_i的近似表达式

$>p_i\approx \frac{\Gamma }{T_i}---\left(4\right)$>

为使本发明的目的、技术方案和优点更加清楚，下面作进一步的详细描述。

4.视频点播请求路由马尔可夫决策问题

表2系统动态

A.点播视频请求路由问题可以归结为一个标准的离散时间马尔可夫决策过程模型。系统随时间的变化过程如表2所示。在时间段(t–1,t)内，分发器将到达的终端用户点播视频请求缓存在其等待队列中。在时间点t，分发器采集系统的状态，包括：1)系统到达向量λ(t)＝{λ_i(t)},i∈I，描述了等待队列中i类终端用户请求的数量；2)服务器负载矩阵N(t)＝{n_ij(t)},i∈I>ij(t)}，描述了重定向到数据中心j上i类终端用户请求的数量。决策完成后，系统时间演进到(t+1)^-,并收到回报R(N(t),a(t))，一些终端用户请求离开系统。这时，系统转换到下一状态。综上所述，系统的马尔可夫决策过程模型可总结如下：

状态：令系统的状态空间为S，其中一个元素即为(λ,N)。实际的系统状态可以看作为一个关于时间的函数，即状态可记为(λ(t),N(t))。

决策时间：决策时间为每个时间槽的开始。由于时间槽长度为Γ，因此决策时间为t∈{0,Γ,2Γ,...,nΓ,...}。

行为：在第t个时间槽的开始，分发器进行决策，采取行为a(t)。a(t)受以下条件约束：

$>\underset{j\in J}{\Sigma }{a}_{ij}\left(t\right)\le {\lambda }_i\left(t\right),\forall i\in I---\left(5\right)$>

$>\underset{i\in I}{\Sigma }{\omega }_i\left(a_{ij}\right(t)+n_{ij}(t\left)\right)\le C_j,\forall j\in J---\left(6\right)$>

其中，约束(5)是流守恒约束，含义为分发器重定向到各个数据中心的终端用户请求数量不能超过本时间槽内到达的终端用户请求数量。约束(6)是数据中心的资源(带宽)限制。

状态转移概率：由于到达向量是一个随机向量，且与服务器的负载无关，因此主要受到关注的是状态变量中的N，即服务器负载。容易得到以下系统动态方程：

N(t+1)＝N(t)+a(t)-y(t) (7)

其中，y(t)＝{y_ij(t)}为时间槽t的末尾离开数据中心j的i类终端用户请求数量。显然有0≤y_ij(t)≤n_ij(t)+a_ij(t),i∈I>为y_ij(t)的分布函数，即的显示表达式为：

$>g_{ij}^t\left(n\right)=\left(\begin{array}{cc}\left(\begin{array}{c}{n}_{ij}\left(t\right)+a_{ij}\left(t\right)\\ n\end{array}\right)·{(1-p_i)}^{n_{ij}\left(t\right)+a_{ij}\left(t\right)-n},& p_i^n,n\le n_{ij}\left(t\right)+a_{ij}\left(t\right)\\ 0,& otherwise\end{array}\right)---\left(8\right)$>

令λ_i服从某种离散概率分布分布函数f_i(n)，即f_i(n)＝Pr(λ_i＝n)，则系统转移概率可表达为：

$>\begin{array}{c}\mathrm{Pr}\left(\right(N\left(t+1\right),\lambda \left(t+1\right)\left)\right|\left(N\left(t\right),\lambda \left(t\right)\right),a\left(t\right))\\ =\left(\begin{array}{cc}0,& if\forall j,n_{ij}(t+1)>n_{ij}\left(t\right)+a_{ij}\left(t\right)\\ \underset{i\in I}{\Pi }{f}_i\left({\lambda }_i\right(t+1\left)\right)·\underset{i\in J}{\Pi }\underset{i\in I}{\Pi }{g}_{ij}^t\left(n_{ij}\left(t\right)+a_{ij}\left(t\right)-n_{ij}\left(t+1\right)\right),& otherwise\end{array}\right)\end{array}---\left(9\right)$>

回报：系统回报通常是由云提供商定义的，通用的表达形式为r–c，其中r与c分别为每服务一个终端用户请求所得到的收入与成本。从时间的角度来看，r与c跟终端用户在系统内的驻留时间有关。在第t个时间槽所得的收益为：

$>R\left(N\right(t),\lambda (t),a(t\left)\right)=\underset{i\in I}{\Sigma }\underset{j\in J}{\Sigma }\left(n_{ij}\right(t)+a_{ij}(t\left)\right)·(r_i-c_{ij})---\left(10\right)$>

其中n_ij(t)+a_ij(t)是在第t个时间槽内数据中心j中i类终端用户请求的数量，r_i-c_ij为数据中心j每服务一个i类终端用户请求所得的净利润。

优化目标：该问题的优化目标是最大化累积回报的期望。在实际中系统是一个有限时间马尔可夫决策模型，因为到达分布仅会在一定时间内维持稳态(称该时间段为稳态期)。可以用一个无限时间折扣目标函数表示

马尔可夫决策模型来近似有限时间马尔可夫决策模型，其中0≤δ≤1为一个折扣因子。其原因为稳态期的长度(通常为几个小时的量级)比决策时间槽的长度(通常为几秒的量级)要长得多。

5.贪心请求路由算法

贪心请求路由算法的优化目标是最大化当前时间槽内的回报，而非一段时间内的累计回报。视频点播请求路由问题可以归纳为一个整数线性规划问题：

$>\underset{a\left(t\right)}{max}\underset{i\in I}{\Sigma }\underset{j\in J}{\Sigma }{a}_{ij}\left(t\right)·(r_i-c_{ij})---\left(12\right)$>

约束条件为(5)和(6)。

贪心请求路由算法具体步骤如下：

6.有界马尔可夫决策请求路由算法

A.有界参数马尔可夫决策模型中的一个状态可以看作为马尔可夫决策模型M中一系列状态的聚合状态，且中的参数，如区间转移概率与区间收益函数等，都可以看作是M中同属于一个聚合状态的所有状态的参数范围。以这个角度来看，可以看作为M的一个“较小规模”的近似。

B.请求离去概率区间：假设系统在第t个时间槽处于某一有界马尔可夫决策聚合状态(λ(t),L(t))，若存在n≤L_j(t)+∑_i∈Ia_ij(t)，则在该时间槽内数据中心j中有n个请求离开系统的概率必然在如下区间

$>\left(\begin{array}{c}\mathrm{Pr}\left(Y_j\left(t\right)=n\right)\in [\left(\begin{array}{c}{L}_j\left(t\right)+{\Sigma }_{i\in I}{a}_{ij}\left(t\right)\\ n\end{array}\right)p_{\min }^n{(1-p_{\max })}^{L_j\left(t\right)+{\Sigma }_{i\in I}{a}_{ij}\left(t\right)-n},\\ \left(\begin{array}{c}{L}_j\left(t\right)+{\Sigma }_{i\in I}{a}_{ij}\left(t\right)\\ n\end{array}\right)p_{\max }^n{(1-p_{\min })}^{L_j\left(t\right)+{\Sigma }_{i\in I}{a}_{ij}\left(t\right)-n}]\end{array}\right)$>

其中p_max＝max_i∈Ip_i；

p_min＝min_i∈Ip_i。

请求路由有界参数马尔可夫决策问题可表示为：

状态：令聚合状态空间为S'，其中一个元素为(λ,L)。

决策时刻与决策行为：决策时刻与决策行为与请求路由马尔科夫决策问题相同。

区间转移概率：在BMDP模型中，转移概率是一个闭区间。首先观察到

$>\begin{array}{c}\mathrm{Pr}\left(\left(L\left(t+1\right),\lambda \left(t+1\right)\right)|\left(L\left(t\right),\lambda \left(t\right)\right),a\left(t\right)\right)\\ =\underset{i\in I}{\Pi }{f}_i\left({\lambda }_i\left(t+1\right)\right)·\underset{j\in J}{\Pi }\mathrm{Pr}\left(L_j\left(t+1\right)|L_j\left(t\right),\lambda \left(t\right),a\left(t\right)\right)\\ =\underset{i\in I}{\Pi }{f}_i\left({\lambda }_i\left(t+1\right)\right)·\underset{j\in J}{\Pi }\mathrm{Pr}\left(Y_j\left(t\right)=L_j\left(t\right)+\underset{i\in I}{\Sigma }{a}_{ij}\left(t\right)-L_j\left(t+1\right)\right)\end{array}---\left(13\right)$>

结合以上结论，公式(13)所属区间可表达为

其中Θ_j(t)＝L_j(t)+∑_i∈Ia_ij(t)，Y_j(t)＝L_j(t)+∑_i∈Ia_ij(t)-L_j(t+1)分别表示在第t个时间槽内不区分请求种类的请求到达与离去数量。

区间回报函数：回报包含两部分，第一部分是行为a_ij(t)所得的回报，其值为∑_j∈J∑_i∈Ia_ij(t)(r_i-c_ij)，另一部分是一个闭区间[m·e'L(t),M·e'L(t)]，其中

$>M=\underset{i\in I,j\in J}{max}\{r_i-c_{ij}\}$>

$>m=\underset{i\in I,j\in J}{min}\{r_i-c_{ij}\}$>

区间回报函数可表达为

有界马尔可夫决策请求路由算法具体步骤如下：

输入：请求路由BMDP问题

输出：区间值函数与策略π

其中IVI(Interval Value Iteration)为区间值迭代算法，区间值迭代算法将请求路由有界马尔可夫决策问题作为输入。首先选定区间值函数的一个初始值，并反复调用区间迭代函数IVI(其算法如下所示)。算法结束时将会输出一个区间值函数与相应的B-策略π。

输入：一个有界马尔可夫决策模型一个区间值函数以及一个变量π用来存储当前迭代所产生的策略。

输出：与π

V_↑的升序状态空间排列与V_↓的降序状态空间排列分别存储在序列O_up与O_down中。对于状态空间中的每个独立状态s与行为空间的每个独立行为a，算法计算序列O_up与O_down的序列最大下标r_up与r_down，并通过计算区间状态转移概率的边界P'_up与P'_down得到两个序列最大马尔可夫决策。通过P'_up，可以得到最大化区间值函数上界V_↑'的一个行为集合a。若行为集合a中只包含一个元素，即a＝{a}，则a就是该状态中的B-最优策略，区间值函数下界V_↓'可以马上计算得到。否则，在行为集合中找到一个可最大化区间值函数下界V_↓'的行为a∈a，并将a设为该状态的B-最优策略。