一种面向网络视频缓存系统的拥塞控制与负载均衡的方法

摘要

本发明公开了一种面向网络视频缓存系统的拥塞控制与负载均衡的方法，基于每个缓存的发送队列动态变化来转发用户请求，将用户请求转发至发送队列较短的缓存；具体地，将每一个缓存需要发送至其他缓存的视频数据排列为一个发送队列，则该队列的出队速度为缓存的上行链路带宽，该队列的入队速度为转发至该缓存的其他缓存用户视频请求；当队列满足强稳定条件时，队列长度的平均值是有界的，因此队列没有发生网络拥塞；通过计算并最小化队列的李雅普诺夫漂移，达到负载均衡的目的。本发明可以在满足原系统优化目标的同时，避免缓存流量拥塞，并实现缓存间的负载均衡，提高网络视频缓存系统的整体性能。

说明书

技术领域

本发明属于网络缓存技术领域，尤其涉及一种面向网络视频缓存系统的拥塞控制与负载均衡的方法。

背景技术

网络视频缓存系统在机顶盒等网络设备设置视频缓存存储视频数据，并利用缓存的视频内容应答用户的视频请求，从而降低视频数据的传输延时，提高用户观看视频的用户体验。类似的缓存系统还包括在智能电视设备设置缓存的缓存系统等。在此类缓存系统中，缓存数据除了可以应答本地用户的视频请求外，也可以协助响应较近用户(例如同一个小区内)的视频请求。例如，当用户请求的视频在本地缓存没有存储时，可以从同小区的其他缓存获取视频数据。这样的缓存协作应答机制可以进一步减小视频传输的开销、提高用户的用户体验。基于相近缓存协作机制的机顶盒缓存系统中，需要设置一个缓存系统协调设备来协调缓存间的协作。这个协调设备可以通过云计算等技术来设置一个逻辑管理单元，该逻辑单元与所有机顶盒缓存设备逻辑相连，用以控制缓存。其次，在同一个协作区域内的机顶盒缓存设备可以看做是物理相连的，即任一缓存都可以向其他任意缓存发送视频数据。在上述的缓存协作响应机制中，确定用户请求转发机制是一个核心问题：即确定用户的请求需要被转发至哪一个缓存来响应。在考虑用户请求转发问题时，以往的工作焦点往往基于数据在缓存是否有存储来转发用户的请求，而忽略了响应的缓存应答用户请求的能力(例如链路带宽等)问题。例如，Y.Wang等人在“SHARP:A Scalable Framework forDynamic Joint Replica Placement and Request Routing Scheduling”一文中提出了基于缓存存储内容对用户请求进行联合优化的用户请求转发机制。H.Xie等人在“TECC:Towards Collaborative In-network Caching Guided by Traffic Engineering”一文中提出了基于流量控制的缓存存储机制。但是，仅仅基于缓存存储内容来转发用户请求，可能使某些缓存负载过重，造成网络拥塞以及缓存间的负载不均衡，从而降低缓存系统的性能以及用户观看视频的用户体验。

综上所述，目前的机顶盒缓存系统基于缓存协作的用户请求转发方法中，没有有效控制网络流量以避免网络拥塞、实现负载均衡。

发明内容

本发明的目的在于提供一种面向网络视频缓存系统的拥塞控制与负载均衡的方法，旨在解决目前的网络视频缓存系统基于缓存协作的用户请求转发方法中，没有有效控制网络流量以避免网络拥塞、实现负载均衡的问题。

本发明是这样实现的，一种网络视频缓存系统拥塞控制与负载均衡的方法，所述面向网络视频缓存系统的拥塞控制与负载均衡的方法基于每个缓存的发送队列动态变化来转发用户请求，将用户请求转发至发送队列较短的缓存；具体为每一个缓存需要发送至其他缓存的视频数据排列为一个发送队列，则该队列的出队速度为缓存的上行链路带宽，该队列的入队速度为转发至该缓存的其他缓存用户视频请求；当队列满足强稳定条件时，队列长度的平均值是有界的，因此队列没有发生网络拥塞；通过计算并最小化队列的李雅普诺夫漂移，达到负载均衡的目的。

