Efficient rendezvous for distributed messages in frequency-hopping communication networks

• US 8,879,604 B2
• Filed: 07/06/2011
• Issued: 11/04/2014
• Est. Priority Date: 07/06/2011
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Woo, Lik Chuen Alec, Hui, Jonathan W., Hong, Wei
• Primary Examiner(s): Chan, Wing F
• Assistant Examiner(s): KRISHNAN, RAJESHWARI
• Application Number:
  US13/177,132
• Publication Number:
  US 20130013806A1
• Time in Patent Office: 1,217 Days
• Field of Search: 370/310, 370/336, 370/429, 370/445, 370/345, 375/139, 375132-135, 375/E1.033, 455/456.1, 455/525, 455/414.1, 455/419, 455/3.01, 709/212, 709/238, 709/207, 340/7.43, 717/116, 705/15, 705/5, 705/7.18, 705/7.19, 715/733
• US Class Current: 375/133
• CPC Class Codes: H04B 1/7156 Arrangements for sequence synchronisation
• CPC Class Codes: H04H 20/59 for emergency or urgency
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 5/06 the signals being represented by different frequencies combined with time-division multiplexing H04L5/26
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 72/30 Resource management for broadcast services
• CPC Class Codes: H04W 74/0808 using carrier sensing, e.g. carrier sense multiple access [CSMA]

Abstract

In one embodiment, a rendezvous request message is generated (e.g., by a sender) that specifies a channel C and a rendezvous time T for which a distributed message is to be transmitted in a frequency-hopping computer network. The rendezvous request message is then transmitted on one or more channels used in the computer network based on reaching a plurality of intended recipients of the distributed message with the rendezvous request message prior to rendezvous time T. Accordingly, the distributed message is then transmitted on channel C at rendezvous time T. In another embodiment, a device receives a rendezvous request message, and in response to determining to honor the rendezvous request message, listens for the distributed message on channel C at rendezvous time T.

Claims

1. A method, comprising:

generating a rendezvous request message, the rendezvous request message specifying a channel C and a rendezvous time T for which a distributed message is to be transmitted in a frequency-hopping computer network, and a priority indicating the importance of the distributed message to be transmitted on channel C at time T, wherein the computer network operates with one or more broadcast timeslots in a frequency-hopping sequence;

comparing a) transmission overhead and latency associated with transmitting the rendezvous request message, to b) waiting for a subsequent broadcast timeslot;

determining, based on the comparison, if it is worth waiting for the subsequent broadcast timeslot to transmit the distributed message;

in response to the determining that it is not worth waiting for the subsequent broadcast timeslot,

transmitting the rendezvous request message on one or more channels used in the computer network, the one or more channels based on reaching a plurality of intended recipients of the distributed message with the rendezvous request message prior to rendezvous time T, and

transmitting the distributed message on channel C at rendezvous time T; and

in response to the determining that it is worth waiting for the subsequent broadcast timeslot,

transmitting the distributed message during the subsequent broadcast timeslot.

2. The method as in claim 1, wherein the rendezvous time T is selected from a specified time and a delay until transmitting the distributed message.

3. The method as in claim 1, wherein transmitting the rendezvous request message on the one or more channels comprises transmitting the rendezvous request message once on each channel used in the computer network.

4. The method as in claim 3, wherein transmitting the rendezvous request message once on each channel used in the computer network comprises selecting an order of the channels based on a pseudo-random permutation.

5. The method as in claim 1, further comprising:

determining one or more reachable neighbors from the intended recipients; and

limiting the one or more channels on which the rendezvous request message is transmitted to those channels needed to reach the one or more reachable neighbors.

6. The method as in claim 1, further comprising:

maximizing channel overlap between the intended recipients for transmitting the rendezvous request message.

7. The method as in claim 1, wherein the one or more channels is a single channel transmitted during each timeslot of a frequency-hopping sequence, and wherein each of the intended recipients listens on the single channel at least once during the frequency-hopping sequence.

8. The method as in claim 1, further comprising:

determining that the distributed message extends beyond a single frame; and

in response, indicating within the distributed message transmission that the distributed message continues to at least a next frame.

9. The method as in claim 1, further comprising:

carrier sensing prior to transmitting the rendezvous request message; and

determining the rendezvous time T based on latency expected based on the carrier sensing.

10. The method as in claim 1, wherein the distributed message is a broadcast message to all reachable recipients in the computer network.

11. The method as in claim 1, wherein the distributed message is a multicast message to select intended recipients in the computer network.

12. An apparatus, comprising:

