Systematic neighbor detection in shared media computer networks

• US 9,723,538 B2
• Filed: 06/20/2011
• Issued: 08/01/2017
• Est. Priority Date: 06/20/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shetty, Sandeep J., Geiger, Richard G., Shaffer, Shmuel
• Primary Examiner(s): Sefcheck, Gregory
• Assistant Examiner(s): ULYSSE, JAEL M
• Application Number:
  US13/164,734
• Publication Number:
  US 20120320790A1
• Time in Patent Office: 2,234 Days
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In one embodiment, a particular node in a shared media computer network may determine a set of network parameters for the network, and a timing of super-frames in the network, each super-frame having one or more frames, each frame divided into a plurality of timeslots. In addition, the particular node computes a discovery scheduling function using its own identification to determine in which particular timeslot of the frames to transmit a network discovery packet. Accordingly, the particular node may transmit the network discovery packet in the particular timeslot of the frames. In an additional or alternative embodiment, the particular node may receive a network discovery request from a requesting node. In response, the particular node determines whether it is free to reply to the network discovery request based on parameters in the network discovery request, and if free to reply, may transmit a network discovery packet to the requesting node.

Claims

1. A method, comprising:

determining, by a particular node, whether a shared media computer network is operating in a passive discovery mode or an active discovery mode;

based on determining that the shared media computer network is operating in a passive discovery mode, executing a passive discovery mode at the particular node in a shared media computer network to initially form a neighbor relationship by;

receiving, at a particular node, a set of network parameters for the shared media computer network;

determining, by the particular node, a timing of super-frames in the network, each super-frame having one or more frames, each frame divided into a plurality of timeslots;

computing, by the particular node, a discovery scheduling function to determine which particular timeslot of the one or more frames a network discovery packet is to be transmitted from the particular node, wherein the particular timeslot is determined based on a media access control (MAC) address of the particular node in the network being input to the discovery scheduling function;

transmitting, by the particular node, the network discovery packet from the particular node during the particular timeslot of the frames determined by the discovery scheduling function, the network discovery packet carrying the network parameters and the MAC address of the particular node;

receiving a network discovery packet at the particular node from a second node in the network; and

transmitting the network discovery packet from the particular node at a transmission power based on an indication in the received network discovery packet.

2. The method as in claim 1, wherein the discovery scheduling function is computed to individually determine a frame-specific timeslot for each of the frames.

3. The method as in claim 1, wherein the network discovery packet is transmitted on a particular channel, and wherein the super-frame is specific to the particular channel.

4. The method as in claim 1, wherein a number of the plurality of timeslots is adjusted based on a number of nodes in the network.

5. The method as in claim 4, wherein the network discovery packet is transmitted on a particular channel, and wherein the number of the plurality of timeslots is adjusted based on the number of nodes in the network operating on the particular channel.

6. The method as in claim 1, wherein determining the timing of super-frames is based on the network parameters.

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

receiving the network parameters at the particular node in a received network discovery packet from a second node in the network.

8. The method as in claim 7, wherein the second node is a root node of a directed acyclic graph (DAG).

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

synchronizing super-frame timing based on the received network discovery packet.

10. The method as in claim 1, wherein the particular node is a root node of a directed acyclic graph (DAG).

11. The method as in claim 10, wherein the particular timeslot is a synchronization timeslot specific to the root node.

12. The method as in claim 11, wherein there is only a single synchronization timeslot in the super-frame.

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

including in the transmitted network discovery packet a channel access back-off parameter based on a received power of the transmitted network discovery packet at one or more receiving nodes, the channel access back-off parameter to bias channel access toward receiving nodes with higher received power than a received power of other receiving nodes.

14. A method, comprising:

executing an active discovery mode at a particular node in a shared media computer network to initially form a neighbor relationship with a requesting node;

receiving, at a particular node in a shared media computer network, a network discovery request from the requesting node, wherein the network discovery request includes one or more parameters that specifically limits freedom to reply to the requesting node;

