(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
2094799119 2015774390 2152474925 1998066559
Approximation techniques are developed to evaluate the performance of symmetric fork-join synchronization delays for K M G 1 queues. For a server utilization spl rho , 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: R sub K sup F 1 ( spl rho )=R sub 1 ( spl rho )+F sub K spl alpha sub K ( spl rho ) spl sigma sub 1 ( spl rho ), where F sub K is obtained from the previous equation at spl rho =0, R sub 1 ( spl rho ) and spl sigma sub 1 ( spl rho ) are the mean and the standard deviation of response time at any one of the queues, respectively, and spl alpha sub K ( spl rho ) is a low-degree service-time distribution dependent polynomial in spl rho , 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. In a Fork-Join (FJ) queueing system an upstream fork station splits incoming jobs into N tasks to be further processed by N parallel servers, each with its own queue; the response time of one job is determined, at a downstream join station, by the maximum of the corresponding tasks' response times. This queueing system is useful to the modelling of multi-service systems subject to synchronization constraints, such as MapReduce clusters or multipath routing. Despite their apparent simplicity, FJ systems are hard to analyze. This paper provides the first computable stochastic bounds on the waiting and response time distributions in FJ systems. We consider four practical scenarios by combining 1a) renewal and 1b) non-renewal arrivals, and 2a) non-blocking and 2b) blocking servers. In the case of non blocking servers we prove that delays scale as O(logN), a law which is known for first moments under renewal input only. In the case of blocking servers, we prove that the same factor of log N dictates the stability region of the system. Simulation results indicate that our bounds are tight, especially at high utilizations, in all four scenarios. A remarkable insight gained from our results is that, at moderate to high utilizations, multipath routing 'makes sense' from a queueing perspective for two paths only, i.e., response times drop the most when N = 2; the technical explanation is that the resequencing (delay) price starts to quickly dominate the tempting gain due to multipath transmissions. 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. 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 >