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

Abstract

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, and show its equivalence to finding a bounded-cost cycle on an exponentially large graph, which is un-solvable in polynomial time by the best-known algorithm. Using a novel concept called delay deficit, we develop a sufficient condition for meeting deadlines as a function of inter-scheduling times, and show that regular schedules are optimal for satisfying this condition. Motivated by this, we design a polynomial-time algorithm that returns an (almost) regular schedule, optimized to meet service guarantees for all flows.