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

Worst case end-to-end response times for non-preemptive FP/DP* scheduling

Steven Martin Pascale Minet 1
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : In this paper, we are interested in real-time flows requiring quantitative and deterministic Quality of Service (QoS) guarantees. We focus more particularly on two QoS parameters: the worst case end-to-end response time and jitter. We consider a non-preemptive scheduling of flows, called FP/DP*, combining fixed priority and dynamic priority, where the dynamic priority of a flow packet is assigned on the first node visited by the packet in the network. Examples of such a scheduling are FP/FIFO* and FP/EDF*. With any flow is associated a fixed priority denoting the importance of the flow from the user point of view. The arbritation between packets having the same fixed priority is done according to their dynamic priority. A packet can be transmitted only if (i) there is no packet having a higher fixed priority and (ii) there is no packet having a higher dynamic priority. A classical approach used to compute the worst case end-to-end response time is the holistic one, but it leads to pessimistic upper bounds. We propose the trajectory approach to improve the accuracy of the results. Indeed, the trajectory approach only considers worst case scenarios experienced by a flow along its trajectory. It then eliminates scenarios that cannot occur in the network.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:57:07 PM
Last modification on : Friday, February 4, 2022 - 3:07:58 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:32:01 PM


  • HAL Id : inria-00070588, version 1



Steven Martin, Pascale Minet. Worst case end-to-end response times for non-preemptive FP/DP* scheduling. [Research Report] RR-5418, INRIA. 2004, pp.26. ⟨inria-00070588⟩



Record views


Files downloads