In this paper we establish upper and lower bounds on the steady-state per-c
lass workload distributions in a single-server queue with multiple priority
classes. Motivated by communication network applications, the model has co
nstant processing rate and general input processes with stationary incremen
ts. The bounds involve corresponding quantities in related models with the
first-come first-served discipline. We apply the bounds to support a new no
tion of effective bandwidths for multi-class systems with priorities. We al
so apply the lower bound to obtain sufficient conditions for the workload d
istributions to have heavy tails. (C) 2000 Elsevier Science B.V. All rights
reserved.