Systems and methods for network routing

• US 7,839,791 B2
• Filed: 06/30/2008
• Issued: 11/23/2010
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: David G. Holmer, Herbert B. Rubens
• Original Assignee: David G. Holmer, Herbert B. Rubens
• Inventors: Rubens, Herbert B., Holmer, David G.
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US12/217,016
• Publication Number:
  US 20090046714A1
• Time in Patent Office: 876 Days
• Field of Search: None
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

Systems and methods are provided for routing data through a network. In one system, a first node is enabled to overhear packet transmissions from a second node. The cost of transmitting packets from the first node to the second node is updated based on each overheard packet transmission. In another system, when the cost of transmitting packets from a source to an overhearing node to a destination is less than the cost of transmitting packets from the source to the destination, an advertisement is sent to the source causing the packet transmissions to be routed from the source to the destination through the overhearing node. In yet another system, using a safe-sequence tag that is attached to any packet transmitted by any node and updated when it is received by another node, along with stored histories of best metric advertisements, predetermined rules are applied to maintain loop freedom.

Claims

1. A method for routing data through a network of two or more nodes, comprising:

(a) enabling a first node to overhear packet transmissions from a second node;

(b) determining a cost of transmitting packets from the first node to the second node;

(c) storing state information regarding each overheard packet transmission; and

(d) updating as necessary the cost of transmitting packets from the first node to the second node based on each overheard packet transmission, wherein the cost of transmitting packets from the first node to the second node is based at least in part on modulation statistics.

2. The method of claim 1, further comprising determining a route from the first node to a third node based on the cost of transmitting packets from the first node to the second node.

3. A method for routing data through a network of three or more nodes, comprising:

(a) enabling an overhearing node to overhear packet transmissions from a source node to a destination node;

(b) determining a cost of transmitting packets from the source node to the destination node;

(c) determining a cost of transmitting packets from the source node to the overhearing node to the destination node;

(d) storing state information regarding each overheard packet transmission;

(e) updating as necessary the cost of transmitting packets from the source node to the destination node, and the cost of transmitting packets from the source node to the overhearing node to the destination node, based on each overheard packet transmission; and

(f) when the cost of transmitting packets from the source node to the overhearing node to the destination node is less than the cost of transmitting packets from the source node to the destination node, sending an advertisement to the source node causing the packet transmissions to be routed from the source node to the destination node through the overhearing node.

4. A method for routing data through a network of three or more nodes, comprising:

(a) for a first route from a source node to a destination, generating one or more advertisements with increasing sequence numbers;

(b) for a second route from the source node to the destination node through an intermediate node, generating one or more advertisements with increasing sequence numbers;

(c) including as metrics in each advertisement a current cost estimate for reaching the destination node and a minimum cost estimate for reaching the destination node advertised for the sequence number;

(d) including a safe-sequence tag with any packet transmitted by any node;

(e) updating each safe-sequence tag when it is received by another node;

(f) storing in the source node a first history of best metrics for the first route;

(g) storing in the source node a second history of best metrics for the second route;

(h) storing in the source node a third history of advertisements made by the source node; and

(i) applying predetermined rules to the minimum cost estimates in the first, second, and third histories to maintain loop freedom.

5. The method of claim 4, further comprising storing in each node in the network a plurality of histories of best metrics, each history corresponding to one of a plurality of routes to a plurality of destination nodes and one of one or more next-hop nodes to each destination node.

6. A memory storing instructions adapted to be executed by a computer processor to perform a method for routing data through a network of two or more nodes, the method comprising:

(a) enabling a first node to overhear packet transmissions from a second node;

(b) determining a cost of transmitting packets from the first node to the second node;

(c) storing state information regarding each overheard packet transmission; and

(d) updating as necessary the cost of transmitting packets from the first node to the second node based on each overheard packet transmission, wherein the cost of transmitting packets from the first node to the second node is based at least in part on modulation statistics.

7. The memory of claim 6, the method further comprising determining a route from the first node to a third node based on the cost of transmitting packets from the first node to the second node.

8. A memory storing instructions adapted to be executed by a computer processor to perform a method for routing data through a network of three or more nodes, the method comprising:

(a) enabling an overhearing node to overhear packet transmissions from a source node to a destination node;

(b) determining a cost of transmitting packets from the source node to the destination node;

(c) determining a cost of transmitting packets from the source node to the overhearing node to the destination node;

(d) storing state information regarding each overheard packet transmission;

(e) updating as necessary the cost of transmitting packets from the source node to the destination node, and the cost of transmitting packets from the source node to the overhearing node to the destination node, based on each overheard packet transmission; and

(f) when the cost of transmitting packets from the source node to the overhearing node to the destination node is less than the cost of transmitting packets from the source node to the destination node, sending an advertisement to the source node causing the packet transmissions to be routed from the source node to the destination node through the overhearing node.

9. A memory storing instructions adapted to be executed by a computer processor to perform a method for routing data through a network of three or more nodes, the method comprising:

(a) for a first route from a source node to a destination, generating one or more advertisements with increasing sequence numbers;

(b) for a second route from the source node to the destination node through an intermediate node, generating one or more advertisements with increasing sequence numbers;

(c) including as metrics in each advertisement a current cost estimate for reaching the destination node and a minimum cost estimate for reaching the destination node advertised for the sequence number;

(d) including a safe-sequence tag with any packet transmitted by any node;

(e) updating each safe-sequence tag when it is received by another node;

(f) storing in the source node a first history of best metrics for the first route;

(g) storing in the source node a second history of best metrics for the second route;

(h) storing in the source node a third history of advertisements made by the source node; and

(i) applying predetermined rules to the minimum cost estimates in the first, second, and third histories to maintain loop freedom.

10. The memory of claim 9, the method further comprising storing in each node in the network a plurality of histories of best metrics, each history corresponding to one of a plurality of routes to a plurality of destination nodes and one of one or more next-hop nodes to each destination node.