Technical Report Number
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 Deﬁcit Round Robin algorithm (QSDRR) preferentially discards from long queues, but in-troduces hysteresis into the discard policy to minimize synchronization among TCP ﬂows. 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 ﬂow, 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 ﬂows, if the ﬂows are evenly distributed across the queues. In this paper, we develop and evaluate a ﬂow dis-tribution algorithm using a Bloom ﬁlter architecture with dynamic rebalancing. We show that our algorithm signiﬁcantly reduces the memory requirement compared to maintaining per-ﬂow state and can achieve near optimal ﬂow distribution. Thus, using this algorithm in conjunction with QSDRR, we can achieve the performance of per-ﬂow queueing at a signiﬁcantly reduced cost.
Katawala, Anshul and Turner, Jonathan S., "Achieving per-flow Queueing Performance without a per-flow Queue" Report Number: WUCSE-2004-44 (2004). All Computer Science and Engineering Research.