Stochastic bounds in Fork–Join queueing systems under full and partial mapping

Amr Rizk (), Felix Poloczek () and Florin Ciucu ()
Additional contact information
Amr Rizk: University of Massachusetts Amherst
Felix Poloczek: University of Warwick
Florin Ciucu: University of Warwick

Queueing Systems: Theory and Applications, 2016, vol. 83, issue 3, No 4, 291 pages

Abstract: Abstract In a Fork–Join (FJ) queueing system, an upstream fork station splits incoming jobs into N tasks to be further processed by N parallel servers, each with its own queue; the response time of one job is determined, at a downstream join station, by the maximum of the corresponding tasks’ response times. This queueing system is useful to the modeling of multi-service systems subject to synchronization constraints, such as MapReduce clusters or multipath routing. Despite their apparent simplicity, FJ systems are hard to analyze. This paper provides the first computable stochastic bounds on the waiting and response time distributions in FJ systems under full (bijective) and partial (injective) mapping of tasks to servers. We consider four practical scenarios by combining (1a) renewal and (1b) non-renewal arrivals, and (2a) non-blocking and (2b) blocking servers. In the case of non-blocking servers, we prove that delays scale as $$\mathcal {O}(\log N)$$ O ( log N ) , a law which is known for first moments under renewal input only. In the case of blocking servers, we prove that the same factor of $$\log N$$ log N dictates the stability region of the system. Simulation results indicate that our bounds are tight, especially at high utilizations, in all four scenarios. A remarkable insight gained from our results is that, at moderate to high utilizations, multipath routing “makes sense” from a queueing perspective for two paths only, i.e., response times drop the most when $$N=2$$ N = 2 ; the technical explanation is that the resequencing (delay) price starts to quickly dominate the tempting gain due to multipath transmissions.

Keywords: Fork–Join queue; Performance evaluation; Parallel systems; MapReduce; Multipath; 90B22; 68M20; 60K25; 90B18 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s11134-016-9486-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:83:y:2016:i:3:d:10.1007_s11134-016-9486-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-016-9486-x

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().