An approximate solution method for multiclass queueing networks with state dependent routing and window flow control

Abstract

A Multidass Queueing Network (MQN) Q ( N, .M ) consisting of M centres with index set .M and population vector N is partitioned into two subnetworks Q ( fJ -V , .M -1) ) and Q (V , V ) . The centres in Q (V , · V ) are further partitioned in to disjoint subnetworks called branches. A set of State Dependent Routing (SDR) probabilities is used to admit customers from Q ( N - V , .M - V ) into the individual branches of Q (V , V ) such that the customers are preferentially routed to the least congested branches. The SDR probabilities are such that Q( JV, .M ) has a product form solution . The S D R probabilities set a n upper bound o n the number of customers that can concurrently be present in each branch of Q (V , V ). In addition, an upper bound is set on the total number of customers that can concurrently be present in Q (V , V ) . Once this bound is reached, the product form SDR probabilities route customers around Q(V, 1) ). Exact solutions for MQNs with product form SDR are computationally intractable unless each SDR branch consists of a single centre only. An approximate solution method is therefore developed for MQNs with product form SDR. The approximate solution method is next extended to admit customers in first come first served order to Q (V , 1) ) when the total number of customers in Q (V , V ) reaches its upper bound. Such a combination of SDR and blocking can be used to model adaptive routing and window flow control mechanisms in computer networks. MQNs with SDR and blocking violate product form. Simulation solutions are used to test the accuracy of the approximation Jn method . The accuracy of the approximation technique is found to be good. Finally, the effects of population constrained SDR on network performance measures an investigated.