## Technical Overview

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, calledCore-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.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.

Core-Stateless Fair Queueing AlgorithmIn CSFQ each edge node

In turn all nodes, including edge nodes, perform the following operations

estimatethe incoming rate of each flow, and use it to label flow's packets

- periodically
estimatethe fair rate,falong the outgoing link.- upon packet arrival
computethe forwarding probabilityPbased on the packet label (which represents the current value of the estimated flow rate) the fair rate of the output link. Thenforwardthe packet with probabilityP- when a packet is forwarded
replaceits label with the minimum between its previous value and the fair rate of the output linkFlow Rate EstimationEdge nodes estimate the rate of each flow based on exponential averaging. For details see Section 2.2.1 in [1].

Link Fair Rate EstimationWhen the link is congested, the fair ratefis 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 offwe use an iterative algorithm based on linear interpolation to compute it.When the link is uncongested we take

fto 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 RateUpon a packet arrival each node computes its forwarding probabilityPbased on the following formula

where

ris the current estimated rate of the flow, which is contained in the packet label, andfis the fair rate of the output link. By forwarding the packet with probabilityP, 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 relabelingTo reflect the eventual change in flow's rate, when a packet is forwarded its label is set tor'= 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 ComplexityOnly 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 probabilityP, 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 andO(1)at core nodes, wherenrepresents the number of flows. In addition, the computation complexity isO(1)at both core and edge nodes.## References