软件定义网络中的中间盒调度方法及系统

摘要

本发明公开了一种软件定义网络中的中间盒调度方法及系统，该方法包括如下步骤：获取流的列表，所述中间盒用于对流进行相应的处理；获取每种中间盒的需求数目n；获取网络，所述网络上分布着资源池；维护一个分数表，分数表记载着所有中间盒在每个资源池的得分，第i个资源池p

说明书

【技术领域】

本发明涉及计算机网络领域，具体涉及软件定义网络中的中间盒调度方法及系统。

【背景技术】

随着互联网的飞速发展，网络管理与控制逐渐成为制约其发展的重大挑战。中间盒 (Middlebox)是进行复杂包处理的专用网络管控设备，包括代理服务器(Proxy)、深 度包检测(IDS)设备、负载均衡器(Load Balancer)、专用防火墙(Fire Wall)等。然 而在传统网络中，这些设备的配置和管理是十分复杂的工作，因为不同的流的Middlebox 的处理序列(service chain)，配置要保证包的处理遵循相应的Middlebox序列；不同因 为这些Middlebox的配置可能有一定的关联，附图1显示了一种Middlebox处理相关引 起的问题。根据图中的网络策略，H1和H2要先经过代理服务器，然后经过防火墙。 但是经过代理服务器后，来自H1和H2的网络包的源地址已经发生了改变。但是，根 据网络的配置策略，后面的防火墙可能恰恰需要网络包的源地址信息，而不是被代理服 务器修改后的地址。在传统的网络里，这样的策略是在当前拓扑下是无法实现的。相反 的，管理人员只能通过笨拙地调整Middlebox的物理位置来实现相应的功能。另外，不 同厂家的Middlebox的配置命令和配置参数可能不同，不同类型的Middlebox的配置方 式又不一样。复杂的命令和配置参数对网络管理人员提出了很高的要求，也增大了网络 管理人员配置错误的概率。这使得网络的可靠性大大降低。

软件定义网络，是全新的网络架构。不同于传统的互联网络，软件定义网络分离了 控制层面和数据层面，交换机去除了复杂的分布式的控制逻辑，全部的控制逻辑都集中 在控制器里。在传统的TCP/IP网络中，转发逻辑的控制是分散在各个路由器中的。 路由器通过相互发送路由信息来获取全局拓扑，运行分布式的路由算法。这样的网络结 构存在很多问题，如网络发生故障后，某条链路断掉，但是周围的很多路由器不能迅速 感知这些信息，仍然维护者一个错误的拓扑。在这个错误的拓扑上运行路由算法，可能 计算得到不可行的路由条目。

附图2是一个软件定义网络的示例图。软件定义网络有控制器(Controller)和交换 机(Switch)组成，每个交换机都直接和控制器相连(或者逻辑上直接相连)。控制器 通过这条链路获取整个网络拓扑和各个交换机的状态，然后在这些信息的基础上计算相 关的路由策略。路由策略计算后下发交换机(成为流表)，交换机根据这些策略(流表) 进行包的转发。在软件定义网络中，控制器具有全局的视角，可以对所有交换机进行控 制，避免了传统的分布式的控制方法带来的问题，增加了网络的可控制性和可编程性。

作为一个创新的网络架构，软件定义网络已经被用于网络资源管理中，并带来了全 新的管理效率。之前的研究网络管理人员可以利用软件定义网络来简化Middlebox的配 置。在传统的网络里面，Middlebox的管理是一件非常困难和有挑战性的工作，因为 Middlebox本身的复杂性。随着各种各样、越来越多的Middlebox被部署到网络里面， 通过网络管理员人为地手工配置Middlebox变得非常困难，而且容易出错。在软件定义 网络中，通过扩展南向接口(如Openflow协议)，让软件定义网络可以同时管理交换机 和Middlebox。这样，一方面，控制器可以维护整个网络中所有设备(包括交换机和 Middlebox)的各种信息和状态；另一方面，由控制器去管理Middlebox，配置具体的参 数，可以简化网络管理人员对Middlebox的控制，然后只需要简单地在控制器里定义相 关的管理算法，就可以轻松地管理复杂的Middlebox。

把软件定义网络扩展到管理Middlebox，软件定义网络可以在控制器里统一管理 Middlebox的状态和配置策略，这样，对于相干或者相互关联的Middlebox策略，控制 器可以进行统一的配置，会让不同的Middlebox互相协作，共同达到配置目的。另一方 面，管理人员通过控制器间接的和Middlebox交互，免去了各种各样的Middlebox的负 载配置方法和参数，只需要宏观的设置一些策略就可以自动生成复杂的配置策略。相对 于手工配置和记忆这些各式各样的复杂策略，这样出粗的概率更小，整个网络的稳定更 强，而且通过一些自动验证技术，网络的可靠性更高。附图3是软件定义网络挂你 Middlebox的架构图。软件定义网络通过扩展openflow协议管理Middlebox的状态、进 行相应的配置。在这种结构下，控制器具有整个网络的全部Middlebox的信息，可以正 确地处理Middlebox的序列问题，也可以处理Middlebox之间的关联问题。原本复杂的 Middlebox配置命令可以封装在扩展协议当中，这降低了人为记忆配置的错误率。

