TU Darmstadt / ULB / TUbiblio

Optimizing Stochastic Scheduling in Fork-Join Queueing Models: Bounds and Applications

KhudaBukhsh, W. R. and Rizk, A. and Froemmgen, A. and Koeppl, H. (2017):
Optimizing Stochastic Scheduling in Fork-Join Queueing Models: Bounds and Applications.
In: Technical Program of IEEE INFOCOM 2017, IEEE, [Online-Edition: https://arxiv.org/abs/1612.05486],
[Article]

Abstract

Fork-Join (FJ) queuing models capture the dynamics of system parallelization under synchronization constraints, for example, for applications such as MapReduce, multipath transmission and RAID systems. Arriving jobs are first split into tasks and mapped to servers for execution, such that a job can only leave the system when all of its tasks are executed. In this paper, we provide computable stochastic bounds for the waiting and response time distributions for heterogeneous FJ systems under general parallelization benefit. Our main contribution is a generalized mathematical framework for probabilistic server scheduling strategies that are essentially characterized by a probability distribution over the number of utilized servers, and the optimization thereof. We highlight the trade-off between the scaling benefit due to parallelization and the FJ inherent synchronization penalty. Further, we provide optimal scheduling strategies for arbitrary scaling regimes that map to different levels of parallelization benefit. One notable insight obtained from our results is that different applications with varying parallelization benefits result in different optimal strategies. Finally, we complement our analytical results by applying them to various applications showing the optimality of the proposed scheduling strategies.

Item Type: Article
Erschienen: 2017
Creators: KhudaBukhsh, W. R. and Rizk, A. and Froemmgen, A. and Koeppl, H.
Title: Optimizing Stochastic Scheduling in Fork-Join Queueing Models: Bounds and Applications
Language: English
Abstract:

Fork-Join (FJ) queuing models capture the dynamics of system parallelization under synchronization constraints, for example, for applications such as MapReduce, multipath transmission and RAID systems. Arriving jobs are first split into tasks and mapped to servers for execution, such that a job can only leave the system when all of its tasks are executed. In this paper, we provide computable stochastic bounds for the waiting and response time distributions for heterogeneous FJ systems under general parallelization benefit. Our main contribution is a generalized mathematical framework for probabilistic server scheduling strategies that are essentially characterized by a probability distribution over the number of utilized servers, and the optimization thereof. We highlight the trade-off between the scaling benefit due to parallelization and the FJ inherent synchronization penalty. Further, we provide optimal scheduling strategies for arbitrary scaling regimes that map to different levels of parallelization benefit. One notable insight obtained from our results is that different applications with varying parallelization benefits result in different optimal strategies. Finally, we complement our analytical results by applying them to various applications showing the optimality of the proposed scheduling strategies.

Journal or Publication Title: Technical Program of IEEE INFOCOM 2017
Publisher: IEEE
Divisions: 18 Department of Electrical Engineering and Information Technology
18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications > Bioinspired Communication Systems
18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications
Date Deposited: 14 Dec 2016 08:09
Official URL: https://arxiv.org/abs/1612.05486
Related URLs:
Export:

Optionen (nur für Redakteure)

View Item View Item