Optimization on content service with local search in cloud of clouds

  曾老师的这篇文章发表于Journal of Network and Computer Applications,主要解决的是利用启发式算法决定如何在cloud of clouds中进行副本分发,满足用户移动请求的大前提下,花费的服务开销最小。

     具体来说,就是数据可以只存放在一个云上,也可以在多个云上存放多个副本,副本也可以在云间进行拷贝。而实时请求来临时,既可直接从单个云读取,也可以通过网络在云间进行副本转发,将一份最新的数据副本转发至离用户最近的云中,用户从该云中获取数据。此文就是为了获得内容迁移的益处并最小化服务开销,基于本地搜索提出了几种启发式算法,利用这些算法迁移内容副本适应移动的存取请求。
     在优化cloud of clouds内容分发的过程中,首先是对整个系统进行数学建模,将问题公式化。众多云、存取点及他们之间的连接网络,构成“图”结构。将不同节点、路径、成本、请求、函数、各时刻的各种结点和请求集合,分别用不同的参数表示出来,列出副本分发的成本计算公式。这一过程主要需要的就是数学功底,图论、集合和数学建模的一些知识。不要被众多参数和公式吓到,那只是唬人的,用来说明问题而已。
     接下来就是提出解决问题的算法。就是如何分发数据和重定向请求,最节省成本。要通过对成本数学模型的分析,尝试确定最优副本分发数据函数ζ和请求重定向函数φ(可将此处函数理解为集合映射)。然而问题规模过大,问题复杂度太高,但确必须在一个合理的时间段内解决。相较于寻找最优的ζ和φ,在提出的启发式算法优化内容分发过程中将他们当做二等参数,允许内容分发机制决定是否撤销得到的二等参数。分在线和离线两种情况提出了三种启发式算法LSBS、LSGS和offline-GR,并且度量了相应算法的时间复杂度。
     最后利用Youtube上的video Trace进行了仿真实验,比较内容大小、存取周期、CSP数目对三种启发式算法成本开销及存取延迟的影响。

     有一个问题是在线算法和离线算法有什么区别,我的理解是“在线”是指决策作出时不依赖历史请求信息,“离线”是依赖历史请求数据,事后做出判断。
     
上一篇:Codeforces 833E Caramel Clouds


下一篇:End-to end provisioning of storage clouds