在当今的互联网中，软件定义网络(Software-Defined Network，SDN)和网络功能 虚拟化技术(Network Function Virtualization，NFV)对现有的网络架构产生了巨大的影 响，这种影响在未来数十年将越来越明显。越来越多的企业和组织将自己的基础IT服 务迁移到云计算平台，与此同时，云环境中Middlebox部署和调度成为越来越重要的课 题。在云环境中部署物理的Middlebox是很不现实的，而且成本巨大。因此，越来越多 的云计算平台引入网络虚拟化技术，来构建高扩展性和灵活性的网络。在这种新的环境 下，采用网络功能虚拟化技术，部署软件Middlebox进行相关的网络处理，更加符合用 户的需求。软件Middlebox可以动态的开关和迁移，一方面极大地提高了云计算环境的 灵活性，另一方面为Middlebox的部署和管理提出了新的挑战。

在网络虚拟化的环境下，软件Middlebox可以根据当前流量动态地开关和迁移。而 传统的静态的物理Middlebox不能通过调整位置来动态地服务动态的流量。所以传统网 络经常发生Middlebox负载不均的情况——有的Middlebox比较空闲，有的Middlebox 负载太重。这降低了整个网络的效率。有的网络采用负载均衡的技术，但是传统网络实 现负载均衡非常困难，甚至需要额外的硬件和复杂的配置。

在软件定网络中有相应的比较好的负载均衡的解决方案。但是这些负载均衡方案没 有考虑到包的延迟，如果把包转发到过远的Middlebox可能会增大包的延迟。附图4就 是一个负载均衡带来额外延迟的例子。图中，从客户机0到客户机1的包需要先经过防 火墙处理。拓扑中有a、b两个防火墙可供选择，防火墙a处于空闲状态，处理包的时 间是1ms，防火墙b处于过载状态，处理包的时间是10ms。根据简单的负载均衡策略， 从客户机0到客户机1的包会先转发到防火墙a处理，然后再向客户机1转发。但是这 种策略下，包的全部延迟是61ms。如果仍然把包交给防火墙b来处理，整体的延迟只 有35ms。在这个例子中，为了考虑防火墙的负载均衡，最后反而增加了包的延迟，这 反映了传统的负载均衡存在的问题。

软件的Middlebox相较于传统的Middlebox，有较强的灵活性。软件的Middlebox 的位置不是固定的，可以根据流量的动态变化进行动态的部署。对于这样环境下的 Middlebox，在管理的过程中要考虑Middlebox的动态性。而传统的静态的Middlebox， 因为物理位置是固定的，配置方法甚至可以采用静态的配置策略。但是这样的简单的管 理方法是不适合于动态特性的Middlebox的。对于软件的Middlebox，要考虑Middlebox 的动态部署和调度。

在软件定义网络和网络功能虚拟化的环境下，要实现动态的Middlebox部署和调度 方案，要具体地解决两个问题：

1)动态地根据流量的分布部署Middlebox，把Middlebox尽可能的部署到需求比较 大的位置。要根据网络流量的分布和具体的需求，把Middlebox动态地开关和迁移，让 Middlebox和流量需求比较大的客户机放在比较近的地方。这样动态地部署，也充分利 用了软件Middlebox灵活迁移的特性，体现了软件定义网络和网络功能虚拟化环境下 Middlebox部署的优越性。

2)给定一个具体的Middlebox部署方案，根据流的分布和需求，并考虑Middlebox 的处理能力，将流分配给Middlebox。根据流量的分布和需求计算了合适的Middlebox 部署方案后，要在这个方案的基础上进行流的调度，每个流应该分配到哪个具体的 Middlebox上进行处理，是这个阶段要解决的问题。对于流的分配问题，既要考虑到 Middlebox的负载均衡问题，让Middlebox的处理负载尽可能地平均，又要考虑到 Middlebox距离客户机的距离问题，尽可能让客户机把包转发到距离自己较近的 Middlebox那里去处理。考虑到整个Middlebox处理序列，这个问题更加复杂。当网络 包从序列中上个Middlebox转发到下个Middlebox时，需要考虑整个序列流程中延迟的 和，需要找到一个整体延迟较优或最优的方案。在这个问题环境下，简单地离客户机最 近并不一定能得到较好的延迟效果。

在网络功能虚拟化的概念出现之前，Middlebox调度方案大多数都是针对硬件 Middlebox的，在这样的环境中，Middlebox的位置是固定的，不能根据流量的动态变 化动态布置。所以在之前的大多数方案，没有解决第一个问题。

另外对于第二个问题，在传统网络中是采用静态配置的方法，不能应对动态变化的 流；在一些软件定义网络中，有人尝试采用简单的负载均衡方法，这样的方法虽然能平 均Middlebox的负载，但是有的时候会增加流的延迟。如附图4中提到的例子，只考虑 简单的负载均衡可能反而会增大网络包的延迟。

【发明内容】

为了克服现有技术的不足，本发明提供了一种软件定义网络中的中间盒调度方法及 系统，使得中间盒的部署更加合理，进一步使流的调度更加合理。

一种软件定义网络中的中间盒调度方法，包括如下步骤：

1)获取流的列表，所述流的列表含有每条流的源点、目的点、依次经过的中间盒 的信息，所述中间盒用于对流进行相应的处理；

2)获取每种中间盒的需求数目n；

3)获取网络，所述网络上分布着资源池，所述资源池运行至少一个中间盒；

4)维护一个分数表，分数表记载着所有中间盒在每个资源池的得分，第i个资源 池p_i的第x类中间盒MB_x用<p_i,MB_x>表示；

