Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (23): 78-85.DOI: 10.3778/j.issn.1002-8331.1808-0441

Previous Articles     Next Articles

Stage-Aware Geo-Distributed Data Analytics Job Insurance Mechanism

WU Bo, XU Daoqiang, ZOU Yunfeng, WANG Tiantian, LI Xin   

  1. 1.Huai’an Power Supply Branch, State Grid Jiangsu Electric Power Co., Ltd., Huai’an, Jiangsu 211600, China
    2.State Grid Jiangsu Electric Power Co., Ltd., Nanjing 210008, China
    3.Electric Power Research Institute, State Grid Jiangsu Electric Power Co., Ltd., Nanjing 210024, China
    4.State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China
    5.College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
  • Online:2019-12-01 Published:2019-12-11



  1. 1.国网江苏省电力有限公司 淮安供电分公司,江苏 淮安 211600
    2.国网江苏省电力有限公司,南京 210008
    3.国网江苏省电力有限公司 电力科学研究院,南京 210024
    4.南京大学 计算机软件新技术国家重点实验室,南京 210023
    5.南京航空航天大学 计算机科学与技术学院,南京 211106

Abstract: To mitigate the negative impact of unstable edge computing, it designs Geo-distributed job Insurance Mechanism(GIM), a new task replication and dispatching algorithm that guarantees the completion time of data analytics jobs across clouds and edges. To cater to the parallel processing and resource constraints, it first formulates the problem as a minimax polynomial integer programming. After relaxing the integer constraint, it adopts feasible-point algorithm to quickly converge to the optimal solution of the relaxed problem. Finally, it rounds such optimal solution based on high-risk-task-first heuristic and obtains a high-quality feasible solution of the original problem. The simulations driven by production trace show that GIM beats the other redundant execution strategies by at least 22% in terms of the average job completion time under different system utilization.

Key words: cloud computing, edge computing, task scheduling, insurance mechanism, delay optimization, job completion time

摘要: 为缓解边缘计算的不稳定性,设计了适用于跨域规模的任务复制与分配机制以保障作业各阶段的完成(Geo-distributed job Insurance Mechanism,GIM)。为满足并行任务执行特征和资源限制,先将问题形式化为Min-Max多项式整数规划问题,再放松整数约束并采用feasible-point算法快速地收敛到最优解,最后基于高危任务优先原则对最优解进行取整,得到满足原问题约束的高质量任务复制与分配方案。模拟实验表明,在不同的系统负载下,相比于当前的冗余执行策略,GIM至少能够减少22%的作业平均完成时间。

关键词: 云计算, 边缘计算, 任务调度, 保障机制, 时延优化, 作业完成时间