Unified routing scheme for ad-hoc internetworking

• US 7,159,035 B2
• Filed: 09/25/2002
• Issued: 01/02/2007
• Est. Priority Date: 12/23/1998
• Status: Expired due to Term

• Current Assignee: Beijing Xiaomi Mobile Software Co., Ltd. (Xiaomi Corp.)
• Original Assignee: Nokia Corporation
• Inventors: Beyer, David A., Garcia-Luna-Aceves, J Joaquin, Frivold, Thane J.
• Primary Examiner(s): Caldwell, Andrew
• Assistant Examiner(s): Willett, Stephan
• Application Number:
  US10/256,168
• Publication Number:
  US 20030037167A1
• Time in Patent Office: 1,560 Days
• Field of Search: 709/238, 709/241, 370/391, 370/204, 455/406, 455/437, 465/462
• US Class Current: 709/241
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Routing table update messages that include both network-level and link-level addresses of nodes of a computer network are exchanged among the nodes of the computer network. Further, a routing table maintained by a first one of the nodes of the computer network may be updated in response to receiving one or more of the update messages. The routing table is preferably updated by selecting a next node to a destination node of the computer network only if every intermediate node in a path from the next node to the destination node satisfies a set of nodal conditions required by the first node for its path to the destination node and the next node offers the shortest distance to the destination node and to every intermediate node along the path from the next node to the destination node. The shortest distance to the destination node may be determined according to one or more link-state and/or node-state metrics regarding communication links and nodes along the path to the destination node. Also, the nodal characteristics of the nodes of the computer system may be exchanged between neighbor nodes, prior to updating the routing table. Preferred paths to one or more destination nodes may be computed according to these nodal characteristics, for example using a Dijkstra shortest-path algorithm.

Claims

1. A method, comprising:

maintaining local routing information by a first node of a computer network;

examining the local routing information maintained by the first node of the computer network to determine whether alternate paths exist to a neighbor node of the first node, using a sequence of one or more links other than a candidate link through the computer network;

computing a link quality of the candidate link;

if no alternate path exists to the neighbor node, accepting the candidate link; and

if one or more alternate paths do exist to the neighbor node, then comparing link qualities of the links along each of the alternate paths with the link quality of the candidate link and accepting the candidate link if the link quality of the candidate link compares favorably with the link qualities of the links on the alternate paths.

2. The method of claim 1 wherein a favorable comparison is one wherein the link quality of the candidate link is equal to or better than a link quality of a worst one of the link qualities of the links on the alternate paths.

3. The method of claim 1 wherein a favorable comparison is one wherein the link quality of the candidate link is equal to or better than a path quality function of the links along the alternate paths.

4. The method of claim 1 further comprising the step of accepting the candidate link if the link quality of the candidate link exceeds a defined threshold value.

5. The method of claim 3 wherein the link quality of any link in the computer network is equal to the probability of success for each packet transmitted over that link.

6. The method of claim 3 wherein the path quality function of the links along the alternate paths comprises the products of the link qualities for each the links on the alternate paths.

7. A method, comprising:

maintaining local routing information in a first node of a computer network;

identifying a second node of the computer network as a neighbor node;

selecting a link as a candidate link, wherein the link corresponds to one hop in the computer network;

determining whether any alternate paths exist that do not include the candidate link within the alternate paths, wherein the alternate paths comprise a plurality of links;

if no alternative paths exist, accepting the candidate link; and

if an alternative path exist, performing the following steps

computing a first link quality of the candidate link,

computing a second link quality of the plurality of links of the alternate path, and

accepting the candidate link if the first link quality compares favorably to the second link quality.