摘要：關(guān)于元組空間搜索算法的詳細(xì)介紹可以參考包分類技術(shù)這篇文章，本文只對(duì)該篇博客進(jìn)行簡(jiǎn)單的介紹，其中案例和部分圖片來自于包分類技術(shù)算法主要組成部分單條的包過濾規(guī)則動(dòng)作以下為具體的例子可以看到一個(gè)中有多個(gè)字段，每個(gè)字段的形式為字段值掩碼前綴使用相同

關(guān)于TTS（元組空間搜索算法）的詳細(xì)介紹可以參考OVS+DPDK Datapath 包分類技術(shù)這篇文章，本文只對(duì)該篇博客進(jìn)行簡(jiǎn)單的介紹，其中案例和部分圖片來自于OVS+DPDK Datapath 包分類技術(shù)

以下為具體的例子：

1 Rule #1: ip_src=192.168.0.0/16 ip_dst=0/0 protocol=0/0 port_src=0/0 port_dst=0/0
2 Rule #2: ip_src=0/0 ip_dst=23.23.233.0/24 protocol=6/8(TCP) port_src=0/0 port_dst=23/16 
3 Rule #3: ip_src=0/0 ip_dst=11.11.233.0/24 protocol=17/8(UDP) port_dst=0/0 port_dst=4789/16
4 Rule #4: ip_src=10.10.0.0/16 ip_dst=0/0 protocol=0/0 port_src=0/0 port_dst=0/0

可以看到一個(gè)rule中有多個(gè)字段，每個(gè)字段的形式為 ：字段值/掩碼前綴

以下為具體的例子：

1 Tuple #1: ip_src_mask=16 ip_dst_mask=0 protocol_mask=0 port_src_mask=0 port_dst_mask=0
2 Tuple #2: ip_src_mask=0 ip_dst_mask=24 protocol_mask=8 port_src_mask=0 port_dst_mask=16

tuple是將有相同規(guī)則的rule進(jìn)行合并，例如上述rule #1和rule #4可以看成是同一個(gè)tuple #1，因?yàn)槠涿總€(gè)字段的掩碼都相同，所以tuple有如下特點(diǎn)：

使用相同的匹配字段

每個(gè)匹配字段都使用相同的掩碼長(zhǎng)度

以Tuple #2中的Rule #2為例說明一下，首先用tuple的掩碼去與rule中的各個(gè)字段值，丟棄tuple不關(guān)心的位，得到：

ip_src=_ ip_dst=23.23.233 protocol=6 port_src=_ port_dst=23

然后把這些位拼接起來，就是哈希表的key，轉(zhuǎn)換為二進(jìn)制如下：

key = 0001 0111(23) 0001 0111(23) 1110 1001(233) 0000 0110(6) 0000 0000 0001 0111(23)

最后，用這個(gè)key去做散列，即是哈希表的索引

所有的rule都被分成了多個(gè)tuple，并存儲(chǔ)在相應(yīng)tuple下的哈希表中

當(dāng)要對(duì)一個(gè)包進(jìn)行匹配時(shí)，將遍歷這多個(gè)tuple下的哈希表，一個(gè)一個(gè)查過去，查出所有匹配成功的結(jié)果，然后按一定策略在匹配結(jié)果中選出最優(yōu)的一個(gè)。

下面以ovs中具體的事例進(jìn)行說明：

首先添加一個(gè)rule #1，該rule創(chuàng)建的過程中會(huì)創(chuàng)建對(duì)應(yīng)的掩碼（mask FF.FF.FF.00），也就是TTS中的Tuple，然后rule與mask進(jìn)行與操作生成key，通過key進(jìn)行散列得到一個(gè)索引值，最終將該rule #1加入到hash表HT 1對(duì)應(yīng)的索引中

可以看到，同一個(gè)哈希表中的mask都是相同的，也就是說每一個(gè)tuple對(duì)應(yīng)一個(gè)表

接下來收到一個(gè)包packet #1，如下圖所示，該包查找的過程中，會(huì)與所有的hash表進(jìn)行匹配，由于目前只有一個(gè)表HT 1，所以該包會(huì)與HT 1對(duì)應(yīng)的mask進(jìn)行與運(yùn)算，對(duì)其結(jié)果進(jìn)行散列后查到對(duì)應(yīng)表中的結(jié)果

同步驟1，此時(shí)又來了一個(gè)rule #2，按照同樣的步驟，創(chuàng)建一個(gè)新的表HT 2

收到另一個(gè)包Packet #2，同步驟2進(jìn)行查找，首先與HT 1對(duì)應(yīng)的mask進(jìn)行匹配查找，無法找到結(jié)果

然后與HT 2對(duì)應(yīng)的mask進(jìn)行查找，查詢到對(duì)應(yīng)的結(jié)果

通過上述步驟可以看出來，TTS中的時(shí)間復(fù)雜度與Tuple的數(shù)量相關(guān)，如果Tuple的數(shù)量越多，則耗費(fèi)的時(shí)間越長(zhǎng)，當(dāng)Tuple的數(shù)量==表項(xiàng)的數(shù)量，此時(shí)等同于挨個(gè)遍歷所有的表項(xiàng)

在上一篇博文中，其中Megaflow Cache的實(shí)現(xiàn)就是采用了TTS，在如下圖中，每個(gè)megaflow cache的表項(xiàng)對(duì)應(yīng)TTS中的rule

具體的實(shí)現(xiàn)結(jié)構(gòu)如下圖，在最新的ovs中采用的是Mircroflow cache和Megaflow Cache結(jié)合的方式，其中可以看到Megaflow Cache是通過鏈表的形式進(jìn)行組合的，sw_flow_mask結(jié)構(gòu)體相當(dāng)于是mask（TTS中的tuple），sw_flow結(jié)構(gòu)體相當(dāng)于是rule，其中Microflow cache中存放的是上次訪問的sw_flow_mask索引，具體的流程會(huì)在接下來的博客進(jìn)行詳細(xì)的介紹。

OVS+DPDK Datapath 包分類技術(shù)

作者：yearsj
轉(zhuǎn)載請(qǐng)注明出處：https://segmentfault.com/a/11...