Optimizing batch size for prefetching data over wide area networks

• US 7,711,797 B1
• Filed: 07/31/2006
• Issued: 05/04/2010
• Est. Priority Date: 07/31/2006
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Huang, An-Cheng
• Primary Examiner(s): LIN, WEN TAI
• Application Number:
  US11/495,599
• Time in Patent Office: 1,373 Days
• Field of Search: None
• US Class Current: 709/218
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics

Abstract

A data prefetching technique optimizes the batch size of prefetch requests. The optimized batch size may be determined based on a prefetch transfer time of a previous prefetch operation, where the prefetch transfer time is measured as an elapsed time interval from when data from the previous prefetch operation is first received to when the data from the previous prefetch operation is finished being received.

Claims

1. A device, comprising:

a processor to;

calculate a prefetch transfer time, T_pt, over a link in a network, where the prefetch transfer time includes an elapsed time interval from when data from a previous prefetch is first received by the device to when the data from the previous prefetch is finished being received by the device,

where

2. The device of claim 1, where the network is a wide area network.

3. The device of claim 1, where the processor, when determining the batch size, is further to:

compare the prefetch transfer time to a threshold value;

reduce the batch size of the data that is to be prefetched when the prefetch transfer time is above the threshold value; and

increase the batch size of the data that is to be prefetched when the prefetch transfer time is below the threshold value.

4. The device of claim 3, where the threshold value is a value within a range of values, and where the processor is further to:

reduce the batch size when the prefetch transfer time is above a high end of the range, and

increase the batch size when the prefetch transfer time is below a low end of the range.

5. The device of claim 1, where the processor is further to:

obtain a round trip time for data traversing the network,

where the processor, when determining the batch size, is to use the obtained round trip time.

6. The device of claim 1, where the processor is further to:

obtain an indication of data locality of a session corresponding to the data that is to be prefetched,

where the indication of data locality value includes a likelihood that a plurality of read requests to acquire the data are at least one of spatially close or temporally close, and where the processor is to use the obtained indication of data locality when determining the batch size.

7. The device of claim 1, where the processor is further to:

obtain a round trip time for data traversing the network;

obtain an indication of data locality of a session corresponding to the data that is to be prefetched, where the indication of data locality value includes a likelihood that a plurality of read requests to acquire the data are at least one of spatially close or temporally close; and

use the obtained round trip time and the obtained indication of data locality when determining the batch size.

8. The device of claim 1, where the processor is further to use a previous batch size when determining the batch size.

9. An automated method, comprising:

measuring, by a network device, a prefetch transfer time, T_pt, over a network of a previously prefetched batch of data, the prefetch transfer time including an elapsed time interval from when portions of the previously prefetched batch of data is first received by the network device to when the previously prefetched batch of data is finished being received by the network device,

where

10. The method of claim 9, where the size of the next batch of data is increased when the measured prefetch transfer time is lower than the threshold.

11. The method of claim 9, where the size of the next batch of data is decreased when the measured prefetch transfer time is higher than the threshold.

12. The method of claim 9, further comprising:

setting the size of the next batch of data to a default size for a first prefetch operation.

13. The method of claim 9, where the network is a wide area network.

14. The method of claim 9, where the threshold value is a value within a range of values and where modifying the size of the next batch of data includes:

reducing the size of the next batch of data when the prefetch transfer time is above a high end of the range of values; and

increasing the size of the next batch of data when the prefetch transfer time is below a low end of the range of values.

15. The method of claim 9, further comprising:

obtaining a round trip time for data traversing the network,

where the modifying of the size of the next batch of data includes using the obtained round trip time.

16. The method of claim 9, further comprising:

obtaining an indication of data locality of a session corresponding to the data that is to be prefetched,

where the indication of data locality value includes a likelihood that a plurality of read requests to acquire the data are at least one of spatially close or temporally close, where the modifying of the size of the next batch of data includes using the obtained indication of data locality when modifying a size of the next batch of data.

17. The method of claim 9, where measuring the prefetch transfer time further includes:

storing an identifier for the previously prefetched batch of data;

storing a time associated with the previously prefetched batch of data; and

using the identifier and the stored time to measure the prefetch transfer time.

18. A system, comprising:

a first network acceleration device to transmit data prefetch requests to request a determined batch size of data, the first network acceleration device determining the batch size to request based on a prefetch transfer time, T_pt, observed for previous prefetch requests, the prefetch transfer time including an elapsed time interval from when data associated with one of the previous prefetch requests is first received to when all of the data associated with the one of the previous prefetch requests is finished being received,

where

19. The system of claim 18, where the first and second network acceleration devices are separated by a wide area network.

20. The system of claim 18, where, when determining the batch size to request, the first network acceleration device compares the prefetch transfer time to a threshold value and adjusts a previous batch size based on the prefetch transfer time being above or below the threshold value, associated with a particular one of the previous prefetch request.

21. The system of claim 20, where the threshold value is a value within a range of values, and

where the first network acceleration device is to:

reduce the previous batch size when the prefetch transfer time is above a high end of the range, and

increase the previous batch size when the prefetch transfer time is below a low end of the range.

22. The system of claim 18, where the first network acceleration device is further to:

obtain a round trip time for data traversing the network, and

use the round trip time when determining the batch size to request.

23. The system of claim 18, where the first network acceleration device is to:

obtain an indication of data locality of a session corresponding to the data prefetch requests, where the indication of data locality value includes a likelihood that a plurality of read requests to acquire the data are at least one of spatially close or temporally close, and

use the obtained indication of data locality when determining the batch size to request.

24. A network device comprising:

means for measuring a time interval from a previous data prefetch operation as an elapsed time from when data from the previous data prefetch operation is first received at the network device to when all of the data from the previous prefetch operation is finished being received at the network device, where

the time interval includes a prefetch transfer time T_pt,