基于增量式最小费用最大流的虚拟服务迁移方法及系统

技术领域

本发明涉及信息技术领域，更具体的说，特别涉及一种基于增量式最小费用最大流的虚拟服务迁移方法及系统。

背景技术

近年来，移动边缘计算(MEC)成为潮流，其是一种将服务器部署在更靠近用户周围的路由器、网关以及基站等结点上，并以云计算技术为核心的云计算平台。对于一些延迟敏感的应用，如面部识别、实时游戏、视频直播等在线服务的应用，传统的云计算中心并不能很好的满足这些应用程序的时延要求。但是有了MEC，云中心将部分计算资源推送至了网络边缘，使一些服务更加靠近用户。这不仅能缓解云计算中心的负载压力，同时能在一定程度上降低服务延迟，降低网络流量，从而更好地满足延迟敏感应用的需求。虽然MEC的优势很明显,但考虑到用户的移动性、对服务访问的时间差异性以及单个边缘服务器的有限覆盖范围，如果将服务固定在一个边缘服务器上，其往往会引起服务延迟的增加。因此，如果不考虑这些因素，所提供的服务可能会显著增加访问延迟，更加糟糕的可能是，会产生大量的网络流量，造成网络拥塞，从而导致服务质量的严重下降，甚至是服务中断。

目前，动态规划算法和机器学习方法经常被用来解决这个问题。有学者基于强化学习算法，提出了一种用于虚拟机执行的自适应配置算法，以解决数据中心的工作负载问题。也有学者提出了一种服务迁移机制，能将计算服务迁移至可用的服务器上进行自适应网格计算。还有学者针对迁移问题定义了代价模型，提出了一个具备感知能力、更加灵活、具有很强适应能力的迁移框架，但其针对的是单个服务。

现有工作在迁移策略上已经取得了不错的效果，但随着人们需求的日益增长，网络规模也随之增长，访问模式也更为复杂，之前的策略难以在大规模的网络拓扑结构下做出最优决策。同时，之前的方法或是针对单服务的迁移，或是缺乏一定的动态性，亦或是求解时间过长。

发明内容

本发明的目的在于针对现有技术存在的技术问题，提供一种基于增量式最小费用最大流的虚拟服务迁移方法及系统，能够在很短时间内求解出最优的服务放置与迁移方案，简单、可靠也易于实现。

为了解决以上提出的问题，本发明采用的技术方案为：

本发明提供一种基于增量式最小费用最大流的虚拟服务迁移方法，该方法包括：

根据边缘服务器的地理位置以及连接关系，构建网络拓扑图；

计算每一对边缘服务器间的最短路径距离，并生成最短路径距离矩阵；

根据所述距离矩阵并结合每个服务的访问信息，建立最小费用最大流模型，所述模型包括服务结点和边缘服务器结点；

对模型进行求解得到最小费用最大流，对服务结点进行迁移并将其放置在对应的边缘服务器结点上；

更新每个服务的访问信息，采用增量式最小费用最大流算法，更新服务结点的位置；

对每个服务的访问信息进行实时的监控和统计，在访问信息的变化率超过设定阈值时，调整其对应的服务结点和边缘服务器结点。

进一步的，所述最小费用最大流模型具体为：

以S结点与T结点为模型的源结点和终结点，Ni代表第i个服务结点，Ej代表第j个边缘服务器结点，源结点S只与服务结点Ni相连，每个服务结点Ni和所有边缘服务器结点Ej相连，每个边缘服务器结点Ej均与终结点T相连；模型中的每条边均关联容量和通信成本。

进一步的，所述采用增量式最小费用最大流算法，更新服务结点的位置，具体包括：

在对模型求解算法的残余网络中，更新每个服务结点放置在边缘服务器结点上的访问成本以及迁移成本；

根据统计的访问信息，对残余网络中的服务结点以及边缘服务结点进行相应的删添；

利用增量式最小费用最大流算法进行求解，根据求解得到的最小费用最大流更新服务结点在边缘服务器结点上的位置。

进一步的，所述增量式最小费用最大流算法，具体包括：

服务结点的访问量发生改变，并在访问次数的变量大于预先学习得到的阈值时，更新服务结点的位置；

服务结点的数量改变时，删除服务结点或增加服务结点，更新服务结点的位置；

边缘服务器承载量发生改变，并在边缘服务器结点的容量减小且从其流出的流大于该边减少后的容量或者出现边缘服务器结点删除时、以及边缘服务器结点容量增加或有新的边缘服务器结点添加时，更新服务结点的位置。

进一步的，所述服务结点的访问量发生改变时，具体包括：

当访问次数的变量大于预先学习得到的阈值时，在上一次的残余网络中，对与该服务结点相连边的权值进行修改；

在服务结点连向边缘服务器结点的边上添加迁移成本，并从费用改变的服务结点出发，重新寻找最小费用最大流；

根据所得到的最小费用最大流，对服务结点的位置进行更新。

进一步的，所述服务结点的数量改变时，具体包括：

当有服务结点减少时，在残余网络中删除所述服务结点以及相关的边；

当有服务结点增加时，在残余网络中添加所述服务结点以及相关的边，选择该服务结点到边缘服务器结点的最小费用路径，在服务结点连向边缘服务器结点的边上添加迁移成本；

从所述删减或增加的服务结点出发，寻找新的最小费用最大流，并对服务结点的位置进行更新。

进一步的，所述边缘服务器承载量发生改变时，具体包括：

当边缘服务器的容量减小，并在其流出的流大于对应边减少后的容量或边缘服务器结点删除时，将费用最大的边对应的流退回；从对应的边缘服务结点出发，选择到终结点的最短路径并增加流，并在服务结点连向边缘服务器结点的边上添加迁移成本；从对应的服务结点出发，寻找新的最小费用最大流，更新服务结点的位置；

当边缘服务器容量增加或有新的边缘服务器结点添加时，则对残余网络进行修改，并在服务结点连向边缘服务器结点的边上添加迁移成本；从对应的边缘服务器结点出发，寻找新的最小费用最大流，更新服务结点的位置。

本发明还提供一种基于增量式最小费用最大流的虚拟服务迁移系统，该系统包括如下：

拓扑图构建模块：用于根据边缘服务器的地理位置以及连接关系，构建网络拓扑图；

矩阵生成模块：用于计算每一对边缘服务器间的最短路径距离，并生成最短路径距离矩阵；

模型建立模块：用于根据所述距离矩阵并结合每个服务的访问信息，建立最小费用最大流模型，所述模型包括服务结点和边缘服务器结点；

服务结点迁移模块：用于对模型进行求解得到最小费用最大流，对服务结点进行迁移并将其放置在对应的边缘服务器结点上；

服务结点更新模块：用于更新每个服务的访问信息，采用增量式最小费用最大流算法更新服务结点的位置；

监控调整模块：用于对每个服务的访问信息进行实时的监控和统计，在访问信息的变化率超过设定阈值时，调整其对应的服务结点和边缘结点。

本发明还提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现任一项所述方法的步骤。

本发明还提供一种非暂态计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现任一项所述方法的步骤。

与现有技术相比，本发明的有益效果在于：

本发明提供的方法及系统将边缘网络中多种访问服务的通信成本问题转化成了最小费用最大流问题，比之动态规划算法以及启发式算法的时间复杂度有所降低，比之贪心算法总访问成本大大降低；并采用增量式最小费用最大流算法，能在很短时间内求解出使整体服务访问成本最小化的最优服务放置与迁移方案，也能够很好的应对服务访问数量突发的放量剧增和异常情况，比现有的动态规划方法、贪心方法以及机器学习的方法更高效，其简单、可靠也易于实现，保证了对用户的快速响应，提升了服务质量。

附图说明

为了更清楚地说明本发明中的方案，下面将对实施例描述中所需要使用的附图作一个简单介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。其中：

图1为本发明虚拟服务迁移方法的流程示意图。

图2为本发明虚拟服务迁移的网络拓扑图。

图3为本发明最小费用最大流模型的示意图。

图4为本发明增量式最小费用最大流算法的流程示意图。

图5为本发明上一次的残余网络的原理图。

图6为本发明修改后的残余网络的原理图。

图7为本发明虚拟服务迁移系统的原理图。

图8为本发明电子设备的原理示意图。

具体实施方式

为了便于理解本发明，下面将参照相关附图对本发明进行更全面的描述。附图中给出了本发明的较佳实施例。但是，本发明可以以许多不同的形式来实现，并不限于本文所描述的实施例。相反地，提供这些实施例的目的是使对本发明的公开内容的理解更加透彻全面。

