BOUNDS ON THE MEAN DELAY IN MULTICLASS QUEUING-NETWORKS UNDER SHORTFALL-BASED PRIORITY RULES

A significant amount of recent research has been focused on the stabil ity of multiclass open networks of queues (MONQs), It has been shown t hat these networks may be unstable under various queueing disciplines even when at each one of the nodes the arrival rate is less than the s ervice rate. Clearly, in such cases the expected delay and the expecte d number of customers in the system are infinite. In this paper we pro pose a new class of scheduling rules that can be used in multiclass qu eueing networks. We refer to this class as the stable shortfall-based priority (SSBP) rules. This SSBP class itself belongs to a larger clas s of rules, which we refer to as the shortfall-based priority (SBP) ru les. SEP is a generalization of the standard nonpreemptive priority ru le in which customers of the same priority class are served first-come , first-served (FCFS), Rules from SEP can mimic FCFS as well as the so -called strict or head-of-the-line priority disciplines. We show that the use of any rule from the SSBP class ensures stability in a broad c lass of MONQs found in practice. We proceed with the construction of a sample path inequality for the work done by an SSBP server and show h ow this inequality can be used to derive upper bounds for the delay wh en service times are bounded. Bounds for the expected delay of each cl ass of customers in an MONQ are then obtained under the assumptions th at the external arrival processes have i.i.d. interarrival times, the routings are deterministic and the service times at each step of the r oute are bounded. In order to derive these bounds for the average dela y in an MONQ we make use of some of the classical ideas of Kingman.