Scalable spine nodes with partial replication of routing information in a network environment

Patent metadata

Field	Value
Publication number	US-2017032011-A1
Application number	US-201514810200-A
Country	US
Kind code	A1
Filing date	Jul 27, 2015
Priority date	Jul 27, 2015
Publication date	Feb 2, 2017
Grant date	—

Abstract

Embodiments are provided for partially replicating endpoint routing information, and comprise calculating a first shard interval of a key space based, at least in part, on capacities of a plurality of spine nodes in a network fabric. Embodiments also include mapping the first shard interval to a first spine node of the plurality of spine nodes, communicating shard mapping information associated with the mapping to a set of leaf nodes in the network fabric, and populating an endpoint repository in the first spine node with routing information for one or more endpoints corresponding to the first shard interval. More specific embodiments include calculating respective shard intervals for other spine nodes of the plurality of spine nodes based, at least in part, on the capacities of the plurality of spine nodes. In specific embodiments, the calculating the first shard interval is based, in part, on one or more dynamic parameters.

First claim

What is claimed is:

1 . A method, comprising:
calculating a first shard interval of a key space based, at least in part, on capacities of a plurality of spine nodes in a network fabric; mapping the first shard interval to a first spine node of the plurality of spine nodes; communicating shard mapping information associated with the mapping to a set of leaf nodes in the network fabric; and populating an endpoint repository in the first spine node with routing information for one or more endpoints corresponding to the first shard interval.

2 . The method of claim 2 , further comprising:
determining a capacity of the first spine node; and receiving capacity information indicating one or more other capacities for one or more other spine nodes of the plurality of spine nodes.

3 . The method of claim 1 , wherein the determining the first shard interval of the key space is based, in part, on one or more dynamic parameters of at least one spine node in the plurality of spine nodes.

4 . The method of claim 1 , further comprising:
receiving, at the first spine node, a packet en route to a destination endpoint; and identifying, if the destination endpoint does not correspond to the first shard interval, a second spine node mapped to a second shard interval, wherein the destination endpoint corresponds to the second shard interval; and forwarding the packet to the identified second spine node.

5 . The method of claim 1 , wherein a hashing algorithm applied to a unique identifier of any one of the one or more endpoints corresponding to the first shard interval generates a key that is included in the first shard interval.

6 . The method of claim 1 , further comprising:
calculating one or more other shard intervals for each one or more other spine nodes of the plurality of spine nodes based, at least in part, on the capacities of the plurality of spine nodes.

7 . The method of claim 6 , wherein the first shard interval and the one or more other shard intervals are assigned to the plurality of spine nodes in numerical sort order of tunnel endpoint Internet Protocol (IP) addresses of the plurality of spine nodes.

8 . The method of claim 1 , further comprising:
mapping at least one backup shard interval to the first spine node, wherein the at least one backup shard interval includes at least a portion of another shard interval mapped to another spine node.

9 . The method of claim 8 , wherein each key of the first shard interval is included in one or more backup shard intervals mapped to one or more other spine nodes based on a replication factor.

10 . The method of claim 1 , wherein the shard mapping information is communicated out of band to the set of leaf nodes in the network fabric.

11 . The method of claim 1 , further comprising:
dynamically recalculating the first shard interval to determine an updated first shard interval based on the capacities of the plurality of spine nodes and one or more dynamic parameters of at least one spine node of the plurality of spine nodes.

12 . The method of claim 11 , wherein the one or more dynamic parameters include a load of one or more of the plurality of spine nodes.

13 . At least one non-transitory, machine readable storage medium comprising instructions that, when executed by a processor, cause the processor to:
calculate a first shard interval of a key space based, at least in part, on capacities of a plurality of spine nodes in a network fabric; map the first shard interval to a first spine node of the plurality of spine nodes; communicate shard mapping information associated with the mapping to a set of leaf nodes in the network fabric; and populate an endpoint repository in the first spine node with routing information for one or more endpoints corresponding to the first shard interval.

14 . The medium of claim 13 , wherein mapping the first shard interval to the first spine node includes populating a shard mapping table with the shard mapping information.

15 . The medium of claim 13 , further comprising instructions that when executed by a processor cause the processor to:
dynamically recalculating the first shard interval to determine an updated first shard interval based on the capacities of the plurality of spine nodes and one or more dynamic parameters of at least one spine node of the plurality of spine nodes.

16 . The medium of claim 15 , wherein the one or more dynamic parameters include at least one of a load of the at least one spine node and a fault state of one or more of the spine nodes.

17 . An apparatus, comprising:
at least one memory element having instructions stored therein; and at least one processor, wherein the instructions when executed by the at least one processor, cause the processor to:
calculate a first shard interval of a key space based, at least in part, on capacities of a plurality of spine nodes in a network fabric;
map the first shard interval to a first spine node of the plurality of spine nodes;
communicate shard mapping information associated with the mapping to a set of leaf nodes in the network fabric; and
populate an endpoint repository in the first spine node with routing information for one or more endpoints corresponding to the first shard interval.

18 . The apparatus of claim 17 , wherein the first shard interval is calculated based, in part, on one or more dynamic parameters of at least one spine node of the plurality of spine nodes.

19 . The apparatus of claim 17 , wherein a hashing algorithm applied to a unique identifier of any one of the one or more endpoints corresponding to the first shard interval is to generate a key that is included in the first shard interval.

20 . The apparatus of claim 17 , wherein the instructions when executed by the processor, further cause the processor to:
map a backup shard interval to the first spine node, wherein the backup shard interval includes at least a portion of another shard interval mapped to another spine node, wherein each key of the first shard interval is included in one or more backup shard intervals mapped to one or more other spine nodes based on a replication factor.

Assignees

• Cisco Tech Inc

Inventors

• Song Jialin
• Shetty Nikhil Gopinath
• Rathi Ravindra Nandalal

Classifications

• G06F16/25

  Integrating or interfacing systems involving database management systems · CPC title

• G06F16/275 Primary

  Synchronous replication · CPC title

• G06F17/30917

  Physics · mapped topic

• G06F17/30581 Primary

  Physics · mapped topic

• G06F17/30327

  Physics · mapped topic