关于TTS（元组空间搜索算法）的详细介绍可以参考文章OVS+DPDKDatapath包分类技术。本文仅对本篇博客做简单介绍，其中案例及部分图片来自OVS+DPDKDatapath包分类技术TTS算法主要组件Rule：单包过滤规则+action下面是一个具体的例子：1Rule#1:ip_src=192.168.0.0/16ip_dst=0/0protocol=0/0port_src=0/0port_dst=0/02规则#2：ip_src=0/0ip_dst=23.23.233.0/24protocol=6/8(TCP)port_src=0/0port_dst=23/163规则#3：ip_src=0/0ip_dst=11.11.233.0/24协议=17/8(UDP)port_dst=0/0port_dst=4789/164规则#4：ip_src=10.10.0.0/16ip_dst=0/0protocol=0/0port_src=0/0port_dst=0/0可以看到一条规则中有多个字段，每个字段的形式为：字段值/掩码前缀元组：使用相同的匹配字段+每个匹配字段都使用相同的掩码长度。下面是一个具体的例子：1Tuple#1:ip_src_mask=16ip_dst_mask=0protocol_mask=0port_src_mask=0port_dst_mask=02Tuple#2:ip_src_mask=0ip_dst_mask=24protocol_mask=8port_src_mask=0port_dst_mask=16tupleistomerge规则同规则。比如上面的rule#1和rule#4可以看成是同一个元组#1，因为每个字段的掩码都是一样的，所以这个元组有以下特点：使用相同的匹配字段每个匹配字段使用samemasklengthKey:usedforhash以Tuple#2中的Rule#2为例进行说明，首先使用tuplemask匹配规则中各个字段的值，丢弃Tupledon'tcareaboutbits，得到：ip_src=_ip_dst=23.23.233protocol=6port_src=_port_dst=23然后将这些位拼接在一起就是哈希表的key，转换成二进制如下：key=00010111(23)00010111(23)11101001(233)00000110(6)0000000000010111(23)最后用这个key做哈希，就是哈希表的索引匹配过程。所有的规则被分成多个元组存储在对应的元组中。在哈希表中匹配一个数据包时，会遍历这多个元组下的哈希表，逐一检查，找出所有的匹配结果，然后根据一定的策略从匹配结果中选出最优的一个下面以ovs中的具体例子来说明：首先添加一个规则#1，规则创建过程中会创建对应的mask（maskFF.FF.FF.00），也就是TTS中的Tuple，然后是rule和mask进行AND运算生成一个key，通过对key进行哈希得到一个索引值，最后将rule#1添加到哈希表HT1对应的索引中。可以看出，同一个中的masks哈希表都是一样的。也就是说，每个元组对应一个表，然后接收到一个packet#1，如下图，在packet的查找过程中，会匹配到所有的hash表。由于只有一张表HT1，所以报文会和HT1对应的掩码进行AND运算，对结果进行哈希处理后，对应表中的结果与步骤1相同。此时，有另一个规则#2。同样的步骤新建一个表HT2收到另一个数据包Packet#2，同步骤2查找，先匹配HT1对应的掩码，如果找不到结果，再用HT对应的掩码查找2、通过以上步骤找到对应的结果可以看出TTS中的时间复杂度与Tuples的个数有关。如果Tuple的数量更多，则需要更长的时间。当Tuples个数==表项个数时，相当于将所有表项逐一遍历。OVS和TTS在之前的博文中，MegaflowCache的实现使用了TTS。如下图所示，每个megaflowcacheentry的具体实现结构对应TTS中的规则如下图。在最新的ovs中，采用了最重要的是MircroflowCache和MegaflowCache的组合，这里可以看到MegaflowCache是??以链表的形式组合在一起的。sw_flow_mask结构相当于一个掩码（TTS中的元组），sw_flow结构相当于一个规则。其中，在Microflow缓存中存放的是上次访问的sw_flow_mask索引，具体过程将在下一篇博客中详细介绍。参考资料OVS+DPDKDatapath包分类技术作者：yearsj转载请注明出处：https://segmentfault.com/a/11...
