Optimal Slicing and Scheduling with Service Guarantees in Multi-Hop Wireless Networks

We analyze the problem of scheduling in wireless networks to meet end-to-end service guarantees. Using network slicing to decouple the queueing dynamics between flows, we show that the network's ability to meet hard throughput and deadline requirements is largely influenced by the scheduling policy. We characterize the feasible throughput/deadline region for a flow under a fixed route and set of slices, and find throughput- and deadline-optimal policies for a solitary flow. We formulate the feasibility problem for multiple flows in a general topology as a mixed-integer program, and show that it grows exponentially in the size of the network. Drawing on results from the solitary flow setting, we show that scheduling links in a regular fashion leads to smaller delay, and we derive tighter upper bounds on end-to-end delay for regular schedules. Finally, we design a polynomial-time algorithm that returns an (almost) regular schedule, optimized to meet service guarantees for all flows.