one or more network interfaces to communicate in a frequency-hopping computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

generate a rendezvous request message, the rendezvous request message specifying a channel C and a rendezvous time T for which a distributed message is to be transmitted in the frequency-hopping computer network, and a priority indicating the importance of the distributed message to be transmitted on channel C at time T, wherein the computer network operates with one or more broadcast timeslots in a frequency-hopping sequence;

compare a) transmission overhead and latency associated with transmitting the rendezvous request message, to b) waiting for a subsequent broadcast timeslot;

determine, based on the comparison, if it is worth waiting for the subsequent broadcast timeslot to transmit the distributed message;

in response to the determining that it is not worth waiting for the subsequent broadcast timeslot,

transmit the rendezvous request message on one or more channels used in the computer network, the one or more channels based on reaching a plurality of intended recipients of the distributed message with the rendezvous request message prior to rendezvous time T; and

transmit the distributed message on channel C at rendezvous time T; and

in response to the determining that it is worth waiting for the subsequent broadcast timeslot,

transmit the distributed message during the subsequent broadcast timeslot.

13. The apparatus as in claim 12, wherein the rendezvous time T is selected from a specified time and a delay until transmitting the distributed message.

14. The apparatus as in claim 12, wherein the processor when executed to transmit the rendezvous request message on the one or more channels is operable to transmit the rendezvous request message once on each channel used in the computer network.

15. The apparatus as in claim 12, wherein the processor when executed is further operable to:

determine one or more reachable neighbors from the intended recipients; and

limit the one or more channels on which the rendezvous request message is transmitted to those channels needed to reach the one or more reachable neighbors.

16. The apparatus as in claim 12, wherein the processor when executed is further operable to:

maximize channel overlap between the intended recipients for transmitting the rendezvous request message.

17. The apparatus as in claim 12, wherein the one or more channels is a single channel transmitted during each timeslot of a frequency-hopping sequence, and wherein each of the intended recipients listens on the single channel at least once during the frequency-hopping sequence.

18. The apparatus as in claim 12, wherein the distributed message is a broadcast message to all reachable recipients in the computer network.

19. The apparatus as in claim 12, wherein the distributed message is a multicast message to select intended recipients in the computer network.

20. A method, comprising:

receiving a rendezvous request message, the rendezvous request message specifying a channel C and a rendezvous time T for which a distributed message is to be transmitted in a frequency-hopping computer network, and a priority indicating the importance of the distributed message to be transmitted on channel C at time T, wherein the computer network operates with one or more broadcast timeslots in a frequency-hopping sequence;

determining whether to honor the rendezvous request message based upon the priority within the rendezvous request message; and

in response to determining to honor the rendezvous request message, listening for the distributed message on channel C at rendezvous time T,

wherein,

the rendezvous request message and distributed message are received from a transmitter in the network, in response to the transmitter comparing a) transmission overhead and latency associated with transmitting the rendezvous request message to b) waiting for a subsequent broadcast timeslot, and determining, based on the comparison, that it is not worth waiting for the subsequent broadcast timeslot, and

the distributed message is received during the subsequent broadcast timeslot from the transmitter, in response to the transmitter determining, based on the comparison, that it is worth waiting for the subsequent broadcast timeslot.

21. The method as in claim 20, further comprising:

determining to not honor the rendezvous request message in response to a higher priority task at rendezvous time T.

22. The method as in claim 20, further comprising:

determining to not honor the rendezvous request message; and

avoiding transmission on channel C at rendezvous time T.

23. An apparatus, comprising:

one or more network interfaces to communicate in a frequency-hopping computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

receive a rendezvous request message, the rendezvous request message specifying a channel C and a rendezvous time T for which a distributed message is to be transmitted in the frequency-hopping computer network, and a priority indicating the importance of the distributed message to be transmitted on channel C at time T, wherein the computer network operates with one or more broadcast timeslots in a frequency-hopping sequence;

determine whether to honor the rendezvous request message based upon the priority within the rendezvous request message; and

listen for the distributed message on channel C at rendezvous time T in response to determining to honor the rendezvous request message,

wherein,

the rendezvous request message and distributed message are received from a transmitter in the network, in response to the transmitter comparing a) transmission overhead and latency associated with transmitting the rendezvous request message to b) waiting for a subsequent broadcast timeslot, and determining, based on the comparison, that it is not worth waiting for the subsequent broadcast timeslot, and

the distributed message is received during the subsequent broadcast timeslot from the transmitter, in response to the transmitter determining, based on the comparison, that it is worth waiting for the subsequent broadcast timeslot.