Scheduling for End-to-End Deadline-Constrained Traffic With Reliability Requirements in Multihop Networks

We attack the challenging problem of designing a scheduling policy for end-to-end deadline-constrained traffic with reliability requirements in a multihop network. It is well known that the end-to-end delay performance for a multihop 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-timescale quality-of-service (QoS)-constrained traffic in a multihop environment. This motivates us in this paper to develop a useful architecture that enables us to exploit the degree of freedom in choosing appropriate service discipline. Based on the new architecture, we propose three different approaches, each leading to an original algorithm. We study the performance of these algorithms in different scenarios to show both optimality characteristics and to demonstrate the favorable service discipline characteristics they possess. We provide extensive numerical results to compare the performance of all 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 nonasymptotic conditions.