(12) United States Patent
`Hoang
`
`USOO6725267B1
`(10) Patent No.:
`US 6,725,267 B1
`(45) Date of Patent:
`Apr. 20, 2004
`
`(54) PREFETCHED DATA IN A DIGITAL
`BROADCAST SYSTEM
`
`(75) Inventor: Khoi Hoang, Newark, CA (US)
`
`(73) ASSignee: Privave Corporation, Fremont, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/709,948
`(22) Filed:
`Nov. 10, 2000
`Related U.S. Application Data
`
`(63) Continuation-in-part of application No. 09/584.832, filed on
`May 31, 2000.
`7
`(51) Int. Cl." ................................................ G06F 15/16
`(52) U.S. Cl. ....................... 709/226; 709/104; 709/217;
`709/233
`(58) Field of Search ................................. 709/104, 217,
`709/226, 233
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,280.221 A 7/1981 Chun et al. ................... 375/17
`E. A 7/1990 Horton et al.
`58/335
`4.963,995 A 10/1990 Lang .......................... 358/33
`5,089,982 A 2/1992 Gran et al. ................. 364/726
`5,132,992 A 7/1992 Yurt et al.
`5,421,031 A
`5/1995 De Bey ....................... 725.92
`5,521,630 A * 5/1996 Chen et al.
`5,557,316 A 9/1996 Hoarty et al. .................. 348/7
`5,604,528 A 2/1997 Edwards et al.
`5,612,742 A 3/1997 Krause et al.
`5,619.249 A 4/1997 Billock et al.
`5,632,681 A 5/1997 Bakoglu et al.
`5,654,746 A 8/1997 McMullan, Jr. et al.
`5,701,582. A 12/1997 De Bey ....................... 455/5.1
`5,724,646 A 3/1998 Ganek et al. ................ 455/4.2
`5,745,758 A
`4/1998 Shaw et al.
`
`5,751,282 A 5/1998 Girard et al. ............... 345/327
`5,751,709 A
`5/1998 Rathnavelu ................. 370/395
`5,768,539 A 6/1998 Metz et al.
`5,781,228 A * 7/1998 Sposato
`5,790,423 A 8/1998 Lau et al.
`5,805,804 A 9/1998 Laursen et al. ........ 395/200.02
`5,815,146 A
`9/1998 Youden et al. .............. 345/327
`5,850,258. A 12/1998 Kang ......................... 348/390
`(List continued on next page.)
`OTHER PUBLICATIONS
`PCT International Search Report, International Application
`No. PCT/US02/19618 filed Jun. 20, 2002, mailed Sep. 19,
`2002, 4 pages.
`Video on Demand Technologies and Demonstrations, Final
`Report, Marek Podgorny and Geoffrey C. Fox, Northeast
`Parallel
`Architectures
`Center,
`Contract
`No.:
`F-30602-94–C–0256, Mar. 1997, pp. 1–108.
`(List continued on next page.)
`Primary Examiner Le Hien Luu
`Assistant Examiner Stephan Willett
`(57)
`ABSTRACT
`A method for Sending data to a client to provide data-on
`demand Services comprises the Steps of receiving a data file,
`Specifying a time interval, parsing the data file into a
`plurality of data blocks based on the time interval Such that
`each data block is displayable during a time interval, deter
`mining a required number of time slots to Send the data file,
`allocating to each time slot at least a first of the plurality of
`data blocks and optionally one or more additional data
`blocks, such that starting from any of the time slots, (i) the
`data file can be displayed by accessing the first of the
`plurality of data blocks; (ii) at a consecutive time slot, a next
`data block Sequential to a prior displayed data block is
`available for displaying; and (iii) repeating step (ii) until all
`of the plurality of data blocks for the data file has been
`displayed, and Sending the plurality of data blockS based on
`the allocating Ste
`g Slep.
`
`14 Claims, 5 Drawing Sheets
`
`102
`Central Controlling
`Sever
`
`14
`Monitoring
`Module
`
`Central
`Storage
`
`- 103
`
`100
`
`112
`
`->
`
`108
`
`404a
`
`Charle Sever 1 :
`
`Up-Converter 1
`
`106a
`e
`
`106
`
`1049
`-
`
`104.c
`
`Chane Sever 2
`
`Channel Server 3
`
`Up-Converter 2
`
`Up-Converter 3
`
`s
`106c |g
`s
`
`
`
`O
`
`HX-
`
`X
`
`11
`
`O
`Chathhel Server in
`
`104
`
`Up-Conve ter
`
`116a
`a
`
`116b
`
`Backup
`Channel
`
`Backup channel
`Sewer2
`
`Backup
`rter 1
`> Up-Conve
`
`s
`
`BackLip
`Up-converter 2
`
`DISH, Exh.1009, p.0001
`
`

