Pathwise Performance of Debt Based Policies for Wireless Networks with Hard Delay Constraints Conference Paper uri icon


  • Hou et al have introduced a framework to serve clients over wireless channels when there are hard deadline constraints along with a minimum delivery ratio for each client's flow. Policies based on "debt," called maximum debt first policies (MDF), were introduced and shown to be timelythroughput optimal. By "timely-throughput optimality" it is meant that if there exists a policy that fulfils a set of clients with a given vector of delivery ratios and a vector of channel reliabilities, then the MDF policy will also fulfill them. The debt of a user is the difference between the number of packets that should have been delivered so as to meet the delivery ratio and the number of packets that have been delivered for that client. The MDF policy prioritizes the clients in decreasing order of debts at the beginning of every period. Note that a throughput optimal policy only guarantees that lim inf T 1/ T Tt=1 1{client n's packet is delivered in frame t} qi , where the right hand side is the required delivery ratio for client i. Thus, it only guarantees that the debts of each user are o(T), and can be otherwise arbitrarily large. This raises the interesting question about what is the growth rate of the debts under the MDF policy. We show the optimality of MDF policy in the case when the channel reliabilities of all users are same, and obtain performance bounds for the general case. We characterize the performance by almost sure bounds on lim sup t d i (t) /(t) for all i, where (t) = 2t log log t. 2013 IEEE.

name of conference

  • 52nd IEEE Conference on Decision and Control

published proceedings


author list (cited authors)

  • Singh, R., Him, I., & Kumar, P. R.

citation count

  • 9

complete list of authors

  • Singh, Rahul||Him, I-Hong||Kumar, PR

publication date

  • January 2013