Method and system for background replication of data objects

• US 8,099,492 B2
• Filed: 08/20/2008
• Issued: 01/17/2012
• Est. Priority Date: 07/25/2002
• Status: Expired

• Current Assignee: Intellectual Ventures Holding 40 LLC (Intellectual Ventures LLC)
• Original Assignee: Intellectual Ventures Holding 40 LLC (Intellectual Ventures LLC)
• Inventors: Dahlin, Michael D., Venkataramani, Arunkumar, Kokku, Ravindranath, Yalagandula, Praveen
• Primary Examiner(s): Joo, Joshua
• Application Number:
  US12/195,073
• Publication Number:
  US 20080313328A1
• Time in Patent Office: 1,245 Days
• Field of Search: 709223-226, 709230-235, 709238-242, 370229-235
• US Class Current: 709/224
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

In an embodiment, a system and method may manage network resources to provide a near zero-cost background replication of data. Such a system may be inhibited from causing interference with foreground data flows. Such a system may also utilize a large fraction of spare network bandwidth. A system configured to implement such a method may include one or more servers and at least one client in communication via a network. Additionally the system may include a hint server, a monitor and/or a front-end application between a demand server and the network.

Claims

1. A method of controlling data transmission over a communication network, the method comprising:

sending, by a device, one or more data packets over the communication network in view of a congestion window representative of a congestion state of the communication network;

determining, by the device, a time that a first data packet was sent;

receiving, by the device, an acknowledgement of receipt of at least the first data packet;

determining, by the device, a time that the acknowledgement of receipt of the first data packet was received;

determining, by the device, an estimate of network congestion based at least in part on the time the first data packet was sent and the time the acknowledgement of receipt of the first data packet was received; and

if the estimate of network congestion exceeds a congestion threshold, then reducing a size of the congestion window,

wherein round trip times are indicative of a bottleneck queue size and wherein the congestion threshold represents a number of round trip times that exceed the bottleneck queue size.

2. The method of claim 1, wherein said determining, by the device, the estimate of network congestion includes:

determining, by the device, a number of round trip times, received during an interval, that exceed a threshold round trip time,

wherein a round trip time includes an elapsed time between a time that a data packet is sent and a time that an acknowledgement of receipt of the data packet is received.

3. The method of claim 2, wherein the congestion threshold further represents a percentage of round trip times that exceed the threshold round trip time during the interval.

4. The method of claim 1, wherein said reducing, by the device, the size of the congestion window includes reducing, by the device, the size of the congestion window by at least a multiplicative factor.

5. The method of claim 1, wherein the congestion window determines an amount of prefetch data to be in transit at any one time.

6. The method of claim 1, wherein said sending, by the device, one or more data packets includes sending, by the device, one or more pointers to one or more requested data.

7. The method of claim 1, wherein said sending, by the device, one or more data packets includes sending, by the device, one or more requested data packets.

8. The method of claim 1, wherein said determining, by the device, the estimate of network congestion includes determining, by the device, a number of round trip times received during an interval that exceed a threshold round trip time,

wherein a round trip time includes an elapsed time between a time that a data packet is sent and a time that an acknowledgement of receipt of the data packet is received, and

wherein the congestion threshold is determined to be exceeded if the number of round trip times exceeding the threshold round trip time during the interval exceeds a threshold fraction of a number of round trip times measured.

9. The method of claim 1, further comprising increasing, by the device, the size of the congestion window if the estimate of network congestion does not exceed the congestion threshold.

10. The method of claim 1, further comprising linearly increasing, by the device, the size of the congestion window if the estimate of network congestion does not exceed the congestion threshold.

11. The method of claim 1, further comprising increasing, by the device, the size of the congestion window by a determined number of data packets per determined number of round trip times if the estimate of network congestion does not exceed the congestion threshold.

12. The method of claim 1, further comprising increasing, by the device, the size of the congestion window by a determined number of data packets and by a determined multiplicative factor per determined number of round trip times if the estimate of network congestion does not exceed the congestion threshold.

13. The method of claim 1, wherein said sending, by the device, includes sending the first data packet and a second data packet, wherein a time period between said sending the second data packet and said sending the first data packet is determined based on the size of the congestion window.

14. The method of claim 1, wherein the bottleneck queue size includes a buffer size at a bottleneck router that accounts for round trip delay of a data packet.

15. An article of manufacture, comprising:

a non-transitory computer readable medium; and

a plurality of programming instructions stored on the non-transitory computer readable medium and configured to cause a processor to;

determine a time that a first data packet was sent;

determine a time that an acknowledgement of receipt of the first data packet was received;

determine an estimate of network congestion based at least in part on the time the first data packet was sent and the time the acknowledgement of receipt of the first data packet was received; and

