支持多核处理器的SDN多级流表并行查找的系统及方法

摘要

本发明公开了一种支持多核处理器的SDN多级流表并行查找的系统及方法，涉及网络技术领域。该方法包括以下步骤：在每一个多级流表的尾端增加一条默认表项；前期的数据流进入多级流表查找时，自动构建一个基于数据流关键字的快表，记录数据流与每一级流表匹配的表项结果，数据流通过快表直接与SDN设备中的多级流表的表项关联起来；后期的数据流从快表中直接获取多级流表中的转发规则信息，直接通过快表找到多级流表中待匹配的表项和执行的动作，将SDN多级流表中进行的多次匹配转化为快表中的单次匹配。本发明能提高查找效率，提高多核处理器在SDN多级流表中的执行效率。

说明书

技术领域

本发明涉及网络技术领域，具体是涉及一种支持多核处理器的 SDN多级流表并行查找的系统及方法。

背景技术

SDN(SoftwareDefinedNetwork，软件定义网络)对现有网络提 出了革命性的改变，将网络设备控制面与数据面分离出来，从而实现 了网络流量的灵活控制，为核心网络提供了统一的管理化平台。SDN 中数据平面的转发区别于传统二层网络基于MAC(MediumAccess Control，介质访问控制)地址查找、三层网络基于IP(InternetProtocol， 网络之间互连的协议)地址查找和MPLS(Multi-ProtocolLabel Switching，多协议标签交换)网络基于标签(Lable)查找的单一方 式，采用以流为单位对数据报文进行分类处理和转发，流表是决定数 据流转发的核心，流表的设计是SDN设备的关键技术。

当前随着SDN的快速发展，流表中需要匹配的字段在不断增加， 数据流在转发过程中需要执行的转发行为也在不断丰富，为了给用户 提供更加灵活多变的配置方式，多级流表已在SDN新的协议规范中 被提出。多级流表的设计需求对SDN传统ASIC(ApplicationSpecific IntegratedCircuit，专用集成电路)硬件平台提出了很多挑战。

现有的ASIC架构芯片(如网络处理器、交换芯片)由于报文解 析、流表查找、逻辑处理都只能依据严格的逻辑模式进行，灵活性较 差，通常只能使用TCAM(TernaryContentAddressableMemory，三 态内容寻址存储器)来实现流表的存储和查找。TCAM专用芯片面积 大、功耗大，价格高昂，如果芯片内置则表项大小很少，外扩成本和 功耗都很大，同时TCAM支持的表项宽度有限，对于当前SDN多关 键字的表项在存储与查找方面都难以满足。ASIC芯片所具有的设计 方式和硬件本身的特性与SDN越来越灵活的功能需求形成明显的矛 盾。

在新的需求下，高性能的多核处理器在数据处理过程中能够实现 并行处理，网络延时小，数据吞吐量大，并且流程设计灵活，硬件约 束小，在当前网络设备中已有着广泛的应用，SDN数据平面的硬件 平台也在向多核处理器方向迁移。在多核处理器的应用过程中，存储 都是SDRAM(SynchronousDynamicRandomAccessMemory，同步 动态随机存取存储器)为主，相对TCAM，多核处理器的优点是大容 量和低价格，表项的格式根据用户需求可以自由设计，没有位宽限制， 可以包含任意多个关键字。表项的查找方式依据表项的存储数据结构 来决定，完全是用软件算法来实现，区别于TCAM的硬件查找，由 此可以看出基于多核平台的SDN设备性能由表项的查找算法决定。

当前基于SDRAM的流表查找主要有线性查找算法、树形查找算 法、几何查找算法和递归查找算法等，但是上述传统算法在多核处理 器中对可并行执行、快速命中等性能方面的要求显得不足，主要表现 在以下方面：

线性查找算法基于线性链表的数据组织方式，流表表项以链表的 方式存储在SDRAM中，数据报文进行表项查找时需要对链表上的表 项逐条匹配。该算法数据结构简单，容易实现，但是在表项存储量较 大的情况下，链表的深度较大，设备端口上通过的每个数据报需要和 链表上的表项进行匹配的平均次数增大，匹配的次数最坏情况下是表 项的整个表项总数，所以在表项较多情况下算法的执行效率较低。在 流表表项数目较多的情况下，单纯依靠线性查找算法是不可取的，线 性查找算法只适用于流表表项较少的应用场合。

树形查找算法、几何查找算法和递归查找算法都是在查找次数上 进行优化和改进，通过数据结构的优化，将表项的存储分散成树或图 的数据结构，避免单纯的线性存储方式。树形查找算法、几何查找算 法和递归查找算法从一定程度上降低了表项的存储深度，减少了平均 查找的次数，优化了查找的性能，但是这三种算法相对于线性查找算 法数据结构组织复杂，在掩码查找上支持的能力较弱，同时在并行查 找和频繁表项更新等环境中算法的运行效率不高，这三种算法一般只 适用于单核处理器和表项结构较为稳定的设备环境中，并且在容量较 大的情况下树或图的层次不可能控制在几层范围内，也很难实现表项 的快速匹配查找。

上述算法分别适合不同的环境，每种算法适用不同的场合，需要 结合具体的环境才能发挥其较好的性能优势，但是在基于多核处理器 的SDN设备中，要求支持多级流表表项的并行查找、大容量表项存 储、频繁表项更新等操作，单纯的应用上述传统算法难以满足实际应 用的需求，并且造成多核处理器处理性能瓶颈，对硬件资源造成浪费。

