motivation 12/8

motivation
在發表過的幾篇將simple pattern實作在TCAM的paper中，
是根據TCAM的特性：
1. ternary，也就是可以用*的表示
2. 架構中(使用TCAM以及SRAM)，讓有相同input character以及destination state的state可以盡量用*合併在一起，以達到使用更少的TCAM entry。
最後，使用TCAM就會衍生出對state assign ternary code的問題。

使用TCAM另一個目標也是要減少TCAM的entry數，降低power consumption
多數的paper都是藉由第2點的特性，讓TCAM entry可以represent多個不同states由同樣的input character到達destination state
另外在cool-CAM這篇paper，雖然是做ip lookup，提到可藉由分group的方法，降低TCAM的power consumption。

在D2FA中，
本來作者的想法是透過default transition，解決DFA的memory comsunmption問題，
實際上，會建立出default transition的原因是在：
找出2個或是多個states之間，大部份的transition是相同的，讓其中一個state來"代表"其他的state，進而取代其他state的transition，而其他state就會多出default transtion到可"代表"的state。
但d2fa使得memory access的次數增加，在基本的二維的transition table，也是依然要用symbol表示default transition存在，

綜合以上的觀點，
1.找出states可以default到的state(原D2FA paper稱之為 root of the default transition tree)
2.找到多個default root，所以可藉由這樣的方法分group，
3.各個group之中，可由default root取代group之間的transition，也就是會有TCAM的第2個特性，
3.a 在group之中，大部份的states其實也是擁有同樣的transition，
一樣可以用第2個特性來進一步的減少TCAM entry
4.可減少d2fa的memory access次數到與DFA相同的 1 per every input character。

0812 - TCAM based D2FA

參考的paper
TCAM-based DFA Deflation: A Novel Approach To
Fast and Scalable Regular Expression Matching

1.idea
雖然D2FA可以有效的解決DFA的memory comsunmption，但是在look up 的過程中，會需要經過多次的default transition，使得memory access的次數增加，也雖然透過default transition使得DFA在圖形表達時，看起來會有很少的transition數量，但是在基本的二維的transition table，也是依然要用symbol表示default transition存在，所以希望透過TCAM解決memory access的次數的問題以及用更少的memory來表達transition table

2.方法
在建立D2FA的過程中，會因為diameter bound產生不同個數的D2FA forest，較大的diameter bound 會需要多次的default transition來找出實際的next state。但是可以有效的透過default transition減少state之間大部份的相同的transition，所以實際上我們只需要保留identical transition，以及透過default transition之後才找到的next-state transition，也因為大部份的state是因為有共同的transtiion才會使得default transition存在，所以藉由這樣的"common"關係，就可以利用TCAM的ternary來做進一步的壓縮。

所以方法就是建立在
1.用D2FA來做group，
2.針對group給予在TCAM中表達出state的code

考慮一個例子，

.*A.{2}CD，
在經過"default to"過group之後，可以有以下6個group結果
(冒號後的states都是default 到冒號前的state)
0 :8 12
5 :1 5
6 :2
7 :3 7
11:6 9 11
13:0 4 10 13

考慮6以及11這兩組group

簡單表示出相關的state及 tx，
數字是state，大寫字母是指一般的transition，小寫d為default transition

       9 -C->  4     4
         ↓         ↑     ↑
        d         D    C
       ∣       ∣   ∣
       11 <-d- 6 <-d- 2


11-A-> 5
11-C-> 10
11-D-> 13

在上面提到的 identical transition (不經由default即可找到next state)
有以下幾個

9+C->4
2+C->4
6+D->4
11+A->5
11+C->10
11+D->13

透過default transition之後才找到next state的transition

2+A->5 6+A->5 9+A->5
2+D->4 6+C->10 9+D>13

雖然從11出發三個transition規類在identical transition
但是11跟2 6 9 三個state都有共同的transtion，
所以經過給TCAM CODE之後，只需要保留

9+C->4    6+D->4   *+A->5
2+C->4    2+D->4   *+C->10
                                  *+D->13


雖然這只是一組group的例子
全部group都有考慮的話，可以有的common transition會更多，也可以用更少的memory

Research

• IP Look-Up
  [ISCC2010]
  DUO–Dual TCAM Architecture for Routing Tables with Incremental
  
  [INFOCOM2011]
  Offset Addressing Approach to Memory-Efficient IP Address Look up
  
• Packet Classification
  
• Pattern Match
  [ISSP2008]
  XFA：Faster Signature Matching With Extended Automata
  
  [ANCS2007]
  An Improved Algorithm to Accelerate Regular Expression Evaluation
  
  [ANCS2006]
  Advanced Algorithms for Fast and Scalable Deep Packet Inspection
  
  [SIGCOMM2010]
  An Improved DFA for Fast Regular Expression Matching
  
  [ICC2010]
  Sampling Techniques to Accelerate Pattern Matching in Network Intrusion Detection Systems
  
  [INFOCOM2011]
  An Efficient Regular Expressions Compression Algorithm From A New Perspective
  

About me

Name : Wen-Tse Liang

Birthday : 07-03-1988

Education :
National Cheng Kung University
    Dept. of Computer Science and Information Engineering
        Computer and Internet Architecture Lab 

Chung Yuan Christian University
    Dept. of Information and Computer Engineering

E-mail : p76994393@mail.ncku.edu.tw

FaceBook :http://www.facebook.com/zetse