US6721850B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of cache replacement for streaming media
Assignee: Alcatel Lucent SAS
•
Filing: 2001-02-27
•
Granted: 2004-04-13
•
Expires: 2021-02-27
Abstract
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.
Inventors
- 👤 Markus Hofmann
- 👤 Jayram Mudigonda
- 👤 Sanjoy Paul
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 14:01
CPC Classifications
H; H04; H04N; H04N21/00; H04N21/20; H04N21/21; H04N21/222; H04N21/2221; H04N21/23; H04N21/231; H04N21/23106; H04N21/239; H04N21/2393; H04N7/00; H04N7/16; H04N7/173; H04N7/17309; H04N7/17336
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
80 words
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.
Claim 2
Dependent Claim
80 words
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.
Claim 3
Dependent Claim
42 words
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.
Claim 4
Dependent Claim
111 words
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.
Claim 5
Dependent Claim
83 words
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.
Claim 6
Dependent Claim
84 words
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.
Claim 7
Dependent Claim
87 words
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.
Claim 8
Dependent Claim
35 words
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.
Claim 9
Dependent Claim
49 words
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.
Claim 10
Dependent Claim
34 words
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.
Claim 11
Dependent Claim
69 words
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.
Claim 12
Dependent Claim
18 words
The cache replacement method of claim 10 , wherein said particular service interval is the largest service interval.
Claim 13
Dependent Claim
80 words
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.
Claim 14
Dependent Claim
80 words
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.
References Cited (Backward Citations)
US5293609A
Cited
US5787472A
Cited
US5845320A
Cited
US5991306A
Cited
US5897655A
Cited
US5933849A
Cited
US6128623A
Cited
US6330605B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-04-13 | 2007-10-13 | 2008-04-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-04-13 | 2011-10-13 | 2012-04-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-04-13 | 2015-10-13 | 2016-04-13 | $7700.00 | Window Closed / Lapsed |