RANDOM TREES IN QUEUING-SYSTEMS WITH DEADLINES

We survey our research on scheduling aperiodic tasks in real-time syst ems in order to illustrate the benefits of modelling queueing systems by means of random trees. Relying on a discrete-time single-server que ueing system, we investigated deadline meeting properties of several s cheduling algorithms employed for servicing probabilistically arriving tasks, characterized by arbitrary arrival and execution time distribu tions and a constant service time deadline T. Taking a non-queueing th eory approach (i.e., without stable-stable assumptions) we found that the probability distribution of the random time Y-T where such a syste m operates without violating any task's deadline is approximately expo nential with parameter lambda(T) = 1/mu(T), with the expectation E[Y-T ] = mu(T) growing exponentially in T. The value mu(T) depends on the p articular scheduling algorithm, and its derivation is based on the com binatorial and asymptotic analysis of certain random trees. This paper demonstrates that random trees provide an efficient common framework to deal with different scheduling disciplines and gives an overview of the various combinatorial and asymptotic methods used in the appropri ate analysis.