Queuing systems with redundant requests have drawn great attention because of their promise to reduce the job completion time and its variability. Despite a large body of work on this topic, we are still far from fully understanding the benefits of redundancy in practice. We here take one step towards practical systems by studying queuing systems with bi-modal job service time distribution. Such distributions have been observed in practical systems , as can be seen in  Google cluster traces. We develop an analogy to a classical urns and balls problem, and use it to study the queuing time performance of two non-adaptive classical scheduling policies: random and round-robin. In particular, we introduce new performance metrics in the analogous model, and argue that they are good indicators of the queuing time performance of non-adaptive scheduling policies. We then propose a new non-adaptive scheduling policy that is based on combinatorial designs, and show that it improves our performance metrics. We observe in simulation that the proposed scheduling policy, as the performance metrics indicate , reduces the queuing times up to 25\% compared to random scheduling and up to 100\% compared round-robin scheduling.
Queuing systems with redundant requests have drawn great attention because of their promise to reduce the job completion time and variability. Despite a large body of work on the topic, we are still far from fully understanding the benefits of redundancy in practice. We here take one step towards practical systems by studying queuing systems with bi-modal job service time distribution. Such distributions have been observed in practice , as can be seen in , e.g., Google cluster traces. We develop an analogy to a classical urns and balls problem, and use it to study the queuing time performance of two non-adaptive classical scheduling policies: random and round-robin. We introduce new performance indicators in the analogous model, and argue that they are good predictors of the queuing time in non-adaptive scheduling policies. We then propose a non-adaptive scheduling policy that is based on combinatorial designs, and show that it has better performance indicators. Simulations confirm that the proposed scheduling policy, as the performance indicators suggest , reduces the queuing times compared to random and round-robin scheduling.
D
its
R
this
the
R
practical systems
practice
A
, e.g.,
R
In particular, we
We
R
metrics
indicators
R
indicators
predictors
R
performance of
in
D
new
R
improves our performance metrics. We observe in simulation
has better performance indicators. Simulations confirm
R
metrics indicate
indicators suggest
D
up to 25\%
R
scheduling and up to 100\% compared
and