SDN设备由ASIC芯片向多核处理器平台迁移的过程中，之前的 表项设计方式和基于TCAM的硬件查找方式已经不再具有借鉴意义。 新的多核平台在芯片内部集成的核数多达32个、64个，对算法的并 行执行效率提出了更大的挑战，如果设计的算法难以满足其并行执行 的要求，严重情况下将造成多核处理器平台的技术瓶颈，使得多核芯 片的处理性能难以发挥到应有的水平。

传统的线性查找算法、树形查找算法、几何查找算法和递归查找 算法等实现的多级流表查找算法，由于其数据结构和算法组织方式的 局限性，难以在网络数据设备多核处理器平台下实现大容量的并行快 速查找，给平台造成技术瓶颈，使得多核处理器的并行处理能力不能 完全得以发挥，造成极大的资源浪费。

参见图1所示，传统的多级流表采用完全独立流表依次串联的设 计方案，以三级流表为例，每个数据报文(Packet)依次查找表1(Table 1)、表2(Table2)、表3(Table3)中的表项。每张表中的表项越多， 数据报文需要匹配的平均次数就越多；多级串联的流表数量越多，数 据报文需要匹配的平均次数也越多，可见现有的多级流表算法整体的 平均匹配次数与表项数目和表的大小成正比。无论采用上述那种算 法，算法的性能与流表的级数成反比，每增加一级流表就意味着算法 需要增加更多的匹配次数，花费更多的查找时间。多级流表依次查找， 算法性能表现对SDN流表的级数和表项条目数极为敏感，随着流表 级数和表项数目的增加，算法性能也随之下降。出于对性能的考虑， 传统多级流表的设计往往控制在几层范围内，这在一定程度上限制了 SDN流程设计的灵活性和SDN功能设计的完善性。

发明内容

本发明的目的是为了克服上述背景技术的不足，提供一种支持 多核处理器的SDN多级流表并行查找的系统及方法，对多级流表的 组织结构重新设计，增加基于数据流关键字的快表，将传统SDN多 级流表中进行的多次匹配转化为快表中的单次匹配，能够提高查找效 率，提高多核处理器在SDN多级流表中的执行效率。

本发明提供一种支持多核处理器的SDN多级流表并行查找的系 统，该系统包括快表建立单元、表项设计单元、流表表项删除单元、 流表表项添加单元，其中：

快表建立单元用于：前期的数据流进入多级流表查找时，自动在 多级流表中增设一个基于数据流关键字的快表，记录每一级流表匹配 的表项结果，将各类输入数据包头部的关键字哈希到众多快表上，进 行数据的转发规则获取和转发，优化多核处理器的并行执行；数据流 通过快表直接与SDN设备中的多级流表的表项关联起来；后期的数 据流从快表中直接获取多级流表中的转发规则信息，直接通过快表找 到多级流表中待匹配的表项和执行的动作，将SDN多级流表中进行 的多次匹配转化为快表中的单次匹配；

表项设计单元用于：在多级流表匹配数据流的过程中，在快表表 项中建立数据流的快表信息；在每一个多级流表的尾端增加一条默认 表项；

流表表项删除单元用于：删除流表表项时，让原本关联到默认表 项的快表感知多级流表的表项发生变更，自动解除流表与默认表项的 关联，让快表表项重新去关联没有被删除的流表表项；

流表表项添加单元用于：添加流表表项时，让原本关联到默认表 项的快表感知多级流表的表项发生变更，自动解除流表与默认表项的 关联，重新绑定新增的流表表项。

在上述技术方案的基础上，所述快表的表项成员中包括三个用 于记录数据流匹配的多级表项指针，每个输入的数据报文提取报文头 部的关键字，进行哈希运算，根据哈希值的不同将数据包划分到不同 的快表表项桶Bucket中，每个Bucket中含有8个表项成员，根据表 项中的指针地址找到匹配的表项，执行相关的动作；

所述表项设计单元定义以下名词：

关键字的集合Key＝{k[1],k[2],k[3],…,k[n]}，k[n]属于集合Key， k表示关键字的字段，字段有多个，根据SDN的版本不同有所区别， n是变量，k[n]是一条表项中的关键字字段第n个匹配字段，k[n]是数 据报文中IP头部、用户数据报协议UDP头部信息或传输控制协议 TCP头部信息；

关键字掩码的集合Mask＝{m[1],m[2],m[3],…,m[n]}，m[n]属于集 合Mask，m表示掩码，字段对应的掩码有多个，n是变量，m[n]是 一条表项中的条件字段第n个匹配字段的掩码；

动作的集合Action＝{a[1],a[2],a[3],…,a[i]}，a[i]属于集合Action， a表示执行的动作，执行的动作有多个，i是变量，a[i]是一条流表表 项中第i个需要执行的动作；

流表的集合L[x]＝{r[1],r[2],r[3],…,r[j]}，L是流表的集合，x是变 量，L[x]表示第x张流表；r表示流表的表项，j是变量，r[j]属于流 表集合L[x]，r[j]是流表第x张流表L的第j条表项；

快表的集合F＝{b[1]，b[2],b[3],…,b[n]}，F表示快表的集合，b 表示快表表项，n是变量，b[n]属于快表集合F，b[n]是快表F的第n 条表项，快表表项Bucket的最大值Bucket_Max，表示快表F中容纳 的最大表项数；

网络上所有可能的出现的数据包的集合 P＝{p[1],p[2],p[3],…,p[j]}，P表示数据报文的集合，j是变量，p[j]表 示具有同一特征类型的数据报文；

