The Trajectory Approach for the End-to-End Response Times with Non-preemptive FP/EDf

摘要

We focus on non-preemptive Fixed Priority (FP) scheduling. Unlike the classical approach, where flows sharing the same priority are assumed to be scheduled arbitrarily, we assume that these flows are scheduled Earliest Deadline First (EDF), by considering their absolute deadline on their first visited node. The resulting scheduling is called FP/EDF~*. In this paper, we establish new results for FP/EDF~* in a distributed context, first when flows follow the same sequence of nodes (the same path). We then extend these results when flows follow different paths. We show how to compute an upper bound on the end-to-end response time of any flow when the packet priority is computed on the first node and left unchanged on any subsequent node. This alleviates the packet processing in core nodes. For that purpose, we use a worst case analysis based on the trajectory approach, that is less pessimistic than classical approaches. We compare our results with those provided by the holistic approach: the benefit can be very high.