Automatic rerouting in thread networks

• US 10,462,053 B2
• Filed: 01/02/2019
• Issued: 10/29/2019
• Est. Priority Date: 07/10/2017
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Hui, Jonathan Wing-Yan
• Primary Examiner(s): Ho, Duc C
• Application Number:
  US16/238,438
• Publication Number:
  US 20190140948A1
• Time in Patent Office: 300 Days
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 84/22 with access to wired networks

Abstract

In aspects of automatic rerouting in Thread networks, a router device in a mesh network receives a packet to forward to a destination node, and the packet includes a Routing Locator (RLOC) for the destination node. The router device can determine that the packet cannot be forwarded using the RLOC. The router device can then initiate an address query over the mesh network, where the address query includes an Endpoint Identifier (EID) of the destination node. The router device can receive an EID-to-RLOC mapping for the EID from a node device in the mesh network, and forward the packet to the destination node using the received EID-to-RLOC mapping.

Claims

1. A method of rerouting a packet in a mesh network, the method comprising:

receiving, by a backbone router connected to the mesh network, a message from a router in the mesh network requesting an address query across other mesh networks connected to a backbone network, the message including an Endpoint Identifier (EID) of a destination node for the packet;

transmitting the address query to other backbone routers connected to the backbone network, the address query including the EID of the destination node;

receiving, from at least one of the other backbone routers, an EID-to-Routing Locator (RLOC) mapping for the EID; and

transmitting the received EID-to-RLOC mapping to the router, the transmitting configuring the router to forward the packet to the destination node using the received EID-to-RLOC mapping.

2. The method of claim 1, further comprising:

updating, by the backbone router, a cache of EID-to-RLOC mappings stored by the backbone router to include the received EID-to-RLOC mapping.

3. The method of claim 2, further comprising:

updating, by the backbone router, the cache of EID-to-RLOC mappings by opportunistically obtaining EID-to-RLOC mappings by observing mesh network traffic or backbone network traffic routed through the backbone router.

4. The method of claim 1, further comprising:

receiving, by the backbone router, the packet comprising a destination address including the RLOC included in the received EID-to-RLOC mapping; and

forwarding, using the destination address, the packet to another backbone router.

5. The method of claim 1, further comprising:

receiving, by the backbone router, an address notification message including the received EID-to-RLOC mapping; and

forwarding the address notification message to a source node that transmitted the packet.

6. The method of claim 5, wherein the source node is a cloud service.

7. The method of claim 1, wherein the transmitting the address query to other backbone routers connected to the backbone network is effective to cause each of the other backbone routers to:

search, based on the address query, a respective cache of EID-to-RLOC mappings stored in each of the other backbone routers;

or

transmit the address query to nodes in a respective mesh network connected to each of the other backbone routers.

8. The method of claim 1, further comprising:

receiving, by the backbone router and via to the backbone network, another address query from one of the other backbone routers, the other address query including another EID;

searching, based on the other address query, a cache of EID-to-RLOC mappings stored in the backbone router; and

if an EID-to-RLOC mapping for the other address query is found in the cache, transmitting the found EID-to-RLOC mapping for the other address query across the backbone network;

or

if the EID-to-RLOC mapping for the other address query is not found in the cache, transmitting the other address query to nodes in the mesh network.

9. A mesh network device implemented as a backbone router device, the backbone router device comprising:

a mesh network interface configured for communication in a mesh network;

a backbone network interface configured for communication with other backbone routers in a backbone network, each of the other backbone routers being connected to a respective other mesh network; and

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

receive, using the mesh network interface, a message from a router in the mesh network requesting an address query across the other mesh networks, the message including an Endpoint Identifier (EID) of a destination node for a packet;

transmit, using the backbone network interface, the address query to the other backbone routers, the address query including the EID of the destination node;

receive, using the backbone network interface and from at least one of the other backbone routers, an EID-to-Routing Locator (RLOC) mapping for the EID; and

