Method and system for caching streaming multimedia on the internet

• US 9,167,015 B2
• Filed: 06/27/2014
• Issued: 10/20/2015
• Est. Priority Date: 03/29/2000
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Sound View Innovations, LLC (Sound View Innovation Holdings, LLC)
• Inventors: Guo, Katherine H., Hofmann, Markus A., Paul, Sanjoy, Ng, Tze Sing Eugene, Zhang, Hui
• Primary Examiner(s): DENNISON, JERRY B
• Application Number:
  US14/317,302
• Publication Number:
  US 20140379870A1
• Time in Patent Office: 480 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 65/403 Arrangements for multi-party communication, e.g. for conferences data switching systems for conference H04L12/18; arrangements for connecting several subscribers to a common circuit, i.e. affording conference facilities H04M3/56; television conferencing systems H04N7/15
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

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.

Claims

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 helper servers (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 or not the request can be satisfied by the local HS, the request being satisfied when a chunk having a starting time equal to the requested playback starting time resides on a disk associated with the local HS;

determining whether there are any additional chunks on the local HS that follow the chunk that satisfies the request in consecutive time order;

when it is determined that the request can be initially satisfied by 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 when the end of the SM object has not been reached after delivery;

when it is determined that the request cannot be satisfied or continue to be satisfied by the local HS, identifying a server in the network that is not the content server storing at least a predetermined M chunks having a starting time equal to one of the requested playback starting time, when the request cannot be initially satisfied by the local HS, or the updated playback starting time, when the request cannot continue to be satisfied by the local HS, according to a minimum normalized cost function;

delivering to the one of the plurality of clients the identified M chunks and updating the playback starting time when the end of the SM object has not been reached;

when it is determined that the request cannot be satisfied or continue to be satisfied by the local HS or remote HS in the network that is not the content server, delivering to one of the plurality of clients the one or more chunks from the content server the one or more chunks having an associated starting time equal to the requested playback starting time or the updated playback starting time until it is determined that the local HS or remote HS can satisfy the request or until the end of the SM object has been reached, whichever comes first, and updating the playback starting time when the end of the SM object has not been reached; and

when requests are not satisfied by the local HS, receiving the 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. The method of claim 1, 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.

3. The method of claim 2, 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.

4. A method as recited in claim 3, 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.

5. 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.

6. The method of claim 5, 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.

7. The method of claim 5, wherein the composed set is formed by including only SM objects having a helper hotness rating below a predefined threshold.

8. 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.

9. The method of claim 8, 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.

10. The method of claim 9, wherein the step of generating the random value R is performed by utilizing the IP address of the local HS as a seed.

11. 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.

12. The method of claim 11, 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.

13. The method of claim 12, 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.

14. 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.