除非另有定义，本文所使用的所有的技术和科学术语与属于本发明的技术领域的技术人员通常理解的含义相同。本文中在本发明的说明书中所使用的术语只是为了描述具体的实施例的目的，不是旨在于限制本发明。

参阅图1所示，本发明提供一种基于增量式最小费用最大流的虚拟服务迁移方法，该方法具体步骤包括如下：

步骤S1:根据边缘服务器的地理位置以及连接关系，构建网络拓扑图。具体的，所述网络拓扑图中边的权值是由所连接的边缘结点间的距离以及网络传输速度决定的。

本发明的应用场景能够抽象成如图2所示的网络拓扑图，由于在边缘网络中，虚拟服务运行在边缘结点的服务器上，所以将边缘结点抽象成了边缘服务器结点，即图2中与决策中心连接的边缘服务器1～5，用户可以通过最近的访问接入点1～5，来对自己所需要的服务访问对应的边缘服务器。

步骤S2:计算所述网络拓扑图中每一对边缘服务器间的最短路径距离，并生成最短路径距离矩阵。具体的，利用最短路径算法计算得到最短路径距离，方法简单也可靠。

步骤S3：统计最近时间段内对每个服务的访问信息，根据所述最短路径距离矩阵，建立最小费用最大流模型，所述模型包括服务结点和边缘服务器结点。具体的，根据所述最短路径距离矩阵，计算出每个服务放置在各个边缘结点上的访问成本以及迁移成本，并建立最小费用最大流模型。

本发明实施例中，参阅图3所示，所述最小费用最大流模型的建立过程，具体为：

以S结点与T结点为模型的源结点和终结点，这是为了构建模型而设置的。Ni代表第i个服务结点，Ej代表第j个边缘服务器结点，其中i为1～n,j为1～m，即一共有n个服务结点和m个边缘服务器结点。源结点S只与服务结点Ni相连，每个服务结点Ni和所有边缘服务器结点Ej相连，每个边缘服务器结点Ej均与终结点T相连。模型中的每条边均关联两个值，分别为容量和通信成本。

进一步的，源结点S与服务结点Ni相连的每条边的容量均为1，这是使得所有服务均能放置在边缘服务器或云中心处，成本均为0。每个服务结点Ni与所有边缘服务器结点Ej相连的边的容量为1，成本即为将服务结点放置在该边缘服务器结点上的延迟成本与迁移成本之和。每个边缘服务器结点Ej与终结点T相连的边的容量为该边缘服务器结点所能承载服务的数量，成本均为0。

步骤S4：对模型进行求解得到最小费用最大流，对服务结点进行迁移并将其放置在对应的边缘服务器结点上。

具体的，利用经典的最小费用最大流求解算法进行求解，在求解出的最小费用最大流中，若有流从服务结点Ni流经边缘服务器结点Ej，代表将服务结点Ni放置在边缘服务器结点Ej上，并以此对服务结点进行迁移和放置，即根据求解结果可以得到服务结点对应的边缘服务器结点，再对服务结点进行迁移和放置。本发明实施例中，经典的最小费用最大流求解算法采用连续最短路径法、放缩法或消圈法，均可以可靠、有效地得到最小费用最大流。

步骤S5：更新每个服务的访问信息，即每隔一段时间重新统计对每个服务的访问信息，采用增量式最小费用最大流算法，更新其对应的服务结点在边缘服务器结点上的位置。

具体的，在对模型求解算法的残余网络中，更新每个服务结点放置在各个边缘服务器结点上的访问成本以及迁移成本；根据统计的访问信息对残余网络中的服务结点以及边缘服务器结点进行相应的删添；利用增量式最小费用最大流算法进行快速求解，根据求解得到的最小费用最大流更新服务结点在边缘服务器结点上的位置。

本发明实施例中，由于用户对服务的访问模式会时常发生变化，故可以每隔一段时间对服务的访问信息进行重新统计和更新。按以往的方法，会选择重新按照步骤S3和S4的进行，但这求解时间往往会过长。本发明实施例利用增量式最小费用最大流算法，直接在求解算法上一次的残余网络中对相应服务结点与边进行修改，而不是从头开始构建最小费用最大流模型并求解，在修改后的残余网络上执行消圈法，可以将求解时间减少8-15倍。

步骤S6：对每个服务的访问信息进行实时的监控和统计，在访问信息的变化率超过设定阈值时，调整其对应的服务结点和边缘结点。

具体的，用户对服务结点的访问数量会出现突发的放量剧增和异常情况，通过监控器对访问信息进行实时的监控和统计。当这些监控或者统计的访问信息的变化率超过设定阈值时，就立即更新残余网络，即通过步骤S5中提出的增量式最小费用最大流算法进行求解，并对服务结点和边缘服务器结点进行相应的调整。

本发明实施例中，采用增量式最小费用最大流算法对每个服务结点的位置进行更新，参阅图4所示，具体包括如下：

步骤S51：用户对服务结点的访问量发生改变，并在满足设定条件时，更新服务结点的位置，具体包括：

步骤S511：当访问次数的变量大于预先学习得到的阈值时，在上一次的残余网络中，对与该服务结点相连边的权值进行修改；否则不修改，以此减少需要修改权值的边的数量。

本发明实施例中，考虑到每隔一段时间，对大部分服务结点的访问量会发生变化，又由于用户对一些服务结点的访问次数不会产生太大的变化，故可将访问次数与预先通过机器学习的方法学习得到的最优阈值进行比较，来确定是否需要修改边的权值。进一步的，利用机器学习的方法确定需要修改服务结点关联边权值的阈值，此阈值不是利用经验或者传统方法设定的，而是通过机器学习的方法以及以往的数据集训练得到最优阈值，此时得到的阈值能够适应用户的多种访问模式、大规模高频变化的网络结构以及各种异常情况，使得决策中心不会频繁改变残余网络结构，从而减少服务调整次数，提高服务质量。

步骤S512：在服务结点连向边缘服务器结点的边上添加迁移成本，并从费用改变的服务结点出发，重新寻找最小费用最大流。具体的，利用消圈法重新寻找最小费用最大流，由于是在上一阶段最小费用最大流的基础上出发，故能较之其他方案采用消圈法能更快寻找出最优方案。

步骤S513：根据所得到的最小费用最大流，对服务结点在边缘服务器结点上的位置进行更新。

本发明实施例中，假设上一次调整的部分残余网络见图5，此时服务结点N1到边缘服务器结点E1边的容量和权值为(0，100)，表示已将服务结点N1放置在边缘服务器结点E1上，并生成相应的反向边(1，-100)。同理服务结点Nn分配到了边缘服务器结点E2上。一段时间过后，用户对服务结点N1和Nn的访问次数发生了变化且访问次数大于阈值，则残余网络中相应的边需要修改，修改后的残余网络见图6。

通过图5可以看出，形成了N1→E2→Nn→E1→N1的负环，可利用消圈法从服务结点N1开始消圈，直至残余网络中不存在负圈，此时达到最大流最小费用。

步骤S52：服务结点的数量改变时，删除服务结点或增加服务结点，并更新服务结点的位置，具体包括：

当有服务结点减少时，在残余网络中删除所述服务结点以及相关的边；

当有服务结点增加时，在残余网络中添加所述服务结点以及相关的边，选择该服务结点到边缘服务器结点的最小费用路径，进行流的添加达到最大流，从而实现所有服务结点的放置；在服务结点连向边缘服务器结点的边上添加迁移成本；

从所述删减或增加的服务结点出发，并流向边缘服务器结点，寻找新的最小费用最大流，并对服务结点的进行迁移和放置完成更新。具体的，也采用消圈法寻找新的最小费用最大流。

步骤S53：边缘服务器承载量发生改变时，更新服务结点的位置，具体包括：

步骤S531：当边缘服务器的容量减小时，检查从该边缘服务器结点流出的流是否大于对应边减少后的容量，具体为：

若流出的流仍小于该边减少后的容量，则只改变残余网络中该边的容量，残余网络不进行调整；

若流出的流大于该边减少后的容量或者出现边缘服务器结点删除时，则将流入该边缘服务器结点中费用最大的边对应的流退回；从对应的边缘服务结点出发，选择到终结点的最短路径并增加流，并在服务结点连向边缘服务器结点的边上添加迁移成本；

从对应的服务结点出发，利用消圈法寻找新的最小费用最大流，并以此对服务结点的进行迁移和放置，完成对服务结点的位置进行更新；

步骤S532：当边缘服务器容量增加或有新的边缘服务器结点添加时，则对残余网络进行修改，并在服务结点连向边缘服务器结点的边上添加迁移成本；从对应的边缘服务器结点出发，利用消圈法寻找新的最小费用最大流，并对服务结点的位置进行更新。

