Flow control for gossip protocol

• US 8,103,787 B1
• Filed: 06/25/2010
• Issued: 01/24/2012
• Est. Priority Date: 03/28/2007
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: VanRenesse, Robbert
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US12/823,933
• Time in Patent Office: 578 Days
• Field of Search: 709/210, 709/202, 709/204, 709/205, 709/248, 709/223, 709/224, 709/230, 709/232, 709/233
• US Class Current: 709/232
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 47/25 with rate being modified by the source upon detecting a change of network conditions
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Techniques for reducing propagation delay and message loss within a network when replicating information among host computing devices are provided. To maintain flow control among host computing devices, a distributed transmission rate for host computing devices is allocated. Host computing devices adjust the transmission rate based on determined use by each host computing device. Individual host computing devices can also reduce propagation delay and message loss when replicating information by adjusting the number of updates produced based on overflow detections.

Claims

1. A system for regulating transmission rates between two or more host computing devices within a network, wherein each host computing device includes state information having variables about the host computing device, each variable having a version for tracking information, the system comprising:

a first host computing device associated with a first transmission rate, the first host computing device storing in a data store state information having two or more variables corresponding to the first host computing device, wherein each variable is associated with a variable version value for tracking variable values and wherein the first host computing device maintains a first current host version value for the state information corresponding to a maximum version value among the variable version values associated with each of the two or more variables corresponding to the first host computing device; and

a second host computing device associated with a second transmission rate, the second host computing device storing in a data store state information having two or more variables corresponding to the second host computing device, wherein each variable is associated with a variable version value for tracking variable values and wherein the second host computing device maintains a second current host version value for the state information corresponding to a maximum variable version value among the variable version values associated with each of the two or more variables corresponding to the second host computing device; and

wherein the first host computing device updates values of the two or more variables corresponding to the first host computing device on the first data store to correspond with values of the two or more variables corresponding to the second host computing device from the second data store, according to transmission rate information at each host computing device, if the variables on the second current host are associated with a version value that is greater than the maximum version value among the variables on the first current host.

2. The system of claim 1, wherein the first host computing device transmits to the second host computing device values of variables stored on the first data store having a maximum variable version value greater than the maximum second current host version value according to the transmission rate information at each host computing device.

3. In a communication system including a plurality of host computing devices, wherein each host computing device includes state information having variables about the host computing device, each variable having an individual version for tracking information, a method for managing state information, the method comprising:

obtaining a remote host version value of state information from a connected host data store, the state information corresponding to two or more variables, the two or more variables having individual version values, wherein the remote host version value corresponds to a maximum individual version value among the individual version values associated with each of the two or more variables for the state information stored on a connected host data store;

determining a receiving host version value of state information maintained by a current host data store, the state information corresponding to two or more variables, the two or more variables having individual version values, wherein the receiving host version value corresponds to a maximum individual version value among the individual version values associated with each of the two or more variables for the state information stored on a receiving host data store;

determining whether the receiving host version value is greater than the obtained remote host version value;

determining a number of pending updates to be transmitted to the connected host data store based on a determination that the receiving host version value is greater than the obtained remote host version value, the pending updates corresponding to values of the two or more variables on the receiving host data store having an individual version greater than the obtained remote host version value;

determining a maximum number of the pending updates that can be transmitted over a period of time, wherein the maximum number of updates is based on a size of a current transmission window; and

adjusting a rate of additional updates based on pending updates.

4. The method of claim 3, wherein the current transmission window comprises a maximum number of updates that a host data store can send per round-trip time.

5. The method of claim 4, wherein adjusting the rate of additional updates comprises decreasing a number of updates for transmission if the number of pending updates exceeds the maximum number of updates.

6. The method of claim 4, wherein adjusting the rate of additional updates comprises increasing a number of updates for transmission if the number of pending updates does not exceed the maximum number of updates.

7. The method of claim 4, wherein adjusting the rate of additional updates comprises linearly adjusting the number of updates.

