应用层网络.ppt

《应用层网络.ppt》由会员分享，可在线阅读，更多相关《应用层网络.ppt（136页珍藏版）》请在三一文库上搜索。

1、应用层网络,Application-layer Overlay Networks,覆盖网络（Overlay Network）,网络： 一群互连的、可以相互通信的计算机，定义了主机间通信所使用的编址、路由及服务模型。 覆盖网络： 建立在一个或多个已有网络之上的逻辑网络； 改变底层网络的一个或几个特性，以实现底层网络所不能提供的某种网络服务。 替代覆盖网络的方案： 修改已有网络,因特网是一个覆盖网络,因特网是建立在众多物理网络及电信线路上的逻辑网络 增加了一个在网间寻址及路由的IP层 实现数据包跨物理网络的传输,覆盖网络的应用,路由（如路由覆盖网络） 寻址（如对等网络） 安全（如VPN） 多播（如

2、MBone） 移动（如移动IP） ,覆盖网络的优点和缺点,优点： 一般不需要部署新的设备，不修改或很少修改已有的软件/协议（但需要在已有软件上部署新的软件）。 不需要在每一个节点上都部署新软件。 缺点： 协议栈中增加了一个层次，增加了包头及包处理开销 节点的负担加重了 扩放性问题,应用层网络,应用层网络是在因特网上构建的一个完全位于应用层的网络系统。 应用层网络由分布在因特网上的一组主机组成： 为一个或多个应用程序提供下层基础设施（网络服务） 采用与目前因特网不同的方法转发和处理应用程序的数据 由第三方运营和管理，不是当前因特网体系结构的一部分。 应用层网络实际上是基于因特网的大规模分布式应用

3、，因借助网络层的一些技术来进行成员之间的寻址和路由而具有了网络层的某些特征。,典型的应用层网络系统,路由覆盖网络 应用层组播 内容分发网络 P2P系统,1 路由覆盖网络,因特网路由策略仅反映ISP对开销和运行效率的考虑，端用户和应用程序无法参与。 对于有些应用来说，因特网路由协议（OSPF/RIP、BGP）所选的路由不能满足其要求。 路由覆盖网络的目的是为上层应用提供更好的路由服务，满足其特殊的应用需求。,1.1 弹性覆盖网络 Resilient Overlay Networks（RON）,RON是为解决BGP路由失效恢复慢的问题而提出的，其设计目标为： 快速检测和恢复路由失效 20秒内检测到

4、路由失效（停运或性能下降）并恢复 紧密集成路由选择与应用 允许应用定义路由失效和对失效的响应 允许应用选择适合自己的路径度量来选择路径 灵活的策略路由 允许针对单个用户或主机定义路由策略,RON概述,RON是建立在已有因特网路由结构上的一个应用层覆盖网络。 RON节点监视在它们之间的因特网路径的质量，使用这些信息决定直接使用因特网的路由结构，还是将数据包路由到其它RON节点，以优化应用特定的路由度量。,RON体系结构模型,RON客户通过管道（conduit）与RON节点交互 Probes负责探测虚链接状态 Router实现路由协议 Forwarder提供分组转发功能 性能数据库保存虚链接状态信

5、息（延迟、分组丢失率、链路吞吐量 ）,RON节点,RON节点是运行了RON软件的主机，实现和路由器类似的功能。 任意两个RON节点之间维护一条由下层因特网链路构成的路径（虚链接）。 每个节点及时探测到其余节点的虚链接状态，保存在本地的性能数据库中。 RON的设计目标是为一组RON客户（使用RON转发数据的应用程序 ）提供更可靠的IP路由机制。,RON工作过程,第一个RON节点（入节点）对分组进行分类，决定分组要使用的路径类型（低延迟或高吞吐率等），为其选择一条路由。 若下一跳为一个RON节点，入节点为分组封装一个RON报头（包含一个流标签），发送到下一个RON节点。 入节点对后续到达的属于同一

6、个客户的分组标上相同的流标签，直接查找流缓存表转发。 后续RON节点根据目的地址和流标签决定下一跳（不再进行分类）。 最后一个RON节点（出节点）将分组交给RON客户。,RON路由的特点,支持不同的路由策略： 使用不同的链路度量参数维护多条路径 根据RON客户程序的需要选择最合适的路径,RON路由的工作要点,路径评估： 节点使用停运检测（outage detection）算法，主动探测到其它RON节点之间的虚链路是否工作。 针对每一种路径度量（延迟、丢包率、吞吐率），给出表明路径有多“好”的数值。 链路状态传播： 节点周期性地从本地性能数据库中取出到其它节点的各种路径度量的汇总信息，通过RON

