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.
Type de document :
Communication dans un congrès
Erik Altman; Weisong Shi. 8th Network and Parallel Computing (NPC), Oct 2011, Changsha,, China. Springer, Lecture Notes in Computer Science, LNCS-6985, pp.201-213, 2011, Network and Parallel Computing. 〈10.1007/978-3-642-24403-2_17〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01593017
Contributeur : Hal Ifip <>
Soumis le : lundi 25 septembre 2017 - 16:33:38
Dernière modification le : vendredi 1 décembre 2017 - 01:09:44
Document(s) archivé(s) le : mardi 26 décembre 2017 - 14:00:22

Fichier

978-3-642-24403-2_17_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Haiquan Zhao, Nan Hua, Ashwin Lall, Ping Li, Jia Wang, et al.. Towards a Universal Sketch for Origin-Destination Network Measurements. Erik Altman; Weisong Shi. 8th Network and Parallel Computing (NPC), Oct 2011, Changsha,, China. Springer, Lecture Notes in Computer Science, LNCS-6985, pp.201-213, 2011, Network and Parallel Computing. 〈10.1007/978-3-642-24403-2_17〉. 〈hal-01593017〉

Partager

Métriques

Consultations de la notice

82

Téléchargements de fichiers

18