流表查找过程是Open vSwitch核心中的核心。在此之前，庾志辉写过关于对Open vSwitch（下文简称OVS）源代码分析的系列博客（链接如下：http://blog.csdn.net/yuzhihui_no1/article/details/39504139），时间是2014年9月25日，sdnlab前几个月时间也对这个OVS源代码分析系列进行了转载（链接如下：http://www.sdnlab.com/3206.html）。
文中的分析对于研究OVS的人来说有很大的帮助，减少了许多阅读代码的弯路，在这里对他表示感谢。有一点不足的是，由于庾志辉当时分析的应该是OVS2.0（或者2.1）的代码，之后OVS对其自身查表的过程进行了改进，因此当前OVS版本（2.4）中描述的查表算法与庾志辉当时分析的流表查找过程已经有了一些区别。为此，本文对新改进的OpenFlow流表查找算法进行分析，供大家参考、交流。在庾志辉博客中已经提到的内容就不在此赘述，主要讲一些区别（即OVS流表查找改进的地方）以及个人的一些理解。
在一个网络交换设备中，报文的处理流程可简化为以下三个步骤：协议解析，表项查找，动作执行（包含转发、对报文的修改等动作），如图1所示。由于表项的数目可能很大，匹配的形式包括最长前缀匹配、精确匹配、范围匹配，设计高效的查表算法一直是网络研究人员追求的目标。表项查找设计涉及到两个方面：表项数据结构的组织和查表算法的执行。
OVS是部署在服务器内部，用于实现虚拟机之间交换的OpenFlow软件交换机。软件交换机通常运行在通用处理器（CPU）之上，因此其查表时间相比于用ASIC、TCAM、NP等硬件实现更慢。与传统的路由器、交换机不同，OpenFlow的匹配域包含了L2-L4等匹配域。由于匹配域增多，为了防止表项产生组合爆炸问题，OpenFlow规范中指出，其转发过程采用多级流水线查表设计。这样一来，OVS高效查表的难度和挑战进一步加大，其查表设计就显得尤为重要，直接影响软件转发的性能。
本文将从表项查找的两个方面，表项数据结构的组织（Megaflow Cache+Microflow Cache）和查表算法（元组空间搜索），对OVS的流表查找过程进行详细分析。
一直以来，流Cache是提高查表性能的有效手段，已经被广泛应用于报文查表加速。它将数据平面的转发路径分为快速路径（即流Cache）和慢速路径，利用流量局部特性，使得大部分报文命中快速路径中的表项，从而提高转发性能。OVS也采用了流Cache设计思路。
OpenFlow流Cache的组织架构改进经历了三个阶段。
在早期OVS的版本中，为缓解多级流表查表慢的问题，OVS在内核态采用Microflow Cache方法。Microflow Cache是基于Hash的精确匹配查表（O(1)），表项缓存了多级查表的结果，维护的是每条链接粒度的状态。Microflow Cache减少了报文进用户态查多级表的次数。一条流的首报文进入用户态查表后，后续的报文都会命中内核中的Microflow Cache，加快了查表速度。但是对于大量短流的网络环境来说，Microflow Cache命中率很低，导致大部分报文仍然需要到用户态进行多级流表查找，因此转发性能提升有限。
而后，为了解决Mircoflow Cache存在的问题，OVS采用Mircoflow Cache代替了Megaflow Cache。与Mircoflow Cache的精确Hash查表不同，Megaflow Cache支持带通配的查表，所以可减少报文至用户空间查表的次数。庾志辉的博客中当时分析的就是关于megaflow的数据结构和查表流程，相关内容不在此赘述，请看上文中的链接。但是，由于OVS采用元组空间搜索（下文介绍）实现Megaflow Cache的查找，所以平均查表次数为元组表的数量的一半。假设元组空间搜索的元组表链为m，那么平均查表开销为O(m/2)。Mircoflow Cache和Megaflow Cache查表开销对比为O(1)< O(m/2)。因此，Megaflow Cache相比于Mircoflow Cache，尽管减少了报文进用户空间查表的次数，但是增加了报文在内核态查表的次数。
为此，OVS当前版本采用Megaflow Cache+Microflow Cache的流Cache组织形式，仍保留了Microflow Cache作为一级Cache，即报文进入后首先查这一级Cache。只不过这个Microflow Cache含义与原来的Microflow Cache不同。原来的Microflow Cache是一个实际存在的精确Hash表，但是最新版本中的Microflow Cache不是一个表，而是一个索引值，指向的是最近一次查Megaflow Cache表项。那么报文的首次查表就不需要进行线性地链式搜索，可直接对应到其中一张Megaflow的元组表。这三个阶段的查表开销如表1所示。
| 流Cache的组织 |
查表开销 |
备注 |
| Mircoflow Cache |
O(1) |
|
| Megaflow Cache |
O(m/2) |
m为元组表的数量 |
| Mircoflow Cache& Megaflow Cache |
P*O(1)+(1-P)*O(m/2) |
P为命中一级表的概率 |
Microflow Cache和Megaflow Cache的组织和关系由于和查表算法紧密关系，所以在下文分析完元组空间搜索后给出。
附带提两点。1，在OVS的NEWS文件夹中记录了每个版本更新的相关细节，包括流Cache的设计，所以读者可在里面搜索到OVS功能演进过程的所有信息。2，具体Megaflow的计算过程尽管不是本文讨论的范围，但的确非常精妙，有兴趣的读者可关注一下。
由于OpenFlow的匹配域扩展到了十二个字段甚至更多的字段，其协议解析后提取的查表关键字（即sw_flow_key）数据结构表示如图2所示。
所以设计查找算法在性能、存储方面更具挑战。在防火墙、QoS等方面已经对多字段查表进行了大量的研究，若将匹配域中的每一个字段又被称为一个维度，多字段的软件查表算法大体上可以分为两类：单维组合分类算法和多维联合分类算法。单维组合查找算法的主要思想是：单独地对数据包每个字段进行匹配，并对每个字段的匹配结果进行合并从而找到最终匹配的规则，其代表包括递归流分类（RFC）、位向量（BV）等。多维联合分类查找算法的大致思想是不单独地考虑每个字段内部特点，而是简单地把包头的所有字段看作一个维度，进行联合查找，其代表包括决策树（Decision tree）、元组空间搜索（TSS）等。
由于OVS选择采用元组空间查找(Tuple Space Search，TSS)，因此这里只重点介绍TSS算法，感兴趣的同学可百度其他算法。TSS算法的主要思想是，将所有规则按照各字段前缀长度的组合划分成比规则数目小得多的元组集合，然后在这些元组里进行哈希查找。举个例子，有如下规则集，如表2所示包含三个匹配域和10条对应的规则。表中R1-R10为规则，F1、F2、F3为三个匹配字段，每个字段均为4bit。
| 规则 |
F1 |
F2 |
F3 |
| R1 |
0*** |
01** |
100* |
| R2 |
01** |
1*** |
010* |
| R3 |
1*** |
01** |
110* |
| R4 |
00** |
0*** |
100* |
| R5 |
* |
0101 |
* |
| R6 |
1*** |
10** |
101* |
| R7 |
00** |
1*** |
000* |
| R8 |
* |
1101 |
* |
| R9 |
* |
1001 |
* |
| R10 |
10** |
1*** |
010* |
用[x，y，z]中的x、y、z分别表示F1、 F2、F3的前缀长度。则10条规则表示如下。
| 规则 |
前缀组合[x，y，z] |
| R1 |
[1,2,3] |
| R2 |
[2,1,3] |
| R3 |
[1,2,3] |
| R4 |
[2,1,3] |
| R5 |
[0,4,0] |
| R6 |
[1,2,3] |
| R7 |
[2,1,3] |
| R8 |
[0,4,0] |
| R9 |
[0,4,0] |
| R10 |
[2,1,3] |
由上表可知，规则可分为三类，R1、R3、R6∈[1,2,3]，R5、R8、R9∈[0,4,0]，R2、R4、R7、R10∈[2,1,3]。在不考虑规则优先级的情况下，TSS的查找表构造如图3所示。
所以最多只需要三次Hash查找，即可找到对应表项。可以看到TSS的一个最大优点是，当所有规则的各字段长度的组合相对较少时，TSS算法是很高效的。如例子中的，10条规则只需要3次hash查找即可。TSS的缺点是当所有规则的各字段的组合很多时，最坏情况下的搜索次数就变为n（n为规则的数量）。在上个例子中，假设所有规则的字段组合都不一致，那么TSS查表次数就为10，退化为最原始的顺序查表。因此，TSS的算法是否高效与转发规则的特征有直接的关系。
那么为什么OVS选择TSS，而不选择其他查找算法？论文[2]给出了以下三点解释：
（1）在虚拟化数据中心环境下，流的添加删除比较频繁，TSS支持高效的、常数时间的表项更新；
（2）TSS支持任意匹配域的组合；
（3）TSS存储空间随着流的数量线性增长。
综上原因，OVS选择了TSS查表算法，并对其进行了一些优化（优化的一些手段，例如优先级排序、分段hash查找等等，详见论文和源码）。结合上面所提到的Microflow Cache和Megaflow Cache，给出目前OVS中内核态查表的流程，如图4所示。
图中红色标记的Mask_cache_array即为Microflow Cache，是个地址，存放的是上一次匹配命中的Megaflow中某个元组表的索引值。其结构如下。
|
1
2
3
4
|
struct
mask_cache_entry
{
u32
skb_hash
;
/
/
SKB中五元组
hash后的值
u32
mask_index
;
/
/掩码数组
Mask
_array的索引值
}
;
|
Mask_array是个指针数组，数组中每个元素存放的是掩码，每个掩码就代表一个元组表，。每条流的首报文都会遍历这个数组，相当于遍历所有的元组表。每个元组表采用hash的方式，用链式解决Hash冲突。
|
1
2
3
4
5
|
struct
mask_array
{
struct
rcu_head
rcu
;
/
/
RCU控制
int
count
,
max
;
/
/掩码数组的计数和最大值
struct
sw_flow_mask
__rcu
*
masks
[
]
;
/
/掩码存放的数组
}
;
|
以上就是目前OVS查表的分析，不足之处欢迎大家批评指正。
为进一步提高OVS转发效率，我们目前正致力于FAST（Fpga Accelerated Sdn swiTc）开源项目。FAST采用可编程硬件（FPGA）对OVS的处理流程进行卸载加速，并利用FPGA可重构的特性扩展SDN交换机的功能，提高OpenFlow的转发效能，推进SDN在实际环境中的部署。
一、实践是检验真理的唯一标准
OVS的论文中出现过这样的表述“我们根据实际部署后发现xxx这个更好”，说明对于算法或者优化机制的选择，有些时候是没有理论依据的，而是根据在实际测试的结果作出的。这点从上面采用元组空间搜索算法的理由也可以看出。换句话说，如果不是在虚拟化数据中心的应用场景中，OVS是否还采用这样的算法和优化查表机制，就该值得商榷了。
二、温故而知新
看大牛的论文时常觉得写得晦涩难懂，一点也不易读。但通常情况下是自己的姿势水平不够，相关的背景知识了解太少，基础不够，所以还要继续学习。
参考文章
文中的分析主要参考来源于两篇论文以及OVS2.4源码，如下：
[1] N. Shelly, E. Jackson, T. Koponen, N. McKeown, and J. Rajahalme. Flow Caching for High Entropy Packet Fields. In Proc. of HotSDN, 2014.
[2] Pfaff B, Pettit J, Koponen T, et al. The design and implementation of Open vSwitch[C]//12th USENIX Symposium on Networked Systems Design and Implementation. 2015.（NSDI 2015 Best Paper Award）
[3] Open vSwitch version 2.4. http://openvswitch.org/releases/openvswitch-2.4.0.tar.gz
作者简介：
毛健彪：国防科技大学计算机学院网络与信息安全研究所在读博士生，从事软件定义网络、数据中心网络等方面等研究。作者所在的课题组目前正在进行基于FPGA的SDN硬件交换机开源项目FAST的开发与推广，特别感谢国防科技大学计算机学院网络所徐东来工程师在OVS代码分析过程中的帮助和指导。
