Orders and bounds for response times

Bruno Gaujal 1 Arie Hordijk Dinard Van Der Laan
1 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Which of two deterministic periodic admission sequences (periodic sequences of nonnegative integers) gives the smaller average expected waiting time has already been investigated. A partial order, called the cone order has been introduced, and it is shown that the average waiting time and more generally any multimodular function is monotone with respect to the cone order. It is natural to define a multimodular order by requiring that any multimodular function is monotone. In contrast to stochastic cases, where the convex order for stochastic admission sequences is used, we consider deterministic admission sequences in this paper. Note that deterministic admission sequences can only be ordered for all multimodular functions if they are equal. Therefore we consider multimodular functions with a fixed minimal point as we did with the cone order. We introduce the multimodular order and we show that the cone order is equivalent to the multimodular order. In section. the shift invariant counterparts of these orders are studied and it is shown that the regular admission sequence is the minimal point. For the optimal routing problem to n queues we derive that a lower bound is obtained by using regular admission sequences (or what is the same bracket sequences) with 'minimizing' routing fractions (densities) as admission sequences to all queues. But generally only in the routing to $n=2$ queues, the routing fractions will be balanceable and only in that case the admission sequences can be glued together and be made to a feasible routing policy.
Type de document :
[Intern report] A01-R-274 || gaujal01e, 2001, 14 p
Liste complète des métadonnées

Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:49:48
Dernière modification le : jeudi 11 janvier 2018 - 06:20:05


  • HAL Id : inria-00100699, version 1



Bruno Gaujal, Arie Hordijk, Dinard Van Der Laan. Orders and bounds for response times. [Intern report] A01-R-274 || gaujal01e, 2001, 14 p. 〈inria-00100699〉



Consultations de la notice