System and method for reliably communicating information without explicit acknowledgements

• US 8,351,844 B2
• Filed: 07/16/2012
• Issued: 01/08/2013
• 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:
  US13/549,700
• Publication Number:
  US 20120276839A1
• Time in Patent Office: 176 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:

identifying a timer value associated with a network channel in a communications network;

determining whether a command corresponding to the network channel is received out of sequence in a most recent period indicated by the timer value;

identifying a first adjustment to the timer value based on determining whether the command is received out of sequence, the first adjustment to the timer value providing an adjusted timer value;

determining a number of times that a particular command is received;

identifying a second adjustment to the adjusted timer value based on determining the number of times that the particular command is received, the second adjustment to the adjusted timer value providing a resulting timer value;

determining whether the resulting timer value is outside of a range of allowed adjustment results;

based on determining that the resulting timer value is not outside of the range of allowed adjustment results, identifying an upper bound and a lower bound associated with the resulting timer value;

selecting a random or pseudo-random number between the upper bound and the lower bound; and

establishing a new timer value based on the selected random or pseudo-random number.

2. The method of claim 1, wherein identifying a timer associated with the network channel comprises:

determining that a prior timer value is not used; and

based on determining that the prior timer value is not used, selecting an initial value as the timer value.

3. The method of claim 2, wherein selecting an initial value as the timer value comprises selecting the initial value from the group consisting of a lowest possible value, a highest possible value, a value in between the lowest possible value and the highest possible value and an average of a prior upper bound and a prior lower bound for the timer value.

4. The method of claim 1, wherein the most recent period is determined as an amount of time between a current time and a prior time at which the timer value was identified or elapsed.

5. The method of claim 1, wherein identifying a first adjustment to the timer value comprises:

based on determining that a command is received out of sequence, identifying the first adjustment as a fixed number that is equal to or below zero; and

adding the first adjustment to the timer value.

6. The method of claim 1, wherein identifying a first adjustment to the timer value comprises:

based on determining that no command is received out of sequence, identifying the first adjustment as a fixed number that is equal to or above zero; and

adding the first adjustment to the timer value.

7. The method of claim 1, wherein determining whether the resulting timer value is outside of a range of allowed adjustment results comprises:

based on determining that the resulting timer value is outside of the range of allowed adjustment results, setting the resulting timer value to a nearest boundary value of the range.

8. The method of claim 1, comprising:

receiving information associated with a command;

examining the received information;

determining, based on examining the received information, whether the command is out of order, whether the command was not received, whether the command is a highest sequence number command, or whether a number of times the command was received has exceeded a threshold value;

based on determining at least one of;

the command is out of order, the command was not received, the command is the highest sequence number command, and the number of times the command was received has exceeded the threshold value, recalculating the timer value for providing a newly identified timer value; and

setting the timer value based on the newly identified timer value.

9. The method of claim 8, wherein setting the timer value based on the newly identified timer value comprises:

subtracting from the newly identified timer value an amount of time remaining on an existing timer;

determining whether a result of the subtracting is negative; and

based on determining that the result of the subtracting is not negative, setting the result of the subtracting as the timer value.

10. The method of claim 9, comprising:

based on determining that the result of the subtracting is negative, setting zero as the timer value.

11. A method comprising:

receiving commands associated with a network channel in a communications network;

receiving information from a neighboring network device indicating that the network device did not receive a command;

responsive to receiving the information, selecting a random number; and

sending missing commands to the neighboring network device based on the selected random number, including an indicator that the missing commands are sent as make up commands.

12. The method of claim 11, wherein receiving information from a neighboring network device indicating that the network device did not receive a command comprises receiving information from the neighboring network device that includes at least one of:

a command with a sequence number that is two or more less than a highest sequence number command sent or received, and

an indication from the neighboring network device that it did not receive one or more commands.

13. The method of claim 11, wherein sending missing commands to the neighboring network device comprises sending zero, one or more commands indicated as not received by the neighboring network device, and

wherein at least one of a number of missing commands sent and which missing commands are sent, is based on the selected random number.

14. A system comprising:

a processor; and

instructions encoded in a non-transitory machine readable medium for execution by the processor and configured to cause the processor to perform operations comprising;

identifying a timer value associated with a network channel in a communications network;

determining whether a command corresponding to the network channel is received out of sequence in a most recent period indicated by the timer value;

