TL;DR
This paper introduces Measurement-Based Fair Queuing (MBFQ), a novel two-tier scheduling algorithm for virtual switches that efficiently allocates outbound bandwidth to VMs proportionally to their purchased weights. MBFQ achieves this with minimal CPU overhead by separating coarse-grained, periodic bandwidth adjustments (macroscheduler) from fine-grained, per-packet pacing (microscheduler), making it suitable for modern cloud environments.
What Problem Does This Paper Address?
In cloud environments, virtual machines (VMs) running on a shared physical server need their outbound network bandwidth allocated fairly. The classical approach to "fair queuing" typically assumes tight integration between network hardware and schedulers, with per-packet feedback and cheap scheduler invocations. However, modern virtual switches, implemented in software and interacting with hardware NICs that batch transmissions (e.g., via Large Send Offload), break these assumptions. This leads to challenges in achieving fair allocation without incurring significant CPU overhead, which is costly for cloud providers. Existing solutions either require specialized hardware, are too CPU-intensive, or don't scale well in a distributed, multi-core software environment. The paper aims to provide a CPU-efficient, scalable, and fair bandwidth allocation mechanism for these virtualized environments.
Methods
The core innovation is MBFQ, a two-tier scheduling approach:
- Microscheduler: This component operates cheaply and paces individual VM transmissions using a token bucket mechanism. It's designed to be distributed across multiple CPU cores for scalability.
- Macroscheduler: This component runs periodically (every
Tseconds, e.g., 100ms) and is responsible for measuring VM bandwidth usage and redistributing tokens to the microschedulers. It adjusts the token bucket rates based on measured send rates (SR) and allocated rates (AR).
The algorithm has two phases:
- Phase 1 (Computing Target Rates): It calculates an ideal target rate (
TR) for each VM. If a VM is underutilizing its current allocation, itsTRmight be reduced to free up bandwidth. If a VM is fully utilizing its allocation and has pending demand, itsTRis gradually increased, with a staged approach to avoid over-allocation and ensure VMs can reach their minimum guaranteed bandwidth quickly. - Phase 2 (Preventing Congestion and Enforcing Fair Sharing): This phase adjusts the
TRs to ensure the total allocated bandwidth doesn't exceed link capacity. Any "remaining" bandwidth is then distributed proportionally to VMs based on their weights, ensuring leftover capacity is utilized.
Datasets
Not discussed in the paper. The evaluation uses a custom testbed with Dell PowerEdge R410 servers and Windows Server OS with Hyper-V.
Key Insights and Ideas
- The "Virtual Switch" Context is Crucial: The paper highlights how the specific constraints of software-based virtual switches (batched NIC feedback, CPU cost, multi-core scaling) necessitate a departure from traditional hardware-centric fair queuing algorithms.
- Two-Tier Scheduling for Efficiency: Separating the periodic, heavier computation of the macroscheduler from the lightweight, per-packet pacing of the microscheduler is key to achieving low CPU overhead and scalability.
- Measurement is Key: MBFQ relies on measuring VM send rates to dynamically adjust allocations, making it adaptive to changing demands.
- Staged Ramp-Up for Fairness and Efficiency: The gradual increase in allocated bandwidth for VMs with pending demand balances the need for quick access to purchased capacity with the risk of allocating bandwidth that might not be immediately usable.
- Reclaim Timer Trade-off: Reclaiming idle bandwidth too quickly can lead to spurious reclamation from VMs experiencing short bursts. A moderate reclaim timer (e.g., 500ms) is a compromise between rapid redistribution and avoiding premature reclamation.
Key Results
- MBFQ allows a VM to reach its allocated bandwidth within three scheduling intervals (
3*T). - Idle bandwidth is reclaimed within five periods (
5*T). - The algorithm is designed to be work-conserving, meaning it tries to utilize all available bandwidth.
- CPU utilization increase with MBFQ is minimal (e.g., 22.74% to 23.22% in one experiment), demonstrating its efficiency.
- The paper shows experimental results demonstrating bandwidth ramp-up and ramp-down behavior, and the impact of the reclaim timer.
Limitations and Future Work
- Ramp-up Delay: While MBFQ aims to ramp up quickly, the actual speed is still influenced by TCP congestion control and the time it takes for VMs to consume allocated bandwidth. The paper suggests that faster ramp-up might not be beneficial if TCP cannot keep up.
- Reclaim Timer Compromise: The chosen reclaim timer (500ms) is a compromise. A shorter timer might lead to more efficient bandwidth utilization but could also cause more spurious reclamations.
- Future Work: The paper briefly mentions that a combination of static and dynamic bandwidth allocations could be explored, where latency-sensitive VMs get static queues and others dynamically share the rest. The authors also suggest that for latency-sensitive applications, hardware-assisted QoS (like 802.1p) might be necessary.
Summary updated