用于在内容分发网络中实现分布式内容缓存的方法和装置

摘要

描述了一种内容分发服务器。所述内容分发服务器可以用在内容分发网络(CDN)中。还描述了分布式内容缓存技术。可以在CDN内以高效的、低成本的方式实现所述分布式内容缓存技术。在各种实施例中，通过降低(理想地)最小化与网络中的内容分发相关联的成本函数，来确定在所述CDN内的多个网关设备处缓存的内容。所述成本函数可以考虑到从网关设备向用户分发内容的成本以及与从CDN的集中位置向用户分发内容相关联的成本。

说明书

技术领域

本文所公开的主题总体上涉及数据分发，并且更具体地，涉及从一个 或多个内容提供商到多个终端用户的数字内容分发。

背景技术

内容分发网络(CDN)是用于向网络中的终端用户分发数字内容的系 统。CDN经常由内容提供商所使用以将他们的内容分发给公众。内容提供 商可以维护他们自己的CDN或者他们可以向独立的CDN运营商进行支付 来分发他们的内容。通常，CDN会同意以一定的服务质量(QoS)向用户 分发内容。CDN典型地会操作一个或多个数据中心来支持内容分发。众所 周知的是，数据中心是大型设施，其典型地安置有涉及存储和向用户分发 数字内容的计算机硬件(例如，服务器、路由器、磁盘驱动器等)的大型 阵列。CDN可以拥有(多个)数据中心或者其可以承包一个或多个独立数 据中心签订合同以便于内容分发。

将会意识到的是，CDN可能非常昂贵并且操作复杂。另外，随着不断 增长的对数字内容的需求，CDN正在被要求维护或支持更大的或更多数量 的数据中心以满足需求并且满足其服务质量义务。需要可以用来降低与数 字内容分发相关联的成本和硬件要求的技术、系统和设备。

发明内容

在本文所描述的各种实施例中，提供了使用分布式内容缓存(DCC) 来提高内容分发系统(CDN)的性能和设计的技术和系统。本文中描述的 特征中的一些可以被用于例如提高CDN的操作效率并且降低实现这样的系 统的成本。在一些实施例中，提供了用于在CDN中优化DCC性能的优化 技术。在一些实现方式中，还提供了在CDN中存储内容以允许例如跨网络 中的不同网关或边缘设备对文件进行无缝分发的网络编码技术(或其他编 码技术)。网络编码的使用可以允许与单独文件分割相关联的一些问题得以 避免，因此允许文件在网络上被无缝地分发，而不必关心给定文件的不同 部分的具体位置。

根据本文所描述的概念、系统、电路和技术的一个方面，提供了一种 用在向多个用户分发内容的内容分发网络(CDN)中的机器实现的方法。 所述CDN使用管理内容分发服务的中央服务器以及位于用户位置附近的多 个网关设备，所述网关设备具有数据存储能力以用于缓存将由CDN分发的 内容中的至少一些。更具体地，所述方法包括：收集描述CDN的信息；集 合与用户内容需求相对应的CDN操作的统计；通过使与内容分发相关联的 成本函数最小化来确定将被存储在多个网关设备处的内容，其中，所述成 本函数说明与从服务器进行的内容分发相关联的成本和与从所述网关设备 进行的内容分发相关联的成本，其中，确定内容包括使用所收集的信息和 所集合的统计；以及根据对将被存储的内容进行确定的结果来将内容发送 到所述多个网关设备以使内容在所述多个网关设备上被缓存。

在一个实施例中，在中央服务器处执行收集、集合、确定和发送。

在一个实施例中，所述方法还包括不断地重复收集、集合、确定和发 送，来以高效的方式操作所述CDN。

在一个实施例中，所述成本函数包括说明服务器的分发延迟的项。

在一个实施例中，所述成本函数包括对服务器的负载方差(variance) 的约束。

在一个实施例中，确定将被存储在所述多个网关设备处的内容包括使 用以下优化过程中的至少一个来使所述成本函数最小化：通用近端梯度方 案(GeneralProxyGradientScheme)、内点法(interiorpointmethod)以及 诸如GUROBI和CVX之类的数值求解器。

在一个实施例中，将内容发送到所述多个网关设备以使内容在所述多 个网关设备上被缓存包括经由互联网发送所述内容。

在一个实施例中，与所述CDN相关联的所述多个网关设备通过共同的 互联网服务提供商(ISP)与互联网进行通信，其中，所述中央服务器连接 到所述互联网。

在一个实施例中，将内容发送到所述多个网关设备包括使得所述内容 中的至少一些从不位于中央服务器位置的一个或多个数据中心被发送到所 述网关设备。

在一个实施例中，将内容发送到所述多个网关设备以使内容在所述多 个网关设备上被缓存包括将网络编码的文件区段发送到网关设备。

根据本文所描述的概念、系统、电路以及技术的的另一个方面，为多 个用户提供内容分发服务的内容分发网络(CDN)包括：管理CDN的内容 分发服务的内容分发服务器。在一个示例性实施例中，所述内容分发服务 器被配置为开发用于CDN的缓存方案，以用于在部署于用户位置处或用户 位置附近的多个网关设备处缓存所选择的内容。在一些实施例中，所述缓 存方案可以提高向用户分发内容的效率。在一些实施例中，所述内容分发 服务器被配置为通过使与内容分发相关联的成本函数最小化来开发所述缓 存方案，所述成本函数考虑到与从所述网关设备进行的内容分发相关联的 成本和与从所述CDN的一个或多个其他内容存储位置进行的内容分发相关 联的成本二者。

