FAST AND LOSS-FREE LOCAL RECOVERY BY A RPL PARENT DEVICE

• US 20190081892A1
• Filed: 03/15/2018
• Published: 03/14/2019
• Est. Priority Date: 09/13/2017
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: THUBERT, PASCAL, WETTERWALD, PATRICK
• Granted Patent: US 10,491,515 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

In one embodiment, a network device (e.g., a RPL router) executes fast local RPL recovery in a low power and lossy network (LLN). The network device, in response to becoming an orphan in a directed acyclic graph (DAG) topology, can utilize the data plane to maintain at least some data traffic by randomly forwarding the data traffic to identified neighbor devices, while eliminating children from the list of forwarders and by finding successors that can be used for re-parenting. Hence, when a RPL network device having lost its last feasible parent can avoid data loss and accelerate a re-parenting process using local repair in the data plane instead of the control plane of the routing protocol used to establish the DAG topology.

Claims

1. A method comprising:

detecting, by a network device having established a connection with a parent network device in a directed acyclic graph (DAG) topology established according to a prescribed routing protocol in a communication network, that the network device has become an orphan based on detecting a loss of the connection with the parent network device;

receiving, by the network device, a data packet from a child network device having attached to the network device according to the prescribed routing protocol; and

forwarding, by the network device, a flagged copy of the data packet to one or more randomly-selected neighboring network devices, for attempted forwarding into the DAG topology, including setting in the flagged copy a loop detection flag that enables the network device to detect whether the flagged copy is returned to the network device.

2. The method of claim 1, further comprising the network device identifying the one or more neighboring network devices distinct from the prescribed routing protocol.

3. The method of claim 1, further comprising:

receiving a second data packet from the child network device;

determining the second data packet is the flagged copy comprising the loop detection flag; and

deleting the child network device from becoming a prospective parent for attempted recovery within the DAG topology.

4. The method of claim 3, further comprising:

determining the child network device having sent the flagged data packet to the network device is one of the one or more randomly-selected neighboring network devices in response to detecting a forwarding error flag in the flagged copy.

5. The method of claim 3, further comprising:

storing a pending target entry identifying the one or more neighboring network device having been forwarded the flagged data packet;

identifying the one neighboring network device having forwarded the flagged data packet to the child network device based on the corresponding pending target entry; and

deleting the one identified neighboring network device having forwarded the flagged data packet from becoming a prospective parent for the attempted recovery within the DAG topology.

6. The method of claim 1, wherein the forwarding further includes setting a rank field in the flagged copy to a worst-rank value higher than any other rank in the DAG topology.

7. One or more non-transitory tangible media encoded with logic for execution by a machine and when executed by the machine operable for:

detecting, by the machine implemented as a network device having established a connection with a parent network device in a directed acyclic graph (DAG) topology established according to a prescribed routing protocol in a communication network, that the network device has become an orphan based on detecting a loss of the connection with the parent network device;

receiving, by the network device, a data packet from a child network device having attached to the network device according to the prescribed routing protocol; and

forwarding, by the network device, a flagged copy of the data packet to one or more randomly-selected neighboring network devices, for attempted forwarding into the DAG topology, including setting in the flagged copy a loop detection flag that enables the network device to detect whether the flagged copy is returned to the network device.

8. The one or more non-transitory tangible media of claim 7, further operable for identifying the one or more neighboring network devices distinct from the prescribed routing protocol.

9. The one or more non-transitory tangible media of claim 7, further operable for:

receiving a second data packet from the child network device;

determining the second data packet is the flagged copy comprising the loop detection flag; and

deleting the child network device from becoming a prospective parent for attempted recovery within the DAG topology.

10. The one or more non-transitory tangible media of claim 9, further operable for:

determining the child network device having sent the flagged data packet to the network device is one of the one or more randomly-selected neighboring network devices in response to detecting a forwarding error flag in the flagged copy.

11. The one or more non-transitory tangible media of claim 9, further operable for:

storing a pending target entry identifying the one or more neighboring network device having been forwarded the flagged data packet;

identifying the one neighboring network device having forwarded the flagged data packet to the child network device based on the corresponding pending target entry; and

deleting the one identified neighboring network device having forwarded the flagged data packet from becoming a prospective parent for the attempted recovery within the DAG topology.

12. The one or more non-transitory tangible media of claim 7, wherein the forwarding further includes setting a rank field in the flagged copy to a worst-rank value higher than any other rank in the DAG topology.

13. A method comprising:

detecting, by a network device having established a connection with a parent network device in a directed acyclic graph (DAG) topology established according to a prescribed routing protocol in a communication network, that the network device has become an orphan based on detecting a loss of the connection with the parent network device;

outputting, by the network device, a message for a root of the DAG topology based on identifying a neighboring network device, including inserting into the message a request for the root to send a response via the identified neighboring network device, and sending the message to the neighboring network device; and

selectively executing fast parent selection based on identifying the neighboring network device as a feasible successor parent device in response to receiving the response from the root via the neighboring network device, distinct from the prescribed routing protocol that established the DAG topology.

14. The method of claim 13, wherein the outputting includes:

identifying the neighboring network device based on registering a link layer address of the network device with the neighboring network device according to a neighbor discovery protocol distinct from the prescribed routing protocol;

unicasting transmitting the message to the neighboring network device.

15. The method of claim 13, further comprising:

identifying one or more neighboring network devices as feasible successor parent devices based on one or more of the replies from the root;

the fast parent selection including identifying, from among the feasible successor parent devices, a preferred parent device having a best relative rank within the DAG topology.

16. The method of claim 15, wherein the identifying of feasible successor parent devices includes detecting, in the one reply from the root, a routing header identifying each of the feasible successor parent devices.

17. One or more non-transitory tangible media encoded with logic for execution by a machine and when executed by the machine operable for:

detecting, by the machine implemented as a network device having established a connection with a parent network device in a directed acyclic graph (DAG) topology established according to a prescribed routing protocol in a communication network, that the network device has become an orphan based on detecting a loss of the connection with the parent network device;

outputting, by the network device, a message for a root of the DAG topology based on identifying a neighboring network device, including inserting into the message a request for the root to send a response via the identified neighboring network device, and sending the message to the neighboring network device; and

selectively executing fast parent selection based on identifying the neighboring network device as a feasible successor parent device in response to receiving the response from the root via the neighboring network device, distinct from the prescribed routing protocol that established the DAG topology.

18. The one or more non-transitory tangible media of claim 17, wherein the outputting includes:

identifying the neighboring network device based on registering a link layer address of the network device with the neighboring network device according to a neighbor discovery protocol distinct from the prescribed routing protocol;

unicasting transmitting the message to the neighboring network device.

19. The one or more non-transitory tangible media of claim 17, further operable for:

identifying one or more neighboring network devices as feasible successor parent devices based on one or more of the replies from the root;

the fast parent selection including identifying, from among the feasible successor parent devices, a preferred parent device having a best relative rank within the DAG topology.

20. The one or more non-transitory tangible media of claim 19, wherein the identifying of feasible successor parent devices includes detecting, in the one reply from the root, a routing header identifying each of the feasible successor parent devices.