Systems and methods for network routing

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.

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.

A computer network comprising:

• (a) two or more nodes, each comprising a computer processor and data storage;
• (b) means for processing data regarding enabling a first node to overhear packet transmissions from a second node;
• (c) means for processing data regarding determining a cost of transmitting packets from the first node to the second node;
• (d) means for processing data regarding storing state information regarding each overheard packet transmission;
• and
• (e) means for processing data regarding updating as necessary the cost of transmitting packets from the first node to the second node based on each overheard packet transmission.

A computer network comprising:

• (a) three or more nodes, each comprising a computer processor and data storage;
• (b) means for processing data regarding enabling an overhearing node to overhear packet transmissions from a source node to a destination node;
• (c) means for processing data regarding determining a cost of transmitting packets from the source node to the destination node;
• (d) means for processing data regarding determining a cost of transmitting packets from the source node to the overhearing node to the destination node;
• (e) means for processing data regarding storing state information regarding each overheard packet transmission;
• (f) means for processing data regarding 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
• (g) 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, means for processing data regarding 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.

A computer network comprising:

• (a) for a first route from a source node to a destination, means for processing data regarding 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, means for processing data regarding generating one or more advertisements with increasing sequence numbers;
• (c) means for processing data regarding 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) means for processing data regarding including a safe-sequence tag with any packet transmitted by any node;
• (e) means for processing data regarding updating each safe-sequence tag when it is received by another node;
• (f) means for storing in the source node a first history of best metrics for the first route;
• (g) means for storing in the source node a second history of best metrics for the second route;
• (h) means for storing in the source node a third history of advertisements made by the source node;
• and
• (i) means for processing data regarding applying predetermined rules to the minimum cost estimates in the first, second, and third histories to maintain loop freedom.

A medium 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.

A medium 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.

A medium 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.