US 8,553,584 B2Granted

Automated traffic engineering for 802.1AQ based upon the use of link utilization as feedback into the tie breaking mechanism

AssigneeTelefonaktiebolaget L M Ericsson (publ)

InventorsDavid Ian Allan, Scott Andrew Mansfield

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method in an Ethernet Bridge for improved load distribution in an Ethernet network that includes the Ethernet Bridge including determining a first set of one or more shortest paths between each Ethernet Bridge pair in the Ethernet network, selecting at least a first shortest path, calculating a link utilization value for each link of the Ethernet network, determining a second set of one or more shortest paths between each Ethernet Bridge pair in the Ethernet network, generating a path utilization value for each shortest path, selecting a second shortest path on the basis of said path utilization value, whereby the selection of the second shortest in light of path utilization minimizes the standard deviation of load distribution across the entire Ethernet network.

Claims14

Dependent claims

A method in an Ethernet Bridge for improved load distribution in an Ethernet network that includes the Ethernet Bridge, wherein the Ethernet Bridge is one of a plurality of Ethernet Bridges in the Ethernet network each of which implement a common algorithm tie-breaking process to produce minimum cost shortest path trees, the Ethernet Bridge includes a database to store the topology of the Ethernet network, wherein the topology of the Ethernet Network includes a plurality of nodes and links between the nodes, the method comprising the steps of:

determining a first set of one or more shortest paths between each Ethernet Bridge pair in the Ethernet network by executing a shortest path search algorithm on the topology of the Ethernet network stored in the database;
selecting at least a first shortest path from the first set of shortest paths for each Ethernet Bridge pair, by applying the common algorithm tie-breaking process;
calculating a link utilization value for each link of the Ethernet network based on the count of shortest paths selected that transit each link;
determining a second set of one or more shortest paths between each Ethernet Bridge pair in the Ethernet network by executing the shortest path search algorithm on the topology of the Ethernet network stored in the database;
generating a path utilization value for each shortest path in the second set of one or more shortest paths based on link utilization values corresponding to each shortest path;
selecting a second shortest path from the second set of one or more shortest path on the basis of said path utilization value, wherein the selecting utilizes the common algorithm tie-breaking process when multiple shortest paths having equal path utilization values are present in the set of one or more shortest paths;
and
storing at least the first shortest path and the second shortest paths for each Ethernet Bridge pair in a forwarding database, wherein the forwarding database indicates where to forward traffic incoming to the Ethernet Bridge,
whereby the selection of the second subsets in light of path utilization minimizes the standard deviation of load distribution across the entire Ethernet network.

6 more elements

An Ethernet Bridge for improved load distribution in an Ethernet network that includes the Ethernet Bridge, wherein the Ethernet Bridge is one of a plurality of Ethernet Bridges in the Ethernet network, wherein a topology of the Ethernet Network includes a plurality of nodes and links between the nodes, the Ethernet Bridge comprising:

a topology database to store link information for each link in the Ethernet network;
a forwarding database to store forwarding information for each port of the Ethernet Bridge, wherein the forwarding database indicates where to forward traffic incoming to the Ethernet Bridge;
a control processor coupled to the topology database and the forwarding database, the control processor configured to process data traffic, wherein the control processor comprises:
a shortest path search module configured to determine at least one shortest path between each Ethernet Bridge pair in the Ethernet network by executing a shortest path search algorithm on the topology database, wherein the shortest path search module is configured to send, for each of the Ethernet Bridge pairs with a plurality of equal cost shortest paths, the equal costs shortest paths to a load distribution module;
a sorting module configured to rank each of the plurality of equal cost shortest paths based on a path utilization value derived from link utilization values associated with each path in the plurality of equal cost shortest paths;
and
the load distribution module configured to select, from the plurality of equal cost shortest paths, a first subset of the plurality of equal cost shortest paths for that Ethernet Bridge pair to be used to share data traffic load between the Ethernet Bridge pair and to select, based on the path utilization value, a second subset from the plurality of equal cost shortest paths for that Ethernet Bridge pair to be used to share data traffic load with the first subset for that Ethernet Bridge pair, whereby the selection of the second subset in light of the path utilization value minimizes the standard deviation of load distribution across the entire Ethernet network.

4 more elements

Dependencies are inferred from the claim text.