`

`US 6,725,267 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`1/1999 Thompson .................. 370/389
`5,856,973 A
`5,892,535 A 4/1999 Allen et al. .................... 348/9
`5,909,594 A 6/1999 Ross et al.
`5,915,094. A 6/1999 Kouloheris et al. .... 395/200.49
`5,949,948 A 9/1999 Krause et al. ................. 386/6
`5,961,603 A 10/1999 Kunkel et al.
`5,978,649 A 11/1999 Khan
`5,995,092 A 11/1999 Yuen et al.
`6,005.599 A 12/1999 Asai et al. ..................... 348/7
`6,011,798 A 1/2000 McAlpine .....
`... 370/395
`6,012,080 A 1/2000 OZden et al. .
`... 709/102
`6,018,359 A
`1/2000 Kermode et al. .............. 348/7
`6,018,765 A 1/2000 Durana et al.
`... 709/217
`6,028.847. A 2/2000 Beanland .................... 370/252
`6,029,045 A 2/2000 Picco et al.
`6,029,046 A 2/2000 Khan et al.
`6,049,332 A 4/2000 Boetje et al.
`6,049,539 A 4/2000 Lee et al.
`E. A : : Mills st al - - - - - - - - - - - - - - - - - 709/200
`6,058,122 A
`5/2000 R et al. .............. 370522
`6,075,570 A
`6/2000 Usui et al. .................. 34.8569
`6,076,062 A * 6/2000 Van Steenbrugge
`6,112,023 A 8/2000 Dave et al.
`6,118,821. A * 9/2000 Matsumoto et al.
`6,119,163 A * 9/2000 Monteiro et al.
`6,128,467 A 10/2000 Rege .......................... 455/4.2
`6,157,949 A 12/2000 Cheng et al. ...
`... 709/219
`6,160,546 A 12/2000 Thompson et al. ......... 345/327
`6,169,767 B1 * 1/2001 Strolle et al.
`6,198.723 B1
`3/2001 Parruck et al. ............. 370/230
`
`2Y- - - 2
`
`e a
`
`3/2001 Logan et al. ............... 707/501
`6,199,076 B1
`4/2001 Ikeda .......................... 725/92
`6.212,681 B1
`4/2001 Barton et al. ............... 348/473
`6,215,526 B1
`4/2001 Brodigan .................... 370/486
`6.219,355 B1
`4/2001 Sequeira
`6,222,530 B1
`5/2001 Barton ........................ 386/46
`6,233,389 B1
`6/2001 SeaZholtz et al. ........... 370/468
`6,246,695 B1
`6,263,019 B1 * 7/2001 Ryan
`6,266,369 B1
`7/2001 Wang et al.
`6,282,195 B1
`8/2001 Miller et al................. 370/392
`6,349,098 B1
`2/2002 Parruck et al. ............. 370/395
`6,370,688 B1
`4/2002 Hejna, Jr. ................... 725/101
`6,389,075 B2
`5/2002 Want et al.
`6,477,579 B1 11/2002 Kunkel et al.
`6,502,139 B1 12/2002 Birk et al. .................. 709/233
`2001/0014211 A1 * 8/2001 Morinaga
`
`
`
`OTHER PUBLICATIONS
`
`PCT/ISA/220, PCTISR, International Application No. PCT/
`US02/12752 Filed Apr. 23, 2002, mailed Feb. 10, 2003.
`PCTISA/220, PCTISR, International Application No, PCT/
`US02/3800 Filed Nov. 27, 2002, mailed Feb. 14, 2003.
`PCT International Search Report, International Application
`No.: PCT/US00/22989 filed Aug. 22, 2000, mailed Aug. 15,
`2001, 9 pages.
`PCT International Search Report, International Application
`No.: PCT/US01/17993 filed May 31, 2001, mailed Sep. 28,
`2001, 5 pages.
`
`* cited by examiner
`
`DISH, Exh.1009, p.0002
`
`

`

