Disclosed herein are systems, computer-implemented methods, and computer-readable media for sampling network traffic. The method includes receiving a plurality of flow records, calculating a hash for each flow record based on one or more invariant part of a respective flow, generating a quasi-random number from the calculated hash for each respective flow record, and sampling flow records having a quasi-random number below a probability P. Invariant parts of flow records include destination IP address, source IP address, TCP/UDP port numbers, TCP flags, and network protocol. A plurality of routers can uniformly calculate hashes for flow records. Each router in a plurality of routers can generate a same quasi-random number for each respective flow record and uses different values for probability P. The probability P can depend on a flow size. The method can divide the quasi-random number by a maximum possible hash value.