7、本身的网络发送。,路由表构成,针对每一种路由策略计算一组路由表，每一个路由表针对一种路径度量计算得到。 路由表的层次结构： 每个策略标签指向一个路由偏好表。 每个路由偏好对应一种路径度量的路由表。,RON转发,转发器检查每个到来分组的RON报头，确定要发给本地客户还是一个远程节点： 如果去往本地客户，利用RON报头中的packet type将数据包交给对应的RON客户。 如果flow ID匹配流缓存表中的一个表项，使用表项中的路由信息。 如果flow ID不匹配流缓存表中的任何表项，利用RON报头查找路由表。,RON报头结构,路由表查找过程,路由表查找分三步完成： 基于策略类型查找 基于路由偏

8、好查找 基于目的地址查找,1.2 服务覆盖网络 Service Overlay Networks（SON）,每个ISP只关心自己网络的性能，并只对自己的用户提供服务保证。 BGP只能找到一条可达的路由，无法保证端-端应用性能。 SON是为了在因特网上提供端-端服务质量（Quality of Service，QoS）而提出的，以方便创建和部署QoS敏感的增值业务。,SON的实现基础,SON服务商通过双边服务协议（Service Level Agreement，SLA）从各个ISP购买具有一定QoS保证的带宽，在已有因特网上构造一个逻辑的端-端服务投送网络。 用户通过业务合同，直接向SON服务商付

9、费来使用SON提供的增值服务。,SON体系结构,SON由服务网关连接而成 两个服务网关之间的逻辑连接由底层ISP提供，带宽和服务质量由双边SLA保证。,SON的优点,引入一个新的流量聚合层次（服务聚合）： ISP按流量所属的SON进行流量聚合。 解除了应用服务与网络服务的耦合： ISP根据SLA设置数据传输服务（粗粒度）。 SON采用与服务相关的带宽管理、流量工程和QoS保证机制，确保服务的端-端服务质量（细粒度）。 减小了管理和控制网络服务的复杂性 允许灵活地创建和部署新的增值服务,1.3 面向服务的因特网 Service Oriented Internet（SOI）,覆盖网络的缺点： 由于

10、完全不考虑网络层，一定程度的低效率是不可避免的。 有些覆盖网络提供的服务需要底层网络的支持才能发挥作用。 有些功能在多个覆盖网中重复实现。 服务覆盖网下面需要一个底层基础架构，解决覆盖网的低效问题，并支持新的应用需求。,SOI概述,SOI在逻辑上分离数据传输网络和服务覆盖网络： 数据传输网络：大致对应当前的自治系统，为服务覆盖网提供比特管道服务。 服务覆盖网络：由服务提供商运营，向订户（服务订购者）提供特殊的增值服务。 服务覆盖网络被抽象成服务云，在多个地方与数据传输网络接口。 用户请求在数据网络上被路由到某个服务云的最近（或最合适）入口，由服务云中的某个主机服务。,SOI体系结构,SOI概述

11、（续）,数据网络与服务网络逻辑分离的好处： 允许这两种网络独立进化，在支持已有服务的同时方便未来因特网服务的灵活部署。 实现逻辑独立性的机制： 彻底分离数据网络与服务网络的编址、路由和转发机制 每个服务云可以独立实现自己的编址、路由和转发机制,SOI的抽象,SOI是建立在已有IP网络之上、为灵活部署新的因特网服务而提供的一个公共平台。 SOI架构基于三个重要的抽象： 服务云 面向服务的编址方案（服务云，云中的对象） 服务层（服务网关，服务存在点）,（1）服务云,服务云是一群部署在因特网上、相互协作向用户提供应用服务的服务实体（如服务器、代理、缓存、内容交换机等）。 服务云是一个虚拟的服务覆盖网

12、络，依靠下层网络域在因特网范围传输数据。 服务云和因特网的接口称为服务存在点，数据对象进出服务云只能通过服务存在点。,（2）面向服务的编址方案,SOI的编址方案提供服务云及服务云中对象的位置无关标识： 每个服务云被分配一个固定长度（32位）的ID（称sid），由一个中央权威机构管理。 服务云中的对象用一个对象ID（称oid）标识，其语法和语义由各个服务云定义，只在服务云内部使用。,命名与名字解析,服务云的命名与解析： 每个服务云大致对应了目前具有两层或三层域名的一个机构（如），机构的域名就作为服务名。 可以重用DNS或建一个类似的名字解析系统，将服务名解析为sid。 对象的命名与解析： 服务云

