HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 2:49:48 PM
Last modification on : Friday, February 4, 2022 - 3:33:35 AM


  • 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⟩



Record views