USOO73983.12B1
`
`(12) United States Patent
`Guo et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,398,312 B1
`Jul. 8, 2008
`
`(54) METHOD AND SYSTEM FOR CACHING
`STREAMING MULTIMEDIA ON THE
`INTERNET
`
`(75) Inventors: Katherine H. Guo, Eatontown, NJ (US);
`Markus A. Hofmann, Tinton Falls, NJ
`• Casa
`(US), Sanjoy Paul Marlboro, NJ (US);
`Tze sing Eugene Ng Pittsburgh, PA
`(US); Hui Zhang, Pittsburgh, PA (US)
`
`(73) Assignee: Lucent Technologies Inc., Murray Hill,
`NJ (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/538,351
`(22) Filed:
`Mar. 29, 2000
`
`(51) Int. Cl.
`(2006.01)
`G06F 5/73
`(2006.01)
`G06F 5/16
`(2006.01)
`G06F 12/00
`(2006.01)
`G06F 3/00
`(2006.01)
`G06F 3/28
`(52) U.S. Cl. ....................... 709/226; 709/225; 709/231;
`711/118
`(58) Field of Classification Search .................
`oooo...
`709/223, 217 219, 226; 375/354358; 725/86-153:
`711/118, 161, 154
`See application file for complete search history.
`References Cited
`U.S. PATENT DOCUMENTS
`5,550,577 A * 8/1996 Verbiest et al. ............... 725/92
`
`(56)
`
`5,586.264 A * 12/1996 Belknap et al. ............. 725,115
`5,805,821. A * 9/1998 Saxena et al. .....
`... 709,231
`5,940,391 A * 8/1999 Malkin et al. .....
`... 370,390
`6,029, 195 A * 2/2000 Herz .........
`... T25,116
`6,061,720 A * 5/2000 Kamel et al. ................ TO9,219
`6,199,076 B1* 3/2001 Logan et al. ...
`... T15,501.1
`6,209.787 B1 * 4, 2001 I
`4. W-1
`ida ............................ 235,381
`6,317,795 B1 * 1 1/2001 Malkin et al. ..
`... 709/246
`6,331,859 B1* 12/2001 Crinon ...
`... 345,619
`6,377.972 B1 * 4/2002 Guo et al. ................... TO9,201
`6,381,314 B1 * 4/2002 Wallinski ....
`... 379,101.01
`6,438,579 B1* 8/2002 Hosken ...................... TO9,203
`6,484.199 B2 * 1 1/2002 Eyal ........................... 709,223
`6,647.417 B1 * 1 1/2003 Hunter et al. ............... 709,225
`6,708,213 B1* 3/2004 Bommaiah et al. .......... 709/226
`6,728,760 B1 * 4/2004 Fairchild et al. ......
`... 709,217
`6,978,348 B2 * 12/2005 Belknap et al. ............. T11 118
`OTHER PUBLICATIONS
`U.S. Appl. No. 60/177,786, filed Jan. 2000, Eyal, Aviv.*
`MP3.com. (Top 40) www.mp3.com, Aug. 6, 2003, MP3.com.*
`Yahoo! Inc., (Top 100) http://launch.yahoo.com/musicvideos/lists/
`top.asp, Aug. 6, 2003, Yahoo! Inc.*
`* cited by examiner
`Primary Examiner Nathan J. Flynn
`Assistant Examiner—David E. England
`
`ABSTRACT
`(57)
`An apparatus and method to enhance existing caches in a
`network to better Support streaming media storage and distri
`bution. Helper machines are used inside the network to imple
`ment several methods which Support streaming media includ
`ing segmentation of streaming media objects into Smaller
`units, cooperation of Helper machines, and novel placement
`and replacement policies for segments of media objects.
`
`8 Claims, 5 Drawing Sheets
`
`402
`
`CENTRQUESSANs
`OBJECT FROM THE LOCAL
`HELPER SERVER
`
`
`
`
`
`
`
`404
`
`CAN
`REQUEST
`BESERICEDAT
`LOCALHELPER
`SERVER
`
`YES
`
`FIND THELOWEST COST
`CACHENTHENETWORK
`
`RETRIEWEANUMBER OF
`CHUNKSFROMLOWEST
`COSTCACHEUPUNTIL
`OCALHELPERSERVER
`CAN SERVICE THENEXT
`CHUNK
`
`
`
`END
`OFSMOBJECT
`REACHE
`
`420
`
`UPDATE THE PLAYBACK
`REEST TIMENTY
`THENEXTCHUNKTOBE
`REREVED FROM THESM
`BCT
`
`H
`
`f 406
`
`RETREWE.ONE ORMORE
`CHUNKS OFREQUESTED
`SM OBJECT FROMLOCAL
`HELPERSERFER
`
`412
`
`UPDATE THE PLAYBACK
`REQUEST TIMEDENTIFY
`THENEXTCHUMKTB
`RETRIEWE FROM THES
`OBJEC
`
`408
`
`EN
`NO/OFSMOBJECT
`REACHED
`
`41
`
`YS
`
`TRMINATEPROCESS
`
`400
`
`-1-
`
`Amazon v. Audio Pod
`US Patent 9,954,922
`Amazon EX-1036
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 8, 2008
`Jul. 8, 2008
`
`Sheet 1 of 5
`Sheet 1 of 5
`
`US 7,398,312 B1
`US 7,398,312 B1
`
`
`
`
`
`FIG. 1
`FIG. 1
`
`-2-
`
`-2-
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 8, 2008
`Jul. 8, 2008
`
`Sheet 2 of 5
`Sheet 2 of 5
`
`US 7,398,312 B1
`US 7,398,312 B1
`
`
`
`
`
`
`
`INSITO
`9E~
`
`
`
`
`=pEi=
`Co)RSS][|e—
`LNAITO
`
`Or
`
`
`
`
`
` aYsSAYsSLNALNOO
`
`¢Olas
`
`-3-
`
`
`
`

`

`U.S. Patent
`
`Jul. 8, 2008
`
`Sheet 3 of 5
`
`US 7,398,312 B1
`
`300
`
`CACHE SERVER STORAGE
`FG. 3a
`(PRIOR ART)
`
`1 DSK
`BLOCK
`
`
`
`BLOCK
`
`CACHE SERVER STORAGE
`FIG. 3b
`
`-4-
`
`

`

`U.S. Patent
`
`Jul. 8, 2008
`
`Sheet 4 of 5
`
`US 7,398,312 B1
`
`402
`
`CLIENT REQUESTS ANSM
`OBJECT FROM THE LOCAL
`HELPER SERVER
`
`CAN
`REQUEST
`BESERVICEDAT
`LOCALHELPER
`SERVER
`
`FIND THE LOWEST COST
`CACHE IN THE NETWORK
`
`
`
`RETRIEVE ANUMBER OF
`CHUNKS FROM LOWEST
`COST CACHE UP UNTL
`LOCALHELPER SERVER
`CAN SERVICE THE NEXT
`CHUNK
`
`END
`OF SM OBJECT
`REACHED
`
`420
`
`UPDATE THE PLAYBACK
`REQUEST TIME TOIDENTIFY
`THE NEXT CHUNK TO BE
`RETRIEVED FROM THE SM
`OBJECT
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`RETRIEVE ONE ORMORE
`CHUNKS OF REQUESTED
`SM OBJECT FROM LOCAL
`HELPER SERVER
`
`UPDATE THE PLAYBACK
`REQUEST TIME TO DENTIFY
`THENEXT CHUNK TO BE
`RETREVED FROM THE SM
`OBJECT
`
`
`
`408
`
`END
`OF SM OBJECT
`REACHED
`
`
`
`YES
`
`TERMINATE PROCESS
`
`
`
`400
`o
`
`FG. 4
`
`-5-
`
`

`

`U.S. Patent
`
`Jul. 8, 2008
`
`Sheet 5 of 5
`
`US 7,398,312 B1
`
`CHUNK CHUNK CHUNK CHUNK CHUNK CHUNK CHUNK CHUNK CHUNK CHUNK
`1
`2
`3
`4.
`5
`6
`7
`8
`9
`10
`
`t2
`t1
`TIME-STAMP
`
`to
`
`ta
`
`t5
`
`to
`
`t7
`
`to
`
`t
`9
`
`t10
`
`STREAMING MEDIA (SM) OBJECT
`FIG. 5a
`
`
`
`LOCAL SERVER CACHE
`22
`
`REMOTE CACHE
`23
`
`REMOTE CACHE CONTENT SERVER
`14
`
`2,3,4,7,8,9
`
`1,2,5,6
`
`1,3,5,6,7,8,9,10
`
`1,2,3,4,5,6,7,8,9,10
`
`CACHE STORAGE TABLE
`
`FIG. 5b
`
`-6-
`
`

`

`US 7,398,312 B1
`
`1.
`METHOD AND SYSTEM FOR CACHING
`STREAMING MULTIMEDIA ON THE
`INTERNET
`
`BACKGROUND OF THE INVENTION
`
`2
`Web caching has been extensively implemented on the
`Internet to reduce networkload (i.e., bandwith consumption),
`server load, and high start-up latency. The utilization of Web
`caching on the Internet has been extensively studied. For a
`more detailed discussion of Web caching, see T. Bernesrs
`Lee, A. Lutonen, and H. F. Nielsen Meyr, Cern httpd: http://
`www.w3.org/Daemon/Status.html, 1996; and C. M. Bow
`man, et al. Harvest: 'A scalable, customizable discovery and
`access system’ Technical Report CU-CS-732-94, Dept. of
`Computer Science, University of Colorado, Boulder, USA,
`1994 both references are incorporated by reference herein.
`See also, D. Wessels, “ICP and the squid cache'. National
`Laboratory for Applied Network Research, 1999, http://ir
`cache.nlanr.net/Squid; this reference is also incorporated by
`reference herein. However, current caching systems, like
`those described above, are restricted to 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 methods, therefore, do not
`adequately support streaming multimedia data (i.e., web
`objects) Such as video and audio SM objects. Streaming mul
`timedia data like Video objects, for example, are usually too
`large to be cached in their entirety. A single, two hour long
`MPEG movie, for example, requires about 1.4 Gbytes of disk
`space. Given a fixed investment in disk space, only a few
`streams could be stored at a cache, thus, decreasing the hit
`probability and the efficiency of the caching system. A natural
`solution would be to break video objects into smaller pieces
`for the purpose of caching. This solution is deficient, how
`ever, in that existing caching systems will treat different
`chunks from the same video object independently, while it
`might be desirable to consider the logical relationship among
`the various pieces.
`SM objects can be generally differentiated from static web
`objects in that SM objects consist of multimedia data whose
`transmission has temporal characteristics such that the trans
`mission rate is explicitly regulated or else the data becomes
`useless. In addition, the size of SM 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. 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 differ
`ent SM objects, it is easy to show that the cache will be busy
`replacing one SM object with another resulting in significant
`performance degradation.
`Based on the foregoing, there is a need for a system and
`method for enhancing current caching systems to Support
`streaming multimedia over a public network system, Such as
`the Internet.
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`1. Field of the Invention
`The present invention relates to network systems, and par
`ticularly to public network systems, such as the Internet.
`More particularly, the invention relates to methods which
`improve the caching of streaming multimedia data (e.g.,
`audio and video data) from a content provider over a network
`to a client’s computer.
`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). In the network-based context, one simple model of
`producing the information involves the client requesting the
`downloading of the multimedia data. Once downloaded, the
`client may then consume, or present, the information. This
`model is relatively easy to implement, however, it is non
`optimal in that the client is required to wait for the download
`ing to complete before the presentation can begin. This delay
`can be considerable.
`A more Sophisticated model of producing information
`involves a content server at one network site streaming the
`multimedia information over the network to a client at
`another site. The client begins to present the information as it
`arrives (i.e., just-in-time rendering), rather than waiting for
`the entire data set to arrive before beginning the presentation.
`At the client computer, the received data is buffered into a
`cache memory and continuously processed as soon as, or
`soon after, being received by the client. The advantage of
`streaming is that the client computer does not have to wait
`until all the data is downloaded from the server before some
`of the data is processed and the multimedia output is created.
`An example of multimedia data streaming is found in the
`Real player that is available over the Internet at Universal
`Resource Locator (“URL) http://www.real.com The Real
`audioplayer continuously sends audio data over the Internet
`from a server computer to the client computers. The audio
`data is buffered and processed by the client computers while
`the data is being sent. The client computers process the data
`by creating an audio output from the audio data.
`Applications. Such as the Real audioplayer, have condi
`tioned computer network users to expect instantaneous
`streaming data on demand. The Internet, however, is often
`unable to deliver streaming data. This inability is most pro
`nounced for video data. The inability to deliver streaming
`data on demand is due in part to the fact that live and on
`50
`demand streaming multimedia (SM) objects are generally
`delivered over the Internet and other data networks via unicast
`connections. This architecture has many shortcomings, both
`from the content provider's point of view and the user or
`recipient’s point of view. From the content provider's point of
`55
`view, he is faced with a server load that increases linearly with
`the number of clients. That is, each additional client request
`ing streaming multimedia data imposes an additional burden
`upon the content provider to meet the increased demand.
`From the Internet Service Provider's (ISPs) point of view,
`streaming multimedia under a unicast architecture poses net
`work congestion problems. From the client's point of view,
`there is often long delays between the time the video content
`is requested by a client and the time when the video content
`actually begins playing (i.e., high start-up latency). In addi
`tion to the high start-up latency there also exists unpredictable
`playback quality due to network congestion.
`
`SUMMARY OF THE INVENTION
`
`Illustrative embodiments of the present invention present a
`novel architecture and methods for Supporting high quality
`live and on-demand streaming multimedia on a public net
`work system, such as the Internet. By using helper servers
`(HS), also referred to as a helper, which operate as caching
`and streaming agents inside the network, existing caching
`techniques are enhanced to better Support streaming multi
`media over the Internet. The HSs serve to implement several
`methods specifically designed to Support streaming multime
`dia, including segmentation of streaming multimedia objects
`(SM objects) into Smaller units (i.e., chunks), cooperation of
`the HSS, and novel cache placement and replacement policies
`of the constituent units (chunks) which make up the SM
`objects.
`
`60
`
`65
`
`-7-
`
`

`

`US 7,398,312 B1
`
`3
`The HSs reduce a content provider's memory and process
`ing requirements by reducing the server load. Further, the
`invention reduces congestion problems by not being con
`strained by the unicast architecture of the prior art. And, the
`invention, reduces the long delays between the time video
`content is requested by a client and the time when the video
`content actually begins playing (i.e., reduces high start-up
`latency).
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`10
`
`The foregoing features of the present invention will
`become more readily apparent and may be understood by
`referring to the following detailed description of an illustra
`tive embodiment of the present invention, taken in conjunc
`tion with the accompanying drawings, where:
`FIG. 1 is an illustration of a network system which include
`HSs in accordance with the present invention;
`FIG. 2 is an illustration of a network system constructed
`according to one implementation of the invention;
`FIG. 3a is a block diagram of the construction of a cache
`according to the prior art;
`FIG. 3b is a block diagram of the construction of a cache
`according to an embodiment of the invention;
`FIG. 4 is a flowchart illustrating the method of helper
`selection according to an embodiment of the present inven
`tion;
`FIG. 5a is a block diagram of an SM object segmented
`according to an embodiment of the present invention; and
`FIG. 5b is a table illustrating cache storage of various
`elements in the network.
`
`15
`
`25
`
`30
`
`DETAILED DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`4
`services and/or prefetching services. HSs selectively cooper
`ate and communicate SM objects (or segments of Such
`objects) between and among each other and between content
`servers and clients. That is, the HS understands an SM
`objects transmission requirements and can behave, in some
`respects, like a content server.
`Data stream: a data stream transmits segments of a stream
`ing multimedia object between elements in the network. The
`source might be the sender (i.e., the content provider) or a HS.
`Receiving hosts could be HS or receivers (i.e., clients). FIG.
`1 illustrates several of the terms defined herein. Specifically,
`FIG. 1 shows an illustrative source 10 delivering a data stream
`directly to each of the HSs H1(2) and H2 (4). H2 is further
`shown delivering a data stream to each of the HSS H3 (6) and
`receiver R (8). In general, the data stream from H2 to H3 need
`not be the same as that arriving at receiver R (8), but in this
`example the data stream from H2 to H3 is illustratively part or
`all of the same SM object transmitted by the data stream
`arriving at receiver R (8).
`Streaming architectures in accordance with illustrative
`embodiments of the present invention Support techniques to
`enhance caches to support streaming media over a public
`network system, such as the Internet. While caching is the
`traditional approach for improving scalability, it fails to scale
`in terms of object size and number of Supported streams for
`streaming multimedia objects. In particular, existing solu
`tions for streaming multimedia on the Internet have several
`shortcomings because these solutions use a separate unicast
`stream for each request, thus requiring a stream to travel from
`the server to the client across the Internet for every request.
`To overcome these drawbacks and to further enhance the
`ability of existing caching systems to properly scale in terms
`of object size and number of Supported streams, illustrative
`embodiments of the present invention advantageously com
`bine two orthogonal mechanisms which are implemented via
`a novel system architecture to enhance existing caching sys
`tems. Briefly stated, the methods are: (1) novel cache place
`ment and replacement policies of SM objects which address
`the issues of data representation (i.e., how SM object data is
`segmented for storage), and data distribution (i.e., how SM
`object data is distributed and communicated throughout the
`network), and (2) cooperation of HSs which address how the
`HSS (i.e., caching and streaming agents inside the network)
`communicate via a novel scalable state distribution protocol
`which directs requests to the most appropriate HS or the
`COntent Server.
`An exemplary arrangement of using the invention is shown
`in FIG. 2 which illustrates a public network system. FIG. 2
`further includes a server computer, as represented by content
`server 12, which stores and serves content over a network 14.
`The illustrative network 14 is a high-speed, high-bandwidth
`interactive distribution network, and can be representative of
`the Internet. The content server 12 serves content in the form
`of text, audio, video, graphic images, and other multimedia
`data. In the Internet context, the content servers might repre
`sent Web sites which serve or multicast content in the form of
`hypermedia documents (e.g., Web pages) to "client' comput
`ers, as represented by computers 26-40. The network further
`includes HS 22-24. Each HS 22-24 is configured as a conven
`tional database server having processing capabilities, includ
`ing a CPU (not shown) and storage. HSS 22-24 cache Internet
`resources, such as those requested by client computers 26-40
`that have been downloaded from the content server 12 to
`allow localized serving of those resources. The interaction
`and cooperation of the above entities are further described
`below.
`
`This application is related to co-pending U.S. Pat. No.
`6,708,213 filed on Mar. 29, 2000 by Ethendranath Bom
`maiah, Katherine H. Guo, Markus Hofmann, and Sanjoy
`Paul, having a common assignee; the contents of which are
`incorporated herein by reference.
`To facilitate an understanding of illustrative embodiments
`of the present invention, it is advantageous to first consider the
`network operating environment of the present invention, as
`well as definitions relating to system architecture and opera
`tion.
`Illustrative embodiments of the present inventive architec
`tures, systems, and methods described herein focus on data
`streaming in global, worldwide public networks, such as the
`Internet. Those skilled in the art will recognize, however, that
`the present architectures, systems, and methods are appli
`cable to a wide variety of data networks and applications. The
`following terms and definitions are used in the present dis
`closure.
`Cache: a region in a computer disk that holds a Subset of a
`larger collection of data.
`Cache Replacement Policy: a policy which specifies which
`cache item(s) should be removed from the cache when the
`cache is full or nearly full.
`Streaming multimedia object (SM object): a type of data
`whose transmission has temporal characteristics Such that the
`data may become useless unless the transmission rate is regu
`lated in accordance with predetermined criteria (e.g., audio
`and video files). Transmission can start at any point within the
`object and can be terminated by the receiver at any time.
`Helper Server (HS): a HS, also referred to as a helper, is one
`of a plurality of servers in the network that provide certain
`value-added services. For example, a HS can provide caching
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`-8-
`
`

`

`US 7,398,312 B1
`
`10
`
`15
`
`25
`
`5
`Cache placement and replacement policies form an inte
`gral part of a caching system for both static and streaming
`multimedia objects (SM objects). However, existing cache
`placement and replacement policies do not support SM
`objects well. The present invention defines several aspects
`which serve to Support the cache placement and replacement
`policies associated with SM objects. They include a hotness
`rating associated with each SM object, data representation,
`and data distribution.
`1. Helper Server Helper Hotness Rating
`A first aspect for describing cache placement and replace
`ment policies of the present invention is the helper hotness
`rating. Caching systems for SM objects attempt to reduce
`end-to-end delay, server load and network load by distribut
`ing the SM objects among the HSS 22-24 located closest to the
`clients 26-40. It is not feasible, however, to replicate all SM
`objects in all the HSS 22-24 in the network 12 due to limited
`disk space on the HSS 22-24. From the HSs 22-24 point of
`view, given the limited disk space, a metric is required to
`identify those SM objects which are more frequently
`requested by clients 26-40 for cache storage at the HSS 22-24.
`ASM object is defined to be “hot” if a large number of client
`requests arrive at the HS 22-24 in a short period of time.
`Accordingly, each SM object is assigned a helper hotness
`rating at each HS 22-24 in the network at which the object is
`cached, defined by:
`helper hotness rating=(total # of client requests for the
`SM object), time span over which the requests are
`received at the HS
`(1)
`30
`This equation illustrates that high client demand for an SM
`object equates to a high helper hotness rating. The helper
`hotness rating is a local measure (i.e., local to the HS) repre
`senting how popular a SM object is among clients 26-40
`served by that HS.
`An exception exists where the client request history is not
`long enough to calculate a reasonable server hotness rating
`for a particular SM object. In such a case, a rating will be
`manually assigned to that object. Some objects can be rea
`sonably predicted to be very hot, for example, the top 10
`Videos of the week, top news stories, and a video showing a
`NASA spacecraft landing on Mars.
`In general, the role of the HSS 22-24 is to reduce network
`congestion by preventing client requests from going to the
`content server 12 whenever possible. In carrying out that
`responsibility, many client requests never reach the content
`server 12. AS Such, hotness as defined by equation (1) is an
`inappropriate metric for the content server 12. Accordingly, a
`more practical hotness metric, applicable to only the content
`server 12, is defined as:
`
`6
`2. Data Representation/Segmentation
`A second aspect for describing cache placement and
`replacement policies of the present invention is the segmen
`tation of the SM objects. A major distinction between SM
`objects and regular (i.e., static) objects on the web is their
`size. The size of SM objects is typically an order of magnitude
`or two larger than the size of Static objects. For example, a
`single, two hourlong MPEG movie requires about 1.4 Gbytes
`of disk space. From the perspective of a system designer, two
`design options are presented. A first design option is to store
`SM objects in their entirety at the HSS 22-24. This solution is
`deficient, however, in that, given the limited disk space at the
`HSS 22-24, only a small percentage of SM objects could be
`stored at the HS 22-24 at one time. A second design option
`proposes breaking the SM objects into Smaller segments, and
`treating these segments as special web objects observing their
`temporal relationship. An exception to this approach, might
`be to store SM objects defined to be very hot in their entirety.
`Notwithstanding the exception for storing very hot objects
`in their entirety, a SM object will generally be segmented at
`the HSS 22-24 to better utilize the HSs cache storage capac
`ity. As an illustration, assume a representative HS 22-24 has a
`static cache Storage whereby the minimal storage allocation
`unit of the static cache storage is a disk block of size S. In
`accordance with the object segmentation approach of the
`present invention, the SM object is divided into multiple
`chunks where each chunk is made up of a fixed number of
`segments. The chunks which make up the SM object can then
`be cached and replaced independently, thereby significantly
`increasing the utilization of the cache storage.
`As a further consideration in the segmentation of SM
`objects, each segment of a SM object has a starting playback
`time and an ending playback time inter-relating the various
`segments which make up a SM object. In addition, client
`requests for SM objects contain an explicit starting and end
`ing playback time. Thus, when a SM object request arrives at
`a HS, a simplistic hit/miss determination associated with
`classical web caching is inadequate. ASM object request will
`likely result in the client receiving some number of segments
`of the SM object from more than one HS 22-24. This not only
`increases signaling cost, but also increases the probability of
`losing synchronization. Therefore, it is preferable to cache
`successive segments of an SM object at a particular HS rather
`than caching a sequence of disjointed segments having mul
`tiple gaps.
`FIG.3a shows a block diagram of a cache storage 300 of a
`representative HS 22-24 in the network. The cache storage
`300 is shown to be made up of a plurality of contiguous disk
`block units 302a-302i, each unit being of a fixed size, S. The
`cache storage 300 may also be viewed as being logically
`divided into chunks in accordance with the data segmentation
`and storage principles of the present invention. For purposes
`of illustration, a chunk is selected to be four times (4x) the
`fundamental disk block unit S, as illustrated in FIG. 3b. As
`shown, chunk 0) is made up of disk blocks 302a-302d, and
`chunk 1 is made up of disk blocks 302e-h.
`When an SM object is received at a HS 22-24, disk blocks
`are allocated on demand. Given that SM objects are repre
`sented in chunks, caching begins at the first available chunk at
`the HS 22-24. For example, assuming that disk block 302a
`represents the first available storage location at the HS 22-24.
`The first chunk of the received SM object, Chunk 0), will be
`allocated to disk block segments 302a-302d. When the chunk
`boundary is reached, i.e., 302d, caching begins at the next
`disk block 302e. That is, chunk 1 of the SM object will be
`allocated to disk block 302e-302h. It is noted that a chunk of
`
`35
`
`40
`
`45
`
`50
`
`server hotness rating= X. (Helper hotness ratings) = hserver
`all HSs
`
`(2)
`
`55
`
`This equation states that, for a particular SM object, the
`content server metric for hotness is the sum of all the con
`stituent helper hotness ratings for all HSS 22-24 in the net
`work 14. That is, each HS 22-24 reports its local hotness
`rating to the content server 12 for inclusion in the general
`summation defined by Equation (2) to derive the server hot
`ness rating.
`The applicability of the helper and server hotness ratings
`will become more apparent in the context of the description
`provided below.
`
`60
`
`65
`
`-9-
`
`

`

`US 7,398,312 B1
`
`7
`an SM object chunk may not always be cached to its chunk
`boundary because an SM object stream can terminate at any
`time.
`In practice, allocating cache storage in accordance with the
`principles of a chunk size influences the size and number of
`gaps in an object. Dividing the cache storage into larger chunk
`sizes increases the probability of blocking where blocking is
`defined as the inability of being able to store a new SM object
`at the HS when the disk space is full. Alternatively, dividing
`the SM object into smaller chunks increases the probability of
`creating gaps, i.e., non-contiguous stored chunks, at an HS. In
`either case, it may be necessary for a client to get all the
`constituent segments of a SM object from more than one HS
`22-24. To do so, some form of intelligent pre-fetching is
`required which pre-fetches Subsequent segments while a cur
`rent segment is being streamed to the client.
`3. Data Distribution
`A third aspect for describing cache placement and replace
`ment policies of the present invention is data distribution.
`Data distribution encompasses two distinct Sub-aspects. A
`first sub-aspect refers to how data is distributed between the
`various communicating elements (i.e., content server 12, HSS
`22-24, and clients) in the network 14, as will be described
`with reference to the following placement policies (1) server
`25
`push where the content server 12 pushes popular multime
`dia SM objects to a plurality of HSS 22-24, (2) helper pull
`where each HS 22-24 individually pulls popular SM objects
`from the content server 12, and (3) demand driven where
`clients 26-40 request SM objects from particular HS caches
`and HS 22-24 in turn passes the request to the content server
`12.
`The second sub-aspect of data distribution pertains to how
`data is stored on disk, which is embodied in two approaches,
`a deterministic approach and a random approach, and which
`is discussed in detail below.
`
`35
`
`5
`
`10
`
`15
`
`30
`
`8
`additions at the content server 12 necessitate a periodic recal
`culation of the rank r of the remaining objects, which results
`in a continuous redistribution of the fraction of HSS 22-24 the
`SM objects are distributed to. Accordingly, the rank-based
`approach of the prior art proves unstable. To reduce this
`instability for SM objects, the present invention uses a cat
`egory-based approach.
`The category-based approach is characterized, not by an
`objects rank r, as applied in the rank-based approach, but
`rather by a server hotness rating, h, maintained by the
`server for each SM object it is hosting. The hotness rating
`h can be manually assigned or collected from HSS 22-24 in
`the network 14, as defined by equation (2) above. Based on
`the SM objects hotness rating at the server, h, the content
`server 12 assigns the SM object to one of four categories:
`cold, warm, hot, and very hot as follows:
`SM object is cold, if its server hotness rating, Osh serversri:
`warm, if its server hotness rating, Rish see.<R2, hot, if its
`server hotness rating, Rash-Rs, very hot, if its server
`hotness rating, Rish
`, where 0<R<R<R are input
`parameters.
`The category-based approach is advantageous for SM
`objects in that object category assignments are made strictly
`on the basis of the server hotness rating, independent of the
`SM object’s dynamically changing rank, thereby reducing
`the instability associated with the prior art rank-based
`approach.
`The category-based ranking approach of the present inven
`tion, defines what fraction of the HSS 22-24 an SM object is to
`be multicast to. The category-based based ranking approach
`is embodied in two ways: a category-based whole object
`server push approach (WOSP), and a fractional object server
`push approach (FOSP). Each of which will be described in
`detail below.
`The WOSP approach is given by the following: an SM
`object is multicast to a fractional of the HSs, if the SM object
`is ranked cold; an SM object is multicast to a fractional of the
`HSs, if the SM object is ranked warm; an SM object is
`multicast to a fractiona of the HSs, if the SM object is ranked
`hot; an SM object is multicast to a fractional of the HSs, if the
`SM object is ranked very hot, where a-a- are provided as
`input parameters and 0<=aka-a-a-1.
`As an illustrative example of the WOSP approach, assume
`parameters al-a are input as al-/s, a2/4, as /2, and aa-1.
`Accordingly, very hot objects would be multicast to all HSs
`22-24 in the network (e.g., a -1), hot objects would be mul
`ticast to one half of all HSS 22-24 in the network (e.g., a =/2).
`It is noted that the fraction of HSS 22-24 selected for multicast
`distribution is made randomly in the preferred embodiment,
`however other methods for determining which HSs to distrib
`ute to are within the scope of the present invention.
`As previously stated, the category ranking (i.e., very hot,
`hot, warm, cold) of an SM object depends only on its server
`hotness rating. Therefore, adding and deleting SM objects at
`the content server 12 will not affect an existing SM objects
`server hotness ranking leading to enhanced Stability over
`prior art methods.
`In the FOSP approach, all SM