一种分布式的数据平面资源优化方法与系统

1.本发明属于可编程网络领域，特别涉及一种分布式的数据平面资源优化方法与系统。
背景技术：
：：2.相较于传统数据平面，现有的可编程数据平面具有更强的灵活性，提供了抽象的语言框架，简化了有状态的网络功能的开发，是目前被广泛认可的资源优化方案。可编程数据平面可以通过可编程交换机编译器，在可编程交换机上进行程序部署，然而有限的交换机资源严重阻碍了现有技术的发展。3.单台交换机的总内存通常只有几十mb，对于高命中率检测的测量任务，网络管理员需要限制交换机中计数器的数量，使其能够在单台交换机的资源限制下完成部署。这给网络管理员增加了工作的复杂性，同时容易造成计数错误。随着可编程交换机和p4语言的出现，在数据平面同时运行多个p4程序，能够充分利用交换机资源。当前工作也有工作开展了相关工作的研究，但仍存在一定的问题。4.将程序放在可编程网络中执行时，依赖的是可以运行在交换机的p4程序。p4程序是与目标无关的，它是在高度专业化的基于硬件的交换机或软件特定的软件交换机上运行的。p4程序经过编译后，会生成一种中间表示形式ir,它以图的形式表示p4程序。其中节点为匹配动作表(mat)，这是p4程序能够进行成为新的领域特定语言的关键。一个mat中包含匹配字段，用于对数据包头进行匹配，安装动作中定义的操作对匹配结果进行相应操作。在运行时，根据依赖关系和硬件资源的需要，将相应的mat放置在交换机asic流水，执行p4程序定义的测量任务。将mat放置在可编程交换机的过程在本文中，我们关注测量领域的数据平面程序，将网络管理员编写实现的测量任务对应p4程序作为一个任务。5.针对交换机的资源限制问题，现有的方法主要从两个方面进行优化：减少资源占用和分布式方案。speed采用减少数据平面资源冗余的思想，对经过p4前端编译器之生成的中间表示采用合并最长公共子序列的方式来处理。在相同的两个p4程序上，先对两个程序的tdg进行拓扑排序，计算两者的最长公共子序列，以公共子序列作为合并的节点。在分布式部署的研究方面，speed采用了obs思想，简化了程序底层部署的复杂度。6.在减少数据平面程序冗余方面，speed采用合并最长公共子序列(lcs)的方式来处理。在相同的两个p4程序上，speed是先对两个tdg图做拓扑排序，再根据两个拓扑序获得它们的最长公共子序列，以这个子序列为合并的节点。但是一个图在拓扑排序的过程中，有可能会产生多个拓扑序，speed难以考虑多种情况，因此在部分tdg上的合并可能达不到总是最优解的情况。7.在分布式部署的研究中，speed涉及到线性规划部署的问题，其中speed中在将任务部署到真实网络中时采用了obs思想，简化了底层网络部署的复杂度，但是不可避免的忽视了程序之间的依赖，对于这个问题，speed的处理方式是采用插入路由模块携带所有元数据来保证前后两个程序的正常运行，但是这就带来了新的开销和延迟问题。技术实现要素：8.为了克服现有技术中存在的不足，本发明提供了一种分布式的数据平面资源优化方法与系统。充分利用合并算法和拆分算法实现任务资源优化、减少程序的冗余，以达到节省可编程交换机的资源的目的。首先根据输入程序占用stage和可编程交换机固定stage对输入程序分类；接着对资源密集型程序采用拆分算法，对资源稀疏型程序采用合并算；最后利用整型线性规划模型对合并算法和拆分算法获得的子任务集合sst计算程序的最终部署方案。本发明克服了现有技术中难以实现最优程序合并、任务处理时间较长的缺陷，能够在满足任务自身约束、交换机资源约束以及全局约束的前提下，以最小化资源占用stage为目标，保证各可编程交换机的资源分配均衡，完成交换机底层与任务之间的映射关系，提高了任务处理的时间和效果，提高了交换机稀缺的内存资源的利用率。9.为了使本
发明内容表述更加清晰，首先对可编程交换机中的概念进行解释：10.pipeline：可编程交换机的pipeline如图1所示，每条pipeline由多个stage组成，程序放置在交换机后，严格按照顺序从第一个stage开始向后执行。11.stage：每条pipeline具有有限数量的stage，每个stage中具有有限的存储器(sram和tcam)和计算资源。12.本发明的技术方案为：13.一种分布式的数据平面资源优化方法，包括步骤如下：14.步骤1，对输入的程序进行前端编译生成tdg表依赖图，将所述tdg表依赖图加入原始任务集合；同时将所述程序分为资源密集型和资源稀疏型，所述资源密集型程序为占用stage资源超过可编程交换机固定stage的输入程序，所述资源稀疏型程序为占用stage资源未超过可编程交换机固定stage的输入程序；15.步骤2，根据程序类型在对输入程序进行任务资源优化，具体包括：16.对所述资源稀疏型程序使用合并算法：进行多个资源稀疏型程序之间的两两合并，通过最小化节点数目，获得合并后的子任务，将合并后的子任务加入子任务集合sst；17.对所述资源密集型程序使用拆分算法：通过删除所述资源密集型程序的tdg表依赖图中的边，获得stage占用和最小、且各自占用的stage相差最小的拆分后的子任务，将拆分后的子任务加入子任务集合sst；18.步骤3，获得步骤2所述子任务集合sst中各任务在底层网络的最终部署方案。19.进一步的，维护所述原始任务集合和所述子任务集合sst，用于维持输入程序与所述子任务集合sst中程序之间的映射关系、相应的流路径信息、资源占用情况，确保在任务资源优化后，仍能够维持原有的依赖关系。20.进一步的，所述tdg表依赖图具体为：21.所述tdg表依赖图是有向无环图，表示为：g＝(t,e)；22.其中，g表示tdg表依赖图，图的节点t为匹配动作表mat，图的边e为匹配动作表mat之间的依赖关系；每个节点t所表示的匹配动作表mat的属性包括：匹配字段、动作字段、表的大小；每个边e所表示的依赖关系的属性值包括：无依赖、匹配依赖、行为依赖、倒转依赖和接替依赖。23.进一步的，所述合并算法具体包括如下子步骤：24.步骤2.1.1，邻接矩阵d用于描述tdg表依赖图中所有n个节点之间的依赖关系，若d[i,j]＝1表示两节点之间存在依赖路径；若d[i,j]＝0表示两节点之间不存在依赖路径；[0025]通过需要合并的两个资源稀疏型程序的tdg表依赖图ga和gb生成邻接矩阵da和db；且满足条件如下：不同tdg表依赖图中相同的匹配动作表mat所在节点用相同的下标表示；合并后的tdg表依赖图是没有环路的；tdg表依赖图之间的依赖关系保持不变；[0026]步骤2.1.2，合并候选集tp，用于表示多个tdg表依赖图中去重后的所有节点的集合；边集ep满足以下关系：[0027][0028]其中，i、j表示矩阵的下标，即tdg表依赖图中节点的编号；[0029]根据所述合并候选集tp和边集ep构造无向图gp＝(tp,ep)，结合点的权重集w和点的度集，构成加权无向图gu＝(tp,ep,w,d)；[0030]步骤2.1.3，将所述加权无向图gu输入至dtsingle算法和dttwo算法中去除周围节点，获得s1点集；[0031]所述去除的周围节点包括：权重大于它所有相邻节点权重和的单个节点的周围节点、两个节点之间距离为2并且这两个节点的权重和大于周围所有相邻节点权重和的所述两个节点的周围节点；[0032]步骤2.1.4，用处理后获得的所述s1点集在所述加权无向图gu的基础上获得加权无向图g1，表示为g1＝(s1,gu)；[0033]步骤2.1.5，对所述s1点集中的节点进行遍历；[0034]定义st为集合数组，st[i]表示集合中的从第1个点到第i个点并且包含第i个点的最大加权独立集；[0035]定义wt为数组，wt[i]表示集合中从第1个点到第i个点并且包含第i个点的最大加权独立集的权重和；[0036]用bestset表示所求最优的最大加权独立集；bestweight表示所求最优的最大加权独立集的权重和；[0037]令当前节点为u，使集合中从第1个节点到节点u并且包含节点u的最大加权独立集的权重和wt[u]的初值为u的权重w[u]，表示为wt[u]＝w[u]；最大加权独立集st[u]的初值为{u}，表示为st[u]＝st[u]∪{u}；[0038]同时从下标1到i遍历s1点集，遍历至当前节点v，如果将节点u加入节点v的最大加权独立集st[v]后，获得的st[u]集合是独立集，并且wt[u]更大，则将当前节点的最大加权独立集以及最大加权独立集的权重和更新为st[u]和wt[u]；[0039]直至遍历完所述s1点集，获得最大加权独立集st[i]和最大加权独立集的权重和wt[i]；[0040]步骤2.1.6，将所述最大加权独立集st[i]和所述最大加权独立集的权重和wt[i]赋值给所述bestset和所述bestweight，得到最优的最大加权独立集、最优的最大加权独立集的权重和；[0041]步骤2.1.7，定义资源共享集合tshare，用于表示多个tdg表依赖图中重复且能够被用来合并的节点的集合；[0042]输出所述最优的最大加权独立集bestset中的节点，并将所述节点加入资源共享集合tshare，更新tshare，获得合并后子任务的tdg表依赖图gm＝(tm,em)；[0043]其中tm＝tp，em为tshare在遍历ga和gb更新后的依赖关系；[0044]步骤2.1.8，将所述合并后子任务的tdg表依赖图gm加入所述子任务集合sst，完成资源稀疏型程序的合并。[0045]进一步的，所述拆分算法具体包括如下子步骤：[0046]步骤2.2.1，输入待拆分资源密集型程序的tdg表依赖图g＝(t,e)；[0047]步骤2.2.2，初始化两个子图sub1和sub2；初始化两个子图对应的首结点指针firstnode和subnode；初始化stage数量差d；[0048]步骤2.2.3，对于所述待拆分资源密集型程序的tdg表依赖图g中的每一个节点t进行判断：[0049]若两个节点的所述依赖关系的属性值为无依赖，计算所述两个节点之间的边的前后两个子图的stage数量；两个子图的实际数量差dis小于数量差d，则进行更新，具体的更新操作包括：令d＝dis，且使所述subnode指针指向该节点t；[0050]若两个节点的所述依赖关系的属性值不为无依赖，则不执行拆分，继续判断下一个节点，直至遍历完所述待拆分资源密集型程序的tdg表依赖图g中的全部节点；[0051]步骤2.2.4，遍历完成后，判断拆分获得的所述两个子图是否相同；[0052]若所述两个子图不是完全相同的，则将拆分获得的两个子图作为两个子任务加入子任务集合sst，完成资源密集型程序的拆分；[0053]若所述两个子图完全相同，拆分失败，提示程序代码编写存在不合理性。[0054]进一步的，所述部署方案的具体计算过程为：[0055]根据目标函数均衡负载，用于保证所有所述子任务集合sst中任务所占的级数最少，且所占用交换机数量最少，且所占用交换机中资源占用均衡；[0056]所述目标函数的公式如下：[0057][0058][0059]其中，ps表示网络中可编程交换机的集合，j表示ps中的第j台可编程交换机，表示ps中第j台交换机是否被使用，xi,j是表示任务i是否放置在交换机j上的关系变量；[0060]约束条件分析，所述约束条件包括：任务自身约束、交换机资源约束以及全局约束；[0061]任务自身约束：任务i必须放置在其flowpath流经的交换机上，任务自身约束公式如下：[0062][0063]其中，pathi,j表示任务i是否流经可编程交换机j，xi,j是表示任务i是否放置在交换机j上的关系变量；[0064]交换机资源约束：用于保证放置在交换机上的任务所使用的资源必须小于交换机的资源，所述任务所使用的资源包括：tcam资源、sram资源以及stage资源，交换机资源约束的公式如下：[0065][0066][0067][0068]其中，表示任务i需要耗费的tcam资源，表示任务i需要耗费的sram资源，表示任务i需要耗费的stage资源，xi,j是表示任务i是否放置在交换机j上的关系变量；[0069]全局约束：用于保证每台交换机的资源占用趋于均衡，在所有部署任务的交换机中，单个交换机的资源消耗的数量的方差最小；[0070][0071][0072]其中，m表示交换机的数量，n表述任务的数量，表示任务i需要耗费的stage资源，xi,j是表示任务i是否放置在交换机j上的关系变量；[0073]根据所述目标函数、所述约束条件建立整型线性规划模型，获得所述子任务集合sst中各任务在底层网络的最终部署方案。[0074]一种分布式的数据平面资源优化系统，所述系统包括：[0075]分类器：用于对输入的程序进行前端编译生成tdg表依赖图，并进行程序占用资源分析与程序分类；[0076]集成编译器：用于执行所述合并算法或所述拆分算法，对输入程序进行任务资源优化；[0077]整型线性规划模型：整型线性规划模型包括所述目标函数和所述约束条件，用于获得所述子任务集合sst中各任务在底层网络的最终部署方案。[0078]一种分布式的数据平面资源优化系统，所述系统包括：[0079]分类器：用于对输入的程序进行前端编译生成tdg表依赖图，并进行程序占用资源分析与程序分类；[0080]集成编译器：用于执行所述合并算法或所述拆分算法，对输入程序进行任务资源优化；[0081]部署策略模块：用于获得所述子任务集合sst中各任务在底层网络的最终部署方案。[0082]与现有技术相比，本发明的有益效果为：[0083]本发明设计了一种集成在p4c的集成编译器，通过对分类后的资源稀疏型程序、资源密集型程序，有针对性的提出了合并算法、拆分算法，在集成编译器中对程序进行有针对性的任务资源优化。具体来说，集成编译器通过合并算法，能够减少因为程序异构造成的冗余，在程序层面改变资源占用；集成编译器通过程序拆分算法，能够减小程序的资源粒度，提升了程序资源分配的灵活性。[0084]本发明设计了一个全网的程序部署方案，接收经过集成编译器优化的数据平面程序，输入至由目标函数和定义约束条件建立的整型线性规划模型中，实现程序部署方案的计算，从而整合整个数据平面的资源来部署程序，能够高效率利用交换机内存资源，更好的满足可编程数据平面受限的情况。附图说明[0085]图1是本发明说明书中可编程交换机的流水线示意图。[0086]图2是本发明实施例中一种分布式的数据平面资源优化系统流程图。[0087]图3是本发明实验例中合并算法示意图。[0088]图4是本发明实验例中邻接矩阵示意图。[0089]图5是本发明实验例中合并算法结果示意图。[0090]图6是本发明对比例中本发明所提方法与p4visor算法的合并节点效率对比图。[0091]图7是本发明对比例中本发明所提方法与p4visor算法的合并节点执行速度对比图。[0092]图8是本发明对比例中speed合并节点的示例图。[0093]图9是本发明对比例中本发明所提方法与speed算法的合并效果对比图。[0094]图10是本发明对比例中本发明所提方法与speed算法的方差对比图。具体实施方式[0095]为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。[0096]实施例[0097]如图2所示，为一种分布式的数据平面资源优化系统流程图，应用一种分布式的数据平面资源优化系统，实现一种分布式的数据平面资源优化方法；[0098]一种分布式的数据平面资源优化方法，包括步骤如下：[0099]步骤1：对程序进行预处理；[0100]具体来说，将程序输入至分类器，通过前端编译生成表依赖图(tabledependencygraph，tdg)。tdg表依赖图是一个有向无环图g＝(t,e)。节点t表示匹配动作表mat，e表示在匹配动作表mat之间存在的边。在tdg表依赖图中，匹配动作表mat作为图的顶点vt，表之间的依赖关系作为图的边。因此，对于每个节点t，有以下几个属性：匹配字段matchfields、动作字段actionfields、表的大小tablesize；对于每个边e，有以下几个属性：无依赖nodep、匹配依赖matchdep、行为依赖actiondep、倒转依赖reversedep、接替依赖successordep。[0101]对程序占用的资源进行分析，按照其占用stage是否超过可编程交换机固定stage，将输入程序分为资源密集型和资源稀疏型，不同类型的程序在进行资源优化时采用不同的处理算法。[0102]步骤2：通过集成编译器进行任务资源优化；[0103]对于不同的类型采用不同的处理方法，包括合并算法和拆分算法。合并算法针对多个资源稀疏型程序，主要目的是减少程序冗余；拆分算法针对一个资源密集型程序，解决单台交换机资源不足以满足该程序正常运行的程序。[0104]方案1，合并算法：合并是可以完成多个程序之间的合并，以下以两个程序合并为例进行描述。[0105]合并两个p4程序，本质上是对两个由p4程序的控制流图形成的dag有向无环图进行合并，将两个dag图合并为一个加权的dag图。合并的目标是最小化节点数目，将两个dag图合并，并最大化重叠。tdg表依赖图是一种有向无环图。具体流程如下：[0106]首先，邻接矩阵d用于描述tdg表依赖图中所有n个节点之间的依赖关系，若d[i,j]＝1表示两节点之间存在依赖路径；若d[i,j]＝0表示两节点之间不存在依赖路径；根据两个程序的tdg表依赖图ga和gb生成邻接矩阵da和db，用于表述依赖关系，即ga＝(ta,ea)对应的邻接矩阵da，gb＝(tb,eb)对应的邻接矩阵db；且需满足以下条件：在ga和gb中相同的匹配动作表mat所在节点用相同的下标；合并后的tdg表依赖图是没有环路的；且ga和gb的依赖关系保持不变。[0107]其次，合并候选集tp，用于表示多个tdg表依赖图中去重后的所有节点的集合；边集ep满足以下关系：[0108][0109]其中，i、j表示矩阵的下标，即tdg表依赖图中节点的编号；[0110]构造无向图gp＝(tp，ep)，结合点的权重集w和点的度集d，构成加权无向图gu＝(tp,ep,w,d)。[0111]然后，输入无向图gu调用dtsingle算法和dttwo算法，获得s1点集。这个过程中，将以下节点去除：单个节点的权重大于它所有相邻节点的权重和；两个节点之间距离为2并且这两个节点的权重和大于周围所有相邻节点的权重和，将周围的节点去除。[0112]接着，用处理后获得的s1在gu的基础上获得加权无向图g1，表示为g1＝(s1,gu)；[0113]接着，对s1点集中的节点进行遍历；[0114]st是一个集合数组，st[i]表示集合中的从第1个点到第i个点并且包含第i个点的最大加权独立集。wt是一个数组，wt[i]表示集合中从第1个点到第i个点并且包含第i个点的最大加权独立集的权重和。bestset表示所求的最佳最大加权独立集。bestweight表示所求的最佳最大加权独立集的权重和。[0115]令当前的点是u，使集合中从第1个点到节点u并且包含u的最大加权独立集的权重和wt初值为u的权重，st[u]集合初值为{u}。同时从下标1到i遍历s1，当前节点是v，如果将点u加入集合st[v]后集合是独立集，并且wt[u]能更大，那么就更新st[u]和wt[u]。[0116]接着，遍历s1，找最大的wt[i],将对应的wt[i]和st[i]赋值给bestset和bestweight。[0117]而后，定义资源共享集合tshare，用于表示多个tdg表依赖图中重复且能够被用来合并的节点的集合。[0118]输出bestset中的结点，完成合并操作。将bestset节点加入资源共享集合tshare，建立合并后子任务的tdg表依赖图gm＝(tm,em)；其中tm＝tp，em根据tshare遍历ga和gb来更新。[0119]最后，将gm加入子任务集合sst。[0120]方案2，拆分算法：拆分是在减少程序放置粒度的同时，减少设备之间的调度开销，选取恰当的拆分节点与边是至关重要的。将其描述为数学问题进行求解，对于生成的tdg表依赖图，由于边的属性不同，tdg表依赖图可转换为加权有向无环图。在图中选取恰当的边删除，使得得到的两个子图的stage占用和最小且各自占用的stage相差最小。本方案适用于多节点拆分，在此以两节点拆分为例进行描述，具体步骤如下：[0121]首先，待拆分任务的tdg表依赖图g＝(t,e)作为输入。[0122]其次，初始化子图sub1,sub2；初始化子图首结点指针firstnode与subnode；初始化stage数量差d，用于判断sub1,sub2之间stage的实际数量差。[0123]再次，对于g中的每一个节点t，都要进行判断，看节点的依赖关系的属性值t.dep是否为no_dep，如果是，由此计算该边前后两个子图的stage数量，如果两个子图stage的实际数量差dis小于d，则进行更新，具体的更新操作有d＝dis且subnode指向该节点t；[0124]最后，遍历完成后，如果两个子图不是完全相同的，则将子图加入子任务集合sst；否则，拆分失败，提示任务代码编写存在不合理性。[0125]步骤3：在完成程序在编译层面的优化后，通过部署策略模块将分布式部署到底层网络。首先描述如何将程序放到底层网络中，然后通过整型线性规划模型，给出任务部署在真实环境的实现细节。[0126]现有技术中的布局解决方案集中于单台交换机的放置或者不考虑基于测量任务和交换机之间的内在约束；或者考虑了任务约束，但是存在资源分配不均的问题。因此，本发明通过估计测量任务的资源使用情况，进行程序资源的预处理操作，然后通过测量任务信息获得网络内对应的流路径以及映射关系，在全网范围内进行任务布局，以优化全局资源使用。[0127]步骤3.1：在上一步的任务资源优化阶段，同时维护两个数组，数组记录任务与子任务的映射关系、相应的流路径信息、资源占用情况。确保在任务资源优化后，仍能够维持原有的依赖关系。接下来将根据任务自身约束、交换机资源约束以及全局约束将程序部署在全网的交换机上。[0128]步骤3.2：给定获取的子任务集合sst，将其建模为整型线性规划问题(ilp)。[0129]根据目标函数和约束条件建立整型线性规划模型：[0130]步骤3.2.1：交换机具有多种类型的相互依赖的资源，同时也要考虑负载均衡的问题。取极端情况，将所有任务都部署在一台交换机上显然是不可取的。因此，分布式将所有任务所占的级数最少，且所占用交换机数量最少，且所占用交换机中资源占用均衡。构建目标函数如公式(2)和(3)所示：[0131][0132][0133]其中，ps表示网络中可编程交换机的集合，j表示ps中的第j台可编程交换机，表示ps中第j台交换机是否被使用，xi,j任务是否放在交换机j上。[0134]步骤3.2.2：约束条件：[0135](1)任务自身约束，任务i必须放置在其flowpath流经的交换机上。任务自身约束条件如公式(4)所示：[0136][0137]其中，pathi.j表示任务i是否流经交换机j；[0138](2)交换机资源约束，放置在交换机上的任务所使用的资源必须小于交换机的资源(包括tcam、sram以及stage占用)。其中，表示任务i需要耗费的tcam资源，表示任务i需要耗费的sram资源，表示任务i需要耗费的stage资源。交换机资源约束条件如公式(5)、(6)、(7)所示：[0139][0140][0141][0142](3)全局约束：每台交换机的资源占用趋于均衡，在所有部署任务的交换机中，单个交换机的资源消耗的数量的方差最小全局约束条件如公式(8)、(9)所示：[0143][0144][0145]步骤3.2.3：根据上述步骤建立整型线性规划模型，将子任务集合sst输入整型线性规划模型中计算获得各程序的最终部署方案。[0146]实验例[0147]对于给定的3个测量任务p4程序a，b，c。具体步骤如下：[0148]对程序进行预处理：在分类器中对程序进行bmv2前端编译，生成tdg表依赖图；[0149]进行程序资源评估分类，程序a和程序b的资源评估都小于交换机的自身stage，程序c大于交换机的stage。[0150]在本发明的集成编译器中，进行任务资源优化：[0151]方案1：根据上一步的结果，对程序a和程序b采用合并算法进行处理，如图3所示，根据两个程序的tdg表依赖图，ga和gb生成邻接矩阵da和db，用于表述依赖关系。给定tdg表依赖图，将涉及到的所有结点的依赖关系用邻接矩阵d表示，其中如果d[i,j]＝1表示两节点之间存在依赖路径；否则不存在。[0152]即ga＝(ta,ea)对应的邻接矩阵da，gb＝(tb,eb)对应的邻接矩阵db，需满足以下条件：在ga和gb中相同的匹配动作表mat用相同的下标表示；合并后的tdg表依赖图是没有环路的；且ga和gb的依赖关系保持不变。[0153]定义合并候选集tp，包含ga和gb中所有不重复的节点；定义边集ep，需满足公式(1)所示关系：[0154][0155]其中，i、j表示矩阵的下标，即tdg表依赖图中节点的编号；[0156]构造无向图gp＝(tp，ep)，图4为gp的邻接矩阵。将边的依赖关系的类型作为边的权值，结合点的权重集w和点的度集d，构成加权无向图gu＝(tp,ep,w,d)。[0157]输入无向图gu调用dtsingle和dttwo算法，获得s1点集。这个过程中，将以下节点去除：单个节点的权重大于它所有相邻节点的权重和；两个节点之间距离为2并且这两个节点的权重和大于周围所有相邻节点的权重和，将周围的节点去除。[0158]用处理后获得的所述s1点集在所述加权无向图gu的基础上获得加权无向图g1，表示为g1＝(s1,gu)。[0159]st是一个集合数组，st[i]表示集合中的从第1个点到第i个点并且包含第i个点的最大加权独立集。wt是一个数组，wt[i]表示集合中从第1个点到第i个点并且包含第i个点的最大加权独立集的权重和。bestset表示所求的最大加权独立集。bestweight表示所求的最大加权独立集的权重和。[0160]对s1中的节点进行遍历，令当前节点是u。使集合中从第1个节点到节点u并且包含u的最大加权独立集的权重和wt初值为u的权重，st[u]集合初值为{u}。同时从下标1到i遍历s1，当前节点是v，如果将点u加入集合st[v]后集合是独立集，并且wt[u]能更大，那么就更新st[u]和wt[u]。[0161]遍历s1，找最大的wt[i],将对应的wt[i]和st[i]赋值给bestset和bestweight。在本实验例中bestset为{0}。[0162]输出bestset的结点，完成合并操作。将bestset节点加入资源共享集合tshare，建立合并后的图gm＝(tm，em)，其中tm＝tp，em根据tshare来遍历ga和gb来更新，形成合并后任务的tdg表依赖图。合并后效果如图5所示：[0163]将gm加入子任务集合sst。[0164]方案2：对程序c进行拆分。[0165]待拆分任务的tdg表依赖图，g＝(t,e)作为输入。[0166]初始化子图集合sub1，sub2；初始化子图首结点指针firstnode与subnode；初始化数量差d为该图的stage。[0167]对于g中的每一个节点t，都要进行判断，看节点的依赖关系的属性值t.dep是否为no_dep，如果是，由此计算该边前后两个子图的stage数量，如果两个子图的数量差dis小于d，则进行更新，具体的更新操作有d＝dis且subnode指向该节点t；[0168]遍历完成后，程序c拆分获得的两个子图不是完全相同的，则将子图加入子任务集合sst。[0169]通过合并或者拆分方案处理多个程序，最终生成子任务集合sst，根据部署策略模块中设定好的目标函数和约束函数，将子任务集合sst传入整型线性规划模型，同时传入底层网络的拓扑，来计算获得最终部署方案。[0170]对比例[0171]在同等的合并效果下，本发明所提方法相比p4visor可以花费更少的时间实现合并操作，在速度上提升两个数量级，如图6、图7所示，在图中可以看出在合并节点效率差不多的情况下，本发明所提方法的执行速度要比p4visor快得多，这是因为p4visor采用启发式算法，在节点选取上比较耗时。[0172]speed合并节点的示例如图3所示，图3(a)是和图3(b)分别是两个tdg图，他们每个节点都是一一对应可合并的，图3(a)的拓扑序是1324，而图3(b)的拓扑序是4321或者4231，如果speed把4321作为图3(b)的拓扑序的话，那么合并的节点数就是1，但是最大的合并的节点数应该是2。在该例中，有两个处于同等地位的节点(bc)，该序列应该考虑2！种情况，而不是仅考虑单一情况。同理，若存在n个地位同等的结点，则应考虑n！种情况，找到最优解则需要额外花费o(n！)的时间复杂度。[0173]在与speed合并节点的数目比较中，本发明有着更好的表现效果，合并节点比speed提升58.64％，对于减少程序冗余效果更好，对比结果如图9所示。[0174]在全网布局中，本发明的资源利用率高于同类型部署方案。采用全局网络中交换机资源使用方差作为评价指标，本发明所提方法与speed进行比较，发现本发明所提方法的方差比其他方法小5倍，很好的实现资源均衡。证明本发明所提方法能够在分布式部署时资源使用均衡，方差对比结果如图10所示。[0175]本发明采用了具体个例对本发明的原理及实施方案进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处。综上所述，本说明书内容不应理解为对本发明的限制。当前第1页12当前第1页12
技术特征：
1.一种分布式的数据平面资源优化方法，其特征在于，包括步骤如下：步骤1，对输入的程序进行前端编译生成tdg表依赖图，将所述tdg表依赖图加入原始任务集合；同时将所述程序分为资源密集型和资源稀疏型，所述资源密集型程序为占用stage资源超过可编程交换机固定stage的输入程序，所述资源稀疏型程序为占用stage资源未超过可编程交换机固定stage的输入程序；步骤2，根据程序类型对输入程序进行任务资源优化，具体包括：对所述资源稀疏型程序使用合并算法：进行多个资源稀疏型程序之间的两两合并，通过最小化节点数目，获得合并后的子任务，将合并后的子任务加入子任务集合sst；对所述资源密集型程序使用拆分算法：通过删除所述资源密集型程序的tdg表依赖图中的边，获得stage占用和最小、且各自占用的stage相差最小的拆分后的子任务，将拆分后的子任务加入子任务集合sst；步骤3，获得步骤2所述子任务集合sst中各任务在底层网络的最终部署方案。2.根据权利要求1所述一种分布式的数据平面资源优化方法，其特征在于，维护所述原始任务集合和所述子任务集合sst，用于维持输入程序与所述子任务集合sst中程序之间的映射关系、相应的流路径信息、资源占用情况，确保在任务资源优化后，仍能够维持原有的依赖关系。3.根据权利要求1所述一种分布式的数据平面资源优化方法，其特征在于，所述tdg表依赖图具体为：所述tdg表依赖图是有向无环图，表示为：g＝(t,e)；其中，g表示tdg表依赖图，图的节点t表示匹配动作表mat，图的边e为匹配动作表mat之间的依赖关系；每个节点t所表示的匹配动作表mat的属性包括：匹配字段、动作字段、表的大小；每个边e所表示的依赖关系的属性值包括：无依赖、匹配依赖、行为依赖、倒转依赖和接替依赖。4.根据权利要求3所述一种分布式的数据平面资源优化方法，其特征在于，所述合并算法具体包括如下子步骤：步骤2.1.1，邻接矩阵d用于描述tdg表依赖图中所有n个节点之间的依赖关系，若d[i,j]＝1表示两节点之间存在依赖路径；若d[i,j]＝0表示两节点之间不存在依赖路径；通过需要合并的两个资源稀疏型程序的tdg表依赖图g
a
和g
b
生成邻接矩阵d
a
和d
b
；且满足条件如下：不同tdg表依赖图中相同的匹配动作表mat所在节点用相同的下标表示；合并后的tdg表依赖图是没有环路的；tdg表依赖图之间的依赖关系保持不变；步骤2.1.2，合并候选集t
p
，用于表示多个tdg表依赖图中去重后的所有节点的集合；边集e
p
满足以下关系：其中，i、j表示矩阵的下标，即tdg表依赖图中节点的编号；根据所述合并候选集t
p
和边集e
p
构造无向图g
p
＝(t
p
,e
p
)，结合点的权重集w和点的度集d，构成加权无向图g
u
＝(t
p
,e
p
,w,d)；步骤2.1.3，将所述加权无向图g
u
输入至dtsingle算法和dttwo算法中去除周围节点，获
得s1点集；所述去除的周围节点包括：权重大于它所有相邻节点权重和的单个节点的周围节点、两个节点之间距离为2并且这两个节点的权重和大于周围所有相邻节点权重和的所述两个节点的周围节点；步骤2.1.4，用处理后获得的所述s1点集在所述加权无向图g
u
的基础上获得加权无向图g1，表示为g1＝(s1,g
u
)；步骤2.1.5，对所述s1点集中的节点进行遍历；定义st为集合数组，st[i]表示集合中的从第1个点到第i个点并且包含第i个点的最大加权独立集；定义wt为数组，wt[i]表示集合中从第1个点到第i个点并且包含第i个点的最大加权独立集的权重和；用bestset表示所求最优的最大加权独立集；bestweight表示所求最优的最大加权独立集的权重和；令当前节点为u，使集合中从第1个节点到节点u并且包含节点u的最大加权独立集的权重和wt[u]的初值为u的权重w[u]，表示为wt[u]＝w[u]；最大加权独立集st[u]的初值为{u}，表示为st[u]＝st[u]∪{u}；同时从下标1到i遍历s1点集，遍历至当前节点v，如果将节点u加入节点v的最大加权独立集st[v]后，获得的st[u]集合是独立集，并且wt[u]更大，则将当前节点的最大加权独立集以及最大加权独立集的权重和更新为st[u]和wt[u]；直至遍历完所述s1点集，获得最大加权独立集st[i]和最大加权独立集的权重和wt[i]；步骤2.1.6，将所述最大加权独立集st[i]和所述最大加权独立集的权重和wt[i]赋值给所述bestset和所述bestweight，得到最优的最大加权独立集、最优的最大加权独立集的权重和；步骤2.1.7，定义资源共享集合t
share
，用于表示多个tdg表依赖图中重复且能够被用来合并的节点的集合；输出所述最优的最大加权独立集bestset中的节点，并将所述节点加入资源共享集合t
share
，更新t
share
，获得合并后子任务的tdg表依赖图g
m
＝(t
m
,e
m
)；其中t
m
＝t
p
，e
m
为t
share
在遍历g
a
和g
b
更新后的依赖关系；步骤2.1.8，将所述合并后子任务的tdg表依赖图g
m
加入所述子任务集合sst，完成资源稀疏型程序的合并。5.根据权利要求3所述一种分布式的数据平面资源优化方法，其特征在于，所述拆分算法具体包括如下子步骤：步骤2.2.1，输入待拆分资源密集型程序的tdg表依赖图g＝(t,e)；步骤2.2.2，初始化两个子图sub1和sub2；初始化两个子图对应的首结点指针firstnode和subnode；初始化stage数量差d；步骤2.2.3，对于所述待拆分资源密集型程序的tdg表依赖图g中的每一个节点t进行判断：若两个节点的所述依赖关系的属性值为无依赖，计算所述两个节点所夹边的前后两个
子图的stage数量；两个子图的实际stage数量差dis小于数量差d，则进行更新，具体的更新操作包括：令d＝dis，且使所述subnode指针指向该节点t；若两个节点的依赖关系的属性值不为无依赖，则不执行拆分，继续判断下一个节点，直至遍历完所述待拆分资源密集型程序的tdg表依赖图g中的全部节点；步骤2.2.4，遍历完成后，判断拆分获得的所述两个子图是否相同；若所述两个子图不是完全相同的，则将拆分获得的两个子图作为两个子任务加入子任务集合sst，完成所述资源密集型程序的拆分；若所述两个子图完全相同，拆分失败，提示程序代码编写存在不合理性。6.根据权利要求1所述一种分布式的数据平面资源优化方法，其特征在于，所述部署方案的具体计算过程为：根据目标函数均衡负载，用于保证所有所述子任务集合sst中任务所占的级数最少，且所占用交换机数量最少，且所占用交换机中资源占用均衡；所述目标函数的公式如下：所述目标函数的公式如下：其中，ps表示网络中可编程交换机的集合，j表示ps中的第j台可编程交换机，表示ps中第j台交换机是否被使用，x
i,j
是表示任务i是否放置在交换机j上的关系变量；约束条件分析，所述约束条件包括：任务自身约束、交换机资源约束以及全局约束；任务自身约束：任务i必须放置在其flowpath流经的交换机上，任务自身约束公式如下：其中，path
i.j
表示任务i是否流经可编程交换机j，x
i,j
是表示任务i是否放置在交换机j上的关系变量；交换机资源约束：用于保证放置在交换机上的任务所使用的资源必须小于交换机的资源，所述任务所使用的资源包括：tcam资源、sram资源以及stage资源，交换机资源约束的公式如下：式如下：式如下：其中，表示任务i需要耗费的tcam资源，表示任务i需要耗费的sram资源，表示任务i需要耗费的stage资源，x
i,j
是表示任务i是否放置在交换机j上的关系变量；全局约束：用于保证每台交换机的资源占用趋于均衡，在所有部署任务的交换机中，单
个交换机的资源消耗的数量的方差最小；个交换机的资源消耗的数量的方差最小；其中，m表示交换机的数量，n表述任务的数量，表示任务i需要耗费的stage资源，x
i,j
是表示任务i是否放置在交换机j上的关系变量；根据所述目标函数、所述约束条件建立整型线性规划模型，获得所述子任务集合sst中各任务在底层网络的最终部署方案。7.一种分布式的数据平面资源优化系统，其特征在于，所述系统包括：分类器：用于对输入的程序进行前端编译生成tdg表依赖图，并进行程序占用资源分析与程序分类；集成编译器：用于执行所述合并算法或所述拆分算法，对输入程序进行任务资源优化；部署策略模块：用于获得所述子任务集合sst中各任务在底层网络的最终部署方案。

技术总结
本发明公开了一种分布式的数据平面资源优化方法与系统，充分利用合并算法和拆分算法来优化数据平面程序资源，解决可编程网络下交换机的资源限制问题。首先对输入程序进行分类，接着针对资源稀疏型程序使用合并算法，对资源密集型程序使用拆分算法，由合并算法和拆分算法获得子任务集合，最后获得子任务集合中各任务在底层网络的部署方案。相比于现有技术本发明能够提升程序合并的速度以及效果、有效减少程序冗余，拆分程序减少程序放置粒度、减少设备之间的调度开销，同时能够提供资源利用率更高的部署方案，证明了一种分布式的数据平面资源优化方法与系统的实用性。面资源优化方法与系统的实用性。面资源优化方法与系统的实用性。


技术研发人员：李福亮 贾星薪 陈松林 王兴伟
受保护的技术使用者：东北大学
技术研发日：2023.04.07
技术公布日：2023/9/22