IP Library › Granted Patent US 10,608,921
Granted Patent B2
US 10,608,921 · App. 16/160,481 · Granted Mar 31, 2020

Routing in fat tree networks using negative disaggregation advertisements

Inventors: Pascal Thubert (La Colle sur Loup, FR); Eric Levy-Abegnoli (Valbonne, FR); Jakob Heitz (Santa Clara, CA)
Assignee: Cisco Technology, Inc.
H04L45/02
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 10,608,921
App. No.
16/160,481
Granted
Mar 31, 2020
Kind
B2
Abstract

A particular fat tree network node stores default routing information indicating that the particular fat tree network node can reach a plurality of parent fat tree network nodes of the particular fat tree network node. The particular fat tree network node obtains, from a first parent fat tree network node of the plurality of parent fat tree network nodes, a negative disaggregation advertisement indicating that the first parent fat tree network node cannot reach a specific destination. The particular fat tree network node determines whether the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination. If so, the particular fat tree network node installs supplemental routing information indicating that every parent fat tree network node except the first parent fat tree network node can reach the specific destination.

Claims (81)

1. A method comprising:

at a particular fat tree network node that stores default routing information indicating that the particular fat tree network node can reach a plurality of parent fat tree network nodes of the particular fat tree network node:

obtaining, from a first parent fat tree network node of the plurality of parent fat tree network nodes, a negative disaggregation advertisement indicating that the first parent fat tree network node cannot reach a specific destination;

determining whether the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination; and

if it is determined that the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination, installing supplemental routing information indicating that every parent fat tree network node except the first parent fat tree network node can reach the specific destination.

2. The method of claim 1 , further comprising:

at the particular fat tree network node:

if it is determined that the first parent fat tree network node is not the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination:

locating previously installed supplemental routing information indicating that the first parent fat tree network node can reach the specific destination; and

removing the previously installed supplemental routing information indicating that the first parent fat tree network node can reach the specific destination.

3. The method of claim 2 , further comprising:

at the particular fat tree network node:

if it is determined that the first parent fat tree network node is not the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination:

determining that none of the plurality of parent fat tree network nodes can reach the specific destination; and

in response to determining that none of the plurality of parent fat tree network nodes can reach the specific destination, providing, to at least one child fat tree network node of the particular fat tree network node, a negative disaggregation advertisement indicating that the particular fat tree network node cannot reach the specific destination.

4. The method of claim 1 , further comprising:

at the particular fat tree network node:

obtaining, from the first parent fat tree network node, a reachability advertisement indicating that the first parent fat tree network node can reach the specific destination; and

installing supplemental routing information indicating that the first parent fat tree network node can reach the specific destination.

5. The method of claim 4 , further comprising:

at the particular fat tree network node:

determining whether the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that can reach the specific destination; and

if it is determined that the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that can reach the specific destination, providing, to at least one child fat tree network node of the particular fat tree network node, a reachability advertisement indicating that the particular fat tree network node can reach the specific destination.

6. The method of claim 5 , further comprising:

at the particular fat tree network node:

if it is determined that the first parent fat tree network node is not the only parent fat tree network node of the plurality of parent fat tree network nodes that can reach the specific destination:

determining that each of the plurality of parent fat tree network nodes can reach the specific destination; and

removing the supplemental routing information indicating that every parent fat tree network node except the first parent fat tree network node can reach the specific destination and the supplemental routing information indicating that the first parent fat tree network node can reach the specific destination.

7. The method of claim 1 , further comprising:

at the particular fat tree network node:

obtaining a network packet destined for the specific destination; and

routing the network packet to the specific destination based on the supplemental routing information.

8. An apparatus comprising:

a memory that stores default routing information indicating that the apparatus can reach a plurality of parent fat tree network nodes of the apparatus; and

one or more processors coupled to the memory, wherein the one or more processors are configured to:

obtain, from a first parent fat tree network node of the plurality of parent fat tree network nodes, a negative disaggregation advertisement indicating that the first parent fat tree network node cannot reach a specific destination;

determine whether the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination; and

if it is determined that the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination, install supplemental routing information indicating that every parent fat tree network node except the first parent fat tree network node can reach the specific destination.

9. The apparatus of claim 8 , wherein the one or more processors are further configured to:

if it is determined that the first parent fat tree network node is not the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination:

locate previously installed supplemental routing information indicating that the first parent fat tree network node can reach the specific destination; and

remove the previously installed supplemental routing information indicating that the first parent fat tree network node can reach the specific destination.

10. The apparatus of claim 9 , wherein the one or more processors are further configured to:

if it is determined that the first parent fat tree network node is not the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination:

