Loop conflict avoidance in a network computing environment

Patent metadata

Field	Value
Publication number	US-12020089-B2
Application number	US-202117459505-A
Country	US
Kind code	B2
Filing date	Aug 27, 2021
Priority date	Aug 23, 2018
Publication date	Jun 25, 2024
Grant date	Jun 25, 2024

Abstract

Systems, methods, and devices for improved routing operations in a network computing environment. A system includes a network topology comprising a plurality of spine nodes and a plurality of leaf nodes, wherein a link between a first spine node and a first leaf node is inactive. The first spine node includes one or more processors configurable to execute instructions stored in non-transitory computer readable storage media. The instructions include receiving a packet to be transmitted to the first leaf node. The instructions include identifying an alternative spine node at a same level in the network topology. The instructions include attaching a tunnel label to the packet, wherein the tunnel label indicates the packet should be transmitted to the alternative spine node.

First claim

What is claimed is:

1. A system comprising:
a plurality of spine nodes and a plurality of leaf nodes in a network topology;
a first spine node of the plurality of spine nodes in the network topology, wherein the first spine node is configured to perform steps comprising:
receiving a packet including a prefix to be transmitted to a destination leaf node of the plurality of leaf nodes, wherein a link between the first spine node and the destination leaf node is inactive;
analyzing a redundancy group for the first spine node to identify an alternative spine node of the plurality of spine nodes that has an active link to the destination leaf node, wherein the alternative spine node is located at a same level in the network topology as the first spine node; and
attaching a tunnel label to the packet, wherein the tunnel label identifies the alternative spine node and indicates the packet should be transmitted to the alternative spine node;

wherein a leaf node of the plurality of leaf nodes in the network topology transmits the packet to the alternative spine node in response to reading the tunnel label; and
wherein the leaf node of the plurality of leaf nodes in the network topology identifies the alternative spine node based on the tunnel label and in lieu of performing a lookup on the prefix of the packet associated with the destination leaf node.

2. The system of claim 1 , wherein the first spine node is configured to receive the packet from an originating leaf node of the plurality of leaf nodes in the network topology; and
wherein the first spine is further configured to return the packet to the originating leaf node for the originating leaf node to forward the packet to the alternative spine node.

3. The system of claim 1 , wherein the plurality of spine nodes in the network topology advertises a local loopback route to the plurality of leaf nodes as a transitive attribute to signal that one or more spine nodes in the same level in the network topology as the first spine node are part of the redundancy group.

4. The system of claim 1 , wherein the plurality of leaf nodes in the network topology associate a per-customer edge label with each loopback route received by the plurality of leaf nodes, and wherein the plurality of leaf nodes advertises the per-customer edge label to the plurality of spine nodes in the network topology.

5. The system of claim 1 , wherein the first spine node is further configured to pre-program a recursive backup path to the alternative spine node.

6. The system of claim 1 , wherein the first spine node is further configured to identify one or more other spine nodes of the plurality of spine nodes other than the first spine node at the same level in the network topology that have the active link to the destination leaf node based on advertisements received from the plurality of spine nodes at the same level in the network topology.

7. The system of claim 1 , wherein the first spine node is further configured to perform steps comprising:
determining the link between the first spine node and the destination leaf node is no longer inactive; and
in response to determining the link is no longer inactive, transmitting a new packet destined for the destination leaf node directly to the destination leaf node in lieu of attaching the tunnel label to the new packet.

8. The system of claim 1 , wherein the first spine node is configured to identify alternative spine node by identifying-one or more other spine nodes of the plurality of spine nodes other than the first spine node at a same level in the network topology that have the active link to the destination leaf node.

9. A method performed by a first spine node of a plurality of spine nodes in a network topology, the method comprising:
receiving a packet including a prefix to be transmitted to a destination leaf node of a plurality of leaf nodes in the network topology, wherein a link between the first spine node and the destination leaf node is inactive;
analyzing a redundancy group for the first spine node to identify an alternative spine node of the plurality of spine nodes that has an active link to the destination leaf node, wherein the alternative spine node is located at a same level in the network topology as the first spine node;
attaching a tunnel label to the packet, wherein the tunnel label identifies the alternative spine node and indicates the packet should be transmitted to the alternative spine node; and
providing the packet with the tunnel label to an originating leaf node of the plurality of leaf nodes in the network topology to direct the originating leaf node to provide the packet to the alternative spine node identified in the tunnel label based on instructions in the tunnel label, and in lieu of performing a lookup on the prefix of the packet associated with the destination leaf node.

10. The method of claim 9 , wherein receiving the packet comprises receiving the packet from the originating leaf node in the network topology, and wherein the method further comprises returning the packet to the originating leaf node for the originating leaf node to forward the packet to the alternative spine node.

11. The method of claim 10 , wherein the packet comprises a prefix associated with the destination leaf node, and wherein the originating leaf node transmits the packet to the alternative spine node without performing a lookup on the prefix associated with the destination leaf node.

12. The method of claim 9 , wherein one or more spine nodes of the plurality of spine nodes in the same level in the network topology as the first spine node advertise a local loopback route to the plurality of leaf nodes in the network topology as a transitive attribute to signal that one or more spine nodes of the plurality of spine nodes in the same level in the network topology as the first spine node are part of the redundancy group.

13. The method of claim 12 , wherein the plurality of leaf nodes in the network topology associate a per-customer edge label with each received loopback route received by the plurality of leaf nodes, and wherein the plurality of leaf nodes advertises the per-customer edge label to the plurality of spine nodes in the same level in the network topology as the first spine node.

14. The method of claim 9 , further comprising pre-programming a recursive backup path to the alternative spine node.

15. The method of claim 9 , wherein the alternative spine node is located at the same level in the network topology as the first spine node, and wherein identifying the alternative spine node comprises analyzing the redundancy group for the first spine node.

16. The method of claim 9 , further comprising identifying one or more other spine nodes of the plurality of spine nodes at the same level in the network topology other than the first spine node that have the active link to the destination leaf node based on advertisements received from the plurality of spine nodes at the same level in the network topology.

17. The method of claim 9 , further comprising:
determining the link between the first spine node and the destination leaf node is no longer inactive; and
in response to determining the link is no longer inactive, transmitting a new packet destined for the destination leaf node directly to the destination leaf node in lieu of attaching the tunnel label to the new packet.

18. The method of claim 9 , wherein identifying the alternative spine node comprises identifying one or more other spine nodes of the plurality of spine nodes at a same level in the network topo

Assignees

• Arrcus Inc

Inventors

• Malhotra Neeraj
• Patel Keyur
• Yeung Derek Man-Kit
• Pai Nalinaksh
• Rajaraman Kalyani
• Ragukumar Vikram

Classifications

• G06F2009/45595

  Network integration; Enabling network access in virtual machine instances · CPC title

• H04L67/1097

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/542 Primary

  Event management; Broadcasting; Multicasting; Notifications · CPC title

• G06F16/278

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title