United States Patent [19J
`Kisor
`
`I 1111111111111111 11111 1111111111 111111111111111 1111111111111111 Ill lllll llll
`US006098091A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,098,091
`*Aug. 1, 2000
`
`[54] METHOD AND SYSTEM INCLUDING A
`CENTRAL COMPUTER THAT ASSIGNS
`TASKS TO IDLE WORKSTATIONS USING
`AVAILABILITY SCHEDULES AND
`COMPUTATIONAL CAPABILITIES
`
`[75]
`
`Inventor: Greg Kisor, Beaverton, Oreg.
`
`[73] Assignee: Intel Corporation, Santa Clara, Calif.
`
`OTHER PUBLICATIONS
`
`Lizkow, M., et al., "Condor-A Hunter of Idle Worksta(cid:173)
`tions," Proc. of the 8th Int'l. Conf. On Distributed Comput(cid:173)
`ing Systems, IEEE, pp. 104-111, Jun. 1998.
`
`Theimer, M., et al., "Finding Idle Machines in a Worksta(cid:173)
`tion-Based Distributed System," IEEE Trans. on Software
`Engineering, vol. 15, No. 11 pp. 1444-1458., Nov. 1989.
`
`[ *] Notice:
`
`This patent issued on a continued pros(cid:173)
`ecution application filed under 37 CFR
`1.53( d), and is subject to the twenty year
`patent term provisions of 35 U.S.C.
`154(a)(2).
`This patent is subject to a terminal dis(cid:173)
`claimer.
`
`[21] Appl. No.: 08/777,024
`
`[22] Filed:
`
`Dec. 30, 1996
`
`[51]
`
`Int. Cl.7
`
`G06F 15/16; G06F 9/00
`
`[52]
`[58]
`
`[56]
`
`U.S. Cl. ........................... 709/202; 709/102; 709/100
`Field of Search ......................... 395/200.54, 200.32,
`395/674; 709/202, 224, 104, 100, 102,
`103
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5/1989 Shear .......................................... 380/4
`4,827,508
`4,969,092 11/1990 Shorter ........... .... ......... ... ......... 709/102
`5,025,369
`6/1991 Schwartz ................................. 709/102
`5,109,512
`4/1992 Bahr et al. .............................. 395/673
`....................... 709/103
`8/1992 Lapourte et al.
`5,136,708
`5,341,477
`8/1994 Pitkin et al. ....................... 395/200.33
`................. 395/200.54
`4/1995 Sekizawa et al.
`5,410,651
`5,522,070
`5/1996 Sumimoto ............................... 395/674
`5,568,375 10/1996 Rausch .................................... 364/131
`1/1998 Dedrick ....................... ....... 395/200.47
`5,710,884
`5,758,077
`5/1998 Danahy et al.
`.................... 395/200.31
`5,758,345
`5/1998 Wang ...................................... 707/100
`6/1998 Choquier et al. ....... ... ........ 395/200.53
`5,774,668
`5,815,665
`9/1998 Teper et al. ........................ 395/200.59
`5,881,284
`3/1999 Kubo ....................................... 709/100
`5,964,832 10/1999 Kisor .............. .... ......... ... ......... 709/202
`
`(List continued on next page.)
`
`Primary Examiner-Zarni Maung
`Assistant Examiner-Andrew Caldwell
`Attorney, Agent, or Firm-Blakely, Sokoloff, Taylor &
`Zafman LLP
`
`[57]
`
`ABSTRACT
`
`A method and system for assigning tasks to peer-to-peer
`computers connected via a wide area network. The system
`includes a central computer and one or more remote com(cid:173)
`puters. The central computer and the remote computers
`operate in one of a pluralility of relationships, including a
`subscriber relationship and a contractor relationship. In the
`subscriber relationship, the central computer determines
`whether a remote computer still subscribes to an Internet
`Service Provider (ISP) and bills the remote computer
`accordingly. In the contractor relationship, the central com(cid:173)
`puter polls each remote computer to inquire about the
`available times when the remote computer is idle and the
`computational capabilities of the remote computer. The
`central computer then executes an assignment or scheduling
`program to assign tasks to idle remote computers for pro(cid:173)
`cessing. After the idle remote computers finish processing
`the assigned tasks, the central computer credits a payment to
`the remote computer. In one embodiment, the remote com(cid:173)
`puter disconnects from the network while processing the
`assigned task and periodically reconnects to transmit status
`reports to the central computer.
`
`27 Claims, 6 Drawing Sheets
`
`4zl CR:}::s~~~~:':fTZ~~7::;~:::·~:::t
`®
`
`I
`
`Netflix, Inc. - Ex. 1008, Page 000001
`IPR2022-00322 (Netflix, Inc. v. CA, Inc.)
`
`

`

`6,098,091
`Page 2
`
`OIBER PUBLICATIONS
`
`Clark, H., et al., "DAWGS-ADistributed Computer Server
`Utilizing Idle Workstations," Proc. of the 5th Distributed
`Memory Computing Conf., IEEE, pp. 732-741, 1990.
`Blumofe, R, et al., "Scheduling Large-Scale Parallel Com(cid:173)
`putations on Networks of Workstations," Proc. of the 3rd
`IEEE Int'l. Symp. on High Performance Distributed Com(cid:173)
`puting, pp. 96-105, Aug. 1994.
`Celenk, M., et al., "Parallel Task Execution in LANs and
`Performance Analysis," Proc. of the 1995 IEEE 14th Annu(cid:173)
`nal Int'l. Phoenix Conf. on Computers and Communica(cid:173)
`tions, pp. 423-429, Mar. 1995.
`Kremien, 0., "Buying and Selling Computational Power
`Over the Network," Proc. of the 4th Int'l. Conf. on Com(cid:173)
`puter Communications and Networks, IEEE, pp. 616-619,
`Sep. 1995.
`Chen, C., et al., "The DEC: Processing Scientific Data Over
`the Internet," Proc. of the 16th Int'l. Conf. on Distributed
`Computing Systems, pp. 673-679, May 1996.
`
`Shiuan, J. et al., "Client-Server Based Ray-Tracer Using
`ASTRA: an Asynchronous RPC Mechanism," Computer
`Communications, vol. 19, No. 5, 445-455, May 1996.
`
`Tandiary, F., et al., "Batrun: Utilizing Idle Workstations for
`Large-Scale Computing," IEEE Parallel & Distributed
`Technology: Systems and Applications, vol. 4, No. 2, pp.
`41-48, Aug. 1996.
`
`Morris, J., et al., "Fault Tolerant Networks of Workstations,"
`Proc. of the 3rd Int'l. Conf. on High Performance Comput(cid:173)
`ing, IEEE, pp. 271-276, Dec. 1996.
`
`Waldspurger, C., et al., "Spawn: A Distributed Computa(cid:173)
`tional Economy," IEEE Trans. on Software Engineering,
`vol. 18, No. 2, pp. 103-117, Feb. 1992.
`
`Derfler, F., et al., "How Networks Work," Ziff-Davis Press,
`pp. 141-163, 1996.-
`
`Netflix, Inc. - Ex. 1008, Page 000002
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 1 of 6
`
`6,098,091
`
`112
`
`REMOTE
`
`(cid:143)
`
`0
`0
`
`SUN® MICR011
`
`116
`
`REMOTE
`
`0
`0
`
`(cid:143)
`
`APPLE ®
`MACINTOSH111
`
`100
`
`~
`
`108
`
`REMOTE
`
`(cid:143)
`
`0
`0
`
`IBM® PCri.
`
`MODEM
`
`140
`
`136
`
`MODEM
`CENTRAL
`COMPUTER
`
`104
`
`128
`
`PROGRAM
`144
`
`~
`
`KEYBOARD
`122
`
`RAM
`
`PC
`
`g
`
`g;J
`
`II II II ' 00 I
`
`0
`0
`
`HARD DRIVE
`132
`
`100+ MILES
`
`PROCESSOR
`134
`
`120
`
`REMOTE
`
`0
`0
`
`(cid:143)
`
`INTEL® PCr.
`
`FIG. 1
`
`Netflix, Inc. - Ex. 1008, Page 000003
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 2 of 6
`
`6,098,091
`
`(cid:143) 204
`
`0
`0
`
`MODEM
`
`212
`
`216
`
`220
`
`MODEM
`
`(cid:143) 208
`
`0
`0
`
`228
`
`SCHEDULER
`
`232
`
`TASKS TOBE
`COMPLETED
`
`227
`
`RESOURCES
`AVAILABLE
`
`224
`
`RESOURCES
`AVAILABLE
`
`FIG. 2
`
`Netflix, Inc. - Ex. 1008, Page 000004
`
`

`

`00 = \0
`0--, = \0
`
`~
`
`~
`
`O'I
`0 ....,
`~ ....
`'JJ. =(cid:173)~
`
`t
`
`0
`0
`0
`N
`!'"'
`
`~ = ......
`
`~ ......
`~
`r:JJ. .
`d .
`
`45 sec.
`
`-
`
`1 hr. 10 sec.
`
`1 hr. 15 min.
`
`FIG. JA
`
`16
`
`28
`
`25
`
`30
`
`5
`
`2
`
`3
`
`1
`
`TASK AT GIVEN !COMP
`TIME TO COMPLETE
`
`(E.G. !COMP)
`BENCHMARK RA TING
`
`PRIORI7Y
`
`HARD DRIVE
`STORE INFO. ON
`
`WEB SITE SOURCE
`
`COMPRESSION
`PEG
`
`~
`
`~
`
`-~
`
`COMPRESSION
`MPEG
`
`-~
`~ TASKS TO BE
`
`COMPLETED
`
`1::29
`
`SCHEDULER
`
`328
`
`324
`
`1312
`
`3.
`
`3
`
`3
`
`3
`
`313
`
`Netflix, Inc. - Ex. 1008, Page 000005
`
`

`

`00 = \0
`0--, = \0
`
`~
`
`~
`
`°'
`0 ...,
`~ ....
`'J). =(cid:173)~
`
`t
`
`0
`0
`0
`N
`:-'
`
`"""'" ~ = """'"
`
`~
`~
`
`r:JJ. .
`d .
`
`FIG. 38
`
`s
`
`1 Gb
`
`32Mb
`
`PROCESSOR
`
`PENTIUM
`
`35
`
`DATA
`OTHER
`
`BANDWIDTH
`TRANSMISSION
`
`TO BACKBONE
`#OF HOPS
`
`MEMORY
`
`RAM
`
`PROCESSOR
`
`(E.G.ICOMP)
`
`RATING
`
`BENCHMARK
`
`9-Sp.m.
`MONDAY
`
`TIME)
`
`(GREENWICH
`AVAILABLE
`
`TIME
`
`'47
`
`340
`
`338
`
`~ 336
`
`308
`
`NUMBER
`TELEPHONE
`
`OR
`
`NUMBER
`SERIAL
`
`COMPUTER
`ID
`
`IDENTIFIER
`COMPUTER
`
`'I\
`
`332
`
`SCHEDULER JMt
`
`Netflix, Inc. - Ex. 1008, Page 000006
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 5 of 6
`
`6,098,091
`
`START
`
`POLL REMOTE COMPUTERS TO DETERMINE
`TIMES OF DAY AVAILABLE AND SPECIFICATIONS
`
`ORGANIZE TASKS TO BE COMPLETED IN ORDER OF
`PRIORITY AND REMOVE COMPUTER AVAILABILITY
`
`ASSIGN PARTICULAR TASKS TO PARTICULAR REMOTE
`COMPUTERS TO BEGIN AND END AT TIMES WITHIN
`WHICH THE REMOTE COMPUTER IS AVAILABLE
`
`404
`
`408
`
`412
`
`416
`
`428
`
`420
`
`REASSIGN AND
`RETRANSMIT TASK
`TO BACK-UP REMOTE
`COMPUTER
`
`NO
`
`432
`
`436
`
`AT SCHEDULED TIME CONNECT VIA
`INTERNET TO REMOTE COMPUTER AND
`TRANSMIT INSTRUCTIONS AND DATA
`
`DISCONNECT FROM REMOTE COMPUTER
`
`AT COMPLETION OF TASI( RECONNECT AND
`INSTRUCT REMOTE COMPUTER TO STORE OR
`TRANSMIT PROCESSED INFORMATION
`
`CREDIT REMOTE COMPUTER FOR PROCESSING TIME
`AND STORAGE SPACE USED TO COMPLETE TASK
`
`FIG. 4
`
`END
`
`Netflix, Inc. - Ex. 1008, Page 000007
`
`

`

`U.S. Patent
`
`Aug. 1, 2000
`
`Sheet 6 of 6
`
`6,098,091
`
`FIG. 5
`
`CENTRAL COMPUTER SENDS A TASK
`REQUEST TO MANAGEMENT PROGRAM
`
`MANAGEMENT PROGRAM CHECKS
`RESOURCE TABLE FOR CONNECTED
`REMOTE COMPUTERS
`
`504
`
`508
`
`520
`
`JS THERE A REMOTE
`COMPUTER THAT IS CONFIGURED
`TO HANDLE TASK?
`
`516
`
`MANAGEMENT PROGRAM VERIFIES
`WHICH COMPUTERS CAPABLE OF
`HANDLING THE TASK USING
`RESOURCE TABLE
`
`524
`
`NOTIFY CENTRAL COMPUTER
`THAT UNABLE TO
`HANDLE TASK AND TO
`TRY AGAIN LATER
`
`QUERY COMPUTERS IF AVAILABLE
`
`STOP
`
`528
`
`532
`
`PICK A COMPUTER BASED ON
`"COST" AND ''SPEED" EFFICCIENCY
`
`534
`
`IN SCHEDULER LOG TABLE ENTRY
`FOR PICKED REMOTE COMPUTER AND
`ALLOCATE COMPUTER TO TASK
`
`538
`
`SEND TASK DEFINITION
`TO REMOTE COMPUTER
`
`NO
`
`NO
`
`YES
`
`550
`
`UPDATE SCHEDULER,
`TRANSMIT RESULTS TO
`CENTRAL COMPUTER
`
`STOP
`
`Netflix, Inc. - Ex. 1008, Page 000008
`
`

`

`6,098,091
`
`1
`METHOD AND SYSTEM INCLUDING A
`CENTRAL COMPUTER THAT ASSIGNS
`TASKS TO IDLE WORKSTATIONS USING
`AVAILABILITY SCHEDULES AND
`COMPUTATIONAL CAPABILITIES
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`The present invention relates generally to a management
`system for managing a distributed system of Internet com(cid:173)
`puters connected via the Internet or similar Wide Area
`Network. More particularly, the present invention relates to
`apportioning tasks among personal computers connected via
`wide area networks. The invention is particularly relevant to
`assigning tasks to personal computers at the time of day in 15
`which the personal computers would otherwise be idle.
`2. Description of the Related Art
`In recent years, wide area networks ("WAN") have
`become an important part of the day to day lives of many 20
`computer owners. Every day millions of users connect to the
`most well known WAN, the Internet. Nearly every personal
`computer ("PC") user having a modem and a telephone line
`can access the Internet for little cost through commercial
`companies that provide a gateway to the Internet. Personal 25
`computers operate in a subscriber relationship with a central
`computer provided by the company providing the gateway
`to the Internet wherein the personal computer receives data
`and computing services from the central computer in
`exchange for paying a charge. Internet services include 30
`E-Mail, database access, and news groups. The Internet also
`acts as a service medium for many companies trying to
`market products.
`Many of the personal computers which are connected to
`WANs are high powered personal computers which may
`contain microprocessors, such as the Intel Pentium® or
`PentiumPro TM microprocessor. These personal computers
`may also include RAM memory, a display unit, long-term
`storage such as a hard disk drive, and other proprietary
`processors such as video graphic cards and math 40
`co-processors. These independent, stand-alone computers
`are idle for a significant portion of the day. For example, a
`personal computer owned at home may be idle or even off
`while the owner is away at work. The computer may also be
`idle at night while the owner is asleep. Personal computers 45
`at the office may only be utilized from 9 AM. in the morning
`till 5 P.M. in the evening. At any particular time, peak usage
`in one part of the world can be offset by low usage in a
`different part of the world. For example, periods of high
`computer usage in New York City may be night time in
`Tokyo when idle personal computers are readily available. It
`would be advantageous to find a way of utilizing this wasted
`computer resource.
`As WANs, such as the Internet, become more popular, the
`demand on the computational power of the computers which 55
`provide WAN services keeps increasing. Computers, includ(cid:173)
`ing servers, must perform many tasks including the provid(cid:173)
`ing and generating of WEB pages, compressing Moving
`Pictures Expert Group ("MPEG") and Joint Photographic
`Expert Group (" JPEG") images, and serving up WEB pages. 60
`These tasks and the exploding number of users place
`increasing demands on the computers at WAN service
`providers and Internet WEB sites. Service providers, such as
`American On-Line™ ("AOL") and Compuserve increas(cid:173)
`ingly must buy more powerful computers to service the 65
`additional members and the new content that is constantly
`being updated. These service providers could save on com-
`
`2
`puter costs if some of the computational requirements of
`their system could be serviced by personal computers owned
`by private individuals and other independent entities who
`subscribe to the Internet provider services.
`Any system which attempts to use PCs coupled to the
`Internet service providers ("ISP") to satisfy computational
`requirements must be dynamic and easily modifiable. Each
`computer connecting to the ISP may be independently
`owned and individual owners may frequently change their
`10 personal computer system characteristics. Furthermore, sub(cid:173)
`scribers with PCs are frequently being added to the ISP
`network, while other owners are dropping the ISP service.
`AOL, for example, has a "churn" rate of thousands of
`computers adding and dropping the service every year.
`Thus, there exists a need for a dynamic, accommodating
`system capable of assigning tasks required by Internet
`Service Provider to personal computers and coordinating
`transmission and completion of those tasks.
`
`SUMMARY OF IBE INVENTION
`The present invention is a method and apparatus for WAN
`computing including a central computer which coordinates
`tasks performed by a plurality of independent remote com(cid:173)
`puters. The central computer polls the remote computers as
`to time of day the remote computers will be available and
`computational capabilities of the remote computers. The
`central computer then matches tasks to be completed with
`remote computers based on the results of the polling and
`transmits the task to the assigned remote computers at the
`appropriate time.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The advantages of the present invention will become
`more readily apparent to those ordinarily skilled in the art
`35 after reviewing the following detailed description and
`accompanying drawings, wherein:
`FIG. 1 is an illustrative block diagram of one embodiment
`of a distributed system including a central computer and
`remote computers;
`FIG. 2 is an illustrative block diagram of the central
`computer and the information coordinated by the central
`computer coupled with a remote computer and the informa(cid:173)
`tion available on the remote computer;
`FIGS. 3A and 3B are illustrative block diagrams showing
`one example of a resources available information table and
`a tasks to be completed information table; and,
`FIG. 4 is an flow chart showing the steps taken by the
`central computer in managing the distribution of tasks to the
`50 remote computer;
`FIG. 5 is a flow chart illustrating one embodiment of the
`steps performed by the central computer management pro-
`gram.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`The present invention relates to a method and apparatus
`for distributing tasks from a central computer to remote
`computers over a wide area network. In the following
`description, some terminology is used to discuss the net(cid:173)
`work. A wide area network ("WAN") is a data network
`which is not restricted in terms of distance. Typical distances
`can be larger than 100 kilometers. A local area network
`("LAN") are data networks which are restricted in distance,
`typically distances between computers in a LAN are less
`than 500 meters. Typical LAN networks include Ethernet
`and Token Ring Networks.
`
`Netflix, Inc. - Ex. 1008, Page 000009
`
`

`

`6,098,091
`
`3
`Typically, a WAN is a collection of packet switching
`networks that are physically interconnected by protocol
`gateways. These networks use protocols that allow them to
`function as a large, composite network. The Internet is a
`WAN connecting thousands of disparate networks and 5
`industry, education, government, and research. The Internet
`network uses transmission control protocol/Internet protocol
`("TCP/IP") as a standard for transmitting information. TCP/
`IP is a set of communication protocols that support peer-to(cid:173)
`peer connectivity functions for WANs. The Internet protocol 10
`works in an Internet layer delivering Internet protocol pack-
`ets to the proper destinations. The Internet layer permits
`hosts to inject data packets into any network and have them
`travel independently to their intended destination
`(potentially on a different network). The packets may arrive 15
`in a different order than they were sent, in which case a
`higher level system must rearrange the data packets in the
`proper delivery order.
`FIG. 1 is an illustration of the computer network 100. The
`computer network 100 includes a central computer 104 and 20
`a plurality of remote computers 108, 112, 116 and 120. Each
`computer including both, the central computer and the
`remote computer may be a variety of different types of
`computers from different computer vendors e.g. a IBM®
`computer 108, an Apple® computer 116, and a Sun® 25
`workstation 112. However, in one embodiment as pictured,
`each computer is a personal computer ("PC") with indepen(cid:173)
`dent computer components including a single microproces(cid:173)
`sor. The independent computer components include a key(cid:173)
`board 122, a processor 134, a random access memory 128, 30
`a long term storage device 132 and a display device 136.
`Each computer may be coupled to other computers in the
`Internet network via a variety of communication techniques,
`including ISDN lines, typical telephone lines, cable
`modems, satellite transmission, or other emerging as well as 35
`established communication techniques. If standard analog
`telephone lines are used, a modem device 140 is used to
`convert the digital information into analog information for
`transmission along standard twisted pair telephone line.
`Typically, the computers are part of a WAN and may be 40
`separated by hundreds or even thousands of miles. Thus, it
`is also envisioned that the central computer may communi(cid:173)
`cate with remote computers using radio signals or other
`communication technologies.
`The central computer 104 executes a management pro(cid:173)
`gram 144 to coordinate operation of the network. The central
`computer preferably is a high performance PC. The central
`computer and the remote computers operate in a peer-to(cid:173)
`peer relationship, such that each computer requests time, and
`no computer exercises control over another computer. The
`peer-to-peer relationship allows the duties of the central
`computer 104 to be easily transferred to a remote computer.
`Thus, in a preferred embodiment, the assignments handled
`by the central computer may be passed from the central
`computer 104 to a remote computer such that former remote 55
`computer 112 acts as the central computer. In order to pass
`off the tasks of the central computer, the former central
`computer must transfer the scheduler including the tasks to
`be completed and the resources available to the remote
`computer 112.
`Management program 144 contains instructions executed
`by the central computer which polls the remote computers
`108, 112, 116 and 120 as to times of day when the remote
`computers are available to provide computing services to the
`central computer in a contractor relationship. The manage- 65
`ment program also determines remote computer system
`capabilities. The remote computer responses are processed
`
`4
`and tasks assigned to remote computers to be completed at
`times in which the remote computers agrees to be available
`to operate in a contractor relationship.
`FIG. 2 is an illustrative block diagram of the central
`computer 204 and the information coordinated by the central
`computer coupled with a remote computer 208 and the
`information available to the remote computer. In one
`embodiment, the central computer 204 is coupled to a
`modem 212 which converts information into a form appro(cid:173)
`priate for a telephone line 216. A second modem 220
`coupled to the remote computer converts the telephone
`signal back into a form appropriate for processing by the
`remote computer. The telephone line 216 may include
`routing routers and forwarding networks between central
`computer 204 and remote computer 208.
`Many protocols are available for connecting the central
`computer to the remote computer. In particular, packet based
`protocols are preferred. Such packet-based protocols include
`APPLETALK™ from Apple Computer, Inc. of Cupertino,
`Calif., ITUTX25 (from International Telecommunications
`Union Standard) or Frame Relay, and SPX/IPX from Novell
`of San Jose, Calif. In one embodiment, Integrated Services
`Digital Network ("ISDN") lines may be used to connect the
`central computer 204 with the remote computer 208. ISDN
`is a digital end-to-end telecommunication network that
`supports multiple services including, but not limited to voice
`and data. In a preferred embodiment of the invention, an
`Always On/Dynamic ISDN (AO/DI) is used. AO/DI is a
`networking service that provides an always-available con(cid:173)
`nection to packet-based data services through the WAN.
`Although the prior paragraph describes one method of
`implementing a connect-disconnect routine for connecting
`Internet coupled computers, other methods are also avail(cid:173)
`able. For example, satellite and cable modem hook-ups may
`be implemented.
`The central computer 204 runs management program 144
`which periodically polls remote systems 208 regarding the
`time of day when the remote system will be available to
`operate in a contractor relationship and the resources avail(cid:173)
`able 224 on the remote system 208. This information is
`transmitted back by the remote system 208 along the line
`216 to the central computer 204.
`The central system 204 executes a management program
`45 144 which includes a scheduler 228. The scheduler 228
`organizes tasks 232 that need to be completed with the
`resources available information 224 transmitted by the
`remote computer 208. The central computer then generates
`a schedule of tasks to be completed by the remote comput-
`50 ers.
`FIGS. 3A and 3B are block diagrams illustrating one
`example of how the resources available file 224 and the tasks
`file 232 might be organized. Specifically FIGS. 3A and 3B
`illustrate one embodiment of data fields used by the sched(cid:173)
`uler 304 to handle data from the resources available 308 and
`the tasks file 312. More specifically, FIG. 3A illustrates the
`tasks file 312 including a tasks to be completed field 313.
`Typical examples of tasks to be completed 312 include
`MPEG compression 314, JPEG compression 316, acting as
`60 a HyperText transfer protocol ("HTTP") server 318 serving
`Internet Web pages, and storing information on hard drives
`320. Each task to be completed field 313 has a correspond(cid:173)
`ing priority field 324 which indicates the importance of the
`tasks completion to the overall system. In order to support
`the concept of priority, two or more levels of importance
`must be specified. High priority tasks may be duplicated and
`sent to multiple remote computers to ensure robustness and
`
`Netflix, Inc. - Ex. 1008, Page 000010
`
`

`

`6,098,091
`
`5
`
`5
`prevent system failure if a particular remote computer fails
`to complete its task. Each task to be complete field 313 may
`also be associated with a benchmark rating field 328 includ(cid:173)
`ing a measure of computational requirements in a standard
`unit such as an ICOMP rating 328 (Intel computational
`rating) and an amount of time field 329 indicating the
`amount of time needed to complete the task at the given
`benchmark rating. Other examples of benchmark ratings that
`may be used include a millions of instructions per second
`("MIPS") rating or a benchmark tailored for the specific task
`such as JPEG pixels per second. This information can be
`used to more appropriately assign assignment tasks to be
`completed to the appropriate remote computers using the
`resources available table 308. Tasks to be completed fields
`313 may also be associated with other computational needs
`such as memory requirements and co-processor require(cid:173)
`ments. Such data may be contained in additional data fields
`in the tasks file 312.
`Referring now to FIG. 3B, scheduler 304 coordinates the
`tasks file 312 with the resource available file 308. The 20
`information in resource available file 308 of FIG. 3B was
`transmitted by the remote computers to the central computer.
`Each remote computer may be associated with a machine
`identification (e.g. Internet address), a computer serial num(cid:173)
`ber or a phone number at which the remote computer can be
`reached. This information is indexed in a computer identifier
`field 332. Corresponding with the computer identifier field
`332 may be other data fields such as a time available field
`336 indicating when the remote computer is available. The
`time when the remote computer is available should be given
`in a worldwide standardized time frame, such as the time of
`day in Greenwich mean time. Other possible corresponding
`data fields include the benchmark rating field 338 indicating
`hardware capabilities available at the remote computer, the
`processor field 340 indicating the type of processor used by
`the remote computer, the RAM field 342 indicating RAM
`available on the remote computer, the memory field 344
`including memory available for long term storage 344, the
`number of hops to an Internet backbone field 345 (indicating
`the number of hops which is the number of routers or
`switches between the backbone and the remote computer),
`the transmission bandwidth field 346 indicating the trans(cid:173)
`mission bandwidth of communications with the remote
`computer and other data fields 347 which may indicate other
`hardware such as processing cards that may be available. All
`of this information may be coded so that the central com(cid:173)
`puter can appropriately assign a task to be completed to
`remote computers most efficiently able to complete the task.
`At the times when the remote computer has agreed to
`operate in a contractor relationship, the central computer
`using the management program will follow scheduler
`instructions and will send the assigned task to the remote
`computer.
`FIG. 4 is a flow diagram of the processes executed by the
`central computer 104. In step 404, the central computer polls
`the remote computer to determine whether the remote com(cid:173)
`puter still subscribes to the ISP Service, the time of day the
`remote will be available to operate in a contractor relation(cid:173)
`ship and the hardware specifications of the remote computer.
`The polling should occur on a periodic basis to account for 60
`consumers dropping and adding the ISP service. Preferably,
`the polling occurs on a daily basis to coincide with the
`billing and determination of who is still a member of the ISP
`service. The information on when the remote computer will
`be available to operate in a contractor relationship may have 65
`been input by the contracting PC owner or the information
`may be drawn from past availability patterns subject to
`
`6
`override by the PC owner. The polling may also commit the
`contracting PC owner not to change the PC configuration for
`a 24 hour period. The specifications retrieved during polling
`may include a variety of data, including but not limited to
`long term storage memory, microprocessor, and other per(cid:173)
`sonal computer components. The answers to the queries may
`be programmed in diagnostic routines which run on the
`remote computer and relay the information to the central
`computer or the answers may be entered by the owner of the
`10 remote computer. The remote computer is designed to be
`completely independent of the central computer.
`In Step 408, the central computer organizes the tasks to be
`completed in order of priority and system computational
`requirements taking into account remote computer availabil-
`15 ity.
`In Step 412, the central computer assigns the tasks to
`particular remote computers. The tasks are assigned consid(cid:173)
`ering the resources available to the remote computer and the
`time of day that the remote computer is available to operate
`in a contractor relationship. High priority tasks may be
`assigned to two or more separate remote computers to
`improve the robustness of the system. The remote computer
`assignments also take into account the computational
`requirements of the task and assign computationally inten-
`25 sive tasks to computers with appropriate hardware. For
`example, a computationally intensive task might be assigned
`to a computer with a PentiumPro TM processor, while a HTTP
`server site task might be assigned to a computer with
`significant long term storage memory capabilities (e.g. a
`30 large hard disk drive).
`At a scheduled time when the remote computer is avail(cid:173)
`able to operate in a contractor relationship, the central
`computer arranges to connect the remote computer to the
`Internet and transfers the instructions and data necessary for
`35 the remote computer to complete the task (Step 416). The
`connection may be achieved by a variety of means, one
`possible means is the AO/DI line, although other embodi(cid:173)
`ments are also available. After transferring the data, the
`remote computer may be disconnected from the central
`40 computer (Step 420). In some embodiments, for example
`satellite or cable modem, the connect and disconnect steps
`may be unnecessary because the remote computer and the
`central computer are always connected. During the period in
`which the remote computer is completing the tasks assigned
`45 by the central computer, the connection between the remote
`computer and the central computer is reestablished periodi(cid:173)
`cally to verify the status of the tasks and confirm that the task
`is being completed on schedule (Step 424). If during one of
`the verifications sessions, the remote computer fails to
`50 respond or indicates that there is difficulty completing the
`assigned tasks, the central computer will reassign and
`retransmit the task to another back-up remote computer
`(Step 428). Otherwise, the remote computer will complete
`the task and reconnect to the central computer to inform the
`55 central computer on the completion of the task, at which
`time the central computer will instruct the remote computer
`whether to store the information for future retrieval or to
`transmit the processed information back to the central com-
`puter or other designated computer (Step 432).
`Finally, after completion of the task, the central computer
`will credit a payment to an account corresponding to the
`remote computer for the computer time spent by the remote
`computer on the allotted task. A billing program may take
`into account the processing time used, the storage space
`used, and even the time of day at which the task was
`completed (e.g., remote computers which performed tasks
`during peak computing times may receive more credit than
`
`Netflix, Inc. - Ex. 1008, Page 000011
`
`

`

`6,098,091
`
`10
`
`7
`remote computers which complete the tasks late in the
`night). The billing program may periodically update the
`established client accounts.
`FIG. 5 is a flow chart illustrating the processing steps
`executed by the central computer management program in 5
`accordance with one embodiment of the present invention.
`The embodiment of FIG. 5 is particularly useful in very
`dynamic situation where new tasks are constantly being
`assigned and it is more difficult to schedule ahead all tasks
`and match with appropriate remote computers.
`In the embodiment shown in FIG. 5, the central computer
`sends a task request to the management program of this
`central computer (Step 504). The management program
`checks the resource table for connected or