摘要：

软件定义网络（SDN）是计算机网络行业中的新范例，它将当前的分布式体系结构更改为集中式体系结构。这种集中式体系结构的三个主要组件是Openflow控制器，Openflow通道和Openflow交换机。

Openflow控制器是集中控制单元，根据Openflow协议规范，通过openflow通道与openflow交换机进行通信。启用支持Openflow的交换机是软件定义网络体系结构的基础，Openflow控制器将与传入数据包匹配所必需的数据包处理参数以及针对数据包类型要采取的操作写入Openflow交换机的流表中。

OpenFlow协议不要求使用任何特定算法在流表中搜索匹配的流，本文分析了4种数据搜索算法的性能，并提出了一种以负载因子为参数的自适应算法，以减少搜索时间。

背景/问题：

SDN网络中，控制器通过安全通道与基础网络交换机通信， Openflow是为控制器和交换机之间的通信定义的第一个标准通信接口，Openflow交换机和控制器通过安全的Openflow通道进行通信，SDN控制器将数据包处理规则写入Openflow交换机的流表。

图1显示了Openflow交换机的主要组件：

图1

交换机可以具有一个或多个流表和一个组表，用以执行数据包查找和转发。交换机中的每个流表都包含一组流条目，每个流条目都包含匹配字段、计数器和一组适用于匹配数据包的指令。 流匹配字段是使用Openflow可扩展匹配（OXM）格式描述的，它是一种紧凑的Type-Length-Value格式，长度为5到259个字节。一旦使用OXM标识了数据包匹配字段，则将数据包与在流表中找到条目匹配。 如果在当前表中找不到匹配项，则可以根据是否配置了表未命中条目（预先设定的一个处理方式），将数据包丢弃或转发到下一个表或控制器。

流表的数据包处理机制如图2所示：

图2

按我的理解，过程大概是这样的，首先一个交换机有一个或多个流表，每个流表上有许多的匹配流表项。流进入交换机以后匹配第一个流表，如果有流表项与之相匹配，则执行相应的操作，即match+action。如果没有匹配，则根据第一个流表的预先定义未命中操作，转接下一个流表或者标记为最终未命中，而最终未命中的流执行预定义好的操作。

表1中列出了流表条目的主要组成部分：

表1

• 头部的匹配字段用于匹配流表中的传入数据包。
• 优先级是流条目的匹配优先级。

（匹配字段和优先级组合在一起，唯一标识了表中的流条目。）

• 数据包匹配时更新计数器。
• 流条目中的指令用于修改数据包的操作集或管道处理。
• 超时表示在交换机使流到期之前的最大时间或空闲时间。
• Cookies是控制器用于过滤流量统计信息，流量修改和流量删除的不透明数据值，它们不用于数据包匹配。

举个例子：

在OpenVswitch 2.1.2中，结构流定义网络中的流， 该字段分为四个部分，以方便分段查找。

首先使用下层字段来标识匹配的流条目，并且仅当下层字段不足以对特定条目进行零插入时才使用上层字段，这为数据路径流提供了更好的通配符。

表2 中给出了OpenVswitch 2.1.2中定义的流匹配字段：

表2

表3和表4分别给出了用于数据包匹配的隧道参数和元数据字段：

表3和表4

尽管Openflow规范指定了每种数据包类型要匹配的数据包字段，但并没有要求使用任何特定算法来在流表中进行数据搜索。

解决方法：

本文分析了一些数据搜索的性能。

1.SEQUENTIAL SEARCH ALGORITHM（顺序搜索算法）

最简单的数据搜索算法是顺序搜索——在这种方法中，我们以任何顺序将数据插入表中，为了搜索表中的条目，我们从第一个元素开始执行搜索，并顺序执行操作，直到找到匹配的条目或到达表的末尾。

最佳情况下的性能为O（1），因为匹配项是在第一个搜索本身中获得的。但是，如果要搜索的元素不在表中，则会发生最坏情况，我们需要搜索整个表以得出该元素不在表中的结论。如果表中元素的数量为n，则顺序搜索的最差情况性能为O（n）。随着n变大，顺序搜索将是不切实际的。

密钥数量较少的另一种简单技术是直接寻址——令U = {0，1，..，m-1}是“ m”个关键字的范围，应用程序将绘制此关键字。如果此关键字的范围相当小，并且没有两个元素具有相同的关键字，则可以使用数组存储关键字。数组中的每个插槽都对应于U中的键，因此，数组或直接地址表中将存在“ m”个插槽，对应于U中的每个元素。我们可以使用关键字的值作为数组的索引来直接访问数组的位置，以查看是否存在元素。

如果我们可以使用O（1）时间搜索条目，同时将表大小限制为| K |，这将是有利的。即存在一个数组里，需要查k的时候，则直接插数组U[k]，看看是否有值。如果碰到有冲突的，即一个插槽里存了两个值的时候，则按照哈希冲突一样的处理规则去应对。

2.DIVISION BY PRIME ALGORITHM（质数划分算法）p.s其实就是哈希

所使用的哈希函数为h（k）= k mod m，其中k为键，m为插槽数，h（k）为k / m的余数，由于只需要进行除法操作即可找到插槽，因此速度很快。

但是我们不能为m选择任何值， 具体来说，我们不能选择m为2的幂。如果m = 2 ^ p，则h（k）= k mod m将是k的p个低阶位，如果这些p位的分布不均等，则不会导致均匀散列（uniform hashing）。 因此，最好避免m = 2 ^ p并选择m为素数不太接近2的幂，以便h（k）取决于k的所有位。

除此之外，与大多数机器中的乘法或加法相比，除法运算通常要花费更多的时间。

3.MULTIPLICATION BY ODD NUMBER ALGORITHM（奇数相乘算法）

乘法方法的优点是m的值可以是2的幂。例如，可以取m = 2 ^ r，此方法适用于字长为w位的机器，其中w是2的幂（例如32位或64 位）。

此方法的哈希函数为h（k）=（（A * k）mod 2w）>>（w-r）位。

“ A”是一个乘法常数，它是2 ^ w和2 ^ w-1之间的奇数，不太接近2 ^ w或2 ^ w-1。 A的最佳选择为A≈（√5– 1）/ 2 = 0.6180339887…

此方法通常比除以质数法更快。

4.DOUBLE HASHING ALGORITHM（双重哈希算法）

在该方法中，利用哈希函数对关键字进行哈希处理，该函数假定均匀散列处理将α（负载因子）个条目映射到每个插槽中。
在此方法中，不是将关键字保存在链接列表中，而是使用另一个哈希函数再次对与每个哈希值相对应的关键字进行哈希处理，这有助于直接访问特定插槽的每个元素，而无需顺序遍历整个列表。

通常，可以选择两个哈希函数为h1（k）= k mod m，h2（k）= 1 +（k mod m'）。 选择m为质数，m’小于m。

在我们的例子中，我们选择m = 727和m’= 719，并且使用的哈希函数为h1（k）= k mod m，h2（k）= floor（（k mod m’）/ 8）。

实验仿真结果：

对于α大于64的负载因子，与双散列相比，使用链式分解冲突的质数法需要更多的时间来给出搜索结果。

对于α等于435的负载因子，使用通过链解决冲突时，双哈希技术比顺序搜索查找数据的速度快三倍。

对于α接近64的负载因子，这两种方法大约需要相同的时间来搜索数据。

对于α小于64的负载因子，散列存储区中的顺序搜索比双散列要快。

图3，图4和图5显示了负载因子小于64，α等于64和α大于64的四种算法的比较：

图3

图4

图5

从分析中可以明显看出，在阈值负载因子以下，哈希存储桶中数据的顺序搜索比双哈希方法要快。在阈值之上，双重哈希技术比哈希存储桶中的顺序搜索更快。

于是本文提出一种算法，该算法使用计数器来计算与哈希值相对应的条目数，如果计数小于阈值，则进行顺序搜索以搜索特定条目，否则使用双重哈希。