进一步，所述面向网络视频缓存系统的拥塞控制与负载均衡的方法包括以下步骤：

步骤一，在时刻t，各个缓存向缓存协调设备发送当前缓存系统的情景信息，包括缓存当前的用户请求，缓存当前的上行带宽，缓存当前存储内容，缓存当前的发送队列长度等信息；

步骤二，缓存系统协调设备根据这些情景信息判断用户请求转发策略；

步骤三，缓存系统协调设备根据用户转发策略对该时刻产生的用户请求转发，由相应的协助缓存应答用户当前的视频请求；

步骤四，各个缓存根据转发的用户请求更新队列长度，缓存系统进入下一个时刻t+1，缓存系统周期性执行步骤一至步骤三重新转发用户产生的新视频请求来应对缓存系统情景信息的更新。

进一步，所述步骤二具体包括：

第一步，缓存系统原优化目标为最大化系统效用U(t)，首先根据缓存系统原优化目标U(t)以及各缓存队列长度Q_i(t)，计算修正后的优化目标，该目标为最小化：

第二步，针对新的优化目标求解用户请求转发策略变量求解方法使用CPLEX计算工具。

进一步，所述第一步中对系统原优化目标进行修正的方法基于李雅普诺夫方程与李雅普诺夫漂移计算，计算步骤如下；

缓存i的发送队列强稳定条件定义为：Q(t)表示时刻t所有队列长度的向量，则定义李雅普诺夫方程为即所有缓存发送队列长度的平方值之和。李雅普诺夫漂移为相邻时刻李雅普诺夫方程值的差：Δ(Q(t))＝L(Q(t＋1))-L(Q(t))。则，李雅普诺夫漂移项的上界为：

$\begin{array}{c}\Delta \left(Q\right(t\left)\right)=V\left(Q\right(t+1\left)\right)-L\left(Q\right(t\left)\right)\\ \le B-\underset{i}{\Sigma }{Q}_i\left(t\right)B_i\left(t\right)+\underset{j}{\Sigma }\underset{i}{\Sigma }\underset{i^{\prime }}{\Sigma }{Q}_i\left(t\right)x_{{\mathrm{ii}}^{\prime }}^j\left(t\right)\end{array};$

其中B为常数，满足原优化目标并且同时最小化李雅普诺夫漂移的优化方案为在每一个系统时刻最小化Δ(Q(t))-V·U(t)，则此项的上界为：

$\Delta \left(Q\right(t\left)\right)-V·U\left(t\right)\le B-\underset{i}{\Sigma }{Q}_i\left(t\right)B_i\left(t\right)+\underset{j}{\Sigma }\underset{i}{\Sigma }\underset{i^{\prime }}{\Sigma }{Q}_i\left(t\right)x_{{\mathrm{ii}}^{\prime }}^j\left(t\right)-V·U\left(t\right);$

对上式的最小化等同于最小化修正过后的优化目标，修正后的优化目标在每一个时刻最小化Δ(Q(t))-V·U(t)，优化目标在最大化原系统优化目标U(t)的同时最小化李雅普诺夫漂移项。

进一步，所述步骤四中缓存对发送队列的更新根据以下公式计算：

$Q_i(t+1)=max\left(Q_i\right(t)-B_i(t),0)+\underset{j}{\Sigma }\underset{i^{\prime }}{\Sigma }{x}_{{\mathrm{ii}}^{\prime }}^j\left(t\right).$

进一步，缓存系统的目标为最大化效用值U(t)，设计目标是优化系统原效用函数的同时，并对各个缓存的负载进行均衡；在用户转发决策为变量下，在每一个系统时刻t最小化Δ(Q(t))-V·U(t)；其中V为正可调参数；在拥塞控制与负载均衡下，每一个时刻系统的效用优化目标为最小化下面的目标表达式：

