通信首页 | 产品超市 | 资讯 | 技术 | 行业研究 | 访谈 | 专题 | 社区 | 展会 | 政策法规 | 综述
3G | NGN | VoIP | IPTV | 手机电视 | 路由器 | 交换机 | 布线 | 安全 | 服务器 | UPS | 音乐手机
慧聪网首页 > 通信行业 > 技术文章 > 通信运营
行业搜索
CDN网络分发算法及仿真的研究
2006年5月19日 9:59  来源:中国新通信  作者:马惟哲
  1 引言

  网络信息传递性能的日益恶化日渐成为Internet发展的瓶颈。改善Internet性能的方案之一就是采用CDN(Content Delivery Network),即内容分发网络技术。CDN的基本思路就是通过在Internet网络结构中增加一个完善、全面的中间层,利用缓存、复制、负载平衡和DNS重定向等技术,实时处理网络流量和各节点的负载状况,将用户的请求导向最近的服务节点上,用户就近取得所需的内容,从而解决网络拥塞、提高上网访问的总体性能。

  2 CDN的主要技术

  CDN网络中客户的内容请求通过全局内容路由到达某个内容交换机,由交换机将请求的内容分发到距用户最近的网络边缘节点,即内容缓存服务器上,同时也将客户的请求重定向到边缘节点,改善用户的访问效果。

  CDN的主要技术有内容路由、内容分发等。内容路由包括如DNS重定向、名称路由、4-7层交换等技术,将客户的请求路由到最合适的内容服务器上,使网络性能达到最佳。内容分发解决整个CDN系统中内容的编码、管理、安全和边缘分送,根据实际的网络流量和服务器负荷状况,将用户的请求在不同服务器之间合理分配,实现内容服务器负载均衡,提高内容缓存的命中率,降低客户的访问延时。这些主要技术的实现离不开性能优良的CDN分发算法的支持,分发算法对系统性能和系统的可展性产生直接的影响。

  3 CDN的分发算法

  3.1 分发算法的分类

  CDN的分发算法有多种不同的分类方法。根据交换机工作的层次分为第4层和第7层分发算法;根据交换机在作出分发决定时是否考虑系统状态信息分为静态和动态算法;根据交换机使用信息的来源分为客户状态、服务器状态和客户/服务器状态算法。图1总结了分发算法的之间的关系。


  本文将对CDN的一些典型分发算法,包括WRR、URL Hashing和LARD进行研究,通过进行仿真实验对上述算法在系统吞吐量、缓存命中率、平均请求延时以及节点未利用率等四个方面的性能进行比较,以加深对分发算法的理解。

  3.2 WRR算法

  轮询(Round-Robin)算法属于第四层的静态算法,使用一个循环列表来作分发决定,若Si是最后选择的节点,则新的请求将被分配到Si+1节点,其中i+1=(i+1) mod N,N为后端服务器的数目。轮询算法可以根据服务器的容量设置不同的分发概率进行扩展。Ci表示服务器的容量,其相对容量定义为ξi=Ci/max( C ),max( C )是所有服务器中的最大容量。轮询算法产生一个随机数e(0≤e≤1),假设Si是最后一个选择的服务器,只有当e≤ξ时请求才分发到Si+1服务器。否则,Si+2将成为下一个候选,并依此类推(即产生另一个随机数与Si+2的相对容量比较)。

  静态加权轮询(WRR,Weighted Round Robin)是轮询算法的一个变种,它为每个服务器设置一个权重Wi表示其容量, Wi=Ci/min( C ),其中min( C )是所有服务器的最小容量,然后根据服务器的权重产生分发次序。

  3.3 URL Hashing算法

  URL Hashing算法是一种典型的缓存绑定算法,是从OSI网络模型第7层获取请求的内容信息的动态算法。算法根据内容来决定请求的分发,把相同内容请求分发到相同的服务器上,提高服务器缓存的命中率,这就是所谓的相同内容服务位置一致性。算法维护的hash表记录了内容和后端服务器的一一对应关系,依据请求数据包的URL信息来决定为该请求服务的服务器,以实现高的相同内容请求服务位置一致性。

  3.4 LARD算法

  LARD(Locality-Aware Request Distribution)算法的基本原则是将所有相同内容请求分发到提供相关内容的同一服务器,使客户请求的内容尽可能在服务器的缓存中找到。算法维护一个服务内容与后端服务节点集的映射表,算法为内容请求分配一个负载最轻的服务器。当请求内容节点集在K秒时间里发生了负载不均衡,则重新维护映射表。

  判断服务器是否严重负载不均衡的关键参数是Tlow和Thigh。若某个服务器的负载高于Thigh,而服务器群中还有负载低于Tlow的,那么负载高于Thigh的服务器把部分连接转移到负载低于Tlow的服务器中去。若某个服务器的负载高于2倍的Thigh时,负载高于2倍Thigh的服务器将把部分请求转移到系统中最低负载的服务器中去。

  如果不限制系统中的总有效连接数,可能所有服务器的负载都将达到2 Thigh。为了防止这种情况的发生,要限制系统中总的有效连接数,假设后端服务器节点数为n,那么最大总有效连接数L=(n-1)* Thigh+Tlow -1。这样,系统中肯定存在负载低于Thigh的节点,那么发生连接转移时,能确保连接转移前的服务器和连接转移后的服务器的不均衡度最小为Thigh -Tlow,最大不会大于2Thigh - Tlow。

  设置合适的Tlow值,依赖于后端服务器节点的服务速度。Tlow值应该尽量高,以避免服务器资源闲置,提高系统的吞吐量。在Tlow取定值的情况下,如果Thigh-Tlow的值小,可以限制不同后端服务器之间的服务延时差距,如果Thigh-Tlow的值大,可以在保证相同内容服务位置一致性的情况下限制负载不均衡度和短期的负载差距波动。因此在对请求延时影响不大的情况下,Thigh应尽可能设得大。假设已知Tlow,最大和最小请求延时的差为D,平均请求延时为R,那么为了有效的确保Thigh,Thigh应设为(Tlow+D/R)/2。

  4 仿真实验与性能比较

  4.1 仿真实验的配置

  对上述三种算法进行性能比较的仿真实验在PⅢ 800MHz的计算机上进行,操作系统为Red Hat Linux 7.0。仿真模型中,每个内容缓存服务器都配置了一个带2级高速缓存的800MHZ PIII CPU、一个突发传输速率为10MB/S的硬盘。连接建立和连接拆除耗CPU时间145us,高速缓存的传输速率为每512字节耗时40us。由于是研究客户请求的分发算法,在不影响仿真性能的条件下,做了以下两个合理的假设:第一,不考虑转发机制所带来的各种不同的延时,即统一将交换机转发请求到内容服务器的延时设为0;第二,连接交换机和内容服务器的网络有无限的带宽,对请求延时没有影响,也就是说服务的瓶颈只可能出现在内容服务器上。仿真实验用到的参数如后所列:CPU处理延时0.145 ms;硬盘突发传输速率105us/KB;最大连接数10;Thigh 10个;高速缓存传输速率80us/KB;硬盘传输延时28 ms;Tlow 6个;缓存大小500 KB。

  4.2 仿真模型的输入

  由于研究对象是交换算法,因此可以忽略用户请求的全局路由,假设客户的请求直接到达服务器交换机,即用户产生的请求到达率成泊松分布,而该请求的内容服从zipf(齐普夫定律)分布。仿真中设置了300个文件,文件的大小随机生成,其平均值为8KB大小,并将这300个文件从0到299编号,分成30等级,即每10个文件为一个等级(0到9为第1等级,10到19为第2等级…,依次类推)。根据zip-like分布产生各个等级文件的出现概率,对同一等级的文件,按随机产生其中的一个。

  4.3 仿真结果及分析

  4.3.1 吞吐量的比较

  图2显示的是系统的节点数从1到10变化时三种算法的吞吐量的曲线,图中,△表示LARD,□表示URL Hashing,△表示WRR算法。吐量曲线表明在静态文件服务方面,第7层的LARD、URL Hashing算法明显优于第4层WRR算法,尤其当后端服务节点数多于3台的时候。这主要是因为第7层交换算法本身具有的很高的相同内容请求服务位置一致性,使得7层交换算法的高速缓存命中率要高于第4层交换算法。随着服务结点数的增加,同属于第7层算法的LARD算法的吞吐量要高于URL Hashing算法,原因是LARD算法考虑了服务器之间的负载均衡,而URL Hashing算法则没有考虑这一点,因此LARD算法的节点未利用率也要低于URL Hashing算法,如图5所示。


  4.3.2 缓存命中率的比较

  图3显示了不同数目的服务器节点情况下系统缓存命中率的变化曲线。图中显示LARD、URL Hashing的缓存命中率明显高于WRR的缓存命中率。节点数的多少对静态算法的WRR的缓存命中率几乎没影响,相比之下LARD、URL Hashing的缓存命中率则随着节点数的增加而提高,节点数增加到一定数目后LARD、URL Hashing缓存命中率变化趋缓。


  4.3.3 平均请求延时的比较

  图4显示了不同数目服务器节点情况下平均请求延时的变化曲线。由于缓存的命中率高,LARD、URL Hashing算法的平均请求延时也就大大低于WRR算法。这说明了相同内容服务位置一致性对于静态内容服务有决定性的作用,越高的相同内容服务位置一致性带来越好的性能表现。


  4.3.4 节点未利用率曲线

  图5显示了不同数目的服务器节点情况下节点未利用率的变化曲线。从图看出,LARD和WRR算法的节点未利用率要明显低于URL Hashing的,也就是LARD和WRR算法的负载均衡要好于URL Hashing的。原因是URL Hashing算法在选择服务器时,没有考虑负载均衡,而另外两个则对此作了考虑。前面已经说明了LARD算法的设计方向就是综合好的相同内容请求服务位置一致性和好的负载均衡。这里仿真数据也表明了LARD算法在这两个方面确实结合得很好,高速缓存命中率很高而节点未利用率很低。


   结束语

   决定一个算法性能好坏的两个关键因素是负载均衡性和缓存的命中率。仿真的结果表明:在不考虑交换机转发机制的情况下,第7层分发算法的吞吐量要明显高于第4层的算法,LARD算法的吞吐量最高,URL Hashing其次,WRR最低。第7层交换算法的高速缓存命中率要比第4层算法高。在负载均衡方面,URL Hashing算法最差,LARD和WRR算法相差不大。今后的研究将对CPU速度、内存大小、磁盘参数对CDN性能的影响进行研究。
 
 [热门关键词]:CDN 仿真 内容分发  发表评论    【推荐】 【打印】 【论坛

