Method and System for Caching Streaming Multimedia on the Internet

Abstract

An apparatus and method to enhance existing caches in a network to better support streaming media storage and distribution. Helper machines are used inside the network to implement several methods which support streaming media including segmentation of streaming media objects into smaller units, cooperation of Helper machines, and novel placement and replacement policies for segments of media objects.

1 . A method for servicing a client request for a streaming media (SM) object in a network having a content server which hosts SM objects for distribution over the network through a plurality of HSs to a plurality of clients, the SM object being comprised of a plurality of successive time-ordered chunks, the method comprising: 
 receiving a request for at least a portion of an SM object at a local HS, the request including a playback starting time;    determining whether a chunk having a starting time equal to the requested playback starting time resides on a disk associated with the local HS;    delivering to one of the plurality of clients the one or more chunks having an associated starting time equal to the requested playback starting time from the local HS and updating the playback starting time;    identifying a server in the network storing at least M chunks which have a starting time equal to the updated playback starting time and which satisfies a minimum cost criterion, if it is determined that the updated playback starting time is not equal to an end-time of the SM object; and    receiving the at least M chunks from the identified server at the local HS until it is determined that a next chunk to be retrieved is stored at the local HS.    
   
   
       2 . A method for servicing a client request for a streaming media (SM) object in a network having a content server which hosts SM objects for distribution over the network through a plurality of HSs to a plurality of clients, the SM object being comprised of a plurality of successive time-ordered chunks, the method comprising: 
 receiving a request for at least a portion of an SM object at a local HS, the request including a playback starting time;    determining whether a chunk having a starting time equal to the requested playback starting time resides on a disk associated with the local HS;    if the chunk having a starting time equal to the requested playback starting time resides on a disk associated with the local HS, delivering at least that chunk to the one of the plurality of clients; and    if the chunk having a starting time equal to the requested playback starting time does not reside on a disk associated with the local HS, identifying a server in the network storing at least that chunk and receiving at least that chunk from the identified server at the local HS until it is determined that a next chunk to be retrieved is stored at the local HS.    
   
   
       3 . The method of  claim 2 , further comprising: 
 storing at least a portion of the SM object at the local HS.    
   
   
       4 . The method of  claim 3 , wherein a chunk is further comprised of an integer multiple number of HS storage disk blocks, wherein storing at least a portion of the SM object at the local HS comprises: 
 receiving the SM object;    determining whether sufficient disk space is available on the local HS to store the received SM object;    storing the received SM object at the local HS, if it is determined that there is sufficient disk space; and    performing the following steps, if it is determined that there is insufficient disk space available to store the received SM object: 
 identifying at least one SM object from among a plurality of SM objects hosted by the local HS which is not in use and has an access time which is least recent, wherein the access time corresponds to a time when the SM object was last requested; and  
 replacing chunks of the identified at least one SM object corresponding to the received SM object to store at least a portion of the received SM object.  
   
   
   
       5 . The method of  claim 4 , wherein the step of replacing chunks further comprises the step of replacing the chunks having the largest associated time-stamp value of the at least one identified SM object.  
   
   
       6 . A method as recited in  claim 5 , wherein the step of replacing the chunks having the largest time-stamp value further comprises the step of replacing the chunks having the largest time-stamp value on a disk block by disk block basis starting from the end of the chunk.  
   
   
       7 . The method of  claim 3 , wherein a chunk is further comprised of an integer multiple number of disk blocks, wherein storing at least a portion of the SM object at the local HS comprises: 
 receiving the SM object;    determining whether there is disk space available on the local HS;    storing the SM object at the local HS, if it is determined that there is sufficient disk space available; and    performing the following steps, if it is determined that there is insufficient disk space available: 
 composing a set of SM objects from among a plurality of SM objects stored on the disk space whose access time is determined to be least recent, where the access time corresponds to a time when the SM object was last requested; and  
 replacing chunks of the SM objects belonging to the composed set with chunks of the received SM object.  
   
   
   
       8 . The method of  claim 7 , wherein the replacing step further comprises the step of replacing a chunk having an associated highest time-stamp value from each of the SM objects belonging to the composed set in a round-robin basis.  
   
   
       9 . The method of  claim 7 , wherein the composed set is formed by including only SM objects having a helper hotness rating below a predefined threshold.  
   
   
       10 . The method of  claim 3 , wherein a chunk is further comprised of an integer multiple number of disk blocks, wherein storing at least a portion of the SM object at the local HS comprises: 
 receiving the SM object at the local HS in the network; and    randomly determining a fraction and storing the fraction of the SM object at the local HS in the network.    
   
   
       11 . The method of  claim 10 , wherein the step of randomly determining the fraction comprises the steps of: 
 estimating at the local HS, the number of HSs in the network, K;    calculating a value, P, that is inversely proportional to the value K;    generating a random value, R, for a received chunk of the received SM object;    comparing the generated random value, R, with the calculated value P;    caching the received chunk, if it is determined that the generated random value, R, is less than the calculated value P; and    discarding the received chunk, if it is determined that the generated random value, R, is greater than the calculated value P.    
   
   
       12 . The method of  claim 11 , wherein the step of generating the random value R is performed by utilizing the IP address of the local HS as a seed.  
   
   
       13 . The method of  claim 3 , wherein a chunk is further comprised of an integer multiple number of disk blocks, wherein storing at least a portion of the SM object at the local HS comprises: 
 requesting the SM object at the local HS in the network;    receiving the SM object the local HS in the network; and    randomly determining a fraction and storing the fraction of the SM object at the local HS in the network.    
   
   
       14 . The method of  claim 13 , wherein the step of randomly determining the fraction comprises the steps of: 
 estimating at the local HS, the number of HSs in the network, K;    calculating a value, P, that is inversely proportional to the value K;    generating a random value, r, for a received chunk of the received SM object;    comparing the generated random value, R, with the calculated value P;    caching the received chunk, if it is determined that the generated random value, R, is less than the calculated value P; and    discarding the received chunk, if it is determined that the generated random value, R, is greater than the calculated value P.    
   
   
       15 . The method of  claim 14 , wherein the step of generating the random value R is performed by utilizing an arrival time as the seed of the SM object at the local HS.  
   
   
       16 . The method of  claim 3 , wherein a chunk is further comprised of an integer multiple number of disk blocks, wherein storing at least a portion of the SM object at the local HS comprises: 
 receiving the SM object at the local HS;    determining whether there is disk space available on the local HS to store the SM object;    storing the SM object at local HS, if it is determined that there is sufficient disk space available; and    performing the following steps, if it is determined at the determining step that there is insufficient disk space available: 
 composing a set of streaming media objects from among a plurality of streaming media objects stored on the disk space, whose access time is determined to be above a predetermined threshold, wherein the access time is a time when the SM object was last retrieved;  
 assigning a unique integer value to each chunk of the composed set of SM objects based at least one of a name of the SM object, a time-stamp of the chunk, and a last access time of the chunk;  
 generating a random value, R, having a range between one and the largest unique integer value assigned; and  
 replacing a stored chunk having the assigned integer value which corresponds to the generated random value with a chunk of the received SM object.  
   
   
   
       17 . A method for determining an optimal sequence of cache accesses to service a request for a streaming media (SM) object in a network including a content server which hosts SM objects for distribution over the network through a plurality of helper servers (HSs) to a plurality of clients, the SM objects being comprised of a plurality of successive time-ordered chunks, the method comprising the steps of: 
 (i) receiving a request at a local HS for an SM object, the request including a requested playback starting time;    (ii) determining whether a chunk of an SM object having a starting time equal to the requested playback starting time is stored at the local HS;    (iii) retrieving the one or more chunks of the SM object when step (ii) is satisfied and updating the requested playback starting time;    (iv) identifying a minimum cost server in the network which stores at least M chunks of the SM object having a starting time equal to the updated playback starting time;    (v) retrieving the at least M chunks on a chunk by chunk basis from the identified minimum cost server and the local HS;    (vi) retrieving the next chunk from the local HS and updating the requested playback starting time; and    (vii) repeating step (ii) through step (vi) until the entire streaming media object has been retrieved.    
   
   
       18 . The method of  claim 17 , wherein the minimum cost server comprises one of the content server or another one of the HSs.  
   
   
       19 . The method of  claim 17 , wherein at step (v), a chunk is always retrieved from the local HS if it is available.  
   
   
       20 . The method of  claim 19 , further comprising the step of returning chunks of the requested SM object to one of the plurality of clients as they are retrieved at the local HS.