Updating entries of a distribution data structure

Patent metadata

Field	Value
Publication number	US-10924390-B2
Application number	US-201816178727-A
Country	US
Kind code	B2
Filing date	Nov 2, 2018
Priority date	Nov 2, 2018
Publication date	Feb 16, 2021
Grant date	Feb 16, 2021

Abstract

In some examples, a system populates a distribution data structure useable by a switch in distributing communications of data packets across a plurality of network paths for the switch. In response to an addition of a new network path or a removal of an existing network path for the switch, the system updates entries of the distribution data structure using a process that identifies selected entries of the distribution data structure to skip as part of updating the distribution data structure.

First claim

What is claimed is:

1. A non-transitory machine-readable storage medium comprising instructions that upon execution cause a system to:
populate a distribution data structure useable by a switch in distributing communications of data packets across a plurality of network paths for the switch; and
in response to an addition of a new network path or a removal of an existing network path for the switch:
for each respective network path of the plurality of network paths, compute a respective difference value representing a first number of entries of the distribution data structure mapped to the respective network path prior to the addition or the removal, and a second number of entries of the distribution data structure mapped to the respective network path after the addition or the removal;
identify selected entries of the distribution data structure to skip based on the difference value, and
update entries of the distribution data structure, wherein the selected entries are skipped in the updating.

2. The non-transitory machine-readable storage medium of claim 1 , wherein the instructions upon execution cause the system to:
not consider the identified selected entries of the distribution data structure for update when updating the distribution data structure in response to the addition or the removal.

3. The non-transitory machine-readable storage medium of claim 1 , wherein the identifying of the selected entries of the distribution data structure to skip comprises identifying a number of the selected entries to skip based on a difference between a first number of entries of the distribution data structure mapped to a respective network path prior to the addition or the removal, and a second number of entries of the distribution data structure mapped to the respective network path after the addition or the removal.

4. The non-transitory machine-readable storage medium of claim 1 , wherein the instructions upon execution cause the system to:
in response to updating an entry of the distribution data structure as part of the updating for a given network path of the plurality of network paths, advance a given difference value for the given network path; and
cease updating the distribution data structure for the given network path responsive to the addition or the removal in response to a specified relationship of the given difference value with respect to a threshold.

5. The non-transitory machine-readable storage medium of claim 1 , wherein the distribution data structure includes a plurality of entries, wherein prior to the updating of the distribution data structure, each entry of the plurality of entries contains a pointer to a respective value that corresponds to a respective network path of the plurality of network paths, and
wherein after the updating of the distribution data structure, each entry of the plurality of entries contains a pointer to a respective value that corresponds to a respective network path of network paths that are present after the addition or the removal.

6. The non-transitory machine-readable storage medium of claim 1 , wherein the values to which the pointers of the plurality of entries of the distribution data structure refer comprise values of another data structure including entries representing respective network paths for the switch.

7. The non-transitory machine-readable storage medium of claim 1 , wherein the plurality of network paths comprise network paths of an aggregation group of network paths.

8. The non-transitory machine-readable storage medium of claim 1 , wherein the distribution data structure weights the plurality of network paths equally or unequally in the distributing of communications of data packets across the plurality of network paths for the switch.

9. The non-transitory machine-readable storage medium of claim 1 , wherein the distribution data structure includes a plurality of entries,
wherein each entry of the plurality of entries contains a pointer to a respective value that corresponds to a respective network path of the network paths for the switch, the pointer based on scrambling an initial pointer value derived from a data packet field.

10. The non-transitory machine-readable storage medium of claim 1 , wherein the non-transitory machine-readable storage medium comprising the instructions are part of the switch or a controller remote from the switch.

11. A switch comprising:
a plurality of ports to connect to a plurality of network paths; and
a controller to:
use a distribution data structure in distributing communications of data packets across the plurality of network paths, wherein the distribution data structure comprises a first data structure with entries pointing to a second data structure; and
responsive to an addition of a new network path or a removal of an existing network path for the switch:
changing entries in the second data structure;
identify selected entries of the first data structure to skip,
update the entries of the first data structure to reflect the change in the second data structure, wherein the selected entries are skipped in the updating,
for each respective network path of the plurality of network paths, compute a respective difference value representing a first number of entries of the distribution data structure mapped to the respective network path prior to the addition or the removal, and a second number of entries of the distribution data structure mapped to the respective network path after the addition or the removal; and

use the difference values in identifying the selected entries of the distribution data

structure to skip.

12. The switch of claim 11 , wherein the plurality of network paths are part of an aggregation group.

13. The switch of claim 11 , wherein the controller is to determine updated values for the entries of the first data structure responsive to the addition or the removal.

14. The switch of claim 11 , wherein the controller is to receive, from a remote controller, updated values for the entries of the distribution data structure responsive to the addition or the removal.

15. The switch of claim 11 , wherein the update of the entries of the distribution data structure that includes skipping the selected entries avoids rebalancing all entries of the distribution data structure responsive to the addition or the removal.

16. A method performed by a system comprising a hardware processor, comprising:
populating a distribution data structure useable by a switch in distributing communications of data packets across network paths of an aggregation group of network paths for the switch; and
in response to an addition of a new network path to or a removal of an existing network path from the aggregation group, iteratively updating entries of the distribution data structure using a process that identifies selected entries of the distribution data structure to skip as part of updating the distribution data structure, the iterative updating comprising, for a current entry of the distribution data structure:
for each respective network path of the aggregation group, computing a respective difference value representing a first number of entries of the distribution data structure mapped to the respective network path prior to the addition or the removal, and a second number of entries of the distribution data structure mapped to the respective network path after the addition or the removal
determining whether the current entry is one of the selected entries based on the difference value,
in response to determining that the current entry is one of the selected entries,

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Lavigne Bruce E
• Solano Ocampo Freddy Andrey
• Carvajal Rojas Alonso Jose
• Viquez Calderon Claudio Enrique
• Guillen Hernandez Sergio Jesus

Classifications

• H04L45/036

  Updating the topology between route computation elements, e.g. between OpenFlow controllers · CPC title

• H04L45/245 Primary

  Link aggregation, e.g. trunking · CPC title

• H04L49/253 Primary

  using establishment or release of connections between ports · CPC title

• H04L47/125

  by balancing the load, e.g. traffic engineering · CPC title

• H04L45/02

  Topology update or discovery · CPC title