## 3 Adaptive Filtering Queueing
A larger \(m_{i}\) implies that the flow of packet \(i\) has fewer residing packets in the buffer, which means that the flow label of packet \(i\) will be enrolled into filtering level \(v_{i}\). There are two supplementary  
Figure 1: Adaptive Filtering Queueing (AFQ) scheme. rules. First, once packet \(i\) encounters an empty filtering level at \(v_{emp}\), then \(v_{i}\ =\ v_{emp}\). Second, if there is no hit until \(\hat{F}_{max}\), then \(v_{i}\ =\ \hat{F}_{max}\). \[v_{i}\ =\ \{ \begin{array}{cl}m_{i}-1&2<m_{i}\leq\hat{F}_{max}\\ 1&1\leq m_{i}\leq 2\end{array}  \tag{4}\]  
After determining the filtering level of packet \(i\), AFQ needs to decide its location in filtering level \(v_{i}\) according to Equation (5), denoted by \(index_{i}\). A circular replacement method is used to update the flow labels in each filtering level. Furthermore, we assume that each filtering level has the same capacity, denoted by \(L\). AFQ updates the filtering level table according to traffic conditions. When the traffic is heavier, AFQ updates the filtering level table with a higher frequency. \[index_{i}\ =\ max((index_{i}+1)\ mod\ (L+1),1) \tag{5}\]  
AFQ utilizes a simple packet-dropping algorithm to decide the treatment of packet \(i\), where \(prob_{i}\) denotes the dropping probability of packet \(i\). Once packet \(i\) is accepted, it will be enqueued into the FIFO buffer; otherwise, it will be discarded immediately. Thus, only the arriving packets whose filtering levels are equal to or larger than the fair filtering level can be admitted to enter the buffer. \[prob_{i}\ =\ \min(floor(\hat{\alpha}_{new}/m_{i}),1) \tag{6}\]  
We propose a mechanism to add to AFQ to simplify the packet comparisons (_i.e._, the flow labels) while reducing memory consumption. In this design, the routers are classified as edge or core routers, similar to CSFQ. Edge routers use hash algorithms, such as SHA-1, to transfer the flow label of each packet into a key \(a_{j}\) that alleviates the IP dependency. Next, the key \(a_{j}\) is inserted into the packet's header. Figure 2 shows that the core routers have to maintain two tables; one is a first-layer table with size \((b^{n},L)\), and the other is a second-layer table with size \((n,p)\). When a packet arrives at the core router, AFQ extracts key \(a_{j}\) with size s from the packet header of the arrival and compares it with the keys from the first-layer table instead of the flow labels. Next, we use the same circular replacement method to maintain the keys in the first-layer table. If there is a hit at filtering level \(z\) where \(z\in[b^{0},b^{n}]\), AFQ has to compare its flow label with a flow label at \((index_{j}\), \(a_{j})\) in the second-layer table. We use Equation (7) to calculate the \(index_{j}\). \[index_{j}\ =\ \{min(k)\ |(z<b^{k}),k\in[1,n]\} \tag{7}\]  
If a packet encounters two hits, a real hit happened; otherwise, no real hit happened. A real hit corresponds to previous mentioned hit in the AFQ algorithm. If there is only a hit in the first table, the flow label of the arriving packet will replace the flow label at \((index_{j},a_{j})\) in the second-layer table; If different flows have the same key, the flow with more arriving packets has a higher chance to be captured in the second-layer table. In other words, its arriving packets will have a higher probability to be constrained. Consequently, AFQ can achieve sufficient discriminability. The updating of the second-layer table differs from the first-layer table in the use of the frequency-based replacement method. The two-layer mapping mechanism imposes additional burden on edge routers, but it can efficiently speed up the packet comparisons while reducing memory consumption on core routers. For instance, if \(s=8\) bits (get first 8 bits from160 bits producing by SHA-1), \(L=32\), \(b=2\), \(n=7\) and \(p=128\), the original AFQ requires \(32\times 8\times 128=32\),768 Bytes memory. When using the mechanism,AFQ requires approximately \(32\times 1\times 128+8\times 128\times 7=11\),264 Bytes.