Flow identification for supporting per-flow queueing

Abstract

Over the last several years there has been considerable interest in multimedia communications over the Internet. This paper investigates one of the key technical issues in supporting per-flow queueing-flow identification. We present several hashing-based flow identification approaches and examine their performance and scalability limits with a quantitative analysis and a simulation study with backbone traffic traces. Of the hashing schemes we studied, 32-bit CRC and XOR-folding of the five-tuple demonstrate excellent performance, both on the memory requirement for a collision rate target, and on the number of collided flows on average and in the worst-case. Our findings show that, with hashing-based schemes, it is feasible to implement flow identification at high speeds to support hundreds of thousands of flows with resource reservation.