Online Packet Scheduling With Hard Deadlines in Multihop Communication Networks
The problem of online job or 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 influences and is influenced by decisions on other hops and only a few provably efficient online scheduling algorithms exist in the multihop setting. The authors consider a general multihop network topology in which packets with various deadlines and weights arrive at and are destined to different nodes through given routes. They 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.