本发明实施例提供的虚拟服务迁移方法，通过构建网络拓扑图，并生成最短路径距离矩阵，从而建立最小费用最大流模型。求解得到最小费用最大流，对服务结点进行迁移和放置，并在每隔一时间段，采用增量式最小费用最大流算法更新其对应的服务结点。对每个服务的访问信息进行实时的监控和统计，需要时调整其对应的服务结点和边缘结点。本发明实施例将边缘网络中的多种服务访问的总延迟问题转换成了最小费用最大流问题，并采用增量式最小费用最大流算法，得到使整体服务访问成本最小化的最优放置与迁移策略，同时能在很短时间内求解出策略，也能很好的应对服务访问数量突发的放量剧增和异常情况。

参阅图7所示，本发明实施例还提供一种基于增量式最小费用最大流的虚拟服务迁移系统，该系统包括如下：

拓扑图构建模块：用于根据边缘服务器的地理位置以及连接关系，构建网络拓扑图。

矩阵生成模块：用于计算每一对边缘服务器间的最短路径距离，并生成最短路径距离矩阵。

模型建立模块：用于根据所述距离矩阵并结合每个服务的访问信息，建立最小费用最大流模型，所述模型包括服务结点和边缘服务器结点。

服务结点迁移模块：用于对模型进行求解得到最小费用最大流，对服务结点进行迁移并将其放置在对应的边缘服务器结点上。

服务结点更新模块：用于更新每个服务的访问信息，采用增量式最小费用最大流算法更新服务结点的位置。

监控调整模块：用于对每个服务的访问信息进行实时的监控和统计，在访问信息的变化率超过设定阈值时，调整其对应的服务结点和边缘服务器结点。

具体地，本发明实施例提供的系统具体用于执行上述方法实施例，本发明实施例对此不再进行赘述。

图8为本发明实施例提供的一种电子设备的实体结构示意图，如图8所示，该电子设备可以包括：处理器(processor)301、通信接口(Communications Interface)302、存储器(memory)303和通信总线304，其中，处理器301，通信接口302，存储器303通过通信总线304完成相互间的通信。处理器301可以调用存储在存储器303上并可在处理器301上运行的计算机程序，以执行上述各实施例提供的方法，例如包括：

根据边缘服务器的地理位置以及连接关系，构建网络拓扑图；

计算每一对边缘服务器间的最短路径距离，并生成最短路径距离矩阵；

根据所述距离矩阵并结合每个服务的访问信息，建立最小费用最大流模型，所述模型包括服务结点和边缘服务器结点；

对模型进行求解得到最小费用最大流，对服务结点进行迁移并将其放置在对应的边缘服务器结点上；

更新每个服务的访问信息，采用增量式最小费用最大流算法，更新服务结点的位置；

对每个服务的访问信息进行实时的监控和统计，在访问信息的变化率超过设定阈值时，调整其对应的服务结点和边缘服务器结点。

此外，上述的存储器303中的逻辑指令可以通过软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明实施例的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

本发明实施例还提供一种非暂态计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现以执行上述各实施例提供的方法，例如包括：

根据边缘服务器的地理位置以及连接关系，构建网络拓扑图；

计算每一对边缘服务器间的最短路径距离，并生成最短路径距离矩阵；

根据所述距离矩阵并结合每个服务的访问信息，建立最小费用最大流模型，所述模型包括服务结点和边缘服务器结点；

对模型进行求解得到最小费用最大流，对服务结点进行迁移并将其放置在对应的边缘服务器结点上；

更新每个服务的访问信息，采用增量式最小费用最大流算法，更新服务结点的位置；

对每个服务的访问信息进行实时的监控和统计，在访问信息的变化率超过设定阈值时，调整其对应的服务结点和边缘服务器结点。

以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性的劳动的情况下，即可以理解并实施。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行各个实施例或者实施例的某些部分所述的方法。

本发明提供的基于增量式最小费用最大流的虚拟服务迁移方法及系统，解决了边缘网络中多服务的放置与迁移决策问题，改善最小服务访问总延迟的情况。在小规模网络中，其能在数十毫秒的时间内计算出服务结点的放置与迁移方案。对于大规模网络，若出现服务请求数量的突然增加以及高频不规则变化的情况，使用增量式算法也能在数十秒的时间内求解出放置和迁移策略，以此解决以往服务迁移算法的低效问题，能够使得用户访问服务的延迟大大降低，提升服务质量与用户体验。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。