Detection and Handling of Lost Messages During Load-Balancing Routing Protocols

• US 20080117823A1
• Filed: 11/09/2007
• Published: 05/22/2008
• Est. Priority Date: 11/09/2006
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Krishnakumar, Anjur Sundaresan, Yajnik, Shalini, Gobriel, Sameh, Krishnan, P.
• Granted Patent: US 7,843,833 B2
• Time in Patent Office: Days
• US Class Current: 370/236
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 45/36 Backward learning

Abstract

Methods that enable the detection and handling of lost messages during load-balancing routing protocols are disclosed. In accordance with the illustrative embodiment, when a candidate intermediate node N receives a routing-protocol message, node N performs: (1) a first procedure that is capable of detecting some lost routing-protocol messages that were previously transmitted by node N, and (2) a second procedure that is capable of detecting some lost routing-protocol messages that were previously transmitted by a neighbor of node N.

Claims

1. A method comprising:

receiving at a first node in a network a first message from a second node in said network, wherein said first message is for establishing a route in said network from a source node in said network to a destination node in said network, and wherein said first message comprises

(i) a route R from said source node to said second node, and

(ii) the value of a load metric at one or more nodes in said route R; and

inferring, after the receipt of said first message, that said second node did not receive a second message that was previously transmitted by said first node.

2. The method of claim 1 wherein said first message and said second message are multicast messages.

3. The method of claim 1 wherein said network is a multi-hop ad-hoc wireless network.

4. The method of claim 3 wherein said second node is a single hop from said first node.

5. The method of claim 1 wherein the inferring comprises determining whether a third message for establishing a route in said network from said source node to said destination node was previously received at said first node.

6. The method of claim 5 further comprising transmitting from said first node a fourth message that is for establishing a route in said network from said source node to said destination node;

wherein said third message comprises;

(i) a route S that starts from said source node and does not include said second node, and

(ii) the value of said load metric at one or more nodes in said route S; and

wherein said fourth message comprises;

(i) a route S′

consisting of said route S plus said first node appended at the end, and

(ii) the value of said load metric at one or more nodes in said route S′

.

7. The method of claim 1 wherein said first message, said second message, said third message, and said fourth message are multicast messages.

8. The method of claim 1 further comprising determining the value W of said load metric at said first node.

9. The method of claim 8 wherein, when a third message for establishing a route in said network from said source node to said destination node was previously received at said first node, it is inferred that said second node did not receive said second message when:

said first message indicates a value Y for said load metric at said second node;

said first message indicates a value X for said load metric summed over the nodes in said route R;

said third message comprises a route S that starts from said source node and does not include said second node;

said third message indicates a value L for said load metric summed over the nodes in said route S; and

L+W+Y<

X.

10. The method of claim 8 wherein, when a third message for establishing a route in said network from said source node to said destination node was previously received at said first node, it is inferred that said second node did not receive said second message when:

said first message indicates a value Y for said load metric at said second node;

said first message indicates a value X for said load metric for said route R;

said third message comprises;

(i) a route S that starts from said source node and does not include said second node, and

(ii) a vector {right arrow over (L)} of load metric values corresponding to the nodes in said route S;

the value Z of said load metric for route [S+said first node+said second node] is based on said load metric values {right arrow over (L)}, W, and Y; and

Z<

X.

11. The method of claim 1 further comprising inferring, after the receipt of said first message, that said first node did not receive a third message that was transmitted by a third node in said network.

12. A method comprising:

receiving at a first node in a network a first message from a second node in said network, wherein said first message is for establishing a route in said network from a source node in said network to a destination node in said network, and wherein said first message comprises

(i) a route R from said source node to said second node, and

(ii) the value of a load metric at one or more nodes in said route R; and

inferring, after the receipt of said first message, that said first node did not receive a second message that was transmitted by a third node in said network.

13. The method of claim 12 wherein said first message and said second message are multicast messages.

14. The method of claim 12 wherein said network is a multi-hop ad-hoc wireless network.

15. The method of claim 14 wherein said second node is a single hop from said first node in said network, and wherein said third node is a single hop from said first node in said network.

16. The method of claim 15 wherein it is inferred that said second node did not receive said second message when said third node belongs to said route R.

17. The method of claim 16 further comprising transmitting from said first node a third message that is for establishing a route in said network from said source node to said destination node, wherein said third message comprises:

(i) a route R′

consisting of all nodes in said route R from said source node to said third node, inclusive, plus said first node appended after said third node, and

(ii) the value of said load metric at one or more nodes in said route R′

.

18. A method comprising determining that a first multicast message transmitted by a first node in a multi-hop ad-hoc wireless network was not received by a second node that is one hop away from said first node;

wherein said first multicast message was transmitted as part of a protocol for establishing load-balanced routes in said multi-hop ad-hoc wireless network; and

wherein the determination is based on the value of a load metric at one or more nodes in said multi-hop ad-hoc wireless network.

19. The method of claim 18 wherein the determination is also based on the receipt of a second multicast message at said first node, and wherein said second multicast message is also transmitted as part of said protocol.

20. The method of claim 18 wherein the determination is also based on the receipt of a second multicast message at said second node, and wherein said second multicast message is also transmitted as part of said protocol.