Accuracy Tradeoffs in Software-Defined Measurement

This research explores tradeoffs in accuracy when using software-defined measurement for tasks such as traffic engineering, accounting, and troubleshooting in network management. It discusses challenges such as limited resources and complexity in switches, and compares different measurement primitives for tasks like finding heavy hitter IPs. The study also examines using sketches with hash-based counters for efficient resource utilization and discusses architecture and motivation for these approaches.

• Software-defined measurement
• Accuracy tradeoffs
• Traffic engineering
• Network management
• Measurement primitives

gabbane Follow

Uploaded on Oct 10, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. HotSDN13 Resource/Accuracy Tradeoffs in Software-Defined Measurement Masoud Moshref, Minlan Yu, Ramesh Govindan

2. Management policies need measurement Traffic Engineering: Find elephant flows to route [Hedera] Estimate rack-to-rack traffic matrix [MicroTE] Accounting: Tiered pricing based on network usage Troubleshooting: Find network bottlenecks of an application Incast problem Motivation Motivation Tradeoff Case study Discussion 2

3. Software Defined Measurement Controller Traffic Engineering (Re)Configure 1 1 Configure resources resources 2 Fetch statistics Motivation Motivation Tradeoff Case study Discussion 3 3

4. Challenges Limited resources Limited CPU/memory in switches Limited control network bandwidth Complexity of different primitives in switches Counting by prefix matching (TCAM) Counting based on hashes Programming Programming Complexity of different primitives in switches Counting by prefix matching (TCAM) Counting based on hashes Different measurements Resource usage depends on measurement Motivation Motivation Tradeoff Case study Discussion 4

5. Using Different Primitives for Measurement Comparing primitives in performing a measurement task Example: Finding heavy hitter IP when traffic from 10.0.1.0/24 goes beyond a threshold Architecture Tradeoff Motivation Case study Discussion 5

6. Counting TCAM matches Counter s Filters 0 1 1 0 * * * * 18 1. Monitor 10.0.1.0/24 2. When goes beyond threshold, iteratively search (e.g. binary search) Controller link bandwidth Slowly varying traffic Large time-scale measurement Measure-install loop latency Controlle r - 10.0.1.0/24 1 10.0.1.0/25 Install Fetch 2 10.0.1.128/25 3 10.0.1.128/26 ... Architecture Tradeoff Motivation Case study Discussion 6

7. Sketches using hash based counters Src:10.0.1.5, Size:2 H 1 3 2 1 5 0 0 1 0 5 3 1 0 2 Uses cheaper resources (SRAM) 1. Fetch counters 2. Approximate traffic for each IP Not dependent on traffic history Use for varying traffic Still history may help in large time scale to optimize parameters Controlle r Architecture Tradeoff Motivation Case study Discussion 7

8. Programming switches Use more complex data structures/commands Heap for finding large flows 10.0.1.5 90 10.0.1.1 25 10.0.1.3 50 10.0.1.12 17 10.0.1.10 3 Uses CPU resources Can it keep up with line rate? Architecture Tradeoff Motivation Case study Discussion 8

9. Summary of tradeoffs of primitives Criteria Prefix matching TCAM Medium Large Yes Hash-based counting SRAM Large Small No Programming Memory usage Bandwidth usage Time-scale Traffic history sensitivity Concerns SRAM Small Small No Accuracy vs Resource Accuracy vs Resource Accuracy vs Resource Architecture Tradeoff Motivation Case study Discussion 9

10. Case Study: Hierarchical Heavy Hitter Detection 10

11. Hierarchical Heavy Hitters 36 *** 26 10 0** 1** 12 14 5 5 00* 01* 10* 11 * 111 001 011 101 5 7 12 2 0 5 2 3 010 110 000 100 Case study Motivation Tradeoff Discussion 11

12. Hierarchical Heavy Hitters Longest IP prefixes Contribute a large amount of traffic After excluding any HHH descendants in the prefix tree Threshold=10 36 *** 26 10 0** 1** 12 14 5 5 00* 01* 10* 11 * 111 001 011 101 5 7 12 2 0 5 2 3 010 110 000 100 Case study Motivation Tradeoff Discussion 12

13. Algorithms for single switch HHH detection Prefix-based counting Proposed an iterative algorithm at controller Given TCAM capacity, monitor prefixes that maximize accuracy 5 26 5 26 3 - 3 13 2 - 2 13 Hash-based counting Use Hierarchical Count-Min sketch Approximate traffic in all levels using sketches Efficiently traverse IP tree at controller to find HHHs 30 30 26 Approximate Traverse tree 20 20 18 9 9 8 Case study Motivation Tradeoff Discussion 13

14. Evaluation 1 0.8 Recall 0.6 0.05,Hash-based 0.05,Prefix matching 0.01,Hash-based 0.01,Prefix matching 0.4 Normalize switch cost 80 SRAM 1 TCAM 0.2 0 20k 256 80k 1k 320k 4k SRAM counters TCAM counters Sketches have better accuracy for small threshold (longer prefixes, higher variability) counters and large thresholds Max-Cover saves bandwidth for large number of Case study Motivation Tradeoff Discussion 14

15. Future work Controller Traffic Engineering Anomaly Detection Use joint information Guarantee accuracy Accountin g North-bound Software Defined Measurement South-bound Select primitive Assign switch resources Run global measurement Motivation Motivation Tradeoff Case study Discussion 15