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