×

Efficient precomputation of quality-of-service routes

  • US 6,633,544 B1
  • Filed: 06/24/1999
  • Issued: 10/14/2003
  • Est. Priority Date: 06/24/1998
  • Status: Expired due to Term
First Claim
Patent Images

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 all claims
  • 12 Assignments
Timeline View
Assignment View
    ×
    ×