Application-layer Overlay Networks

Presentation on theme: "Application-layer Overlay Networks"— Presentation transcript:

1 Application-layer Overlay Networks
应用层网络 Application-layer Overlay Networks

2 覆盖网络（Overlay Network）
网络： 一群互连的、可以相互通信的计算机，定义了主机间通信所使用的编址、路由及服务模型。 覆盖网络： 建立在一个或多个已有网络之上的逻辑网络； 改变底层网络的一个或几个特性，以实现底层网络所不能提供的某种网络服务。 替代覆盖网络的方案： 修改已有网络

3 因特网是一个覆盖网络 因特网是建立在众多物理网络及电信线路上的逻辑网络 增加了一个在网间寻址及路由的IP层 实现数据包跨物理网络的传输

4 覆盖网络的应用 路由（如路由覆盖网络） 寻址（如对等网络） 安全（如VPN） 多播（如MBone） 移动（如移动IP） ……

5 覆盖网络的优点和缺点 优点： 缺点： 一般不需要部署新的设备，不修改或很少修改已有的软件/协议（但需要在已有软件上部署新的软件）。
不需要在每一个节点上都部署新软件。 缺点： 协议栈中增加了一个层次，增加了包头及包处理开销 节点的负担加重了 扩放性问题

6 应用层网络 应用层网络是在因特网上构建的一个完全位于应用层的网络系统。 应用层网络由分布在因特网上的一组主机组成：
为一个或多个应用程序提供下层基础设施（网络服务） 采用与目前因特网不同的方法转发和处理应用程序的数据 由第三方运营和管理，不是当前因特网体系结构的一部分。 应用层网络实际上是基于因特网的大规模分布式应用，因借助网络层的一些技术来进行成员之间的寻址和路由而具有了网络层的某些特征。

7 典型的应用层网络系统 路由覆盖网络 应用层组播 内容分发网络 P2P系统

8 1 路由覆盖网络 因特网路由策略仅反映ISP对开销和运行效率的考虑，端用户和应用程序无法参与。
对于有些应用来说，因特网路由协议（OSPF/RIP、BGP）所选的路由不能满足其要求。 路由覆盖网络的目的是为上层应用提供更好的路由服务，满足其特殊的应用需求。

9 1.1 弹性覆盖网络 Resilient Overlay Networks（RON）
RON是为解决BGP路由失效恢复慢的问题而提出的，其设计目标为： 快速检测和恢复路由失效 20秒内检测到路由失效（停运或性能下降）并恢复 紧密集成路由选择与应用 允许应用定义路由失效和对失效的响应 允许应用选择适合自己的路径度量来选择路径 灵活的策略路由 允许针对单个用户或主机定义路由策略

10

11 RON概述 RON是建立在已有因特网路由结构上的一个应用层覆盖网络。

12 RON体系结构模型 RON客户通过管道（conduit）与RON节点交互 Probes负责探测虚链接状态 Router实现路由协议
Forwarder提供分组转发功能 性能数据库保存虚链接状态信息（延迟、分组丢失率、链路吞吐量 ）

13 RON节点 RON节点是运行了RON软件的主机，实现和路由器类似的功能。
每个节点及时探测到其余节点的虚链接状态，保存在本地的性能数据库中。 RON的设计目标是为一组RON客户（使用RON转发数据的应用程序 ）提供更可靠的IP路由机制。

14 RON工作过程 第一个RON节点（入节点）对分组进行分类，决定分组要使用的路径类型（低延迟或高吞吐率等），为其选择一条路由。
若下一跳为一个RON节点，入节点为分组封装一个RON报头（包含一个流标签），发送到下一个RON节点。 入节点对后续到达的属于同一个客户的分组标上相同的流标签，直接查找流缓存表转发。 后续RON节点根据目的地址和流标签决定下一跳（不再进行分类）。 最后一个RON节点（出节点）将分组交给RON客户。

15 RON路由的特点 支持不同的路由策略： 使用不同的链路度量参数维护多条路径 根据RON客户程序的需要选择最合适的路径

16 RON路由的工作要点 路径评估： 节点使用停运检测（outage detection）算法，主动探测到其它RON节点之间的虚链路是否工作。
针对每一种路径度量（延迟、丢包率、吞吐率），给出表明路径有多“好”的数值。 链路状态传播： 节点周期性地从本地性能数据库中取出到其它节点的各种路径度量的汇总信息，通过RON本身的网络发送。

17 路由表构成 针对每一种路由策略计算一组路由表，每一个路由表针对一种路径度量计算得到。 路由表的层次结构： 每个策略标签指向一个路由偏好表。
每个路由偏好对应一种路径度量的路由表。

18 RON转发 转发器检查每个到来分组的RON报头，确定要发给本地客户还是一个远程节点：
如果去往本地客户，利用RON报头中的packet type将数据包交给对应的RON客户。 如果flow ID匹配流缓存表中的一个表项，使用表项中的路由信息。 如果flow ID不匹配流缓存表中的任何表项，利用RON报头查找路由表。

19 RON报头结构

20 路由表查找过程 路由表查找分三步完成： 基于策略类型查找 基于路由偏好查找 基于目的地址查找

21 1.2 服务覆盖网络 Service Overlay Networks（SON）
每个ISP只关心自己网络的性能，并只对自己的用户提供服务保证。 BGP只能找到一条可达的路由，无法保证端-端应用性能。 SON是为了在因特网上提供端-端服务质量（Quality of Service，QoS）而提出的，以方便创建和部署QoS敏感的增值业务。

