Bounds on the mean delay in multiclass queueing networks under shortfall-based priority rules

Sridhar Seshadri, Michael Pinedo

Research output: Contribution to journalArticlepeer-review


A significant amount of recent research has been focused on the stability of multiclass open networks of queues (MONQs). It has been shown that these networks may be unstable under various queueing disciplines even when at each one of the nodes the arrival rate is less than the service rate. Clearly, in such cases the expected delay and the expected number of customers in the system are infinite. In this paper we propose a new class of scheduling rules that can be used in multiclass queueing networks. We refer to this class as the stable shortfall-based priority (SSBP) rules. This SSBP class itself belongs to a larger class of rules, which we refer to as the shortfall-based priority (SBP) rules. SBP is a generalization of the standard non-preemptive priority rule in which customers of the same priority class are served first-come, first-served (FCFS). Rules from SBP 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 class 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 how this inequality can be used to derive upper bounds for the delay when service times are bounded. Bounds for the expected delay of each class of customers in an MONQ are then obtained under the assumptions that the external arrival processes have i.i.d. interarrival times, the routings are deterministic and the service times at each step of the route are bounded. In order to derive these bounds for the average delay in an MONQ we make use of some of the classical ideas of Kingman.

Original languageEnglish (US)
Pages (from-to)329-350
Number of pages22
JournalProbability in the Engineering and Informational Sciences
Issue number3
StatePublished - 1998
Externally publishedYes

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Bounds on the mean delay in multiclass queueing networks under shortfall-based priority rules'. Together they form a unique fingerprint.

Cite this