The Solution of Homogeneous Queueing Networks with Many Job Classes

Two general-purpose algorithms exist for the solution of product-form queueing network models: convolution and mean-value analysis. Because the space and time complexity of both of these algorithms is exponential in the number of classes in the model, they are for most purposes useless for the solution of networks with many jobs (and few jobs per class). We describe a new algorithm, having polynomial space and time complexity, that is specifically designed for the solution of queueing networks in which the classes exhibit highly symmetric patterns and in which the service stations, whose behavior is the primary object of the evaluation, have identical service characteristics. This category of queueing networks arises naturally in the modeling of local area networks.