United States Patent 19
`Venkatesh et al.
`
`54). STORAGE AND ACCESS OF CONTINUOUS
`MEDIA FILES INDEXED AS LISTS OF RAID
`STRIPE SETS ASSOCIATED WITH FILE
`NAMES
`
`75 Inventors: Dinesh Venkatesh, Brookline; John
`Forecast, Newton; Wayne W. Duso,
`Shrewsbury, all of Mass.
`73 Assignee: EMC Corporation, Hopkinton, Mass.
`
`21 Appl. No.: 08/851,509
`22 Filed:
`May 5, 1997
`Related U.S. Application Data
`60 Provisional application No. 60/044,948, Apr. 25, 1997.
`6
`51) Int. Cl. ...................................................... G06F 12/00
`52) U.S. Cl. ................ 711/114; 395/182.04; 395/182.05
`58 Field of Search ............................ 711/114; 371/51.1,
`371/404; 395/182.04, 182.05
`
`56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,608,688 8/1986 Hansen et al. ............................ 371/11
`4,755,928 7/1988 Johnson et al. ...
`... 364/200
`4,761,785 8/1988 Clark et al. .......
`... 371/51.1
`5,072,378 12/1991. Manka ..........
`... 395/575
`5,148,432 9/1992 Gordon et al.
`... 371/10.1
`5,175,837 12/1992 Arnold et al. ...
`395,425
`5,206,939 4/1993 Yani et al. ........
`... 395/400
`5,208,665 5/1993 McCalley et al.
`... 358/862
`5,208,813 5/1993 Stallmo et al. ...
`... 371/10.1
`5,218,695
`6/1993 Noveck et al. ......................... 395/600
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`
`0 061570 A3 10/1982 European Pat. Off. .......... G11C 9/06
`633694 A1 1/1995 European Pat. Off. ....... HO4N 7/173
`O 683 464 A2 11/1995 European Pat. Off. ........ G06F 17/60
`O 697 660 A1 2/1996 European Pat. Off. ........ G06F 11/20
`WO 93/16557 8/1993 WIPO .............................. HO4N 7/14
`WO 94/OO816
`1/1994 WIPO .
`. GO6F 13/OO
`WO95/10918 4/1995 WIPO .............................. HO4N 7/14
`WO 97/16023 5/1997 WIPO ............................ HO4N 7/173
`
`
`
`USOO5974503A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,974,503
`Oct. 26, 1999
`
`OTHER PUBLICATIONS
`Dishon et al., “A Highly Available Storage System Using the
`Checksum Method.” Seventeenth International Symposium
`on Fault-Tolerant Computing, Jul. 6-8, 1987, Pittsburg,
`Penn., IEEE Computer Society, IEEE, New York, N.Y., pp.
`178-181.
`Martin E. Schulze, “Considerations in the Design of a RAID
`Prototype,” Computer Science Division, EECS, University
`of California at Berkeley, CA, Aug. 25, 1988.
`Katz et al., “Disk System Architectures for High Perfor
`mance Computing,” Computer Science Division, EECS,
`University of California at Berkeley, CA, Mar. 1989.
`(List continued on next page.)
`
`Primary Examiner John W. Cabeca
`ASSistant Examiner Nasser Moazzami
`Attorney, Agent, or Firm-Arnold White & Durkee
`(57
`ABSTRACT
`A continuous media file is comprised of Stripe Sets over disk
`drives in one or more RAID sets. In a preferred embodiment,
`the RAID set includes n disk drives. The data storage of each
`disk drive in the RAID set is partitioned into an integer
`number m of hyper-volumes, and the parity is Stored in one
`hyper-volume of each of m disk drives in the RAID set. The
`Stripe Set includes a Series of transfer units of data in
`respective ones of the disk drives. Each transfer unit
`includes an integer number i of data blockS. and each
`inclu
`leg
`per
`s
`hyper-volume includes an integer numberk of transfer units.
`Each stripe set includes (m)(n-1) transfer units of data. The
`transfer units of the RAID set are allocated for the storage
`of continuous media data in a right-to-left and then top-to
`bottom order in which the transfer units appear in an m row
`by n column matrix in which the rows of the matrix
`represent parity groups of hyper-volumes in the disk drives
`and the columns of the matrix represent Storage in the
`respective disk drives. At most one write access to each
`parity hyper-volume need be performed during write acceSS
`to a Stripe Set. Parity changes for the data being written are
`accumulated in non-volatile memory, and written to the
`RAID set after completion of the writing of the data
`p
`9.
`
`12 Claims, 36 Drawing Sheets
`
`40
`y
`
`52s
`f
`
`APE
`LIBRARY
`
`51
`50
`"E"HE
`
`SCSI
`READ, WRITE
`| STATION | ADAPTER
`
`READ, WRITE | SCSI
`STATION
`ADAPER
`TAPESILO
`A
`24-f
`
`45
`
`47s
`7
`
`airs
`SCSI
`ADAPTER
`s
`
`26
`STREAM |--
`SERVER
`
`CACHE
`DSK
`ARRAY | MEMORY
`
`SCSI
`ADAPTER
`CACHEDDISKARRAY
`23
`
`STREAM
`SERVER
`21
`
`MEDIASERVER
`
`-20
`EPr"
`
`29
`CONTROLLER
`SERVER
`28
`CONTROLLERH
`SERVER
`
`- 31
`
`k
`
`30
`
`25
`NETWORK
`
`- 93
`
`54
`
`S
`
`- CLIENT #
`E3
`at
`SWITCH -qENT #3
`- cliENT AN
`
`DISH, Exh.1015, p.0001
`
`

