ICE Buckets: Improved Counter Estimation for Network Measurement
| Autor: | Yaron Kassner, Benny Fellman, Gil Einziger, Roy Friedman |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Networking and Internet Architecture (cs.NI)
FOS: Computer and information sciences Computer Networks and Communications Computer science Network packet Network security business.industry 05 social sciences Real-time computing 050301 education 020206 networking & telecommunications 02 engineering and technology Intrusion detection system Load balancing (computing) Communications system Flow network Upper and lower bounds Computer Science Applications Computer Science - Networking and Internet Architecture 0202 electrical engineering electronic engineering information engineering Electrical and Electronic Engineering business 0503 education Software |
| DOI: | 10.48550/arxiv.1606.01364 |
| Popis: | Measurement capabilities are essential for a variety of network applications, such as load balancing, routing, fairness and intrusion detection. These capabilities require large counter arrays in order to monitor the traffic of all network flows. While commodity SRAM memories are capable of operating at line speed, they are too small to accommodate large counter arrays. Previous works suggested estimators, which trade precision for reduced space. However, in order to accurately estimate the largest counter, these methods compromise the accuracy of the smaller counters. In this work, we present a closed form representation of the optimal estimation function. We then introduce Independent Counter Estimation Buckets (ICE-Buckets), a novel algorithm that improves estimation accuracy for all counters. This is achieved by separating the flows to buckets and configuring the optimal estimation function according to each bucket's counter scale. We prove a tighter upper bound on the relative error and demonstrate an accuracy improvement of up to 57 times on real Internet packet traces. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|