$\underset{j}{\Sigma }\underset{i}{\Sigma }\underset{i^{\prime }}{\Sigma }{Q}_i\left(t\right)x_{{\mathrm{ii}}^{\prime }}^j\left(t\right)-V·U\left(t\right);$

即在最大化效用值U(t)的同时，最小化项。

本发明的另一目的在于提供一种1所述面向网络视频缓存系统的拥塞控制与负载均衡的方法的系统，所述系统包括：

缓存系统协调设备，为逻辑分配给该协作范围内缓存、执行必要调控的具有运算与通信能力的物理设备资源，与各个缓存通过通信链路相连；

网络视频缓存模块，用于通过存储内容提供商的视频数据并且直接应答用户对视频的请求来降低视频传输开销与延时，例如网络视频机顶盒。缓存有特定的存储容量，各个缓存通过通信链路相互辅助应答用户的视频请求；

缓存协作机制模块，位于缓存系统协调设备，用于当用户当前缓存没有存储用户请求视频数据时，将用户请求转发至其他缓存，由后者应答用户的请求；

情景信息模块，位于缓存系统协调设备，用于收集缓存系统情景信息，例如缓存上行带宽，缓存发送队列长度，用户请求数据，缓存当前存储数据等。

本发明提供的面向网络视频缓存系统的拥塞控制与负载均衡的方法，通过在同一个协作范围内缓存间协作应答用户的视频请求来提高用户请求响应。用户通过自己的机顶盒设备接入网络，当用户请求的视频内容在本地缓存未命中时，通过协调设备将用户的请求转发至其他机顶盒缓存设备，并由后者将视频内容传输至请求缓存。本发明基于网络视频缓存之间的缓存协作机制来应答用户的视频请求，提出了一种基于最小化缓存发送队列李雅普诺夫漂移的缓存拥塞控制与负载均衡策略，在转发用户请求时考虑缓存发送队列状态，可以在满足原系统优化目标的同时，避免缓存流量拥塞，并实现缓存间的负载均衡。通过仿真验证，在传统无拥塞控制用户请求转发机制中，缓存发生网络拥塞，而同等条件下本发明可以有效避免缓存拥塞。其次，本发明可以达到缓存间负载均衡的效果。因此，本发明可以有效提高网络视频缓存系统的整体性能。

附图说明

图1是本发明实施例提供的网络视频缓存系统拥塞控制与负载均衡的方法流程图。

图2是本发明实施例提供的网络视频缓存系统结构示意图。

图3是本发明实施例提供的仿真结果示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

本发明基于每个缓存的发送队列动态变化来转发用户请求，将用户请求转发至发送队列较短的缓存，从而达到控制流量与均衡负载的作用；具体地，每一个缓存需要发送至其他缓存的视频数据排列为一个发送队列，则该队列的出队速度为缓存的上行链路带宽，该队列的入队速度为转发至该缓存的其他缓存用户视频请求；当队列满足强稳定条件时，队列长度的平均值是有界的，因此队列没有发生网络拥塞。此外，通过计算并最小化队列的李雅普诺夫漂移，可以达到负载均衡的目的；本发明可以有效的控制缓存发送数据量，避免网络拥塞并达到缓存负载均衡，最终实现机顶盒缓存系统整体性能提升。

下面结合附图对本发明的应用原理作详细的描述。

如图1所示，本发明实施例的面向网络视频缓存系统的拥塞控制与负载均衡的方法包括以下步骤：

(1)在时刻t，各个缓存向缓存协调设备发送缓存系统情景信息，包括缓存当前的用户请求，缓存当前的上行带宽，缓存当前存储内容，缓存当前的发送队列长度等信息。

(2)缓存系统协调设备根据这些情景信息判断用户请求转发策略，算法步骤包括：

(2a)缓存系统的原优化目标为最大化系统效用U(t)。首先根据系统原优化目标U(t)以及各缓存队列长度Q_i(t)，计算修正后的优化目标，该目标为最小化：

