Introduction

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.

Try It

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.

<!-- EDF vs FIFO packet scheduling demo — packets shown as colored tiles -->
<p class="hint">Eight packets share a single link — each has an arrival time, a transmission size, and a deadline. Watch FIFO and EDF race through the same queue: green = met deadline, red = missed.</p>
<div class="controls">
  <button id="btn-run" type="button">Run simulation</button>
  <button id="btn-reset" type="button" class="ghost">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; met deadline</span>
  <span class="leg-miss">&#9632; missed deadline</span>
</div>

/* Layout for two-lane EDF vs FIFO comparison */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// EDF vs FIFO simulation — same packet queue, two scheduling policies.
// EDF rule: always transmit the packet with the earliest (smallest) deadline.

// Fixed packet set — each has arrival time, transmission size, and deadline (all in ms).
// Fields: id (label), arrive (ms), size (ms of tx time), deadline (ms)
// Total work = 300 ms, max deadline = 350 ms => utilization 0.857 < 1 => EDF optimal.
const PACKETS = [
  { id: 'A', arrive: 0,  size: 30,  deadline: 120 },
  { id: 'B', arrive: 0,  size: 100, deadline: 350 },
  { id: 'C', arrive: 5,  size: 25,  deadline: 80  },
  { id: 'D', arrive: 10, size: 20,  deadline: 60  },
  { id: 'E', arrive: 30, size: 40,  deadline: 200 },
  { id: 'F', arrive: 60, size: 35,  deadline: 250 },
  { id: 'G', arrive: 80, size: 50,  deadline: 320 }
];

// Run a greedy simulation of the given policy on PACKETS.
function simulate(policy) {
  // deep copy so we never mutate the original
  const pkts = PACKETS.map(p => ({ ...p, finishTime: null }));
  const results = [];
  let t = 0;
  const pending = [];
  let pktIdx = 0;

  while (results.length < pkts.length) {
    // Admit all packets that have arrived by now.
    while (pktIdx < pkts.length && pkts[pktIdx].arrive <= t) {
      pending.push(pkts[pktIdx++]);
    }
    if (pending.length === 0) {
      // No packets ready; jump to next arrival.
      t = pkts[pktIdx].arrive;
      continue;
    }
    // Pick next packet according to policy.
    let chosen;
    if (policy === 'fifo') {
      chosen = pending.shift();
    } else {
      // EDF picks the packet with the smallest deadline.
      const minDl = Math.min(...pending.map(p => p.deadline));
      const idx = pending.findIndex(p => p.deadline === minDl);
      chosen = pending.splice(idx, 1)[0];
    }
    t += chosen.size;
    // Admit any packets that arrived while we were transmitting.
    while (pktIdx < pkts.length && pkts[pktIdx].arrive <= t) {
      pending.push(pkts[pktIdx++]);
    }
    results.push({ ...chosen, finishTime: t, missed: t > chosen.deadline });
  }
  return results;
}

const fifoResults = simulate('fifo');
const edfResults  = simulate('edf');

function buildTrack(containerId, results) {
  const el = document.getElementById(containerId);
  el.innerHTML = '';
  results.forEach(r => {
    const d = document.createElement('div');
    d.className = 'pkt pending';
    d.textContent = r.id;
    d.title = `${r.id}: arrive ${r.arrive}ms, size ${r.size}ms, deadline ${r.deadline}ms`;
    el.appendChild(d);
  });
}

function animateLane(containerId, statId, results, delay) {
  const track = document.getElementById(containerId);
  const cells = track.querySelectorAll('.pkt');
  const statEl = document.getElementById(statId);
  let i = 0;
  function next() {
    if (i > 0) {
      cells[i - 1].classList.remove('sending');
      cells[i - 1].classList.add(results[i - 1].missed ? 'miss' : 'ok');
    }
    if (i >= results.length) {
      const missed = results.filter(r => r.missed).length;
      if (missed === 0) {
        statEl.textContent = 'All deadlines met!';
        statEl.className = 'lane-stat ok-all';
      } else {
        statEl.textContent = i18nFmt('%n% deadline(s) missed.', { n: missed });
        statEl.className = 'lane-stat some-miss';
      }
      return;
    }
    cells[i].classList.add('sending');
    i++;
    // Step through one packet per animation frame.
    setTimeout(next, 400);
  }
  setTimeout(next, delay);
}

function run() {
  document.getElementById('btn-run').disabled = true;
  buildTrack('fifo-track', fifoResults);
  buildTrack('edf-track', edfResults);
  document.getElementById('fifo-stat').textContent = '';
  document.getElementById('edf-stat').textContent = '';
  animateLane('fifo-track', 'fifo-stat', fifoResults, 0);
  animateLane('edf-track', 'edf-stat', edfResults, 200);
}

function reset() {
  document.getElementById('btn-run').disabled = false;
  buildTrack('fifo-track', fifoResults);
  buildTrack('edf-track', edfResults);
  document.getElementById('fifo-stat').textContent = '';
  document.getElementById('edf-stat').textContent = '';
}

document.getElementById('btn-run').addEventListener('click', run);
document.getElementById('btn-reset').addEventListener('click', reset);
buildTrack('fifo-track', fifoResults);
buildTrack('edf-track', edfResults);
Result
Console

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.

The Real Complexity

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(nlog⁡n)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 ≤1\leq 1) but expensive in general networks. The gap between "schedule what you have" (easy, O(nlog⁡n)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.

Where It Matters

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.

Conclusion

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(nlog⁡n)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/packet-scheduling-edf/Content licensed under CC BY-NC 4.0.