Routing optimizations in a network computing environment

Patent metadata

Field	Value
Publication number	US-11212215-B2
Application number	US-201916549439-A
Country	US
Kind code	B2
Filing date	Aug 23, 2019
Priority date	Aug 23, 2018
Publication date	Dec 28, 2021
Grant date	Dec 28, 2021

Abstract

Systems, methods, and devices for improved routing operations in a network computing environment. A system includes a network topology comprising a spine node and a plurality of leaf nodes. The system is such that at least one of the plurality of leaf nodes is associated with one or more networking prefixes. The spine node stores a prefix table. The prefix table includes a listing of networking prefixes in the network topology. The prefix table includes an indication of at least one equal-cost multipath routing (ECMP) group associated with each of the networking prefixes in the network topology. The prefix table includes an indication of at least one leaf node of the plurality of leaf nodes associated with each of the networking prefixes in the network topology.

First claim

What is claimed is:

1. A system comprising:
a network topology comprising a spine node and a plurality of leaf nodes, wherein at least one of the plurality of leaf nodes is associated with one or more networking prefixes;
the spine node storing a prefix table, the prefix table comprising:
a listing of networking prefixes in the network topology;
an indication of at least one equal-cost multipath routing (ECMP) group associated with each of the one or more networking prefixes in the network topology; and
an indication of at least one leaf node of the plurality of leaf nodes associated with each of the one or more networking prefixes in the network topology;

wherein the at least one ECMP group is unique for each of the one or more networking prefixes in the network topology such that ECMP resources for the network topology cannot be shared across the one or more networking prefixes in the network topology.

2. The system of claim 1 , wherein the spine node further comprises a label table indicating at least one ECMP group associated with the spine node and further indicating which of the plurality of leaf nodes is associated with the at least one ECMP group associated with the spine node.

3. The system of claim 1 , wherein each of the plurality of leaf nodes comprises a prefix table comprising:
the listing of the networking prefixes in the network topology; and
an indication of unique ECMP group associated with each of the networking prefixes in the network topology.

4. The system of claim 1 , wherein each of the plurality of leaf nodes is associated with at least one ECMP group.

5. The system of claim 1 , wherein one or more ECMP groups are located on the spine node.

6. The system of claim 1 , wherein a single ECMP group is on the spine node and the single ECMP group points to two or more leaf nodes of the plurality of leaf nodes.

7. The system of claim 1 , wherein the networking prefixes are Internet Protocol (IP) address prefixes.

8. The system of claim 1 , wherein the spine node is a router and at least one of the plurality of leaf nodes is a consumer electronics device.

9. The system of claim 1 , wherein the network topology comprises a plurality of spine nodes and each of the plurality of spine nodes is in communication with each of the plurality of leaf nodes.

10. The system of claim 1 , wherein the spine node is configured to implement a routing policy comprising per-packet load balancing within an applicable ECMP group.

11. One or more processors configurable to execute instructions stored in non-transitory computer readable storage media, the instructions comprising:
receiving a data packet comprising a label, the label comprising a networking prefix;
identifying the networking prefix based on a prefix table, wherein the prefix table is stored on a spine node within a leaf-spine network topology;
identifying an assigned equal-cost multipath (ECMP) group associated with the networking prefix based on a prefix table; and
forwarding the data packet to a leaf node within the assigned ECMP group;
wherein the assigned ECMP group is unique to the networking prefix such that ECMP resources within the leaf-spine network topology cannot be shared across a plurality of networking prefixes in the leaf-spine network topology.

12. The one or more processors of claim 11 , wherein the instructions further comprise load balancing the assigned ECMP group to identify an active leaf node within the assigned ECMP group.

13. The one or more processors of claim 11 , wherein the instructions further comprise storing a label table comprising an indication of one or more ECMP groups associated with a spine node in the leaf-spine network topology.

14. The one or more processors of claim 11 , wherein the instructions further comprise storing the prefix table, wherein the prefix table comprises:
an indication of a plurality of leaf nodes in a leaf-spine network topology;
an indication of one or more networking prefixes associated with each of the plurality of leaf nodes; and
an indication of unique ECMP groups associated with each of the plurality of leaf nodes.

15. The one or more processors of claim 11 , wherein the instructions are implemented by a spine node within a two-layer leaf-spine network topology comprising a plurality of leaf nodes, wherein the spine node is in communication with each of the plurality of leaf nodes.

16. A method comprising:
receiving a data packet comprising a label, the label comprising a networking prefix;
identifying the networking prefix based on a prefix table, wherein the prefix table is stored on a spine node within a leaf-spine network topology;
identifying an assigned equal-cost multipath (ECMP) group associated with the networking prefix based on a prefix table; and
forwarding the data packet to a leaf node within the assigned ECMP group;
wherein the assigned ECMP group is unique to the networking prefix such that ECMP resources within the leaf-spine network topology cannot be shared across a plurality of networking prefixes in the leaf-spine network topology.

17. The method of claim 16 , further comprising load balancing the assigned ECMP group to identify an active leaf node within the assigned ECMP group.

18. The method of claim 16 , further comprising storing a label table comprising an indication of one or more ECMP groups associated with a spine node in a leaf-spine network topology.

19. The method of claim 16 , further comprising storing the prefix table, wherein the prefix table comprises:
an indication of a plurality of leaf nodes in a leaf-spine network topology;
an indication of one or more networking prefixes associated with each of the plurality of leaf nodes; and
an indication of unique ECMP groups associated with each of the plurality of leaf nodes.

20. The method of claim 16 , wherein the method is implemented by a spine node within a two-layer leaf-spine network topology comprising a plurality of leaf nodes, wherein the spine node is in communication with each of the plurality of leaf nodes.

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

  Event management; Broadcasting; Multicasting; Notifications · CPC title

• G06F16/278

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