`U.S. Patent
`
`Apr. 20, 2004
`
`Sheet 1 of 5
`
`US 6,725,267 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`1OO
`
`38
`S. E.
`a
`
`Transmission
`Medium
`110
`
`Central Controlling Server
`
`Central
`Storage
`
`104a
`
`104b.
`
`Up-Converter 1
`
`Channel Server 1
`
`Channel Server 2
`
`Up-Converter 2
`
`Channel Server 3
`
`
`
`Up-Converter 3
`
`O
`
`O
`
`Channel Server n
`
`Up-Converter n
`
`
`
`
`
`
`
`
`
`
`
`
`
`Cable Television
`System
`
`FIG. 1A
`
`DISH, Exh.1009, p.0003
`
`

`

`U.S. Patent
`
`Apr. 20, 2004
`
`Sheet 2 of 5
`
`US 6,725,267 B1
`
`102
`
`Central Controlling
`Server
`
`
`
`
`
`114
`Monitoring
`Module
`
`
`
`Central
`Storage
`
`1OO
`
`108
`
`
`
`
`
`3 58
`E. C.
`9 N
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Channel Server 1
`
`Channel Server 2
`
`
`
`104b.
`
`Channel Server 3
`
`
`
`er
`|Up convere 2
`
`106C
`
`Up-Converter 3
`
`
`
`
`
`Channel Server n
`
`106n
`
`onverter n --
`
`Backup
`Channel
`
`Backup Channel
`Server 2
`
`116b
`
`Backup
`Up-Converter 1
`
`Backup
`Up-Converter 2
`
`118b
`
`FG. 1B
`
`DISH, Exh.1009, p.0004
`
`

`

`U.S. Patent
`
`Apr. 20, 2004
`
`Sheet 3 of 5
`
`US 6,725,267 B1
`
`Server
`Controller
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`104
`
`QAM
`Modulator
`
`Local Memory
`
`Network
`Interface
`
`FIG. 2
`
`To Up
`Converter
`106
`
`Central
`Controling
`Server
`102
`
`DISH, Exh.1009, p.0005
`
`

`

`U.S. Patent
`
`Apr. 20, 2004
`
`Sheet 4 of 5
`
`US 6,725,267 B1
`
`
`
`OAM
`Demodulator
`
`110
`-
`
`Conditional
`ACCeSS
`Control
`
`Local Memory
`
`STB
`Controller
`
`Graphics
`Overlay
`
`FIG 3
`
`DISH, Exh.1009, p.0006
`
`

`

`U.S. Patent
`
`Apr. 20, 2004
`
`Sheet S of 5
`
`US 6,725,267 B1
`
`Receive a number of data
`blocks "x" for a data file
`
`402
`
`= 0
`
`-404
`
`Clear a Reference Array
`
`406
`
`416
`
`j= j + 1
`
`408
`
`END
`
`410
`
`
`
`
`
`Write Al Data Blocks Stored in Matrix Positions of Column
`(i+) mod (x)) in a Matrix into the Reference Array; Do Not
`Write if the Reference Array Already Contains the Data Block
`
`
`
`Does RA Contain
`Data Block i?
`
`i = i + 1
`
`Add Data Block i into the Matrix at Matrix Postion
`(i+j)mod(x), j and the Reference Array
`
`
`
`FIG. 4
`
`DISH, Exh.1009, p.0007
`
`

`

`US 6,725,267 B1
`
`1
`PREFETCHED DATA IN A DIGITAL
`BROADCAST SYSTEM
`
`RELATED APPLICATION
`This application is a continuation-in-part application of
`the parent application titled “Systems and Methods for
`Providing Video-On-Demand Services for Broadcasting
`Systems' filed on May 31, 2000, bearing application Ser.
`No. 09/584,832.
`
`BRIEF DESCRIPTION OF THE INVENTION
`This invention relates generally to data-on-demand SyS
`tems. In particular, this invention relates to Video-on
`demand Systems.
`
`15
`
`2
`committed to service 10,000 clients. This technique may
`work if most of the Subscribing clients do not order videos
`at the Same time. However, this technique is Set up for failure
`because most clients are likely to want to view VideoS at the
`same time (i.e., evenings and weekends), thus, causing the
`local Server to become overloaded.
`Thus, it is desirable to provide a System that is capable of
`providing on-demand Services to a large number of clients
`over virtually any transmission medium without replacing
`existing infrastructure.
`SUMMARY OF THE INVENTION
`In an exemplary embodiment, at a Server Side, a method
`for Sending data to a client to provide data-on-demand
`Services comprises the Steps of receiving a data file, Speci
`fying a time interval, parsing the data file into a plurality of
`data blockS based on the time interval Such that each data
`block is displayable during the time interval, determining a
`required number of time slots to Send the data file, allocating
`to each time slot at least a first of the plurality of data blocks
`and optionally one or more additional data blocks, Such that
`the plurality of data blockS is available in Sequential order to
`a client accessing the data file during any time slot, and
`Sending the plurality of data blockS based on the allocating
`Step. In one embodiment, the parsing Step includes the Steps
`of determining an estimated data block size, determining a
`cluster size of a memory in a channel Server, and parsing the
`data file based on the estimated data block size and the
`cluster size. In another embodiment, the determining Step
`includes the Step of assessing resource allocation and band
`width availability.
`In one embodiment, the method further comprises the
`Steps of Selecting a set of prefetch data blocks from the
`plurality of data blocks and Separately Sending the Set of
`prefetch data blocks in a dedicated channel for Sending
`prefetch data, program guide, commercials, firmware
`update, etc. In an exemplary embodiment, the Step of
`Selecting a Set of prefetch data blocks includes the Steps of:
`(1) determining a bandwidth reduction, a bandwidth alloca
`tion for prefetch data in the dedicated channel, and a delay
`time; and (2) Selecting the prefetch data blocks based on the
`bandwidth reduction, the bandwidth allocation, and the
`delay time.
`In another embodiment, the method further comprises the
`Steps of receiving a request for a preview, randomly Select
`ing a Set of data blocks from the plurality of data blocks to
`compose the preview, and causing a display of the preview.
`In yet another embodiment, the method further comprises
`Sending a set of commercial data blocks in the dedicated
`channel and causing a display of the Set of commercial data
`blocks at predetermined times. In an exemplary
`embodiment, the commercial data blocks are continuously
`Sent in the dedicated channel. In this embodiment, the Step
`of displaying the Set of commercial data blocks includes the
`Steps of receiving a user Selection of a price based on a
`frequency of commercial display and causing a display of
`the Set of commercial data blocks based on the user Selec
`tion.
`In yet another embodiment, the method further comprises
`the Steps of checking a packet header of the data file for an
`emergency bit, tuning to the dedicated channel to receive
`emergency information when the emergency bit is detected,
`and causing a display of the emergency information. In one
`embodiment, this method further comprises the Steps of
`determining whether the emergency information is for a
`relevant region and displaying the emergency information if
`the emergency information is for the relevant region.
`
`BACKGROUND OF THE INVENTION
`Video-on-demand (VOD) systems are one type of data
`on-demand(DOD) system. In VOD systems, video data files
`are provided by a Server or a network of Servers to one or
`more clients on a demand basis.
`In a conventional VOD architecture, a server or a network
`of Servers communicates with clients in a Standard hierar
`chical client-Server model. For example, a client Sends a
`request to a server for a data file (e.g., a video data file). In
`response to the client request, the Server Sends the requested
`file to the client. In the Standard client-server model, a
`client's request for a data file can be fulfilled by one or more
`Servers. The client may have the capability to Store any
`received data file locally in non-volatile memory for later
`use. The Standard client-Server model requires a two-way
`communications infrastructure. Currently, two-way commu
`nications requires building new infrastructure because exist
`ing cables can only provide one-way communications.
`Examples of two-way communications infrastructure-are
`hybrid fiber optics coaxial cables (HFC) or all fiber infra
`Structure. Replacing existing cables is very costly and the
`resulting Services may not be affordable to most users.
`In addition, the Standard client-Server model has many
`limitations when a Service provider (e.g., a cable company)
`attempts to provide VOD services to a large number of
`clients. One limitation of the standard client-server model is
`that the Service provider has to implement a mechanism to
`continuously listen and fulfill every request from each client
`within the network; thus, the number of clients who can
`receive Service is dependent on the capacity of Such a
`mechanism. One mechanism uses massively-parallel com
`puters having large and fast disk arrays as local Servers.
`However, even the fastest existing local Server can only
`deliver video data streams to about 1000 to 2000 clients at
`one time. Thus, in order to Service more clients, the number
`of local Servers must increase. Increasing local Servers
`requires more upper level Servers to maintain control of the
`local Servers.
`Another limitation of the standard client-server model is
`that each client requires its own bandwidth. Thus, the total
`required bandwidth is directly proportional to the number of
`Subscribing clients. Cache memory within local ServerS has
`been used to improve bandwidth limitation but using cache
`memory does not Solve the problem because cache memory
`is also limited.
`Presently, in order to make Video-on-demand Services
`more affordable for clients, existing Service providers are
`increasing the ratio of clients per local Server above the local
`Server's capabilities. Typically, a local Server, which is
`capable of providing Service to 1000 clients, is actually
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`DISH, Exh.1009, p.0008
`
`

`

`25
`
`3
`In an exemplary embodiment, at a client Side, a method
`for processing data received from a server to provide data
`on-demand Services comprises the steps of: (a) receiving a
`Selection of a data file during a first time slot; (b) receiving
`at least one data block of the data file during a Second time
`slot; (c) during a next time slot: receiving any data block not
`already received, Sequentially displaying a data block of the
`data file, and repeating step (c) until all data blocks of the
`data file has been received and displayed. In one
`embodiment, the method for processing data received from
`a Server is performed by a Set-top box at the client Side.
`In an exemplary embodiment, a data file is divided into a
`number of data blocks and a Scheduling matrix is generated
`based on the number of data blocks. At the server side, the
`Scheduling matrix provides a Send order for Sending the data
`blocks, Such that a client can access the data blocks in
`Sequential order at a random time. In an exemplary
`embodiment, a method for generating a Scheduling matrix
`for a data file comprises the Steps of: (a) receiving a number
`of data blocks x for a data file; (b) setting a first variable
`to Zero; (c) setting a second variable i to Zero; (d)
`clearing all entries in a reference array; (e) writing at least
`one data block stored in matrix positions of a column (i+)
`modulo X in a matrix to a reference array, if the reference
`array does not already contain the data block, (f) writing a
`data blocki into the reference array and a matrix position
`(i+j) modulo X,j) of the matrix, if the reference array does
`not contain the data blocki; (g) incrementing the Second
`variable i by one and repeating step (e) until the Second
`variable i is equal to the number of data blocks x); and (h)
`incrementing the first variable
`by one and repeating the
`Step (c) until the first variable
`is equal to the number of
`data blockS X). In one embodiment, a Scheduling matrix is
`generated for each data file in a set of data files and a
`convolution method is applied to generate a delivery matrix
`based on the Scheduling matrices for Sending the Set of data
`files.
`A data-on-demand System comprises a first Set of channel
`Servers, a central controlling Server for controlling the first
`Set of channel Servers, a first Set of up-converters coupled to
`the first Set of channel Servers, a combiner/amplifier coupled
`to the first Set of up-converters, and a combiner/amplifier
`adapted to transmit data via a transmission medium. In an
`exemplary embodiment, the data-on-demand System further
`comprises a channel monitoring module for monitoring the
`System, a Switch matrix, a Second Set of channel Servers, and
`a Second set of up-converters. The channel monitoring
`module is configured to report to the central controlling
`Server when System failure occurs. The central controlling
`Server, in response to report from the channel monitoring
`module, instructs the Switch matrix to replace a defective
`channel server in the first set of channel servers with a
`channel Server in the Second Set of channel Servers and a
`defective up-converter in the first Set of up-converters with
`an up-converter in the Second Set of up-converters.
`55
`A method for providing data-on-demand Services com
`prises the Steps of calculating a delivery matrix of a data file,
`Sending the data file in accordance with the delivery matrix,
`Such that a large number of clients is capable of viewing the
`data file on demand. In one embodiment, the data file
`includes a Video file.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1A illustrates an exemplary DOD system in accor
`dance with an embodiment of the invention.
`FIG. 1B illustrates an exemplary DOD system in accor
`dance with another embodiment of the invention.
`
`4
`FIG. 2 illustrates an exemplary channel Server in accor
`dance with an embodiment of the invention.
`FIG. 3 illustrates an exemplary Set-top box in accordance
`with an embodiment of the invention.
`FIG. 4 illustrates an exemplary proceSS for generating a
`Scheduling matrix in accordance with an embodiment of the
`invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`FIG. 1A illustrates an exemplary DOD system 100 in
`accordance with an embodiment of the invention. In this
`embodiment, the DOD system 100 provides data files, such
`as video files, on demand. However, the DOD system 100 is
`not limited to providing video files on demand but is also
`capable of providing other data files, for example, game files
`on demand. The DOD system 100 includes a central con
`trolling server 102, a central storage 103, a plurality of
`channel servers 104a–104n, a plurality of up-converters
`106a-106n, and a combiner/amplifier 108. The central con
`trolling server 102 controls the channel servers 104. The
`central Storage 103 Stores data files in digital format. In an
`exemplary embodiment, data files Stored in the central
`Storage 103 are accessible via a Standard network interface
`(e.g., ethernet connection) by any authorized computer, Such
`as the central controller server 102, connected to the net
`work. Each channel Server 104 is assigned to a channel and
`is coupled to an up-converter 106. The channel servers 104
`provide data files that are retrieved from the central Storage
`103 in accordance with instructions from the central con
`trolling server 102. The output of each channel server 104 is
`a quadrature amplitude modulation (QAM) modulated inter
`mediate frequency (IF) signal having a Suitable frequency
`for the corresponding up-converter 106. The QAM
`modulated IF Signals are dependent upon adopted Standards.
`The current adopted standard in the United States is the
`data-over-cable-systems-interface-specification (DOCSIS)
`standard, which requires an approximately 43.75 MHz IF
`frequency. The up-converters 106 convert IF signals
`received from the channel servers 104 to radio frequency
`signals (RF signals). The RF signals, which include fre
`quency and bandwidth, are dependent on a desired channel
`and adopted Standards. For example, under the current
`standard in the United States for a cable television channel
`80, the RF signal has a frequency of approximately 559.25
`MHz and a bandwidth of approximately 6 MHz. The outputs
`of the up-converters 106 are applied to the combiner/
`amplifier 108. The combiner/amplifier 108 amplifies,
`conditions, and combines the received RF signals then
`outputs the Signals out to a transmission medium 110.
`In an exemplary embodiment, the central controlling
`Server 102 includes a graphics user interface (not shown) to
`enable a Service provider to Schedule data delivery by a
`drag-and-drop operation. Further, the central controlling
`server 102 authenticates and controls the channel servers
`104 to Start or Stop according to delivery matrices. In an
`exemplary embodiment, the central controlling Server 102
`automatically Selects a channel and calculates delivery
`matrices for transmitting data files in the Selected channel.
`The central controlling server 102 provides offline addition,
`deletion, and update of data file information (e.g., duration,
`category, rating, and/or brief description). Further, the cen
`tral controlling server 102 controls the central storage 103
`by updating data files and databases Stored therein.
`In an exemplary embodiment, an existing cable television
`System 120 may continue to feed Signals into the combiner/
`
`US 6,725,267 B1
`
`1O
`
`15
`
`35
`
`40
`
`45
`
`50
`
`60
`
`65
`
`DISH, Exh.1009, p.0009
`
`

`

`US 6,725,267 B1
`
`15
`
`25
`
`S
`amplifier 108 to provide non-DOD services to clients. Thus,
`the DOD system 100 in accordance with the invention does
`not disrupt present cable television Services.
`FIG. 1B illustrates another exemplary embodiment of the
`DOD system 100 in accordance with the invention. In
`addition to the elements illustrated in FIG. 1A, the DOD
`system 100 includes a Switch matrix 112, a channel moni
`toring module 114, a set of back-up channel Servers
`116a-116b, and a set of back-up up-converters 118a–118b.
`In one embodiment, the Switch matrix 112 is physically
`located between the up-converters 106 and the combiner/
`amplifier 108. The Switch matrix 112 is controlled by the
`central controlling Server 102. The channel monitoring mod
`ule 114 comprises a plurality of configured Set-top boxes,
`which Simulate potential clients, for monitoring the health of
`the DOD system 100. Monitoring results are communicated
`by the channel monitoring module 114 to the central con
`trolling Server 102. In case of a channel failure (i.e., a
`channel Server failure, an up-converter failure, or a commu
`nication link failure), the central controlling server 102
`through the Switch matrix 112 disengages the malfunction
`ing component and engages a healthy backup component
`116 and/or 118 to resume service.
`In an exemplary embodiment, data files being broadcasted
`from the DOD system 100 are contained in motion pictures
`expert group (MPEG) files. Each MPEG file is dynamically
`divided into data blocks and Sub-blockS mapping to a
`particular portion of a data file along a time axis. These data
`blocks and Sub-blocks are Sent during a pre-determined time
`in accordance with three-dimensional delivery matrices pro
`vided by the central controlling server 102. A feedback
`channel is not necessary for the DOD system 100 to provide
`DOD services. However, if a feedback channel is available,
`the feedback channel can be used for other purpose, Such as
`billing or providing Internet Services.
`FIG. 2 illustrates an exemplary channel server 104 in
`accordance with an embodiment of the invention. The
`channel server 104 comprises a server controller 202, a CPU
`204, a QAM modulator 206, a local memory 208, and a
`network interface 210. The server controller 202 controls the
`overall operation of the channel server 104 by instructing the
`CPU 204 to divide data files into blocks (further into
`Sub-blocks and data packets), Select data blocks for trans
`mission in accordance with a delivery matrix provided by
`the central controlling Server 102, encode Selected data,
`compress encoded data, then deliver compressed data to the
`OAM modulator 206. The OAM modulator 206 receives
`data to be transmitted via a bus (i.e., PCI, CPU local bus) or
`Ethernet connections. In an exemplary embodiment, the
`QAM modulator 206 may include a downstream QAM
`50
`modulator, an upstream quadrature amplitude modulation/
`quadrature phase shift keying (QAM/QPSK) burst demodu
`lator with forward error correction decoder, and/or an
`upstream tuner. The output of the QAM modulator 206 is an
`IF signal that can be applied directly to an up-converter 106.
`The network interface 210 connects the channel server
`104 to other channel servers 104 and to the central control
`ling Server 102 to execute the Scheduling and controlling
`instructions from the central controlling Server 102, report
`ing Status back to the central controlling Server 102, and
`receiving data files from the central Storage 103. Any data
`file retrieved from the central storage 103 can be stored in
`the local memory 208 of the channel server 104 before the
`data file is processed in accordance with instructions from
`the server controller 202. In an exemplary embodiment, the
`channel server 104 may send one or more DOD data streams
`depending on the bandwidth of a cable channel (e.g., 6, 6.5,
`
`6
`or 8 MHz), QAM modulation (e.g., QAM 64 or QAM 256),
`and a compression standard/bit rate of the DOD data stream
`(i.e., MPEG-1 or MPEG-2).
`FIG. 3 illustrates an exemplary set-top box (STB) 300 in
`accordance with an embodiment of the invention. The STB
`300 comprises a QAM demodulator 302, a CPU 304, a
`conditional access module 306 (e.g., a Smart card System), a
`local memory 308, a buffer memory 309, a STB controller
`310, a decoder 312, and a graphics overlay module 314. The
`STB controller 310 controls the overall operation of the STB
`300 by controlling the CPU 302 and the QAM demodulator
`302 to Select data in response to a client's request, decode
`Selected data, decompress decoded data, reassemble
`decoded data, store decoded data in the local memory 308 or
`the buffer memory 309, and deliver stored data to the
`decoder 312. In an exemplary embodiment, the STB con
`troller 310 controls the overall operation of the STB 300
`based on data packet headers in the data packets received
`from the transmission medium 110. In an exemplary
`embodiment, the local memory 308 comprises non-volatile
`memory (e.g., a hard drive) and the buffer memory 309
`comprises volatile memory.
`In one embodiment, the OAM demodulator 302 com
`prises transmitter and receiver modules and one or more of
`the following: privacy encryption/decryption module, for
`ward error correction decoder/encoder, tuner control, down
`Stream and upstream processors, CPU and memory interface
`circuits. The OAM demodulator 302 receives modulated IF
`Signals, Samples and demodulates the Signals to restore data.
`The conditional access module 306 permits a decoding
`process when access is granted after authentication and/or
`when appropriate fees have been charged. Access condition
`is determined by the service provider.
`In an exemplary embodiment, when acceSS is granted, the
`decoder 312 decodes at least one data block to transform the
`data block into images displayable on an output Screen. The
`decoder 312 Supports commands from a Subscribing client,
`Such as play, Stop, pause, Step, rewind, forward, etc.
`The graphics overlay module 314 enhances displayed
`graphics quality by, for example, providing alpha blending
`or picture-in-picture capabilities. In an exemplary
`embodiment, the graphics overlay module 314 can be used
`for graphics acceleration during game playing mode, for
`example, when the Service provider provides games-on
`demand Services using the System in accordance with the
`invention.
`In an exemplary embodiment, although data files are
`broadcasted to all cable television subscribers, only the
`DOD subscriber who has a compatible STB300 will be able
`to decode and enjoy data-on-demand Services. In one exem
`plary embodiment, permission to obtain data files on
`demand can be obtained via a Smart card System in the
`conditional access control module 306. A Smart card may be
`rechargeable at a local Store or vending machine Set up by
`a Service provider. In another exemplary embodiment, a flat
`fee System provides a Subscriber unlimited access to all
`available data files.
`In an exemplary embodiment, data-on-demand interactive
`features permit a client to Select at any time an available data
`file. The amount of time between when a client presses a
`Select button and the time the Selected data file begins
`playing is referred to as a response time. AS more resources
`are allocated (e.g., bandwidth, server capability) to provide
`DOD Services, the response time gets Shorter. In an exem
`plary embodiment, a response time can be determined based
`on an evaluation of resource allocation and desired quality
`of Service.
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`DISH, Exh.1009, p.0010
`
`

`

