论文部分内容阅读
随着虚拟化技术的快速发展,基于虚拟化技术的云计算平台的构建现在越来越完善。越来越多的人使用云平台完成任务部署。由于用户的全球化,区域化趋势变得更加突出,近年来基础设施提供商倾向于在多个国家和地区部署数据中心。图处理是一种适用于各种应用的新兴计算模型,图分割对于优化图处理作业的费用成本和性能非常重要。随着移动互联网和社交网站的兴起,许多服务提供商改变了服务器自给自足的运营模式,通过租用分布在多个地区的基础设施供应商的数据中心虚拟机,并将许多图应用程序(如社交网络)的数据存储在地理分布式数据中心上,以便在全球范围内为用户提供低延迟、高质量的服务。由于图的流量异构性和地理分布式数据中心的多级网络异构性,对现有的图分割方法提出了新的挑战。本文中,我们首先在当下使用广泛的Microsoft Azure云平台的四个不同的数据中心租用使用较广泛的四种类型实例,对每类实例进行连续一周的测试,研究云平台的网络带宽特性以及网络价格特点,以及对Amazon EC2云平台进行相应测试。其次,我们根据GAS图处理模型建立了地理分布式平台下图应用的数据输出时间和费用模型,在此基础上,我们提出了一种具有地理感知的图分割方法Geo-Cut,旨在最小化地理分布式图处理的数据传输时间,同时满足数据传输费用的预算约束。Geo-Cut算法分为两个阶段。首先,我们提出一种优化的流式启发算法,通过一次流式图分割方法快速将边分配到不同的数据中心,同时获得最小化的数据中心间数据通信成本。其次,在第一阶段的初始图分割基础上提出了分区重映射优化方法和边移动优化方法。这两种方法分别通过将图分割结果重映射到不同数据中心和将边移出成为分布式图处理性能瓶颈的数据中心。对第一阶段获得的分区结果进行优化,减少数据中心数据传输时间,同时满足预算约束。由于其轻量级运行时间开销,Geo-Cut算法也可以应用于动态图分割,并取得较好的图分割结果。最后,在真实云环境和仿真实验云环境下,我们将Geo-Cut算法与四种流行的图分割算法进行对比,并在数据中心的数据传输时间和数据传输费用两个方面对实验结果进行详细分析,评估Geo-Cut算法的效率和有效性。最终数据评估结果表明,与最先进的图分割方法相比,Geo-Cut算法既可以减少数据中心数据传输时间,又能降低数据中心数据传输费用。Geo-Cut算法可以将数据传输时间减少高达79%,数据传输成本降低高达75%。