System and method for reliably communicating information without explicit acknowledgements

• US 8,224,235 B1
• Filed: 11/29/2010
• Issued: 07/17/2012
• Est. Priority Date: 10/03/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Woo, Alec, Culler, David E
• Primary Examiner(s): SHARMA, SUJATHA R
• Application Number:
  US12/955,073
• Time in Patent Office: 596 Days
• Field of Search: 455/3.01, 455/3.03, 455/412.1, 455/445, 455/500, 455/504, 455/510, 455/526, 370/254, 370/328, 370/329, 370/252, 370/400, 370/395.4, 370/374, 370/381, 370/312, 370/363, 370/368, 709/232, 709/224, 709/237
• US Class Current: 455/3.01
• CPC Class Codes: H04H 60/11 Arrangements for counter-measures when a portion of broadcast information is unavailable
• CPC Class Codes: H04L 1/08 by repeating transmission, e.g. Verdan system H04L1/1858 and H04L1/189 take precedence
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint

Abstract

A system and method communicates commands from a command originator to receiving devices, yet the receiving devices do not confirm receipt of the command. The most current command (e.g. the one with the highest sequence number) is rebroadcast by the command originator and the receiving devices, tending to be more frequent upon detection of an event indicating that the most current command was not received by at least one other device, and less frequently upon detection of an event indicating that the most current command was provided with sufficient duplication that if another device could receive it, the device likely did receive it, subject to a maximum and minimum rate.

Claims

1. A method comprising:

determining, by a transmitting node, whether a first message is to be broadcast in a communications network in which the transmitting node is present;

responsive to determining that a first message is to be broadcast;

incrementing, by the transmitting node, a value of a counter, and

broadcasting, by the transmitting node and in the communications network, the first message along with a first sequence number that is associated with the first message, the first sequence number being based on the value of the counter;

clearing, by the transmitting node, a timer that was previously set;

identifying, by the transmitting node, a value of the timer randomly between an upper bound and a lower bound; and

setting, by the transmitting node, the timer to the identified value.

2. The method of claim 1, wherein the communications network includes channels configured for broadcasting messages, and

wherein the transmitting node is configured to broadcast different messages on different channels such that a message and associated sequence number are broadcast on a channel along with an identifier corresponding to the channel that is based on at least one of the message and the value of the counter.

3. The method of claim 1, comprising:

responsive to determining that a first message is not to be broadcast, checking, by the transmitting node, whether the timer has elapsed;

based on the checking indicating that the timer has not elapsed, determining, by the transmitting node, whether at least one of a message and an indication has been received from network nodes that are configured for receiving the first message broadcast by the transmitting node; and

based on determining that at least one of a message and an indication has been received from the network nodes, logging, by the transmitting node, a date and a time associated with the received message or indication, along with a sequence number corresponding to the received message or indication.

4. The method of claim 3, wherein the logging comprises:

storing, by the transmitting node, the date, time and sequence number corresponding to the received message or indication in a buffer associated with the transmitting node, the buffer being used to determine at least one of;

whether a message is received out of order, wherein a message is determined to be out of order based on a sequence number associated with the message being older than a sequence number associated with another message that has been previously broadcast or received by the transmitting node,

whether an indication is received corresponding to missed messages, and

a number of times a message with a highest sequence number is received, the highest sequence number being greater than sequence numbers associated with all other messages that have been broadcast in the communications network.

5. The method of claim 3, comprising:

based on the checking indicating that the timer has elapsed, rebroadcasting, by the transmitting node, the first message along with the first sequence number;

identifying, by the transmitting node, a new value of the timer; and

setting, by the transmitting node, the timer to the new value.

6. The method of claim 5, comprising:

receiving, at the transmitting node, an indication from a receiving node that an old message with a sequence number older than a highest sequence number corresponding to a message that has been broadcast, has not been received by the receiving node, the highest sequence number being greater than sequence numbers associated with all other messages that have been broadcast in the communications network; and

responsive to receiving the indication, broadcasting, by the transmitting node, a make up message that is same as the old message.

7. The method of claim 1, wherein the value of the timer that is set randomly between the upper bound and the lower bound is based on at least one of:

a prior value of the timer,

whether a number of times a message with a highest sequence number has been received is greater than a predetermined threshold value, wherein the highest sequence number is greater than sequence numbers associated with all other messages that have been broadcast in the communications network,

whether a message that is received by the transmitting node since a last time the timer was set is out of order or indicated as not having been received, wherein a message is determined to be out of order based on a sequence number associated with the message being older than a sequence number associated with another message that has been previously broadcast or received by the transmitting node, and

prior values associated with the upper bound and lower bound.

8. The method of claim 7, comprising:

based on determining that the number of times a message with the highest sequence number has been received is greater than the predetermined threshold value, setting, by the transmitting node, the upper bound and the lower bound to new values that are higher compared to previous values associated with the upper bound and the lower bound,

the new values being less than absolute high limits associated with the upper bound and lower bound.

9. The method of claim 7, comprising:

based on determining that a message that is received by the transmitting node is out of order, or receiving an indication that a message that has been broadcast is not received by a receiving node, setting, by the transmitting node, the upper bound and the lower bound to new values that are lower compared to previous values associated with the upper bound and the lower bound,

the new values being higher than absolute low limits associated with the upper bound and lower bound.

10. A method comprising:

determining, by a receiving node in a communications network, whether a second message and a second sequence number that is associated with the second message have been received;

based on determining that a second message and a second sequence number have been received, comparing, by the receiving node, the second sequence number to sequence numbers associated with previously received messages;

responsive to comparing the second sequence number to sequence numbers associated with previously received messages, determining that the second sequence number is higher than the sequence numbers associated with previously received messages;

based on determining that the second sequence number is higher;

storing, by the receiving node, the second message and the second sequence number, and

performing, by the receiving node, an action based on information associated with the second message;

identifying, by the receiving node, a value of a timer based on a set of parameters; and

setting, by the receiving node, the timer to the identified value.

11. The method of claim 10, wherein the set of parameters includes:

a value indicating a determination whether a number of times that the second message and the second sequence number have been received exceeds a predetermined threshold value,

a value indicating a determination whether a message has been received out of order, wherein a message is determined to have been received out of order based on a sequence number associated with the message being older than a sequence number associated with another message that has been previously received by the receiving node,

an indication that a node in the communications network has not received a message,

a prior value of the timer,

an upper bound or a lower bound that is used to select the prior value of the timer, and

a pseudo-random number.

12. The method of claim 10, comprising:

based on determining that the second sequence number is not higher, checking, by the receiving node, whether the second message has been received out of order, wherein a message is determined to have been received out of order based on a sequence number associated with the message being older than a sequence number associated with another message that has been previously received by the receiving node; and

responsive to the checking indicating that the second message has not been received out of order, storing, by the receiving node, the second message, the second sequence number and information corresponding to a date and time of receiving the second message.

13. The method of claim 12, comprising:

responsive to the checking indicating that the second message has been received out of order, storing, by the receiving node, the second message, the second sequence number and information corresponding to the date and time of receiving the second message along with an indication that the second message has been received out of order.

14. The method of claim 10, comprising:

based on determining that a second message and a second sequence number have not been received, checking, by the receiving node, whether the timer has elapsed; and

based on the checking indicating that the timer has elapsed, broadcasting, by the receiving node, a message and an associated sequence number that is a highest sequence number, the highest sequence number being greater than sequence numbers associated with all other messages that have been broadcast in the communications network.

15. The method of claim 14, comprising:

receiving, at the receiving node, an indication that another node in the communications network has not received a message; and

broadcasting, by the receiving node, a make up message and associated sequence number, the make up message being same as the message that has not been received by the another node.

16. A system comprising:

a transmitting node included in a communications network, the transmitting node comprising first instructions stored in a non-transitory machine-readable first medium for execution by a first processing device and configured to cause the first processing device to perform operations comprising;

determining, by the transmitting node, whether a first message is to be broadcast in the communications network;

responsive to determining that the first message is to be broadcast;

incrementing, by the transmitting node, a value of a counter, and

broadcasting, by the transmitting node and in the communications network, the first message along with a first sequence number associated with the first message, the first sequence number being based on the value of the counter;

clearing, by the transmitting node, a first timer that was previously set;

identifying, by the transmitting node, a value of the first timer randomly between an upper bound and a lower bound; and

setting, by the transmitting node, the first timer to the identified value; and

a receiving node included in the communications network, the receiving node comprising second instructions stored in a non-transitory machine-readable second medium for execution by a second processing device and configured to cause the second processing device to perform operations comprising;

determining, by the receiving node, whether a second message and a second sequence number that is associated with the second message have been received;

based on determining that the second message and second sequence number have been received, comparing, by the receiving node, the second sequence number to sequence numbers associated with previously received messages;

responsive to comparing the second sequence number to sequence numbers associated with previously received messages, determining that the second sequence number is higher than the sequence numbers associated with previously received messages;

based on determining that the second sequence number is higher;

storing, by the receiving node, the second message and the second sequence number, and

performing, by the receiving node, an action based on information associated with the second message;

identifying, by the receiving node, a value of a second timer based on a set of parameters; and

setting, by the receiving node, the second timer to the identified value.

17. The system of claim 16, wherein the first instructions are configured to cause the first processing device to perform operations comprising:

