Scheduling for end-to-end deadline-constrained traffic with reliability requirements in multi-hop networks

We attack the challenging problem of designing a scheduling policy for end-to-end deadline-constrained traffic with reliability requirements in a multi-hop network. It is well-known that the end-to-end delay performance for a multi-hop flow has a complex dependence on the high-order statistics of the arrival process and the algorithm itself. Thus, neither the earlier optimization based approaches that aim to meet the long-term throughput demands, nor the solutions that focus on a similar problem for single-hop flows directly apply. Moreover, a dynamic programming-based approach becomes intractable for such multi-time scale Quality-of-Service(QoS)-constrained traffic in a multi-hop environment. This motivates us in this work to develop an alternative model that enables us to exploit the degree of freedom in choosing appropriate service discipline. Based on the new model, we propose two alternative solutions, first based on a Lyapunov-drift minimization approach, and second based on a novel relaxed optimization-formulation. We provide extensive numerical results to compare the performance of both of these solutions to throughput-optimal back-pressure-type schedulers and to longest waiting time based schedulers that have provably optimal asymptotic performance characteristics. Our results reveal that the dynamic choice of service discipline of our proposed solutions yields substantial performance improvements compared to both of these types of traditional solutions under non-asymptotic conditions.