5)对每条流到达可能的资源池经过的最短路径中经过的中间盒进行打分，其中当 前中间盒的得分与当前流的当前起点至当前中间盒的距离反相关，对每个中间盒 <p_i,MB_x>每次获得的分数进行累加；

6)根据每个中间盒<p_i,MB_x>的总分从大到小进行排序，选取在第x类中间盒MB_x中相对排名前n名的中间盒MB_x作为处理流的中间盒。

在一个实施例中，还包括如下步骤：

在所述流中，获取经过中间盒个数最多的最长流，其中所述最长流经过的中间盒个 数为K；

通过如下方法对中间盒进行打分：

对流进行K轮打分：

第一轮打分：对每条流从源点到到达的第一个可能的中间盒进行打分，然后对每个 中间盒<p_i,MB_x>的得分进行累加；对每个中间盒<p_i,MB_x>的总分从大到小进行排序，选 取在第x类中间盒MB_x中相对排名前n名的中间盒MB_x作为处理流的临时中间盒；

第m轮打分：对每条流从第m-1个中间盒到达的第m个可能的中间盒进行打分， 然后对每个中间盒<p_i,MB_x>的得分进行累加；对每个中间盒<p_i,MB_x>的总分从大到小进 行排序，选取在第x类中间盒MB_x中相对排名前n名的中间盒MB_x作为处理流的临时 中间盒；其中，K＞m≧2；

第K轮打分：对每条流从第K-1个中间盒到达的第K个可能的中间盒进行打分， 然后对每个中间盒<p_i,MB_x>的得分进行累加；对每个中间盒<p_i,MB_x>的总分从大到小进 行排序，选取在第x类中间盒MB_x中相对排名前n名的中间盒MB_x作为处理流的最终 的中间盒。

在一个实施例中，在步骤6)之后还包括如下步骤：

7)设置中间盒<p_i,MB_x>在流负载阈值以内最大的处理延迟为L<p_i,MB_x>；

8)依次计算每条流到达可能的资源池经过的最短路径的预估路径延迟，所述预估 路径延迟包括链路延迟和中间盒处理延迟，所述中间盒处理延迟是对应流经过的所有中 间盒的最大可能的处理延迟之和，选取预估路径延迟小于最大忍受延迟的路径作为对应 流的可选择路径；

9)若某个中间盒的负载大于流负载阈值，则将所述中间盒加入中间盒掩码集内；

10)所述中间盒掩码集内的中间盒不处理流，若某条流无法找到所述可选择路径， 则将所述中间盒掩码集内流负载最低的中间盒从所述中间盒掩码集中剔除，再寻找所述 流的可选择路径。

在一个实施例中，在步骤6)之后步骤7)之前还包括如下步骤：

依次计算每条流可能经过的最短路径的链路延迟，对所述链路延迟从大到小进行排 序；

依次对从大延迟对应的流到小延迟对应的流执行步骤7)至步骤10)。

在一个实施例中，若在步骤10)中有中间盒从所述中间盒掩码集中剔除，则在所 有流找到所述可选择路径后，检验每条流的预估路径延迟是否小于最大忍受延迟。

在一个实施例中，某种中间盒的需求数目n＝aN/M+b；其中，所述中间盒单位时间 内可以处理M的数据，所有流的需求是单位时间内N的数据量，a和b是工程系数。

在一个实施例中，在所述步骤5)中，当前中间盒的得分与当前流的当前起点至当 前中间盒的距离成反比。

本发明还提供了一种软件定义网络中的中间盒调度系统，包括资源池，还包括控制 器，所述控制器用于：

获取流的列表，所述流的列表含有每条流的源点、目的点、依次经过的中间盒的信 息，所述中间盒用于对流进行相应的处理；

获取每种中间盒的需求数目n；

获取网络，所述网络上分布着所述资源池，所述资源池运行至少一个中间盒；

维护一个分数表，分数表记载着所有中间盒在每个资源池的得分，第i个资源池p_i的第x类中间盒MB_x用<p_i,MB_x>表示；

对每条流到达可能的资源池经过的最短路径中经过的中间盒进行打分，其中当前中 间盒的得分与当前流的当前起点至当前中间盒的距离反相关，对每个中间盒<p_i,MB_x> 每次获得的分数进行累加；

根据每个中间盒<p_i,MB_x>的总分从大到小进行排序，选取在第x类中间盒MB_x中 相对排名前n名的中间盒MB_x作为处理流的中间盒。

在一个实施例中，所述控制器还用于：

在所述流中，获取经过中间盒个数最多的最长流，其中所述最长流经过的中间盒个 数为K；

通过如下方法对中间盒进行打分：

对流进行K轮打分：

第一轮打分：对每条流从源点到到达的第一个可能的中间盒进行打分，然后对每个 中间盒<p_i,MB_x>的得分进行累加；对每个中间盒<p_i,MB_x>的总分从大到小进行排序，选 取在第x类中间盒MB_x中相对排名前n名的中间盒MB_x作为处理流的临时中间盒；

第m轮打分：对每条流从第m-1个中间盒到达的第m个可能的中间盒进行打分， 然后对每个中间盒<p_i,MB_x>的得分进行累加；对每个中间盒<p_i,MB_x>的总分从大到小进 行排序，选取在第x类中间盒MB_x中相对排名前n名的中间盒MB_x作为处理流的临时 中间盒；其中，K＞m≧2；

第K轮打分：对每条流从第K-1个中间盒到达的第K个可能的中间盒进行打分， 然后对每个中间盒<p_i,MB_x>的得分进行累加；对每个中间盒<p_i,MB_x>的总分从大到小进 行排序，选取在第x类中间盒MB_x中相对排名前n名的中间盒MB_x作为处理流的最终 的中间盒。

在一个实施例中，所述控制器还用于：

设置中间盒<p_i,MB_x>在流负载阈值以内最大的处理延迟为L<p_i,MB_x>；

依次计算每条流到达可能的资源池经过的最短路径的预估路径延迟，所述预估路径 延迟包括链路延迟和中间盒处理延迟，所述中间盒处理延迟是对应流经过的所有中间盒 的最大可能的处理延迟之和，选取预估路径延迟小于最大忍受延迟的路径作为对应流的 可选择路径；

若某个中间盒的负载大于流负载阈值，则将所述中间盒加入中间盒掩码集内；

所述中间盒掩码集内的中间盒不处理流，若某条流无法找到所述可选择路径，则将 所述中间盒掩码集内流负载最低的中间盒从所述中间盒掩码集中剔除，再寻找所述流的 可选择路径。

相对于传统的静态配置方案和简单的负载均衡方案，我们的方案可以让Middlebox 部署在处理需求大的地方，让更多的流能在距离较近的Middlebox进行处理；在调度流 的过程中，我们不仅考虑到负载均衡，还考虑到Middlebox距离对包延迟的影响，在这 种综合考虑之下，我们的调度方案获得了更好的延迟性能。综合我们的子方案，我们的 自适应方案可以用尽可能少的Middlebox来实现我们的延迟需求。

【附图说明】

图1是现有技术中包含Middlebox的网络示意图；

图2是本发明一种实施例的软件定义网络示意图；

图3是本发明一种实施例的软件定义网络管理示意框图；

图4是现有技术负载均衡带来额外延迟的示意图；

图5是本发明一种实施例的网络模型示意图；

图6是本发明一种实施例的K轮打分算法示意图；

图7是本发明一种实施例的软件定义网络中的中间盒调度系统示意图；

图8是本发明一种实施例的部分算法框架图；

图9是本发明一种实施例的流调度算法框架图；

图10是本发明一种实施例的软件定义网络中的中间盒调度系统工作过程示意图；

图11是本发明另一种实施例的软件定义网络中的中间盒调度系统工作过程示意图。

【具体实施方式】

以下对发明的较佳实施例作进一步详细说明。

在对软件定义网络中的中间盒调度方法及系统进行描述前，先介绍一下其网络相关 的模型。

网络模型

本发明的网络模型是基于软件定义网络的模型。在本网络中总共有4种节点：控制 器(Controller)，Openflow交换机(Switch)，客户机(Host)和Middlebox资源池(Resource  Pool)。附图5给出了一个网络的示例，图中省略了控制器。控制器是用来控制交换机 和Middlebox的，在其中维护了交换机和Middlebox状态。通过扩展Openflow协议， 让控制器可以同时管理交换机的转发状态和Middlebox的工作状态，并对交换机的流表 和Middlebox的策略进行配置。客户机是网络的用户，是流的源点或者目的点。根据流 的具体内容和属性，每条流都会经过一定序列的Middlebox处理，可以称之为处理序列。 资源池是可以运行Middlebox软件的机器，可以在里面动态地进行软件Middlebox的开 关和迁移。

延迟模型

网络包的延迟包括链路上的传输延迟和Middlebox的处理延迟。

链路上的传输延迟，在本发明的网络模型里，认为这一部分的延迟是固定的。

Middlebox的处理延迟，考虑包在Middlebox里面的排队，如果Middlebox处理流 的负载大于某个程度，我们认为包会在Middlebox的buffer里进行排队。Middlebox的 负载越大，可能的排队时间就越长。

Middlebox内部排队模型

一个Middlebox可以建模成具有三级池的一种处理结构：一个Middlebox由输入池、 处理池和输出池。流被发送到Middlebox后先存在输入池进行排队，然后由调度器送入 各个处理单元进行处理，处理完之后送出到输出池，准备通过网络硬件发送出去。为了 建模Middlebox的处理过程，假设所有需要处理的网络包的大小都是S_pk，而Middlebox 同时可以处理K_p个包，可以把这种处理能力定义为K_p个处理单元(worker)。每个处 理单元同一时刻只能处理一个软件包，而且在处理完当前网络包的时候不会切换到另外 的网络包的处理过程。假设T是一个处理单元处理一个固定大小S_pk的网络包所需要的 时间，那么就可以定义一个Middlebox单位时间的处理网络包的数目C_mb＝K_p/T，可以 称为Middlebox的处理能力。假设某个时刻到达Middlebox的包的数目是R_pk，则 Middlebox的处理速度可以表示为：

$\mathrm{ProcRate}\left(R_{\mathrm{pk}}\right)\left(\begin{array}{cc}{R}_{\mathrm{pk}},& R_{\mathrm{pk}}<C_{\mathrm{mb}}\\ C_{\mathrm{mb}},& R_{\mathrm{pk}}>C_{\mathrm{mb}}\end{array}\right);$

如上述公式所示，当包的到达速率R_pk小于C_mb的时候，所有的包都不需要排队， 直接被分配到R_pk个处理单元上，所以处理速度是R_pk；但是，当包的达到速率大于C_mb的时候，也就是此时Middlebox来不及实时处理完所有的包，这时候包需要在Middlebox 的输入池进行排队，这个时候处理速度达到了Middlebox处理能力的峰值，也就是C_mb。 因为一个处理单元在同一时刻只能处理一个网络包，这个时候Middlebox的处理速度是 C_mb。

在分方案的模型中，每个客户机的发包速率遵循泊松分布P(λ₁)，那么n个独立的客 户机的发包速率就是P(λ₂)，其中λ₂＝nλ₁。那么整个排队模型就是一个典型的M/D/C排 队过程，其中C＝K_p，D＝T。排队时间的分布函数F(y)可以表示为

$F\left(y\right)={\int }_0^{\infty }F(x+y-T)\frac{{\lambda }_2^{K_p}{x}^{K_p-1}}{(K_p-1)!}{e}^{-{\lambda }_{2}x}\mathrm{dx}$

这个公式也可以被进一步地表达成分段函数的形式，当W∈[mD,(m+1)D]，

$(W\le x,{\lambda }_2)=P^{\prime }(W\le x,n)=\underset{n=0}{\overset{K_p-1}{\Sigma }}\frac{{\lambda }_2^n{e}^{-{\lambda }_2}}{n!}\underset{k=1}{\overset{m}{\Sigma }}\frac{{(-{\lambda }_2(x-\mathrm{kD}))}^{(k+1)K_p-1-n}}{((k+1)K_p-1-n)!}{e}^{{\lambda }_2(x-\mathrm{kD})}$

假设每个Middlebox所能容忍的延迟上限是r，要保证处理时间大于r的概率小于 某个值η，如公式所示：

P(W>r)<η

对于多个Middlebox，公式中P就是一个处理序列上的多个Middlebox的联合分布 函数。

部署和调度目标

一条流可以被描述成(src,dst,(MB_a,MB_b,MB_c)),这表示一条从源点src发向目的点dst 的流，这条流需要先后被a、b、c类型的Middlebox处理。这样网络的流量分布可以用 一个流的列表来表示。

在拓扑中，假设有PoolNum个资源池，这些资源池用来运行Middlebox软件，每个 资源池最多可以运行N个Middlebox。一个Middlebox的部署方案可以被描述成一个向 量pl。例如pl[i]表示第i个资源池。定义MBSet(pl[i])为资源池pl[i]中的Middlebox的集 合，定义MBNum(pl[i])为pl[i]中Middlebox的数目。

对于一个特定的部署方案pl集合，需要为每条流选择一个近似最优或者最优的路径。 我们定义这个路径为最小延迟路径(Minimum Delay Path，MDP)。我们分别用links(f) 和mbs(f)表示流f的MDP经过的链路的集合和Middlebox的集合。定义FlowNum(m) 为经过Middlebox m的流的数目，那么这个Middlebox的延迟就是Delay(FlowNum(m))， 对于链路L来说，延迟是Dealy(L)。假设r是能忍耐的流的最大的延迟。那么目标就是 通过Middlebox的动态部署和调度，保证每条流的延迟都小于最大忍耐延迟r，同时让 Middlebox的部署数目最小。这个问题可以表示成如下优化问题：

服从：

对于所有属于pl的Middlebox：MBNum(p)≤N；

$\forall f\in \mathrm{TList}:P(S_{\mathrm{lk}}+S_{\mathrm{mb}}>r)<\eta ;$

whereS_lk＝∑_l∈links(f)Delay(L)；

S_mb＝∑_m∈mbs(f)Delay(FlowNum(m))；

公式中的P是一个流经过的所有Middlebox的处理延迟的联合分布函数概率。S_lk是流的MDP中的所有链路的延迟之和，对于一条固定的路径，认为S_lk是常数。S_mb是 MDP上所有的Middlebox处理延迟之和。对于一个具体的单个Middlebox m来说，它 的处理延迟是Delay(FlowNum(m))。所以为了计算P，我们必须计算概率密度函数P。 这是非常复杂和困难的，因为，每个Middlebox的分布都和经过它的流的数目相关的。 鉴于P的计算比较复杂，可以用期望值来限制流的延迟。这样P(S_lk+S_mb)<η可以被表达 成：

S_lk+∑_m∈mbs(f)E(FlowNum(m))<γ；

可以限制每个Middlebox m最多只能处理Max_m个流，那么因为：

FlowNum(m)≤Max_m；

所以有：

E(FlowNum(m))≤E(Max_m)；

这样，对于流的延迟的限制就可以表达成：

∑_l∈links(f)Delay(l)+∑_m∈mbs(f)E(FlowNum(m))<γ；

那么这个优化问题可以重新表达成：

服从：

对于所有属于pl的Middlebox，所有属于MBSet(pl[i])的单个Middlebox m：

MBNum(p)≤N,FlowNum(m)≤Max_m；

$\forall f\in \mathrm{TList}:$

∑_l∈links(f)Delay(l)+∑_m∈mbs(f)E(FlowNum(m))<γ；

为了解决这个优化问题，可以把问题拆成两个部分，一是Middlebox的动态部署， 二是，对于具体的Mdidlebox部署方案，如何调度流量，如果给每条流找到自己的MDP。

实施例1

本实施例提出一种Middlebox动态部署方法以解决上述问题，其包括如下步骤：

1)获取一系列参数：给定流的分布TList、网络G、需要的每种Middlebox数目的 列表MBNumList。

流的分布TList是一个流的列表，每条流f可以表示为一个列表，如 (src,dst,(MB_a,MB_b,MB_c))表示流f从源点src出发到目的点dst，且必须顺序地由a,b,c类 型的Middlebox处理，这个处理序列(service chain)可以用f.chain表示。对于网络G， G.plist表示资源池的列表，每个资源池可以运行N个Middlebox。

2)维护一个对应于所有资源池的所有Middlebox类型的分数表，通过模拟K轮投 票的方法来决定Middlebox的放置位置。第i个资源池p_i的第x类中间盒MB_x用<p_i,MB_x> 表示，在这个分数表中，每个资源池都有所有类型的Middlebox，即使当前某个资源池 并没有运行某个Middlebox。这里的K是指TList里面的流的最长的处理序列，即该流 经过的Middlebox个数。在第i轮打分中，每条流对它的处理序列(service chain)的第 i个Middlebox的类型进行打分，如果某个流在此轮打分中没有对应的Middlebox，则这 个流不参与打分。

算法开始，初始化打分表和资源点，在每一轮，先计算每条流可能经过的最短路径 的当前起点(如果是第一轮，则当前起点是流的源点，如果是第二轮以后，当前起点则 是流的上一个Middlebox终点)到下一个相关资源池的距离，然后根据这个距离给这个 资源池的该Middlebox类型进行打分。

第一轮打分：

如图5所示，假设从客户机0出发的第一个流第一个必须经过的Middlebox是MB_A， 那么第一个流可能由资源池1的MB_A1处理，在这个情况下，从客户机0到资源池1的 最短路径即是：客户机1→第一交换机→资源池1；第一个流也可能由资源池0的MB_A0处理，在这个情况下，从客户机0到资源池1的最短路径即是：客户机1→第一交换机 →第二交换机→资源池0。获取第一个流到达可能的资源池经过的最短路径，计算从源 点(即客户机0)到达第一种Middlebox MB_A的距离(即到达资源池的距离)，这个距 离就用dist(f.src,p)表示，可以采用1/ln(dist(f.src,p))进行评分，然后对MB_A0和MB_A1进 行打分。然后对第二个流按照上述方法进行同样的操作，假设第二个流也首先经过MB_A处理，这样，MB_A0和MB_A1可以再次获得相应的得分…直至将所有的流都按照上述方 法处理完毕。

第i个资源池p_i的第x类Middlebox MB_x用<p_i,MB_x>表示，对于每一个<p_i,MB_x>， 将各个流对<p_i,MB_x>的打分进行相加，根据每个中间盒<p_i,MB_x>的总分从大到小进行排 序，选取在第x类中间盒MB_x中相对排名前n名的中间盒MB_x作为处理流的临时中间 盒。例如，需要3种中间盒MB_A，则在上述排序表中，选取在MB_A中相对排名前三的 中间盒MB_A作为处理流的临时中间盒。

从第二轮打分开始，流的起点变为上一轮选出的相应的Middlebox的位置，然后再 计算从这个起点到下一个可能的Middlebox的距离，对流必须经过的第二种Middlebox 进行打分。例如，假设经过第一轮打分，MB_A1得分比MB_A0高，MB_A1作为临时的中间 盒，而第一流还要经过另一种MB_C处理，则对MB_C的打分应以MB_A1作为源点。然后 按照上述方法对各个Middlebox进行打分。在第i轮打分中，每条流对它的处理序列 (service chain)的第i个Middlebox的类型进行打分，每个<p_i,MB_x>的当前得分都要与 之前的总得分进行相加，然后再对所有Middlebox进行排名，然后根据分数排名重新选 择第i轮得到的临时中间盒，直至获得最后一轮的结果，选取在第x类中间盒MB_x中相 对排名前n名的中间盒MB_x作为处理流的最终的中间盒。

算法流程如下：

在每一轮最后，根据当今的分数，根据每种Middlebox类型的需求，对于每种类型 的Middlebox，可以选出临时性的Middlebox放置位置(资源点)。

K轮投票算法KLevelVoting(G,TList,MBNumList)

1.初始化打分表和资源点

2.对于每一轮循环：

3.对于Tlist里面的每条流f：

4.对于每一个可能的起点(上轮资源点)：

5.对每个资源池根据距离进行投票

6.根据本轮结果选出本轮的可能资源点

7.选出最终结果。

实施例2

一种Middlebox流调度方法

在实施例1中，描述了Middlebox动态放置问题并给出了相关的方案，在此基础上 进行流的调度，把每条流按照处理序列分配到具体的Middlebox上。给定具体的流量分 布TList，放置方案pl，和最大忍受的延迟r，通过变形的Viterbi算法(Masked-Viterbi) 来计算流的调度问题。对于每一条流f来讲，我们称最优的调度路径为最小延迟路径 (Minimum Delay Path，MDP)，调度问题就是求TList中每条流的最小延迟路径的问题。

流调度算法