transmit, using the mesh network interface, the received EID-to-RLOC mapping to the router, the transmission configuring the router to forward the packet to the destination node using the received EID-to-RLOC mapping.

10. The mesh network device of claim 9, wherein the application is configured to update a cache of EID-to-RLOC mappings stored by the backbone router device to include the received EID-to-RLOC mapping.

11. The mesh network device of claim 9, wherein the application is configured to update a cache of EID-to-RLOC mappings by opportunistically obtaining EID-to-RLOC mappings by observing mesh network traffic or backbone network traffic routed through the backbone router device.

12. The mesh network device of claim 9, wherein the application is configured to:

receive, using the mesh network interface, the packet comprising a destination address including the RLOC included in the received EID-to-RLOC mapping; and

forward, using the destination address and the backbone network interface, the packet to another backbone router.

13. The mesh network device of claim 9, wherein the application is configured to:

receive, using the mesh network interface, an address notification message including the received EID-to-RLOC mapping; and

forward the address notification message to a source node that transmitted the packet, wherein the source node is a cloud service.

14. The mesh network device of claim 9, wherein the transmission of the address query to the other backbone routers is effective to cause each of the other backbone routers to:

search, based on the address query, a respective cache of EID-to-RLOC mappings stored in each of the other backbone routers;

or

transmit the address query to nodes in a respective mesh network connected to each of the other backbone routers.

15. The mesh network device of claim 9, wherein the application is configured to:

receive, using the backbone network interface, another address query from one of the other backbone routers, the other address query including another EID;

search, based on the other address query, a cache of EID-to-RLOC mappings stored in the backbone router device; and

if an EID-to-RLOC mapping for the other address query is found in the cache, transmit, using the backbone network interface, the found EID-to-RLOC mapping for the other address query across the backbone network;

or

if the EID-to-RLOC mapping for the other address query is not found in the cache, transmit, using the mesh network interface, the other address query to nodes in the mesh network.

16. A system comprising:

a mesh network including a mesh-network router device;

a backbone router device connected to the mesh network and a backbone network; and

other backbone routers connected to the backbone network and other respective mesh networks;

the backbone router device configured to;

receive, from the mesh-network router device via the mesh network, a message requesting an address query across the other mesh networks, the message including an Endpoint Identifier (EID) of a destination node for a packet;

transmit the address query to the other backbone routers using the backbone network, the address query including the EID of the destination node;

receive, from at least one of the other backbone routers, an EID-to-Routing Locator (RLOC) mapping for the EID; and

transmit the received EID-to-RLOC mapping to the router, the transmission configuring the mesh-network router to forward the packet to the destination node using the received EID-to-RLOC mapping.

17. The system of claim 16, wherein the other backbone routers are configured to:

search, based on the address query, a respective cache of EID-to-RLOC mappings stored in each of the other backbone routers;

or

transmit the address query to nodes in the other respective mesh networks connected to each of the other backbone routers.

18. The system of claim 16, wherein the backbone router device is configured to:

update a cache of EID-to-RLOC mappings stored by the backbone router device to include the received EID-to-RLOC mapping.

19. The system of claim 16, wherein the backbone router device is configured to:

receive, via the mesh network, the packet comprising a destination address including the RLOC included in the received EID-to-RLOC mapping; and

forward, using the destination address, the packet to another of the backbone routers.

20. The system of claim 16, wherein the backbone router device is configured to:

receive, via the backbone network, another address query from one of the other backbone routers, the other address query including another EID;

search, based on the other address query, a cache of EID-to-RLOC mappings stored in the backbone router device; and

if an EID-to-RLOC mapping for the other address query is found in the cache, transmit the found EID-to-RLOC mapping for the other address query across the backbone network;

or

if the EID-to-RLOC mapping for the other address query is not found in the cache, transmit the other address query to nodes in the mesh network.