(2b)针对新的优化目标求解用户请求转发策略变量求解方法可以使用广泛现存技术，例如使用CPLEX等传统优化问题计算工具。

(3)缓存系统协调设备根据用户转发策略对该时刻产生的用户请求转发，由相应的协助缓存应答用户当前的视频请求。

(4)各个缓存根据转发的用户请求更新队列长度。系统进入下一个时刻t＋1，周期性执行步骤(1)至步骤(3)重新转发用户产生的新视频请求来应对情景信息的更新。

需要说明的是步骤(2a)中所述的对原优化目标进行修正的方法基于李雅普诺夫方程与李雅普诺夫漂移计算，其计算步骤如下。首先李雅普诺夫漂移项的上界为：

$\begin{array}{c}\Delta \left(Q\right(t\left)\right)=V\left(Q\right(t+1\left)\right)-L\left(Q\right(t\left)\right)\\ \le B-\underset{i}{\Sigma }{Q}_i\left(t\right)B_i\left(t\right)+\underset{j}{\Sigma }\underset{i}{\Sigma }\underset{i^{\prime }}{\Sigma }{Q}_i\left(t\right)x_{{\mathrm{ii}}^{\prime }}^j\left(t\right)\end{array};$

其中B为常数。满足原优化目标并且同时最小化李雅普诺夫漂移的优化方案为在每一个系统时刻最小化Δ(Q(t))-V·U(t)，则此项的上界为：

$\Delta \left(Q\right(t\left)\right)-V·U\left(t\right)\le B-\underset{i}{\Sigma }{Q}_i\left(t\right)B_i\left(t\right)+\underset{j}{\Sigma }\underset{i}{\Sigma }\underset{i^{\prime }}{\Sigma }{Q}_i\left(t\right)x_{{\mathrm{ii}}^{\prime }}^j\left(t\right)-V·U\left(t\right)$

对上式的最小化等同于最小化修正过后的优化目标。因此，修正后的优化目标在每一个时刻最小化Δ(Q(t))-V·U(t)，该优化目标在最大化原系统优化目标U(t)的同时最小化李雅普诺夫漂移项Δ(Q(t))。从而在最大化原系统优化目标的同时达到控制网络流量与缓存负载均衡的效果。

还需要进一步说明的是步骤(4)中缓存对发送队列的更新根据以下公式计算：

$Q_i(t+1)=max\left(Q_i\right(t)-B_i(t),0)+\underset{j}{\Sigma }\underset{i^{\prime }}{\Sigma }{x}_{{\mathrm{ii}}^{\prime }}^j\left(t\right);$

如图2所示，本发明实施例的网络视频缓存系统主要包括：

缓存系统协调设备：这里所述的协调设备负责协作范围内的缓存协调，执行必要调控(例如用户请求转发等)，具有运算与通信能力的物理设备资源。例如，使用云计算技术，分配给某小区进行网络视频机顶盒缓存协调的服务器设备资源等。协调设备与各个缓存通过通信链路相连。

网络视频机顶盒缓存模块：这里所述的网络视频机顶盒缓存是指设置在面向网络视频业务的机顶盒内的存储设备。通过存储内容提供商的视频数据并且直接应答用户对视频的请求来降低视频传输开销与延时。机顶盒缓存有特定的存储容量。各个缓存可以通过通信链路相互辅助应答用户的视频请求。

缓存协作机制模块：该模块位于缓存系统协调设备上。当用户当前缓存没有存储用户请求视频数据时，协调设备将用户请求转发至其他缓存，由后者应答用户的请求。

情景信息模块：该模块位于缓存系统协调设备上。用于收集各个缓存上行带宽，缓存发送队列长度，用户请求数据，缓存当前存储数据等系统信息。

