（应用数学专业论文）数据挖掘技术在cdn网络中的应用研究.pdf

北京邮电大学硕士学位论文 数据挖掘技术在c d n 网络中的应用研究 摘要 随着计算机网络技术的发展，网络已渗透到了世界的各个角落。 但是，当我们在上网时，经常遇到响应速度缓慢，甚至服务器错误响 应或无法进行正常访问等问题。网络实际性能与人们对其服务质量的 期望之间的矛盾，已成为关注的焦点。鉴于此，在现有的网络中建立 一个完善全面的中间层c d n ( c o n t e n td 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 的请求用户细分需求以及数据特性，研究和 提出一种针对混合属性数据的聚类算法，并将其应用于c d n 用户集 群划分。 本课题关注在用户端不使用第三方软件的条件下，调研c d n 内 容路由优化技术，提出一种新的内容路由优化方案，并且研究数据挖 掘聚类算法在c d n 用户集群划分中的应用。 本论文主要进行了如下几个方面的工作： 1 介绍了c d n 技术，详细论述了c d n 内容路由，总结了内容路 由的方法和实现技术，重点讨论其实现技术中全局负载基于d n s 重定 向、h t t p 重定向和广域三角重定向，并指出了各自的优缺点。 2 深入研究基于客户端探测的技术，针对目前c d n 内容路由技 术及其不足，研究全局负载均衡技术和基于客户端探测的c d n 内容路 北京邮电大学硕士学位论文 由技术两者结合的可能性。 3 研究了数据挖掘技术，特别是w e b 数据挖掘技术，并总结出 w e b 数据挖掘技术发展方向。 4 研究了数据挖掘技术中的聚类算法在用户集群划分中的应 用，并论述了客户细分的基本理论、方法和步骤。 c d n 的应用越来越广泛，并且解决网络带宽不足的问题。满足人 们各种需求的c d n 也必将迎来更好的发展机遇，因此这种把数据挖掘 技术和c d n 内容路由技术相结合，直接运用于基于全局负载均衡和基 于客户端探测技术相结合的设计模式也必将更好的体现它的实用价 值和参考价值。 关键词：路由优化全局负载均衡基于用户端探测用户集群数 据挖掘聚类算法 北京邮电大学硕士学位论文 d a t am i n i n gt e c h n o l o g yi nc d n a p p l i e dr e s e a r c h a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g y , n e t w o r kh a s i n f i l t r a t e di n t oe v e r yc o m e ro ft h ew o r l d h o w e v e r , w h e nw eo nt h e i n t e r n e t ，w eo f t e ne n c o u n t e rt os l o wr e s p o n s e s ，a n de v e ne r r o rr e s p o n s e s t h ed i s t a n c eb e t w e e nt h ea c t u a lp e r f o r m a n c eo ft h en e t w o r ka n dt h e q u a l i t yo fs e r v i c ee x p e c t a t i o n si sv e r yl a r g e ，a n di th a sb e c o m et h ef o c u s i nv i e wo f t h i s ，e s t a b l i s h i n gac o m p r e h e n s i v em i d d l el a y e rc d n ( c o n t e n t d e l i v e r yn e t w o r k , c o n t e n td i s t r i b u t i o nn e t w o r k ) i n t h e e x i s t i n g n e t w o r k si st h em o s tp o p u l a rs e l e c t i o nc u r r e n t l y b e t w e e nt h i s ，t h ec o n t e n tr o u t i n gs y s t e mi st h ee s s e n t i a lp a r to ft h e c d na r c h i t e c t u r e b e c a u s e ，a c c o r d i n gt ot h eu s e r sr e q u e s ta n dt h e c o n d i t i o no ft h ee d g es e r v e r , t h eb e s te d g es e r v e ri ss e l e c t e d a n di nt h e d e s i g no fn e wc o n t e n tr o u t i n gs y s t e m , t h eu s e rc l u s t e rd i v i s i o ni sa l s o v e r yi m p o r t a n t a n dd a t am i n i n gi st h ep r o c e d u r eo fe x t r a c t i n go fi m p l i c i t ，o r i g i n a l ， u s e f u lk n o w l e d g ei nt h ed a t a b a s e ，w h i c hi sa l r e a d ya p p l i e di nm a n yf i e l d s i nr e c e n ty e a r s c l u s t e r i n ga n a l y s i si so n eo ft h em a i nt e c h n o l o g y m e a s u r e si nt h er e s e a r c ho nd a t am i n i n gw i t ham a s so ft h e o r i e sa n d m e t h o d sa c h i e v e d w i t ht h ee s t a b l i s h m e n to fd e c i s i o ns u p p o r ts y s t e m s u c ha sd a t aw a r e h o u s ea n dt h er e q u i r e m e n to fb u s i n e s si n t e l l i g e n c ei n t h ed a t ai n t e n s i v ee n t e r p r i s e s ，d a t am i n i n gh a sb e e nu s e di nm a n yn e w a p p l i c a t i o n sa n dt h er e s e a r c ho nd a t ac l u s t e r i n gi sf a c e dw i t hal o to f n e w c h a l l e n g e s c d ni so n eo ft h et y p i c a ld a t ai n t e n s i v ew e bs i t e ，d i v i d i n gt h e c u s t o m e r sa n ds u p p l y i n gd i f f e r e n te d g es e r v e r st od i f f e r e n tu s e r sc l u s t e r s h a sa l r e a d yb e c o m ei n s t a n td e m a n dt oi m p r o v ec d n sp e r f o r m a n c e a n e wa l g o r i t h mc l u s t e r i n gt h ed a t as e t sw i t hm i x e dn u m e r i c a la n d 北京邮电大学硕士学位论文 c a t e g o r i c a l v a l u e si sr e s e a r c h e db a s e do nt h er e q u i r e m e n to fu s e r s s e g m e n t a t i o na n dt h ec h a r a c t e r i s t i co f t h ed a t ai nt h ec d n a p p l i c a t i o ni s p r o p o s e di nt h ep a p e r o nt h ec o n d i t i o no fn o tu s et h i r d - p a r t ys o r w a r ei nt h ec l i e n t s i d e ， t h ep a p e rr e s e a r c h e st h eo p t i m i z a t i o nt e c h n o l o g yo ft h ec d n sr o u t e ， r a i s e san e wo p t i m i z a t i o np r o g r a mo ft h ec d n sr o u t e ，a n dr e s e a r c h e s c l u s t e r i n ga l g o r i t h m i su s e di nd i v i s i o no ft h ec d n su s e r s i nt h i sp a p e r , t h er e s e a r c hi ss u m m a r i z e da sf o l l o w s ： 1 t h et e c h n o l o g yo fc d na n dt h er o u t i n gs y s t e ma r ei n t r o d u c e d b f i e f l mw i t he m p h a s i so nt h em e t h o d so fb a s e dd n sr e d i r e c t i o n ，h t r p r e d i r e c t i o na n dt h ew a n t r i a n g u l a rr e d i r e c t ，w h i c ha r et h em e t h o d so f t h e g l o b a ll o a db a l a n c i n g a l s o ，t h ea d v a n t a g e sa n dd i s a d v a n t a g e so f r e d i r e c t m e t h o d sa lec o n c e r n e d 2 c l i e n t - s i d ep r o b e st e c h n o l o g yi ss t u d i e d a n di nt h el i g h to ft h e l a c ko ft h ec u r r e n tc d nr o u t i n gt e c h n o l o g y , t h ec o m b i n a t i o no ft h e g l o b a ll o a db a l a n c i n gt e c h n o l o g ya n d t h ec l i e n t - s i d ep r o b e st e c h n o l o g yi s t oe x p o u n da n dp r o v e 3 s t u d i e dd a t am i n i n gt e c h n o l o g y , e s p e c i a l l yw e bd a t am i n i n g t e c h n o l o g y , a n ds u m m e du pw e bd a t am i n i n gt e c h n o l o g yd e v e l o p m e n t d i r e c t i o n 4 t h e a p p l i c a t i o n o fc l u s t e r i n g t e c h n o l o g y i nc d nu s e r s s e g m e n t a t i o ni sr e s e a r c h e d a n dd i s c u s s e st h eb a s i ct h e o r yo fc u s t o m e r s e g m e n t a t i o n ，m e t h o d sa n dp r o c e s s c d n a p p l i c a t i o n sa r eu s e dm o r ea n dm o r ew i d e l y a n di tc a ns o l v e t h ep r o b l e mo fi n s u f f i c i e n tn e t w o r kb a n d w i d t h c d nw h i c hm e e t st h e p e o p l e sn e e d sw i l lu s h e rab e t t e rd e v e l o p m e n to p p o r t u n i t i e s s ot h a tt h e c o m b i n a t i o no fd a t am i n i n gt e c h n o l o g ya n dc d nc o n t e n tr o u t i n g t e c h n o l o g y , w h i c h i s d i r e c t l ya p p l i e do nt h en e wc o n t e n tr o u t i n g t e c h n o l o g y , w i l la l s ob e t t e rr e f l e c tt h ep r a c t i c a lv a l u ea n di t sr e f e r e n c e v a l u e k e yw o r d s ：r o u t i n go p t i m i z a t i o n g l o b a ll o a db a l a n c i n g c l i e n t s i d e p r o b e s u s e r sc l u s t e r i n gd a t am i n i n g c l u s t e r i n ga l g o r i t h m 北京邮电大学硕士学位论文 独锚健( 或创耨性) 声骥 本天声明所呈交的论文是本人在导师撂导下进行的研究工作及取得的研究 藏果。尽我浙知，除了文串特别秀嚣以标注稗致谢中所罗列的蠹容戮静，论文孛不 包含其他人融经发表缄撰写过的研究成果，也不包含为获褥j | ：京邮咆大学或其他 教育桃擒静学健或涯书霸使霸避鳃材辩。与我一溺王襻的藏恚对本研究所徽昀任 何爨献均已在论文孛摊了明确的说明并袭示了谢意。 枣请学位论文与资料著有不实之处，本久承摆甥福关责任。 本人签名卜 荔量金。 麓麓： 放翌- 菇：。 关于论文镬溺授权酶说嬲 学位论文谗者完全了解裁索蓐邀大学翥关傺餐翻镬髑学健论文瓣规定，r p - 研究裳在校攻读学位期阕论文羔侔的知识产权单饿属北京邮电大学。学校有权保 蜜并囊国家有关部门或桃糗送交论文的复洋簧和磁盘，允许学位论文被查阅秘借 阕；学校可戮公布学链论文的垒部或部分内容，w 以允诲采用影帮、缩印或其它 复制手段保存、汇编学挺论文。( 绦密的学位论文在解密焉遵守此攥定) 傺密论文注释：本学链论文满于保密在年解密惹适用本授权书。霉傺密论 文注释：本学健论文不属于保密范围，适用本授权稍。 本夫签名；墨叁筮 。露期：2 遵：勉。芝 导癖签褒： 委痢建奎迭名。豳嬲：圣鳟：查箜。，。 北京邮电大学硕士学位论文 第一章绪论弟一阜殖y 匕 本章主要介绍了c d n 1 】产生的背景、具体定义，现状和发展，简述了c d n 内容路由系统和数据挖掘技术和现状，最后介绍了论文背景、主要工作，论文结 构和创新点。 1 1 论文的研究背景 随着计算机和网络的飞速发展和扩展普及，据c c n i c 调查统计，至2 0 0 8 年6 月为止，上网用户总人数为2 5 3 亿，国内网站数量约为1 9 1 9 万个，上网计 算机数8 4 7 0 万台【2 】。上网的用户数越来越多w e b 站点的数量继续在增加，可供 访问的资源日趋丰富，特别是文本、图像、音乐、广告、流媒体动画等大量涌现， 使得目前的互联网时代日趋庞大和完善，已经成为日常生活重要的一部分，但是 也使得潜伏的一系列问题激化显现出来。 2 0 0 5 0 62 0 0 5 1 22 0 0 6 2 0 1 22 0 0 7 2 0 0 7 1 22 0 0 8 图卜1中国网民人数增长情况 有图1 1 可以看出，用户数量和信息量在快速增长，从而带来网上业务量成 倍递增，造成了对网络带宽的大量需求，并且网络访问的延迟与等待总是普遍存 在，这些情况导致了网络拥塞，服务器过载，网上应用等待时间过长等诸多问题， 使整个互联网内容传送性能下降。 如何缓解网络拥塞，提高用户获取信息的速度，成为困扰众多企业和服务商 的一大难题。依靠增加带宽来解决这一问题是一个方面，另外它还受到传输途中 的路由阻塞和延迟、网站服务器的处理能力等因素的影响，并且和访问者与网站 服务器之间的距离有密切的关系。因此，即使各个i s p 将网络带宽加大后，如果 0 5 0 5 o 5 0 3 2 2 1 1 0 0 北京邮电大学硕士学位论文 访问者和网站之间的距离较远，它们之间的通信一样需要经过重重的路由转发和 处理，网络延误不可避免。而用户对网络系统性能的要求越来越高，如对访问的 响应时间、服务提供的可靠性等要求。 在1 9 9 8 年，美国麻省理工学院的一批研究生，提出了一套能够实现用户就 近访问的解决方案，设计并实现了该系统。在2 0 0 0 年建立了世界第一家提供商 用c d n 服务的专业技术公司a k a m a i ，为y a h o o 提供专业服务。其运作模式可 以这样理解：y a h o o 作为“内容制造者 在网络的位置不变，而a k a m f i 相当于 “专业的邮递公司一，它选择适当的位置，安装一系列设备建立若干“邮局一， 帮助y a h o o 把内容传输到网络中有需求的任意角落。这样一来，y a h o o 不必设立 自己的镜像站点，从传输内容的重负中解脱出来，而用户可以就近访问“邮局一 获取内容，使得y a h o o 和用户都得到了极大的方便。从此c d n 技术就开始受到 广泛关注并快速发展，逐步成为i n t e r n e t 中的一项重要服务。据统计，采用c d n 技术，能处理整个网站页面7 0 - 9 5 的内容访问量，减轻服务器的压力，提 升网站的性能和可扩展性。 c d n 目前在国内外大型网站已得到普式应用，具有良好的应用效果和长远 的发展前景。 数据挖掘( d a t am i n i n g ，简称d m ) 技术依靠计算机的强大运算能力，不但可 以解决如何在海量数据中提取出有用数据或者信息的问题，而且还有可能通过适 当的算法设计，提供解决传统c d n 用户集群划分存在问题的有效途径。数据挖 掘还是一种重要的数据分析方法，是知识发现( k n o w l e d g ed i s c o v e r yo f d a t a b a s e ， 简称i d ) 过程中的一个关键步骤，是当前涉及人工智能和数据库等学科的一 个相当活跃的研究领域。它旨在发现庞大的数据中隐藏着的、先前未知并潜在有 用的模式和信息，以帮助人们正确理解和认识数据，进行科学决策。 1 2c d n 、数据挖掘概述 1 2 1c 州简介 c d n 是一种新型的网络构建方式，它是为能在传统的p 网发布多媒体信息 而特别优化的网络覆盖层；而从广义的角度，c d n 代表了一种基于质量与秩序 的网络服务模式。简单地说，内容发布网是一个经策略性部署的整体系统，包括 分布式存储、负载均衡、网络请求的重定向和内容管理4 个要件，而内容管理和 全局的网络流量管理是c d n 的核心所在。通过用户就近性和服务器负载的判断， c d n 确保内容以一种极为高效的方式为用户的请求提供服务。总的来说，内容 服务基于缓存服务器，也称作代理缓存，它位于网络的边缘，距用户仅有“一跳一 2 北京邮电大学硕士学位论文 之遥。同时，代理缓存是内容提供商源服务器的一个透明镜像。这样的架构使得 c d n 服务提供商能够代表他们的客户，即内容供应商，向最终用户提供尽可能 好的体验。 c d n 网络的建设主要有企业建设的c d n 网络，为企业服务；l d c 的c d n 网络，主要服务于i d c 和增值服务；网络运营商主建的c d n 网络，主要提供内 容推送服务；c d n 网络服务商，专门建设的c d n 用于做服务，用户通过与c d n 机构进行合作，c d n 负责信息传递工作，保证信息正常传输，维护传送网络， 而网站只需要内容维护，不再需要考虑流量问题。为网络的快速、安全、稳定、 可扩展等方面提供保障。 用户访问传统的站点的一般过程为： 1 ) 用户向浏览器提供要访问的域名； 2 ) 浏览器调用域名解析函数库对域名进行解析，以得到此域名对应的m 地 址： 3 ) 浏览器使用所得到的疋地址，域名的服务主机发出数据访问请求； 4 ) 浏览器根据域名主机返回的数据显示网页的内容。 通过以上四个步骤，浏览器完成从用户处接收用户要访问的域名到从域名服 务主机处获取数据的整个过程。c d n 网络是在用户和服务器之间增加c a c h e 层， 如何将用户的请求引导到c a c h e 上获得源服务器的数据，主要是通过接管d n s 实现，使用 c d n 缓存后的网站的过程如下： 1 ) 用户向浏览器提供要访问的域名； 2 ) 浏览器调用域名解析库对域名进行解析，由于c d n 对域名解析过程进 行了调整，所以解析函数库一般得到的是该域名对应的c n a m e 记录，为了得 到实际口地址，浏览器需要再次对获得的c n a m e 域名进行解析以得到实际的 m 地址；在此过程中，使用的全局负载均衡口1d n s 解析，如根据地理位置信息 解析对应的m 地址，使得用户能就近访问； 3 ) 此次解析得到c d n 缓存服务器的口地址，浏览器在得到实际的i p 地址 以后，向缓存服务器发出访问请求； 4 ) 缓存服务器根据浏览器提供的要访问的域名，通过c a c h e 内部专用d n s 解析得到此域名的实际口地址，再由缓存服务器向此实际p 地址提交访问请求； 5 ) 缓存服务器从实际i p 地址得得到内容以后，一方面在本地进行保存，以 备以后使用，二方面把获取的数据返回给客户端，完成数据服务过程； 6 ) 客户端得到由缓存服务器返回的数据以后显示出并完成整个浏览的数据 请求过程。 北京邮电大学硕士学位论文 当用户访问加入c d n 服务的网站时，域名解析请求将最终交给全局负载均 衡d n s 进行处理。全局负载均衡d n s 通过一组预先定义好的策略，将当时最接 近用户的节点地址提供给用户，使用户能够得到快速的服务。同时，它还与分布 在世界各地的所有c d n c 节点保持通信，搜集各节点的通信状态，确保不将用 户的请求分配到不可用的c d n 节点上，实际上是通过d n s 做全局负载均衡。 对于普通的i n t e m e t 用户来讲，每个c d n 节点就相当于一个放置在它周围 的w e b 服务器。通过全局负载均衡d n s 的控制，用户的请求被透明地指向离 他最近的节点，节点中c d n 服务器会像网站的原始服务器一样，响应用户的请 求。由于它离用户更近，因而响应时间必然更快。对于源站来说，通过将不同地 区用户分发到最近的c d n 节点访问，大大减轻源站的访问压力，节省带宽，同 时也提高了用户的访问质量。 随着网络技术的发展，现有的各种网络，如数据网、电信网、移动网以及广 播电视网都将融入下一代网络( n g n ) 即一个以m 为基础的覆盖各种资源的网 络。那时，网络上的应用将更加丰富，同时也只有将用户需要访问的内容尽可能 分布到离用户最近的地方才能有效地提高网络的利用率，为用户提供更高品质的 服务，而这些都为c d n 提供了无限的发展空间。 此外，各种国际标准化组织也不断推出新的技术和协议标准来保证c d n 技 术支持的应用服务的发展，如e s i ( e d g es i d ei n c l u d e s ) 4 1 技术，以及r u p ( r e s o u r c eu p d a t ep r o t o c 0 1 ) ，o p e s ( o p e np l u g g a b l ee x t e n s i o ns e r v i c e s ) ，i c a p ( i n t e r n e tc o n t e n ta d a p t a t i o np r o t o c 0 1 ) 等协议标准，使c d n 能支持更多更丰富 的应用服务，如内容过滤、广告插播等。 目前i e t e 在c d n 方面已陆续发布了一系列相关的标准，主要有：i e t e r f c 3 0 4 0 ( 2 0 0 1 ) i n t e m e tw e b 复制和缓存分类、i e t fr f c 3 4 6 6 ( 2 0 0 3 ) 内容互 联( c d i ) 模型、i e t fr f c 3 5 6 8 ( 2 0 0 3 ) 已知内容网络( c n ) 内容路由机制【5 1 、 i e t fr f c 3 5 7 0 ( 2 0 0 3 ) 内容互联( c d i ) 场景等，分别规定了才c d n 的模型、 应用场景、复制和缓存分类以及内容路由机制等方面的技术内容。 可以肯定，c d n 技术将随着网络技术的发展而不断发展，并成为i n t e m e t 及将来n g n 网络中不可分割的一部分。 1 2 2 内容路由系统简介 c d n 内容路由指的是把用户的内容请求重定向，或者说，。路由刀到离用 户最近的内容服务器。 c d n 内容路由器负责内容路由，为用户的请求选择最佳的访问站点。它以 现有的网络为基础，支撑点依然是现有p 路由机制。图1 2 表明了c d n 路 4 北京邮电大学硕士学位论文 由、口路由和用户内容请求的层次关系。我们把c d n 路由所处的层次形象地称 为“内容层 。内容层充分利用现有的碑核心路由网络，通过特定的内容路由 策略，为用户的内容请求选择最佳的内容服务器，完成内容的重定向。 c o n t e n tr e g l u e a t ic 。nr 删惦 i pc 0 r o u t e ( 狰核心路由) 图1 - 2内容路由层次图 内容服务的内容路由机带t l ( r r s ，r e q u e s tr o u t i n gs y s t e m ) 是c d n 网络规划中 最关键的因素之一，它的设计直接关系到c d n 的核心思想：就近服务。这一点 也是本论文需要做的主要工作。 1 2 3 数据挖掘技术简介 随着互联网的发展，并伴随数据库技术的进步，人们工作及生活中需要处理 的数据信息激增。数据的增长速度远远超出了人们分析处理的能力，造成“数据 丰富而信息贫乏”的困境，而数据背后隐藏着许多重要的信息，人们希望能够对 其进行更高层次的分析，以便更好地利用这些数据。数据挖掘( d a t am i n i n g ) 卅的 概念应运而生，其实际作用便是从大量的数据信息中发现人们所需要的高层次知 识。数据挖掘在初始便是由知识发现演化而来，处理这些数据又需要强有力的数 据库建模支持。因此，知识发现的初始意义便是k d d ( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) ，就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提 取隐含在其中的、人们不可预知的、形象而高度归纳的有用信息。 数据挖掘可以看成是一种数据从源头至用户前台的动态过程，通过自动分析 数据源，进行数据归纳、规则推理，从而挖掘出潜在的数据规律及动态模式。对 于数据挖掘需要处理的原始数据，可以是结构化的，如关系数据库中的数据，也 可以是半结构化的，如文本、图形、图像数据，还可以是分布在网络上的异构型 数据，如w e b 中的格式化网页及半结构化对象。对于数据分析处理从而发现知 识的方法，可以是数学的，也可以是其他交叉学科的；还可以是演绎的，归纳的。 5 北京邮电大学硕士学位论文 对于知识发现的结果，可以用于信息管理、查询优化、决策支持、过程控制等， 还可以用于数据自身的清理维护。 国三丽 嬲 一 ( _ 1 i j 三铲哩 图卜3 数据挖掘过程模型图 可以预见，数据挖掘是一个需要经过多次反复的处理过程。从数据挖掘进入 工程应用领域起，就有人对数据挖掘的过程进行归纳和总结，提出了不同的数据 挖掘处理过程模型。其中u s a m am f a y y a d 、g r e g o r yp i a t e t s k y - s h a p i r o 等人给出 的多处理阶段模型是一种通用模型，也是最广为接受的一种处理模型。如图1 3 所示的过程模型图在数据挖掘领域被多次引用。 数据挖掘是知识发现的一个主要步骤，知识发现的步骤包括：数据准备、数 据预处理、数据挖掘、模式评估、知识表示。整个知识发现过程不仅仅是图片所 示简单的线性流程，步骤之间其实包含了循环反复。 1 3 论文主要工作和创新点 1 3 1 主要工作 在本课题中，本人根据第一视频网站目前所使用的c d n 网络存在的一些问 题，结合我们对国内外c d n 网络建设和使用中的一些先进技术手段和相关解决 方案的研究，提出c d n 内容路由优化的解决方案。主要做了如下三个方面的工 作： 1 研究c d n 网络构架，并重点研究c d n 内容路由的实现技术：全局负载 均衡技术和基于客户端探测的技术； 2 提出并论证了全局负载均衡技术和基于客户端探测技术相结合的新技 术； 3 研究数据挖掘技术中的聚类算法，并提出其在c d n 用户集群划分中的 应用。 6 北京邮电大学硕士学位论文 1 3 2 创新点 本课题的创新之处在于包含了以下几点： 1 提出全局负载均衡技术【7 】和客户端探测技术喁1 相结合的内容路由方案。 2 运用数据挖掘算法进行c d n 用户集群，能从客户端探测结果，随时更 新维护全局负载均衡时的内容路由表，使用户请求重定向到更精确的边 缘服务器，提高服务命中率。 3 提出内容路由优化实现技术客户端无需安装额外的第三方软件，使c d n 在提高访问命中率的同时，更具有灵活性。 1 4 论文的结构 第一章主要介绍了论文的研究背景，简述c d n 的概念、产生的背景、现状 和发展，简述了c d n 内容路由系统和数据挖掘技术，最后介绍了主要工作、创新 点和论文结构。 第二章介绍了本文用到的主要技术：全局负载均衡技术，基于客户端探测技 术，数据挖掘技术和w c b 数据挖掘技术及其聚类算法，这些均是实现基于客户端 探测技术的全局负载均衡方案和用户集群划分的重要技术。 第三章主要讨论了基于客户端探测技术的全局负载均衡方案，包括客户端探 测技术、全局负载均衡和客户端探测技术。 第四章介绍数据挖掘技术在c d n 用户集群划分中的应用。 第五章是总结与展望。 其中第三章到第五章是本课题研究的主要内容。 7 北京郝电大学顶学口论i 第二章相关技术介绍 从全局负载均衡技术和客户端探测的技术相结台内容路由方案( 详见第三章 和第四章) 可知本论文要用到的主要技术：全局负载均衡技术，客户端探测技术， 数据挖掘聚类算法，用户集群划分。 在本章会分别简单介绍以上新方案的各项重要实现技术。 21 c d n 网络构架、关键技术和设计原则 c d n 本身包含的内容比较多，这里只足概要介绍和本课题紧密相关部分 2 11 c o n 的网络构架组成 根据网络拓扑结构，一般的大型c n d 都是分级部署。目前流行的c d n 结 构分为两种一种是只包括核心层和分布层的两级结构，该结构中的用户智能重 定向一般使用d n s 重定向的全局负载均衡算法。另一种三级结构，则包括核心 层、骨干层和分布层。 本论文中研究的c d n 网络结构是采用两级结构，只包括核心层和分布层的 两级结构( 如图2 - 1 ) 。核心层包括中心服务器和全局负载均衡设备等，分布层 包括边缘服务器和本地负载均衡设备及用户设备等( 如图2 - 1 所示) 。 i i 盈u 国。国 h 。 国。国 北京邮电大学硕士学位论文 图2 - 1c d n 网路的架构组成 图中g s l b 表示全局负载均衡设备，s l b 表示本地负载均衡设备，表示g s l b 与s l b 之间的控制通道 有图2 - 1 可知，c d n 主要有以下几个部件组成： ( 1 ) 中心服务器( c e n t e rs e r v e r ) c s ( c e n t e rs e r v e r ) 逻辑上只有一个服务器，实际上是有多个服务器组成的 一个集群，它依照一定的策略( 如负载等) ，把用户的请求分配到集群中的各个 中心服务器。 c s 的作用：1 ) 配合全局负载均衡设备负责所有用户的内容请求，根据用户 的信息做出准确的用户就近性判断，并根据判断的结果，将用户的请求分发到指 定的边缘服务器节点。2 ) 负责c d n 的内容分发管理，把需要服务的内容通过 合适的格式和方式，分发到所有的边缘c d n 服务器。 ( 2 ) 边缘服务器e s ( e d g es e r v e r ) e s 用于缓存内容实体和对缓存内容进行组织和管理。当有用户访问该客户 内容时，直接由各缓存服务器响应用户的请求。 ( 3 ) 本地负载均衡s l b ( s e r v e rl o a db a l a n c e ) 位于c d n 接入点，除配合完成全局的负载均衡之外，负责内容服务引擎的 负载平衡及业务服务的访问控制。 ( 4 ) 全局负载均衡g s l b ( g l o b a ls e r v e rl o a db a l a n c e ) 负责通过静态或动态的方式为用户的请求选择最佳的访问站点。全局负载均 衡设备实现c d n 全网各边缘服务器节点之间的资源负载均衡，它与各节点的本 地负载均衡设备保持通信，搜集各节点缓存设备的健康状态、性能、负载等，自 动将用户指引到位于其地理区域中的边缘服务器或者引导用户离开拥挤的网络 和边缘服务器。还可以通过使用多站点的内容和服务来提高容错性和可用性，防 止因本地网或区域网络中断、断电或自然灾害而导致的故障。全局负载均衡设备 一般依照一些标准将用户的请求转到最优边缘服务器，从而为其提供更好的服 务。这些标准可以是g 站点的健康状况、站点距离和检索指定内容所需的响应时 间等。 2 1 2c o n 的关键技术 c d n 的关键技术主要有内容路由技术、内容分发技术、内容存储技术、内 容管理技术等。 ( 1 ) 内容路由技术 内容路由技术的作用是将用户请求导向整个c d n 网络中的最佳e s 。最佳 9 北京邮电大学硕士学位论文 e s 的选择可以运用多种评估策略来实现，例如用户与服务器距离最近、服务器 负载最轻等。这是c d n 的核心，它决定了整个c d n 的效率和性能。内容路由 技术可以通过多种方法实现，包括d n s 、应用层重定向、传输层重定向等。 ( 2 ) 内容分发技术 内容分发技术指将内容从源到复制缓存到e s 的过程。从实现上看，有两种 主流的分发技术：p u s h 和p u l l 。p u s h 是一种主动分发的技术。通常，p u s h 由内容管理系统发起，将内容从源或者中心媒体资源库分发到e s 。分发的协议 可以采用h t t p 、f t p 、r s t p 等。对于p u s h 分发需要考虑的主要问题是分发 策略，即在什么时候分发什么内容，可以根据用户访问的统计信息，以及预定义 的内容分发规则来确定。 p u l l 是一种被动的分发技术，p u l l 分发通常由用户请求驱动。当用户请 求的内容在本地的e s 上不存在时，c a c h e 启动p u l l 方法从内容源或者其他e s 实时获取内容。在p u l l 方式下，内容的分发是按需的。 在内容分发的过程中，对于e s 设备而言，关键的是需要建立内容源u r l 、 内容发布的u r l 、用户访问的u r l ，以及内容在e s 中存储的位置之间的映射 关系。 ( 3 ) 内容存储技术 对于c d n 系统而言，需要考虑两个方面的内容存储问题。一个是内容源的 存储，一个是内容在e s 中的存储。对存储性能的要求是吞吐量大、可靠性和稳 定性。 ( 4 ) 内容管理技术 本地内容管理主要针对一个c d n 节点( 由多个e s 设备和一个本地负载均衡 设备构成) 进行，即决定c d n 节点中应该存储何种资源以及如何进行节点内容更 新。 2 1 3o d n 系统的设计原则 内容分发网络( c d n ) 的发展与应用本地负载均衡的主要目标是提高内容服 务的效率，提高边缘节点的存储利用率。通过本地负载均衡管理，可以在c d n 边缘节点实现基于内容感知的调度，通过内容感知的调度，可以避免将用户重定 向到没有该内容的c a c h e 设备上，从而提高负载均衡的效率。通过本地负载均衡 管理还可以有效地实现在c d n 边缘节点内容的存储共享，提高存储空间的利用 率。 为了提高访问服务质量，设计c d n 系统，应该综合考虑以下要求： ( 1 ) 安全可靠性：为保证将来的业务应用，网络必须具有高可靠性。可以 1 0 北京邮电大学硕士学位论文 在采用硬件备份、冗余等可靠性技术的基础上，采用相关的软件技术，提供较强 的管理机制、控制手段、事故监控和网络安全保密等技术措施，提高网络系统的 安全可靠性。 ( 2 ) 灵活性和可扩展性l 网络系统是一个不断发展的系统，所以它必须具 有良好的扩展性。能够根据将来信息化的不断深入发展的需要，方便地扩展网络 覆盖范围、扩大网络容量和提高网络各层次节点的功能。 ( 3 ) 开放性：具备与多种协议计算机通信网络互连互通的特性，确保网络 系统基础设施的作用可以充分发挥。 ( 4 ) 可管理性：能够实现监控、监测整个网络的运行状况，合理分配网络 资源、动态配置网络负载，可以迅速确定网络故障等。 2 2 全局负载均衡技术 c d n 是一个经过一定策略部署的整体系统。通过用户就近性和服务器负载 的判断，c d n 确保内容以一种极为高效的方式为用户的请求提供服务。总的来 说，被选择的边缘服务器，最理想状况是距用户仅有。一跳一( s i n g l eh o p ) 之遥。 其中，内容路由系统是c d n 架构中至关重要的组成部分。因为它需要根据 用户的请求以及边缘服务器的状态信息决策判断，从而选取最佳的边缘服务器。 由此可见，设计有效的内容路由系统是提升c d n 整体性能的关键。而全局负载 均衡又是实现内容路由系统的关键技术。 2 2 1 负载均衡简介 负载均衡技术就是将网络的流量尽可能均匀地分配到几个能完成相同任务 的服务器或网络节点上去执行和处理，从而避免部分网络节点过载而另一部分节 点空闲的不利状况。这既可以提高网络流量，又可以提高网络的整体性能。c d n 中的负载均衡技术主要有两种： ( 1 ) 全局负载均衡技术 全局负载均衡的主要目的是在整个网络范围内实现将用户的请求定向到最 近的节点或者区域。因此，全局负载均衡的主要功能是实现就近性判断，全局负 载均衡技术是整个c d n 系统的关键技术，采用先进的第四层交换技术。它包含 以下三个要素：( 1 ) 网络就近性；包括各c d n 节点到用户端的总跳数、各c d n 节点到用户端的延时、静态就近性列表、动态就近性判断机制。( 2 ) 最佳c d n 节 点的选择需考虑节点负载最低，就近性及节点的设计容。( 3 ) 全局负载均衡算法( 内 容路由的方法) ：d n s 重定向、h t r p 重定向、全局三角重定向等。 北京邮电大学硕士学位论文 ( 2 ) 本地负载均衡技术 和全局负载均衡相比，本地负载均衡一般局限于一定的区域范围内。本地负 载均衡侧重于根据c d n 节点的健康性、负载情况、策略等进行精细的负载均衡。 因此，本地负载均衡设备一般需要了解c d n 节点的具体运行状况作为执行本地 负载均衡的依据。本地负载均衡有多种