Analysis and simulation of a fair queueing algorithm

We discuss gateway queueing algorithms and their role in controlling congestion in datagram networks. A fair queueing algorithm, based on an earlier suggestion by Nagle, is proposed. Analysis and simulations are used to compare this algorithm to other congestion control schemes. We find that fair queueing provides several important advantages over the usual first-come-first-serve queueing algorithm: fair allocation of bandwidth, lower delay for sources using less than their full share of bandwidth, and protection from ill-behaved sources.

• Publication year

  1989

• Venue

  Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication

• Publication date

  1989-08-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/75246.75248
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A new architecture for packet switching network protocols

  1989cited by this paper
• Queueing disciplines and passive congestion control in byte-stream networks

  1989cited by this paper
• Congestion avoidance and control

  1988cited by this paper
• Nest: A Network Simulation and Prototyping Tool

  1988cited by this paper
• The fuzzball

  1988cited by this paper
• Queuing algorithm to provide type-of-service for IP links

  1988cited by this paper
• Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Part III - Analysis

  1987cited by this paper
• Fast switching and fair control of congested flow in broadband networks

  1987cited by this paper
• On Packet Switches with Infinite Storage

  1987cited by this paper
• The NSFNET backbone network

  1987cited by this paper
• Performance analysis and application of a two-priority packet queue

  1987cited by this paper
• Improving round-trip time estimates in reliable transport protocols

  1987cited by this paper
• Round robin scheduling for fair flow control in data communication networks

  1986cited by this paper
• Protocol for providing the connectionless mode network services

  1984cited by this paper
• Queueing and framing disciplines for a mixture of data traffic types

  1984cited by this paper
• Congestion control in IP/TCP internetworks

  1984cited by this paper
• Dynamic Control of Session Input Rates in Communication Networks

  1982cited by this paper
• Flow Control: A Comparative Survey

  1980cited by this paper

• Delta Fair Sharing: Performance Isolation for Multi-Tenant Storage Systems

  2026cites this paper
• Bring Your Own Objective: Inter-operability of Network Objectives in Datacenters

  2026cites this paper
• Model Predictive Congestion Control for Data Center Networks

  2026cites this paper
• Enabling Multi-Protocol Deployment in Polymorphic Networks

  2026cites this paper
• NOS-Gate: Queue-Aware Streaming IDS for Consumer Gateways under Timing-Controlled Evasion

  2026cites this paper
• Dynamic Queuing for Approximate Fairness in Programmable Shared Memory Switches

  2025cites this paper
• A Survey on Flash-Memory Storage Systems: A Host-Side Perspective

  2025cites this paper
• A Lightweight Asynchronous Scheduling Solution for Large-scale Deterministic Networks

  2025cites this paper
• Ares: Fair and Efficient Scheduling of Deep Learning Jobs with Elastic Fair Queuing

  2025cites this paper
• A Scalable and Overflow-Tolerant Mechanism for Minimum Virtual Time Tracking

  2025cites this paper
• Dynamic Predictive Feedback Mechanism for Intelligent Bandwidth Control in Future SDN Networks

  2025cites this paper
• Fast and Fair Training for Deep Learning in Heterogeneous GPU Clusters

  2025cites this paper
• Optimizing Multi-DNN Inference on Mobile Devices through Heterogeneous Processor Co-Execution

  2025cites this paper
• Undermining Delay-based QUIC Congestion Control: A Receiver-driven Attack via Crafted Host Delays

  2025cites this paper
• SW-EDF: A Single-Iteration Algorithm for Combined Input- and Output-Queued Switching

  2025cites this paper
• EP-AQM: A Programmable Packet Scheduling Method Based on Eligibility Predicate

  2025cites this paper
• Total Link Service Rate Estimation With Packet Metadata

  2025cites this paper
• On-Demand Regular Expression Matching on FPGAs for Efficient Deep Packet Inspection

  2025cites this paper
• Towards Fair and QoS-Aware Bandwidth Allocation in Next-Generation Multi-Gigabit WANs

  2025cites this paper
• Properties of Horizontal Pod Autoscaling Algorithms and Application for Scaling Cloud-Native Network Functions

  2025cites this paper
