一种基于多商品流问题模型的虚拟网快速愈合方法

摘要

本发明公开了一种基于多商品流问题模型的虚拟网快速愈合方法，包括底层网络供应商和服务提供商进行通信的控制协议，失效虚拟网映射的恢复过程，未能成功恢复的虚拟网映射的应对策略，以及记录物理网中各结点链路的故障次数方法。本发明很好地适应了当今互联网环境，其运行过程高效，迅速；其运行结果很好的改善了网络的负载均衡性，并具有很高的恢复成功率。

说明书

技术领域

本发明涉及一种在虚拟网映射失效之后，利用多商品流问题的解进行恢复的方法，尤其涉及一种基于多商品流问题模型的虚拟网快速愈合方法。

背景技术

互联网在过去的几十年中取得了巨大的成功，它为人们提供了一个全新的交换信息、接受信息的平台。它的广泛普及，促进了网络技术的发展和应用。然而，规模巨大的网络同时也限制了它将来的发展。比如，以当前的网络的规模和大小，部署新的网络技术无疑十分困难。网络的虚拟化技术为允许网络的多体系结构提供了一个有力的解决方案。网络虚拟化是指通过虚拟链路将虚拟路由器连接起来，在这个虚拟的网络拓扑上使用不同的协议为用户提供一组服务。网络服务提供商所提供服务的多样化促进了虚拟网的发展。虚拟网正被广泛部署在物理网。

近年来，网络虚拟化技术高速发展，并随之产生了一系列成熟的虚拟网构建算法，这些算法多用于在同一个底层网络拓扑上同时运行多个虚拟网应用，从而极大的提高了网络资源的利用率。然而，在这些构建算法成熟发展的背后，却带来了众多来自虚拟网抗毁性方面的挑战。

发明内容

本发明的目的在于针对现有技术的不足，提供一种基于多商品流问题模型的虚拟网快速愈合方法。

本发明的目的是通过以下技术方案来实现的：一种基于多商品流问题模型的虚拟网快速愈合方法，包括以下步骤：

（1）服务供应商在提供各种虚拟网络服务的过程中，通过用户的反馈信息获知出现故障的虚拟网，并通知底层供应商检测造成这些虚拟网故障的原因。

（2）底层供应商接收到服务供应商的请求后，开始检测并判断虚拟网故障时由物理结点故障造成还是由物理链路故障造成，再根据相应的情况进行虚拟网的恢复工作。

（3）由于底层网络资源限制，未能被实时恢复的虚拟网被加入一个基于“可恢复优先”原则的队列。“可恢复优先”原则是指，如果队首的虚拟网映射能在当前的InP检测周期T内被恢复，则将其恢复并弹出队列；如果不能被恢复，则将其移动至队列尾部。InP检测周期T指底层供应商会定期检测排在队列首部的若干个虚拟网，并进行恢复。

（4）将发生故障的物理结点或链路加入一个基于“最近最少失效”原则的队列，用于计算这些结点或链路的可靠性。“最近最少失效”原则是指将最近一次发生故障的物理部件插入队列顶端。

（5）底层供应商将恢复成功的虚拟网返回给服务提供商，服务提供商再将此被恢复的虚拟网提供给需要此服务的用户。

进一步地，所述步骤（2）具体如下：

（A）如果是物理链路故障，先统计出所有被映射在该链路上的所有                                                条虚拟链路，，…，，并将这些虚拟链路的带宽需求转化为流量，即。然后在该物理链路的结点两端解一个包含这个流量的多商品流问题，最后将这个网络流所经过的路径分别加入对应的失效虚拟网中，从而完成整个恢复工作。

（B）如果是物理结点故障，先统计出所有被映射在该结点上的所有个虚拟结点，，…，，并将这些虚拟结点重新映射到物理网络中结点价值最高的一个物理结点，其中由结点的资源和可靠性决定。在重映射完一个虚拟结点之后，再恢复原来与该虚拟结点邻接的所有虚拟结点之间的虚拟链路。

本发明的有益效果是，本发明的方法很好地适应了当今互联网环境，其运行过程高效，迅速；其运行结果很好地改善了网络的负载均衡性，并具有很高的恢复成功率。

附图说明

图1是由物理链路引起的虚拟网映射失效的恢复示意图；

图2是由物理节点引起的虚拟网映射失效的恢复示意图；

