On a unifying product form framework for redundancy models

Autor: Ina Maria Verloop, Tejas Bodas, Urtzi Ayesta
Přispěvatelé: Basque Foundation for Science ( Ikerbasque ), Institut de recherche en informatique de Toulouse ( IRIT ), Institut National Polytechnique [Toulouse] ( INP ) -Université Toulouse 1 Capitole ( UT1 ) -Université Toulouse - Jean Jaurès ( UT2J ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Équipe Services et Architectures pour Réseaux Avancés ( LAAS-SARA ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Centre National de la Recherche Scientifique - CNRS (FRANCE), IKERBASQUE (SPAIN), Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), Universidad del País Vasco - Euskal Herriko Unibertsitatea - EHU (SPAIN), Laboratoire d'Analyse et d'Architecture des Systèmes - LAAS (Toulouse, France), Ikerbasque - Basque Foundation for Science, Réseaux, Mobiles, Embarqués, Sans fil, Satellites (IRIT-RMESS), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Centre National de la Recherche Scientifique (CNRS), Équipe Services et Architectures pour Réseaux Avancés (LAAS-SARA), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Basque Foundation for Science (Ikerbasque), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1)
Rok vydání: 2018
Předmět:
Exponential distribution
Redundancy-d
Computer science
Computer Networks and Communications
Generalization
Système d'exploitation
0211 other engineering and technologies
Réseaux et télécommunications
02 engineering and technology
01 natural sciences
Combinatorics
010104 statistics & probability
Redundancy (information theory)
Architectures Matérielles
Server
Cancel-on-start
0202 electrical engineering
electronic engineering
information engineering
Redundancy (engineering)
0101 mathematics
Queue
[ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]
Mathematics
020203 distributed computing
021103 operations research
Stationary distribution
business.industry
Product-form distribution
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Queueing system
Systèmes embarqués
[ INFO.INFO-PF ] Computer Science [cs]/Performance [cs.PF]
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR]
[INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF]
Hardware and Architecture
Independence assumption
Modeling and Simulation
Product (mathematics)
Closed-form expression
business
[ MATH.MATH-PR ] Mathematics [math]/Probability [math.PR]
Software
Computer network
Zdroj: Rapport LAAS n° 18047. 2018
Performance Evaluation
Performance Evaluation, 2018, 127-128, pp.93-119. ⟨10.1016/j.peva.2018.09.008⟩
Performance Evaluation, Elsevier, 2018, 127-128, pp.93-119. ⟨10.1016/j.peva.2018.09.008⟩
ISSN: 0166-5316
DOI: 10.1016/j.peva.2018.09.008
Popis: In this paper, we present a unifying analysis for redundancy systems with cancel-on-start ( c . o . s . ) and cancel-on-complete ( c . o . c . ) with exponentially distributed service requirements. With c . o . s . ( c . o . c . ) all redundant copies are removed as soon as one of the copies starts (completes) service. As a consequence, c . o . s . does not waste any computing resources, as opposed to c . o . c . We show that the c . o . s . model is equivalent to a queueing system with multi-type jobs and servers, which was analyzed in Visschers et al., (2012), and show that c . o . c . (under the assumption of i.i.d. copies) can be analyzed by a generalization of Visschers et al., (2012) where state-dependent departure rates are permitted. This allows us to show that the stationary distribution for both the c . o . c . and c . o . s . models has a product form. We give a detailed first-time analysis for c . o . s and derive a closed form expression for important metrics like mean number of jobs in the system, and probability of waiting. We also note that the c . o . s . model is equivalent to Join-Shortest-Work queue with power of d (JSW( d )). In the latter, an incoming job is dispatched to the server with smallest workload among d randomly chosen ones. Thus, all our results apply mutatis-mutandis to JSW( d ). Comparing the performance of c . o . s . with that of c . o . c . with i.i.d. copies gives the unexpected conclusion (since c . o . s . does not waste any resources) that c . o . s . is worse in terms of mean number of jobs. As part of ancillary results, we illustrate that this is primarily due to the assumption of i.i.d. copies in case of c . o . c . (together with exponentially distributed requirements) and that such assumptions might lead to conclusions that are qualitatively different from that observed in practice.
Databáze: OpenAIRE
Externí odkaz: