中间处理约束下的异构网络资源配置方法

摘要

本发明提出一种中间处理约束下的异构网络资源配置方法，包括：分别获取每个数据流的截止时间和资源需求量，并根据每个数据流的截止时间和资源需求量为每个数据流设置对应的评价分数，根据评价分数对数据流进行排序，以为每个中间节点生成对应的偏好列表；获取异构网络的网络拓扑信息，计算数据流经过中间节点的传输路径长度；将每个中间节点的服务名额初始化为1，并在数据流与中间节点之间进行双向匹配，以得到每个中间节点的准服务名单；根据准服务名单得到中间节点和数据流的映射关系，并结合中间节点对应的偏好列表对数据流进行顺序调度。本发明实现了数据密集型应用在中间处理约束下的低延迟及高性能，达到资源最优配置和最佳网络性能。

说明书

技术领域

本发明涉及网络资源管理技术领域，特别涉及一种中间处理约束下的异构网络资源配 置方法。

背景技术

异构网络中的实时大数据应用通常基于大量感知数据的分析和处理，根据系统反馈做 出相应决策。传统的不加选择地将初始感知数据上传到服务器的方式，不仅导致低效，而 且极大地浪费网络资源，甚至造成网络拥塞和业务失效等后果。因此，一种可行的方式， 则是充分利用网络节点的处理能力，将初始数据在节点上进行处理后，再将结果传送到服 务器。然而，异构网络中的节点之间的能力差异、分级处理模式、以及负载均衡等因素， 催生出一种新的需求，即越来越多的特殊工作流要求在其源到目的之间的路径上的某个中 间节点上进行处理(例如尺寸裁剪、格式转换、去噪处理等)，即中间处理约束。中间处理 节点(简称中间节点)通常是专用的、高性能的、具有充足资源(例如CPU、GPU、内存 等)的机器。

另一方面，一个软实时的应用包括多个数据流。由于流之间具有相互依赖性——某些 流必须在其它流完成之后才能进行处理，因此，流期望的完成时间也各有差异，即每个流 的截止时间不同。同时，对于软实时应用，其包含的流即使在截止时间之后才完成，这个 流依然是有效的。在这个背景下，优化软实时应用的延迟则意味着最小化所有流的总延迟。

而传统的解决方案要么只关注路由优化，寻找最短的传输路径，以减少数据的传输延 迟；要么只关注流的调度次序，以减少流在处理节点上的排队时间。由于流的完成时间由 路由延迟、排队时间和处理时间三部分组成，任何单一角度的优化，都无法实现系统资源 的全局最优配置。因此，全局优化要求同时考虑路由与调度两个角度。路由角度的问题是 如何将中间节点分配给流，而调度角度的问题则是哪些流应该被优先地处理。

发明内容

本发明旨在至少在一定程度上解决上述相关技术中的技术问题之一。

为此，本发明的目的在于提出一种中间处理约束下的异构网络资源配置方法，该方法 从调度和路由两个角度进行联合优化，以最小化数据密集型应用的延迟，实现了数据密集 型应用在中间处理约束下的低延迟及高性能，达到资源最优配置和最佳网络性能。

为了实现上述目的，本发明的实施例提出了一种中间处理约束下的异构网络资源配置 方法，包括以下步骤：S1：分别获取每个数据流的截止时间和资源需求量，并分别根据每 个数据流的截止时间和资源需求量为每个数据流设置对应的评价分数，并根据所述评价分 数对所述数据流进行排序，以为每个中间节点生成对应的偏好列表；S2：获取所述异构网 络的网络拓扑信息，并根据所述网络拓扑信息计算所述数据流经过所述中间节点的传输路 径长度；S3：将每个所述中间节点的服务名额初始化为1，并在所述数据流与中间节点之间 进行双向匹配，以得到每个所述中间节点的准服务名单；S4：根据每个所述中间节点的准 服务名单得到所述中间节点和数据流的映射关系，根据所述映射关系和所述中间节点对应 的偏好列表对所述数据流进行顺序调度。

另外，根据本发明上述实施例的中间处理约束下的异构网络资源配置方法还可以具有 如下附加的技术特征：

在一些示例中，所述S2进一步包括：根据所述网络拓扑信息计算所有数据流的源节点 到中间节点之间的最短路径长度，以及所述中间节点到所有流的目的节点之间的最短路径 长度；根据所述所有数据流的源节点到中间节点之间的最短路径长度和所述中间节点到所 有流的目的节点之间的最短路径长度得到所述数据流经过所述中间节点的传输路径长度。

在一些示例中，其中，所述中间节点的传输路径长度为所述所有数据流的源节点到中 间节点之间的最短路径长度和所述中间节点到所有流的目的节点之间的最短路径长度之 和。

在一些示例中，所述步骤S3进一步包括：S31：对所述中间节点进行排序，以为每个数 据流生成对应的偏好列表；S32：每个数据流向其对应的偏好列表上的第一个中间节点提出 申请；S33：每个所述中间节点判断向其提出申请的数据流的数量是否超过该中间节点的可 服务名额，如果是，则根据该中间节点对应的偏好列表剔除可服务名额之外的数据流，并 将可服务名额之内的数据流加入其准服务名单中，并将所述中间节点的可服务名额加1。

在一些示例中，在所述步骤S33之后，还包括：S34：如果所有数据流均集中在一个中 间节点的准服务名单内，则执行所述步骤S4，否则，执行所述步骤S31。

在一些示例中，在所述步骤S33中，还包括：如果每个所述中间节点判断向其提出申请 的数据流的数量未超过该中间节点的可服务名额，则直接将所述数据流加入所述中间节点 的准服务名单。

在一些示例中，所述步骤S31，进一步包括：S311：根据每个所述中间节点对应的偏好 列表和每个中间节点当前的准处理名单计算每个数据流在每个中间节点上期望的完工时 间；S312：根据所述期望的完工时间和所述数据流经过所述中间节点的传输路径长度为每 个所述中间节点设置一个评价分数，并根据所述评价分数对所述中间节点进行排序，以为 每个所述数据流生成对应的偏好列表。

在一些示例中，所述步骤S311进一步包括：S3111：判断所述中间节点的准处理名单上 是否存在数据流；S3112：如果所述中间节点的准处理名单上不存在所述数据流，则将所述 数据流添加至所述中间节点的准处理名单；S3113：根据所述中间节点对应的偏好列表得到 所述数据流在所述中间节点上的调度次序，并计算所述数据流的处理时间和期望的排队时 间，并根据所述数据流的处理时间和期望的排队时间得到所述数据流期望的完工时间。

在一些示例中，其中，所述数据流期望的完工时间为所述数据流的处理时间和期望的 排队时间之和。

根据本发明实施例的中间处理约束下的异构网络资源配置方法，基于经典的匹配理论， 采用逐步提升名额的循环迭代机制，根据流和中间节点之间的相互偏好性，提出了流和中 间节点之间的双向匹配框架，以达到路由与调度的融合，即从调度和路由两个角度进行联 合优化，以最小化数据密集型应用的延迟，实现了数据密集型应用在中间处理约束下的低 延迟及高性能，从而达到资源最优配置和最佳网络性能。另外，本发明可以适用于比较广 泛的场景，如智慧城市、智能工厂和云数据中心等，因此适用范围广。

本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明 显，或通过本发明的实践了解到。

附图说明

本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显 和容易理解，其中：

图1是本发明一个实施例的中间处理约束下的异构网络资源配置方法的流程图；

图2是本发明一个实施例的数据流完成时间组成部分示意图；

图3是本发明一个具体实施例的数据流期望完工时间计算过程示意图；

图4是本发明一个具体实施例的中间处理约束下的网络数据处理过程示意图；

图5是本发明一个实施例的所有数据流的总时延累积概率分布示意图；

图6是本发明一个实施例的相对问题下界的最优性差距累积概率分布示意图；

图7是本发明一个实施例的数据流的最大完成时间累积概率分布示意图；以及

图8是本发明一个实施例的数据流的平均路由延迟累积概率分布示意图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同 或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描 述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。

以下结合附图描述根据本发明实施例的中间处理约束下的异构网络资源配置方法。

首先，本发明的主要实现思想为：在中间处理约束下，通过在流与中间节点之间进行 双向匹配，达到路由与调度两个角度的联合优化。针对网络中的多个数据流竞争多个中间 节点的情况，数据流根据其偏好选择各自优选的中间节点，同时，中间节点服务能力是有 限的，每个中间节点都有一个服务名额，因而需要根据其偏好，选择各自可服务名额内的 数据流，经过循环迭代，得到流与中间节点的映射关系。然后，中间节点根据其偏好对需 要在该节点上处理的流进行顺序调度。其中，中间节点的选择决定了路由延迟和处理时间， 而流的调度次序决定了排队时间。

具体地，图1是根据本发明一个实施例的中间处理约束下的异构网络资源配置方法的 流程图。如图1所示，该方法包括以下步骤：

步骤S1：分别获取每个数据流的截止时间和资源需求量，并分别根据每个数据流的截 止时间和资源需求量为每个数据流设置对应的评价分数，并根据评价分数对数据流进行排 序，以为每个中间节点生成对应的偏好列表。其中，该评价分数是一个标准化的加权和。

步骤S2：获取异构网络的网络拓扑信息，并根据网络拓扑信息计算数据流经过中间节 点的传输路径长度。

在本发明的一个实施例中，例如，步骤S2进一步包括：

步骤S21：针对所有的数据流和中间结点，根据网络拓扑信息计算所有数据流的源节点 到中间节点之间的最短路径长度，以及中间节点到所有流的目的节点之间的最短路径长度。

步骤S22：根据所有数据流的源节点到中间节点之间的最短路径长度和中间节点到所有 流的目的节点之间的最短路径长度得到数据流经过中间节点的传输路径长度。更为具体地， 中间节点的传输路径长度为所有数据流的源节点到中间节点之间的最短路径长度和中间节 点到所有流的目的节点之间的最短路径长度之和。

步骤S3：将每个中间节点的服务名额初始化为1，并在数据流与中间节点之间进行双向 匹配，以得到每个中间节点的准服务名单。

在本发明的一个实施例中，步骤S3进一步包括：

步骤S31：对中间节点进行排序，以为每个数据流生成对应的偏好列表。该步骤例如进 一步包括：

S311：根据步骤S1中得到的每个中间节点对应的偏好列表和每个中间节点当前的准处 理名单计算每个数据流在每个中间节点上期望的完工时间，其中，每个中间节点当前的准 处理名单初始为0。该步骤例如进一步包括：

S3111：针对每个中间节点，判断该中间节点的准处理名单上是否存在数据流。

S3112：如果中间节点的准处理名单上不存在数据流，则将数据流临时添加至中间节点 的准处理名单。

S3113：根据步骤S1中得到的中间节点对应的偏好列表得到该数据流在中间节点上的调 度次序，并计算该数据流的处理时间和期望的排队时间，并根据数据流的处理时间和期望 的排队时间得到数据流期望的完工时间。更为具体地，数据流期望的完工时间为数据流的 处理时间和期望的排队时间之和。

S312：根据数据流在中间节点上期望的完工时间和数据流经过中间节点的传输路径长 度为每个中间节点设置一个评价分数，并根据该评价分数对中间节点进行排序，以为每个 数据流生成对应的偏好列表。其中，该评价分数是一个标准化的加权和。

步骤S32：依据步骤S312中得到的每个数据流对应的偏好列表，每个数据流向其对应的 偏好列表上的第一个中间节点提出申请。

步骤S33：每个中间节点判断向其提出申请的数据流的数量是否超过该中间节点的可服 务名额，如果是，则根据该中间节点对应的偏好列表剔除可服务名额之外的数据流，并将 可服务名额之内的数据流加入其准服务名单中，并将中间节点的可服务名额加1。进一步地， 如果每个中间节点判断向其提出申请的数据流的数量未超过该中间节点的可服务名额，则 直接将数据流加入中间节点的准服务名单。

进一步地，在步骤S33之后，例如还包括：

步骤S34：如果所有数据流均集中在一个中间节点的准服务名单内，则执行后续的步骤 S4，否则，返回执行步骤S31。

步骤S4：根据每个中间节点的准服务名单得到中间节点和数据流的映射关系，在每个 中间节点上中，根据映射关系和步骤S1中得到的中间节点对应的偏好列表对数据流进行顺 序调度。

因此，本发明实施例的方法基于经典的匹配理论，采用逐步提升名额的循环迭代机制， 根据流和中间节点之间的相互偏好性，提出了流和中心节点之间的双向匹配框架，以达到 路由与调度的融合，实现了数据密集型应用在中间处理约束下的低延迟、高性能的目标。

为了便于理解，以下结合附图2-8，以具体地示例对本发明上述实施例所述的方法进行 进一步详细地描述。

参见图2所示，数据流的完成时间是完工时间和路由延迟的总和，其中，完工时间又包 括数据流在节点上的排队时间和处理时间两部分，而路由延迟则等于经过中间节点，从源 节点到目的节点之间的路径上的传输延迟。假设中间节点是异构的，其数据速度具有差异 性，则易知处理时间和路由延迟依赖于中间节点的选取，而排队时间依赖于数据流在中间 节点上的调度策略。然而，同时减小排队时间、处理时间和路由延迟并非易事。例如，对 于数据流来说，在高性能的节点上处理可以实现较短的处理时间，但是它的传输路径可能 会很长；另外，在实现最短路由时，往往会选择数据流最短路径上的节点，而若这个节点 需要服务的数据流超过其负载限额，该节点上的排队时间可能会非常长。

例如，用M表示所有数据流的集合，K表示所有中间节点的集合。C_m表示数据流 m(m∈M)的完成时间，d_m表示数据流的截止时间，则数据流m的时延(Tardiness)可以表 示为T_m＝max{0,C_m-d_m}。本发明的实施例是在中间处理约束下，最小化所有数据流的总 时延，即因此，本发明实施例的方法从数据流调度和路由两个角度进行联合优化， 具体来说，解决了如何将中间节点分配给数据流，且哪些数据流应该被优先地处理，以最 小化所有数据流的总时延。

对于中间节点的分配，本发明的实施例采用在数据流和中间节点之间进行双向匹配的 方法，通过循环迭代，实现中间节点的接近最优的分配方案。例如，定义A_m为数据流m选 择中间节点时的偏好列表(A_m中的元素属于集合K)，定义B_k为中间节点k(k∈K)选择数 据流时的偏好列表(B_k中的元素属于集合M)。例如：

在数据流选择中间节点时，定义一个标准化的变量θ_l作为衡量数据流经过中间节点的 数据传输路径长度l_mk(m∈M,k∈K)的评价分数，θ_l与l_mk成反比。类似地，标准化的变量θ_e作为衡量数据流的期望完工时间h_mk的评价分数，θ_e与h_mk成反比，则偏好列表A_m由按θ_l+θ_e对中间节点进行降序排序得到。由于数据流期望的完工时间取决于队列中的数据流相互作 用，因而偏好列表A_m在匹配的每一次迭代里都是动态变化的。

在中间节点选择数据流时，定义一个标准化的变量θ_d作为衡量数据流截止时间d_m的评 价分数，θ_d与d_m成反比。类似地，标准化的变量θ_d作为衡量数据流的资源需求量q_m的评 价分数，θ_q与q_m成反比，则偏好列表B_k由按θ_d+θ_q对数据流进行降序排序得到。

由于数据流的完工时间取决于数据流在中间节点上的排队时间和处理时间，为了计算 数据流在各个中间节点上期望的完工时间，需要在节点上进行一次模拟调度过程。作为具 体的示例，参见图3所示，f₁，f₂和f₃三个数据流已经在某个中间节点的准处理名单里， 计算数据流f₄在该中间节点上的期望的完工时间，则只需临时地将f₄加入到该中间节点的 准处理名单中，然后，根据f₁→f₄在偏好列表B_k上的排序进行调度。在该示例中，假设B_k中的排列顺序为f₁＞f₂＞f₃＞f₄，资源需求量q₁＝10,q₂＝5,q₃＝8,q₄＝6，假设数据流在节 点上的处理时间p_m与资源需求量q_m成正比，不失一般性，设p_m＝q_m(m＝1,2,3,4)。节点上 的总资源量为Q＝18。在该节点上调度四个数据流，则可以得到数据流f₄在该中间节点上 的期望的排队时间为10，期望的完工时间为16。

进一步地，为实现中心节点的高效资源分配方案，下面在数据流与中心节点之间进行 双向匹配。该双向匹配是一个循环迭代的过程，具体来说，就是不断循环迭代以下步骤1 至步骤2：

步骤1：生成偏好列表A_m，每个数据流向其偏好列表上的第一个中间节点提出申请， 对于每一个中间节点，如果向其申请的数据流的数目x超过其服务名额即则根 据偏好列表B_k，每个中间节点剔除可服务名额之外的数据流将可服务名额之 内的数据流(前x个)放入其准服务名单，然后，将该中间节点的可服务名额增加1；否则， 直接将x个数据流放入其准服务名单。

步骤2：如果所有数据流都在某个中间节点的准服务名单里，则迭代中止，此时每个中 间节点的准服务名单，即为中间节点和数据流的映射关系；否则，继续进行循环迭代。

另一方面，针对哪些数据流应该被优先地处理的问题，例如，本发明的实施方案如下： 如果一个中间节点要服务的数据流超过1，则根据准处理名单上的数据流在偏好列表B_k中 的排序，进行顺序调度。其中，数据流在节点上的处理必须满足资源约束，即同一时间处 理的数据流的资源需求总量不能超过该节点上可用的资源量。

以下通过具体的示例对本发明的实施例进行性能评估。例如，参见图4所示，考虑一个 智慧城市中的智能交通系统，其中拥有500个传感器节点，10个中间处理节点，即 |M|＝500,|K|＝10。其它的参数在合理的范围内随机生成，一共生成100个随机网络拓扑。

参见图5所示，相比单一的调度策略和路由策略，本发明的实施例能够实现最短的时延。 在本示例中，能够实现60％的实例中总时延为0，这表示60％的应用能够及时地完成。

为定量地评估本发明实施例的最优性，对于每一个实例I，定义最优性差距为：

$Gap\left(I\right)=\frac{Z\left(I\right)-Z_{LB}\left(I\right)}{Z\left(I\right)},$

其中，Z(I)表示实例I的目标函数值，Z_LB(I)表示该优化问题的下界。参见图6所示， 超过90％的情况下，本发明实施例的最优性差距都小于0.4，然而，单一的调度策略和路由 策略仅能够实现5％的情况下，最优性差距小于0.4。这说明本发明实施例的结果与问题下界 非常接近，能够实现接近最优的性能。

图7给出了最大完成时间的累积概率分布示意图。从图7中可以看出，本发明的实施例 可以实现最小的最大完成时间。图8给出了平均路由延迟的累积概率分布示意图。从图8中 可以看出，由于将具有最短传输路径的中间节点分配给流，单一的路由策略实现了最短路 由延迟，然而单一的调度策略由于不考虑传输路径的长短，从而导致路由延迟不可控。

也就是说，本发明的实施例针对中间处理约束下的异构网络资源分配问题，提出了最 小化所有流的总时延的优化目标。通过对影响优化目标的因素进行权衡，分别提出了针对 流和中间节点的偏好列表生成方法。通过逐步提升名额的方法，提出了流和中间节点之间 的双向匹配框架。通过该框架的循环迭代，实现中间节点的优化分配。最后，根据节点分 配方案，在节点上对流进行顺序调度。因此，本发明能够实现低时延的优化目标，能够得 到接近最优的异构网络资源分配结果。

综上，根据本发明实施例的中间处理约束下的异构网络资源配置方法，基于经典的匹 配理论，采用逐步提升名额的循环迭代机制，根据流和中间节点之间的相互偏好性，提出 了流和中间节点之间的双向匹配框架，以达到路由与调度的融合，即从调度和路由两个角 度进行联合优化，以最小化数据密集型应用的延迟，实现了数据密集型应用在中间处理约 束下的低延迟及高性能，从而达到资源最优配置和最佳网络性能。另外，本发明可以适用 于比较广泛的场景，如智慧城市、智能工厂和云数据中心等，因此适用范围广。

在本发明的描述中，需要理解的是，术语“中心”、“纵向”、“横向”、“长度”、“宽度”、 “厚度”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”“内”、“外”、 “顺时针”、“逆时针”、“轴向”、“径向”、“周向”等指示的方位或位置关系为基于附图所示的 方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或 元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。

此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或 者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者 隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个， 三个等，除非另有明确具体的限定。

在本发明中，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”、“固定”等术 语应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或成一体；可以是机械 连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元 件内部的连通或两个元件的相互作用关系，除非另有明确的限定。对于本领域的普通技术 人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。

在本发明中，除非另有明确的规定和限定，第一特征在第二特征“上”或“下”可以是第 一和第二特征直接接触，或第一和第二特征通过中间媒介间接接触。而且，第一特征在第 二特征“之上”、“上方”和“上面”可是第一特征在第二特征正上方或斜上方，或仅仅表示第一 特征水平高度高于第二特征。第一特征在第二特征“之下”、“下方”和“下面”可以是第一特征 在第二特征正下方或斜下方，或仅仅表示第一特征水平高度小于第二特征。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、 或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包 含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须 针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一 个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技 术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合 和组合。

尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的， 不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例 进行变化、修改、替换和变型。