用于分段多媒体的缓存管理器以及用于缓存管理的相应方法

摘要

本发明涉及一种用于管理分段多媒体项的中间缓存的缓存管理器（100）。每个多媒体项可使用多个版本，每个版本代表具有不同质量的多媒体项。缓存管理器（100）包括控制部件（101，102），用于控制片段的预取和收回。控制部件（101，102）至少响应于时间和质量相关的片段间关系（131）。

说明书

技术领域

一般地，本发明涉及在多种质量中可用的分段多媒体项的缓存，例如， 在不同版本中利用不同分辨率（resolution）进行编码的HTTP自适应流 （HAS）视频片段。本发明特别尝试提高多媒体服务器和请求多媒体片段 的客户端之间较小的中间缓存的缓存命中率。

背景技术

现有的超文本传输协议（HTTP）缓存按照与HTTP web内容相类似 的方式来处理分段视频。缓存管理器所使用的用于从缓存存储器收回片段 或从内容服务器预取用于在缓存存储器中存储的片段的典型算法基于最近 最少使用（LRU）或最不经常使用（LFU）机制。

当应用于在多种质量中可用的分段多媒体时，基于LRU或LFU的缓 存管理的主要缺点在于无法使用分段之间的时间依赖性和基于质量的依赖 性的事实，这样的结果是缓存命中率不是优化的。

发明名称为“具有缓存管理的视频优化媒体流”的欧洲专利申请EP 0702491介绍了一种改进的视频缓存，其考虑用于调度大量存储和缓存缓 冲器之间的传输的视频片段之间的时间依赖性。因此，在预取视频片段中 使用具有时间顺序的片段的视频流的属性，从而提升缓存效率。

然而，EP0702491不考虑单个视频项的多个质量的可用性以及客户端 在例如基于资源可用性在这些质量之间动态地切换的可能性。作为结果， 当可以按不同质量请求多媒体项并且所请求的质量可以在多媒体（例如， 视频的HTTP自适应流（HAS））消耗期间自适应地改变时，EP0702491 中公开的缓存算法不优化缓存命中率。

特别对于具有有限容量的中间缓存节点，例如，访问节点中的HTTP 缓存，缓存算法中的改进可能导致缓存命中率的显著增加并且因此在使用 这种缓存时增加收益/成本比率。

因此，本发明的目的在于公开了一种缓存管理器和相应的缓存管理方 法，其解决上面提及的现有解决方案的缺点。更为具体地，目的是公开一 种缓存管理器和具有提升的用于多种质量中可用的分段多媒体的缓存命中 率的相应缓存管理方法。

发明内容

根据本发明，通过缓存管理器来实现上面定义的目标，所述缓存管理 器用于管理多媒体项的片段的中间缓存，所述多媒体项的多个版本是可用 的，每个版本代表具有不同质量的多媒体项，缓存管理器包括控制部件， 用于控制将多媒体项的片段预取到缓存存储器中并且控制从缓存存储器收 回多媒体项的片段，这些控制部件响应于指示多媒体项的多个版本的片段 之间的时间和质量相关的片段间关系的信息。由权利要求1限定这种缓存 管理器。

因此，构成本发明基础的基本思路是使用与片段间关系（时间和质量 相关的）相关的特定知识来提升缓存收回和预取效率。实际上，例如当用 户通过下载具有质量级别Q和片段标识符ID的片段在特定时间点观看视 频时，用户将喜欢观看具有接近于Q的质量级别的片段ID+1的似然相对 较高。更通用地，相比于在时间上与当前消耗的片段离得更远的片段，用 户更可能请求具有当前消耗的多媒体片段的ID随后的ID的片段。此外， 未来请求的多媒体片段的质量级别更可能接近于当前消耗的质量级别。片 段之间的组合时间和质量依赖关系因此应当实现预取在不久的未来更可能 被请求的多媒体片段，并且移除在不久的未来不太可能被请求的片段。明 显地，这将导致提升的缓存命中率，即所请求的片段在缓存中的更高可用 性。

注意的是，可将时间和质量相关的片段间关系与传统标准进行组合， 从而优化缓存命中率，所述传统标准例如是流行度、最后使用的时间和日 期等。如下面将解释的，可进一步利用较少的传统标准来补充时间和质量 相关的片段间关系知识，以进一步优化缓存命中率，所述传统标准例如是 用户简档信息、历史信息和网络负载信息。附加地，系统可以使用被绑定 到内容自身的信息，例如，体育游戏或脱口秀，而且还可以被绑定到指示 典型的时间跳跃点的信息，例如商业活动的开始、采访的结束等。

