A network monitoring device includes a flow processing element, disposed to receive flow information relating to network flows, and to generate a set of virtual packets, each representing a portion of a network flow. The virtual packets are maintained in a time-sequential order, and read by elements of the network monitoring device to generate information relating to network traffic, such as symptoms affecting the communication network, problems affecting the communication network, and otherwise. The network monitoring device randomly samples virtual packets, with at least one of two effects: (1) flow information from traffic reporting devices that are themselves sampling at differing rates can be equalized, with the effect of standardizing information from all of them; (2) the network monitoring device itself can restrict its attention to a fraction of all virtual packets, with the effect of keeping up with a relatively large number of virtual packets.