Method and apparatus for selecting an optimal path from a path-starting node of a network to a path-ending node of the network
In accordance with one aspect of the present invention, a method provides a circuit from a first customer location to a second customer location. The method includes selecting a path-starting node from a network of nodes, and selecting a path-ending node from the network of nodes. The path-starting node is connectable to the first customer location, and the path-ending node is connectable to the second customer location. The method also includes selecting at least one subset of files from a database containing a set of files. Each file of the set of files contains segment data pertaining to a segment that connects a pair of nodes within the network. Each of the at least one subset contains data pertaining to a path from the path-starting node to the path-ending node. If more than one subset of files is selected, selecting an optimal path corresponding to an optimal subset of files.
1 . A method of providing a circuit from a first customer location to a second customer location, the method comprising:
selecting (a) a path-starting node that is connectable to the first customer location, and (b) a path-ending node that is connectable to the second customer location from a database containing a set of files, each file of the set of files containing segment data pertaining to a segment that connects a pair of nodes within the network, selecting at least one subset of files, such that each of the at least one subset contains data pertaining to a path from the path-starting node to the path-ending node; and if more than one subset of files is selected, selecting an optimal path corresponding to an optimal subset of files.
2 . The method of claim 1 , wherein selecting at least one subset of files includes:
(a) determining a plurality of 1st-tier paths such that each 1st-tier path of the plurality of 1st-tier paths is a 1st-tier segment from the path-starting node to a 1st-tier node adjacent to the path-starting node within the network, the 1st-tier segment being of a database of segments, each of the 1st-tier nodes having a distance of one segment from the path-starting node;
(b) identifying a plurality of (n+1) th -tier nodes, each of the (n+1) th -tier nodes having a distance of n+1 segments from the path-starting node if none of the(n+1) th -tier nodes is the path ending node;
determining a plurality of paths each of which has n+1 segments and includes (i) a path that has n segments, from the path-starting node to an nth-tier node and (ii) an (n+1) th segment from the n th -tier node to an (n+1) th -tier node adjacent to the n th -tier node within the network, the (n+1) th -tier segment being of the database of segments;
(c) determining a plurality of path costs, each path cost of the plurality of path costs corresponding to a path that includes both the path-starting node and the path-ending node if at least one node of at least one path is the path-ending node;
(d) determining a plurality of optimal paths from the plurality of path costs
3 . The method of claim 2 , further comprising:
counting segments in each path, wherein the path cost of each path is equal to a number of segments in the path, wherein the plurality of optimal paths is determined such that no path in the network from the path-starting node to the path-ending node has fewer segments than any optimal path in the plurality of optimal paths.
4 . The method of providing a circuit from a first customer location to a second customer location of claim 2 , further comprising:
excluding from the plurality of optimal paths any path that has a path facility type less than a desired minimum capacity, including:
for each segment that has a segment facility type and that is included in a path lacking a path facility type, setting the path facility type to the segment facility type; and
for each segment that has a segment facility type and that is included in a path having a path facility type, re-setting the path facility type to the segment facility type if the path facility type is greater than the segment facility type;
excluding from the plurality of optimal paths any path that has a path facility type less than the desired minimum capacity.
5 . The method of claim 4 , wherein:
the database includes a TRIP file for each segment, the TRIP file including a first node and a second node.
6 . The method of claim 5 , wherein:
the TRIP file further includes a segment facility type.
7 . The method of claim 4 , further comprising:
aggregating loads, including:
determining a load availability of each path in the plurality of optimal paths; and
selecting as the optimal path the path for which the load availability is greatest.
8 . The method of providing a circuit from a first customer location to a second customer location of claim 4 , further comprising:
balancing loads, including:
determining a load availability of each path in the plurality of optimal paths; and
selecting as the optimal path the path for which the load availability is least.
9 . A computer-readable medium containing a set of instructions that when executed by a computer cause the computer to execute a method, the method including selecting:
(a) a path-starting node that is connectable to the first customer location, and
(b) a path-ending node that is connectable to the second customer location, the path starting node and the path-ending node being of a network of nodes; and
selecting at least one subset of files from a database containing a set of files, such that:
each file of the set of files contains segment data pertaining to a segment that connects a pair of nodes within the network,
each of the at least one subset contains data pertaining to a path from the path-starting node to the path-ending node; and
selecting an optimal path corresponding to an optimal subset of files, if more than one subset of files is selected.
10 . A computer-readable medium of claim 9 , wherein selecting a subset of files includes:
(a) determining a plurality of 1st-tier paths such that each 1st-tier path of the plurality of 1st-tier paths is a 1st-tier segment from the path-starting node to a 1st-tier node adjacent to the path-starting node within the network, the 1st-tier segment being of a database of segments, each of the 1st-tier nodes having a distance of one segment from the path-starting node;
(b) while none of the n th -tier nodes is the path-ending node,
identifying a plurality of (n+1) th -tier nodes, each of the (n+1) th -tier nodes having a distance of n+1 segments from the path-starting node;
determining a plurality of paths each of which has n+1 segments and includes (i) a path that has n segments, from the path-starting node to an n th -tier node and (ii) an (n+1) th segment from the n th -tier node to an (n+1) th -tier node adjacent to the n th -tier node within the network, the (n+1) th -tier segment being of the database of segments;
(c) if at least one node of at least one path is the path-ending node, determining a plurality of path costs, each path cost of the plurality of path costs corresponding to a path that includes both the path-starting node and the path-ending node;
(d) from the plurality of path costs, determining a plurality of optimal paths.
11 . The computer-readable medium of claim 11 , wherein the set of instructions also includes at least one instruction for:
counting segments in each path, wherein the path cost of each path is equal to a number of segments in the path, wherein the plurality of optimal paths is determined such that no path in the network from the path-starting node to the path-ending node has fewer segments than any optimal path in the plurality of optimal paths.
12 . The computer-readable medium of claim 11 , wherein the set of instructions also includes at least one instruction for:
excluding from the plurality of optimal paths any path that has a path facility type less than a desired minimum capacity, including:
for each segment that has a segment facility type and that is included in a path lacking a path facility type, setting the path facility type to the segment facility type; and
for each segment that has a segment facility type and that is included in a path having a path facility type, re-setting the path facility type to the segment facility type if the path facility type is greater than the segment facility type;
excluding from the plurality of optimal paths any path that has a path facility type less than the desired minimum capacity.
13 . The computer-readable medium of selecting claim 13 , wherein:
the database includes a TRIP file for each segment, the TRIP file including a first node and a second node.
14 . The computer-readable medium of claim 14 , wherein:
the TRIP file further includes a segment facility type.
15 . The computer-readable medium of claim 13 , wherein the set of instructions also includes at least one instruction for:
aggregating loads, including:
determining a load availability of each path in the plurality of optimal paths; and
selecting as the optimal path the path for which the load availability is greatest.
16 . The computer-readable medium of selecting of claim 13 , wherein the set of instructions also includes at least one instruction for:
balancing loads, including:
determining a load availability of each path in the plurality of optimal paths; and
selecting as the optimal path the path for which the load availability is least.
17 . In a network of nodes in a telecommunications environment, a computer system comprising:
a processor;
a bus coupled to the processor; and
a memory coupled to the bus, the memory containing a set of instructions that when executed by a computer cause the computer to execute a method, the method including selecting:
(a) a path-starting node that is connectable to the first customer location, and
(b) a path-ending node that is connectable to the second customer location, the path-starting node and the path-ending node being of a network of nodes; and
selecting at least one subset of files from a database containing a set of files, such that:
each file of the set of files contains segment data pertaining to a segment that connects a pair of nodes within the network,
each of the at least one subset contains data pertaining to a path from the path-starting node to the path-ending node; and
selecting an optimal path corresponding to an optimal subset of files, if more than one subset of files is selected.
18 . The computer system of claim 17 , wherein
selecting at least one subset of files from the database containing the set of files includes:
(a) determining a plurality of 1st-tier paths such that each 1st-tier path of the plurality of 1st-tier paths is a 1st-tier segment from the path-starting node to a 1st-tier node adjacent to the path-starting node within the network, the 1st-tier segment being of a database of segments, each of the 1st-tier nodes having a distance of one segment from the path-starting node;
(b) while none of the n th -tier nodes is the path-ending node,
identifying a plurality of (n+1) th -tier nodes, each of the (n+1) th -tier nodes having a distance of n+1 segments from the path-starting node;
determining a plurality of paths each of which has n+1 segments and includes (i) a path that has n segments, from the path-starting node to an n th -tier node and (ii) an (n+1) th segment from the n th -tier node to an (n+1) th -tier node adjacent to the nth-tier node within the network, the (n+1) th -tier segment being of the database of segments;
(c) if at least one node of at least one path is the path-ending node, determining a plurality of path costs, each path cost of the plurality of path costs corresponding to a path that includes both the path-starting node and the path-ending node;
(d) from the plurality of path costs, determining a plurality of optimal paths.
19 . The computer system of claim 18 , wherein the set of instructions also includes at least one instruction for:
counting segments in each path, wherein the path cost of each path is equal to a number of segments in the path, wherein the plurality of optimal paths is determined such that no path in the network from the path-starting node to the path-ending node has fewer segments than any optimal path in the plurality of optimal paths.
20 . The computer system of claim 18 , wherein the set of instructions also includes at least one instruction for:
excluding from the plurality of optimal paths any path that has a path facility type less than a desired minimum capacity, including:
for each segment that has a segment facility type and that is included in a path lacking a path facility type, setting the path facility type to the segment facility type; and
for each segment that has a segment facility type and that is included in a path having a path facility type, re-setting the path facility type to the segment facility type if the path facility type is greater than the segment facility type;
excluding from the plurality of optimal paths any path that has a path facility type less than the desired minimum capacity.
21 . The computer system of claim 21 , wherein:
the database includes a TRIP file for each segment, the TRIP file including a first node and a second node.
22 . The computer system of claim 22 , wherein:
the TRIP file further includes a segment facility type.
23 . The computer system of claim 21 , wherein the set of instructions also includes at least one instruction for:
aggregating loads, including:
determining a load availability of each path in the plurality of optimal paths; and
selecting as the optimal path the path for which the load availability is greatest.
24 . The computer system of claim 21 , wherein the set of instructions also includes at least one instruction for:
balancing loads, including
determining a load availability of each path in the plurality of optimal paths; and
selecting as the optimal path the path for which the load availability is least.
25 . A method of selecting an optimal path that in a telecommunication network that includes a plurality nodes that are linked by a segment to at least one adjacent node in the network, the method comprising:
(a) defining a path starting node that is connectable to a first location
(b) defining a path ending node that is connectable to a second location spaced from the first location;
(c) providing a database that includes the plurality of nodes and information relating to at least one characteristic of the each segment; and
(d) determining from the database using a computer available paths that link the starting node and the ending node in the network, and
(f) selecting an optimal path from the available paths based on a predefined criteria.
26 . The method of 25 further comprising establishing a telecommunication link between the first and second locations utilizing the selected optimal path.
27 . The method of claim 26 wherein the at least one characteristic includes at least one of: (i) load capacity; (ii) bandwidth; (iii) link type.
28 . The method of claim 25 wherein the database includes A TRIP file for each segment, the trip file including a first node and a second node.