Approximations to Study the Impact of the Service Discipline in Systems with Redundancy - POLARIS - Performance analysis and Optimization of LARge Infrastructure and Systems
Journal Articles Proceedings of the ACM on Measurement and Analysis of Computing Systems Year : 2024

Approximations to Study the Impact of the Service Discipline in Systems with Redundancy

Abstract

As job redundancy has been recognized as an effective means to improve performance of large-scale computer systems, queueing systems with redundancy have been studied by various authors. Existing results include methods to compute the queue length distribution and response time but only when the service discipline is First-Come-First-Served (FCFS). For other service disciplines, such as Processor Sharing (PS), or Last-Come-First-Served (LCFS), only the stability conditions are known. In this paper we develop the first methods to approximate the queue length distribution in a queueing system with redundancy under various service disciplines. We focus on a system with exponential job sizes, i.i.d. copies, and a large number of servers. We first derive a mean field approximation that is independent of the scheduling policy. In order to study the impact of service discipline, we then derive refinements of this approximation to specific scheduling policies. In the case of Processor Sharing, we provide a pair and a triplet approximation. The pair approximation can be regarded as a refinement of the classic mean field approximation and takes the service discipline into account, while the triplet approximation further refines the pair approximation. We also develop a pair approximation for three other service disciplines: First-Come-First-Served, Limited Processor Sharing and Last-Come-First-Served. We present numerical evidence that shows that all the approximations presented in the paper are highly accurate, but that none of them are asymptotically exact (as the number of servers goes to infinity). This makes these approximations suitable to study the impact of the service discipline on the queue length distribution. Our results show that FCFS yields the shortest queue length, and that the differences are more substantial at higher loads.
Fichier principal
Vignette du fichier
RED_PS.pdf (872.45 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-04390014 , version 1 (12-01-2024)

Licence

Identifiers

Cite

Nicolas Gast, Benny van Houdt. Approximations to Study the Impact of the Service Discipline in Systems with Redundancy. Proceedings of the ACM on Measurement and Analysis of Computing Systems , 2024, 8 (1), pp.1-32. ⟨10.1145/3639040⟩. ⟨hal-04390014⟩
83 View
64 Download

Altmetric

Share

More