based on the one or more parameters, determining whether the particular node is free to reply to the network discovery request based on at least on a received power range included in the network discovery request and a received signal strength of the network discovery request, wherein the particular node is free to reply to the network discovery request when the received signal strength is within the received power range;

in response to being free to reply to the network discovery request, transmitting a network discovery packet from the particular node to the requesting node; and

in response to being determining that the particular node is not free to reply to the network discovery request, excluding transmission of the network discovery packet to the requesting node.

15. The method as in claim 14, wherein the particular node is not free to reply to those certain nodes having a media access control (MAC) address that when input into a particular hash function results in deterministic differentiation from other nodes in the network.

16. The method as in claim 14, wherein the particular node is not free to reply to those certain nodes operating on a particular channel.

17. The method as in claim 14, wherein a particular parameter of the one or more parameters limits freedom to reply to those certain nodes receiving the network discovery request at a receive signal strength greater than a configured threshold.

18. A method, comprising:

determining, by a particular node, whether a shared media computer network is operating in a passive discovery mode or an active discovery mode;

based on determining that the shared media computer network is operating in a passive discovery mode;

determining a set of network parameters for the shared media computer network;

determining a timing of super-frames in the network, each super-frame having one or more frames, each frame divided into a plurality of timeslots;

computing a discovery scheduling function to determine during which particular timeslot of the one or more frames a network discovery packet is to be transmitted from the particular node, wherein the particular timeslot is determined based on an identification of the particular node in the network being input to the discovery scheduling function; and

transmitting the network discovery packet from the particular node in the particular timeslot of the frames determined by the discovery scheduling function, the network discovery packet carrying the network parameters and the identification of the particular node; and

based on determining that the shared media computer network is operating in an active discovery mode;

receiving, at the particular node, a network discovery request from a requesting node;

determining whether the particular node is free to reply to the network discovery request based on at least on a received power range included in the network discovery request and a received signal strength of the network discovery request, wherein the particular node is free to reply to the network discovery request when the received signal strength is within the received power range; and

in response to being free to reply to the network discovery request, transmitting the network discovery packet from the particular node to the requesting node.

19. An apparatus, comprising:

one or more network interfaces to communicate in a shared media 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;

execute a passive discovery mode to initially form a neighbor relationship by;

determining whether a shared media computer network is operating in a passive discovery mode or an active discovery mode;

based on determining that the shared media computer network is operating in a passive discovery mode;

receiving a set of network parameters for the shared media computer network;

determining a timing of super-frames in the network, each super-frame having one or more frames, each frame divided into a plurality of timeslots;

computing a discovery scheduling function to determine during which particular timeslot of the one or more frames a network discovery packet is to be transmitted from the particular node, wherein the particular timeslot is determined based on a media access control (MAC) address of the particular node in the network being input to the discovery scheduling function;

transmitting the network discovery packet in the particular timeslot of the frames, the network discovery packet carrying the network parameters and the MAC address of the apparatus;

receiving a network discovery packet from a second node in the network; and

transmitting the network discovery packet at a transmission power based on an indication in the received network discovery packet.

20. An apparatus, comprising:

one or more network interfaces to communicate in a shared media 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;

execute an active mode to initially form a neighbor relationship with a requesting node by;

receiving a network discovery request from a requesting node, wherein the network discovery request includes one or more parameters that specifically limits freedom to reply to the requesting node;

based on the one or more parameters, determining whether the apparatus is free to reply to the network discovery request;

in response to being free to reply to the network discovery request, transmit a network discovery packet to the requesting node; and

in response to being determining that the particular node is not free to reply to the network discovery request, excluding transmission of the network discovery packet to the requesting node.

21. The apparatus as in claim 20, wherein the particular node is not free to reply to those certain nodes receiving the network discovery request at a receive signal strength greater than a configured threshold;

those certain nodes having a media access control (MAC) address of the particular node that when input into a particular hash function results in deterministic differentiation from other nodes in the network;

or those certain nodes operating on a particular channel.