Random next iteration for data update management

• US 8,745,264 B1
• Filed: 03/31/2011
• Issued: 06/03/2014
• Est. Priority Date: 03/31/2011
• Status: Expired due to Fees

• 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:
  US13/076,932
• Time in Patent Office: 1,160 Days
• Field of Search: 709/203, 709/231, 709/235, 370/235, 370/412
• US Class Current: 709/235
• 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 selected to process workload data for the customer and 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 and processing the workload data using a processing host server of the group of host servers; and

in response to processing the workload data using the processing host server, selecting a random ordering of the other host servers in the group of host servers and sending updates of the workload data to each of the other host servers in the group of host servers according to the random ordering,

wherein updates to be periodically shared across all the host servers in the group of host servers are sent with randomized orderings in order to reduce a statistical likelihood of network congestion due to flow convergence.

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

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

4. The computer-implemented method of claim 1, wherein the processing host server of the group of host servers sending the updates is able to select itself as a next receiving host server per the random 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 random ordering is implemented in an Application Programmer Interface (API) library which is configured to manage network traffic.

7. The computer-implemented method of claim 6, wherein the network traffic includes at least one of broadcast traffic and multicast traffic.

8. The computer-implemented method of claim 6, wherein the API is implemented in a Message Passing Interface (MPI) or open message passing (OpenMP) library.

9. The computer-implemented method of claim 6, wherein the API is implemented in an Internet Protocol (IP) library.

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

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

12. The computer-implemented method of claim 1, wherein host servers selected to process similar network traffic for the customer are distributed across as many network switches at the lowest layer of the network aggregation fabric as possible.

13. The computer-implemented method of claim 1, wherein a portion of the host servers in the group of host servers selected to process similar network traffic for the customer are distributed across a plurality of sub-networks.

14. The computer-implemented method of claim 1, wherein at least one cluster of network switches for performing an operation is a network with re-arrangeably non-blocking bandwidth.

15. The computer-implemented method of claim 14, wherein the at least one cluster of network switches for performing an operation is a Clos topology network.

16. The computer-implemented method of claim 1, wherein at least one cluster of network switches utilizes a network topology selected from a hierarchical router pair or an irregular ad hoc network topology.

17. 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 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 selected to process the common type of customer data and being dispersed across a number of interconnecting devices for at least a lowest layer of the network fabric;

routing the common type of customer data to one of the group of computing elements corresponding to a terminating address and processing the common type of customer data using a processing computing element of the group of computing elements;

in response to processing the common type of customer data using the processing computing element of the group of computing elements, selecting a random ordering of the other computing elements in the group of computing elements and sending updates of the common type of customer data to each of the other computing elements in the group of computing elements according to the random ordering,

wherein updates to be periodically shared across all the computing elements in the group of computing elements are sent with different randomized orderings.

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

a processor; and

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 selected to process workload data for the customer and 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 and processing the workload data using a processing host server of the group of host servers; and

in response to processing the workload data using the processing host server, select a random ordering of the other host servers in the group of host servers and send updates of the workload data to each of the other host servers in the group of host servers according to the random ordering,

wherein updates to be periodically shared across all the host servers in the group of host servers are sent with randomized orderings in order to reduce a statistical likelihood of network congestion due to flow convergence.

19. The system of claim 18, wherein multicast or broadcast network traffic is converted to iterative unicast on a sending host server of the group of host servers before transmitting to the network aggregation fabric.

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

21. The system of claim 18, wherein the processing host server of the group of host servers sending the updates is able to select itself as a next receiving host server per the random ordering.

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

23. The system of claim 22, wherein the network traffic includes at least one of broadcast traffic and multicast traffic.

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

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