On Erasure Broadcast Channels with Hard Deadlines

Many network applications, such as emergency messages, require reliable and predictable trans- missions. Despite outstanding progress in designing communication networks with high rate and low delays, communication with hard deadline constraint still remains a challenging problem. This work considers packet scheduling in a broadcast channel with packet erasures where several receivers expect to receive their own different messages (multiple unicast), each with possibly different hard deadline limitations. A novel metric is proposed and is evaluated: the global deadline outage probability, which is the probability that the communication deadline is not met for at least one of the users. The cut-set upper bound is derived and a scheduling policy is proposed to determine in each time slot, which receiver’s packets should be sent. This policy is optimal among all possible scheduling policies, i.e., it reaches all boundary points of cut-set upper bounds when the base station knows the erasure patterns for all the receivers before making the scheduling decision. A closed-form expression for the global deadline outage probability is obtained for two receivers and is plotted for several system parameters. These figures are not Monte-Carlo simulations, and therefore the obtained expression can be used for future downlink broadcast networks design. Another metric is also proposed and briefly discussed: the individual deadline outage probability, which gives the probability that the hard communication deadline is not met for each user exclusively. A scheduling policy is proposed for this case, which is shown to be optimal. Two more realistic scenarios where i) only the current channel state and ii) neither current nor any future channel state is known to the base station prior to make scheduling decision are also briefly discussed.