טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentTsidon Erez
SubjectCounter-Estimation Decoupling for Approximate Rates
DepartmentDepartment of Electrical Engineering
Supervisor Professor Isaac Keslassy
Full Thesis textFull thesis text - English Version


Abstract

Network management applications require large numbers of counters in order to collect traffic characteristics for each network flow. However, these

counters often barely fit into on-chip SRAM memories. Past papers have proposed using counter estimators instead, thus trading off counter precision

for a lower number of bits. But these estimators do not achieve optimal estimation error, and cannot always scale to arbitrary counter values.

In this dissertation, we introduce the CEDAR algorithm for decoupling the counter estimators from their estimation values, which are quantized into

estimation levels and shared among many estimators. These decoupled and shared estimation values enable us to easily adjust them without needing to go through all the counters.

We demonstrate how our CEDAR scheme can achieve the min-max relative error, i.e., can guarantee the best possible relative error over the entire counter scale. Likewise, we show how it can also achieve the min-max absolute error. We also explain how to use dynamic adaptive estimation values in order to

support counter up-scaling and adjust the estimation error depending on the current maximal counter. In addition, we apply our schemes to the estimation of exponentially-weighted average flow rates. Finally, we implement CEDAR on FPGA and explain how it can run at line rate.

We further analyze its performance and size requirements.and size requirements.