22 SON的实现基础 SON服务商通过双边服务协议（Service Level Agreement，SLA）从各个ISP购买具有一定QoS保证的带宽，在已有因特网上构造一个逻辑的端-端服务投送网络。 用户通过业务合同，直接向SON服务商付费来使用SON提供的增值服务。

23 SON体系结构 SON由服务网关连接而成 两个服务网关之间的逻辑连接由底层ISP提供，带宽和服务质量由双边SLA保证。

24 SON的优点 引入一个新的流量聚合层次（服务聚合）： 解除了应用服务与网络服务的耦合： 减小了管理和控制网络服务的复杂性
ISP按流量所属的SON进行流量聚合。 解除了应用服务与网络服务的耦合： ISP根据SLA设置数据传输服务（粗粒度）。 SON采用与服务相关的带宽管理、流量工程和QoS保证机制，确保服务的端-端服务质量（细粒度）。 减小了管理和控制网络服务的复杂性 允许灵活地创建和部署新的增值服务

25 1.3 面向服务的因特网 Service Oriented Internet（SOI）
覆盖网络的缺点： 由于完全不考虑网络层，一定程度的低效率是不可避免的。 有些覆盖网络提供的服务需要底层网络的支持才能发挥作用。 有些功能在多个覆盖网中重复实现。 服务覆盖网下面需要一个底层基础架构，解决覆盖网的低效问题，并支持新的应用需求。

26 SOI概述 SOI在逻辑上分离数据传输网络和服务覆盖网络： 服务覆盖网络被抽象成服务云，在多个地方与数据传输网络接口。
数据传输网络：大致对应当前的自治系统，为服务覆盖网提供比特管道服务。 服务覆盖网络：由服务提供商运营，向订户（服务订购者）提供特殊的增值服务。 服务覆盖网络被抽象成服务云，在多个地方与数据传输网络接口。 用户请求在数据网络上被路由到某个服务云的最近（或最合适）入口，由服务云中的某个主机服务。

27 SOI体系结构

28 SOI概述（续） 数据网络与服务网络逻辑分离的好处： 实现逻辑独立性的机制：
允许这两种网络独立进化，在支持已有服务的同时方便未来因特网服务的灵活部署。 实现逻辑独立性的机制： 彻底分离数据网络与服务网络的编址、路由和转发机制 每个服务云可以独立实现自己的编址、路由和转发机制

29 SOI的抽象 SOI是建立在已有IP网络之上、为灵活部署新的因特网服务而提供的一个公共平台。 SOI架构基于三个重要的抽象： 服务云
面向服务的编址方案（服务云，云中的对象） 服务层（服务网关，服务存在点）

30 （1）服务云 服务云是一群部署在因特网上、相互协作向用户提供应用服务的服务实体（如服务器、代理、缓存、内容交换机等）。
服务云是一个虚拟的服务覆盖网络，依靠下层网络域在因特网范围传输数据。 服务云和因特网的接口称为服务存在点，数据对象进出服务云只能通过服务存在点。

31 （2）面向服务的编址方案 SOI的编址方案提供服务云及服务云中对象的位置无关标识：
每个服务云被分配一个固定长度（32位）的ID（称sid），由一个中央权威机构管理。 服务云中的对象用一个对象ID（称oid）标识，其语法和语义由各个服务云定义，只在服务云内部使用。

32 命名与名字解析 服务云的命名与解析： 对象的命名与解析： 将两级地址的解析分开，增加了灵活性和安全性。
每个服务云大致对应了目前具有两层或三层域名的一个机构（如yahoo.com），机构的域名就作为服务名。 可以重用DNS或建一个类似的名字解析系统，将服务名解析为sid。 对象的命名与解析： 服务云根据自己的商业需要定义对象的命名和编址系统。 服务云提供对象解析的功能。 将两级地址的解析分开，增加了灵活性和安全性。

33 （3）服务层 SOI架构的基础是位于IP层之上的一个服务层，包含两个网络单元：
服务网关：可看成是下层网络域的扩展，通常部署在网络域边缘，负责穿过网络域的路由和服务交付。 服务存在点：服务云与网络域接口的地方，逻辑上是服务云的一部分，负责在服务云内部交付对象。 进出服务云的数据都要经过服务网关，服务网关提供服务区分、识别和跟踪服务云流量的功能。

34 服务层在协议栈中的位置

35 服务层协议数据单元（服务对象） 服务对象头部分为sid部分和oid部分 服务修正符由服务云定义，对服务对象的转发有影响。

36 服务网关（Service Gateway）
数据面功能： 根据目的sid（或目的sid + 源sid）及相关的服务修正符，将服务对象转发到去往目的服务云的下一跳（相邻的S-POP或另一个SG）。 控制面功能： 运行服务网关路由协议，建立服务路由表。 服务路由表包含目的sid（及相关的服务修正符）到下一跳SG/S-POP（用IP地址表示）的映射。

37 服务存在点（S-POP） 服务存在点有两个主要功能： 为实现第一个功能：
与服务网关合作，为它所代理的服务云路由和转发服务对象（发往服务云外部）。 和服务云中的其它S-POP合作，在服务云内部路由和转发服务对象。（服务云内部机制） 为实现第一个功能： 控制面：参与服务网关路由协议，建立（部分的）服务路由表，表中包含从sid空间到相邻SG的映射。 数据面：利用服务路由表，将服务对象转发到服务云外。

38 服务网关路由协议 服务网关路由协议主要负责建立服务路由表，包括两个部分：
S-POP注册和公告： S-POP向本地服务网关注册，通告其存在、所代表的服务云sid、能够处理的流量类型（一组服务修正符）。 传播服务可达性：从邻居服务网关学习路径和向它们发布路径（类似BGP）。

