network-monitoring.md (1505B)
1 +++ 2 title = 'Network monitoring' 3 +++ 4 5 ## Network monitoring 6 Tasks: 7 - which path id my packet take? 8 - which rules on the switch did the packet follow? 9 - how long did the packet queue at each switch? 10 - who did the packet share the queue with? 11 12 In-band network telemetry: leverage programmability of switches to insert monitoring info into packet header along network path 13 14 Heavy hitters: network flows that are larger (in number of packets, or bytes) than some fraction *t* of total packets seen on the link or some top *k* flows by size 15 16 Space-saving algorithm: counter-based algorithm that uses O(k) counters to track k heavy flows 17 - properties: 18 - no flow counter in the table is ever underestimated 19 - min value in the table (`val_r`) is an upper bound on the overestimation error of any counter 20 - any flow with true count higher than average table count will always be present in the table 21 - if flow has appeared in table: hash to flow key, increment corresponding counter 22 - if flow not contained in table: find the min counter in the table, replace the key with the current flow key, increment the counter 23 24 Universal streaming: 25 - there exists universal approach to estimate G-sum when function `g(*)` is non-decreasing such that g(0) = 0 and g(x) does not monotonically grow faster than x² 26 - universal sketch construction can be used to estimate G-sum with high probability using poly-logarithmic memory 27 28 Item i is a g-heavy hitter if changing its frequency `f_i` significantly affects its G-sum