（计算机应用技术专业论文）cdn网络中基于服务质量的分布式路由研究.pdf

中北大学学位论文 c d n 网络中基于服务质量的分布式路由研究 摘要 互联网的出现给人们的工作和生活带来了极大的便利，近年来随着互联网的快速发 展，网络的应用趋于多样化。各种业务，特别是流媒体( 如音乐，视频等) 纷纷应用于 网络，使得网络的访问瓶颈日益突出，访问延迟加大。为了提高用户访问网站的响应速 度、优化现有互联网中信息的流动、提高网站的安全性和可用性，于是c d n ( c o n t e n t d e l i v e r yn e t w o r k ) 应运而生，短短的几年里，c d n 已经取得了巨大的成功，在一定的 程度上很好的缓解了主干网络及主站点的压力，加快了用户的访问速度，提高了服务质 量，降低了访问延迟。 c d n 的技术原理是在现有的互联网络中建立一个完善的中间层，将网站的内容发布 到最接近用户的网络“边缘 ，使用户能以最快的速度、从距离用户最近的地方获得所 需的信息。内容分送网络主要涉及的关键技术包括内容管理、内容路由、内容存储和内 容分发同步。 目前，对c d n 几大技术的研究非常多，内容路由是研究的一个热点，但是更多的 研究重点均放在了如何通过用户重定向技术来提高用户的访问质量和实现负载均衡方 面，而很少来研究如何通过放置内容副本来提高网络的服务质量，至于将内容复制与用 户重定向相结合来提高服务质量的研究更是少之又少，本文正是以这两者相结合的思路 为出发点，提出了基于内容类别的内容动态复制及分布式内容路由相结合来提高用户的 访问质量，实现全局及局部负载均衡的策略。仿真结果表明本策略能有效降低用户访问 延迟，提高了c d n 网络的服务质量。 关键字：内容分发网络，服务质量，动态复制，内容路由 中北大学学位论文 s t u d yo nt h ed i s t r i b u t e dq o sr o u t i n g o fc o n t e n t d i s t r i b u t i o nn e t w o r f uh e i f e i y a n gq i u x i a n g a b s t r a c t i nr e c e n ty e a r s ，w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e r n e tt e c h n o l o g y , m o r ea n dm o r e m u l t i m e d i aa p p l i c a t i o n ss u c ha sd i g i t a lv i d e oa n da u d i oa r ea p p l i e do ni n t c r n e t ，i na d d i t i o n ， t h eq u a l i t yo fs e r v i c ea r cn e e d e dm u c hh i g h e rt h a nb e f o r e i no r d e rt op r o v i d eh i g hq u a l i t yo f s e r v i c eo nt h en e t w o r kt os a t i s f ya l lt h er e q u i r e m e n t s ，c d n ( c o n t e n td e l i v e r yn e t w o r k ) h a s b e e np r o p o s e di nr e c e n ty e a r s ，w h i c hi sa ni n t e r m e d i a t el a y e ro fi n f r a s t r u c t u r e r e p l i c a t i n g t h i r d - p a r t yc o n t e n to ns e r v e r sc l o s e rt ot h ef i n a lu s e r sa n dr e d i r e c t i n gt r a n s p a r e n t l yt h e i r r e q u e s t st ot h e “b e s tr e p l i c a ”，c d np r o v i d e r sa r ea b l et oo f f e ri m p r o v e dc o n t e n ta c c e s s s e r v i c e t h ek e yt e c h n o l o g i e so fc o n t e n td e l i v e r yn e t w o r ki n c l u d ec o n t e n tm a n a g e m e n t ，c o n t e n t s t o r a g e ，c o n t e n td e l i v e r ya n dc o n t e n tr o u t i n g e x i s t i n gw o r ko nc d n h a sp r i m a r i l yf o c u s e d o nt e c h n i q u e sf o re f f i c i e n t l yr e d i r e c t i n gu s e rr e q u e s tt oa p p r o p r i a t ec d ns e r v e r st or e d u c e l a t e n c ya n db a l a n c el o a d h o w e v e r , l i t t l ea t t e n t i o nh a sb e e ng i v e nt ot h ed e v e l o p m e n to f p l a c e m e n ts t r a t e g i e s f o rc o n t e n tr e p l i c a st of u r t h e ri m p r o v ec d np e r f o r m a n c e p l a c e m e n t s t r a t e g i e sa r ei m p o r t a n tb e c a u s ea p p r o p r i a t ep l a c e m e n to fc o n t e n tr e p l i c a sb e n e f i t sc o n t e n t p r o v i d e r sb yr e d u c i n gl a t e n c yf o rt h e i rc l i e n t s ，a n db e n e f i t si s p sb yr e d u c i n gb a n d w i d t h c o n s u m p t i o n i nt h i sp a p e r , w ec o n c e r nt h ej o i n to p t i m i z a t i o no fr e p l i c ap l a c e m e n ta n dd i s t r i b u t e du s e r r e q u e s tr e d i r e c t i o n i no u rm o d e l ，d i f f e r e n tc o n t e n th a sd i f f e r e n tl a t e n c yb o u n dr e q u i r e m e n t s o u rs o l u t i o ni sd y n a m i ci nt h es e n s et h a tr e p l i c a sa r ea d d e da n dr e m o v e df r o mc d ns e r v e r s a c c o r d i n gt ot h ed y n a m i c a l l yc h a n g i n gu s e rr e q u e s tt r a f f i c t h er e s u l t ss h o wt h a tt h ep r o p o s e d s o l u t i o ni sc a p a b l eo f d e c r e a s ea c c e s sd e l a ya n di m p r o v et h eq u a l i t yo fs e r v i c e k e yw o r d s ：c d n ，q u a l i t yo fs e r v i c e ，d y n a m i cr e p l i c a ，c o n t e n tr o u t i n g 中北大学学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：b i l l ：2 丝：兰兰 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论文的规定，其中包括： 学校有权保管、并向有关部门送交学位论文的原件与复印件；学校可 以采用影印、缩印或其它复制手段复制并保存学位论文；学校可允许学 位论文被查阅或借阅；学校可以学术交流为目的，复制赠送和交换学位 论文；学校可以公布学位论文的全部或部分内容( 保密学位论文在解密 后遵守此规定) 。 日期：加夕 导师签名：豳塑熟 日期：堡塑：羔：兰2 中北大学学位论文 1 1c d n 简介 1 绪论 c d n 的全称是c o n t e n td e l i v e r y d i s t r i b u t i o nn e t w o r k ，即内容分发网络，其目的是 通过在现有的i n t e r n e t 中增加一层新的网络架构，将网站的内容发布到最接近用户的网 络“边缘”，解决了网络“最后一公里 的问题，使用户可以就近取得所需的内容，提高 用户访问网站的响应速度。c d n 有别于镜像，因为它比镜像更智能，或者可以做这样 一个比喻：c d n = 更智能的镜像+ 缓存+ 流量导流。因而，c d n 可以明显提高i n t e m e t 网 络中信息流动的效率，从技术上全面解决由于网络带宽小、用户访问量大、网点分布不 均等问题，提高用户访问网站的响应速度【1 1 。据统计，采用c d n 技术能处理整个网站 页面的7 0 - 9 5 的内容访问量，减轻了服务器的压力，提升了网站的性能和可扩展性 【2 1 。 1 1 1 c d n 的出现 互联网的出现给人们的日常生活和工作带来了极大的便利，但随着互联网用户的迅 速增长和用户对提高互联网服务质量需求的不断增加以及网络应用的多样化，传统的由 i c p 和电子商务网站提供信息服务的模式正面临着严重的挑战。i c p 和电子商务应用站 点一般是在一个或少数几个地方建立物理站点，面向全国乃至全球互联网用户提供信息 服务和电子商务服务。互联网的自身结构特点和网络带宽瓶颈问题使得人们访问全球站 点时延迟长，效率低。 近年来尽管随着技术的突飞猛进，互联网的传输带宽也越来越宽，用于存储内容信 息的服务器性能和容量也越来越高，但在我们的日常网络访问中依然感觉到网络的速度 不尽人意，获得的信息不够准确、不够快。据中国互联网络信息中心2 0 0 7 年7 月发布 的第2 0 次中国互联网络发展状况统计报告，目前网民对网络速度的满意度仅为4 7 1 i 引。 造成网络访问速度慢的原因很多，如网络带宽瓶颈、传输途中的路由阻塞和延迟以 及作为信息存储媒体的服务器性能( 存储容量、存取速度) 的提高速度赶不上众多用户提 1 中北大学学位论文 取信息的需求。人们发现传统的网页访问方式在应对大规模的访问时显得力不从心，无 论是对服务器还是带宽的压力都将导致网站无法为巨量访问用户提供高品质的系列应 用服务。 c d n ( 内容分发网络内容传送网络) 正是在改善互联网性能的呼声中应运而生的。有 别于传统互联网性能改善方案( 如增加接入带宽，升级硬件和建立多个镜像站点) ，c d n 提出“让内容离用户更近 的全新思路。 1 1 2 c d n 系统设计思想 目前，几乎所有的i n t e r n e t 的应用服务访问都是基于域名解析服务来进行的。让我 们来看一下传统的i n t e r n e t 网络的基本结构1 4 ，如图1 - 1 所示。 。；i c l 授权d n s 服务器 ， i c p lw e b 服务器 图1 - 1i n t e r a c t 网络基本结构及数据传输方式 我们来分析一下传统的i n t e r n e t 网络的基本结构和数据传输情况，根据图1 - 1 的网络 结构，用户的访问流程如下： 1 在用户浏览器中输入将要访问的网站的域名； 2 浏览器将域名的解析请求发送给本地d n s ： 2 中北大学学位论文 3 本地d n s 将请求发给网站授权的d n s ( a u t h o r i t a t i v ed n ss e r v e r ) ； 4 授权d n s 把服务器地址作为解析结果( i p 地址) 返回到本地d n s ： 5 本地d n s 把解析结果返还给用户，同时将该域名的解析结果缓存起来，作为下 一个用户解析请求的直接响应。直到相应的删生存周期) 过期，才再向网站 的授权d n s 发送解析请求； 6 用户得到i p 地址后，就可以直接对网站的服务器进行访问。 传统的网站访问模式虽然简单，但存在的几个问题会严重影响i n t e m e t 用户的访问 效率和质量。 首先，传统的d n s 解析，在将主机名转换为i p 地址时，并不会预先判断网络的状 态，它可能将服务请求发送到服务能力饱和或者己经停机的服务器，不能有效的均衡网 络资源。 其次，就是访问效率低下，用户获得响应的时间过长。传统模式下用户对一个网站 内容的访问往往要经过多个路由器，最终才能到达网站的服务器，中间还有可能要跨过 多个i s p 和网络。即使在理想情况下，路由器的每一次转接( h o p ) ，都会造成一个延迟， 虽然单个这样的延迟时间较少，但当网络规模很大时，h o p 数会大量增加，造成的延迟 也会更加明显。而且，当任何一个路由器的故障或者拥塞都可能造成访问的中断或者延 迟的增加，严重影响访问的质量。 c d n 正是针对传统的网站访问模式存在的固有缺陷，采用智能动态负载均衡系统和 内容分布存储系统，在现有的i n t e r n e t 网络中，为众多的网站用户提供加速服务，同时 大大降低了i s p 广域网的出口带宽。 1 1 3 c d n 工作流程 当前比较成熟的是采用基于d n s 的内容路由的内容分送网络，下面我们就以此来 说明c d n 系统网络架构。 当用户访问己经加入了c d n 服务的网站时，其解析过程与传统网站访问解析过程 最大区别在于d n s 重定向服务器不是以传统的轮询( r o u n dr o b i n ) 方式来响应本地d n s 的解析请求，而是充分考虑请求用户的地理位置和当时网络的负载情况，由此决定把请 求用户重定向到最佳的服务节点上。通过d n s 重定向服务器的动念负载均衡技术，可 3 中北大学学位论文 以将请求用户重定向到最佳c d n 内容服务器上；c d n 内容服务器的高性能则进一步保 证了访问用户可以获得更及时可靠的响应；而c d n 内容分发和管理机制保障了各个 c d n 内容服务器与i c p 的源服务器的数据同步，用户访问c d n 内容服务器将得到与原 服务器完全相同的内容。 图1 2 给出了用户访问加入c d n 服务的网站的完整过程【4 1 。 i c p i1 | | f e b 服务器 节点 务器 图1 2 加入c d n 网络后i n t e r a c t 结构图和数据传输方式 用户访问加入c d n 服务的网站的流程： 1 用户在浏览器中输入将要访问网站的域名，浏览器将域名的解析请求发送到本 地d n s ； 2 本地d n s 将收到的解析请求发送给i c p 的授权域名服务器( a u t h o r i t a t i v e d n s ) ，授权域名服务器查询数据库，将c d n 重定向服务器地址返还给本地 d n s ： 3 本地d n s 重新将域名解析请求发送给c d n 重定向服务器； 4 c d n 重定向服务器根据采用的负载均衡技术，选择最佳c d n 内容服务器节点， 4 中北大学学位论文 并将结果( i p 地址) 返还给本地d n s ； 5 本地d n s 将收到的c d n 内容服务器节点的l p 地址发送给请求用户； 6 请求用户将服务请求发送到收到的c d n 内容服务器节点； 7 c d n 内容服务器节点响应请求用户，提供请求服务内容。 上面描述的是第一个用户，在第一次访问一个网站，并且所访问的本地域名服务器 在没有解析过该域名的情况下的访问流程。 从上面可以看到，它需要七步才能够完成对用户的一次响应，看似比较繁琐。但是 在该过程中，本地域名服务器会对解析过的域名进行缓存，并且c d n 内容服务节点会 对用户访问过的内容进行缓存，后续请求用户的访问就可以用缓存的域名直接发送请 求。图1 3 是c h i n a c a c h e 的核心d n s 重定向方式下的访问示意图。 i s p 提供 l o c a id 图1 3 采用全局访问控制系统后c h i n a c a c h e 的访问示意图 1 1 4 c d n 的益处 我们从1 1 2 和1 1 3 的论述中不难得出以下结论：无论是i s p 、i c p 或者是最终用 户，都能享受到c d n 服务带来的益处【5 1 。 1 给i s p 带来的益处： 5 中北大学学位论文 对于i s p ，由于用户请求被自动定向到了离用户“最近”的c d n 节点，减少了由 于距离和路由器转接造成的延迟，提高用户访问时的响应速度。由于用户的访问不用通 过不同网络服务商( c a r r i e r i s p ) 之间来回移动( 通常是网络中的瓶颈) ，所以对于网络服务 商i s p 能够节省大量的广域网的出口带宽，这样，在有限的带宽情况下，既可以提高对 用户的响应速度，同时也能为更多的用户提供更多的服务，提高带宽利用率，节省i s p 资源，优化网络，减少拥塞，消除不同i s p 之间网间互联拥堵的弊病，提高用户访问的 响应速度，提高i s p 的服务质量。 2 给网站带来的益处： 对于网站，在使用了c d n 服务后，用户对网站的访问将直接由分布在全国各地的 c d n 服务节点直接响应，网站的源服务器的负载会迅速降低，从而减轻网站为应付访 问量的不断增加所需的人力、物力投资的压力。同时，c d n 服务中的智能动态负载均 衡技术，可以将用户的访问自动定向到c d n 网络中的不同节点，消除了单点故障对用 户访问造成的影响，提高了网站的可用性和服务质量。将网站的内容发布到更接近用户 的地方，明显提高网站服务质量，减轻源网站服务器的负荷，解决服务器端的“第一公 里 问题，降低网站的扩容压力，减小投资风险，降低“通信风暴 的影响，自由选择 分布在各处的c d n 服务节点，多种内容同步手段，确保c d n 上内容与源服务器的及时 同步，对外隐藏源服务器，代替网站抵御各种非法访问和攻击，提高网站的安全性。 3 给最终用户带来的益处： 对于最终用户，访问加入c d n 服务的网站后，可以直接从离自己只有“一步之遥 的c d n 节点取得访问的内容，解决了难以容忍的延迟等待。 1 1 5 c d n 的发展与应用现状 c d n 在国外已经得到了广泛的应用，如著名c d n 提供商a k a m a i 己经在全球部署 了2 万多台服务器，覆盖7 1 个国家1 6 j 。国内主要的c d n 运营商c h i n a c a c h e 公司已经 在全国部署了5 0 0 多个c d n 服务节点，遍布中国1 0 0 多个主要城市，覆盖中国电信、 中国网通、中国移动、中国联通、中国铁通和中国教育科研网等各大运营商，总的网络 处理能力已达3 5 0 g 1 7 1 。 目前部署的c d n 系统一般都采用了基于d n s 的内容路由技术作为实现全局负载均 6 中北大学学位论文 衡的手段，采用4 7 层交换技术实现c d n 服务节点内部服务器群本地负载均衡。随着 c d n 规模的不断扩大，请求用户的不断增多，我们需要采用更为先进的全局负载均衡 技术。 同时，随着c d n 技术的不断发展，c d n 所支持的内容类型也日趋广泛，由初期的 静态网页到动态网页，再到各种音频、视频流媒体，到目前为止，c d n 不仅能够提供 以网络加速为基础的系列服务，包括针对静态网页，动态网页，流媒体，文件下载，f l v 文件播放等内容提供加速，还能提供一些相关的增值服务以更有效地满足客户在这些应 用方面的需求。 1 2 c d n 路由 1 2 1 c d n 路由的概念 c d n 路由又称为“内容路由或“内容重定向 ，是指根据各种策略及一组度量 标准将请求导向代理节点，主要包括d n s 路由技术、传输层路由技术和应用层路由技 术【引。无论是哪种路由技术，c d n 内容路由均是建立在现有的i p 网络基础之上的，支 撑点依然是现有的i p 路由机制【9 1 。图表1 4 明了c d n 路由、i p 路由和用户请求的层次 关系。我们把c d n 路由所处的层次形象地称为“内容层 。内容层充分利用现有的m 核心路由网络，通过特定的内容路由策略，为用户的内容请求选择最佳的内容服务器， 完成内容的重定向。 i 用户的内容请求 l c d n 内容路由 i 1 p 心路由 图1 - 4 c d n 网络的内容路由层次 7 中北大学学位论文 目前针对c d n 内容路由的研究主要包括：基于d n s 的内容路由、基于名字的内容 路由和局部内容路由。 1 2 2 基于d n s 的内容路由 目前的c d n 网络主要采用的是基于d n s 的内容路由，从图1 3 中我们可以看到采用 这种路由的网络架构，主要包括g a c ( g l o a b l ea c c e s sc o n t r o l l e r ) 智能访问控制系统和 c c n ( c h i n a c a c h en o d ) c h i n a c a c h e 节点群，其中g a c 是其内容路由的核心系统。 g a c 是c h i n a c a c h ec d n 中的关键子系统，负责对所有使用服务用户的域名进行 解析，以决定最终用户的实际访问地址。g a c 除了具备普通d n s 解析功能以外，还具 有全球动态智能解析功能。在收到用户的访问解析请求后，会首先对各个节点按照设定 的策略进行检查，然后根据检查的情况把当时一个最合适的节点地址返回给用户，从而 实现动态智能解析功能，使用户能从最优的节点得到响应。 基于d n s 重定向的内容路由充分利用了现有的网络结构，结构简单，易于实现，因 而被人们认为是一种有效的技术，是现阶段c d n 应用中主要采用的内容路由技术。但是， 它的缺陷也是显而易见的： 重定向过程包括了访问远端根d n s 服务器和c d n 重定向服务器的过程，需要花较长 时间去定位离用户实际很近的c d n 内容服务器。d n s 重定向路由延时成为c d n 性能提高 的瓶颈之一。 采用基于d n s 重定向机制，内容路由只能在访问站点名的尺度上进行路由，而不能 在具体内容的u r l 的尺度上进行路由，一个大站点的内容不能被分开存储于不同c d n 内 容服务器。 当c d n 内容服务器数量较大时，d n s 重定向服务器在获取c d n i 为容服务器的状态参 数和测试网络性能过程中，重定向服务器的处理和通讯能力成为限制c d n 网络性能提高 的瓶颈之一。 由于d n s 路由过程中固有的i p 缓存机制，导致内容路由在很多时候控制力受到很多 限制。另外，由于采用中心服务器方式，如果通往重定向服务器链路严重拥塞或者重定 向服务器故障，c d n 系统瘫痪。 文献 1 0 1 提出了一种基于策略的路由请求系统p b r 2 s ，此系统也是基于d n s 路由机 8 中北大学学位论文 制的，但是它能够根据网络的当前状态，动态地更新d n s 名字服务器，可以较为安全地 处理突发数据。算法是基于内容完全分发至各个c d n j 艮务节点的，它假设用户网络由多 个自治系统组成，p b r 2 s 预先以一个或者几个相近的自治系统为单位，在其内部部署一 组边缘服务器和分布d n s 服务器，它们负责本自治系统内部的内容服务。系统包括一系 列标准化协议，如：传输层安全t l s ( tr a n s p o r tl a y e rs e c u r i t y ) 毛e p b r 2 s 中它被用作策略 实施点与策略决策点进行( c o p s ( c o m m o no p e np o l i c ys e r v i c e ) 协议通信的承载协议，为 其提供安全可靠的信道。另外，系统还使用简单网络管理协议( s n mp1 在边缘服务器和 策略决策点之间进行信息交互策略信息库与策略决策点按照标准通过l d a p ( l i a h t w e i a h td i r e c t o r ya c c e s spr o t o c 0 1 ) 协议进行读写操作。 1 2 3 基于名字的内容路由 由于d n s 重定向技术存在的缺陷，斯坦福大学和m r r 的研究者提出了一种叫做“名 字路由 的路由方案。它不同于传统的基于i p 地址的路由思想，而是基于用户请求的 内容的名字( 通常是一u r l ) 进行路由。下面就斯坦福大学提出的名字路由方案【1 1 l 作简单 介绍。 名字路由技术： 斯坦福大学提出了基于名字的路由( n a m eb a s e dr o u t i n g ) 思想。它不同于传统的基于 i p 地址的路由思想，而是基于用户需求的内容的名字( 通常是一个u r l ) 进行路由。基于 名字的路由技术引起了人们的广泛注意，人们开始对它展开进一步的研究。无论在国内 和国外，它都是一项崭新的技术。名字路由的思想按照斯坦福的描述，在下一代网络里， 用户想要连接的不是一个特定的服务器或者一个i p 地址，而是以名字( 如u r l ) 标识的 内容。基于名字路由的体系主要由内容服务器( c o n t e n ts e r v e r , c s ) 和内容路由器( c o n t e n t r o u t e r , c r ) 构成。图1 5 代表了未来的名字路由结构。 c s c o n t e n ts e r v e r ，内容服务器 c r c o n t e n tr o u t e r ，内容路由器 9 中北大学学位论文 图1 - 5 名字路由结构图 n a m e n e x t h o p p a t hs e r v e r c l l n c o m 1 2 3 4 l o m s5 m s c n n c o m5 6 7 86 5 m s1 0 m s n a m e 一般代表c s 的域名。n e x th o p 表示的是下一个对等体c r ( 包括c s ) 的口地 址。p a t h 和s e r v e r 两项集中代表了从当前c r 到达目的内容的时间耗费，到达内容的时 间耗费= 到达c s 的时间耗费+ c s 查询内容的时间耗费；其中p a t h 项代表了到达c s 的 时间耗费，s e r v e r 项表示了c s 查询内容的时间耗费。c r 根据最长后缀匹配原则，筛选 出与用户请求的内容名一致的路由项，然后根据最小的时间耗费( p a t h + s e r v e r ) 选择下一 个对等体c r ( 或者c s ) c r 的功能包括：参加名字路由体系的动态路由表更新过程，负责为用户的内容请 求选择最佳的c s ，或者将内容请求前递到邻近的c r 。从这个意义上说，c r 相当于分 布式d n s 服务器。 c s 的功能包括：提供内容分发功能，响应通过c r 最终路由到c s 的用户请求；通 。过c r 通告c s 的内容信息。 支撑名字路由体系的两个核心协议： i n r p ( 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 0 1 ) ：i n r p 与d n s 协议兼容，i n r p 的报 文格式与d n s 报文格式一致。i n r p 的作用如下； 根据用户的请求的内容名( u r l ) 进行路由表的最长后缀匹配搜索，并通过一定算 法将用户的内容请求从匹配结果中选择最佳的下一跳c r 或者c s 。在响应超时等出错 情况下，重定向用户内容请求到新的c r 或c s ，建立c r 和用户、c r 和c r ( c s ) 的连 接。 1 0 中北大学学位论文 n b r p ( n a m e b a s e dr o u t i n gp r o t o c 0 1 ) ：n b r p 在c d n 名字路由中的作用相当于 b g p 在i p 路由中的作用。与b g p 一样，n b r p 的着眼点是选择最好的路由并控制路由 的传播。它们的差别就是b g p 是基于i p 的，而n b r p 是基于名字( u r l ) 的。n b r p 的 作用如下： 传播和更新节点可达路由信息，包括c r 和c s 的添加和删除等路由信息。当网络 拓扑和网络状态发生改变时，维护和更新内容路由表。 用户访问举例： 我们用一个用户访问案例来阐述名字路由的工作原理和流程。案例分成三个部分： c s 路由通告：存在一c d n 节点c s ，域名“w w w n u c e d u c n ”。c s 向邻近c r 通告 可达信息。c r 又向邻近c r 通告该c s 的可达信息。 内容请求的路由：一用户输入u r l ：h t t p ：w w w n u c c d u c i l 时，该内容请求到达用 户配置的c r ，c r 通过路由表查询将该u r l 路由到离用户最近的节点c s ( w w w n u c e d u c n ) ，c s 响应内容请求，响应沿c r 原路返回。图1 7 中c r 与c r 之 间的虚线连接表示内容请求可能通过多个c r 到达目的c s 。 h t t p ：w w w n u c e d u c n w w w i l u g e d u c n 图1 7 名字路由访问示意图 内容获取：用户根据返回的c s 的i p 地址，向目的c s 发起h 1 r p 等内容请求获取 内容。这一部分与基于d n s 路由时用户获取内容过程一样，充分利用了现有口资源。 基于名字的内容路由技术采用了分布式体系结构，在应用层c d n 节点之间借鉴i p 路由的思想。内容路由的过程主要是在局部邻近客户的路由器中进行，大大减小了路由 时间。基于名字的路由无论在国内还是国外都是一项崭新的技术，还存在很多有待论证 和研究的方面： 由于是基于内容名字u r l 的路由，路由器需要在路由过程中打开t c p 包获取内容 u r l 和其他参数信息。复杂的数据包分析将增加路由开销和延时。 11 中北大学学位论文 基于u r l 的路由表和路由协议还没有成熟方案。h u b ，c h r i s t m a s t r e e 和i c a p 等 路由协议都只有一个雏形。名字路由需要对已有网络做较大改动。 文献【9 】和【1 2 】对名字路由进行了详述。 1 2 4 局部内容路由 局部内容路由1 5 j ，有时我们也称它为本地内容路由。局部内容路由是当c d n 节点 内存在多个内容服务器时，由前端交换机将路由到该c d n 内容服务节点的客户请求通 过一定策略分发到节点内某个内容服务器的过程。 局部内容路由即为4 _ 7 层交换。如图1 8 所示，在研究局部内容路由时，假设客户 的请求直接到达某个服务器接入点( p o p ) 的前端交换机，由交换机将客户的请求分发到合 适的内容服务器上。局部内容路由的主要功能是实现c d n 内容服务节点内服务器之间 的负载均衡、提高内容缓存的命中率，从而提高客户访问的服务质量。 客户端 图1 8 局部内容路由图 在图1 8 的结构中，c d n 内容服务节点内使用服务器群技术。基于服务器群的网络 系统，其内部的多个内容服务节点对用户来说是透明的，用户只知道位于服务器群前端 的设备( 前端交换机) 的虚拟i p 地址。也就是说，一个服务节点对全局路由系统来说只有 一个i p 地址和一个与之对应的域名。内容服务器的数量可以是几个到几十个，它们可 以通过高速的局域网相连。每个内容服务器都有一个特有的i p 地址。当一个用户的请 1 2 中北大学学位论文 求到达某个前端交换机( 或者p o p ) 时，首先根据一定的分发算法选择适当的内容服务器， 然后使用一定的转发机制将该请求发送的相应的服务器上。基于前端交换机不同的分发 算法和转发机制的选择方法，可以将其分为第4 层交换和第7 层交换： 第4 层交换：当客户要求建立一个t c p i p 连接，即当第一个t c ps y n 包到达时， 交换机马上根据数据报选择目标服务器。由于这种路由机制客户的数据包没有到达应用 层，所以交换机在选择目标服务器时并不知道客户请求的内容。 第7 层交换：这种交换技术首先与客户端建立一个完全的t c p 连接，然后在应用 层检查请求数据包再选择目标服务器。由于它分析数据包的应用层，因此它知道客户请 求的内容。对t c p i p 模型来说，应用层为第5 层，所以也有些人将这种交换技术称为 第5 层交换( 或者应用层交换) 。 另外，此种结构还可以在本地再使用多级的交换结构，也就是说，本地可以首先有 一个前端交换机不考虑请求的内容( 即使用第4 层算法如轮询算法等) 将其转发到下一级 的交换机上，而下一级交换机再根据请求的内容( 即使用第7 层算法) 进一步分发到响应 的服务器上。这些方案实际上结合了第4 层算法和第7 层算法的优点得以实现的。随着 当前用户对服务质量要求的提高和服务种类的增加，实现整个局部内容路由的q o s 也将 成为局部内容路由的一个重要的研究方向。 1 2 5 基于网络拓扑的内容路由 基于网络拓扑【1 3 】【1 4 】的内容路由的思想是把服务器分为若干树状群，当有用户访问时 先测量用户到各个群的核心点的距离，找到其中距离最小的一个群。然后再测量用户到 这个群内其它子服务器的距离，如果存在距离小于到核心服务器的距离的子服务器，则 在该服务器下继续寻找，否则返回子服务器的地址，然后进行下步的访问连接，同时将 搜索信息保存备用。这种路由方式相比核心的d n s 路由方式的解析速度要快些，但是它 所选择的服务器在很多情况下不一定是离用户最近的服务器。 3 本文研究的内容和篇章结构 本文研究的重点是如何从路由方面来提高c d n 网络的访问质量，通过对c d n 的网 13 中北大学学位论文 络结构、当前的c d n 路由及现有的c d nq o s 路由策略和算法进行了研究和分析的基础 上，结合c d n 的特点，另辟思路，从内容的方面着手，以q o s 的度量之一“延迟”作 为参数，提出了通过按内容类别的动念复制和分布式内容路由相结合来尽可能为内容提 供延迟保证的策略，并通过仿真对算法进行了分析 本文篇章结构如下： 第一章介绍了c d n 网络的相关知识、运用发展概况以及c d n 内容路由的研究现状。 第二章比较分析了三种q o s 路由策略的优缺点，介绍了现有的i po o s 路由算法， 指出c d n 的q o s 路由和传统i p q o s 路由的区别，然后着重介绍了目前对c d nq o s 路 由的研究现状。 第三章按照内容复制与重定向相结合的思想，根据用户对内容访问的“局部”性特 征，提出了按内容类别的动态复制与分布式内容路由结合的来保证用户访问质量的策 略。 第四章将本文的策略与现有的相似策略进行了仿真比较，并分析了仿真结果。 第五章对全文进行了总结，并对c d nq o s 路由的未来发展提出展望。 1 4 中北大学学位论文 2 1 基本路由算法 2 q o s 路由和c d n 的q o s 路由 在i n t e r n e t 等分组交换网中，由于没有建立连接电路，传送的每个分组都需要携带 传送目的地址以及到达终点的各中间节点的路由表信息。构造路由表可以使用集中式算 法( 最典型的是d i j k s t r a 算法) 或者分布式算法( 如距离矢量算法和链路状态算法) 。由于节 点或链路失效以及新节点或动态链路加入时，可能导致网络拓扑的变化，集中式算法不 能处理这种情况。分布式算法知道网络拓扑的改变，根据更新的拓扑信息来计算路由路 径，因而更具有动态性。下面介绍三种最基本的路由算法，几乎其它所有复杂的路由算 法都是由这几种算法演化而来的。 2 1 1d i j k s t r a 最短路径算法 通信网络可以模型化为一个图形，其中顶点和边分别代表了网络的节点和链路。各 条链路的代价表示为图形中的相关边的权值。d i j k s t r a 是一种集中式算法，它需要完整 的网络拓扑和链路权值，以此来计算从一个指定源节点到网络中其它节点的最短路径。 图g = g ，e ) ，其中y 和e 分别表示图形的顶点和边的集合。从顶点u 到顶点y 的边的权 值表示为w ；w ( u ，y ) ，w 须为非负的。一条边的权值尺度通常包括跳数、链路带宽、平 均传输时延、链路排队时延或者它们的组合。算法使用一种权值尺度来计算最短路径。 d i j k s t r a 算法的步骤如下： 1 、各个节点用从源节点沿已知最佳路径到本节点的距离来标注，标注分为临时性 标注和永久性标注； 2 、初始时，所有节点都为临时性标注，标注为无穷大； 3 、将源节点标注为o ，且为永久性标注，并令其为工作节点； 4 、检查与工作节点相邻的临时性节点，若该节点到工作节点的距离与工作节点的 标注的和小于该节点的标注，则用新计算得到的和来重新标注该节点； 1 5 中北大学学位论文 5 、在整个图中查找具有最小值的临时性标注节点，将其变为永久性节点，并成为 下一轮检查的工作节点； 6 、重复( 4 ) 、( 5 ) ，直到目的节点成为工作节点。 2 1 2 距离矢量路由算法 距离矢量路由算法又名b e l l m a n f o r d 路由算法。该算法要求每个节点内部维持一张 路由表，表中给出到每个目的节点已知的最短距离和下一跳节点。子网中每个节点在表 中都占有一个入口，路由表包括两部分内容：到某个目的节点的最佳下一跳和估计到该 目的节点的“距离 。距离尺度可为跳数、时延、分组队列长度或者类似的值。算法假 设每个节点知道自己到所有相邻节点的距离，这是完全可以做到的，比如：如果是以节 点间的跳数来计量距离，则相邻节点间的距离等于1 ；如果是以时延来计量距离，则每 个节点可定期向相邻节点发送“回声( e c h o ) 分组，每个节点收到分组后在其上记下接 收的时间，并以最快的速度发送回去，通过检查分组上的时间戳就可以推算出节点问的 延迟时间；如果是以分组队列长度来计量距离，则只需统计一下去往该节点的分组数即 可。 距离矢量路由算法的工作流程如下： 1 、路由器启动时，对路由表进行初始化，包含所有与本路由器直接相连的网络路 径，这些网络路径不经过中间节点，初始路由表中各项的路径长度为0 。 2 、各路由器周期性地向外广播其路由表报文，与某路由器j r ，直接相连的路由器足 收到尺；的报文后，逐项检查报文内容，遇到下面所叙述的表目之一，必须对本地路由表 的相应内容进行修改； 1 ) 路由器r j 歹0 出的表目在足路由表中没有，则r 路由表中增加相应的表目，其信 宿是q 表目中的信宿，距离为吩表目中的距离加1 , t - 跳为r ，。 2 ) 尺乎0 某信宿的距离加1 小于r 到该信宿的距离，说明r 到该信宿若经过尺f ， 其路径会更短，则r 修改本表目，其信宿域保持不变，而将距离为尺；中相同信 宿表目的距离值加1 。 1 6 中北大学学位论文 3 ) r 到某信宿的路径经过r ，而r 的路由表中不再含有到该信宿的表目，则删 除r 路由表中相应的表目。 4 ) r 到某信宿的路径经过q ，而q 的路由表中到该信宿的距离发生了变化r 则 对r 中相应的表目距离项进行修改，以尺中距离加1 取代。 距离矢量路由的主要问题是，网络拓扑改变时算法收敛慢以及无穷计算问题。加强 距离矢量收敛的一个常用方法是水平分裂算法，但水平分裂算法不能解决所有的无穷计 算问题。 2 1 3 链路状态路由算法 链路状态路由算法中每条链路都有一系列状态信息。如图2 - 1 所示，链路状态是一 个包含剩余带宽、时延和代价的三元组。节点也有状态信息，节点的状态信息可以单独 的测量出来或者映射到相邻链路的状态中。 链路状态路由算法的工作流程如下： 1 、每个路由器发现它的邻居节点，并知道其网络地址； 2 、测量到各邻居节点的延迟或者开销； 3 、组装一个分组以告之路由器刚知道的所有信息； 4 、将该分组发送给所有其它路由器； 5 、计算到每个其它路由器的最短路径。 现在各种各样的链路状态路由选择算法已经得到了广泛的应用，如开放最短路径优 先( o p e ns h o r t e s tp a t hf i r s to s p n 协议就是使用链路状态算法的一个例子【1 5 1 。 17 中北大学学位论文 图2 - 1 网络链路状态 2 2 服务质量( q u a l i t yo fs e r v i c e ) 路由算法使用不同的q o s 尺度来决定最佳路径，一个完善的路由算法能够综合多个