determine that none of the plurality of parent fat tree network nodes can reach the specific destination; and

in response to determining that none of the plurality of parent fat tree network nodes can reach the specific destination, provide, to at least one child fat tree network node of the apparatus, a negative disaggregation advertisement indicating that the apparatus cannot reach the specific destination.

11. The apparatus of claim 8 , wherein the one or more processors are further configured to:

obtain, from the first parent fat tree network node, a reachability advertisement indicating that the first parent fat tree network node can reach the specific destination; and

install supplemental routing information indicating that the first parent fat tree network node can reach the specific destination.

12. The apparatus of claim 11 , wherein the one or more processors are further configured to:

determine whether the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that can reach the specific destination; and

if it is determined that the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that can reach the specific destination, provide, to at least one child fat tree network node of the apparatus, a reachability advertisement indicating that the apparatus can reach the specific destination.

13. The apparatus of claim 12 , wherein the one or more processors are further configured to:

if it is determined that the first parent fat tree network node is not the only parent fat tree network node of the plurality of parent fat tree network nodes that can reach the specific destination:

determine that each of the plurality of parent fat tree network nodes can reach the specific destination; and

remove the supplemental routing information indicating that every parent fat tree network node except the first parent fat tree network node can reach the specific destination and the supplemental routing information indicating that the first parent fat tree network node can reach the specific destination.

14. The apparatus of claim 8 , wherein the one or more processors are further configured to:

obtain a network packet destined for the specific destination; and

route the network packet to the specific destination based on the supplemental routing information.

15. One or more non-transitory computer readable storage media encoded with instructions that, when executed by a processor of a particular fat tree network node that stores default routing information indicating that the particular fat tree network node can reach a plurality of parent fat tree network nodes of the particular fat tree network node, cause the processor to:

obtain, from a first parent fat tree network node of the plurality of parent fat tree network nodes, a negative disaggregation advertisement indicating that the first parent fat tree network node cannot reach a specific destination;

determine whether the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination; and

if it is determined that the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination, install supplemental routing information indicating that every parent fat tree network node except the first parent fat tree network node can reach the specific destination.

16. The one or more non-transitory computer readable storage media of claim 15 , wherein the instructions further cause the processor to:

if it is determined that the first parent fat tree network node is not the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination:

locate previously installed supplemental routing information indicating that the first parent fat tree network node can reach the specific destination; and

remove the previously installed supplemental routing information indicating that the first parent fat tree network node can reach the specific destination.

17. The one or more non-transitory computer readable storage media of claim 16 , wherein the instructions further cause the processor to:

if it is determined that the first parent fat tree network node is not the only parent fat tree network node of the plurality of parent fat tree network nodes that cannot reach the specific destination:

determine that none of the plurality of parent fat tree network nodes can reach the specific destination; and

in response to determining that none of the plurality of parent fat tree network nodes can reach the specific destination, provide, to at least one child fat tree network node of the particular fat tree network node, a negative disaggregation advertisement indicating that the particular fat tree network node cannot reach the specific destination.

18. The one or more non-transitory computer readable storage media of claim 15 , wherein the instructions further cause the processor to:

obtain, from the first parent fat tree network node, a reachability advertisement indicating that the first parent fat tree network node can reach the specific destination; and

install supplemental routing information indicating that the first parent fat tree network node can reach the specific destination.

19. The one or more non-transitory computer readable storage media of claim 18 , wherein the instructions further cause the processor to:

determine whether the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that can reach the specific destination; and

if it is determined that the first parent fat tree network node is the only parent fat tree network node of the plurality of parent fat tree network nodes that can reach the specific destination, provide, to at least one child fat tree network node of the particular fat tree network node, a reachability advertisement indicating that the particular fat tree network node can reach the specific destination.

20. The one or more non-transitory computer readable storage media of claim 19 , wherein the instructions further cause the processor to:

if it is determined that the first parent fat tree network node is not the only parent fat tree network node of the plurality of parent fat tree network nodes that can reach the specific destination:

determine that each of the plurality of parent fat tree network nodes can reach the specific destination; and

remove the supplemental routing information indicating that every parent fat tree network node except the first parent fat tree network node can reach the specific destination and the supplemental routing information indicating that the first parent fat tree network node can reach the specific destination.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Oct 23, 2018
From: THUBERT, PASCAL; LEVY-ABEGNOLI, ERIC; HEITZ, JAKOB
To: CISCO TECHNOLOGY, INC.
Reel/Frame 047278/0378 →
Continuity (2)
Provisional Application 62659922 · Apr 19, 2018
Related Publication 20190327166A1 · Oct 24, 2019