Handling Decisions and Traffic Dependencies in Layered Queueing Networks

A Layered Queueing Network (LQN) is a recognized performance modelling technique for performance prediction and evaluation of distributed systems. However, at present LQNs do not handle models with state-based behaviour such as timeouts and aborts, called ‘decisions’ here. This research extends LQNs by incorporating decisions into the model. The XML input language used to describe LQNs has been extended to handle these decisions. Both the LQN simulator, lqsim, and analytic solver, lqns, were then modified to solve models with decisions. The analytic solver uses decomposition and mean value analysis to solve models. Unfortunately, mean value analysis cannot be used to solve models with state-based behaviour. To overcome this limitation, a new approach called Dynamic Parameter Substitution (DPS) is used where intermediate results found while solving the model are used to alter the input parameters for subsequent iterations of the solution. To accomplish this goal, Layered Queueing eXperiment (LQX) language functions were derived to handle timeout and retry decisions and to handle fair-share queueing. The results from solving models using DPS were compared to results found from hybrid modelling, simulation, and where feasible, Petri nets. This research also improves the accuracy of the LQN analytic solver when solving models with traffic dependencies, namely interlocking and sub-chain dependent behaviour. Interlocking occurs from the decomposition of the model into submodels; a single customer from an upper submodel may appear as two or more customers in lower level submodels. Some forms of interlocks were handled by the previous solutions, but with some limitations. Sub-chain dependencies are hidden more deeply in LQN models, and are handled for the first time. Sub-chain dependencies occur when traffic from multiple independent clients share a common intermediate server then diverges to lower level servers when this server is acting as a source of customers. This research presents a generalized solution to handle more general cases of interlocks and sub-chain dependencies. The results of the improved solution have good accuracy compared with simulation results and the problems of the extraneous delays and infeasible utilizations are eliminated.