Fair scheduling and buffer management in Internet routers

Input buffered switch architecture has become attractive for implementing high performance routers, and expanding use of the Internet sees an increasing need for quality of service. It is challenging to provide a scheduling technique that is both highly efficient and fair in resource allocation. We first introduce an iterative fair scheduling (iFS) scheme for input buffered switches that supports fair bandwidth distribution among the flows and achieves asymptotically 100% throughput. The iFS is evaluated both under synthetic workload and with Web traces from the Internet. Compared to the commonly used synthetic input, our simulation results reveal significant difference in performance when real network traffic is employed. We then consider fair scheduling under various buffer management mechanisms and analyze their impact on the fairness in bandwidth allocation. Our studies indicate that early packet discard in anticipation of congestion is necessary and per-flow based buffering is effective for protecting benign users from being adversely affected by misbehaved traffic. Buffer allocation according to bandwidth reservation is especially helpful when the input traffic is highly bursty.