identifying a first adjustment to the timer value based on determining whether the command is received out of sequence, the first adjustment to the timer value providing an adjusted timer value;

determining a number of times that a particular command is received;

identifying a second adjustment to the adjusted timer value based on determining the number of times that the particular command is received, the second adjustment to the adjusted timer value providing a resulting timer value;

determining whether the resulting timer value is outside of a range of allowed adjustment results;

based on determining that the resulting timer value is not outside of the range of allowed adjustment results, identifying an upper bound and a lower bound associated with the resulting timer value;

selecting a random or pseudo-random number between the upper bound and the lower bound; and

establishing a new timer value based on the selected random or pseudo-random number.

15. The system of claim 14, wherein the instructions that are configured to cause the processor to perform operations comprising identifying a timer value associated with the network channel comprises instructions that are configured to cause the processor to perform operations comprising:

determining that a prior timer value is not used; and

based on determining that the prior timer value is not used, selecting an initial value as the timer value.

16. The system of claim 14, wherein selecting an initial value as the timer value comprises selecting the initial value from the group consisting of a lowest possible value, a highest possible value, a value in between the lowest possible value and the highest possible value and an average of a prior upper bound and a prior lower bound for the timer value.

17. The system of claim 14, wherein the most recent period is determined as an amount of time between a current time and a prior time at which the timer value was identified or elapsed.

18. The system of claim 14, wherein the instructions that are configured to cause the processor to perform operations comprising identifying a first adjustment to the timer value comprises instructions that are configured to cause the processor to perform operations comprising:

based on determining that a command is received out of sequence, identifying the first adjustment as a fixed number that is equal to or below zero; and

adding the first adjustment to the timer value.

19. The system of claim 14, wherein the instructions that are configured to cause the processor to perform operations comprising identifying a first adjustment to the timer value comprises instructions that are configured to cause the processor to perform operations comprising:

based on determining that no command is received out of sequence, identifying the first adjustment as a fixed number that is equal to or above zero; and

adding the first adjustment to the timer value.

20. The system of claim 14, wherein the instructions that are configured to cause the processor to perform operations comprising determining whether the resulting timer value is outside of a range of allowed adjustment results comprises instructions that are configured to cause the processor to perform operations comprising:

based on determining that the resulting timer value is outside of the range of allowed adjustment results, setting the resulting timer value to a nearest boundary value of the range.

21. The system of claim 14, comprising instructions that are configured to cause the processor to perform operations comprising:

receiving information associated with a command;

examining the received information;

determining, based on examining the received information, whether the command is out of order, whether the command was not received, whether the command is a highest sequence number command, or whether a number of times the command was received has exceeded a threshold value;

based on determining at least one of;

the command is out of order, the command was not received, the command is the highest sequence number command, and the number of times the command was received has exceeded the threshold value, recalculating the timer value for providing a newly identified timer value; and

setting the timer value based on the newly identified timer value.

22. The system of claim. 21, wherein the instructions that are configured to cause the processor to perform operations comprising setting the timer value based on the newly identified timer value comprises instructions that are configured to cause the processor to perform operations comprising:

subtracting from the newly identified timer value an amount. of time remaining on an existing timer;

determining whether a result of the subtracting is negative; and

based on determining that the result of the subtracting is not negative, setting the result of the subtracting as the timer value.

23. A system comprising:

a processor; and

instructions encoded in a non-transitory machine readable medium for execution by the processor and configured to cause the processor to perform operations comprising;

receiving commands associated with a network channel in a communications network;

receiving information from a neighboring network device indicating that the network device did not receive a command;

responsive to receiving the information, selecting a random number; and

sending missing commands to the neighboring network device based on the selected random number, including an indicator that the missing commands are sent as make up commands.

24. The system of claim 23, wherein the instructions that are configured to cause the processor to perform operations comprising receiving information from a neighboring network device indicating that the network device did not receive a command comprises instructions that are configured to cause the processor to perform operations comprising receiving information from the neighboring network device that includes at least one of:

a command with a sequence number that is two or more less than a highest sequence number command sent or received, and

an indication from the neighboring network device that it did not receive one or more commands.

25. The system of claim 23, wherein the instructions that are configured to cause the processor to perform operations comprising sending missing commands to the neighboring network device comprises instructions that are configured to cause the processor to perform operations comprising sending zero, one or more commands indicated as not received by the neighboring network device, and

wherein at least one of a number of missing commands sent and which missing commands are sent, is based on the selected random number.