Optimal Online Scheduling With Arbitrary Hard Deadlines in Multihop Communication Networks

Abstract

The problem of online packet scheduling with hard deadlines has been studied extensively in the single-hop setting, whereas it is notoriously difficult in the multihop setting. This difficulty stems from the fact that packet scheduling decisions at each hop influence and are influenced by decisions on other hops, and only a few provably efficient online scheduling algorithms exist in the multihop setting. We consider a multihop wired network (interference-free and full duplex transmissions) in which packets with various deadlines and weights arrive at and are destined to different nodes through given routes. We study the problem of joint admission control and packet scheduling in order to maximize the cumulative weights of the packets that reach their destinations within their deadlines. We first focus on uplink transmissions in the tree topology and show that the well-known Earliest Deadline First algorithm achieves the same performance as the optimal offline algorithm for any feasible arrival pattern. We then address the general topology with multiple source-destination pairs, develop a simple online algorithm, and show that it is O(P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</sub> log P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</sub> )-competitive, where P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</sub> is the maximum route length among all packets. Our algorithm only requires information along the route of each packet, and our result is valid for general arrival samples. Moreover, we show that O(P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</sub> log P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</sub> )-competitive is the best any online algorithm can do. Via numerical results, we also show that our algorithm achieves performance that is comparable to the noncausal optimal offline algorithm. To the best of our knowledge, this is the first algorithm with a provable (based on a sample-path construction) competitive ratio, subject to hard deadline constraints for general network topologies.