机顶盒缓存系统模型：假设系统中有N个缓存，每一个缓存用标号i表示，1≤i≤N。每一个缓存在时刻t的发送队列长度用Q_i(t)表示，1≤i≤N。受限于上行带宽限制，缓存n_i在时刻t能够发送的数据用随机变量B_i(t)表示。假设系统要存储有M个视频，由标号j代表，1≤j≤M。用表示缓存i需要转发至缓存i'的有关视频内容j的数据，即用户请求转发控制变量。则，缓存i的队列长度变化演进可以用下式表示：

$Q_i(t+1)=max\left(Q_i\right(t)-B_i(t),0)+\underset{j}{\Sigma }\underset{i^{\prime }}{\Sigma }{x}_{{\mathrm{ii}}^{\prime }}^j\left(t\right);$

缓存i的发送队列强稳定条件定义为：强稳定条件表示发送队列平均长度是有界的，因此满足强稳定条件的发送队列没有发生网络的拥塞。其次，假设Q(t)表示时刻t所有队列长度的向量，则定义李雅普诺夫方程为即所有缓存发送队列长度的平方值之和。定义这样的二次李雅普诺夫方程可以获取负载均衡的效果：因为李雅普诺夫方程为所有队列长度平方值之和，当李雅普诺夫方程值较大时，至少有一个缓存上的负载较大。因此，在每一个时刻持续降低李雅普诺夫方程的值，一方面可以保持队列长度有界避免拥塞，另一方面可以达到负载均衡的效果。

定义李雅普诺夫漂移为相邻时刻李雅普诺夫方程值的差：Δ(Q(t))＝L(Q(t＋1))-L(Q(t))。假设系统的目标为最大化效用值U(t)，设计目标是优化系统原效用函数的同时，避免产生网络拥塞，并对各个缓存的负载进行均衡。为了满足以上设计目标，可以使用李雅普诺夫理论，就是在用户转发决策为变量下，在每一个系统时刻t最小化Δ(Q(t))-V·U(t)。其中V为正可调参数。通过一系列数学推导变形，可以得到，在考虑拥塞控制与负载均衡下，每一个时刻系统的效用优化目标为最小化下面的目标表达式：

$\underset{j}{\Sigma }\underset{i}{\Sigma }\underset{i^{\prime }}{\Sigma }{Q}_i\left(t\right)x_{{\mathrm{ii}}^{\prime }}^j\left(t\right)-V·U\left(t\right);$

与仅最大化效用值U(t)的传统用户请求转发优化方案相比，考虑拥塞控制与负载均衡的用户请求转发方案中，在最大化效用值U(t)的同时，最小化项。后项的含义是，当缓存i的发送队列较长时，为了达到优化目标，系统会向i转发较少的用户请求(通过控制变量反映)。因此，对传统系统优化目标修正后的优化目标可以避免缓存发生网络拥塞，并能达到控制负载均衡的目标。

下面结合仿真对本发明的应用效果作详细的描述。

对本发明方案的仿真平台包括3个缓存，缓存间可以相互辅助应答用户请求。缓存间两两可以互相通信。我们仿真了1000个系统单位时间，每一个时隙中缓存上行带宽变化。

如图3(a)所示，本方案中缓存的发送队列长度(Backlog)在每一个时隙都严格小于800MB，说明我们的拥塞控制用户转发方案是有效的。图3(b)所示为传统面向视频内容传输开销优化的用户转发方案。在这种方案中，用户请求被转发至传输开销最小的缓存，而不考虑该缓存的网络拥塞状况。如图所示，缓存发送队列随着系统时间持续增长至13000MB。因此这样的转发方案无法避免网络拥塞。与该方案相比，在同样的仿真条件下，我们的面向拥塞控制的用户转发方案是更有益的。

如图3(c)所示，我们显示了在本方案中三个缓存的平均发送队列长度。在仿真中，我们设置缓存1与缓存2之间的传输开销为1；而缓存3到其他两个缓存的传输开销为2。由仿真结果，缓存1与缓存2因为有较小的传输开销，因此其发送队列比缓存3长。其次，缓存1与缓存2的平均发送队列长度相似，这说明了我们的用户转发方案在负载均衡方面是有效的。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。