13、根据自己的商业需要定义对象的命名和编址系统。 服务云提供对象解析的功能。 将两级地址的解析分开，增加了灵活性和安全性。,（3）服务层,SOI架构的基础是位于IP层之上的一个服务层，包含两个网络单元： 服务网关：可看成是下层网络域的扩展，通常部署在网络域边缘，负责穿过网络域的路由和服务交付。 服务存在点：服务云与网络域接口的地方，逻辑上是服务云的一部分，负责在服务云内部交付对象。 进出服务云的数据都要经过服务网关，服务网关提供服务区分、识别和跟踪服务云流量的功能。,服务层在协议栈中的位置,服务层协议数据单元（服务对象）,服务对象头部分为sid部分和oid部分 服务修正符由服务云定义，对服务对象的

14、转发有影响。,服务网关（Service Gateway）,数据面功能： 根据目的sid（或目的sid + 源sid）及相关的服务修正符，将服务对象转发到去往目的服务云的下一跳（相邻的S-POP或另一个SG）。 控制面功能： 运行服务网关路由协议，建立服务路由表。 服务路由表包含目的sid（及相关的服务修正符）到下一跳SG/S-POP（用IP地址表示）的映射。,服务存在点（S-POP）,服务存在点有两个主要功能： 与服务网关合作，为它所代理的服务云路由和转发服务对象（发往服务云外部）。 和服务云中的其它S-POP合作，在服务云内部路由和转发服务对象。（服务云内部机制） 为实现第一个功能： 控制面

15、：参与服务网关路由协议，建立（部分的）服务路由表，表中包含从sid空间到相邻SG的映射。 数据面：利用服务路由表，将服务对象转发到服务云外。,服务网关路由协议,服务网关路由协议主要负责建立服务路由表，包括两个部分： S-POP注册和公告： S-POP向本地服务网关注册，通告其存在、所代表的服务云sid、能够处理的流量类型（一组服务修正符）。 传播服务可达性：从邻居服务网关学习路径和向它们发布路径（类似BGP）。,参考文献,Resilient Overlay Networks. SOSP 2001. Service Overlay Networks: SLAs, QoS and Bandwidt

16、h Provisioning. ICNP02. Service Oriented Internet.,2 应用层组播,IP组播体系结构： 路由器采用分布式算法构造一棵数据转发树；组播分组沿转发树转发时，在树的分支节点处由路由器进行复制。 IP组播协议：MOSPF、DVMRP等。 IP多播骨干网：MBone IP组播是实现组播转发的最有效方法，可使全网范围的分组复制数量最少。,IP组播的缺点,路由器必须为每个组播组单独保存状态，路由表和转发表也需要为每个组播组维护一个地址项（组播地址不能聚合），扩展性很差。 要求所有路由器支持组播功能，给IP组播的推广使用带来很大困难。 试图用一种统一的组播模型

17、来适应所有的应用，给组播算法的设计造成很大困难。 组播组的管理开销大。 在IP组播中实现可靠性和拥塞控制非常困难。 在经济方面，尚没有针对组播的流量计费机制。,应用层组播,在应用层上，依靠端系统之间的单播实现组播。 优点： 不需要改变现有路由器，能够很快进入应用。 单播技术较成熟，基于单播实现的应用层组播易于实现差错控制、流量控制、拥塞控制等。 缺点： 延迟较大：应用层组播不考虑网络本身的拓扑结构。 效率不如IP组播：应用层组播会产生较多数据冗余。 应用层组播研究如何构造并维护高效率的覆盖网络。,应用层组播的例子：Overcast,Overcast网络用于单源组播，由以下几个部分组成： 一个源

18、服务器 任意数目分布在因特网上的中间节点（有永久存储的PC机） 分布在因特网上的标准HTTP客户（Web浏览器） 分发树建立协议：将中间节点组织成一棵以源为根的分发树。,多播组的命名,Overcast借用HTTP URL表示多播组： hostname指出一个Overcast网络的根，源相同的所有组共享一棵分发树。 Path指示该网络中的一个多播组。 标准的HTTP客户都可以加入这些多播组。 使用URL作为多播组的名字空间有以下好处： 分层的名字空间解决了多播组地址空间缺乏的问题。 基于HTTP的应用不加修改就能使用到多播。 URL结构丰富，表达能力强。,Overcast的应用：视频分发系统,系

