Time- and cost- efficient task scheduling across geo-distributed data centers
Typically called big data processing, analyzing large volumes of data from geographically distributed regions with machine learning algorithms has emerged as an important analytical tool for governments and multinational corporations. The traditional wisdom calls for the collection of all the data a...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2019
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/105436 http://hdl.handle.net/10220/48661 http://dx.doi.org/10.1109/TPDS.2017.2773504 |
| _version_ | 1811695638414360576 |
|---|---|
| author | Hu, Zhiming Li, Baochun Luo, Jun |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Hu, Zhiming Li, Baochun Luo, Jun |
| author_sort | Hu, Zhiming |
| collection | NTU |
| description | Typically called big data processing, analyzing large volumes of data from geographically distributed regions with machine learning algorithms has emerged as an important analytical tool for governments and multinational corporations. The traditional wisdom calls for the collection of all the data across the world to a central data center location, to be processed using data-parallel applications. This is neither efficient nor practical as the volume of data grows exponentially. Rather than transferring data, we believe that computation tasks should be scheduled near the data, while data should be processed with a minimum amount of transfers across data centers. In this paper, we design and implement Flutter, a new task scheduling algorithm that reduces both the completion times and the network costs of big data processing jobs across geographically distributed data centers. To cater to the specific characteristics of data-parallel applications, in the case of optimizing the job completion times only, we first formulate our problem as a lexicographical min-max integer linear programming (ILP) problem, and then transform the ILP problem into a nonlinear program problem with a separable convex objective function and a totally unimodular constraint matrix, which can be further solved using a standard linear programming solver efficiently in an online fashion. In the case of improving both time-and costefficiency, we formulate the general problem as an ILP problem and we find out that solving an LP problem can achieve the same goal in the real practice. Our implementation of Flutter is based on Apache Spark, a modern framework popular for big data processing. Our experimental results have shown convincing evidence that Flutter can shorten both job completion times and network costs by a substantial margin. |
| first_indexed | 2024-10-01T07:26:39Z |
| format | Journal Article |
| id | ntu-10356/105436 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:26:39Z |
| publishDate | 2019 |
| record_format | dspace |
| spelling | ntu-10356/1054362019-12-06T21:51:14Z Time- and cost- efficient task scheduling across geo-distributed data centers Hu, Zhiming Li, Baochun Luo, Jun School of Computer Science and Engineering Big Data Processing Task Scheduling DRNTU::Engineering::Computer science and engineering Typically called big data processing, analyzing large volumes of data from geographically distributed regions with machine learning algorithms has emerged as an important analytical tool for governments and multinational corporations. The traditional wisdom calls for the collection of all the data across the world to a central data center location, to be processed using data-parallel applications. This is neither efficient nor practical as the volume of data grows exponentially. Rather than transferring data, we believe that computation tasks should be scheduled near the data, while data should be processed with a minimum amount of transfers across data centers. In this paper, we design and implement Flutter, a new task scheduling algorithm that reduces both the completion times and the network costs of big data processing jobs across geographically distributed data centers. To cater to the specific characteristics of data-parallel applications, in the case of optimizing the job completion times only, we first formulate our problem as a lexicographical min-max integer linear programming (ILP) problem, and then transform the ILP problem into a nonlinear program problem with a separable convex objective function and a totally unimodular constraint matrix, which can be further solved using a standard linear programming solver efficiently in an online fashion. In the case of improving both time-and costefficiency, we formulate the general problem as an ILP problem and we find out that solving an LP problem can achieve the same goal in the real practice. Our implementation of Flutter is based on Apache Spark, a modern framework popular for big data processing. Our experimental results have shown convincing evidence that Flutter can shorten both job completion times and network costs by a substantial margin. Accepted version 2019-06-12T03:33:07Z 2019-12-06T21:51:14Z 2019-06-12T03:33:07Z 2019-12-06T21:51:14Z 2017 Journal Article Hu, Z., Li, B., & Luo, J. (2018). Time- and cost- efficient task scheduling across geo-distributed data centers. IEEE Transactions on Parallel and Distributed Systems, 29(3), 705-718. doi:10.1109/TPDS.2017.2773504 1045-9219 https://hdl.handle.net/10356/105436 http://hdl.handle.net/10220/48661 http://dx.doi.org/10.1109/TPDS.2017.2773504 en IEEE Transactions on Parallel and Distributed Systems © 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: https://doi.org/10.1109/TPDS.2017.2773504 14 p. application/pdf |
| spellingShingle | Big Data Processing Task Scheduling DRNTU::Engineering::Computer science and engineering Hu, Zhiming Li, Baochun Luo, Jun Time- and cost- efficient task scheduling across geo-distributed data centers |
| title | Time- and cost- efficient task scheduling across geo-distributed data centers |
| title_full | Time- and cost- efficient task scheduling across geo-distributed data centers |
| title_fullStr | Time- and cost- efficient task scheduling across geo-distributed data centers |
| title_full_unstemmed | Time- and cost- efficient task scheduling across geo-distributed data centers |
| title_short | Time- and cost- efficient task scheduling across geo-distributed data centers |
| title_sort | time and cost efficient task scheduling across geo distributed data centers |
| topic | Big Data Processing Task Scheduling DRNTU::Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/105436 http://hdl.handle.net/10220/48661 http://dx.doi.org/10.1109/TPDS.2017.2773504 |
| work_keys_str_mv | AT huzhiming timeandcostefficienttaskschedulingacrossgeodistributeddatacenters AT libaochun timeandcostefficienttaskschedulingacrossgeodistributeddatacenters AT luojun timeandcostefficienttaskschedulingacrossgeodistributeddatacenters |