`

`5,974,503
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,235,601 8/1993 Stallmo et al. ........................ 371/40.4
`5.255.270 10/1993 Yanai et al. .......
`... 371/10.2
`5,263,145 11/1993 Brady et al. ..
`... 395/425
`5,269,011 12/1993 Yanai et al. ...
`... 395/425
`5,274,799 12/1993 Brant et al. ...
`... 385/575
`5,276,860
`1/1994 Fortier et al. .....
`... 395/575
`5,276,867
`1/1994 Kenley et al. .......................... 395/600
`5,335,352 8/1994 Yanai et al. ............................. 395/800
`5,341,493 8/1994 Yanai et al. .......
`... 395/425
`5,367,698 11/1994 Webber et al. ...
`... 395/800
`5,371,532 12/1994 Gelman et al. ............................. 348/7
`5,381,539
`1/1995 Yanai et al. ............................. 395/425
`5,408,465 4/1995 Gusella et al. ............................ 370/17
`5,410,343 4/1995 Coddington et al. .
`... 348/7
`5,414,455 5/1995 Hooper et al. ...
`... 348/7
`5,442,390 8/1995 Hooper et al. .............................. 348/7
`5,442,749 8/1995 Northcutt et al.
`... 395/200.09
`5,442,771 8/1995 Filepp et al...........
`... 395/200.08
`5,477,263 12/1995 O'Callaghan et al. ..................... 348/7
`5,508,733 4/1996 Kassatly ...............
`... 348/13
`5,519,435 5/1996 Anderson ......
`... 348/8
`5,528,282 6/1996 Voeten et al. ............................... 348/7
`5,528,513
`6/1996 Vaitzblit et al. ..
`364/514 A
`5,530,557 6/1996 Asit et al. ............................... 358/342
`5,533,021
`7/1996 Branstad et al.
`... 370/60.1
`5,534,912 7/1996 Kostreski .................................... 348/6
`5,537,408 7/1996 Branstad et al. .......................... 370/79
`5,537.534 7/1996 Voigt et al. .......
`... 395/182.04
`5,539,660 7/1996 Blair et al. ........
`... 364/514 C
`5,544.313 8/1996 Shachnai et al
`... 395/200.01
`5,544,327 8/1996 Dan et al. ............................... 395/250
`5,544,345 8/1996 Carpenter et al.
`... 395/477
`5,544,347 8/1996 Yanai et al. .......
`... 395/489
`5,550,577 8/1996 Verbiest et al. ............................. 348/7
`5,550,982 8/1996 Long et al. .......
`... 395/200.13
`5,553,005 9/1996 Voeten et al. ....................... 364/514 R
`5,557,317 9/1996 Nishio et al. ............................... 348/7
`5,559,949 9/1996 Reimer et al.
`... 395/161
`5,572,660 11/1996 Jones .................
`... 395/182.04
`5,574,662 11/1996 Windrem et al. .
`... 364/514 R
`5,579,475 11/1996 Blaum et al. .....
`... 395/182.05
`5,583,561 12/1996 Baker et al. ................................ 347/7
`5,586.264 12/1996 Belknap et al. ..
`... 395/200.08
`5,594.910
`1/1997 Filepp et al............................. 395/800
`5,603,058 2/1997 Belknap et al. ..
`... 395/855
`5,606,359 2/1997 Youden et al. ...
`... 348/7
`5,625,405 4/1997 Dulac et al. .....
`... 348/7
`5,633,810 5/1997 Mandal et al. .......................... 364/514
`5,657,439 8/1997 Jones et al. ...
`... 395/182.05
`5,812,753 9/1998 Chiariotti ........................... 395/182.04
`OTHER PUBLICATIONS
`Gray et al., “Parity Striping of Disc Arrays: Low-Cost
`Reliable Storage with Acceptable Throughput, Technical
`Report 90.2, Tandem Computers, Cupertino, CA., Jan. 1990.
`Edward K. Lee, “Software and Performance Issues in the
`Implementation of a RAID Prototype.” Computer Science
`Division, EECS, University of California at Berkeley, CA,
`Mar. 1989.
`Sincoskie, WD, “System architecture for a large scale video
`on demand service,” Computer Networks and ISDN Sys
`tems, vol. 22, No. 2, Sep.1991, pp. 155-162.
`Tobagi FA, Pang J, "StarWorks (Trademark)-A video
`applications server.” Proceedings, IEEE COMPCON 93,
`San Francisco, Calif., 1993, pp. 4-11.
`Vaitzblit L., “The design and implementation of a high
`bandwidth file service for continuous media, Master's
`Thesis, Massachusetts Institute of Technology, Cambridge,
`Mass., Nov. 4, 1991.
`
`
`
`Patterson et al., “A Case for Redundant Arrays Of Inexpen
`sive Disks (RAID).” Report No. UCB/CSD 87/391, Com
`puter Science Division (EECS), University of California,
`Berkeley, California, Dec. 1987, pp. 1-24.
`Patterson et al., “Introduction to Redundant Arrays of Inex
`pensive Disks (RAID).” COMPCON 89 Proceedings, Feb.
`27-Mar. 3, 1989, IEEE Computer Society, pp. 112–117.
`Ousterhout et al., “Beating the I/O Bottleneck: A Case for
`Log-Structured File Systems,” Operating Systems Review,
`vol. 23, No. 1, ACM Press, Jan., 1989, pp. 11–28.
`Douglis et al., “Log Structured File Systems,” COMPCON
`89 Proceedings, Feb. 27-Mar. 3, 1989, IEEE Computer
`Society, pp. 124-129.
`Rosemblum et al., “The Design and Implementation of a
`Log-Structured File System.” ACM Transactions on Com
`puter Systems, vol. 1, Feb. 1992, pp. 26-52.
`M(aurice) William Collins, “A Network File Storage Sys
`tem,” IEEE Seventh Symposium on Mass Storage Systems,
`Nov. 4–7, 1985, Tuscon, AZ., pp. 1-11, Los Alamos Nat.
`Lab. No. LA-UR-85-3183.
`John H. Howard, “An Overview of the Andrew File Sys
`tem,” USENIX Winter Conference, Feb. 9-12, 1988, Dallas,
`TX, p. 23–26.
`John H. Howard et al., “Scale and Performance in a Dis
`tributed File System.” ACM Transactions on Computer
`Systems, vol. 6, No. 1, Feb. 1988, p. 51-81.
`David C. Steere et al., “Efficient User-Level File Cache
`Management on the Sun Vinode Interface,” USENIX Sum
`mer Conference, Jun. 11-15, 1990, Anaheim, CA, p.
`325-331.
`Matt Blaze et al., “Long-Term Caching Strategies for Very
`Large Distributed File Systems,” USENIX, Summer '91,
`Nashville, TN, p. 3-15.
`Thomas W. Page, Jr., et al., “Management of Replicated
`Volume Location Data in the Ficus Replicated File System,”
`USENIX, Summer 91, Nashville, TN, p. 17–29.
`Storage Computer Corporation, “High Performance, Fault
`Tolerant Disk Array Platform For File Servers And Com
`puter Systems,” 1991, Nashua, NH 12 pages.
`France Telecom, “TeleSauvegarde, 26 page paper dated
`Nov. 2, 1994 about work based on France Telecom patent
`application "Dispositifet Proceed de Sauvegaude a Distance
`de Donnees Numericues” Method and Apparatus for Safe
`guarding at a Distance Numeric Data, Institute National de
`la Propiete Industrielle, France, Applin. No. 93.12771, Oct.
`28, 1994 (filed Oct. 21, 1993), and partial English translation
`(15 pages).
`Krishnan Natarajan, “Video Servers Take Root,” IEEE
`Spectrum, Apr. 1995, IEEE, New York, NY, pp. 66–69.
`K. K. Ramakrishnan et al., “Operating System Support for a
`video-on-demand file service,” Multimedia Systems (1995)
`3:53-65.
`Ralf Steinmetz, “Analyzing the Multimedia Operating Sys
`tem.” IEEE MultiMedia, Spring 1995, pp. 68-84.
`Audrey Chou, “EMC, Computer-Storage Leader, Still
`Hears Footsteps.” The Wall Street Journal, Aug. 9, 1995,
`Dow Jones & Co., Princeton, N.J.
`Pardhu Vadlamudi, “EMC Hunts for Solution to Bottle
`necks.” InfoWorld, Apr. 15, 1996, #1590, San Mateo, CA
`944O2.
`Michael Goldberg, “EMC to Pump Data Over Networks,”
`Computerworld, Apr. 15, 1996.
`“EMC Moves Into Servers,” Broadcasting Cable, Apr. 15,
`1996.
`
`DISH, Exh.1015, p.0002
`
`

`

`5,974,503
`Page 3
`
`“Symmetrix Model 55XX Product Manual, P/N
`200-810–550 Rev D," EMC Corporation, Hopkinton,
`Mass., May 1994, pp. 1-236.
`“NFS: Network File System Protocol Specification,” RFC
`1094, Sun Microsystems, Inc., Mar. 1989, pp. 1-27.
`J. Case, M. Fedor, M. Schoffstall, J. Davin, “A Simple
`Network Management Protocol (SNMP).” May 1990, MIT
`Laboratory for Computer Science, Cambridge Mass., pp.
`1-35.
`Rangen PV, Vin HM, “Designing file systems for digital
`video and audio,” Proceedings of the 13th ACM Symposium
`on Operating Systems Principles, Monterey, Calif., 1991,
`pp. 81-94.
`Vin HM, Rangan PV, (1993) “Designing a multiuser HDTV
`storage server.” IEEE Journal on Selected Areas in Com
`munications, vol. 11, No. 1, Jan. 1993, pp. 153-164.
`Anderson DP, Osawa Y, Govindan R, “A file system for
`continuous media, ACM Transactions on Computer Sys
`tems, vol. 10, No. 4, Nov. 1992, pp. 311-337.
`
`Federighi C, “A Distributed Hierarchical Storage Manager
`for a Video-on-Demand System,” Department of Electrical
`Engr. and Computer Science, University of California, Ber
`keley, California, Dec. 1993.
`Haskins R, “The shark continuous-media file server.” Pro
`ceedings IEEE COMPCOM 93, San Francisco, Calif., 1993,
`pp. 12-15.
`Little TD, Rhanger G, Folz RJ, Gibbon JF, Reeve FW,
`Schelleng DH, Venkatesh D, “A digital on-demand video
`Service Supporting content based queries, Proceedings of
`ACM Multimedia 93, Anaheim, Calif., Aug. 1-6, 1993, pp.
`427-436.
`Lougher, P. Sheperd, D. “The design of a storage server for
`continuous media,” The Computer Journal, vol. 36, No. 1,
`1993, pp. 32–42.
`Rangan PV, Vin HM, Ramanathan S, “Designing an on-de
`mand multimedia service, IEEE Communications Maga
`zine, vol. 30, No. 7, Jul. 1992, pp. 56–64.
`
`DISH, Exh.1015, p.0003
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 1 of 36
`
`5,974,503
`
`
`
`DISH, Exh.1015, p.0004
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 2 of 36
`
`5,974,503
`
`Le62
`
`
`
`HITIOHLNOD
`
`ISOS>|HOLIMS.4INIWiv:AMOWSW||AVHYY
`
`
`
`L#IN3N9SsYIANASYaldvayFHOVIYXSIG
`pSiWaldvay
`N#LNAIN94WHS
`eGISOS
`|6OlfAVUYSIOBHOVO
`
`
`ze]ONYAVTSIOIsog|TALIWM/avaY
`oedaldvav)||NOLS
`
`HIAYASVIGIINoPhoe
`
`
`duvOSAIyHaldvdv]|NOLWLS
`
`
`
`uaiOuiNoDWildvay]|NOLVLSAdVL
`HaAYaSisos|(alum/avay
`
`<—_—_—_Tyaquasdaldvay
`
`
`WVIHLSISOS
`
`Lzsee
`SpveAv
`
`
`°AuVHaN
`
`
`isos|Tallum/avay
`
`
`
`O1IS3dVL
`
`DISH, Exh.1015, p.0005
`
`DISH, Exh.1015, p.0005
`
`
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 3 of 36
`
`5,974,503
`
`2
`
`TaNNYHOLH
`HOLOIHIC
`
`cvNG!
`
`HOLOAUIG}4}—H}4OLOINIG}H
`
`
`TaNNYHO¥Sid
`
`°e!e°eeeeeee°ee°
`
`ISOS
`
`ddldVav
`
`TANNVHO
`
`YOLOAYIG
`
`ISOS
`
`daldVdv
`
`HOLOaYIG-—+
`TANNYHO
`
`&Old
`
`DISH, Exh.1015, p.0006
`
`DISH, Exh.1015, p.0006
`
`
`
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 4 of 36
`
`5,974,503
`5,974,503
`
`Gem=.OZddVL
`
`09
`
`MYOMLAN
`
`
`
`TOYLNODous
`
`
`INJ9VLNSW39YNVr9dWNSJSf19
`
`
`
`AVYHYSICSCqgaH9v9
`pecan
`€9
`Y¥344iNg
`
`c9
`
`vOl
`
`JHOVO
`
`tc
`
`DISH, Exh.1015, p.0007
`
`DISH, Exh.1015, p.0007
`
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 5 of 36
`
`5,974,503
`
`79
`
`! /
`
`9/
`
`Z/
`
`SYS V STREAMS
`
`
`
`
`
`/ \ HN? ((N) NOE
`
`
`
`
`9///
`
`DISH, Exh.1015, p.0008
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 6 of 36
`
`5,974,503
`
`---
`
`NETWORK CLIENTS
`
`NFS
`FAP
`
`CM
`FAP
`
`FILE ACCESS
`PROTOCOLS 75
`71
`PHYSICAL
`E. SYSTEMS 79
`78
`
`CMFS
`BUFFER
`STORAGE
`
`
`
`80 - 47
`A.
`
`SLACKTIME - NOW
`
`ETA
`
`CMFS
`
`FIG. 6
`
`ETA,
`
`ETA m
`
`FIG. 8
`
`DISH, Exh.1015, p.0009
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 7 of 36
`
`5,974,503
`
`| 8
`
`
`
`
`
`
`
`&{3T003H0S QVEHHI98? 9NINGEHOS ;
`
`DISH, Exh.1015, p.0010
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 8 of 36
`
`5,974,503
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`91
`
`NETWORK
`CLIENT #1
`
`STREAM
`SERVER #1
`RAM
`
`STREAM
`SERVER #1
`
`9
`
`NETWORK
`CLIENT #1
`
`92
`
`NETWORK
`CLENT #2
`
`
`
`
`
`FIG. 13
`
`SERVER #2
`RAM
`
`DISH, Exh.1015, p.0011
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 9 of 36
`
`5,974,503
`
`PREFETCH
`TASK
`
`101
`
`
`
`
`
`
`
`
`
`S
`OBJECT
`A MQVIE
`
`FIND THE NEXT
`SEGMENT FOR
`THE MOVIE
`
`
`
`CONTINUE
`
`VIDEO PREFETCH
`(SEGMENT, SIZE)
`
`
`
`
`
`
`
`
`
`
`
`107
`
`REDUCE
`SEGMENT
`SIZE BYN
`
`
`
`DISH, Exh.1015, p.0012
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 10 of 36
`
`5,974,503
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`VIDEO
`PREFETCH
`
`
`
`IDENTIFY
`NEXT TRACK
`INSEGMENT
`
`
`
`IS
`TRACKN
`CACHE
`?
`
`REMOVE CACHE
`SLOT FROM THE HEAD
`OF THE REPLACEMENT
`OUEUE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`STAGE TRACK
`FROM DISK
`TO CACHE
`
`PUT REQUESTING
`PROCESS ON THE
`WAT LIST FOR
`THE TRACK
`
`
`
`
`
`MORE
`TRACKS TO
`PREFETCH
`
`RETURN
`
`FIG 11
`
`DISH, Exh.1015, p.0013
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 11 of 36
`
`5,974,503
`
`133
`
`34
`
`IDENTIFY
`NEXT TRACK
`INSEGMENT
`
`IS
`TRACK IN
`CACHE
`p
`
`
`
`TRANSFER TRACK
`FROM CACHE TO
`THE CHANNEL
`DIRECTOR BUFFER
`
`TRANSFER TRACK
`FROM THE CHANNEL
`DIRECTOR BUFFER
`TO THE STREAM
`SERVER
`
`REMOVE PROCESS
`FROM WAIT
`LIST
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`INSERT THE CACHE
`SLOT AT THE
`HEAD OF THE
`REPLACEMENT OUEUE
`
`
`
`
`
`MORE
`TRACKS TO
`FETCH
`
`DISH, Exh.1015, p.0014
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 12 of 36
`
`5,974,503
`
`PREFETCHTIME
`COMPUTATION
`
`141
`
`
`
`
`
`
`
`
`
`IS NEW
`REQUEST FOR
`SAME MOVIE AS AN
`EXISTING STREAM 1 NO
`p
`
`
`
`
`
`46
`YES
`FIND THE EXISTING STREAM HAVING
`A FETCHOR PRE-FETCH TIME
`CLOSEST TO THE FETCH TIME FOR
`THE NEW REQUEST
`147
`
`
`
`
`
`
`
`NEW REQUEST
`BEHND THE STREAM
`IN THE MOVE
`
`
`
`COMPUTE THE TIME DIFFERENCE
`(TA) BETWEENTHE FETCHTIME
`FOR THE NEW REQUEST AND THE
`PREFETCHTIME FOR THE
`EXISTING STREAM
`
`
`
`142
`
`
`
`143
`
`TA - TMIN
`
`
`
`
`
`
`
`
`
`NO
`
`CACHE
`RESOURCES
`AVAILABLE
`YES
`5SRNC 144
`RESOURCES
`AVAILABLE-1 No
`
`
`
`YES
`s
`
`T
`REJEC
`REQUEST
`
`-149
`COMPUTE THE TIME
`DIFFERENCE (TA) BETWEEN THE
`FETCHTIME OF THE EXISTING
`STREAM AND THE FETCHTIME
`OF THE NEW REQUEST
`
`F.G. 14
`
`DISH, Exh.1015, p.0015
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 13 of 36
`
`5,974,503
`
`151
`
`DISK
`RESOURCES
`AVAILABLE
`
`YES
`
`REJECTED
`GON REQUEST
`
`
`
`150
`
`CACHE
`RESOURCES
`AVAILABLE
`
`NO
`
`YES
`
`
`
`154
`DISK
`RESOURCES
`AVAILABLE
`?
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`COST OF
`DISKRESOURCES >
`COST OF CACHE
`RESOURCES
`
`
`
`
`
`
`
`
`
`
`
`
`
`RESOURCES
`AVAILABLE
`
`
`
`SET PREFETCH
`ADVANCE OF THE
`NEW REQUEST TOTA
`
`
`
`ACCEPT
`REQUEST
`
`
`
`
`
`
`
`
`
`157
`SCHEDULE TEMPORARY
`PREFETCHING FOR NEW
`REQUEST, ADVANCED BY
`TMINTO TERMINATE AT TA
`
`156
`
`IS
`THE NEW
`REQUEST BEHND THE
`STREAM IN THE
`MOVE
`
`YES
`
`SET PREFETCHADVANCE
`OF THE NEW REQUEST
`
`REJECT
`159
`REQUEST
`SCHEDULE TERMINATION OF PREFETCHING
`FOR EXISTING STREAM (ATTA) AND BEGIN
`MORE ADVANCED (BYTA) PREFETCHING
`FOR THE EXISTING STREAM
`
`145
`
`FIG. 15
`
`DISH, Exh.1015, p.0016
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 14 Of 36
`
`5,974,503
`
`FETCH
`-
`
`NETWORK
`CLIENTS
`
`91
`
`- CLIENT #1
`E CLIENT #2
`E CLIENT #3
`/ENZ
`/ MVE
`
`30%
`MOVE
`
`RAM
`
`92
`
`-
`
`PREFETCH
`--
`
`. .
`
`.
`
`-
`
`CLIENT #5
`CLIENT #6
`s - -E CLIENT #7
`DISK
`as
`STREAM
`CLIENT #8
`ARRAY
`MOVE
`SERVER #2
`RAM
`
`47
`
`. . . .
`
`93
`. CN.30% H CLENT #9
`DISK
`MOVIE -
`ARRAY NE CLIENT #10
`CACHE E CLENT #11
`41
`STREAM
`CLENT #12
`SERVER #3
`RAM
`
`94
`E. CLIENT #13
`30%
`CLENT #14
`F MOVIENE CLIENT #15
`
`siSE4
`CLENT #16
`RAM
`
`FG 16
`
`DISH, Exh.1015, p.0017
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 15 of 36
`
`5,974,503
`
`SERVICE
`NETWORK
`
`
`
`
`
`CLIENT
`REQUEST FOR
`POPULAR MOVE
`
`SET
`INDEXTO
`AVALID PC
`
`
`
`
`
`
`
`
`
`
`
`
`
`NEW
`REQUEST FALLS
`INTO WINDOW
`OF INDEXED
`PC 2
`
`
`
`
`
`
`
`
`
`
`
`
`
`DOES
`NDEXED PC
`HAVE SUFFICENT
`RESOURCES TO HANDLE
`THE REQUEST
`
`
`
`
`
`
`
`
`
`
`
`
`
`ASSIGN CLIENT
`REQUEST TO THE
`INDEXED PC
`
`
`
`172
`
`DO OTHER
`PROCESSES
`
`
`
`ADVANCE
`INDEX TONEXT
`VALID PC
`
`ALL
`VALID PC'S
`NSPECTED
`
`
`
`
`
`SERVER
`WINDOW RAM
`AVAILABLE
`YES
`ASSGN SERVER WINDOW
`RAM TO REQUESTED
`MOVE AND LOAD THE
`WINDOW RAM
`
`REECT
`REQUEST
`
`18O
`
`
`
`FIG. 17
`
`DISH, Exh.1015, p.0018
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 16 of 36
`
`5,974,503
`
`176
`
`ASSIGN CLENT
`REQUEST TO THE
`INDEXED PC
`
`191
`
`
`
`
`
`
`
`VERY
`POPULAR
`MOVE
`
`
`
`DETERMINE NO OF
`ADDITIONAL CLIENT
`REQUESTS THAT
`COULD BE SERVICED
`BY THE INDEXED PC
`
`
`
`
`
`
`
`NO, a
`URESHOLD-Jo
`YES
`SEARCH FOR ANOTHER
`SERVER PCHAVING
`AN UNALLOCATED RAM
`WINDOW AND THE MOST
`RESOURCES FOR
`SERVICING ADDITIONAL
`CLIENT REQUESTS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`196
`
`NITATE ATASK TO
`ASSIGN THE UNALLOCATED
`RAM WINDOW TO THE MOVIE
`AND LOAD THE RAM
`T
`WINDOW WITH DUPLICATE
`MOVE DATA
`
`FIG. 18
`
`DISH, Exh.1015, p.0019
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 17 Of 36
`
`5,974,503
`
`24
`
`CACHED
`DISK ARRAY
`
`FIG. 19
`
`STREAM
`SERVERS
`
`25
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CACHED
`DISKARRAY
`
`28,29
`
`l VOLUME
`7 MANAGER
`SCHEDULER
`CONTROLLER
`SERVER
`
`NETWORK
`CLIENTS
`
`STREAM
`SERVER
`
`DISH, Exh.1015, p.0020
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 18 of 36
`
`5,974,503
`
`D4
`
`D5
`
`D6
`
`D7
`
`222
`
`N--
`
`DISK DRIVE
`RAID SET
`220
`
`Fig. 21
`
`TRANSFER UNIT MAPPING TABLE
`TRANSFER UNIT INDEX DRIVE INDEX HYPER-VOL. INDEX
`
`
`
`- 230
`
`: g
`
`Fig.
`
`2 2
`
`DISH, Exh.1015, p.0021
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`WRITE
`SShi, NTU
`
`t ui OCygn)
`
`ntu - NTU 2"
`
`5
`
`242
`
`YES
`
`ETURN
`R
`
`NO
`
`243
`
`NO CD
`
`244
`
`Sheet 19 of 36
`
`5,974,503
`
`249
`READ OLD TRANSFER UNIT
`FROM DISKDRIVE (DI)
`BEGINNING AT SBA
`
`250
`ADD OLD TRANSFER UNIT
`TO THE PARTY BUFFER:
`PCBUFF -- PCBUFF GPC
`
`WRITE NEW TRANSFER
`UNIT TO DISKDRIVE (DI)
`BEGINNING AT SBA
`
`252
`ntu -- ntu - 1
`
`INDEXTRANSFER UNIT MAPPING
`TABLE WITH tui TO GET DRIVE
`INDEX (DI) AND HYPER-VOLUME
`INDEX (HV)
`
`247
`
`COMPUTE STARTING
`BLOCKADDRESS:
`SBA -- ((HVI) (k)+SSI) ()
`
`248
`LOAD NEW TRANSFER
`UNIT INTO THE PARITY
`BUFFER:
`PCBUFF
`
`TUNEW
`
`
`
`
`
`253
`
`YE
`<3d S
`NO
`
`254
`INDEXTRANSFER
`UNIT TABLE WITH
`tui TO GET DRIVE
`INDEX (DI)
`
`p
`
`255
`
`ADD NEW TRANSFER UNIT
`INTO THE PARTY BUFFER:
`PCBUFF
`PCBUFF GETUNEW
`
`Fig. 23
`
`(C)
`
`DISH, Exh.1015, p.0022
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 20 of 36
`
`5,974,503
`
`READ TRANSFER UNIT OF
`PARTY FROMDRIVE HV
`
`
`
`
`
`
`
`WAIT FOR COMPLETION OF WRITING
`OF NEW DATA FOR THE CURRENT
`TRANSFER UNIT PARTY GROUP
`
`ADD THE TRANSFER UNIT OF PARTY
`TO THE PARTY BUFFER:
`PCBUFF
`PCBUFF GE TUPARITY
`
`
`
`WRITE TRANSFER UNIT OF
`PARITY FROM THE PARITY
`BUFFER TO DRIVE HV
`
`
`
`
`
`DEALLOCATE PARITY BUFFER
`WHEN THE WRITING OF THE
`PARTY TO DRIVE HV HAS
`BEEN COMPLETED
`
`DISH, Exh.1015, p.0023
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 21 of 36
`
`5,974,503
`
`Fig. 25
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CLIP DIRECTORY
`
`CLIP D
`
`NO OF BLOCKS 1 BYTES
`OWNERSHIPINFO.
`LOCKING INFO.
`STRIPE SET LIST
`SS#; SS#, REM
`SS#; SShi, REM
`SS#; SSii, REM
`
`
`
`SS#; SS#, REM
`END OF LIST
`
`283
`
`Fig. 26
`
`Fig. 27
`
`FREE STRIPE SET LIST
`SS#; SSh
`SS#; SSh
`SS#; SSii
`
`O
`
`O
`
`SSii; SSif
`END OF LIST
`
`ACTIVE CLIENT LIST
`
`302
`CLIENT D
`STREAM SERVER ID
`PLAY LIST OF CLIPS
`CURRENT PLAYPOSITION
`
`
`
`DISH, Exh.1015, p.0024
`
`

`

`GE)—bs
`
`1st]LASAdIMLS33u4
`
`YSAMASYATIONLNOOD
`CNVAYOLOSUICdi19
`
`AYOLOAYIGLNAITO
`
`
`
`AW1dLNAYYND
`
`SLSITAV1dGNV
`
`SLSI1LASAdIMLS
`
`didS.LNAITOHOS
`
`LSiLASadIMLS
`
`
`
`YaANSSWVAYLS
`
`1sLasadiuls
`
`S.LNAIT0YOS
`
`di19LXAN
`
`LIN3YYND
`LINNYS4dSNVEL
`
`AdldLs
`
`Las
`
`
`
`A1EgVLONiddVN
`
`aiva
`
`LAS
`
`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 22 of 36
`
`5,974,503
`
`8¢
`
`Ic
`
`NOILISOd
`
`AVNASICGAHOVO 022
`
`DISH, Exh.1015, p.0025
`
`DISH, Exh.1015, p.0025
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 23 of 36
`
`5,974,503
`
`RECORD
`
`401
`
`OPEN RECORD
`
`Fig. 29
`
`
`
`
`
`
`
`
`
`CLOSE
`
`READY FOR
`RECORDING
`
`402
`
`STAR RECORD
`
`RECORDING - - - - - - - - -- CALLBACKS:
`403
`DISKO ERROR
`NETWORKO ERROR
`NO DISK SPACE
`
`PLAY
`
`
`
`
`
`401
`
`DLE
`
`OPEN - PLAY
`
`406
`
`READY FOR
`PLAYING
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`RESUME
`407
`PLAYING - - - - - - - - -- CALLBACKS:
`DISK/O ERROR
`NETWORK f OERROR
`CLIP COMPLETED
`PLAY LIST COMPLETED
`
`PAUSE
`4.08
`
`RESUME
`
`FAST
`FORWARD
`
`REWIND
`
`FAST
`REVERSE
`
`409 FAST
`FAST
`REVERSE
`FORWARD
`PAUSE CLOSE
`
`Fig. 30
`
`DISH, Exh.1015, p.0026
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 24 of 36
`
`5,974,503
`
`OPEN PLAY
`COMMAND
`
`351
`
`
`
`
`
`SERVER
`N ANDLE
`STATE FOR
`CLENT
`
`NO
`
`352
`RETURNERROR CODE INDICATING
`THAT THE SERVER IS NOT IN AN
`DLE STATE FOR THE CLENT
`
`YES
`
`353
`ATTEMPT TO ALLOCATE
`SERVER RESOURCESTO
`MAKE THE STREAM
`READY FOR PLAYING
`
`CONTINUE
`
`
`
`354
`
`RESOURCES
`ALLOCATED
`
`YES
`
`CLP
`IN ARCHIVE
`AND NOT ON
`DISK
`?
`YES
`
`WAIT
`OPTION
`SELECTED
`
`356
`
`
`
`358
`
`
`
`
`
`355
`RETURNERROR
`NO | CODE INDICATING
`INSUFFICIENT
`RESOURCES
`
`DLESTATE
`
`GF)
`NO
`
`357
`RETURN CALLBACK THAT
`COMMAND HAS COMPLETED
`SUCCESSFULLY, INCLUDING
`A STREAM HANDLE
`
`359
`No RETURNERROR
`CODE INDICATING
`CLIP S IN ARCHIVE
`AND NOT ON DISK
`
`YES
`
`360
`RETURN STATUS CODE
`INDICATING RETRIEVAL
`FROMARCHIVE
`
`IDLE STATE
`
`READY FOR
`PLAYING
`
`ARCHIVE TO DISK
`
`361
`
`G
`
`Fig. 31
`
`
`
`
`
`
`
`DISH, Exh.1015, p.0027
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 25 of 36
`
`5,974,503
`
`PAUSE
`COMMAND
`
`371
`
`373
`
`
`
`PROPER
`STATE
`p
`
`NO
`
`
`
`
`
`YES
`
`PAUSE
`ONLY OR VCR
`CONTROLS
`
`NO
`
`
`
`
`
`YES
`
`372
`RETURNERROR CODE
`INDICATING THAT THE
`CLIENT'S STREAMS
`NOT INA PROPER
`STATE
`
`374
`RETURNERROR CODE
`INDICATING PAUSE IS
`NOT PERMITTED BY
`THE SELECTED
`OPTION
`
`CONTINUE
`
`CONTINUE
`
`SEND PAUSE COMMAND TO THE 375
`ASSIGNED STREAM SERVER
`
`RECEIVE THE CURRENT BLOCK
`OFFSET FROM THE ASSIGNED
`STREAM SERVER
`
`376
`
`
`
`
`
`CONVERT THE CURRENT
`BLOCK OFFSET TO A TIME
`POSITION WITHIN THE CLIP
`
`377
`
`RETURN THE TIME
`POSITION TO THE CLIENT
`
`378
`
`PAUSED
`
`Fig. 32
`
`DISH, Exh.1015, p.0028
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 26 of 36
`
`5,974,503
`
`PLAYING
`
`381
`
`
`
`
`
`END OF
`PLAY-LIST
`
`NO
`
`CONTINUE
`PLAYING
`
`YES
`
`382
`RETURN CALLBACK TO
`CLIENT INDICATING
`PLAY LIST IS FINISHED
`
`
`
`
`
`
`
`383
`
`
`
`LOOP
`FLAG SET
`
`NO
`
`384
`RESET PLAY-LIST
`YES POINTER TO THE
`HEAD OF THE
`PLAY-LIST
`
`CONTINUE
`PLAYING
`
`385
`
`AUTO - CLOSE
`FLAG SET
`
`
`
`YES
`
`386
`CLOSE STREAM
`
`DLE STATE
`
`NO
`
`387
`SET AND ACTIVATE TIMER
`
`(G)
`
`
`
`
`
`
`
`
`
`CLIENT
`RESPONSE
`
`YES
`
`389
`EXECUTE CLIENT
`RESPONSE
`
`CONTINUE
`
`390
`
`
`
`
`
`TIMER
`EXPRED
`YES
`
`Fig. 33
`
`DISH, Exh.1015, p.0029
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 27 of 36
`
`5,974,503
`
`CLIENT
`
`
`
`
`
`CLIENT SENDS A
`"CREATE SESSION"
`COMMAND TO THE
`SERVER
`
`
`
`CREATE
`SSESSION
`
`w
`
`423 SESSION
`HANDLE -
`
`CLIENT RECEIVES THE
`SESSION HANDLE AND
`USES IT TO SEND ONE
`ORMORE "EDITSESSION"
`COMMANDS TO THE
`SERVER TOADD ONE OR
`MORE CLIPS TO THE
`PLAY-LIST
`
`
`
`
`
`
`
`VIDEO FILE SERVER
`
`SERVER CREATES A
`SESSION AND PLAY-LIST FOR
`THE CLIENT AND RETURNS
`A SESSION HANDLE
`
`EDIT
`SESSION
`
`
`
`
`
`PLAY
`LIST
`-
`
`---
`
`SERVER ADDS ONE OR
`MORE CLPS TO THE
`PLAY-LIST IN RESPONSE
`TO THE "EDITSESSION"
`COMMANDS FROM THE
`CLIENT
`
`CLENT SENDS A
`"RESUME SESSION" lar
`COMMAND TO THE
`SERVER TO BEGIN
`PLAY OF THE
`PLAY-LIST
`
`RESUME
`-- SESSION
`
`N
`
`
`
`
`
`
`
`
`
`
`
`SERVER BEGINS PLAY
`OF THE PLAY-LIST AND
`TRANSMITS DATA FROM
`THE FIRST CLP N THE
`PLAY-LIST TO THE CLIENT'S
`SPECIFIED DESTINATION
`
`FIG. 35
`
`Fig. 34
`
`FIG. 35
`
`DISH, Exh.1015, p.0030
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 28 of 36
`
`5,974,503
`
`FROM
`FG.34
`--
`
`FROM
`FIG.34
`--
`
`
`
`
`
`
`
`
`
`SERVER ISSUES A
`CALLBACK TO THE
`CLENT EACHTIME
`TRANSMISSION FROM
`A CLIP S COMPLETED
`
`
`
`
`
`PLAY- -
`LIST /
`/
`
`SERVER ADDS OR
`REMOVES CLPS
`CLIENT SENDS MORE /
`FROM THE PLAY
`EDIT
`"EDITSESSION"
`SESSION | LIST DURING PLAY
`COMMANDS TO THE
`SERVER TO ADD OR - - - - - - - - - - -
`IN RESPONSE TO
`REMOVE CLPS
`THE "EDITSESSION"
`FROM THE PLAY-LIST M
`COMMANDS FROM
`DURING PLAY
`y
`THE CLIENT
`y
`
`
`
`END OF
`SESSION
`
`W
`w
`
`w y
`DESTROYv
`SESSION y
`
`
`
`
`
`
`
`
`
`PLAY-ST
`EMPTY FOR MORE
`THAN TIMEOUT
`PERIOD
`
`
`
`SERVER DESTROYS
`THE SESSION
`
`END OF
`SESSION
`
`Fig. 35
`
`DISH, Exh.1015, p.0031
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 29 of 36
`
`5,974,503
`
`BROADCAST
`SESSION
`
`CREATE SESSION
`
`441
`
`
`
`
`
`DESTROY
`SESSION
`
`442
`
`SESSION
`CREATED
`
`EDIT SESSION
`
`RESUME SESSION
`
`DESTROY
`SESSION
`
`
`
`443
`
`SESSION
`PLAYING
`
`EDITSESSION
`
`RESUME SESSION
`
`PAUSE SESSION
`
`DESTROY
`SESSION
`
`
`
`445
`
`SESSION
`PAUSED
`
`EDITSESSION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fig. 36
`
`DISH, Exh.1015, p.0032
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 30 0f 36
`
`5,974,503
`
`EDITSESSION
`COMMAND
`
`451
`
`YES
`
`453
`
`
`
`
`
`SESSION
`PLAYING
`
`452
`
`
`
`NO
`
`
`
`
`
`RETURNERROR
`CODE INDICATING
`THAT THE SESSION
`DOES NOT EXIST
`
`CONTINUE
`
`
`
`COMPUTE DIFFERENCE
`BETWEEN THE EARLIEST
`TIME OF CONTINUOUS
`MEDIATO BE ADDED TO
`OR DELETED FROM THE
`PLAY-LIST, AND THE
`CURRENT TIME
`
`
`
`
`
`
`
`
`
`
`
`
`
`RETURNERROR CODE
`INDICATING THAT THE
`EDIT IS TOO CLOSE TO
`BROADCAST TIME TO
`AVOD INTERRUPTION
`
`EDIT THE
`PLAY-LIST
`
`454
`
`RETURN THE
`EDITED PLAY - LIST
`
`45.5
`
`CONTINUE
`
`Fig. 37
`
`DISH, Exh.1015, p.0033
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 31 of 36
`
`5,974,503
`
`CONTROLLER
`SERVER
`
`READ EPHEMERAL
`ATOMIC STATE
`INCLUDING MIS
`FLAG FROM THE
`CACHED DISKARRAY
`
`
`
`
`
`
`
`
`
`M/S
`FLAG
`SETICLEARED
`
`
`
`
`
`
`
`
`SLAVE
`CONTROLLER
`ROUTINE
`
`MASTER
`CONTROLLER
`ROUTINE
`
`Fig. 38
`
`DISH, Exh.1015, p.0034
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 32 of 36
`
`5,974,503
`
`SLAVE
`CONTROLLER
`ROUTINE
`
`52
`
`NO
`MASTER
`HEARTBEAT
`WITHIN TIMEOUT
`PERIOD
`
`YES
`
`MASTER
`REPORTING
`FAILURE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`523
`LOG THE FAILURE
`NTO THE CACHED
`DISKARRAY
`
`524
`SETICLEAR THE
`M/S FLAG IN THE
`CACHED DISK
`ARRAY
`
`525
`WAIT A SUFFICIENT
`AMOUNT OF TIME
`FOR THE OTHER
`CONTROLLERTO
`FINISH ANY WRITE
`BACK OF EPHEMERAL
`ATOMIC STATUS
`
`
`
`526
`PERFORMA RECOVERY
`OPERATION AND
`INITIALIZE THE STATE OF
`THE CONTROLLER SERVER
`TO ASSUME MASTER
`CONTROLLER STATUS
`
`Fig. 39
`
`RETURN
`
`DISH, Exh.1015, p.0035
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 33 of 36
`
`5,974,503
`
`MASTER CONTROLLERROUTINE
`
`531
`
`
`
`
`
`WRITE
`PENDING TO
`CACHED DISK
`ARRAY
`
`532
`
`PERFORM WRITE
`BACK TO THE
`CACHED DISKARRAY
`
`534
`
`LOGERRORIN
`CONTROLLER
`CACHE AND
`INITIATE STREAM
`SERVER RECOVERY
`
`
`
`
`
`
`
`
`
`537
`PERFORMA NEXT TRANSACTION
`TOWARDS RECOVERING FROM
`STREAM SERVER FAILURE
`
`533
`
`
`
`
`
`
`
`FAILURE
`TO RECEIVE
`STREAM SERVER
`HEARTBEAT
`1.
`
`
`
`535
`
`STREAM
`SERVER REPORTING
`FAILURE
`
`536
`
`STREAM
`SERVER RECOVERY
`N PROGRESS
`
`
`
`
`
`538
`
`
`
`CLIENT
`REGUEST
`OUTSTANDING
`p
`
`YES
`
`539
`PERFORMA NEXT TRANSACTION
`TOWARDS SATISFYING THE
`CLENT REQUEST
`
`
`
`NO
`
`Fig. 40
`
`DISH, Exh.1015, p.0036
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 34 of 36
`
`5,974,503
`
`TRANSPARENT
`FAILOVER
`
`CLIENT
`CONTROL
`FAILOVER
`
`
`
`
`
`
`
`STREAM
`SERVER
`RECOVERY
`
`551
`
`
`
`
`
`
`
`NEXT
`AFFECTED
`STREAM
`?
`
`
`
`
`
`
`
`TRANSPARENT
`FAILOVER
`2
`
`554
`
`
`
`
`
`
`
`CLENT
`CONTROL
`FAILOVER
`
`
`
`
`
`
`
`TERMINATE
`THE STREAM
`
`SEND MESSAGE
`TO CLIENT THAT
`THE STREAM HAS
`BEEN TERMINATED
`
`
`
`DE-ALLOCATE
`STREAM STATUS
`AND POSITION
`
`
`
`Fig. 41
`
`DISH, Exh.1015, p.0037
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 35 0f 36
`
`5,974,503
`
`TRANSPARENT
`FAILOVER
`
`
`
`
`
`
`
`
`
`SEND AMESSAGE
`TO THE CLIENT OF
`THEAFFECTED
`STREAM NFORMING
`OF THE FAILOVER
`
`BACK-UP THE
`POSITION OF THE
`AFFECTED STREAM
`
`
`
`ASSIGNA NEW
`STREAM SERVER
`TO THE AFFECTED
`STREAM
`
`RE-ROUTE THE
`AFFECTED STREAM
`FROM ITS NEW
`STREAM SERVER
`TO ITS RESPECTIVE
`CLIENT'S DESTINATION
`
`RE-ESTABLISH
`TRANSMISSION OF
`THE AFFECTED
`STREAM FROM TS
`NEW STREAM SERVER
`
`
`
`
`
`
`
`Fig. 42
`
`DISH, Exh.1015, p.0038
`
`

`

`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 36 of 36
`
`5,974,503
`
`
`
`
`
`
`
`CLENT
`CONTROL
`FAILOVER
`
`TERMINATE THE
`AFFECTED STREAM
`
`SEND MESSAGE
`TO CLIENT THAT
`THE STREAM HAS
`BEEN TERMINATED
`
`FAILOVER
`REOUEST FROM
`CLIENT
`?
`
`YES
`
`
`
`
`
`
`
`
`
`
`
`
`
`DE-ALLOCATE
`STREAM STATUS
`AND POSITION
`
`
`
`RE-ESTABLISH
`STREAM FROM
`PORT SPECIFIED
`BY THE CLIENT
`
`
`
`Fig. 43
`
`DISH, Exh.1015, p.0039
`
`

`

`1
`STORAGE AND ACCESS OF CONTINUOUS
`MEDIA FILES INDEXED AS LISTS OF RAID
`STRIPE SETS ASSOCIATED WITH FILE
`NAMES
`
`RELATED APPLICATIONS
`The present application is a continuation of provisional
`application Serial No. 60/044,948 filed Apr. 25, 1997 by
`Dinesh Venkatesh, Wayne W. Duso, John Forecast, Uday
`Gupta, Uresh K. Vahalia, and Dennis P. J. Ting, entitled
`“Raid Striping, Client-Server Protocols, and Failover Ser
`vices for a Video File Server.’
`
`AUTHORIZATION PURSUANT TO 37 C.F.R S
`1.17(e)
`A portion of the disclosure of this patent document
`contains command formats and other computer language
`listings all of which are Subject to copyright protection. The
`copyright owner, EMC Corporation, has no objection to the
`facsimile reproduction by anyone of the patent document or
`the patent disclosure, as it appears in the Patent and Trade
`mark Office patent file or records, but otherwise reserves all
`copyright rights whatsoever.
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention relates generally to a data Storage
`System employing a redundant array of disk drives (RAID),
`and more particularly