Abstract:

It is extremely difficult to measure traffic information with a growing network link speed. In recent years, increasing focus has been put on probabilistic algorithms which are fast enough to examine all packets and can provide estimates of the sizes of all flows. However, the previously proposed flow estimating algorithm of PMC has the drawbacks of poor space efficiency and large estimation error. To address the problem, a double bit field (D-BF) algorithm is proposed. The method is divided into two steps: the newly arrived packet is mapped to two bit fields using different hash functions in the data capturing stage; two virtual matrixes recovered from the bit fields have been intersected to eliminate errors caused by the hash collision in the data recovering stage. Experimental results show that the proposed D-BF is more accurate than PMC in flow estimate, while a reduction of 75% in memory space can be achieved.

Key words: computer network, traffic measurement, flow estimate, bit field