19、统由一个studio和在一些合适位置放置的appliance组成，appliance和studio协作组织成一棵分发树。 studio存储内容，并根据需要调度内容到appliance上。 内容发布者生成一个web页，发布内容的链接。 用户点击内容的URL后， 浏览器根据hostname将请求发送到studio。 Studio根据path将请求发送到客户附近的appliance。,节点初始化,节点初始化（节点配置和注册）： 确定节点进行一般IP连接所需要的IP地址和网关地址（DHCP服务或手工配置）。 向一个全局的、熟知的注册机构发送自己的序列号。 注册机构提供给节点一个应当加入的Overcas

20、t网络列表、一个可选的永久IP配置、应当服务的网络区域、应当执行的访问控制。,建立分发树,Overcast建立转发树的原则是，最大化从根（源服务器）到所有中间结点的带宽： 将节点放置在尽可能远离根的地方，同时不牺牲到根的带宽。 得到一棵较深的分发树，节点在分发树上得到的带宽不低于其直接从根获取内容得到的带宽。,分发树的建立过程,当有一个新节点向根注册时，启动分发树建立过程： 设根为“当前节点”； 新节点检测直接到“当前节点”的带宽，以及经过“当前节点”的各个孩子节点到达“当前节点”的带宽； 如果经由某个孩子节点到“当前节点”的带宽和从它直接到达“当前节点”的带宽一样高，该孩子节点成为“当前节点

21、”，继续探测。 如果有多个孩子节点满足条件，距离新节点最近（跳数最少）的孩子节点成为“当前节点” 。 如果没有一个孩子节点满足条件，“当前节点”成为父节点，搜索过程结束。,分发树的自适应调整,节点周期性地重新评估它在树中的位置： 如果到某个兄弟节点的带宽不低于到父节点的带宽，将自己置于该兄弟节点之下。 如果直接到祖父节点的带宽大于到父节点的带宽，将自己置为当前父节点的兄弟节点。 Overcast网络容忍非根节点的失效： 当节点发现父节点不可达时，将自己连接到祖父节点下。 如果祖父节点不可达，节点继续沿系谱往上移，直到找到一个当前活跃的节点。,网络维护,每个节点维护一张表，记录在树中低于自己的节

22、点的信息，根节点的信息表包含树中所有节点的最新信息 。 每个节点周期性地向父节点报告自己的存在： 如果一个孩子节点在预定的时间间隔内没有报告，父节点在表中记录该孩子及其子孙节点“死了”。 节点还会报告其观察到或被告知的信息，如错过报告时间的孩子和新增的孩子等。,加入多播组,web客户发送一个包含该多播组URL的HTTP GET请求，URL的hostname指出分发树的根，path指出多播组。 根节点使用path、用户位置以及当前状态数据库决定将用户从树的哪个位置接入。,用Overcast实现多播,数据在父节点和子节点之间通过TCP传输： 内容可能会流水地通过树上的几代节点。 一个大文件或一段长

23、时间的实时流可能会同时在几十个不同的TCP流中传输。 如果出现路径失效： 重建分发树； 节点检查日志，重新启动未完成的传输。,参考文献,Overcast: Reliable Multicasting with an Overlay Network. OSDI 2000.,3 内容分发网络 Content Delivery Networks（CDN）,提高Web服务性能主要围绕网络传输和服务器两个方面： 提高单台web服务器的性能： 增加更多的内存和磁盘空间，使用更高速的处理器（或多处理器），使用缓存来减少读盘次数等。 性能提高有限，响应延迟受网络拥塞影响大。 建立服务器集群（server fa

24、rm）： 多个web服务器分担对同一个web站点的访问请求。 响应延迟受网络拥塞影响大。,提高Web服务性能的方法（续）,建立分级的web缓存机制： 将用户最近访问过的网页保留在高速缓存中，使用一个代理（proxy）来管理缓存。 浏览器配置为向代理请求网页，若本地缓存没有，向上一级代理或源服务器请求。,提高Web服务性能的方法（续）,建立内容分发网络： 在因特网的不同地方设置镜像服务器，将用户请求重定向到最近的服务器。 有助于减小网络传输和服务器负载对请求响应时间的影响。,CDN涉及的主体,内容提供商（customer）： 提供内容服务的机构或公司，其内容保存在源服务器（origin serv

25、er）。 CDN提供商： 拥有CDN架构，为内容提供商提供快速可靠的内容递送服务。 端用户（client）： 从内容提供商的网站上访问内容的实体。,内容分发环境,CDN的内容,CDN一般保存静态内容： 如图像、视频、媒体剪辑、广告、动态网页中的嵌入式对象等。 在CDN的上下文中，内容泛指任何数字形式的数据资源，主要包括两大部分： 经过编码的媒体。 元数据：用来标识、发现和管理媒体数据的内容描述。,CDN的客户,CDN的客户一般是媒体和因特网广告公司、数据中心、ISP、在线音乐零售商、移动运营商、消费电子生产商等。 CDN客户希望可靠而及时地在因特网上向端用户发布和投送内容。 CDN提供商根据投

