A flow table-based design to approximate fairness

The current Internet architecture relies on congestion avoidance mechanisms implemented in the transport layer protocols, like TCP, to provide good service under heavy load. If routers distribute bandwidth fairly, the Internet would be more robust and could accommodate more diversity of end hosts. Most of the mechanisms proposed to accomplish this can be grouped into two general categories. The first category, which includes fair queueing (FQ) and its many variants, uses packet scheduling algorithms that are more difficult to implement compared to FIFO queueing. The algorithms in the second category, active queue management schemes with enhancements for fairness (e.g., FRED, SFB), are based on FIFO queueing. They are easy to implement and are much fairer than the original RED design, but they do not provide max-min fairness among a large population of flows. A router mechanism, AFD (approximate fair dropping), has been proposed to achieve approximately max-min fair bandwidth allocations with relatively low complexity. We propose an implementation of AFD which can mimic the performance of the original design with much less state.