可选地，如权利要求2所限定的，根据本发明的缓存管理器包括从一 个或多个多媒体呈现描述文件提取时间和质量相关的片段间关系信息的部 件，所述多媒体呈现描述文件例如是与多媒体项相关的清单文件。

实际上，当使用自适应流技术时，典型地在所谓的多媒体呈现描述 （MPD）文件中介绍片段之间的关系，所述多媒体呈现描述（MPD）文 件例如是清单文件。因此，根据本发明的缓存管理器可使用这种清单或 MPD文件以建立与HTTP自适应流会话中的片段之间的关系相关的知识。

进一步可选地，如权利要求3所限定的，控制部件可适于在开始时进 行响应以填充多媒体项的信息。

实际上，例如，在电影开始处，在活动会话和片段间关系上将有较少 的信息可用。因此，在这个时间点处将考虑通用填充信息以控制片段的预 取和收回。

根据权利要求4所限定的进一步可选方面，控制片段的预取和收回的 部件可适于响应于以下内容中的一个或多个：

-用户简档信息

-片段填充信息

-用户历史信息

-会话历史信息

-内容历史信息

-内容拥有者/生产者所提供的内容信息

-多媒体服务器和所述缓存存储器之间的网络负载

-所述缓存存储器和最终用户设备之间的网络负载

-客户端侧的算法信息

因此，片段预取和收回算法可以考虑附加信息。额外信息可以是例如 描述可用于指定用户的典型带宽的用户简档、指示已经请求指定片段的时 间量的片段填充信息、描述例如指定用户的切换行为（zapping behaviour） 的用户历史、描述例如用户停止消耗指定媒体项的典型时间点的内容历史、 描述例如在指定会话中请求的典型质量级别（或多个级别）的会话历史、 多媒体服务器和缓存之间的网络的一部分中的和/或缓存和客户端之间的 网络的一部分中的负载或可用资源、以及与特定客户端侧算法策略相关的 知识。后者例如可以包括与客户端侧的缓冲相关的信息。当平滑流客户端 例如注意到其用于观看视频的缓冲填充级别低于门限值时，其可以自动地 切换到最低可能的质量以避免中断。在缓存中保持相应的低质量片段因此 可以是有价值的策略，其可以优化用于这种客户端的缓存命中率。可以使 用与服务器和缓存之间的网络部分中的负载和可用资源相关的知识来确定 如何聚集地预取片段。

为了控制片段的预取和片段的收回，根据本发明的缓存管理器因此可 能不仅考虑时间和质量依赖的片段间关系，还可以使用前述信息类型的任 意组合，以进一步优化多媒体缓存部署的缓存命中率和收益/成本比率。

如权利要求5进一步指定的，根据本发明的缓存管理器可进一步包括 用于机器学习时间和质量相关的片段间关系的部件。

因此，用于确定从缓存中移除哪些片段和从大量存储预取哪些片段的 软件/硬件可以基于机器学习算法，所述算法动态地调整其自己以适应其所 部属的环境。这样的优点是可以学习对网络中现有客户端的更新或新客户 端的行为。这种方式避免了用于中间缓存节点的过量软件更新。

在如权利要求6限定的根据本发明的缓存管理器的实施方式中，控制 片段的预取和收回的部件可进一步适于保持和/或分配值给缓存存储器中 存储的片段，每个值代表在考虑时间和质量相关的片段间关系的情况下， 将请求多媒体项的版本的相应片段的似然。

实际上，实现本发明的简单方式包括保持用于每个版本的多媒体项的 每个片段的值。这些值代表要请求片段的似然，并且因此还代表在缓存中 保持片段的兴趣。根据在考虑中的片段和相同多媒体项的最近请求的片段 之间的时间关系和质量关系来确定每个值。可以使用最终发生的附加信息 来确定/调整所述值。每次当请求一个或多个片段时，更新所述值。

根据本发明的如权利要求7限定的进一步有利的方面，缓存管理器可 包括重定向部件，适于指示将多媒体会话从第一缓存节点重定向到第二缓 存节点，重定向部件至少响应于将客户端映射到一个或多个缓存节点的网 络拓扑信息。