所述表项设计单元设计快表表项时，为快表表项的每个成员设计 以下数据域：

Valid1：第一有效位，用于表示该条表项的有效性；

Pending：状态位，用于表示该条表项的可用性；

Key：关键字，表项的关键字字段，是该表项的特征值；

Flag：标志位，表示后面数据域三个指针的有效性；

Ptr1：第一指针，用于指向第一级流表表项的指针；

Ptr2：第二指针，用于指向第二级流表表项的指针；

Ptr3：第三指针，用于指向第三级流表表项的指针；

流表的表项包括：

Prev：链表前向指针，用于指向前一个表项结构体的指针；

Prio：优先级字段，表示该表项的优先级高低，数值越大优先级 越高，反之越小；

Key：关键字；

Mask：掩码，表示访问控制列表的表项中的掩码，用于与数据 流信息的条件字段进行与运算；

Ref：引用计数，用于记录当前正在使用该表项的成员个数；

Valid2：第二有效位，用于表示该表项的有效性；

Lock：结构体资源锁，用于多个核间并行执行时，对表项资源的 同步和互斥；

Action：执行动作，流表定义的执行动作；

Next1：第一链表后向指针，用于指向后一个表项结构体的指针， 整个流表表项通过该指针以双链表的方式进行逻辑存储；

流表的表头包括：

Table_Id，表示流表的表号；

Conut，表示当前流表中含有多少个表项；

Lock：结构体资源锁；

Next2：第二链表后向指针，指向流表的第一个表项结构；

所述流表表项的存储结构为链表方式、树形结构或图形结构；

所述快表中一个成员的第一有效位被置为1，表示满足该成员关 键字条件的数据报文，通过该成员直接找到多级流表需要执行的表 项，成员中的标志位＝7，二进制为111，表示在三级流表中分别找到 三个能匹配的表项，指向流表表项的三个指针Ptr1、Ptr2和Ptr3有效；

所述表项设计单元在流表的数据结构设计过程中，在每个流表的 尾端增加一个默认表项，标记为r[d]，其优先级为0，默认表项是在 流表初始化过程中自动加入的，掩码全部成员都为0，各种类型的数 据报文都能匹配上这条默认表项；数据报文在依次匹配流表的表项， 如果前面的表项都不能匹配，则匹配到默认表项。

本发明还提供一种支持多核处理器的SDN多级流表并行查找的 方法，包括以下步骤：

前期的数据流进入多级流表查找时，自动在多级流表中增设一个 基于数据流关键字的快表，记录每一级流表匹配的表项结果，将各类 输入数据包头部的关键字哈希到众多快表上，进行数据的转发规则获 取和转发，优化多核处理器的并行执行；数据流通过快表直接与SDN 设备中的多级流表的表项关联起来；

后期的数据流从快表中直接获取多级流表中的转发规则信息，直 接通过快表找到多级流表中待匹配的表项和执行的动作，将SDN多 级流表中进行的多次匹配转化为快表中的单次匹配；

在多级流表匹配数据流的过程中，在快表表项中建立数据流的快 表信息；在每一个多级流表的尾端增加一条默认表项；

删除流表表项时，让原本关联到默认表项的快表感知多级流表的 表项发生变更，自动解除流表与默认表项的关联，让快表表项重新去 关联没有被删除的流表表项；

添加流表表项时，让原本关联到默认表项的快表感知多级流表的 表项发生变更，自动解除流表与默认表项的关联，重新绑定新增的流 表表项。

在上述技术方案的基础上，所述快表的表项成员中包括三个用 于记录数据流匹配的多级表项指针，每个输入的数据报文提取报文头 部的关键字，进行哈希运算，根据哈希值的不同将数据包划分到不同 的快表表项桶Bucket中，每个Bucket中含有8个表项成员，根据表 项中的指针地址找到匹配的表项，执行相关的动作；

所述表项设计单元定义以下名词：

关键字的集合Key＝{k[1],k[2],k[3],…,k[n]}，k[n]属于集合Key， k表示关键字的字段，字段有多个，根据SDN的版本不同有所区别， n是变量，k[n]是一条表项中的关键字字段第n个匹配字段，k[n]是数 据报文中IP头部、用户数据报协议UDP头部信息或传输控制协议 TCP头部信息；

关键字掩码的集合Mask＝{m[1],m[2],m[3],…,m[n]}，m[n]属于集 合Mask，m表示掩码，字段对应的掩码有多个，n是变量，m[n]是 一条表项中的条件字段第n个匹配字段的掩码；

动作的集合Action＝{a[1],a[2],a[3],…,a[i]}，a[i]属于集合Action， a表示执行的动作，执行的动作有多个，i是变量，a[i]是一条流表表 项中第i个需要执行的动作；

流表的集合L[x]＝{r[1],r[2],r[3],…,r[j]}，L是流表的集合，x是变 量，L[x]表示第x张流表；r表示流表的表项，j是变量，r[j]属于流 表集合L[x]，r[j]是流表第x张流表L的第j条表项；

快表的集合F＝{b[1]，b[2],b[3],…,b[n]}，F表示快表的集合，b 表示快表表项，n是变量，b[n]属于快表集合F，b[n]是快表F的第n 条表项，快表表项Bucket的最大值Bucket_Max，表示快表F中容纳 的最大表项数；

