## 3 Adaptive Filtering Queueing  
In Figure 1, we depict four main components of AFQ, including accepted traffic estimation, fair filtering level estimation, a filtering level table and a packet-dropping algorithm. At the end of this section, we propose a mechanism that permits the scalability of AFQ. If the mean arriving rate of a flow is larger than the max-min fair rate, such a flow is defined as an aggressive flow; otherwise, this flow is defined as a non-aggressive flow. In addition, the flow label is composed of a pair of IP source-destination addresses related to a flow. When a packet arrives at a router, AFQ identifies the filtering level of the arriving packet by randomly comparing with a flow label from the first level to an estimated level in the filtering level table. Based on the accepted traffic estimation and the previous fair filtering level, AFQ updates estimates of the fair filtering level. Finally, AFQ uses a simple packet-dropping algorithm to determine whether the packet is qualified to be accepted or discarded according to estimates of the fair filtering level and the filtering level of the arrival. In a router, AFQ estimates accepted traffic \(\hat{A}_{new}\) passing through the packet dropping component in a time interval using use Equation (1). The unit of \(\hat{A}_{new}\) is bits, and \(T_{d}\) denotes the length of such a time interval. \[\hat{A}_{new}\ =\ k_{a}A_{now}+(1-k_{a})\hat{A}_{old} \tag{1}\]  
\(\hat{A}_{old}\) is the value prior to the updating of \(\hat{A}_{new}\), and \(A_{now}\) is the amount of traffic accepted in the current time interval. In addition, \(k_{a}\) is a coefficient used to balance the short-term and long-term estimates of \(\hat{A}_{new}\). The estimation of the fair filtering level \(\widehat{\alpha}\) is proportional to \(CT_{d}/\hat{A}_{new}\), as described in Equation (2). Similarly, \(\widehat{\alpha}_{old}\) is the value before the updating of \(\widehat{\alpha}_{new}\), and \(C\) denotes the router's link capacity (bits per second). If \(\hat{A}_{new}\) is smaller than the idea output traffic \(CT_{d}\), then \(\widehat{\alpha}_{new}\) increases. A larger \(\widehat{\alpha}_{new}\) will allow more arriving packets to be accepted. By observing the dynamics of accepted traffic, AFQ can produce a precise estimate of the fair filtering level. \[\widehat{\alpha}_{new}\ =\ \widehat{\alpha}_{old}CT_{d}/\hat{A}_{new} \tag{2}\]  
AFQ compares the flow label of each arriving packet with a flow label in a filtering level table at random from filtering level 1 to \(\widehat{\alpha}_{new}\) until there is a hit. The filtering level table consists of multiple filtering levels, and each filtering level only keeps flow labels, not whole packets, whose utility is to discriminate the dropping probabilities of arriving packets. If both own the same flow label (_i.e._, are coming from the same flow), then a hit occurs. In AFQ, multiple filtering levels work as a hierarchical filter that filters out the unqualified arriving packets. AFQ may have insufficient discriminability because of traffic dynamics, which leads to fairness degradation; hence, we should enlarge the \(\widehat{\alpha}_{new}\). We readjust \(\widehat{\alpha}_{new}\) by \(k_{b}\) times the \(\widehat{\alpha}_{new}\) in Equation (3), denoted by \(\hat{F}_{max}\). \(k_{b}\) is a coefficient whose function is to enhance the discriminability of AFQ. Finally, the range of flow label comparisons is altered from filtering level 1 to \(\hat{F}_{max}\). In other words, \(\hat{F}_{max}\) contributes to the realization of sufficient discriminability; the principle to determine whether arriving packets are accepted or dropped still depends on \(\widehat{\alpha}_{new}\). As a result, the complexity of AFQ is of O(\(\hat{F}_{max}\)). \[\hat{F}_{max}\ =\ k_{b}\widehat{\alpha}_{new},\ k_{b}\geq 1 \tag{3}\]  
Assuming that packet \(i\) has a first hit at filtering level \(m_{i}\), we use Equation (4) to calculate filtering level \(v_{i}\).