`US 6,725,267 B1
`
`7
`In an exemplary embodiment, a Selected response time
`determines the duration of a time slot. The duration of a time
`slot (TS) is the time interval for playing a data video file, is
`divided into a number of data blocks Such that each data
`block can Support the playing of the data file for the duration
`of a time slot.
`In one embodiment, the number of data blocks (NUM
`OF BLKS) for each data file can be calculated as follows:
`
`8
`reference array. If the reference array does not contain data
`block i, data block i is added into the Scheduling matrix at
`matrix position (i+) modulo (x), j and the reference array
`(step 422). After the data block i is added to the scheduling
`matrix and the reference array, i is incremented by 1, Such
`that i=i--1 (Step 424), then the process repeats at Step 414
`until i=X. If the reference array contains data block i, i is
`incremented by 1, such that i=i-1 (step 424), then the
`process repeats at Step 414 until i=X. When i=X, j is incre
`mented by 1, Such that j=+1 (Step 416) and the process
`repeats at step 406 until j=X. The entire process ends when
`j=x (step 410).
`In an exemplary embodiment, if a data file is divided into
`Six data blocks (X=6), the Scheduling matrix and the refer
`ence arrays are as follows:
`
`Estimated BLK Size = (DataFile Size * TS)/DataFile Length
`BLKSIZE = (Estimated BLK Size + CLUSTER SIZE - 1 Byte),
`CLUSTER SIZE
`BLK SIZE BYTES = BLK SIZE * CLUSTER SIZE
`NUM OF BLKS = (DataFile Size + BLK SIZE BYTES -
`1 Byte)/BLK SIZE BYTES
`
`(1)
`(2)