网络上所有可能的出现的数据包的集合 P＝{p[1],p[2],p[3],…,p[j]}，P表示数据报文的集合，j是变量，p[j]表 示具有同一特征类型的数据报文。

所述表项设计单元设计快表表项时，为快表表项的每个成员设计 以下数据域：

Valid1：第一有效位，用于表示该条表项的有效性；

Pending：状态位，用于表示该条表项的可用性；

Key：关键字，表项的关键字字段，是该表项的特征值；

Flag：标志位，表示后面数据域三个指针的有效性；

Ptr1：第一指针，用于指向第一级流表表项的指针；

Ptr2：第二指针，用于指向第二级流表表项的指针；

Ptr3：第三指针，用于指向第三级流表表项的指针；

流表的表项包括：

Prev：链表前向指针，用于指向前一个表项结构体的指针；

Prio：优先级字段，表示该表项的优先级高低，数值越大优先级 越高，反之越小；

Key：关键字；

Mask：掩码，表示访问控制列表的表项中的掩码，用于与数据 流信息的条件字段进行与运算；

Ref：引用计数，用于记录当前正在使用该表项的成员个数；

Valid2：第二有效位，用于表示该表项的有效性；

Lock：结构体资源锁，用于多个核间并行执行时，对表项资源的 同步和互斥；

Action：执行动作，流表定义的执行动作；

Next1：第一链表后向指针，用于指向后一个表项结构体的指针， 整个流表表项通过该指针以双链表的方式进行逻辑存储；

流表的表头包括：

Table_Id，表示流表的表号；

Conut，表示当前流表中含有多少个表项；

Lock：结构体资源锁；

Next2：第二链表后向指针，指向流表的第一个表项结构；

所述流表表项的存储结构为链表方式、树形结构或图形结构。

所述快表中一个成员的第一有效位被置为1，表示满足该成员关 键字条件的数据报文，通过该成员直接找到多级流表需要执行的表 项，成员中的标志位＝7，二进制为111，表示在三级流表中分别找到 三个能匹配的表项，指向流表表项的三个指针Ptr1、Ptr2和Ptr3有效。

所述表项设计单元在流表的数据结构设计过程中，在每个流表的 尾端增加一个默认表项，标记为r[d]，其优先级为0，默认表项是在 流表初始化过程中自动加入的，掩码全部成员都为0，各种类型的数 据报文都能匹配上这条默认表项；数据报文在依次匹配流表的表项， 如果前面的表项都不能匹配，则匹配到默认表项。

在上述技术方案的基础上，所述快表建立单元建立快表时执行 以下步骤：

S101、多核处理器的核从数据报文p[j]中提取报文中对应的条件 字段k[1],k[2],k[3],…,k[n]进行哈希运算，获得32位的哈希值 Hash_Value；

S102、在快表用上面计算的哈希值取余快表表项桶最大值 Bucket_Max，得到b[Hash_Value％Bucket_Max]表项，标记为b[j]，％ 表示取余运算，在b[j]的8个成员中寻找第一有效位为1的成员，根 据表项条件字段k[1],k[2],k[3],…,k[n]与数据报文提取的条件字段匹 配进行匹配，如果没有匹配到，说明该数据流在快表中尚未建立表项 信息，则转到步骤S103，否则转到步骤S108；

S103、建立报文的数据流信息：将数据报文提取全部条件字段 k[1],k[2],k[3],…,k[n]作为流的重要信息填入到空闲快表表项成员的关 键字中，该表项的第一有效位＝0，填写完成关键字后，将该表项的第 一有效位置为1、状态位置为1，表示该表项正在被使用，但是表项 信息尚没有完善，目前不可用；

S104、关联当前快表表项与第一张流表：如果标志位“与”001 为“真”，则直接转到步骤S106，表明快表与第一张流表表项已经关 联；否则执行如下步骤：将数据报文提取的信息关键字与第一张流表 的表项进行逐一匹配，匹配过程是：将数据报文提取的关键字首先同 流表表项r[j]中的掩码进行“与”运算，再将其结果与流表表项r[j] 中的关键字进行“等于”判断，如果结果为真，则表明当前的表项被 匹配上，直接转到步骤S105；否则继续下一条流表表项的匹配，直 到匹配最后一条掩码为全0的默认表项为止；

S105、将快表表项成员中的第一指针Ptr1指向流表表项r[j]，将 表项r[j]结构体的引用计数增加1，并将标志位逻辑运算“或”上001， 此时完成了当前快表表项与第一张流表表项的关联，如果表项r[j]上 动作需要跳转到指定第二张流表，则转到步骤S106；动作需要跳转 到第三张流表，则转到步骤S107；动作需要直接跳出查找，则转到 步骤S108；动作无跳转，则默认转到步骤S106，继续进行流表查找；

S106、关联当前快表表项与第二张流表：同步骤S104，如果标 志位“与”010为“真”，则直接转到步骤S107，表明快表与第二张 流表表项已经关联；否则执行如下步骤：将数据报文提取的信息关键 字与第二张流表的表项进行逐一匹配，匹配完成后同步骤S105，将 快表表项成员中的第二指针Ptr2指向流表表项r[j]，将表项r[j]结构 体的引用计数增加1，并将标志位逻辑运算“或”上010，此时完成 了当前快表快项与第二张流表表项的关联，如果表项r[j]上动作需要 跳转到指定第三张流表，则转到步骤S107；动作需要直接跳出查找， 则转到步骤S108；动作无跳转，则默认转到步骤S107，继续进行流 表查找；

S107、关联当前快表表项与第三张流表：同步骤S104，如果标 志位“与”100为“真”，则直接转到步骤S108，表明快表与第三张 流表表项已经关联；否则执行如下步骤：将数据报文提取的信息关键 字与第三张流表的表项进行逐一匹配，匹配完成后同步骤S105，将 快表表项成员中的第三指针Ptr3指向流表表项r[j]，将表项r[j]结构 体的引用计数增加1，并将标志位逻辑运算“或”上100，此时完成 了当前快表快项与第三张流表表项的关联；

S108、首先检测快表表项成员的第一有效位是否为1，如果不为 1，将其设置为1；检测状态位是否为0，如果不为0，将其设置为0， 至此表明该数据流快表表项信息全部建立完成；

S109、数据报文在快表中匹配上表项成员，并且表项第一有效位 为1，状态位为0，根据成员中的指针，直接找到三张流表表项中匹 配的表项，并找到流表表项中需要执行的动作，动作包含：修改数据 报文头部信息、指定出端口、丢弃、跳转到指定的流表或容许通过； 如果表项第一有效位为1，状态位为1，表明当前快表表项处于在建 过程中，快表与流表关联信息需要进一步完善，返回步骤S104。

在上述技术方案的基础上，如果三张流表上的某一张流表L[x] 上某一条表项r[j]被删除，流表表项删除单元执行以下步骤：

S201、在流表上找到待删除的流表表项r[j]，将表项r[j]从链表中 删除，然后将流表表头中的Count值减1；

S202、将该表项中的第二有效位设置成无效，如果r[j]的引用计 数不大于0，转到步骤S203；否则转到步骤S204；

S203、如果r[j]的引用计数不大于0，说明当前已经没有快表指 向该结构体空间，直接释放表项r[j]结构体内存；

S204、数据报文在使用快表表项成员的过程中，通过指针找流表 的表项r[j]，首先要对表项r[j]的第二有效位进行判断，如果第二有效 位被设置成无效，则表明该访问列表已经被删除，表明需要执行的动 作已经失效，转到步骤S205；

S205、将r[j]中的引用计数减1，如果r[j]的引用计数不大于0， 则直接释放r[j]结构体内存，并且将当前快表表项成员中的对应的标 志位清除，将状态位置为1；如果r[j]的引用计数大于0，后来的数据 报文将重复步骤S204的操作，直到r[j]的引用计数不大于0，内存被 释放为止。

在上述技术方案的基础上，如果三张流表上的某一张流表L[x] 上增加一条表项r[j]，流表表项添加单元执行以下步骤：

S301、在双链表上增加新表项r[j]，表项添加的位置根据优先级 字段比较来确定，要求插入的节点r[j-1]的优先级不低于新表项r[j] 的优先级，完成插入操作后将将流表表头中的Count值加1；

S302、重新删除并添加该流表上从r[j+1]到尾部默认表项之间的 全部表项；

S303、数据报文在使用快表表项成员的过程中，通过指针索引到 流表的表项r[j+1]时，如果发现表项r[j+1]的第二有效位被设置成无 效，则表明该访问列表已经被删除，表明需要执行的动作已经失效， 将快表表项成员中对应的标志位置为0，状态位置为1；

S304、数据报文重新构建快表表项，新建的快表表项成员匹配默 认表项r[d]、优先级较低的r[j+1]表项或新增优先级更高的表项。

与现有技术相比，本发明的优点如下：

(1)传统的算法是：多级流表依次匹配每一级流表表项，从而 获取数据转发规则，与传统的算法相比，本发明对多级流表的组织结 构重新设计，增加基于数据流关键字的快表，前期的数据流在进入多 级流表查找的过程中自动建立快表，数据流通过快表直接与SDN设 备中的多级流表的表项关联起来，在多级流表匹配数据流的过程中， 记录每一级流表匹配的表项结果，从而在快表表项中建立数据流的快 表信息，让后续的数据流从快表中直接获取多级流表中的转发规则信 息，将传统SDN多级流表中原本需要多次匹配表项的设计变更为单 次匹配，实现高速并行查找、多级表项存储，让数据报文能够在有限 的几次匹配中就能够查找到对应的流表表项，并缓解流表级数与查找 性能之间的反比关系，突破SDN设备在多核处理器平台中多级流表 查找上的瓶颈，提高查找效率，从而提高多核处理器在SDN多级流 表中的执行效率。

(2)本发明在每一个多级流表的尾端增加一条默认表项，当添 加流表表项时，主动删除并添加一次该流表上的默认表项，让原本关 联到默认表项的快表感知流表发生变更，自动解除与默认表项的关 联，重新绑定新增的流表表项，在保证算法正确性和及时性的同时， 将快表的震荡减低为最小，因为这对已经绑定非默认表项的快表不会 带来影响，即使在在流表表项频繁发生更新的过程中，依然能够避免 因快表的大面积重构而导致的SDN整体转发性能产生急剧震荡。

(3)本发明中的快表表项设计得比较大，各类输入数据包头部 的关键字(Key)哈希到众多快表上，进行数据的转发规则获取和转 发，优化多核处理器的并行执行，即使多核处理器集中在原本有限的 几张流表和流表表项资源上，能够尽量避免由资源争夺和资源等待等 造成的转发性能下降现象。

附图说明

图1是现有的多级流表的示意图。

图2是本发明实施例中多级流表的结构示意图。

图3是本发明实施例中快表表项成员Entry的数据结构示意图。

图4是本发明实施例中流表表项成员Entry的数据结构示意图。

