کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
448872 693609 2013 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Scalable identification and measurement of heavy-hitters
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر شبکه های کامپیوتری و ارتباطات
پیش نمایش صفحه اول مقاله
Scalable identification and measurement of heavy-hitters
چکیده انگلیسی

Existing methods to detect and measure heavy-hitters (frequent items) are either lightweight but too inaccurate and memory-demanding (e.g. those relying on sampling), or too heavyweight to be deployed at high speeds. In this paper, we present several sampled-based algorithms to the problem and show that they exhibit two critical features. First, despite sampling, our schemes provide accurate results and detection guarantees that are independent of the traffic properties. Second, they are provably shown to require memory that is not only constant regardless of the amount of traffic observed and its composition, but a small factor above the theoretical minimum. Thus, unlike most solutions, ours scale in both space and speed; the use of sampling allowing to trade off performance for cost. As we will see, our algorithms build on similar principles. The first two use a constant sampling probability. Upgrading the second to support a variable sampling rate and to adjust it depending on the traffic intensity and CPU available yields our third scheme; a highly versatile solution that performs quasi-optimally and requires minimal configuration.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Communications - Volume 36, Issue 8, 1 May 2013, Pages 908–926
نویسندگان
,