METHODS AND DISTRIBUTED SYSTEMS FOR DATA LOCATION AND DELIVERY

• US 20070288638A1
• Filed: 04/02/2007
• Published: 12/13/2007
• Est. Priority Date: 04/03/2006
• Status: Abandoned Application

• Current Assignee: University of British Columbia
• Original Assignee: British Columbia Cancer Agency Branch (Province of British Columbia)
• Inventors: Liu, Xin, Wang, Jun, Vuong, Son
• Application Number:
  US11/695,592
• Publication Number:
  US 20070288638A1
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1059 Inter-group management mechanisms, e.g. splitting, merging or interconnection of groups
• CPC Class Codes: H04L 67/1072 Discovery involving ranked list compilation of candidate peers
• CPC Class Codes: H04L 67/108 characterised by resources being split in blocks or fragments
• CPC Class Codes: H04L 67/1093 Some peer nodes performing special functions

Abstract

A category overlay infrastructure for Peer-to-Peer (P2P) content search and a cost-effective large-scale on-demand media streaming are described. Based on a novel hierarchical P2P model, the category overlay infrastructure can provide good load balancing and efficient keyword search services for large-scale networks. The category overlay search services may be applied for locating video segments. The on-demand media streaming architecture can apply an efficient media segment scheduling algorithm and aggregate concurrent media streaming from multiple sources to allow users to play high-quality video or other media.

Claims

1. A method for storing a data item for download over a data communication network, the method comprising:

dividing the data item into a plurality of segments and identifying a plurality of nodes on the network that are capable of hosting the segments;

evaluating suitabilities for hosting the segments of nodes of the plurality of nodes;

selecting a subset of the plurality of nodes based upon the corresponding suitabilities; and

,

forwarding the segments of the data item to the nodes of the selected subset for hosting by the nodes of the selected subset.

2. A method according to claim 1 comprising, for at least some of the segments, forwarding the segments to each of a plurality of nodes of the selected subset for hosting by each of the plurality of nodes.

3. A method according to claim 1 wherein evaluating the suitabilities is based at least in part upon available bandwidths of the nodes.

4. A method according to claim 1 wherein evaluating the suitabilities is based at least in part upon a measure of the reliability of the nodes.

5. A method according to claim 4 wherein the measure of the reliability of the nodes is based in part on a connect-time of the node.

6. A method according to claim 5 wherein the measure of reliability is a cumulative measure of reliability based upon the value EstimatedStay given by:

EstimatedStay_i(new)=α

×

EstimatedStay_i(prev)+β

×

CurrentStay_i

where α and

β

are constants with α

+β

=1 and β

<

0.2, Estimated Stay_i(NEW) is the current value of the cumulative measure of reliability, Estimated Stay_i(Prev) is a value of the cumulative measure of reliability at the time that the node most recently came online, and CurrentStay_i is a length of time that the node has been continuously online and participating in a system on which the method is being performed.

7. A method according to claim 1 wherein evaluating the suitabilities is based at least in part upon a measure of the frequencies with which data has been previously downloaded from the nodes.

8. A method according to claim 1 wherein evaluating the suitabilities comprises ranking the nodes according to a criterion that increases with a bandwidth of the node available for uploading data and decreases with a measure of a frequency with which data has been previously downloaded from the node.

9. A method according to claim 8 wherein evaluating the suitabilities comprises computing a goodness value for nodes of the plurality of nodes, the goodness value given by:

$\begin{array}{c}{G}_i^{\mathrm{St}}=<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{St}}\times <br><br>\frac{{\mathrm{EstimatedStay}}_i}{\underset{1\le <br><br>i\le <br><br>m}{\max }<br><br>\left\{{\mathrm{EstimatedStay}}_i\right\}}+{\mathrm{\beta <br><br>}}_{\mathrm{St}}\times <br><br>\frac{{\mathrm{Bw}}_i\times <br><br>\left(1-R_i^{\mathrm{usage}}\right)}{\underset{1\le <br><br>i\le <br><br>m}{\max }<br><br>\left\{{\mathrm{Bw}}_i\times <br><br>\left(1-R_i^{\mathrm{usage}}\right)\right\}}-\\ <br><br>{\mathrm{\gamma <br><br>}}_{\mathrm{St}}\times <br><br>\frac{{\mathrm{Freq}}_i^{\mathrm{serve}}}{\underset{1\le <br><br>i\le <br><br>m}{\max }<br><br>\left\{{\mathrm{Freq}}_i^{\mathrm{serve}}\right\}}\end{array}$