因此，用于根据本发明来优化预取和片段收回决策的信息可进一步用 于重定向多媒体会话至网络中的另一缓存节点，多媒体会话例如是客户端 的视频流会话。例如，这样在另一缓存节点已将相同的多媒体会话递送给 另一客户端的情况中可能是有利的，最终结果是时间上的轻微延迟。当缓 存节点处理多媒体会话并且观看具有标识符ID和质量级别Q的片段时， 在会话中还会发出对具有标识符ID+1和质量级别Q的请求的似然将是较 高的。因此，可能有利的是，将所述会话请求重定向到处理会话的缓存节 点，所述缓存节点已经处理了相同内容的会话并且在观看片段标识符ID+1 和质量级别Q。

为了确定哪个缓存节点应当处理会话，典型地，在现有技术中使用拓 扑信息并且不考虑与HAS会话相关的专用信息。结果是，传统地将会话 重定向到临近的缓存节点。为了能够有效地重定向多媒体会话，根据本发 明的缓存管理器可使用网络拓扑信息，例如，将客户端映射到一个或多个 位置上临近的缓存节点的列表。诸如缓存节点（即，接收请求的缓存节点 和将会话重定位至其的缓存节点）的实际负载的附加信息，以及与由不同 缓存节点处理的会话相关的特殊信息，包括这些会话的时间和质量信息， 将提升重定向算法的效率。附加信息可包括与会话的期待流行度相关的先 验知识。为了共享网络拓扑信息和与不同缓存节点处理的会话和负载相关 的最终附加信息，必须实现能够在缓存节点间通信这种信息的协议或能够 通过中央平台的调解来分发这种信息的协议。

进一步注意的是，可以按片段级别来控制根据本发明的多媒体会话的 重定向，即通过另一缓存节点来递送会话的一个或多个片段，或可以按会 话级别来控制根据本发明的多媒体会话的重定向，即将整个多媒体会话重 定向到另一缓存节点。

除了权利要求1所限定的缓存管理器，本发明还涉及用于管理多个版 本可用的多媒体项的片段的中间缓存的相应方法，每个版本代表具有不同 质量的多媒体项，所述方法包括：响应于指示多个版本的多媒体项中的片 段之间的时间和质量相关的片段间关系的信息，控制将多媒体项的片段预 取到缓存存储器中以及将多媒体项的片段从缓存存储器收回。由权利要求 8限定这个相应的方法。

如权利要求9所指示的，根据本发明的方法可选地可包括将多媒体会 话从第一缓存节点重定向到第二缓存节点，由此至少使用将客户端映射到 一个或多个缓存节点的网络拓扑信息。

附图说明

图1是根据本发明的缓存管理器100的实施方式的功能框图；

图2示出了当单个会话是活动的时，根据本发明的缓存管理器的第二 实施方式的操作，其中下载多个质量Q中可用的多媒体项；

图3示出了当两个会话是活动的时，根据本发明的缓存管理器的第三 实施方式的操作，其中下载多个质量Q中可用的多媒体项；

图4示出了根据本发明的具有重定向组件的缓存管理器的实施方式的 功能框图。

具体实施方式

图1描述了片段存储或缓存150、片段管理器100和基础传输层160。

片段存储150是包含多个多媒体片段的简单存储器组件。可从片段存 储150请求片段并且可将片段注入片段存储150。附加地，可以监测存储 器组件并且存储器组件将返回与可用的片段相关的信息。

片段管理器100代表根据本发明的缓存管理器的第一实施方式。片段 管理器100负责向客户端对片段的请求进行回答，片段管理器100包含预 取组件102，用于在片段存储150中预取和插入片段，以及收回组件101， 用于从片段存储150收回或移除片段。附加地，当片段存储150中不存在 这些片段时，片段管理器100还负责从远程实体、大量媒体存储请求片段， 并且当决定这样做的时候，有可能在片段存储150中存储这些片段。最后， 片段管理器150还会存储与其看到的请求相关的信息到各种信息组件103 中，信息组件103负责保持与多媒体业务相关的相关数据。这些信息组件 103可以在片段管理器100的内部或外部。

在信息组件103中包含各种组件，所述组件基本上捕获全局和局部信 息以辅助片段收回和预取算法作出他们的决策。图1中示出的实例包括： 具有与指定会话的片段如何按照时间和质量来进行链接相关的信息的列表 文件（或多个列表文件）131、用户简档信息132、与特定用户相关的用户 历史信息133、与特定会话相关的会话历史信息134、与典型地如何消耗特 定内容相关的内容历史信息135、以及与所监测的网络负载136相关的信 息。然而，这是非穷尽列表并且可以在本发明的可替换实施方式的收回和 预取算法中使用其他附加信息。

收回组件101负责确定应当将哪些片段从片段缓存150移除。为了这 样做，收回组件101使用在信息组件103中可用的各种类型信息131、132、 133、134、135和136。