• The Streaming Batch Model for Efficient and Fault-Tolerant Heterogeneous Execution

  2025cites this paper
• Equinox: Holistic Fair Scheduling in Serving Large Language Models

  2025cites this paper
• Geoduck: Nanosatellite Constellation Scheduling for Low Latency Event Detection

  2025cites this paper
• Söze: One Network Telemetry Is All You Need for Per-flow Weighted Bandwidth Allocation at Scale

  2025cites this paper
• CT-PIFO: A Congruity Tree Based Packet Scheduler to Improve Flow Completion Time

  2025influential citation
• Adaptive MAC Layer Scheduling Mechanism for Multimedia Traffic Optimization in Dynamic Network Topologies

  2025cites this paper
• Creating General User Models from Computer Use

  2025cites this paper
• Detecting Stragglers in Programmable Data Plane

  2025cites this paper
• Poly-HQoS: a polymorphic packet scheduler for traffic isolation in multi-tenant cloud environment

  2025influential citation
• P3PO: Parallel Processing For Priority Ordering In Programmable Schedulers

  2025cites this paper
• Proportional Fairness and Isolation for Serverless Applications over FaaS Platforms

  2025cites this paper
• DFQ+: Dynamic queuing for approximate fairness in programmable shared memory switches

  2025cites this paper
• Adaptive Approximate Fair Queueing for Shared-Memory Programmable Switches

  2024cites this paper
• Optimal Resource Efficiency with Fairness in Heterogeneous GPU Clusters

  2024cites this paper
• Inversion impact of approximate PIFO to Start-Time Fair Queueing

  2024cites this paper
• XDQ: Enhancing XDP with Queuing and Packet Scheduling

  2024cites this paper
• CIPO: Efficient, lightweight and programmable packet scheduling

  2024cites this paper
• Chronicles of Jockeying in Queuing Systems

  2024cites this paper
• Fair Set Cover

  2024cites this paper
• DNS Congestion Control in Adversarial Settings

  2024influential citation
• Principles for Internet Congestion Management

  2024cites this paper
• EDM: An Ultra-Low Latency Ethernet Fabric for Memory Disaggregation

  2024influential citation
• Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming

  2024cites this paper
• Research on Dynamic Traffic Scheduling Algorithm Based on Huawei Network Equipment

  2024cites this paper
• Ensuring Fair LLM Serving Amid Diverse Applications

  2024cites this paper
• Programmable Cycle-Specified Queue for Long-Distance Industrial Deterministic Packet Scheduling

  2024cites this paper
• vPIFO: Virtualized Packet Scheduler for Programmable Hierarchical Scheduling in High-Speed Networks

  2024cites this paper
• Managing and Decreasing Power Consumption of Devices in a Smart City Environment

  2024cites this paper
• DR-PIFO: A Dynamic Ranking Packet Scheduler Using a Push-In-First-Out Queue

  2024cites this paper
• Enhancing Fairness for Approximate Weighted Fair Queueing With a Single Queue

  2024cites this paper
• SimPFair: tight fairness at low cost

  2024cites this paper
• Opportunistic Scheduling for Users with Heterogeneous Minimum Rate QoS Requirements

  2024cites this paper
• Towards providing reliable job completion time predictions using PCS

  2024influential citation
• Recent trends and future directions of congestion management strategies for routing in IoT-based wireless sensor network: a thematic review

  2024cites this paper
• Zero-setup Intermediate-rate Communication Guarantees in a Global Internet

  2024cites this paper
• Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning

  2024cites this paper
• BFQ, Multiqueue-Deadline, or Kyber? Performance Characterization of Linux Storage Schedulers in the NVMe Era

  2024cites this paper
• Understanding Routable PCIe Performance for Composable Infrastructures

  2024cites this paper
• Enforcing Fairness in the Traffic Policer Among Heterogeneous Congestion Control Algorithms

  2024cites this paper
• Sifter: An Inversion-Free and Large-Capacity Programmable Packet Scheduler

  2024cites this paper
