Paper Info
Title
Deriving distribution of thread service time in layered queueing networks
Abstract
Replication is a technique used in distributed systems to improve performance, availability, and reliability. In replication schemes, often a J out of $N$ voting pattern (also called quorum) is used in which the quorum waits for J replies to arrive. Integrating a quorum scheme into the Layered Queueing Network (LQN) performance modeling language necessitates the computation of the quorum response time as the Jth order statistic. To do so, we need the exact (or an accurate estimation of the) time distribution of individual replies. This distribution was estimated in previous work but only for the special case of (J=N) and yields large errors for J « N. This paper presents a new analytic approach for the derivation of the distributions. Under a number of assumptions, we derive closed form expressions for the probability distribution functions of the replies. The application of our new approach on a number of LQN models shows that, even for models that violate those assumptions, it is far more accurate than previous approaches and it yields an error less than 10% for most example models.
Year
DOI
Venue
2007
10.1145/1216993.1217007
WOSP
Keywords
Field
DocType
thread service time,quorum response time,deriving distribution,layered queueing network,new analytic approach,performance modeling language,new approach,accurate estimation,lqn model,previous approach,probability distribution function,time distribution,quorum scheme,replication,order statistic,distribution functions,distributed system,distribution function,order statistics
Expression (mathematics),Computer science,Modeling language,Response time,Theoretical computer science,Layered queueing network,Probability distribution,Queueing theory,Order statistic,Special case
Conference
ISBN
Citations 
PageRank 
1-59593-297-6
3
0.49
References 
Authors
27
3
Name
Order
Citations
PageRank
Tariq Omari1233.22
Salem Derisavi247826.96
Greg Franks340929.08