在一个实施例中，部署在用户位置处或用户位置附近的多个网关设备 处于所述CDN控制之下。

还描述了可以用在CDN或其他网络中的管理内容分发服务的内容分发 服务器。在一个示例性实施例中，内容分发服务器被配置为开发用于CDN 或其他网络的缓存方案，以用于在部署于用户位置处或用户位置附近的多 个网关设备处缓存所选择的内容。在一些实施例中，所述缓存方案可以提 高内容被分发给用户的效率。所述缓存方案可以用于诸如内容分发服务器 之类的系统或服务器中。在一些实施例中，服务器(例如，内容分发服务 器)被配置为通过降低(以及理想地最小化)与内容分发相关联的成本函 数来开发所述缓存方案，所述成本函数考虑到与从所述网关设备进行的内 容分发相关联的成本以及与从所述CDN的一个或多个其他内容存储位置进 行的内容分发相关联的成本二者。在一个实施例中，所述内容分发服务器 被配置为根据所述缓存方案向所述多个网关设备中的各个网关设备分发内 容。

在一个实施例中，所述内容分发服务器被配置为不定期地更新所述缓 存方案以说明CDN中的随着时间的变化。

在一个实施例中，所述内容分发服务器通过互联网耦合到所述多个网 关设备。

在一个实施例中，所述多个网关设备都与共同的互联网服务提供商 (ISP)相关联。

在一个实施例中，所述内容分发服务器被配置为：收集与所述CDN的 当前配置有关的信息；集合与用户内容需求相对应的CDN的操作的统计； 以及使用所收集的信息和所集合的统计来开发用于所述CDN的缓存方案。

在一个实施例中，所述成本函数使用所述内容分发服务器向网关发送 单位内容的成本以及在网关处缓存单位内容的成本。

在一个实施例中，所述成本函数包括说明在所述服务器处的分发延迟 的项。

在一个实施例中，所述成本函数包括对服务器负载方差的约束。

在一个实施例中，所述内容分发服务器被配置为向所述多个网关设备 分发网络编码的内容以使其在所述多个网关设备中被缓存。

根据本文所描述的概念、系统、电路以及技术的又一个方面，提供一 种产品，包括其上存储有指令的一个或多个非暂时性计算机可读介质，当 所述指令由计算系统执行时，执行用在向多个用户分发内容的内容分发网 络(CDN)中的方法。所述CDN可以包括管理内容分发服务的中央服务器 以及位于用户位置附近的多个网关设备，所述多个网关设备具有数据存储 能力以用于缓存所述CDN中的待分发内容中的至少一些。更具体地，所述 方法可以包括以下中的一个或组合：收集描述所述CDN的信息；集合与用 户内容需求相对应的CDN的操作的统计；通过使与内容分发相关联的成本 函数最小化来确定将被存储在所述多个网关设备处的内容，其中，所述成 本函数说明与从所述服务器进行的内容分发相关联的成本以及与从所述网 关设备进行的内容分发相关联的成本，其中，确定内容包括使用所收集的 信息和所集合的统计；以及根据对将被存储的内容进行确定的结果来将内 容发送到所述多个网关设备以使内容在所述多个网关设备上被缓存。

在一个实施例中，所述成本函数包括说明在所述服务器处的分发延迟 的项。

在一个实施例中，所述成本函数包括对服务器负载方差的约束。

附图说明

根据以下对附图的描述，可以更加充分地理解前述特征，在附图中：

图1是示出了根据实施例的内容分发网络(CDN)的框图；

图2是示出了随着CDN内可用的电影文件数量(M)的变化，针对 CDN内的各种网关数量(N)的最优成本值的图；

图3是示出了根据实施例的优化过程的收敛的图；

图4是示出了根据实施例的随着CDN的服务器容量的变化的各种成本 的图；以及

图5是示出了根据实施例的用于对使用DCC的CDN进行操作的示例 性方法的流程图。

具体实施方式

本文所描述的技术、系统和设备允许以高效的且有成本效益的方式将 数字内容分发给网络内的用户。这些技术、系统和设备可以由内容提供商、 内容分发网络(CDN)运营商、以及数据中心运营商使用，以例如降低与 内容分发相关联的成本、复杂度和硬件要求。在各种实施例中，分布式内 容缓存(DDC)技术被用于降低与CDN相关联的数据中心内的硬件要求。 如将要更加详细描述的，DCC涉及将待分发内容的部分或全部存储在网络 的终端点附近(即，用户位置附近)而不是存储在一个或多个中央位置(例 如，数据中心等)。因此，在本文所描述的一些实施例中，内容被存储在与 网络的用户相关联的位于用户位置处或用户位置附近的边缘设备或网关 内。另外，在各种实施例中，给定网络内的存储成本和通信约束，提供了 用于智能选择将被缓存在网络的网关设备内的内容以实现高效的内容分发 的技术。本文所描述的技术、系统、和设备可以被用来在不同类型的网络 中分发内容，包括大型网络和小型网络二者以及私有网络和共用网络二者。