responsive to determining that the first message is not to be broadcast, checking, by the transmitting node, whether the first timer has elapsed;

based on the checking indicating that the first timer has not elapsed, determining, by the transmitting node, whether at least one of a message and an indication has been received from network nodes that are configured for receiving the first message broadcast by the transmitting node; and

based on determining that at least one of a message and an indication has been received from the network nodes, logging, by the transmitting node, a date and a time associated with the received message or indication, along with a sequence number corresponding to the received message or indication.

18. The system of claim 17, wherein the first instructions are configured to cause the first processing device to perform operations comprising:

based on the checking indicating that the first timer has elapsed, rebroadcasting, by the transmitting node, the first message along with the first sequence number;

identifying, by the transmitting node, a new value of the first timer; and

setting, by the transmitting node, the first timer to the new value.

19. The system of claim 18, wherein the first instructions are configured to cause the first processing device to perform operations comprising:

receiving, by the transmitting node, an indication from a network node that an old message with a sequence number older than a highest sequence number corresponding to a message that has been broadcast, has not been received by the network node, the highest sequence number being greater than sequence numbers associated with all other messages that have been broadcast in the communications network; and

responsive to receiving the indication, broadcasting, by the transmitting node, a make up message that is same as the old message.

20. The system of claim 16, wherein the second instructions are configured to cause the second processing device to perform operations comprising:

based on determining that the second sequence number is not higher, checking whether the second message has been received out of order, wherein a message is determined to have been received out of order based on a sequence number associated with the message being older than a sequence number associated with another message that has been previously broadcast or received; and

responsive to the checking indicating that the second message has not been received out of order, storing, by the receiving node, the second message, the second sequence number and information corresponding to a date and time of receiving the second message.

21. The system of claim 20, wherein the second instructions are configured to cause the second processing device to perform operations comprising:

responsive to the checking indicating that the second message has been received out of order, storing, by the receiving node, the second message, the second sequence number and information corresponding to the date and time of receiving the second message along with an indication that an out of order message has been received.

22. The system of claim 16, wherein the second instructions are configured to cause the second processing device to perform operations comprising:

based on determining that the second message and second sequence number have not been received, checking, by the receiving node, whether the second timer has elapsed; and

based on the checking indicating that the second timer has elapsed, broadcasting, by the receiving node, a message and an associated sequence number that is a highest sequence number, the highest sequence number being greater than sequence numbers associated with all other messages that have been broadcast in the communications network.

23. The system of claim 22, wherein the second instructions are configured to cause the second processing device to perform operations comprising:

receiving, at the receiving node, an indication that another node in the communications network has not received a message; and

broadcasting, by the receiving node, a make up message and associated sequence number, the make up message being same as the message that has not been received by the another node.

24. The system of claim 16, wherein the value of the first timer that is set randomly between the upper bound and the lower bound is based on at least one of:

a prior value of the first timer,

whether a number of times a message with a highest sequence number has been received is greater than a predetermined threshold value, wherein the highest sequence number is greater than sequence numbers associated with all other messages that have been broadcast in the communications network,

whether a message that is received by the transmitting node since a last time the first timer was set is out of order or indicated as not having been received, and

prior values associated with the upper bound and lower bound.

25. The system of claim 24, wherein the first instructions are configured to cause the first processing device to perform operations comprising:

based on determining that the number of times a message with the highest sequence number has been received is greater than the predetermined threshold value, setting, by the transmitting node, the upper bound and the lower bound to new values that are higher compared to previous values associated with the upper bound and the lower bound,

the new values being less than absolute high limits associated with the upper bound and lower bound.

26. The system of claim 24, wherein the first instructions are configured to cause the first processing device to perform operations comprising:

based on determining that a message that is received by the transmitting node is out of order, or receiving an indication that a message that has been broadcast is not received by a receiving node, setting, by the transmitting node, the upper bound and the lower bound to new values that are lower compared to previous values associated with the upper bound and the lower bound,

the new values being higher than absolute low limits associated with the upper bound and lower bound, and

a message is determined to be out of order based on a sequence number associated with the message being older than a sequence number associated with another message that has been previously broadcast or received by the transmitting node.

27. The system of claim 16, wherein the set of parameters includes:

a value indicating a determination whether a number of times that the message and the associated sequence number have been received exceeds a predetermined threshold value,

a value indicating a determination whether a message has been received out of order, wherein a message is determined to have been received out of order based on a sequence number associated with the message being older than a sequence number associated with another message that has been previously received by the receiving node,

an indication that a node in the communications network has not received a message,

a prior value of the second timer,

an upper bound or a lower bound that is used to select the prior value of the second timer, and

a pseudo-random number.