39 参考文献 Resilient Overlay Networks. SOSP 2001.
Service Overlay Networks: SLAs, QoS and Bandwidth Provisioning. ICNP’02. Service Oriented Internet.

40 2 应用层组播 IP组播体系结构： IP组播协议：MOSPF、DVMRP等。 IP多播骨干网：MBone
路由器采用分布式算法构造一棵数据转发树；组播分组沿转发树转发时，在树的分支节点处由路由器进行复制。 IP组播协议：MOSPF、DVMRP等。 IP多播骨干网：MBone IP组播是实现组播转发的最有效方法，可使全网范围的分组复制数量最少。

41 IP组播的缺点 路由器必须为每个组播组单独保存状态，路由表和转发表也需要为每个组播组维护一个地址项（组播地址不能聚合），扩展性很差。
试图用一种统一的组播模型来适应所有的应用，给组播算法的设计造成很大困难。 组播组的管理开销大。 在IP组播中实现可靠性和拥塞控制非常困难。 在经济方面，尚没有针对组播的流量计费机制。

42 应用层组播 在应用层上，依靠端系统之间的单播实现组播。 应用层组播研究如何构造并维护高效率的覆盖网络。 优点： 缺点：
不需要改变现有路由器，能够很快进入应用。 单播技术较成熟，基于单播实现的应用层组播易于实现差错控制、流量控制、拥塞控制等。 缺点： 延迟较大：应用层组播不考虑网络本身的拓扑结构。 效率不如IP组播：应用层组播会产生较多数据冗余。 应用层组播研究如何构造并维护高效率的覆盖网络。

43 应用层组播的例子：Overcast Overcast网络用于单源组播，由以下几个部分组成： 一个源服务器
任意数目分布在因特网上的中间节点（有永久存储的PC机） 分布在因特网上的标准HTTP客户（Web浏览器） 分发树建立协议：将中间节点组织成一棵以源为根的分发树。

44 多播组的命名 Overcast借用HTTP URL表示多播组： 使用URL作为多播组的名字空间有以下好处：
hostname指出一个Overcast网络的根，源相同的所有组共享一棵分发树。 Path指示该网络中的一个多播组。 标准的HTTP客户都可以加入这些多播组。 使用URL作为多播组的名字空间有以下好处： 分层的名字空间解决了多播组地址空间缺乏的问题。 基于HTTP的应用不加修改就能使用到多播。 URL结构丰富，表达能力强。

45 Overcast的应用：视频分发系统 系统由一个studio和在一些合适位置放置的appliance组成，appliance和studio协作组织成一棵分发树。 studio存储内容，并根据需要调度内容到appliance上。 内容发布者生成一个web页，发布内容的链接。 用户点击内容的URL后， 浏览器根据hostname将请求发送到studio。 Studio根据path将请求发送到客户附近的appliance。

46 节点初始化 节点初始化（节点配置和注册）： 确定节点进行一般IP连接所需要的IP地址和网关地址（DHCP服务或手工配置）。
向一个全局的、熟知的注册机构发送自己的序列号。 注册机构提供给节点一个应当加入的Overcast网络列表、一个可选的永久IP配置、应当服务的网络区域、应当执行的访问控制。

47 建立分发树 Overcast建立转发树的原则是，最大化从根（源服务器）到所有中间结点的带宽：
将节点放置在尽可能远离根的地方，同时不牺牲到根的带宽。 得到一棵较深的分发树，节点在分发树上得到的带宽不低于其直接从根获取内容得到的带宽。

48 分发树的建立过程 当有一个新节点向根注册时，启动分发树建立过程： 设根为“当前节点”；
新节点检测直接到“当前节点”的带宽，以及经过“当前节点”的各个孩子节点到达“当前节点”的带宽； 如果经由某个孩子节点到“当前节点”的带宽和从它直接到达“当前节点”的带宽一样高，该孩子节点成为“当前节点”，继续探测。 如果有多个孩子节点满足条件，距离新节点最近（跳数最少）的孩子节点成为“当前节点” 。 如果没有一个孩子节点满足条件，“当前节点”成为父节点，搜索过程结束。

49 分发树的自适应调整 节点周期性地重新评估它在树中的位置： Overcast网络容忍非根节点的失效：
如果到某个兄弟节点的带宽不低于到父节点的带宽，将自己置于该兄弟节点之下。 如果直接到祖父节点的带宽大于到父节点的带宽，将自己置为当前父节点的兄弟节点。 Overcast网络容忍非根节点的失效： 当节点发现父节点不可达时，将自己连接到祖父节点下。 如果祖父节点不可达，节点继续沿系谱往上移，直到找到一个当前活跃的节点。

50 网络维护 每个节点维护一张表，记录在树中低于自己的节点的信息，根节点的信息表包含树中所有节点的最新信息 。
每个节点周期性地向父节点报告自己的存在： 如果一个孩子节点在预定的时间间隔内没有报告，父节点在表中记录该孩子及其子孙节点“死了”。 节点还会报告其观察到或被告知的信息，如错过报告时间的孩子和新增的孩子等。

51 加入多播组 web客户发送一个包含该多播组URL的HTTP GET请求，URL的hostname指出分发树的根，path指出多播组。

52 用Overcast实现多播 数据在父节点和子节点之间通过TCP传输： 如果出现路径失效： 内容可能会流水地通过树上的几代节点。
重建分发树； 节点检查日志，重新启动未完成的传输。

