Control of fair queueing: modeling, implementation, and experiences

Feedback control of QoS-aware servers has recently gained much popularity due to its robustness in the face of uncertainty and modeling errors. Performance of servers is characterized by the behavior of queues, which constitute the main elements of the control loop. The central role of queues in the loop motivates understanding their behavior in the context of feedback control schemes. A popular queueing policy in servers where different traffic classes must be allocated a different share of a common resource is fair queueing (FQ). This paper investigates the interactions between a FQ element and a feedback controller. It is shown that the FQ element introduces challenges that render simple feedback control ineffective and potentially unstable. These challenges are systematically exposed, explained, and resolved. An extended feedback control scheme for the FQ element is subsequently developed. The scheme is tested on an experimental prototype demonstrating higher predictability and an order of magnitude improvement in responsiveness over the initial design. The results of the paper apply in general to most systems that use a dynamic processor sharing approach for service differentiation.