if the estimate of network congestion exceeds a congestion threshold, then reduce a size of a congestion window to be used for future packet transmission,

wherein round trip times are indicative of a bottleneck queue size and wherein the congestion threshold represents a number of round trip times that exceed the bottleneck queue size.

16. The article of manufacture of claim 15, wherein the plurality of programming instructions are further configured to cause the processor to:

determine a number of round trip times received during an interval that exceed a threshold round trip time,

wherein a round trip time includes an elapsed time between a time that a data packet is sent and a time that an acknowledgement of receipt of the data packet is received, and

wherein the plurality of programming instructions are further configured to cause the processor to determine the estimate of network congestion using at least the number of round trip times received during the interval.

17. The article of manufacture of claim 16, wherein the congestion threshold further represents a percentage of round trip times that exceed the threshold round trip time during the interval.

18. The article of manufacture of claim 15, wherein the plurality of programming instructions are further configured to cause the processor to:

determine a number of round trip times received during an interval that exceed a threshold round trip time,

wherein a round trip time includes an elapsed time between a time that a data packet is sent and a time that an acknowledgement of receipt of the data packet is received, and

wherein the congestion threshold is determined to be exceeded if the number of round trip times that exceed the threshold round trip time during the interval exceeds a threshold fraction of a number of round trip times measured.

19. The article of manufacture of claim 15, wherein the plurality of programming instructions are further configured to cause the processor to determine a time period to send a second data packet based at least in part on the size of the congestion window.

20. The article of manufacture of claim 15, wherein the bottleneck queue size includes a buffer size at a bottleneck router that accounts for round trip delay of a data packet.

21. An apparatus, comprising:

a network device that includes a memory and that further includes;

a network interface module to couple the network device to a communication network; and

a communications module coupled to the network interface module and configured to;

transmit one or more packets over the communication network to one or more receivers in view of a congestion window representative of a congestion state of the communication network;

receive acknowledgements of receipt of the one or more packets;

determine a round trip time using a time that a first packet was sent and a time that a corresponding acknowledgement was received;

determine an estimate of network congestion for the communication network based at least in part on the determined round trip time; and

if the estimate of network congestion exceeds a congestion threshold, then reduce a size of a congestion window to be used for future transmission,

wherein round trip times are indicative of a bottleneck queue size and wherein the congestion threshold represents a number of round trip times that exceed the bottleneck queue size.

22. The apparatus of claim 21, wherein the congestion threshold further represents a percentage of round trip times that exceed a threshold round trip time during an interval.

23. The apparatus of claim 21, wherein the communications module is further configured to determine the estimate of network congestion based on a number of round trip times received during an interval that exceed a threshold round trip time,

wherein a round trip time includes an elapsed time between a time that a packet is sent and a time that an acknowledgement of receipt of the packet is received, and

wherein the congestion threshold is determined to be exceeded if the number of round trip times that exceed the threshold round trip time during the interval exceeds a threshold fraction of a number of round trip times measured.

24. The apparatus of claim 21, wherein the bottleneck queue size includes a buffer size at a bottleneck router that accounts for round trip delay of a packet.

25. An apparatus, comprising:

means for sending one or more data packets over a communication network, in view of a congestion window representative of a congestion state of the communication network;

means for determining a time that a first data packet was sent;

means for receiving an acknowledgement of receipt of at least the first data packet;

means for determining a time that the acknowledgement of receipt of the first data packet was received;

means for determining an estimate of network congestion based at least in part on the time the first data packet was sent and the time the acknowledgement of receipt of the first data packet was received; and

means for reducing the size of the congestion window if the estimate of network congestion exceeds a congestion threshold,

wherein round trip times are indicative of a bottleneck queue size and wherein the congestion threshold represents a number of round trip times that exceed the bottleneck queue size.

26. The apparatus of claim 25, wherein the means for reducing the size of the congestion window reduces the size of the congestion window by at least a multiplicative factor.

27. The apparatus of claim 25, wherein the means for determining the estimate of network congestion determines a number of round trip times received during an interval that exceed a threshold round trip time,

wherein a round trip time includes an elapsed time between a time that a data packet is sent and a time that an acknowledgement of receipt of the data packet is received, and

wherein the congestion threshold is determined to be exceeded if the number of round trip times that exceed the threshold round trip time during the interval exceeds a threshold fraction of a number of round trip times measured.

28. The apparatus of claim 25, further comprising means for increasing the size of the congestion window if the estimate of network congestion does not exceed the congestion threshold.

29. The apparatus of claim 25, further comprising means for linearly increasing the size of the congestion window if the estimate of network congestion does not exceed the congestion threshold.