流调度算法分为两个阶段。第一阶段，不考虑Middlebox的负载，计算每条流的最 小可能延迟。在这个阶段，我们认为每个Middlebox的处理延迟都是基本的延迟，不考 虑包在Middlebox的缓存(buffer)里面排队的情景。用基本的Viterbi算法可以求解这 个问题。计算出每个流的最短可能延迟之后，我们根据这个延迟大小对流进行排序(从 大延迟到小延迟)，然后在第二阶段，考虑Middlebox的负载情况，按照第一阶段的排 序结果采用Masked-Viterbi计算每条流的最终的MDP。在第二阶段，我们维护着一个 Middlebox的掩码集(Mask Set)。如果一个Middlebox的负载达到某种程度，我们就把 这个Middlebox加入到这个掩码集里面，在计算具体某条流的MDP时候，掩码集的 Middlebox不作考虑，直接跳过。如果跳过掩码集，对于某条流找不到可能的路径，那 么我们将临时性的对掩码集中的某个元素进行剔除，我们选择掩码集中的负载相对较小 的Middlebox进行剔除，然后重新计算这条流的MDP。这个剔除-重计算的过程可能会 反复进行多次，直到找到合适的MDP。整个过程如下：

算法Masked-Viterbi(Tlist,pla,r)

1.对于Tlist里面的每条流f：

2.计算f的最小可能路径

3.对Tlist里的流进行重排序(按延迟从大到小)

4.对于Tlist里面的每条流f：

5.对于f处理序列中的每种Middlebox类型：

6.根据每个Middlebox的流的数目计算掩码集

7.在掩码集上计算f的MDP的当前节点

8.如果计算不出MDP的当前节点则循环：

9.剔除掩码集中一个负载小的Middlebox

10.重新计算MDP的当前节点

11.判断f的MDP是否合法，如果合法：

12.把这个MDP加入到结果里

13.返回最终结果

Middlebox自适应部署和调度

给定流的分布TList(随时间变化)，拓扑G，最大可以忍受的延迟r，最少部署多 少Middlebox可以满足我们的延迟需求，以及如何部署和调度流？这个问题是以上两个 字问题的综合。

算法描述

我们综合两个子算法KLevelVoting和Masked-Viterbi，构建了一个Middlebox自适 应部署和调度方案。整个算法结构描述如下：

自适应部署和调度算法(G,TList,r)

1.根据Tlist计算Middlebox的基本需求数目MBNumList

2.循环直到MBNumList太大：

3.采用KLevelVoting计算G,Tlist,r,MBNumList部署方案

4.用Masked-Viterbi计算此部署方案下流的调度方案

5.如果得到合适的结果：

6.返回结果

7.否则：

8.继续循环

9.不能找到满足r的方案

我们先根据Middlebox的处理能力，计算出没有Middlebox最基本的需求数目。然 后采用KLevelVoting算法计算出在此数目下的Middlebox部署方案，然后在此部署方案 下用Masked-Viterbi计算流的调度。如果没有找到满足r的方案，我们适当增加 Middlebox的数目，重新开始计算。如果增加到某种数目仍不能满足我们的需求，我们 认为在此TList和拓扑G下，不能找到最大延迟为r的方案。

实施例3

本实施例中主体部分在软件定义网络中的控制器中实现，另外需要修改Middlebox 软件，让Middlebox软件接受控制器的控制。整个方案的实现由控制器中的算法模块、 Middlebox控制模块以及Middlebox中的控制器适配模块组成，如图3所示。算法在算 法模块中实现，控制器对Middlebox的控制通过Middlebox控制模块实现，而Middlebox 与控制器的交互是通过控制器适配模块实现的，这个过程如图10所示。客户机发送包 到交换机上，交换机查询流表，如果交换机找不到相应的流表，就会把包发送到控制器， 控制器运行算法，计算得到包相应的流表，下发到交换机。交换机根据流表，将包转发 到相应的Middlebox。Middlebox处理完包，将包转发回交换机，交换机再根据相应的 流表将包转发给接下来的Middlebox，或者转发回目的客户机。

为了区别不同阶段的包，我们通过打标签的方式，区分包的处理进度。如附图11 所示，交换机接受到从源客户机来的网络包，默认有个空的标签，如果交换机没有相应 的流表，那么交换机将会把这个空的标签以及网络包本身转发给控制器。控制器中维护 着所有流的策略信息，控制器根据这个空的标签和网络包的相关信息查询相关的策略， 生成流表，下发到交换机。交换机根据流表把包转发到相应的Middlebox中处理。 Middlebox在处理包的过程中，根据相应的策略，处理包的内容，并更新相应的标签。 整个更新的过程都是在控制器的管理下完成对侧。更新完标签，Middlebox将包转发回 交换机。交换机接受到新的包，查询流表，如果没有相应的流表，继续把标签和包转发 给控制器，让控制器配置相应的流表。如此反复，知道包被自己处理序列中全部类型的 Middlebox所处理。最后交换机将被完全处理后的包转发给目的客户机。

算法模块是我们方案中的核心模块，我们的两个子算法及综合的自适应算法都是在 这部分实现的。在每一次算法循环中，我们调整Middlebox数目，然后用KLevelVoting 计算Middlebox部署方案，在此部署方案基础上，使用Masked-Viterbi计算每条流的 MDP。如果最终得到合法的结果，则返回结果，如果没有则调整Middlebox数目开始新 的循环，直到达到Middlebox数目上限。

调整Middlebox数目

初始状态下，每种类型的Middlebox的数目是通过估计Middlebox处理能力得到的。 设某种类型的Middlebox单位时间内可以处理M的数据，流的需求是单位时间内N的 数据量，所以此种类型基本的Middlebox需求数目就是aN/M+b，其中a和b都是工程 值。

