Measurement Based Fair Queuing for Allocating Bandwidth to Virtual Machines

We wish to allocate outgoing bandwidth at a server among customer VMs. The allocation for each VM is proportional to the bandwidth purchased for that VM by the customer, and any idle bandwidth is also proportionally redistributed. This is the classical fair queuing problem. However, most solutions [9, 5, 4] to the classical fair queuing problem assume tight feedback between transmitter and scheduler, and cheap scheduler invocation on every transmission. Since these assumptions are false in Virtual Switches, we propose MBFQ (Measurement Based Fair Queuing) with two levels of scheduling: a microscheduler that operates cheaply and paces VM transmissions, and a macroscheduler that periodically redistributes tokens to microschedulers based on the measured bandwidth of VMs. We show that MBFQ allows a VM to obtain its allocated bandwidth in three scheduling intervals, and that idle bandwidth is reclaimed within five periods. An implementation of MBFQ is available in Windows Server 2016 Technical Preview.