26、送给端用户的内容（即流量）向内容提供商收费。,CDN的体系结构,基础结构：提供基础设施资源，由通过高速网络连接的分布式计算资源和网络基础设施组成。 通信和连接：提供核心的互连网协议、CDN特定的协议、认证协议、安全通信协议SSL。 CDN：CDN核心功能。 端用户：web用户，在web浏览器上给出内容提供商网站的URL连接到CDN。,CDN提供的服务和功能,内容存储和管理 在代理服务器间分发内容 缓存管理 静态、动态和流内容投送 备份和灾难恢复解决方案 监视、测量和报告性能,内容简介,从以下三个方面介绍CDN： CDN组成 内容分发和管理 请求路求 参考文献： A Taxonomy and S

27、urvey of Content Delivery Networks. Http:/www.cloudbus.org/reports/CDN-Taxonomy.pdf,3.1 CDN的组成,CDN的任务是结合网络条件和缓存服务器负载等动态信息，在多个反向代理（surrogate）之间重定向请求和平衡负载。 在一个CDN中，通常使用一组反向代理来建立内容分发设施，使用一些机制将用户请求重定向到一个反向代理，各单元之间使用特定的协议进行通信。,Surrogate 和 Proxy,Proxy用于代理内部网络对因特网的连接请求。客户机将本来要直接发送到外部服务器上的服务请求发送到代理服务器，由代理服务

28、器中继服务请求。 Surrogate用于代理外部网络上的主机访问内部网络，此时Surrogate对外表现为一个web服务器。 反向代理可以增强web服务器的安全性，和作为后端服务器集群的负载均衡器。 反向代理方式和普通代理方式没有冲突，可以在防火墙设备中同时使用。,CDN的结构特性,3.1.1 CDN的组织方式,网络方法： 在路由器和交换机等网络组件上安装相关软件，将内容请求重定向到本地缓存或特定的内容服务器。 覆盖方法： 使用放置于网络中多个地方的应用特定服务器（反向代理，高速缓存服务器）处理特殊内容（web内容、流媒体等）的分发。 除了提供基本的网络连接和QoS保证外，核心网络组件在内容分

29、发过程中不发挥积极作用。,3.1.2 CDN服务器,源服务器（origin server）： 存放资源的权威版本，由内容提供商更新。 复制服务器（replica server）： 存放资源的拷贝，并被授权响应用户的请求 。 通过源服务器进行内容更新。,CDN的复制服务器,CDN的复制服务器可以作为媒体服务器、web服务器或高速缓存服务器： 媒体服务器（media server）：提供数字编码的内容，安装有媒体服务器软件，用音频或视频素材响应用户的请求。 Web服务器：包含到流媒体的链接，以及CDN希望提供的其它基于web的内容。 高速缓存服务器（cache server）：在网络边缘复制内容，

30、以减少对源服务器的访问。,流媒体应用的实现,音/视频文件存储在媒体服务器上，元文件存储在Web服务器上。 媒体播放器和媒体服务器之间通过RTP/UDP传输音/视频流，使用RTSP进行交互性操作。,3.1.3 CDN组件之间的关系,CDN的各个组件通过相互协作来实现CDN内部的内容复制和高速缓存： 复制：在不同的计算机系统上创建和维护内容拷贝，典型地是将内容从源服务器“推送”到复制服务器。（Push） 缓存（caching）：将可缓存的响应保存在本地，以便将来响应相同的请求。 （Pull）,用户-反向代理-源服务器,内容投递的基本关系是在用户、反向代理服务器和源服务器之间： 用户一般同反向代理服

31、务器通信。 反向代理服务器用本地缓存的内容响应用户请求，或作为源服务器的网关。,用户-网元-高速缓存代理（caching proxy）,在网络方法中，网元（路由器、交换机）上的控制逻辑将用户请求转发到相应的高速缓存代理（代理阵列）。,高速缓存代理-高速缓存代理,根据高速缓存代理之间的通信方式，高速缓存代理可以组织成代理阵列或代理网： Proxy array：紧耦合结构，有一个权威代理作为主代理，与其它代理通信。 Proxy mesh：松耦合结构，每个代理都和其它代理有联系，构成代理网。Proxy mesh需要一个高速缓存服务器作为网关，转发来自用户本地缓存代理的请求。,代理阵列 和 代理网,3