53 参考文献 Overcast: Reliable Multicasting with an Overlay Network. OSDI 2000.

54 3 内容分发网络 Content Delivery Networks（CDN）
提高Web服务性能主要围绕网络传输和服务器两个方面： 提高单台web服务器的性能： 增加更多的内存和磁盘空间，使用更高速的处理器（或多处理器），使用缓存来减少读盘次数等。 性能提高有限，响应延迟受网络拥塞影响大。 建立服务器集群（server farm）： 多个web服务器分担对同一个web站点的访问请求。 响应延迟受网络拥塞影响大。

55 提高Web服务性能的方法（续） 建立分级的web缓存机制： 将用户最近访问过的网页保留在高速缓存中，使用一个代理（proxy）来管理缓存。
浏览器配置为向代理请求网页，若本地缓存没有，向上一级代理或源服务器请求。

56 提高Web服务性能的方法（续） 建立内容分发网络： 在因特网的不同地方设置镜像服务器，将用户请求重定向到最近的服务器。
有助于减小网络传输和服务器负载对请求响应时间的影响。

57 CDN涉及的主体 内容提供商（customer）： CDN提供商： 端用户（client）：
提供内容服务的机构或公司，其内容保存在源服务器（origin server）。 CDN提供商： 拥有CDN架构，为内容提供商提供快速可靠的内容递送服务。 端用户（client）： 从内容提供商的网站上访问内容的实体。

58 内容分发环境

59 CDN的内容 CDN一般保存静态内容： 在CDN的上下文中，内容泛指任何数字形式的数据资源，主要包括两大部分：
如图像、视频、媒体剪辑、广告、动态网页中的嵌入式对象等。 在CDN的上下文中，内容泛指任何数字形式的数据资源，主要包括两大部分： 经过编码的媒体。 元数据：用来标识、发现和管理媒体数据的内容描述。

60 CDN的客户 CDN的客户一般是媒体和因特网广告公司、数据中心、ISP、在线音乐零售商、移动运营商、消费电子生产商等。

61 CDN的体系结构 基础结构：提供基础设施资源，由通过高速网络连接的分布式计算资源和网络基础设施组成。
通信和连接：提供核心的互连网协议、CDN特定的协议、认证协议、安全通信协议SSL。 CDN：CDN核心功能。 端用户：web用户，在web浏览器上给出内容提供商网站的URL连接到CDN。

62

63 CDN提供的服务和功能 内容存储和管理 在代理服务器间分发内容 缓存管理 静态、动态和流内容投送 备份和灾难恢复解决方案
监视、测量和报告性能

64 内容简介 从以下三个方面介绍CDN： 参考文献：
内容简介 从以下三个方面介绍CDN： CDN组成 内容分发和管理 请求路求 参考文献： A Taxonomy and Survey of Content Delivery Networks.

65 3.1 CDN的组成 CDN的任务是结合网络条件和缓存服务器负载等动态信息，在多个反向代理（surrogate）之间重定向请求和平衡负载。

66 Surrogate 和 Proxy Proxy用于代理内部网络对因特网的连接请求。客户机将本来要直接发送到外部服务器上的服务请求发送到代理服务器，由代理服务器中继服务请求。 Surrogate用于代理外部网络上的主机访问内部网络，此时Surrogate对外表现为一个web服务器。 反向代理可以增强web服务器的安全性，和作为后端服务器集群的负载均衡器。 反向代理方式和普通代理方式没有冲突，可以在防火墙设备中同时使用。

67 CDN的结构特性

68 3.1.1 CDN的组织方式 网络方法： 在路由器和交换机等网络组件上安装相关软件，将内容请求重定向到本地缓存或特定的内容服务器。 覆盖方法： 使用放置于网络中多个地方的应用特定服务器（反向代理，高速缓存服务器）处理特殊内容（web内容、流媒体等）的分发。 除了提供基本的网络连接和QoS保证外，核心网络组件在内容分发过程中不发挥积极作用。

69 3.1.2 CDN服务器 源服务器（origin server）： 复制服务器（replica server）：
存放资源的权威版本，由内容提供商更新。 复制服务器（replica server）： 存放资源的拷贝，并被授权响应用户的请求 。 通过源服务器进行内容更新。

70 CDN的复制服务器 CDN的复制服务器可以作为媒体服务器、web服务器或高速缓存服务器：
媒体服务器（media server）：提供数字编码的内容，安装有媒体服务器软件，用音频或视频素材响应用户的请求。 Web服务器：包含到流媒体的链接，以及CDN希望提供的其它基于web的内容。 高速缓存服务器（cache server）：在网络边缘复制内容，以减少对源服务器的访问。

71 流媒体应用的实现 音/视频文件存储在媒体服务器上，元文件存储在Web服务器上。
媒体播放器和媒体服务器之间通过RTP/UDP传输音/视频流，使用RTSP进行交互性操作。

72 3.1.3 CDN组件之间的关系 CDN的各个组件通过相互协作来实现CDN内部的内容复制和高速缓存：
复制：在不同的计算机系统上创建和维护内容拷贝，典型地是将内容从源服务器“推送”到复制服务器。（Push） 缓存（caching）：将可缓存的响应保存在本地，以便将来响应相同的请求。 （Pull）

73 用户-反向代理-源服务器 内容投递的基本关系是在用户、反向代理服务器和源服务器之间： 用户一般同反向代理服务器通信。
反向代理服务器用本地缓存的内容响应用户请求，或作为源服务器的网关。

