Scalable and fast approximate excess rate detection

An important requirement in high speed network monitoring is the fast and scalable identification of heavy-hitters, traffic flows whose generation rate exceeds some pre-established peak or mean rate conditions. This problem has been addressed in the past through the design of approximate counters, d...

Full description

Saved in:
Bibliographic Details
Main Authors: Bianchi, G, Teofili, S, Boschi, E, Trammell, B, Greco, C
Format: Conference Proceeding
Language:English
Subjects:
Approximation methods
counting Bloom filters
Detectors
Memory management
Monitoring
Radiation detectors
Scalability
Time measurement
token buckets
traffic measurement
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An important requirement in high speed network monitoring is the fast and scalable identification of heavy-hitters, traffic flows whose generation rate exceeds some pre-established peak or mean rate conditions. This problem has been addressed in the past through the design of approximate counters, derived from counting Bloom filters, capable of performing this task without the need to keep per-flow state. This paper presents an enhancement to the primitive operation used in this approach. We demonstrate an approximate excess rate detector, which exhibits faster operation and significant memory savings. Our construction can detect both flows which exceed a given average long term transmission rate as well as burst patterns exceeding a predetermined configuration threshold. We show that there exists a tight relationship between the configuration parameter of an approximate excess rate detector and that of a token bucket. We further provide dimensioning guidelines highlighting the detector's relationship with the aggregate traffic rate and the number of hitters.