Managing grey zones of unreachable nodes in computer networks

• US 9,118,539 B2
• Filed: 07/30/2012
• Issued: 08/25/2015
• Est. Priority Date: 07/30/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Hui, Jonathan W.
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): LEE, ANDREW CHUNG CHEUNG
• Application Number:
  US13/561,985
• Publication Number:
  US 20140029610A1
• Time in Patent Office: 1,121 Days
• Field of Search: 370/217, 370/221, 370/238, 370/338, 370/389, 370/392
• US Class Current: 1/1
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

In one embodiment, a node (e.g., a root-node) of a currently known directed acyclic graph (DAG) topology of a computer network can identify a sub-DAG of one or more nodes that are unreachable. The node can further determine a scope of the unreachable nodes of the sub-DAG and tunnel a redirected message to a reachable node of the DAG topology that is adjacent to at least one of the unreachable nodes of the sub-DAG. The redirected message may cause the reachable node to distribute the redirected message to one or more of the unreachable nodes of the sub-DAG based on the scope.

Claims

1. A method, comprising:

identifying, within a currently known directed acyclic graph (DAG) topology of a computer network, a sub-DAG of nodes that are unreachable, wherein the sub-DAG of unreachable nodes is a grey zone, the grey zone an area of the network where there is a lack of proper routing information to properly forward messages even though a feasible underlying path could exit;

determining a scope of the unreachable nodes of the sub-DAG;

tunneling a redirected message to a reachable node of the DAG topology that is adjacent to at least one of the unreachable nodes of the sub-DAG, the redirected message causing the reachable node to distribute the redirected message to one or more of the unreachable nodes of the sub-DAG based on the scope, wherein the redirected message has a time-to-live (TTL);

determining that the redirected message cannot reach a particular unreachable node of the one or more unreachable nodes;

increasing the TTL of the redirected message yielding a second redirected message; and

tunneling the second redirected message to the reachable node to cause the reach-able node to distribute the redirected message to the particular unreachable node with the increased TTL.

2. The method of claim 1, further comprising:

receiving an updated routing control message from one or more particular nodes of the one or more unreachable nodes that receives the redirected message; and

updating the DAG topology of the computer network based on the received updated routing control message.

3. The method of claim 1, wherein the redirected message is one of either a control message or a data message.

4. The method of claim 1, further comprising:

determining an alternate parent node route within the DAG topology for one or more particular nodes of the unreachable nodes;

removing each unreachable node that can be reached via the alternate patent node route from the sub-DAG; and

updating the DAG topology to reflect the alternate parent node route for each corresponding unreachable node.

5. The method of claim 1, further comprising:

comparing the increased TTL of the redirected message against a threshold; and

tunneling the redirected message having the increased TTL to the reachable node when the increased TTL is less than the threshold.

6. The method of claim 5, wherein the redirected message having the increased TTL is a probe message, the method further comprising:

tunneling the redirected message to a different reachable node of the DAG topology that is adjacent to the at least one of the unreachable nodes of the sub-DAG when the redirected message having the increased TTL is greater than the threshold.

7. The method of claim 1, wherein the redirected message causes the reachable node to distribute the redirected message via at least one of broadcasting or multicasting.

8. The method of claim 1, wherein the one or more nodes of the sub-DAG are nodes of the DAG topology sharing a same sub-root node that is unreachable by a root node of the DAG topology.

9. The method of claim 1, wherein determining the scope of the unreachable nodes of the sub-DAG further comprises:

correlating one or more received destination unreachable messages for the one or more unreachable nodes of the sub-DAG.

10. The method of claim 9, wherein the destination unreachable messages are internet control message protocol (lCMP) destination unreachable messages.

11. The method of claim 1, wherein determining the scope of the unreachable nodes of the sub-DAG further comprises:

sending connectivity verification messages to one or more nodes within the vicinity of the sub-DAG to determine which of the one or more nodes are unreachable.

12. The method of claim 1, wherein determining the scope of the unreachable nodes of the sub-DAG is based on knowledge of the DAG topology of a sub-root node of the sub-DAG.

13. The method of claim 1, wherein the identifying a sub-DAG of the one or more nodes that are unreachable is in response to receiving a particular number of retransmitted messages destined to one or more of the unreachable nodes of the sub-DAG.

14. An apparatus, comprising:

one or more network interfaces to communicate within a 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;

identify, within a currently known directed acyclic graph (DAG) topology of a computer network, a sub-DAG of nodes that are unreachable, wherein the sub-DAG of unreachable nodes is a grey zone, the grey zone an area of the network where there is a lack of proper routing information to properly forward messages even though a feasible underlying path could exit;

determine a scope of the unreachable nodes of the sub-DAG;

tunnel a redirected message to a reachable node of the DAG topology that is adjacent to at least one of the unreachable nodes of the sub-DAG, the redirected message causing the reachable node to distribute the redirected message to one or more of the unreachable nodes of the sub-DAG based on the scope;

determine that the redirected message cannot reach a particular unreachable node of the one or more unreachable nodes;

increase the TTL of the redirected message yielding a second redirected message; and

tunnel the second redirected message to the reachable node to cause the reachable node to distribute the redirected message to the particular unreachable node with the increased TTL.

15. The apparatus as in claim 14, wherein the process when executed is further operable to:

receive an updated routing control message from one or more particular nodes of the one or more unreachable nodes that receives the redirected message; and

update the DAG topology of the computer network based on the received updated routing control message.

16. The apparatus as in claim 14, wherein the redirected message is one of either a control message or a data message.

17. The apparatus as in claim 14, wherein the process when executed is further operable to:

determine an alternate parent node route within the DAG topology for one or more particular nodes of the unreachable nodes;

remove each unreachable node that can be reached via the alternate patent node route from the sub-DAG; and

update the DAG topology to reflect the alternate parent node route for each corresponding unreachable node.

18. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:

identify, within a currently known directed acyclic graph (DAG) topology of a computer network, a sub-DAG of nodes that are unreachable, wherein the sub-DAG of unreachable nodes is a grey zone, the grey zone an area of the network where there is a lack of proper routing information to properly forward messages even though a feasible underlying path could exit;

determine a scope of the unreachable nodes of the sub-DAG; and

tunnel a redirected message to a reachable node of the DAG topology that is adjacent to at least one of the unreachable nodes of the sub-DAG, the redirected message causes the reachable node to distribute the redirected message to one or more of the unreachable nodes of the sub-DAG based on the scope;

determine that the redirected message cannot reach a particular unreachable node of the one or more unreachable nodes;

increase the TTL of the redirected message yielding a second redirected message; and

tunnel the second redirected message to the reachable node to cause the reachable node to distribute the redirected message to the particular unreachable node with the increased TTL.