Frequent traffic flow identification through probabilistic bloom filter and its GPU-based acceleration
| Autor: | Michael W. Berry, Sisi Xiong, Yanjun Yao, Hairong Qi, Qing Cao |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Router
Bandwidth management Traffic analysis Computer Networks and Communications Computer science Real-time computing Probabilistic logic 020206 networking & telecommunications 02 engineering and technology Bloom filter Traffic flow Computer Science Applications Traffic flow (computer networking) Hardware and Architecture 0202 electrical engineering electronic engineering information engineering Overhead (computing) 020201 artificial intelligence & image processing Traffic generation model |
| Zdroj: | Journal of Network and Computer Applications. 87:60-72 |
| ISSN: | 1084-8045 |
| Popis: | Traffic measurement and monitoring are critical for many network applications, for example, bandwidth management and detecting security threats such as DoS (Denial of Service) attacks. In these cases, traffic is usually modeled as a collection of flows. One central problem is to identify those frequent flows, which account for a large percentage of total traffic, or whose frequency exceeds the user-specified threshold. In this paper, we describe a novel data structure called the probabilistic Bloom filter (PBF), which extends the classical Bloom filter into probabilistic direction, so that it can effectively estimate flows' frequencies, and identify frequent flows. We analyze the performance, tradeoffs, and capacity of this data structure, and investigate how to calibrate this data structure's parameters. We further develop one extension of the PBF for dynamic data stream needs. We implement our PBF on GPUs to gain more time efficiency. By testing with real network traces collected from a backbone router, we demonstrate that our method can keep track of flows' frequencies with adjustable accuracy, so that frequent flows can be identified with constant computational time complexity and low memory overhead. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect