CALCULATION METHOD, SYSTEM, DEVICE, AND CHIP FOR COMBINED PROGRAMMING ACTION IN SOFTWARE-DEFINED NETWORK

本发明涉及软件定义网络技术领域，尤其涉及软件定义网络组合编程动作计算方法、系统、装置及芯片。

随着信息技术的不断发展，互联网已经成为现代社会不可或缺的信息基础设施，然而，当前网络瘦腰型架构已经无法承载用户越来越多的网络需求，因此，一种新型的网络架构---软件定义网络(Software-defined networking，SDN)受到了广泛地关注，SDN的主要思想是将传统网络设备中的控制逻辑从数据平面进行分离，通过集中化的控制来进行整个网络的管理。

灵活可编程性是SDN提供的重要特性之一，因此，SDN网络编程模型成为一个热点的研究技术领域，其中，模块化组合编程已经成为网络编程模型中最为重要的编程特性。模块化组合编程中，主要分为并行编程和串行编程。并行编程主要是实现多个模块按照各自的逻辑并行处理同一个数据包，而串行处理是指一个数据包经过一个模块逻辑处理之后然后再经过下一个模块处理，在模块化组合编程中，并行模块和串行模块产生的SDN交换机规则需要编译成逻辑上等价的一套规则下发到底层交换机，现有的规则编译算法主要是根据多个子模块的规则表空间的相交情况来产生新的规则集，具体来说：

(1)并行模块编译时，各个模块首先生成各自的规则表，然后，每两个模块按照各自规则表进行叉乘，即将来自两个规则表的每两条规则的匹配域空间进行求交，若求交的结果不为空，则根据该两条规则的交集来生成一条新的规则，如图1-1所示。

(2)串行模块编译时，各个模块仍然是首先生成各自的规则表，然后，让需要先处理数据包的模块所对应的规则表进行预处理，即让规则表的每条规则用其所对应的动作先作用于规则的匹配域，最后再让两个模块的规则表进行叉乘，叉乘形成规则表的过程与并行模块编译类似，如图1-2所示。

现有的SDN组合编程编译算法根据不同子模块的规则空间的相交情况来 构造进行合并后的规则，同时为合并后的规则计算其优先级大小，然而，当前的编译算法针对合并后规则的action list(规则动作链表)的计算只是将子模块的两条规则的action list简单地串接在一起，如图2-1所示。

这种简单串接action list的方法会导致合成后的规则与之前规则的语义不等价或者产生冗余的动作，产生这种问题最根本的原因是多个并行模块可能需要对数据包的包头同时进行读写然后再转发到不同的端口，而这种串接action list的方法使得两段子action list无法形成对数据包独立地操作，因此，从根本上无法保证逻辑上的并行操作，如图2-2所示，规则1的要求是将原数据包的F₂匹配域进行修改后转发到端口1，而规则2是将原数据包修改其匹配域F₁后转发到端口2。但是，合并后的规则转发到端口2的数据包是被同时修改了F₁和F₂，其与原规则2的语义并不等价。

除此之外，虽然这种转接方式可以保证串行方式的模块化编译，但多个子action list可能对数据包的包头重复进行操作，从而产生冗余的动作，如图2-3所示，合并规则的action list中第一个对数据包F₁的修改是冗余的。

发明公开

针对现有技术不足，本发明提出了软件定义网络组合编程动作计算方法、系统、装置及芯片。

本发明提出一种软件定义网络组合编程动作计算方法，包括：

步骤1，将所述软件定义网络中的规则动作链表进行抽象，生成一个或多个节点，所述节点组成节点集合V；

步骤2，向所述节点集合V中的所有所述节点添加有向边，生成有向图，为所述有向图生成汉密尔顿路径，其中所述有向图中每条边的权重之和最小。

所述步骤1包括步骤101，获取原始数据p，为所述原始数据p生成初始节点n₀，其中将所述原始数据p的数据包头部进行复制，并与所述初始节点n₀进行关联，顺序执行所述规则动作链表；

步骤102，若所述规则动作链表中的规则为空，则结束操作，否则执行步骤103；

步骤103，将所述规则动作链表将要执行的动作记为act，若所述act为modify，则修改所述原始数据p的数据包头部，若所述act为forward，则生成 一个新的节点n_i，并将所述原始数据p的数据包头部进行复制，并将所述原始数据p与所述节点n_i进行关联，跳转到步骤102，直到所述规则动作链表中的规则为空。

所述步骤2包括步骤201，若所述节点集合V为空或者只有1个节点，则结束操作，否则执行步骤202；

步骤202，从所述节点集合V中任取1个节点v，将所述节点v与集合中剩余的节点依次进行如下操作，其中所述剩余的节点记为v_i：若所述节点v关联的所述原始数据p的数据包头部通过添加modify action的方式转变成v_i所关联的所述原始数据p的数据包头部，则添加一条有向边，由所述节点v指向所述节点v_i，反之亦然；

步骤203，计算添加的有向边的权重，所述权重的数值为添加的modifyaction的数据，转向步骤201。

每个所述节点为一个<packet，port>对。

本发明还提出一种软件定义网络组合编程动作计算系统，包括：

生成节点集合V模块，用于将所述软件定义网络中的规则动作链表进行抽象，生成一个或多个节点，所述节点组成节点集合V；

生成汉密尔顿路径模块，用于向所述节点集合V中的所有所述节点添加有向边，生成有向图，为所述有向图生成汉密尔顿路径，其中所述有向图中每条边的权重之和最小。

所述生成节点集合V模块包括关联n₀模块，用于获取原始数据p，为所述原始数据p生成初始节点n₀，其中将所述原始数据p的数据包头部进行复制，并与所述初始节点n₀进行关联，顺序执行所述规则动作链表；

判断模块，用于若所述规则动作链表中的规则为空，则结束操作，否则执行关联n_i模块；

关联n_i模块，用于将所述规则动作链表将要执行的动作记为act，若所述act为modify，则修改所述原始数据p的数据包头部，若所述act为forward，则生成一个新的节点n_i，并将所述原始数据p的数据包头部进行复制，并将所述原始数据p与所述节点n_i进行关联，跳转到判断模块，直到所述规则动作链表中的规则为空。

所述生成汉密尔顿路径模块包括判断节点数量模块，用于若所述节点集合V为空或者只有1个节点，则结束操作，否则执行添加有向边模块；

添加有向边模块，用于从所述节点集合V中任取1个节点v，将所述节点v与集合中剩余的节点依次进行如下操作，其中所述剩余的节点记为v_i：若所述节点v关联的所述原始数据p的数据包头部通过添加modify action的方式转变成v_i所关联的所述原始数据p的数据包头部，则添加一条有向边，由所述节点v指向所述节点v_i，反之亦然；

计算权重模块，用于计算添加的有向边的权重，所述权重的数值为添加的modify action的数据，转向判断节点数量模块。

每个所述节点为一个<packet，port>对。

本发明还提出一种软件定义网络组合编程动作计算系统的装置。

本发明还提出一种软件定义网络组合编程动作计算方法的芯片。

附图简要说明

图1-1为并行模块编译流程图；

图1-2为串行模块编译流程图；

图2-1为编译action list流程图；

图2-2为语义不等价图；

图2-3为动作冗余图；

图3为对规则action list的抽象图；

图4为有向图的构建图；

图5为汉密尔顿路径图；

图6为本发明流程图；

图7为本发明示例图。

实现本发明的最佳方式

本发明将action list进行抽象，使其产生多个节点(每个节点为一个<packet，port>对)。假设一个原始数据p命中规则r，命中之后，执行r所关联的action list，记为r.a，具体抽象的过程如下：

步骤一：对应原始数据p，产生初始节点n₀，即将p的数据包头部进行复制，然后关联于n₀，之后顺序执行r.a；

步骤二：若r.a中规则为空，则跳转到步骤四，否则执行步骤三；

步骤三：记r.a将要执行的action为act，若act为modify(即修改数据包指令)，则修改数据包p的数据包头部，若act为forward(即转发数据包指令)，则产生一个新的节点n_i，并数据包p的数据包头部进行复制，并关联于节点n_i。跳转到步骤二；

步骤四：结束。

整个过程，如附图3所示。

多个action list经过上述步骤后，可以产生一个或者多个节点，这些节点能形成一个节点集合V。然后，在这些节点之间添加有向边，最后构成一个有向图，其具体步骤如下所示。

步骤一：若集合V为空或者只有1个节点，则跳转到步骤四，否则进行步骤二；

步骤二：从集合V中任取1个节点v，然后将v与集合中剩余的节点(设为v_i)依次进行如下操作：若v关联的数据包包头能够通过添加modify action(即修改数据包包头指令)的方式转变成v_i所关联的数据包包头，则添加一条有向边，由v指向vi；反之，亦然。跳转到步骤三；

步骤三：计算添加的有向边的权重，大小为添加的modify action的数据，并转向步骤一；

步骤四：结束

整个过程如附图4所示。

经过上述步骤之后，1个有向图可以构成。然后，从关联原始数据包p的节点n0出发，寻找一条哈密顿路径，该路径遍历图中所有的节点，其边的权重之和最小，如附图5所示。

通过找出的一条哈密顿路径，可以重构回一条组合后的action list，这个action list的主要由路径中边上的modify action以及每个节点上派生出的 forward action(即转发数据包指令)按路径的顺序所构成。

综上所述，整个流程图如附图6所示。

具体事例如附图7所示。

本发明还提出一种软件定义网络组合编程动作计算系统，包括：

生成节点集合V模块，用于将所述软件定义网络中的规则动作链表进行抽象，生成一个或多个节点，所述节点组成节点集合V；

生成汉密尔顿路径模块，用于向所述节点集合V中的所有所述节点添加有向边，生成有向图，为所述有向图生成汉密尔顿路径，其中所述有向图中每条边的权重之和最小。

所述生成节点集合V模块包括关联n₀模块，用于获取原始数据p，为所述原始数据p生成初始节点n₀，其中将所述原始数据p的数据包头部进行复制，并与所述初始节点n₀进行关联，顺序执行所述规则动作链表；

判断模块，用于若所述规则动作链表中的规则为空，则结束操作，否则执行关联n_i模块；

关联n_i模块，用于将所述规则动作链表将要执行的动作记为act，若所述act为modify，则修改所述原始数据p的数据包头部，若所述act为forward，则生成一个新的节点n_i，并将所述原始数据p的数据包头部进行复制，并将所述原始数据p与所述节点n_i进行关联，跳转到判断模块，直到所述规则动作链表中的规则为空。

所述生成汉密尔顿路径模块包括判断节点数量模块，用于若所述节点集合V为空或者只有1个节点，则结束操作，否则执行添加有向边模块；

添加有向边模块，用于从所述节点集合V中任取1个节点v，将所述节点v与集合中剩余的节点依次进行如下操作，其中所述剩余的节点记为v_i：若所述节点v关联的所述原始数据p的数据包头部通过添加modify action的方式转变成v_i所关联的所述原始数据p的数据包头部，则添加一条有向边，由所述节点v指向所述节点v_i，反之亦然；

计算权重模块，用于计算添加的有向边的权重，所述权重的数值为添加的modify action的数据，转向判断节点数量模块。

每个所述节点为一个<packet，port>对。

本发明还提出一种包括软件定义网络组合编程动作计算系统的装置。

本发明还提出一种利用软件定义网络组合编程动作计算方法的芯片。

工业应用性

本发明所提出软件定义网络组合编程动作计算方法、系统、装置及芯片，具有如下优点和应用性：

本发明经过一系列的理论建模，能够保证SDN组合编程中合成规则action list的语义等价性，通过在抽象有向图中搜寻一条哈密顿路径来计算出最终合成规则的action list，因此，该action list能保证其action的数目能最小。