Skip to Main content Skip to Navigation
New interface
Conference papers

Towards a Universal Sketch for Origin-Destination Network Measurements

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, September 25, 2017 - 4:33:38 PM
Last modification on : Friday, June 11, 2021 - 5:12:08 PM
Long-term archiving on: : Tuesday, December 26, 2017 - 2:00:22 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Haiquan (chuck) Zhao, Nan Hua, Ashwin Lall, Ping Li, Jia Wang, et al.. Towards a Universal Sketch for Origin-Destination Network Measurements. 8th Network and Parallel Computing (NPC), Oct 2011, Changsha,, China. pp.201-213, ⟨10.1007/978-3-642-24403-2_17⟩. ⟨hal-01593017⟩



Record views


Files downloads