Dynamic flooding for link state protocols

1. A method for distributing link state information, the method comprising:

building a link state database on a plurality of network devices in a spine/leaf network topology, wherein the spine/leaf network topology comprises links interconnecting the plurality of network devices that includes a plurality of spine network devices and a plurality of leaf network devices;

electing a leader from among the plurality of spine network devices;

computing, by the leader, a flooding topology,

wherein:

the flooding topology specifies:

the plurality of network devices,

a first subset of links between a plurality of non-leader network devices of the plurality of network devices, wherein each of the plurality of non-leader network devices shares link state updates using the first subset of links,

a second subset of links of the leader from which the leader will share link state updates,

at least one of a first link of each of the plurality of non-leader network devices is not included in the first subset, and

at least one of a second link of the leader is not included in the second subset;

the flooding topology comprises a diameter that is below a diameter threshold;

a number of flooding links of any one spine network device of the plurality of spine network devices in the flooding topology does not exceed a spine degree threshold;

a number of flooding links of any one leaf network device of the plurality of leaf network devices in the flooding topology does not exceed a leaf degree threshold; and

encoding, by the leader, the flooding topology to obtain an encoded flooding topology;

distributing, by the leader, the encoded flooding topology to the plurality of non-leader network devices;

after the distributing:

receiving a link state update at a non-leader network device of the plurality of non- leader network devices; and

transmitting, by the non-leader network device, the link state update to only a subset of adjacent network devices, wherein the subset of adjacent network devices is determined using the encoded flooding topology and the first subset of links of the non-leader network device specified in the encoded flooding topology.

2. The method of claim 1 , further comprising:

computing, by the leader, after receiving the link state update, a new flooding topology;

encoding, by the leader, the new flooding topology to obtain a new encoded flooding topology; and

distributing, by the leader, the new encoded flooding topology to the plurality of network devices.

3. The method of claim 1 , wherein the flooding topology is at least a bi-connected topology.

4. The method of claim 1 , wherein encoding the flooding topology is performed using an adjacency matrix.

5. The method of claim 1 , wherein encoding the flooding topology is performed using a set of paths.

6. The method of claim 1 , wherein electing the leader comprises:

sending, from each of the plurality of network devices, a message comprising a leader priority, wherein the leader is elected based on having a highest leader priority.

7. The method of claim 6 , wherein, when two network devices of the plurality of network devices have a same leader priority, the leader is elected based from among the two network devices by having a numerically higher identifier.

8. The method of claim 1 , wherein building the link state database on the plurality of network devices is performed using one protocol selected from a group of protocols consisting of intermediate system to intermediate system (IS-IS) and open shortest path first (OSPF).

9. The method of claim 1 , wherein the number of spine network devices is n, the number of leaf network devices is m, m is greater than or equal to n((n/2)−1), and the diameter threshold of the flooding topology is four.

10. The method of claim 1 , wherein the flooding topology evenly distributes link state updates among the plurality of spine devices.

11. A non-transitory computer readable medium comprising instructions that, when executed by a processor, perform a method of distributing link state information traffic, the method comprising:

building a link state database on a plurality of network devices in a spine/leaf network topology, wherein the spine/leaf network topology comprises links interconnecting the plurality of network devices that includes a plurality of spine network devices and a plurality of leaf network devices;

electing a leader from among the plurality of spine network devices;

computing, by the leader, a flooding topology, wherein:

the flooding topology specifies,

a first subset of links between a plurality of non-leader network devices of the plurality of network devices, wherein each of the plurality of non-leader network devices shares link state updates using the first subset of links,

a second subset of links of the leader from which the leader will share link state updates,

at least one of a first link of each of the plurality of non-leader network devices is not included in the first subset, and

at least one of a second link of the leader is not included in the second subset;

the flooding topology comprises a diameter that is below a diameter threshold;

a number of flooding links of any one network device of the plurality of network devices in the flooding topology does not exceed a spine degree threshold;

a number of flooding links of any one leaf network device of the plurality of leaf network devices in the flooding topology does not exceed a leaf degree threshold; and

encoding, by the leader, the flooding topology to obtain an encoded flooding topology;

distributing, by the leader, the encoded flooding topology to the plurality of non-leader network devices;

after the distributing:

receiving a link state update at a non-leader network device of the plurality of non-leader network devices; and

transmitting, by the non-leader network device, the link state update to only a subset of adjacent network devices, wherein the subset of adjacent network devices is determined using the encoded flooding topology and the first subset of links of the non-leader network device specified in the encoded flooding topology.

12. The non-transitory computer readable medium of claim 11 , the method further comprising:

computing, by the leader, after receiving the link state update, a new flooding topology;

encoding, by the leader, the new flooding topology to obtain a new encoded flooding topology; and

distributing, by the leader, the new encoded flooding topology to the plurality of network devices.

13. The non-transitory computer readable medium of claim 11 , wherein the flooding topology is configured as at least a bi-connected topology.

14. The non-transitory computer readable medium of claim 11 , wherein encoding the flooding topology is performed using an adjacency matrix.

15. The non-transitory computer readable medium of claim 11 , wherein electing the leader comprises:

sending, from each of the plurality of network devices, a message comprising a leader priority, wherein the leader is elected based on having a highest leader priority.

16. The non-transitory computer readable medium of claim 15 , wherein, when two network devices of the plurality of network devices have a same leader priority, the leader is elected based from among the two network devices by having a numerically higher identifier.

17. The non-transitory computer readable medium of claim 11 , wherein building the link state database on the plurality of network devices is performed using one protocol selected from a group of protocols consisting of intermediate system to intermediate system (IS-IS) and open shortest path first (OSPF).

18. The non-transitory computer readable medium of claim 11 , wherein the number of spine network devices is n, the number of leaf network devices is m, m is greater than or equal to n((n/2)−1), and the diameter threshold of the flooding topology is four.

19. The non-transitory computer readable medium of claim 11 , wherein the flooding topology evenly distributes link state updates among the plurality of spine devices.