Detailed network measurements using sparse graph counters: The theory

Yi Lu, Andrea Montanari, Balaji Prabhakar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Measuring network flow sizes Is important for tasks like accounting/billing , network forensics and security. Per-flow accounting Is considered hard because it requires that many counters be updated at a very high speed; however , the large fast memories needed for storing the counters are prohibitively expensive. Therefore , current approaches aim to obtain approximate flow counts; that Is , to detect large elephant lows and then measure their sizes. Recently the authors and their collaborators have developed [1] a novel method for per-flow traffic measurement that is fast , highly memory efficient and accurate. At the core of this method Is a novel counter architecture called "counter braids". , 99 In this paper , we analyze the performance of the counter braid architecture under a Maximum Likelihood (ML) flow size estimation algorithm and show that It Is optimal; that Is , the number of bits needed to store the size of a flow matches the entropy lower bound. While the ML algorithm is optimal , It Is too complex to Implement. In [1] we have developed an easy-to-implement and efficient message passing algorithm for estimating flow sizes.

Original languageEnglish (US)
Title of host publication45th Annual Allerton Conference on Communication, Control, and Computing 2007
PublisherUniversity of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
Pages1252-1259
Number of pages8
ISBN (Electronic)9781605600864
StatePublished - Jan 1 2007
Externally publishedYes
Event45th Annual Allerton Conference on Communication, Control, and Computing 2007 - Monticello, United States
Duration: Sep 26 2007Sep 28 2007

Publication series

Name45th Annual Allerton Conference on Communication, Control, and Computing 2007
Volume2

Other

Other45th Annual Allerton Conference on Communication, Control, and Computing 2007
CountryUnited States
CityMonticello
Period9/26/079/28/07

    Fingerprint

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Networks and Communications

Cite this

Lu, Y., Montanari, A., & Prabhakar, B. (2007). Detailed network measurements using sparse graph counters: The theory. In 45th Annual Allerton Conference on Communication, Control, and Computing 2007 (pp. 1252-1259). (45th Annual Allerton Conference on Communication, Control, and Computing 2007; Vol. 2). University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering.