Calculation of a lowest cost path

Patent metadata

Field	Value
Publication number	US-10009254-B2
Application number	US-201615159596-A
Country	US
Kind code	B2
Filing date	May 19, 2016
Priority date	May 10, 2016
Publication date	Jun 26, 2018
Grant date	Jun 26, 2018

Abstract

A method in a flow controller for selecting optimal path is provided. A plurality of potential flow paths in the network for a particular pair of source and destination switch ports is determined in a flow controller. A plurality of cost factors associated with each of the plurality of potential flow paths is identified. Individual cost values are determined for each of the identified plurality of cost factors for each of the plurality of potential flow paths by multiplying the identified cost factors by a stratification factor. A single cost value for each of the plurality of potential flow paths is determined based on the determined individual cost values. One of the potential flow paths is selected in the flow controller for the particular pair of source and destination switch ports based upon the determined single cost value.

First claim

What is claimed is:

1. A method in a flow controller for automatically selecting an optimal one of a plurality of paths between two ports, the method comprising:
identifying, in the flow controller, a plurality of potential paths from a source port to a destination port through a graph representing a network, each of the potential paths including a plurality of vertices and a plurality of edges connecting the plurality of vertices, the plurality of vertices representing a plurality of network nodes and the plurality of edges representing a plurality of network links interconnecting the plurality of network nodes;
assigning edge weights to edges of the plurality of potential paths based on predefined path optimization criteria;
determining, in the flow controller, a cost value for each of the plurality of potential paths based on the assigned edge weights; and
selecting, in the flow controller, one of the plurality of potential flow paths from the source port to the destination port based upon the determined cost value wherein the plurality of network links comprises at least one of cross-switch links and/or backplane links operating either in guaranteed bandwidth mode or aggregated bandwidth mode, and wherein the predefined path optimization criteria includes a number of data transmission hops over a cross-switch link included in a potential path, a number of data transmission hops over a back plane link, bandwidth of an aggregated link included in a potential path and bandwidth of a guaranteed link included in a potential path.

2. The method as recited in claim 1 , further comprising, subsequently to identifying the plurality of potential paths, removing duplicate paths from the plurality of potential paths, wherein a potential path is a duplicate path if it shares a particular vertex with another path and if one of another path's edges to the particular vertex represents an active link assigned to carry traffic from the same source port.

3. The method as recited in claim 1 , further comprising prioritizing the predefined path optimization criteria based on predefined importance of each path optimization criterion.

4. The method as recited in claim 1 , wherein assigning edge weights to edges further comprises:
assigning a plurality of weight values to each edge of the plurality of potential paths, wherein each of the plurality of weights corresponds to one of the predefined path optimization criteria; and
determining a single weight value for each edge of the plurality of potential flow paths based on the determined plurality of weights.

5. The method as recited in claim 1 , wherein assigning a plurality of weight values further comprises stratifying the plurality of weight values so that each of the plurality of weight values falls into a distinct non-overlapping range of values.

6. The method as recited in claim 1 , further comprising designating a connection between the source port and the destination port as failed if the selected one of the plurality of potential flow paths includes an edge representing an unavailable link or if the selected one of the plurality of potential flow paths includes more than a predefined maximum number of data transmission hops over a cross switch link.

7. The method as recited in claim 4 , wherein a weight value corresponding to bandwidth of an aggregated link is assigned so that an aggregated link having highest percentage of bandwidth remaining after a potential connection between the source port and the destination port is made will have a lowest weight value.

8. The method as recited in claim 4 , wherein a weight value corresponding to bandwidth of a guaranteed link is assigned so that a guaranteed link having least bandwidth remaining after a potential connection between the source port and the destination port is made will have a lowest weight value.

9. A method in a flow controller for automatically selecting an optimal one of a plurality of paths between two ports, the method comprising:
identifying, in the flow controller, a plurality of potential paths from a source port to a destination port through a graph representing a network, each of the potential paths including a plurality of vertices and a plurality of edges connecting the plurality of vertices, the plurality of vertices representing a plurality of network nodes and the plurality of edges representing a plurality of network links interconnecting the plurality of network nodes;
assigning edge weights to edges of the plurality of potential paths based on predefined path optimization criteria wherein assigning edge weights to edges includes assigning a plurality of weight values to each edge of the plurality of potential paths, wherein each of the plurality of weights corresponds to one of the predefined path optimization criteria and determining a single weight value for each edge of the plurality of potential flow paths based on the determined plurality of weights wherein a weight value corresponding to bandwidth of an aggregated link is assigned so that an aggregated link having highest percentage of bandwidth remaining after a potential connection between the source port and the destination port is made will have a lowest weight value;
determining, in the flow controller, a cost value for each of the plurality of potential paths based on the assigned edge weights and
selecting, in the flow controller, one of the plurality of potential flow paths from the source port to the destination port based upon the determined cost value.

10. The method as recited in claim 9 , further comprising, subsequently to identifying the plurality of potential paths, removing duplicate paths from the plurality of potential paths, wherein a potential path is a duplicate path if it shares a particular vertex with another path and if one of another path's edges to the particular vertex represents an active link assigned to carry traffic from the same source port.

11. The method as recited in claim 9 , wherein the plurality of network links comprises at least one of cross-switch links and/or backplane links operating either in guaranteed bandwidth mode or aggregated bandwidth mode, and wherein the predefined path optimization criteria includes a number of data transmission hops over a cross-switch link included in a potential path, a number of data transmission hops over a back plane link, bandwidth of an aggregated link included in a potential path and bandwidth of a guaranteed link included in a potential path.

12. The method as recited in claim 11 , further comprising prioritizing the predefined path optimization criteria based on predefined importance of each path optimization criterion.

13. The method as recited in claim 9 , wherein assigning a plurality of weight values further comprises stratifying the plurality of weight values so that each of the plurality of weight values falls into a distinct non-overlapping range of values.

14. The method as recited in claim 11 , further comprising designating a connection between the source port and the destination port as failed if the selected one of the plurality of potential flow paths includes an edge representing an unavailable link or if the selected one of the plurality of potential flow paths includes more than a predefined maximum number of data transmission hops over a cross switch link.

15. The method as recited in claim 9 , wherein a weight value corresponding to bandwidth of a guaranteed link is assigned so that a guaranteed link having least bandwidth remaining after a potential connection between the source port and the destination port is made will have a lowest weight value.

Assignees

• Netscout Systems Inc

Inventors

• Greenbaum David A
• Rosenberry Steven M
• Toich Peter D
• Curtis John C

Classifications

• H04L45/122

  by minimising distances, e.g. by selecting a route with minimum of number of hops · CPC title

• H04L45/38

  Flow based routing · CPC title

• H04L45/12

  Shortest path evaluation · CPC title

• H04L45/125

  based on throughput or bandwidth · CPC title

• H04L45/124 Primary

  using a combination of metrics · CPC title