Analytic solution of fair share scheduling in layered queueing networks

Fair share scheduling has been widely used in many distributed systems. Layered Queueing Networks (LQN) are a widely used performance evaluation technique for distributed systems. Therefore, being able to evaluate performance of systems using fair share scheduling is essential. However, Fair share scheduling in a LQN model could only be solved using simulation previously. A main concern of simulation is long execution times. This paper uses a method called ‘Dynamic Parameter substitutions’ (DPS) to solve the Fair share scheduling analytically. DPS is an iterative method to calculate state-based parameters using performance results that are found using Mean Value Analysis (MVA). The paper shows how DPS is integrated into the LQNS solver (LQNS-DPS), which makes solutions of models with fair scheduling both fast and scalable. LQNS-DPS was verified using two sets of models, both with cap and guarantee shares. Over 150 randomly parameterized models, throughput found using LQNS-DPS was on average no worse than 6% of the result found from simulation