Interpolation Approximations for Symmetric Fork-Join Queues

Abstract

In this paper we propose a family of heuristic approximations for the expected response time of K-dimensional symmetric Fork-Join systems in statistical equilibrium with general inter-arrival and service time distributions. To do this, we rely on the light traffic interpolation technique popularized by Reiman and Simon. The starting point for our approach is the formula for the heavy traffic limit for two dimensional Fork-Join queues that was obtained in [17,19]. By observing a fortuitous agreement between the light traffic derivative and the heavy traffic limit for this system under Markovian assumptions. we are able to obtain an approximation to the heavy traffic limit for -dimensional systems with general inter-arrival and service distributions. By combining this heavy traffic limit with light traffic limits, we are able to obtain interpolation approximations for the Fork-Join queue which agree extremely well with simulation results.