Mesh network addressing

Patent metadata

Field	Value
Publication number	US-9300581-B1
Application number	US-201514798456-A
Country	US
Kind code	B1
Filing date	Jul 13, 2015
Priority date	Feb 3, 2015
Publication date	Mar 29, 2016
Grant date	Mar 29, 2016

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.

First claim

The invention claimed is:

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

Assignees

• Google Inc
• Google Inc

Inventors

• Hui Jonathan Wing-Yan
• Turon Martin A
• Woodyatt James H

Classifications

• H04W84/18

  Self-organising networks, e.g. ad-hoc networks or sensor networks · CPC title

• H04W72/56

  based on priority criteria · CPC title

• H04L45/74 Primary

  Address processing for routing · CPC title

• H04L45/04 Primary

  Interdomain routing, e.g. hierarchical routing · CPC title

• H04W40/02

  Communication route or path selection, e.g. power-based or shortest path routing · CPC title