74 用户-网元-高速缓存代理（caching proxy）
在网络方法中，网元（路由器、交换机）上的控制逻辑将用户请求转发到相应的高速缓存代理（代理阵列）。

75 高速缓存代理-高速缓存代理 根据高速缓存代理之间的通信方式，高速缓存代理可以组织成代理阵列或代理网：
Proxy array：紧耦合结构，有一个权威代理作为主代理，与其它代理通信。 Proxy mesh：松耦合结构，每个代理都和其它代理有联系，构成代理网。Proxy mesh需要一个高速缓存服务器作为网关，转发来自用户本地缓存代理的请求。

76 代理阵列 和 代理网

77 3.1.4 协议 CDN中的通信协议分为两类： 网元交互协议：用于将用户请求重定向到一个合适的服务器，涉及路由器、内容交换机/负载均衡器、服务器等实体。 高速缓存交互协议：用于在分布式高速缓存中确定所请求的内容在哪个高速缓存中。

78 网元-服务器（NECP） 运行在服务器（源服务器、拦截代理）与其前端设备（内容交换机、负责均衡路由器）之间的控制协议：
服务器启动时，与网元的熟知端口建立TCP连接，在TCP连接上进行双向消息交换。 网元通过消息交换了解服务器的能力、可用性、可以获得哪些内容等，作为重定向用户请求的依据。

79 重定向路由器-拦截代理（WCCP） 运行在重定向路由器和拦截代理之间，建立和维护用户请求的透明重定向：
若干拦截代理和若干重定向路由器组成一个服务组，指定一个代理（IP地址最小）作为首领，负责在代理群之间分配负载，并将负载分配方法在组内传播。 通过该协议，路由器知道如何重定向用户请求；拦截代理知道如何管理高速缓存中的内容。

80 防火墙安全会话转换协议SOCKS SOCKS是为客户-服务器应用安全通过防火墙而提供的一个通用框架。

81 Internet Cache Protocol（ICP）
用户请求发送到本地缓存。 若本地缓存没有，本地缓存向同伴缓存广播请求。 若同伴均回复没有或超时，本地缓存向父缓存请求。 若父缓存没有，父缓存或本地缓存向源服务器请求。 ICP基于查询/应答实现，通信开销大，延迟大。

82 Cache Digest 每个节点保存其它节点中所缓存的内容的摘要： 优点：不需要发送查询消息到其它缓存节点。
本地缓存收到用户请求后，检查本地缓存的内容和其它节点的缓存内容摘要； 若本地缓存有内容，直接响应用户的请求； 若有缓存内容摘要，向相应的缓存节点请求； 若没有缓存内容摘要，向源服务器请求内容。 优点：不需要发送查询消息到其它缓存节点。 缺点：存储摘要的代价很高，节点之间需要更新摘要。

83 Cache array routing protocol（CARP）
浏览器利用cache阵列成员表、一个查找函数和用户请求的URL，就能确定最合适的cache服务器。 Cache阵列成员表定义在一个可公开获取的文本文件中，文件中列出了每台代理服务器的名字、IP地址和负载因子（管理员指定）。 浏览器需要下载Cache阵列成员表和一个查找函数（JavaScript函数）。

84 CARP（续） 查找函数实现CARP算法： 优点：
使用指定的哈希函数计算URL的散列值及每个成员名字的散列值，两个值结合得到每个成员对该URL的一个分值。 将该分值与成员的负载因子结合，得到每个成员对该URL的总分。 总分最高的cache服务器选中。 优点： 没有缓存冗余，缓存命中率高。 缓存节点间不需要通信，没有查询和更新开销。

85 3.1.5 内容/服务类型 CDN提供的内容/服务有三类：静态内容，流媒体，各种内容服务。 静态内容：
HTML页、图片、文档、软件补丁、音/视频文件等。 更新频率很低，易于缓存。 所有CDN提供商都支持静态内容的投递。

86 流媒体 流媒体包括： 流媒体服务需要专门的流式服务器，使用特定软件实现流媒体在IP网络中的传输。 投送流媒体内容对于CDN是一个挑战。
现场音/视频：内容从编码器立即送到媒体服务器，然后送给媒体用户。 点播音/视频：内容预先被编码，作为流媒体文件保存在媒体服务器中，用户请求时投送。 流媒体服务需要专门的流式服务器，使用特定软件实现流媒体在IP网络中的传输。 投送流媒体内容对于CDN是一个挑战。

87 内容服务 将CDN作为服务分发渠道，允许增值服务提供商在上面提供增值服务（内容服务），如：
网页压缩服务：提供对网页的实时压缩，并对源服务器和用户透明。 电子商务服务：比如在CDN的边缘服务器上保存和维护购物车、进行在线交易等，减轻源站的压力。

88 3.2 内容分发和管理 内容分发： 内容管理： 反向代理放置：确定反向代理服务器的放置位置及数量，最小化用户访问延迟和网络带宽消耗。
内容选择和投送：正确选择要复制到CDN的内容，减少用户下载时间和服务器负载。 内容外包：如何将选择的内容复制到放置好的反向代理服务器？复制到哪一个反向代理服务器？ 内容管理： 高速缓存组织：缓存技术、缓存更新、缓存策略。

89 3.2.1 反向代理服务器的放置 目标：确定反向代理服务器的个数和放置位置。 问题模型： 理论算法： 启发式算法：
给定一个图G（V, E）和要放置的中心数量k，确定中心的位置，使得所有节点到最近中心的最大距离最小化。 理论算法： 计算复杂度大。 启发式算法： 利用来自CDN的一些信息，如负载模式、网络拓扑等，以较低的计算代价获得次优解。

