Although Fair Queueing (FQ) algorithms have many desierable properties for congestion control, their implementation complexity may prevent them from being cost-effectively deployed at high-speeds. To reduce this complexity, we propose a network architecture, called Core-Stateless in which only edge nodes perform per flow management. Core nodes do not need to perform per flow management, and therefore can be easily implemented at high speeds.Technical Overview
Our goal is to use this network architecture to approximate the functionality of a network in which all nodes implement FQ. In this way we can provide approximately fair allocations at a much lower implementation cost.
In CSFQ each edge node
Link Fair Rate Estimation When the link is congested, the fair rate f is computed such that the rate of the aggregate forwarded rate equals the link capacity. Since the aggregate forwarded rate is a non-decreasing and monotonic function of f we use an iterative algorithm based on linear interpolation to compute it.
When the link is uncongested we take f to be the maximum among the arrival rates of the incoming flows (i.e., the largest label of a packet seen during a certain period).
A link is assumed to be congested/ucongested if during an predefined time interval the aggregate forwarded rate is always larger/lower than the link capacity. For algorithms details see Section 2.2.2 in in [1].
Computing Packet Forwarding Rate Upon a packet arrival each node computes its forwarding probability P based on the following formula
where r is the current estimated rate of the flow, which is contained in the packet label, and f is the fair rate of the output link. By forwarding the packet with probability P, the expected rate of the flow's forwarded traffic is
Note that r' is exactly the bandwidth that the flow would receive under FQ. This is the key property that allows CSFQ to approximate FQ.
Packet relabeling To reflect the eventual change in flow's rate, when a packet is forwarded its label is set to r' = min(f, r). In this way we ensure the label consistency, i.e., at the next node the label will still represent the estimate rate of the flow's incoming traffic.
Algorithm Complexity Only edge nodes needs to perform per flow management, as they need to estimate the rate of each incoming flow. Core nodes do not need to perform per flow management, since to compute the forwarding probability P, they need to know only the packet label and the fair rate of the output link.
As a result the state complexity of CSFQ is O(n) at edge nodes and O(1) at core nodes, where n represents the number of flows. In addition, the computation complexity is O(1) at both core and edge nodes.