or a mathematical equivalent thereof where;

G^St_i is the goodness value for a node identified by an index, i, EstimatedStay is a measure of reliability of the i^th node, m is the number of nodes in the plurality of nodes, Bw_i is the bandwidth made available by the i^th node, R_i^usage is a measure of a degree to which bandwidth made available by the i^th node has been exploited, F^reqserve_i is a measure of the number of requests for segments that have been served by the i^th node in a recent time interval and α

_St, β

_St, γ

_St are weighting factors.

10. A method according to claim 1 comprising forwarding one or more of the segments of the data item for hosting by a plurality of the nodes of the subset.

11. A method according to claim 1 wherein evaluating the suitabilities comprises receiving a list of nodes of the plurality of nodes sorted according to a measure of suitability.

12. A method according to claim 11 wherein the nodes are arranged in one or more clusters, the one or more clusters have a topology having a core node at its root, and receiving the list of nodes comprises requesting the list of nodes from the core node of a cluster and receiving the list of nodes in response to the request.

13. A method according to claim 11 comprising assigning the segments to the nodes sequentially in order of the position of the nodes in the list.

14. A method according to claim 12 wherein the nodes are organized in a plurality of the clusters, and the method comprises receiving a list from each of the core nodes, each of the lists listing a plurality of nodes associated with the cluster.

15. A method according to claim 14 wherein each of the lists comprises a list of nodes and a measure of suitability associated with each of the listed nodes.

16. A method according to claim 1 wherein the data item comprises a media file and dividing the data item into a plurality of segments comprises dividing the media into temporally-sequential segments.

17. A method according to claim 16 wherein dividing the data item into a plurality of segments comprises dividing one or more of the temporally-sequential segments into a plurality of blocks.

18. A method according to claim 1 wherein each of the nodes comprises a data processor executing peer-to-peer software that receives any forwarded segments and stores the forwarded segments in a local data store accessible to the data processor.

19. A method according to claim 1 wherein the data item comprises a video file.

20. A method for streaming a data item on a data communication network, the data item comprising a plurality of segments, the segments hosted on a plurality of nodes on the network, the method comprising:

downloading and sequentially playing segments of the data item;

wherein;

downloading the segments comprises downloading data from each of a plurality of different ones of the nodes to a receiving node; and

,

for at least one of the segments, downloading the segment comprises identifying two or more of the nodes that host the segment and requesting different portions of the segment from each of the two or more of the nodes

21. A method according to claim 20 wherein the portions of the segment comprise blocks and the method comprises requesting the blocks from the plurality of nodes according to a round-robin scheme.

22. A method according to claim 20 wherein each of the segments comprises a plurality of blocks and the method comprises requesting from each of the two or more of the nodes a number of the blocks based upon a bandwidth available from the node.

23. A method according to claim 22 comprising requesting a first plurality of the blocks from one node of the two or more of the nodes that has a highest bandwidth among the two or more of the nodes.

24. A method according to claim 23 comprising, taking each of the blocks in sequence order and, for each of the blocks, requesting the block from one of the two or more of the nodes that can complete delivery of the block at the earliest time.

25. A method according to claim 20 wherein the data item comprises a media file and the method comprises buffering a number of the blocks and commencing playback of the media file after the number of the blocks have been buffered.

26. A method according to claim 25 wherein it is desired to play the media file at a bit rate Br and identifying two or more of the nodes that host the segment comprises identifying a set of the nodes that host the segment and have an available aggregate bandwidth at least equal to Br.

27. A method according to claim 20 comprising making a determination that a node is not providing a requested portion of a segment and, in response to the determination requesting the requested portion of the segment a substitute node from which the requested segment can be obtained.

28. A method according to claim 20 wherein the data item comprises a media file, the method is performed at the receiving node at which the media file is to be played, and the method comprises, at the receiving node, generating a schedule for downloading blocks of the data item and sending the schedule to the two or more of the nodes.

29. A method according to claim 20 wherein identifying two or more of the nodes that host the segment comprises, selecting an agent node based upon a sequence position of the segment in the data item and querying the selected agent node to identify nodes that host the segment.

30. A method according to claim 20 comprising, after requesting one of the portions from one of the two or more of the nodes:

determining that the one of the two or more of the nodes has not provided the requested portion;

