Approximate solutions for M/G/1 fork/join synchronization

Abstract

Approximation techniques are developed to evaluate the performance of symmetric fork-join synchronization delays for K M/G/1 queues. For a server utilization ρ, the mean response time for fork-join requests is expressed as the sum of the mean response time at one of the queues and the mean synchronization delay as follows: RKF/J(ρ) = R1(ρ) + FKαK(ρ)σ1(ρ), where FK is obtained from the previous equation at ρ = 0 (since αK(0) exterior product = 1), R1(ρ) and σ1(p) are the mean and the standard deviation of response time at any one of the queues, respectively, and αK(ρ) is a low-degree service-time distribution dependent polynomial in ρ, whose coefficients are determined from simulation results. We also use simulation results to show that when fork-join requests share the servers with local requests, a good approximation (and an upper bound) to the fork-join response time is obtained by treating the components of fork-join response time as independent, i.e., the mean fork-join response time can be approximated by the expected value of the maximum of the response times at the K queues.