A Scheduling Framework for Periodic Tasks in Geo-Distributed Data Centers
Yan Li
1,2,3
, Hong Zhang
3
, Yong Wang
3
, Xinran Liu
3
, Peng Zhang
4
1
University of Chinese Academy of Sciences, Beijing 100080, China
2
Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
3
National Computer Network Emergency Response Technical Team/Coordination Center, Beijing 100029, China
4
Institute of Information engineering, Chinese Academy of Sciences, Beijing 100093, China
Abstract— we present FPT, a scheduling framework for
periodic tasks that uses the temporal characteristic of periodic
tasks to alleviate the overhead of geo-distributed data centers.
In FPT, clients are able to express the periodicity about their
tasks, and this characteristic is used to realize one-time
scheduling for multiple executions. For a set of periodic tasks,
aiming to find the minimum number of VMs required to
guarantee the scheduability and generate the task execution
sequence on each VM, an algorithm is also presented. A case-
study and its evaluation are given to show the efficiency of our
framework.
key words
task scheduling; periodic task; geo-distributed data
centers; cloud computing
I. INTRODUCTION
With the prevalence of cloud computing services, there
has been a growing trend toward geographically distributed
data centers. Google has built dozens of data centers all over
the world to guarantee the quality of internet service to
global users [1]. One of the greatest challenges in leveraging
these data centers is efficient task scheduling. Better energy
efficiency, geographical load balancing and fairness are
extensively discussed in previous works [2, 3, 4, 5, and 6].
However, cloud task scheduling is an NP-hard
optimization problem. Due to existence of different
workload types with various requirements that should be
supported by data centers, no any single schedule strategy
can allocate resources to all imaginable types efficiently. For
example, numerical computing tasks are usually CPU
intensive, while database operations typically require high-
memory support. The heterogeneity of workload demands
poses significant technical challenges on the schedule
mechanism, giving rise to many delicate issues -notably
efficiency -that must be carefully addressed [7].
Existing approaches to workload characterization for
cloud computing mainly focus on task resource requirements
for CPU, memory, disk, I/O, network, etc. However, in
addition to resource requirements, tasks frequently have
placement constraints or temporal characteristics of the
execution. Table 1 show data taken from our production geo-
distributed data centers called iVCE test bed over a period of
31 days in this July. On average, there are 18 million tasks
need to schedule per day. Most of these tasks are very short
and the average running time is 3 minutes. Notably, more
than half of them are periodic task. Actually the test bed
especially the scheduler is facing significant pressure to
allocate resources efficiently. In some extremes, the success
ratio of task scheduling is less than 50%. After analysis, the
low success ratio is mainly attributed to the high load. As
shown in table 1, there are more than 200 tasks need to
schedule average per second. The test bed has used a
centralized management approach, in which a super master
node schedules tasks among the Geo-Distributed data centers.
In another side, there exist many complicated task placement
constraints such as on OS versions, machine types, physical
place and network accessing methods, those lead to high
computational-complexity to find an optimal resource to
execute a task. Using benchmarks of Google compute
clusters, the results of experiment in [8] indicate that the
presence of constraints increases task scheduling delays by a
factor of 2 to 6, which often means tens of minutes of
additional task wait time.
TABLE 1. MEAN VALUE IN JULY
Source Number of
tasks
Average
running time
Number of periodic
tasks
iVCE test bed
18 million 180 seconds 10.5 million
In general, distributed scheduling scheme can reduce the
pressure. But this is beyond the scope of this paper. We try to
use the temporal features- notably periodicity -to optimize
the scheduling process.
Despite the unprecedented heterogeneity in geo-
distributed data centers, state-of-the-art computing
frameworks have paid little attention to the temporal features
of workload.
However, the periodic features increase the difficulties of
efficiently scheduling at least from the following two aspects:
(1) The heavy overhead on the master node resulting
from the highly frequent scheduling. As shown in table 1,
there are more than 200 tasks need to schedule average per
second.
(2) The pressure of too much bandwidth consumption.
Though Geo-Distributed data centers are usually connected
together with dedicated high-bandwidth communication
links, the bandwidth is limited during the peak-hour.
Assuming that the average size of tasks is 1 MB, it will
consume 200MB/S bandwidth to distribute tasks.
2015 IEEE Symposium on Service-Oriented System Engineering
978-1-4799-8356-8/15 $31.00 © 2015 IEEE
DOI 10.1109/SOSE.2015.29
247
评论0
最新资源