Method and system for data layout and replacement in distributed streaming caches on a network
View Patent ↗A system and method for segmenting, distributing and replacing streaming multimedia clips in a network system including at least one origin server connected to a plurality of streaming caches via an interactive distribution network, such as the Internet. The at least one origin server stores a plurality of streaming multimedia clips in an associated memory and segments the clips into a plurality of data segment of exponentially increasing size; the origin server then distributes the plurality of data segments to the plurality of streaming caches where each streaming cache decides whether to store or discard each segment in accordance with a predefined probability. Another aspect of the invention involves replacing stored data segments at each of the plurality of streaming caches as needed. In one embodiment, a hotness rating is computed for each streaming multimedia clip stored in an SC. Clips are replaced as needed based on their hotness rating relative to other clips. In a second embodiment, a potential function is computed for each segment stored in an SC. Segments are replaced as needed based on their potential function value relative to other stored segments.
1. In a network, a method for segmenting a streaming multimedia clip and distributing said streaming multimedia clip from an origin server to a plurality of streaming caches which comprise a distribution set in said network, the method comprising the steps of:
determining a size (L) of the multimedia clip;
segmenting the streaming multimedia clip into a first plurality of data segments of exponentially increasing size, wherein a segment size of a k-th data segment in the first plurality of data segments is computed using the size of the multimedia clip and a total number of data segments in the first plurality of data segments;
dividing a remaining undivided portion of said multimedia clip into a second plurality of data segments having a predetermined segment size; and
distributing the first and second pluralities of data segments from the origin server to said plurality of streaming caches, wherein an i-th data segment is distributed in an i-th distribution round to each of said plurality of streaming caches.
2. The method according to claim 1 , wherein the segment size of the k-th data segment in the first plurality of data segments is computed as L/2 (K−k+ 1),
where K is the total number of data segments in the first plurality of data segments, and
where k is an index defining each of the K data segments, (k=1, 2, . . . , K), in the first plurality of data segments.
3. The method according to claim 1 , wherein the size L of the multimedia clip is measured in units of time.
4. The method according to claim 1 , wherein the segmenting and dividing steps further comprise the steps of:
determining in an m-th segmenting round if a data segment of the first plurality of data segments is equal to or greater than a predetermined threshold value, said m-th data segment referred to as a threshold data segment; and
dividing the remaining undivided portion of said multimedia clip into the second plurality of data segments if the data segment of said multimedia clip is equal to or greater than the predetermined threshold value.
5. The method according to claim 4 , wherein said remaining undivided portion is divided into data segments in successive rounds having an index m+1 through N, where N is a total number of data segments of the first plurality of data segments and the second plurality of data segments.
6. The method according to claim 4 , wherein the predetermined segment size is equal to the size of the threshold data segment.
7. The method according to claim 4 , wherein the predetermined segment size is computed as:
2 (r−1) * δ
where δ is computed as L/2 (N−1) ; and
where r is a user adjustable parameter used to determine the predetermined segment size for those fixed segments which occur once the predetermined threshold has been reached.
8. The method according to claim 7 , wherein δ is on the order of 5 to 30 seconds.
9. The method according to claim 7 , wherein the values for δ, r and m are determined by an origin server in accordance with an origin server aware scheme.
10. The method according to claim 7 , wherein the values for δ, r and m are determined by inter-cache communications in an origin server transparent scheme.
11. The method of claim 1 , wherein the distributing step further comprises the step of:
at each of the plurality of streaming caches, storing an i-th data segment of the first plurality of data segments in an i-th distribution round with a probability equal to ½ (i−1) , where (i=1, . . . , k); and
at each of said plurality of streaming caches, storing an i-th data segment of the second plurality of data segments in an i-th distribution round with probability equal to a predetermined probability, where (i=k+1, . . . , N).
12. A method of distributing a segmented streaming multimedia clip among a plurality of streaming caches, comprising the steps of:
at each of said streaming caches:
receiving a plurality of data segments of the segmented streaming media clip, wherein the plurality of data segments comprises a first plurality of data segments of exponentially increasing size and a second plurality of data segments having a predetermined segment size, wherein an i-th data segment is received in an i-th distribution round, wherein a segment size of a k-th data segment in the first plurality of data segments is computed using the size of the multimedia clip and a total number of data segments in the first plurality of data segments;
storing the i-th data segment of the segmented streaming multimedia clip in the i-th distribution round with a probability proportional to ½ (i−1) , where the i-th data segment is associated with the first plurality of data segments; and
storing the i-th data segment of the segmented streaming multimedia clip in the i-th distribution round with a fixed probability where the i-th data segment is associated with the second plurality of data segments.
13. The method according to claim 12 , further comprising the step of:
storing the i-th data segment of said segmented streaming multimedia clip with probability equal to [½ (i−1) ]* e(x), where the i-th data segment is associated with the first plurality of data segments, where e(x) is a constant that is proportional to a popularity rating of the clip, where 0<e(x)<1.
14. A system for segmenting, distributing and replacing segments of streaming multimedia clips in a network, comprising:
at least one origin server storing said streaming multimedia clips;
a plurality of streaming caches in communication with said at least one origin server, said plurality of streaming caches defining a distribution set;
first processing means associated with said at least one origin server for segmenting the streaming multimedia clip into a first plurality of data segments of exponentially increasing size and a second plurality of data segments having a predetermined segment size, wherein a segment size of a k-th data segment in the first plurality of data segments is computed using the size of the multimedia clip and a total number of data segments in the first plurality of data segments, and for distributing said first and second pluralities of data segments to each of said plurality of streaming caches; and
second processing means associated with each of said plurality of streaming caches for storing data segments received from said at least one origin server in each of said plurality of streaming caches and for replacing said stored data segments from each of said plurality of streaming caches.
15. The system of claim 14 , wherein said second processing means further comprises:
means for computing a potential function for each stored data segment for replacing segments.
16. The system of claim 14 , wherein said second processing means further comprises:
means for computing a probability to determine whether to store or discard each data segment received from said at least one origin server.