32、.1.4 协议,CDN中的通信协议分为两类： 网元交互协议：用于将用户请求重定向到一个合适的服务器，涉及路由器、内容交换机/负载均衡器、服务器等实体。 高速缓存交互协议：用于在分布式高速缓存中确定所请求的内容在哪个高速缓存中。,网元-服务器（NECP）,运行在服务器（源服务器、拦截代理）与其前端设备（内容交换机、负责均衡路由器）之间的控制协议： 服务器启动时，与网元的熟知端口建立TCP连接，在TCP连接上进行双向消息交换。 网元通过消息交换了解服务器的能力、可用性、可以获得哪些内容等，作为重定向用户请求的依据。,重定向路由器-拦截代理（WCCP）,运行在重定向路由器和拦截代理之间，建立和维护用

33、户请求的透明重定向： 若干拦截代理和若干重定向路由器组成一个服务组，指定一个代理（IP地址最小）作为首领，负责在代理群之间分配负载，并将负载分配方法在组内传播。 通过该协议，路由器知道如何重定向用户请求；拦截代理知道如何管理高速缓存中的内容。,防火墙安全会话转换协议SOCKS,SOCKS是为客户-服务器应用安全通过防火墙而提供的一个通用框架。 当内网用户想访问外网服务器时，首先与SOCKS代理服务器建立连接，进行认证。若认证通过，SOCKS代理服务器与外网服务器建立连接，并中继用户请求；否则终止与用户的连接。 SOCKS代理服务器只是简单地传递包，而不关心是何种应用协议，因此SOCKS是一种通

34、用的服务，在概念上位于应用层和传输层之间。,Internet Cache Protocol（ICP）,Cache被组织成层次结构： 用户请求发送到本地缓存。 若本地缓存没有，本地缓存向同伴缓存广播请求。 若同伴均回复没有或超时，本地缓存向父缓存请求。 若父缓存没有，父缓存或本地缓存向源服务器请求。 ICP基于查询/应答实现，通信开销大，延迟大。,Cache Digest,每个节点保存其它节点中所缓存的内容的摘要： 本地缓存收到用户请求后，检查本地缓存的内容和其它节点的缓存内容摘要； 若本地缓存有内容，直接响应用户的请求； 若有缓存内容摘要，向相应的缓存节点请求； 若没有缓存内容摘要，向源服务器

35、请求内容。 优点：不需要发送查询消息到其它缓存节点。 缺点：存储摘要的代价很高，节点之间需要更新摘要。,Cache array routing protocol（CARP）,浏览器利用cache阵列成员表、一个查找函数和用户请求的URL，就能确定最合适的cache服务器。 Cache阵列成员表定义在一个可公开获取的文本文件中，文件中列出了每台代理服务器的名字、IP地址和负载因子（管理员指定）。 浏览器需要下载Cache阵列成员表和一个查找函数（JavaScript函数）。,CARP（续）,查找函数实现CARP算法： 使用指定的哈希函数计算URL的散列值及每个成员名字的散列值，两个值结合得到每个

36、成员对该URL的一个分值。 将该分值与成员的负载因子结合，得到每个成员对该URL的总分。 总分最高的cache服务器选中。 优点： 没有缓存冗余，缓存命中率高。 缓存节点间不需要通信，没有查询和更新开销。,3.1.5 内容/服务类型,CDN提供的内容/服务有三类：静态内容，流媒体，各种内容服务。 静态内容： HTML页、图片、文档、软件补丁、音/视频文件等。 更新频率很低，易于缓存。 所有CDN提供商都支持静态内容的投递。,流媒体,流媒体包括： 现场音/视频：内容从编码器立即送到媒体服务器，然后送给媒体用户。 点播音/视频：内容预先被编码，作为流媒体文件保存在媒体服务器中，用户请求时投送。 流

37、媒体服务需要专门的流式服务器，使用特定软件实现流媒体在IP网络中的传输。 投送流媒体内容对于CDN是一个挑战。,内容服务,将CDN作为服务分发渠道，允许增值服务提供商在上面提供增值服务（内容服务），如： 目录服务：将用户的查询请求定向到包含请求内容的数据库服务器，并将频繁请求的查询结果缓存在CDN的边缘服务器上。 网页压缩服务：提供对网页的实时压缩，并对源服务器和用户透明。 电子商务服务：比如在CDN的边缘服务器上保存和维护购物车、进行在线交易等，减轻源站的压力。,3.2 内容分发和管理,内容分发： 反向代理放置：确定反向代理服务器的放置位置及数量，最小化用户访问延迟和网络带宽消耗。 内容选择