预取组件102负责确定从多媒体大量（mass）存储预取哪些片段。为 了这样做，预取组件102还使用在信息组件103中可用的各种类型的信息 131、132、133、134、135和136。

请求接收器161、请求发送器162、响应接收器163、和响应发送器164 构成去往外部世界的消息接口。基本上，这些提供用于与网络中的其他实 体（例如，客户端和大量存储）进行通信的传输层160。

注意的是，可以在使用可扩展视频编码（SVC）和HTTP自适应流 （HAS）的组合的系统中使用本发明。这例如是在MPEG DASH（HTTP 的动态自适应流）标准规范中。SVC按分级的结构层对不同版本的视频文 件进行编码。基础层代表较低质量版本的视频文件。在基础层上构建增强 层以生成更高质量版本的视频文件。在这种系统中，根据本发明的缓存管 理器所带来的收益甚至更高，这是因为总是对较低层（例如，基础层）要 求片段。而较高的增强层可从缓存中移除，由于基础层是所有版本的视频 文件都需要的，所以可保持基础层。

图2和图3示出了根据本发明原理进行操作的缓存管理器的第二实施 方式的操作。在该第二实施方式中，在每个质量级别（垂直轴Q）为视频 文件（水平轴T）的每个片段保持值。图2示出了单个用户在指定的时间 点下载特定片段的情况，所述特定片段即是图2中的阴影片段。水平虚线 示出了假定用户下载的视频文件的连续片段。在用户下载阴影片段的时间 点处，根据本发明的缓存管理器为其他片段分配值。这些值依赖于时间和 质量相关的片段间关系，并且代表对用户将要请求片段的可能性的测量。 将这种值分配给片段的简单策略可以如下：

-当前下载的片段之后的相同质量级别的首先三个片段增加3。

-相同质量级别的随后三个片段增加2；

-相同质量级别的随后三个片段增加1；

-具有质量级别差为1并且与当前下载的片段标识符具有至多5的差别 的片段标识符的片段增加2；

-质量级别差为1的随后4个片段增加1；以及

-具有质量级别差为2并且与当前下载的片段标识符具有至多5的差别 的片段标识符的片段增加1；

假设，在下载阴影片段之前，所有片段的值为0，图2代表在下载了 阴影片段之后，不同质量级别的片段的值。

图3示出了第一用户下载了第一阴影片段并且第二用户下载了第二阴 影片段的情况中的相同实施方式。第二用户下载的片段构成后来的片段， 并且第二用户下载具有比第一用户观看的片段更高的质量级别的这个后来 的片段。当再次假设在第一和第二用户下载阴影片段之前所有片段的值为 0，图3代表用户和用户2按他们各自需求的质量下载了他们各自的片段之 后，在不同质量级别处的片段的值。图3中的点线进一步代表第一和第二 用户将下载的片段的假设序列。

对所有活动的会话重复上面解释的值的分配，并且将分配给片段的最 终值进行标准化。根据本发明的缓存管理器的收回组件和预取组件应当将 他们的从缓存收回片段和将片段预取到缓存的决策基于这些值。具有较高 值的片段最不可能被收回组件从缓存移除。未在缓存中的具有较高值的片 段可能被预取组件从大量存储预取。

在同样保持片段的重要性值的可替换实施方式中，缓存管理器将值分配 给位于缓存中的特定片段。假设所有的片段具有相同的持续时间。当将片 段从缓存移除时，缓存管理器中的收回组件选择具有最低值的片段。在算 法中，S（m）表示电影m的所有片段的集合。通过代表通常下载片段的 顺序的整数值s和代表对应于片段s的质量的Q（s）来识别每个片段。片 段的缓存重要性是代表其愿意将这个片段保持在缓存中的程度的值。在第 三实施方式中分配这些值的方案如下：

其中：

m代表用户u观看的电影；

s代表用户u观看的电影m的片段的标识符；

q代表片段s的质量；

i代表整数索引；

i_importance代表具有标识符i的片段的重要性值；以及

f（i,s）是用于当知道用户u当前正在观看相同电影m的片段s时， 为片段i计算重要性的增加的函数。

示例函数f（i,s）可以如下：

$f(i,s)=1+\frac{|100-(i-s)|}{1+|Q\left(i\right)-Q\left(s\right)|}+\min (20,\frac{(i-s)|Q\left(i\right)-Q\left(s\right)|}{10})$