90 启发式算法（1） Greedy replica placement： 前提：知道网络中所有用户的位置，以及每一对节点间的距离。
算法思想：从N个可能的站点中选择访问代价最小的M个站点放置反向代理。 过程： 第一轮计算每个站点的代价，计算时假定所有用户的访问都汇聚到该站点，代价最小的站点被选中。 结合已选中的站点，第二轮搜索代价第二小的站点。 依次类推，直至M个站点选出来。

91 启发式算法（2） Topology-informed placement strategy： 假设： 算法基本思想： 改进的算法：
有较大出度的节点可用较小的延迟到达更多的节点。 算法基本思想： 使用自治域一级的拓扑，每个节点代表一个AS，每一条链路对应一对BGP对等体。按节点出度的降序选择M个节点放置反向代理。 改进的算法： 用路由器一级的拓扑代替AS一级的拓扑，与路由器相连的每个局域网都可以放置一个反向代理。

92 启发式算法（3） Hotspot算法： 按照产生流量的大小对站点进行排序； 将M个反向代理放置在生成流量最大的M个站点上。

93 确定反向代理服务器的数量 单ISP方法： 多ISP方法： 仅在CDN提供商的网络边缘放置反向代理服务器。
缺点：反向代理服务器可能离用户很远。 多ISP方法： 在尽可能多的互联网入网点（ISP Points of Presence）上放置反向代理服务器。 优点：反向代理服务器位于请求用户的ISP上。 缺点：建设成本及复杂性高，服务器使用率低。

94 3.2.2 内容选择和投送 正确选择要复制到CDN的内容，以减少用户下载时间和服务器负载。 两类方法：
全站点内容选择和投送：将源服务器上的全部对象外包给反向代理服务器。 部分站点内容选择和投送：只将源服务器上的部分内容复制到反向代理服务器。

95 全站点内容选择和投送 内容提供商配置其DNS，令所有对其web站点的请求都由一个CDN服务器解析，这样全部内容都由CDN投送。 优点：简单。
缺点：不具有可行性（边缘服务器不可能拥有足够的存储空间，更新也很难做到）。

96 部分站点内容选择和投送 反向代理服务器只投送内置于网页的对象（如图片）。
内容提供商修改其内容，将特定对象URL中的host name改为CDN提供商权威域中的域名。 HTML基础网页从源服务器获取，内嵌的对象从CDN反向代理服务器获取。 优点： 降低了对反向代理服务器的存储容量需求； 只投送静态的或更新较慢的内容，减轻更新压力。

97 部分站点方法（1） 基于实证的（empirical-based）方法： 基于流行的（popularity-based）方法：
管理员依据经验选择复制到反向代理服务器的内容。 缺点：选择正确经验的不确定性。 基于流行的（popularity-based）方法： 最流行的对象被复制到反向代理服务器。 缺点： 耗时（要对对象的流行程度进行评估和排序） 难以得到可靠的对象请求统计信息（流行性变化大） 新内容的统计信息得不到

98 部分站点方法（2） 基于对象的（object-based）方法： 内容以对象为单位复制到反向代理服务器。
在满足存储容量的前提下，每复制一个对象到反向代理服务器都试图最大化性能增益（贪婪算法）。 优点：可获得最佳性能 缺点：实现复杂度高

99 部分站点方法（3） 基于聚类的（cluster-based）方法： web内容依据相关性或访问频度分组，并以内容聚类为单位进行复制。
基于URL的内容聚类：依据web站点的拓扑来汇聚web内容，从一个web站点中识别出最流行的对象，然后按URL之间的相关距离进行聚类。 这类方法可以减少用户下载时间和服务器负载，但实施的复杂度高。

100 3.2.3 内容外包（content outsourcing）
如何将选择的内容复制到一组放置好的反向代理服务器上？ cooperative push-based（内容预取）： 内容从源服务器推送到反向代理服务器，反向代理服务器通过相互协作来降低复制和更新代价。 CDN维护内容和反向代理之间的映射，用户请求被定向到最近的反向代理服务器或源服务器。 适合采用全局贪婪启发式算法在合作的反向代理服务器之间进行复制决策。 该方法还处于实验阶段，未被任何CDN提供商使用。

101 基于“拉”的内容外包方法 Non-cooperative pull-based： Cooperative pull-based：
用户请求被定向到最近的反向代理服务器； 如果缓存不命中，反向代理从源服务器取内容。 大多数流行的CDN提供商使用该方法。 Cooperative pull-based： 如果缓存不命中，反向代理使用一个分布式索引在附近找到所请求内容的拷贝。

102 外包内容的最佳放置 问题： 外包内容复制到哪一个反向代理服务器最好？ 各种启发式算法（略）： 考虑负载均衡和/或下载延迟

103 3.2.4 缓存组织（cache organization）
内容管理主要由CDN的缓存组织方式决定： 缓存技术：如何从分布式缓存中找到要请求的内容？ 缓存更新：如何保证缓存内容的一致性和新鲜性？

104 （1）缓存技术（caching techniques）
CDN中的内容缓存分为簇内缓存和簇间缓存

105 簇内缓存 基于查询的缓存方案： 当一个反向代理服务器发现cache miss后，向簇内的其它反向代理服务器广播一个查询。
若所有的反向代理服务器都没有该内容，该反向代理向源服务器请求。 缺点：查询流量大（查询洪泛），延迟长（需要等待所有的反向代理服务器返回响应）。

