Sketchovsky: Enabling Sketch Ensembles on Programmable Switches
Sketchovsky: Enabling Ensembles of
Sketches on Programmable Switches
H
u
n
N
a
m
k
u
n
g
*
§
Z
a
o
x
i
n
g
L
i
u
†
D
a
e
h
y
e
o
k
K
i
m
‡
V
y
a
s
S
e
k
a
r
*
§
P
e
t
e
r
S
t
e
e
n
k
i
s
t
e
*
*
†
‡
§
(Now at)
Network measurement is essential for management
Resource
Provisioning
Syn Flood
Detection
Port Scan
Detection
Management
Tasks
Top K flows
on
5-tuple
Unique # of flows
on
srcIP
Entropy
on
dstPort
…
D
i
v
e
r
s
e
M
e
a
s
u
r
e
m
e
n
t
T
a
s
k
s
…
2
Ensemble of sketches on programmable switch is promising
Data
Plane
Control
Plane
Packets
Top K flows
on
5-tuple
Unique # of flows
on
srcIP
Entropy
on
dstPort
…
Fixed-Function Network Switch
Packet Sampling Approach (Netflow)
P
r
o
g
r
a
m
m
a
b
l
e
S
w
i
t
c
h
3
S
k
e
t
c
h
i
n
g
A
l
g
o
r
i
t
h
m
s
(
S
k
e
t
c
h
e
s
)
S
k
e
t
c
h
E
n
s
e
m
b
l
e
Prior work cannot handle ensemble of sketches
T
h
r
e
e
r
e
q
u
i
r
e
m
e
n
t
s
f
o
r
r
u
n
n
i
n
g
t
h
e
s
k
e
t
c
h
e
n
s
e
m
b
l
e
1.
G
e
n
e
r
a
l
i
t
y
:
a
n
y
c
o
m
b
i
n
a
t
i
o
n
o
f
m
e
a
s
u
r
e
m
e
n
t
t
a
s
k
s
2.
L
o
w
R
e
s
o
u
r
c
e
:
f
o
o
t
p
r
i
n
t
o
n
s
w
i
t
c
h
3.
H
i
g
h
A
c
c
u
r
a
c
y
:
f
o
r
m
e
a
s
u
r
e
m
e
n
t
t
a
s
k
s
4
Per-sketch optimization has fundamental limitation for ensemble
SketchLib (NSDI’ 22)
HW resources
5
Sketchovsky Overview
Sketchovsky
Cross-Sketch
Optimizations
Sketch
Ensemble
An optimized
sketch code
I
N
P
U
T
•
P
r
o
p
o
s
e
f
i
v
e
c
r
o
s
s
-
s
k
e
t
c
h
o
p
t
i
m
i
z
a
t
i
o
n
s
a
s
b
u
i
l
d
i
n
g
b
l
o
c
k
s
•
F
i
n
d
b
e
s
t
s
t
r
a
t
e
g
y
o
n
h
o
w
t
o
a
p
p
l
y
b
u
i
l
d
i
n
g
b
l
o
c
k
s
•
Automatically generate optimized code
→ up to
18 sketch instances
by reducing up to
45% HW resource
Auto-code
Composition
6
Outline
•
Motivation
•
Five cross-sketch optimizations
•
Strategy finder
•
Evaluation
7
Sketches have three common workflow steps
Hash
Computation
Counter
Update
Heavy Flowkey
Storage
8
Five cross-sketch optimizations
Sketch
Ensemble
9
Hash1: Reusing hash results reduces hash units
10
Hash2: XOR-based hash reconstruction
H
a
s
h
r
e
s
u
l
t
s
c
a
n
b
e
r
e
c
o
n
s
t
r
u
t
e
d
u
s
i
n
g
X
O
R
o
p
e
r
a
t
i
o
n
3 hash units → 2 hash units
Applicable condition
11
Ctr1: Reusing counter arrays can reduce memory
Sketch 1
Sketch 2
Sketch 3
Sketch 1,2,3
Data
Plane
Control
Plane
Measurement
Task 1
Measurement
Task 2
Measurement
Task 3
Accuracy is improved!
12
Outline
•
Motivation
•
Five cross-sketch optimizations
•
Strategy finder
•
Evaluation
13
Problem formulation for strategy finder
Sketch Ensemble
5
O
p
t
i
m
i
z
a
t
i
o
n
s
Challenge: large search space!
14
Search space decomposition
across
workflow steps
Large search space
15
Sketch Ensemble
Outline
•
Motivation
•
Five cross-sketch optimizations
•
Strategy finder
•
Evaluation
16
Sketchovsky makes previously infeasible ensembles
become feasible
Higher is better
17
Sketchovsky reduces hardware resources
Lower is better
18
Sketchovsky preserves or improves accuracy
Lower is better
19
Conclusion
•
Diverse measurement tasks at scale are critical for management
•
Sketch ensemble on programmable switch is promising, but prior
work has fundamental limitation
•
We propose a composition framework Sketchovsky that propose
cross-sketch optimizations, strategy finder, and auto-code
composition
•
Sketchovsky makes previously infeasible ensembles feasible by
reducing up to 45% hardware resources without accuracy loss
20
Network measurement plays a crucial role in management tasks such as port scan detection and resource provisioning. The concept of sketch ensembles on programmable switches shows promise in addressing key challenges related to control and data plane operations. This approach offers a way to efficiently handle diverse measurement tasks with high accuracy, while minimizing resource footprints. Previous work and limitations in per-sketch optimization are also discussed, highlighting the need for more effective strategies. Sketchovsky introduces cross-sketch optimizations to enhance the performance of sketch ensembles, aiming to generate optimized code and reduce hardware resource usage significantly.
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
Sketchovsky: Enabling Ensembles of Sketches on Programmable Switches Hun Namkung* Zaoxing Liu Daehyeok Kim Vyas Sekar* Peter Steenkiste* (Now at) *
Network measurement is essential for management Management Tasks Port Scan Detection Resource Provisioning Syn Flood Detection Diverse Top K flows on 5-tuple Unique # of flows on srcIP Entropy on dstPort Measurement Tasks 2
Ensemble of sketches on programmable switch is promising Control Plane Top K flows on 5-tuple Unique # of flows on srcIP Entropy on dstPort Sketch Ensemble Data Plane Sketch Instance N Packets Sketch Sketch Sketching Algorithms (Sketches) Packet Sampling Approach (Netflow) Instance 2 Instance 1 Fixed-Function Network Switch Programmable Switch 3
Prior work cannot handle ensemble of sketches Three requirements for running the sketch ensemble 1. Generality: any combination of measurement tasks 2. Low Resource: footprint on switch 3. High Accuracy: for measurement tasks Prior Work Generality Low Resource High Accuracy More expressive sketches (UnivMon, CocoSketch) Per-sketch optimization (SketchLib) Dynamic resource allocation (P4All, FlyMon) 4
Per-sketch optimization has fundamental limitation for ensemble SketchLib (NSDI 22) HW resources Can we run the sketch ensemblewith sub-linear resources while preserving high accuracy? 5
Sketchovsky Overview Sketch Ensemble inst1.p4 inst1.p4 inst1.p4 inst1.p4 sket1.p4 sket1.p4 INPUT An optimized sketch code Sketchovsky Apply opt X to inst Y Strategy Strategy Finder Auto-code Composition Cross-Sketch Optimizations opt.p4 opt.p4 Propose five cross-sketch optimizations as building blocks Find best strategy on how to apply building blocks Automatically generate optimized code up to 18 sketch instances by reducing up to 45% HW resource 6
Outline Motivation Five cross-sketch optimizations Strategy finder Evaluation 7
Sketches have three common workflow steps Heavy Flowkey Storage Counter Update Hash Packets Computation flow key = srcIP +1 3 1 Pkt header SRAM Storage 5 +1 2 192.168.0.1 +1 2 3 SALU SRAM Hash Unit Programmable Switch 8
Five cross-sketch optimizations We can reuse hardware resources across sketch instances! Sketch3 Sketch2 Sketch1 Heavy Flowkey Storage Heavy Flowkey Storage Heavy Flowkey Storage Counter Update Counter Update Counter Update Hash Hash Hash Computation Sketch Ensemble Computation Computation O1. reuse hash results as-is O2. reuse hash results with XOR O5. reuse heavy flowkey storage O3. reuse counter arrays O4. reuse a SALU for two counter arrays 9
Hash1: Reusing hash results reduces hash units Applicable condition Sketch 1 Sketch 2 Sketch 3 Flowkey ????? ????? ????? 31????? 11????? 11????? 21????? Hash Units 12????? 12????? 22????? ??????????? 13????? 13????? Hash results can be reusedacrosssketch instances! 6 hash units 3 hash units 10
Hash2: XOR-based hash reconstruction Applicable condition Sketch 1 Sketch 2 Sketch 3 { } = { } Flowkey ????? ????? ?????,????? 3?????,????? 1????? 2????? Hash Units ??????????? 1????? 2????? Hash results can be reconstruted using XOR operation 3 hash units 2 hash units 11
Ctr1: Reusing counter arrays can reduce memory Accuracy is improved! Control Plane Measurement Task 1 8 SRAMs Measurement Task 2 13 SRAMs Measurement Task 3 ?1 ?3 ?2 ?3 ?3 +1 +1 +1 +1 ?3 ?2 +1 +1 +1 +1 Data Plane ?1 ?1 ?2 +1 +1 +1 ?1 +1 +1 Sketch 1,2,3 Sketch 2 Sketch 1 Sketch 3 SALU ( ??): 9 4 SRAM ( ????) : 25 13 12
Outline Motivation Five cross-sketch optimizations Strategy finder Evaluation 13
Problem formulation for strategy finder For all possible strategy ?, we want to solve ? 5 Optimizations X = ???? ??_????????(?) ?.?. ????? ? = ???? ??? 1??? 2 ???1 ???2 ??? ?1 ?2 ?3 ?4 ?5 ?6 ?7 Sketch Ensemble Challenge: large search space! 14
Search space decomposition across workflow steps ? Large search space ???? ???? ???? X = ???? ??_????????(?) ?.?. ????? ? = ???? ??? 1??? 2 ???1 ???2 ??? ?1 ?2 ?3 ?4 ?5 ?6 ?7 Sketch Ensemble Equivalent Solve above for???? , ????, ???? separately and merge: ???? ,???? Small search space ,???? = ? 15
Outline Motivation Five cross-sketch optimizations Strategy finder Evaluation 16
Sketchovsky makes previously infeasible ensembles become feasible Higher is better 17
Sketchovsky reduces hardware resources Number of sketch instances = 12, we generate 300 ensembles Resource Use (RU) % : ????????? ???????? Error bar : 10% ~ 90% percentile ???? ???????? Lower is better 18
Sketchovsky preserves or improves accuracy 10 sketching algorithms LC Linear counting HLL HyperLogLog Lower is better PCSA PCSA MRB Multi-resolution Bitmap MRAC MRAC CS Count-sketch CM Count-min sketch KARY K-ary sketch ENT Entropy sketch UM UnivMon 19
Conclusion Diverse measurement tasks at scale are critical for management Sketch ensemble on programmable switch is promising, but prior work has fundamental limitation We propose a composition framework Sketchovsky that propose cross-sketch optimizations, strategy finder, and auto-code composition Sketchovsky makes previously infeasible ensembles feasible by reducing up to 45% hardware resources without accuracy loss 20
