文摘
在线视频观看的爆炸性需求带来巨大的带宽压力蜂窝网络。高效视频缓存是至关重要的提供高质量的流媒体视频点播(VoD)服务来满足迅速增加的要求从移动用户在线视频观看。传统的缓存算法通常治疗单个视频文件分别和他们倾向于保持最受欢迎的视频文件缓存。然而,在现实中,一个视频通常对应于多个不同的文件(版本)也有不同的大小和不同的视频分辨率。因此,缓存这些文件的一个视频会导致大量的冗余的一个版本以来的视频可以用来生产其它版本的视频通过使用特定的视频编码技术。最近,雾计算把计算能力的边缘网络减少服务提供者和用户之间的距离。在本文中,我们利用雾计算和部署在网络边缘缓存系统。具体地说,我们研究蜂窝网络中基于转码的视频缓存缓存服务器部署在蜂窝网络提供的边缘质量提高手机用户的在线视频点播服务。通过使用代码转换,可以使用一个缓存的视频转换为不同的劣质版本的不同用户所需的视频。我们首先制定基于代码转换的缓存问题整数线性规划问题。 Then we propose a Transcoding based Caching Algorithm (TCA), which iteratively finds the placement leading to the maximal delay gain among all possible choices. We deduce the computational complexity of TCA. Simulation results demonstrate that TCA significantly outperforms traditional greedy caching algorithm with a decrease of up to 40% in terms of average delivery delay.
1。介绍
在线视频观看的爆炸性需求移动用户带来巨大的带宽压力蜂窝网络。一个常见的方式来缓解这样的压力是部署缓存服务器接近最终用户帮助视频扩散1,2]。缓存算法可以分为两种类型:在线算法和离线算法,一般运行在小和大时间尺度,分别。典型的在线算法包括最近最少使用(LRU) (3)和最常用的(LFU) (4),这两个动态缓存做决定基于用户请求到达。相比之下,离线缓存算法对所有视频缓存做决定:缓存是否每个人根据用户的历史数据获取不考虑用户的实时要求。在本文中,我们将重点讨论离线缓存算法的设计。除非另有规定,这个词缓存算法本文意味着离线缓存算法。
传统的离线缓存算法(例如,5,6)假设所有缓存的视频文件分别是独立的和治疗。他们计算每个文件的声望通过计算时间访问的文件已经在过去和缓存最受欢迎的文件。然而,不同的用户可能要求不同版本(也具有不同的分辨率)的视频,和不同版本的一个视频的内容不是独立的,而是有关。因此,在这种情况下缓存的文件可能包含很多冗余的一个版本以来的视频可以用来产生一些其他版本的视频通过使用特定的视频编码技术,如可伸缩视频编码(SVC) [7和转码8]。
SVC被用来提高缓存性能(9]。SVC视频编码成不同的层。SVC,视频的一个版本包含一个或多个视频层,和不同版本的视频分享某些低视频质量层。在此基础上观察,受欢迎程度可以从上面的角度调谐per-video-layer视角。有了这样的了解,(9)提出了一个缓存算法提供视频服务分层通过SVC缓存决定每层级别而不是每个视频级别。然而,SVC-based缓存有以下缺点。首先,它要求SVC-encoded视频文件存储在缓存服务器和还在移动终端SVC-decoding能力;然而,由于高解码复杂性和过度开销(7],SVC不是广泛部署在在线视频点播。这很大程度上限制SVC-based缓存算法的广泛应用在现实中。第二,数量质量版本支持SVC-encoded视频完全等于视频的层数。这很大程度上限制了服务的粒度SVC-encoded服务平台可以提供给用户,他们可能希望各种版本的视频质量。
代码转换也被用于改善在线视频点播系统的缓存性能。不同于SVC编码/解码,转码已经成熟的技术将视频从高质量的任何低质量8]。转换可以很容易地在缓存服务器没有参与的移动客户端。与SVC-based缓存相比,转码基于缓存有两个优点。首先,视频质量将可以进行更细的粒度,以满足不同用户需求。第二,代码转换兼容现有的视频格式,而不需要升级软件在移动终端(客户端)和视频源(源端)。在[10],沈等人提出了一种基于代码转换的网络缓存算法,与缓存的缓存系统转码的视频实时根据用户请求,使缓存替换与LRU算法。然而,这种算法LRU和代码转换的只是一个简单的组合,这很大程度上限制了其缓存性能。此外,使用LRU (10)不能保证每个视频都有一个质量版本缓存服务器,因此多冗余仍在缓存文件。
最近,雾计算把计算能力的边缘网络减少服务提供者和用户之间的距离。在本文中,我们利用雾计算和部署在网络边缘缓存。具体来说,我们专注于研究转码启用缓存。目标是使缓存服务器保持最有价值的视频版本,以减少视频传输的延迟视频请求从缓存大小的所有用户受到约束和有限的带宽在不同的基站之间的联系(合作缓存)。我们首先制定基于代码转换的缓存问题整数线性规划问题。然后提出一个基于代码转换的缓存算法(柠檬酸),该迭代找到位置导致的最大延迟获得视频抓取之间所有可能的选择通过考虑请求到达率的视频文件大小不同的视频版本,以及不同的缓存服务器之间的延迟交货。减少冗余内容,柠檬酸限制每个缓存服务器最多保留一个版本的视频质量。我们推断柠檬酸的计算复杂度。仿真结果表明,我们的柠檬酸算法可以显著减少视频传输延迟与传统的线下贪婪算法相比在5]。
剩下的纸是组织如下。部分2简要回顾相关的工作。部分3描述了高速缓存系统模型和制定最优转换建立独立的缓存和合作缓存问题,分别。节4,我们建议柠檬酸缓存算法。节5,我们执行模拟评价柠檬酸的性能。我们在部分总结本文6。
2。相关工作
传统的离线缓存算法通常单独治疗单个视频文件,倾向于保持最受欢迎的视频文件缓存(5,6]。文献[5)提出了一个合作缓存算法的分布式缓存系统。盯着一个零向量缓存,该算法迭代更新缓存向量通过将文件缓存服务器,这样放置导致的最大性能改进,计算基于每个视频的普及。文献[6)提出了一个缓存算法利用用户利益和视频流行,为了实现缓存效率和用户偏好之间的良好平衡。
然而,在传统的缓存算法,几个文件保存在缓存服务器可能属于同一视频但具有不同的品质,从而导致大量的冗余的一个版本以来的视频可以被用来制造其他版本的视频通过使用某些视频编码/解码技术,如SVC (7和转码8]。
SVC视频编码成不同的层次,不同质量版本的视频分享某些低层次。因此,SVC-encoded视频,声望计算每层的角度从每个视频的角度改变。在这个方向,在9),一个SVC-based缓存算法提高缓存的性能。然而,由于高解码复杂度和额外开销(7,11),SVC不广泛部署在在线视频点播特定资源有限的移动终端。此外,版本质量SVC-based视频的数量可以转换的数量非常有限,它等于其编码层。这很大程度上限制了服务粒度SVC-based编码系统可以提供。
代码转换一直是一项成熟的技术,高质量的视频转换为低质量的实时视频(12]。通过应用转换在缓存服务器,视频质量可以在更细的粒度上进行改造以满足用户的不同需求,并兼容现有的视频格式,而不需要升级软件在移动客户端或视频来源。
在这方面,10)设计一个在线缓存系统,它使用LRU缓存替换和使用代码转换秘密缓存的视频文件。文献[13)设计一个增广电台访问网络模型来评估性能的代码转换的基础网络缓存系统和显示缓存性能可以进一步提高。文献[14]研究了多参数优化模型的缓存存储和转换能力约束,提出了一个合作LRU-based在线视频缓存算法(在线JCCP),它使用缓存服务器之间的合作进一步提高缓存的性能。然而,在这些研究中,LRU只是简单地加上代码转换,和文件的缓存或更换仍然是基于LRU本身,不能确保每个视频都有一个质量版本缓存单个缓存服务器。例如,当一个高版本需要缓存,从缓存中删除低版本的文件(如果有的话)应该是一个更好的选择。然而,使用LRU (10,13,14)不能合并等操作。因此,冗余仍在缓存。
代码转换也造成一定的额外成本。文献[15]指出这个问题,提出了一个在线部分转码缓存方案用于云计算网络,目的是最小化总代码转换和存储造成的额外成本。文献[16)在2018年提出了一个基于云计算的架构来分配缓存系统中虚拟机的转码任务降低流媒体服务提供者的成本,指出基于转码的视频缓存值得进一步研究。此外,由于移动边缘计算能力的显著提高17,18和新代码转换技术的出现19,20.),现在可行的移动边缘缓存系统进行完整的代码转换。
在本文中,我们将重点研究基于代码转换的离线缓存算法。我们的算法本文不同于上述工作在以下方面。首先,它限制了一个缓存服务器最多保留一个版本的视频质量,从而消除不必要的冗余。第二,它的质量决定缓存版本视频缓存根据不同版本的视频请求。
3所示。系统模型和问题公式化
在本节中,我们首先概述基于转码的视频缓存系统提供流媒体服务在移动边缘。然后,我们说明执行代码转换的关键理念建立缓存。最后,我们制定最优转换基于缓存的问题。
3.1。系统模型
我们首先介绍研究下的缓存系统。如图1显示,有缓存服务器系统中,地理上分布的边缘移动网络向移动用户提供在线视频点播服务的基站覆盖。我们假设每个缓存服务器连接到一个基站通过短与无限带宽,为简单起见,我们将相同的序列号分配给一个缓存服务器及其附加基站。每个缓存服务器可以自动译码系统缓存的视频从一个高质量的版本实时低质量的版本。这些缓存服务器都连接到一个远程视频源服务器,所有质量版本的所有的视频,用户可以请求,通过回程网络。在本文中,每个用户被认为是由一个基站,可以从它的本地缓存服务器获取视频数据,视频源服务器,或另一个本地缓存服务器(在合作缓存的情况下)。
我们下一个介绍一个典型的应用场景,如图1为了说明见抓取在这样一个系统的操作。图所示,用户(说)发送一个请求视频质量版本标签 ,即。,a quality version 2 of video 1, to its local cache server 1, which just has a video quality version 。因此,缓存服务器1可以满足请求的转换()()由于本地缓存版本高于要求的版本。我们假设移动用户之间的传输速度和当地基站足够高,这样的交付延迟抓取视频从本地缓存服务器的用户是可以忽略的,和我们进一步假设代码转换可以实时执行缓存服务器上,这样我们不考虑转码延迟。
此外,假设 缓存服务器系统协同工作。一个用户,说在图1,他请求(),但不能让它直接从它的本地缓存服务器2,可以从服务器获取视频也1码()(和发送)用户通过基站2。沿着小路从服务器1到用户 ,我们假设基站1和基站2之间的联系将为每个会话分配一个特定带宽的视频传输和也造成一定的交付延迟。最后,如果请求()的用户不能满足于任何本地缓存服务器,他/她需要从远程数据源服务器获取它。沿着小路从远程视频源服务器的用户 ,我们假设回程链路将为每个会话分配一个特定带宽的视频传输和也造成一定的交付延迟。
我们的目标是找到一个缓存向量将视频文件放在不同的缓存服务器,同时最小化所有用户的平均交货延迟的视频传输。这样的优化有很大的挑战在计算复杂性。例如,考虑有五个层次的品质与两个给定视频,假设每一个图的三个缓存服务器1有一个有限的空间等于最大尺寸质量最高的视频版本。然后,2视频各有5种不同的品质,每个缓存服务器需要选择的版本选择一个视频或两个视频商店,其中每个数字的数量6对应5质量版本的文件+零质量意义不是存储的视频。此外,如果这三个缓存服务器配合,版本选择为他们的视频 ;让我们进一步推广这种计算如下:在一个真正的缓存系统,假设的总数是每个有视频质量和水平缓存服务器的总数,这些缓存服务器的视频版本的选择吗 大量,因此这类优化问题通常是太复杂在多项式时间内得到解决。
在上面的系统模型中,我们假定代码转换可以实时执行缓存服务器上。事实上,代码转换延迟与转码服务器的容量以及负载的转换过程。我们将把这个问题在我们的未来的工作。
接下来,我们将首先定义变量和参数,然后使用制定以下分段的问题;我们将提出一个启发式算法来解决这个问题在下一节。
3.2。符号和参数
制定问题正在研究之前,我们以后在表使用的符号和参数列表1。
我们表示缓存服务器的设置 ,在那里缓存服务器的总数。我们假设一个缓存服务器 有空间的字节缓存视频文件。
假设有视频系统中,每一方都有不同版本的请求,我们使用 和 来表示一组的所有视频和所有的视频版本的集合,分别。每个版本的视频质量,用 给定的大小字节,我们假设 , 。请求的数量为每个视频的版本 从用户根据基站用 ,这被认为是提前知道像在5,9]。
提供一个文件可能导致交货延迟。具体地说,提供一个视频的大小从远程视频源服务器用户基站的细胞会导致延迟的 ,在哪里交付的延迟是一个单位的视频数据从源服务器通过基站用户吗 ,由于有限的带宽分配的回程链路传输。此外,在这种情况下这些缓存服务器协同工作,提供一个视频的大小从服务器用户与基站联系在一起会导致延迟的 ,在哪里交付的延迟是一个单位的视频数据从缓存服务器用户通过基站 ,由于有限的带宽分配在基站之间的联系和基站的传播。我们表示缓存向量组整数 ,每个元素代表版本的视频质量在服务器缓存 ,和特别, 意味着服务器没有任何版本的视频 。我们使用 代表服务器的缓存向量 。
3.3。制定与转码缓存
3.3.1。独立缓存代码转换
我们首先考虑缓存服务器独立运作的情况。在这种情况下,一个用户只能获取一个视频文件从本地缓存服务器(高优先级)或从远程视频源在云中(低优先级)。我们的目标是找到一个最优缓存向量为每个单独的缓存服务器( )同时最小化的平均延迟交付的所有视频抓取用户覆盖的基站 。以来的平均延迟=总交货延迟交付的所有视频抓取除以总数量的请求,请求的总数是假定为一个常数,最小化的目标平均交付延迟相当于最小化总交付延迟(用)。的总交货延迟可以计算如下: 在哪里是一个指标函数等于0和1,分别在“条件”=虚假和真实的。我们解释(1)如下。首先,让我们考虑一个给定的视频质量的版本 要求用户根据基站 。如果视频的缓存版本在服务器能满足这些请求,即 ,我们有 ,这些用户可以获取 从本地缓存服务器直接及时;否则,我们有 ,这些用户需要从远程视频源服务器获取交货延迟 ,在哪里请求文件的总数吗 ,是视频传输的延迟对于每一次这样的请求。考虑所有版本的视频要求,我们有以下总交付延迟(用)获取所有这些版本。 考虑所有的视频和他们所有的质量请求的版本,我们有公式(1)。
最后,我们制定最优转换建立独立缓存缓存服务器如下: 制定(3)两个约束条件。首先,总大小的缓存文件在服务器上不得超过缓存空间 。第二,的价值必须是一个整数,表示这是一个整数规划问题。正如已经提到的部分3.1的计算复杂性(3)是 每个缓存服务器;这样计算太复杂在多项式时间内得到解决 。
3.3.2。合作缓存代码转换
然后我们考虑缓存服务器的情况与对方合作提供高质量的在线视频点播服务。在这种情况下,在所有的服务器包括本地缓存服务器和远程视频源服务器,用户可以获取视频文件从最好的服务器可以满足请求而导致交货延迟最小。我们的目标是找到一个缓存向量本地缓存系统同时最小化所有用户的平均交货延迟。再一次,这一目标相当于总交付延迟(用最小化)的所有视频抓取请求。
的总交货延迟可以计算如下: 在哪里 是一组能满足请求的缓存塞维对于一个给定的视频版本吗 。
我们解释(4)如下。让我们先计算交货延迟的对于一个给定的组合 , ,和 ,即。,transmitting video 满足所有用户请求基站 。一方面,如果没有一个缓存服务器可以满足用户请求,我们有 ,因此有 。因此,用户必须取回 从远程视频源服务器,导致交货延迟 。另一方面,如果至少一个缓存服务器可以满足用户请求,我们有吗 对于每一次这样的服务器,因此有 。然后,在所有这些缓存服务器 ,我们选择最小的缓存服务器延迟基站为了满足视频的请求 ,然后我们的总交货延迟 。在这里,我们假设一对缓存服务器之间的延迟小于远程数据源服务器之间和一个本地缓存服务器。考虑所有版本的视频要求,我们有以下总交付延迟(用获取所有这些版本): 考虑所有的视频和他们所有的质量请求的版本,我们有公式(4)。
最后,我们制定最优转换基础合作缓存问题如下: 两个约束(6(类似的)3)。正如已经提到的部分3.1的计算复杂性(6)是 ;这样计算通常是太复杂,在多项式时间内得到解决。
4所示。基于代码转换的缓存算法
在本节中,我们设计一个基于代码转换的缓存算法(柠檬酸)。
4.1。算法概述
柠檬酸是生成一个缓存向量贪婪的方式,这样它迭代分配一个视频质量版本可用的缓存服务器,导致最大性能在所有选择,直到没有文件可以放置。
柠檬酸工作如下。首先,它初始化一个零向量缓存与 。然后,它迭代更新通过将缓存服务器上的一个视频版本,每次一个视频版放置。给定一组的视频版本被认为是在一组缓存服务器缓存,通常存在多个位置选择在每个迭代中。为每一个可能的位置 (即。,placing video 在服务器),我们计算交付延迟视频(称为后延迟)通过使用(2)或(5),基于独立缓存或合作是否使用缓存,在当前 。此外,我们有一个交付延迟视频前的位置(称为基延迟)。减少延迟(即。,base delay minus the after-placement delay) is called the delay gain associated with the placement. Among all possible placement choices, TCA chooses the choice leading to the maximal delay gain and accordingly updates the caching vector. This process is repeated until no more file can be cached at any of the cache servers or no more video version needs to be considered for caching.
4.2。算法设计
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
首先,一系列的变量初始化1 - 4行,包括(我) 被初始化为一组包含所有可能的位置选择,其中每个元素 代表一个可能的位置,即,它仍然是适用的 在服务器 ,(2)可能的位置 每个缓存服务器 ,(3)一个零向量缓存 ,(iv)一个零向量缓存每个缓存服务器 。
然后,它迭代更新(见第5行线24算法1)。在每个迭代中,6号线发现最好的位置(即。,placing the版本的视频在服务器在所有可能的位置 ,在函数计算延迟获得可能的位置基于当前缓存向量 。后,如果最大延迟增益等于零,柠檬酸会打破循环;否则,它将继续以下操作。10号线调整缓存大小 ,通过删除空间来容纳新的视频版本 并检索先前缓存的视频版本占用的空间 (如果有的话)。11和12行更新 在和 ,分别根据新的选择 ;13和14行删除配售 ,从和 ,因为所有获取的用户请求 从服务器可以满足这个新位置,因此它不再需要缓存低版本的视频吗 。接下来,行15 - 20移除这些位置,不可能意识到由于有限的剩余的缓存空间,和 。后,如果成了空(参见第21行),柠檬酸将打破循环。最后,柠檬酸输出最终的缓存向量 。
柠檬酸可以很容易地推导出的计算复杂度如下。行1 - 4显然需要初始化时间。在第5行和行之间的for循环24日,第6行最高的复杂性和for循环需要最多时间。因此,柠檬酸的计算复杂度 。
5。绩效评估
在本节中,我们进行模拟评价柠檬酸的性能。我们比较两个缓存算法的三个实例,包括柠檬酸的两个实例,采用独立缓存(TCA-I)合作缓存(TCA-C),分别与传统贪婪算法(贪婪的)合作缓存(5]。
5.1。参数设置
我们设置 为模拟缓存服务器,每个拥有相同的缓存大小。违约率的每个服务器之间的传输视频和远程数据源服务器2 Mbps,违约率(即。、合作为视频传输速率)的缓存服务器交付的模式合作缓存设置为5 Mbps。默认的缓存服务器上缓存大小是400 gb。我们假定有1000个视频缓存,所有这些有一小时的播放时间。根据Youtube推荐决议和比特率,每个视频支持5种不同质量级别的视频分辨率,包括240 p, 360 p, 480 p, 720 p和1080 p,对应的视频比特率400,750,1000,2500,和4500 kbps (21]。因此,5000年的总大小的视频版本接近4 TB。
典型的设置用于实证研究在VoD系统后(9,22),1000年的流行视频都要遵循Zipf分布;即。,the最受欢迎的视频将请求的速度成正比 ,在哪里是一个形状参数和设置为0.8,除非另有说明。此外,不同版本的视频被认为是同样由用户请求。
5.2。仿真结果
合作传输速率传输的延迟的影响。对于这个测试,我们进行了一系列的模拟不同合作传播率从2到11 Mbps 1 Mbps的粒度。结果如图所示2,那里的设在合作率和传输设在平均视频传输延迟。三条曲线对应于TCA-C、贪婪和TCA-I,分别。前两种算法采用合作缓存,可以减少交付延迟通过增加合作传输速率。第三种算法使用独立的本地缓存,因此有一个常数的性能与合作传输速率无关。这个图的结果清楚地表明,TCA-C具有最佳性能,因为它充分利用代码转换和合作在不同的缓存服务器缓存。交货延迟的收益在40%和38%相比TCA-I和贪婪,分别。
缓存大小交货延迟的影响。在该测试中,我们进行了一系列的模拟不同的缓存大小从50 GB 800 GB 100 GB的粒度。图3显示了结果。在图3,所有的三条曲线显示类似的下降趋势平均交付延迟与缓存空间增加。此外,对于每一个给定的缓存大小,结果表明,TCA-C显著优于TCA-I和贪婪,减少平均交付延迟高达50%和53%,分别。结果表明,TCA-C可以有效地利用可用的缓存空间,以提高用户体验的视频抓取。
视频的流行分布交付延迟的影响。在该测试中,我们进行了一系列的模拟不同形状参数Zipf从0.4到1.2,0.1的粒度。图4显示了结果。不足为奇的是,所有的模拟算法导致减少交付延迟增加的形状参数 。这是因为一个更大的显示更少的视频是更受欢迎的缓存,这样他们可以满足大部分用户的要求。图4表明TCA-C总是最佳的性能。
6。结论
在本文中,我们研究了基于代码转换的缓存提高分布式视频缓存系统的性能。制定最优基础视频转码缓存问题(即在两种不同的模式。、独立缓存和合作缓存)整数线性规划问题。柠檬酸然后,我们提出了一种基于代码转换的缓存算法,迭代地地方视频缓存服务器版本,导致最大延迟获得在所有可能的选择。仿真结果表明,柠檬酸(当在合作缓存模式)可以显著降低交付延迟与传统贪婪算法相比。
数据可用性
使用的数据来支持本研究的发现可以从相应的作者。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作是由美国国家科学基金会支持部分资助下的中国号。61572071,U1534201, 61531006,和61471339,自然科学与工程研究委员会加拿大(NSERC)(发现格兰特rgpin - 2018 - 03792),和InnovateNL SensorTECH拨款5404-2061-101。