在一些实施例中，提供了一个或多个成本函数以用于提高DCC操作的 效率。可以利用优化技术使成本函数最小化以找到与系统相关联的多个决 策变量的值。决策变量值然后可以被用于选择将被存储在网络的用户网关 内的内容。在一些实施例中，使用网络编码来对要被存储在边缘位置上的 内容进行编码。使用这种方式，可以避免与对内容文件的部分(例如，视 频电影文件的分开的部分)进行分割和排序相关联的问题。使用网络编码 技术，内容文件可以被分为多个编码区段，不需要序列号来重新集合成可 用文件。相反，终端用户仅必须从不同的来源位置收集足够数量的这样的 编码区段以允许解码发生。只要足够数量的线性独立的编码区段被接收以 允许解码，编码片段的实际来源并不重要。

如先前所描述的，CDN典型地使用数据中心以便于向终端用户分发内 容。数据中心是大型设施，集中了有效内容分发所需的许多设备。这种对 设备的集中允许整体成本被降低，包括维护成本和通信成本二者。然而， 这样的集中也具有与其相关联的问题。这些问题可以包括与过度供应、能 量耗散以及到终端用户的距离相关联的问题。任何提供在线服务的公司， 不论规模，都必须将与数据中心相关联的成本考虑为其商业模型的关键组 成部分。

过度供应与这样的事实有关：大多数的数字中心被设计为与峰值需求 相匹配而不是与平均需求相匹配，这极大地增加了所需的服务器数量。由 于它们的物理架构(例如，大量的并发操作的处理器等)，数据中心可能生 成大量的不需要的热量，这些热量需要被移除以保证连续的运行。有时， 移除这些热量可能是一个挑战。数据中心通常还远离网络中的用户位置。 这些大的距离可能需要增加的带宽供应以用于通信，并且还可能针对具有 严格延迟约束的应用(例如，视频流)呈现出问题。

使用分布式内容缓存(DCC)是在执行数字内容分发时降低或消除与 数据中心相关联的一些问题的一种方式。如上文所描述的，DCC涉及将要 被分发给用户的内容中的一些或全部存储在位于用户位置处或用户位置附 近的边缘或网关设备。随着存储价格的不断下降，网关可以配备有大量的 数字存储以用于存储数字内容。在一些实施例中，这些设备也可以配备有 可以用于支持内容缓存的某种级别的数字计算能力。另外，这样的设备通 常通过宽带链路连接到互联网(或其他网络)，因此给予设备充当用于内容 分发的小规模服务器的能力。在一些系统中，与不同用户相关联的网关设 备能够以相对低成本的方式直接彼此直接通信或者通过相应的ISP彼此通 信。在一些实施例中，当在CDN中实现DCC时可以利用这样的低成本的 通信能力，网关以端到端的方式服务其他网关。

为说明上述的想法，考虑想要向用户提供高分辨率、点播(on-demand) 视频服务的有线电视公司所面临的挑战。一方面，有线电视公司可以使用 其CDN以一定的成本将内容分发给用户，该成本取决于所需求的资源量(例 如，通信量、数据中心成本等)。作为替代，有线电视公司可以利用其网络 上的数千个网关的存储器和连通性来卸载CDN功能中的至少一些。如果以 这种方式使用网关，则有线电视公司将必须确定对于给定的例如存储成本、 网络的通信约束和网络可靠性，如何跨不同的网关来分发内容文件。如先 前描述的，本文描述了可以用于确定如何以高效的、成本有效的方式在网 关设备之间分发内容的技术、系统和设备。

图1是示出了根据实施例的内容分发网络(CDN)10的框图。如所示 出，CDN10包括内容分发服务器12，其用于经由互联网20或其他网络来 管理到多个用户14a-14n的数字内容的分发。数字内容可以包括响应于请求 而可以被分发给终端用户的任何类型的内容，包括例如视频文件、音频文 件、软件下载、流媒体、数据文件、文本文件、新闻内容、视频游戏、在 线游戏和/或其他。在以下讨论中，将在视频文件的环境中描述各种内容分 发技术和系统，所述视频文件例如是作为电影点播类型应用的一部分而分 发的电影。然而，应该理解的是，在其他实现方式中，所描述的技术和系 统可以与其他类型的数字内容一起使用。

如图1所示，与CDN10相关联的用户14a-14n中的每个均耦合到相对 应的网关设备16a-16n，所述网关设备16a-16n充当到更大网络(例如，互 联网20)的入口点。每个网关设备16a-16n可以包括允许用户连接到更大 网络的任何类型的设备。例如，网关设备可以包括：机顶盒、家用网关、 WiMax网关、蜂窝网关、有线调制解调器、DSL调制解调器、与蜂窝通信 系统相关联的微微小区、路由器、游戏控制台或具有支持期望的应用程序 的存储和足够计算能力的任何其他设备(诸如桌面计算机或膝上型计算 机)。在一些实施例中，网关设备16a-16n中的一个或多个还可以提供不同 网络之间的某种层次的协议或信号格式转换，但这不是必须的。另外，在 一些实施例中，不同用户14a-14n可以使用不同类型的网关设备16a-16n。 在一些实施例中，网关设备16a-16n可以是由ISP、内容提供商或CDN运 营商提供给用户的设备，尽管也可以使用用户拥有的和/或用户控制的网关 设备16a-16n。

