TY - GEN
T1 - On the performance of largest-deficit-first for scheduling real-time traffic in wireless networks
AU - Kang, Xiaohan
AU - Wang, Weina
AU - Jaramillo, Juan José
AU - Ying, Lei
PY - 2013
Y1 - 2013
N2 - This paper considers the problem of scheduling real-time traffic in wireless networks. We consider an ad hoc wireless network with general interference and general one-hop traffic. Each packet is associated with a deadline and will be dropped if it is not transmitted before the deadline expires. The number of packet arrivals in each time slot and the length of a deadline are both stochastic and follow certain distributions. We only allow a fraction of packets to be dropped. At each link, we assume the link keeps track of the difference between the minimum number of packets that need to be delivered and the number of packets that are actually delivered, which we call deficit. The largest-deficit-first (LDF) policy schedules links in descending order according to their deficit values, which is a variation of the largest-queue-first (LQF) policy for non-real-time traffic. We prove that the efficiency ratio of LDF can be lower bounded by a quantity that we call the real-time local-pooling factor (R-LPF). We further prove that given a network with interference degree β, the R-LPF is at least 1/(β + 1), which in the case of the one-hop interference model translates into an R-LPF of at least 1/3.
AB - This paper considers the problem of scheduling real-time traffic in wireless networks. We consider an ad hoc wireless network with general interference and general one-hop traffic. Each packet is associated with a deadline and will be dropped if it is not transmitted before the deadline expires. The number of packet arrivals in each time slot and the length of a deadline are both stochastic and follow certain distributions. We only allow a fraction of packets to be dropped. At each link, we assume the link keeps track of the difference between the minimum number of packets that need to be delivered and the number of packets that are actually delivered, which we call deficit. The largest-deficit-first (LDF) policy schedules links in descending order according to their deficit values, which is a variation of the largest-queue-first (LQF) policy for non-real-time traffic. We prove that the efficiency ratio of LDF can be lower bounded by a quantity that we call the real-time local-pooling factor (R-LPF). We further prove that given a network with interference degree β, the R-LPF is at least 1/(β + 1), which in the case of the one-hop interference model translates into an R-LPF of at least 1/3.
KW - Fluid limit
KW - Largest-deficit-first
KW - Local-pooling fluid factor
KW - Real-time scheduling
KW - Stability
UR - http://www.scopus.com/inward/record.url?scp=84882942305&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84882942305&partnerID=8YFLogxK
U2 - 10.1145/2491288.2491298
DO - 10.1145/2491288.2491298
M3 - Conference contribution
AN - SCOPUS:84882942305
SN - 9781450321938
T3 - Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)
SP - 99
EP - 108
BT - MobiHoc 2013 - Proceedings of the 14th ACM International Symposium on Mobile Ad Hoc Networking and Computing
T2 - 14th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2013
Y2 - 29 July 2013 through 1 August 2013
ER -