Dynamic Per-flow Queuing to Reduce Competitions Among Large Number of Flows

Per-flow queuing is believed to be able to guarantee advanced Quality of service (QoS) for each flow at high speed routers. With the dramatic increase for both link speed and number of traffic flows, per-flow queuing confronts a great challenge, since millions of queues need to be maintained for implementation in a traditional sense. In this paper, setting only a small number of physical queues, we propose a Dynamic per-flow queuing (DPFQ) mechanism that achievesthe same performance as per-flow queuing at a cost of an additional Binary content addressable memory (BCAM). The proposed mechanism works due to the fact that the number of simultaneous active flows at a mini-time scale in the router buffer is much smaller than that of in-progress flows. In DPFQ, a physical queue is created on demand when a new flow comes, and released when the flow temporarily pauses or finishes. A small BCAM is occupied to map flows to queues, so as to guarantee that only the packets from the same flow are buffered in any assigned queue. Through analysis and simulation we show that using a small number of physical queues, DPFQ achieves both low operation delay and power consumption.