Hop-by-hop routing with node-dependent topology information

• US 6,646,989 B1
• Filed: 03/20/1999
• Issued: 11/11/2003
• Est. Priority Date: 06/29/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Przygienda, Antoni Bronislaw, Fayet, Vincent Georges Pierre, Khotimsky, Dennis Andreyevich
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): Molinari, Michael J
• Application Number:
  US09/273,434
• Time in Patent Office: 1,697 Days
• Field of Search: 370/238, 370/238.1, 370/389, 370/395.31, 370/254, 370/400, 709/241, 709/238, 709/243
• US Class Current: 370/238
• CPC Class Codes: H04L 45/12 Shortest path evaluation

Abstract

This invention relates to a method to effect hop-by-hop routing in a network segment where different nodes have different views of the network topology. In particular, the methods of this invention are applicable when each node in a network or network segment may be aware of only a subset of the communication links in the network, without perceiving other communication links. Based on each node'"'"'s individual view of the network, the method introduces the concept of a visibility set that includes all visible communication links. More specifically, an efficient algorithm is disclosed for searching for a family of one-to-all optimal feasible paths in communication network where different nodes may have different views of the network topology. The algorithm comprises (a) restricting the set of available paths to a destination node to the set of feasible paths from the source node to the destination node; and choosing as the optimal route the feasible path which has the lowest cost, wherein a path is a feasible path if (i) the path does not contain a cycle, and (ii) for each intermediate node visited by the path, the subpath from that intermediate node to the destination node is visible from the intermediate node.

Claims

1. In a communication network modeled by a directed graph G=(V,E) where the vertices in set V represent routing nodes and the edges in E correspond to communication links, the set of edges E being a union of K ordered edge subsets E₁, E₂, . . . , E_K, a method for searching for a set of paths from a source node to any destination node which can be represented as a concatenation of K possibly empty subpaths T₁, T₂, . . . , T_K, with each subpath T_i that is not empty being composed entirely of the edges in subset E_i, said method comprising the steps of:

(a) selecting the first subset of edges E₁ in the ordered sequence of edge subsets E₁, E₂, . . . , E_K;

(b) determining the shortest paths from the source node to all other nodes on a partial graph consisting of the set of vertices V and the edges in the selected subset of edges E₁;

(c) for any node reachable from the source node along any of the determined shortest paths, storing the determined shortest path;

(d) for any node reachable from the source node along any one of the determined shortest paths, creating a set of fake edges from the source node to the reachable node, and assigning a weight to each fake edge equal to the length of the corresponding shortest path;

(e) selecting a next subset of edges E_i in the ordered sequence of edge subsets E₁, E₂, . . . , E_K, and determining the shortest paths from the source node to all other nodes on a partial graph consisting of the set of vertices V and the union of the edges in the selected subset of edges E_i and the previous set of fake edges;

(f) repeating steps (c)-(e) until all subsets of edges in the ordered sequence of the edge subsets are considered; and

(h) selecting as a target set of paths to a desired destination node the set of the shortest paths determined in the last iteration of step (c) for the desired destination, if the set of shortest path is defined.

2. The method of claim 1 further comprising the step of forwarding a packet from the source node to the destination node along the selected target of paths.

3. The method of claim 1 further comprising the step of establishing a connection between the source node and the destination node.

4. The method of claim 1 further comprising the step of repeating steps (a)-(h) for all nodes designated as source nodes.

5. The method of claim 1 further comprising the step of repeating steps (a)-(h) for each desired destination node in the communication network.

6. The method of claim 1 further comprising the step of storing the next hop or first intermediate node along the chosen target set of paths.

7. The method of claim 1 further comprising the step of classifying network nodes into a multilevel hierarchy such that every link visible to a node belonging to a lower level of the multilevel hierarchy is necessarily visible to each node belonging to each higher level of the multilevel hierarchy.

8. The method of claim 1 wherein a path is visible from a predetermined node if the weights of all the links in the path as perceived by that predetermined node are finite.

