METHOD AND APPARATUS FOR COMPUTING PATHS TO DESTINATIONS IN NETWORKS HAVING LINK CONSTRAINTS
A capability is provided for computing paths to destinations in networks having link constraints. An improved Constrained Shortest Path First (CSPF) algorithm is provided for computing a path from a source node to a destination node through a network. The improved CSPF algorithm uses neighbor node lists, in addition to a tentative node list and a paths list, for computing a path. The improved CSPF algorithm, during path computation, maintains a tentative node list including nodes selected for inclusion within the path. The tentative node list specifies the computed path. The improved CSPF algorithm, for each node selected for inclusion within the tentative node list, uses a neighbor node list for the selected node, and selects a neighbor node from the neighbor node list for inclusion within the tentative node list. The neighbor node list for a selected node includes a plurality of neighbor nodes of the selected node, where the neighbor nodes of the neighbor node list are arranged within the neighbor node list based on link constraints of a plurality of links between the selected node and the respective neighbor nodes of the selected node.
1 . A method for computing a path through a network, comprising:
selecting a node for the path, wherein the selected node is included in a tentative list of nodes for the path;
obtaining a neighbor node list for the selected node, wherein the neighbor node list includes a plurality of neighbor nodes of the selected node, wherein the neighbor nodes are arranged within the neighbor node list based on link constraints of a plurality of links between the selected node and the respective neighbor nodes; and
adding one of the neighbor nodes from the neighbor node list to the tentative list of nodes for the path.
2 . The method of claim 1 , wherein obtaining the neighbor node list for the selected node comprises one of:
receiving the neighbor node list for the selected node; and
building the neighbor node list for the selected node.
3 . The method of claim 2 , wherein building the neighbor node list for the selected node comprises:
identifying each of a plurality of nodes that are direct neighbor nodes of the selected node; and
adding each of the identified neighbor nodes to the neighbor node list.
4 . The method of claim 1 , wherein the identified neighbor nodes are listed in the neighbor node list in an order that is determined based on, for each of the links between the selected node and the respective neighbor nodes of the selected node, the link constraint associated with the link.
5 . The method of claim 4 , wherein, for each link, the link constraints comprise at least one of a link utilization for the link, a minimum link capacity required for the link, a maximum link bandwidth allowed for the link, a link cost associated with the link, and an administrative constraint associated with the link.
6 . The method of claim 1 , wherein the path is a path from a source node to a destination node, the method further comprising:
when the destination node of the path is identified, setting the tentative list of nodes of the path as the computed path from the source node to the destination node.
7 . The method of claim 6 , further comprising:
initiating signaling for establishing the computed path between the source node and the destination node.
8 . An apparatus for computing a path through a network, comprising:
a processor configured for:
selecting a node for the path, wherein the selected node is included in a tentative list of nodes for the path;
obtaining a neighbor node list for the selected node, wherein the neighbor node list includes a plurality of neighbor nodes of the selected node, wherein the neighbor nodes are arranged within the neighbor node list based on link constraints of a plurality of links between the selected node and the respective neighbor nodes; and
adding one of the neighbor nodes from the neighbor node list to the tentative list of nodes for the path.
9 . The apparatus of claim 8 , wherein obtaining the neighbor node list for the selected node comprises one of:
receiving the neighbor node list for the selected node; and
building the neighbor node list for the selected node.
10 . The apparatus of claim 9 , wherein building the neighbor node list for the selected node comprises:
identifying each of a plurality of nodes that are direct neighbor nodes of the selected node; and
adding each of the identified neighbor nodes to the neighbor node list.
11 . The apparatus of claim 8 , wherein the identified neighbor nodes are listed in the neighbor node list in an order that is determined based on, for each of the links between the selected node and the respective neighbor nodes of the selected node, the link constraint associated with the link.
12 . The apparatus of claim 11 , wherein, for each link, the link constraints comprise at least one of a link utilization for the link, a minimum link capacity required for the link, a maximum link bandwidth allowed for the link, a link cost associated with the link, and an administrative constraint associated with the link.
13 . The apparatus of claim 8 , wherein the path is a path from a source node to a destination node, wherein the processor is configured for:
when the destination node of the path is identified, setting the tentative list of nodes of the path as the computed path from the source node to the destination node.
14 . The apparatus of claim 13 , wherein the processor is configured for:
initiating signaling for establishing the computed path between the source node and the destination node.
15 . A computer readable storage medium storing instructions which, when executed by a computer, cause the computer to perform a method for computing a path through a network, the method comprising:
selecting a node for the path, wherein the selected node is included in a tentative list of nodes for the path;
obtaining a neighbor node list for the selected node, wherein the neighbor node list includes a plurality of neighbor nodes of the selected node, wherein the neighbor nodes are arranged within the neighbor node list based on link constraints of a plurality of links between the selected node and the respective neighbor nodes of the selected node; and
adding one of the neighbor nodes from the neighbor node list to the tentative list of nodes for the path.
16 . The computer readable storage medium of claim 15 , wherein obtaining the neighbor node list for the selected node comprises one of:
receiving the neighbor node list for the selected node; and
building the neighbor node list for the selected node.
17 . The computer readable storage medium of claim 16 , wherein building the neighbor node list for the selected node comprises:
identifying each of a plurality of nodes that are direct neighbor nodes of the selected node; and
adding each of the identified neighbor nodes to the neighbor node list.
18 . The computer readable storage medium of claim 15 , wherein the identified neighbor nodes are listed in the neighbor node list in an order that is determined based on, for each of the links between the selected node and the respective neighbor nodes of the selected node, the link constraint associated with the link.
19 . The computer readable storage medium of claim 18 , wherein, for each link, the link constraints comprise at least one of a link utilization for the link, a minimum link capacity required for the link, a maximum link bandwidth allowed for the link, a link cost associated with the link, and an administrative constraint associated with the link.
20 . The computer readable storage medium of claim 15 , wherein the path is a path from a source node to a destination node, the method further comprising:
when the destination node of the path is identified, setting the tentative list of nodes of the path as the computed path from the source node to the destination node.