identifying another node that hosts the at least one of the segments; and

,

requesting the requested portion from the another node.

31. A method according to claim 20 comprising, upon receiving data from the data item, forwarding the data to another device by a data communication channel including a wireless link.

32. A method according to claim 31 comprising initiating downloading the data item in response to a request from the another device.

33. A method for locating a desired data item in a distributed storage system comprising a plurality of nodes interconnected by a data communication network, the method comprising:

determining a category for the desired data item from among a plurality of categories;

selecting an agent node based upon the category for the desired data item;

querying the selected agent node for the desired data item using at least one keyword associated with the desired data item; and

,

at a requesting node, receiving from the selected agent node an identification of one or more nodes of the system that host the desired data item.

34. A method according to claim 33 wherein the nodes of the system are arranged in one or more clusters, there is an agent node for the category in each of the clusters, and the method comprises querying the agent nodes of a plurality of the clusters for the desired data item.

35. A method according to claim 34 wherein the selected agent node and the requesting node belong to the same one of the clusters and querying the agent nodes of other ones of the plurality of clusters is performed by the selected agent node.

36. A method according to claim 34 comprising, at the receiving node, waiting for a predetermined time period to receive responses to the queries from the selected agent node and from the agent nodes of other clusters and, after the predetermined time period, selecting one or more nodes identified by the responses to deliver the desired data item.

37. A method according to claim 33 comprising maintaining a category table at the requesting node, the category table associating each of the plurality of categories with a corresponding agent node.

38. A method according to claim 37 wherein the category table comprises a timestamp indicating when each of the plurality of categories became associated with the corresponding agent node.

39. A method according to claim 38 comprising, at one node, receiving a category table from another node and updating the category table at the one node based upon the received category table.

40. A method according to claim 33 wherein the desired data item comprises a media file and the categories comprise categories for a plurality of different media genres.

41. A system for storage and delivery of data items, the system comprising:

a plurality of nodes, each of the plurality of nodes comprising a data processor, a data store accessible to the data processor, and stored computer instructions executable by the data processor; and

,

a data communication network interconnecting the plurality of nodes;

wherein, for at least some of the nodes;

the computer instructions, when executed, control the data processor to retrieve data from a selected data item by downloading a plurality of segments of the data item and sequentially playing the segments of the data item;

wherein;

at least one of the segments comprises a plurality of blocks and downloading the segment comprises identifying two or more other nodes that host the segment and requesting different blocks of the segment from each of the two or more of the nodes.

42. A system according to claim 41 wherein the data items comprise media files and the computer instructions comprise instructions that cause a playback system to commence playing the data item at the node before all segments of the data item have been received.

43. A system according to claim 41 wherein the computer instructions control the data processor to determine a bandwidth available from each of the other nodes that host the segment and create a schedule for retrieving the blocks of the segment from two or more of the other nodes that host the segment based at least in part upon the available bandwidths for the other nodes that host the segment.

44. A system according to claim 43 wherein the computer instructions control the data processor to take each of the blocks in sequence order and, for each of the blocks, request the block from one of the other nodes that host the segment and can complete delivery of the block at the earliest time.

45. A system according to claim 43 wherein the computer instructions control the data processor to cache downloaded segments in the data store and to deliver those cached segments to other nodes in response to requests from the other nodes for the cached segments.

46. A system according to claim 43 wherein:

the nodes are arranged in a plurality of clusters,

the data items are each associated with a category,

within each cluster, each category is associated with one agent node that comprises a record of the location in the cluster of the data items associated with the category, and,

each node comprises a record of a plurality of agent nodes for the cluster and their associated categories.

47. A system according to claim 43 wherein at least some of the nodes comprise set top boxes in a cable television system.

49. A system according to claim 47 wherein the at least some nodes comprise means for scheduling delivery of the blocks from the other nodes based upon available bandwidths of the other nodes.

48. A system for storage and streaming delivery of data items, the system comprising:

a plurality of nodes interconnected by a data communication network, at least some of the nodes comprising;

a data store;

means for identifying two or more other nodes storing a segment of a desired data item, the segment comprising a plurality of blocks;

means for requesting a block of the segment from each of the two or more of the nodes;

means for receiving the blocks from the other nodes; and

,

means for playing the blocks in sequence.

50. A system according to claim 48 wherein at least some of the nodes comprise set top boxes in a cable television system.