Packet Scheduling (EDF)

Every time you make a video call, your router faces hundreds of decisions per second: this packet carries your voice, that one carries a web image, another is a background update. They all want the wire at the same time, but only one can go first.

The naive answer — first come, first served — turns out to be terrible for voice and video. Those flows have deadlines: a voice packet that arrives 200 ms late is useless, while a background update can wait an extra second without anyone noticing.

Earliest-Deadline-First (EDF) is the scheduling rule that was proven optimal for exactly this situation by C. L. Liu and James W. Layland in 1973. The idea is as simple as it sounds: always send the packet whose deadline is closest. What makes EDF remarkable is not the idea itself — it is the proof that no other rule can do better when the link has enough capacity to meet all deadlines at all.

The demo below runs two schedulers side by side on the same queue of packets. Each packet has an arrival time, a size (transmission time), and a deadline. The link can send one packet at a time.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls">
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="lanes">
  <div class="lane">
    <div class="lane-title">FIFO</div>
    <div id="fifo-track" class="track"></div>
    <div class="lane-stat" id="fifo-stat"></div>
  </div>
  <div class="lane">
    <div class="lane-title">EDF</div>
    <div id="edf-track" class="track"></div>
    <div class="lane-stat" id="edf-stat"></div>
  </div>
</div>
<div id="legend" class="legend">
  <span class="leg-ok">&#9632; {{legend_ok}}</span>
  <span class="leg-miss">&#9632; {{legend_miss}}</span>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; margin-bottom: .8rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.lanes { display: flex; gap: 1rem; }
.lane { flex: 1; }
.lane-title { font-weight: 700; font-size: .85rem; margin-bottom: .35rem;
              text-transform: uppercase; letter-spacing: .04em; color: #1d3557; }
.track { display: flex; flex-wrap: wrap; gap: 3px; min-height: 60px;
         padding: 4px; background: #f0f3f6; border-radius: 6px; }
.pkt { width: 36px; height: 36px; border-radius: 5px; display: flex;
       align-items: center; justify-content: center; font: 700 11px ui-monospace,monospace;
       border: 2px solid transparent; transition: background .25s, border-color .25s; }
.pkt.pending { background: #c9ccd1; border-color: #adb1b8; color: #333; }
.pkt.sending { background: #ffd166; border-color: #e0aa3b; color: #333;
               animation: pulse .5s infinite alternate; }
.pkt.ok { background: #2dc653; border-color: #22a344; color: #fff; }
.pkt.miss { background: #e63946; border-color: #c92f3c; color: #fff; }
@keyframes pulse { from { opacity: 1; } to { opacity: .6; } }
.lane-stat { font-size: .82rem; font-weight: 600; margin-top: .4rem; min-height: 1.3em; }
.lane-stat.ok-all { color: #0a7d33; }
.lane-stat.some-miss { color: #c92f3c; }
.legend { display: flex; gap: 1rem; margin-top: .6rem; font-size: .8rem; color: #555; }
.leg-ok { color: #2dc653; }
.leg-miss { color: #e63946; }

// Code not found

FIFO sends packets in arrival order and often misses deadlines for small, urgent packets that arrive behind large slow ones. EDF always picks the packet with the earliest deadline — under feasible load it meets every deadline, and even when overloaded it misses as few as possible.

EDF has a pleasantly clean theoretical story — and a messier one lurking just behind it.

The good news: EDF is optimal. Liu and Layland's 1973 theorem states that on a single processor (or link), if any schedule can meet all deadlines, EDF can too. The proof is an exchange argument: if you ever send a later-deadline packet before an earlier-deadline one, swapping them can only help. Sorting by deadline costs $O(n \log n)$ and that is all.

The bad news: "feasible" is a condition, not a guarantee. Whether a given set of periodic tasks can ever be scheduled without missing deadlines — the feasibility problem — is decidable in polynomial time for fixed-priority schemes, but becomes NP-hard the moment you add constraints like shared resources, dependencies, or multiple processors. Even for EDF on two processors, deciding feasibility is NP-complete in the strong sense.

Admission control is the practical response: before accepting a new flow, the router checks that the enlarged workload is still feasible. That check is cheap for a single link (utilization $\leq 1$) but expensive in general networks. The gap between "schedule what you have" (easy, $O(n \log n)$) and "decide what to accept" (hard, potentially NP) is the real algorithmic tension in network quality-of-service. Compare with scheduling where similar tensions arise in job-shop contexts.

The "always serve the most urgent request first" principle shows up wherever a deadline missed is a service failed:

• Voice and video over IP: RTP packets carrying a phone call have strict playout deadlines. EDF (or its weighted variant WFQ) is the backbone of QoS on modern routers that guarantee call quality under congestion.
• Real-time operating systems: embedded controllers in cars, planes and medical devices use EDF or rate-monotonic variants to certify that safety-critical tasks will always finish on time.
• Satellite and wireless links: bandwidth is scarce, propagation delays are large, and different traffic classes (control signals, telemetry, video) have wildly different deadlines — EDF-based frame scheduling is standard.
• Database and cloud systems: query SLAs, checkpoint writers and replication streams all benefit from deadline-aware scheduling when the disk or network becomes a bottleneck.

EDF is a solved problem in the single-resource case — what keeps researchers busy is the multi-resource, multi-hop version that connects directly to load balancing and general resource-constrained scheduling.

Earliest-Deadline-First earns its place in the canon with a proof as clean as its rule: swap any out-of-deadline-order pair and you can only improve things. The single-resource case is fully solved — $O(n \log n)$, optimal, done.

The interesting difficulty begins the moment you add a second resource, a shared lock, or a second network hop. Those extensions turn a solved problem into NP-hard territory, which is why admission control, multiprocessor scheduling, and network-wide QoS remain active research areas half a century after Liu and Layland wrote their theorem.

Next time your video call stays crisp through a congested Wi-Fi link, you are likely benefiting from a scheduler that is, at its core, nothing more than sorting by urgency — and being able to prove that nothing smarter was needed.