• A Systematic Configuration Space Exploration of the Linux Kyber I/O Scheduler

  2024cites this paper
• D-PIFO: A Dynamic Priority Scheduling Algorithm for Performance-Critical Packets Based on the Programmable Data Plane

  2024cites this paper
• Fairness in Serving Large Language Models

  2023cites this paper
• Enabling Users to Control their Internet

  2023cites this paper
• Octopus: In-Network Content Adaptation to Control Congestion on 5G Links

  2023cites this paper
• To Work-Conserving Packet Scheduling by Load Balance for VOQ Switches

  2023cites this paper
• Janus: Latency-Aware Traffic Scheduling for IoT Data Streaming in Edge Environments

  2023cites this paper
• Energy Time Fairness: Balancing Fair Allocation of Energy and Time for GPU Workloads

  2023influential citation
• Anticipatory Resource Allocation for ML Training

  2023cites this paper
• QVISOR: Virtualizing Packet Scheduling Policies

  2023cites this paper
• Analysis of New Energy Oriented Electric Power Protection Service Queue Scheduling Mechanism

  2023cites this paper
• BMW Tree: Large-scale, High-throughput and Modular PIFO Implementation using Balanced Multi-Way Sorting Tree

  2023cites this paper
• DDPG Based Dynamic Scheduling Optimization Mechanism in Real Switch

  2023cites this paper
• RIFO: Pushing the Efficiency of Programmable Packet Schedulers

  2023cites this paper
• Revisiting Weighted AIMD-based Congestion Control: A Comprehensive Perspective

  2023cites this paper
• This paper is included in the Proceedings of the 17th USENIX Symposium on Operating Systems Design and Implementation.

  2023cites this paper
• Date of publication xxxx 00, 0000, date of current version xxxx 00, 0000

  2023cites this paper
• Dragonfly: In-Flight CCA Identification

  2023cites this paper
• How I Learned to Stop Worrying About CCA Contention

  2023cites this paper
• Karma: Resource Allocation for Dynamic Demands

  2023cites this paper
• WFO: Cloud-Edge Cooperative Data Offloading Strategy Akin to Water Flow

  2023cites this paper
• Cilantro: Performance-Aware Resource Allocation for General Objectives via Online Feedback

  2023influential citation
• ProNet: Network-level Bandwidth Sharing among Tenants in Cloud

  2023influential citation
• Saba: Rethinking Datacenter Network Allocation from Application's Perspective

  2023cites this paper
• Achieving Near-Optimal Individual Regret & Low Communications in Multi-Agent Bandits

  2023influential citation
• On slots’ scheduling

  2023cites this paper
• Know Your Enemy To Save Cloud Energy: Energy-Performance Characterization of Machine Learning Serving

  2023cites this paper
• Reinforcement Learning based Scheduling Optimization Mechanism on Switches

  2023cites this paper
• An algorithm for scheduling of threads for system and application code split approach in dynamic malware analysis

  2023cites this paper
• Age of Information Analysis in Shared Edge Computing Servers

  2023cites this paper
• A Scheduling optimization Mechanism Combining Q-learning and Genetic Algorithm

  2023cites this paper
• OWFQ: Reducing Packet Drops for Approximate Weighted Fair Queueing with Calendar Queues

  2023cites this paper
• QGWFQS: A Queue-Group-Based Weight Fair Queueing Scheduler on FPGA

  2023cites this paper
• On optimization efficiency of scalability and availability of cloud-based software services using scale rate limiting algorithm

  2022cites this paper
• Max-Min Fairness based Scheduling Optimization Mechanism on Switches

  2022cites this paper
• WA-OPShare: Workload-Adaptive Over-Provisioning Space Allocation for Multi-Tenant SSDs

  2022cites this paper
• Justitia: Software Multi-Tenancy in Hardware Kernel-Bypass Networks

  2022cites this paper
• Hierarchical Multiresource Fair Queueing for Packet Processing

  2022cites this paper
• SurgeProtector: mitigating temporal algorithmic complexity attacks using adversarial scheduling

  2022cites this paper
• Controlling Congestion via In-Network Content Adaptation

  2022cites this paper