Network path selection based on bandwidth

A method of determining a path through a network from a source node to a destination node via intermediate nodes, the source node, the destination node and the intermediate nodes being interconnected by a plurality of links, each of the plurality of links having a first metric value and a link bandwidth metric value, the method comprising:

• a) determining a path from the source node, the path ending at a current node;
• b) forming expanded paths from the path using selected links from the current node, each of the expanded paths having a path metric value based on the first metric values of the links in each of the expanded paths;
• c) forming a first set of paths from expanded paths having a common end node based on the path metric value for each expanded path, each path in the first set having a path bandwidth metric value;
• d) determining a second set of paths formed from paths in the first set having a desirable path bandwidth metric value;
• e) determining a first common node between two randomly chosen paths from the second set, the first common node being an intermediate node for each of the two chosen paths, a segment of each of the two chosen paths between the common end node and the first common node defining a unique segment for each of the two paths, each unique segment having a segment bandwidth metric value;
• f) determining a path from the two chosen paths based on a desirable segment bandwidth metric value from the segment bandwidth metric value for each of the two unique segments;
• g) repeating steps e) and f) retaining the determined path as one of the two chosen paths until all paths in the second set have been chosen;
• and
• h) repeating steps a) to g) to further expand the determined path at each intermediate node until the end node for the determined path is the destination node.

A system for determining a path through a network from a source node to a destination node via intermediate nodes, the source node, the destination node and the intermediate nodes being interconnected by a plurality of links, each of the plurality of links having a first metric value and a link bandwidth metric value, the system comprising:

• a data storage for holding path information for a path between the source node and a current node;
• a link search mechanism to select links from the current node;
• a controller operably connected to the data storage and the link search mechanism to locate and expand a path from the source node to the current node using the selected links to form expanded paths, each of the expanded paths having a path metric value based on the metric values for links in the expanded path and a path bandwidth metric value, and to determine a first set of paths having a common end node according to the path metric value for each of the expanded paths;
• a path bandwidth analysis mechanism to determine those paths in the first set having a desirable path bandwidth metric value;
• a segment determination mechanism to determine a first common node between two chosen paths from those paths having a desirable path bandwidth metric value, the first common node being an intermediate node for each of the two chosen paths, a segment of each of the two chosen paths between the common end node and the first common node defining a unique segment for each of the two paths, each unique segment having a segment bandwidth metric value;
• and
• a segment bandwidth determination mechanism to determine the determined path from the two chosen paths based on a desirable segment bandwidth metric value from the segment bandwidth metric value for each of the two unique segments.

A computer readable medium having stored thereon computer-executable instructions for selecting a path from a first set of paths each path having a similar path metric value and a path bandwidth metric value, each path extending through a network from a common source node to a common end node via intermediate nodes, the common source node, the common end node and the intermediate nodes being interconnected by a plurality of links, the method comprising:

• a) determining a second set of paths formed from paths in the first set having a desirable path bandwidth metric value;
• b) determining a first common node between two chosen paths from the second set, the first common node being an intermediate node for each of the two chosen paths, a segment of each of the two chosen paths between the common end node and the first common node defining a unique segment for each of the two paths each unique segment having a segment bandwidth metric value;
• c) determining a path from the two chosen paths based on a desirable segment bandwidth metric value from the segment bandwidth metric value for each of the two unique segments;
• and
• d) repeating steps b) and c) retaining the determined path as one of the two chosen paths until all paths in the second set of paths have been chosen.

A computer readable medium having stored thereon computer-executable instructions for determining a path through a network from a source node to a destination node via intermediate nodes, the source node, the destination node and the intermediate nodes being interconnected by a plurality of links, each of the plurality of links having a first metric value and a link bandwidth metric value, the method comprising:

• a) determining a path from the source node, the path ending at a current node;
• b) forming expanded paths from the path using selected links from the current node, each of the expanded paths having a path metric value based on the first metric values of the links in each of the expanded paths;
• c) forming a first set of paths from expanded paths having a common end node based on the path metric value for each expanded path, each path in the first set having a path bandwidth metric value;
• d) determining a second set of paths formed from paths in the first set having a desirable path bandwidth metric value;
• e) determining a first common node between two randomly chosen paths from the second set, the first common node being an intermediate node for each of the two chosen paths, a segment of each of the two chosen paths between the common end node and the first common node defining a unique segment for each of the two paths, each unique segment having a segment bandwidth metric value;
• f) determining a path from the two chosen paths based on a desirable segment bandwidth metric value from the segment bandwidth metric value for each of the two unique segments;
• g) repeating steps e) and f) retaining the determined path as one of the two chosen paths until all paths in the second set have been chosen;
• and
• h) repeating steps a) to g) to further expand the determined path at each intermediate node until the end node for the determined path is the destination node.