在所示出的实施例中，与CDN10相关联的所有用户14a-14n都通过共 同的互联网服务提供商(ISP)18连接到互联网20。如将要更加详细地描 述的，通过将CDN10限制到共享一个ISP的用户，可以呈现网关设备 16a-16n之间的相对低成本的通信。然而，在一些实施例中，经由多个不同 提供商与互联网(或其他网络)通信的用户可以存在于一个CDN内。参照 图1，网关设备16a-16n经由多个通信链路22耦合到ISP18。这些链路22 可以包括无线和/或有线链路。在一些实施例中，用户网关可以直接连接到 更大的网络而不需要中间的服务提供商(例如ISP等)。

图1中示出的用户14a-14n可以每个都具有与其相关联的用户设备以允 许用户请求、接收以及利用正被分发给他们的数字内容。例如，用户设备 可以包括计算机、电视机、媒体播放器、音频设备和/或其他。例如，在视 频流应用中，可以使用能够播放流视频文件的用户设备。可以另外地或可 替换地使用很多其它类型的用户设备。例如，在一些实现方式中，与用户 相关联的用户设备可以包括局域网设备。例如，用户14a-14n中的一个或多 个可以在相对应的住宅或办公楼内维护局域网(LAN)。与该LAN相关联 的路由器或无线接入点(WAP)可以连接到相对应的网关设备以将该LAN 连接到互联网。将会意识到的是，这样的LAN可以允许多个用户共享网关 设备。

在一些实施例中，用户14a-14n可以每个都表示位于固定用户位置上的 用户，例如在相应的建筑、住宅或其他固定建筑物内的用户。在其他实现 方式中，用户14a-14n中的一些或全部可以是具有移动用户设备的移动用 户。在这些实现方式中，包括用于缓存内容的本地存储设备的网关可以包 括例如为移动用户提供到网络的访问的无线基站(例如，蜂窝系统中的蜂 窝基站、WiMax网络中的WiMax基站等)。在一些其他的实现方式中，无 线基站可以充当中央服务器并且移动设备本身可以充当在本地存储内容的 本地网关。

除了其他方面，CDN服务器12可以是运转的以用于接收和处理来自用 户的对数字内容的请求。由此，例如，CDN服务器12可以接收来自用户 14h的对特定电影的分发的请求。CDN服务器12然后可以确定所请求的电 影在CDN10内被存储在何处，并且使电影从该位置被分发给请求用户。在 其他实现方式中，网关16a-16n自身可以接收来自用户的请求中的一些或全 部，确定被请求的电影在附近的网关设备内的位置，以及促使被请求的电 影文件被分发到请求用户。在一些实施例中，单个的被请求文件可以被分 割在CDN10内的多个不同存储位置之中。在这种情况下，CDN服务器12 和/或网关可以使文件的所有不同部分全部被分发给用户。在使用网络编码 来存储数字内容的实现方式中，与特定文件相对应的编码文件区段可以被 存储在CDN10内的多个地点中。在此场景下，CDN服务器12或网关可以 使编码的分组从各种不同来源被分发给请求用户。在一些实现方式中，对 编码区段的传送可以持续直到已经发送给用户预定数量的独立编码区段为 止或者直到用户发送指示已经接收到能够使解码进行的足够的编码分组 (例如，足够的自由度)的确认消息为止。如上文描述的，在一些实现方 式中，各种网关16a-16n将能够相互通信。这样的通信可以是有线通信或无 线通信。当支持无线通信时，通信可以包括单跳通信和多跳通信。在一些 实施例中，网关可以通过ISP18或经由某种其他的低成本路径(例如，除 互联网以外的路径)相互通信。

在一些实施例中，请求的电影文件可能没有被存储在网关设备16a-16n 中的一个内，或者可能当前不能从网关设备16a-16n中的一个中得到。在此 场景下，CDN服务器12可以决定从其自有的本地存储或者从与CDN10相 关联的一个或多个数据中心26、28将所请求的文件分发给用户。在一些实 施例中，中央服务器12将所有可能的电影文件都本地存储在服务器位置。 在一些其他实施例中，电影文件可以存储在不与中央服务器位于相同位置 的一个或多个数据中心内。在又一些实施例中，电影文件中的一些可以被 存储在服务器位置，而一些可以被存储在一个或多个其他位置。如果所请 求的文件不可从与CDN10相关联的任何来源获得，则CDN服务器12可 以拒绝该请求。

根据本文所描述的一些实施例，提供了用于确定如何以有效的方式在 CDN内布置内容以提供在CDN内的高效数据内容分发的技术和系统。更 具体地，提供了允许CDN确定应该在网络的各个网关内存储哪些内容以产 生相对低成本的操作的技术。在至少一种实现方式中，CDN服务器12可以 被配置为确定哪些内容将被存储在哪个网关设备16a-16n内以产生高效的 和低成本的操作。应该意识到的是，该功能可以可替代地在CDN10内的一 个或多个其他位置处执行。在一些实施例中，该功能可以在CDN10内的多 个位置处以分布式的方式执行。

