Document Type

Technical Report

Publication Date

2004-07-06

Filename

wucse-2004-44.pdf

DOI:

10.7936/K77P8WRZ

Technical Report Number

WUCSE-2004-44

Abstract

Recent studies have shown that suitably-designed packet discard policies can dramatically improve the performance of fair queueing mechanisms in internet routers. The Queue State Deficit Round Robin algorithm (QSDRR) preferentially discards from long queues, but in-troduces hysteresis into the discard policy to minimize synchronization among TCP flows. QSDRR provides higher throughput and much better fairness than simpler queueing mech-anisms, such as Tail-Drop, RED and Blue. However, since QSDRR needs to maintain a separate queue for each active flow, there is a legitimate concern that it may be too costly for the highest speed links. In previous studies, we have shown that QSDRR can deliver almost the same performance with one-tenth the number queues as flows, if the flows are evenly distributed across the queues. In this paper, we develop and evaluate a flow dis-tribution algorithm using a Bloom filter architecture with dynamic rebalancing. We show that our algorithm significantly reduces the memory requirement compared to maintaining per-flow state and can achieve near optimal flow distribution. Thus, using this algorithm in conjunction with QSDRR, we can achieve the performance of per-flow queueing at a significantly reduced cost.

Comments

Permanent URL: http://dx.doi.org/10.7936/K77P8WRZ

Download

Share

COinS