Regulating transmission rates

• US 7,756,995 B1
• Filed: 03/28/2007
• Issued: 07/13/2010
• Est. Priority Date: 03/28/2007
• Status: Expired due to Fees

• 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:
  US11/692,882
• Time in Patent Office: 1,203 Days
• Field of Search: 709/230, 709/232, 709/233, 709/224, 709/223, 709/250
• US Class Current: 709/233
• 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. In a communication system including a plurality of host computing devices, a method for regulating transmission rates for the plurality of host computing devices, wherein each host includes a transmission rate and state information having one or more variables about a host computing device, each variable having a version for tracking information, the method comprising:

obtaining a remote transmission rate from a connected host;

determining a distributed transmission rate, wherein the distributed transmission rate corresponds to the remote transmission rate and a current transmission rate;

obtaining a remote current variable version value from the connected host, wherein the remote current variable version value corresponds to a maximum version value for one or more variables of corresponding state information about the host computing device on a remote data store;

determining whether the remote current variable version value is greater than a current variable version value, wherein the current variable version value corresponds to a maximum version value for one or more variables on a data store;

updating variable values for the state information about the host computing device on the data store according to the distributed transmission rate corresponding to variable values on the remote data store if the variables from the remote data store are associated with a version greater than the current variable version value of the data store;

transmitting to the connected host according to the distributed transmission rate variable values for the state information about the host computing device on the data store having a version greater than the remote current variable version value; and

adjusting the distributed transmission rate based on at least one of;

average transmission rate of the host computing devices, number of packets updated and transmitted by each of the host computing devices, bandwidth previously taken by each of the host computing devices, a priority assigned to each of the host computing devices, and a maximum transmission rate specified by at least one of the host computing devices.

2. The method of claim 1, wherein obtaining the remote transmission rate from the connected host comprises establishing communication through a network with the connected host.

3. The method of claim 1, wherein determining a distributed transmission rate comprises dividing in half the sum of the remote transmission rate and the current transmission rate.

4. The method of claim 1, wherein determining a distributed transmission rate comprises dividing the sum of the remote transmission rate and the current transmission rate by a factor.

5. The method of claim 4, wherein dividing the sum of the remote transmission rate and the current transmission rate by a factor, the factor corresponding to a number of variable values updated and transmitted.

6. The method of claim 4, wherein dividing the sum of the remote transmission rate and the current transmission rate by a factor, the factor corresponding to previous use.

7. The method of claim 5, wherein dividing the sum of the remote transmission rate and the current transmission rate by a factor, the factor corresponding to priority determinations.

8. The method of claim 1, wherein determining a distributed transmission rate comprises allocating a transmission rate of a host up to a specified maximum transmission rate of the host.

9. The method of claim 1, wherein adjusting the distributed transmission rate includes increasing the current transmission rate.

10. The method of claim 9, wherein increasing the current transmission rate includes acquiring an additional transmission rate from the connected host, wherein the connected host has the additional transmission rate for use.

11. The method of claim 1, wherein adjusting the distributed transmission rate includes decreasing the current transmission rate.

12. The method of claim 11, wherein decreasing the current transmission rate includes releasing an additional transmission to the connected host when the connected host requires the additional transmission rate for use and the current transmission rate is not used at capacity.

13. The method of claim 1, wherein adjusting the distributed transmission rate occurs during each updating of a variable value.

14. The method of claim 1, wherein adjusting the distributed transmission rate occurs during each transmitting of a variable value.

15. The method of claim 1, wherein adjusting the distributed transmission rate occurs during each updating of multiple variable values.

16. The method of claim 1, wherein adjusting the distributed transmission rate occurs during each transmitting of multiple variable values.

17. A computer-readable media storing instructions for causing at least one processor to perform a method for regulating transmission rates for a plurality of host computing devices, the method comprising:

obtaining a remote transmission rate from a connected host;

determining a distributed transmission rate, wherein the distributed transmission rate corresponds to the remote transmission rate and a current transmission rate;

obtaining a remote current variable version value from the connected host, wherein the remote current variable version value corresponds to a maximum version value of state information on a remote data store, the state information associated with one or more variables about a host computing device on the remote data store with each variable having a version;

determining whether the remote current variable version value is greater than a current variable version value, wherein the current variable version value corresponds to a maximum version value of the state information on a data store, the state information associated with one or more variables about the host computing device on the data store with each variable having a version;

updating variable values for the state information about the host computing device on the data store with variable values of the state information about the host computing device on the remote data store according to the distributed transmission rate if the remote current variable version value is greater than the current variable version value;

transmitting the variable values for the state information about the host computing device to the remote data store according to the distributed transmission rate if the current variable version value is greater than the remote current variable version value; and

adjusting the distributed transmission rate based on at least one of transmission rate information, host computing device bandwidth information and data previously transmitted to the remote data store.

18. The computer-readable media of claim 17, wherein adjusting the distributed transmission rate includes increasing the current transmission rate.

19. The computer-readable media of claim 18, wherein increasing the current transmission rate includes acquiring an additional transmission rate from the connected host, wherein the connected host has the additional transmission rate for use.

20. The computer-readable media of claim 17, wherein adjusting the distributed transmission rate includes decreasing the current transmission rate.

21. The computer-readable media of claim 20, wherein decreasing the current transmission rate includes releasing an additional transmission to the connected host when the connected host requires the additional transmission rate for use and the current transmission rate is not used at capacity.

22. The computer-readable media of claim 17, wherein the transmission rate information comprises average transmission rate of the host computing devices.

23. The computer-readable media of claim 17, wherein the transmission rate information comprises number of packets updated and transmitted by each of the host computing devices.

24. The computer-readable media of claim 17, wherein the host computing device bandwidth information comprises bandwidth previously taken by each of the host computing devices.

25. The computer-readable media of claim 17, wherein the host computing device bandwidth information comprises a priority assigned to each of the host computing devices.

26. The computer-readable media of claim 17, wherein the host computing device bandwidth information comprises a maximum transmission rate specified by at least one the host computing devices.

27. The computer-readable media of claim 17, wherein data previously transmitted to the remote data store.