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

Content Provider	Springer Nature Link
Author	Poloczek, Felix Rizk, Amr Ciucu, Florin
Copyright Year	2016
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)$$ , 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$$ 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$$ ; the technical explanation is that the resequencing (delay) price starts to quickly dominate the tempting gain due to multipath transmissions.
Ending Page	291
Page Count	31
Starting Page	261
File Format	PDF
ISSN	02570130
e-ISSN	15729443
Journal	Queueing Systems
Issue Number	3-4
Volume Number	83
Language	English
Publisher	Springer US
Publisher Date	2016-06-24
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Performance evaluation Fork–Join queue Queues and service Systems Theory, Control Probability Theory and Stochastic Processes MapReduce Multipath Parallel systems Performance evaluation; queueing; scheduling Operation Research/Decision Theory Supply Chain Management Communication networks Queueing theory Computer Communication Networks
Content Type	Text
Resource Type	Article
Subject	Statistics and Probability Management Science and Operations Research Computational Theory and Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Asymptotic independence of queues under randomized load balancing

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

Stability of longest-queue-first scheduling in linear wireless networks with multihop traffic and one-hop interference

Approximately optimal scheduling of an M/G/1 queue with heavy tails

Waiting and sojourn times in a multi-server queue with mixed priorities

Marginal queue length approximations for a two-layered network with correlated queues

Generalized parallel-server fork-join queues with dynamic task scheduling

A general workload conservation law with applications to queueing systems

Dynamic scheduling with reconfiguration delays

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

Similar Documents

Asymptotic independence of queues under randomized load balancing

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

Stability of longest-queue-first scheduling in linear wireless networks with multihop traffic and one-hop interference

Approximately optimal scheduling of an M/G/1 queue with heavy tails

Waiting and sojourn times in a multi-server queue with mixed priorities

Marginal queue length approximations for a two-layered network with correlated queues

Generalized parallel-server fork-join queues with dynamic task scheduling

A general workload conservation law with applications to queueing systems

Dynamic scheduling with reconfiguration delays

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