Method and apparatus for real-time parallel delivery of segments of a large payload file

• US 20020131423A1
• Filed: 10/26/2001
• Published: 09/19/2002
• Est. Priority Date: 10/26/2000
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Prismedia Networks Incorporated
• Inventors: Thakur, Rajeev, Chan, Desmond Cho-Hung, Sim, Siew Yong, Isaacson, Trygve, Gropp, William D.
• Granted Patent: US 7,076,553 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1017 based on a round robin mechanism
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A scalable content delivery network (SCDN) employs a parallel download mechanism to ensure that a demanded file is present at a station in time for user consumption. This mechanism is used in solving the content caching and storage problem for applications such as video-on-demand, which is commonly perceived as a tough problem in the industry. In the network, files are divided into smaller units called tracks according to the nature of data contained in each of them. Tracks are further divided into smaller equally sized units called block files. This division builds the foundation for parallel download. A sequence server provides a lock-free mechanism for multiple threads or processes to access data atomically. The sequence server allows clients to gain sequential access to data, or to find out whether the sequence has been violated so that they can retry their operation or take corrective action. Advantages of the invention include the ability to handle distribution of large files and process sequencing.

Claims

1. A method of assembling a file in response to a request from a user sent to a first node in a network having a plurality of connected nodes, comprising the steps of:

determining, based on the request, which content components are necessary to assemble the file;

if all content components are not present at the first node, sending a search request to determine which other nodes have content components;

receiving, from said other nodes, replies to said search request, each reply from a responding node indicating which content components are available from said responding node;

determining a desired set of at least one node from which to download the content components;

downloading the content components from the desired set; and

assembling the file from the downloaded content components.

2. The method of claim 1, wherein said content components are block files and wherein said first determining step comprises:

determining a number of necessary block files based at least in part on metadata associated with the file.

3. The method of claim 1, wherein said sending step further comprises:

referring to a set of attributes and a set of rolled up attributes for identification of each of the plurality of nodes.

4. The method of claim 1, wherein the nodes are organized in a virtual tree and said sending step comprises:

sending a notification to neighboring nodes in the virtual tree to determine the existence of the content components, wherein the notification includes distribution criteria of at least one of the content components.

5. The method of claim 4, wherein said sending step further comprises:

propagating the search request to at least one node in the network that satisfies the distribution criteria.

6. The method of claim 4, wherein said sending step further comprises:

forwarding, by each neighboring node in receipt of the search request, the notification to next nodes that are in a neighbor relationship with each neighboring node excluding the neighboring nodes from which the search request was received.

7. The method of claim 1, wherein said receiving step comprises:

receiving, from said other nodes, replies to said search request, each reply from a responding node indicating which content components are available from said responding node and performance characteristics of said responding node.

8. The method of claim 1, wherein said downloading step comprises:

downloading a first portion of the content components from a first responding node in parallel with downloading a second portion of the content components from a second responding node

9. The method of claim 1, wherein said second determining step comprises:

determining a desired set of at least one node from which to download the content components, wherein said at least one node is selected based at least in part on proximity to the first node.

10. The method of claim 1, wherein said downloading step comprises:

creating, at said first node, a process representing a request for a content component from at least one node having the content component.

11. The method of claim 10, wherein said downloading step comprises:

creating, at said first node, a plurality of processes, each process representing a request for a content component from one of said plurality of nodes.

12. The method of claim 11, wherein said downloading step further comprises:

associating a flag with each content component to be downloaded, said flag indicating whether an associated content component has already been downloaded, had not been downloaded or is currently being downloaded;

associating a unique sequence number with each flag;

in response to one of said plurality of processes reading said flag to determine whether said associated content component has already been downloaded, incrementing said sequence number and passing said incremented sequence number to said reading process;

in response to a request by said reading process to modify said flag to indicate that said associated content component is currently being downloaded, comparing said incremented sequence number passed to said reading process to said incremented sequence number associated with said flag;

if said incremented sequence number passed to said reading process matches said incremented sequence number associated with said flag, accepting said modification to said flag; and

if said incremented sequence number passed to said reading process does not match said incremented sequence number associated with said flag, rejecting said modification to said flag,

whereby race conditions are avoided when more than one process attempts to download the same content component.

14. The computer program product of claim 13, wherein said content components are block files and wherein said first computer readable program code means comprises:

means for determining a number of necessary block files based at least in part on metadata associated with the file.

15. The computer program product of claim 13, wherein the nodes are organized in a virtual tree and wherein said second computer readable program code means comprises:

means for sending a notification to neighboring nodes in the virtual tree to determine the existence of the content components, wherein the notification includes distribution criteria of at least one of the content components.

16. The computer program product of claim 13, wherein said third computer readable program code means comprises:

