Online job dispatching and scheduling in edge-clouds
Online job dispatching and scheduling in edge-clouds
复制标题
DOI：
10.1109/infocom.2017.8057116
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Haisheng Tan;Zhenhua Han;Xiangyang Li;F. Lau
中科院分区：
文献类型：
--
作者：
Haisheng Tan;Zhenhua Han;Xiangyang Li;F. Lau
在边缘云计算中，一组边缘服务器被部署在移动的设备附近，使得这些设备可以以低延迟将作业卸载到服务器。边缘云系统中的一个基本和关键问题是如何分派和调度作业，以使作业响应时间（定义为作业发布和计算结果到达其设备之间的间隔）最小化。在本文中，我们提出了一个一般模型，这个问题，在任意顺序和时间产生的作业在移动的设备和卸载到服务器的上传和下载延迟。我们的目标是最小化所有作业的总加权响应时间。权重是根据作业对延迟的敏感程度来设置的。我们推导出第一个在边缘云环境下的在线作业调度算法OnDisc，该算法在速度增强模型中是可扩展的，即OnDisc对于任何常数ε（0，1）都是（1 + ε）-速度O（1/ε）-竞争性的.此外，OnDisc可以很容易地在分布式系统中实现。在Google的真实数据跟踪上的大量仿真表明，与启发式算法相比，OnDisc可以显着减少总的加权响应时间。
In edge-cloud computing, a set of edge servers are deployed near the mobile devices such that these devices can offload jobs to the servers with low latency. One fundamental and critical problem in edge-cloud systems is how to dispatch and schedule the jobs so that the job response time (defined as the interval between the release of a job and the arrival of the computation result at its device) is minimized. In this paper, we propose a general model for this problem, where the jobs are generated in arbitrary order and times at the mobile devices and offloaded to servers with both upload and download delays. Our goal is to minimize the total weighted response time over all the jobs. The weight is set based on how latency sensitive the job is. We derive the first online job dispatching and scheduling algorithm in edge-clouds, called OnDisc, which is scalable in the speed augmentation model; that is, OnDisc is (1 + ε)-speed O(1/ε)-competitive for any constant ε ∊ (0,1). Moreover, OnDisc can be easily implemented in distributed systems. Extensive simulations on a real-world data-trace from Google show that OnDisc can reduce the total weighted response time dramatically compared with heuristic algorithms.