38、和投送：正确选择要复制到CDN的内容，减少用户下载时间和服务器负载。 内容外包：如何将选择的内容复制到放置好的反向代理服务器？复制到哪一个反向代理服务器？ 内容管理： 高速缓存组织：缓存技术、缓存更新、缓存策略。,3.2.1 反向代理服务器的放置,目标：确定反向代理服务器的个数和放置位置。 问题模型： 给定一个图G（V, E）和要放置的中心数量k，确定中心的位置，使得所有节点到最近中心的最大距离最小化。 理论算法： 计算复杂度大。 启发式算法： 利用来自CDN的一些信息，如负载模式、网络拓扑等，以较低的计算代价获得次优解。,启发式算法（1）,Greedy replica placement：

39、前提：知道网络中所有用户的位置，以及每一对节点间的距离。 算法思想：从N个可能的站点中选择访问代价最小的M个站点放置反向代理。 过程： 第一轮计算每个站点的代价，计算时假定所有用户的访问都汇聚到该站点，代价最小的站点被选中。 结合已选中的站点，第二轮搜索代价第二小的站点。 依次类推，直至M个站点选出来。,启发式算法（2）,Topology-informed placement strategy： 假设： 有较大出度的节点可用较小的延迟到达更多的节点。 算法基本思想： 使用自治域一级的拓扑，每个节点代表一个AS，每一条链路对应一对BGP对等体。按节点出度的降序选择M个节点放置反向代理。 改进的算

40、法： 用路由器一级的拓扑代替AS一级的拓扑，与路由器相连的每个局域网都可以放置一个反向代理。,启发式算法（3）,Hotspot算法： 按照产生流量的大小对站点进行排序； 将M个反向代理放置在生成流量最大的M个站点上。,确定反向代理服务器的数量,单ISP方法： 仅在CDN提供商的网络边缘放置反向代理服务器。 放置策略：在ISP覆盖的区域内，每个大城市放置一个或两个反向代理服务器。 缺点：反向代理服务器可能离用户很远。 多ISP方法： 在尽可能多的互联网入网点（ISP Points of Presence）上放置反向代理服务器。 优点：反向代理服务器位于请求用户的ISP上。 缺点：建设成本及复杂性

41、高，服务器使用率低。,3.2.2 内容选择和投送,正确选择要复制到CDN的内容，以减少用户下载时间和服务器负载。 两类方法： 全站点内容选择和投送：将源服务器上的全部对象外包给反向代理服务器。 部分站点内容选择和投送：只将源服务器上的部分内容复制到反向代理服务器。,全站点内容选择和投送,内容提供商配置其DNS，令所有对其web站点的请求都由一个CDN服务器解析，这样全部内容都由CDN投送。 优点：简单。 缺点：不具有可行性（边缘服务器不可能拥有足够的存储空间，更新也很难做到）。,部分站点内容选择和投送,反向代理服务器只投送内置于网页的对象（如图片）。 内容提供商修改其内容，将特定对象URL中的

42、host name改为CDN提供商权威域中的域名。 HTML基础网页从源服务器获取，内嵌的对象从CDN反向代理服务器获取。 优点： 降低了对反向代理服务器的存储容量需求； 只投送静态的或更新较慢的内容，减轻更新压力。,部分站点方法（1）,基于实证的（empirical-based）方法： 管理员依据经验选择复制到反向代理服务器的内容。 缺点：选择正确经验的不确定性。 基于流行的（popularity-based）方法： 最流行的对象被复制到反向代理服务器。 缺点： 耗时（要对对象的流行程度进行评估和排序） 难以得到可靠的对象请求统计信息（流行性变化大） 新内容的统计信息得不到,部分站点方法（2

43、）,基于对象的（object-based）方法： 内容以对象为单位复制到反向代理服务器。 在满足存储容量的前提下，每复制一个对象到反向代理服务器都试图最大化性能增益（贪婪算法）。 优点：可获得最佳性能 缺点：实现复杂度高,部分站点方法（3）,基于聚类的（cluster-based）方法： web内容依据相关性或访问频度分组，并以内容聚类为单位进行复制。 基于用户会话的内容聚类：利用web日志文件，确定具有关联内容的网页组。 基于URL的内容聚类：依据web站点的拓扑来汇聚web内容，从一个web站点中识别出最流行的对象，然后按URL之间的相关距离进行聚类。 这类方法可以减少用户下载时间和服务器

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

