Parallel data transfer over multiple channels with data order prioritization

• US 8,103,786 B2
• Filed: 06/23/2009
• Issued: 01/24/2012
• Est. Priority Date: 02/28/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Swarmcast, Inc.
• Inventors: Chapweske, Justin F.
• Primary Examiner(s): Osman, Ramy M
• Application Number:
  US12/490,128
• Publication Number:
  US 20090327512A1
• Time in Patent Office: 945 Days
• Field of Search: 709/203, 709217-219, 709224-225, 709/232, 709/233, 709/244
• US Class Current: 709/232
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 65/752 adapting media to network capabilities
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1085 involving dynamic management of active down- or uploading connections
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A parallel download system is described to download data from a plurality of source servers in parallel. The system may include a source scheduler, a prioritization scheduler, and an I/O dispatcher. The source scheduler generates a download schedule to control which source servers will be downloaded from at a current point in time. The prioritization scheduler tracks the latency and throughput of all channels to the source servers and dynamically adjusts the download schedule to control download performance. The I/O dispatcher produces an output stream to present the downloaded data to one or more external applications or a user.

Claims

1. A computing device comprising:

a microprocessor;

a parallel download system executing on the microprocessor to control download of data from a plurality of source servers in parallel, wherein each of the source servers stores a copy of at least a portion of a file containing data, the parallel download system comprising;

a source scheduler executing on the microprocessor and configured to rank a plurality of communication channels to generate a download schedule specifying from which of the plurality of communication channels data will be downloaded in parallel at a point in time, and wherein each of the plurality of communication channels comprises a network connection from the computing device to one of the plurality of source servers;

a prioritization scheduler executing on the microprocessor and configured to (i) determine a range of the data to be requested from one or more source servers, (ii) determine the point in time when the range of data is to be requested from the one or more source servers, (iii) track an overall latency and throughput for the communication channels during parallel download of the data, and (iv) dynamically adjust the download schedule based on the latency and throughput of the communication channels to control download performance;

a proportional allocator executing on the microprocessor and configured to determine a plurality of portions of the range of data to be downloaded from each of the source servers and assign a time interval for downloading each of the plurality of portions of the range of data, wherein the proportional allocator determines the plurality of portions to be download from each of the source server based on one or more of an expected throughput and latency of one or more communication channels to that source server during the time interval for downloading the plurality of portions of the range of data; and

an I/O dispatcher executing on the microprocessor and configured to produce an output stream to present the downloaded data to one or more external applications or a user.

2. The parallel download system of claim 1, wherein the source scheduler keeps track of information about each source server and uses that information to decide which source servers to download from.

3. The parallel download system of claim 1, further comprising a data prioritizer that determines the priority of the data within the file to be scheduled, wherein the data prioritizer specifies an ordering of the data within the file from a highest priority data to a lowest priority data, and wherein different portions of the file are downloaded in parallel from the two or more of the plurality of servers in accordance with the ordering of the data within the file as specified by the data prioritizer and the download schedule as dynamically adjusted by the prioritization scheduler.

4. The parallel download system of claim 3, wherein the data prioritizer specifies the ordering of the data within the file from the highest priority data to the lowest priority data by adjusting the ordering of the data within the file during the download of the different portions of the file from the two or more plurality of servers.

5. The parallel download system of claim 4, further comprising one or more external applications that are attempting to access the data within the file, wherein the data prioritizer adjusts the ordering of the data within the file based on which one or more external applications are attempting to access the data within the file.

6. The parallel download system of claim 4, further comprising a corruption repair engine that detects and repairs corruption in previously downloaded portions of the data within the file, wherein the data prioritizer adjusts the ordering of the data within the file based on the detected and repaired corruption.

7. The parallel download system of claim 6, wherein the data prioritizer assigns a higher priority to the data within the file that the corruption repair engine is repairing.

8. The parallel download system of claim 4, wherein the data prioritizer assigns priority based on the number of servers from which the data is available for download.

9. The parallel download system of claim 3, wherein the data prioritizer employs a prioritization scheme when multiple applications or component are simultaneously specifying different portions of the data to prioritize.

10. The parallel download system of claim 9, wherein the prioritization scheme comprises at least one of a First Come First Serve, Last Come First Serve, Random, Shortest Processing Time First, Round Robin, and Shortest Remaining Processing Time First.

11. The parallel download system of claim 3, wherein the highest priority data is downloaded on average before the lowest priority of data.

12. The parallel download system of claim 3, wherein the prioritization scheduler adjusts the download schedule with respect to the different servers while maintaining a prioritization order in which the data within the file will be received.

13. The parallel download system of claim 1, further comprising one or more channel adapters to translate encoded information from a first format used to transfer the information across a channel to a second format desired for a download.

14. The parallel download system of claim 1, further comprising a control interface that allows external applications or users to control the behavior of the parallel download system.

15. The parallel download system of claim 1, further comprising a bulk scheduler to determine which bytes of the data within the file will be scheduled.

16. The parallel download system of claim 1, wherein the time interval comprises a current time interval, the system further comprising an advanced scheduler that integrates with the proportional allocator to allow data to be allocated during a different time interval than the current time interval.

17. The parallel download system of claim 1, further comprising one or more channel connector to establish a new communication channel to the scheduled source server.

18. The parallel download system of claim 1, wherein the source scheduler ranks the source servers according to one or more of:

external ranking input received from a user or an administrator or an external ranking service;

a throughput associated with each source server;

a latency associated with each source server;

a number of network hops to the source server from the parallel download system;

a geographical location of each source server relative to the parallel download system; and

a channel cost associated with the channel from the parallel download system to each source server.

19. The parallel download system of claim 1, wherein different portions of the file are downloaded in parallel from the two or more of the plurality of servers in accordance with the download schedule.

20. The parallel download system of claim 1, wherein a new server is added to the plurality of servers during download of data.

21. The parallel download system of claim 1, wherein at least one server of the plurality of servers is removed during download of data.

22. The parallel download system of claim 1, wherein the prioritization scheduler comprises the proportional allocator.

23. The parallel download system of claim 1, wherein at least two of the communication channels provide network connections to a same one of the plurality of source servers.

24. A method to control download of data from a plurality of source servers in parallel the method comprising:

ranking a plurality of communication channels, in a computing device, to generate a download schedule to control from which of the plurality of communication channels data will be downloaded in parallel at a point in time, wherein each of the source servers stores a copy of at least a portion of a file containing data, and wherein each of the plurality of communication channels comprises a network connection from the computing device to one of the plurality of source servers;

determining, in the computing device, a range of the data to be requested from one or more source servers;

determining, in the computing device, the point in time when the range of data should be requested from the one or more source servers;

tracking, in the computing device, an overall latency and throughput for all the communication channels during parallel download of the data;

dynamically adjusting, in the computing device, the download schedule based on the latency and throughput of the communication channels, wherein dynamically adjusting comprises dynamically adjusting the range of data and the point in time to request the range of data from the one or more source servers during parallel download to control download performance;

determining, in the computing device, a plurality of portions of the range of data to be downloaded from that source server and assigning, via the computing device, a time interval for downloading each of the plurality of portions of the range of data, wherein determining the plurality of portions to be download comprises determining the plurality of portion to be downloaded from that source server based on one or more of an expected throughput and latency of one or more communication channels to that source server during the time interval for downloading the plurality of portions of the range of data; and

producing, in the computing device, an output stream to present the downloaded data to one or more external applications or a user.

25. The method of claim 24, wherein ranking a plurality of communication channels comprises tracking information about each source server and using that information to decide which source servers to download from.

26. The method of claim 24, further comprising:

determining the priority of the data within the file to be scheduled;

specifying an ordering of the data within the file from a highest priority data to a lowest priority data, wherein different portions of the file are downloaded in parallel from the two or more of the plurality of servers in accordance with the ordering of the data within the file as specified and the dynamically adjusted download schedule.

27. The method of claim 26, wherein specifying the ordering of the data within the file from the highest priority data to the lowest priority data comprises adjusting the ordering of the data within the file during the download of the different portions of the file from the two or more plurality of servers.

28. The method of claim 27, further comprising:

attempting to access the data within the file by one or more external applications, wherein adjusting the ordering comprises adjusting the ordering of the data within the file based on which one or more external applications are attempting to access the data within the file.

29. The method of claim 27, further comprising detecting and repairing corruption in previously downloaded portions of the data within the file, wherein adjusting the ordering of the data comprises adjusting the ordering of the data within the file based on the detected and repaired corruption.

30. The method of claim 27, further comprising assigning priority based on the number of servers from which the data is available for download.

31. The method of claim 24, wherein different portions of the file are downloaded in parallel from the two or more of the plurality of servers in accordance with the download schedule.

32. The method of claim 24, wherein a new server is added to the plurality of servers during download of data.

33. The method of claim 24, wherein at least one server of the plurality of servers is removed during download of data.

34. The method of claim 24, wherein at least two of the communication channels provide network connections to a same one of the plurality of source servers.