System and method for reliably communicating information without explicit acknowledgements

• US 7,844,212 B1
• Filed: 10/03/2007
• Issued: 11/30/2010
• 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:
  US11/906,952
• Time in Patent Office: 1,154 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 of ensuring a plurality of devices receive communications intended for them, the method comprising, at each of the plurality of devices, repeatedly performing a wireless rebroadcasting, each rebroadcasting comprising rebroadcasting a then highest ordered communication received by that device, the repeated rebroadcasting being directed to occur more frequently on average following a detection by that device of one or more events indicating that a different device did not receive at least the highest ordered communication received by that device, and less frequently on average following detection by that device of one or more events indicating that a different device likely received at least the highest ordered communication received by that device.

2. The method of claim 1, additionally comprising, at an originating device from which the communications were previously broadcast before receipt by any of the devices:

detecting whether some, though not all, devices have detected that other devices did not receive a most recent wireless broadcast communication; and

wirelessly rebroadcasting at least one previously broadcast communication responsive to the detecting step.

3. The method of claim 2, wherein each detection by the plurality of devices comprises detecting that a communication has been rebroadcast out of order.

4. The method of claim 2, wherein each detection by the plurality of devices comprises a function of a number of communications received per unit of time.

5. The method of claim 2, wherein the plurality of devices operate sineacknowledgemntly.

6. The method of claim 2, wherein each of the devices performs said rebroadcasting for each of a plurality of channels, the rebroadcasting for each channel by a device being performed independently of the rebroadcasting performed for a different channel by said device.

7. The method of claim 2, wherein an amount of time between successive rebroadcastings is at least partly determined at least pseudo-randomly.

8. The method of claim 2, wherein an amount of time between successive rebroadcastings is subject to at least one boundary.

9. A system for ensuring a plurality of devices receive communications intended for them, the system comprising the plurality of devices, comprising:

a receive manager having an input coupled to a radio for wirelessly receiving at least some of a plurality of communications comprising an indication of an order of the communications, each receive manager for providing at an output the plurality of communications received;

a retransmit manager having an input coupled to the receive manager output for receiving at least some of the plurality of communications and an output coupled to a radio, the retransmit manager for repeatedly performing a wireless rebroadcasting via its output coupled to the radio, each rebroadcasting comprising rebroadcasting a then highest ordered communication received from the receipt manager according to the indication, the frequency of repeated rebroadcasting being responsive to a timer signal received at a timer input;

a timer identification manager having an input coupled to the receive manager output for receiving information regarding a time of receipt of each of the at least some of the plurality of communications, and an output coupled to the broadcast manager timer input, the timer identification manager for causing the signal to be provided at the timer identification manager output coupled to the retransmit manager timer input more frequently on average responsive to a determination made using the information that one or more events indicating that a different device did not receive at least the highest ordered communication received by that device have occurred during a time window, and less frequently on average following detection by that device of one or more events indicating that a different device likely received at least the highest ordered communication received by that device during the time window.

10. The system of claim 9, additionally comprising an originating device from which the communications were previously broadcast before receipt by any of the devices, the originating device comprising:

a receive manager having an input coupled to a radio for receiving at least some of the rebroadcasts from at least some of the plurality of devices, the receive manager for providing at an output information regarding the at least some of the rebroadcasts received at the receive manager input;

a timer manager having an input coupled to the receive manager output for receiving the information, the timer manager for determining whether some, but not all, devices have detected that other devices did not receive a most recent wireless broadcast communication responsive to the information and causing at an output a timer signal to be provided responsive to said determining; and

a broadcast manager having a first input for receiving communications to be broadcast, and a second input coupled to the timer manager output for receiving the timer signal, the broadcast manager for rebroadcasting at least one previously broadcast communication responsive to the timer signal.

11. The system of claim 10, wherein each detection by the timer identification managers of each of the plurality of devices comprises detecting that a communication has been rebroadcast out of order.

12. The system of claim 10, wherein each detection by each of the timer identification managers in each of the plurality of devices comprises a function of a number of communications received per unit of time.

13. The system of claim 10, wherein the plurality of devices operate sineacknowledgemntly.

14. The system of claim 10, wherein each of the devices performs said rebroadcasting for each of a plurality of channels, the rebroadcasting for each channel by a device being performed independently of the rebroadcasting performed for a different channel by said device.

15. The system of claim 10, wherein the timer identification manager causes the signal to be provided at the timer identification manager output responsive to at least a pseudo random number.

16. The system of claim 10, wherein the timer identification manager causing the signal to be provided at the timer identification manager output additionally subject to at least one boundary.

17. A computer program product comprising a computer useable non-volatile storage medium having computer readable program code embodied therein for ensuring a plurality of devices receive communications intended for them, the computer program product comprising computer readable program code devices configured to cause a computer system to, at each of the plurality of devices, repeatedly perform a wireless rebroadcasting, each rebroadcasting comprising rebroadcasting a then highest ordered communication received by that device, the repeated rebroadcasting being directed to occur more frequently on average following a detection by that device of one or more events indicating that a different device did not receive at least the highest ordered communication received by that device, and less frequently on average following detection by that device of one or more events indicating that a different device likely received at least the highest ordered communication received by that device.

18. The computer program product of claim 17, additionally comprising the computer readable program code devices configured to cause the computer system to, at an originating device from which the communications were previously broadcast before receipt by any of the devices:

detect whether some, though not all, devices have detected that other devices did not receive a most recent wireless broadcast communication; and

wirelessly rebroadcast at least one previously broadcast communication responsive to the detecting step.

19. The computer program product of claim 18, wherein each detection by the plurality of devices comprises detecting that a communication has been rebroadcast out of order.

20. The computer program product of claim 19, wherein each detection by the plurality of devices comprises a function of a number of communications received per unit of time.

21. The computer program product of claim 19, wherein the plurality of devices operate sineacknowledgemntly.

22. The computer program product of claim 20, wherein each of the devices performs said rebroadcasting for each of a plurality of channels, the rebroadcasting for each channel by a device being performed independently of the rebroadcasting performed for a different channel by said device.

23. The computer program product of claim 20, wherein an amount of time between successive rebroadcastings is at least partly determined at least pseudo-randomly.

24. The computer program product of claim 18, wherein an amount of time between successive rebroadcastings is subject to at least one boundary.