Method of cache replacement for streaming media

• US 6,721,850 B2
• Filed: 02/27/2001
• Issued: 04/13/2004
• Est. Priority Date: 02/27/2001
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Paul, Sanjoy, Hofmann, Markus, Mudigonda, Jayram
• Primary Examiner(s): Lane, Jack A.
• Application Number:
  US09/794,379
• Publication Number:
  US 20020120818A1
• Time in Patent Office: 1,141 Days
• Field of Search: 711/133, 711/159, 709/226
• US Class Current: 711/133
• CPC Class Codes: H04N 21/2221 being a cable television head-end CATV in broadcast systems H04H20/78
• CPC Class Codes: H04N 21/23106 involving caching operations prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568
• CPC Class Codes: H04N 21/2393 involving handling client requests scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

A system and method of cache replacement for streaming multimedia is provided. A network system includes a content provider connected to local service providers via an interactive distribution network, such as the Internet. The local service providers facilitate delivery of the content from the content provider to multiple subscribers. For each of the data blocks which make up the multimedia stream requested by a subscriber, the local service provider receiving the request determines whether the request can be serviced locally or whether the requested data blocks must be retrieved from the content provider. In the case where the portion of the requested stream must be retrieved from the content provider, the local service provider attempts to cache the requested blocks in its local cache in addition to streaming the data blocks to the requesting subscriber. The local service provider stores two lists to determine which cached block is to be replaced from the local cache memory in the case where the attempt to cache the requested blocks fail because the local cache memory is full. A first list defines those cached blocks for which there are no foreseeable future subscriber requests. The second list defines those cached blocks whose access time from existing suscribers is furthest in the future.

Claims

1. A cache replacement method for a cache configured as a plurality of cache blocks, wherein said cache replacement method operates in successive rounds, the method comprising the steps of:

in each round;

constructing service intervals from client requests for a media clip, said client requests being received in a present round and/or previous rounds;

constructing a service list from said constructed service intervals; and

servicing said client requests for said media clip in an order defined by said service list.

2. The cache replacement method of claim 1, wherein the servicing step further comprises the step of returning an ith block of said media clip in an ith round, where 1<

i<

L, where L is the number of blocks of the media clip.

3. The cache replacement method of claim 1, wherein the servicing step further comprises the steps of:

determining whether a requested block of said media clip is stored at a proxy server;

retrieving said block of said media clip from said proxy server and delivering said retrieved block to a client in response to said client request if it is determined that said block is stored at said proxy server; and

retrieving said requested block of said media clip from an origin server and delivering said retrieved block to a client in response to said client request if it is determined that said block is not stored at said proxy server.

4. The cache replacement method of claim 3, wherein the servicing step further comprises the steps of:

storing said retrieved block of said media clip in a cache associated with said proxy server if it is determined that there is available memory in said cache to store said retrieved block; and

replacing a block stored in said proxy server cache memory with said retrieved block if it is determined that there is not enough memory in said cache to store said retrieved block.

5. The cache replacement method of claim 4, wherein the replacing step further comprises the steps of:

selecting a block from a first list to be replaced from said cache memory if it is determined that said first list contains at least one entry; and

selecting a block from a second list to be replaced from said cache memory if it is determined that said second list does not contain at least one entry and that said second list contains at least one entry.

6. The cache replacement method of claim 1, wherein the step of constructing a service list further comprises the steps of:

sorting said constructed service intervals according to a service interval length, wherein each service interval is comprised of a service interval leader and a service interval follower;

selecting the service interval leader from each entry in the sorted list to be included in said service list; and

selecting the service interval follower from each entry in the sorted list to be included in said service list.

7. The cache replacement method of claim 1, further comprising the step of determining whether at least one block cached in a proxy server cache can be selected for inclusion in an unlocked blocked list.

8. The cache replacement method of claim 7, wherein the determining step further comprises the step of including said at least one cached block in said unlocked block list if it is determined that there are no client requests for said cached block in a present or future round.

9. The cache replacement method of claim 1, further comprising the step of determining whether at least one block cached in a proxy server cache can be selected for inclusion in a victim list.

10. The cache replacement method of claim 9, wherein the determining step further comprises the step of including said at least one cached block in said victim list if said cached block is a block belonging to a particular service interval and said at least one cached block is the block in said particular service interval that will be requested by at least one client furthest in the future.

11. The cache replacement method of claim 10, wherein said particular service interval is the largest service interval.

12. A cache replacement system for a cache configured as a plurality of cache blocks, wherein said cache replacement method operates in successive rounds, the system comprising:

means for constructing service intervals from client requests for a media clip, said client requests being received in a present round and/or previous rounds;

means for constructing a service list from said constructed service intervals; and

means for servicing said client requests for said media clip in an order defined by said service list.