att_abstract={{Despite its importance in today's Internet, network measurement
was not an integral part of the original Internet architecture,
i.e., there was (and still is) little native support
for many essential measurement tasks. Targeting the inadequacy
of counting/accounting capabilities of existing routers,
many data streaming and sketching techniques have been
proposed to estimate the important statistics of traffic going
through a network link. Most of these techniques are, however,
developed to track one specific statistic and/or answer
a specific type of query. Since there are a large number of
such statistics and queries of interest, it is very difficult, if
not impossible, for network vendors and operators to implement
and deploy data streaming/sketching solutions for all
of them, due to router resource (memory, CPU, bus bandwidth,
etc.) constraints.
In this paper, we propose a general-purpose solution that
can not only answer a wide range of queries, but also be able
to answer types of queries that were not known a priori. In
particular, we introduce the use of the Conditional Random
Sampling (CRS) sketch data structure for succinctly capturing
network traffic data between a set of nodes in the
network. This sketch is the first step towards a “universal”
sketch data structure in the sense that it is not tied to
measurement of a single quantity. We show that the CRS
sketch can compute unbiased estimates for any linear summary
statistic in the intersection of a pair of traffic streams,
e.g., traffic and flow matrix information, flow counts, and entropy.
We present detailed experiments, using data collected
at a tier-1 ISP, that show that our sketch is capable of estimating
this wide range of statistics with fairly high accuracy.}},
	att_copyright_notice={{The definitive version was published in 8th IFIP International Conference on Network and Parallel Computing. {{, 2011-10-21}}{{, http://www.springer.com/cda/content/document/cda_downloaddocument/LNCS+Copyright+Form?SGWID=0-0-45-981960-0}}

(c) ACM, 2010. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution.
The definitive version was published in ACM Internet Measurement Conference  {{, 2011-10-21}}{{, http://www.springer.com/cda/content/document/cda_downloaddocument/LNCS+Copyright+Form?SGWID=0-0-45-981960-0}}.}},
	author={Jia Wang and Haiquan Zhao and Nan Hua and Ashwin Lall and Ping Li and Jun Xu},
	institution={{8th IFIP International Conference on Network and Parallel Computing }},
	title={{Towards a Universal Sketch for Origin-Destination Network Measurements}},