Overview
Fair Queuing approximates ideal bit-by-bit sharing by assigning virtual finish times and serving the smallest finish time first.
ExtendedSource checked
Fair Queuing
Schedules work so competing flows receive a fair share of service.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Scheduling
- Difficulty
- Advanced
- Family
- Fair Scheduling
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
virtual timeflow fairnesspriority queueservice share
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)
When to Use
- Use when multiple flows share one resource and starvation must be avoided.
- Use when network packet scheduling is a central requirement.
When Not to Use
- Avoid when strict priority or earliest-deadline behavior is required instead of fairness.
- Avoid when task priorities, durations, or fairness goals are unknown or unstable.
What It Does
- Tracks flows separately
- Assigns virtual finish times
- Serves work in fair order
Use Cases
- Network packet scheduling
- Shared service queues
- Bandwidth fairness
Inputs
- Queued jobs or packets
- Flow identifiers
- Service weights
Outputs
- Fair service order
Key Formulas (1)
Virtual finish time
finish = max(virtualtime, lastfinish flow) + size / weight
finish = max(virtual_time, last_finish_flow) + size / weightRanks queued work by when it would finish under ideal fair sharing.
Pseudocode
- 1.Assign each incoming job to a flow
- 2.Compute its virtual finish time
- 3.Insert it into a priority queue
- 4.Serve the job with the smallest virtual finish time
- 5.Update flow state
Canonical Example
- Input
- flows A and B both backlogged
- Output
- schedule alternates A and B
- Explanation
- Each flow receives comparable service over time.
Implementation Notes
- Keep virtual time calculations in one module to avoid inconsistent ordering.
- Track waiting time, service time, and queue state separately.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Using wall-clock arrival time directly does not model fair virtual service.
- A locally fair rule can still create starvation or poor latency under skewed workloads.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow packets from several flows interleaved by virtual finish time.
Step 1 of 5: Assign each incoming job to a flow
timelineNotes
Weighted variants let some flows receive larger shares while preserving fairness.
Sources (1)
What each reference supports for this entry.
Fair Queueing
PaperReference for fair queueing, virtual finishing times, and packet scheduling across competing flows.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageGeneralizesWeighted Round Robin
Fair queuing is a broader packet-scheduling model that weighted round robin approximates discretely.
Related Algorithms
Tags
SchedulingQueueLoad Balancing