Queueing with redundant requests: exact analysis

Kristen Gardner (), Samuel Zbarsky, Sherwin Doroudi, Mor Harchol-Balter, Esa Hyytiä and Alan Scheller-Wolf
Additional contact information
Kristen Gardner: Carnegie Mellon University
Samuel Zbarsky: Carnegie Mellon University
Sherwin Doroudi: Carnegie Mellon University
Mor Harchol-Balter: Carnegie Mellon University
Esa Hyytiä: University of Iceland
Alan Scheller-Wolf: Carnegie Mellon University

Queueing Systems: Theory and Applications, 2016, vol. 83, issue 3, No 3, 227-259

Abstract: Abstract Recent computer systems research has proposed using redundant requests to reduce latency. The idea is to run a request on multiple servers and wait for the first completion (discarding all remaining copies of the request). However, there is no exact analysis of systems with redundancy. This paper presents the first exact analysis of systems with redundancy. We allow for any number of classes of redundant requests, any number of classes of non-redundant requests, any degree of redundancy, and any number of heterogeneous servers. In all cases we derive the limiting distribution of the state of the system. In small (two or three server) systems, we derive simple forms for the distribution of response time of both the redundant classes and non-redundant classes, and we quantify the “gain” to redundant classes and “pain” to non-redundant classes caused by redundancy. We find some surprising results. First, the response time of a fully redundant class follows a simple exponential distribution and that of the non-redundant class follows a generalized hyperexponential. Second, fully redundant classes are “immune” to any pain caused by other classes becoming redundant. We also compare redundancy with other approaches for reducing latency, such as optimal probabilistic splitting of a class among servers (Opt-Split) and join-the-shortest-queue (JSQ) routing of a class. We find that, in many cases, redundancy outperforms JSQ and Opt-Split with respect to overall response time, making it an attractive solution.

Keywords: Redundancy; Markov chain analysis; Dispatching; 60J27 (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://link.springer.com/10.1007/s11134-016-9485-y 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-9485-y

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

DOI: 10.1007/s11134-016-9485-y

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 ().