8. The method of claim 4, wherein adjusting the rate of additional updates comprises multiplicatively adjusting the number of updates.

9. The method of claim 4, wherein adjusting the rate of additional updates comprises decreasing the number of updates by a multiplicative factor if the pending number of updates exceeds the maximum number of updates and increasing the number of updates by a linear factor if the number of updates have been successfully sent throughout a previous transmission window.

10. The method of claim 4, wherein adjusting the rate of additional updates includes decreasing the number of updates by a first factor if the pending number of updates exceeds the maximum number of updates and increasing the number of updates by a second factor if the number of updates have been successfully sent throughout a previous transmission window, wherein the first and second factor are different.

11. The method of claim 3, wherein each of the updates comprise one or more data packets.

12. A non-transitory computer-readable medium for causing at least one processor to perform a method that transmits state information, the method comprising:

obtaining a remote host version value of state information from a connected host computing device, the state information corresponding to two or more variables, the two or more variables having individual version values, wherein the remote host version value corresponds to a maximum individual version value among the individual version values associated with each of the two or more variables for the state information stored on a connected host data store;

determining a receiving host version value of state information maintained by a current host computing device, the state information corresponding to two or more variables, the two or more variables having individual version values, wherein the receiving host version value corresponds to a maximum individual version value among the individual version values associated with each of the two or more variables for the state information stored on a receiving host data store;

determining whether the receiving host version value is greater than the obtained remote host version value;

determining a number of pending updates to be transmitted to the connected host computing device, based on a determination that the receiving host version value is greater than the obtained remote host version value, the pending updates corresponding to values of the two or more variables on the receiving host data store having an individual version greater than the obtained remote host version value,

determining a maximum number of updates that can be transmitted over a period of time, wherein the maximum number of updates is based on a size of a current transmission window; and

determining whether an overflow occurs by comparing the number of pending updates to the maximum number of updates that can be transmitted;

decreasing the number of updates transmitted by a first adjustment factor when an overflow occurs; and

increasing the number of updates transmitted by a second adjustment factor when an overflow does not occur.

13. The method of claim 12, wherein the first adjustment factor corresponds to a multiplicative factor.

14. The method of claim 12, wherein the first adjustment factor corresponds to a linear factor.

15. The method of claim 12, wherein the second adjustment factor corresponds to a multiplicative factor.

16. The method of claim 12, wherein the second adjustment factor corresponds to a linear factor.

17. The method of claim 12, wherein the transmission window is fixed.

18. The method of claim 12, wherein the transmission window varies.

19. A system for adjusting a number of updates produced, the system comprising:

a receiving host data store and a connected host data store, each host data store storing state information, wherein state information on the host data store includes two or more variables, the two or more variables having individual version values;

an interface for communicating with a connected host computing device; and

a data processing component on the receiving host computing device having an executable component, which, when executed, the data processing component;

determines a receiving host version value of a state on the receiving host data store, wherein the receiving host version value corresponds to a maximum version value among the individual version values associated with each of the two or more variables for the state on the receiving host data store;

obtains a remote host version value of a state on the connected host computing device, wherein the remote host version value corresponds to a maximum version value among the individual version values associated with each of the two or more variables for the state on a connected host data store;

determines whether the receiving host version value is greater than the obtained remote host version value;

collects a set of pending updates for transmission to the connected host computing device of two or more variables on the receiving host data store having a version greater than the remote host version value through one or more updates;

determines whether a number of pending updates exceeds a maximum number of updates that can be sent over a period of time, wherein the calculation of the maximum number is based upon a transmission window size; and

adjusts a number of produced updates based on the comparison of the number of pending updates and the maximum number of updates that can be sent over a period of time.

20. The system of claim 19, wherein the data processing component adjusts the number of produced updates by decreasing the number of produced updates for transmission by a factor when an overflow occurs.

21. The system of claim 19, wherein the data processing component adjusts the number of produced updates by increasing the number of produced updates for transmission by a factor when the number of updates have been successfully sent throughout a previous transmission window.