## 1 Introduction  
Random Early Detection (RED) detects incipient congestion by computing the average queue size [1]. When the average queue size exceeds a threshold, RED drops or marks each arriving packet with a probability, where the probability is a function of the average queue size. RED not only keeps queuing delays low but also maintains high overall throughput because it can prevent current connections from global synchronization. RED should cooperate with transport-layer protocols capable of congestion control, such as TCP; unfortunately, it currently does not. Without congestion control, RED has poor fairness, especially for heterogeneous traffic environments. To improve the fairness of RED, a CHOoseand Keep for responsive flows, CHOose and Kill for unresponsive flows (CHOKe) scheme was proposed [2]. When a packet arrives at a router, CHOKe compares it with a packet at random from the buffer. If both packets come from the same flow, both are discarded at the same time; otherwise, the arriving packet may be discarded with a probability depending on the current degree of congestion. By using additional discrimination on flows with heavy traffic, CHOKe demonstrates improved fairness. XCHOKe is a revised version of CHOKe [3]. XCHOKe maintains a lookup table to record CHOKe hits. Accordingly, it further identifies possible malicious flows. If a flow has many CHOKe hits, this flow has a higher probability of being identified as a malicious flow. Therefore, XCHOKe applies a higher dropping probability to the arriving packets of this flow. Although XCHOKe achieves better fairness than CHOKe and RED, it lacks scalability, making XCHOKe too complicated to be deployed in high-speed networks.  
Considering the trade-off between scalability and fairness, Core-Stateless Fair Queueing (CSFQ) [4] and Rainbow Fair Queueing (RFQ) [5] were proposed. In particular, all routers in CSFQ are classified as edge or core routers. Edge routers need to maintain per-flow state because they have to estimate the flow rate of each arriving packet. Next, the information is inserted into the corresponding packet headers. Core routers estimate the fair share rate and then use a simple dropping algorithm to determine whether an arriving packet is accepted or discarded. RFQ is similar to CSFQ but with one significant difference: the state information that is inserted into the packet headers is the color layers, not the explicit flow rate. The operations of the core routers are further simplified, and the application can assign differentiated preferences to certain packets. The fairness of both core-stateless schemes could be degraded along with the increasing number of traversing nodes. Rotating Preference Queuing (RPQ) consists of a set of FIFO output queues that are dynamically rotated [6]. RPQ dispatches qualified arriving packets to adequate output queues based on packet distribution and preferences. RPQ has excellent fairness, but it needs a large buffer size, which means that RPQ may have a high implementation cost and result in a large queueing delay. Compared with RPQ, CSFQ, CHOKe and FIFO, the proposed AFQ scheme in this paper is scalable because it is easy to implement. Furthermore, AFQ is efficient because it provides approximately perfect fairness under various traffic conditions.  
An interesting research question is whether a scheme can achieve fairness without requiring per-flow state. Providing fairness is important because it also contributes to congestion avoidance. In this paper, the objective is to achieve fair bandwidth sharing with a simple and scalable AFQ approach. The rest of the paper is organized as follows: Section II reviews the related work; Section III describes the details of the AFQ scheme with a two-layer mapping mechanism that can simplify the packet comparisons; Section IV presents the simulation results that demonstrate the fairness of different schemes under various network topologies and traffic conditions; and Section V presents our conclusions.