动态副本放置算法



尽管在构建树的过程中使用DoLR来定位副本,但通信是通过IP进行的。特别地在d一树的节点间使用IP,以使父节点和子节点之间保持跟踪。此外如果客户端发出的请求导致一个新副本的放置,那么客户端的代理服务器会保存一个指向该副本的缓存指针,这就可以在代理服务器到副本之间直接对请求进行路由。缓存指针是软状态的,因为一直可以使用DOLR来定位副本。
 
1.副本放置的目标
 
副本放置的目的在于同时满足客户端延时和服务器负载的约束。客户端延时是指个客户端从SCAN系统读取信息所需要的往返时间,我们设法将其保持在预先定义的约束范围内。服务器负载是指给定服务器需要处理的通信量,假设该负载与服务器服务的用户数和d-树的子节点数直接相关,并设法使其低于一个特定的上限值。我们的目标是在满足这些约束的同时,最小化所部署的副本数量,同时保持d-树的平衡以及在更新时产生尽可能少的流量。
 
2.动态放置
 
我们的动态放置算法分为副本搜索和副本定位两个阶段。副本搜索试图找到已有的副本,并在不过载的情况下满足延时约束。如果这一步成功,则在客户端放置一个链接,并将其缓存在客户端的代理服务器上。如果没有成功,则进人副本放置阶段添加一个新的副本。
 
在副本搜索阶段,使用DOLR寻找与客户端代理服务器较近的副本,称为“入口”副本。DOLR的局部性能够确保该入口副本可以作为一个合理的备选副本与客户端进行通信。此外由于d-树已经联通,因此此入口副本可以与所有其他副本交互。这样我们可以设想存在三种搜索方式:单一的(Singular只考虑入口副本)、局部的(Localized考虑到父节点、子节点和同级节点的人口副本)及穷举的(Ex-haustive考虑所有副本)。对于一个给定的方式,我们检查所有的相关副本并在其中选择一个满足约束的副本;如果没有任何副本满足约束,则建立一个新的副本。
 
①动态技术
 
简单动态副本放置:从用户代理的服务器发送报文到入口副本时,将副本的放置限制在被DOLR路由协议访问的服务器。我们能够在没有全局IP拓扑先验知识的情况下也能定位这些服务器。DOLR的局部特性表明这些地点都适合副本的放置。考虑两种放置策略:Eager方法将副本放置在距离用户尽可能近的地方;Iazy方法将副本放置在距离用户尽可能远的地方。如果所有满足延时约束的服务器都过载,就替换一个旧的副本。如果入口服务器过载,则断开其d-树中建立时间最久的连接。
 
智能动态副本放置:该算法利用局部搜索法和Iaz放置法。我们试图使用覆盖延时来估计IP延时以便减少ping报文的数量。在这里用户可以在打开浏览器时启动一个由CDN服务提供商提供的后台程序,以便能主动地参与到这些协议中。Tapestry网的局部特性自然导致了d-树的局部性,节点和父节点之间倾向于彼此接近(用IP跳数来衡量),这就可以在分发更新时降低延时和组播带宽的消耗。与简单放置方法相比,智能放置方法消耗了较多的“加入”流量来构造了一个具有较少副本、覆盖更多客户端、具有更少的延时和组播带宽消耗的树。
 
②静态比较
 
我们知道上面给出的副本放置方法在副本的部署数量上不太可能达到最优,这是因为客户端是逐个地加入,并且对网络拓扑结构所知有限。在静态方法中,根服务器具备对网络拓扑的完整信息,并在得到所有来自客户端的请求后才放置副本,更新则是通过TP组播进行分发。静态放置方法不太符合实际情况,但是因为它可以利用用户分布情况和网络全局拓扑结构,因此反而能提供更好的性能。
 
带负载均衡的静态副本放置。现在考虑两种类型的静态副本放置方法:
 
1)IP静态。根节点具有全局IP拓扑的知识。
 
2)覆盖静态。对于每一个客户端c,根节点只知道从c到根节点,且覆盖该客户端的Tapestry路径上的服务器(以IP距离计算)。
 
前者是一种“确保不超过”的最佳放置,我们期望它产生的副本总数最少且组播流量最低;后者使用了我们能想到的最好方法来从DOLR系统收集所有的拓扑信息。
 
3.软状态树管理
 
软状态的设施有可能具有极大的鲁棒性,这是因为它们可以很容易地通过重新配置来适应各种环境。SCAN系统的目标是实现两种改进:故障恢复和性能调优。为了实现故障恢复,数据源通过d-树周期性地发送“心跳”报文。成员服务器知道心跳报文的频率,所以当它们在足够长的时间内还没有收到心跳报文时就会采取相应的措施。与上面提到的副本搜索阶段类似,这时副本会启动一个“重新加入的进程来寻找新的父节点。此外每个成员服务器定期向其父节点发送“刷新”报文。如果父节点在一定的预设时间内没有收到刷新消息,则认为与子节点的连接中断。有了这种软状态分组管理,任何SCAN服务器的崩溃都不会对CDN的总体性能产生显著的影响。性能调优包括删除节点和重新平衡化d-树。如果客户端的流量较低,则叶节点上的副本将被去除。为了平衡d-树,每个成员服务器定期地重新加入以寻找新的最佳父节点。
 
CDN互联专业提供国内外高防cdn加速服务