（通信与信息系统专业论文）基于覆盖网络的内容路由.pdf

浙江大学硕士学位论文 摘要 互联网的高速发展给人们的工作和生活带来了极大的便利。网络的应用趋于 多样化，电子商务、多媒体等业务的出现使用户对网络的性能要求也越来越高。 c d n ( 内容分发网络) 技术的广泛应用极大的提高了用户的服务质量。 c d n 是一个建立并覆盖在互联网之上的一层特殊网络，专门用于通过互联网 高效传递丰富的多媒体内容。c d n 能使网站的内容发布到最接近用户的网络 “边缘”，使用户可以就近取得所需的内容，提高用户访问网站的响应速度。因 而c d n 可以提高互联网中信息流动的效率，从技术上全面解决由于网络带宽小、 用户访问量大、网点分布不均等原因造成的“拥塞”，提高用户访问网站的响应 速度。本文结合传统的c d n 路由技术提出了基于覆盖网络的内容路由技术，阐 述了基于覆盖网络的内容路由技术的系统模型和请求分送机制，给出了在存在多 路径情况下满足q o s 机制的c d n 覆盖网络多路径选择算法。 第一章是绪论，简单介绍了c d n 的概念，并给出了传统的内容路由算法， 在此基础上我们提出了基于覆盖网络的内容路由算法。最后分析了这几种内容路 由算法的优缺点。 在第二章中，主要讨论c d n 覆盖网络节点的放置策略。在研究了当前互联 网的组织方法以后，得出如下结论：c d n 覆盖网络节点是一颗天然的组播树， 将本地用户限制在本地节点获取内容服务可以最大限度的提高网络资源利用率。 第三章给出了c d n 覆盖网络系统模型和请求分送架构。之后对c d n 覆盖 网络中的节点进行了分类，并给出了每种节点系统功能的定义以及各节点之间的 逻辑关系。 第四章首先总结了i pq o s 技术，由此引入了覆盖网络q o s 的概念，并给出 了覆盖网络q o s 与i pq o s 的不同点。同时研究了c d n 覆盖网络出现多路径的 可能性，在此基础上给出了满足q o s 要求的c d n 覆盖网络多路径选择算法。最 后用o p n e t 仿真验证了此算法的性能。 最后是总结和展望，对本文的主要思想作了总结，并对进一步的研究方向进 行了展望。 关键字：内容分送网络，内容路由，覆盖网络，q o s 路由，负载均衡 浙江大学硕士学位论文 a b s t r a c t d e s p i t et h ea l l u r i n gp r o m i s eo ft h ei n t e m e ta st h ec o n v e r g e n c ec h a n n e lf o r d e l i v e r yo fa l lt y p e so fm e d i a ，i ti so b v i o u st h a tt h e r ea r em a n yc h a l l e n g e st h a tm u s t b ea d d r e s s e dt oe n s u r ec o n s i s t e n td e l i v e r yt ot h ee n d - u s e r n e wt y p e so fn e t w o r k sa r e b e i n gb u i l tt os p e c i f i c a l l ya d d r e s st h e s en e e d s c o n t e n td e l i v e r yn e t w o r k s ( c d n 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 et h a th e l p st oe f f i c i e n t l yd e l i v e rt h e e v e ri n c r e a s i n gc o n t e n tf r o mc o n t e n tp r o v i d e r st oa l a r g ec o m m u n i t yo fg e o g r a p h i c a l l y d i s t r i b u t e dc l i e n t s t h er e s e a r c hs u b j e c to ft h ed i s s e r t a t i o ni st h ek e yf u n c t i o nl a y e ro f t h ec d nn e t w o r k - r o u t e rl a y e r i nt h i sp a p e r ，an e wc o n t e n t b a s e dr o u t i n gp r o t o c o l b a s e do no v e r l a yn e i w o r k 蠢p r e s e n t e d d e t a i l so ft h en e t w o r ka r c h i t e c t u r ea n dr e q u e s t r o u t i n gi n f r a s t r u c t u r ea r ed e s i g n e d c h a p t e r1 i st h ei n t r o d u c t i o n t h et r a d i t i o n a lt e c h n o l o g yo fc o n t e n tr o u t i n gi s g i v e n t h e nw ep r e s e n tc o n t e n tm u t i n ga l g o r i t h mb a s e do no v e r l a yn e t w o r k i nc h a p t e r2 ，a f t e ra n a l y s et h es t r u c t u r eo fi n t e r n e t ，al a y e r e do v e d a yn e t w o r k s f o rl a r g e s c a l ec d ni sp r o p o s e d ，a l s op u t t i n gf o r w o r dt h en o t i o no fl o c a lr e q u e s t b e i n gs e r v e db yl o c a ls e r v e r c h a p t e r3p r e s e n t st h en e t w o r ka r c h i t e c t u r ea n dr e q u e s t r o u t i n gi n f r a s t r u c t u r ef o r c d nn e t w o r kb a s e do no v e r l a yn e t w o r k t h e nw ec l a s s i f yo v e r l a yn o d e si n t ot h r e e d i f f e r e n tk i n d so f n o d e sa n dd e f i n et h ef u n c t i o no f e a c hn o d e c h a p t e r 4s u m m e r i z ei pq o st e c h n o l o g ya n dp r e s e n t so v e r l a yq o sb yc o m p a r e i tw i t hi pq o s t h e nw es t u d yt h ep o s s i b i l i t yo fn m t i p a t hs i t u a t i o na n dp r o p o s e q o s - a w a r er o u t i n ga l g o r i t h mi nm u t i - p a t hs i t u a t i o n f i n a l l y ，t h ec o n c l u s i o na n de p i l o g u ea r eg i v e n t h em a i nw o r ko f t h e d i s s e r t a t i o n i sc o n c l u d e d t h ef i e l d so ft h ec d nr o u t es y s t e m ，w h i c hn e e dt ob es t u d i e dd e e p l y ， a r em e n t i o n e d k e yw o r d s ：c d n ，c o n t e n tr o u t i n g ，o v e r l a yn e t w o r k s ，q o sr o u t i n g ， l o a db a l a n c i n g i i 浙江大学硕士学位论文 绪论 进入2 1 世纪，i p 网络上的信息越来越多，人们对信息的需求也越来越多。 尽管i p 网络的传输带宽越来越宽，用于存储内容信息的服务器性能和容量越来 越高，但人们依然抱怨信息网络的传输速度低，获得的信息不够准确、不够快。 造成这种现象的原因很多，如网络带宽瓶颈、传输途中的路由阻塞和延迟以 及作为信息存储媒体的服务器性能( 存储容量、存取速度) 的提高速度赶不上众 多用户提取信息的需求。人们发现传统的网页访问方式在应对大规模的访问时显 得力不从心，无论是对服务器还是带宽的压力都将导致网站无法为巨量访问用户 提供高品质的系列应用服务。 c d n ( 内容分发网络) 正是在改善互联网性能的呼声中应运而生的。有别 于传统互联网性能改善方案( 如增加接入带宽，升级硬件和建立多个镜像站点) ， c d n 提出“让内容离用户更近”的全新思路。 1 1c d n 简介 1 1 1c d n 概念介绍 内容分发网络的目的是通过在现有的i n t e r n e t 中增加一层新的网络架构， 将网站的内容发布到最接近用户的网络“边缘”，使用户可以就近取得所需的内 容，解决i n t e r n e t 网络拥塞状况，提高用户访问网站的响应速度【1 1 。从技术上 全面解决由于网络带宽小、用户访问量大、网点分布不均等问题，解决用户访问 网站的响应速度慢的根本问题。 狭义地讲，c d n 是一种新型的网络构建方式，它是为能在传统的i p 网发布 宽带多媒体信息而特别优化的网络覆盖层；从广义的角度，c d n 代表一种基于质 量与秩序的网络服务模式。简单的说，c d n 是一个经策略性部署的整体系统，包 括分布式存储、负载均衡、网络请求的重定向和内容管理4 个方面，而内容管理 和全局的网络流量管理是c d n 的核心所在。通过用户就近性和服务器负载的判 断，c d n 确保内容以一种极为高效的方式为用户的请求提供服务。 总的来说，内容服务基于缓存服务器，也称作代理缓存，它位于网络的边缘， 距用户仅有“一跳”之遥。同时，代理缓存是内容提供商源服务器的一个透明镜 像。这样的架构使得c d n 服务提供商能够代表他们客户，即内容提供商，向最终 用户提供尽可能好的体验，而这些用户是不能够容忍请求响应时间有任何延迟 的。据统计，采用c d n 技术，能处理整个网站页面的7 0 “9 5 的内容访问量，减 一1一 浙江大学硕士学位论文 轻服务器的压力，提升了网站的性能和可扩展性。 1 1 2c d n 系统设计思想 首先，我们来看一下传统的i n t e r n e t 网络的基本结构2 1 和数据传输情况， 如图卜1 所示。 图1 - 1i n t e m e t 网络基本结构及数据传输方式 根据传统的网络结构，用户的访问流程如下： 1 在用户浏览器中输入将要访问的网站的域名； 2 浏览器将域名的解析请求发送给本地d n s ； 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 把解析结果返还给用户，同时将该域名的解析结果缓存起来， 一z 一 浙江大学硕士学位论文 作为下一个用户解析请求的直接响应。直到相应的t t l ( 生存周期) 过期，才再 向网站的授权d n s 发送解析请求： 6 用户得到i p 地址后，就可以直接对网站的服务器进行访问。 传统的网站访问模式虽然简单，但存在的几个问题会严重影响i n t e r n 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 网络中，为众多的网站用户提 供加速服务。 1 1 3c 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 重定向服务器 的动态负载均衡技术，可以将请求用户重定向到最佳c d n 内容服务器上；c d n 内 容服务器的高性能则进一步保证了访问用户可以获得更及时可靠的响应；而c d n 内容分发和管理机制保障了各个c d n 内容服务器与i c p 的源服务器的数据同步， 用户访问c d n 内容服务器将得到与原服务器完全相同的内容。 图卜2 给出了用户访问加入c d n 服务的网站的完整过程。 浙江大学硕士学位论文 图i - 2 “第一个”用户访问流程 用户的访问加入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 ed n s ) ，授权域名服务器查询数据库，将c d n 重定向服务器地 址返还给本地d n s ； 3 本地d n s 重新将域名解析请求发送给c d n 重定向服务器： 4 c d n 重定向服务器根据采用的负载均衡技术，选择最佳c d n 内容服务器 节点，并将结果( i p 地址) 返还给本地d n s ； 5 本地d n s 将收到的c d n 内容服务器节点的i p 地址发送给请求用户； 6 请求用户将服务请求发送到收到的c d n 内容服务器节点； 7 c d n 内容服务器节点响应请求用户，提供请求服务内容。 上面描述的是第一个用户，在第一次访问一个网站，并且所访问的本地域名 服务器在没有解析过该域名的情况下的访问流程。 从上面可以看到，它需要七步才能够完成对用户的一次响应，看似比较繁琐。 但是在该过程中，本地域名服务器会对解析过的域名进行缓存，并且c d n 内容服 浙江大学硕士学位论文 务节点会对用户访问过的内容进行缓存，后续请求用户的访问就可以用缓存的域 名直接发送请求。 1 1 4 c d n 带来的好处 如今，c d n 技术方案之所以能够蓬勃发展，主要原因口1 是： 1 c d n 方案能够提高站点的性能和可靠性，它允许网络内容位于最靠近终 端用户的位置，并可最小化原始服务器的负载和传输延迟时间。 2 它消除了i n t e r n e t 的拥塞点，允许丰富内容的有效传递，是视频和其他 丰富内容的传递成为可能的同时，却没有降低站点的性能。 3 c d n 方案优化了昂贵站点的带宽，消除了对通过更昂贵网络的内容需求， 它还提供了增值服务，允许i s p 从竞争对手、决定性的商标产权等方面区分它们 的服务。 c d n 的用户包括i s p 、i c p 、媒体网站、大中型企业、电子商务网站和政府网 站。利用c d n 技术，这些网站无需投资昂贵的各类服务器、设立分站点。通过与 c d n 合作，c d n 将负责信息传递工作，保证信息正常传输，维护传送网站，而网 站只需要维护内容，不需要考虑流量问题。既节约了成本，又提高了效率。对于 广大网络用户而言，在c d n 技术的基础上，他们可从网络内容提供者那里获得更 多的新业务，可以快速访问网络上的内容，获得更好的服务质量。对于w e b 企业 而言，c d n 技术将给他们带来两个明显的好处：提高了客户的满意度主动将 经常被访问的网络内容发送到距离用户更近的服务器可以缩短响应时间，消除 “找不到服务器”的错误，提高用户的忠诚度。加强对w e b 资源的控制管理 增强的管理功能优化了网络内容提供者的高优先级网络内容、应用软件和企业计 划，使他们获得最大的收益。 1 2 c d n 内容路由 1 2 1c d n 路由的概念 c d n 路由又称为“内容路由”，指的是把用户的内容请求重定向，或者说， “路由”到离用户最近的内容服务器。 c d n 内容路由器负责内容路由，为用户的请求选择最佳的访问站点。 c d n 路由以现有的i p 网络为基础，支撑点依然是现有l p 路由机制。图1 - 3 表明了c d n 路由、i p 路由和用户内容请求的层次关系。我们把c d n 路由所处 一5 一 浙江太学硕上学位论文 务节点会对用户访问过的内容进行缓存，后续请求用户的访问就可以用缓存的域 名直接发送请求。 1 1 4c d n 带来的好处 如今，c d n 技术方案之所以能够蓬勃发展，主要原因口1 是： 1 c d n 方案能够提高站点的性能和町靠性，它允许网络内容位于最靠近终 端用户的位置，并可最小化原始服务器的负载和传输延迟时间。 2 它消除了i n t e r n e z 的拥塞点，允许丰富内容的有效传递，是视频和其他 丰富内容的传递成为可能的i 刊时，却投有降低站点的性能。 3 ，c d n 方案优化了昂贵站点的带宽，消除了对通过更昂贵网络的内容需求， 它还提供了增值服务，允许i s p 从竞争对手、决定性的商标产权等方面区分它们 的服务。 c d n 的用户包括i s p 、i c p 、媒体网站、大中型企业、电子商务网站和政府刚 站。利用c d n 技术，这些刚站无霰投资昂贵的各类服务器、设立分站点。通过与 c d n 合作，c d n 将负责信息传递工作，保证信息正常传输，维护传送网站，而网 站只需要维护内容，不需要考虑流量问题。既节约了成本，又提高了效率。对于 广大网络用户而言，在c d n 技术的基础上，他们可从网络内容提供者那里获得更 多的新业务，可以快速访问网络上的内容，获得更好的服务质量。对于w e b 企业 而苦，c d n 技术将给他们带来两个明显的好处：提高了客_ l i 的满意度主动将 经常被访问的网络内容发送到距离= | j 户更近的服务器可以缩短响应时间，消除 “找不到服务器”的错误，提高用户的忠诚度。加强对w e b 资源的控制管理 增强的管理功能优化了网络内容提供者的高优先级网络内容、应用软件和企业计 划，使他们获得最大的收益。 1 2c d n 内容路由 1 2 1 c d n 路由的概念 c d n 路由又称为“内容路由”，指的是把用户的内容请求重定向，或者说， “路由”到离用户最近的内容服务器。 c d n 内容路由器负责内容路由，为用户的请求选择最佳的访问站点。 c d n 路由以现有的i p 网络为基础，支撑点依然是现有i p 路由机制。图1 - 3 表明了c o n 路由、i p 路由和用户内容请求的层次关系。我们把c d n 路由所处 表明了c o n 路由、i p 路由和用户内容请求的层次关系。我们把c d n 路由所处 一5 一 浙江大学硕士学位论文 务节点会对用户访问过的内容进行缓存，后续请求用户的访问就可以用缓存的域 名直接发送请求。 1 1 4 c d n 带来的好处 如今，c d n 技术方案之所以能够蓬勃发展，主要原因口1 是： 1 c d n 方案能够提高站点的性能和可靠性，它允许网络内容位于最靠近终 端用户的位置，并可最小化原始服务器的负载和传输延迟时间。 2 它消除了i n t e r n e t 的拥塞点，允许丰富内容的有效传递，是视频和其他 丰富内容的传递成为可能的同时，却没有降低站点的性能。 3 c d n 方案优化了昂贵站点的带宽，消除了对通过更昂贵网络的内容需求， 它还提供了增值服务，允许i s p 从竞争对手、决定性的商标产权等方面区分它们 的服务。 c d n 的用户包括i s p 、i c p 、媒体网站、大中型企业、电子商务网站和政府网 站。利用c d n 技术，这些网站无需投资昂贵的各类服务器、设立分站点。通过与 c d n 合作，c d n 将负责信息传递工作，保证信息正常传输，维护传送网站，而网 站只需要维护内容，不需要考虑流量问题。既节约了成本，又提高了效率。对于 广大网络用户而言，在c d n 技术的基础上，他们可从网络内容提供者那里获得更 多的新业务，可以快速访问网络上的内容，获得更好的服务质量。对于w e b 企业 而言，c d n 技术将给他们带来两个明显的好处：提高了客户的满意度主动将 经常被访问的网络内容发送到距离用户更近的服务器可以缩短响应时间，消除 “找不到服务器”的错误，提高用户的忠诚度。加强对w e b 资源的控制管理 增强的管理功能优化了网络内容提供者的高优先级网络内容、应用软件和企业计 划，使他们获得最大的收益。 1 2 c d n 内容路由 1 2 1c d n 路由的概念 c d n 路由又称为“内容路由”，指的是把用户的内容请求重定向，或者说， “路由”到离用户最近的内容服务器。 c d n 内容路由器负责内容路由，为用户的请求选择最佳的访问站点。 c d n 路由以现有的i p 网络为基础，支撑点依然是现有l p 路由机制。图1 - 3 表明了c d n 路由、i p 路由和用户内容请求的层次关系。我们把c d n 路由所处 一5 一 浙江大学硕士学位论文 的层次形象的称为“内容层”。内容层充分利用现有的i p 核心路由网络，通过特 定的内容路由策略，为用户的内容请求选择最佳的内容服务器，完成内容的重定 向。 传统的c d n 路由技术可以分为两类4 1 ： 1 基于d n s 的路由 2 基于名字的路由 基于d n s 的路由是中心服务器体系的路由方式，基于名字的路由采用分布 式体系。 本文在传统c d n 路由技术基础上，结合覆盖网络技术，给出基于覆盖网络 的内容路由技术。基于覆盖网络的内容路由技术也是一种分布式路由体系。 图i - 3 内容路由层次图 1 2 2 基于d n s 的内容路由 在上一节我们详细介绍了基于d n s 内容路由的c d n 访问流程。针对基于 d n s 的内容路由已有大量的研究 1 3 , 1 4 1 。 基于d n s 的内容路由大致流程如下：当用户访问已经加入c d n 服务的网 站时，首先通过d n s 重定向确定最接近用户的c d n 内容服务器节点，同时将 用户的请求指向该节点。当用户的请求到达指定节点时，c d n 的内容服务器负 责将用户请求的内容提供给用户。 由用户访问流程，推算出用户获取内容的r t t ( r o u n d t r i p t i m e ) 公式( 一) ： 获取内容的r t t = d n s 重定向的r t t + 内容服务器提供内容的r t i ( 式一) 其中 d n s 重定向的r t t = 用户d n s 请求到达重定向d n s 的时间耗费+ 重定向 一r 一 浙江大学硕士学位论文 d n s 选择内容服务器的时间耗费+ d n s 响应返回用户的时间耗费( 式二) 基于d n s 的内容路由充分利用了现有的网络结构，结构简单，因而被人们 认为是一种有效的技术，是c d n 应用中采取的主要路由技术之一。但是，它的 性能瓶颈非常突出。 首先，d n s 重定向的r t t 远大于内容服务器提供内容的r t t 。需要花较长 的往返时间去定位离用户非常近的内容服务器。相反，最后访问的内容服务器离 用户却很近。显而易见，d n s 重定向耗费的r t t 远大于用户访问内容服务器的 r t t 。r t t 成了c d n 性能提高的瓶颈之一。 其次，当我们提高网络带宽，缩短了用户到达重定向服务器的时间。d n s 海量数据的查询、重定向d n s 复杂的定位选择过程的延迟，无形中造成了网络 性能提高的又一瓶颈。 c d n 是分布式的，而重定向d n s 技术确是中心服务器式的。由于对重定向 服务器的集中访问形成了网络拥塞点，而c d n 的设计目标之一就是避免网络拥 塞点，这就形成了矛盾。对服务器的集中访问无疑加重了服务器的负载，进一步 导致了数据查询和处理延迟。 1 2 3 基于名字的c d n 路由 由于d n s 重定向技术存在的缺陷，斯坦福大学和m i t 的研究者提出了一种叫 “名字路由”的方案。它不同于传统的基于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 tr o u t e r ，c r ) 构成。 图卜4 代表了基本的名字路由结构。 浙江大学硕士学位论文 n 丁。，母 多刨 萱 图1 - 4 名字路由结构 c r 的功能包括：参加名字路由体系的动态路由表更新过程；负责为用户的 内容请求选择最佳的c s ，或者将内容请求前递到邻近的c r 。从这个意义上说， c r 相当于分布式d n s 服务器。 c s 的功能包括：提供内容分发功能；响应通过c r 最终路由到c s 的用户请 求：通过c r 通告c s 的内容信息。 由名字路由结构，推算出用户获取内容的r t t ( r o u n d t r i p t i m e ) 公式( 三) ： 获取内容的r t t = 至i j 达服务器时间耗费+ 内容服务器提供内容的r t t ( 式三) 其中到达服务器时间耗费为请求经过的各内容路由器的延迟总和。 将名字路由的r t t 公式( 式三) 与d n s 重定向的r t t ( 式一) 相比较，可以 看出它们几乎是一致的。内容服务器提供内容的r t t 不依赖于c d n 路由方式，两 种情况下都是相同的。最大的区别在于定位内容服务器的时间耗费不同。由于基 于名字路由采用了分布式的体系结构，内容路由耗费是由用户附近的c r 和c s 所引起的，地理位置的优势和查询数据量的大大缩小决定了内容路由的r t t 将远 小于d n s 重定向的r t t 。因此，名字路由获取内容的r t t 将远远小于d n s 路由的 获取内容的r t t 。 基于名字路由的路由体系实际上是一个分布式的d n s 体系，借鉴了i p 路由 的思想，它正是根据c d n 网络分布式的特点而设计的。但是要采用名字路由技术， 必须在现有的路由器上加入名字路由功能，但是在短时间内完成路由器的更新换 代简直是天方夜谭，现在阶段其实际部署的可能性很小。 1 2 4 基于覆盖网络的内容路由 覆盖网络是建立在已存在的一个或多个网络之上的一个间接的或者可视化 的抽象。利用覆盖网络，可以不需要修改已存在的软件协议和网络的底层结构而 一8 一 浙江大学硕士学位论文 快速的添加新的网络功能【5 】。有了覆盖网络，即使网络层出现错误，应用系统也 可以凭借覆盖网络快速找到替代路由，并且可以根据应用服务的不同服务质量要 求寻找相应的最优路径。同时，覆盖网络只是重叠在现有网络之上的虚拟网络， 并不需要改变现有网络架构，实现起来也是很方便的。具体来说，覆盖网络是由 一系列分布于i n t e r n e t 各自治系统内部的覆盖服务节点以及连接它们的逻辑链 路所组成的虚拟网络，它能有效地利用i n t e r n e t 给终端用户提供更为可靠的服 务。覆盖节点通常具有路由、数据处理和数据保存等功能，而逻辑链路( 即覆盖 链路) 通常对应底层的一条或多条物理路径。图卜5 所示就是一个覆盖网络的例 子。 图卜5 覆盖网络示意图 基于覆盖网络的内容路由正是利用覆盖网络的这个特点来实现内容路由，下 面对此方案简单介绍一下。 基于覆盖网络的内容路由： 基于覆盖网络的内容路由结构由源服务节点( o r i g i n ) 、请求分送节点( r r d m ) 和一系列内容路由节点( t r a n s i t ) 组成的覆盖网络构成。图卜6 给出了典型的 基于覆盖网络的路由结构。 图卜6 中的o r i g i n 表示源服务节点，v i e w e r 表示请求用户，而其它的如 f i r s t h o p 、g l o b a l t r a n s i t 、r e g i o n a l t r a n s i t 、r e g i o n a l l a s t i o p 以及l a s t h o p 都是内容路由节点，它们一起组成了完成内容路由的覆盖网络( 会在第二章中给 浙江大学硕士学位论文 出具体详细的介绍) 。 源服务节点功能：是内容提供商发布服务的源节点，源服务节点中的服务内 容通过覆盖网络注入或缓存到内容路由节点中。源服务节点还负责将服务信息发 布到内容路由节点当中。 请求分送节点功能：当请求用户发起请求后，将请求发送到请求分送节点。 请求分送节点根据当前请求用户的地理位置，返回当前请求用户的最佳内容路由 接入点。同时，请求分送节点还负责接收内容路由节点的注册信息。 图卜6 基于覆盖网络的路由结构 内容路由节点功能：根据需求不同可同时具备内容路由、数据处理和数据保 存等功能。具体来说如接收和传递源服务节点发布的服务信息，给请求分送节点 发送注册信息以及缓存服务内容等。总的来说由这一系列内容路由节点组成的覆 盖网络负责返回请求用户的请求内容。 由基于覆盖网络的路由结构，推算出用户获取内容的r t t ( r o u n d t r i pt i m e ) 公式( 四) ： 获取内容的r t t ：覆盖网络查询服务内容时间耗费十内容服务器提供内容的 r t t ( 式四) 将基于覆盖网络的内容路由的r t t 公式( 式四) 和名字路由的r t t 公式( 式 三) 以及d n s 重定向的r t t ( 式一) 相比较，可以看出它们几乎也是一致的。内 一1 n 一 浙江大学硕士学位论义 容服务器提供内容的r t t 不依赖于c d n 路由方式，三种情况下都是相同的。最大 的区别在于定位内容服务器的时间耗费不同。由于基于覆盖网络的内容路由和基 于名字路由都采用了分布式的体系结构，使得这两种路由方式定位内容服务器的 时间耗费将远小于d n s 重定向的r t t 。 由于覆盖网络只是重叠在现有网络之上的虚拟网络，并不需要改变现有网络 架构，这使得基于覆盖网络的内容路由既有基于d n s 的内容路由技术的易部署 性，还具备基于名字路由技术的高扩展性。所以基于覆盖网络的内容路由可以充 分利用现有网络框架，延迟响应小，扩展性高1 6 j 。 1 3 本文的主要贡献及篇章结构 本文的主要工作是围绕c d n 的分布式路由基于覆盖网络的内容路由具 体展开的，主要研究对象是c d n 覆盖网网络节点的放置策略、c d n 覆盖网络的 系统模型、c d n 覆盖网络的路由体系，更迸一步将c d n 覆盖网络节点进行分类， 分别定义各类节点的功能以及它们之间的逻辑关系。本文详细讨论了服务范围的 注册处理，c d n 覆盖网络分发树的生成等重要模块。 研究的意义： 目前主要存在了两种内容路由技术：基于d n s 的内容路由和基于名字的内 容路由。 基于d n s 的内容路由具有部署管理方便的优点，但是它作为一种中心服务 器式的路由方式，d n s 重定向存在瓶颈，当d n s 被集中访问时，负载升高，解 析延时会严重影响服务质量，并且d n s 的缓存机制也会降低d n s 服务器对客户 请求的控制能力。 而基于名字的路由技术是根据c d n 网络分布式的特点而设计的，避免了 d n s 路由的不可靠性，它是一种分布式的d n s 体系，但是它需要对现有的网络 设备进行改动，使其支持名字路由功能，所以部署困难。 所以目前的两种内容路由技术都存在难以改进的缺陷，如何将两种内容路由 技术优点结合起来将是我们研究的方向。覆盖网络技术的出现使得梦想成真，本 文提出的基于覆盖网络的内容路由既有基于d n s 的内容路由技术的易部署性， 还具备基于名字路由技术的商扩展性，它可以充分利用现有网络框架，延迟响应 小，扩展性高。 作者所做的主要工作及贡献： 在近一年的时间里，作者专心致志的围绕c d n 的路由技术，结合覆盖网络 一1 1 浙江大学硕士学位论文 技术提出了基于覆盖网络的内容路由，获得了如下成果： 在充分的查阅和学习互联网的当前结构的基础上，给出了分层的c d n 覆盖 网络部署结构，做出如下结论：c d n 覆盖网络节点是一颗天然的组播树，将本 地用户限制在本地节点获取内容服务可以最大限度的提高网络资源利用率。 广泛收集c d n 和覆盖网络路由方面的资料，并在此基础上提出了基于覆盖 网络的内容路由系统模型和请求分送架构。 将c d n 覆盖网络节点进行分类，并对每种节点进行定义。 定义请求分送节点作为注册服务端和内容路由节点作为注册客户端的基本 行为，定义交互信息的格式，给出实现的总体方案。 给出c d n 覆盖网络分发树的生成算法以及传播过程，并给出基于c d n 覆 盖网络分发树的路由过程。 研究c d n 覆盖网络分发树产生多路径的可能性，并在此基础上给出满足 q o s 的多路径选择算法。 本文的篇章结构： 第一章是绪论，简单介绍了c d n 的概念，并给出了传统的内容路由算法， 在此基础上我们提出了基于覆盖网络的内容路由算法。最后分析了这几种内容路 由算法的优缺点。 在第二章中，主要讨论c d n 覆盖网络节点的放置策略。在研究了当前互联 网的组织方法以后，给出如下结论：c d n 覆盖网络节点是一颗天然的组播树， 将本地用户限制在本地节点获取内容服务可以最大限度的提高网络资源利用率。 第三章给出了c d n 覆盖网络系统模型和请求分送架构。之后对c d n 覆盖 网络中的节点进行了分类，并给出了每种节点系统功能的定义以及各节点之间的 逻辑关系。 第四章首先总结了i pq o s 技术，由此引入了覆盖网络q o s 的概念，并给出 了覆盖网络q o s 与i pq o s 的不同点。同时研究了c d n 覆盖网络出现多路径的 可能性，在此基础上给出了满足q o s 要求的c d n 覆盖网络多路径选择算法。 最后是总结和展望，对本文的主要思想的意义作了总结，并对进一步的研究 方向进行了展望。 浙江大学硕士学位论文 1 4 本章小结 本章首先介绍了c d n 的概念，给出了当前存在的两种内容路由技术：基于 d n s 的内容路由和基于名字的内容路由。分析了此两种技术的优点和缺点，然 后结合覆盖网络技术给出了基于覆盖网络的内容路由，并将此技术和当前的两种 内容路由技术作了比较。 浙江大学硕士学位论文 第二章c d n 覆盖网络节点部署策略 2 1 c d n 应用现状 一般情况下网站响应速度的快慢和访问者与网站服务器之间的“距离”密切 相关。为了改善网站响应速度，内容分发网络提出了“让内容离用户更近”的思 路。c d n 的技术原理是在遍布世界的主要i n t e r n e t 接入点部署内容服务器节点， 在这些节点的基础上组成一个覆盖网络，并利用一种特殊的路由机制将网站内容 发布到离用户最近的网络“边缘”，使用户能以最快的速度、从最接近的地方获 取所需的信息。目前c d n 在国外已经得到了广泛的应用，如著名c d n 提供商 a k a m a i 早在2 0 0 1 年6 月就已经在全球部署了1 1 6 8 9 台服务器，覆盖6 2 个国家 8 2 0 个网络【7 1 。国内的c d n 应用也已经起步，如c h i n a c a c h e 公司已经在全国部署 了4 0 个c d n 服务节点。 目前部署的c d n 系统一般都采用了基于d n s 的内容路由技术作为实现全局负 载均衡的手段，采用4 7 层交换技术实现c d n 服务节点内部服务器群本地负载均 衡。随着c d n 规模的不断扩大，请求用户的不断增多，我们需要采用更为先进的 全局负载均衡技术。 同时随着c d n 技术的不断发展，c d n 开始支持越来越多类型的内容发布，由 初期的静态网页到动态网页，再到各种音频视频流媒体，到现在为止，c d n 已经 支持几乎所有源站点内容的发布。针对各种新兴业务，特别是媒体点播，现场直 播等需要与原先静态网页发布所不同的q o s 要求和发布方法。所有这些都对c d n 的部署结构和负载均衡技术提出了新的要求。 各c d n 提供商不断推出满足各种特殊应用的c d n 服务，c d n 数量不断增加， c d n 之间的融合已经成为一个热点。必须充分利用c d n 网络资源，构建通用c d n 网络，为上层c d n 应用提供基本支持，避免重复建设。同时，通用c d n 覆盖网络 还可以通过与i s p 协议获取底层网络支持，采用新的内容路由策略，把q o s 保证 引入c d n 系统。 根据c d n 应用的以上现状和发展趋势，我们提出基于覆盖网络的内容路由体 系及框架，在本章中我们研究c d n 覆盖网络节点的部署策略，而在后续章节中陆 续给出基于覆盖网络的内容路由系统模型以及基于覆盖网络的内容路由算法。 2 - 2 c d n 覆盖网络 内容分发网络的目的是通过在现有的i n t e r n e t 中增加一层新的网络架构， 浙江大学硕士学位论文 将网站的内容发布到最接近用户的网络“边缘”，使用户可以就近取得所需的内 容，解决i n t e r n e t 网络拥塞状况，提高用户访问网站的响应速度。从技术上全 面解决由于网络带宽小、用户访问量大、网点分布不均等问题，解决用户访问网 站的响应速度慢的根本问题。 当前c d n 内容服务节点主要分布在各自治系统( a u t o n o m o u ss y s t e m ， a s ) 内部，为a s 内客户请求提供加速服务。随着c d n 服务需求的不断增加，c d n 规 模不断扩大，c d n 内容服务器正在向“更边缘”的地区级网络甚至局域网分布。 更边缘化的内容服务节点将为客户提供更好的服务体验。 c d n 内容服务节点的不断增长，部署地点的不断边缘化，如何有效的部署和 组织所有的c d n 内容服务节点成为了我们研究的关键。良好的部署和组织结构可 以给我们带来性能上的极大提升，而不符合实际网络状况的部署策略既不能使性 能得到提升，也浪费了c d n 提供商的投资。由此，我们需要好好研究一下目前 i n t e r n e t 的组织结构和网络特性。 2 2 1i n t e r n e t 结构 要在现有i n t e r n e t 结构上部署一层虚拟的c d n 应用服务层，那么就有必要 研究一下底层物理网络拓扑组织机构，它对构建一个高效率的c d n 覆盖网络是必 要的。在构建c d n 覆盖网络时充分考虑底层网络的拓扑结构和组织结构，以使 c d n 覆盖网可以最大限度地利用下层网络的特点，充分利用底层网络资源。 目前，i n t e r n e t 由3 个层次的网络组成4 1 ： 第一层：骨干网，主要由美国国家科学基金网( n s f n e t ) 、能源科学网( e s n e t ) 、 国家宇航科学网( n a s a n e t ) 等网络组成，跨越全国，芳通过大型交换机联通世 界各地。美国国内骨干网线路传输率大多为4 5 m b p s ( 即t 3 ) ，也有部分己扩展 到1 5 5 m b p s ，个别线路传输率已达到6 2 2 m b p s 。 第二层：区域网，由地区网组成( 如b a r r n e t 、加州湾区网、m i d n e t 中西部 网等) ，大多采用传输率为1 5 m b p s ( 即t 1 ) ，也有采用4 5 m b p s 和更高的传输 率。 第三层：用户接入网，主要是校园网、企业网和i s p 。用户通过第三层联入 i n t e r n e t 。校园网内部用户可采用a t m 网、高速e t h n e t 网、电话网( p n t s ) 或 综合服务数字网( i s d n ) 等方式，通过网络中心联入i n t e r n e t 。其他网络的用 户采用p n t s 或i s d n 等方式，通过i s p 服务器联入i n t e r n e t 。 在自治系统内部用内部网关协议( i n t e r n a lg a t e w a yp r o t o c o l ，i g p ) 交换 浙江大学硕士学位论文 路由信息，而在自治系统之间用边界网关协议( b o r d e rg a t e w a yp r o t o c o l ，b g p ) 【9 】 交换