On the Performance of Largest-Deficit-First for Scheduling Real-Time Traffic in Wireless Networks

Xiaohan Kang, Weina Wang, Juan Jose Jaramillo, Lei Ying

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


This paper considers the problem of scheduling real-time traffic in wireless networks. We consider ad hoc wireless networks with general conflict graph-based interference model and single-hop traffic. Each packet is associated with a deadline and will be dropped if it is not transmitted before the deadline. The number of packet arrivals in each time-slot and the maximum delay before the deadline are independent and identically distributed across time. We require a minimum fraction of packets to be delivered. At each link, we assume the link keeps track of the difference between the minimum number of packets that need to be delivered so far and the number of packets that are actually delivered, which we call the deficit. The largest-deficit-first (LDF) policy schedules links in descending order according to their deficit values, which is a variation of the longest-queue-first (LQF) policy for non-real-time traffic. We prove that the efficiency ratio of LDF, which is the fraction of the throughput region that LDF can achieve for given traffic distributions, can be lower-bounded by a quantity that we call the real-time local-pooling factor (R-LPF). We further prove that a lower bound on the R-LPF can be related to the weighted sum of the service rates, with a special case of 1/(beta+1) by considering the uniform weight, where beta is the interference degree of the conflict graph. We also propose a heuristic consensus algorithm that can be used to obtain a good weight vector for such lower bounds for given network topology.

Original languageEnglish (US)
Article number6923479
Pages (from-to)72-84
Number of pages13
JournalIEEE/ACM Transactions on Networking
Issue number1
StatePublished - Feb 2016


  • Fluid limit
  • largest-deficit-first
  • local-pooling factor
  • real-time scheduling
  • stability

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'On the Performance of Largest-Deficit-First for Scheduling Real-Time Traffic in Wireless Networks'. Together they form a unique fingerprint.

Cite this