PROPERTIES AND PERFORMANCE BOUNDS FOR CLOSED FREE CHOICE SYNCHRONIZED MONOCLASS QUEUING-NETWORKS

Several proposals exist for the introduction of synchronization constraints into queueing networks (QN). We show that many monoclass QN with synchronizations can naturally be modeled with a subclass of Petri nets (PN) called free choice nets (FC), for which a wide gamut of qualitative behavioral and structural results have been derived. We use some of these net theoretic results to characterize the ergodicity, boundedness, and liveness of closed free choice synchronized queueing networks (FCSQN). Moreover, we define upper and lower throughput bounds based on the mean value of the service times, without any assumption on the probability distributions (thus including both the deterministic and the stochastic cases). We show that monotonicity properties exist between the throughput bounds and the parameters of the model in terms of population and service times. We propose (theoretically polynomial and practically linear complexity) algorithms for the computation of these bounds, based on linear programming problems defined on the incidence matrix of the underlying FC net. Finally, using classical laws from queueing theory, we provide bounds for mean queue lengths and response time.