Li, Tong and Xu, Ke and Sheng, Meng and Wang, Haiyang and Yang, Kun and Zhang, Yuchao (2016) Towards Minimal Tardiness of Data-Intensive Applications in Heterogeneous Networks. In: 2016 25th International Conference on Computer Communication and Networks (ICCCN), 2016-08-01 - 2016-08-04.
Li, Tong and Xu, Ke and Sheng, Meng and Wang, Haiyang and Yang, Kun and Zhang, Yuchao (2016) Towards Minimal Tardiness of Data-Intensive Applications in Heterogeneous Networks. In: 2016 25th International Conference on Computer Communication and Networks (ICCCN), 2016-08-01 - 2016-08-04.
Li, Tong and Xu, Ke and Sheng, Meng and Wang, Haiyang and Yang, Kun and Zhang, Yuchao (2016) Towards Minimal Tardiness of Data-Intensive Applications in Heterogeneous Networks. In: 2016 25th International Conference on Computer Communication and Networks (ICCCN), 2016-08-01 - 2016-08-04.
Abstract
The increasing data requirement of Internet applications has driven a dramatic surge in developing new programming paradigms and complex scheduling algorithms to handle data-intensive workloads. Due to the expanding volume and the variety of such flows, their raw data are often processed on intermediate processing nodes before being sent to servers. The intermediate processing constraints are however not yet considered in existing task and flow computing models. In this paper, we aim to minimize the total tardiness of all flows in the presence of intermediate processing constraints. We build a model to consider Tardiness-aware Flow Scheduling with Processing constraints (TFS-P), which is unfortunately NP-Hard. Hence, we propose a heuristic Routing and Scheduling duplex MATching (RSMAT) framework based on the classic Gale-Shapley Matching Theory. We find that the problem can be well-addressed by classic Deferred Acceptance (DA) algorithm, in which the match is stable but inefficient for the model. We therefore propose the Tardiness-aware Deferred Acceptance algorithm with Dynamical Quota (TDA-DQ). This algorithm is enhanced by overcoming the inefficient stability and smartly considering the dynamical quota in the system. The evaluation compares TDA-DQ to the lower bound obtained by a modified subgradient optimization algorithm. The result indicates that TDA-DQ can achieve near-optimal performance for data-intensive applications.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Additional Information: | Published proceedings: 2016 25th International Conference on Computer Communications and Networks, ICCCN 2016 |
Uncontrolled Keywords: | Heterogeneous Network; Data-intensive Application; Matching Theory |
Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 14 Feb 2017 10:15 |
Last Modified: | 30 Oct 2024 20:24 |
URI: | http://repository.essex.ac.uk/id/eprint/19006 |