这个函数f（i,s）将更高的重要性分配给在时间上接近当前观看的片段 的片段。这个函数f（i,s）还通过让时间上接近的片段的所期望质量的估计 更高并且假设在时间上稍远的片段将具有用于可用的质量版本的更为相同 的重要性，以允许可变的质量，。

在所述第三实施方式中，优选地保存缓存存储器的一部分以用于属于 视频流的初始片段。这将确保位于电影开始处的片段保持可用，其中当使 用之前的算法时位于电影开始处的片段将具有在缓存中的更低似然。

在根据本发明的缓存管理器的第四实施方式中，使用学习机制来学习 请求在时间上或质量上接近于当前观看的片段的片段的似然。一种可能的 技术包括为不同历史请求路径训练Markov链。给定训练集合，可以将请 求片段Q（s+1）的概率估计为P（Q（s+1）︱Q（s），Q（s-1），…，Q （1）），其假设不久的未来（s+1）由HTTP自适应流请求的质量不仅依 赖于当前质量，并且还依赖于历史请求质量。

为了简化计算并且避免数据稀疏，P（Q（s+1）︱Q（s），Q（s-1），…， Q（1））可近似为P（Q（s+1）︱Q（s），Q（s-1），…，Q（s-n））， 其中n表示为所获取的质量路径的长度。参数n需要被优化。类似地，还 可以从训练集合统计地估计P（Q（s+2），Q（s+1）︱Q（s），Q（s-1），…， Q（s-n），…，P（Q（s+t），…，Q（s+1）︱Q（s），Q（s-1），…， Q（s-n））。

在测试中，假定请求路径Q（s），Q（s-1），…，Q（s-n），将最大 似然标准用于基于从训练集合获得的Markov链来选择最不重要的片段。 还可以结合增量学习以自适应地更新Markov链中的参数，从而适合新网 络的条件。可以针对单独客户还有客户集为每个视频单独地完成这种学习。

图4描述了缓存节点的框图，其中缓存管理器100具有重定向组件401。 在图4中使用图1中使用的附图标记，以指代实现相同功能的功能块。图 4所示的缓存节点进一步包含与网络拓扑相关的信息403和与其他缓存节 点相关的信息402，其中可将会话请求重定向到所述其他缓存节点。监测 后台程序组件404负责发送监测信息到其他缓存节点并且从其他缓存节点 获取监测信息。示例算法将工作如下：图4中描述的缓存节点确定更靠近 发出请求的客户端的缓存节点。其然后基于他们与客户端的邻近度对这些 节点排序并且以最接近客户端的缓存节点作为开始。如果这个节点（下面 表示为c）处理用于相同内容的会话，图4的缓存节点确定所述节点是否 将是用于重定向的有效候选。这将按下述方式来完成。假设，在用于相同 内容的所有会话中，请求S用于具有时间标识符ID和质量标识符Q的片 段。候选缓存节点中可用的存储器是X。

初始缓存节点将遵从用于所有候选缓存节点的这个过程，并且当其将 发现重定向决策到达的节点c时，对会话进行重定向。如果发现没有合适 的候选节点c，其将自己处理请求。

尽管参考具体的实施例图解说明了本发明，但是对于本领域技术人员 而言清楚的是，本发明不限于前述说明性实施例的细节，并且本发明可以 以各种改变和变更具体化而不脱离其范围。因此，所给出的实施例应当被 认为在各方面都是说明性的，而不是限制性的，本发明的范围由所附权利 要求而不是由前面的描述指出，因此在权利要求的等同物的含义和范围内 的所有改变也有意包含在其中。换句话说，期望覆盖任何和所有落在基本 底层原理的范围之内并且其本质属性已在本专利申请中要求保护的修改、 变更或等同物。此外，本专利申请的阅读者还将明白，词语“包括”或“包 含”并不排斥其它元件或步骤，词语“一”或“一个”并不排斥多个，并 且诸如计算机系统、处理器或另一个集成单元的单个元件可以实现权利要 求中记载的若干个装置的功能。权利要求中的任何附图标记不应当被解释 为限制所涉及的各个权利要求。术语“第一”、“第二”、“第三”、“a”、 “b”、“c”等，当用在说明书中，或用在权利要求中时，是被引入以便 区分开相似元件或步骤的，并非必然描述顺序或时间次序。类似地，术语 “顶”、“底”、“上”、“下”等被引入是为了描述的目的，并非必然 表示相对位置。应当理解，这样使用的这些术语在合适的环境下是可互换 的，并且本发明的实施例能够以其它顺序或与上文中描述或图解的不同的 方向来进行根据本发明的操作。