means for receiving, from said other nodes, replies to said search request, each reply from a responding node indicating which content components are available from said responding node and performance characteristics of said responding node.

17. The computer program product of claim 13, wherein said fifth computer readable program code means comprises:

means for downloading a first portion of the content components from a first responding node in parallel with downloading a second portion of the content components from a second responding node

18. The computer program product of claim 13, wherein said fourth computer readable program code means comprises:

means for determining a desired set of at least one node from which to download the content components, wherein said at least one node is selected based at least in part on proximity to the first node.

19. The computer program product of claim 13, wherein said fifth computer readable program code means comprises:

means for creating, at said first node, a plurality of processes, each process representing a request for a content component from one of said plurality of nodes;

means for associating a flag with each content component to be downloaded, said flag indicating whether an associated content component has already been downloaded, had not been downloaded or is currently being downloaded;

means for associating a unique sequence number with each flag;

means for incrementing said sequence number and passing said incremented sequence number to said reading process in response to one of said plurality of processes reading said flag to determine whether said associated content component has already been downloaded;

means for comparing, in response to a request by said reading process to modify said flag to indicate that said associated content component is currently being downloaded, said incremented sequence number passed to said reading process to said incremented sequence number associated with said flag;

means for accepting said modification to said flag if said incremented sequence number passed to said reading process matches said incremented sequence number associated with said flag; and

means for rejecting said modification to said flag if said incremented sequence number passed to said reading process does not match said incremented sequence number associated with said flag, whereby race conditions are avoided when more than one process attempts to download the same content component.

13. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer to assemble a file in response to a request from a user sent to a first node in a network having a plurality of connected nodes, said computer readable program code means comprising:

first computer readable program code means for causing the computer to determine, based on the request, which content components are necessary to assemble the file;

second computer readable program code means for causing the computer, if all content components are not present at the first node, to send a search request to determine which other nodes have content components;

third computer readable program code means for causing the computer to receive, from said other nodes, replies to said search request, each reply from a responding node indicating which content components are available from said responding node;

fourth computer readable program code means for causing the computer to determine a desired set of at least one node from which to download the content components;

fifth computer readable program code means for causing the computer to download the content components from the desired set; and

sixth computer readable program code means for causing the computer to assemble the file from the downloaded content components.

20. A computer-based system for assembling a file in response to a request from a user sent to a first node in a network having a plurality of connected nodes, said system comprising:

means for determining, based on the request, which content components are necessary to assemble the file;

means for sending a search request, if all content components are not present at the first node, to determine which other nodes have content components;

means for receiving, from said other nodes, replies to said search request, each reply from a responding node indicating which content components are available from said responding node;

means for determining a desired set of at least one node from which to download the content components;

means for downloading the content components from the desired set; and

means for assembling the file from the downloaded content components.

21. The computer-based system of claim 20, wherein said content components are block files and wherein said first determining means comprises:

means for determining a number of necessary block files based at least in part on metadata associated with the file.

22. The computer-based system of claim 20, wherein the nodes are organized in a virtual tree and wherein said sending means comprises:

means for sending a notification to neighboring nodes in the virtual tree to determine the existence of the content components, wherein the notification includes distribution criteria of at least one of the content components.

23. The computer-based system of claim 20, wherein said receiving means comprises:

means for receiving, from said other nodes, replies to said search request, each reply from a responding node indicating which content components are available from said responding node and performance characteristics of said responding node.

24. The computer-based system of claim 20, wherein said downloading means comprises:

means for downloading a first portion of the content components from a first responding node in parallel with downloading a second portion of the content components from a second responding node.

25. The computer-based system of claim 20, wherein said second determining means comprises:

means for determining a desired set of at least one node from which to download the content components, wherein said at least one node is selected based at least in part on proximity to the first node.

26. The computer-based system of claim 20, wherein said downloading means comprises:

means for creating, at said first node, a plurality of processes, each process representing a request for a content component from one of said plurality of nodes;

means for associating a flag with each content component to be downloaded, said flag indicating whether an associated content component has already been downloaded, had not been downloaded or is currently being downloaded;

means for associating a unique sequence number with each flag;

means for incrementing said sequence number and passing said incremented sequence number to said reading process in response to one of said plurality of processes reading said flag to determine whether said associated content component has already been downloaded;

means for comparing, in response to a request by said reading process to modify said flag to indicate that said associated content component is currently being downloaded, said incremented sequence number passed to said reading process to said incremented sequence number associated with said flag;

means for accepting said modification to said flag if said incremented sequence number passed to said reading process matches said incremented sequence number associated with said flag; and

means for rejecting said modification to said flag if said incremented sequence number passed to said reading process does not match said incremented sequence number associated with said flag, whereby race conditions are avoided when more than one process attempts to download the same content component.