在后面每一轮的迭代过程中，都会调整Middlebox数目。这种调整有两个问题，一 是调整哪些类型的Middlebox数目，另外，具体调整数目是多少。我们通过观察每种类 型的Middlebox负载情况来判断此种类型的Middlebox是否需要增加。如果这种类型的 Middlebox的处理能力都普遍大于实际处理的数据量，那么这种类型的Middlebox是不 需要进行调整的，调整也不会带来好的效果。反之，需要进行相应的调整。调整的数目 也是根据每种类型的Middlebox的负载进行估计的。我们称这个数目为调整步长。调整 步长和负载的关系，我们用一个分段函数来表述。不同的负载分布情况，对应于不同的 调整步长。

部署算法

部署采用KLevelVoting的方式，模拟K轮流的投票来最终决定Middlebox的部署情 况。在每一次的迭代过程中，我们在具体实施部署算法前，流的分布TList，网络的拓 扑G，以及每种Middlebox的数目MBNumList都被控制器获取了。控制器的任务就是 如何根据流的处理需求来布置指定数目的Middlebox，让Middlebox尽可能地放置在需 求较大的地方。为了达到这个目的，我们让流对潜在的Middlebox放置位置(资源池) 进行投票，根据从包的位置到资源池的距离进行投票。在投票的过程中，每一轮的投票 过程中，某个流f，只对它的处理序列(service chain)f.chain对应的Middlebox类型进 行投票。这个时候，起点是源地址(第一轮投票)，或者上一轮选定的潜在位置(后面 K-1轮投票)，距离就是起点到资源池的距离，然后这个流会给每个Middlebox类型和 资源池的对一个距离倒数相关的分数。在每一轮的投票结束后，每个Middlebox类型和 资源池对都会累加得到最新的总分数。对于某种特点类型的Middlebox，选取特定数目 的得分最高的Middlebox数目。这个数目是和MBNumList相关的数目。每一轮的最后， 都会重新选出潜在的Middlebox位置。最后一轮结束后，会选取得到最终的Middlebox 部署位置。

流调度算法

得到了Middlebox部署位置后，根据流量的分布TList和网络拓扑G，以及最大忍 受的延迟r，我们将通过Masked-Viterbi算法得到流的调度方案。我们的流调度算法分 布两个阶段，第一个阶段是计算每个流的最小的可能的延迟，并通过这个延迟对流进行 排序；第二个阶段是通过跳过负载大的Middlebox来找到合适的流的MDP。

在第一个阶段，我们不考虑Middlebox的负载，而过大负载带来的延迟。我们认为 Middlebox的处理能力是无限大的，然后处理延迟是最基本的处理延迟。在这样的前提 下，我们计算出每条流的MDP，这个MDP的延迟大小就是最小可能的延迟。也就是说， 在当前的条件下，不能得到比这个延迟更小的延迟。根据这个延迟，我们对流进行排序， 从大延迟到小延迟。后面我们将按照这个顺序进行具体的MDP的计算。

在第二个阶段，我们需要考虑Middlebox的处理能力和高负载下的额外的延迟。我 们根据第一阶段的排序结果，来计算每条流的MDP。在计算的过程中，我们维护一个 掩码集，掩码集是所以负载过高的Middlebox的集合。在计算的过程中，我们会避免使 用掩码集的Middlebox。如果不是用掩码集的Middlebox，我们不能找到MDP，那么我 们会从掩码集中剔除一个负载最低的Middlebox，然后重新计算这条流的MDP。这个剔 除再重新计算的过程可能会发生若干次，知道找到合适的MDP。对于每一条流的MDP， 方案最后会检查是否满足r的限制。如果有明显多的流的MDP不满足要求，我们认为 在当前的MBNumList下，我们找不到合适的部署和调度方案，需要调整Middlebox的 数目MBNumList，开始新一轮的迭代。

Middlebox控制模块

Middlebox控制模块是控制器中维护Middlebox状态的模块。常规意义下的软件定 义网络控制器只能管理交换机，但是，在我们的方案中，我们通过扩展软件定义网络的 南向接口(如Openflow协议)，让软件定义网络中的控制器同样可以控制Middlebox。 在控制器里，这部分是在Middlebox控制模块实现的。

Middlebox模块可以读取和设定Middlebox的策略和状态。控制器通过这个模块来 获得整个网络全部Middlebox状态的合集。对于相干的或者相关影响的Middlebox，控 制器可以通过Middlebox控制模块协调Middlebox之间的策略，以达到我们的控制需求。

为了能按照正确的顺序处理包，我们同样对包的格式进行了改进。我们采用IP包 头空闲的标签来标志包的处理情况，初始状态定义为一个标签，然后每经过处理序列 (service chain)上的一个Middlebox，标签都会相应地更新。标签更新的过程是在 Middlebox内部进行的。

控制器适配模块

控制器适配模块是运行在Middlebox里面，用来和控制器交互的模块。在数据层面， 这个模块扩展了控制器对Middlebox管理。控制器向Middlebox发送的读取状态和写状 态、策略的命令，由控制器适配模块接受并转化成Middlebox具体的内部命令执行。

控制器适配模块还负责IP包头的标签处理，当Middlebox处理完某个网络包之后， 将更新一个新的标签，以标志处理过程。

以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本 发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在 不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明 由所提交的权利要求书确定的专利保护范围。