树形数据网格中实现副本放置的一种优化算法
|
摘要
针对树形数据网格这种分布式分层数据网格模型,提出了一种最佳副本放置算法,其中的副本数量k可以由用户指定。算法实现由2个阶段构成.在阶段1,对二叉树的全部节点以反向广度优先顺序被访问,且基于对象i的一个副本是否被放置在一个节点上,以自底向上的方式计算出包含读取成本和存储成本的总复制成本;在阶段2,基于一个递归过程,把由在阶段1计算得到的读取成本和存储成本作为输入,采取自上而下的过程放置副本,以使总复制成本最小化。理论分析和仿真实验结果表明,最佳副本放置算法不仅有较低的时间复杂度,而且在归一化放置成本、有效网络利用和本地访问百分比性能指标方面都优于目前几种典型的副本放置算法。
Aiming at the distributed hierarchical data grid model as tree data grid, an optimal replica placement algorithm is proposed in this paper, in which the number of replicas is k, which is specified by the user. The proposed algorithm consists of two phases. In phase 1,all nodes of binary tree are visited in reverse breadth-first order, and based on whether a replica of object i is placed on a node or not, the total replication cost including both read and storage cost are calculated in a bottom up manner. In phase 2, based on a recursive process, the read cost and the storage cost calculated in phase 1 are used as input, and replicas are placed using top down procedure in order to minimize the total replication cost. Theoretical analysis and simulation results show that the optimal replica placement algorithm proposed in this paper not only has the lower time complexity, but also outperforms several typical replica placement algorithms at present in terms of the normalized placement cost, effective network usage and percentage of local access.
Aiming at the distributed hierarchical data grid model as tree data grid, an optimal replica placement algorithm is proposed in this paper, in which the number of replicas is k, which is specified by the user. The proposed algorithm consists of two phases. In phase 1,all nodes of binary tree are visited in reverse breadth-first order, and based on whether a replica of object i is placed on a node or not, the total replication cost including both read and storage cost are calculated in a bottom up manner. In phase 2, based on a recursive process, the read cost and the storage cost calculated in phase 1 are used as input, and replicas are placed using top down procedure in order to minimize the total replication cost. Theoretical analysis and simulation results show that the optimal replica placement algorithm proposed in this paper not only has the lower time complexity, but also outperforms several typical replica placement algorithms at present in terms of the normalized placement cost, effective network usage and percentage of local access.
引文
[1] SELVI S,MANIMEGALAI D.Task scheduling using two-phase variable neighborhood search algorithm on heterogeneous computing and grid environments[J].Arabian Journal for Science Engineering,2015,40(3):817-844.
[2] 夏纯中,宋顺林.基于商空间的层次式数据网格资源调度算法[J].通信学报,2013,34(6):146-155.XIA CH ZH,SONG SH L.Hierarchical data grid resource allocation based on quotient space theory[J]. Journal on Communications,2013,34(6):146-155.
[3] 邹露.基于蚂蚁算法的数据网格副本选择策略研究[D].南京:南京信息工程大学,2014.ZOU L.Research of replica selection scheme based on ant algorithm in data grid[D].Nanjing:Nanjing University of Information Science & Technology,2014.
[4] 杨丹,张会.一种基于访问趋势的数据网格动态副本创建策略[J].四川大学学报(自然科学版),2013,50(6):1205-1210.YANG D,ZHANG H.An access-tendency based dynamic replica creation strategy for data grid[J].Journal of Sichuan University(Natural Science Edition),2013,50(6):1205-1210.
[5] WANG X,WU J,JIANG G,et al.Fast Replica placement and update strategies in tree networks[C].15th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing (CCGrid), 2015:915-920.
[6] MANSOURI N,DASTGHAIBYFARD G H.Enhanced dynamic hierarchical replication and weighted scheduling strategy in data grid[J].Journal of Parallel and Distributed Computing,2013,73(4):534-543.
[7] ABDULLAH A,LATIP R,WAN M A W M.Evaluation of an economy-based file replication strategy for malaysian research and education network(MYREN) data grid model[J].Computer & Information Science,2012,5(1):62-76.
[8] DAYYANI S,KHAYYAMBASHI M R.RDT:A new data replication algorithm for hierarchical data grid[J]. International Journal of Computer Sciences and Engineering,2015,3(7):186-197.
[9] GERSTEL O,ZAKS S.A new characterization of tree medians with applications to distributed sorting[J].Networks,2013,24(1):23-29.
[10] KOLISCH R,DAHLMANN A.The dynamic replica placement problem with service levels in content delivery networks:A model and a simulated annealing heuristic[J].Or Spectrum,2015,37(1):217-242.
[11] MANSOURI Y,AZAD S T,CHAMKORI A.Minimizing cost of k-replica in hierarchical data grid environment[C]. IEEE 28th International Conference on Advanced Information Networking and Applications(AINA), 2014:1073-1080.
[12] ZHANG B,WANG X W,HUANG M.A data replica placement scheme for cloud storage under healthcare IoT environment[J].Applied Mechanics & Materials,2014(556-562):5511-5517.
[13] MADI M K,YUSOF Y,HASSAN S.Replica placement strategy for data grid environment[J].IGI Global,2013,5(1):70-81.
[14] GRACE R K,MANIMEGALAI R.Dynamic replica placement and selection strategies in data grids-A comprehensive survey[J].Journal of Parallel & Distributed Computing,2014,74(2):2099-2108.
[15] REHNSONIGO V.Optimal replica placement in tree networks with QoS and bandwidth constraints and the closest allocation policy[J].Computer Science,2012,2(2):159-162.
[16] 付雄,王义波,朱鑫鑫,等.数据网格中QoS感知的副本放置方法[J].系统工程与电子技术,2014,36(4):784-788.FU X,WANG Y B,ZHU X X,et al.QoS-aware replica placement in data grids[J].Systems Engineering and Electronics,2014,36(4):784-788.
[17] BHATTACHARYA B,KAMEDA T,ZHAO S.A linear time algorithm for computing minmax regret 1-median on a tree network[J].Algorithmica,2014,70(1):2-21.
[2] 夏纯中,宋顺林.基于商空间的层次式数据网格资源调度算法[J].通信学报,2013,34(6):146-155.XIA CH ZH,SONG SH L.Hierarchical data grid resource allocation based on quotient space theory[J]. Journal on Communications,2013,34(6):146-155.
[3] 邹露.基于蚂蚁算法的数据网格副本选择策略研究[D].南京:南京信息工程大学,2014.ZOU L.Research of replica selection scheme based on ant algorithm in data grid[D].Nanjing:Nanjing University of Information Science & Technology,2014.
[4] 杨丹,张会.一种基于访问趋势的数据网格动态副本创建策略[J].四川大学学报(自然科学版),2013,50(6):1205-1210.YANG D,ZHANG H.An access-tendency based dynamic replica creation strategy for data grid[J].Journal of Sichuan University(Natural Science Edition),2013,50(6):1205-1210.
[5] WANG X,WU J,JIANG G,et al.Fast Replica placement and update strategies in tree networks[C].15th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing (CCGrid), 2015:915-920.
[6] MANSOURI N,DASTGHAIBYFARD G H.Enhanced dynamic hierarchical replication and weighted scheduling strategy in data grid[J].Journal of Parallel and Distributed Computing,2013,73(4):534-543.
[7] ABDULLAH A,LATIP R,WAN M A W M.Evaluation of an economy-based file replication strategy for malaysian research and education network(MYREN) data grid model[J].Computer & Information Science,2012,5(1):62-76.
[8] DAYYANI S,KHAYYAMBASHI M R.RDT:A new data replication algorithm for hierarchical data grid[J]. International Journal of Computer Sciences and Engineering,2015,3(7):186-197.
[9] GERSTEL O,ZAKS S.A new characterization of tree medians with applications to distributed sorting[J].Networks,2013,24(1):23-29.
[10] KOLISCH R,DAHLMANN A.The dynamic replica placement problem with service levels in content delivery networks:A model and a simulated annealing heuristic[J].Or Spectrum,2015,37(1):217-242.
[11] MANSOURI Y,AZAD S T,CHAMKORI A.Minimizing cost of k-replica in hierarchical data grid environment[C]. IEEE 28th International Conference on Advanced Information Networking and Applications(AINA), 2014:1073-1080.
[12] ZHANG B,WANG X W,HUANG M.A data replica placement scheme for cloud storage under healthcare IoT environment[J].Applied Mechanics & Materials,2014(556-562):5511-5517.
[13] MADI M K,YUSOF Y,HASSAN S.Replica placement strategy for data grid environment[J].IGI Global,2013,5(1):70-81.
[14] GRACE R K,MANIMEGALAI R.Dynamic replica placement and selection strategies in data grids-A comprehensive survey[J].Journal of Parallel & Distributed Computing,2014,74(2):2099-2108.
[15] REHNSONIGO V.Optimal replica placement in tree networks with QoS and bandwidth constraints and the closest allocation policy[J].Computer Science,2012,2(2):159-162.
[16] 付雄,王义波,朱鑫鑫,等.数据网格中QoS感知的副本放置方法[J].系统工程与电子技术,2014,36(4):784-788.FU X,WANG Y B,ZHU X X,et al.QoS-aware replica placement in data grids[J].Systems Engineering and Electronics,2014,36(4):784-788.
[17] BHATTACHARYA B,KAMEDA T,ZHAO S.A linear time algorithm for computing minmax regret 1-median on a tree network[J].Algorithmica,2014,70(1):2-21.