A network-wide traffic measurement/analysis problem is formulated as a series of set-cardinality-determination (SCD) problems, using probabilistic distinct sample counting techniques to compute network-wide traffic measurements of interest in a distributed manner via the exchange of light-weight traffic digests (TD's) amongst network nodes/routers. A TD for N packets uses only requires O(loglog N) bits of memory storage, making it possible to distribute nodal TD's to all routers within a domain by piggybacking them as opaque data objects inside existing control messages, such as OSPF link-state packets (LSPs) or I-BGP control messages. A router receiving the TD's can estimate the traffic measurements of interest for each of its local links by solving a series of set-cardinality-determination problems. The traffic measurements of interest are typically per-link, per-traffic-aggregate packet (or flow) counts, where an aggregate is defined by the group of packets sharing the same originating and/or destination nodes (or links) and/or some intermediate nodes (or links).