2011年8月12日 星期五

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