106 簇内缓存（续） 基于摘要的缓存方案： 每个反向代理服务器维护其它服务器中内容的摘要，内容更新的通知发送给所有的反向代理。
反向代理服务器检查保存于本地的内容摘要后，决定将内容请求路由到哪个反向代理。 优点：解决了查询洪泛的问题。 缺点：存储量大，更新流量大（频繁发送更新通知）。

107 簇内缓存（续） 基于目录的缓存方案： 摘要方法的集中式版本，一个集中的目录服务器保存簇内所有反向代理服务器上内容的信息。
每个反向代理只将内容改变通知目录服务器，并在本地cache miss后查询目录服务器。 缺点：目录服务器接收来自所有反向代理的更新和查询流量，是性能瓶颈和单故障点。

108 簇内缓存（续） 基于哈希的缓存方案： 所有反向代理服务器使用相同的哈希函数和一组反向代理IP地址，根据内容的URL确定内容存在哪个服务器（称为内容的指定服务器）上。 对内容的请求全都定向到其指定服务器。 优点：实现代价最小（没有查询流量，也不需要维护摘要或目录），内容共享效率最高（没有缓存冗余）。 缺点：对本地请求的扩放性不好（本地用户的请求会被引导到其它的反向代理服务器）。

109 簇内缓存（续） 基于半哈希的缓存方案： 本地反向代理服务器划出一部分磁盘空间，用于缓存本地用户经常请求的内容，其余空间采用基于哈希的方法与其它服务器协作。 优点：实现开销小，内容共享效率高，本地内容命中率高。

110 簇间缓存 基于摘要或目录的方法： （不可行） 基于哈希（半哈希）的方法：（不可行） 基于查询的方法：
扩放性差（每个簇的代表服务器必须维护其它簇的服务器中所存内容的信息）。 基于哈希（半哈希）的方法：（不可行） 局部性不好。 基于查询的方法： 唯一可以应用到簇间缓存的方法。

111 簇内、簇间使用不同的缓存技术 簇间使用基于查询的缓存技术，簇内使用基于哈希的缓存技术：
当一个簇不能服务某个内容请求时，其代表服务器向邻近的簇（代表服务器）发出询问。 在每个簇内，代表服务器只向内容的指定服务器询问。

112 （2）缓存更新 缓存更新技术用于保证缓存服务器上的内容是最新的。 周期性更新：
内容提供商配置源web服务器，向缓存服务器提供缓存指示，如内容的可缓存性、过期时间、向源服务器的核对时间等。 缺点：每个更新间隔会产生大量不必要的更新流量。

113 缓存更新（续） 更新传播： 按需更新： 每当源服务器上的一个内容发生了改变，更新的内容就被主动推送到所有的缓存服务器。
缺点：内容频繁更新时产生过多的更新流量。 按需更新： 仅当内容被请求时，最新的内容拷贝才被投送到发出请求的缓存服务器。 缺点：源服务器和缓存服务器之间来回传递消息（如询问最新的版本），延迟大。

114 缓存更新（续） 无效（invalidation）： 当源服务器中的某个文档发生改变时，源服务器向所有的代理服务器发送一个无效消息。
需要时，每个代理服务器单独向源服务器获取文档的最新拷贝。 优点：消除了不必要的内容推送和更新查询。 缺点：没有充分利用CDN的资源，每个代理服务器需单独向源服务器获取文档的最新拷贝。

115 （3）内部缓存策略 使用规则集定义缓存策略： 使用启发式算法： 内容提供商用一个规则集向CDN提供商描述缓存策略；
令缓存服务器使用某种启发式算法，自动学习源服务器上的内容更新频率，相应调整它们的行为。

116 3.3 请求路由（request-routing）
请求路由负责将用户请求发送到包含该内容的一个最合适的反向代理服务器上。 请求路由系统使用一组度量参数（如网络邻近性、延迟、距离、服务器负载）确定最合适的服务器。 内容选择和投送技术对请求路由系统的设计有直接影响： 若使用全站点方法：用户请求被发送到代理服务器。 若使用部分站点方法：源服务器投送基本内容，代理服务器投送内置的对象。

117 请求路由的示意图

118 请求路由系统的关键技术 CDN的请求路由系统包括两个关键的部分： 请求路由算法：针对某个内容请求选择一个反向代理服务器的方法。
请求路由机制：将选择结果通知用户的方法。

119 3.3.1 请求路由算法 非自适应算法： 自适应算法： 使用某种启发式来选择缓存服务器，不考虑当前网络状态，实现简单。
当启发式的假设满足时，算法很有效。 自适应算法： 在选择缓存服务器时考虑当前的网络状态（通过估计某些度量参数获得），实现复杂。 面对瞬间突发事件时，算法有很好的鲁棒性。

120 （1）非自适应算法 轮转： 假设所有服务器具有相同的处理能力，且任何服务器可以服务任何请求. 内容请求按轮转顺序发送给各个服务器处理。
优点：对于放置在一起的服务器机群较有效。 缺点： 对于广域分布式系统不适合（没有考虑距离） 未充分实现负载均衡（没有考虑不同请求的计算开销有差异）

121 非自适应算法（续） 基于负载分级： 假设服务器负载和用户-服务器间距离是影响请求处理效率的最重要因素。
所有服务器按照预估的负载（到目前为止已服务的请求数）划分等级。 算法首先根据负载等级选择侯选服务器，然后在侯选服务器中根据用户-服务器距离再选择服务器。 优点：既考虑了负载均衡，又考虑了网络距离。 缺点：需要整个网络的同步，要求较高。

