# US 2019/0356583 A1 · Distance vector negative southbound topology information for routing in fat trees (rift) route

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0356583 A1
- Document ID: US20190356583A1
- Status: Published application
- Kind: A1
- Application number: 16/202,780
- Filed: 2018-11-28
- Published: 2019-11-21
- Earliest claimed: 2018-05-21
- Assignees: Cisco Technology, Inc.
- Applicants: Cisco Technology, Inc.
- Inventors: Pascal Thubert; Nagendra Kumar Nainar; Carlos M. Pignataro
- Web page: https://patentgrep.com/patent/US20190356583A1

## CPC

- H04L 12/4625: {Single bridge functionality, e.g. connection of two networks over a single bridge}
- H04L 12/44: Star or tree networks
- H04L 12/4641: {Virtual LANs, VLANs, e.g. virtual private networks [VPN] (LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272)}
- H04L 45/02: Topology update or discovery
- H04L 45/123: {Evaluation of link metrics (techniques for monitoring network metrics H04L43/08)}
- H04L 45/48: Routing tree calculation
- H04W 40/248: {Connectivity information update}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

In one embodiment, a method is performed. A spine node in communication with a network may determine a subtree of a shadow cone of the spine node. The subtree may comprise a plurality of nodes and a plurality of links connecting pairs of the nodes. The spine node may determine a disaggregated route to a first leaf node to which a disaggregated prefix may be attached. The disaggregated route may be propagated to the plurality of the nodes of the subtree.

## Claims

### Claim 1

A method comprising:
determining, at a spine node in communication with a network, a subtree of a shadow cone of the spine node, the subtree comprising a plurality of nodes and a plurality of links connecting pairs of the plurality of the nodes;
determining a disaggregated route to a first leaf node, wherein a disaggregated prefix is attached to the first leaf node; and
propagating the disaggregated route to the nodes of the subtree.

### Claim 2 (depends on 1)

The method of claim 1, wherein determining the subtree of the shadow cone of the spine node comprises determining a plurality of paths comprising the first leaf node, wherein the disaggregated prefix is attached to the first leaf node.

### Claim 3 (depends on 2)

The method of claim 2, wherein determining the plurality of the paths comprising the first leaf node comprises determining a plurality of shortest paths to the first leaf node from at least one other leaf node.

### Claim 4 (depends on 2)

The method of claim 2, wherein determining the plurality of the paths comprising the first leaf node comprises determining a reverse destination oriented directed acyclic graph (DODAG) of the network from the perspective of the first leaf node.

### Claim 5 (depends on 1)

The method of claim 1, wherein determining the subtree of the shadow cone of the spine node comprises retaining links that are not congruent with routes that have been selected in determining the subtree.

### Claim 6 (depends on 1)

The method of claim 1, wherein determining the subtree of the shadow cone of the spine node comprises adding a link to the subtree to form a distribution tree.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
using source routing to propagate a first message comprising a topology information element (TIE) to install the disaggregated route to the plurality of the nodes of the subtree; and
using source routing to propagate a second message to the plurality of the nodes of the subtree to remove the disaggregated route.

### Claim 8 (depends on 1)

The method of claim 1, further comprising sending a unicast control message to a leaf node, the unicast control message comprising a segment routing source route path.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
propagating a packet comprising information relating to the disaggregated route from an ingress leaf node of a tunnel to an egress leaf node of the tunnel; and
installing a state at a node along a path from the ingress leaf node to the egress leaf node.

### Claim 10

A device comprising:
a network interface in communication with a network;
a processor configured to execute computer readable instructions included on a non-transitory memory; and
a non-transitory memory including processor-readable instructions, that when executed by the processor, cause the device to:
determine, at a spine node in communication with the network, a subtree of a shadow cone of the spine node, the subtree comprising a plurality of nodes and a plurality of links connecting pairs of the nodes;
determine a disaggregated route to a first leaf node, wherein a disaggregated prefix is attached to the first leaf node; and
propagate the disaggregated route to the nodes of the subtree.

### Claim 11 (depends on 10)

The device of claim 10, wherein determining the subtree of the shadow cone of the spine node comprises determining a plurality of paths comprising the first leaf node, wherein the disaggregated prefix is attached to the first leaf node.

### Claim 12 (depends on 11)

The device of claim 11, wherein determining the plurality of paths comprising the first leaf node comprises determining a plurality of shortest paths to the first leaf node from at least one other leaf node.

### Claim 13 (depends on 11)

The device of claim 11, wherein determining the plurality of paths comprising the first leaf node comprises determining a reverse destination oriented directed acyclic graph (DODAG) of the network from the perspective of the first leaf node.

### Claim 14 (depends on 10)

The device of claim 10, wherein determining the subtree of the shadow cone of the spine node comprises retaining links that are not congruent with routes that have been selected in determining the subtree.

### Claim 15 (depends on 10)

The device of claim 10, wherein determining the subtree of the shadow cone of the spine node comprises adding a link to the subtree to form a distribution tree.

### Claim 16 (depends on 10)

The device of claim 10, wherein the processor-readable instructions further cause the device to:
use source routing to propagate a first message comprising a topology information element (TIE) to install the disaggregated route to the plurality of the nodes of the subtree; and
use source routing to propagate a second message to the nodes of the subtree to remove the disaggregated route.

### Claim 17 (depends on 10)

The device of claim 10, wherein the processor-readable instructions further cause the device to send a unicast control message to a leaf node, the unicast control message comprising a segment routing source route path.

### Claim 18 (depends on 10)

The device of claim 10, wherein the processor-readable instructions further cause the device to:
propagate a packet comprising information relating to the disaggregated route from an ingress leaf node of a tunnel to an egress leaf node of the tunnel; and
install a state at a node along a path from the ingress leaf node to the egress leaf node.

### Claim 19

A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, that, when executed by a computing device with a non-transitory memory and one or more processors, cause the computing device to perform or cause performance of:
determining, at a spine node in communication with a network, a subtree of a shadow cone of the spine node, the subtree comprising a plurality of nodes and a plurality of links connecting pairs of the nodes;
determining a disaggregated route to a first leaf node, wherein a disaggregated prefix is attached to the first leaf node; and
propagating the disaggregated route to the nodes of the subtree.

### Claim 20 (depends on 19)

The non-transitory computer readable storage medium of claim 19, wherein the instructions cause the computing device to perform or cause performance of:
using source routing to propagate a first message comprising a topology information element (TIE) to install the disaggregated route to the nodes of the subtree; and
using source routing to propagate a message to remove the disaggregated route to the nodes of the subtree.