Re-evaluating Measurement Algorithms in Software Domain
Re-evaluating Measurement
Algorithms in Software
O
m
i
d
A
l
i
p
o
u
r
f
a
r
d
,
M
a
s
o
u
d
M
o
s
h
r
e
f
,
M
i
n
l
a
n
Y
u
{alipourf, moshrefj, minlanyu}@usc.edu
Software Switches are Popular
D
a
t
a
c
e
n
t
e
r
s
:
“
U
s
e
t
h
e
c
l
o
u
d
t
o
m
a
n
a
g
e
t
h
e
c
l
o
u
d
”
•
Load balancer and Firewall on VMs
I
S
P
s
:
A
T
&
T
r
e
p
l
a
c
e
s
h
a
r
d
w
a
r
e
r
o
u
t
e
r
s
w
i
t
h
N
F
V
•
Allow customers to run network functions on commodity servers
2
Network Function Virtualization
3
Typical X86 server
NAT
IDS
DPI
Firewall
Measurement is Critical for NFVs
•
Make decisions based on measurement input
•
Firewall, load balancing, intrusion detection systems (IDS)
•
We also need measurement for managing NFVs
•
Profiling NFV usage, resource scheduling..
4
“If you can’t measure it, you can’t manage it”
What is the best algorithm for
measurement in software?
5
New Design Concerns in Software
6
Software switches
Working-set (Cache size)
Maximizing Throughput
Hardware switches
Limited Memory Size
Fit in the Memory
Domain
Constraint
Objective
I
t
’
s
t
i
m
e
t
o
r
e
e
v
a
l
u
a
t
e
m
e
a
s
u
r
e
m
e
n
t
a
l
g
o
r
i
t
h
m
s
i
n
s
o
f
t
w
a
r
e
c
o
n
t
e
x
t
!
Previous Works on Measurement Algorithms
7
Measurement Algorithms
8
Popular measurement algorithms
in the hardware switch and
database domain
Measurement Tasks
9
Measurement Tasks
10
Algorithms for Heavy-hitter Detection
Heavy hitters: Detect the most popular flows in the traffic.
Different memory-computation tradeoffs:
•
Simple hash table:
For every packet, hash the header, update a
counter
•
Sketches
: For every packet, hash the header several times,
update relevant counters.
•
Heap
: Keep a heap of counters, remove smallest counter when
there is no space for new packets.
11
Different trade offs for algorithms: which one is the best?
Compare different measurement algorithms
•
Hash, sketch, heap
Metrics
•
Performance: network throughput, per-packet delay
•
Precision: % of selected heavy-hitters that are correct.
Evaluation setting
•
CAIDA traces
•
Click modular router modified with DPDK
12
Evaluating the algorithms
Simple Hash Table Works the Best
Throughput
•
S
i
m
p
l
e
h
a
s
h
t
a
b
l
e
h
a
s
3
4
%
h
i
g
h
e
r
t
h
r
o
u
g
h
p
u
t
o
v
e
r
s
k
e
t
c
h
e
s
,
a
n
d
1
0
8
%
o
v
e
r
h
e
a
p
.
Precision
•
Simple hash table is only 4% less accurate for sizes greater than
200KB.
•
The accuracy difference is less than 1% when the size is greater
than 10MB.
13
Hash has the lowest average per packet delay
14
Tail Latency Jump from L3 to Memory
15
Simple hash table works well for heavy-hitter
detection.
What about the other tasks?
O
b
s
e
r
v
a
t
i
o
n
All measurement tasks maintain a table of entries (e.g., counters).
16
@10 Gbps, 67 ns to process each packet on average (worst case).
17
Memory access is too slow
Plenty of memory for measurement
#entries that can be used for line-rate packet processing
18
Enough memory to hold everything!
5 Mil NetFlow Entries
15 Mil Hash Entries with Distinct counters
200 Mil Hash Entries
Average Flow size of 1KB
1.25 Mfps @ 10Gbps
More than enough space to hold everything!
19
Effects of Skew and Multicore
Different skews of traffic
Simple hash table result is consistently the best
Sharing data across multiple cores
Because of cache contention, performance drops
20
Future Work
21
Where simple hash table fails?
Solution to the failed cases
Improving the model
Conclusion
•
NFV is the new trend in data-centers and ISPs
•
Measurement is a key component for NFV
•
Simple hash table works best
For many tasks, the working set fits in the cache
Especially when the traffic is skewed
We expect this to be true in the future with newer servers
Larger cache, better efficient cache
22
Thanks TY.
Good afternoon,
My name is Omid and today I'll answer this question that which measurement algorithm
works best in the software switch context. This is a joint work with Masoud Moshref, and
Minlan Yu, my advisor, from USC.
This content explores the importance of measurement algorithms in software, focusing on network function virtualization (NFVs) and software switches. It discusses the critical role of measurement in decision-making for firewall, load balancing, and intrusion detection systems in managing NFVs. The need for re-evaluating measurement algorithms in response to new design concerns and previous works in the field is highlighted.
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.
E N D
Presentation Transcript
Re-evaluating Measurement Algorithms in Software Omid Alipourfard, Masoud Moshref, Minlan Yu {alipourf, moshrefj, minlanyu}@usc.edu
Software Switches are Popular Data centers: Use the cloud to manage the cloud Load balancer and Firewall on VMs ISPs: AT&T replaces hardware routers with NFV Allow customers to run network functions on commodity servers 2
Network Function Virtualization Typical X86 server NAT IDS DPI Firewall 3
Measurement is Critical for NFVs Make decisions based on measurement input Firewall, load balancing, intrusion detection systems (IDS) We also need measurement for managing NFVs Profiling NFV usage, resource scheduling.. If you can t measure it, you can t manage it 4
What is the best algorithm for measurement in software? 5
New Design Concerns in Software Domain Hardware switches Software switches Constraint Limited Memory Size Working-set (Cache size) Objective Fit in the Memory Maximizing Throughput It s time to reevaluate measurement algorithms in software context! 6
Previous Works on Measurement Algorithms Measurement task Heavy-hitters detection Super-spreaders detection Flow-size distribution Change detection Entropy estimation Quantiles 7
Measurement Algorithms Measurement task Sketch Heap/tree Heavy-hitters detection Super-spreaders detection Popular measurement algorithms in the hardware switch and database domain Flow-size distribution Change detection Entropy estimation Quantiles 8
Measurement Tasks Measurement task Sketch Heap/tree Heavy-hitters detection NSDI 13, JoA 05 ICDT 05, ANCS 11 Super-spreaders detection NSDI 13, PODS 05 Flow-size distribution SIGMETRICS 04 Change detection TON 07 CONEXT 13 Entropy estimation COLT 11 Quantiles Hot ICE 11 SIGMOD 99, 01, 13 9
Measurement Tasks Measurement task Sketch Heap/tree Heavy-hittersdetection NSDI 13, JoA 05 ICDT 05, ANCS 11 Super-spreaders detection NSDI 13, PODS 05 Flow-size distribution SIGMETRICS 04 Change detection TON 07 CONEXT 13 Entropy estimation COLT 11 Quantiles Hot ICE 11 SIGMOD 99, 01, 13 10
Algorithms for Heavy-hitter Detection Heavy hitters: Detect the most popular flows in the traffic. Different memory-computation tradeoffs: Simple hash table: For every packet, hash the header, update a counter Different trade offs for algorithms: which one is the best? Sketches: For every packet, hash the header several times, update relevant counters. Processing Memory Precision Heap: Keep a heap of counters, remove smallest counter when there is no space for new packets. Processing Memory Precision 11
Evaluating the algorithms Compare different measurement algorithms Hash, sketch, heap Metrics Performance: network throughput, per-packet delay Precision: % of selected heavy-hitters that are correct. Evaluation setting CAIDA traces Click modular router modified with DPDK 12
Simple Hash Table Works the Best Throughput Simple hash table has 34% higher throughput over sketches, and 108% over heap. Precision Simple hash table is only 4% less accurate for sizes greater than 200KB. The accuracy difference is less than 1% when the size is greater than 10MB. 13
Hash has the lowest average per packet delay Average Per Packet Delay (ns) O(log(N)) memory accesses 640 ns 320 ns 3 hashes + 6 mem. accesses 160 ns 1 hash + 2 mem. accesses 80 ns 16 KB 128 KB 1,024 KB 8,192 KB 65,536 KB Heap Sketch Hash table 14
Tail Latency Jump from L3 to Memory 95th Percentile Packet Delay 2,048 ns 1,024 ns 512 ns 256 ns 128 ns 64 ns 16 KB 128 KB 1,024 KB 8,192 KB 65,536 KB Heap Sketch Hash table 15
Simple hash table works well for heavy-hitter detection. What about the other tasks? Observation All measurement tasks maintain a table of entries (e.g., counters). @10 Gbps, 67 ns to process each packet on average (worst case). 16
Memory access is too slow 16 ns L3 Memory 100 ns 17
Plenty of memory for measurement #entries that can be used for line-rate packet processing ~5 Mil NetFlow Entries ~15 Mil Hash Entries with Distinct counters ~200 Mil Hash Entries 18
Enough memory to hold everything! 5 Mil NetFlow Entries 15 Mil Hash Entries with Distinct counters 200 Mil Hash Entries Average Flow size of 1KB 1.25 Mfps @ 10Gbps More than enough space to hold everything! 19
Effects of Skew and Multicore Different skews of traffic Simple hash table result is consistently the best Sharing data across multiple cores Because of cache contention, performance drops 20
Future Work Where simple hash table fails? Solution to the failed cases Improving the model 21
Conclusion NFV is the new trend in data-centers and ISPs Measurement is a key component for NFV Simple hash table works best For many tasks, the working set fits in the cache Especially when the traffic is skewed We expect this to be true in the future with newer servers Larger cache, better efficient cache 22
