System, method, and media for network traffic measurement on high-speed routers

Abstract

A data structure is provided for storing network contact information based on an array of physical memory locations. Virtual vectors are constructed for each source, wherein each element in each virtual vector is assigned to a corresponding physical memory location within the array. The physical memory locations are shared between the virtual vectors uniformly at random so that the noise introduced by sharing can be predicted and removed. A method for storing network contact information is also provided in which a hash function is performed using the address of a source host to find a virtual vector for holding information about the source host. A second hash function is performed using the address of a destination host to find a virtual memory location, within the virtual vector, for holding information about the destination host. Finally, information is stored at a physical memory location assigned to the virtual memory location. Estimation range enhancement is further provided by performing multiple estimations with different sampling probabilities and selecting a best estimation based on a maximum likelihood method.