122 非自适应算法（续） 基于服务器的能力： 基于对服务器的偏好： 假设：服务器接收用户请求的比例越高，说明服务器能力越强。
用户请求被路由到能力强的服务器，以充分利用资源。 基于对服务器的偏好： 定义对不同服务器的偏好，用户请求被路由到最偏好的服务器。

123 （2）自适应算法 基于网络邻近性： 基于用户-服务器延迟： 利用一个周期性更新的路径长度来估计网络邻近性，将用户请求发送给最近的服务器。
缺点：距离度量的估计过程不太精确。 基于用户-服务器延迟： 利用用户访问日志或服务器侧的延迟测量值，将用户请求发送到最近报告了最小延迟的服务器。 优点：考虑了延迟 缺点：需要维护集中的测量数据库，扩放性差。

124 自适应算法（续） 基于多种度量值的加权值： 比如，Cisco的DD算法使用AS间距离、AS内距离和端到端延迟三种度量值的加权和。
优点：灵活性更高。 缺点：在每个服务器上需要配置一个测量代理，增加复杂度和处理开销。

125 3.3.2 请求路由机制 请求路由机制通知用户所选择的代理服务器。

126 （1）全局服务器负载均衡 （Global Server Load Balancing，GSLB）
服务节点：由一个支持GSLB的web交换机和许多实际的web服务器组成。 GSLB交换机具有全局感知能力： 每个GSLB交换机知道本地web服务器的健康和性能信息，并与其它GSLB交换机交换信息。 GSLB交换机充当某些域的权威DNS服务器： GSLB交换机接收特定域的DNS请求，选择最好的代理服务器，返回服务器IP地址。

127 GSLB的请求-路由机制 用户键入http://www.alteon.com 域名解析器向本地DNS服务器请求解析该域名。
DNS请求最终到达某个GSLB交换机。 GSLB交换机选择一个最合适的Web服务器，返回其IP地址。 浏览器使用该IP地址向指定的web服务器发送内容请求。

128 （2）基于DNS的请求路由机制 传统网络中的内容请求过程： 用户向浏览器提供要访问的域名。
浏览器调用域名解析器（本地的一个库函数），域名解析器将DNS请求发送给本地DNS服务器，得到此域名对应的目的主机IP地址。 浏览器使用得到的IP地址，与目的主机建立连接，发送内容请求。 浏览器显示目的主机返回的内容。

129 接管DNS解析 为了让CDN提供商接管域名解析过程，内容提供商需修改其DNS记录。
如内容提供商（域名 内容提供商将其DNS数据库中 www IN A 改为 www IN CNAME cache.cdn.com.

130 CDN中的内容请求过程 用户向浏览器提供要访问的域名。 浏览器调用域名解析器，域名解析器向本地DNS服务器查询。
本地DNS服务器得到该域名对应的CNAME记录，向CDN的权威DNS服务器查询CNAME域名。 在CDN的DNS数据库中，一个域名有多个A记录（每个缓存服务器对应一个A记录），比如： cache IN A cache IN A cache IN A

131 CDN中的内容请求过程（续） CDN的DNS服务器按照某种策略返回一个（或一组）反向代理服务器的IP地址。
反向代理服务器查找本地缓存，返回；若没有， 根据要访问的域名，通过内部专用DNS解析得到域名对应的实际IP地址，向此IP地址提交访问请求。 反向代理获得内容后，缓存在本地，并把内容返回给浏览器。

132 （3）HTTP重定向 利用HTTP重定向消息（状态码为300或302），将反向代理服务器的信息在location域中返回给web客户。
利用该机制可以建立一个特殊的web服务器：接收用户的HTTP请求，选择一个（或一组）反向代理服务器，用重定向消息发送给客户。 主要缺点：源服务器成为瓶颈，缺乏透明性，响应延迟大（在TCP连接上进行消息交互），需要修改web服务器和客户程序。 主要优点：控制粒度细（以页为单位）。

133 （4）URL改写 源服务器通过改写动态网页的URL将客户引导到不同的反向代理服务器。
为使这个过程自动进行，CDN提供能够解析web网页内容并替换内嵌URL的特殊脚本。 URL改写可以是主动的或被动的: 主动改写：HTML页中内嵌对象的URL在内容下载到源服务器之前就完成了。 被动改写：当客户请求到达源服务器时才改写内嵌对象的URL。

134 （5）任播（anycast） 请求路由与任播： 请求路由：将内容请求发送到一组服务器中的一个 任播：将消息发送到一组节点中的任意一个
IP任播： 用一个IP任播地址定义一组提供相同服务的服务器； 每个IP路由器记录去往该组中最近服务器的路由； 对一个域名的解析返回该域名对应的IP任播地址，到该任播地址的内容请求路由到最近的反向代理服务器。 只能基于最短路径度量选择反向代理服务器。

135 应用层任播 使用一个域名（如内容的URL）来定义提供相同服务的一组服务器。 一组任播解析器执行从任播域名到IP地址的映射。
浏览器发送一个任播查询，任播解析器查询一个度量数据库（反向代理服务器的性能数据），根据用户规定的性能标准选择一个合适的反向代理服务器。 可以基于其它度量标准选择反向代理；需要修改服务器和客户端。

136 （6）CDN peering 所有服务节点使用对称链路连接，形成一个对等的（P2P）信息获取网络，而不依靠专门的CDN。
集中目录查询：每个对等节点在一个集中目录中发布愿与其它对等节点共享的内容。 洪泛请求：内容请求被广播到与其直连的对等节点，直至请求被响应或停止洪泛的条件被满足。 各种复杂的节点查找算法（略）