Random next iteration for data update management

• US 9,456,057 B2
• Filed: 05/30/2014
• Issued: 09/27/2016
• Est. Priority Date: 03/31/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Marr, Michael David
• Primary Examiner(s): Bates, Kevin
• Assistant Examiner(s): RAHMAN, SM AZIZUR
• Application Number:
  US14/292,532
• Publication Number:
  US 20140280521A1
• Time in Patent Office: 851 Days
• Field of Search: 709/235
• US Class Current: 1/1
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Host machines and other devices performing synchronized operations can be dispersed across multiple racks in a data center to provide additional buffer capacity and to reduce the likelihood of congestion. The level of dispersion can depend on factors such as the level of oversubscription, as it can be undesirable in a highly connected network to push excessive host traffic into the aggregation fabric. As oversubscription levels increase, the amount of dispersion can be reduced and two or more host machines can be clustered on a given rack, or otherwise connected through the same edge switch. By clustering a portion of the machines, some of the host traffic can be redirected by the respective edge switch without entering the aggregation fabric. When provisioning hosts for a customer, application, or synchronized operation, for example, the levels of clustering and dispersion can be balanced to minimize the likelihood for congestion throughout the network.

Claims

1. A computer-implemented method of managing data in a networked environment, comprising:

under control of one or more computer systems configured with executable instructions,

receiving workload data having a specified terminating address for one of a group of host servers selected to process a common set of the workload data for a customer, the group of host servers being connected by a network aggregation fabric including layers of network switches, a path across the network aggregation fabric to each of the host servers in the group of host servers involving a number of connections across the layers of network switches, the group of host servers being dispersed across a number of network switches for at least a lowest layer of the network aggregation fabric;

routing the workload data to a host server of the group of host servers corresponding to the specified terminating address, the workload data being processed by a processing host server of the group of host servers;

receiving updates corresponding to the processed workload data obtained from the processing host server; and

routing the updates to other host servers in the group of host servers according to an absolute ordering received from the processing host server, the absolute ordering of the other host servers comprising an iterated transmission sequence of the other host servers in the group of host servers, wherein routing the updates comprises the host server transmitting the updates to a next host in the iterated transmission sequence.

2. The computer-implemented method of claim 1, wherein the received workload data is converted to iterative unicast from multicast or broadcast network traffic on a sending host server of the group of host servers before being received at the network aggregation fabric.

3. The computer-implemented method of claim 1, wherein the network aggregation fabric operates in one of an oversubscribed or a non-oversubscribed state.

4. The computer-implemented method of claim 1, wherein the processing host server of the group of host servers selects a next receiving host server per the absolute ordering.

5. The computer-implemented method of claim 1, wherein the group of host servers are not centrally synchronized with a sending host server of the group of host servers.

6. The computer-implemented method of claim 1, wherein the absolute ordering is implemented in an Application Programmer Interface (API) library which is configured to manage network traffic.

7. The computer-implemented method of claim 1, wherein multiple flows of network traffic from the customer are received concurrently at the network aggregation fabric and directed to a common host server.

8. The computer-implemented method of claim 7, wherein at least one of the multiple flows of network traffic is throttled using a back-off control mechanism.

9. A computer-implemented method of managing data in a networked environment, comprising:

under control of one or more computer systems configured with executable instructions,

receiving customer data having a terminating address that corresponds to one of a group of computing elements selected to process a common type of customer data, the group of computing elements being connected by a network fabric including layers of interconnecting devices each including buffering capacity, a path across the network fabric to each computing element in the group of computing elements involving a number of connections across the layers of interconnecting devices, the group of computing elements being dispersed across a number of interconnecting devices for at least a lowest layer of the network fabric;

routing the customer data to a computing element of the group of computing elements corresponding to the terminating address, the customer data being processed by a processing computing element of the group of computing elements;

receiving updates corresponding to the processed customer data obtained from the processing computing element; and

routing updates to other computing elements in the group of computing elements according to an absolute ordering received from the processing computing element, the absolute ordering of the other computing elements comprising an iterated transmission sequence of the other computing elements in the group of computing elements.

10. The computer-implemented method of claim 9, wherein the received customer data is converted to iterative unicast from multicast or broadcast network traffic on a sending computing element of the group of computing elements before being received at the network aggregation fabric.

11. The computer-implemented method of claim 9, wherein the network aggregation fabric operates in one of an oversubscribed or a non-oversubscribed state.

12. The computer-implemented method of claim 9, wherein the processing computing element of the group of computing elements selects a next receiving computing element per the absolute ordering.

13. The computer-implemented method of claim 9, wherein the group of computing elements are not centrally synchronized with a sending computing element of the group of computing elements.

14. A system for managing data in a networked environment, comprising:

a processor; and

a memory including instructions that, when executed by the processor, cause the system to;

receive workload data having a specified terminating address for one of a group of host servers selected to process a common set of the workload data for a customer, the group of host servers being connected by a network aggregation fabric including layers of network switches, a path across the network aggregation fabric to each of the host servers in the group of host servers involving a number of connections across the layers of network switches, the group of host servers being dispersed across a number of network switches for at least a lowest layer of the network aggregation fabric;

route the workload data to a host server of the group of host servers corresponding to the specified terminating address, the workload data being processed by a processing host server of the group of host servers;

receive updates corresponding to the processed workload data obtained from the processing host server; and

route the updates to other host servers in the group of host servers according to an absolute ordering received from the processing host server, the absolute ordering of the other host servers comprising an iterated transmission sequence of the other host servers in the group of host servers.

15. The system of claim 14, wherein the received workload data is converted to iterative unicast from multicast or broadcast network traffic on a sending host server of the group of host servers before being received at the network aggregation fabric.

16. The system of claim 14, wherein the network aggregation fabric is in one of an oversubscribed or non-oversubscribed state.

17. The system of claim 14, wherein the processing host server of the group of host servers select a next receiving host server per the absolute ordering.

18. The system of claim 14, wherein the absolute ordering is implemented in an Application Programmer Interface (API) library which is configured to manage network traffic.

19. The system of claim 18, wherein the API is implemented in a Message Passing Interface (MPI) or open message passing (OpenMP) library.

20. The system of claim 18, wherein the API is implemented in an Internet Protocol (IP) library.