Methods and systems for failure recovery in a virtual network environment

Patent metadata

Field	Value
Publication number	US-10505840-B2
Application number	US-201615267696-A
Country	US
Kind code	B2
Filing date	Sep 16, 2016
Priority date	May 17, 2016
Publication date	Dec 10, 2019
Grant date	Dec 10, 2019

Abstract

A method for failure recovery in a virtual network environment including a virtual network having virtual nodes and virtual links mapped onto substrate nodes and substrate paths, respectively, of a substrate network, the method comprising, in response to an indication of failure of at least one substrate node in the substrate network: re-mapping a virtual node mapped to a failed substrate node to a selected substrate node other than the failed substrate node; and re-mapping a virtual link mapped to a substrate path that involves the failed substrate node to a substrate path that does not involve the failed substrate node; wherein the re-mapping is carried out to achieve at least one re-mapping objective.

First claim

The invention claimed is:

1. A method for failure recovery in a virtual network environment including a plurality of embedded virtual networks each having virtual nodes and virtual links mapped onto substrate nodes and substrate paths, respectively, of a common substrate network, the method comprising, in response to failure of at least one of the substrate nodes, hereinafter a failed substrate node:
identifying those virtual networks, hereinafter failed virtual networks, of which one of the virtual nodes, hereinafter a failed virtual node, was previously mapped to the failed substrate node;
for a first one of the failed virtual networks:
selecting one of a plurality of candidate nodes as a recovery substrate node for the failed virtual network based on a remapping objective, each of the candidate nodes comprising a different one of the substrate nodes other than the failed substrate node, the remapping objective comprising prioritizing maximizing the number of virtual links of the failed virtual network that are capable of being remapped to substrate paths adjacent the candidate substrate node ultimately selected as the recovery substrate node over minimizing a total cost of provisioning bandwidth for remapping the virtual links of the failed virtual network;
remapping the failed virtual node of the failed virtual network to the recovery substrate node for the failed virtual network; and
remapping the virtual links of the failed virtual network that are adjacent the failed virtual node of the failed virtual network to substrate paths adjacent the recovery substrate node for the failed virtual network; and

repeating the selecting, remapping and remapping for at least a second one of the failed virtual networks.

2. The method defined in claim 1 , the method further comprising sorting the failed virtual networks into an ordered list, wherein the first one of the failed virtual networks comes before the second one of the failed virtual networks on the list.

3. The method defined in claim 2 , wherein said sorting the failed virtual networks into an ordered list is carried out according to bandwidth lost in the virtual links of each failed virtual network that are adjacent the failed virtual node of said failed virtual network.

4. The method defined in claim 2 , wherein as a result of the sorting, the bandwidth requirement of the virtual links of the first one of the failed virtual networks that are adjacent the failed virtual node of the first one of the failed virtual networks is lower than the bandwidth requirement of the virtual links of the next one of the failed virtual networks that are adjacent the failed virtual node of the next one of the failed virtual networks.

5. The method defined in claim 1 , wherein a given virtual link adjacent the failed virtual node of the failed virtual network is deemed capable of being remapped to a given substrate path adjacent the candidate substrate node if the given substrate path has sufficient available bandwidth to satisfy a bandwidth requirement of the given virtual link.

6. The method defined in claim 5 , wherein in the event that for each of two or more candidate substrate nodes, the number of virtual links adjacent the failed virtual node of the failed virtual network that are capable of being remapped to a substrate path adjacent the candidate substrate node is the greatest, the method comprises selecting, as the recovery substrate node, one of the two or more candidate substrate nodes for which a best effort objective is satisfied.

7. The method defined in claim 6 , wherein the best effort objective is a shortest path or lowest cost objective.

8. The method defined in claim 6 , wherein the best effort objective is a maximum flow objective.

9. A method for failure recovery in a virtual network environment including a virtual network having virtual nodes and virtual links mapped onto substrate nodes and substrate paths, respectively, of a substrate network, the method comprising, in response to failure of a plurality of the substrate nodes, hereinafter failed substrate nodes:
identifying those virtual nodes, hereinafter failed virtual nodes, that are mapped to the failed substrate nodes;
sorting the failed virtual nodes into an ordered list;
for a first one of the failed virtual nodes on the list:
selecting one of the substrate nodes other than the failed substrate nodes as a recovery substrate node for the failed virtual node based on a remapping objective;
selecting one of a plurality of candidate nodes as a recovery substrate node for the failed virtual node based on a remapping objective; each of the candidate nodes comprising a different one of the substrate nodes other than the failed substrate node, the remapping objective comprising prioritizing maximizing the number of virtual links adjacent the failed virtual node that are capable of being remapped to substrate paths adjacent the candidate substrate node ultimately selected as the recovery substrate node over minimizing a total cost of provisioning bandwidth for remapping the virtual links adjacent the failed virtual node;
remapping the failed virtual node to the recovery substrate node for the failed virtual node; and
remapping the virtual links that are adjacent the failed virtual node to substrate paths adjacent the recovery substrate node for the failed virtual node; and

repeating the selecting, remapping and remapping for at least a second one of the failed virtual nodes on the list.

10. The method defined in claim 9 , wherein the failed virtual nodes appear on the list in order of increasing bandwidth requirement, the second one of the failed virtual nodes having a greater bandwidth requirement than the first one of the failed virtual nodes.

11. The method defined in claim 9 , wherein the failed virtual nodes appear on the list in order of decreasing priority, the second one of the failed virtual nodes having a lower priority than the first one of the failed virtual nodes.

12. The method defined in claim 9 , wherein as a result of the sorting, the bandwidth requirement of the virtual links that are adjacent the first one of the failed virtual nodes is lower than the bandwidth requirement of the virtual links of the next one of the failed virtual nodes.

13. The method defined in claim 9 , wherein a given virtual link adjacent the failed virtual node is deemed capable of being remapped to a given substrate path adjacent the candidate substrate node if the given substrate path has sufficient available bandwidth to satisfy a bandwidth requirement of the given virtual link.

14. The method defined in claim 13 , wherein in the event that for each of two or more candidate substrate nodes, the number of virtual links adjacent the failed virtual node that are capable of being remapped to a substrate path adjacent the candidate substrate node is the greatest, the method comprises selecting, as the recovery substrate node, one of the two or more candidate substrate nodes for which a best effort objective is satisfied.

15. The method defined in claim 14 , wherein the best effort objective is a shortest path or lowest cost objective.

16. The method defined in claim 14 , wherein the best effort objective is a maximum flow objective.

17. The method defined in claim 9 , further comprising repeating the identifying, mapping and mapping for all of the failed virtual nodes in the virtual network.

18. A system for failure recovery in a virtual network environment including a plurality of virtual networks each having virtual nodes and virtual links mapped onto substr

Assignees

• SHAHRIAR Nashid
• Mitra Jeebak
• Ahmed Reaz
• Chowdhury Shihabur Rahman
• Boutaba Raouf
• Huawei Tech Canada Co Ltd

Inventors

• SHAHRIAR Nashid
• Mitra Jeebak
• Ahmed Reaz
• Chowdhury Shihabur Rahman
• Boutaba Raouf

Classifications

• H04L45/28 Primary

  using route fault recovery · CPC title

• H04L45/64

  using an overlay routing layer · CPC title

• H04L45/125

  based on throughput or bandwidth · CPC title

• H04L45/124

  using a combination of metrics · CPC title

• H04L45/22

  Alternate routing · CPC title