Segment EDF: A Scheduling Policy With Tight Deterministic Latency Under Multi-Hop Networks

We investigate tight end-to-end delay guarantees for real-time flows with stochastic arrivals in multi-hop networks. The existing multi-hop scheduling policy either only serves for real-time flows with deterministic arrivals or cannot offer a tight end-to-end delay guarantee for multi-hop flows. In this paper, we prove a closed-form formula, which offers a sufficient and necessary condition for the EDF (Earliest Deadline First) scheduling policy to meet all the end-to-end deadlines for flows with stochastic arrivals in converge-cast tree networks. To the best of our knowledge, this is the first formula that characterizes the exact schedulability region for EDF in multi-hop networks. Moving beyond converge-cast tree networks to general multi-hop networks, we introduce the Segment EDF approach. This method partitions a general network into multiple converge-cast networks using a novel concept called the critical links. By determining segment deadlines within the schedulability region of each converge-cast tree, Segment EDF offers a tight end-to-end delay guarantee for each flow. We present a theoretical analysis showcasing the superior performance of Segment EDF over the existing scheduling policy of hop-by-hop EDF. Furthermore, we evaluate the performance of Segment EDF based on two key metrics: guaranteed flow completion time and admission ratio, in both real-world and synthetic networks. Our simulation results show that Segment EDF can provide 61.31%-96.4% tighter end-to-end delay guarantee and increase admission ratio by about 3.52%-107.59% for sequential arrival flow set and 1.04%-95.50% for batch arrival flow set than hop-by-hop EDF.