US 6,646,989 B1Granted

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

AssigneeLucent Technologies Inc.

InventorsDennis Andreyevich Khotimsky, Vincent Georges Pierre Fayet, Antoni Bronislaw Przygienda

Life of this patent

Estimating the term…

Loading patent…

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.

Claims32

Dependent claims

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 E1, E2, . . . , EK, 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 T1, T2, . . . , TK, with each subpath Ti that is not empty being composed entirely of the edges in subset Ei, said method comprising the steps of:

(a) selecting the first subset of edges E1 in the ordered sequence of edge subsets E1, E2, . . . , EK;
(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 E1;
(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 Ei in the ordered sequence of edge subsets E1, E2, . . . , EK, 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 Ei 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.

5 more elements

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 V1, V2, . . . , VK and each of subsets Vi (i=1 . . . K) associated with a visibility set Fi⊂E such that all nodes in Vi share the same view of the network topology and have a hierarchical level defined as E=F1⊃F2⊃ . . . FK−1⊃FK, 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 F1 such that visibility set F1 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 F1;
(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 Fi of the next hierarchical level such that visibility set Fi 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.

6 more elements

Dependencies are inferred from the claim text.