45、向代理服务器； 如果缓存不命中，反向代理从源服务器取内容。 大多数流行的CDN提供商使用该方法。 Cooperative pull-based： 用户请求被定向到最近的反向代理服务器； 如果缓存不命中，反向代理使用一个分布式索引在附近找到所请求内容的拷贝。,外包内容的最佳放置,问题： 外包内容复制到哪一个反向代理服务器最好？ 各种启发式算法（略）： 考虑负载均衡和/或下载延迟,3.2.4 缓存组织（cache organization）,内容管理主要由CDN的缓存组织方式决定： 缓存技术：如何从分布式缓存中找到要请求的内容？ 缓存更新：如何保证缓存内容的一致性和新鲜性？,（1）缓存技术（cac

46、hing techniques）,CDN中的内容缓存分为簇内缓存和簇间缓存,簇内缓存,基于查询的缓存方案： 当一个反向代理服务器发现cache miss后，向簇内的其它反向代理服务器广播一个查询。 若所有的反向代理服务器都没有该内容，该反向代理向源服务器请求。 缺点：查询流量大（查询洪泛），延迟长（需要等待所有的反向代理服务器返回响应）。,簇内缓存（续）,基于摘要的缓存方案： 每个反向代理服务器维护其它服务器中内容的摘要，内容更新的通知发送给所有的反向代理。 反向代理服务器检查保存于本地的内容摘要后，决定将内容请求路由到哪个反向代理。 优点：解决了查询洪泛的问题。 缺点：存储量大，更新流量大（

47、频繁发送更新通知）。,簇内缓存（续）,基于目录的缓存方案： 摘要方法的集中式版本，一个集中的目录服务器保存簇内所有反向代理服务器上内容的信息。 每个反向代理只将内容改变通知目录服务器，并在本地cache miss后查询目录服务器。 缺点：目录服务器接收来自所有反向代理的更新和查询流量，是性能瓶颈和单故障点。,簇内缓存（续）,基于哈希的缓存方案： 所有反向代理服务器使用相同的哈希函数和一组反向代理IP地址，根据内容的URL确定内容存在哪个服务器（称为内容的指定服务器）上。 对内容的请求全都定向到其指定服务器。 优点：实现代价最小（没有查询流量，也不需要维护摘要或目录），内容共享效率最高（没有缓存

48、冗余）。 缺点：对本地请求的扩放性不好（本地用户的请求会被引导到其它的反向代理服务器）。,簇内缓存（续）,基于半哈希的缓存方案： 本地反向代理服务器划出一部分磁盘空间，用于缓存本地用户经常请求的内容，其余空间采用基于哈希的方法与其它服务器协作。 优点：实现开销小，内容共享效率高，本地内容命中率高。,簇间缓存,基于摘要或目录的方法： （不可行） 扩放性差（每个簇的代表服务器必须维护其它簇的服务器中所存内容的信息）。 基于哈希（半哈希）的方法：（不可行） 局部性不好。 基于查询的方法： 唯一可以应用到簇间缓存的方法。,簇内、簇间使用不同的缓存技术,簇间使用基于查询的缓存技术，簇内使用基于哈希的缓存

49、技术： 当一个簇不能服务某个内容请求时，其代表服务器向邻近的簇（代表服务器）发出询问。 在每个簇内，代表服务器只向内容的指定服务器询问。,（2）缓存更新,缓存更新技术用于保证缓存服务器上的内容是最新的。 周期性更新： 内容提供商配置源web服务器，向缓存服务器提供缓存指示，如内容的可缓存性、过期时间、向源服务器的核对时间等。 缺点：每个更新间隔会产生大量不必要的更新流量。,缓存更新（续）,更新传播： 每当源服务器上的一个内容发生了改变，更新的内容就被主动推送到所有的缓存服务器。 缺点：内容频繁更新时产生过多的更新流量。 按需更新： 仅当内容被请求时，最新的内容拷贝才被投送到发出请求的缓存服务器。 缺点：源服务器和缓存服务器之间来回传递消息（如询问最新的版本），延迟大。,缓存更新（续）,无效（invalidation）： 当源服务器中的某个文档发生改变时，源服务器向所有的代理服务器发送一个无效消息。 需要时，每个代理服务器单独向源服务器获取文档的最新拷贝。 优点：消除了不必要的内容推送和更新查询。 缺点：没有充分利用CDN的资源，每个代理服务器需单独向源服务器获取文档的最新拷贝。,（3）内部缓存策略,使用规则集定义缓存策略： 内容提供商用一个规则集向CDN提供商描述缓存策略； CDN提供商将规则集传播给自己的缓存服务器。 使用