Metric biasing for bandwidth aware tie breaking

Patent metadata

Field	Value
Publication number	US-2015156106-A1
Application number	US-201314101235-A
Country	US
Kind code	A1
Filing date	Dec 9, 2013
Priority date	Jul 24, 2013
Publication date	Jun 4, 2015
Grant date	—

Abstract

A method is implemented in a network element for modifying the characteristics of tree construction for use in virtual network connectivity in a network that includes the network element. A virtual network is associated with a set of virtual network attachment points that are mapped to network elements in a topology of the network where the virtual network is individually associated with an equal cost tree (ECT) set. The method generates individual ECT sets to interconnect sets of virtual network attachment points for connectivity establishment and maintenance of the connectivity in the network. The method modifies link metrics across the topology of the network to be used for computing an ECT set to bias a tie-breaking process for selecting between equal cost paths toward either producing minimal cost shortest path multicast trees or maximizing unicast path diversity in the multiple ECT sets that are generated.

First claim

What is claimed is:

1 . A method in a network element for modifying the characteristics of tree construction for use in virtual network connectivity in a network that includes the network element, a virtual network is associated with a set of virtual network attachment points that are mapped to network elements in a topology of the network where the virtual network is individually associated with an equal cost tree (ECT) set, the method to generate individual ECT sets to interconnect sets of virtual network attachment points for connectivity establishment and maintenance of the connectivity in the network, the method to modify link metrics across the topology of the network to be used for computing an ECT set to bias a tie-breaking process for selecting between equal cost paths toward either producing minimal cost shortest path multicast trees or maximizing unicast path diversity in the multiple ECT sets that are generated, the method comprising the steps of:
selecting the virtual network that requires connectivity in the network; computing shortest path trees to interconnect the set of virtual network attachment points for the virtual network without resolving ties between the shortest path trees; determining which nodes of the shortest path trees for the virtual network are candidate nodes for metric biasing using metric propagation; implementing metric biasing using metric propagation based on biasing configuration; and tie-breaking all multi-path possibilities in the shortest path trees to produce the set of ECTs for the virtual network and the set of virtual network attachment points.

2 . The method of claim 1 , further comprising the step of:
computing an initial set of ECTs based on the network topology for another virtual network and another set of virtual network attachment points.

3 . The method of claim 2 , wherein computing the initial set of ECTs based on the network topology for an aggregate of a set of virtual network attachment points that each require connectivity.

4 . The method of claim 1 , wherein determining which nodes are candidate nodes further comprising the step of:
identifying candidate nodes that do not have virtual network attachment points in a current set of virtual networks and have a single outgoing link used exclusively to reach at least one virtual network attachment point.

5 . The method of claim 4 , wherein determining which nodes are candidate nodes further comprises the step of:
identifying the candidate nodes where there are incoming links with asymmetrical subsets of paths to virtual network attachment points exclusively reachable by the outgoing link amongst the shortest path trees.

6 . The method of claim 1 , wherein implementing metric biasing further comprises the step of:
setting an incoming link metric to an outgoing link metric for an incoming link having a smallest subset of paths to destination virtual network attachment points via the outgoing link, where the outgoing link metric is less desirable than the incoming link metric, wherein the setting biases the tie-breaking for the ECT set towards minimum cost multicast trees.

7 . The method of claim 1 , wherein implementing metric biasing further comprises the step of:
setting an incoming link metric to an outgoing link metric for an incoming link having a largest subset of paths to destination virtual network attachment points via the outgoing link, where the outgoing link metric is less desirable than the incoming link metric, wherein the setting biases the tie-breaking of equal cost paths in the ECT set towards maximum unicast diversity.

8 . The method of claim 1 , wherein the link metric is the available link bandwidth defined as the net remaining bandwidth after all previous ECT placement has occurred.

9 . The method of claim 1 wherein the virtual network is one of a set of virtual networks associated with a single aggregated tree set.

10 . The method of claim 1 , where the network element is in a distributed routing system that applies the method as an individual step in a particular computation order used to converge the network.

11 . The method of claim 1 , wherein an initial tie-breaker of the path selection process is a sum of link metrics.

12 . A network element for implementing a method of modifying the characteristics of tree construction for use in virtual network connectivity in a network that includes the network element, a virtual network is associated with a set of virtual network attachment points that are mapped to network elements in a topology of the network where the virtual network is individually associated with an equal cost tree (ECT) set, the method to generate individual ECT sets to interconnect sets of virtual network attachment points for connectivity establishment and maintenance of the connectivity in the network, the method to modify link metrics across the topology of the network to be used for computing an ECT set to bias a tie-breaking process for selecting between equal cost paths toward either producing minimal cost shortest path multicast trees or maximizing unicast path diversity in the multiple ECT sets that are generated, the network element comprising:
a database to store the topology of the network; and a processor communicatively coupled to the database, the processor configured to execute a metric biasing module, the metric biasing module configured to compute shortest path trees to interconnect the set of virtual network attachment points for the virtual network without resolving ties between the shortest path trees, to determine which nodes of the shortest path trees for the virtual network are candidate nodes for metric biasing using metric propagation, to implement metric biasing using metric propagation based on biasing configuration, and to tie-break all multi-path possibilities in the shortest path trees to produce the set of ECTs for the service and the set of virtual network attachment points.

13 . The network element of claim 12 , wherein the metric biasing module is further configured to compute an initial set of ECTs based on the network topology for another virtual network and another set of virtual network attachment points.

14 . The network element of claim 13 , wherein computing the initial set of ECTs based on the network topology is for an aggregate of a set of virtual network attachment points that each require connectivity.

15 . The network element of claim 12 , wherein the metric biasing module is further configured to identify candidate nodes that do not have virtual network attachment points in a current set of virtual networks and have a single outgoing link used exclusively to reach at least on virtual network attachment point.

16 . The network element of claim 15 , wherein the metric biasing module is further configured to identify the candidate nodes where there are incoming links with asymmetrical subsets of paths to virtual network attachment points exclusively reachable by the outgoing link amongst the shortest path trees.

17 . The network element of claim 12 , wherein the metric biasing module is further configured to set an incoming link metric to an outgoing link metric for an incoming link having a smallest subset of paths to destination virtual network attachment points via the outgoing link, where the outgoing link metric is less desirable than the incoming link metric, wherein the setting biases the tie-breaking for the ECT set towards minimum cost multicast trees.

18 . The network element of claim 12 , wherein the metric biasing module i

Assignees

• Ericsson Telefon Ab L M

Inventors

• Allan David Ian

Classifications

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/123 Primary

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title

• H04L45/24

  Multipath · CPC title

• H04L45/22

  Alternate routing · CPC title