Aggregation protocol

• US 10,284,383 B2
• Filed: 08/30/2016
• Issued: 05/07/2019
• Est. Priority Date: 08/31/2015
• Status: Active Grant

• Current Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Original Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Inventors: Bloch, Gil, Crupnicoff, Diego, Koren, Benny, Wertheim, Oded, Levi, Lion, Graham, Richard, Kagan, Michael
• Primary Examiner(s): Chu, Wutchung
• Application Number:
  US15/250,953
• Publication Number:
  US 20170063613A1
• Time in Patent Office: 980 Days
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/44 Star or tree networks
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A switch in a data network is configured to mediate data exchanges among network elements. The apparatus further includes a processor, which organizes the network elements into a hierarchical tree having a root node network element, vertex node network elements, and child node network elements that include leaf node network elements. The leaf node network elements are originate aggregation data and transmit the aggregation data to respective parent vertex node network elements. The vertex node network elements combine the aggregation data from at least a portion of the child node network elements, and transmit the combined aggregation data from the vertex node network elements to parent vertex node network elements. The root node network element is operative for initiating a reduction operation on the aggregation data.

Claims

1. A method, comprising the steps of:

organizing an aggregation collective group of network elements of a data network into a hierarchical tree having a root node network element, vertex node network elements and child node network elements, the child node network elements comprising leaf node network elements;

originating aggregation data in the leaf node network elements;

iteratively performing the steps of;

(1) receiving the aggregation data from at least a portion of the child node network elements of respective parent vertex node network elements thereof; and

(2) in the vertex node network elements combining the received aggregation data from at least a portion of the child node network elements thereof; and

(3) transmitting the combined received aggregation data from the vertex node network elements to parent vertex node network elements thereof; and

in the root node network element initiating, when all expected aggregation data have been received thereat, a reduction operation on the aggregation data to produce an aggregation result,

wherein organizing an aggregation collective group comprises defining multiple aggregation collective groups, and thereafter performing the additional steps of;

initializing a job that requires resources of the data network; and

selecting a best matching one of the multiple aggregation collective groups for the job.

2. The method according to claim 1, wherein organizing an aggregation collective group of network elements comprises conforming a mapping of the hierarchical tree to a topology of the data network.

3. The method according to claim 1, further comprising the step of:

in the vertex node network elements updating a database of outstanding aggregation operations.

4. The method according to claim 3, wherein the database comprises a status of pending aggregation requests in the child node network elements of the vertex node network elements.

5. The method according to claim 1, further comprising the step of distributing the aggregation result from the root node network element of the hierarchical tree to all the network elements of the aggregation collective group.

6. The method according to claim 5, wherein distributing is performed by head-end replication using a reliable transport protocol.

7. The method according to claim 5, wherein distributing is performed by a reliable multicast protocol.

8. Apparatus, comprising:

a switch interconnected in a data network with a plurality of network elements, the switch configured to mediate data exchanges among the network elements;

a processor, operative for organizing the network elements into at least one hierarchical tree having a root node network element, vertex node network elements and child node network elements, the child node network elements comprising leaf node network elements,

wherein the leaf node network elements are operative for originating aggregation data and transmitting the aggregation data to respective parent vertex node network elements thereof, and

wherein the vertex node network elements are operative for combining the aggregation data from at least a portion of the child node network elements thereof; and

transmitting the combined received aggregation data from the vertex node network elements to parent vertex node network elements thereof, and the root node network element is operative, when all expected aggregation data have been received thereat, for initiating a reduction operation on the aggregation data and producing an aggregation result, wherein organizing the network elements comprises;

defining multiple hierarchical trees; and

memorizing the multiple hierarchical trees,

wherein after organizing the network elements the data network, the processor is operative for performing the additional steps of;

initializing a job that requires resources of the data network; and

selecting a best matching one of the memorized multiple hierarchical trees for the job.

9. The apparatus according to claim 8, wherein organizing the network elements comprises conforming a mapping of the hierarchical tree to a topology of the data network.

10. The apparatus according to claim 8, wherein the vertex node network elements are further operative for updating a database of outstanding aggregation operations.

11. The apparatus according to claim 10, wherein the database comprises a status of pending aggregation requests in the child node network elements of the vertex node network elements.

12. The apparatus according to claim 8, wherein the root node network element is operative for distributing the aggregation result to all the network elements of an aggregation collective group.

13. Apparatus, comprising:

a switch interconnected in a data network with a plurality of network elements, the switch configured to mediate data exchanges among the network elements;

a processor, operative for organizing the network elements into at least one hierarchical tree having a root node network element, vertex node network elements and child node network elements, the child node network elements comprising leaf node network elements,

wherein the leaf node network elements are operative for originating aggregation data and transmitting the aggregation data to respective parent vertex node network elements thereof, and

wherein the vertex node network elements are operative for combining the aggregation data from at least a portion of the child node network elements thereof;

and transmitting the combined received aggregation data from the vertex node network elements to parent vertex node network elements thereof, and the root node network element is operative, when all expected aggregation data have been received thereat, for initiating a reduction operation on the aggregation data and producing an aggregation result,

wherein the vertex node network elements are operative for performing respective local reduction operations on the combined received aggregation data to produce local aggregation results; and

the vertex node network elements are also operative for transmitting the local aggregation results to the parent vertex node network elements thereof.

14. A method, comprising the steps of:

organizing an aggregation collective group of network elements of a data network into a hierarchical tree having a root node network element, vertex node network elements and child node network elements, the child node network elements comprising leaf node network elements;

originating aggregation data in the leaf node network elements;

iteratively performing the steps of;

(1) receiving the aggregation data from at least a portion of the child node network elements of respective parent vertex node network elements thereof; and

(2) in the vertex node network elements combining the received aggregation data from at least a portion of the child node network elements thereof; and

(3) transmitting the combined received aggregation data from the vertex node network elements to parent vertex node network elements thereof; and

in the root node network element initiating, when all expected aggregation data have been received thereat, a reduction operation on the aggregation data to produce an aggregation result,

the method further comprising;

performing in the vertex node network elements respective local reduction operations on the combined received aggregation data to produce local aggregation results; and

transmitting the local aggregation results to the parent vertex node network elements thereof.

15. The method according to claim 14, further comprising distributing the aggregation result from the root node network element to the network elements of the aggregation collective group.

16. The method according to claim 14, wherein organizing an aggregation collective group of network elements comprises conforming a mapping of the hierarchical tree to a topology of the data network.

17. The method according to claim 14, further comprising the step of:

in the vertex node network elements updating a database of outstanding aggregation operations.

18. The method according to claim 17, wherein the database comprises a status of pending aggregation requests in the child node network elements of the vertex node network elements.

19. The method according to claim 14, further comprising organizing the network elements by:

defining multiple hierarchical trees; and

memorizing the multiple hierarchical trees,

thereafter performing the additional steps of;

initializing a job that requires resources of the data network; and

selecting a best matching one of the memorized multiple hierarchical trees for the job.

20. The method according to claim 14, wherein organizing an aggregation collective group comprises defining multiple aggregation collective groups, and thereafter performing the additional steps of:

initializing a job that requires resources of the data network; and

selecting a best matching one of the multiple aggregation collective groups for the job.