Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-02-27
2004-04-13
Lane, Jack A. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S159000, C709S226000
Reexamination Certificate
active
06721850
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to cache memories and methods for increasing the efficiency of cache memories, and more particularly, to a method of cache replacement for streaming media.
2. Description of the Related Art
Computer networks such as the Internet are increasingly being used to transmit multimedia data (e.g., audio and video data). The enormous increase in traffic from transmitting such data has severely strained the Internet infrastructure. This network congestion problem is only expected to grow in the future as new multimedia data and new media rich Internet services become widespread. Presently, data caching is a preferred solution to address the network congestion problem. Data caching attempts to move web content closer to the end-user and thus, minimize network and web server load, thereby improving the performance perceived by the end-user.
Data caching has been extensively implemented on the Internet to reduce network load (i.e., bandwith consumption), server load, and high start-up latency. Existing data caching systems typically cache entire web documents, such as HTML documents and images, for example, and attempt to keep the documents and images consistent with the origin server. Current data caching systems are restrictive in that they only support static web objects, such as HTML documents or images. Static web objects are typically small and as such are always cached in their entirety. Current caching systems do not adequately support streaming multimedia data, such as video and audio streaming media objects. Streaming multimedia data, such as video objects, for example, are usually too large to be cached in their entirety. With the recent proliferation of audio/video content on web sites, it is imperative that data caching systems provide efficient support for streaming media. However, the present data caching systems treat multimedia (i.e., audio/video) clips as regular web objects thereby storing them in their entirety. Treating multimedia clips as regular web objects will prove to be adequate only in the short term as the size of multimedia clips on the web currently is relatively small. In the near future, however, faster Internet access technologies such as XDSL, DSL, VDSL and cable-modems will further enable the transmission of high-bandwidth, high resolution media clips that are much longer in duration than present day media clips. It will no longer be efficient and cost effective to cache such large media objects in their entirety.
The size of present day streaming media objects is typically at least an order of magnitude or two larger than that of a static web object, and therefore, do not lend themselves to be cached in their entirety. For example, a single, two hour long MPEG-2 movie requires about 4.5 GB of hard disk space. Given a fixed investment on buffer space, it is apparent that only a few media objects can be stored at a cache, and therefore, the hit ratio and the efficiency of the cache is limited. Given that caches have finite disk space, it is not feasible to statically store more than a few complete SM objects. If there are several simultaneous requests for different SM objects, the cache typically replaces one SM object with another, thus resulting in performance degradation.
Accordingly, a need exists for an improved cache block replacement method to provide improved cache performance. It is desirable to provide such improved cache block replacement method that is simple to implement and that takes advantage of the different service times required by multiple streams.
SUMMARY OF THE INVENTION
The present invention provides a method of cache replacement for multimedia streams. The cache replacement method of the present invention approximates full-knowledge of all future accesses by considering that future accesses for multimedia objects may be predicted with a high probability. This is based on the fact that in the majority of instances video accesses by clients are sequential, unlike data accesses in classical web caching.
In accordance with the method of the present invention, the cache replacement method operates in successive rounds. In each round, the method serves the streams in accordance with a service list order. Whenever it is determined that cache space must be made available to service a particular stream, an unlocked block list and a victim list are consulted to determine which cached block to release. The cache replacement method generally includes the steps of: in each round, receiving at least one client request for a media clip; constructing at least one service interval from the received client requests; constructing a service list from service intervals constructed in the present round and in previous rounds; and servicing client requests in an order
REFERENCES:
patent: 5293609 (1994-03-01), Shih et al.
patent: 5787472 (1998-07-01), Dan et al.
patent: 5845320 (1998-12-01), Pawlowski
patent: 5897655 (1999-04-01), Mallick
patent: 5933849 (1999-08-01), Srbljic et al.
patent: 5991306 (1999-11-01), Burns et al.
patent: 6128623 (2000-10-01), Mattis et al.
patent: 6330605 (2001-12-01), Christensen et al.
Hofmann Markus
Mudigonda Jayram
Paul Sanjoy
Lane Jack A.
Lucent Technologies - Inc.
LandOfFree
Method of cache replacement for streaming media does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of cache replacement for streaming media, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of cache replacement for streaming media will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3221790