如将要更详细地描述的，在一些实施例中，定义了一个或多个成本函 数以用于对在CDN内存储内容所涉及的各种成本进行估计。为了确定如何 在CDN内布置内容，可以使用一个或多个优化程序来使成本函数最小化。 定义了决策变量，其可以在优化过程期间变化以达到最小的成本函数。决 策变量的最终值然后可以被用于确定哪些内容应该被存储在CDN10中的 哪个网关设备内。现在将要讨论数学框架，以用于描述可以根据实施例使 用的示例性优化技术。

首先，将定义CDN的多个系统变量。系统变量可以包括，例如：

家用网关的索引集合，其中网关的总数量是N。

CDN中可用电影文件的索引集合，其中，不同电影文件 的总数量由M给出。每个电影的索引也是该电影流行度的排名。

y＝(y₁,...,y_M)：具有M个电影文件中的每个的大小的向量。可以通过将y重 复为Y＝[y,...,y]来形成矩阵。

网关i用于外向传输的传输能力。

P_m,i：在网关i处存在对电影m的需求的概率。P可以是M×N的矩阵， 其在位置(m,i)上的项由P_m,i(即，矩阵P的第i列给出在网关i处的对每 个电影的需求的概率)给出。在一些实施例中，对电影的需求可以被假定 为遵循Zipf分布，该分布已经被确立为用于测量视频文件的流行度的良好 近似[参见例如"ITube,YouTube,EverybodyTubes:AnalyzingtheWorld's LargestUserGeneratedContentVideoSystem；”byChaetal.,Proc.ofthe7th ACMSlGCOMMConferenceonInternetMeasurement,ser.IMC'07,NewYork, NY,USA；ACM,2007,pp.1-14.]。具体地，具有流行度排名j(索引为j)的 电影具有需求概率：

$P_{m,i}=\frac{1/j^{\gamma }}{{\Sigma }_{k=1}^{M}1/k^{\gamma }}$

其中，γ表征该分布。随着γ→0，该分布接近均匀。除非有指定，否 则在本文中将假设：对于所有的i，P_m,i是相同的。

c_s：中央服务器向任何网关传输单位内容的成本。

c_g：在任何网关处缓存单位内容的成本。

S_c：服务器的容量。这是能够从服务器传输给所有用户的内容的最大平 均总容量。

δ_s：服务器负载方差的上限。

α：在服务器处的延迟成本。

如先前所描述的，因为图1中的CDN10中的所有用户都经由共同的 ISP连接到互联网，因此可以假定，在CDN10中网关之间的通信量几乎没 有成本。从ISP的视角来看，这个假定是符合实际的，这是因为ISP中的大 部分成本是由ISP之间的通信量所产生的。只要网关之间的通信量负载低 于容量，ISP的成本就不显著。

以下描述了根据实施例的示例性优化过程的决策变量：

x_i＝[x_i，1，...，x_i，M]^T，i∈χ：在家庭网关i处缓存的每个电影文件M的分数 (fraction)。

X＝[x₁，x₂，...，x_N]：向量x_i的矩阵。

a_i,j,m:来自网关i的、对来自网关j的内容m的需求，如果在网关i 处存在对m的需求的话。a_i,j,m的单位采用内容m的分数形式。可以使 用变量A_m来表示针对文件m的“连接矩阵”。即，项a_i,j,m表示在网关 i请求文件m的情况下，来自用户j的、网关i所需求的文件m的百 分比。

L_m,i：网关i向服务器请求的文件m的分数，i∈χ，i≤m≤M。相应的 矩阵为L。

g_i：在网关i∈χ处所使用的用于缓存M个电影的任何内容的存储空间。

g＝{g₁,...,g_N}：g_i值的向量。

s_m：对来自服务器的文件m的需求的平均总量。

s＝{s₁,...,s_N}：s_i值的向量。

中央服务器向用户供应的内容的平均总量。

根据示例性实施例，下文提供了很多不同的优化问题公式。第一公式 是该问题的基线线性规划(LP)公式。然后将非线性约束和目标添加在该 LP公式之上以针对不同的CDN需要生成期望的解(即，非线性公式)。如 将更详细地描述的，在公式中的每个中，在对决策变量施加各种约束和条 件的同时使成本函数最小化。应该意识到的是，本文所讨论的技术和策略 不限于与本文所描述的各种公式一起使用。即，可以可替代地开发其他公 式，以用于实现本文所描述的那些技术和策略的功能、结果、或好处中的 一个或多个。

现在将对基线线性规划(LP)公式进行描述，在至少一个实施例中， 可以将LP公式表达如下：

公式1.(P1：LP公式)

最小化c_s·1^Ts+c_g·1^Tg

0≤x_i≤1

0≤a_i，j，m≤x_j，m

a_i，i，m＝x_i，m

L_m，i≥0

$\underset{m=1}{\overset{M}{\Sigma }}\underset{j\ne i}{\overset{N}{\underset{j=1}{\Sigma }}}{y}_m{a}_{j,i,m}{P}_{m,j}\le C_i$

各种变量上文已定义。通过优化过程被最小化的成本函数是 c_s·1^Ts+c_g·1^Tg。显而易见的是，该函数包括与从中央服务器进行的内容分 发相关联的成本项以及与网关设备处的内容存储相关联的成本项。上文列 出的各种约束捕捉了可以施加在实施例中的网络和节点上的存储和传输限 制。这些约束可以被推广以捕捉对网络设备和用户需求的不同限制，并且 可以使其适应不同的情况。优化过程将找到使该成本函数最小化的各种决 策参数的值。这些值可以然后被用来确定哪些内容应该被存储在哪个网关 设备处。在一些实现方式中，可以假定，网关的数量、每个网关后的用户 的电影需求分布以及文件的数量和大小是已知的。因此，目标是找到网关 处的最优的(或接近最优的)缓存策略以使网络上的电影传播成本最小化。

在上文所描述的LP公式中，没有施加对服务器平均负载容量的约束。 这是因为，在这样的实现方式中，在目标函数中使用c_s·1^Ts来惩罚服务器负 载的使用是足够的。该LP公式忽略了在服务器处的延迟成本，在一些场景 下延迟成本是非常不希望有的。因此，在改进的公式中，可以向成本函数 添加惩罚项以说明延迟。根据排队理论，已知的是服务器的服务延迟与成 比例，其中，是服务器的负载因子。新的公式为：

公式2.(P2，服务延迟惩罚)

最小化$c_s·1^{T}s+c_g·1^{T}g+\frac{\alpha }{1-\frac{S}{S_C}}$

$s.t.\underset{m=1}{\overset{M}{\Sigma }}{s}_m=S$

S≤S_C

X，L，g，s，A_m适用P1

以上公式2中示出的约束是在上文结合公式1所描述的那些约束的简 化版本。如前所述，可以使这些约束适应不同的设置和用户需求。

在大规模的CDN服务器或数据中心中，经常期望的是限制服务器负载 的变动以便于保持例如系统稳定性和/或电网的稳定性。考虑到这些因素， 可以通过δ_s对服务器负载的方差进行约束，并且根据一些实施例可以使用 非线性规划(NLP)技术来求解LP公式的改进版本。该公式可以被表达为：

公式3.(P3，受约束的服务器负载方差)

最小化c_s·1^Ts+c_g·1^Tg

$\left(\begin{array}{cc}s.t.& \underset{m=1}{\overset{M}{\Sigma }}{s}_m=S\end{array}\right)$

S≤S_C

$\underset{i=1}{\overset{N}{\Sigma }}\underset{m=1}{\overset{M}{\Sigma }}{P}_{m,i}(1-P_{m,i}){\left(y_m{L}_{m,i}\right)}^2\le {\delta }_s$

X，L，g，s，A_m适用P1

在一些实现方式中，可以假定对于同一网关而言，对不同电影文件的 请求是独立的。作为结果，服务器负载的方差可以被表达为：

${\Sigma }_{i=1}^N{\Sigma }_{m=1}^M{P}_{m,i}(1-P_{m,i}){\left(y_m{L}_{m,i}\right)}^2-S^2$

现在将从LP公式开始讨论用于求解上文所描述的公式的技术。在一个 求解方式中，开发了算法以将LP公式转化成采用以下形式的标准LP问题：

minc^Tx

s.t.Ax＝b

x≥0.

使用这种方法，决策变量的数量随N和M快速增长。即，在原始公式 中有大约有个变量，并且需要另外个 松弛变量来将问题转化成标准形式。作为结果，矩阵A快速增长，并且随 着问题规模的增长变得难以计算和操纵。

该问题的基线LP公式可以利用至少两种不同的求解器来求解。可以针 对具有对数障碍函数的LP使用内点法来求解相对较小的问题(N＝10以及 N＝15，M<60)。对于较大规模的问题，可以使用CVX求解器(参见例如 CVX:MatlabSoftwareforDisciplinedConvexProgramming,version2.0,July 2013,http://cvxr.com/cvx/；以及"GraphImplementationsforNonsmooth ConvexPrograms,"byGrantetal.,RecentAdvancesinLearningandControl, ser.LectureNotesinControlandInformationSciences,SpringerVerlagLimited, 2008,pp.95-110,http://www.stanford.edu/～boyd/papers/pdf/graph_dcp.pdf)。 利用在10到40之间变化的N而范围从25到200的M，问题得到解决。在 优化问题中涉及的变量数量的范围大约从5000到680000。尽管与在实际设 置中面临的规模相比，这些示例性求解方式的规模相对较小，然而，应该 相信的是，这些被分析的场景提供了对未来的大规模实现方式的有价值的 洞察。

图2是示出了对于γ＝0.25，随着电影文件的数量从25增长到200，针 对各种N值的最优成本值的图。在这种设置下，在800至900兆字节之间 随机选取电影文件的大小，同时允许每个网关向网络中的所有其他网关供 应大约为一个电影大小的1/3至1/2的通信量。假定在网关处缓存单位内容 的成本相当大地低于从服务器供应单位内容的成本。如预期的那样，最优 成本是N和M二者的递增函数。另一方面，越多的内容倾向于被存储在具 有越高容量的网关以用于供应其他对等网关。

利用方差约束，问题成为简单的二次规划。使用标准二次规划技术来 求解该问题。然而，由于输入矩阵的大小，仅测试了具有相对较小维度的 设置。由于服务器负载的方差被严格约束，所以服务器负载快速减少可以 被观察到。该结果是很直观的，这是因为在网关处缓存的内容量增加并且 大部分的内容分发发生在对等网关之间。

在至少一个实施例中，可以使用广义一阶方法来求解上文所描述的第 二公式(即，具有服务延迟惩罚的公式2)。该问题是凸问题(convex)，但 是目标函数在可行域中是无界的。在一种方式中，可以使用加速通用近端 梯度方案。近端函数可以包括例如平方范数(即，)，考虑 到标准欧几里得范数(其是自对偶的)。可以假定S≤0.95S_c以便于解决由于 目标函数的无界性而可能出现的任何问题。应该注意的是，算法的起始点 应该满足S≤0.95S_c。

简化所使用的符号，则第二公式将具有以下一般形式：

最小化$c^{T}x+\frac{1}{1-\frac{S}{S_c}}$

s.t.a^Tx-S

x∈χ

S≤S_c

其中，χ是公式1的可行域。注意，上面的目标函数可以被表达为P(S) +f(S)，其中，P(·)是线性规划的最优解而f(S)是非线性惩罚。假定 0≤S≤0.95S_c，则应该注意到，对于L＝400/S_c， ||f′(y)-f′(x)||≤L||y-x||。

在梯度下降方案的每次迭代中，标准二次规划被求解。每次迭代的主 要步骤给出如下：

yⁱ←(1-θ_i)xⁱ+θ_izⁱ，

xⁱ⁺¹←(1-θ_i)xⁱ+θ_izⁱ⁺¹.

上述问题是标准的凸问题并且可以使用任何凸规划工具来求解。在一 个实现方式中，由于速度约束而使用CVX。图3示出了针对500次迭代的 方法的演化收敛。如所预期的，算法明显地收敛到最优解。

图4是示出针对不同S_c值的不同成本c_s·1^Ts+c_g·1^Tg的图。注意到， 该成本不包括延迟惩罚。明显地，随着S_c增加，总成本收敛到无惩罚约束 的成本。此外，与网关处的存储成本的下降速率相比，由服务器负载引起 的成本部分以较低速率增加。这表明，对于实际设计，服务器在卸载网关 处的存储需求中起到重要的作用，即使在考虑到显著的延迟惩罚时。另外， 在保证合理的延迟约束的同时，可以取得距最优值至多10％的成本。

图5是示出了根据实施例的用于对使用DCC的CDN进行操作的示例 性方法100的流程图。

矩形元素(以图5中的元素102为代表)在本文中表示“处理块”并 且可以表示计算机软件指令或指令组。应该注意，图5的流程图表示本文 所描述的设计的一个示例性实施例，并且通常遵循所概述过程的在这样的 图中的变形被认为在本文所描述和要求的概念、系统以及技术的范围内。

可替换地，处理块可以表示由诸如数字信号处理器电路、专用集成电 路(ASIC)或现场可编程门阵列(FPGA)之类的功能上等价的电路所执行 的操作。一些处理块可以被手动执行，而其他处理块可以由处理器或其他 电路执行。流程图没有对任何特定编程语言的语法进行描绘。相反，流程 图示出了本领域普通技术人员装配电路和/或生成计算机软件以执行特定装 置所要求的处理而需要的功能性信息。应该注意的是，许多例行的程序元 素，例如对循环和变量的初始化以及临时变量的使用可以不被示出。本领 域普通技术人员将会意识到，除非本文中另外指示，否则所描述的特定顺 序仅是说明性的，并且可以被改变而不偏离本文所描述和/或要求的概念的 精神。因此，除非另外陈述，否则下文所描述的过程是无序的，这表示， 在可能时，可以以任何方便或期望的顺序来执行图5中示出的序列。

图5的方法100假定感兴趣的CDN具有位于或靠近用户位置的多个网 关，所述多个网关具有充足的数字存储空间以用于内容缓存。现在参照图5， CDN可以收集与CDN的整体组成有关的信息(框102)。例如，这些信息 可以包括关于与CDN相关联的网络网关的数量和标识的信息，关于与CDN 相关联的电影文件(和/或其他类型文件)的数量、标识和大小的信息，关 于与CDN相关联的网关的传输能力的信息，关于服务器容量的信息，与从 中央服务器进行的内容分发有关的成本信息、与在网关处缓存内容有关的 成本信息和/或其他信息。还可以集合与CDN操作的某些统计有关的信息 (框104)。该统计信息中的一些或全部可以涉及与CDN中的用户偏好和需 求相关联的统计。例如，该信息可以包括关于与CDN相关联的各种网关处 的电影需求的概率、各种电影文件的流行度排名、关于在一个网关处对缓 存在不同网关处的特定电影的需求的信息、关于在各种网关处用于缓存电 影内容的存储空间的信息、对不同电影的需求的平均总量和/或其他信息。

接下来，通过使针对CDN操作的成本函数最小化，来开发将导致对用 户的高效内容分发的用于在CDN的网关处缓存内容的策略，所述成本函数 考虑到与基于服务器的内容分发和基于网关的内容分发二者相关联的成本 (框106)。成本函数最小化过程将典型地生成一个或多个决策变量的值， 所述决策变量的值然后可以被用于确定内容的哪些项目应该被缓存在哪些 网关内。在一些实施例中，可以使用一个或多个公知的优化技术来使该成 本函数最小化。这些优化技术可以包括例如通用近端梯度方案、内点法以 及诸如GUROBI和CVX之类的数值求解器。可替代地，可以开发定制的 优化过程。在一些实现方式中，可以将本文所描述的公式中的一个(即， 公式1、2或3)用于成本函数。可替代地，可以使用其他公式。所使用的 特定公式可以取决于正在实施的CDN的具体特性。例如，在其中服务器延 迟可能显著的CDN中，运营商可以决定使用上文所描述的包括服务器延迟 惩罚的公式2。在其中服务器负载的方差可能呈现问题的CDN中，运营商 可以决定使用对服务器负载方差施加约束的公式3。

在已经生成不同决策变量的值之后，可以将这些值中的一些或全部传 输到CDN的网关(框108)。如上文所描述的，决策变量值将被CDN(例 如，中央服务器)用来确定如何在网关内缓存内容。然后以期望的方式将 内容分发给各种网关设备以供缓存(框110)。在一些实施例中，当网关接 收到新的缓存内容时，该网关可以在存储新的内容之前丢弃先前存储的缓 存内容。在一些实施例中，中央服务器可以确定当前存储在特定网关中的 哪些内容应该被删除以及哪些新的内容应该被添加，并且指示网关做这件 事。使用这种方法，只有新的内容需要被分发给网关。

在一些实施例中，在CDN寿命期间，可以以重复的方式执行图5中的 方法100。例如，CDN可以被配置为定期地、持续地或在固定时间重复方 法100。可替代地或另外地，CDN可以被配置为在每当检测到预定情况的 时候重复方法100。在一些实现方式中，CDN可以被这样配置：当运营商 感觉在CDN中可能存在低效率时，运营商可以手动地启动方法100。方法 100的目标可以是在CDN的网关中实现带来对用户的高效内容分发的内容 缓存方案。这种高效的内容分发可以允许用户以增强的服务质量(QoS)以 及时的方式来访问内容。理想地，将开发出使CDN中的电影传播的成本最 小化的最优缓存策略，但是也可以生成低于最优的高效缓存方案。

在一种方式中，方法100将主要在相对应的CDN的中央服务器内执行。 然而，也可以采用在其他位置处执行，包括在多个位置处分布式执行。在 一些实施例中，可以假定，网络中缓存和传输的电影文件的任何片段都已 网络编码。

如上文所描述的，在一些实施例中，可以使用网络编码或某种其他编 码技术来对将被存储在CDN内的内容进行编码。当用户稍后请求该内容时， 可以将编码的内容分发给该用户并且该用户将必须在使用前对该内容进行 解码。例如，在使用网络编码来编码所存储的电影文件的CDN中，每个电 影文件可以被分割成多个不同的区段。然后可以针对区段中的每个生成随 机系数。然后可以生成由随机系数加权的不同区段构成的线性组合，以形 成如下编码区段：

其中，a_i为随机系数，S_i是文件区段，而N是文件区段的数量。然后可 以使用带有不同随机系数的相同的文件区段来生成很多另外的编码区段。 可以使用随机数生成器来生成随机系数。用来生成编码区段的实际系数可 以被附加在每个编码区段上以供最终在解码中使用。然后编码区段可以被 存储在CDN内的各种位置。应该意识到，以上描述的用于在CDN中实现 网络编码的技术表示使用网络编码的一种可能的方式。其他方式也是可能 的。

当用户随后请求特定电影文件时，CDN可以将与该电影文件相对应的 编码分组从其被存储的任何位置将所述编码分组分发给用户。显然，因为 区段是被编码的，所以在将区段分发给用户的过程中将不会涉及排序。即， 区段可以从任何位置被取回并分发给用户而不必跟踪序列号。用户将必须 成功地接收一定数量的编码区段才能够对内容进行解码。所需要的编码区 段的数量典型地将与文件被原始分割成的文件区段的数量N相同。另外， 所接收的编码区段必须是彼此线性独立以在解码过程中有用。使用随机生 成的系数典型地将使得每个所存储的编码区段线性独立于其他编码区段。 解码过程典型地涉及求解N个未知数的N个线性方程。

在一种可能的方式中，CDN可以继续向请求的用户发送编码区段，直 到接收到来自该用户的指示已经接收到足够区段的确认(ACK)消息。可 替代地，CDN可以初始地向用户发送固定数量的编码区段(例如，N个或 更多)，而仅在用户指示需要更多的情况下才发送更多。将会意识到，可以 替代地使用用于管理对编码区段的分发的其他技术。

由于N个编码分组需要被解码，CDN可以针对特定文件生成并且存储 N个以上的编码分组。所使用的区段数量和区段的大小可以变化。在上文 所描述的方法100以及类似的方法中，使成本函数最小化的过程可以考虑 到在CDN中网络编码的使用或可用性以确定针对该CDN的缓存方案。然 后可以开发确定哪些网关来缓存与特定内容文件相关联的编码区段的缓存 方案。应该意识到，在其他实现方式中可以使用除网络编码以外的编码方 案。可以使用的一些其他编码方案包括例如里德所罗门(RS)码和其他的 MDS码，但是随机线性编码使编码更容易。

在上文的讨论中，已经描述了各种示例性实施例。对本领域那些普通 技术人员来说将显而易见的是，可以对这些示例性实施例进行修改和变型 而不偏离所公开主题的精神和范围。这些修改和变型被认为在所附的权利 要求的权限和范围内。