图5是本发明实施例中流表表头Table_Head的数据结构示意图。

图6是本发明实施例中快表与多级流表之间的结构关系示意图。

具体实施方式

下面结合附图及具体实施例对本发明作进一步的详细描述。

本发明实施例提供一种支持多核处理器的SDN多级流表并行查 找的系统，该系统包括快表建立单元、表项设计单元、流表表项删除 单元、流表表项添加单元，其中：

快表建立单元用于：前期的数据流进入多级流表查找时，自动在 多级流表中增设一个基于数据流关键字的快表，记录每一级流表匹配 的表项结果，将各类输入数据包头部的关键字哈希到众多快表上，进 行数据的转发规则获取和转发，优化多核处理器的并行执行；数据流 通过快表直接与SDN设备中的多级流表的表项关联起来；后期的数 据流从快表中直接获取多级流表中的转发规则信息，直接通过快表找 到多级流表中待匹配的表项和执行的动作，将SDN多级流表中进行 的多次匹配转化为快表中的单次匹配；

表项设计单元用于：在多级流表匹配数据流的过程中，在快表表 项中建立数据流的快表信息；在每一个多级流表的尾端增加一条默认 表项；

流表表项删除单元用于：删除流表表项时，让原本关联到默认表 项的快表感知多级流表的表项发生变更，自动解除流表与默认表项的 关联，让快表表项重新去关联没有被删除的流表表项；

流表表项添加单元用于：添加流表表项时，让原本关联到默认表 项的快表感知多级流表的表项发生变更，自动解除流表与默认表项的 关联，重新绑定新增的流表表项。

本发明实施例还提供一种支持多核处理器的SDN多级流表并行 查找的方法，包括以下步骤：

前期的数据流进入多级流表查找时，自动在多级流表中增设一个 基于数据流关键字的快表，记录每一级流表匹配的表项结果，将各类 输入数据包头部的关键字哈希到众多快表上，进行数据的转发规则获 取和转发，优化多核处理器的并行执行；数据流通过快表直接与SDN 设备中的多级流表的表项关联起来；

后期的数据流从快表中直接获取多级流表中的转发规则信息，直 接通过快表找到多级流表中待匹配的表项和执行的动作，将SDN多 级流表中进行的多次匹配转化为快表中的单次匹配；

在多级流表匹配数据流的过程中，在快表表项中建立数据流的快 表信息；在每一个多级流表的尾端增加一条默认表项；

删除流表表项时，让原本关联到默认表项的快表感知多级流表的 表项发生变更，自动解除流表与默认表项的关联；

添加流表表项时，让原本关联到默认表项的快表感知多级流表的 表项发生变更，自动解除流表与默认表项的关联，重新绑定新增的流 表表项。

流表表项的存储结构可以为链表方式、树形结构或图形结构。

本发明实施例中的多级流表可以是三级流表，也可以是4级、5 级或N级流表，下面以三级流表为例进行说明。

参见图2所示，在多级流表中增设一个基于数据流关键字的Fast Table(快表)，快表表项Entry(成员)中包括三个用于记录数据流 匹配的多级表项指针，每个输入的Packet(数据报文)，提取报文头 部的关键字，进行哈希运算，根据哈希值的不同将数据包划分到不同 的快表表项Bucket(桶)中，由于哈希运算存在冲突的可能性，每个 Bucket中含有8个表项成员，根据表项中的指针地址找到匹配的表 项，执行相关的动作。

为了更好的表达，表项设计单元定义以下名词：

关键字的集合Key＝{k[1],k[2],k[3],…,k[n]}，k[n]属于集合Key， k表示关键字的字段，字段会有很多个，根据SDN的版本不同有所 区别，n是变量，k[n]是一条表项中的关键字字段第n个匹配字段， k[n]通常是数据报文中IP头部、UDP(UserDatagramProtocol，用户 数据报协议)头部信息或TCP(TransmissionControlProtocol，传输 控制协议)头部信息，例如五元组(入接口号、目的Ip地址、源Ip 地址、TCP/UDP目的端口号和源端口号)等，属于MatchFields(流 表匹配域)范畴。

关键字掩码的集合Mask＝{m[1],m[2],m[3],…,m[n]}，m[n]属于集 合Mask，m表示掩码，字段对应的掩码有很多个，n是变量，m[n] 是一条表项中的条件字段第n个匹配字段的掩码。

动作的集合Action＝{a[1],a[2],a[3],…,a[i]}，a[i]属于集合Action， a表示执行的动作，执行的动作可能会有很多个，i是变量，a[i]是一 条流表表项中第i个需要执行的动作，例如：Counters(计数)、 Instructions(指令)、Timeouts(定时)和Cookie(标识)等。

流表的集合L[x]＝{r[1],r[2],r[3],…,r[j]}，L是流表的集合，x是变 量，L[x]表示第x张流表，本发明实施例用三级流表来说明，所以x 的值是1、2或3；r表示流表的表项，j是变量，r[j]属于流表集合L[x]， r[j]是流表第x张流表L的第j条表项。

快表的集合F＝{b[1]，b[2],b[3],…,b[n]}，F表示快表的集合，b 表示快表表项，n是变量，b[n]属于快表集合F，b[n]是快表F的第n 条表项，快表表项Bucket的最大值Bucket_Max，表示快表F中容纳 的最大表项数。

网络上所有可能的出现的数据包的集合 P＝{p[1],p[2],p[3],…,p[j]}，P表示数据报文的集合，j是变量，p[j]表 示具有同一特征类型的数据报文。

