（通信与信息系统专业论文）cdn内容交换技术的研究.pdf

塑垩盔堂堡主兰垡堡塞 甍9 3 5 2 8 摘要 自着网络技术的不断发展，人们对i n t e m e t 内容的访问量和提供服务的服务器数量飞速 增艮。同时，网络的应用也趋于多样化，电子商务、多媒体等业务的出现使用户对网络的性 能要求也越来越高。肠了提高用户访问网站的响应速度、优化现有i n t e m e t 中信息的流动、 提高网站的安全性和可用性，在现有的i n t e m e t 网络中建立一个完善全面的中间层一内容分 送网络，使用户能以最快的速度，从最接近用户的地方获得所需的信息，彻底解决网络拥塞， 提高响应速度，是目前流行的应用方案。 内容分送网络主要涉及的关键技术包括内容路由、内容分发和网络性能的测量，其中 内容路由包括全局路由和局部路由，局部路由又称内容交换，是本文的研究对象。决定内容 交换性能好坏的两个关键因素是分发算法和转发机制。 第一章综述了c d n 的概念及其设计原则，并对c d n 的整体结构按功能模块做了简要 的介绍。 第二章介绍了内容交换的结构，分类阐述了当前用于内容交换的各种分发算法和路由机 制并对这些算法和机制做了简单的分析比较。 第三章对典型的三种分发算法( w r r 、u r lh a s h i n g 、l a r d ) 作了性能上的仿真。根 据仿真结果，分析了三种算法的性能优劣，并论述了服务器参数对三种算法的影响。 第四章对三种典型的转发机制( 包头重写、t c p 切换、t c p 粘合) 作了性能上的仿真。 根据仿真结果，对三种机制做了性能上的分析。 第五章建立了内容交换的理论模型，对使用不同分发算法和转发机制的内容交换结构的 性能作了理论计算。 最后是结论与展望，对整个内容交换的结构实现做了性能上的评价和建议，并对进步 的研究进行了展望。) 皿，、 煳氧蝻雠网穆嘤弩卧 ( 塑垩盔兰堡主兰垡堡兰一一 a b s t r a c t w i t ht h ed e v e l o p m e n to f t h en e t w o r kt e c h n o l o g y , i n t e r a c t u s e r sa r eg e t t i n gb e t t e ra c c e s s b u t w en e e dah i g h - p e r f o r m a n c e ，r e l i a b l ev e h i c l ef o rt h ea p p e a r a n c eo fb a n d w i d t h - i n t e n s i v e ，r i c h m u l t i m e d i ac o n t e n ts u c ha se c o m m e r c et r a n s a c t i o n s ，s t r e a mm e d i a c d ni s t h ec u r r e n ts o l u t i o n s c h e m et oa d v a n c et h eu s e ra c c e s ss p e e da n dg u a r a n t e et h en e t w o r ks e c u r i t y c d nc a nb ed i v i d e di n t ot h r e ei n d e p e n d e n tb u i l d i n gb l o c k s i na d d i t i o nt ot h en e t w o r k i n f r a s t r u c t u r e ：c o n t e n tr o u t i n g ，c o n t e n td e l i v e r y , a n dp e r f o r m a n c em e a s u r e m e n t t h e r ea r et w o d i f f e r e n ta s p e c t st oc o n t e n tr o u t i n g t h ef i r s ti st h eg l o b a lr o u t i n g ；t h es e c o n da d d r e s s e st h el o c a l r o u t i n g ( o rc o n t e n ts w i t c h i n g ) ，w h i c hi st h e m a i nt o p i co f t h i sp a p e r t w of a c t o r s ，w h i c ha f f e c tt h e p e r f o r m a n c e o f t h ec o n t e n ts w i t c h i n g , i sd i s p a t c h i n ga l g o r i t h ma n dm u t i n gm e c h a n i s m c h a p t e r1 i n t r o d u c e st h ec o n c e p ta n dd e s i g np r i n c i p l eo fc d n ，a n dp r e s e n t st h et h r e eb u i l d i n g b l o c ko f c d n c h a p t e r2p r e s e n t st h ea r c h i t e c t u r e so f c o n t e n ts w i t c h i n g ，c l a s s i f i e sa n dd e s c r i b e sm a i nc u r r e n t r o u t i n gm e c h a n i s m sa n dd i s p a t c h i n gr e q u e s ta l g o r i t h m st os p l i tt h el o a da m o n g t h es e l w e rn o d e s ， a n d a n a l y s e st h e i rp e r f o r m a n c e c h a r a c t e rq u a l i t a t i v e l y c h a p t e r 3i m p l e m e n t st h es i m u l a t i o no f t r a d i t i o n a ld i s p a t c h i n ga l g o r i t h m s ( w r r ，u r l h a s h i n g a n dl a r d ) ，a n da n a l y s e st h e i rp e r f o r m a n c ec h a r a c t e rb a s e do nt h er e s u l to f s i m u l a t i o n c h a p t e r 4i m p l e m e n t st h es i m u l a t i o no ft r a d i t i o n a lr o u t i n gm e c h a n i s m ( p a c k e t - r e w r i t i n g , t c p h a n d o f fa n dt c p s p l i c i n g ) ，a n dt h e nc o m p a r e s t h e i rp e r f o r m a n c ec h a r a c t e rb a s e do nt h er e s u l to f s i m u l a t i o n c h a p t e r5e s t a b l i s h e st h eu n i v e r s a lc o n t e n ts w i t c h i n gq u e u i n gm o d e l ，a n dc a l c u l a t e ss w i t c h i n g s y s t e mt h e o r e t i c a lp e r f o r m a n c e l a s ts e c t i o nc o n c l u d e st h ep a p e ra n dp r o s p e c t st h et e c h n o l o g yo fc o n t e n ts w i t c h i n gf o rf u t u r e r e s e a r c h k e y w o r d ：c d n ，c o n t e n ts w i t c h i n g ，d i s p a t c h i n ga l g o r i t h m ，r o u t i n gm e c h a n i s m 塑垩奎堂堡主兰垡堡苎一 第一章绪论 1 1引言 随着网络技术的不断发展，人们对i n t e m e t 内容的访问量以及提供服务的服务器数量也 随之e 速增长。据n u a i n t e m e ts u r v e y s 互联网调查公司统计，2 0 0 2 年9 月低全球互联网用 户已经从2 0 0 2 年5 月底的5 8 0 7 亿增长到了6 0 5 6 亿，全球网络用户首次突破了6 亿，而在 1 9 9 9 年全球仅有1 亿用户。到2 0 0 2 年初，全球w e b 站点数量就已超过4 0 0 0 万个，而在1 9 9 9 年这一数字只有3 6 0 万个。同时，网络的应用也趋于多样化，电子商务，多媒体等业务的出 现使得j 1 ：j 户对网络的性能要求也越来越高。虽然网络用户的数量在急剧增长，网络上分布的 内容在迅速膨胀，但是网络用户对内容的访问率却提升很慢，网络上应用业务的种类仍旧相 当单一。造成这种局面的根本原因是：用户访问时，网站的响应速度太慢。 仔细分析这种网站响应速度缓慢慢的原因可以知道，随着不同宽带技术的不断成熟， 带宽将不是其主导因素，但是如果没有对互联网流量进行精心规划和管理良好，不管有多大 的带宽，用户对网站的访问连接同样也会很慢。除此而外，随着电子商务的迅猛发展，使得 网络系统的可靠性、一致性、安全性和高可用性也显得越来越重要。因此，当前网站的管理 除了必要的内容服务外，提高网站的扩展能力、服务能力以及可用性也成了不可或缺的环节。 而耍很好地解决所有这些问题，必须要有新技术的支持。 为了能提高用户访问网站的响应速度、优化现有i n t e m e t 中信息的流动、提高网站的安 全性和可用性，在现有的i n t e r n e t 网络中建立一个完善全面的中间层一内容分送网络 ( c o n t e n td e l i v e r yn e t w o r k ，简称c d n ) ，使用户能以最快的速度，从最接近用户的地方获得 所需的信息，彻底解决网络拥塞，提高响应速度，是目前流行的应用方案。 1 2c d n 的定义和构建方法 由于c d n 是一种较新的技术，对它的定义也是众说风云。有人认为它只是在i n t e m e t 或私人网络上传送流媒体或视频的分发系统，也有人将它定义为w e b 交换或内容交换，更 有人将它简单地看作是用于提高网路性能的一种手段。但事实上，这些观点只包括了c d n 技术的一部分。在本文中，c d n 将被定义为一种用于优化分发具体内容( 例如静态网页， 电子商务，流媒体，实时视频或音频等) 性能的网络，它的目的是将包括不同图片或视频的 内容以高可用性的方式快速地提供给用户。当前在提高网站性能方面，c d n 已经显示出它 塑坚查兰堡主兰笪堡苎 的作t l = f j 。可以用一句话来概括：c d n 的目的是尽可能地将内容存放到离用户最近的地方以 降低用户访问的延时、抖动( 即某些不可预测的变化所造成的延时) ，进而提高网络带宽的 利h j 率。 有两种方法可用于构建c d n 。一种是叠加模型，该模型将要服务的内容复制到全球的 各个服务器上，在不同的接入点设置服务不同内容( 如图片、流媒体) 的服务器。在这种构 建方法中，核心网络的组件( 包括路由和交换等) ，不属于内容分发网络的范畴，它只涉及 具体类型的流量的基本连接和q o s 控制。象a k a m a i ，d i g i t a li s l a n d 和s p e e d e r a 等公司的 c d n 技术都是使用这种模型。另一种是网络模型。使用这种模型必须使用特定的路由器和 交换机，这样网络可以根据不同预定义好的策略识别不同的应用类型进行请求分发。我们在 设计个c d n 系统时综合使用了上述的两种模型。具体的网络结构将在下一节详细阐述。 般地，我们将c d n 看作是一种叠加模型，即c d n 可以认为是一种叠加于传输网络 之上的用于向分布在各地的用户分发内容的系统，如图1 - 1 所示。因此，本文不关心网络的 传输组件( 包括广播、边缘网关协议( b g p ) 、q o s 等) 。 内容传输1 网站主机电子商务流媒体服务应用软件 内容分送网络 接入手段 图1 - 1c d n 在网络中的位置 1 3 c d n 的设计原则 鉴于c d n 网络系统在整个网络系统中的重要性，网络系统设计必须既适应当前应用考 虑，又面向来来信息化发展需求。在设计网络技术方案时，应遵循以下设计原则： 1 、实用性和先进性 采用先进成熟的技术满足当前的业务需求，兼顾其他相关的业务需求，尽可能采用先进 的i 网络技术以适应更高的数据、多媒体信息的传输需要，使整个系统在一段时期内保持技术 的先进，并具有良好的发展潜力，以适应未来业务的发展和技术升级的需要。 2 、安全可靠性 - 2 塑兰查兰堡主堂垡堡苎一 为保证将来的业务应用，网络必须具有高可靠性。要对网络结构、网络设备、服务器设 备等各个方面进行商可靠性的设计和建设。在采用硬件备份、冗余等可靠性技术的基础上， 采用相关的软件技术，提供较强的管理机制、控制手段、事故监控和网络安全保密等技术措 施，提高网络系统的安全可靠性。 3 、灵活性与可扩展性 网络系统是一个不断发展的系统，所以它必须具有良好的扩展性。能够根据将来信息化 的不断深入发展的需要，方便地扩展网络覆盖范围、扩大网络容量和提高网络各层次节点的 功能。具备支持多种通信媒体、多种物理接口的能力，提供技术升级、设备更新的灵活性。 4 、开放性，互连性 具备与多种协议计算机通信网络互连互通的特性，确保网络系统基础设旃的作用可以充 分发挥。在结构上真正实现开放，基于国际开放式标准，包括各种广域网、局域网、计算机 及数据库协议，坚持全国统一规范的原则，从而为未来的业务发展奠定基础。 5 、经济性艘资保护 以较高的性价比构建网络系统，使资金的产出投入比达到最大值。能以较低的成本、较 少的人员投入来维持系统运转，提供高效能与高效益。尽可能保留并延长已有系统的投资， 充分利用以往在资金与技术方面的投入。 6 、可管理性 在c d n 环境中，所有相关设备是分布在不同的地域的，所以对设备的远程管理便非常重 要。由于系统本身具有一定复杂性，随着业务的不断发展，网络管理的任务必定会日益繁重。 所以在网络的设计中，必须建立一个全面的网络管理解决方案。网络设备必须采用智能化、 可管理的设备，同时采用先进的网络管理软件，实现先进的分布式管理。最终能够实现监控、 监测整个网络的运行状况，合理分配网络资源、动态配置网络负载，可以迅速确定网络故障 等。 将来随着新的多媒体业务模型的增长，内容分发技术与c d n 将成为以高可靠性的、 可扩展的与安全的方式提供托管业务的关键，在保障网络的可访问性( 速度、安全、完整性) 方面发挥出更大的作用。 1 4c d n 的结构 从c d n 的功能上我们可以将其分成如下三个相互独立的模块： 内容路由：将客户端的请求路由到最合适的内容服务器上使网络性能达到最佳，包括如 3 d n s 重定向、名字路由、4 - 7 层的交换和w c c p 等技术。 内容分发：包括整个c d n 系统中的内容的编码、管理、安全和边缘分送。 性能测试：使用c d n 服务的用户必须将整个网络的性能进行反馈。包括内部的测量技 术和外部服务的数据衡量。 各个模块之间以及所提供的服务和网络组件之间的关系如图1 2 所示。 内容分发 内容路由 0 s s b s s d n s 重定向 缓存 4 7 层交换 索引 w c c p 安全性、加密 实时分割 实时分割 用户接口 发布流 网络组件 网络安全加密 实时分割 广播 q o s 互联性( b g p ip ) 性能测量 图l 一2c d n 各个功能模块的关系 另一方面，我们可以从网络的结构角度说明c d n 各个模块之间的关系，图1 - 3 所示。 f 面我们按各个功能模块分别进行介绍。 图1 - 3 c d n 的网络结构 4 1 4 1内容路由 内容路由技术的工作是将客户的请求传送到最合适的地点。在选择最合适的内容服务器 时，有很多度量标准可以影响这种决定。包括： 网络估计：这种信息一般通过网络的路由表获知，如边缘网关协议( b o r d e rg a t e w a y p r o t o c o l 。简称b g p ) 技术。 地理估计：用于将在一个指定的区域内的用户重定向到特定的边缘接入点( p o i n to f p r e s e n c e ，简称p o p ) 上。 响应时间：重定向设备上可以包含它到不同p o p 节点的延时信息，因此将请求重定向 到延时最少的用户接入点。 用户类型：例如收费用户的服务级别应该好于不收费的用户，用户的信息可以基于客户 端系统的一个c o o k i e 或者一个认证系统获知。 内容路由可分为广域路由和局部路由。广域路由主要是从全局的角度找到一个最合适的 用户接入点，并将客户的请求路由到该接入点。广域路由可以使用不同的技术，包括域名系 统( d o m a i nn a m es y s t e m ，简称d n s ) 重定向和名字路由。而局部路由是指在同一p o p 接入 点内的多个服务器中选择适当的服务器，并转发请求到相应的服务器。4 7 层内容交换和网 络缓存通信协议( w e b c a c h e c o m m u n i c a t i o n p r o t o c o l ，简称w c c p ) 技术都属于局部路由。 1 、d n s 重定向 d n s 重定向是最简单的内容路由技术。如图1 - 4 所示，每一个域名都有很多i p 记录与 之绑定。当一个客户发出该域名的请求时，d n s 服务器根据一定的衡量标准将请求重定向 到合适的服务接入点( p o p ) 。 图l _ 4 d n s 重定向 - 5 塑坚查兰堡主兰竺丝塞 虽然这种重定向技术比较简单，但对内容路由来说不是最佳的选择，它的主要问题包括： d n s 的查询时间是最重要的延时，因为即使服务的内容在附近可以获得，d n s 服 务还用付出全球i n t e r a c t 的代价。 d n s 重定向技术不是一种可扩展的解决方案，由于在内容路由中，唯一可用的信 息就是客户请求的内容。 2 、名字路由 由于d n s 重定向技术存在的缺陷，斯坦福大学和m i t 的研究者发明了一种叫名字路由 算法。斯坦福大学分布式系统工作组开发的结合活动目录的翻译传播结构( t r a n s l a t i n g r e l a y i n gi n t e m e ta r c h i t e c t u r ei n t e g r a t i n ga c t i v ed i r e c t o r i e s ，简称t r a i d ) 项目中包括了一个 基于名字的内容路由协议( i n t e r n e tn a m er e s o l u t i o np r o t o c o l ，简称d r p ) 和名字路由协议 ( n a m e b a s e dr o u t i n gp r o t o c o l ，简称n b r p ) 。名字路由根据请求所提供的分级名字进行路 由。每一个内容路由器都包含一个内容路由表，它存储下一跳路由器或服务器的名字。实际 上，基于名字的路由器是在普通i p 路由器，代理或网络地址翻译( n e t w o r ka d d r e s s t r a n s l a t i o n ，简称n a t ) 网关的基础上增加某些功能形成的。而相应的服务器也是增加了 w e b 服务器，缓存或代理的功能，它既可以相应客户的请求也可以通过内容路由器广告它 所服务的内容。由于广域路由不是本文的主要内容，我们不作详细的介绍。 3 、内容交换 内容交换包括4 7 交换( 以下我们对两者不作区分) ，是一种智能交换。它是基于客户 请求的统一资源定位器( u n i f o r mr e s o m c el o c a t o r ，简称u r l ) 、内容的类型、用户名等信 息进行交换。由于这些信息都可以从数据包的开放系统互联体系结构( o p e ns y s t e m s i n t e r c o n n e c t i o n ，简称o s l ) 的4 7 层中得到，所以称为4 7 层交换。 我们知道，标准的以太交换机在第2 层( 数据连路层) _ 作。他是根据媒体访问控制 ( m e d i aa c c e s sc o n t r o l ，简称m a c ) 地址或以太地址交换的。由于m a c 地址是一个以太 数据包所遇到的第一个地址类型，以此这种交换的延时很少。当目的m a c 地址一旦知道， 数据报马上将他交换到目标端口。 第3 层交换又叫i p 交换，它是由数据包上地i p 地址决定交换的端口。其功能相当于一 个路由器，但它处理数据报时必须逐个处理。第4 层交换具有智能性，它是基于t c p 端口 号进行交换的( 如端口8 0 为h t t p ) 。而第7 层交换则是根据数据包的第7 层信息进行交换。 本文研究的对象即为4 - 7 层交换，我们将在下一章作详细介绍。各种网络交换技术的总结如 图1 - 5 所示。 6 塑坚查兰堡主兰竺堡兰一 1 4 2 内容分发 0 s i7 层模型 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 图1 5 交换技术汇总 基于u r l 的h t t p 交换 未用于交换 未用于交换 基于端口号的t c p 交换 基于i p 地址的i p 交换 基于m a c 地址的以太交换 未用于交换 内容分发组件主要处理工作流和对内容的控制( 包括从编码到传递给终端用户等各个环 节) 。处理的内容可以是不同的格式，包括图片，数字或者语音和视频，软件，文档等等。 其中最特殊的内容就是实时内容，如语音和视频，或者某些股票数据。这种内容之所以特别 是因为他们不能够象文本和文档文件一样可以索引。为了解决这种问题系统必须可以智能地 辨别语音和视频内容并产生一个媒体内容的索引。图1 6 显示了内容分发的实现过程。 客户端 内容缓存 图1 6 内容分发的过程 - 1 塑垩查兰堕主堂堡堡兰一 1 4 3 性能测量 性能测量和网络管理组件提供c d n 端到端性能的监控、设计和计算。具体的测量数据 可以通过分布在整个c d n 系统基于软件和硬件的探针以及不同服务器的日志文件获得。测 量时必须包括所有类型的内容的传送( 包括流媒体和基于w e b 的内容) 。为了准确地测量网 络地性能我们必须对系统的内部和外部数据都要进行测量。典型的参数包括： 包丢失率：丢失的数据包和总的数据包的比值。 延时：客户从发送请求到收到应答之间的时间差。 平均带宽( 流媒体) ：流媒体总体占用的带宽和时间的比值。 帧率( 视频流) ：每秒钟视频的帧数。 测颦时，既可以从缓存和流媒体服务器的日志文件上得到相应的数据，从而获得c d n 的性能。例如，流媒体可以从媒体播放器上手机相关的数据，因此获得媒体服务器的性能。 也可以通过在不同的位置的缓存和服务器使用软件或硬件技术安放探针获得相关的信息，在 进一步计算分发和q o s 的统计数据。安放探针最合适的位置是网络的边缘。也可以通过使 ； j 第三方的工具获取有用的报告和曲线。 1 5 本文的研究内容 通过上面几个小节的介绍，我们对c d n 的概念以及其整体的结构组成有了一个全面的 了解。c d n 作为一种新兴的技术，各大设备提供商对其实现或架构均有自己的方法和观点。 而内容交换( 局部内容路由) 技术作为c d n 的关键技术成为能否提供更好的网络性能的重 要囡素。本文的主要贡献是对实现内容交换的不同分发算法和转发机制做了性能上的仿真， 并对这些算法和机制做了优缺点的评估，并在此基础上建立了通用的内容交换理论模型。 文章的内容结构具体安排为： 第章是绪论，综述性地介绍了c d n 的概念及其设计原则，并对c d n 的整体结构按 功能模块做了简要的介绍。 第二章介绍了作为本文研究对象的内容交换的结构，分类阐述了当前用于内容交换的各 种的分发算法和路由机制，并对这些算法和机制做了简单的分析比较。 第三章对典型的三种分发算法( w r r 、u r l h a s h i n g 、l a r d ) 作了性能上的仿真实现。 根据仿真的结果，分析了三种算法的性能优劣，并论述了服务器参数对三种算法的影响。 第四章对三种典型的转发机制( 包重写、t c p 切换、t c p 粘合) 作了性能上的仿真实 r 现。根据仿真结果，对三种机制做了性能上的分析。 第五章中，建立了内容交换的理论模型，并根据上两章的仿真结果，设定相应的模型参 数，对使用不同分发算法和转发机制的内容交换结构的性能作了理论计算。 第六章对前几章作了总结，并对整个内容交换的结构实现做了性能上的评价和建议，对 进一步的研究进行了展望。 1 6 本章总结 本章介绍了c d n 的概念和设计原则；分析了c d n 的整体结构，对c d n 的三个功能模 块( 内容路由、内容分发、性能测量) 做了简要的介绍；并描述了本文的研究内容和篇章结 构。 - 9 - 塑翌盔兰堡主兰垡兰塞一 第二章内容交换的转发机制和分发算法 2 1内容交换的结构 从上一章的简单介绍我们知道，整个c d n 系统从其功能上由内容路由、内容分发、性 能测量三个模块组成。其中内容路由包括两个部分，即全局内容路由和本地内容路由( 内容 交换) 。在本文中，我们所指的内容交换即为4 - 7 层交换。本文的研究对象是内容交换技术， 这一节将从介绍内容交换的具体结构开始。如图2 - 1 所示，我们在研究内容交换时，假设客 户的请求直接到达某个服务器接入点( p o p ) 的内容交换机，由交换机将客户的请求分发到 合适的内容缓存服务器上。内容交换的主要功能是实现内容服务器之间的负载均衡。提高内 容缓存的命中率，从而降低客户的访问延时。 图2 - l 内容交换的网络结构 在上面的结构中，内容缓存服务器使用服务器群技术。基于服务器群的网络系统，其内 部的多个内容服务节点对用户来说是透明的，用户只知道位于服务器群前端的设备的虚拟 l p 地址。也就是说，一个服务节点对全局路由系统来说只有一个i p 地址和一个与之对应的 域名。内容服务器的数量可以是几个到几十个，它们可以通过高速的局域网相连。每个内容 服务器都有一个特有的i p 地址。当个用户的请求到达某个内容交换机( 或者p o p ) 时， 苘先根据一定的分发算法选择适当的内容服务器，然后使用定的转发机制将该请求发送的 相应的服务器上。基于内容交换机不同的分发算法和转发机制的选择方法，可以将其分为第 4 层交换和第7 层交换： 第4 层交换：当客户要求建立一个t c p i p 连接，即当第一个t c p s y n 包到达时，交换 - lo i 塑垩奎堂堡主兰垡丝兰一 机马上根据数据报选择目标服务器。由于这种路由机制客户的数据包没有到达应用层， 所以交换机在选择目标服务器时并不知道客户请求的内容。 第7 层交换：这种交换技术首先与客户端建立一个完全的t c p 连接，然后在应用层检 杏请求数据包再选择目标服务器。由于它分析数据包的应用层，因此它知道客户请求的 内容。对t c p i p 模型来说，应用层为第5 层，所以也有些人将这种交换技术称为第5 层交换( 或者应用层交换) 。 我们将在下两节分别介绍当前使用的各种分发算法和转发机制。 2 2 内容交换的分发算法 从整个c d n 结构中我们可以知道，用户通过全局分发机制将用户的请求路由用户性能 相对较佳的服务点，然后由当地的交换机通过一定的转发机制和分发算法将客户的请求分发 到后端服务器，由后端服务器响应客户请求的内容。因此，分发算法将对用户性能和系统的 可展性产生直接的影响。 2 2 1 分发算法的分类 分发算法使用不同的分类准则有不同的分类方法。如我们可以根据交换机工作的层次分 为第4 层分发算法和第7 层分发算法，我们也可以根据交换机在作出分发决定时是否考虑状 态信息将它分为动态和静态算法，静态算法在作出分发决定时不考虑系统的当前状态，而动 态算法需要考虑系统的状态信息，潜在地实现静态算法，根据交换机在使用o s l 分层中信 息的层次将动态算法分为客户状态算法、服务器状态算法和客户j i l l 务器状态算法。客户状 态算法是使用客户端的某些信息路由请求，如第4 层交换机使用请求数据报中客户的l p 地 址和t c p 端口，而第7 层交换机则检查整个h t l 甲请求并基于客户的详细信息作出分发 决定：服务器状态算法则是交换机根据后端服务器的某些状态如当前和过去的负载条件、延 时时间和可用性以及服务器中缓存的内容信息分发请求：而客户月务器算法，交换机在路 由请求时既考虑客户的状态信息又考虑服务器的状态信息，实际上，大多数现存的知道客户 状态的策略都属于这一类，因为它们总是使用某些服务器负载的信息( 至少是服务器的可用 性) 。 由于交换机每秒钟要作出几百个甚至几千个分发的决定，那些复杂的分发算法很容易使 交换机成为系统的瓶颈，我们就不对它作讨论。另一方面考虑到算法的兼容性和可用性，我 塑坚盔堂堡主堂焦堡塞 一 们所考虑的算法的限制条件有以下三个： 低计算复杂性，因为分发决定需要实时作出。 与现存的网络标准和协议完全兼容。 交换机必须可以访问分发策略所用到的所有状态信息。尤其，服务器群的交换机和 服务器是收集和交换负载信息的实体。我们不考虑需要与不属于内容提供商的组件 动态合作的状态信息。 对上述分类我们可以用图2 2 来进行总结他们之间的关系。 第7 层分发算法 动态算法 一1 。一 客户状j客户服务j 态算法器状态算法j 图2 - 2 分发算法的基本分类 1 、第4 层分发算法 在第4 层分发算法中，静态算法不需要考虑任何系统状态信息。典型的例子是随机 ( r a n d o m ) 和轮询( r o u n d r o b i n ) 算法。随机算法将到达的请求等概率地分布到各个后端 服务器。轮询算法使用一个循环列表和一个指向最后选择的服务器指针来作分发决定，也就 是说，若s ，是最后选择的节点，则新的请求将被分配到s ，其中f + 1 = ( f + 1 ) m o d n ，n 为厉端服务器的数目。显然，轮询算法只利用了过去的分发决定的信息。 随机算法和轮询算法可以根据服务器的容量设置不同的分发概率进行扩展。用c 表示 服务器的容量，其相对容量定义为毒，= c ，m = ( c ) ，其中m a x ( c ) 是所有服务器中的最大 容鬻。服务器的容量是一个设置参数，因此是一个静态的信息。对随机算法来说，可以考虑 不同的容量设置不同的分发概率。轮询算法可以如下考虑：产生一个随机数p ( ose 1 ) ， 假设s ，是最后一个选择的服务器，只有当e 善时请求才分发到s l + l 服务器。否则，s l + 2 将 - 1 2 塑翌查兰堡主兰垡丝兰 一 成为下一个候选，并依此类推( 即产生另一个随机数与s + 2 的相对容量比较) a 不同的处理容量可以使用所谓的静态加权轮询( 简称静态w r r ) ，它是轮询算法的一个 一 变种。每个服务器设置一个权重嵋表示其容量。具体为，w ，= 。压i n ( c ) ，其中m i i l ( c ) 是所有服务器的最小容量。根据服务器的权重产生分发次序。例如，我们假设墨，s 2 ，邑 的权重分别是3 ，2 ，i ，则分发的次序是ss 。s 2 s 足s 2 。 对客户状态算法，由于系统信息的来源只限制于t c m p 数据包，例如，i p 源地址和端 口号等。因此只能用于将不同的i p 地址分发到不同的服务器上，实现所谓的客户分配算法。 对于服务器状态算法，由于可以获得服务器的状态信息，我们可以选择不同的服务器负 载指数，将请求分发到负载最小的服务器上。如最小连接算法就是使用连接数作为服务器的 负载指数。我们还可以对静态轮询算法进行扩展，形成动态加权轮询算法( 简称加权轮询算 法) ，它根据服务器当前的载荷状态动态地改变服务器的权重，交换机周期性地收集服务器 的负载指数信息并计算其权重，对每一个新的连接的分发这是一个动态地增量。 第4 层交换机可根据客户信息( 如源i p 地址和服务端口号) 的基础上结合某些服务器 状态信息提供所谓的客户绑定( c l i e n ta f f i n i t y ) 。它与不管过去的分发记录直接根据服务器的 状态信息分发每一个新的连接不同，来自同一个客户的连续连接可以不管其他的性能和功能 上的理由将他分发到同一服务器上。作为性能原因的一个例子，同一客户的连续的s s l ( s e c u r es o c k e t sl a y e r ) 连接在s s l 密钥存活期间分配到同一服务器上，可以避免s s l 密 钥的协商及其产生所用的时间和资源的花费。作为一个功能上原因的例子，f t p 协议在相同 的客户朋务器互操作使用两个连接。基于客户绑定的算法中，客户和服务器信息可以不同 的权重，一般来说，客户信息优先于服务器信息 第4 层分发算法的分类及其典型的算法如图2 3 所示。 图2 - 3 第4 层分发算法的分类 1 3 - 塑婆查堂堡主兰垡堕塞一 2 、第7 层分发算法 第7 层交换机可以检查整个h r r p ，获得请求的内容信息，再作分发决定。可以根据其 不同的目的将第7 层分发算法作进一步的分类： 为了提高服务器缓存的命中率减少硬盘的访问( 缓存绑定算法) ； 不同的后端服务器提供不同的服务如流媒体服务，动态服务等( 服务器分配算法) ： 为了增加后端服务器之间的负载共享( 负载共享算法) ； 考虑h t l 甲的某些负载信息，如c o o k i e s 和s s l 标识，以降低连接的初始化花费( 客户 绑定算法) 。 u r l h a s h i 】n g ( 简称h a s h ) 算法是一种典豸! ! 的缓存绑定算法，它使用一个h a s h 函数将 静态的文件分配到各个服务器上，在交换机上使用相同的h a s h 函数进行请求分发。这种算 法的目的是最大限度地提高缓存的命中率。但它只能用于静态文件，而且忽略了负载均衡。 因为在请求均衡的条件下分配文件空间是相当困难的。实际上，由于客户大部分的请求内容 是存在于服务器中的一小部分文件，所以要想在请求均衡的条件下分配文件空间是相当困难 的。若考虑到后端服务器可能各不相同，可以从请求的u r l 根据服务的类型静态地分布服 务器。这样可以使用某一具体的服务器服务特定的内容，如动态内容，多媒体文件，流媒体 等，这种策略称为服务分配算法。 第7 层分发算法的第三个目的是提高各个服务器之间的负载共享。这些策略不需要根据 文什空间和服务对后端服务器进行静态分配。有两种算法属于这一类：相同载荷尺寸间隔任 务分配( s i z e i n t e r v a l t a s k a s s i g n m e n t w i t h e q u a l l o a d ，简称s i t a - e ) 和c a p ( c l i e n t - a w a r e p o l i c y ) 。前者更倾向于提供静态内容的服务，而后者提供不同资源影响的服务。s i t a - e 算 法根据文件尺寸动态地分配内容。它根据每一个服务定义文件的尺寸范围使每一个服务器的 总体载荷相同。交换机根据请求的文件的尺寸选择服务器。这样做的目的是将轻载荷的请求 分发到处理轻载荷的服务器上。s i t a e 算法是基于服务时间和文件的尺寸成正比的假设， 而这种假设只对静态内容有效。大多数的负载共享问题都是由于后端服务器的多样性产生 的。在前面提到的算法并没有考虑这一问题，它们要么基了二静态内容要么考虑静态服务分配 的多服务。为了实现提供多服务的负载共享，c a p 策略考虑了请求的多种服务。请求可以 根据他们对服务器的资源的影响进行分类，例如，静态，轻动态，强动态。虽然交换机无法 准确地估计客户请求的服务时间但它可以根据请求的u r l 对它进行分类并估计出它对服 赘器的影响。c a p 与大多数动态策略一样不需要任何参数，由于它的服务级别已经预先决 定，在作出分发决定时只考虑请求的u r l 对它进行分类。 1 4 浙江大学硕士学位论文 最后一个客户状态算法的类型是会话标识，如c o o k i e s 和s s l 标识。基于这种信息交换 机将来自同一客户的请求分发到同一服务器上。会话标识在单个客户粒度上提供了维持客户 绑定强有力的手段。尤其，它避免了第4 层交换机客户i p 地址的限制，客户路径上的代理 可以将火量的用户压缩成少量的不同的l p 地址。 在应用层实现分发算法可以使用客户和服务器的状态信息。l a r d ( l o c a l 时a w a r e r e q u e s td i s t r i b u t i o n ) 算法是一个既考虑本地性又考虑负载均衡的面向内容的分发算法。 l a r d 算法的基本原则是将同一目标的所有的请求分发到相同的服务器上，只要它的利用率 低丁给定的阀值。这样做的目的是使得客户请求的内容尽可能在服务器的缓存中找到。为了 避免服务器的过载，对服务器利用率的检查是必要的。当一个服务器的利用率达到了某一给 定的门限值，交换机将请求分发到载荷较低的服务器，若存在的话，到载荷最小的服务器。 在l a r d 算法中，交换机维持了一个给定文件到服务这些文件的服务器之间的映射。而缓 存管理器根据服务器中的缓存内容分发请求。每一个后端服务器周期地提供给交换机缓存信 息。若客户所请求的内容不在任何服务器中，则选择载荷最低的服务器。否则，选择当前载 荷摄轻的含有该目标缓存的服务器，假设它的载荷在一个给定的阀值范围之内。与l a r d 算法相似，h a c c ( h a r v a r da r m yo f c l u s t e r e dc o m p u t e r s ) 算法也实现了这种功能。 图2 - 4 总结了第7 层分发算法的分类及其典型的算法。 2 2 2 分发算法的分析 图2 - 4 第7 层分发算法的分类 对一个第4 层的交换机，静态算法由于不需要考虑系统的状态信息，是一种最快的分发 方案，而且它易于实现，但这些算法可能会由于不同的服务时间和资源消耗导致负载不均衡 1 孓 塑翌查堂堡主兰焦堕苎一 从而影响其性能。动态算法使用不同的状态信息潜在地实现了静态算法，但需要一个收集和 分析状态信息的机制，因此会产生额外的花费。而且，由于后端服务器的多样性，设置一个 合适的参数也不是一个容易的事。服务器状态算法看起来是最好的选择，虽然不是所有的算 法r 作起来性能都很佳。例如，最小负载算法可能由于在新的信息传播之前将所有的请求分 发剑同一服务器导致服务器饱和，这种影响在分布式系统中非常常见，但还是有许多商业产 品采用最小负载算法。其中，w r r 算法在简单性和有效性上的折中达到最佳。 第7 层分发算法中，当考虑请求内容对服务器的影响时，基于客户的信息可以提供更 高性能，如c a p 算法。静态的分配算法可能产生某些服务器容量的饱和而其他服务器轻载。 但纯粹的客户状态算法和客户，服务器状态算法相比有一个明显的好处就是它不需要昂贵的 花费去监视与估计各个服务器载荷。而实际上，所有的客户状态算法几乎都要考虑一个服务 器的状态即服务器的可用性。提高缓存命中率的分发算法，如l a r d ，为网站提供静态信息 和某些简单数据库信息上性能较好。当我们考虑高多样服务器时，只有那些负载共享的算法 ( 如c a p ) 可以提供满意的性能。 第7 层分发算法可以潜在地实现第4 层分发算法，当他们作分发决定时使用了些更详 细的客户信息。例如，对静态内容，l a r d 算法的性能要优于w r r 算法。但另一方面，第 7 层的操作在花费上更昂贵，因此客户状态算法必须限制对客户状态信息的分析以免使得交 换机成为系统的瓶颈。例如，一个c o o k i e 可能含有4 0 9 6 个字符而且这些信息将在占用许多 t c p 分段。假如交换机在作相应的分发决定之前必须分析每一个c o o k i e ，那么客户的延时将 增加而且服务器很容易成为系统的瓶颈。对一些新的面向内容的算法，考虑其服务的多样性 a 不将所有的焦点集中在提高命中率上是十分重要的。随着传统网站和电子商务以及需要动 态和安全的基于网络的信息系统大的集成，网站所提高的服务和应用的复杂性也随之增加。 2 2 3 服务器的状态信息 客户的状态信息可以从其发送的数据报中获得，而服务器的状态信息则没有这么简单。 j 我们考虑基于某些服务器状态信息的分发算法时将面对不同的问题：首先，必须选择一个 或多个服务器的载荷指数；接着，计算载荷的状态信息和抽样频率；最后，由于服务器群的 结构，某些指数可能不能马上被交换机使用，因此必须考虑如何传输他们，且传输的频率是