图3是失效虚拟网队列的管理示意图；

图4是故障物理结点链路的记录示意图。

具体实施方式

本发明基于多商品流问题模型的虚拟网快速愈合方法，使用最具成功率的方法来对当前的虚拟网映射进行重映射，并充分考虑到了物理网的负载均衡性。包括底层网络供应商（InP）和服务提供商（SP）进行通信的控制协议，失效虚拟网映射的恢复（重映射）过程，未能成功恢复的虚拟网映射的应对策略，以及记录物理网中各结点链路的故障次数方法。

下面根据附图详细说明本发明，本发明的目的和效果将变得更加明显。

本发明基于多商品流问题模型的虚拟网快速愈合方法，包括以下步骤：

1、服务供应商（SP）在提供各种虚拟网络服务的过程中，通过用户的反馈信息获知出现故障的虚拟网，并通知底层供应商（InP）检测造成这些虚拟网故障的原因。

2、底层供应商（InP）在接收到服务供应商（SP）的请求后，开始检测并判断虚拟网故障时由物理结点故障造成还是由物理链路故障造成，再根据相应的情况进行虚拟网的恢复工作。具体如下：

（1）如果是物理链路故障，先统计出所有被映射在该链路上的所有条虚拟链路，，…，，并将这些虚拟链路的带宽需求转化为流量，即。然后在该物理链路的结点两端解一个包含这个流量的多商品流问题，最后将这个网络流所经过的路径分别加入对应的失效虚拟网中，从而完成整个恢复工作。例：如图1，物理链路BF发生故障，导致运行在其上的带宽需求为2的虚拟链路映射失效，我们在结点B和结点F之间解一个流量为2的多商品流问题，将映射在链路BF上的虚拟链路重映射到物理路径BCF，从而恢复了整个虚拟网映射。

（2）如果是物理结点故障，先统计出所有被映射在该结点上的所有个虚拟结点，，…，，并将这些虚拟结点重新映射到物理网络中结点价值最高的一个物理结点，其中由结点的资源和可靠性决定（可靠性具体计算方法见步骤4）。在重映射完一个虚拟结点之后，再恢复原来与该虚拟结点邻接的所有虚拟结点之间的虚拟链路，方法同步骤2.1。例：如图2，虚拟结点H发生故障，我们先将映射在H上的虚拟结点重映射到具有最高结点价值的物理结点B，再将原先映射在物理链路CFH上的虚拟链路重映射到物理链路CB，将原先映射在物理链路GH上的虚拟链路重映射到物理路径GFB，从而恢复了整个虚拟网映射。

3、由于底层网络资源限制，未能被实时恢复的虚拟网被加入一个基于“可恢复优先”原则的队列。“可恢复优先”原则是指，如果队首的虚拟网映射能在当前的InP检测周期T内被恢复，则将其恢复并弹出队列；如果不能被恢复，则将其移动至队列尾部。InP检测周期T指底层供应商会定期检测排在队列首部的若干个虚拟网，并进行恢复。例：如图3，一个InP检测周期T可以恢复2个虚拟网。在第一个周期T内，虚拟网可以被恢复，虚拟网不能被恢复，则将恢复并弹出，移动置队列尾部；在第二个周期T内，虚拟网和都可以被恢复，则将这2个虚拟网映射恢复并弹出，同时又加入了一个新的未能被及时恢复的虚拟网加入队列尾部。

4、将发生故障的物理结点或链路加入一个基于“最近最少失效”原则的队列，用于计算这些结点或链路的可靠性。“最近最少失效”原则是指将最近一次发生故障的物理部件插入队列顶端。例，如图4，队列中保存着3个故障或者曾经发生故障的物理部件：结点和链路，。在时刻，再次发生故障，则将移动置顶端；在时刻，结点发生故障，则将插入队列顶端；在时刻，再次发生故障，则将移动置顶端。结点或链路的可靠性，其中表示结点或链路在队列中的位置（如图4第一幅，，，），表示物理网络中物理结点的个数，表示物理链路的个数。根据可靠性的计算方法可知，离队列顶端越近，可靠性越低；离队列顶端越远，可靠性越高。

5、在完成上述4个步骤之后，底层供应商（InP）将恢复成功的虚拟网返回给服务提供商（SP），服务提供商再将此被恢复的虚拟网提供给需要此服务的用户。