参见图3所示，表项设计单元设计快表表项时，为快表表项的每 个成员设计以下数据域：

Valid1：第一有效位，用于表示该条表项的有效性；

Pending：状态位，用于表示该条表项的可用性；

Key：关键字，表项的关键字字段，是该表项的特征值；

Flag：标志位，表示后面数据域三个指针的有效性；

Ptr1：第一指针，用于指向第一级流表表项的指针；

Ptr2：第二指针，用于指向第二级流表表项的指针；

Ptr3：第三指针，用于指向第三级流表表项的指针。

参见图4所示，流表的表项包括：

Prev：链表前向指针，用于指向前一个表项结构体的指针；

Prio：优先级字段，表示该表项的优先级高低，数值越大优先级 越高，反之越小；

Key：关键字，上文已经说明，此处不再赘述；

Mask：掩码，表示访问控制列表的表项中的掩码，用于与数据 流信息的条件字段进行与运算；

Ref：引用计数，用于记录当前正在使用该表项的成员个数；

Valid2：第二有效位，用于表示该表项的有效性；

Lock：结构体资源锁，用于多个核间并行执行时，对表项资源的 同步和互斥；

Action：执行动作，流表定义的执行动作；

Next1：第一链表后向指针，用于指向后一个表项结构体的指针， 整个流表表项通过该指针以双链表的方式进行逻辑存储。

参见图5所示，流表的表头(Table_Head)包括：

Table_Id，表示流表的表号；

Conut，表示当前流表中含有多少个表项；

Lock：结构体资源锁，上文已经说明，此处不再赘述；

Next2：第二链表后向指针，指向流表的第一个表项结构。

参见图6所示，快表中一个成员的第一有效位被置为1，表示满 足该成员关键字条件的数据报文，可以通过该成员直接找到多级流表 需要执行的表项。成员中的标志位＝7(二进制为111)表示在三级流 表中分别找到三个能够匹配的表项，指向流表表项的三个指针Ptr1、 Ptr2和Ptr3有效。

表项设计单元在流表的数据结构设计过程中，在每个流表的尾端 增加一个默认表项，标记为r[d]，其优先级为0，默认表项是在流表 初始化过程中自动加入的，其特殊的地方是：掩码全部成员都为0， 无论什么类型的数据报文都能匹配上这条默认表项。数据报文在依次 匹配流表的表项，如果前面的表项都不能匹配，则匹配到默认表项， 这里增加的这个表项对于下面涉及到的流表的添加与快表的建立有 着密切的关系。

快表建立单元建立快表时，执行以下步骤：

S101、多核处理器的核从数据报文p[j]中提取报文中对应的条件 字段k[1],k[2],k[3],…,k[n]进行哈希运算，获得32位的Hash_Value(哈 希值)。

S102、在快表用上面计算的哈希值取余快表表项桶最大值 (Bucket_Max)，得到b[Hash_Value％Bucket_Max]表项，标记为 b[j]，％表示取余运算，在b[j]的8个成员中寻找第一有效位为1的成 员，根据表项条件字段k[1],k[2],k[3],…,k[n]与数据报文提取的条件字 段匹配进行匹配，如果没有匹配到，说明该数据流在快表中尚未建立 表项信息，则转到步骤S103，否则转到步骤S108。

S103、建立报文的数据流信息：将数据报文提取全部条件字段 k[1],k[2],k[3],…,k[n]作为流的重要信息填入到空闲快表表项成员的关 键字中，该表项的第一有效位＝0，填写完成关键字后，将该表项的第 一有效位置为1、状态位置为1，表示该表项正在被使用，但是表项 信息尚没有完善，目前不可用。

S104、关联当前快表表项与第一张流表：如果标志位“与”001 为“真”，则直接转到步骤S106，表明快表与第一张流表表项已经关 联；否则执行如下步骤：将数据报文提取的信息关键字与第一张流表 的表项进行逐一匹配，匹配过程是：将数据报文提取的关键字首先同 流表表项r[j]中的掩码进行“与”运算，再将其结果与流表表项r[j] 中的关键字进行“等于”判断，如果结果为真，则表明当前的表项被 匹配上，直接转到步骤S105；否则继续下一条流表表项的匹配，直 到匹配最后一条掩码为全0的默认表项为止。

S105、将快表表项成员中的第一指针Ptr1指向流表表项r[j]，将 表项r[j]结构体的引用计数增加1，并将标志位逻辑运算“或”上001， 此时完成了当前快表表项与第一张流表表项的关联，如果表项r[j]上 动作需要跳转到指定第二张流表，则转到步骤S106；动作需要跳转 到第三张流表，则转到步骤S107；动作需要直接跳出查找，则转到 步骤S108；动作无跳转，则默认转到步骤S106，继续进行流表查找。

S106、关联当前快表表项与第二张流表：同步骤S104，如果标 志位“与”010为“真”，则直接转到步骤S107，表明快表与第二张 流表表项已经关联；否则执行如下步骤：将数据报文提取的信息关键 字与第二张流表的表项进行逐一匹配，匹配完成后同步骤S105，将 快表表项成员中的第二指针Ptr2指向流表表项r[j]，将表项r[j]结构 体的引用计数增加1，并将标志位逻辑运算“或”上010，此时完成 了当前快表快项与第二张流表表项的关联，如果表项r[j]上动作需要 跳转到指定第三张流表，则转到步骤S107；动作需要直接跳出查找， 则转到步骤S108；动作无跳转，则默认转到步骤S107，继续进行流 表查找。