相关文章 更多 
·应用在IPTV中的CDN技术  (4.10 10:0)
·移动流媒体内容分发网络新体系结构  (1.12 10:9)
·实现CDN发布网带宽管理与QoS实现  (11.23 10:33)
我来评两句〖查看最新评论〗 
请您注意:
·遵守中华人民共和国的各项有关法律法规
·承担一切因您的行为而导致的法律责任
·本网留言板管理人员有权删除其管辖留言内容
·您在本网的留言,本网有权在网站内转载或引用
·参与本留言即表明您已经阅读并接受上述条款
昵称:匿名

文字广告
每日新闻排行
·小灵通应对移动资费竞..
·北京联通推单向收费政..
·献礼电信日 中移动5·..
·华为拟推"雇员股票计..
·手机首现单向收费 北京..
·国产手机命悬TD-SCDMA..
·国产手机首次跌破40%..
·通管局证实 北京网通已..
热点专题
北京联通今起单向收费 手机资费坚冰融化
HP商务彩色打印方案征集大赛

访谈
导航系统将成为手机标配
访宇达电通总经理李敬平先生
揭开位置服务技术的神秘面纱
访东信北邮数据业务部经理王欣
交易市场
[求购] 机柜箱
[求购] voip电话机
[求购] 村村通电话
[求购] 诺基亚手机
[求购] 接收机
[求购] 卫星地面接收机
[求购] 0形天线
每日新帖
·有没做光通讯行业渠道..
·请问中兴、华为拒绝乙..
·中通网络公司“多方通..
·巴菲特人生精华
·经典的移动通信流程实..
·3g缩略语分类[转帖]
·电信全网介绍—NISDN
·3-7-3时隙配置表
·不可小视的电信行业“..
·谈谈光缆配盘