Transcript Untersuchungen zur MAC Address Translation (MAT)

Packet Classification with
Evolvable Hardware Hash
Functions
Harald Widiger, Mathias Handy, Dirk Timmermann
University of Rostock
Institute of Applied Microelectronics
and Computer Science
Packet Classification and Hash
Functions
 Packet Classification Problem: In huge rule
sets a search takes much time and/or
demands huge memories
 Hash functions have a search complexity of
ideally O(1) and memory demand of O(N)
 Problem when using (hardware) hash functions:
 High performance for different key sets
 Low hardware costs for a hardware
implementation
16.07.2015
2
Evolvable Hardware
 Goal: High performance for different
and changing key set with low
hardware costs
 Solution: a function which can adapt
constantly and autonomously to an
actual key set  evolvable hardware
16.07.2015
3
Hardware Hash Function
Key (N Bit wide)
Key
Element
0
Element
1
Element
2
Element
N-1
Gene
Gene
Genome
Mux 0
N to 1
Mux 1
N to 1
Mux
N to 1
Mux
N to 1
Mux M-1
N to 1
Out0
Hash (M Bit wide)
 Genomesize:
16.07.2015
2  M  log2 ( N )
4
System Architecture
Classification Rule
Frame In
Data Path
Frame Out
Hash
Update
Keys
Hardware
Evolution
 Hardware consists of a datapath and an evolution
module


In the datapath the packet classification is done by finding
classification rules for incoming frames with the help of the
hash functions
The evolution module changes the hash function depending
on the existing key to increase lookup performance
16.07.2015
5
Evolutionary Algorithm
Classification Rule
Frame In
Data Path
Frame Out
Hash
Update
Genom
Update
Child
Select
16.07.2015
Keys
Survivor
Selection
Fitness
Evaluation
Mutate
Hash
Reconfiguration
6
Simulation Results
18
Hash 1 (50 %)
16
Hash 1 (75 %)
Hash 2 (50 %)
14
Hash 2 (75 %)
average mem. acc.
12
Hash 3 (50 %)
log2(N)
10
8
6
4
2
0
100
1000
10000
100000
1000000
number of elements
16.07.2015
7
Outlook
 Hardware implementation into an
FPGA
 Simulation of the lookup performance
with real rules sets
 Improvement of the performance of
the fitness evaluation
 Finally implementation in a
dynamically reconfigurable
environment
16.07.2015
8