(n, k) fork-join queues are prevalent in popular distributed systems, erasure coding based cloud storages, and modern network protocols like multipath routing, estimating the sojourn time of such queues is thus critical for the performance measurement and resource plan of computer clusters. However, the estimating keeps to be a well-known open challenge for years, and only rough bounds for a limited range of load factors have been given. This paper developed a closed-form linear transformation technique for jointly-identical random variables: An order statistic can be represented by a linear combination of maxima. This brand-new technique is then used to transform the sojourn time of non-purging (n, k) fork-join queues into a linear combination of the sojourn times of basic (k, k), (k + 1, k + 1), ..., (n, n) fork-join queues. Consequently, existing approximations for basic fork-join queues can be bridged to the approximations for non-purging (n, k) fork-join queues. The uncovered approximations are then used to improve the upper bounds for purging (n, k) fork-join queues. Simulation experiments show that this linear transformation approach is practiced well for moderate n and relatively large k.
For @math exponential fork-join queues, the most influential approximation work was proposed by in 1988 @cite_20 , which is based on the fact that the sojourn times @math of sub-tasks @math are associated rvs @cite_7 , whose maximum can be bounded by the maximum of their iid equivalents. The lower bound is obtained by neglecting queueing effects. The approximation is a linear mixture of the upper and lower bounds. Parameters of the mixture are learned based on the mean sojourn times of jobs sampled from simulated basic fork-join queues. @cite_3 improved the lower bound by using an staging analysis technique @cite_16 based on the memory-less property of the exponential service time distribution, and use the mean value of Nelson's upper bound and the staging lower bound as the approximation. According to experiments in @cite_4 , Nelson's approximation is still the most reliable one for exponential queues, compared to following works including @cite_22 and @cite_3 .
@cite_4 @cite_22 @cite_7 @cite_3 @cite_16 @cite_20
618449037 1968846052 2013002076 2152474925 1992580876 1998066559
Fork-join queueing networks model a network of parallel servers in which an arriving job splits into a number of subtasks that are serviced in parallel. Fork-join queues can be used to model disk arrays. A response time approximation of the fork-join queue is presented that attempts to comply with the additional constraints of modelling a disk array. This approximation is compared with existing analytical approximations of the fork-join queueing network. 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. Our starting point is a formula for the heavy traffic limit of two-dimensional Fork-Join queues that was obtained by the authors in [17,20]. 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 K-dimensional systems with general inter-arrival and service distributions. By combining this heavy traffic limit with light traffic limits, we generate interpolation approximations for the Fork-Join queue, which agree extremely well with simulation results. Fork-join structures have gained increased importance in recent years as a means of modeling parallelism in computer and storage systems. The basic fork-join model is one in which a job arriving at a parallel system splits into K independent tasks that are assigned to K unique, homogeneous servers. In the paper, a simple response time approximation is derived for parallel systems with exponential service time distributions. The approximation holds for networks modeling several devices, both parallel and nonparallel. (In the case of closed networks containing a stand-alone parallel system, a mean response time bound is derived.) In addition, the response time approximation is extended to cover the more realistic case wherein a job splits into an arbitrary number of tasks upon arrival at a parallel system. Simulation results for closed networks with stand-alone parallel subsystems and exponential service time distributions indicate that the response time approximation is, on average, within 3 percent of the seeded response times. Similarly, simulation results with nonexponential distributions also indicate that the response time approximation is close to the seeded values. Potential applications of our results include the modeling of data placement in disk arrays and the execution of parallel programs in multiprocessor and distributed systems. Probability and Statistics with Reliability, Queuing and Computer Science Applications, Second Edition, offers a comprehensive introduction to probabiliby, stochastic processes, and statistics for students of computer science, electrical and computer engineering, and applied mathematics. Its wealth of practical examples and up-to-date information makes it an excellent resource for practitioners as well. An approximation technique, called scaling approximation, is introduced and applied to the analysis of homogeneous fork join queuing systems consisting of K>or=2 servers. The development of the scaling approximation technique is guided by both experimental and theoretical considerations. The approximation is based on the observation that there exist upper and lower bounds on the mean response time that grow at the same rate as a function of K. Simple, closed-form approximate expressions for the mean response time are derived and compared to simulation results. The relative error in the approximation is less than 5 for K >