Mesh network addressing

• US 9,300,581 B1
• Filed: 07/13/2015
• Issued: 03/29/2016
• Est. Priority Date: 02/03/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hui, Jonathan Wing-Yan, Turon, Martin A., Woodyatt, James H.
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Kaur, Pamit
• Application Number:
  US14/798,456
• Time in Patent Office: 260 Days
• Field of Search: 370/400, 370/396, 370/395.31
• US Class Current: 1/1
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 2101/659 Internet protocol version 6 [IPv6] addresses
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 45/741 Routing in networks with a plurality of addressing schemes, e.g. with both IPv4 and IPv6
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 61/5014 using dynamic host configuration protocol [DHCP] or bootstrap protocol [BOOTP]
• CPC Class Codes: H04L 61/5092 by self-assignment, e.g. picking addresses at random and testing if they are already in use
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 72/56 based on priority criteria
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In embodiments of mesh network addressing for duplicate address detection, an end device of the mesh network can generate an address identifier that includes an address and time-based information associated with the end device, which is attached to a router device for communication in the mesh network. The address identifier is maintained by the router device as a tuple state of the end device. The end device or the router device can initiate an address query requesting that mesh network devices in the mesh network having a designated address respond with the tuple state that corresponds to the designated address. The end device or router device receives the tuple state of mesh network devices having the designated address in response to the address query, and can then detect a duplicate address of a mesh network device based on the time based information.

Claims

1. A method of detecting duplicate addresses in a mesh network, the method comprising:

generating, by an end device, an address identifier that includes an address and time-based information associated with the end device that is attached to a router device for communication in the mesh network, the address identifier being maintained by the router device as a tuple state of the end device;

initiating an address query requesting that mesh network devices in the mesh network having a designated address respond with the tuple state that corresponds to the designated address;

receiving the tuple state of a mesh network device having the designated address in response to the address query; and

detecting a duplicate address of the mesh network device based on the time-based information that is maintained as part of the tuple state of the mesh network device.

2. The method as recited in claim 1, further comprising comparing the time-based information in the tuple state of the mesh network device to the time-based information in the tuple state of the end device to said detect the duplicate address of the mesh network device.

3. The method as recited in claim 1, further comprising directing one or more of the mesh network devices that have the duplicate address to generate a new address.

4. The method as recited in claim 1, wherein the end device said initiates the address query, receives the tuple state of the mesh network device having the designated address, and detects the duplicate address of the mesh network device based on the time-based information.

5. The method as recited in claim 1, wherein the router device said initiates the address query, receives the tuple state of the mesh network device having the designated address, and detects the duplicate address of the mesh network device based on the time-based information.

6. The method as recited in claim 1, wherein:

the address identifier further includes a random value generated by the end device; and

said detecting the duplicate address of the mesh network device is based on the random value that is maintained as part of the tuple state of the mesh network device.

7. A mesh network device implemented as an end device of a mesh network, the end device comprising:

a mesh network interface configured for communication in the mesh network via a router device;

a memory and processor system to implement an addressing application that is configured to;

generate an address identifier that includes address information associated with the end device that is attached to the router device, the address identifier being maintained by the router device as a tuple state of the end device;

initiate an address query requesting that mesh network devices in the mesh network having a designated address respond with the tuple state that corresponds to the designated address;

receive, via the mesh network interface, the tuple state of a mesh network device having the designated address in response to the address query; and

detect a duplicate address of the mesh network device based on the address information that is maintained as part of the tuple state of the mesh network device.

8. The mesh network device as recited in claim 7, wherein the address identifier further includes time-based information associated with the end device that is attached to the router device.

9. The mesh network device as recited in claim 8, wherein the addressing application is configured to compare the time-based information in the tuple state of the mesh network device to the time-based information in the tuple state of the end device to said detect the duplicate address of the mesh network device.

10. The mesh network device as recited in claim 7, wherein the addressing application is configured to direct one or more of the mesh network devices that have the duplicate address to generate a new address.

11. The mesh network device as recited in claim 7, wherein the addressing application is configured to generate a random value as part of the address information, the address identifier including an address of the end device, the random value, and a lifetime duration that indicates how long the router device is to maintain the tuple state of the end device.

12. The mesh network device as recited in claim 11, wherein the address identifier further includes one or more previous random values generated by the addressing application, the one or more previous random values corresponding to the end device being previously attached to one or more respective router devices.

13. The mesh network device as recited in claim 11, wherein the addressing application is configured to compare the random value in the tuple state of the mesh network device to the random value in the tuple state of the end device to said detect the duplicate address of the mesh network device.

14. The mesh network device as recited in claim 11, wherein the addressing application is configured to determine that the address of the mesh network device is not the duplicate address if the random value in the tuple state of the mesh network device matches the random value in the tuple state of the end device.

15. The mesh network device as recited in claim 11, wherein the addressing application is configured to encode the random value using the lifetime duration.

16. A mesh network system, comprising:

a router device of a mesh network, the router device configured for communication in the mesh network; and

a mesh network device implemented as an end device of the mesh network, the end device attached to the router device for the communication in the mesh network, the end device configured to;

generate an address identifier that includes an address and time-based information associated with the end device that is attached to the router device, the address identifier being maintained by the router device as a tuple state of the end device;

initiate an address query requesting that mesh network devices in the mesh network having a designated address respond with the tuple state that corresponds to the designated address;

receive the tuple state of a mesh network device having the designated address in response to the address query; and

detect a duplicate address of the mesh network device based on the time-based information that is maintained as part of the tuple state of the mesh network device.

17. The mesh network system as recited in claim 16, wherein the end device is configured to compare the time-based information in the tuple state of the mesh network device to the time-based information in the tuple state of the end device to said detect the duplicate address of the mesh network device.

18. The mesh network system as recited in claim 16, wherein the end device is configured to direct one or more of the mesh network devices that have the duplicate address to generate a new address.

19. The mesh network system as recited in claim 16, wherein:

the address identifier further includes a random value generated by the end device; and

the end device is configured to detect the duplicate address of the mesh network device is based on the random value that is maintained as part of the tuple state of the mesh network device.

20. The mesh network system as recited in claim 16, wherein the end device is configured to generate a random value as part of the address information, the address identifier including an address of the end device, the random value, and a lifetime duration that indicates how long the router device is to maintain the tuple state of the end device.