9. The method of claim 8 wherein the weights of the links in a path is the same for all nodes for which the path is visible.

10. The method of claim 1 wherein network nodes run different routing protocols.

11. The method of claim 1 wherein network nodes run different versions of the same routing protocol.

12. The method of claim 1 wherein the communication network supports Quality of Service (QoS) parameters of arbitrary complexity.

13. The method of claim 1 wherein the absolute cost of a desired path between two nodes is a mathematical function of the weights of the links contained in the desired path.

14. The method of claim 13 wherein the mathematical function is a summation.

15. The method of claim 13 wherein the mathematical function is a minimum.

16. In a communication network modeled by a directed graph G=(V,E) where the vertices in set V represent routing nodes and the edges in E correspond to communication links, the vertex set V partitioned into K disjoint subsets V₁, V₂, . . . , V_K and each of subsets V_i (i=1 . . . K) associated with a visibility set F_i⊂

E such that all nodes in V_i share the same view of the network topology and have a hierarchical level defined as E=F₁⊃

F₂⊃

. . . F<sub>K−

1</sub>⊃

F_K, a method for determining the first hop of a route from a source node to any destination node in the network, said method comprising the steps of;

(a) selecting a subset of edges in a visibility set F₁ such that visibility set F₁ is visible from the node associated with the initial vertex of each selected edge;

(b) determining the shortest paths from the source node to all other nodes on a partial graph consisting of the set of vertices V and the selected subset of edges in visibility set F₁;

(c) for any node reachable from the source node along any one the determined shortest paths, storing the length and initial hop of the shortest path from the source node to the reachable node;

(d) for any node reachable from the source node along any one of the determined shortest paths, creating a first set of fake edges from the source node to the reachable node, and assigning a weight to each fake edge equal to the length of the corresponding shortest path;

(e) selecting a subset of edges in the visibility set F_i of the next hierarchical level such that visibility set F_i is visible from the node associated with the initial vertex of each selected edge;

(f) determining the shortest paths from the source node to all other nodes on a partial graph consisting of the set of vertices V and the union of the selected subset of edges of step (e) and the previous set of fake edges;

(g) repeating steps (c)-(f) until the visibility sets of all hierarchy levels have been considered; and

(h) selecting as the first hop, of the route from the source node to a desired destination node, the initial hop of the shortest path determined in the last iteration of step (c) for the desired destination node, if the initial hop is defined.

17. The method of claim 16 further comprising the step of establishing routing policies to route a packet from the source node to the desired destination node.

18. The method of claim 17 wherein the step of establishing routing policies includes dropping a packet if the first hop is undefined.

19. The method of claim 17 wherein the step of establishing routing policies includes forwarding a packet to a neighboring node belonging to a vertex subset associated with a visibility set of a higher hierarchical level.

20. The method of claim 16 further comprising the step of forwarding a packet from the source node to the desired destination node along the chosen shortest path.

21. The method of claim 16 further comprising the step of establishing a connection between the source node and the desired destination node.

22. The method of claim 16 further comprising the step of repeating steps (a)-(h) for all nodes designated as source nodes.

23. The method of claim 16 further comprising the step of repeating steps (a)-(h) for each desired destination node in the communication network.

24. The method of claim 16 further comprising the step of storing the next hop or first intermediate node along the selected shortest path.

25. The method of claim 16 wherein a path is visible from a predetermined node if the weights of all the links in the path as perceived by that predetermined node are finite.

26. The method claim 16 wherein the weights of the links in a path is the same for all nodes for which the path is visible.

27. The method of claim 16 wherein network nodes run different routing protocols.

28. The method of claim 16 wherein network nodes run different versions of the same routing protocol.

29. The method of claim 16 wherein the communication network supports Quality of Service (QoS) parameters of arbitrary complexity.

30. The method of claim 16 wherein the absolute cost of a desired path between two nodes is a mathematical function of the weights of the links contained in the desired path.

31. The method of claim 30 wherein the mathematical function is a summation.

32. The method of claims 30 wherein the mathematical function is a minimum.