SYSTEMATIC NEIGHBOR DETECTION IN SHARED MEDIA COMPUTER NETWORKS

• US 20120320790A1
• Filed: 06/20/2011
• Published: 12/20/2012
• 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: Shaffer, Shmuel, Shetty, Sandeep J., Geiger, Richard G.
• Granted Patent: US 9,723,538 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• 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 a set of network parameters for a 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 using an identification of a particular node in the network to determine in which particular timeslot of the frames to transmit a network discovery packet; and

transmitting the network discovery packet from the particular node in the particular timeslot of the frames, the network discovery packet carrying the network parameters and the identification of the particular node.

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 identification is a media access control (MAC) address of the particular node.

4. 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.

5. 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.

6. The method as in claim 5, 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.

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

8. 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.

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

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

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

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

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.

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

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

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

15. 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.

16. A method, comprising:

receiving, at a particular node in a shared media computer network, a network discovery request from a requesting node;

determining whether the particular node is free to reply to the network discovery s request based on one or more parameters in the network discovery request; and

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.

17. The method as in claim 16, 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. The method as in claim 16, wherein a particular parameter of the one or more parameters limits freedom to reply to those certain nodes having an identification that when input into a particular hash function results in deterministic differentiation from other nodes in the network.

19. The method as in claim 16, wherein a particular parameter of the one or more parameters limits freedom to reply to those certain nodes operating on a particular channel.

20. A method, comprising:

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

in response to 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 using an identification of a particular node in the network to determine in which particular timeslot of the frames to transmit a network discovery packet; and

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

in response to 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 one or more parameters in the network discovery request; 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.

21. 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;

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

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

compute a discovery scheduling function using an identification of the apparatus to determine in which particular timeslot of the frames to transmit a network discovery packet; and

transmit the network discovery packet in the particular timeslot of the frames, the network discovery packet carrying the network parameters and the identification of the apparatus.

22. 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;

receive a network discovery request from a requesting node;

determine whether the apparatus is free to reply to the network discovery request based on one or more parameters in the network discovery request; and

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

23. The apparatus as in claim 22, wherein a particular parameter of the one or more parameters is selected from a group consisting of:

a first parameter that limits freedom to reply to those certain nodes receiving the network discovery request at a receive signal strength greater than a configured threshold;

a second parameter that limits freedom to reply to those certain nodes having an identification that when input into a particular hash function results in deterministic differentiation from other nodes in the network; and

a third parameter that limits freedom to reply to those certain nodes operating on a particular channel.