Efficient precomputation of quality-of-service routes
First Claim
1. A method for computing a selected route from a source node to a destination node in a network using a depth-first search, wherein the selected route is represented by a stack data structure, comprising the steps of:
- (a) storing a directed graph of nodes, links and link costs using a first data structure, wherein the first data structure associates each node other than the destination node with at least one parent pointer that points to a node;
(b) selecting a link from a current node to a next node;
(c) determining feasibility of the link using a recent link state;
(d) if the link is feasible, including the next node in the selected route, wherein the step of including the next node in the selected route further includes the steps of;
(i) pushing the next node on the stack data structure; and
(ii) setting the current node to be the next node;
(e) if the link is not feasible, excluding the next node from the selected route, wherein the step of excluding the next node from the selected route further includes the steps of;
(i) determining whether all parent pointers associated with the current node have been considered;
(ii) if all parent pointers associated with the current node have not been considered, setting the next node to a node pointed to by a parent pointer that has not been considered;
(iii) if all parent pointers associated with the current node have been considered, executing the steps of;
(A) removing the current node from the route;
(B) setting the current node to a previous node in the route;
(C) repeating steps (i)-(iii) until one of a node is found that may be included in the route and it is determined that there exists no node that may be included in the route; and
(f) repeating steps (b)-(e) until one of the destination node is reached and a route cannot be computed to the destination node.
12 Assignments
0 Petitions
Accused Products
Abstract
The present invention provides a method and system for computing and storing minimum-cost routes to all destination nodes in a network. According to one embodiment, the present invention is applied in the context of computing quality of service routes using a source-directed connection-oriented routing environment. The route computation scheme employs an extension to Dijkstra'"'"'s algorithm coupled with discretized link costs to generate a shortest-path graph with one or more routes to each destination. The present invention provides a compact data structure for storing at least one minimum-cost route to each destination node in a network. In particular, the routes are stored using a directed acyclic graph representing at least one minimum-cost pre-computed route for each destination node in the network. Each destination node in the network is associated with one or more parent pointers pointing to an upstream node in network that lies along a minimum-cost route. Routes are retained in the data structure and not extracted until connection arrival.
Upon connection arrival, a route is extracted from the data structure by performing a depth-first search of the acyclic graph, which returns the first route in the common case. As part of the route extraction process, the feasibility of each link in the route is determined based upon a recent link-state. Links that are infeasible are excluded from the extracted route. In addition, according to one embodiment, promising routes are re-ranked in the data structure to provide computational benefits for future route extractions.
285 Citations
16 Claims
-
1. A method for computing a selected route from a source node to a destination node in a network using a depth-first search, wherein the selected route is represented by a stack data structure, comprising the steps of:
-
(a) storing a directed graph of nodes, links and link costs using a first data structure, wherein the first data structure associates each node other than the destination node with at least one parent pointer that points to a node;
(b) selecting a link from a current node to a next node;
(c) determining feasibility of the link using a recent link state;
(d) if the link is feasible, including the next node in the selected route, wherein the step of including the next node in the selected route further includes the steps of;
(i) pushing the next node on the stack data structure; and
(ii) setting the current node to be the next node;
(e) if the link is not feasible, excluding the next node from the selected route, wherein the step of excluding the next node from the selected route further includes the steps of;
(i) determining whether all parent pointers associated with the current node have been considered;
(ii) if all parent pointers associated with the current node have not been considered, setting the next node to a node pointed to by a parent pointer that has not been considered;
(iii) if all parent pointers associated with the current node have been considered, executing the steps of;
(A) removing the current node from the route;
(B) setting the current node to a previous node in the route;
(C) repeating steps (i)-(iii) until one of a node is found that may be included in the route and it is determined that there exists no node that may be included in the route; and
(f) repeating steps (b)-(e) until one of the destination node is reached and a route cannot be computed to the destination node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for calculating and storing a directed graph of network routes comprising the steps of:
-
(a) storing a plurality of nodes, links and link costs in a data structure;
(b) associating each node with a lowest cost estimate parameter;
(c) if the data structure contains at least one node, executing the steps of;
(i) removing a minimum node from the data structure;
(ii) if a sum of the lower cost estimate parameter associated with the minimum node and a link cost from the minimum node to an adjacent node equals the lowest cost estimate parameter associated with the adjacent node, executing the step of assigning a pointer associated with the adjacent node to point to the minimum node;
(iii) if the sum of the lowest cost estimate parameter associated with the minimum node and the link cost from the minimum node to an adjacent node is less than the lowest cost estimate parameter associated with the adjacent node, executing the steps of;
(A) assigning a pointer to the adjacent node to point to the minimum node;
(B) setting the lowest cost estimate parameter associated with the adjacent node to be equal to the sum of the lowest cost estimate parameter associated with the minimum node and the link cost from the minimum node to the adjacent node. - View Dependent Claims (11, 12, 13)
-
-
14. A network node comprising:
-
an interface for receiving packet data;
a second interface for transmitting packet data;
a processor adapted to;
(a) store a directed graph of nodes, links and link costs using a first data structure;
(b) select a link from a current node to a next node;
(c) determine feasibility of the link using a recent link state;
(d) if the link is feasible, include the next node in a selected route;
(e) if the link is not feasible, exclude the next node from the selected route;
(f) repeat steps (b)-(e) until one of a destination node is reached and a route cannot be computed to the destination node;
and wherein the processor is further adapted to;
(a) store a plurality of nodes, links and link costs in a second data structure;
(b) associate each node with a lowest cost estimate parameter;
(c) if the second data structure contains at least one node, execute the steps of;
(i) remove a minimum node from the second data structure;
(ii) if a sum of the lowest cost estimate parameter associated with the minimum node and a link cost from the minimum node to an adjacent node equals the lowest cost estimate parameter associated with the adjacent node, execute the step of assigning a pointer associated with the adjacent node to point to the minimum node;
(iii) if the sum of the lowest cost estimate parameter associated with the minimum node and the link cost from the minimum node to the adjacent node is less ;
than the lowest code estimate parameter associated with the adjacent node, execute the steps of;
(A) assigning the a pointer to the adjacent node to point to the minimum node;
(B) setting the lowest cost estimate parameter associated with the adjacent node to be equal to the sum of the lowest cost estimate parameter associated with the minimum node and the link cost from the minimum node to the adjacent node. - View Dependent Claims (15)
-
-
16. A network comprising:
-
at least one node;
a topology, wherein the topology defines a set of connections between the at least one node and wherein each of the one node further comprises;
an interface for receiving packet data;
a second interface for transmitting packet data;
a processor adapted to;
(a) store a directed graph of nodes, links and link costs using a first data structure;
(b) select a link from a current node to a next node;
(c) determine feasibility of the link using a recent link state;
(d) if the link is feasible, include the next node in a selected route;
(e) if the link is not feasible, exclude the next node from the selected route;
(f) repeat steps (b)-(e) until one of a destination node is reached and a route cannot be computed to the destination node;
and wherein the processor is further adapted to;
(a) store a plurality of nodes, links and link costs in a second data structure;
(b) associate each node with a lowest cost estimate parameter;
(c) if the second data structure contains at least one node, execute the steps of;
(i) remove a minimum node from the second data structure;
(ii) if a sum of the lowest cost estimate parameter associated with the minimum node and a link cost from the minimum node to an adjacent node equals the lowest cost estimate parameter associated with the adjacent node, execute the step of assigning a pointer associated with the adjacent node to point to the minimum node;
(iii) if the sum of the lowest cost estimate parameter associated with the minimum node and the link cost from the minimum node to the adjacent node is less than the lowest code estimate parameter associated with the adjacent node, execute the steps of;
(A) assigning the pointer to the adjacent node to point to the minimum node;
(B) setting the lowest cost estimate parameter associated with the adjacent node to be equal to the sum of the lowest cost estimate parameter associated with the minimum node and the link cost from the minimum node to the adjacent node.
-
Specification