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

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

以下為具體的例子：

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

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

以下為具體的例子：

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是將有相同規則的rule進行合并，例如上述rule #1和rule #4可以看成是同一個tuple #1，因為其每個字段的掩碼都相同，所以tuple有如下特點：

使用相同的匹配字段

每個匹配字段都使用相同的掩碼長度

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

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

然后把這些位拼接起來，就是哈希表的key，轉換為二進制如下：

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

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

所有的rule都被分成了多個tuple，并存儲在相應tuple下的哈希表中

當要對一個包進行匹配時，將遍歷這多個tuple下的哈希表，一個一個查過去，查出所有匹配成功的結果，然后按一定策略在匹配結果中選出最優的一個。

下面以ovs中具體的事例進行說明：

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

可以看到，同一個哈希表中的mask都是相同的，也就是說每一個tuple對應一個表

接下來收到一個包packet #1，如下圖所示，該包查找的過程中，會與所有的hash表進行匹配，由于目前只有一個表HT 1，所以該包會與HT 1對應的mask進行與運算，對其結果進行散列后查到對應表中的結果

同步驟1，此時又來了一個rule #2，按照同樣的步驟，創建一個新的表HT 2

收到另一個包Packet #2，同步驟2進行查找，首先與HT 1對應的mask進行匹配查找，無法找到結果

然后與HT 2對應的mask進行查找，查詢到對應的結果

通過上述步驟可以看出來，TTS中的時間復雜度與Tuple的數量相關，如果Tuple的數量越多，則耗費的時間越長，當Tuple的數量==表項的數量，此時等同于挨個遍歷所有的表項

在上一篇博文中，其中Megaflow Cache的實現就是采用了TTS，在如下圖中，每個megaflow cache的表項對應TTS中的rule

具體的實現結構如下圖，在最新的ovs中采用的是Mircroflow cache和Megaflow Cache結合的方式，其中可以看到Megaflow Cache是通過鏈表的形式進行組合的，sw_flow_mask結構體相當于是mask（TTS中的tuple），sw_flow結構體相當于是rule，其中Microflow cache中存放的是上次訪問的sw_flow_mask索引，具體的流程會在接下來的博客進行詳細的介紹。

OVS+DPDK Datapath 包分類技術

作者：yearsj
轉載請注明出處：https://segmentfault.com/a/11...