Two-Stage Fair Queuing Using Budget Round-Robin

In current high bandwidth-delay-product networks, traditional end-to-end network protocols cannot guarantee the fair allocation of network resources (i.e., a rogue source that sends at an uncontrolled rate can seize a large fraction of the buffers at an intermediate router which results in dropped packets for other connections). Fair-queuing (FQ) algorithms were proposed to overcome this drawback. However, most of these FQ algorithms either suffer from high time-complexity or greatly rely on the multiple queuing structures which are extremely difficult to implement in large scale due to the access delay of DRAM. Based on the analysis on real-life traces, we are able to determine the short-term stability of number of connections in a trunk. Taking this characteristic into consideration, a new FQ algorithm called Budget Round-Robin (BRR) is proposed in this paper. Both theoretical analysis and experimental results demonstrate that BRR and its corresponding memory hierarchy are much superior to the other FQ algorithms when we have a high bandwidth link with large number of active connections (e.g., high-speed Internet).