S107、关联当前快表表项与第三张流表：同步骤S104，如果标 志位“与”100为“真”，则直接转到步骤S108，表明快表与第三张 流表表项已经关联；否则执行如下步骤：将数据报文提取的信息关键 字与第三张流表的表项进行逐一匹配，匹配完成后同步骤S105，将 快表表项成员中的第三指针Ptr3指向流表表项r[j]，将表项r[j]结构 体的引用计数增加1，并将标志位逻辑运算“或”上100，此时完成 了当前快表快项与第三张流表表项的关联。

S108、首先检测快表表项成员的第一有效位是否为1，如果不为 1，将其设置为1；检测状态位是否为0，如果不为0，将其设置为0， 至此表明该数据流快表表项信息全部建立完成；

S109、数据报文在快表中匹配上表项成员，并且表项第一有效位 为1，状态位为0，根据成员中的指针，直接找到三张流表表项中所 能够匹配的表项，并找到流表表项中需要执行的动作，动作包含：修 改数据报文头部信息、指定出端口、丢弃、跳转到指定的流表或容许 通过等内容。如果表项第一有效位为1，状态位为1，表明当前快表 表项处于在建过程中，快表与流表关联信息需要进一步完善，返回步 骤S104。

如果三张流表上的某一张流表L[x]上某一条表项r[j]被删除，流 表表项删除单元执行以下步骤：

S201、在流表上找到待删除的流表表项r[j]，将表项r[j]从链表中 删除，然后将流表表头中的Count值减1。

S202、删除的表项r[j]不能直接释放内存，因为有可能多个快表 的表项指向了该结构体空间，将该表项中的第二有效位设置成无效， 如果r[j]的引用计数不大于0，转到步骤S203，否则转到步骤S204。

S203、如果r[j]的引用计数不大于0，说明当前已经没有快表指 向该结构体空间，直接释放表项r[j]结构体内存。

S204、数据报文在使用快表表项成员的过程中，通过指针找流表 的表项r[j]，首先要对表项r[j]的第二有效位进行判断，如果第二有效 位被设置成无效，则表明该访问列表已经被删除，表明需要执行的动 作已经失效，转到步骤S205。

S205、将r[j]中的引用计数减1，如果r[j]的引用计数不大于0， 则直接释放r[j]结构体内存，并且将当前快表表项成员中的对应的标 志位清除，将状态位置为1；如果r[j]的引用计数大于0，后来的数据 报文将重复步骤S204的操作，直到r[j]的引用计数不大于0，内存被 释放为止。

如果三张流表上的某一张流表L[x]上增加一条表项r[j]，流表表 项添加单元执行以下步骤：

S301、在双链表上增加新表项r[j]，表项添加的位置根据优先级 字段比较来确定，要求插入的节点r[j-1]的优先级不低于新表项r[j] 的优先级，完成插入操作后将将流表表头中的Count值加1。

S302、重新删除并添加该流表上从r[j+1]到尾部默认表项之间的 全部表项。

S303、数据报文在使用快表表项成员的过程中，通过指针索引到 流表的表项r[j+1]时，如果发现表项r[j+1]的第二有效位被设置成无 效，则表明该访问列表已经被删除，表明需要执行的动作已经失效， 将快表表项成员中对应的标志位置为0，状态位置为1。

S304、数据报文重新构建快表表项，该新建的快表表项成员，原 先在流表L[x]没有表项可匹配，只能匹配默认表项r[d]或优先级较低 的r[j+1]表项，当前存在的可能性是匹配上新增优先级更高的表项。

本发明实施例的原理详细阐述如下：

本发明实施例对多级流表组织结构的重新设计，增加数据流快表 结构和多级流表中的默认表项结构，并增加处理流程和逻辑分析，让 前期的数据流在进入多级流表查找的过程中自动建立快表，让快表关 联到多级流表的表项上，后期的数据流可以直接通过快表找到多级流 表中能够匹配的表项和需要执行的动作，将原本需要在SDN中多级 流表中进行多次匹配转化为在快表中单次匹配，从而提高原有算法整 体的性能。

更为重要的是，通过增加的结构设计和流程设计，能够感知多级 流表的表项发生变更，并及时采取相应的变更动作，实时保证数据流 匹配多级流表的正确性。如果流表表项被删除，设计能够自动解除相 关的快表表项与被删除流表表项直接的关联关系，让快表表项重新去 关联其没有被删除的流表表项；当流表表项增加，设计能够将快表中 前期没有匹配到的流表表项，而默认匹配默认表项的数据流，迁移到 去匹配新增加的流表表项。

本发明实施例中的数据流通过快表与直接与SDN设备中多级流 表之间关联起来，并能够在流表表项发生删除或添加等变更时，自动 解除流表与被删除表项之间的关系或主动去匹配新增加的表项。在保 证算法的正确性和及时性的前提下，绕开了数据报文原本需要依次去 多级流表匹配表项的步骤，将原本需要在多级流表中进行多次匹配转 化为在快表中单次匹配，消减了传统算法平均匹配次数，提高了传统 算法在多级流表上的处理性能。

本领域的技术人员可以对本发明实施例进行各种修改和变型，倘 若这些修改和变型在本发明权利要求及其等同技术的范围之内，则这 些修改和变型也在本发明的保护范围之内。

说明书中未详细描述的内容为本领域技术人员公知的现有技术。